Théorèmes de la Limite Centrale pour l'Apprentissage Q Asynchrone Moyenné

Informations Fondamentales

• ID de l'article: 2509.18964
• Titre: Central Limit Theorems for Asynchronous Averaged Q-Learning
• Auteur: Xingtu Liu (Université Simon Fraser)
• Classification: cs.LG math.OC stat.ML
• Conférence de publication: OPT2025: 17e Atelier annuel sur l'optimisation pour l'apprentissage automatique
• Lien de l'article: https://arxiv.org/abs/2509.18964

Résumé

Cet article établit des théorèmes de la limite centrale pour l'apprentissage Q moyenné de Polyak-Ruppert sous des mises à jour asynchrones. L'article démontre un théorème de la limite centrale non-asymptotique dont le taux de convergence en distance de Wasserstein reflète explicitement la dépendance au nombre d'itérations, à la taille de l'espace état-action, au facteur d'actualisation et à la qualité de l'exploration. De plus, un théorème de la limite centrale fonctionnel est dérivé, montrant que le processus des sommes partielles converge faiblement vers un mouvement brownien.

Contexte et Motivation de la Recherche

Contexte du Problème

1. Importance de l'apprentissage Q: L'apprentissage Q est l'un des algorithmes les plus largement utilisés en apprentissage par renforcement, apprenant directement les fonctions de valeur d'action optimales à partir de trajectoires empiriques, avec des succès remarquables dans les jeux Atari, le jeu de Go, la manipulation robotique et l'alignement des modèles de langage de grande taille.
2. Défis de l'analyse théorique:
   • L'apprentissage Q peut être interprété comme une instance d'approximation stochastique (SA), mais l'apprentissage Q asynchrone est un problème SA non-linéaire avec bruit markovien
   • Comparée à l'SA linéaire et à l'apprentissage TD, l'analyse de l'apprentissage Q est plus difficile en raison de sa non-linéarité, ses opérateurs non-lisses et ses processus non-stationnaires
   • Les mises à jour asynchrones introduisent davantage de bruit markovien, augmentant la complexité analytique
3. Limitations des travaux existants:
   • Des travaux antérieurs ont établi le TLC fonctionnel pour l'apprentissage Q synchrone, mais l'apprentissage Q synchrone ne considère que le bruit de martingale
   • Zhang et Xie (2024) ont établi un TLC fonctionnel pour l'apprentissage Q asynchrone à pas constant, mais le pas constant ne satisfait pas les conditions nécessaires pour établir un TLC non-asymptotique
   • Actuellement, aucun TLC non-asymptotique pour l'apprentissage Q n'existe, même dans le cadre synchrone

Motivation de la Recherche

L'établissement de théorèmes de la limite centrale est crucial pour comprendre les propriétés statistiques des algorithmes. Cette normalité asymptotique est d'une importance capitale pour la quantification de l'incertitude et l'inférence statistique en apprentissage par renforcement.

Contributions Principales

1. Premier TLC non-asymptotique pour l'apprentissage Q: Démonstration d'un théorème de la limite centrale non-asymptotique pour l'apprentissage Q asynchrone moyenné, avec un taux de convergence de $\tilde{O}((|S||A|)^{1/2}K^{-1/6}\rho^{-2}(1-\gamma)^{-3})$
2. Théorème de la limite centrale fonctionnel: Établissement du TLC fonctionnel pour l'apprentissage Q asynchrone à pas décroissant, montrant la convergence faible du processus des sommes partielles vers un mouvement brownien
3. Dépendances explicites: Le taux de convergence reflète explicitement la dépendance au nombre d'itérations K, à la taille de l'espace état-action |S||A|, au facteur d'actualisation γ et à la qualité de l'exploration ρ
4. Innovations techniques: Résolution des défis analytiques posés par la non-linéarité, le bruit markovien et les opérateurs non-lisses

Détails de la Méthodologie

Définition de la Tâche

Considérons un processus de décision markovien (MDP) à horizon infini actualisé $M = \langle S, A, P, r, \gamma \rangle$, où:

• $S$: ensemble des états
• $A$: ensemble des actions
• $P: S \times A \rightarrow \Delta_S$: fonction de probabilité de transition
• $\gamma \in [0,1)$: facteur d'actualisation

L'objectif est d'apprendre la fonction Q optimale $Q^* = \max_\pi Q^\pi$.

Algorithme d'Apprentissage Q Asynchrone

L'apprentissage Q asynchrone maintient un estimateur de fonction Q $Q_k$, avec la règle de mise à jour: $Q_{k+1} = Q_k + \alpha_k(F_k - Q_k)$

où:

• $F_k = F(Q_k, y_k)$, $y_k = (s_k, a_k, s_{k+1})$
• $[F(Q_k, s_k, a_k, s_{k+1})](s,a) = \mathbf{1}_{\{(s_k,a_k)=(s,a)\}}\Gamma(Q_k, s_k, a_k, s_{k+1}) + Q_k(s,a)$
• $\Gamma(Q_k, s_k, a_k, s_{k+1}) = r_k(s_k, a_k) + \gamma\max_a Q_k(s_{k+1}, a) - Q_k(s_k, a_k)$

Hypothèses Clés

Hypothèse 1: Il existe une politique optimale $\pi^*$ telle que pour $Q \in \mathbb{R}^{|S|\times|A|}$: $\|(P^\pi - P^{\pi^*})(Q-Q^*)\|_\infty \leq L\|Q-Q^*\|_2^\infty$

Hypothèse 2: $\{y_k\}_{k \geq 0}$ est une chaîne de Markov sur un espace d'états fini, irréductible et apériodique.

Choix du Pas

Sélection d'un pas polynomial $\alpha_k = \alpha(k+b)^{-\beta}$, où $\alpha, b > 0$, $\beta \in (0.5, 1)$.

Raisons de ce choix:

1. Satisfaction des conditions clés du schéma de moyenne de Polyak-Juditsky
2. Le pas constant viole les conditions (i) et (iii), le pas linéaire viole la condition (ii)
3. Le pas polynomial satisfait toutes les conditions nécessaires

Résultats Théoriques Principaux

Théorème de la Limite Centrale Non-Asymptotique

Théorème 4: Sous les hypothèses 1 et 2, on a: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, \tilde{N}\right) \leq \frac{(|S||A|)^{1/2}}{\rho(1-\gamma)^2K^{1/2}} \cdot \tilde{O}\left((\rho(1-\gamma))^{\frac{\beta-2}{1-\beta}} + K^{\beta/2}\rho^{-1}(1-\gamma)^{-1} + K^{1-\beta} + K^{\frac{1-\beta}{2}}\rho^{-1-\beta}(1-\gamma)^{-\beta}\right)$

où $\Delta_k = Q_k - Q^*$, $\tilde{N} = (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)$.

Corollaire 5: Lorsque $\beta = 2/3$, le taux de convergence se simplifie en: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)\right) \leq \tilde{O}\left(\frac{(|S||A|)^{1/2}}{K^{1/6}\rho^2(1-\gamma)^3}\right)$

Théorème de la Limite Centrale Fonctionnel

Théorème 6: Sous les conditions du théorème 4, le processus des sommes partielles $\Phi_K(\zeta) = K^{-1/2}\sum_{k=1}^{\lfloor\zeta K\rfloor}\Delta_k$ converge faiblement sur $D[0,1]$ vers $(A^{-1}\Sigma A^{-\top})^{1/2}B(\cdot)$, où $B(\cdot)$ est un mouvement brownien standard.

Innovations Techniques et Stratégie de Preuve

Défis Techniques Principaux

1. Non-linéarité: L'apprentissage Q est une SA non-linéaire, plus complexe que l'SA linéaire
2. Bruit markovien: Les mises à jour asynchrones introduisent un bruit markovien non-indépendant et identiquement distribué
3. Opérateurs non-lisses: L'opérateur empirique de Bellman dans l'apprentissage Q asynchrone est non-lisse

Stratégie de Preuve

1. Technique des bornes supérieures et inférieures: Introduction de séquences de bornes supérieures $\Delta_k^{\uparrow}$ et inférieures $\Delta_k^{\downarrow}$, utilisation du théorème d'encadrement
2. Décomposition des termes: Décomposition de $\sum_{k=1}^K \Delta_k$ en six termes:
   • Terme (1): Terme d'erreur initiale
   • Terme (2): Terme d'erreur non-linéaire
   • Terme (3): Terme de bruit markovien
   • Termes (4-5): Termes de correction d'ordre supérieur
   • Terme (6): Séquence de différences de martingale
3. Technique de l'équation de Poisson: Transformation du bruit markovien en séquence de différences de martingale
4. Théorème de la limite centrale pour martingales: Application du TLC non-asymptotique pour martingales de Srikant (2024)

Travaux Connexes

Théorie de l'Approximation Stochastique

• Polyak, Juditsky (1992): Technique classique de réduction de variance par moyennage
• Anastasiou et al. (2019): TLC non-asymptotique pour SGD moyenné de Polyak-Ruppert
• Mou et al. (2020): TLC non-asymptotique pour l'SA linéaire

TLC en Apprentissage par Renforcement

• Xie et Zhang (2022), Li et al. (2023): TLC fonctionnel pour l'apprentissage Q synchrone
• Zhang et Xie (2024): TLC fonctionnel pour l'apprentissage Q asynchrone à pas constant
• Srikant (2024), Samsonov et al. (2024): TLC non-asymptotique pour l'apprentissage TD

Conclusions et Discussion

Conclusions Principales

1. Établissement du premier TLC non-asymptotique pour l'apprentissage Q, avec un taux de convergence explicitement dépendant des paramètres du problème
2. Démonstration de la convergence faible du processus des sommes partielles de l'apprentissage Q asynchrone
3. Fourniture d'une base théorique pour la quantification de l'incertitude en apprentissage par renforcement

Limitations

1. Nécessité d'hypothèses Lipschitz relativement fortes (Hypothèse 1)
2. Considération uniquement d'espaces état-action finis
3. Le taux de convergence peut ne pas être optimal

Directions Futures

1. Amélioration du taux de convergence
2. Extension au-delà de la distance de Wasserstein 1
3. Considération du cadre d'approximation fonctionnelle

Évaluation Approfondie

Points Forts

1. Contribution théorique majeure: Premier établissement d'un TLC non-asymptotique pour l'apprentissage Q, comblant un vide théorique important
2. Innovations techniques: Combinaison ingénieuse de techniques de bornes supérieures/inférieures, d'équation de Poisson et de TLC pour martingales résolvant les difficultés techniques
3. Résultats complets: Fourniture simultanée de TLC non-asymptotique et fonctionnel
4. Dépendances explicites: Le taux de convergence reflète explicitement l'influence de chaque paramètre

Insuffisances

1. Hypothèses fortes: L'hypothèse Lipschitz peut être difficile à vérifier en pratique
2. Taux de convergence: Le taux de convergence $K^{-1/6}$ est relativement lent
3. Espaces finis: Non-considération d'espaces d'états continus ou d'approximation fonctionnelle

Portée et Impact

1. Valeur théorique: Fourniture de nouveaux outils et perspectives pour l'analyse théorique de l'apprentissage Q
2. Pertinence pratique: Établissement d'une base théorique pour la quantification de l'incertitude dans les algorithmes d'apprentissage par renforcement
3. Méthodologie: Les techniques de preuve peuvent être généralisées à d'autres problèmes d'SA non-linéaires

Scénarios d'Application

1. Analyse théorique de problèmes d'apprentissage par renforcement tabulaire
2. Étude de la convergence d'algorithmes à mises à jour asynchrones
3. Inférence statistique et construction d'intervalles de confiance en apprentissage par renforcement

Références

• Polyak, B. T. et Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging.
• Xie, C. et Zhang, Z. (2022). A statistical online inference approach in averaged stochastic approximation.
• Zhang, Y. et Xie, Q. (2024). Constant stepsize q-learning: Distributional convergence, bias and extrapolation.