Learning Chance-Constrained MDPs with Bellman Distributional Certificates

Chenbei Lu; Hongyu Yi

cs.LGSep 25, 2026

Learning Chance-Constrained MDPs with Bellman Distributional Certificates

Authors: Chenbei Lu, Hongyu Yi

Organizations: Cornell University AI for Science Institute Cornell University Ithaca, NY, USA · Department of Electrical & Computer Engineering University of Washington Seattle, WA, USA

Abstract

Safe reinforcement learning (RL) commonly enforces expected-cost constraints, but such expectation safety may fail to control the probability of rare high-cost trajectories. Chance-constrained MDPs (CCMDPs) impose a stronger probability-level requirement, but are widely viewed as harder because the chance constraint is nonconvex and depends on the full trajectory rather than a Bellman-linear expectation. In this paper, we reveal that this computational difficulty does not necessarily imply a higher statistical price. For tabular discounted CCMDPs with fixed bounded successor support and access to a certified planning oracle, we establish a model-based upper bound, with a matching lower bound up to logarithmic terms. Technically, our key idea is the Bellman distributional certificate, which constructs a Bellman recursion for constraint violation probabilities before policy selection. The certificate can be reused across candidate policies; combined with shared row-wise reverse-KL confidence sets, it gives a policy-uniform trajectory-KL transfer without a union bound over policies or time--budget Bellman tables. For stochastic policies, we give a model-free variance-reduced policy-gradient algorithm with a finite-sample expected KKT-residual guarantee and independent validation of every accepted policy. Numerical experiments on synthetic CCMDPs and an IEEE 14-bus energy storage control benchmark illustrate the safety and mechanism behavior of the proposed algorithms.

Figures & tables

Figure 1: A: IEEE 14-bus DC network with the battery energy-storage system located at bus 14. B: Reward–violation landscape over the structured policy class. The labeled CCMDP points show the mean performance of the practical Bellman-buffered selector over repeated empirical-model trials as the number $N$ of transition samples per row increases; the star denotes the chance-constrained oracle, and the square denotes the Markov-CMDP expected-cost surrogate. C: Optimality gap $J^{\star}_{\mathrm{chance}}-J(\widehat{\pi}_{N})$ versus $N$ . The shaded band denotes the mean plus or minus $1.96$ standard errors across $60$ independent empirical-model trials, while the dashed Markov-CMDP line is the true-model expected-cost-surrogate benchmark. D: Violation probability versus expected discounted safety cost over the same policy class. The Markov condition $\mathbb{E}[C_{\pi}]\leq\delta d$ is sufficient for $q_{P}(\pi)\leq\delta$ but excludes many policies that are feasible for the original chance constraint, explaining its persistent performance gap. Violation probabilities in Panels B and D are estimated by Monte Carlo simulation under the true transition kernel.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Decision state $s_{i}$	$s_{0}$	$s_{1}$	$s_{2}$	$s_{3}$	$s_{4}$	$s_{5}$	$s_{6}$	$s_{7}$
Risky reward $r(s_{i},1)$	0.72	0.73	0.74	0.77	0.79	0.81	0.84	0.87
Risky bad probability $p_{i}^{r}$	0.014	0.018	0.021	0.024	0.028	0.032	0.036	0.040
Risky next-state probability $0.94-p_{i}^{r}$	0.926	0.922	0.919	0.916	0.912	0.908	0.904	0.900

Appendix

Table A.1: State-dependent risky-action parameters in the synthetic CCMDP. The safe action uses reward

0.45

and bad-transition probability

0.002

at every decision state.

Figure A.1: Synthetic CCMDP diagnostic with shared transition samples. A: true violation probability and discounted return for all 256 stationary deterministic policies, with CCMDP selections from repetition 0 at the indicated budgets; the Markov-CMDP marker uses

D=16{,}000

. The oracle is optimal within the same policy class. B: mean true return over 150 empirical-model draws per budget, with shaded bands of

\pm 1.96

empirical standard errors. C: empirical and practically buffered violation estimates for one shared model at

D=16{,}000

, against exact true probabilities; the diagonal indicates equality and the dotted lines mark

\delta=0.13

Figure A.2: VR-PG on the synthetic CCMDP with

\rho=0.0035

and

\beta=80

. The optimization trajectory is shown against the deterministic policy landscape and alongside the evolution of return and violation probability. The inset includes the numerical stochastic reference; the selected policy is marked in magenta on the return curve. Its independent validation upper bound lies below

\delta=0.13

Markov Decision Processes

Markov decision processes model sequential choices under uncertainty, linking actions, state transitions, and rewards to planning and reinforcement learning.

See all 157 papers

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
Utility-Constrained Policy Optimization
Jun 12, 2026Mehrdad Moghimi, Bernardo Avila PiresConstrained RL Risk-Sensitive RL
York University Toronto, Canada · Google DeepMind London, United Kingdom
Certifying Almost-Sure Reachability in Unknown MDPs
Oct 13, 2026S Akshay, Suguman Bansal, Gaurav MahlaMarkov Decision Processes Reachability Analysis
Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, India · School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA

Feb 16, 2026J/K move · Enter open · S save

Near-Optimal Sample Complexity for Online Constrained MDPs

Chang Liu, Yunfan Li, Lin F. Yang

University of California, Los Angeles

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

Open paper AskPDF arXiv

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.

Abstract

Markov Decision Processes

Explore similar work

Near-Optimal Sample Complexity for Online Constrained MDPs

Utility-Constrained Policy Optimization

Certifying Almost-Sure Reachability in Unknown MDPs