# Reinforcement Learning Methods for Neighborhood Selection in Local Search

arXiv: https://arxiv.org/abs/2601.07948 · HTML: https://mlsanity.com/paper/2601.07948/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 12 Jan 2026.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 6 of 6)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Online Learning for Scheduling MIP Heuristics](https://mlsanity.com/paper/2304.03755/) (2023)
- [Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming](https://mlsanity.com/paper/2503.16371/) (2025)

## Abstract (arXiv)

Reinforcement learning has recently gained traction as a means to improve combinatorial optimization methods, yet its effectiveness within local search metaheuristics specifically remains comparatively underexamined. In this study, we evaluate a range of reinforcement learning-based neighborhood selection strategies -- multi-armed bandits (upper confidence bound, ε-greedy) and deep reinforcement learning methods (proximal policy optimization, double deep Q-network) -- and compare them against multiple baselines across three different problems: the traveling salesman problem, the pickup and delivery problem with time windows, and the car sequencing problem. We show how search-specific characteristics, particularly large variations in cost due to constraint violation penalties, necessitate carefully designed reward functions to provide stable and informative learning signals. Our extensive experiments reveal that algorithm performance varies substantially across problems, although that ε-greedy consistently ranks among the best performers. In contrast, the computational overhead of deep reinforcement learning approaches only makes them competitive with a substantially longer runtime. These findings highlight both the promise and the practical limitations of deep reinforcement learning in local search.