mlsanityData to 14 Oct 2026

Learning Chance-Constrained MDPs with Bellman Distributional Certificates

arXiv 2609.30856 ↗First posted 25 Sep 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 28 of its 52 references that are in the map. First posted on arXiv 25 Sep 2026.

Builds on

28 of 52 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints9 Mar

Other references · 27

  1. 2017Constrained Policy Optimizationcited by 983
  2. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  3. 2017Distributional Reinforcement Learning with Quantile Regressioncited by 474
  4. 2018Reward Constrained Policy Optimizationcited by 417
  5. 2015Risk-Constrained Reinforcement Learning with Percentile Risk Criteriacited by 337
  6. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
  7. 2015Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approachcited by 170
  8. 2020Exploration-Exploitation in Constrained MDPscited by 149
  9. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  10. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  11. 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 115
  12. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
15 more
  1. 2014Optimizing the CVaR via Samplingcited by 99
  2. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  3. 2024A Survey of Constraint Formulations in Safe Reinforcement Learningcited by 44
  4. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  5. 2020Constrained Markov Decision Processes via Backward Value Functionscited by 33
  6. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 24
  7. 2021Safe Reinforcement Learning with Chance-constrained Model Predictive Controlcited by 20
  8. 2022Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimizationcited by 19
  9. 2022Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Boundscited by 16
  10. 2021Model-based Chance-Constrained Reinforcement Learning via Separated Proportional-Integral Lagrangiancited by 15
  11. 2023Probabilistic Constraint for Safety-Critical Reinforcement Learningcited by 11
  12. 2020Model-Based Actor-Critic with Chance Constraint for Stochastic Systemcited by 9
  13. 2020Chance-Constrained Control with Lexicographic Deep Reinforcement Learningcited by 3
  14. 2024Flipping-based Policy for Chance-Constrained Markov Decision Processescited by 3
  15. 2023Dual Formulation for Chance Constrained Stochastic Shortest Path with Application to Autonomous Vehicle Behavior Planningcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Utility-Constrained Policy Optimization
  2. 2025Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds
  3. 2026Near-Optimal Sample Complexity for Online Constrained MDPs
  4. 2025Robust Bayesian Dynamic Programming for On-policy Risk-sensitive Reinforcement Learning
  5. 2026Reinforcement Learning under State and Outcome Uncertainty: A Foundational Distributional Perspective
  6. 2026Instance-Dependent Regret for CMDPs with Step-Wise Constraints
  7. 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time
  8. 2025A Survey of Safe Reinforcement Learning and Constrained MDPs: A Technical Survey on Single-Agent and Multi-Agent Safety