提出新方法，证明强化学习在马尔可夫噪声下几乎必然收敛速度接近最优。
Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
- 用泊松-莫罗漂移构造新李雅普诺夫函数，处理马尔可夫噪声
- 幂律学习率下收敛速度接近 $o(n^{1-2η})$，调和率下接近 $o(n^{-1})$
- 适合关注理论极限的强化学习研究者，尤其关心收敛速率分析
在马尔可夫噪声下建立随机逼近与强化学习的几乎必然收敛速率是一个基础性理论挑战。本文针对一类期望更新为压缩映射的随机逼近算法（如 $Q$-learning、线性时序差分学习）取得进展。对于幂律学习率 $O(n^{-η})$（$η o(1/2,1)$），得到几乎必然收敛率任意接近 $o(n^{1-2η})$；对于调和学习率 $O(n^{-1})$，得到几乎必然收敛率任意接近 $o(n^{-1})$，该结果很强，因接近独立同分布噪声下由迭代对数律给出的最优率 $O(n^{-1}"log"log"n)$。分析关键在于一种新颖的李雅普诺夫漂移构造：将泊松方程修正用于马尔可夫噪声，结合经典的莫罗包络光滑化技术。
原文摘要 · Abstract (English)
Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise is a fundamental theoretical challenge. We make progress towards this challenge for a class of stochastic approximation algorithms whose expected updates are contractive, a setting that arises in many reinforcement learning algorithms such as $Q$-learning and linear temporal difference learning. Specifically, for a power-law learning rate $O(n^{-η})$ with $η\in (1/2, 1)$, we obtain an almost sure convergence rate arbitrarily close to $o(n^{1 - 2η})$. For a harmonic learning rate $O(n^{-1})$, we obtain an almost sure convergence rate arbitrarily close to $o(n^{-1})$, which we argue is a strong result because it is close to the optimal rate $O(n^{-1}\log\log n)$ given by the law of the iterated logarithm (for a special case of i.i.d. noise). Key to our analysis is a novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the well-established Moreau-envelope smoothing for the contractive mapping.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。