提出新算法，显著降低弱通信平均奖励约束MDP的学习误差。
Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
- 基于占用测度几何结构证明强对偶性，突破非凸难题。
- 算法实现$ ilde{ m O}(T^{2/3})$的遗憾与约束违规界，优于已有最优结果。
- 适合研究强化学习约束优化与在线决策的学者参考。
我们研究在弱通信假设下的无限时域平均奖励约束马尔可夫决策过程（CMDPs）。首先，我们在有限状态与动作空间下，针对平稳策略建立了弱通信平均奖励CMDPs的强对偶性。尽管该设置下缺乏线性规划形式且存在非凸性，但通过精心利用占用测度集的几何结构，我们证明强对偶性依然成立。其次，基于此结果，我们提出了一个原始-对偶裁剪值迭代算法，用于学习弱通信平均奖励线性CMDPs。该算法实现了$ ilde{ m O}(T^{2/3})$的遗憾与约束违规界，其中$T$为交互次数，优于现有最佳界限。我们的方法将裁剪值迭代扩展至约束场景，并引入有限时域近似以稳定对偶变量，这对获得更优遗憾界至关重要。为分析该方法，我们开发了一种基于强对偶性的新思路，可将复合拉格朗日遗憾分解为独立的遗憾与约束违规界。
原文摘要 · Abstract (English)
We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Our contributions are twofold. First, we establish strong duality for weakly communicating average-reward CMDPs over stationary policies with finite state and action spaces. Despite the absence of a linear programming formulation and the resulting nonconvexity under the weakly communicating setting, we show that strong duality still holds by carefully exploiting the geometric structure of the occupation measure set. Second, building on this result, we propose a primal--dual clipped value iteration algorithm for learning weakly communicating average-reward linear CMDPs. Our algorithm achieves regret and constraint violation bounds of $\widetilde{\mathcal{O}}(T^{2/3})$, improving upon the best known bounds, where $T$ denotes the number of interactions. Our approach extends clipped value iteration to the constrained setting and adapts it to a finite-horizon approximation, which stabilizes the dual variable and is crucial for achieving improved regret bounds. To analyze this, we develop a novel approach based on strong duality that enables the decomposition of the composite Lagrangian regret into separate bounds on regret and constraint violation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。