- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper applies reinforcement learning to node selection in interval subdivision solvers (Ibex) to find a single solution of parametric nonlinear systems . The formulation is a deterministic MDP: the state is (parameter vector , contracted box) and actions are left/right child selection after bisection; the step reward is , with terminal rewards for a certified solution leaf and for a dead or unknown leaf, and . Lemma 1 characterizes when Q-value comparisons across trajectories reduce to trajectory-length comparisons, and under the reward condition , Theorems 1–2 show that every optimal child-selection policy yields a shortest path to a solution leaf and that max-Q backtracking over unexplored state–action pairs preserves optimality. Training uses a double DQN over episodes at sampled parameter values, integrated into Ibex (Python training via pipes; a pure C++ inference path online). Experiments use Kuramoto equilibrium systems for (7,000/1,000/1,000 train/val/test instances per ): the learned policy reduces visited nodes by a geometric mean of 7.41× vs. BFS (6.58× vs. DFS; e.g., 241 vs. 1,979 nodes at ) and is up to ~5–10× faster in wall-clock for , though slower for –7. Without backtracking, RL still finds solutions far more often than DFS/random search (85.1% vs. 8.7%/41.1% at ; 17.7% vs. 0%/1.1% at ). A 5-seed sensitivity study supports the reward design.
Critical strengths
-
Theory that guides the design. The condition, Lemma 1, and Theorems 1–2 justify the specific reward scale, guarantee that optimal child-selection with backtracking finds shortest paths, and give the online backtracking rule a principled basis; the implementation respects the condition ( chosen so ). This is more grounding than most RL-for-tree-search papers provide.
-
Real integration with real gains where it matters. Deployment inside a state-of-the-art solver (modified Ibex, with a pure C++ inference path avoiding IPC overhead) yields up to order-of-magnitude wall-clock speedups and ~7× node reductions at , and the paper transparently reports regimes where RL loses (N=6–7) and no-backtracking success rates, rather than only aggregate wins.
Critical weaknesses
-
The evaluation does not support the paper's own generality claims. The abstract states "experiments on several parametric systems," yet Section 4 evaluates exactly one family (Kuramoto), one parameter distribution, and a separate model per . Whether the approach transfers to structurally different systems — different contractors, clustered solutions, other parameter dimensionalities, non-polynomial systems — is precisely the open question, and the fixed offline cost (7,000 training episodes per model) is only amortizable if the policy generalizes across parameter values. This mismatch between claim and evidence materially weakens the contribution.
-
Missing baselines and cost accounting. Only the default DFS/BFS of Ibex are compared. Best-first search with contractor-informed box scoring, and imitation learning from shortest-path labels (directly obtainable from the 7,000 training runs), are obvious stronger baselines that are absent. Offline training cost is never quantified against online savings, so the "worth paying a fixed cost offline" argument — the core economic claim — is not substantiated; and the method is slower than DFS at small without a breakeven analysis.
Questions for authors
- (Assessment) Do the results hold beyond the Kuramoto family? Results on even one or two additional parametric systems would substantially affect my assessment of the abstract's claim of "several parametric systems."
- (Clarification) What is the total offline cost per model (episodes × steps × solver time, plus training), and how many online solves at the reported speedups recoup it? Why train a separate network per rather than conditioning on scale?
- (Assessment) How does the RL policy compare against (a) best-first search with a hand-crafted box score (e.g., contraction-ratio-based) and (b) imitation learning from shortest-path labels on the same training instances?
- (Clarification) Theorems 1–2 assume exact ; with function approximation and finite episodes, how do you verify that the learned ranking reflects proximity-to-solution rather than reward-design artifacts?
- (Clarification) At the no-backtracking success rate is 17.7%, so most runtime presumably comes from backtracked exploration; how much of the reported speedup remains attributable to the learned policy in that regime?
We thank the reviewer for the very insightful and helpful feedback. Next, we address the comments in detail.
Q1.Evaluation on additional parametric systems and compare against contraction-ratio-based heuristic and imitation learning from shortest-path label.
Thank you very much for this suggestion. We fixed an implementation issue (the setting of exploraiton rate), reran our experiments, added two more families of parametric systems (Cavity model and Power-Flow model), and included both the contraction-based heuristic baseline and an imitation learning (a behavior cloning strategy) baseline. Indeed, as shown by Table 1,2,3, they help us evaluate the performance of RL more objectively and comprehensively.
From these tables, we highlight the main observations: we observe that the advantages of RL over three baselines vary with the tested parametric systems. For Kuramoto model, RL significantly outperforms all three baselines. For Cavity model, RL substantially outperforms DFS for all the tested values of N. W.r.t. BFS, on average, RL produces less number of nodes, although taking more running time. W.r.t. Contract, RL has a slight advantage in terms of running time, but produces more nodes. For Power-Flow model, RL significantly outperforms BFS (there is no data for N=11,12 as BFS times out). DFS performs well for this example due to the fact that the first solution appears early in the left part of the search tree. But for larger N, RL has a slight advantage over both DFS and Contract.
Q2. Cost accounting.
We have included a table (Table 1 in the revised paper) reporting the offline cost of RL and a new imitation leanning baseline. Regarding "how many online solves at the reported speedups recoup it?", here we take the Kuramoto model at N=10 for example, according to the data reported in Table 7 in Appendix D, w.r.t. the best heuristic node selection strategy, RL saves about 2.9 seconds per instance during online phase. Given the training cost of RL is 1726 seconds, solving 600 instances online by RL would recoup the training cost. In contrast, BC would take about 17642 examples.
It is a bit challenging to train a uniform network for differnet N as the state dimension is different and the distribution of the solutions (or structure of the search tree) also varies. But we agree that this is a nice suggestion and we plan to investigate this in a future work.
Q3.verify that the learned ranking reflects proximity-to-solution rather than reward-design artifacts?
Our theoretical analysis assumes Q∗ is exact. Under this assumption, we have establised a relation between the value of rewards and the length of solution path and prove that every optimal policy generates a shortest path under the assumption that c−≤0 and the tree T has at least one solution leaf. In practice, we can only get approximate values of Q∗. In this case, we have conducted experiments to measure the impact of awards/penalties on the performance.
Firstly, we have expanded our previous experiments on measuring the impact of penalties on the performance of RL (Table 5 in the revised version). Secondly, we have also added a new table in the appendix (Table 6 in the revised version) to analyze the impact of the success reward (r+), the intermediate search penalty (r∘), and the discount factor (γ) on the performance. From these two tables, we see that the impact of rewards/penalties on the performance of RL is minor.
Q3.How much of the reported speedup remains attributable to the backtracking strategy.
In the following table (Table 12 in our revised pdf), we compare the performances of RL on Kuramoto model when the backtracking strategy is respectively the default learned one based on estimations of Q-values and the random one. From the table, it is clear that a significant portion of speedup and node reduction is attributable to the learned backtracking policy for N=11,12.
Table: The impact of backtracking strategies of RL on Kuramoto model for different N.