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

Sep 24, 2025

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

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.

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

Politecnico di Milano

Markov Decision Processes Constrained RL Constrained Optimization

Ask PDF

Feb 16, 2026

Near-Optimal Sample Complexity for Online Constrained MDPs

Safety is a fundamental challenge in reinforcement learning (RL), particularly in real-world applications such as autonomous driving, robotics, and healthcare. To address this, Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance. However, existing methods often suffer from significant safety violations or require a high sample complexity to generate near-optimal policies. We address two settings: relaxed feasibility, where small violations are allowed, and strict feasibility, where no violation is allowed. We propose a model-based primal-dual algorithm that balances regret and bounded constraint violations, drawing on techniques from online RL and constrained optimization. For relaxed feasibility, we prove that our algorithm returns an

\varepsilon

-optimal policy with

\varepsilon

-bounded violation with arbitrarily high probability, requiring

\tilde{O}\left(\frac{SAH^3}{\varepsilon^2}\right)

learning episodes, matching the lower bound for unconstrained MDPs. For strict feasibility, we prove that our algorithm returns an

\varepsilon

-optimal policy with zero violation with arbitrarily high probability, requiring

\tilde{O}\left(\frac{SAH^5}{\varepsilon^2ζ^2}\right)

learning episodes, where

ζ

is the problem-dependent Slater constant characterizing the size of the feasible region. This result matches the lower bound for learning CMDPs with access to a generative model. Our results demonstrate that learning CMDPs in an online setting is as easy as learning with a generative model and is no more challenging than learning unconstrained MDPs when small violations are allowed.

Chang Liu, Yunfan Li, Lin F. Yang

University of California, Los Angeles

Constrained RL Safe RL Sample-Efficient RL Model-Based RL

Ask PDF

Sep 19, 2026

Computationally efficient safe exploration in reinforcement learning

Reinforcement learning in real-life applications requires safety guarantees during exploration. Typical reinforcement learning algorithms do not provide such guarantees, and many modifications that do rely on Gaussian processes (GPs), which have a large computational cost. We propose a computationally lightweight algorithm based on the Nadaraya-Watson estimator that safely explores and optimizes constrained Markov decision processes (MDPs). Our algorithm, CoLSafe-MDP, uses an estimator that scales in constant-time with bounds on the estimates, a significant improvement from its GP-based counterparts that scale cubically with the number of data points. We then evaluate its performance in a grid-based environment and on observational Martian terrain data.

Shreeram Murali, Shankar A. Deka, Dominik Baumann

Cyber-physical Systems Group · Nonlinear Systems and Control Group, Aalto University, Espoo, Finland

Safe RL Constrained RL

Ask PDF

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