arXiv：cs.LG· Qian Zuo, Francesco Emanuele Stradi·· 3 小时前
面向随机硬约束对抗 MDP 的最优遗憾：MA-OPS 算法
Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints
AI 导读
针对带随机硬约束的对抗损失情景式约束 MDP，研究者提出 MA-OPS 算法，结合对 Slater 边际的乐观搜索与对所选出策略的悲观评估，安全学习具有大可行性边际的策略，从而在每轮满足约束的同时最小化遗憾，达到 Õ(√T/ρ + 1/(dρ)) 的遗憾上界。该工作进一步给出匹配下界，证明遗憾对 T、d、ρ 的依赖在对数因子内已是最优。
正文
Abstract:We study episodic constrained Markov decision processes with adversarial losses under stochastic hard constraints. Specifically, starting from a known strictly feasible policy with margin $d$, we seek to obtain optimal regret while satisfying the expected cost constraints in every episode. In this setting, Stradi et al. (2025) show that a carefully designed mixing rule attains regret of order $\widetilde{\mathcal{O}}(\sqrt{T}/\min\{d,d^2\})$. Interestingly, they also provide a lower bound of order $\Omega(\sqrt{T}/\rho)$ for the same setting, where $\rho$ is the Slater margin of the offline problem and can be much larger than $d$. In this work, we build on their approach to obtain optimal regret dependence on these margins. Specifically, we propose MA-OPS, an algorithm that combines an optimistic search for the Slater margin with a pessimistic evaluation of the selected policies to safely learn a policy with a large feasibility margin. This policy is then used to minimize regret while satisfying the constraints at every episode. In particular, we show that MA-OPS attains regret $\widetilde{\mathcal{O}}(\sqrt{T}/\rho + 1/(d\rho))$. Finally, we provide a matching lower bound, showing that the dependence on $T$, $d$, $\rho$ in the regret bound is optimal up to logarithmic factors.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.12153 [cs.LG] |
| (or arXiv:2610.12153v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12153 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Qian Zuo [view email]
[v1]
Thu, 8 Oct 2026 15:36:00 UTC (49 KB)
来源：arXiv：cs.LG · arxiv.org