Résumé Technique : La réutilisation des trajectoires dans les gradients de politique permet une convergence rapide

Énoncé du Problème

Les méthodes de Gradient de Politique (PG - Policy Gradient) sont efficaces pour les problèmes de contrôle continu mais souffrent d'une faible efficacité d'échantillonnage. Les algorithmes de PG « classiques » (ex: REINFORCE, GPOMDP) reposent exclusivement sur des données on-policy fraîches, nécessitant $O(\epsilon^{-2})$ trajectoires pour atteindre un point stationnaire $\epsilon$-approximatif. Cette inefficacité provient de la haute variance des estimations de gradient, qui ne s'estompe pas car les gradients sont toujours estimés à partir de nouveaux échantillons.

Bien que la réutilisation de données passées (trajectoires ou gradients off-policy) soit une stratégie courante pour améliorer l'efficacité, les travaux théoriques existants se sont largement concentrés sur la réutilisation de gradients (ex: SVRPG, SRVRPG, STORM-PG), atteignant des taux allant jusqu'à $O(\epsilon^{-3/2})$. La réutilisation des trajectoires passées, bien qu'intuitive, est restée largement inexplorée d'un point de vue théorique rigoureux. Les tentatives précédentes de réutilisation de trajectoires manquaient soit de garanties de convergence, soit reposaient sur des hypothèses fortes et des estimateurs complexes (nécessitant par exemple le stockage de toutes les politiques passées ou souffrant d'une haute variance due à une pondération par importance naïve).

La question centrale abordée est la suivante : La réutilisation de trajectoires off-policy passées peut-elle mener à des améliorations prouvables de la complexité d'échantillonnage des méthodes de PG ?

Méthodologie

L'algorithme RT-PG

Les auteurs proposent RT-PG (Reusing Trajectories – Policy Gradient), un nouvel algorithme qui estime le gradient de politique en exploitant les trajectoires collectées au cours des $\omega$ dernières itérations. L'innovation centrale est l'estimateur de Moyenne de Puissance Multiple (MPM - Multiple Power Mean), qui combine des données on-policy et off-policy en utilisant un schéma de pondération d'importance multiple (MIW) corrigé.

L'estimateur MPM

Pour traiter les défis statistiques de la réutilisation de données (spécifiquement le biais introduit par la dépendance entre les paramètres de la politique actuelle et les trajectoires passées), l'estimateur MPM emploie deux mécanismes clés :

1. Coefficients Déterministes : Contrairement à l'Heuristique de l'Équilibre (BH - Balance Heuristic) qui utilise des coefficients dépendants de toutes les politiques passées (introduisant un « biais de cross-time »), RT-PG utilise des coefficients déterministes $\alpha_{i,k}$ qui dépendent uniquement du nombre d'itérations et de l'indice de la fenêtre. Cela élimine le biais de cross-time.
2. Correction par Moyenne de Puissance (PM) : Pour garantir que les poids d'importance restent bornés (une propriété « défensive ») et pour contrôler le biais introduit par les coefficients déterministes, l'estimateur applique une correction PM aux poids d'importance classiques. Le poids corrigé pour une trajectoire $\tau$ collectée sous la politique $\pi_{\theta_i}$ et évaluée sous $\pi_{\theta_k}$ est :
   $$\left( (1 - \lambda_{i,k}) \frac{p_{\theta_i}(\tau)}{p_{\theta_k}(\tau)} + \lambda_{i,k} \right)^{-1}$$
   où $\lambda_{i,k} \in [0, 1]$ est un paramètre de correction. Ce terme représente une moyenne harmonique entre le poids classique et 1, garantissant que le poids est borné par $1/\lambda_{i,k}$.

Analyse Théorique

Les auteurs fournissent une analyse rigoureuse en temps fini de l'estimateur MPM :

• Bornes de Concentration : Ils dérivent des bornes de concentration à haute probabilité pour l'estimateur en utilisant l'inégalité de Freedman pour les martingales et un argument de recouvrement pour gérer la nature vectorielle du gradient.
• Contrôle du Biais : L'analyse sépare et contrôle explicitement deux sources de biais :
  • Biais de Cible (Target Bias) : Découlant du fait que le paramètre cible $\theta_k$ dépend de l'historique des trajectoires. Il est contrôlé via un argument de recouvrement sur un sous-ensemble de l'espace des paramètres contenant la cible dépendante de l'historique.
  • Biais PM : Découlant du terme de correction PM. Il est géré par la sélection soigneuse de $\lambda_{i,k}$ basée sur la taille du batch et la borne de divergence $\chi^2$ entre les distributions de trajectoires.

Principales Contributions

1. Première Preuve Rigoureuse : L'article fournit la première preuve théorique que la réutilisation de trajectoires off-policy passées peut accélérer significativement la convergence de la politique (PG).
2. Nouvel Estimateur (MPM) : Introduction de l'estimateur MPM, qui mélange efficacement des données on-policy fraîches avec des trajectoires off-policy des $\omega$ dernières itérations tout en maintenant des poids d'importance bornés et en éliminant le biais de cross-time.
3. Complexité d'Échantillonnage Améliorée :
   • Réutilisation Partielle : Lorsque l'on réutilise les trajectoires des $\omega$ dernières itérations (où $\omega < K$), RT-PG atteint une complexité d'échantillonnage de $\tilde{O}(\epsilon^{-2}\omega^{-1})$.
   • Réutilisation Totale : Lorsque l'on réutilise toutes les trajectoires passées disponibles (où $\omega \ge K$), l'algorithme atteint une complexité d'échantillonnage de $\tilde{O}(\epsilon^{-1})$. Cela correspond aux meilleurs taux connus dans la littérature pour les méthodes de PG et représente une amélioration significative par rapport au taux standard de $O(\epsilon^{-2})$.
4. Implémentation Pratique : Une variante pratique de RT-PG est proposée qui pondère de manière adaptative les données off-policy en fonction des estimations empiriques de la divergence (dissimilarité) des politiques, supprimant ainsi le besoin de la borne globale théorique $D$ en pratique.

Résultats

Résultats Théoriques

Sous les hypothèses standards (divergence $\chi^2$ bornée entre les distributions de trajectoires et régularité de la classe de politique), les auteurs prouvent que RT-PG trouve un point stationnaire $\epsilon$-approximatif avec :

• Une complexité d'échantillonnage de $\tilde{O}(\epsilon^{-1})$ dans le régime de réutilisation totale.
• Une complexité d'échantillonnage de $\tilde{O}(\epsilon^{-2}\omega^{-1})$ dans le régime de réutilisation partielle.

Ces résultats tiennent sans nécessiter le stockage des politiques passées (contrairement aux méthodes basées sur BH), nécessitant seulement le stockage des trajectoires passées.

Résultats Empiriques

Des expériences ont été menées sur des tâches de contrôle continu (Cart Pole, Half Cheetah, Swimmer) en utilisant des politiques gaussiennes linéaires et profondes.

• Efficacité d'Échantillonnage : RT-PG surpasse systématiquement les bases on-policy standards (GPOMDP) et les méthodes de réduction de variance de pointe (SVRPG, SRVRPG, STORM-PG, DEF-PG) en termes d'efficacité d'échantillonnage. Dans l'environnement Half Cheetah, RT-PG a atteint presque deux fois la performance finale de la plupart des bases.
• Impact de la Réutilisation des Trajectoires : Les expériences faisant varier la taille de la fenêtre $\omega$ ont démontré que l'augmentation de la fenêtre de réutilisation accélère la convergence. RT-PG montre des rendements décroissants pour des fenêtres très larges mais surpasse significativement les bases même avec une réutilisation modérée.
• Comparaison avec la Réutilisation Naïve : RT-PG a nettement mieux performé que MIW-PG (qui utilise une pondération uniforme), validant l'efficacité de la correction PM et du schéma de pondération adaptative pour contrôler la variance.
• Efficacité Mémoire : Contrairement aux méthodes basées sur BH qui nécessitent de stocker tous les paramètres de politique passés pour calculer les poids, RT-PG ne nécessite que le stockage des trajectoires passées, ce qui le rend plus scalable pour les espaces de politiques de haute dimension.

Signification et Revendications

L'article affirme fournir la première preuve théorique rigoureuse que la réutilisation de trajectoires est un mécanisme viable et puissant pour accélérer la convergence du Gradient de Politique. En introduisant l'algorithme RT-PG et l'estimateur MPM, les auteurs comblent le fossé entre l'idée intuitive de réutiliser des données passées et les garanties de convergence prouvables.

La signification réside dans :

1. Avancement Théorique : Établir que la réutilisation de trajectoires peut atteindre le taux $\tilde{O}(\epsilon^{-1})$, auparavant jugé difficile pour les méthodes de PG sans hypothèses fortes ou réutilisation de gradients.
2. Utilité Pratique : Démontrer que la réutilisation des trajectoires réduit le coût d'échantillonnage sans compromettre la stabilité de l'apprentissage, offrant une alternative pratique aux méthodes de réutilisation de gradients qui peuvent nécessiter des tailles de batch plus grandes ou des techniques de réduction de variance complexes.
3. Efficacité Mémoire : Atteindre des taux améliorés sans la surcharge mémoire du stockage des paramétrisations de politique passées, une limitation des autres approches de réutilisation de trajectoire comme l'Heuristique de l'Équilibre.

Les auteurs restent modestes quant aux limites, notant que leurs résultats reposent sur l'hypothèse d'une divergence $\chi^2$ bornée entre les distributions de trajectoires et que la complexité d'échantillonnage dépend de la dimensionnalité $d_\Theta$. Ils identifient l'élimination de cette hypothèse et la suppression de la dépendance à la dimension comme des travaux futurs.