Résumé technique : Réexamen des gradients de politique pour des classes de politiques restreintes

Énoncé du problème

Les méthodes standard de gradient de politique (PG) sont largement utilisées pour résoudre les processus de décision de Markov (MDP). Bien qu'elles soient théoriquement garanties de converger vers la politique optimale dans des classes de politiques non restreintes sous une exploration suffisante, elles échouent fréquemment dans des classes de politiques restreintes. Dans ces contextes, qui incluent l'agrégation d'états, les systèmes multi-agents décentralisés et les environnements partiellement observables, les méthodes PG restent souvent bloquées dans des points critiques sous-optimaux.

Les auteurs identifient la cause racine de cet échec comme étant la nature myope du théorème standard du gradient de politique. Le théorème repose sur une fonction Q à un pas, qui évalue l'amélioration d'une politique basée sur une seule étape d'action avant de revenir à la politique actuelle. Dans les classes restreintes, cette « courte-vue » signifie que même si une meilleure politique existe au sein de la classe, le gradient peut indiquer aucune direction d'amélioration car le coût immédiat à un pas de s'écarter de la politique actuelle semble élevé, tandis que les bénéfices à long terme (qui nécessitent plusieurs étapes de la nouvelle politique) ne sont pas capturés dans le calcul du gradient. Ce problème persiste même dans des contextes entièrement observables si la distribution d'états initiale manque d'exploration suffisante pour couvrir le support de la politique optimale.

Méthodologie

1. Formulation de politique corrélée

Pour remédier à la myopie, les auteurs proposent une reformulation de la politique. Au lieu de considérer une politique stochastique comme une mapping directe $\pi: S \to \Delta(A)$, ils définissent une Politique Corrélée $\tilde{\pi}$ comme une distribution sur un ensemble de politiques déterministes $\Pi_{det}$.

• Classe restreinte : Le processus d'apprentissage opère sur $\tilde{\Pi}_{res} = \Delta(\Pi_{det})$, l'ensemble de toutes les distributions sur un ensemble prédéfini de politiques déterministes.
• Exécution : Dans un déploiement standard, une politique déterministe est échantillonnée à partir de $\tilde{\pi}$ à chaque étape indépendamment. Cependant, les auteurs introduisent un mécanisme d'évaluation k-étapes.

2. Gradients de politique k-étapes

L'innovation centrale est le Gradient de politique k-étapes, qui modifie l'horizon d'évaluation pour échapper aux optima locaux.

• Fonction de valeur k-étapes ($J_{\tilde{\pi}, k}$) : Au lieu d'échantillonner une nouvelle politique déterministe à chaque étape, l'algorithme échantillonne une politique déterministe $\pi_{det} \sim \tilde{\pi}$ et l'exécute pendant $k$ étapes consécutives avant de rééchantillonner.
• Fonction Q k-étapes ($Q_{\tilde{\pi}, k}$) : Cette fonction évalue le retour obtenu en adoptant une politique déterministe spécifique $\pi'_{det}$ pour les $k$ premières étapes, suivie du déploiement standard k-étapes de $\tilde{\pi}$.
• Théorème 5.5 (Théorème PG k-étapes) : Le gradient de la fonction de valeur k-étapes par rapport aux paramètres de $\tilde{\pi}$ est exprimé en utilisant la fonction Q k-étapes :
  $$\nabla_\alpha J_{\tilde{\pi}_\alpha, k}(\mu) = \frac{1}{1-\gamma^k} \mathbb{E}_{s \sim d_{\tilde{\pi}_\alpha, k}^\mu} \left[ \mathbb{E}_{\pi_{det} \sim \tilde{\pi}_\alpha} [Q_{\tilde{\pi}_\alpha, k}(s, \pi_{det}) \nabla_\alpha \log \tilde{\pi}_\alpha(\pi_{det})] \right]$$
  En évaluant les actions sur une fenêtre de $k$ étapes, le gradient peut « voir » les bénéfices à long terme d'une politique déterministe qui pourrait engendrer des coûts à court terme, corrigeant ainsi le biais myope.

3. Algorithmes d'optimisation

L'article analyse la convergence de la Descente de gradient projetée (PGD) et de la Descente miroir lorsqu'elles sont appliquées à cet objectif k-étapes. L'analyse suppose uniquement la régularité et la différentiabilité de la fonction de valeur, évitant des hypothèses fortes comme la complétude de Bellman ou la dominance du gradient, courantes dans la littérature antérieure.

Contributions et résultats clés

1. Garantie théorique de near-optimalité

La contribution théorique principale est la preuve que tous les points critiques à gradient nul et les minima locaux de frontière de l'objectif k-étapes sont exponentiellement proches de la politique déterministe optimale en termes de performance.

• Théorème 6.1 : Pour tout point critique $\tilde{\pi}_{crit}$, l'écart de performance satisfait :
  $$\mathbb{E}_{\pi_{det} \sim \tilde{\pi}_{crit}}[J_{\pi_{det}}(\mu)] - J_{\pi^*_{det}}(\mu) \leq \frac{8\gamma^k}{1-\gamma} g_{max}$$
  À mesure que $k$ augmente, la borne se resserre exponentiellement, éliminant efficacement les minima locaux sous-optimaux qui affligent les méthodes à 1 pas.

2. Vitesses de convergence

Les auteurs démontrent que les algorithmes de descente (PGD et Descente miroir) convergent vers ces solutions quasi-optimales à un taux de $O(1/T)$.

• Théorème 6.2 & 6.3 : Malgré l'absence de la condition standard de dominance du gradient (qui échoue souvent dans les classes restreintes), l'évaluation k-étapes induit une condition de dominance de gradient approximative. Cela permet aux algorithmes d'atteindre le taux plus rapide de $O(1/T)$, typiquement associé aux problèmes convexes ou à dominance de gradient, plutôt que le taux plus lent de $O(1/\sqrt{T})$ typique des fonctions lisses non convexes.

3. Éviter le décalage de distribution

Une découverte significative est que ces bornes ne dépendent pas des facteurs de décalage de distribution $\|d_{\pi^*}^\mu / d_{\pi}^\mu\|_\infty$ ou $\|d_{\pi^*}^\mu / \mu\|_\infty$.

• Dans la théorie PG standard, ces facteurs peuvent être infinis si la distribution initiale $\mu$ ne couvre pas le support de l'occupation d'états de la politique optimale, conduisant à des points critiques sous-optimaux même dans des contextes entièrement observables.
• La méthode k-étapes est démontrée capable d'échapper à ces points quelle que soit la couverture de la distribution initiale, à condition que $k$ soit suffisamment grand.

Importance et applications

L'article affirme que ce travail fournit une fondation théorique pour résoudre des MDP complexes avec des classes de politiques restreintes où les méthodes précédentes échouaient ou reposaient sur des hypothèses irréalistes.

• Agrégation d'états : La méthode offre des garanties quasi-optimales pour les politiques qui mappent des états agrégés vers des actions, une nécessité courante dans les systèmes à grande échelle.
• Systèmes multi-agents : Elle s'applique aux contextes coopératifs avec des agents indépendants, des agents décentralisés et des agents décentralisés en groupe. Ceux-ci sont souvent modélisés comme des Dec-POMDP, connus pour être intraitables (NEXP-complets). L'article fournit un résultat théorique positif pour les méthodes basées sur le gradient dans ces contextes.
• Contextes entièrement observables : Le travail souligne que même dans des MDP entièrement observables, une mauvaise exploration (distribution d'états initiale) peut créer des points critiques sous-optimaux. La méthode k-étapes fournit un mécanisme pour échapper à ceux-ci sans nécessiter une exploration initiale parfaite.

Conclusion

En passant d'une évaluation myope à 1 pas à une évaluation corrélée k-étapes, la méthode proposée modifie fondamentalement le paysage d'optimisation des classes de politiques restreintes. Elle garantit que les points critiques sont exponentiellement proches de la solution optimale et assure une convergence rapide pour les algorithmes de descente standards, le tout sans nécessiter d'hypothèses fortes de réalisabilité ou d'exploration initiale parfaite. Cela comble un fossé entre les garanties théoriques et les applications pratiques dans l'agrégation d'états et l'apprentissage par renforcement multi-agent.