Résumé Technique : Apprentissage dans les Bandits Markoviens avec États Non-Observables et Époques de Décision Contraintes

1. Définition du Problème

Cet article traite du problème de la minimisation du regret dans les bandits markoviens sous deux contraintes spécifiques :

1. États Non-Observables : Le contrôleur n'observe pas l'état interne des bras (chaînes de Markov). Le seul retour disponible est la récompense générée par le bras activé. Cela correspond à un cadre de « feedback de bandit complet » où l'espace des états est caché.
2. Époques de Décision Contraintes : Le contrôleur ne peut pas changer de bras arbitrairement à chaque étape de temps. Au lieu de cela, le changement n'est autorisé qu'à des époques de décision ($\tau_i$) spécifiques, qui sont des temps d'arrêt déterminés par le flux de récompenses. Plus précisément, le contrôleur doit rester engagé sur un bras jusqu'à ce qu'un signal spécifique (par exemple, une récompense non nulle) soit reçu.

Les bras sont modélisés comme des Processus de Décision de Markov (MDP) où la dynamique de transition dépend de si le bras est actif ou passif. Le système évolue de telle sorte que les bras non activés continuent de transiter selon leurs noyaux passifs ($p^0_a$), tandis que les bras activés transitent selon les noyaux actifs ($p^1_a$).

2. Cadre d'Apprentissage et Référence

Les auteurs restreignent leur analyse à un benchmark de « regret pur ».

• Politiques Pures : Une politique est définie comme « pure » si elle sélectionne un seul bras du début à la fin de l'horizon d'apprentissage sans jamais changer.
• Définition du Regret : Le regret est la différence entre la récompense cumulée de l'algorithme d'apprentissage et la récompense cumulée de la meilleure politique pure (le bras ayant le gain asymptotique le plus élevé).

Motivation pour les Politiques Pures :
Bien que les politiques pures soient généralement sous-optimales pour les bandits agités (« restless bandits », où les bras non activés évoluent), les auteurs introduisent une classe de bandits appelés bandits agités auto-dégradants. Dans ces cas, si un bras est laissé inactif, son biais attendu (une mesure de la déviation par rapport à la moyenne) a tendance à diminuer ou à rester constant par rapport aux observations du contrôleur. L'article prouve que pour les bandits auto-dégradants, les politiques pures sont asymptotiquement optimales. Cette classe généralise les bandits « reposés » (où les bras inactifs se figent) et inclut des exemples agités non triviaux comme les canaux Gilbert-Elliott non préemptifs et les modèles de Nerlove-Arrow.

3. Méthodologie : UCB-NOM

L'article propose UCB-NOM (Upper Confidence Bound for Non-Observable Markovian bandits), un algorithme optimiste inspiré du principe UCB.

Composantes Clés de UCB-NOM :

1. Estimateur de Gain Empirique : L'algorithme estime le gain ($g_a$) d'un bras $a$ en faisant la moyenne des récompenses collectées lorsque ce bras était actif.
2. Construction de l'Indice Optimiste : Pour gérer la non-observabilité des états et les contraintes, l'algorithme construit une borne supérieure optimiste $\tilde{g}_a(t)$ pour le gain réel. Cet indice inclut :
   • La moyenne empirique des récompenses.
   • Un bonus d'exploration (intervalle de confiance) qui tient compte de :
     • Le nombre de tirages ($N_a(t)$).
     • Le nombre de fois où l'algorithme a basculé vers le bras $a$ (coût de commutation).
     • L'étendue du biais ($sp(b_a)$) de la chaîne de Markov du bras, qui quantifie la déviation maximale de la fonction de biais.
3. Truc de Doublement (Doubling Trick) : Pour satisfaire la propriété de « commutation rare » requise pour les garanties théoriques, l'algorithme emploie un truc de doublement. Une fois qu'un bras est sélectionné, il est joué jusqu'à ce que le nombre de ses visites double. Cela garantit que le nombre de commutations croît de manière logarithmique avec le nombre de tirages.

Défis Théoriques Abordés :

• Non-observabilité : Contrairement aux travaux précédents (ex. RCA par Tekin & Liu) qui reposent sur l'observation des états pour déclencher des cycles de régénération, UCB-NOM ne peut pas utiliser la régénération. À la place, il limite l'erreur en utilisant l'étendue du biais et le nombre de commutations.
• Époques Contraintes : L'algorithme doit tenir compte du délai entre les époques de décision. L'analyse suppose une borne ($C_\tau$) sur le temps attendu jusqu'à la prochaine époque de décision.

4. Résultats Clés et Garanties Théoriques

A. Bornes Inférieures (Impossibilité du Regret Logarithmique)

L'article établit que sans connaissance préalable de la structure du bandit, le regret logarithmique ($O(\log T)$) est inatteignable pour les algorithmes cohérents et à commutations rares.

• Théorème 4 : Pour tout algorithme cohérent et à commutations rares, le regret attendu est de l'ordre de $\omega(\log T)$ (super-logarithmique). Ceci est prouvé en construisant des modèles alternatifs qui sont indiscernables du modèle réel via les seules récompenses, mais qui possèdent des bras optimaux différents, forçant l'algorithme à tirer excessivement des bras sous-optimaux pour les distinguer.

B. Performance de UCB-NOM (Cas Général)

• Théorème 6 : UCB-NOM atteint un regret de $O(f(T)^2 \log T)$, où $f(T)$ est une fonction de proxy d'étendue qui diverge vers l'infini.
• Signification : En choisissant un $f(T)$ qui diverge arbitrairement lentement, UCB-NOM peut approcher arbitrairement près le régime idéal logarithmique, égalant ainsi la borne inférieure super-logarithmique.

C. Performance avec Connaissance Préalable (Étendue du Biais Bornée)

Si l'algorithme est fourni avec une borne supérieure $D$ connue sur l'étendue du biais de tous les bras (et le délai de l'époque de décision), la performance s'améliore considérablement.

• Théorème 8 (Dépendant de l'Instance) : Avec un proxy d'étendue fixe $f \equiv D$, UCB-NOM atteint un regret dépendant de l'instance de $O(\log T)$.
• Théorème 9 (Pire Cas) : Sous la même hypothèse d'étendue bornée, l'algorithme atteint un regret de pire cas de $O(\sqrt{T \log T})$.

D. Réglage et Paramètres de Confiance

L'article analyse le choix du paramètre de confiance $\delta(t)$. Il suggère qu'être « sous-optimiste » (choisir un $\delta(t)$ plus petit pour élargir les intervalles de confiance) est préférable dans les contextes markoviens par rapport aux bandits stochastiques. Ceci est dû au fait que le bruit dans les estimateurs markoviens peut être plus important que la variance des récompenses suggérée par l'étendue du biais, nécessant des bonus d'exploration plus larges pour maintenir la propriété optimiste.

5. Signification et Contributions

L'article revendique les contributions suivantes :

1. Formulation du Problème : Il formalise un cadre d'apprentissage combinant des états non-observables et des époques de décision endogènes et contraintes, motivé par les réseaux de communication (ex. ordonnancement de canaux non préemptifs).
2. Bandits Agités : Il identifie et définit une classe de bandits agités où les politiques pures sont optimales, justifiant l'utilisation du regret pur comme référence.
3. Limites Fondamentales : Il prouve que la non-observabilité des états combinée aux époques de décision contraintes empêche intrinsèquement le regret logarithmique dans le cas général, établissant une borne inférieure super-logarithmique.
4. Conception d'Algorithme : Il introduit UCB-NOM, un algorithme qui atteint un regret quasi-optimal sans observation d'état. Crucialement, les bornes de regret ne dépendent pas du nombre d'états ($|S_a|$) des chaînes de Markov sous-jacentes, mais de l'étendue du biais.
5. Aperçus Structurels : Il démontre qu'avec une simple connaissance préalable (une borne sur l'étendue du biais), les garanties classiques de regret logarithmique des bandits stochastiques peuvent être récupérées, suggérant que la non-observabilité des états est un « inconvénient léger » dans les contextes auto-dégradants, à condition que les limites structurelles soient connues.

Les auteurs concluent que bien que le cadre soit plus complexe que celui des bandits stochastiques standards, le cadre et l'algorithme proposés fournissent des garanties théoriques robustes sans nécessiter les techniques complexes typiquement associées aux Processus de Décision de Markov Partiellement Observables (POMDP), à condition de respecter le benchmark du regret pur.