CS Paper Radar

Rare Event Constrained Reinforcement Learning with Large Deviations

Rahul Misra

cs.LG stat.MLeess.SYmath.OCmath.PRmath.ST ·submitted 2026-11-01 16:59 UTC · v1
theory

Abstract

We study finite-horizon reinforcement learning with a safety constraint on the probability of reaching a failure set. In contrast to the well-studied safe reinforcement learning literature, we consider problems where the probability of reaching the failure set is vanishingly small, but the consequences of reaching the failure set are catastrophic. Direct simulation and estimation of the optimal policy is naturally ineffective when the failure probability is extremely small. Moreover, on a real system the controller can only choose actions, and this is not enough to make failures frequent. In contrast to the rare event simulation literature, our goal is not to estimate the probability of the rare event occurrence, but to upper bound it such that the failure constraint is satisfied. Thus, instead of sampling failures, we use the large deviations principle. We define a damage variable that on exceeding a certain threshold indicates failure. We study the cumulant generating function (CGF) as its positive root provides an upper bound on the failure probability via Cramer's theorem. We extend this approach to Markov decision processes with hitting times through state-action CGFs, and give finite-horizon and state-dependent versions of the bound. The state-action CGFs do not depend on the policy and can be estimated from regular transitions, so the bound can be checked for any policy a priori. This gives a policy improvement algorithm in which every policy satisfies the failure constraint with high probability.

Closest papers

Nearest neighbours by meaning across the whole index.

Arrive and Survive: Scaling Safe Goal-Conditioned Policy Learning from One-Bit Failure Signals

cs.LG cs.RO ·2026-08-27 ·Guopeng Li, Yiyang Duan, Yiru Jiao, Chengcheng Xu
code/data similarity 0.68
Abstract · 21 pages, 14 figures, 5 tables, Code: https://github.com/RomainLITUD/safe-crl

Contrastive reinforcement learning (CRL) scales effectively in goal-conditioned tasks by casting policy learning into a self-supervised contrastive objective. However, in a failure-terminated Markov decision process, established CRL considers pre-failure future goals only when constructing positive samples, without accounting for the probability mass removed by failure termination. Our theoretical analysis shows that this omission induces a systematic overestimation bias in goal-reaching values. Consequently, near-failure trajectories provide disproportionately strong supervision of success despite retaining little future occupancy. Unsafe actions can thereby be reinforced through catastrophic failure bootstrapping, leading to failed policy learning and unsustainable goal-reaching behaviours. To address this problem, we introduce two minimal yet strong corrections: mass-weighted InfoNCE corrects the overweighting of short surviving futures in critic learning, and a log-survival-mass score restores the missing survival mass in policy optimization. The resulting method, Safe Contrastive Reinforcement Learning (Safe-CRL), requires only the one-bit signal provided by failure termination to scale safe goal-conditioned policy learning. Across twelve failure-prone robot navigation and locomotion tasks, Safe-CRL consistently improves survival and substantially outperforms the Scaling-CRL baseline in goal-reaching performance. Additionally, deep Safe-CRL policies exhibit complex failure-avoidance behaviours. This study completes the CRL theory under failure termination and provides a scalable safe RL framework. The code is available via https://github.com/RomainLITUD/safe-crl.

0.31

Learning Chance-Constrained MDPs with Bellman Distributional Certificates

cs.LG ·2026-09-25 ·Chenbei Lu, Hongyu Yi
top venuebenchmarktheory similarity 0.67
Abstract · Accepted to NeurIPS 2026

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 \emph{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.

0.36

Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model

cs.LG stat.ML ·2026-10-03 ·Amirparsa Bahrami, Oliver Mortensen, Mohammad Sadegh Talebi
similarity 0.65
Abstract

In this paper, we study the sample complexities of value and policy learning in finite discounted Markov decision processes (MDPs) under recursive entropic risk preferences with risk parameter \(β\neq 0\), assuming access to a generative model of the MDP. We provide a refined analysis of model-based risk-sensitive Q-value iteration (MB-RS-QVI), a plug-in model-based method introduced in prior work, and derive \((\varepsilon,δ)\)-PAC guarantees for both learning the optimal \(Q\)-value function and an \(\varepsilon\)-optimal policy. Our bounds improve the exponential dependence on the effective horizon \(1/(1-γ)\) compared with the best existing guarantees for this setting. In particular, they match the existing lower bounds in their exponential dependence on \(|β|/(1-γ)\), as well as in \(S\), \(A\), \(\varepsilon\), and \(|β|\), up to logarithmic factors. Consequently, our analysis removes the exponential gap between the previously known upper and lower bounds, leaving only a polynomial gap in the effective horizon.

0.13

Certifying Almost-Sure Reachability in Unknown MDPs

cs.LO cs.AI ·2026-10-13 ·S Akshay, Suguman Bansal, Gaurav Mahla
theory similarity 0.65
Abstract

{\em Specification-Guided Reinforcement Learning (RL)} has largely concerned itself with \emph{learning} an optimal policy against a formal specification in an unknown {\em Markov Decision Process (MDP)}. We take up the dual question. Given a policy already in hand, can one \emph{verify} that it is correct against a formal specification in an unknown MDP, using sampling access alone? Such a question arises naturally in safety-critical systems. We investigate it for the {\em almost-sure reachability property}, whose correctness is witnessed by a {\em ranking supermartingale (RSM)} certificate. Our first finding is negative. In the absence of any further information about the MDP, one can neither learn such a certificate nor verify a candidate one with probabilistic guarantees. On the positive side, we show that, under a mild restriction, a known lower bound $p_{\min}$ on nonzero transition probabilities, a correct certificate \emph{can} be learned with PAC-style guarantees. To the best of our knowledge, this is the first study of learning and verifying certificates for almost-sure reachability in unknown MDPs from sampling access alone. Finally, our experiments show that the $p_{\min}$-based sufficient condition, while sound, is conservative: the learned certificate often remains valid on the true MDP even when the condition fails.

0.07

On the Convergence of Success Conditioning for Policy Optimization

cs.LG math.OC ·2026-10-02 ·Matthew Brun, Xu Andy Sun
theory similarity 0.63
Abstract

Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDPs). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within $\mathcal{O}(1/\varepsilon^p)$ iterations to an $\varepsilon$-optimal policy, where the exponent $p$ depends on problem data. For single-period MDPs, such a policy is obtained within $\mathcal{O}(\log(1/\varepsilon))$ iterations.

0.17

Dissimilarity-Based Markov Decision Processes for Stabilizing State Distributions

cs.LG ·2026-10-21 ·Xun Shen, Yuepeng Wang, Daniyal Sajedi-Hosseini, Akifumi Wachi, Ken Kawano +4 more
similarity 0.63
Abstract · 44 pages, 12 figures, 13 tables. Xun Shen, Yuepeng Wang, and Daniyal Sajedi-Hosseini contributed equally. Under review at TMLR

Reinforcement learning for stochastic systems typically optimizes expected cumulative rewards, while reliable and repeatable behavior also depends on how the state distribution evolves over time. Optimizing expected return alone does not guarantee that this distribution converges to a desired target or remains stable. This paper develops a theoretical framework for learning policies that stabilize state distributions. We formulate the problem as a Dissimilarity-based Markov Decision Process (DMDP), in which the policy acts on the current state distribution and the objective measures its dissimilarity to a target distribution. We establish sufficient conditions under which the optimal policy makes the target distribution asymptotically stable. To support policy learning, we introduce a finite-dimensional representation of distributions and show how stability guarantees for its parameter dynamics extend to the underlying state distributions. We further develop certificates for the learned policies, including their deployment using estimated distribution parameters. These results quantify how learning and estimation errors affect the guarantees and identify conditions under which learned policies retain asymptotic stability. For practical implementation, we combine distribution estimates and target-dependent rewards with PPO and SAC. A computable example on a linear system illustrates the proposed theoretical certificates. Furthermore, experiments on a HalfCheetah task demonstrate the benefits of distribution feedback and explicit target matching for regulating the velocity distribution.

0.28

Safety Hacking in Constrained Best-of-$N$ Inference-time Scaling

cs.LG cs.AIcs.CLcs.CR ·2026-08-24 ·Akifumi Wachi, Takumi Tanabe, Youhei Akimoto
similarity 0.63
Abstract

Inference-time pipelines often sample multiple outputs, filter them with a learned safety model, and return the proxy-feasible output with the highest learned reward. We show that this composition creates a two-stage failure: an imperfect safety proxy first contaminates the feasible set with unsafe outputs, and reward maximization can then amplify this residual contamination. We define \emph{safety hacking} as selecting an output that passes the learned constraint but violates the true safety criterion. For constrained Best-of-$N$ sampling, we derive finite-$N$ bounds governed by the joint upper reward tails of safe and unsafe outputs within the proxy-feasible set. If unsafe-but-feasible outputs have the heavier tail, safety hacking becomes asymptotically certain as $N$ grows, even when false-positive mass and average safety- and reward-proxy errors are arbitrarily small. We also show that policies within a bounded $χ^2$ divergence from the proxy-feasible reference distribution admit an $N$-independent safety-hacking bound, and instantiate this general coverage-control principle with constrained pessimistic sampling. Coverage control limits amplification but cannot repair a contaminated feasible set: admitted unsafe outputs may still be favored, and regularized selection is not necessarily safer than constrained Best-of-$N$ for every reward proxy. Toy and language-model experiments characterize both contamination and its reward-tail amplification, which exposes an inherent difficulty in inference-time scaling with learned safety models.

0.37

Robust PAC Learning of Concurrent Stochastic Games

cs.LG cs.GTcs.LOcs.MA ·2026-09-03 ·Angel Y. He, David Parker
top venuebenchmark similarity 0.63
Abstract · Camera-ready version of a paper accepted to NeurIPS 2026. Main text: 10 pages, 1 figure, 2 tables; Appendix: 22 pages, 2 figures, 1 table. M…

We introduce the first Probably Approximately Correct (PAC) learning framework for general-sum concurrent stochastic games (CSGs) with transition uncertainty, while addressing the challenge of Nash equilibrium (NE) existence. Our algorithm maintains data-driven $L^1$ confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal $\varepsilon$-NE, using a robust MDP-based exploration mechanism to drive joint state-action coverage. Crucially, we introduce a Nash margin characterisation that enables principled reasoning about equilibrium existence: the framework either returns an $\varepsilon$-approximate NE whose social-welfare value is $\varepsilon$-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition $p_{\mathrm{reach}}>0$ over relevant state-action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity $\widetilde{O}\left( {R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2)} \right)$. Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.

0.33