Résumé technique : Apprentissage en ligne dans les MDP arborescents en traitant les politiques comme des bras de bandit

1. Définition du problème

L'article aborde le problème de l'apprentissage en ligne dans les Processus de Décision Markoviens Arborescents (T-MDP). Un T-MDP est défini comme un MDP à horizon fini où les transitions d'état forment un arbre enraciné dans un état initial $s_1$. Une caractéristique déterminante des T-MDP est que chaque état est accessible depuis $s_1$ par exactement une trajectoire état-action.

Ces structures émergent naturellement comme des abstractions de jeux à forme extensive avec rappel parfait joués contre des adversaires stationnaires. L'objectif spécifique d'apprentissage est de trouver une meilleure réponse à un adversaire inconnu mais stationnaire, par le biais d'interactions répétées au cours du jeu. L'agent ne connaît pas les probabilités de transition $p$, mais connaît la fonction de récompense $r$. L'agent interagit avec l'environnement en jouant des épisodes complets à partir de $s_1$, en observant les trajectoires, et en sélectionnant de nouvelles politiques pour les épisodes suivants.

L'article examine ce problème dans deux régimes :

1. PAC (Probablement Approximativement Correct) : L'objectif est de produire une politique $\pi$ telle que $V(\pi) \geq V(\pi^*) - \epsilon$ avec une probabilité d'au moins $1-\delta$, en minimisant le nombre d'épisodes (complexité en échantillons).
2. Minimisation du regret : L'objectif est de minimiser le regret cumulatif $R_T = \sum_{t=1}^T (V(\pi^*) - \mathbb{E}[V(\pi_t)])$ sur $T$ épisodes.

2. Méthodologie

L'innovation méthodologique centrale consiste à traiter chaque politique dans le T-MDP comme un bras de bandit. Bien que cette approche soit conceptuellement simple, le nombre de politiques déterministes est exponentiel par rapport au nombre d'états ($|A|^{|S|}$), rendant une implémentation naïve prohibitive en termes de calcul et de mémoire.

Pour surmonter cela, les auteurs proposent un cadre où les politiques partagent des données basées sur la structure arborescente du MDP.

2.1 Décomposition de la valeur

Les auteurs établissent que la valeur de n'importe quelle politique $\pi$, notée $V(\pi)$, peut être exprimée comme une combinaison convexe des retours terminaux. Plus précisément, $V(\pi) = \sum_{\sigma \in X(\pi)} q(\sigma) \cdot \rho(\sigma)$, où :

• $X(\pi)$ est l'ensemble des états terminaux cohérents avec la politique $\pi$.
• $q(\sigma)$ est la probabilité d'atteindre l'état terminal $\sigma$ depuis $s_1$ sous $\pi$.
• $\rho(\sigma)$ est la récompense cumulative actualisée le long du chemin vers $\sigma$.

Puisque la fonction de récompense est supposée connue, $\rho(\sigma)$ est connu. Le problème d'apprentissage se réduit à l'estimation des probabilités de transition $q(\sigma)$ pour les états terminaux. Crucialement, les données nécessaires pour estimer $q(\sigma)$ peuvent être collectées en jouant n'importe quelle politique cohérente avec $\sigma$, et pas seulement $\sigma$ lui-même.

2.2 Bornes de confiance et partage de données

L'article introduit une nouvelle borne de confiance pour $V(\pi)$ qui exploite les données partagées entre les politiques.

• Mécanisme de comptage : Pour un état terminal $\sigma$, l'algorithme suit $n_t(\sigma)$, le nombre d'épisodes où la politique jouée était cohérente avec $\sigma$, et $n_t^+(\sigma)$, le nombre de fois où $\sigma$ a été effectivement atteint.
• Comptage de politique : Pour une politique $\pi$, le "comptage de jeu" $n_t(\pi)$ est défini comme $\min_{\sigma \in X(\pi)} n_t(\sigma)$. Cela représente la disponibilité des données goulots d'étranglement pour l'évaluation de $\pi$.
• Estimateur : La valeur empirique $\hat{V}_t(\pi)$ est un estimateur sans biais construit à partir des probabilités empiriques $\hat{q}_t(\sigma) = n_t^+(\sigma) / n_t(\sigma)$.

2.3 Fondement théorique : Dépendance en cylindre négatif

Un défi technique majeur est que les variables aléatoires utilisées pour estimer $V(\pi)$ (issues de Bernoulli de l'atteinte des états terminaux) sont dépendantes car plusieurs politiques peuvent être jouées au cours du même épisode.

• Les auteurs prouvent que ces variables présentent une Dépendance en Cylindre Négatif (NCD).
• Ils introduisent des "variables jumelles" (variables de Bernoulli indépendantes ayant les mêmes moyennes) pour borner la déviation de l'estimateur dépendant.
• En utilisant l'Inégalité de Bernstein sur ces variables jumelles, ils dérivent des bornes de confiance (UCB et LCB) qui tiennent avec une forte probabilité. Cela permet d'appliquer des algorithmes de bandit (Lucb et Ucb) à l'ensemble exponentiel de politiques avec une mémoire et un calcul polynomiaux par étape.

2.4 Algorithmes

Les auteurs adaptent deux algorithmes de bandit standards :

1. Lucb-T : Une adaptation de l'algorithme Lucb pour le cadre PAC. Il sélectionne itérativement la politique avec la meilleure estimation de valeur et la politique avec la plus haute borne de confiance supérieure (UCB) parmi les autres, en les jouant jusqu'à ce qu'elles soient séparées par $\epsilon$.
2. Ucb-T : Une adaptation de l'algorithme Ucb pour la minimisation du regret. Il sélectionne la politique avec la plus haute UCB à chaque épisode.

Les deux algorithmes utilisent une procédure appelée PU (Politique avec la plus haute UCB) pour calculer efficacement la politique maximisante en $O(|S||A||k_{max}| + |\Sigma|)$ temps, évitant ainsi la nécessité d'énumérer toutes les politiques.

3. Contributions clés

1. Résultat analytique : Une nouvelle inégalité de concentration (Théorème 2) établissant des bornes de confiance pour les valeurs des politiques dans les T-MDP. Ce résultat gère la dépendance entre les données partagées par les politiques et pourrait avoir une applicabilité plus large à l'apprentissage dans des tâches séquentielles.
2. Conception algorithmique : Des algorithmes conceptuellement simples (Lucb-T et Ucb-T) qui traitent les politiques comme des bras de bandit mais exploitent la structure arborescente pour une implémentation efficace.
3. Garanties théoriques :
   • Complexité en échantillons (Théorème 9) : Une borne supérieure dépendante de l'instance pour Lucb-T qui somme un "terme d'écart" sur les états terminaux ($\sum_{\sigma \in \Sigma} \frac{1}{(\Delta^\epsilon_\sigma)^2}$) plutôt que sur les politiques.
   • Borne de regret (Théorème 10) : Une borne supérieure dépendante de l'instance pour Ucb-T, sommant également sur les états terminaux.
4. Validation empirique : Implémentation et tests sur trois jeux à information imparfaite de différentes échelles : Kuhn Poker (petit), Leduc Poker (moyen) et Reconnaissance Blind Tic-Tac-Toe (RBT, grand, avec des millions d'états).

4. Résultats

• Passage à l'échelle : Les algorithmes proposés surpassent constamment les alternatives disponibles (telles que Lucb vanilla, Bpi-Ucrl, Mdp-GapE, Mccfr et Uct) à mesure que la taille du problème augmente.
• Efficacité du partage de données : Sur les petits problèmes (Kuhn Poker à 3 cartes), Lucb vanilla (sans partage de données) est compétitif. Cependant, sur des variantes plus grandes (Kuhn Poker à 5 cartes, Leduc, RBT), les variantes "arbre" (Lucb-T, Ucb-T) surpassent nettement les références sans partage, démontrant la nécessité du partage de données pour la mise à l'échelle.
• Performance RBT : Les algorithmes gèrent avec succès RBT, un jeu comportant jusqu'à $2 \times 10^7$ états, où d'autres algorithmes PAC (Bpi-Ucrl, Mdp-GapE) ont échoué à bien performer.
• Théorie vs Pratique : Les expériences mettent en évidence des écarts entre les bornes théoriques et les performances pratiques, en particulier dans le cadre PAC où les temps d'arrêt peuvent être prohibitivement longs, suggérant que si les algorithmes sont théoriquement solides, un réglage pratique est essentiel.

5. Importance et affirmations

L'article affirme que sa contribution principale est la généralisation d'algorithmes de bandit bien connus (Lucb et Ucb) aux T-MDP en traitant les politiques comme des bras. L'importance réside dans :

• Surmonter la complexité exponentielle : Démontrer que l'on peut atteindre une complexité de mémoire et de calcul polynomiale malgré le nombre exponentiel de politiques, en utilisant la structure arborescente pour partager les données.
• Bornes dépendantes de l'instance : Fournir des garanties théoriques qui dépendent de l'"écart" aux états terminaux plutôt que du nombre total de politiques, offrant une analyse plus affinée que les bornes du pire cas.
• Applicabilité pratique : Valider l'approche sur des jeux à grande échelle à information imparfaite (spécifiquement RBT), qui servent de référence pour la faisabilité de l'apprentissage de meilleures réponses dans des problèmes complexes de prise de décision séquentielle contre des adversaires fixes.

Les auteurs notent que leur hypothèse d'une fonction de récompense connue est raisonnable pour leur domaine motivant (jeux à information imparfaite) mais constitue une restriction par rapport aux MDP généraux où les récompenses peuvent être inconnues. Ils reconnaissent également que si leurs bornes évitent la dépendance aux probabilités de visite des états (qui peuvent être arbitrairement petites dans les MDP généraux), cela est un avantage spécifique de la structure T-MDP et des récompenses connues.