Résumé technique : Identification du meilleur bras avec un regret minimal

Formulation du problème

Cet article introduit et étudie le problème de l'Identification du Meilleur Bras (Best Arm Identification - BAI) avec un Regret Minimal dans le cadre des bandits multi-bras stochastiques. Le contexte est celui d'un scénario à confiance fixe où un agent interagit avec $K$ bras, chacun étant associé à une distribution de récompense issue d'une famille exponentielle à paramètre unique connue. L'agent doit identifier l'unique bras optimal (celui ayant la moyenne la plus élevée) avec une probabilité d'au moins $1-\delta$.

Contrairement au BAI à confiance fixe standard, qui se concentre uniquement sur la minimisation de la complexité d'échantillonnage (le nombre de tirages requis pour atteindre le niveau de confiance), ou à la minimisation du regret standard, qui se concentre sur la maximisation de la récompense cumulée sur un horizon fixe, ce problème cherche à minimiser le regret cumulé attendu jusqu'au temps d'arrêt $\tau_\delta$, sous la contrainte que la probabilité d'erreur soit au plus de $\delta$. Les auteurs soutiennent que dans les applications pratiques comme les essais cliniques, le coût de l'exploration n'est pas uniforme ; tirer un bras sous-optimal entraîne un « regret » proportionnel à son écart de sous-optimalité. Par conséquent, un processus expérimental « responsable » devrait prioriser la minimisation de ce regret cumulé tout en garantissant l'identification correcte du meilleur bras.

Méthodologie et conception de l'algorithme

Pour répondre à ce problème, les auteurs proposent l'algorithme Double KL-UCB (DKL-UCB). L'algorithme est conçu pour équilibrer les objectifs conflictuels d'identifier le meilleur bras (nécessitant une exploration suffisante des bras sous-optimaux) et de minimiser le regret (nécessitant l'exploitation de la meilleure estimation actuelle).

Les composants clés de DKL-UCB incluent :

1. Bornes de confiance duales : L'algorithme maintient deux bornes supérieures de type Kullback-Leibler (UCB) distinctes pour chaque bras $i$ à l'instant $t$ :
   • $f$-UCB ($U^f_i(t)$) : Utilise une fonction d'exploration $f(t) = 3 \log t$. Cette borne est conçue pour identifier agressivement le meilleur bras actuel (le « leader »).
   • $g$-UCB ($U^g_i(t)$) : Utilise une fonction d'exploration $g(\delta, t) = \log(2Kt^2/\delta)$. Cette borne est adaptée à l'exigence de confiance fixe et aide à distinguer le meilleur bras des autres bras sous-optimaux.
2. Sélection de candidats : À chaque étape, l'algorithme identifie deux bras candidats :
   • $A^f_t$ : Le bras ayant la plus haute $f$-UCB.
   • $A^g_t$ : Le bras ayant la plus haute $g$-UCB, en excluant $A^f_t$.
3. Échantillonnage randomisé : L'agent tire soit $A^f_t$, soit $A^g_t$ en fonction d'un lancer de pièce biaisé avec une probabilité $\beta(\delta) = 1 - \min\{1/\log\log(1/\delta), 1/2\}$. Lorsque $\delta \to 0$, $\beta(\delta) \to 1$, ce qui signifie que l'algorithme favorise de plus en plus le bras identifié par la $f$-UCB (le bras probablement optimal) pour minimiser le regret, tout en tirant occasionnellement le candidat de la $g$-UCB pour s'assurer que les bras sous-optimaux sont suffisamment explorés afin de satisfaire la contrainte de confiance.
4. Règle d'arrêt : L'algorithme s'arrête lorsque la borne inférieure (LCB) du leader de la $f$-UCB dépasse la $g$-UCB du second, garantissant ainsi que le niveau de confiance $\delta$ est respecté.

Résultats théoriques

1. Bornes inférieures de l'information théorique

Les auteurs établissent une borne inférieure fondamentale dépendante de l'instance pour le regret cumulé attendu de tout algorithme $\delta$-PAC (Probably Approximately Correct).

• Borne inférieure de regret : Pour tout algorithme $\delta$-PAC, le regret cumulé attendu satisfait :
  $$\liminf_{\delta \to 0} \frac{E_\mu[R(\tau_\delta)]}{\log(1/\delta)} \geq I^*(\mu)$$
  où $I^*(\mu) = \sum_{i=2}^K \frac{\Delta_i}{\text{kl}(\mu_i, \mu_1)}$. Ici, $\Delta_i$ est l'écart de sous-optimalité et $\text{kl}$ est la divergence KL.
• Résultat d'impossibilité (Complexité d'échantillonnage) : L'article prouve que l'obtention de l'optimalité asymptotique en termes de regret nécessite une complexité d'échantillonnage super-logarithmique. Plus précisément, tout algorithme asymptotiquement optimal doit satisfaire $E_\mu[\tau_\delta] = \omega(\log(1/\delta))$. Cela souligne une tension fondamentale : pour minimiser le regret, l'agent doit tirer le bras optimal beaucoup plus souvent que le nombre logarithmique minimal requis pour simplement le distinguer, ce qui conduit à une complexité d'échantillonnage totale strictement supérieure à $\Theta(\log(1/\delta))$.

2. Performance de l'algorithme

Les auteurs prouvent que DKL-UCB atteint l'optimalité asymptotique en termes de regret cumulé :
$$\limsup_{\delta \to 0} \frac{E_\mu[R(\tau_\delta)]}{\log(1/\delta)} \leq I^*(\mu)$$
Ceci correspond à la borne inférieure, confirmant que DKL-UCB est optimal pour le problème du BAI avec regret minimal.

Concernant la complexité d'échantillonnage, l'algorithme atteint :
$$E_\mu[\tau_\delta] = \omega(\log(1/\delta)) \cap o\left(\log(1/\delta) \cdot (\log\log(1/\delta))^2\right)$$
Cela indique que bien que la complexité d'échantillonnage soit super-logarithmique (comme prouvé nécessaire), elle est presque optimale, ne s'écartant de la borne inférieure que par un petit facteur multiplicatif de $(\log\log(1/\delta))^2$.

Contributions clés et importance

L'article apporte plusieurs contributions distinctes à la littérature sur les bandits multi-bras :

1. Formulation du problème : Il définit et motive formellement le problème du BAI avec regret minimal, comblant le fossé entre la pure minimisation de la complexité d'échantillonnage et la pure minimisation du regret. Il soutient que dans les contextes réels où les actions sous-optimales ont des coûts variables (regrets), minimiser le regret cumulé pendant la phase d'exploration est un objectif plus éthique et plus pratique.
2. Limites fondamentales : Il établit la première borne inférieure dépendante de l'instance pour le regret cumulé attendu dans le cadre du BAI à confiance fixe. Crucialement, il fournit un résultat d'impossibilité montrant que la minimisation du regret dans le BAI nécessite intrinsèquement une complexité d'échantillonnage d'ordre supérieur par rapport au BAI standard, élucidant la « tension » entre ces deux objectifs.
3. Innovation algorithmique : La conception de DKL-UCB, qui utilise deux bornes de confiance distinctes et une stratégie de sélection randomisée spécifique, offre une approche novatrice pour équilibrer l'exploration et l'exploitation dans le contexte du BAI.
4. Analyse comparative : L'article démontre que les algorithmes optimisés pour la minimisation de la complexité d'échantillonnage (comme Track-and-Stop) ne minimisent pas nécessairement le regret, et vice versa. À travers l'analyse théorique et les expériences numériques, il montre que DKL-UCB surpasse significativement les algorithmes de BAI standard en termes de regret cumulé, tout en maintenant une complexité d'échantillonnage quasi optimale.

Validation expérimentale

Des expériences numériques sur des instances de bandits de Bernoulli confirment les résultats théoriques. DKL-UCB obtient systématiquement un regret cumulé plus faible que Track-and-Stop et Top-Two Thompson Sampling (TTTS), particulièrement lorsque le niveau de confiance $\delta$ devient petit. Inversement, comme prévu, Track-and-Stop et TTTS présentent une complexité d'échantillonnage plus faible, validant le compromis théorique identifié dans l'article.

Conclusion

L'article conclut que bien que la minimisation du regret et la minimisation de la complexité d'échantillonnage dans le BAI soient des objectifs distincts avec des stratégies optimales différentes, ils sont profondément interconnectés. L'algorithme proposé DKL-UCB navigue avec succès dans ce compromis, atteignant la borne fondamentale du regret tout en n'infligeant qu'une pénalité marginale en termes de complexité d'échantillonnage. Les auteurs notent que des travaux futurs pourraient explorer les bornes non-asymptotiques et la performance du regret dans le pire des cas, ainsi que les limites fondamentales précises de la complexité d'échantillonnage sous des contraintes de regret relaxées.