- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3(+1)
Read review
Paper summary
The paper investigates whether learned move-selection policies genuinely outperform random selection when both are integrated into local-search algorithms with descent. It introduces commit depth (cd), which controls the number of descent steps performed after each selected move, and systematically evaluates how descent affects the relative performance of learned and random selectors. The main contribution is demonstrating that descent substantially reduces the apparent advantage of learned move selection. In a controlled job-shop scheduling experiment, the learned selector’s advantage over random selection shrinks as descent depth increases and reverses when descent continues to a local optimum. The authors extend this analysis to six published learned local-search methods across several combinatorial optimisation problems, finding that the advantage of five methods shrinks substantially or disappears. They also identify a candidate-budget confound in MIStar: its apparent advantage largely disappears when random selection evaluates the same number of candidates. Finally, the authors investigate fine-tuning policies with descent included in the training loop. Fine-tuning improves performance over random-plus-descent baselines for ECO-DQN and NeuOpt, but not consistently for DACT, MIStar, or L2S. Validation includes controlled experiments, statistical analyses, robustness checks across instances and search budgets, comparisons at equal wall-clock time, and evaluations of published methods. Overall, the paper provides empirical evidence that learned local-search methods should be evaluated against computationally matched random baselines within the complete search pipeline, rather than in isolation.
Critical strengths
- Identifies a genuinely important evaluation problem: a learned move selector should not be evaluated independently of the descent mechanism surrounding it.
- The controlled JSSP experiment is quite convincing. The authors hold the search framework fixed and systematically change only the commit depth.
Critical weaknesses
- The central causal explanation is demonstrated most strongly on JSSP. It does not establish equally clearly that the same “conservative move” mechanism causes the shrinkage in other domains like DACT, NeuOpt
- Fine-tuning evidence is relatively small - at most 8.7 hours of GPU per run; 2 seeds per method are far from convincing.
Questions for authors
- Can the authors provide evidence that the same mechanism explains the performance collapse for DACT, NeuOpt, ECO-DQN, L2S, MIStar, and SAT?
- How sensitive are the conclusions to the choice of neighbourhood and descent operator? Could a learned policy retain a substantial advantage if descent uses a different neighbourhood, randomised descent or a cheaper local improvement model?