2025-11-10T02:47:02.164832

Central Limit Theorems for Asynchronous Averaged Q-Learning

Liu
This paper establishes central limit theorems for Polyak-Ruppert averaged Q-learning under asynchronous updates. We prove a non-asymptotic central limit theorem, where the convergence rate in Wasserstein distance explicitly reflects the dependence on the number of iterations, state-action space size, the discount factor, and the quality of exploration. In addition, we derive a functional central limit theorem, showing that the partial-sum process converges weakly to a Brownian motion.
academic

Zentrale Grenzwertsätze für asynchrones gemitteltes Q-Learning

Grundinformationen

  • Paper-ID: 2509.18964
  • Titel: Central Limit Theorems for Asynchronous Averaged Q-Learning
  • Autor: Xingtu Liu (Simon Fraser University)
  • Klassifizierung: cs.LG math.OC stat.ML
  • Veröffentlichungskonferenz: OPT2025: 17th Annual Workshop on Optimization for Machine Learning
  • Paper-Link: https://arxiv.org/abs/2509.18964

Zusammenfassung

In diesem Artikel werden zentrale Grenzwertsätze für das Polyak-Ruppert-gemittelte Q-Learning unter asynchronen Aktualisierungen etabliert. Der Artikel beweist einen nicht-asymptotischen zentralen Grenzwertsatz, dessen Konvergenzrate in der Wasserstein-Distanz die Abhängigkeit von der Anzahl der Iterationen, der Größe des Zustands-Aktions-Raums, dem Diskontfaktor und der Explorationsqualität explizit widerspiegelt. Darüber hinaus wird ein funktionaler zentraler Grenzwertsatz hergeleitet, der zeigt, dass der Partialsummenprozess schwach gegen eine Brownsche Bewegung konvergiert.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Bedeutung des Q-Learning: Q-Learning ist einer der am weitesten verbreiteten Algorithmen im Reinforcement Learning und lernt direkt aus Erfahrungstrajektorien die optimale Aktionswertfunktion. Es hat enorme Erfolge in Bereichen wie Atari-Spielen, Go, Robotersteuerung und Ausrichtung großer Sprachmodelle erzielt.
  2. Herausforderungen der theoretischen Analyse:
    • Q-Learning kann als Instanz der stochastischen Approximation (SA) interpretiert werden, aber asynchrones Q-Learning ist ein nicht-lineares SA-Problem mit Markov-Rauschen
    • Im Vergleich zu linearer SA und TD-Learning ist die Analyse von Q-Learning aufgrund seiner nicht-linearen, nicht-glatten Operatoren und nicht-stationären Prozesse anspruchsvoller
    • Asynchrone Aktualisierungen führen zusätzlich Markov-Rauschen ein und erhöhen die Analysekomplexität
  3. Einschränkungen bestehender Arbeiten:
    • Bisherige Arbeiten haben funktionale CLTs für synchrones Q-Learning etabliert, aber synchrones Q-Learning berücksichtigt nur Martingal-Rauschen
    • Zhang und Xie (2024) etablierten einen funktionalen CLT für asynchrones Q-Learning mit konstanter Schrittweite, aber konstante Schrittweiten erfüllen nicht die notwendigen Bedingungen zur Etablierung eines nicht-asymptotischen CLT
    • Derzeit existiert kein nicht-asymptotischer CLT für Q-Learning, nicht einmal in synchronen Einstellungen

Forschungsmotivation

Die Etablierung von zentralen Grenzwertsätzen ist entscheidend für das Verständnis der statistischen Eigenschaften von Algorithmen. Diese asymptotische Normalität ist für die Unsicherheitsquantifizierung und statistische Inferenz im Reinforcement Learning von großer Bedeutung.

Kernbeiträge

  1. Erster nicht-asymptotischer CLT für Q-Learning: Beweis eines nicht-asymptotischen zentralen Grenzwertsatzes für asynchrones gemitteltes Q-Learning mit Konvergenzrate O~((∣S∣∣A∣)1/2K−1/6ρ−2(1−γ)−3)\tilde{O}((|S||A|)^{1/2}K^{-1/6}\rho^{-2}(1-\gamma)^{-3})
  2. Funktionaler zentraler Grenzwertsatz: Etablierung eines funktionalen CLT für asynchrones Q-Learning mit abnehmender Schrittweite, das zeigt, dass der Partialsummenprozess schwach gegen eine Brownsche Bewegung konvergiert
  3. Explizite Abhängigkeitsbeziehungen: Die Konvergenzrate spiegelt explizit die Abhängigkeit von der Anzahl der Iterationen K, der Größe des Zustands-Aktions-Raums |S||A|, dem Diskontfaktor γ und der Explorationsqualität ρ wider
  4. Technische Innovationen: Lösung der Analysehausforderungen, die durch Nicht-Linearität, Markov-Rauschen und nicht-glatte Operatoren entstehen

Methodische Details

Aufgabendefinition

Betrachten Sie einen unendlichen Horizont-diskontierten Markov-Entscheidungsprozess (MDP) M=⟨S,A,P,r,γ⟩M = \langle S, A, P, r, \gamma \rangle, wobei:

  • SS: Zustandsmenge
  • AA: Aktionsmenge
  • P:S×A→ΔSP: S \times A \rightarrow \Delta_S: Übergangwahrscheinlichkeitsfunktion
  • γ∈[0,1)\gamma \in [0,1): Diskontfaktor

Das Ziel ist das Erlernen der optimalen Q-Funktion Q∗=max⁡πQπQ^* = \max_\pi Q^\pi.

Asynchroner Q-Learning-Algorithmus

Asynchrones Q-Learning verwaltet einen Q-Funktionsschätzer QkQ_k mit der Aktualisierungsregel: Qk+1=Qk+αk(Fk−Qk)Q_{k+1} = Q_k + \alpha_k(F_k - Q_k)

wobei:

  • Fk=F(Qk,yk)F_k = F(Q_k, y_k), yk=(sk,ak,sk+1)y_k = (s_k, a_k, s_{k+1})
  • [F(Qk,sk,ak,sk+1)](s,a)=1{(sk,ak)=(s,a)}Γ(Qk,sk,ak,sk+1)+Qk(s,a)[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)
  • Γ(Qk,sk,ak,sk+1)=rk(sk,ak)+γmax⁡aQk(sk+1,a)−Qk(sk,ak)\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)

Schlüsselannahmen

Annahme 1: Es existiert eine optimale Strategie π∗\pi^* derart, dass für Q∈R∣S∣×∣A∣Q \in \mathbb{R}^{|S|\times|A|}: ∥(Pπ−Pπ∗)(Q−Q∗)∥∞≤L∥Q−Q∗∥2∞\|(P^\pi - P^{\pi^*})(Q-Q^*)\|_\infty \leq L\|Q-Q^*\|_2^\infty

Annahme 2: {yk}k≥0\{y_k\}_{k \geq 0} ist eine irreduzible und aperiodische endliche Zustandsmarkov-Kette.

Schrittweite-Auswahl

Wählen Sie die polynomiale Schrittweite αk=α(k+b)−β\alpha_k = \alpha(k+b)^{-\beta}, wobei α,b>0\alpha, b > 0, β∈(0.5,1)\beta \in (0.5, 1).

Gründe für diese Wahl:

  1. Erfüllung der Schlüsselbedingungen des Polyak-Juditsky-Mittelungsschemas
  2. Konstante Schrittweiten verletzen die Bedingungen (i) und (iii), lineare Schrittweiten verletzen Bedingung (ii)
  3. Polynomiale Schrittweiten erfüllen alle notwendigen Bedingungen

Haupttheoretische Ergebnisse

Nicht-asymptotischer zentraler Grenzwertsatz

Theorem 4: Unter den Annahmen 1 und 2 gilt: W1(K−1/2∑k=1KΔk,N~)≤(∣S∣∣A∣)1/2ρ(1−γ)2K1/2⋅O~((ρ(1−γ))β−21−β+Kβ/2ρ−1(1−γ)−1+K1−β+K1−β2ρ−1−β(1−γ)−β)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)

wobei Δk=Qk−Q∗\Delta_k = Q_k - Q^*, N~=(A−1ΣA−⊤)1/2N(0,I)\tilde{N} = (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I).

Korollar 5: Wenn β=2/3\beta = 2/3, vereinfacht sich die Konvergenzrate zu: W1(K−1/2∑k=1KΔk,(A−1ΣA−⊤)1/2N(0,I))≤O~((∣S∣∣A∣)1/2K1/6ρ2(1−γ)3)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)

Funktionaler zentraler Grenzwertsatz

Theorem 6: In der Einstellung von Theorem 4 konvergiert der Partialsummenprozess ΦK(ζ)=K−1/2∑k=1⌊ζK⌋Δk\Phi_K(\zeta) = K^{-1/2}\sum_{k=1}^{\lfloor\zeta K\rfloor}\Delta_k schwach auf D[0,1]D[0,1] gegen (A−1ΣA−⊤)1/2B(⋅)(A^{-1}\Sigma A^{-\top})^{1/2}B(\cdot), wobei B(⋅)B(\cdot) eine standardisierte Brownsche Bewegung ist.

Technische Innovationen und Beweisstrategien

Haupttechnische Herausforderungen

  1. Nicht-Linearität: Q-Learning ist nicht-lineare SA, komplexer als lineare SA
  2. Markov-Rauschen: Asynchrone Aktualisierungen führen nicht-identisch verteiltes Markov-Rauschen ein
  3. Nicht-glatte Operatoren: Der empirische Bellman-Operator in asynchronem Q-Learning ist nicht-glatt

Beweisstrategien

  1. Obere und untere Schranken-Techniken: Durch Einführung von oberen Grenzsequenzen Δk↑\Delta_k^{\uparrow} und unteren Grenzsequenzen Δk↓\Delta_k^{\downarrow}, unter Verwendung des Sandwich-Theorems
  2. Termzerlegung: Zerlegung von ∑k=1KΔk\sum_{k=1}^K \Delta_k in sechs Terme:
    • Term (1): Anfangsfehlterm
    • Term (2): Nicht-linearer Fehlerterm
    • Term (3): Markov-Rauschterm
    • Term (4-5): Korrektionsterme höherer Ordnung
    • Term (6): Martingal-Differenzsequenz
  3. Poisson-Gleichungs-Techniken: Umwandlung von Markov-Rauschen in Martingal-Differenzsequenzen
  4. Martingal-zentraler Grenzwertsatz: Anwendung des nicht-asymptotischen Martingal-CLT von Srikant (2024)

Verwandte Arbeiten

Theorie der stochastischen Approximation

  • Polyak, Juditsky (1992): Klassische Varianzreduktions-Mittelungstechniken
  • Anastasiou et al. (2019): Nicht-asymptotischer CLT für Polyak-Ruppert-gemitteltes SGD
  • Mou et al. (2020): Nicht-asymptotischer CLT für lineare SA

CLT im Reinforcement Learning

  • Xie und Zhang (2022), Li et al. (2023): Funktionale CLT für synchrones Q-Learning
  • Zhang und Xie (2024): Funktionale CLT für asynchrones Q-Learning mit konstanter Schrittweite
  • Srikant (2024), Samsonov et al. (2024): Nicht-asymptotischer CLT für TD-Learning

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Etablierung des ersten nicht-asymptotischen CLT für Q-Learning mit explizit parameterabhängiger Konvergenzrate
  2. Beweis der schwachen Konvergenz des Partialsummenprozesses für asynchrones Q-Learning
  3. Bereitstellung einer theoretischen Grundlage für die Unsicherheitsquantifizierung im Reinforcement Learning

Einschränkungen

  1. Erfordert starke Lipschitz-Annahmen (Annahme 1)
  2. Berücksichtigt nur endliche Zustands-Aktions-Räume
  3. Konvergenzrate ist möglicherweise nicht optimal

Zukünftige Richtungen

  1. Verbesserung der Konvergenzrate
  2. Erweiterung über 1-Wasserstein-Distanz hinaus auf andere Metriken
  3. Berücksichtigung von Funktionsapproximations-Einstellungen

Tiefgreifende Bewertung

Stärken

  1. Bedeutender theoretischer Beitrag: Erstmalige Etablierung eines nicht-asymptotischen CLT für Q-Learning, Schließung einer wichtigen theoretischen Lücke
  2. Technische Innovationen: Geschickte Kombination von Obere-Untere-Schranken-Techniken, Poisson-Gleichungen und Martingal-CLT zur Lösung technischer Probleme
  3. Vollständige Ergebnisse: Gleichzeitige Bereitstellung von nicht-asymptotischen und funktionalen CLTs
  4. Explizite Abhängigkeitsbeziehungen: Konvergenzrate spiegelt explizit die Auswirkungen aller Parameter wider

Schwächen

  1. Starke Annahmen: Lipschitz-Annahmen könnten in der Praxis schwer zu verifizieren sein
  2. Konvergenzrate: Die K−1/6K^{-1/6}-Konvergenzrate ist relativ langsam
  3. Endliche Zustände: Berücksichtigung kontinuierlicher Zustandsräume oder Funktionsapproximation fehlt

Einflussfähigkeit

  1. Theoretischer Wert: Bereitstellung neuer Werkzeuge und Perspektiven für die theoretische Analyse von Q-Learning
  2. Praktische Bedeutung: Schaffung einer theoretischen Grundlage für die Unsicherheitsquantifizierung in Reinforcement-Learning-Algorithmen
  3. Methodologie: Beweisstechniken sind auf andere nicht-lineare SA-Probleme übertragbar

Anwendungsszenarien

  1. Theoretische Analyse von tabellarischen Reinforcement-Learning-Problemen
  2. Konvergenzforschung für asynchrone Aktualisierungsalgorithmen
  3. Statistische Inferenz und Konfidenzintervallkonstruktion im Reinforcement Learning

Literaturverzeichnis

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