Résumé Technique : Tree-Guided Identify-Then-Exploit (TG-ITE)

Formulation du Problème

L'article traite du problème des bandits de duel stochastiques à $N$ bras sous l'hypothèse du vainqueur de Condorcet. Dans ce cadre, un apprenant sélectionne des paires de bras $(i, j)$ et observe un résultat binaire indiquant quel bras l'emporte, régi par une matrice de préférences inconnue $P$. L'hypothèse centrale est l'existence d'un vainqueur de Condorcet unique $a^\star$ tel que $P(a^\star, j) > 1/2$ pour tout $j \neq a^\star$, tandis que les préférences entre les bras non-gagnants peuvent être cycliques.

L'étude se concentre sur l'unification de trois objectifs distincts au sein de ce même cadre :

1. Identification du Meilleur Bras (BAI - Best Arm Identification) : Retourner $a^\star$ avec une haute confiance ($1-\delta$) à un temps d'arrêt dépendant des données.
2. Minimisation du Regret Faible (Weak Regret) : Minimiser le regret cumulé où un tour incurre un regret nul si au moins l'un des deux bras choisis est $a^\star$.
3. Minimisation du Regret Fort (Strong Regret) : Minimiser le regret où un tour incurre un regret nul uniquement si les deux bras choisis sont $a^\star$ (auto-jeu ou self-play).

La question de recherche centrale est de savoir si un cadre algorithmique unifié peut atteindre des performances optimales pour les trois objectifs simultanément, en surmontant le compromis traditionnel entre l'exploration (nécessaire pour le BAI) et l'exploitation (nécessaire pour la minimisation du regret).

Méthodologie : Tree-Guided Identify-Then-Exploit (TG-ITE)

La solution proposée, TG-ITE, adopte un paradigme Identify-Then-Exploit (Identifier puis Exploiter). Elle découple le problème en une phase d'identification partagée suivie de stratégies d'exploitation spécifiques à l'objectif.

1. Primitif d'Identification Partagé : TREEASCENT

L'innovation centrale est un algorithme d'identification guidé par un arbre appelé TREEASCENT. Contrairement aux stratégies classiques d'« Explore-Then-Commit » (ETC) qui sont souvent sous-optimales en termes de regret cumulé, TREEASCENT utilise une structure d'arbre binaire équilibrée et déterministe pour guider la recherche du vainqueur de Condorcet.

• Mécanisme : En partant d'un bras arbitraire $b$, l'algorithme remonte le chemin de l'ancêtre d'un arbre binaire fixe. À chaque niveau $h$, il effectue un tournoi d'élimination directe sur un « bloc de frères » de bras (bras nouvellement attachés à ce niveau) pour trouver un représentant.
• Fusion : Le représentant du bloc de frères est ensuite comparé au « champion » actuel (le vainqueur du niveau précédent) à l'aide d'un test par paire séquentiel (DUELTEST).
• Efficacité : En allouant des budgets de confiance proportionnels à la taille des blocs de frères (tailles croissant géométriquement), l'algorithme identifie un incumbent à haute confiance avec une complexité d'échantillonnage de $O(N)$. Ceci est réalisé sans nécessiter d'hypothèses plus fortes comme la transitivité stochastique forte ou l'inégalité triangulaire stochastique, en s'appuyant uniquement sur l'existence du vainqueur de Condorcet et un écart global $\Delta$.

2. Stratégies d'Exploitation Spécifiques à l'Objectif

Une fois qu'un incumbent à haute confiance est identifié via TREEASCENT, le cadre passe à des politiques d'exploitation spécifiques :

• Pour le BAI (TG-ITE-BAI) : L'algorithme exécute simplement TREEASCENT et s'arrête en retournant le bras identifié. Cela atteint une complexité d'échantillonnage de $O(N)$, correspondant à la borne inférieure théorique pour le BAI.
• Pour le Regret Faible (TG-ITE-WEAK) : L'algorithme utilise TREEASCENT comme un « warm start » (démarrage à chaud) à confiance constante pour trouver un vainqueur initial. Il emploie ensuite une stratégie de type « Winner-Stays » (le vainqueur reste) appelée SCREENANDREPLACE. Dans chaque époque, l'incumbent actuel est examiné face à tous les challengers. Si un challenger semble battre l'incumbent, un tournoi de remplacement est organisé. Cette approche atteint un regret faible de $O(N)$, améliorant les résultats précédents de $O(N \log N)$.
• Pour le Regret Fort (TG-ITE-STRONG) : L'algorithme identifie un incumbent fiable via TREEASCENT puis engage un auto-jeu (comparaison de l'incumbent contre lui-même).
  • Horizon Connu : Exécuter TREEASCENT avec une confiance $1/(H+1)$, puis auto-jeu.
  • Horizon Indéfini (Anytime) : Entrelacer des passes d'identification de plus en plus confiantes avec des blocs d'auto-jeu de plus en plus longs.
  • Cela atteint un regret fort de $O(N \log T)$, égalant les algorithmes spécialisés de regret fort.

Principales Contributions et Résultats

1. Cadre Unifié

TG-ITE est le premier cadre qui unifie le BAI, le regret faible et le regret fort dans les bandits de duel en utilisant un primitif d'identification partagé. Il démontre que le compromis entre l'identification et la minimisation du regret est « bénin » dans le contexte des bandits de duel grâce à la capacité d'utiliser un bras pour l'exploration et un autre pour l'exploitation.

2. Amélioration de la Complexité d'Échantillonnage et des Bornes de Regret

• BAI : Atteint une complexité d'échantillonnage de $O(N)$ sans exiger de transitivité stochastique forte ou d'hypothèses d'ordre total, égalant les meilleurs résultats connus pour le BAI.
• Regret Faible : Atteint un regret faible de $O(N)$, comblant l'écart de $O(\log N)$ trouvé dans les approches d'optimisation conjointe précédentes (ex. Ma et al., 2025) et égalant les meilleures bornes indépendantes de l'instance.
• Regret Fort : Atteint un regret de $O(N \log T)$, égalant les garanties des algorithmes spécialisés comme WS-S et RUCB.
• Optimisation Conjointe : Le cadre permet l'optimisation simultanée du BAI et du regret faible, atteignant des garanties de $O(N)$ pour les deux, éliminant les facteurs sous-optimaux de $O(\log N)$ présents dans les travaux antérieurs.

3. Garanties Théoriques

L'article fournit des preuves rigoureuses de la correction et du coût de TREEASCENT et des phases d'exploitation ultérieures.

• Théorème 1 : TREEASCENT identifie le vainqueur de Condorcet avec une probabilité $1-\epsilon$ en utilisant $O(N)$ comparaisons.
• Théorème 2 : Le regret faible de TG-ITE-WEAK est borné par $O(N/\Delta^2)$, ce qui est linéaire en $N$ et indépendant de l'horizon temporel $T$.
• Théorèmes 3 & 4 : Les bornes de regret fort sont de $O(N \log T)$ pour les horizons connus et inconnus.

4. Extensions

L'article présente également une Extension Budgétisée à Écart Connu (Section 5). Si une borne inférieure $g$ sur l'écart de Condorcet est connue, l'algorithme peut remplacer le DUELTEST de type anytime par un test à budget fixe. Cela supprime le facteur $\log(1/\Delta)$ des bornes, fournissant des budgets de comparaison déterministes et des garanties plus serrées, bien qu'au prix de la connaissance préalable de l'écart.

Validation Expérimentale

Les auteurs évaluent TG-ITE par rapport à des bases représentatives (incluant WS-W, WS-S, RUCB, WR-TINF et WSW-PE) sur des instances synthétiques conçues pour tester la non-transitivité et les écarts asymétriques.

• Mise à l'échelle du BAI : TG-ITE-BAI suit une progression quasi-linéaire avec $N$, surpassant les méthodes d'élimination par paire adaptatives sur des instances cycliques.
• Regret Faible : TG-ITE-WEAK atteint le regret cumulé le plus bas et plafonne rapidement, démontant l'efficacité de la stratégie de démarrage à chaud (warm-start).
• Regret Fort : TG-ITE-STRONG surpasse significativement les bases, la courbe s'aplatissant une fois l'auto-jeu commencé, confirmant le comportement théorique $O(N \log T)$.

Signification et Revendications

L'article affirme que TG-ITE fournit une preuve théorique que le compromis entre l'identification du meilleur bras et la minimisation du regret est relativement bénin dans les bandits de duel. En exploitant la structure unique des bandits de duel (sélection de deux bras), le cadre parvient à découpler avec succès les phases d'exploration et d'exploitation sans la sous-optimalité typiquement observée dans les bandits multi-bras standards.

Les auteurs soulignent que leur approche :

1. Unifie trois objectifs distincts sous un seul primitif d'identification réutilisable (TREEASCENT).
2. Améliore l'état de l'art pour le regret faible en supprimant le facteur $O(\log N)$ et en assouplissant l'hypothèse d'ordre total.
3. Égale les taux optimaux pour le BAI et le regret fort sans exiger d'hypothèses structurelles plus fortes (comme la transitivité stochastique forte) sur lesquelles reposaient les algorithmes optimaux précédents.

Le travail suggère que le modèle « Identify-Then-Exploit », lorsqu'il est guidé par une décomposition de tournoi basée sur un arbre, est une stratégie puissante et généralisable pour l'apprentissage basé sur les préférences.