Rectified Policy Rollouts with Hierarchical Expert Guidance for Neural Combinatorial Optimization

In the field of Neural Combinatorial Optimization (NCO), Reinforcement Learning (RL) stands out for its ability to naturally enforce complex constraints via its auto-regressive decision pattern. To mitigate the longstanding challenges, e.g., reward sparsity and sample inefficiency in the vast combinatorial action space which causes ineffective training, subpar performance, and poor scalability, we propose CORectifier, a novel NCO solver learned under the hierarchical gated rectification mechanism to regularize the arbitrary exploration: partial policy-predicted actions in a trajectory are probabilistically replaced with high-quality segments from reference solutions. CORectifier prompts the model with tri-level optimal signals, operating at the batch, instance, and sub-instance levels with fragments of diverse lengths injected at random decision steps. This Rectified RL (RRL) paradigm helps develop optimality-aware and sample-efficient RL learners while maintaining their sequential-decision manner for constraint satisfaction, delivering a new perspective to hybridize RL and SL/IL for NCO with improved utility rate of limited supervision. Sufficiently extensive experiments on Traveling Salesman Problem (TSP), Asymmetric TSP (ATSP), Prize-Collecting TSP (PCTSP), Capacitated Vehicle Routing Problem (CVRP), Knapsack Problem (KP), Job-Shop Scheduling Problem (JSSP), and Single Machine Total Weighted Tardiness Problem (SMTWTP), across synthetic and real-world benchmarks, show superior quality than RL baselines by up to 59.7%.