acceptodds
Under review as a conference paper at ICLR 2027

Node Selection for Subdivision with Reinforcement Learning

Abstract

Subdivision is an important method for finding all the real solutions of nonlinear equations in a given box, through a recursive process of contracting and bisecting. In certain applications like constraint satisfaction, it suffices to find a single solution efficiently. This turns out to be a challenging node selection problem when the underlying subdivision tree is huge. In this paper, we propose to employ reinforcement learning to learn an efficient node selection policy for solving parametric nonlinear equations. Under certain assumptions, we prove that there exists an optimal node selection policy solely based on selecting child nodes. We train a Double Deep Q-Network by exploring the node selection space at many different parameter values offline, and integrate the learned policy into a state-of-the-art subdivision solver. During the online phase, to efficiently find one solution of the system at new values of parameters, we apply the learned policy to select promising child nodes and backtrack when necessary based on maximum Q-value estimates to continue the search. Experiments on several parametric systems show that our method significantly outperforms default heuristic strategies.

Primary area:
reinforcement learning
Keywords:
node selection, reinforcement learning, subdivision, nonlinear system solving, constraint satisfaction

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_sqjzOpenReview ↗
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 f(u,x)=0f(u,x)=0. The formulation is a deterministic MDP: the state is (parameter vector uu, contracted box) and actions are left/right child selection after bisection; the step reward is −0.1-0.1, with terminal rewards +10+10 for a certified solution leaf and −15-15 for a dead or unknown leaf, and γ=0.99\gamma=0.99. Lemma 1 characterizes when Q-value comparisons across trajectories reduce to trajectory-length comparisons, and under the reward condition c−=(r−−r∘)/(1−γ)≤0c_-=(r_- - r_\circ)/(1-\gamma)\le 0, 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 N=6,…,12N=6,\ldots,12 (7,000/1,000/1,000 train/val/test instances per NN): 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 N=12N=12) and is up to ~5–10× faster in wall-clock for N≥8N\ge 8, though slower for N=6N=6–7. Without backtracking, RL still finds solutions far more often than DFS/random search (85.1% vs. 8.7%/41.1% at N=6N=6; 17.7% vs. 0%/1.1% at N=12N=12). A 5-seed sensitivity study supports the reward design.

Critical strengths
  1. Theory that guides the design. The c−≤0c_-\le 0 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 (r−=−15r_-=-15 chosen so c−<0c_-<0). This is more grounding than most RL-for-tree-search papers provide.

  2. 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 N≥10N\ge 10, and the paper transparently reports regimes where RL loses (N=6–7) and no-backtracking success rates, rather than only aggregate wins.

Critical weaknesses
  1. 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 NN. 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.

  2. 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 NN without a breakeven analysis.

Questions for authors
  1. (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."
  2. (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 NN rather than conditioning on scale?
  3. (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?
  4. (Clarification) Theorems 1–2 assume exact Q∗Q^*; with function approximation and finite episodes, how do you verify that the learned ranking reflects proximity-to-solution rather than reward-design artifacts?
  5. (Clarification) At N=12N=12 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?
1 comment

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∗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−≤0c^-\leq 0 and the tree TT has at least one solution leaf. In practice, we can only get approximate values of Q∗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+r^+), the intermediate search penalty (r∘r^\circ), and the discount factor (γ\gamma) 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,12N=11,12.

Table: The impact of backtracking strategies of RL on Kuramoto model for different N.

METHODMETRIC6789101112
Randomtime (s)0.030.060.120.190.360.811.41
Random|tree|13.7118.2427.5032.8045.4775.8899.71
Randomnodes7.7110.3916.1119.0527.0947.7763.27
Random𝔇5.77.19.010.511.913.315.3
Learnedtime (s)0.040.070.120.200.350.640.87
Learned|tree|13.0216.0521.2125.3830.4137.7344.35
Learnednodes7.288.9911.8714.1717.1222.6825.88
Learned𝔇5.87.29.110.912.414.015.9
Reviewer_qeJyOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper uses reinforcement learning to improve node selection in subdivision-based root finding. A Double DQN policy chooses between child boxes and guides backtracking, while Ibex handles interval contraction and root certification. The authors show that, under suitable reward conditions and exact optimal Q-values, the policy follows a shortest path to a certified solution. Experiments evaluate the method on Kuramoto systems of several sizes.

Critical strengths
  1. An interesting application of RL to certified root finding. Learning the search order while leaving numerical operations and certification to an established solver is a sensible design. It offers a useful way to improve efficiency without asking the network to produce or certify solutions directly.
  2. The experiments show useful improvements over the tested baselines. The learned policy reduces visited nodes across the tested sizes and achieves clear runtime improvements on the harder instances. The results without backtracking also show that it selects promising branches more often than random search.
Critical weaknesses
  1. RL-based node selection has already been studied in branch-and-bound, including Reinforcement Learning for Node Selection in Branch-and-Bound by Mattick and Mutschler. Learning child selection with backtracking also has prior work. Although certified root finding is a different task, the contribution beyond adapting the state, reward, and solver interface appears incremental. Comparisons with existing learned selectors adapted to the same environment would help establish the value of the proposed design. The main solver comparisons are limited to DFS and BFS. An additional optimization-based baseline, such as multistart nonlinear least squares followed by interval root certification, would also help assess practical value. Such a comparison should report both total runtime and certified success rate, rather than compare an approximate numerical root with a certified solution.

  2. All experiments use the Kuramoto family, with 10–22 unknowns and a fixed parameter-sampling distribution. Testing different sizes of one family does not establish performance across different nonlinear systems. Additional equation families, larger problems, and tests under changed parameter distributions are needed to support broader claims.

Questions for authors

none

2 comments

We thank the reviewer for the positive recognition of our work and for the constructive comments. Next, we address the comments in detail.

Q1.Comparisons with existing learned selectors

Firstly, we have revised our paper to create a seperate "Related work" section to state the main difference of this work with existing ones. Here, we highlight briefly our main new contibutions: we employ Double Deep Q-Network to select only between two child nodes at each step until reaching a leaf node. If backtracking is needed, we can naturally continue the search based on the available maximum Q-value estimates of unexplored frontier nodes. Indeed, we prove that a shortest path towards a solution can be found in this way if it exists based on the theory of Bellman equation. This theoretical result also establishes a relation between the value of rewards and the length of solution path, for which we are not aware of similar results in existing literatures for node selection.

Secondly, we have included a learned selector based on imitation learning (IL) as a new baseline. The following table compares the performances of RL and IL. In the table, the offline time of IL is the sum of the time for generating the labeled training data and the time for training the neural network. For RL, as no pre-labeled supervision data is needed, the offline time is much shorter than that of IL, about one or two magnitude less for larger N for all three families of systems. The online time is the time of solving an instance by Ibex when replacing its default node selection strategy with respectively the learned one by IL and RL. The online performance of IL is slightly better than RL, which is not a surprise as IL imitates an oracle.

Table: Comparison with imitation learning on three parametric systems for different N.

Kuramoto model with different NN

METHODTIME (s)N=6N=7N=8N=9N=10
ILOffline562+52257+67798+725255+850323+9
ILOnline0.0350.0620.1210.2170.427
RLOffline28647474911351726
RLOnline0.0360.0740.1210.1970.352

Cavity model with different NN

METHODTIME (s)N=4N=5N=6N=7N=8
ILOffline2681+810100+1031938+1061864+14159415+17
ILOnline0.1300.2600.5432.1253.306
RLOffline122167231265470
RLOnline0.2900.6781.8683.4219.316

Power-Flow model with different NN

METHODTIME (s)N=5N=6N=7N=8N=9
ILOffline269+6962+74711+814856+1041971+11
ILOnline0.0100.0180.0450.0760.217
RLOffline117174242340503
RLOnline0.0130.0220.0740.2320.304

As we focus on improving the node selection strategy in subdivision methods, we have decided to add two new baselines, namely the above imitation learning baseline and a contraction-based heuristic search baseline instead of adding the optimization-based baseline.

Q2.Additional equation families

We have added two more families of parametric systems and compared with RL with three heuristic approaches (see Table 2 in the revised version). The parameter distributions used in the two new families of examples are uniform distributions, which are different from the Gaussion distribution used in Kuramoto model. Here, we highlight the main observations obtained from Table 2: 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.

While I appreciate the additional experiments, the methodological novelty beyond existing RL-based node selection remains limited and the runtime benefits are problem-dependent, so I lean toward rejection.

Reviewer_cGriOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces reinforcement learning (RL) into the subdivision process for solving systems of nonlinear equations. It learns a child-node selection policy at each search node to reduce the search tree exploration and improve solving efficiency. Meanwhile, a backtracking mechanism is incorporated, allowing the model to explore other unexplored branches when the current search path fails. From a theoretical perspective, the paper analyzes the optimality of the node selection policy using the Bellman equation and proves that, under certain assumptions and reward conditions, an optimal policy can generate the shortest path from the root node to a solution leaf. Experimental results show that, as the problem size increases, the RL method achieves increasingly significant advantages over traditional DFS and BFS strategies in terms of the number of explored nodes and solving time.

Critical strengths
  1. Well-motivated problem: This paper attempts to introduce reinforcement learning (RL) into the subdivision process for solving systems of nonlinear equations. By learning a node selection policy to guide the search, the proposed approach aims to reduce the search tree exploration and improve solving efficiency.

  2. Theoretical Analysis: The paper analyzes the optimality of the node selection policy using the ellman equation and proves that, under certain assumptions and reward conditions, an optimal policy can generate the shortest path from the root node to a solution leaf, providing theoretical support for the proposed search strategy.

Critical weaknesses
  1. Limited Novelty and Unclear Differentiation from Related Work: The core idea of this paper is to use reinforcement learning(RL) to learn a child-node selection policy, i.e., choosing which of the two generated child nodes should be explored first. However, similar learning-based search strategies have been investigated in previous studies. For example, in the Branch-and-Bound literature, existing works have employed reinforcement learning to select nodes from the set of unexplored nodes, while other studies have used imitation learning to select child nodes of the current node. Furthermore, reinforcement learning has also been explored for interval constraint propagation. Therefore, the paper needs to provide a more comprehensive discussion of related work and clarify the substantive differences between the proposed method and existing learning-based search strategies. In particular, it is currently unclear what methodological or theoretical innovations the proposed Double DQN-based child-node selection strategy brings compared with existing reinforcement learning or imitation learning approaches for node selection.

  2. Limited Benchmark Diversity: The experiments are primarily conducted on the Kuramoto model. Although instances of different scales are generated by varying the number of oscillators, these instances still belong to the same family of parametric nonlinear systems and share relatively similar problem structures. This may limit the representativeness of the experimental results for other types of nonlinear systems and is insufficient to fully demonstrate the generalization capability of the proposed method. It would be beneficial to evaluate the method on additional nonlinear systems with different mathematical structures and characteristics to provide a more comprehensive assessment of its applicability and generalization performance.

  3. The overall presentation of the paper lacks clarity, and the organization and explanation of some parts could be improved. For example, the workflow illustrated in Figure 1(a) is somewhat confusing, making it difficult to intuitively understand the overall methodology. The authors are encouraged to improve the figure to enhance the readability of the paper.

Questions for authors
  1. Regarding the Completeness of Experimental Comparisons: Table 1 compares three methods: DFS, BFS, and RL. However, Table 3, which evaluates the methods without backtracking, only reports the results of DFS, Random Search, and RL, without including BFS. Could the authors explain why BFS is excluded from this experiment? Furthermore, could the authors provide BFS results under the same experimental setting to enable a more comprehensive comparison of different search strategies without backtracking?

  2. Regarding the Action Space Design: The action space in this paper is restricted to the two child nodes of the current Box. In other words, the RL agent only learns which of the two generated child nodes should be explored first, without considering branching variable selection or the choice of subdivision points. Could the authors clarify how the variable selection and bisection rules are determined in the underlying solver, and whether these predefined rules may limit the performance of the proposed search strategy? Furthermore, would incorporating branching variable selection into the RL action space potentially lead to further improvements in search efficiency?

  3. Regarding the Differences from Existing Learning-Based Search Methods: This paper employs Double DQN to select between the two child nodes of the current node. However, previous studies have already explored similar node selection problems using reinforcement learning or imitation learning. Could the authors further clarify the substantive differences between the proposed method and existing learning-based search approaches in terms of state representation, reward design, policy learning, and search mechanisms? In particular, do the theoretical analyses presented in this paper provide any theoretical properties or performance advantages that distinguish the proposed method from previous approaches?

  4. Regarding Reward Function Sensitivity: Appendix B provides a preliminary sensitivity analysis of the failure penalty r−r^-. However, the current analysis mainly investigates the effect of varying this parameter, while the impact of other reward parameters, such as the success reward r+r^+, the intermediate search penalty r∘r^\circ, and the discount factor γ\gamma, on model performance has not been sufficiently investigated. Considering that the reward function affects not only the learning process of the RL policy but also the conditions under which the theoretical guarantees hold, could the authors further analyze how different reward configurations affect search efficiency, training stability, and theoretical properties? Such an analysis would help establish the robustness of the proposed method to reward design.

2 comments

We sincerely thank the reviewer for helpful feedback. We now address the questions in detail.

Q1:Unclear Differentiation from Related Work/Differences from Existing Learning-Based Search Methods

We have added a new "Related work" section to explictly differentiate our work from related studies. The main points are summarized as follows.

  1. Most of exisiting imitation learning (IL) or reinforcement learning (RL) works for node selection in B&B maintain a dynamically growing global list of unexplored nodes. The power of IL methods is largely attributed to employing an oracle, which also limits their applicability on solving large size problems. For existing RL works, their effectiveness are limited by the complex state space and a large dynamic action space. In contrast, compared with MILP, there are no optimum bounds to be utilized for comparison for subdivision methods. Therefore, we employ DDQN to select only between two child nodes at each step aggressively in a ``diving" manner until reaching a leaf node. If backtracking is needed, we can naturally continue the search based on the available maximum Q-value estimates of unexplored frontier nodes. As we focus on solving parametric systems, it suffices to distinguish states by parameter values and box coordinates. For most of the existing approaches, as they need to select the node from a dynamically changing frontier list, more complicated tree/graph representation are needed.

  2. Yilmaz & Yorke-Smith (2021) employed imitation learning to iteratively make a binary choice between two child nodes for solving MILP problems. Their backtracking strategy, however, primarily resorts to the underlying MILP solver. In contrast, for both child node selection and backtracking, we rely on the learned estimates of Q-values. Neveu et al. (2016) proposed FeasibleDiving for interval Branch and Bound algorithms. Motivated by this approach, we design a contraction-ratio-based heuristic node selection strategy to serve as a baseline in our experiments.

  3. Beyond node selection. Besides node selection, both imitation learning and reinforcement learning have been employed for learning to branch/cut in solving MILP problems. For interval constraint propagation, Goualard & Jermann (2008) proposed to dynamically learn the best contracting operator by reinforcement learning. In this work, we adopt the subdivision solver's default branching and contracting strategies and focus on designing the optimal node selection strategy.

Q2.Limited Benchmark Diversity:

We have added two more families of parametric systems and compared RL with three heuristic approaches (see Table 2 in the revised version). We observe that the advantages of RL over three baselines vary with the tested parametric systems. Overall, RL significantly outperforms all heuristic baselines on the first model, and has a slight advantage over the heuristics on the other two systems for larger N.

Q3.Overall presentation lacks clarity and Figure 1(a)confusing

We have created a new "Related work" section to better organize the paper. We have simplified Figure 1(a) to highlight the key points. We have also improved the analysis of experimental results.

Q4. Completeness of experimental comparisons

We admit that the tile of Table 3 was a bit misleading. We have modified it as Comparison of four “diving” strategies without backtracking on Kuramoto model to emphasize that this table is meant for comparing the three (now four) strategies which aggressively select only between two child nodes until reaching a leaf node. For this reason, it is not suitable to compare with BFS in this table.

Q5.Action Space Design

Regarding the action space, we adopt the subdivision solver's built-in branching strategies and contracting strategies and only make a binary choice between the left and right child. In our experiments, the branching strategy is simply chosen to be Round Robin for all three examples. While jointly learning three strategies could yield additional speedups, the child-node selection problem holds independent theoretical and practical interest. Therefore, we isolate it in this work and leave the joint optimization of these two strategies and child selection for future work.

Q7.Reward Function Sensitivity

We have added a new table in the appendix (Table 5 in the revision) to analyze the impact of the success reward (r+r^+), the intermediate search penalty (r∘r^\circ), and the discount factor (γ\gamma) on the performance. From the table, we see that the impact of these parameters on the performance is minor and the default values we adapted in this paper is reasonable. Note that the theoretial result is only related to the sign of c−c^-, whose value depends on the parameters r−r^-, r∘r^\circ, and the discount factor γ\gamma.

I appreciate the authors' efforts in responding to the review comments and providing additional experimental results. These revisions have addressed some of my previous concerns. However, the novelty of this work remains limited compared with existing RL-based node selection methods. Furthermore, the revised paper moves the original main experimental results to other tables and the appendix, while the new Table 1 mainly focuses on the comparison of offline and online time with imitation learning, without reporting other metrics such as the number of visited nodes. The overall organization and presentation of the paper could still be improved. Therefore, I still lean toward rejection.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.