提出新算法，实现平均奖励马尔可夫决策的最优后悔率。
Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach
- 基于自然策略梯度与分批更新，结合函数逼近提升可扩展性。
- 在单链假设下达到 $ ilde{O}( ext{sqrt}(T))$ 的最优后悔率。
- 适用于存在周期性或瞬态状态的复杂强化学习场景。
Actor-Critic 方法因可扩展性广受应用，但现有针对无限时域平均奖励马尔可夫决策过程（MDPs）的理论分析常依赖严格遍历性假设。本文提出 NAC-B：一种带分批机制的自然演员-评论家方法，在允许瞬态状态和周期性的单链假设下，实现了 $ ilde{O}( ext{sqrt}(T))$ 的阶最优后悔率。该假设是经典策略梯度定理在平均奖励设置下仍成立的最弱条件之一。NAC-B 在演员和评论家中均采用函数逼近，支持大规模状态与动作空间。分批设计缓解了 MDP 中潜在的周期性问题，并降低了梯度估计的随机性。分析通过引入常数 $C_{ ext{hit}}$ 与 $C_{ ext{tar}}$ 形式化了这些优势，二者刻画了马尔可夫样本经验平均收敛到平稳分布的速率。
原文摘要 · Abstract (English)
Actor-Critic methods are widely used for their scalability, yet existing theoretical guarantees for infinite-horizon average-reward Markov Decision Processes (MDPs) often rely on restrictive ergodicity assumptions. We propose NAC-B, a Natural Actor-Critic with Batching, that achieves order-optimal regret of $\tilde{O}(\sqrt{T})$ in infinite-horizon average-reward MDPs under the unichain assumption, which permits both transient states and periodicity. This assumption is among the weakest under which the classic policy gradient theorem remains valid for average-reward settings. NAC-B employs function approximation for both the actor and the critic, enabling scalability to problems with large state and action spaces. The use of batching in our algorithm helps mitigate potential periodicity in the MDP and reduces stochasticity in gradient estimates, and our analysis formalizes these benefits through the introduction of the constants $C_{\text{hit}}$ and $C_{\text{tar}}$, which characterize the rate at which empirical averages over Markovian samples converge to the stationary distribution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。