acceptodds
Under review as a conference paper at ICLR 2027

Learning-Guided Formal Abstractions for Policy Synthesis in Stochastic Systems

Abstract

We study nonlinear stochastic control problems with reach-avoid objectives, modeled as Markov decision processes (MDPs) over continuous state-action spaces. Our goal is to compute a policy with a certified lower bound on its probability of satisfying a given reach-avoid objective. Formal abstraction methods provide such guarantees but often scale poorly, as discretizing the state-action space leads to prohibitively large abstract models. By contrast, reinforcement learning (RL) scales better but provides no such guarantees. We introduce learning-guided abstractions, which combine the learning abilities of RL with the guarantees of formal abstractions. Specifically, we use an RL policy to identify a small region of promising state-action pairs and construct a sound abstraction only over this region. The resulting abstraction is represented as a set-valued MDP, on which we synthesize an optimal policy that can be refined to the original continuous MDP with a certified lower bound on its reach-avoid probability. Crucially, RL guides where abstraction effort is spent, while the formal abstraction guarantees the correctness of the synthesized policy. Across our benchmarks, learning-guided abstractions reduce the number of abstract state-action pairs by up to three orders of magnitude while retaining tight probabilistic guarantees, enabling policy synthesis at resolutions and problem sizes for which standard exhaustive abstractions are prohibitive.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Formal Verification, Policy Synthesis, Reinforcement Learning, Stochastic Dynamical Systems, Finite Abstractions

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_gsKxOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper looks into the problem of finding a control policy for a non linear, stochastic, continuous state and action environment with a certified lower bound on the probability of satisfying a reach avoid specification. The method used by the authors is to train a deep RL (PPO or SAC) agent on the environment to get a policy that satisfies the required lower bound. They use the trajectory from this policy to build a state action tube, i.e, the set of states and actions that are nearby the state and actions relevant for the policy via two hyperparameters β\beta and κ\kappa. Everything outside the tube is considered to be a single state souts_{out}. The resulting state space is encoded as an SMDP where a robust policy iteration is used to get a verified optimal policy. The major advantage of this work is in the reduction of the state space that needs to be abstracted which empirically shown on environments against a baseline where all of the state space is abstracted (Gracia & Lahijanian 2025).

Critical strengths

Following are the strengths of the paper:

  • The idea is simple and easy to follow, figure 1 gives the reader a good understanding of the high level working of the algorithm.
  • The empirical evaluation shows the baseline running out of memory in many benchmarks (Cartpole, Dubins4D, Drone6D) and shows good scalability for the introduced method.
  • The correctness argument is clean and mostly follows from Gracia & Lahijanian 2025.
Critical weaknesses

Following are the weaknesses:

  • While the authors claim that initial state can be a set of states, the empirical evaluation has benchmarks where the initial state is a single state. It would be interesting to see how the method works when the initial state is a dense set.
  • The pseudocode of Algorithm 1 has an improvement loop where β\beta and κ\kappa are increased if the probability does not satisfy the lower bound. The experiments have a fixed β\beta and κ\kappa parameter which are different for each of the benchmark. We are not sure how this parameters were obtained and whether the improvement loop was run.
Questions for authors
  1. Could you add at least one benchmark with a box shaped X_0 ?
  2. How were β\beta, κ\kappa, and N chosen per benchmark?
  3. How does the method compare against the other papers mentioned in related works?
1 comment

Thank you for the valuable feedback and suggestions. We updated our paper with a new experiment on larger initial state sets (Q4 in Section 5) and respond to your questions below.

1. Experiments with sets of initial states

Thank you for this suggestion. We added this experiment as Q4 in Section 5 of our paper; see point 1 of the shared response for details. The results (Figure 4 in our updated paper) show that the reach-avoid probability is robust to moderately sized initial state sets X0\mathcal{X}_0, while retaining the benefits of smaller abstractions and lower runtimes. For Drone4D, the median reach-avoid probability (over 5 seeds) remains close to the dense baseline; for Dubins4D, this comparison is not possible as the dense baseline runs out of memory. Interestingly, also when randomly initialized within a larger set X0\mathcal{X}_0, the RL rollouts still converge to a narrow tube (as can be seen by comparing the upper-right panel of Figure 4 with the left panel of Figure 1). For more details on this new experiment, please see point 1 of our shared response and Q4 in Section 5 of the revised paper.

In addition, the experiments in Table 2 of our original submission already consider a set of initial states (not a singleton initial set). Please refer to the shared response, point 1, for more details. We updated Table 2 and the text for Q3 to clarify this.

2. Choosing β\beta, κ\kappa, and NN

As written on line 428, Table 1 reports a single iteration of Algorithm 1 with the selected β\beta and κ\kappa. Instead of running the improvement loop explicitly, Table 5 (Q2) emulates it by sweeping β\beta and κ\kappa. We agree that our original submission overclaimed that we evaluated the improvement loop in Algorithm 1, so we corrected this claim (line 359).

For details on how we chose β\beta and κ\kappa for Table 1, please see our shared response, point 2.

Similarly, we tested several partition sizes NN and chose values that provide good reach-avoid probabilities but are also not unnecessarily fine-grained (as confirmed by Table 4 in App. G.3, which shows that dense abstractions with fewer states often cause vacuous bounds). Choosing the partition size is inherent to any abstraction-based approach and can indeed be challenging in practice. As discussed in our related work (lines 103-105), this has motivated iterative and adaptive (non-uniform) partitioning procedures (Lahijanian et al., 2015; Soudjani and Abate, 2013; Dutreix and Coogan, 2021). These procedures are complementary to our approach (see Section 4.2, line 359) but introduce additional design choices, and combining them with our tube-based construction is a non-trivial extension beyond our current scope.

We clarified the selection of β\beta, κ\kappa, and NN in Appendix G.1 (lines 1080-1091).

3. Comparison against other related work

As we discuss on lines 101-118, the related work falls into three main categories:

  1. (Abstractions) Most abstraction techniques construct dense abstractions over the entire state-action space, including Gracia & Lahijanian (2025), which is our experimental baseline. An exception is Sun and Shoukry (2022), which uses a learned policy to restrict actions but not states, thus leading to much smaller reductions than our tube-based construction. For example, for CartPole, reducing the number of actions from 41 to 5 but keeping the dense state space still uses 1.6×109×5=8×1091.6 \times 10^9 \times 5 = 8 \times 10^9 state-action pairs, which far exceeds our machine's memory (by contrast, our learning-guided abstraction has 470×470 \times fewer state-action pairs). Majumdar et al. (2021) use an open-loop plan to guide abstraction, but in a different problem setup (non-stochastic systems and qualitative reach-avoid specifications).

  2. (Certificates) Reach-avoid supermartingale certificates, proposed by Zikelic et al. (2023) and extended by Badings et al. (2025), solve the same problem as we do (Problem 1). However, our approach is more than 10x faster than Badings et al. (2025) on their benchmarks (see Q3, Table 2). The other cited works on certificates consider different models and/or specifications and are thus not directly applicable.

  3. (Shields) Applying shields to continuous state-action control problems (like Problem 1) relies on finite abstraction techniques, therefore inheriting the same characteristics as related work from the first category.

Reviewer_yDVTOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper synthesizes control policies with a certified lower bound on the reach-avoid probability for nonlinear stochastic systems with continuous states and actions. Instead of abstracting the whole state-action space into a set-valued MDP (SMDP), whose size grows exponentially with dimension, it uses rollouts of an RL policy to select a small tube of grid cells and actions, abstracts only that tube, and treats everything outside it as unsafe. The authors prove that the resulting bound is sound regardless of how good the RL policy is, and that enlarging the tube can only improve it. On nine benchmarks up to 6D, the sparse abstraction is up to three orders of magnitude smaller than the dense one, handles three cases where the dense abstraction runs out of memory, and is reported to be 10–25× faster than a neural-certificate method.

Critical strengths
  1. The division of labor is clean: RL only suggests where to spend abstraction effort, and the guarantee comes entirely from the SMDP. The method therefore stays sound even with a poor RL policy, and the Monte Carlo checks exceed every reported bound.

  2. The scaling gain is well supported. CartPole, Dubins4D and Drone6D cannot be handled by the dense abstraction on the same machine, yet get certified bounds of 97.7–99.7% with the tube, while a coarser dense abstraction of the same size fails to give tight bounds (Sec. 5).

Critical weaknesses
  1. All reported bounds are for a single initial state (Sec. 5), while Problem 1 and the motivation are stated for an initial set X0. With one starting point, a thin tube around the rollouts is natural; with a realistic initial set the tube must cover every start, and much of the size reduction, which is the paper's main claim, may disappear. This also makes the 10–25× comparison in Table 2 hard to interpret if the neural certificates cover a whole initial set.

  2. The only baseline is the dense abstraction, so it is unclear how much the learning component matters. Since soundness does not depend on the guide, the tube could also be built from non-RL trajectories, as in the trajectory-guided abstraction of [1] that the paper itself cites, e.g., from a sampling-based planner such as RRT* [2] or LQR-stabilized trajectories as in LQR-Trees [3]. The runtime comparison is also optimistic: β and κ need per-benchmark tuning (values that are too small give vacuous bounds, Sec. 5), but Table 1 reports a single iteration with the final values.

References:

[1] R. Majumdar, K. Mallik, M. Salamati, S. Soudjani, and M. Zareian. Symbolic reach-avoid control of multi-agent systems. ICCPS, 2021.

[2] S. Karaman and E. Frazzoli. Sampling-based algorithms for optimal motion planning. IJRR, 30(7):846–894, 2011.

[3] R. Tedrake, I. R. Manchester, M. Tobenkin, and J. W. Roberts. LQR-trees: Feedback motion planning via sums-of-squares verification. IJRR, 29(8):1038–1052, 2010.

Questions for authors
  1. Could you run one benchmark, e.g., Drone4D from Table 1, with an initial box instead of a single point, and report how tube size, runtime and the bound change? Please also state which X0 was used in Table 2.

  2. How does a tube built from a non-RL guide, such as those in Weakness 2, compare with the PPO/SAC tube on the 4D benchmarks?

  3. How were β and κ chosen for Table 1, and what is the total runtime if Algorithm 1 starts from small values and expands the tube?

Minor: Table 1 reports the bound averaged over 5 seeds; for a certificate, the worst seed is more informative.

2 comments

Thank you for the valuable feedback and suggestions for further experiments. We added a new experiment (Q4) using larger initial state sets, and an exploratory experiment with kinodynamic RRT as a non-RL alternative for tube construction. We respond to your concrete questions below.

1. Experiments with sets of initial states

Thank you for this suggestion. We added this experiment as Q4 in Section 5 of our paper. The results (Figure 4 of our updated paper) show that the reach-avoid probability is robust to moderately sized initial state sets X0\mathcal{X}_0 (for Drone4D, the median over 5 seeds stays close to the dense baseline; for Dubins4D, the baseline runs out of memory), while retaining the benefits of smaller abstractions and lower runtimes. Interestingly, the RL rollouts still converge to a narrow tube when randomly initialized within the larger X0\mathcal{X}_0 (e.g., compare the upper-right panel of Figure 4 with the left panel of Figure 1). For more details on this new experiment, please see point 1 of our shared response and Q4 in Section 5 of the revised paper.

For Table 2, the initial sets X0\mathcal{X}_0 are non-singletons taken directly from Badings et al. (2025) and now listed in App. G.2.10 (see shared response, point 1). Thus, the speed-up in Table 2 (now corrected from 10-25x to 11-29x) is a fair comparison. We updated Table 2 and the text for Q3 to clarify this.

2. RRT baseline

Our framework is indeed compatible with any approach that gives a state-action tube, including sampling-based planners. However, we believe that RL is better suited to our setup for two reasons:

  1. RL computes a policy. We use this policy to identify not only active states but also active actions, whereas a planned path (in the form of a sequence of actions) can only determine active states, as the plan's actions are time- and not state-dependent.
  2. We consider stochastic dynamics. Although sampling-based planners such as RRT can sample from stochastic dynamics, they still produce a single plan. Generating rollouts then either requires sampling new trajectories under this plan's action sequence (which may lead to bad trajectories, e.g., hitting obstacles) or computing plans from other initial states x0∈X0x_0 \in \mathcal{X}_0 (which is computationally expensive). By contrast, RL algorithms such as PPO and SAC inherently account for stochasticity, and generating rollouts under the learned policy is cheap.

Exploratory RRT experiment. Yet, we agree that an empirical evaluation of a sampling-based planner is interesting. As a first step, we ran an exploratory experiment on Drone4D and Dubins4D using RRT instead of RL in Appendix G.3.1 of the revised paper. We use kinodynamic RRT as in LaValle & Kuffner (2001) to plan from the center of X0\mathcal{X}_0 to XT\mathcal{X}_T, omitting the rewiring step of RRT$^\star$, which requires solving an (expensive) two-point boundary value problem at every step. Due to stochastic dynamics, the plan is feasible under some sequence of noise realizations but may be infeasible under different realizations. Thus, we do not generate multiple rollouts and just construct a tube around the RRT trajectory. The results show two things:

  1. The RRT-based approach can underestimate risk. For example, Figure 7 in the revised paper shows that, for Drone4D, it takes the narrow path around the first obstacle. This significantly degrades the bound on the reach-avoid probability: with β=(8,6,8,6)\beta = (8,6,8,6), RRT gives only 69.05%, compared with ~98% using RL with β=(4,2,4,2)\beta = (4,2,4,2).
  2. The RRT-based approach requires a higher state-inflation β\beta. Together with the fact that RRT cannot reduce the active actions, this gives larger abstractions than using RL. In Dubins4D, RRT requires β=(10,10,10,10)\beta=(10,10,10,10) to obtain a bound of 98.93% comparable to RL at β=(5,5,5,5)\beta=(5,5,5,5), using ~3 times more state-action pairs.

These results suggest that RL is indeed better suited to our approach than sampling-based planners. A systematic comparison with other variants, e.g., LQR-trees (Tedrake et al., 2010), would be interesting for future work.

3. Choosing β\beta and κ\kappa

Please see our shared response, point 2, for details on how we chose β\beta and κ\kappa for Table 1.

We agree that it is very interesting to evaluate Algorithm 1 with incremental tube expansion. Naively, the total runtime would be the sum of abstraction and synthesis times for all iterations, plus the RL training time once. Since earlier iterations use smaller tubes, this overhead is small. For example, the Drone4D (PPO) iteration in Figure 6 at β=(2,1,2,1)\beta=(2,1,2,1) takes 4.8s versus 14.2s at (4,2,4,2)(4,2,4,2), while the dense baseline needs 324s. In principle, we can leverage the monotonicity of tube expansion (Theorem 2) and reuse the computed value functions across expansion iterations. We believe such reuse between iterations deserves a systematic study beyond the scope of our current paper.

Thanks for the response and the new experiments. They address most of my questions. I’ll keep my score at 3.

Reviewer_TNPyOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents an approach to learn a policy that limits the abstraction of a state-action space. They train an initial policy to identify a small set of relevant state-action pairs, create a finite abstraction over this set, and compute an optimal policy. Their main contribution is the identification of a sparse tube of relevant state-action pairs, and they compare this against set-valued Markov decision processes using the full state-action space from Gracia & Lahijanian (2025). They prove that the sparse abstraction is sound and abstract model sizes are reduced significantly across several RL benchmarks.

Critical strengths

The results show abstraction sizes can be reduced by up to three orders of magnitude without significantly impacting the reach-avoid probability. This is a strong result which supports their approach’s ability to avoid out-of-memory errors. The dense approach leads to OOM on three of the benchmarks, while the new approach is able to solve them.

Critical weaknesses

Out of the two refinement mechanisms used, only the tube expansion one is evaluated separately. The research questions only address this mechanism and not the RL policy improvement method. The paper states both are evaluated, but all experiments run a single iteration of Algorithm 1, so the RL-improvement step and the full loop are never tested.

Every benchmark uses a singleton initial state for every benchmark while Problem 1 asks for a guarantee over all initial states x_0 in X_0. Rollouts from a single point naturally produce a narrow tube, so it is unclear whether the reported reductions hold when X_0 is a set, as Problem 1 requires.

Questions for authors

How long does it take to improve the RL policy if it was unable to identify a helpful tube? What is the stopping criterion?

How were the state-inflation values selected? Is there any reason why there is such a large jump in reach-avoid probability between (2, 1, 2, 1) and (4, 2, 4, 2) in Table 5?

2 comments

Thank you for the valuable feedback. We updated our paper with a new experiment with larger initial state sets (Q4 in Section 5) and respond to your questions below.

(1) Experiments with sets of initial states

Please see our shared response, point 1, where we clarify that the experiments in Table 2 of our original submission already consider a set of initial states (not a singleton initial state). As discussed in the shared response, we updated Table 2 and the text for Q3 to clarify this.

Nevertheless, we agree that the experiments in Q1 and Table 1 did not properly evaluate robustness against larger initial state sets. Thus, we added a new experiment, Q4, to our paper. The results (Figure 4 in our updated paper) show that the reach-avoid probability is robust to moderately sized initial state sets X0\mathcal{X}_0, while retaining the benefits of much smaller abstractions and lower runtimes. For Drone4D, the median reach-avoid probability (over 5 seeds) remains close to the dense baseline; for Dubins4D, this comparison is not possible as the dense baseline runs out of memory. Differences between seeds do increase with X0\mathcal{X}_0, because the RL rollouts vary more. Interestingly, also when randomly initialized within a larger set X0\mathcal{X}_0, the RL rollouts still converge to a narrow tube (as can be seen by comparing the upper-right panel of Figure 4 with the left panel of Figure 1). For more details on this new experiment, please see point 1 of our shared response and Q4 in Section 5 of the revised paper.

(2) RL policy improvement

As written on line 428, our experiments ran a single iteration of Algorithm 1. We agree that our original submission overclaimed that we evaluated "RL policy improvement" in Algorithm 1, so we corrected this claim (line 359). Instead, to determine the number of RL training steps used for each benchmark, we ran RL training for increasing numbers of steps (starting from 100k). For each value, we computed the fraction of rollouts that reached the target and stopped once we found a setting that led to a high fraction of successful rollouts. Using this stopping criterion, we obtained the numbers of training steps reported in Appendix G for each benchmark. We used these values consistently across all benchmarks in Section 5.

We agree that developing and evaluating more sophisticated policy improvement loops is an interesting research direction. In a naive loop, each additional round of RL training would train from scratch and thus cost roughly the RL training time reported in Table 1 (15-517 seconds, depending on the benchmark). Alternatively, we could continue training the previous RL policy checkpoint, which reduces training time but increases the chance of ending in a local optimum. In the future, we also plan to incorporate feedback from the abstraction (e.g., abstract states with a low reach-avoid probability) to shape the RL reward function. This could guide the agent toward better policies more efficiently than simply increasing training steps.

(3) Choosing state-inflation values

Please see our shared response, point 2, for details on how we selected the state-inflation values β\beta.

The large jump between (2,1,2,1)(2,1,2,1) and (4,2,4,2)(4,2,4,2) in Table 5 is caused by the conservative worst-case abstract dynamics. For each noise cell, the successor set in Eq. (5) spans three cells per position dimension, so at every step, the worst-case adversary picks a successor one cell away from the center of the successor set. When the drone changes direction (e.g., in the two corners), the velocity uncertainty also builds up, and the worst-case trajectory drifts several cells away from the states visited by the RL policy. For β=(2,1,2,1)\beta = (2,1,2,1), this drift leaves the tube, leading to poor reach-avoid probabilities. With β=(4,2,4,2)\beta = (4,2,4,2), the tube is wide enough for the policy to steer back toward the center. We added this explanation and heatmaps of the reach-avoid probability for Drone4D to App. G.3 (Figure 6), showing that for the smaller β\beta, the reach-avoid probability is indeed lost when the drone changes direction.

Reviewer_TNPyOpenReview ↗

Thank you.

Thank you for the rebuttal response that address most of my concerns. I will maintain my original weak-accept rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Shared response to all reviewers

We thank the reviewers for their valuable feedback and questions. In this shared response, we summarize the main changes made to our paper, and we address shared comments regarding (1) experiments with sets of initial states and (2) the choices for parameters β\beta and κ\kappa.

Summary of changes to paper

In response to the reviews, we made the following changes to the paper:

  1. We added a new major experiment (Q4 in Section 5) to investigate the robustness of our approach against larger initial state sets.
  2. We clarified that the experiments for Q3 and in Table 2 are already for sets of initial states.
  3. We added a discussion paragraph (lines 517-524 in Section 5) to better reflect on the benefits and limitations of our learning-guided abstractions.
  4. We added an exploratory comparison using RRT instead of RL to compute tubes (Appendix G.3.1).

(1) Experiments with sets of initial states

Table 2 already uses sets of initial states. First, we clarify that the benchmarks in Table 2 of our original paper (comparison to neural certificates) already use a set of initial states X0\mathcal{X}_0, matching the benchmarks of Badings et al. (2025). We added X0\mathcal{X}_0 for each benchmark to Appendix G.2.10; e.g., for CollisionAvoidance, it is a union of two boxes:

X0=([−1,−0.9]×[−0.6,0.6])∪([0.9,1]×[−0.6,0.6]).\quad \mathcal{X}_0 = \bigl([-1,-0.9]\times[-0.6,0.6]\bigr)\cup\bigl([0.9,1]\times[-0.6,0.6]\bigr).

As stated in Section 4 (line 284), we generate RL rollouts from initial states sampled uniformly from X0\mathcal{X}_0. The bounds reported in Table 2 are the minimum bounds on the reach-avoid probability over all abstract states whose cell intersects X0\mathcal{X}_0. We agree this was unclear in the original submission, so we corrected the header of Table 2 and updated the text for Q3 in Section 5.

New experiment (Q4). The benchmarks in Table 1 are indeed defined with a singleton initial state X0=x0\mathcal{X}_0 = \\{ x_0 \\}. By Theorems 1-2, our lower bound on the reach-avoid probability is constant over each partition cell CsC_s. The values in Table 1 therefore hold not only for x0x_0, but for the entire cell containing x0x_0.

Nevertheless, we agree with the reviewers that this does not yet properly evaluate robustness against larger initial sets, so we added a new experiment, Q4, to our paper. The results (Figure 4 of our updated paper) show that the benefits of learning-guided abstractions are retained for moderately sized X0\mathcal{X}_0: for Drone4D, the median minimum reach-avoid probability over X0\mathcal{X}_0 stays close to the dense baseline, while our abstractions have 4.4-6.6x fewer states and lower runtimes than the baseline. Dubins4D is less robust, but since the dense baseline runs out of memory, it is unclear how much of this drop is due to our sparse abstraction versus inherently bad initial states in the larger X0\mathcal{X}_0. For full details and results, please see Q4 in Section 5 of the revised paper.

(2) Choices for parameters β\beta and κ\kappa

To choose the state-inflation β\beta and the number of active actions per abstract state κ\kappa used for our experiments, we evaluated several values in reasonable increments. For example, for Dubins3D and Drone4D, we evaluated a grid of 4×54 \times 5 values for β\beta and κ\kappa reported in Table 5 of Appendix G.3. Note that both β\beta and κ\kappa are integer-valued, so the number of reasonable choices (e.g., symmetric values across spatial (x,y,z) state dimensions) is often limited.

By Theorem 2, increasing β\beta or κ\kappa never decreases the reach-avoid probability, but it does increase the abstraction size (e.g., Table 5 shows that increasing β\beta from (4,2,4,2)(4,2,4,2) to (6,3,6,3)(6,3,6,3) at κ=9\kappa = 9 for Drone4D increases the bound on the reach-avoid probability only from 99.19% to 99.33%). For our experiments in Table 1, we therefore use values beyond which the improvement is marginal. We clarified the selection of β\beta, κ\kappa, and other key parameters in Appendix G.1 (lines 1080-1091) and refer to this appendix on line 416.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.