揭示强化学习中累积奖励的集中规律，为策略评估提供理论支撑。
Concentration of Cumulative Reward in Markov Decision Processes
- 基于鞅分解与固定点方程，统一分析无限与有限时域下的奖励集中性。
- 给出大数定律、中心极限定理等渐近性质，以及非渐近的霍费丁型不等式。
- 适用于强化学习中的策略比较与后悔率等价性分析，理论研究者必读。
本文研究马尔可夫决策过程（MDPs）中累积奖励的集中性质，涵盖渐近与非渐近两种情形。提出一种统一方法，覆盖无限时域（平均奖励与折扣奖励框架）和有限时域设置。渐近结果包括大数定律、中心极限定理及迭代对数律；非渐近界包含霍费丁型不等式与非渐近版本的迭代对数律。此外，探讨了两项关键应用：一是任意两个平稳策略间奖励路径差的行为分析；二是文献中两种后悔定义在速率上的等价性证明。证明依赖于累积奖励的鞅分解、策略评估固定点方程解的性质，以及鞅差序列的渐近与非渐近集中结果。
原文摘要 · Abstract (English)
In this paper, we investigate the concentration properties of cumulative reward in Markov Decision Processes (MDPs), focusing on both asymptotic and non-asymptotic settings. We introduce a unified approach to characterize reward concentration in MDPs, covering both infinite-horizon settings (i.e., average and discounted reward frameworks) and finite-horizon setting. Our asymptotic results include the law of large numbers, the central limit theorem, and the law of iterated logarithms, while our non-asymptotic bounds include Azuma-Hoeffding-type inequalities and a non-asymptotic version of the law of iterated logarithms. Additionally, we explore two key implications of our results. First, we analyze the sample path behavior of the difference in rewards between any two stationary policies. Second, we show that two alternative definitions of regret for learning policies proposed in the literature are rate-equivalent. Our proof techniques rely on a martingale decomposition of cumulative reward, properties of the solution to the policy evaluation fixed-point equation, and both asymptotic and non-asymptotic concentration results for martingale difference sequences.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。