R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes

Résumé Technique : R-GTD : Une Analyse Géométrique de l'Apprentissage par Différence Temporelle de Gradient dans des Régimes Singuliers

Énoncé du Problème
Les algorithmes d'apprentissage par Différence Temporelle de Gradient (GTD), en particulier GTD2, sont des méthodes établies pour l'évaluation de politiques hors politique avec approximation linéaire de fonction. Ils minimisent l'Erreur de Bellman Projetée Moyenne Quadratique (MSPBE) afin de trouver une approximation de fonction de valeur satisfaisant l'équation de Bellman dans un espace de caractéristiques. Cependant, les garanties de convergence théoriques des méthodes GTD existantes reposent sur une hypothèse restrictive : la Matrice d'Interaction des Caractéristiques (FIM), définie par $\Phi^\top D_\beta (\gamma P^\pi - I) \Phi$, doit être non singulière. En pratique, la FIM peut devenir singulière ou presque singulière (mal conditionnée), entraînant une instabilité, une divergence ou une dégradation des performances. Bien que des travaux antérieurs aient tenté de résoudre ce problème via la régularisation, leurs garanties théoriques dépendent souvent d'autres conditions hautement restrictives, telles que la restriction de la solution optimale à l'origine ou l'hypothèse d'une non-singularité globale pour dériver des bornes d'erreur. De plus, la relation géométrique entre les solutions régularisées et l'ensemble de solutions original de GTD2 dans les régimes singuliers reste inexplorée.

Méthodologie
Les auteurs proposent R-GTD (Gradient Temporal-Difference Régularisé), un nouvel algorithme dérivé d'un objectif d'optimisation reformulé. La méthodologie centrale comprend les étapes suivantes :

1. Reformulation de l'Objectif : Les auteurs étendent le problème d'optimisation sous contraintes de GTD2 en introduisant une variable de relâchement auxiliaire $w$ et un terme de pénalité quadratique. Cela conduit à un problème d'optimisation régularisé (Problème 4) qui minimise une somme pondérée de l'erreur de Bellman projetée et d'un terme impliquant la variable auxiliaire.
2. Formulation en Point Selle : Ce problème sous contraintes est reformulé en un problème de point selle min-max convexe-concave (Problème 5) à l'aide d'une fonction de Lagrange. Il est démontré que le Lagrangien est fortement convexe par rapport aux variables primales ($\theta, w$) et concave par rapport à la variable duale ($\lambda$), assurant l'existence d'un point selle unique même lorsque la FIM est singulière.
3. Déduction de l'Algorithme : En appliquant la Dynamique de Gradient Primal-Dual (PDGD) au Lagrangien, les auteurs déduisent les règles de mise à jour de R-GTD (Algorithme 1). Ces règles intègrent l'échantillonnage d'importance pour les données hors politique et mettent à jour trois paramètres : les poids de la fonction de valeur ($\theta$), la variable auxiliaire ($w$) et la variable duale ($\lambda$).
4. Analyse Géométrique : L'article fournit une analyse géométrique rigoureuse du comportement de la solution. Il caractérise la solution R-GTD comme une perturbation de l'ensemble de solutions de GTD2. Plus précisément, il analyse le comportement limite lorsque le paramètre de régularisation $c \to \infty$, en distinguant les cas non singuliers et singuliers.

Contributions Clés
L'article apporte trois contributions principales :

• Suppression des Hypothèses de Non-Singularité : R-GTD garantit la convergence vers une solution unique sans exiger que la FIM soit non singulière. Contrairement aux méthodes régularisées antérieures qui imposent des conditions restrictives supplémentaires pour gérer les singularités, R-GTD y parvient grâce à sa formulation spécifique, sans hypothèses supplémentaires.
• Caractérisation Géométrique et Bornes d'Erreur : Les auteurs fournissent une analyse géométrique détaillée du régime singulier. Ils établissent des bornes d'erreur explicites entre la solution R-GTD et la vraie solution projetée. Dans le cas singulier, ils prouvent que la solution R-GTD converge vers la projection orthogonale de l'ensemble de solutions de GTD2 sur le complément de l'espace nul de la matrice $G = M^\top B^{-1} M$. Cela précise exactement quelle solution au sein de l'ensemble affine GTD2 est sélectionnée par la régularisation.
• Validation Empirique : L'algorithme est validé dans des configurations où la FIM est strictement singulière. Les expériences démontrent que R-GTD converge de manière cohérente vers une solution unique de point selle avec une stabilité supérieure par rapport à GTD2 et d'autres bases de régularisation (par exemple, Ghiassian et al., 2020 ; Yu, 2017).

Résultats

• Convergence : L'analyse théorique confirme que la dynamique en temps continu de R-GTD converge globalement vers un point selle unique. En utilisant la méthode des Équations Différentielles Ordinaires (EDO), il est démontré que les itérés stochastiques de l'Algorithme 1 convergent vers cette solution avec une probabilité un.
• Bornes d'Erreur : Dans le cas non singulier, l'erreur entre la solution R-GTD et la solution GTD2 est bornée par $O(1/c)$. Dans le cas singulier, la solution R-GTD converge vers un élément spécifique de l'ensemble de solutions affine de GTD2 (celui orthogonal à l'espace nul de $G$) avec une borne d'erreur de $O(1/c)$.
• Performance Expérimentale : Dans les expériences impliquant des MDP singuliers, le contre-exemple de Baird et des environnements stochastiques (Frozen Lake), R-GTD supprime systématiquement la composante de l'espace nul qui cause l'instabilité dans GTD2 standard. Il atteint une erreur finale plus faible et une variance réduite par rapport aux méthodes de référence, en particulier lorsque la FIM est mal conditionnée. L'analyse de sensibilité suggère que des valeurs intermédiaires du paramètre de régularisation $c$ (par exemple, $c \in [1, 4]$) offrent le meilleur compromis entre stabilité et biais.

Signification
L'article affirme que R-GTD comble une lacune théorique dans la compréhension de l'apprentissage GTD dans des conditions singulières. En supprimant l'hypothèse de non-singularité, il fournit un cadre robuste pour l'évaluation hors politique dans des scénarios où les interactions de caractéristiques sont dégénérées. L'analyse géométrique offre une compréhension précise de la manière dont la régularisation sélectionne une solution unique parmi l'ensemble potentiellement infini de solutions GTD2, assurant la stabilité sans sacrifier la structure théorique fondamentale de GTD2. Les auteurs notent que l'analyse actuelle se limite à l'approximation linéaire de fonction et à la convergence asymptotique, laissant l'approximation non linéaire et les garanties en temps fini comme axes de travail futurs.