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

1. Problem Statement

The paper addresses a fundamental gap in applying Deep Reinforcement Learning (RL) to optimal safe controller synthesis.

• The Mismatch: Classical safe control (based on Hamilton-Jacobi reachability) seeks to maximize the set of initial states from which a system can remain safe indefinitely (worst-case safety). Standard RL, however, optimizes expected returns over a user-specified distribution of initial conditions. This leads to policies that perform well on frequently sampled states but fail catastrophically in low-probability regions that are still within the safe set.
• The Robust Formulation: A natural alternative is Robust Optimization: finding a policy that minimizes cost under the worst-case initial condition within a specified set of parameters $\Theta$ (which includes initial states, dynamics, and safety constraints).
• The Core Challenge (Unknown Feasibility): A robust optimization problem is only solvable if the specified set of parameters is feasible (i.e., there exists a policy that keeps the system safe for all parameters in the set). However, determining the largest feasible subset $\Theta^* \subseteq \Theta$ is the very goal of the control problem and is computationally intractable to solve exactly.
  • If the set includes infeasible parameters, the robust objective becomes unsatisfiable (all policies yield the same worst-case failure), causing the learning process to degenerate.
  • If the set is too small, the resulting policy is not robust enough.

Goal: Simultaneously identify the largest feasible subset of parameters $\Theta^*$ and learn a policy $\pi$ that is safe for all $\theta \in \Theta^*$.

2. Methodology: Feasibility-Guided Exploration (FGE)

The authors propose Feasibility-Guided Exploration (FGE), a framework that interleaves feasibility estimation with robust policy optimization. The method consists of three core components:

A. Estimating the Feasible Parameter Set ($\Theta^*$)

Since feasibility labels are asymmetric (an observed safe rollout proves feasibility, but an unsafe rollout may just mean the current policy is suboptimal), standard supervised learning fails.

• Conservative Classifier: FGE trains a classifier $q_\psi(f=1|\theta)$ to predict if a parameter $\theta$ is feasible.
• Data Mixing: To handle the lack of negative labels, the training data is a mixture of:
  1. Positive Labels: Parameters observed to be safe ($D_f$).
  2. Noisy Labels: On-policy rollouts (which may be unsafe due to suboptimal policies).
• Theoretical Guarantee: By mixing these distributions with a coefficient $\alpha$, the classifier is guaranteed to have zero false positives (never marks an infeasible parameter as feasible) while controlling the false-negative rate. This ensures the robust constraint remains satisfiable.

B. Feasible Robust Optimization via Saddle-Point Finding

Once a feasible set estimate $\tilde{\Theta}^*$ is obtained, the problem is framed as a minimax game:
$$\max_{\pi} \min_{\theta \in \tilde{\Theta}^*} J(\pi, \theta)$$

• Adversarial Dynamics: Instead of using a Gaussian adversary (as in RARL) which struggles to constrain outputs to feasible regions, FGE uses Online Learning techniques.
• FTRL (Follow-the-Regularized-Leader): The policy update uses FTRL with a quadratic regularizer to ensure stability and sublinear regret.
• Best-Response Approximation: The adversary (parameter selector) performs a "best-response" search over the estimated feasible set $\tilde{\Theta}^*$ to find the worst-case parameter for the current policy. This is approximated using a learned policy classifier to predict performance.

C. Expanding the Feasible Set (Exploration)

To prevent the algorithm from getting stuck in a small feasible region (negative feedback loop), FGE introduces an explicit Exploration Distribution:

• Rejection Sampling: The algorithm actively samples parameters that the current classifier predicts as infeasible (or uncertain).
• Goal: Force the policy to attempt these difficult parameters. If a rollout succeeds, the parameter is added to the feasible set $D_f$, expanding $\tilde{\Theta}^*$.
• Rehearsal Buffer: The algorithm also maintains a buffer of "hard but feasible" parameters where the current policy performs poorly, ensuring they are re-trained.

The Training Loop:

1. Sample parameters from a mixture of: Base distribution, Explore distribution (rejection sampling on infeasible), and Rehearsal distribution (hard feasible).
2. Run on-policy RL (PPO) to update the policy.
3. Update the feasibility classifier using new safe rollouts.
4. Update the "worst-case" parameter buffer (best-response).

3. Key Contributions

1. Novel Objective: Formalized the Parameter-Robust Avoid Problem with Unknown Feasibility, which jointly optimizes for the maximal feasible parameter region and the safe policy.
2. FGE Framework: Proposed a practical algorithm that combines:
   • Constraint-driven exploration to expand the feasible set.
   • Saddle-point finding (using online learning/FTRL) for robust optimization.
   • A conservative feasibility classifier with theoretical guarantees on false positives.
3. Empirical Superiority: Demonstrated that FGE learns policies with significantly larger safe sets compared to state-of-the-art baselines.

4. Experimental Results

The method was evaluated on a suite of high-dimensional tasks in the MuJoCo simulator and other environments (Autonomous Driving, Fixed-Wing Aircraft, Lunar Lander).

• Baselines: Compared against Domain Randomization (DR), Robust Adversarial RL (RARL), Curriculum Learning methods (VDS, PLR), and Unsupervised Environment Design (UED) methods (PAIRED, FARR, ACCEL, SFL).
• Performance Metrics:
  • Safety Rate: FGE achieved the highest safety rates across all tasks.
  • Coverage Gain: FGE discovered >50% more feasible "hard" parameters compared to the best existing methods (specifically DR).
  • Coverage Loss: FGE maintained high performance on "easy" parameters, showing no significant degradation compared to baselines.
• Case Studies:
  • Dubins Car: FGE successfully learned to navigate extremely rare, tight gaps (overtaking scenarios) that other methods crashed on, by allocating more samples to these regions via rejection sampling.
  • Hopper: FGE learned recovery maneuvers for falling through gaps between platforms, whereas baselines failed to concentrate samples on these specific difficult regions.
  • High-Dimensional Inputs: FGE scaled effectively to tasks with RGB image observations (Lander2D) and 9D parameter spaces (Lander9D).
• Ablation Studies:
  • Removing the Explore Distribution drastically reduced coverage gain.
  • Removing the Rehearsal Buffer caused training instability and higher coverage loss.
  • The proposed Mixture Classifier outperformed density-based approaches (Neural Spline Flows, Planar Flows).

5. Significance

• Bridging Theory and Practice: The paper successfully bridges the gap between rigorous Hamilton-Jacobi safety analysis (which is often intractable in high dimensions) and scalable Deep RL.
• Solving the "Unknown Feasibility" Paradox: It provides a solution to the chicken-and-egg problem where one needs a feasible set to train a robust policy, but needs a robust policy to find the feasible set.
• Safety-Critical Applications: The method is particularly relevant for safety-critical systems (autonomous driving, aviation, robotics) where ensuring safety over the entire operating envelope is required, not just on average.
• Efficiency: By using rejection sampling and a conservative classifier, FGE avoids wasting resources on truly impossible scenarios while aggressively exploring the boundary of what is possible.

In summary, FGE represents a significant advancement in safe RL by enabling agents to autonomously discover the limits of their safety capabilities and learn policies that are robust to the widest possible range of environmental conditions.