Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning

• URL: http://arxiv.org/abs/2605.11975v2
• Date: Mon, 18 May 2026 06:36:11 GMT
• Title: Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning
• Abstract summary: We study minimum-cost reach-avoid reinforcement learning, where an agent must satisfy a reach-avoid specification with probability at least $p$ while minimizing expected cumulative costs in environments.<n>Existing safe and constrained reinforcement learning methods typically fail to jointly enforce probabilistic reach-avoid cost in the learning setting in environments.
• Score: 0.7319728937144206
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study stochastic minimum-cost reach-avoid reinforcement learning, where an agent must satisfy a reach-avoid specification with probability at least $p$ while minimizing expected cumulative costs in stochastic environments. Existing safe and constrained reinforcement learning methods typically fail to jointly enforce probabilistic reach-avoid constraints and optimize cost in the learning setting in stochastic environments. To address this challenge, we introduce reach-avoid probability certificates (RAPCs), which identify states from which stochastic reach-avoid constraints are satisfiable. Building on RAPCs, we develop a contraction-based Bellman formulation that serves as a principled surrogate for integrating reach-avoid considerations into reinforcement learning, enabling cost optimization under probabilistic constraints. We establish almost sure convergence of the proposed algorithms to locally optimal policies with respect to the resulting objective. Experiments in the MuJoCo simulator demonstrate improved cost performance and consistently higher reach-avoid satisfaction rates.

Related papers

• Robust Peak-cost Constrained Reinforcement Learning [10.897248153175935]
  We study robust peak-cost constrained reinforcement learning (RP-CRL)<n>The objective is to maximize expected reward while controlling the maximum cost encountered along a trajectory.<n>We show that, unlike standard CMDPs, peak-cost constrained MDPs may not admit zero duality gap.
  arXiv  Detail & Related papers  (2026-07-16T21:00:50Z)
• MC-CPO: Mastery-Conditioned Constrained Policy Optimization [1.4323566945483497]
  Engagement-optimized adaptive tutoring systems may prioritize short-term behavioral signals over sustained learning outcomes.<n>We introduce Mastery-Conditioned Constrained Policy Optimization (MC-CPO), a two-timescale primal-dual algorithm that integrates structural action masking with constrained policy optimization.<n>Across 10 random seeds and one million training steps in the neural regime, MC-CPO satisfies constraint budgets within tolerance, reduces safety costs relative to unconstrained and reward-shaped baselines, and substantially lowers the Reward Hacking Severity Index (RHSI)
  arXiv  Detail & Related papers  (2026-04-05T20:13:34Z)
• CoVeR: Conformal Calibration for Versatile and Reliable Autoregressive Next-Token Prediction [49.09876340754804]
  conformsctextCoVeR is a model-free decoding strategy that balances search efficiency with the need for versatile trajectories.<n>We show that conformsctextCoVeR simultaneously maintains a compact search space and ensures high coverage probability over desirable trajectories.
  arXiv  Detail & Related papers  (2025-09-05T01:07:12Z)
• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality [53.525547349715595]
  We propose a novel primal-only algorithm called Rectified Robust Policy Optimization (RRPO)<n>RRPO operates directly on the primal problem without relying on dual formulations.<n>We show convergence to an approximately optimal feasible policy with complexity matching the best-known lower bound.
  arXiv  Detail & Related papers  (2025-08-24T16:59:38Z)
• Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees [0.3058340744328236]
  Conformal Mixed-Integer Constraint Learning provides probabilistic feasibility guarantees for data-driven constraints in optimization problems.<n>We show that C-MICL consistently achieves target rates, maintains competitive objective performance, and significantly reduces computational cost compared to existing methods.
  arXiv  Detail & Related papers  (2025-06-04T03:26:31Z)
• Ensuring Safety in an Uncertain Environment: Constrained MDPs via Stochastic Thresholds [28.4976864705409]
  This paper studies constrained Markov decision processes (CMDPs) with constraints against thresholds, aiming at the safety of reinforcement learning in unknown and uncertain environments.<n>We leverage a GrowingWindow estimator sampling from interactions with the uncertain and dynamic environment to estimate the thresholds, based on which we design Pessimistic-Optimistic Thresholding (SPOT)<n>SPOT enables reinforcement learning under both pessimistic and optimistic threshold settings.
  arXiv  Detail & Related papers  (2025-04-07T11:58:19Z)
• Resilient Constrained Reinforcement Learning [87.4374430686956]
  We study a class of constrained reinforcement learning (RL) problems in which multiple constraint specifications are not identified before study. It is challenging to identify appropriate constraint specifications due to the undefined trade-off between the reward training objective and the constraint satisfaction. We propose a new constrained RL approach that searches for policy and constraint specifications together.
  arXiv  Detail & Related papers  (2023-12-28T18:28:23Z)
• Latent State Marginalization as a Low-cost Approach for Improving Exploration [79.12247903178934]
  We propose the adoption of latent variable policies within the MaxEnt framework. We show that latent variable policies naturally emerges under the use of world models with a latent belief state. We experimentally validate our method on continuous control tasks, showing that effective marginalization can lead to better exploration and more robust training.
  arXiv  Detail & Related papers  (2022-10-03T15:09:12Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints. We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates. The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
  arXiv  Detail & Related papers  (2022-09-16T09:38:38Z)
• Robust Constrained Reinforcement Learning [21.316736188238806]
  Constrained reinforcement learning is to maximize the expected reward subject to constraints on utilities/costs. We propose a framework of robust constrained reinforcement learning under model uncertainty. The goal is to guarantee that constraints on utilities/costs are satisfied for all MDPs in the uncertainty set, and to maximize the worst-case reward performance over the uncertainty set.
  arXiv  Detail & Related papers  (2022-09-14T18:29:02Z)
• Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL [43.672794342894946]
  Reward-free reinforcement learning (RF-RL) relies on random action-taking to explore the unknown environment without any reward feedback information. It remains unclear how such safe exploration requirement would affect the corresponding sample complexity in order to achieve the desired optimality of the obtained policy in planning. We propose a unified Safe reWard-frEe ExploraTion (SWEET) framework, and develop algorithms coined Tabular-SWEET and Low-rank-SWEET, respectively.
  arXiv  Detail & Related papers  (2022-06-28T15:00:45Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  We propose Penalized Proximal Policy Optimization (P3O), which solves the cumbersome constrained policy iteration via a single minimization of an equivalent unconstrained problem. P3O utilizes a simple-yet-effective penalty function to eliminate cost constraints and removes the trust-region constraint by the clipped surrogate objective. We show that P3O outperforms state-of-the-art algorithms with respect to both reward improvement and constraint satisfaction on a set of constrained locomotive tasks.
  arXiv  Detail & Related papers  (2022-05-24T06:15:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.