- 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 and . Everything outside the tube is considered to be a single state . 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 and are increased if the probability does not satisfy the lower bound. The experiments have a fixed and 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
- Could you add at least one benchmark with a box shaped X_0 ?
- How were , , and N chosen per benchmark?
- How does the method compare against the other papers mentioned in related works?
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, 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, 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 β, κ, and N
As written on line 428, Table 1 reports a single iteration of Algorithm 1 with the selected β and κ. Instead of running the improvement loop explicitly, Table 5 (Q2) emulates it by sweeping β and κ. 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 β and κ for Table 1, please see our shared response, point 2.
Similarly, we tested several partition sizes N 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 β, κ, and N 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:
(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×109 state-action pairs, which far exceeds our machine's memory (by contrast, our learning-guided abstraction has 470× 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).
(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.
(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.