Active Context Selection Improves Simple Regret in Contextual Bandits

Résumé technique : La sélection active de contexte améliore le regret simple dans les bandits contextuels

Formulation du problème
Cet article examine le problème du bandit à plusieurs bras contextuel dans un espace de contexte fini, où les contextes représentent des sous-populations distinctes (par exemple, des groupes démographiques). L'objectif d'apprentissage est défini par le regret simple pondéré par le contexte : après un budget expérimental fixe $T$, l'apprenant doit recommander un seul meilleur traitement pour chaque sous-population. La métrique de performance est l'écart espéré entre les traitements optimal et recommandé, pondéré par le vecteur de distribution de population $p$ sur les $k$ sous-populations.

L'étude distingue deux régimes d'échantillonnage :

1. Échantillonnage passif : Les contextes sont révélés aléatoirement selon la distribution fixe $p$, et l'apprenant choisit uniquement le traitement.
2. Échantillonnage actif : L'apprenant peut choisir activement à la fois la sous-population (contexte) et le traitement pour chaque tour.

L'analyse suppose un scénario de pire cas concernant les distributions de récompense, mais reste dépendante de l'instance par rapport à la distribution de contexte $p$. L'article se concentre sur le régime « riche en données » où l'horizon $T$ est significativement plus grand que le nombre de traitements $n$, le nombre de contextes $k$, et l'inverse de la probabilité minimale de contexte.

Méthodologie et cadre théorique

• Allocation optimale pour $p$ connu :
  Lorsque la distribution de sous-population $p$ est connue, les auteurs caractérisent l'allocation optimale du budget expérimental. Ils démontrent que pour le critère de regret simple de pire cas, les politiques sans historique (où la sélection de contexte dépend uniquement de $p$ et non de l'historique observé) suffisent à atteindre le taux minimax.

  • Taux passif : Sous échantillonnage passif, le regret évolue comme $\Theta(\sqrt{\frac{n}{T}} \|p\|_{1/2})$.
  • Taux actif : Sous échantillonnage actif, la stratégie optimale alloue des échantillons à la sous-population $j$ avec une probabilité proportionnelle à $p_j^{2/3}$. Cela atteint un taux de regret de $\Theta(\sqrt{\frac{n}{T}} \|p\|_{2/3})$.
  • L'écart : Le facteur d'amélioration de l'échantillonnage actif par rapport à l'échantillonnage passif est caractérisé par le rapport $R(p) = \|p\|_{1/2} / \|p\|_{2/3}$. Les auteurs montrent que pour des distributions fortement non uniformes, cet écart peut atteindre $\Theta(k^{1/4})$. L'allocation active optimale déplace les probabilités d'échantillonnage vers une distribution plus uniforme par rapport à $p$, augmentant ainsi l'exploration dans les plus petites sous-populations.

• Interventions budgétisées :
  L'article étend l'analyse à des scénarios où l'échantillonnage actif est coûteux, permettant à l'apprenant de choisir la sous-population dans seulement une fraction $\alpha$ des tours. Les auteurs formulent un problème d'optimisation sous contrainte visant à minimiser le regret, sous la contrainte que l'allocation $q$ doit satisfaire $q_j \geq (1-\alpha)p_j$. Ils dérivent une structure de seuil pour l'allocation optimale : les sous-populations ayant un grand $p_j$ peuvent rester à leur allocation passive si le budget est insuffisant pour les améliorer, tandis que d'autres sont boostées vers la proportion $p_j^{2/3}$. Ils identifient un budget minimum $\alpha_{\min}(p)$ nécessaire pour retrouver le taux optimal pleinement actif.

• $p$ inconnu (l'algorithme EETC) :
  Lorsque $p$ est inconnu, une politique pleinement active ne peut pas simplement adopter la règle $p^{2/3}$. Les auteurs proposent l'algorithme Explore-Explore-Then-Commit (EETC), qui équilibre trois phases :

  1. Exploration passive initiale : L'apprenant agit passivement pour estimer $p$.
  2. Échantillonnage passif continu : L'apprenant poursuit l'échantillonnage passif jusqu'à ce que le budget restant soit suffisant pour mettre en œuvre l'allocation active optimale basée sur l'estimation courante.
  3. Engagement : L'apprenant passe à l'échantillonnage actif en utilisant la distribution estimée pour allouer les tours restants.
     L'analyse théorique montre que pour des horizons grands, EETC atteint le même taux de regret simple que la politique active pleinement optimale avec $p$ connu, à des facteurs constants près.

Résultats clés et expériences

• Garanties théoriques : L'article établit des taux de regret serrés pour $p$ connu et inconnu. Il prouve que la sélection active de contexte améliore strictement l'échantillonnage passif, l'ampleur de l'amélioration dépendant de l'hétérogénéité de la distribution de contexte.
• Expériences synthétiques : Les expériences sur des données synthétiques confirment que l'écart de regret entre les politiques passives et actives s'élargit à mesure que le nombre de sous-populations $k$ augmente, s'alignant sur la borne théorique $\Theta(k^{1/4})$. L'algorithme EETC est montré pour correspondre étroitement aux performances de la politique active oracle ($p$ connu).
• Données réelles (MovieLens) : Les auteurs ont évalué leurs méthodes sur l'ensemble de données MovieLens 1M, traitant les recommandations de films comme des traitements et les groupes démographiques comme des sous-populations. Les résultats indiquent que les politiques passives produisent le regret le plus élevé. Tant la politique active ($p$ connu) que EETC surpassent significativement la référence passive, EETC approchant les performances de la politique active oracle à mesure que l'horizon augmente.

Signification et affirmations
L'article prétend quantifier la valeur spécifique de la sélection active de sous-populations dans la conception d'expériences et l'apprentissage de politiques. Sa contribution principale est de démontrer que la sélection active de sous-population améliore toujours les performances par rapport à l'échantillonnage passif, le gain étant substantiel lorsque la distribution de population est biaisée.

Les auteurs soulignent que leur travail comble le fossé entre les bandits contextuels standards (où les contextes sont environnementaux) et la conception d'expériences (où l'expérimentateur contrôle l'échantillon). En caractérisant la règle d'allocation optimale ($q_j \propto p_j^{2/3}$) et en fournissant un algorithme (EETC) qui s'adapte aux distributions inconnues sans sacrifier l'optimalité asymptotique, l'article offre un cadre rigoureux pour l'allocation efficace des ressources dans des populations hétérogènes. Le travail suggère que dans les scénarios où le recrutement ciblé ou l'échantillonnage contrôlé est réalisable, ignorer la capacité de sélectionner des contextes conduit à des recommandations de traitements sous-optimales.