Instance-Dependent Regret for CMDPs with Step-Wise Constraints

Qian Zuo; Francesco Emanuele Stradi; Leyang Xue; Sattar Vakili

cs.LGOct 1, 2026

Instance-Dependent Regret for CMDPs with Step-Wise Constraints

Authors: Qian Zuo, Francesco Emanuele Stradi, Leyang Xue, Sattar Vakili

Organizations: University of Edinburgh · Politecnico di Milano · University College London

Abstract

We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order $\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_Σ,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$ over $K$ episodes, where $H$ is the horizon of a single episode, while $S$ and $A$ are the numbers of states and actions, respectively. Here, $\mathrm{Var}^{\star}$ is the maximum return variance among safe policies, $\mathbb{V}_Σ$ is the variance accumulated before the first unsafe action is encountered, and $\mathcal{C}$ captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains $\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$ step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in $K$ . Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.

Figures & tables

Figure 1: The structure of the safe subgraph reshapes transition variance. All panels share the same reward function and transition kernel and differ only in their costs. Changing only the costs removes the stochastic branch in panel (a) and retains it in panels (b)–(c). Its successors have equal continuation values and zero transition variance in panel (b), but unequal values and positive transition variance in panel (c). With

\tau=1/2

, crossed actions have cost

1>\tau

, while all other actions have cost

0

. Blue solid elements denote the safe subgraph, gray solid elements denote actions excluded by the cost threshold and their transitions, and red dashed elements denote exclusion because a successor has no safe continuation.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Four safe subgraph topologies on the same $H=6$ gadget-chain MDP (Example 1 ). Each row shows the safe subgraph under a different cost function. Black solid edges are safe. Red dashed edges are unsafe. In a closed gadget, both actions at $s^{\prime}_{B,i}$ are unsafe, so $a_{\mathrm{st},i}$ fails the successor-viability condition and only $a_{\mathrm{det},i}$ remains. In an open gadget, $a_{\mathrm{det},i}$ and $\beta_{1,i}$ are unsafe, leaving a successor-value gap of one by ( F.10 ). Dotted black edges show the branch of $a_{\mathrm{st}}$ to $s^{\prime}_{A,i}$ . Gadget indices are omitted from the action labels.

Panel of Figure 3 — Figure 3: Regret and safety in stochastic navigation. Panels (a) and (b) show strong regret and cumulative step-wise violation. Panels (c) and (d) show policy value and expected violation per episode, using a moving average over up to 500 episodes. At $k=0$ , we evaluate the initial policy. Curves show means across eight environments after averaging five paired seeds per environment. Shaded areas show one SD across environment means. The horizontal line in (c) marks the mean optimal safe value.

Method	$\mathcal{R}(K)/10^{3}$	$\mathcal{R}_{+}(K)/10^{3}$	$\mathrm{Viol}(K)/10^{3}$
SVAE	-2.406 (0.947)	1.428 (0.112)	1.426 (0.132)
SUCBVI	0.150 (1.707)	2.590 (1.037)	1.546 (0.121)
MVP-V + filter	45.989 (1.973)	46.756 (1.776)	3.005 (0.124)
MVP-V	31.238 (9.735)	34.020 (9.161)	2.816 (0.246)

Appendix

Table 1: Regret and step-wise violation in stochastic navigation. We report cumulative regret, strong regret, and step-wise violation at

K=10{,}000

. Entries are means (SDs) across eight environments after averaging five paired seeds per environment. Bold numbers mark the lowest mean in each column, including ties at the displayed precision.

Panel of Figure 4 — Figure 4: Regret under different safe-policy return variances. The three panels compare SVAE with its Hoeffding-type variants as $\mathrm{Var}^{\star}$ varies. Curves show means over 20 paired seeds, with shading indicating one SD. The episode axes use a logarithmic scale.

$\mathrm{Var}^{\star}$	$K\mathrm{Var}^{\star}$	$\mathbb{V}_{\Sigma}$	Hoeffding-P	Hoeffding
			$\Delta\mathcal{R}(K)$
0	0	0.000 (0.000)	$-0.110$ (0.031)	$-0.460$ (0.268)
0.0225	225	0.739 (0.263)	$-0.115$ (0.198)	$-0.560$ (0.376)
0.09	900	2.691 (1.078)	$-0.120$ (0.202)	$-0.495$ (0.386)

Appendix

Table 2: Accumulated variance and regret differences. We report SVAE’s accumulated variance

\mathbb{V}_{\Sigma}

and paired regret differences at

K=10{,}000

as means (SDs) over 20 seeds. Each difference

\Delta\mathcal{R}(K)

is SVAE’s regret minus the regret of the indicated Hoeffding-type variant.

Panel of Figure 5 — Figure 5: Effect of transition probability on safety identification. Panel (a) shows the mean cumulative number of times the unsafe root action is taken, with shading indicating one SD. Panel (b) shows the fraction of runs in which this action has not yet been excluded. For each $p$ , we use 20 paired seeds and fix $\Delta_{c}=0.2$ . Both episode axes use a logarithmic scale.

$p$	$\Delta_{c}$	$\mathcal{C}$	Root executions	Successor visits	$\mathrm{Viol}(K)$
Varying the successor probability ( $\Delta_{c}=0.20$ )
0.40	0.20	125.0	117.1 (57.8)	46.5 (21.3)	9.29 (4.27)
0.20	0.20	250.0	230.1 (112.1)	46.5 (21.3)	9.29 (4.27)
0.10	0.20	500.0	471.0 (231.5)	46.5 (21.3)	9.29 (4.27)
0.05	0.20	1,000.0	931.9 (535.4)	46.5 (21.3)	9.29 (4.27)
Varying the cost gap ( $p=0.20$ )

Appendix

Table 3: Effect of transition probability and cost gap on safety identification. We report executions of the unsafe root action, visits to its non-viable successor, and cumulative step-wise violation at

K=10{,}000

. Entries are means (SDs) over 20 seeds. The two parameter sweeps use separate seed sets. Bold rows mark the lowest identification complexity

\mathcal{C}

in each sweep.

Panel of Figure 6 — Figure 6: Recursive elimination at propagation distance $d=3$ . Panel (a) shows cumulative entries into the unsafe branch after detection. Panel (b) shows cumulative regret when the branch has a safe continuation, with a logarithmic episode axis. Curves show means over 20 paired seeds, with shading indicating one SD. The two methods have identical regret in (b) for every paired seed.

Constrained RL

Constrained reinforcement learning optimizes task performance while keeping safety risks, resource use, or other costs within explicit limits.

See all 226 papers

Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints
Sep 24, 2025Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni +2Markov Decision Processes Constrained RL
Politecnico di Milano
Near-Optimal Sample Complexity for Online Constrained MDPs
Feb 16, 2026Chang Liu, Yunfan Li, Lin F. YangConstrained RL Safe RL
University of California, Los Angeles
Computationally efficient safe exploration in reinforcement learning
Sep 19, 2026Shreeram Murali, Shankar A. Deka, Dominik BaumannSafe RL Constrained RL
Cyber-physical Systems Group · Nonlinear Systems and Control Group, Aalto University, Espoo, Finland

Sep 24, 2025J/K move · Enter open · S save

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

Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni, Alberto Marchesi+1

Politecnico di Milano

Markov Decision Processes Constrained RL Constrained Optimization

Open paper AskPDF arXiv

We study 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, 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 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, 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 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.

Abstract

Constrained RL

Explore similar work

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

Near-Optimal Sample Complexity for Online Constrained MDPs

Computationally efficient safe exploration in reinforcement learning