Pure Exploration Beyond Reward Feedback: The Role of Post-Action Context

Résumé technique : Exploration pure au-delà de la rétroaction par récompense : le rôle du contexte post-action

Formulation du problème
Ce papier introduit une nouvelle variante du problème d'identification du meilleur bras (Best Arm Identification, BAI) dans le cadre à confiance fixe des bandits stochastiques à plusieurs bras (Multi-Armed Bandits, MAB). Dans ce cadre, qualifié de « BAI avec contexte post-action », l'apprenant sélectionne une action (bras) $X$ et observe non seulement la récompense $Y$, mais aussi un contexte intermédiaire post-action $Z$. Le contexte $Z$ est généré comme une conséquence de l'action choisie, distinguant ce problème des bandits contextuels standards où le contexte précède l'action.

Les auteurs analysent deux régimes structurels définis par la relation causale entre l'action, le contexte et la récompense :

1. Contexte séparateur : La récompense $Y$ dépend uniquement du contexte $Z$, rendant $X$ et $Y$ conditionnellement indépendants étant donné $Z$ ($P(Y|X, Z) = P(Y|Z)$). Dans ce cas, la distribution de la récompense est déterminée entièrement par le contexte observé.
2. Contexte non-séparateur : La récompense $Y$ dépend à la fois de l'action $X$ et du contexte $Z$ ($P(Y|X, Z) \neq P(Y|Z)$). Ici, le contexte fournit des informations supplémentaires mais ne constitue pas une statistique suffisante pour la récompense.

L'objectif est d'identifier le bras ayant la récompense espérée la plus élevée avec une probabilité d'erreur au plus $\delta$, tout en minimisant la complexité en échantillons (le nombre de rounds requis).

Méthodologie et algorithmes
Le papier dérive des bornes inférieures dépendantes de l'instance sur la complexité en échantillons pour les deux cadres et propose des algorithmes qui atteignent asymptotiquement ces bornes.

• Cadre séparateur :

  • Borne inférieure : Les auteurs dérivent une borne inférieure qui dépend des fréquences des contextes observés plutôt que des fréquences des bras tirés. Cela s'explique par le fait que, dans le cadre séparateur, toute observation d'un contexte spécifique $Z=j$ fournit des informations sur la récompense moyenne de ce contexte, indépendamment du bras qui l'a généré.
  • Algorithme (STS) : L'algorithme proposé « Separator Track and Stop » (STS) utilise une règle d'échantillonnage novatrice appelée G-tracking. Contrairement aux méthodes traditionnelles qui suivent les fréquences optimales de tirage des bras, le G-tracking suit les fréquences optimales d'observation des contextes. Il traite le problème comme une tâche d'apprentissage hors-politique active où l'apprenant sélectionne une distribution sur les bras pour atteindre une distribution cible sur les contextes. L'algorithme résout un problème d'optimisation convexe pour trouver les fréquences de contexte optimales et utilise une projection géométrique pour sélectionner la prochaine distribution de bras, assurant ainsi que les fréquences de contexte observées convergent vers la cible optimale.

• Cadre non-séparateur :

  • Borne inférieure : La borne inférieure dérivée prend en compte la distribution conjointe des actions et des contextes.
  • Algorithme (NSTS) : L'algorithme « Non-Separator Track and Stop » (NSTS) étend le cadre classique Track-and-Stop. Il emploie le D-tracking pour estimer et suivre les proportions optimales de tirage de bras spécifiques, en utilisant l'information conjointe des actions et de leurs contextes résultants pour affiner les estimations des moyennes de récompense.

Contributions clés

1. Définition du problème : Formalisation du BAI avec contexte post-action, distinguant les régimes structurels séparateur et non-séparateur.
2. Bornes théoriques : Dérivation de bornes inférieures dépendantes de l'instance sur la complexité en échantillons pour les deux régimes. La borne séparatrice est démontrée comme étant strictement plus serrée que les bornes dérivées en ignorant le contexte.
3. Conception d'algorithmes :
   • Introduction du G-tracking, une règle d'échantillonnage qui optimise directement les fréquences d'observation des contextes dans le cadre séparateur, en exploitant la géométrie de l'espace des contextes.
   • Extension du cadre Track-and-Stop au cadre non-séparateur (NSTS).
4. Analyse de la sous-optimalité : Démonstration théorique et empirique que les algorithmes ignorant le contexte post-action (comme le Track-and-Stop standard) sont strictement sous-optimaux. Dans le cadre séparateur, ignorer le contexte peut entraîner des augmentations arbitrairement grandes de la complexité en échantillons, même lorsque les écarts de récompense sont faibles, car cela échoue à exploiter la structure d'indépendance conditionnelle.
5. Analyse de réduction : Le papier analyse la réduction du problème séparateur aux bandits linéaires, montrant que de telles réductions augmentent la borne inférieure de la complexité en échantillons par rapport à l'approche directe proposée.

Résultats

• Théoriques : Les algorithmes proposés (STS et NSTS) sont prouvés $\delta$-corrects et atteignent l'optimalité asymptotique, correspondant aux bornes inférieures dérivées lorsque $\delta \to 0$.
• Empiriques : Des expériences sur des données synthétiques et des données réelles (journaux de recommandation KuaiSAR) démontrent des gains de performance significatifs.
  • Dans le cadre séparateur, STS surpasse drastiquement les bases de référence (Track-and-Stop et Lazy Track-and-Stop), qui échouent souvent à s'arrêter dans des horizons temporels raisonnables.
  • Dans le cadre non-séparateur, NSTS réduit considérablement le nombre d'échantillons requis par rapport au Track-and-Stop, qui ignore les informations contextuelles.
  • Les graphiques de suivi confirment que STS converge vers les fréquences de contexte optimales, tandis que les bases de référence échouent à s'aligner avec la stratégie optimale.

Signification et affirmations
Le papier affirme que l'exploitation du contexte post-action modifie fondamentalement la stratégie optimale pour l'exploration pure. Les auteurs soulignent que dans les scénarios où des observations intermédiaires (médiateurs) sont disponibles, les ignorer conduit à une inefficacité substantielle. Spécifiquement, dans le cadre séparateur, la capacité à regrouper les informations à travers différents bras générant le même contexte permet une identification beaucoup plus rapide du meilleur bras. Le travail met en évidence que les algorithmes BAI standards ne sont pas simplement sous-optimaux, mais peuvent être arbitrairement inefficaces dans ces environnements structurés. Le papier conclut que les travaux futurs pourraient traiter le cas où la matrice de probabilité du contexte est inconnue, notant que cela introduit des défis de non-convexité rendant la conception d'algorithmes efficaces difficile.