# Bandit-Based Random Mutation Hill-Climbing

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2016.

## Built on by (most cited first, 4 of 4)

- [Evolutionary Multi-Armed Bandits with Genetic Thompson Sampling](https://mlsanity.com/paper/2205.10113/) (2022)
- [Genetic multi-armed bandits: a reinforcement learning approach for discrete optimization via simulation](https://mlsanity.com/paper/2302.07695/) (2023)
- [Benchmarking Randomized Optimization Algorithms on Binary, Permutation, and Combinatorial Problem Landscapes](https://mlsanity.com/paper/2501.17170/) (2025)
- [Bandits in Prod: Hyperparameter Optimization at Inference Time](https://mlsanity.com/paper/2609.01335/) (2026)

## Abstract (arXiv)

The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it is better than or equal to it. In this work, we propose to use a novel method to select the neighbour solution using a set of independent multi- armed bandit-style selection units which results in a bandit-based Random Mutation Hill-Climbing algorithm. The new algorithm significantly outperforms Random Mutation Hill-Climbing in both OneMax (in noise-free and noisy cases) and Royal Road problems (in the noise-free case). The algorithm shows particular promise for discrete optimisation problems where each fitness evaluation is expensive.