Résumé Technique : S'engager sur le Bit : Apprentissage par Renforcement Réactif Bien Conçu

1. Énoncé du Problème

Les algorithmes d'apprentissage par renforcement (RL) sont traditionnellement conçus et analysés sous l'hypothèse de Markov, où l'agent a un accès complet à l'état. Cependant, les environnements pratiques sont souvent partiellement observables (POMDP) ou nécessitent une approximation de fonction qui restreint l'agent à des caractéristiques d'état non markoviennes (agrégation d'états dure). Dans de tels contextes, l'agent doit apprendre une politique réactive—une application des caractéristiques observées vers des distributions d'actions (options)—sans mémoire des observations passées.

Les résultats théoriques existants pour l'apprentissage de politiques réactives optimales sous agrégation d'états dure reposent généralement sur l'hypothèse de $q^\star$-réalisabilité. Cette condition exige que la fonction de valeur d'action optimale $q^\star(x, u)$ soit constante au sein de chaque caractéristique (c'est-à-dire $q^\star(x, u) = q(\phi(x), u)$). Les auteurs soutiennent que cette hypothèse est trop restrictive, excluant des environnements simples (comme l'exemple du "couloir") où une politique réactive optimale existe mais où les états sous-jacents au sein d'une caractéristique ont des valeurs optimales différentes. De plus, le Q-learning standard échoue dans ces scénarios car il tente d'approximer une fonction de valeur qui est ambiguë au sein de la caractéristique agrégée.

L'article aborde le problème de l'apprentissage d'une politique réactive optimale dans des POMDP finis et épisodiques avec des observations déterministes, visant à assouplir les hypothèses de réalisabilité requises pour la convergence.

2. Méthodologie

Q-learning Engagé

Les auteurs proposent le Q-learning Engagé, une variante du Q-learning classique. Le mécanisme central est une stratégie d'engagement :

• Lors de l'entrée dans une caractéristique $z$, la politique de comportement échantillonne une seule option (distribution d'actions) $\omega$.
• L'agent s'engage sur cette option et l'exécute jusqu'à ce que la caractéristique observée change ($z' \neq z$).
• L'agent ne rééchantillonne une nouvelle option que lorsque la caractéristique change.
• Les valeurs Q $Q(z, \omega)$ sont mises à jour en fonction de la transition de la caractéristique $z$ vers $z'$.

Cela contraste avec le Q-learning non engagé, qui pourrait rééchantillonner des actions à chaque pas de temps indépendamment de la stabilité de la caractéristique. L'engagement garantit que le processus d'apprentissage opère à l'échelle temporelle des transitions de caractéristiques plutôt que des transitions d'états brutes.

Cadre Théorique : Environnements Quasi-Markoviens et Robustesse au Recâblage

Pour analyser la convergence, les auteurs introduisent deux concepts clés :

1. Environnements Quasi-Markoviens : Un environnement est quasi-markovien si, pour chaque caractéristique, il existe une distribution unique sur les états d'entrée (ou un état d'entrée unique). Dans de tels environnements, la propriété de Markov tient entre les caractéristiques : la distribution d'état lors de l'entrée dans une caractéristique est indépendante de la caractéristique précédente. Les auteurs montrent que dans les environnements quasi-markoviens, la valeur optimale d'une caractéristique correspond à la valeur de son état d'entrée, permettant à la programmation dynamique de fonctionner correctement.

2. Robustesse au Recâblage : C'est la contribution centrale de l'article. Un environnement est robuste au recâblage si la politique réactive optimale reste inchangée sous tout "recâblage" de l'environnement. Un recâblage modifie les "dynamiques d'entrée" (comment une caractéristique est entrée) tout en maintenant les dynamiques internes de la caractéristique et les probabilités de transition de caractéristiques invariantes.

   • Recâblage Généralisé : Permet des changements arbitraires des distributions d'entrée.
   • Recâblage $\pi$ : Un type spécifique de recâblage où les distributions d'entrée sont remplacées par la distribution d'entrée "moyenne" induite par la politique de comportement $\pi$.

Les auteurs définissent le Risque de Bellman et le Risque de Valeur comme des objectifs apprenables (contrairement à l'Erreur de Bellman ou l'Erreur de Valeur dans les contextes partiellement observables) et montrent que la minimisation du Risque de Bellman dans un environnement quasi-markovien produit les valeurs d'entrée correctes.

3. Contributions Clés

• Algorithme de Q-learning Engagé : Un algorithme qui converge prouvablement vers la politique réactive optimale sous une hypothèse strictement plus faible que les travaux antérieurs.
• Condition de Robustesse au Recâblage : L'introduction d'une nouvelle hypothèse pour l'agrégation d'états. L'article démontre que la robustesse au recâblage est strictement plus faible que la $q^\star$-réalisabilité. Cela signifie que l'algorithme converge dans une classe plus large d'environnements, y compris ceux où la fonction de valeur optimale n'est pas constante au sein d'une caractéristique (par exemple, l'environnement couloir).
• Formalisme Quasi-Markovien : Une définition rigoureuse des environnements quasi-markoviens et de l'MDP agrégé associé, qui sert de pont théorique entre l'environnement partiellement observable et l'algorithme d'apprentissage.
• Preuve de Convergence : En utilisant une extension du théorème de Borkar-Meyn au bruit markovien (Liu et al., 2025), les auteurs prouvent que le Q-learning Engagé converge presque sûrement vers la politique réactive optimale dans tout environnement robuste au recâblage.

4. Résultats

• Convergence : Les itérés $(Q_t)$ du Q-learning Engagé convergent presque sûrement vers une solution $Q^\star$. La politique gourmande dérivée de $Q^\star$ est optimale dans l'environnement si celui-ci est robuste au recâblage.
• Hiérarchie des Hypothèses : L'article établit une hiérarchie stricte d'hypothèses :
  • $q^\star$-réalisabilité $\implies$ Robustesse au recâblage généralisé $\implies$ Robustesse au recâblage.
  • Les implications inverses ne tiennent pas. Plus précisément, l'environnement couloir est robuste au recâblage mais pas $q^\star$-réalisable.
• Validation Empirique : Des expériences numériques dans l'environnement couloir démontrent que tandis que le Q-learning régulier échoue à faire des progrès, le Q-learning Engagé converge rapidement vers la politique optimale sur diverses longueurs de couloir.

5. Importance et Affirmations

L'article affirme que le Q-learning Engagé fournit une solution théoriquement fondée pour l'apprentissage par renforcement réactif dans des environnements partiellement observables sans nécessiter la forte hypothèse de $q^\star$-réalisabilité.

• Assouplissement des Hypothèses : En introduisant la robustesse au recâblage, ce travail élargit la classe d'environnements où des politiques réactives optimales peuvent être apprises. Les auteurs notent que trouver une politique réactive optimale sous agrégation d'états est généralement NP-complet (Littman, 1994), rendant de telles hypothèses nécessaires pour des algorithmes efficaces ; cependant, ce travail identifie l'hypothèse la plus faible connue pour la convergence.
• Interprétabilité : L'algorithme opère à un "niveau supérieur" (l'espace des caractéristiques), résolvant efficacement un MDP agrégé. Le mécanisme d'"engagement" n'est pas une restriction mais une alignement naturel avec l'objectif de trouver une politique réactive qui applique les caractéristiques aux options.
• Apprenabilité : L'article clarifie que les métriques d'erreur standard (Erreur de Valeur, Erreur de Bellman) ne sont pas apprenables dans les contextes partiellement observables car elles dépendent de distributions d'état non observables. En revanche, le Risque de Bellman proposé est apprenable à partir des caractéristiques et récompenses observées, fournissant une base solide pour l'analyse de convergence.

Les auteurs concluent que leur approche offre un cadre robuste pour le RL réactif, comblant le fossé entre les limitations théoriques de l'agrégation d'états et le besoin pratique de politiques sans mémoire dans des environnements complexes. Des travaux futurs sont suggérés pour étendre ces résultats aux options non stationnaires, aux problèmes à horizon infini avec actualisation, et à la robustesse approximative au recâblage.