On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

Résumé Technique : Sur la variance de l'apprentissage par différence temporelle et sa réduction par les variables de contrôle

Énoncé du problème
L'évaluation de politique est un défi fondamental en apprentissage par renforcement (RL). Alors que les méthodes de Monte Carlo (MC) fournissent des estimateurs non biaisés des fonctions de valeur, elles souffrent d'une variance élevée en raison de la nécessité de moyenner sur des trajectoires complètes. Inversement, l'apprentissage par différence temporelle (TD) utilise le bootstrapping (mise à jour des estimations basée sur d'autres estimations) pour réduire la variance, mais cela introduit un biais. Le mécanisme précis par lequel le TD réduit la variance, particulièrement dans le régime en ligne, et la manière dont il se compare asymptotiquement à MC, est resté un sujet de débat nuancé. De plus, bien que l'estimation directe de l'avantage (DAE - Direct Advantage Estimation) ait montré un succès empirique dans le RL profond, sa justification théorique concernant la réduction de la variance s'est limitée aux propriétés de convergence plutôt qu'à une analyse rigoureuse de ses bornes de variance par rapport au TD standard.

Méthodologie
Les auteurs analysent la variance de l'apprentissage TD multi-étapes dans un cadre phasé (synchrone) en utilisant des représentations tabulaires. Ce cadre fait abstraction des complexités associées aux mises à jour asynchrones et aux approximations stochastiques, permettant une isolation plus claire des mécanismes de variance.

1. Décomposition de la variance : L'article dérive une relation de récurrence pour la variance des mises à jour TD multi-étapes. En développant cette récursion, les auteurs comparent la variance asymptotique du TD par rapport aux estimateurs MC.
2. Cadre des variables de contrôle : Les auteurs considèrent la fonction d'avantage ($A^\pi$) comme une variable de contrôle pour l'évaluation de la politique. Ils utilisent le concept de variables de contrôle ajustées par régression, où la fonction d'avantage est estimée simultanément avec la fonction de valeur afin de minimiser la variance de l'estimateur de rendement.
3. Estimation directe de l'avantage (DAE) : L'article analyse la DAE (Pan et al., 2022) comme un problème de moindres carrés contraint. En traitant les estimations de la fonction d'avantage comme des paramètres nuisibles dans un cadre de régression, les auteurs reformulent la règle de mise à jour de la DAE pour montrer explicitement sa structure en tant que variable de contrôle ajustée par régression.
4. Validation empirique : Les affirmations théoriques sont illustrées par des environnements de type Chaîne MDP soigneusement conçus. Ces expériences font varier le degré de stochasticité (masquage de récompense, transitions collantes) et la couverture état-action pour tester les comportements asymptotiques de MC, TD et DAE sous différentes conditions.

Contributions clés

1. Borne de variance asymptotique du TD : Les auteurs prouvent que, tant dans les contextes phasés (synchrones) que IID (asynchrones), la variance asymptotique de l'apprentissage TD multi-étapes est bornée supérieurement par celle des méthodes de Monte Carlo.

   • Mécanisme : L'article identifie que le TD réduit la variance non pas simplement par un compromis biais-variance, mais en agrégeant efficacement un ensemble plus large de trajectoires indépendantes. Lorsque les états de bootstrapping sont divers et faiblement corrélés, le moyennage de leurs valeurs réduit la variance. À l'inverse, si les états de bootstrapping sont identiques (fortement corrélés), la capacité de réduction de la variance du TD diminue et il approche asymptotiquement la variance de MC.
   • Effet d'horizon : Pour un nombre de échantillons fixé, les mises à jour à horizon court (petit $k$) induisent moins de variance que les mises à jour à horizon long unique.

2. La DAE comme variable de contrôle ajustée par régression : L'article démontre que la fonction d'avantage peut servir de variable de contrôle pour les estimateurs MC. Il établit en outre que l'estimation directe de l'avantage (DAE) est une forme de variable de contrôle ajustée par régression qui estime simultanément les fonctions de valeur et d'avantage.

   • Borne de variance : Dans la limite de grands échantillons, la DAE atteint une borne supérieure de variance plus serrée que le TD standard. Plus précisément, la variance de la DAE est bornée par la variance d'un estimateur MC ajusté par la fonction d'avantage (MC-A), laquelle est elle-même inférieure ou égale à la variance du MC standard.

3. Illustrations empiriques :

   • Dans les environnements déterministes où les états de bootstrapping sont identiques, le TD ne parvient pas à réduire la variance par rapport à MC, confirmant la dépendance théorique vis-à-vis de la diversité des trajectoires.
   • Dans les environnements à transitions stochastiques, le TD présente le compromis biais-variance attendu, et la DAE converge rapidement (similairement aux itérations de Bellman) car la fonction d'avantage explique totalement la variance.
   • Dans les scénarios de masquage de récompense (où la variance de la récompense ne peut être expliquée par les actions), les estimations d'avantage de la DAE ne peuvent pas éliminer totalement la variance, ce qui entraîne un léger écart asymptotique par rapport aux itérations de Bellman, bien qu'elle surpasse tout de même le TD.
   • Dans les contextes de faible couverture (espaces d'actions sous-échantillonnés), la DAE peut souffrir d'un biais de petit échantillon dû à des estimations d'avantage peu fiables, mais elle converge néanmoins vers une erreur quadratique moyenne (MSE) plus faible que le TD, suggérant une robustesse même avec des variables de contrôle imparfaites.

Résultats et Signification
Cet article fournit une explication théorique rigoureuse des capacités de réduction de la variance du bootstrapping, allant au-delà de l'intuition du "compromis biais-variance" pour proposer un mécanisme basé sur l'agrégation de trajectoires. Il clarifie que la supériorité du TD sur MC est conditionnée par la diversité des états de bootstrapping.

De plus, ce travail offre un fondement théorique à la DAE, expliquant son succès empirique dans le RL profond en la présentant comme une méthode de variable de contrôle. Les résultats suggèrent que l'utilisation de la fonction d'avantage comme variable de contrôle peut théoriquement atteindre des bornes de variance plus serrées que le TD standard.

Limites et Portée
Les auteurs notent plusieurs limites :

• Les résultats théoriques sont dérivés pour les contextes phasés et IID ; la généralisation à des schémas d'échantillonnage markoviens réalistes reste une question ouverte.
• L'analyse se concentre sur la réduction de la variance ; la DAE entraîne des coûts de calcul supplémentaires (résolution de moindres carrés) et des exigences de stockage.
• Les bornes de variance serrées pour la DAE reposent sur une approximation de grand échantillon où les coefficients de la variable de contrôle sont optimaux. Bien que les résultats empiriques suggèrent des bénéfices dans les régimes de petits échantillons, une analyse rigoureuse du biais de petit échantillon de la DAE est laissée aux travaux futurs.

L'article conclut que la compréhension de l'agrégation de trajectoires indépendantes est centrale pour la réduction de la variance du TD, et que la régression par variable de contrôle (via la DAE) offre une voie structurée pour réduire davantage la variance dans l'évaluation de politique.