Résumé Technique : Méthodes de Gradient de Politique pour l'Apprentissage par Renforcement Non-Markovien

Énoncé du Problème

L'apprentissage par renforcement (AR) repose traditionnellement sur le cadre des processus de décision markoviens (PDM), en supposant que les dynamiques et les récompenses dépendent uniquement de l'état et de l'action courants. Cependant, de nombreux environnements réels — tels que les systèmes partiellement observables, les agents de dialogue, les systèmes de recommandation et les marchés financiers — sont intrinsèquement des processus de décision non markoviens (PDNM). Dans ces contextes, les observations et les récompenses dépendent de l'ensemble de l'historique des interactions.

Conditionner directement les politiques à l'historique complet est computationnellement intraitable car l'espace des historiques croît de manière exponentielle. Bien que les approches existantes tentent de compresser l'historique, elles rencontrent souvent des limitations :

• Dynamiques Fixes : Certaines méthodes supposent que les dynamiques de l'état interne de l'agent sont fixes et n'optimisent que la politique de contrôle (par exemple, Dong et al., 2022).
• Objectifs Prédictifs : D'autres méthodes apprennent des représentations d'état en optimisant des objectifs prédictifs auxiliaires (par exemple, prédire les observations futures), ce qui peut nécessiter des représentations de haute dimension et ne s'aligne pas directement avec l'objectif ultime de maximisation de la récompense cumulative (par exemple, Subramanian et al., 2022).

Ce papier aborde le défi d'apprendre conjointement une représentation d'état compacte et une politique de contrôle dans les PDNM, sans recourir à des dynamiques fixes ni à des objectifs prédictifs intermédiaires.

Méthodologie

Politiques Agent State-Markov (ASM)

Les auteurs introduisent une classe de politiques Agent State-Markov (ASM). Dans ce cadre, l'agent maintient un état interne $S_t$ mis à jour de manière récursive en fonction de l'état précédent, de l'action précédente et de l'observation courante :
$$S_t \sim \nu_t(\cdot \mid S_{t-1}, A_{t-1}, O_t)$$
La politique de contrôle $\phi$ mappe ensuite l'état de l'agent courant vers une action :
$$A_t \sim \phi_t(\cdot \mid S_t)$$
Le couple $(\nu, \phi)$ constitue la politique ASM. Crucialement, les auteurs proposent d'optimiser les paramètres des dynamiques d'état $\nu$ et de la politique de contrôle $\phi$ conjointement pour maximiser la récompense cumulative attendue, plutôt que de fixer $\nu$ ou de l'apprendre via la prédiction.

Contributions Théoriques

Le papier établit un Théorème du Gradient de Politique pour les politiques ASM, étendant les résultats classiques aux PDNM épisodiques et à horizon infini avec discount.

1. Expression du Gradient : Pour une politique ASM paramétrée $\pi_\theta$, le gradient de la récompense attendue $J(\theta)$ est dérivé comme suit :
   $$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \left[ \sum_{t} R_{t:\infty} \nabla_\theta \log \pi_\theta(S_t, A_t \mid S_{t-1}, A_{t-1}, O_t) \right]$$
   où $R_{t:\infty}$ représente la récompense future (reward-to-go).
2. Factorisation : En raison de la structure des politiques ASM, le terme de log-probabilité se factorise en les dynamiques d'état et la politique de contrôle :
   $$\nabla_\theta \log \pi_\theta = \nabla_\theta \log \nu_\theta + \nabla_\theta \log \phi_\theta$$
   Cela permet la mise à jour séparée mais simultanée de la représentation d'état et de la politique.
3. Garanties de Convergence : Sous des hypothèses standard de régularité et de bornitude, les auteurs prouvent :
   • Convergence à temps fini : La norme carrée moyenne du gradient converge à un taux de $\tilde{O}(H^{3.5}/\sqrt{K})$ pour les tâches épisodiques (où $H$ est l'horizon et $K$ le nombre d'itérations).
   • Convergence presque sûre : Avec des tailles de pas décroissantes, la norme du gradient converge vers zéro presque sûrement.
   • Des garanties similaires sont établies pour le cadre à horizon infini avec discount, où l'horizon effectif est déterminé par le facteur de discount $\gamma$.

Algorithme : ASMPG

Sur la base du théorème du gradient, les auteurs proposent l'algorithme Agent State-Markov Policy Gradient (ASMPG). Il s'agit d'un algorithme en ligne, de style REINFORCE, qui :

• Échantillonne des trajectoires en utilisant la politique ASM courante.
• Calcule l'estimation du gradient en utilisant la structure récursive de l'état de l'agent.
• Met à jour les paramètres du réseau de dynamiques d'état et du réseau de politique en utilisant l'ascension de gradient stochastique.

Résultats Expérimentaux

Les auteurs ont évalué ASMPG sur cinq environnements non markoviens :

1. CheeseMaze : Une tâche de navigation partiellement observable avec des observations ambiguës.
2. HallwayNavigation : Une tâche de labyrinthe déterministe où les configurations locales de murs sont ambiguës.
3. HealthcareTreatment : Une tâche de planification de traitement avec des variables de toxicité et de résistance cachées.
4. MachineRepair : Une tâche de maintenance avec des niveaux d'usure cachés affectant la dégradation des machines.
5. VelocityOnlyCartPole : Une tâche de contrôle où seule la vitesse (et non la position) est observée.

Comparaison : ASMPG a été comparé à AIS-KL et AIS-MMD (Subramanian et al., 2022), qui apprennent des représentations d'état via des objectifs prédictifs (États d'Information Approximatifs).

Constats :

• Sur les cinq environnements, ASMPG a obtenu des récompenses moyennes par étape ou par épisode supérieures à celles des bases prédictives.
• L'écart de performance était particulièrement notable dans les tâches nécessitant une mémoire à long terme, telles que CheeseMaze, MachineRepair et VelocityOnlyCartPole.
• Les résultats suggèrent que l'optimisation directe des dynamiques d'état pour l'objectif de récompense est plus efficace que l'optimisation pour la suffisance prédictive.

Importance et Revendications

Le papier revendique que sa contribution principale est une formulation centrée sur la récompense pour l'AR non markovien. En traitant les dynamiques d'état de l'agent comme un composant apprenable optimisé conjointement avec la politique de contrôle, la méthode contourne le besoin d'objectifs prédictifs auxiliaires ou de représentations d'état fixes.

Les revendications clés incluent :

• Validité Théorique : La dérivation d'un théorème du gradient de politique pour les PDNM généraux fournit une fondation rigoureuse pour l'optimisation conjointe, étendant les résultats classiques des PDM.
• Efficacité Pratique : Les résultats empiriques démontrent que l'optimisation conjointe centrée sur la récompense surpasse les méthodes reposant sur des représentations d'état prédictives, même lorsque les tailles de représentation sont comparables.
• Conditions d'Optimalité : Le papier note que si une dynamique d'état d'agent "idéale" existe (celle qui est une statistique suffisante pour les récompenses et les observations futures), restreindre la recherche aux politiques ASM n'entraîne aucune perte d'optimalité.

Les auteurs reconnaissent que la méthode proposée repose sur des estimateurs de type REINFORCE, qui peuvent souffrir d'une variance élevée. Ils identifient le développement de variantes acteur-critique pour les politiques ASM comme une direction naturelle pour le travail futur afin de réduire la variance tout en préservant l'objectif centré sur la récompense.