Fundamental Limitations of Fixed-Budget Best-Arm Identification

Résumé Technique : Limitations Fondamentales de l'Identification du Meilleur Bras à Budget Fixe

Formulation du Problème
L'article traite du problème de l'Identification du Meilleur Bras (Best-Arm Identification - BAI) à budget fixe, également connu sous le nom de Sélection et Classement (Ranking and Selection). Dans ce cadre, un décideur échantillonne séquentiellement $K$ bras, chacun générant des récompenses indépendantes issues d'une distribution dont la moyenne $\mu_k$ est inconnue. L'objectif est d'identifier le bras possédant la plus grande moyenne, $i^*(\mu)$, en utilisant un budget total de tirage fixe $T$. La métrique de performance est la probabilité d'identification incorrecte, $p_{\mu, T}$, plus précisément son taux de décroissance exponentielle lorsque $T \to \infty$ :
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

La question théorique centrale est de savoir s'il existe une « complexité » pour ce problème. Une complexité est définie comme une fonction $\Gamma^*(\mu)$ qui satisfait deux conditions :

1. Borne Supérieure Universelle : Pour tout algorithme et toute instance $\mu$, le taux de décroissance de l'erreur est borné au-dessus par $\Gamma^*(\mu)$.
2. Achèvement Uniforme : Il existe un algorithme unique qui atteint ce taux de décroissance $\Gamma^*(\mu)$ uniformément pour toutes les instances du problème $\mu$.

L'article examine si le taux de l'oracle statique, $\Gamma^*_{so}(\mu)$, sert de complexité. L'oracle statique représente le taux de décroissance d'erreur optimal réalisable par une stratégie non adaptative qui connaît les vraies moyennes $\mu$ à lient de l'avance et alloue des échantillons à des proportions fixes pour maximiser le taux de décroissance. Bien que des algorithmes adaptatifs aient été conçus pour que les proportions d'échantillonnage convergent vers ces proportions statiques optimales, il restait une question ouverte pour savoir si un algorithme adaptatif pouvait égaler le taux de décroissance de l'oracle statique de manière uniforme pour toutes les instances.

Méthodologie
Les auteurs utilisent un raisonnement par l'absurde pour démontrer qu'aucun algorithme unique ne peut atteindre le taux de l'oracle statique uniformément pour toutes les instances lorsque $K \geq 3$. La méthodologie repose sur les composantes suivantes :

1. Rapports de Difficulté : En suivant Degenne (2023), l'article utilise le rapport de difficulté $R_{H, \infty}(A, \mu)$, qui mesure la performance d'un algorithme $A$ par rapport à une fonction de difficulté de référence $H(\mu)$. Si une complexité existe, il doit exister un algorithme où le supremum de ce rapport sur toutes les instances est $\leq 1$.
2. Théorème 1 (Degenne 2023) : La preuve exploite une inégalité clé de Degenne (2023) qui borne la performance de toute famille d'algorithmes adaptatifs cohérents. Pour toute référence $H$ et un ensemble d'instances alternatives $D(\mu)$, l'inverse du pire rapport de difficulté est borné par un problème d'optimisation statique sur les proportions d'échantillonnage $\omega$ :
   $$\left( \sup_{\lambda \in D(\mu)} R_{H, \infty}(A, \lambda) \right)^{-1} \leq \sup_{\omega \in \Delta_K} \inf_{\lambda \in D(\mu)} \left( H(\lambda) \sum_{k=1}^K \omega_k \text{KL}(\mu_k, \lambda_k) \right)$$
3. Construction d'Instances : Pour prouver la non-existence de complexité, les auteurs construisent une instance « de base » spécifique $x$ et une famille d'instances alternatives $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$.
   • $\lambda_A$ : Diffère de $x$ uniquement dans les bras 1 et 2. Distinguer $x$ de $\lambda_A$ nécessite un échantillonnage important des bras 1 et 2.
   • $\lambda_{B,j}$ (pour $j \in \{3, \dots, K\}$) : Diffère de $x$ uniquement dans le bras $j$, faisant de l'arm $j$ le nouveau meilleur bras. Distinguer $x$ de $\lambda_{B,j}$ nécessite un échantillonnage important du bras $j$.
   • La construction garantit que les bras les plus « difficiles » à distinguer varient selon la famille. Une allocation d'échantillonnage $\omega$ unique ne peut pas être simultanément optimale pour distinguer $x$ de tous les membres de $D(x)$ car l'information requise est concentrée sur des ensembles de bras disjoints.

Résultats Clés
L'article établit un résultat négatif fondamental pour le BAI à budget fixe :

• Récompenses Gaussiennes : Pour $K \geq 3$ bras avec des récompenses gaussiennes (variance 1), les auteurs prouvent que pour toute famille d'algorithmes cohérents $A$, il existe une instance $\mu$ telle que le rapport de difficulté relatif à l'oracle statique dépasse 1. Spécifiquement :
  $$\inf_{A \in \mathcal{C}_{cons}} \sup_{\mu} R_{H_{so}, \infty}(A, \mu) \geq 1 + \sum_{j=3}^K \frac{1}{(1 + \sqrt{j-1})^2} > 1 + \frac{1}{8} \log(K)$$
  Cette borne inférieure est strictement supérieure à 1 pour tout $K \geq 3$, prouvant qu'aucun algorithme ne peut égaler uniformément l'oracle statique.

• Généralisation aux Familles Exponentielles Naturelles (NEF) : Le résultat est étendu à toute famille exponentielle naturelle (NEF) à un paramètre. En utilisant une approximation quadratique locale de la divergence de Kullback-Leibler (KL), les auteurs montrent que le résultat gaussien implique la même limitation pour toutes les NEF régulières à un paramètre.

• Réponse à la Question Ouverte : Ce travail répond définitivement à la question posée par Qin (2022) et formalisée par Degenne (2023) : le BAI à budget fixe n'admet pas de complexité pour $K \geq 3$. Bien que l'oracle statique fournisse une borne inférieure sur le taux de décroissance de l'erreur, aucun algorithme adaptatif unique ne peut atteindre cette borne uniformément à travers toutes les instances du problème.

Signification et Revendications
L'article prétend résoudre une lacune théorique fondamentale dans la compréhension du BAI à budget fixe.

• Limitation de l'Adaptativité : Il démontre que la convergence des proportions d'échantillonnage vers l'oracle statique (un objectif de conception courant pour les algorithmes adaptatifs) est insuffisante pour garantir l'égalité avec le taux de décroissance de l'oracle statique. Le « prix de l'adaptativité » dans le cadre du budget fixe est qu'un algorithme ne peut pas être optimal pour toutes les instances simultanément.
• Portée : Ce travail comble une lacune dans la littérature pour $3 \leq K < e^{80/3}$ pour les récompenses gaussiennes et étend la non-existence de complexité à toutes les NEF à un paramètre.
• Frontière Théorique : Ce travail établit que le taux de l'oracle statique n'est pas une complexité universelle pour le BAI à budget fixe lorsque $K \geq 3$. Les auteurs suggèrent que cela implique la nécessité de cibles ou de références théoriques alternatives, puisque l'oracle statique ne peut être atteint uniformément.

L'article ne propose pas de nouveaux algorithmes pour surmonter cette limitation, ni ne suggère d'applications spécifiques au-delà des implications théoriques pour la Sélection-et-Classement et les Bandits Multi-Bras. La contribution est strictement un résultat négatif définissant les limites fondamentales de ce qui est réalisable dans ce cadre.