新算法无需满足斯莱特条件，可同时处理随机与对抗约束下的在线强化学习。
Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
- 不依赖斯莱特条件，在随机约束下实现√T级累积误差与约束违反。
- 在对抗约束下，约束违反和α-遗憾均保持亚线性，优于现有最优算法。
- 适合需严格安全约束的现实场景，如自动驾驶、医疗决策等复杂系统。
我们研究了在随机与对抗性约束下的在线周期性约束马尔可夫决策过程（CMDPs）。提出一种新算法，其性能显著优于最新提出的“双世界最优”算法（Stradi et al., 2025）。在随机设定下（约束从固定但未知分布中采样），该方法在不依赖斯莱特条件的情况下，实现了$ ilde{/mathcal{O}}( ext{√}T)$的遗憾与约束违反，适用于不存在严格可行解的情形。此外，还对更强的“正约束违反”概念提供了保证，不允许早期严重违反后通过严格安全策略恢复。在对抗设定下（约束可在各周期间任意变化），算法确保了无斯莱特条件下的亚线性约束违反，并实现了相对于无约束最优解的亚线性$α$-遗憾，其中$α$为合适的乘法近似因子。通过合成实验验证了算法的实际有效性。
原文摘要 · Abstract (English)
We study \emph{online episodic Constrained Markov Decision Processes} (CMDPs) under both stochastic and adversarial constraints. We provide a novel algorithm whose guarantees greatly improve those of the state-of-the-art best-of-both-worlds algorithm introduced by Stradi et al. (2025). In the stochastic regime, \emph{i.e.}, when the constraints are sampled from fixed but unknown distributions, our method achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation without relying on Slater's condition, thereby handling settings where no strictly feasible solution exists. Moreover, we provide guarantees on the stronger notion of \emph{positive} constraint violation, which does not allow to recover from large violation in the early episodes by playing strictly safe policies. In the adversarial regime, \emph{i.e.}, when the constraints may change arbitrarily between episodes, our algorithm ensures sublinear constraint violation without Slater's condition, and achieves sublinear $α$-regret with respect to the \emph{unconstrained} optimum, where $α$ is a suitably defined multiplicative approximation factor. We further validate our results through synthetic experiments, showing the practical effectiveness of our algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。