提出首个高效求解对抗奖励下线性混合约束MDP的近优算法
Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards
- 设计带正则化的对偶更新，实现漂移分析以应对奖励变化
- 实现$ ilde{O}( ext{d}^2 ext{H}^3 ext{K})$近似最优后悔与约束违反界
- 适合研究安全强化学习与对抗环境下的高效决策问题
我们研究在全信息反馈和未知转移核条件下，有限时域线性混合约束马尔可夫决策过程（CMDPs）中的安全强化学习问题，其中奖励为对抗性。本文提出一种原-对偶策略优化算法，在温和条件下实现了$ ilde{O}(d^2 H^3 K)$的后悔与约束违反上界，其中$d$为特征维数，$H$为时域长度，$K$为回合数。据我们所知，这是首个针对对抗奖励下线性混合CMDPs的可证明高效的算法。特别地，其后悔界近似最优，仅差对数因子于已知极小极大下界。核心思想是引入正则化对偶更新，从而支持漂移分析；这一机制至关重要，因为当奖励跨回合变化时，强对偶分析无法直接应用。此外，我们将加权岭回归参数估计扩展至约束情形，构造更紧的置信区间，这对推导近优后悔界至关重要。
原文摘要 · Abstract (English)
We study safe reinforcement learning in finite-horizon linear mixture constrained Markov decision processes (CMDPs) with adversarial rewards under full-information feedback and an unknown transition kernel. We propose a primal-dual policy optimization algorithm that achieves regret and constraint violation bounds of $\widetilde{O}(\sqrt{d^2 H^3 K})$ under mild conditions, where $d$ is the feature dimension, $H$ is the horizon, and $K$ is the number of episodes. To the best of our knowledge, this is the first provably efficient algorithm for linear mixture CMDPs with adversarial rewards. In particular, our regret bound is near-optimal, matching the known minimax lower bound up to logarithmic factors. The key idea is to introduce a regularized dual update that enables a drift-based analysis. This step is essential, as strong duality-based analysis cannot be directly applied when reward functions change across episodes. In addition, we extend weighted ridge regression-based parameter estimation to the constrained setting, allowing us to construct tighter confidence intervals that are crucial for deriving the near-optimal regret bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。