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

Central Limit Theorems for Asynchronous Averaged Q-Learning

基本信息

  • 论文ID: 2509.18964
  • 标题: Central Limit Theorems for Asynchronous Averaged Q-Learning
  • 作者: Xingtu Liu (Simon Fraser University)
  • 分类: cs.LG math.OC stat.ML
  • 发表会议: OPT2025: 17th Annual Workshop on Optimization for Machine Learning
  • 论文链接: https://arxiv.org/abs/2509.18964

摘要

本文为异步更新下的Polyak-Ruppert平均Q学习建立了中心极限定理。文章证明了非渐近中心极限定理，其在Wasserstein距离下的收敛率明确反映了对迭代次数、状态-动作空间大小、折扣因子和探索质量的依赖关系。此外，还导出了函数中心极限定理，表明部分和过程弱收敛到布朗运动。

研究背景与动机

问题背景

  1. Q学习的重要性: Q学习是强化学习中最广泛使用的算法之一，直接从经验轨迹学习最优动作价值函数，在Atari游戏、围棋、机器人操作和大语言模型对齐等领域取得了巨大成功。
  2. 理论分析的挑战:
    • Q学习可以解释为随机逼近(SA)的实例，但异步Q学习是带有马尔科夫噪声的非线性SA问题
    • 相比线性SA和TD学习，Q学习的分析更具挑战性，因为其非线性、非光滑算子和非平稳过程的特点
    • 异步更新进一步引入了马尔科夫噪声，增加了分析复杂度
  3. 现有工作的局限性:
    • 已有工作建立了同步Q学习的函数CLT，但同步Q学习只考虑鞅噪声
    • Zhang和Xie (2024)为常数步长的异步Q学习建立了函数CLT，但常数步长不满足建立非渐近CLT的必要条件
    • 目前尚无Q学习的非渐近CLT，即使在同步设置下也是如此

研究动机

建立中心极限定理对于理解算法的统计性质至关重要，这种渐近正态性对强化学习中的不确定性量化和统计推断具有重要意义。

核心贡献

  1. 首个Q学习非渐近CLT: 证明了异步平均Q学习的非渐近中心极限定理，收敛率为 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. 函数中心极限定理: 建立了衰减步长下异步Q学习的函数CLT，显示部分和过程弱收敛到布朗运动
  3. 显式依赖关系: 收敛率明确反映了对迭代次数K、状态-动作空间大小|S||A|、折扣因子γ和探索质量ρ的依赖关系
  4. 技术创新: 解决了非线性、马尔科夫噪声和非光滑算子带来的分析挑战

方法详解

任务定义

考虑无限水平折扣马尔科夫决策过程(MDP) M=⟨S,A,P,r,γ⟩M = \langle S, A, P, r, \gamma \rangle，其中：

  • SS: 状态集合
  • AA: 动作集合
  • P:S×A→ΔSP: S \times A \rightarrow \Delta_S: 转移概率函数
  • γ∈[0,1)\gamma \in [0,1): 折扣因子

目标是学习最优Q函数 Q∗=max⁡πQπQ^* = \max_\pi Q^\pi。

异步Q学习算法

异步Q学习维护Q函数估计器 QkQ_k，更新规则为： Qk+1=Qk+αk(Fk−Qk)Q_{k+1} = Q_k + \alpha_k(F_k - Q_k)

其中：

  • 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)

关键假设

假设1: 存在最优策略 π∗\pi^* 使得对 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

假设2: {yk}k≥0\{y_k\}_{k \geq 0} 是不可约且非周期的有限状态马尔科夫链。

步长选择

选择多项式步长 αk=α(k+b)−β\alpha_k = \alpha(k+b)^{-\beta}，其中 α,b>0\alpha, b > 0，β∈(0.5,1)\beta \in (0.5, 1)。

这种选择的原因：

  1. 满足Polyak-Juditsky平均方案的关键条件
  2. 常数步长违反条件(i)和(iii)，线性步长违反条件(ii)
  3. 多项式步长满足所有必要条件

主要理论结果

非渐近中心极限定理

定理4: 在假设1和2下，有： 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)

其中 Δ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)。

推论5: 当 β=2/3\beta = 2/3 时，收敛率简化为： 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)

函数中心极限定理

定理6: 在定理4的设置下，部分和过程 ΦK(ζ)=K−1/2∑k=1⌊ζK⌋Δk\Phi_K(\zeta) = K^{-1/2}\sum_{k=1}^{\lfloor\zeta K\rfloor}\Delta_k 在 D[0,1]D[0,1] 上弱收敛到 (A−1ΣA−⊤)1/2B(⋅)(A^{-1}\Sigma A^{-\top})^{1/2}B(\cdot)，其中 B(⋅)B(\cdot) 是标准布朗运动。

技术创新与证明思路

主要技术挑战

  1. 非线性: Q学习是非线性SA，比线性SA复杂
  2. 马尔科夫噪声: 异步更新引入非独立同分布的马尔科夫噪声
  3. 非光滑算子: 异步Q学习中的经验Bellman算子是非光滑的

证明策略

  1. 上下界技术: 通过引入上界序列 Δk↑\Delta_k^{\uparrow} 和下界序列 Δk↓\Delta_k^{\downarrow}，利用夹逼定理
  2. 项分解: 将 ∑k=1KΔk\sum_{k=1}^K \Delta_k 分解为6个项：
    • Term (1): 初始误差项
    • Term (2): 非线性误差项
    • Term (3): 马尔科夫噪声项
    • Term (4-5): 高阶修正项
    • Term (6): 鞅差分序列
  3. Poisson方程技术: 将马尔科夫噪声转化为鞅差分序列
  4. 鞅中心极限定理: 应用Srikant (2024)的非渐近鞅CLT

相关工作

随机逼近理论

  • Polyak-Juditsky (1992): 经典的平均化方差减少技术
  • Anastasiou等 (2019): Polyak-Ruppert平均SGD的非渐近CLT
  • Mou等 (2020): 线性SA的非渐近CLT

强化学习中的CLT

  • Xie和Zhang (2022), Li等 (2023): 同步Q学习的函数CLT
  • Zhang和Xie (2024): 常数步长异步Q学习的函数CLT
  • Srikant (2024), Samsonov等 (2024): TD学习的非渐近CLT

结论与讨论

主要结论

  1. 建立了首个Q学习的非渐近CLT，收敛率明确依赖于问题参数
  2. 证明了异步Q学习部分和过程的弱收敛性
  3. 为强化学习中的不确定性量化提供了理论基础

局限性

  1. 需要较强的Lipschitz假设(假设1)
  2. 仅考虑有限状态-动作空间
  3. 收敛率可能不是最优的

未来方向

  1. 改进收敛率
  2. 扩展到1-Wasserstein距离之外的其他度量
  3. 考虑函数逼近设置

深度评价

优点

  1. 理论贡献重大: 首次建立Q学习的非渐近CLT，填补了重要理论空白
  2. 技术创新: 巧妙结合上下界技术、Poisson方程和鞅CLT解决技术难题
  3. 结果完整: 同时给出非渐近和函数CLT
  4. 依赖关系明确: 收敛率明确反映各参数的影响

不足

  1. 假设较强: Lipschitz假设在实践中可能难以验证
  2. 收敛率: K−1/6K^{-1/6} 的收敛率相对较慢
  3. 有限状态: 未考虑连续状态空间或函数逼近

影响力

  1. 理论价值: 为Q学习理论分析提供新工具和视角
  2. 实用意义: 为强化学习算法的不确定性量化奠定理论基础
  3. 方法论: 证明技术可推广到其他非线性SA问题

适用场景

  1. 表格型强化学习问题的理论分析
  2. 异步更新算法的收敛性研究
  3. 强化学习中的统计推断和置信区间构造

参考文献

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