Structured Value Function Parameterization for Neural Routing Solvers

Learning heuristics for combinatorial optimization problems through reinforcement learning and deep neural networks has seen a surge of interest in recent years. We revisit the use of value functions in this setting, as many implementations still rely on simple average reward baselines, computed from multiple samples of the same instance. For the class of binary programs with linear objectives, we formulate a Markov decision process, where the policy sequentially assigns the decision variables, and show that its value function decomposes exactly into the cost-weighted sum of the marginal inclusion probabilities of the undecided variables. We utilize this insight as an architectural prior by parameterizing the critic to predict those probabilities rather than a scalar directly. Our experiments show that the structured parameterization improves policy performance and reduces sensitivity to the critic learning rate, achieving state-of-the-art results on the challenging multi-task vehicle routing problem environment, consisting of 16 routing variants. Additionally, we show that the learned value function can be used at inference time to guide a truncated rollout search, which produces favorable results on the pareto front for longer time budgets. Finally, our MDP framework also reveals that some states can be automatically stepped through, when the constraints of the problem imply a single legal action. Such states contribute no policy gradient and, especially during early training, account for a substantial share of all states, leading to considerable efficiency gains.