首个在对抗性环境中实现低后悔与约束违规的线性CMDP算法
Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses
- 引入加权LogSumExp软最大策略，适应对抗损失
- 首次实现后悔与约束违规均达$ ilde{O}(K^{3/4})$
- 适合研究在线决策与鲁棒强化学习的学者
现有线性约束马尔可夫决策过程（CMDPs）研究多集中于随机设定，其中损失和成本为固定值或来自固定分布。然而此类模型在对抗性环境变化下极为脆弱。为此，我们提出一种针对在线有限时域对抗性线性CMDPs的原始-对偶策略优化算法：损失由对手自适应选择（全信息反馈），成本为随机（弱信息反馈）。该算法是首个在此设定下实现次线性后悔与约束违规的算法，两者均被证明为$ ilde{ m O}(K^{3/4})$，其中$K$为回合数。算法引入并使用一类新型策略——加权LogSumExp软最大策略，以适应对抗性损失函数。核心贡献包括：(i) 针对这类策略的新覆盖数论证；(ii) 两项创新算法组件——周期性策略混合与正则化对偶更新，有效控制覆盖数与对偶变量。数值实验验证了理论结果的有效性。
原文摘要 · Abstract (English)
Existing work on linear constrained Markov decision processes (CMDPs) has primarily focused on stochastic settings, where the losses and costs are either fixed or drawn from fixed distributions. However, such formulations are inherently vulnerable to adversarially changing environments. To overcome this limitation, we propose a primal-dual policy optimization algorithm for online finite-horizon {adversarial} linear CMDPs, where the losses are adversarially chosen under full-information feedback and the costs are stochastic under bandit feedback. Our algorithm is the \emph{first} to achieve sublinear regret and constraint violation bounds in this setting, both bounded by $\widetilde{\mathcal{O}}(K^{3/4})$, where $K$ denotes the number of episodes. The algorithm introduces and runs with a new class of policies, which we call weighted LogSumExp softmax policies, designed to adapt to adversarially chosen loss functions. Our main result stems from the following key contributions: (i) a new covering number argument for the weighted LogSumExp softmax policies, and (ii) two novel algorithmic components -- periodic policy mixing and a regularized dual update -- which allow us to effectively control both the covering number and the dual variable. We also report numerical results that validate our theoretical findings on the performance of the algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。