Learning Chance-Constrained MDPs with Bellman Distributional Certificates

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 imply a higher statistical price. In tabular discounted CCMDPs, we give a Bellman-certified model-based algorithm whose sample complexity matches the \emph{minimax optimal} primary dependence of classical CMDP learning, and prove a matching lower bound. Technically, our key idea is the \emph{Bellman distributional certificate}, which constructs a Bellman recursion for constraint violation probabilities before policy selection. The certificate can be reused across candidate policies, shifting concentration analysis from the number of possible policies to a finite Bellman certificate table. Building on this certificate, we establish high-probability safety and near-optimality guarantees for deterministic policy learning in discounted CCMDPs. To our knowledge, we also provide the first model-free sample complexity guarantee for stochastic policy learning in CCMDPs via variance-reduced policy gradient. Numerical experiments on synthetic CCMDPs and IEEE 14-bus energy-storage control benchmark illustrate the safety and behavior of the proposed algorithms.