对抗性线性 CMDP 的速率最优算法

View PDF HTML (experimental)

Abstract:We study episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions, where both the loss and constraint functions may vary adversarially across episodes. The best previous algorithm achieves $\widetilde{\mathcal{O}}(K^{3/4})$ regret and cumulative constraint violation, leaving a gap to the optimal $\widetilde{\mathcal{O}}(\sqrt{K})$ dependence on the number of episodes $K$. We close this gap by proposing a new primal dual algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{K})$ regret and cumulative constraint violation without assuming Slater's condition. The main challenge is that learning linear CMDPs requires uniform concentration over a value function class with a controlled covering number, whereas standard techniques in constrained online learning, such as policy mixing, can make this class more complex. Our algorithm combines adaptive Follow the Regularized Leader (FTRL), contracted value estimation, and an exponential Lyapunov function. An adaptive dual regularizer offsets the dependence on the dual weights in the primal regret bound, removing the need for policy mixing. We further show that the normalization in the FTRL update bounds the policy parameters independently of the magnitudes of the dual weights, which explains why the resulting policy class remains compatible with uniform concentration. Under feature access, the computational complexity is independent of the size of the state space.

Subjects:	Machine Learning (cs.LG)
Cite as:	arXiv:2610.00927 [cs.LG]
	(or arXiv:2610.00927v1 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2610.00927 arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Kihyun Yu [view email]
[v1] Thu, 1 Oct 2026 02:03:07 UTC (166 KB)