Learning Chance-Constrained MDPs with Bellman Distributional Certificates

Conference: NeurIPS2026 (task-queue assignment; the source is arXiv v1)
arXiv: 2609.30856v1
Area: Reinforcement Learning
Keywords: chance constraints, Bellman distributional certificates, reverse-KL confidence sets, variance-reduced policy gradients, post-selection safety certification

TL;DR

The paper expresses cumulative-cost violation events through remaining-budget Bellman recursions, obtains nearly matching deterministic-policy sample complexity under bounded successor support and a certified planning oracle, and combines local approximate-KKT optimization with independent validation for stochastic policies; synthetic and power-system simulations distinguish statistical conservatism from conservatism induced by expected-cost surrogates.

Background & Motivation

Constrained Markov decision processes usually restrict expected cumulative cost, but a low average does not exclude a small set of high-cost trajectories. Chance constraints instead restrict the probability of exceeding a cumulative-cost threshold, more directly expressing reliability requirements. This is not merely a different loss function: expected costs add across steps, whereas violation probability depends on the entire trajectory and the budget already consumed.

With a known model, budget augmentation, distributional dynamic programming, and search can handle such events. With an unknown model, data-dependent policy selection introduces another difficulty. Simulating each candidate separately wastes samples, while selecting an apparently safe policy and then applying a fixed-policy error bound on the same data does not automatically establish post-selection safety. Meanwhile, nonconvex and combinatorial planning difficulty need not imply a statistical charge for every budget cell, time index, or policy.

Core Idea: conservatively reduce the infinite-horizon violation event to a finite budget event, then certify all candidate policies using shared confidence sets on original state–action rows; an alternative model-free route optimizes trajectory violation probabilities directly but reserves the final safety decision for independent validation data.

Method

Overall Architecture

The inputs are a finite-state discounted environment, known bounded immediate rewards and costs, and a cost threshold and allowed violation probability for each constraint. The output can be a certified policy or unresolved. The original objective maximizes cumulative reward subject to cumulative-cost violation probabilities:

\[ q_{P,i}(\pi)=\mathbb{P}_{P,\pi,\mu}\!\left(\sum_{t=0}^{\infty}\gamma^{t}c_i(s_t,a_t)>d_i\right)\leq\delta_i,\qquad J_P(\pi)=\mathbb{E}_{P,\pi,\mu}\!\left[\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t)\right]. \]

A common conservative budget representation supports two alternative routes, rather than a model-based training stage followed by a model-free one. The model-based route samples original transition rows through a generative model, computes robust violation probabilities backward, and selects a policy through a certified planner. The model-free route uses trajectory indicators, likelihood-ratio gradients, and variance-reduced updates to generate a candidate, followed by independent validation. Time and remaining budget are trajectory parameters available to the policy, not a newly enlarged environment requiring separate samples at every augmented state.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Environment and chance constraints"] --> B["Conservative budget representation"]
    B -->|Generative-model samples| C["Shared-model certification"]
    B -->|Training trajectories| D["Trajectory-gradient optimization"]
    D -->|Fresh data after fixing the candidate| E["Independent safety validation"]
    C --> F["Certified policy or unresolved"]
    E --> F
    F -->|If a policy is returned| G["Track time and remaining<br/>budget during execution"]

Training samples and execution data flow have different roles: certification uses a training model or fresh validation trajectories, while execution follows the policy and budget updates without solving the certification problem at every step. The synthetic experiment uses a stationary policy subclass, so its execution policy need not explicitly depend on the budget.

Key Designs

1. Conservative budget representation: make the finite event cover infinite-horizon risk

Simply truncating cumulative cost can miss violations caused by the tail. The construction first reserves a discounted-tail allowance, then rounds the initial budget downward and every discounted step cost upward. The tail allowance is a cumulative-cost bound, not a violation probability; the grid width is not a statistical confidence radius either. Together they place the original event inside a computable finite event.

\[ H=\left\lceil\frac{\log(1/((1-\gamma)\alpha_{\rm tail}))}{1-\gamma}\right\rceil,\qquad b_i^0=\left\lfloor\frac{d_i-\alpha_{\rm tail}}{\eta_i}\right\rfloor,\qquad w_{i,h}(s,a)=\left\lceil\frac{\gamma^h c_i(s,a)}{\eta_i}\right\rceil. \]

Each update subtracts the integer charge; a negative coordinate becomes an absorbing failure value. A negative initial budget starts in failure. Policies can depend on the current state, budget vector, and time, making these sufficient for the future finite violation probability. Appendix B proves sufficiency by backward induction: the endpoint checks budget failure, and the preceding step averages over the next state.

The safety argument in Appendix C is pathwise. If the integer budget never fails, the true prefix cost cannot exceed the threshold after reserving the tail allowance, and the discounted tail cannot exceed that allowance. Therefore an original infinite-trajectory violation implies finite budget failure. The direction matters: the certificate may reject safe policies, but rounding costs downward would create unjustified safety claims.

Conservatism has a cost. Grid-rounding losses accumulate over the certificate horizon, potentially classifying probability mass near the original threshold as failure. The original safe optimum need not belong to the rounded feasible set, and even a known deterministic model does not automatically remove this discrepancy.

2. Shared-model certification: cover post-selection policies with the same original-row samples

The model-based route draws independent successor samples at each original state–action row and forms one shared empirical transition kernel. Immediate rewards and costs are known. The confidence set uses reverse KL from the empirical row to a candidate row, rather than requiring every possible successor to have been observed; such a requirement would prematurely exclude the true model when rare successors exist.

\[ \kappa_n=\frac{(d_0-1)\log(n+1)+\log(|\mathcal{S}||\mathcal{A}|/\zeta)}{n},\qquad \mathcal{C}_{s,a}=\{p\in\Delta(\mathcal{S}):\mathrm{KL}(\widehat{P}_{s,a}\|p)\leq\kappa_n\},\qquad \overline q_i^\pi(s,b,h)=\sup_{p\in\mathcal{C}_{s,a}}p^\top\overline q_i^\pi(\cdot,B_h(s,a,b),h+1),\quad a=\pi_h(s,b). \]

The violation table starts with a terminal budget-failure indicator and is computed backward. Because its entries represent failure probabilities, safety certification maximizes over the transition confidence set rather than taking an optimistic minimum. Reward ranking uses ordinary empirical Bellman evaluation. Safety and reward play asymmetric roles, so high reward does not imply a stronger certificate.

Appendix D first obtains simultaneous coverage of all original rows through type counting on bounded supports, taking a union bound only over original rows. Once this event is fixed, true rows lie in the confidence sets everywhere, and Bellman monotonicity places the robust table above the true rounded failure probabilities. The argument consequently holds for the entire policy class, including policies selected after inspecting data. What is reused is the transition-row data and confidence sets, not a numerically identical table for every policy.

The key step in Appendix E is not a linear accumulation of local errors. The KL chain rule combines row KL along the entire augmented trajectory, and Pinsker's inequality converts this into an event-probability error. Rectangular confidence sets let an adversarial transition process vary with time and budget to realize the robust backward maxima; its trajectory law obeys the same KL control relative to the empirical law. Two transfer bounds bracket the true failure probability and robust certificate:

\[ r_n=\sqrt{H\kappa_n/2},\qquad 0\leq\overline q_{i,H,\eta}(\pi)-q_{P,i}^{\rm rnd}(\pi)\leq2r_n,\qquad |\widehat J(\pi)-J_{P,H}(\pi)|\leq R_Hr_n,\quad R_H=\sum_{h=0}^{H-1}\gamma^h. \]

No union bound over complete policies or time–budget table entries is needed, and the budget-space size does not enter the row-coverage event. However, the Cartesian product of budget coordinates can still make planning expensive; this statistical result does not remove computational costs.

The algorithm actually tightens the certificate threshold to \(\delta_i-3\rho/4\). Its comparator is a nonempty rounded interior set inside a finite policy class fixed before sampling, not the unrestricted original chance-constrained optimum:

\[ V_\rho^\star=\max_{\pi\in\Pi_{\mathcal O}:\ q_{P,i}^{\rm rnd}(\pi)\leq\delta_i-\rho\ \forall i}J_P(\pi),\qquad D=\widetilde O\!\left(d_0|\mathcal S||\mathcal A|\left[\frac{1}{(1-\gamma)^3\varepsilon^2}+\frac{1}{(1-\gamma)\rho^2}\right]\right),\qquad J_P(\widehat\pi)\geq V_\rho^\star-\varepsilon-\xi. \]

Theorem 1 also requires a known fixed bound on successor support size, independent of state-space size, accuracy, and discounting; successor identities and probabilities may remain unknown. The grid widths and tail allowance equal \(\min\{\varepsilon/8,(1-\gamma)/128\}\), and the planner must return a certificate-feasible policy within the solver gap of the best empirical value. With enough samples, certificate error consumes only part of the interior margin, so the comparator passes the tightened test. On the high-probability event, the algorithm then avoids unresolved and is safe for the original chance constraints.

Relating this result further to the original optimum requires limited probability mass near the threshold affected by rounding; Appendix E explicitly introduces this additional boundary condition. It cannot be omitted to claim original global optimality. Appendix F separately constructs reward-identification and chance-boundary-identification hard instances, each with at most two successors per row, and derives matching terms through adaptive Bernoulli testing. Combining the two hard families yields their sum up to constants; a single instance need not exhibit both difficulties simultaneously.

The certified planner is an oracle assumption. Appendix G encodes knapsack through choose/skip actions on a deterministic chain and shows that exact planning remains NP-hard even with a known deterministic model. The nearly matching result concerns statistical sample complexity, not polynomial-time solution guarantees.

3. Trajectory-gradient optimization: estimate the chance event directly, with only local approximate-KKT guarantees

The model-free route does not estimate a transition kernel. Each fixed-length trajectory maintains the full budget vector, and terminal failure indicators provide samples for all constraints simultaneously. For a fixed trajectory, budgets and failure indicators are not differentiated with respect to policy parameters; only action probabilities change. Multiplying a failure indicator by the sum of action log-probability gradients therefore gives an unbiased violation-probability gradient.

\[ \chi_i=\mathbb I\{b_{i,H}<0\},\qquad \widehat{\nabla g_i^H}(\theta)=\chi_i\sum_{t=0}^{H-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t,t,b_t),\qquad g_i^H(\theta)=q_{P,i}^H(\theta)+2\rho-\delta_i,\qquad f_H(\theta)=-(1-\gamma)J_P(\pi_\theta). \]

The reward gradient uses geometrically stopped trajectories to estimate normalized infinite-horizon return, rather than silently replacing reward with a finite-horizon objective. Training tightens the allowed violation probability to separate optimization and final validation errors. Reward and constraint rollouts have different lengths, and the sample bound counts expected environment transitions; gradient calls are not interchangeable with interaction steps.

The optimizer introduces nonnegative slack variables and uses a fixed quadratic penalty with proximal updates. The proximal map constrains only the slack; parameter iterates are assumed to remain in a compact convex subset of the open parameter domain. Large batches periodically refresh gradients, while smaller batches estimate differences between consecutive iterates. Since trajectory distributions change with the policy, these differences require likelihood-ratio corrections rather than uncorrected reuse of old trajectory gradients.

The constraint Jacobian and constraint-value factors in the penalty gradient use independent samples to prevent product bias. Appendix H.8 applies a separate change-of-measure correction to each independent factor in the difference estimator. Positive action probabilities, controlled likelihood-ratio moments, score and score-derivative moments, mean-square-smooth differences, and bounded variance are substantive assumptions, not automatic consequences of using policy gradients.

Assumption 3's residual-domination condition is particularly important: a stationary point of a fixed penalty is not generally a KKT point of the constrained problem. The paper additionally assumes that, at visited points, the sum of parameter stationarity, slack stationarity, and constraint residuals is bounded by a finite constant times the composite penalty stationarity residual. Together with a slack error bound, feasible initialization, finite initial merit gap, bounded multipliers, and bounded slack, this converts the variance-reduced stationarity bound into a KKT-residual bound.

The KKT residual includes the Lagrangian gradient, positive constraint violation, and complementarity, minimized over a bounded nonnegative multiplier set. The theorem bounds the random candidate's expected residual by the target tolerance, with inverse-cubic tolerance dependence in optimization. It does not guarantee strict feasibility on every run or globally optimal reward. Local constants can depend on the policy class, certificate horizon, grid, margin, and visited set; they are not universally small constants.

4. Independent safety validation: certify accepted candidates without promising a policy on every run

After training, the algorithm uniformly samples a candidate from already computed post-update iterates and validates it with fresh trajectories. The theoretical output is neither the final iterate nor the highest-return iterate selected using the true model. Independence makes the candidate fixed conditional on training data, so the validation failure indicators estimate a fixed Bernoulli mean.

\[ M_{\rm val}=\left\lceil\frac{2\log(2m/\zeta)}{\rho^2}\right\rceil,\qquad \widehat q_{i,\rm val}^H(\theta_{\rm cand})+\rho/2\leq\delta_i\quad\forall i. \]

Hoeffding's inequality and a union bound over constraints control validation error. The pathwise conservative-budget inclusion then transfers acceptance to original infinite-horizon safety. This safety proof does not require training to reach a local KKT point, while an expected-KKT guarantee cannot replace validation.

The precise statement of Theorem 3 is that, with high probability, the algorithm either accepts a truly safe candidate or returns unresolved. If the candidate's true rounded risk is below the allowed risk by at least the validation margin, acceptance follows on the same event. A failed test means that the candidate or available data did not establish safety; it neither proves the candidate unsafe nor guarantees that another batch will pass.

A Worked Example

In the synthetic environment of Appendix I.1, only the bad state incurs a one-time unit cost, the discount is \(\gamma=0.95\), and the threshold is \(d=0.50\). The discounted cost at time thirteen exceeds the threshold, while at time fourteen it is smaller. Thus the original violation event is exactly visiting the bad state by time thirteen. Self-loops give the environment an unbounded absorption time, yet this chance event admits an exact finite recursion without changing the environment into a fixed-horizon process.

The model-based experiment enumerates stationary deterministic policies, filters them using buffered violation probabilities, and then ranks rewards. The model-free experiment trains a Bernoulli policy with one logit per decision state. Independent validation tests the randomly selected candidate, not the endpoint of the training curve. An apparently safe optimization curve and independent certification of a specified policy are different conclusions.

Loss & Training

The model-free experiment uses normalized negative return plus a quadratic slack penalty, a fixed penalty coefficient of 80, and step size 0.01. Its risk margin is 0.0035 and tightened training threshold is 0.123. Every 20 updates, 2,048 independent trajectory triples refresh the estimator; other updates use 128 triples with likelihood-ratio corrections, for 250,000 updates in total.

Each triple provides independent reward-gradient, risk-gradient, and risk-value samples, and the slack is projected onto the nonnegative half-line. Training consumes 168 million trajectories. This is neither evidence of optimization with only a small trajectory budget nor a numerical verification of every local theoretical assumption.

Key Experimental Results

Main Results

The synthetic task has 8 decision states, 1 bad state, and 1 absorbing terminal state; both actions have self-loop probability 0.06. The safe action gives reward 0.45 and bad-transition probability 0.002, and the allowed violation probability is 0.13. All methods use the same 256-policy class. Each budget has 150 independent empirical-model draws, and different budgets are not nested prefixes of one sample stream. The returns below are mean true-kernel values computed exactly after selection.

Total transition samples	Bellman-buffered selector return	Markov-CMDP return	Same-class chance oracle	Safe trials: buffered / Markov
8,000	3.562	4.026	4.404	150/150 / 148/150
800,000	4.391	3.928	4.404	150/150 / 150/150

At low budgets, the buffered selector is more conservative and actually earns less. The paper reports higher mean return than the surrogate from tested budget 32,000 onward. The buffered selector is safe in 150/150 trials at every tested budget, but these are finite repetitions: the corresponding pointwise two-sided 95% Clopper–Pearson interval is approximately [0.9757,1], not proof of zero underlying failure probability.

Model-free results must distinguish the random candidate, final iterate, and reference values. The table retains the source precision; training and visualization use seed 11, and candidate selection is a separate draw after training.

Policy / reference	Iteration	True return	True risk	Independent validation
Initial stochastic policy	0	4.16658	Not separately reported	Not performed
Randomly selected candidate	59,611	4.29506	0.12601	Accepted
Final iterate	250,000	4.36245	0.12769	Not the validated candidate
Enumerated deterministic feasible reference	Not applicable	4.40376	Not separately reported	Not applicable
Multi-start stochastic numerical reference	Not applicable	4.50970	0.13	Not applicable

The candidate receives 602,267 fresh validation trajectories. Its estimated risk is 0.126168; adding the 0.00175 margin gives 0.127918, below 0.13, so it is accepted. The final iterate has higher return but cannot replace the candidate in the certification result. The multi-start stochastic reference is not a proven global optimum. The deterministic reference values 4.40376 and 4.404 in the two tables reflect different reporting precision for the same reference.

Ablation Study

The paper does not provide a standard neural-module removal table. The following source-supported mechanism and protocol analysis does not present different sampling protocols as controlled ablations of one algorithm.

Config / protocol	Quantitative settings	Interpretation boundary
Synthetic Bellman buffer	Fixed log term 2; scale 0.75; 16 sampled rows	Shared model; practical buffer is not the theorem constant
Synthetic Markov-CMDP	Expected-cost threshold 0.065	Empirical surrogate has no extra uncertainty buffer
IEEE 14-bus policy class	176 states; 5 actions; 145 policies; 60 trials	Same-class comparison, not all control policies
IEEE finite-budget certificate	Discount 0.85; cost threshold 0.30; risk threshold 0.15; tail 0.005; grid 0.0015; horizon 48; integer budget 196	Conservative rounding and statistical buffering are distinct
IEEE sampling and evaluation	25, 50, 100, 200, 500, 1000 samples per row; evaluation with 50,000 trajectories of 100 steps	Safety batches independent across stages; reward model sampled separately
IEEE practical buffer	Scale 0.20/H; confidence parameter 0.05; surrogate cost threshold 0.045	Calibrated constant; no theorem-level risk-margin tightening

The IEEE 14-bus experiment discretizes storage state of charge, time block, and load regime, with storage located at bus 14. Actions charge, discharge, or idle; rewards are normalized operating benefits and safety costs measure transmission-line overload severity. The 145 candidates consist of 144 threshold policies and the always-idle policy, not arbitrary continuous power-system controllers.

Safety data are independent across Bellman stages, and reward ranking uses another independent empirical model. This differs from Theorem 1's shared original-row model, so the plotted per-row sample count cannot directly be treated as the theorem's total sampling budget. The buffer's 0.20/H coefficient is calibrated, and theoretical risk-margin tightening is omitted. Figure 1 illustrates the mechanism rather than verifying theorem-level coverage constants.

Key Findings

• The synthetic experiment separates statistical conservatism that decreases with more data from structural conservatism of the Markov-inequality surrogate. More data do not make the latter equivalent to the chance constraint.
• Different synthetic budgets use independent datasets, so returns in an individual repetition need not improve monotonically. A mean trend is not a sample-path monotonicity guarantee.
• IEEE plotted risks are finite Monte Carlo estimates under the true kernel, while rewards and expected costs are evaluated using the known finite kernel. No unreported plot values are inferred.

Highlights & Insights

• Safety certification and reward optimization use different Bellman objects. Failure probabilities require pessimistic upper bounds, while reward ranks the already certified set, separating appealing performance from risk evidence.
• Shared-row confidence events turn post-selection safety into a deterministic policy-uniform argument. Trajectory KL prevents the computational size of the budget table from becoming an additional statistical dimension, which matters more than stacking local confidence buffers.
• The routes offer different safety interfaces: model-based coverage certifies any candidate on one common event, whereas model-free validation certifies a specified candidate with fresh data. The reusable lesson is the certification boundary and data independence, not unrestricted reuse of a validation set to screen many policies.

Limitations & Future Work

• The model-based theorem requires fixed bounded successor support, generative-model access, known rewards and costs, and a certified planner. It does not directly cover complex environments, online safe exploration, or unknown-cost learning. Budget combinations and NP-hard planning remain implementation bottlenecks.
• The reward comparator needs a rounded interior margin. When cumulative cost concentrates near the threshold, finer grids still require boundary-mass analysis; original feasibility alone does not replace this condition.
• The model-free theory relies on strong local residual domination, positive policy probabilities, likelihood-ratio moments, and feasible initialization. It gives expected approximate KKT rather than global optimality, and validation can remain unresolved. More verifiable regularity conditions and concrete solvers are important next steps.
• Synthetic diagnostics, model-free training, and power-system simulations make this more than a purely theoretical paper. However, large training-trajectory costs and calibrated buffers limit empirical sample-efficiency claims. IEEE risks are finite-trajectory estimates, not clinical evidence or certification of real-grid deployment.

Related Work & Insights

• Versus expected-cost CMDPs: Markov's inequality supplies a sufficient safety condition but restricts a first moment rather than the original violation event. This paper retains threshold probabilities at the cost of budget representation and certificate computation.
• Versus distributional RL and CVaR methods: “Distributional” here does not mean fitting a full return distribution or replacing chance constraints with CVaR. The certificate bounds the probability of violating a specific cost threshold.
• Versus deterministic CCMDP learning by Yi, Lu, and Wu: Shared-row uniform certification replaces policy-wise risk estimation and improves state-space and horizon dependence under the stated support and planning assumptions. These conditions cannot be dropped to claim universal superiority.
• Research direction: Adaptive budget certificates combining tractable planning with verifiable boundary-mass conditions, or lower-cost independent validation, are potential extensions rather than results already established here.

Rating

• Novelty: 4/5 — Shared reverse-KL row certificates and policy-uniform trajectory transfer are the main contributions.
• Experimental Thoroughness: 3/5 — Mechanism diagnostics and power-system simulations are included, but practical protocols differ from the theorem and training is expensive.
• Writing Quality: 4/5 — The appendix specifies comparators, local assumptions, and experimental boundaries; understanding requires reading these conditions carefully.
• Value: 4/5 — The work distinguishes statistical difficulty, computational difficulty, and final certification responsibility for chance constraints.