提出新算法解决非稳态马尔可夫决策问题的后悔率优化。
Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization
- 基于多级蒙特卡洛与显式预热机制，处理无循环结构的平均奖励约束MDP。
- 在有限时间内实现$ ilde{O}( ext{sqrt}{T})$的后悔率和约束违规量上界。
- 适用于存在瞬态状态的复杂场景，适合强化学习理论研究者。
我们研究在无循环假设下具有通用策略参数化的无限时域平均奖励约束马尔可夫决策过程（CMDPs）。现有约束强化学习的后悔率分析大多依赖遍历性或强混合时间假设，但在存在瞬态状态时失效。本文提出一种原始-对偶自然演员-评论家算法，利用多级蒙特卡洛（MLMC）估计器和显式预热机制，在无需混合时间预言机的前提下处理无循环动态。分析表明，其有限时间后悔率和累计约束违规量上界为$ ilde{O}( ext{sqrt}{T})$，仅受策略与评论家参数化带来的近似误差影响，从而将最优阶保证扩展至更广泛的CMDP类别。
原文摘要 · Abstract (English)
We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the unichain assumption and general policy parameterizations. Existing regret analyses for constrained reinforcement learning largely rely on ergodicity or strong mixing-time assumptions, which fail to hold in the presence of transient states. We propose a primal--dual natural actor--critic algorithm that leverages multi-level Monte Carlo (MLMC) estimators and an explicit burn-in mechanism to handle unichain dynamics without requiring mixing-time oracles. Our analysis establishes finite-time regret and cumulative constraint violation bounds that scale as $\tilde{O}(\sqrt{T})$, up to approximation errors arising from policy and critic parameterization, thereby extending order-optimal guarantees to a significantly broader class of CMDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。