分析带马尔可夫噪声的非扩张随机逼近，首次证明平均奖励TD学习收敛到样本路径依赖的不动点。
Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
- 研究非扩张算子驱动的随机逼近，引入泊松方程噪声项的新界。
- 给出渐近与有限样本两方面的理论分析，适用于平均奖励强化学习场景。
- 适合关注强化学习收敛性、随机优化理论的研究者。
随机逼近是一类强大且成功的算法，但以往大多数分析集中于由压缩算子驱动的情形，不适用于某些重要强化学习场景（如平均奖励设置）。本文转而研究仅满足非扩张性质的随机逼近，并针对带有马尔可夫噪声的情形，提供渐近与有限样本分析。分析的核心是基于泊松方程导出的噪声项新界。作为应用，首次证明经典表格型平均奖励时序差分学习收敛至一个样本路径依赖的不动点。
原文摘要 · Abstract (English)
Stochastic approximation is a powerful class of algorithms with celebrated success. However, a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforcement learning settings like the average reward setting. This work instead investigates stochastic approximations with merely nonexpansive operators. In particular, we study nonexpansive stochastic approximations with Markovian noise, providing both asymptotic and finite sample analysis. Key to our analysis are novel bounds of noise terms resulting from the Poisson equation. As an application, we prove for the first time that classical tabular average reward temporal difference learning converges to a sample-path dependent fixed point.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。