Rate-Optimal Algorithm for Adversarial Linear CMDPs

Kihyun Yu; Honghao Wei; Dabeen Lee

cs.LGOct 1, 2026

Rate-Optimal Algorithm for Adversarial Linear CMDPs

Authors: Kihyun Yu, Honghao Wei, Dabeen Lee

Organizations: KAIST · Washington State University · Seoul National University

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.

Figures & tables

Algorithm	MDP	Loss	Constr.	Rate	$\|{\mathcal{S}}\|$ -free	Slater-free	Hard
Roy and Das (2026)	Tabular	Adv.	Adv.	$\sqrt{K}$	✗	✓	✓
Peng et al. (2026)	Linear	Sto.	Sto.	$\sqrt{K}$	✓	✗	✓
Peng et al. (2026)	Linear	Sto.	Sto.	$K^{3/4}$	✓	✓	✓
Yu et al. (2026a)	Lin. Mixture	Adv.	Sto.	$\sqrt{K}$	✗	✗	✗
Yu et al. (2026b)	Linear	Adv.	Sto.	$K^{3/4}$	✓	✗	✗
Algorithm 1	Linear	Adv.	Adv.	$\sqrt{K}$	✓	✓	✗

Table 1 : Comparison of recent algorithms for CMDPs. Here, Sto. and Adv. denote stochastic and adversarial, respectively. The

|{\mathcal{S}}|

-free column indicates whether the computational complexity is independent of

|{\mathcal{S}}|

. Slater-free indicates that neither the algorithm nor its guarantees require Slater’s condition. Hard indicates whether a hard constraint violation guarantee is provided.

\pi_{h}^{k+1}(\cdot|s)\in\argmin_{\pi(\cdot|s)\in\Delta({\mathcal{A}})}\ \psi_{k}(\pi(\cdot|s))+\sum_{\tau=k(m)}^{k}(\hat{Q}_{f,h}^{\tau}(s,\cdot)+Y_{\tau}\hat{Q}_{g,h}^{\tau}(s,\cdot))^{\top}\pi(\cdot|s)

Algorithm 1 Rate-Optimal Algorithm for Adversarial Linear CMDPs

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

$\bm{\mu}_{h}$	the parameters for transition kernel
$\bm{\theta}_{f,h}^{k},\bm{\theta}_{g,h}^{k}$	the parameters for loss and constraint functions
$\bm{\phi}$	the known feature map
$\bar{\bm{\phi}}_{h}^{m}$	the contracted feature
$V_{f^{k},h}^{\pi},\hat{V}_{f,h}^{k}$	the value function and its estimate
$Q_{f^{k},h}^{\pi},\hat{Q}_{f,h}^{k}$	the $Q$ -function and its estimate
$\bar{\mathbb{P}}_{h}^{m}$	the transition kernel of a contracted CMDP in epoch $m\in E$

Appendix

Table 2 : Summary of Notation

\alpha_{k}=\frac{1}{4}\sqrt{\sum_{\tau=1}^{k}L_{\tau}^{2}}\quad\text{where}\quad||\nabla_{\tau}||_{\infty}\leq L_{\tau}\;\forall\tau\in[k]

Appendix

Algorithm 2 Adaptive FTRL for online convex optimization with the probability simplex

\pi_{h}^{k+1}(\cdot|s)\in\argmin_{\pi(\cdot|s)\in\Delta({\mathcal{A}})}\ \psi_{k}(\pi(\cdot|s))+\sum_{\tau=k(m)}^{k}(\hat{Q}_{f,h}^{\tau}(s,\cdot)+{\color[rgb]{0.8242,0.1367,0.1367}\bar{Y}_{\tau}}\hat{Q}_{g,h}^{\tau}(s,\cdot))^{\top}\pi(\cdot|s)

Appendix

Algorithm 3 Algorithm for Hard Constraint Violation

Figure 1 : Cumulative regret (left) and the positive part of cumulative constraint violation (right) for $K=5{,}000$ episodes. Curves show averages over five seeds; shaded regions indicate 95% confidence intervals.

Explore similar work

May 12, 2026cs.LG

Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses

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.

Kihyun Yu, Seoungbin Bae, Dabeen Lee

Department of Industrial and Systems Engineering KAIST · Department of Mathematical Sciences Seoul National University · Research Institute of Mathematics, Seoul National University; Interdisciplinary Program in Artificial Intelligence, Seoul National University; Korea Institute for Advanced Study

Primal-Dual Methods Markov Decision Processes Adversarial Training

Ask PDF

Sep 24, 2025cs.LG

Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints

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.

Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni +2

Politecnico di Milano

Markov Decision Processes Stochastic Optimization \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Structural Constraints Stochastic Adversarial Robustness

Ask PDF

May 12, 2026cs.LG

Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Our contributions are twofold. First, we establish strong duality for weakly communicating average-reward CMDPs over stationary policies with finite state and action spaces. Despite the absence of a linear programming formulation and the resulting nonconvexity under the weakly communicating setting, we show that strong duality still holds by carefully exploiting the geometric structure of the occupation measure set. Second, building on this result, we propose a primal--dual clipped value iteration algorithm for learning weakly communicating average-reward linear CMDPs. Our algorithm achieves regret and constraint violation bounds of

\widetilde{\mathcal{O}}(T^{2/3})

, improving upon the best known bounds, where

T

denotes the number of interactions. Our approach extends clipped value iteration to the constrained setting and adapts it to a finite-horizon approximation, which stabilizes the dual variable and is crucial for achieving improved regret bounds. To analyze this, we develop a novel approach based on strong duality that enables the decomposition of the composite Lagrangian regret into separate bounds on regret and constraint violation.

Kihyun Yu, Beomhan Baek, Dabeen Lee

1KAIST · 2Seoul National University

Markov Decision Processes Optimal Regret Primal-Dual Methods Regret

Ask PDF