Résumé Technique : Le Gradient Naturel de Politique comme Itération de Politique Doublement Lissée

Énoncé du Problème

Les problèmes d'apprentissage par renforcement (RL) sont généralement modélisés comme des processus de décision markoviens (MDP). Alors que les méthodes classiques de programmation dynamique telles que l'itération de politique (PI) et l'itération de valeur (VI) reposent sur les propriétés de contraction et de monotonie de l'opérateur de Bellman, les méthodes modernes basées sur le gradient, telles que le gradient naturel de politique (NPG) et la moyenne duale de politique (PDA), sont souvent analysées à travers le prisme de l'optimisation continue sur l'espace des politiques.

Un fossé conceptuel existe dans la littérature : les analyses du NPG échouent souvent à exploiter la contraction fondamentale en norme $\ell_\infty$ de l'opérateur de Bellman, qui sous-tend les garanties de convergence forte des méthodes classiques. Par conséquent, les résultats théoriques existants pour le NPG souffrent souvent d'une ou plusieurs limitations :

1. Absence de convergence géométrique globale.
2. Dépendance aux distributions d'états initiales ou aux coefficients de concentrabilité.
3. Nécessité d'une régularisation supplémentaire du MDP ou de l'algorithme pour induire une courbure.
4. Dépendance à des tailles de pas adaptatives et dépendantes des trajectoires.

L'article vise à combler ce fossé en fournissant un cadre unifié reliant la PI classique aux méthodes modernes basées sur le gradient, permettant une analyse de convergence géométrique sans distribution, sans modifier le MDP ni exiger de pas adaptatifs.

Méthodologie : Itération de Politique Doublement Lissée (DSPI)

Les auteurs introduisent l'Itération de Politique Doublement Lissée (DSPI), un cadre algorithmique unifié formulé comme un cadre d'opérateur de Bellman. La DSPI met à jour la politique via une étape gourmande régularisée appliquée à une moyenne pondérée des fonctions Q passées.

Le cœur de la DSPI implique deux niveaux de lissage :

1. Lissage par Moyenne : Au lieu d'utiliser uniquement la fonction Q la plus récente, l'algorithme maintient une moyenne courante ($\bar{Q}_k$) de toutes les fonctions Q passées.
2. Lissage par Régularisation : La mise à jour de la politique gourmande est remplacée par une étape régularisée (par exemple, softmax) impliquant une fonction concave $\nu(\cdot)$ (telle que l'entropie).

La règle de mise à jour est définie comme suit :
$$\pi_{k+1}(s) \in \arg\max_{\mu \in \Delta(A)} \left\{ \mu^\top \bar{Q}_{k+1}(s) + \eta_k \nu(\mu) \right\}$$
où $\bar{Q}_{k+1} = (1-\beta_k)\bar{Q}_k + \beta_k Q_{\pi_k}$, et le paramètre de lissage $\eta_k$ décroît géométriquement en fonction des tailles de pas $\beta_k$.

De manière cruciale, les auteurs démontrent que la DSPI admet une formulation compacte utilisant des opérateurs de Bellman lissés ($H_\eta$ et $H^\pi_\eta$). Cela permet d'analyser l'algorithme en utilisant les propriétés de monotonie et de contraction de ces opérateurs, plutôt que de s'appuyer uniquement sur des outils théoriques d'optimisation.

Contributions Clés

1. Unification des Algorithmes

L'article établit que la DSPI est un cadre général qui englobe plusieurs algorithmes majeurs comme cas particuliers :

• Itération de Politique (PI) : Retrouvée lorsque la taille de pas $\beta_k \equiv 1$ (pas de moyenne) et que la régularisation disparaît.
• Gradient Naturel de Politique (NPG) : Retrouvé en définissant $\nu(\cdot)$ comme l'entropie de Shannon et en choisissant des calendriers de tailles de pas spécifiques.
• Moyenne Duale de Politique (PDA) : Retrouvée en choisissant $\nu(\cdot)$ comme une fonction génératrice de divergence négative décalée.
• Itération de Politique Moyennée Duale : Une nouvelle variante où la politique est mise à jour de manière gourmande basée sur les fonctions Q moyennées ($\nu(\cdot) \equiv 0$).

2. Analyse de Convergence Unifiée

En exploitant les propriétés des opérateurs de Bellman lissés, les auteurs fournissent une analyse de convergence unifiée pour la DSPI :

• Convergence Asymptotique : Démontrée pour toute suite de tailles de pas non sommable.
• Convergence Géométrique Globale : Démontrée pour des tailles de pas constantes. La borne d'erreur est donnée par :
  $$\|V^* - V^{\pi_k}\|_\infty \leq (1 - (1-\gamma)\beta)^{k-1} (\gamma \|V^* - V^{\pi_0}\|_\infty + \tau \nu_{\max})$$
  où $\gamma$ est le facteur d'escompte et $\beta$ est la taille de pas constante.

3. Garanties Théoriques Améliorées pour le NPG et la PDA

L'application du cadre DSPI au NPG et à la PDA produit les résultats suivants, qui améliorent ou égalent l'état de l'art sans nécessiter d'hypothèses restrictives :

• Sans Distribution : Les bornes de convergence dépendent uniquement de la norme $\ell_\infty$ de l'écart de la fonction de valeur, et non de la distribution d'états initiale ou des coefficients de concentrabilité.
• Aucune Régularisation Supplémentaire : L'analyse tient sans modifier le MDP ni ajouter de régularisateurs supplémentaires au-delà du terme d'entropie inhérent au NPG standard.
• Tailles de Pas Simples : Les résultats tiennent pour un calendrier de tailles de pas géométriquement croissant simple et prédéfini ($\alpha_k = \beta \alpha_0 / (1-\beta)^k$), éliminant le besoin de tailles de pas adaptatives dépendant de la trajectoire de la politique ou de l'erreur de Bellman.
• Complexité en Itérations : Le NPG et la PDA atteignent une politique $\epsilon$-optimale en $O((1-\gamma)^{-1} \log((1-\gamma)^{-1}\epsilon^{-1}))$ itérations.

4. Terminaison Finie de l'Itération de Politique Moyennée Duale

Pour le cas non régularisé (Itération de Politique Moyennée Duale), les auteurs prouvent une terminaison finie. L'algorithme trouve une politique optimale en au plus $O(mn(1-\gamma)^{-1} \log((1-\gamma)^{-1}))$ itérations, où $n$ et $m$ sont les tailles des espaces d'états et d'actions. Cela est réalisé en montrant que l'algorithme élimine au moins une action sous-optimale toutes les $k^*$ itérations.

5. Extensions

Le cadre est montré pour s'étendre naturellement à :

• Approximation Linéaire de Fonction : La DSPI avec approximation linéaire de fonction atteint une convergence géométrique jusqu'à un terme d'erreur d'approximation de fonction.
• Problèmes de Chemin le Plus Court Stochastique (SSP) : L'analyse s'étend aux problèmes SSP non escomptés, établissant une convergence géométrique globale sans distribution sous l'hypothèse que toutes les politiques stationnaires sont propres.

Résultats et Signification

L'article affirme que sa signification principale réside dans la fourniture d'une perspective unifiée reliant la programmation dynamique classique au RL moderne basé sur le gradient. En interprétant le NPG et la PDA comme des variantes lissées et moyennées de l'itération de politique, les auteurs sont capables de :

1. Récupérer des Garanties Fortes : Établir une convergence géométrique globale pour le NPG et la PDA en utilisant uniquement les propriétés intrinsèques de l'opérateur de Bellman (monotonie et contraction).
2. Éliminer les Artifices : Supprimer le besoin de régularisation "induisant une courbure" ou de tailles de pas adaptatives souvent requises dans les analyses précédentes basées sur l'optimisation.
3. Simplifier l'Analyse : Fournir une analyse plus simple et plus fondée qui évite les complexités des coefficients de décalage de distribution.

Les auteurs notent que, bien que leur analyse actuelle suppose l'accès à des fonctions Q exactes (isolant la dynamique d'amélioration de la politique), le cadre prépare le terrain pour des travaux futurs dans des contextes sans modèle où les fonctions Q doivent être estimées. Ils identifient la combinaison de la DSPI avec des garanties d'évaluation de politique à temps fini comme une prochaine étape non triviale pour obtenir des résultats de complexité d'échantillonnage précis pour le RL sans modèle.