Model Releases
Learning Chance-Constrained MDPs with Bellman Distributional Certificates
arXiv:2609.30856v1 Announce Type: new Abstract: Safe reinforcement learning (RL) commonly enforces expected-cost constraints, but such expectation safety may fail to control the probability of rare hi
arXiv:2609.30856v1 Announce Type: new 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.
Related
- Boundary-Seeking Policy Gradient for Safe Reinforcement Learning
- A decoupled diffusion planner that adapts to changing cost limits by using cost-conditioned generation for safety and reward gradients for performance
- Constraint-Enhanced Reinforcement Learning Based on Dynamic Decoupled Spherical Radial Squashing
- Exchange Policy Optimization Algorithm for Semi-Infinite Safe Reinforcement Learning
- Rare Event Analysis via Stochastic Optimal Control
Source: arXiv cs.LG | 2026-09-28