Node Selection for Subdivision with Reinforcement Learning

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.