Reproduce “Reinforcement Learning Methods for Neighborhood Selection in Local Search” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Yannick Molinghen, Augustin Delecluse, Renaud De Landtsheer, Stefano Michelini

This research evaluates the practical effectiveness of various reinforcement learning techniques, including Multi-Armed Bandits and Deep Reinforcement Learning, for dynamic neighborhood selection within local search metaheuristics across diverse combinatorial optimization problems. Findings indicate that simpler adaptive methods like ε-greedy are often more robust and computationally efficient than DRL approaches, which demonstrate problem-specific benefits but require significantly longer runtimes.

Key insights

  • No single RL method universally outperforms all others across different problems and time budgets; optimal neighborhood selection strategies are highly problem-specific.
  • Simpler Multi-Armed Bandit methods, particularly ε-greedy, provide a strong balance of adaptivity and low computational overhead, consistently ranking among the best performers.
  • Deep Reinforcement Learning (DRL) methods, despite their potential, incur significant computational overhead and generally require substantially longer runtimes to become competitive or superior, with benefits being problem-dependent (e.g., PPO on CSP).

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.