Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning

Oswin So; Eric Yang Yu; Songyuan Zhang; Matthew Cleaveland; Mitchell Black; Chuchu Fan

cs.LGFeb 17, 2026

Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning

Authors: Oswin So, Eric Yang Yu, Songyuan Zhang, Matthew Cleaveland, Mitchell Black, Chuchu Fan

Organizations: Department of Aeronautics and Astronautics, MIT · MIT Lincoln Laboratory

Abstract

Recent advances in deep reinforcement learning (RL) have achieved strong results on high-dimensional control tasks, but applying RL to reachability problems raises a fundamental mismatch: reachability seeks to maximize the set of states from which a system remains safe indefinitely, while RL optimizes expected returns over a user-specified distribution. This mismatch can result in policies that perform poorly on low-probability states that are still within the safe set. A natural alternative is to frame the problem as a robust optimization over a set of initial conditions that specify the initial state, dynamics and safe set, but whether this problem has a solution depends on the feasibility of the specified set, which is unknown a priori. We propose Feasibility-Guided Exploration (FGE), a method that simultaneously identifies a subset of feasible initial conditions under which a safe policy exists, and learns a policy to solve the reachability problem over this set of initial conditions. Empirical results demonstrate that FGE learns policies with over 50% more coverage than the best existing method for challenging initial conditions across tasks in the MuJoCo simulator and the Kinetix simulator with pixel observations.

Figures & tables

Figure 1: FGE modifies the parameter sampling distribution. FGE modifies the base distribution over the parameters by introducing an explore distribution to improve policy performance on parameters that have not been observed to be safe so far, and a rehearsal distribution obtained via sampling-based approximate best response to train on poorly performing parameters that were previously solved. We combine all three distributions to obtain the final distribution for FGE that balances the objectives of maximizing safety rate gain and minimizing safety rate loss.

Figure 2: Adaptive Cruise Control Example. We illustrate an example using an autonomous driving scenario. The parameters $\theta=[\bar{a},v_{0}]$ model varying max acceleration $\bar{a}$ (e.g., from weather) and initial relative velocity $\Delta v_{0}$ . We want to avoid crashing into the car in front ( $\Delta p\leq 0$ ). ( Left ) We plot trajectories for different $\bar{a}$ and ( Right ) visualize the feasible parameter set $\Theta^{*}$ in green.

Figure 3: (Left) We only have positive labels for feasibility from the set of parameters that were measured to be safe $\mathcal{D}_{\mathfrak{f}{}}{}$ . Since we don’t have negative labels, standard supervised learning cannot be used. (Center) We address this by defining a target distribution $p_{\text{mix}}$ via mixing positive labels from $\color[rgb]{0.4648,0.4648,0.4648}p_{\mathcal{D}_{\mathfrak{f}{}}}(\theta)$ with noisy labels from $\color[rgb]{0.5078,0.4648,0.75}p^{\pi}$ , controlled by $\alpha$ . (Right) Approximating $\color[rgb]{0.3398,0.6445,0.5664}p_{\text{mix}}(\mathfrak{f}{}=1|\theta)$ with $\color[rgb]{0.2031,0.543,0.7422}q_{\psi}(\mathfrak{f}{}=1|\theta)$ using rollout samples and $\color[rgb]{0.4648,0.4648,0.4648}\mathcal{D}_{\mathfrak{f}{}}$ samples yields a feasibility classifier with no false positives and a controllable false-negative rate with $\alpha$ and $\rho$ ( Theorem 1 ).

Figure 4: Gradient Descent Ascent (GDA) vs FGE on a Bilinear Game. On

\max_{\pi\in[-1,1]}\min_{\theta\in[-1,1]}\pi\theta

for

\pi

, GDA fails to converge in last-iterate, while FGE using ( 12 ) converges to the saddle point at the origin. Both converge in average iterate (see App I ). We plot the average

\theta

for FGE.

Figure 5: Feasibility-Guided Exploration (FGE). Starting from an on-policy RL algorithm, we adapt the initial state distribution as a mixture of the base ( ) , exploration ( ) and rehearsal ( ) distributions. The exploration component expands the feasible set and the rehearsal buffer targets feasible parameters that the current policy underperforms. After each episode, newly discovered feasible parameters $\theta$ are added to the dataset $\mathcal{D}_{\mathfrak{f}{}}$ . A mixture of samples from $\mathcal{D}_{\mathfrak{f}{}}$ ( ) and the episode ( , ) forms $p_{\text{mix}}(\mathfrak{f}{},\theta)$ used to train the feasibility classifier $q_{\psi}$ . The feasibility classifier $q_{\psi}$ guides rejection sampling for the explore distribution. We also train a policy-conditioned classifier $p^{\pi}$ to predict $\pi$ ’s performance given $\theta$ , enabling approximate best-response selection of worst-case feasible $\theta$ ( ) for rehearsal . We use the ACC example and plot its parameter space in all plots (see Fig. 2 ).

Figure 6: Benchmark Tasks. Unsafe regions to be avoided are shown in red for each environment.

Panel of Figure 7 — Figure 7: FGE has the highest safety rates. ( Left ) Performance profile ( Agarwal et al., 2021 ) . At every threshold, FGE has the most runs with higher safety rate than the threshold, dominating all other baseline methods. ( Right ) IQM over all tasks. FGE achieves the highest safety rate by rendering the most hard parameters safe without losing coverage on easy parameters.

Figure 8: FGE renders challenging initial conditions safe by allocating more samples to them. ( left ) We analyze the Dubins environment and find two types of challenging initial conditions where the ego car must squeeze through a tight gap to remain safe. In particular, the overtake condition is extremely rare. (right) FGE allocates vastly more samples to this condition than VDS . (center) Consequently, FGE is able to solve this challenging overtake condition while VDS crashes.

Figure 9: Rejection Sampling Enables Efficient Exploration in FGE . The explore distribution in FGE effectively allocates samples to regions that have not been solved yet. By the middle plot, FGE has concentrated a third of its samples on the gap between the two platforms, eventually solving this region by the end of training. In contrast, VDS fails to remain safe in this region.

Figure 10: Heuristics used by existing methods do not concentrate samples as efficiently as FGE . Only FGE is able to effectively concentrate its samples in the difficult to solve gap region on Hopper .

Figure 11: FGE scales to high-dimensional observations ( Lander2D ) and high-dimensional parameter spaces ( Lander9D ). FGE maintains the highest safety rates even on tasks with RGB image observations ( Lander2D , Lander9D ) and with 9D parameter spaces ( Lander9D ).

Figure 14: Replacing the feasibility classifier with a density-based classifier hurts performance on Dubins .

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 15: Chain MDP

Figure 16: Variance of the single-sample gradient estimator for the chain MDP.

Figure 17: Multi Chain MDP

Figure 18: Coverage Comparison. (a) FGE achieves near

100\%

coverage across all environments, and consistently achieves the highest coverage in the harder environments. (b) FGE achieves the largest coverage increases relative to DR across all environments, substantially outperforming all other baselines. Other methods can expand on the feasible set of DR , but underperform FGE by

40\%

90\%

on the harder environments. (c) Most baselines do not lose coverage when compared to DR with the exception of RARL due to its instability during training. ACCEL also performs poorly due to the need for each rollout to last for the maximum episode steps, reducing the number of total updates steps taken. (d) With the exception of ToyLevels, almost all the unique safe parameters occur due to FGE , suggesting that FGE consistently renders parameters feasible that no other method can.

Figure 19: Training Curves.

Figure 20: RND ablation.

Figure 21: Value vs classifier for feasibility on Dubins .

Figure 22:

\alpha

sensitivity ablation.

Figure 23: Safe RL Pareto Frontier.

Method	Hyperparameter	Value
All	Neural Network Size	[256, 256]
	Activation Function	$\tanh$
	NN Optimizer	Adam
	# envs (per collect)	1024
	# rollout steps	30
FGE	$p_{\text{base}}$	0.02

Appendix

Table 1: Common hyperparameters across all tasks.

Method	Hyperparameter	ToyLevels	Dubins	Hopper	Cheetah	FixedWing
All	Policy learning rate	4e-4	5e-5	4e-4	4e-4	4e-4
	Value learning rate	1e-3	8e-4	8e-4	8e-4	8e-4
	# PPO epochs	5000	50000	50000	50000	50000
	Truncate timesteps	199	1000	1000	1000	1000
	Batch size	30	30	15	30	30
	Entropy coefficient	1e-3	5e-3	2e-3	1e-4	1e-4

Appendix

Table 2: Task-specific hyperparameters for each method.

Panel of Figure 31 — Figure 31: Numerical experiment on a toy example to investigate the sensitivity of the saddle-point finding iterates to violated assumptions.

Figure 32: Last-iterate and average-iterate errors on a bilinear game.

Safe RL

Safe reinforcement learning studies how agents can learn and act while respecting safety constraints and limiting harmful outcomes.

See all 213 papers

Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning
May 12, 2026Jingduo Pan, Taoran Wu, Yiling Xue +1Constrained RL Safe RL
Key Laboratory of System Software (Chinese Academy of Sciences), Institute of Software, Chinese Academy of Sciences, Beijing, China · University of Chinese Academy of Sciences, Beijing, China · School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences, Beijing, China
Beyond Hard Constraints: Budget-Conditioned Reachability For Safe Offline Reinforcement Learning
Mar 8, 2026Janaka Chathuranga Brahmanage, Akshat KumarSafe RL Constrained RL
School of Computing and Information Systems, Singapore Management University.
Certifying Almost-Sure Reachability in Unknown MDPs
Oct 13, 2026S Akshay, Suguman Bansal, Gaurav MahlaMarkov Decision Processes Reachability Analysis
Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai, India · School of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA

May 12, 2026J/K move · Enter open · S save

Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning

Jingduo Pan, Taoran Wu, Yiling Xue, Bai Xue

Key Laboratory of System Software (Chinese Academy of Sciences), Institute of Software, Chinese Academy of Sciences, Beijing, China · University of Chinese Academy of Sciences, Beijing, China · School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences, Beijing, China

Constrained RL Safe RL

Open paper AskPDF arXiv

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.

Abstract

Safe RL

Explore similar work

Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning

Beyond Hard Constraints: Budget-Conditioned Reachability For Safe Offline Reinforcement Learning

Certifying Almost-Sure Reachability in Unknown MDPs