提出新算法解决平均奖励TD学习收敛难题，性能媲美折扣设置。
Bridging the Gap Between Average and Discounted TD Learning
- 通过双马尔可夫轨迹采样设计新算法，突破非压缩贝尔曼算子限制。
- 在表格与线性近似下均保证收敛，样本复杂度从四次方降至平方。
- 适合研究强化学习理论或需高效策略评估的开发者使用。
平均奖励设定下的时序差分（TD）学习分析面临显著理论挑战，因为贝尔曼算子对任何范数均不满足压缩性，这使得标准随机更新分析难以应用，而此前方法存在局限。本文提出一种专为平均奖励设定设计的新算法，利用来自两个马尔可夫轨迹的采样。该方法通过保证投影贝尔曼方程唯一解的收敛性，克服了以往缺陷。其收敛性分析统一适用于线性函数逼近与表格型设置，且收敛界中不含显式的维度依赖项。结果与折扣设定下的已知结论一致。此外，算法对问题条件数的依赖性显著改善，样本复杂度从先前文献中的四次方降低至二次方，达到折扣设置下的效率水平。
原文摘要 · Abstract (English)
The analysis of Temporal Difference (TD) learning in the average-reward setting faces notable theoretical difficulties because the Bellman operator is not contractive with respect to any norm. This complicates standard analyses of stochastic updates that are effective in discounted settings. Although a considerable body of literature addresses these challenges, existing theoretical approaches come with limitations. We introduce a novel algorithm designed explicitly for policy evaluation in the average-reward setting, utilizing sampling from two Markovian trajectories. Our proposed method overcomes previous limitations by guaranteeing convergence to the unique solution of a properly defined projected Bellman equation. Notably, and in contrast to earlier work, our convergence analysis is uniformly applicable to both linear function approximation and tabular settings and does not involve explicit dimension-dependent terms in its convergence bounds. These results align with what is known to hold in the discounted setting. Furthermore, our algorithm achieves improved dependence on the problem's condition number, reducing the sample complexity from quartic, as in prior literature, to quadratic scaling, and thus matching the efficiency seen in the discounted setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。