mlsanityData to 14 Oct 2026

On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics

arXiv 2607.22036 ↗First posted 24 Jul 2026cs.NEcited by 0

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

Selection Hyper-heuristics (HHs) automate algorithmic design by selecting from a set of low-level heuristics which one to apply at each stage of the optimisation process. Several impressive results have been recently rigorously proven regarding the performance of selection hyper-heuristics (HHs) for standard benchmark functions. However, the learning mechanisms employed by these HHs are considerably simplified compared to the machine learning techniques typically used in real world applications. In this paper we analyse a Reinforcement Learning Hyper-heuristic (RLHH) from the literature. The only previous result available proved that for a wide range of parameter settings, RLHH does not learn to select heuristics appropriately for the standard LeadingOnes benchmark function. In this paper, we rigorously prove that with appropriate parameter values RLHH equipped with two random local search operators, RLS_1 and RLS_2 optimises the LeadingOnes benchmark function in the best possible expected runtime achievable with the two operators up to lower order terms. Experiments show that for realistic problem sizes it is faster than the Generalised Random Gradient HH which was previously proven to also have optimal expected runtime up to lower order terms.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 6 of its 51 references that are in the map. First posted on arXiv 24 Jul 2026.

Builds on

6 of 51 references.

References · 6

  1. 2018Better Runtime Guarantees Via Stochastic Dominationcited by 13
  2. 2018Significance-based Estimation-of-Distribution Algorithmscited by 6
  3. 2023How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffscited by 5
  4. 2024Hyper-Heuristics Can Profit From Global Variation Operatorscited by 3
  5. 2025Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operatorcited by 3
  6. 2026Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problemscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024ARLBench: Flexible and Efficient Benchmarking for Hyperparameter Optimization in Reinforcement Learning
  2. 2025Hyperparameter Optimisation with Practical Interpretability and Explanation Methods in Probabilistic Curriculum Learning
  3. 2024Combining Automated Optimisation of Hyperparameters and Reward Shape
  4. 2024Learning Rate-Free Reinforcement Learning: A Case for Model Selection with Non-Stationary Objectives
  5. 2025Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming
  6. 2020Hyperparameter Selection for Offline Reinforcement Learning
  7. 2024Hyper: Hyperparameter Robust Efficient Exploration in Reinforcement Learning
  8. 2025Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search