Rate-Optimal Algorithm for Adversarial Linear CMDPs

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. We further extend the algorithm to achieve the same $\widetilde{\mathcal{O}}(\sqrt{K})$ guarantees for regret and hard constraint violation, which does not allow constraint violations to cancel across episodes. 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 1 October 2026

  SmoothOperator: Enhancing Representations for Fine-grained Open-set Recognition via Modulated Label Smoothing

  Thiru Thillai Nadarasar Bahavan, Yu Xia, Sachith Seneviratne and 1 other
• arXiv preprint · 2 October 2026

  Seer: Maximum Likelihood Regression for Learning-Speed Curves

  Carl Myers Kadie
• arXiv preprint · 1 October 2026

  Fixing a Model That Learned Worse Cancer Means Lower Risk: Monotonic Constraints in Bladder Cancer Recurrence Prediction

  Saram Abbas, David Thomas, Naeem Soomro and 3 others
• arXiv preprint · 2 October 2026

  Scale-Recursive Rectified Flows for Few-Step Precipitation Ensembles

  Shunya Nagashima and Takumi Bannai
• arXiv preprint · 1 October 2026

  Don't Waste the Noise: Importance-Guided Perturbation Allocation under Joint Global and Local Constraints

  Melika Shirian and Kianoosh Vadaei

All new papers in Machine Learning