On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics

• URL: http://arxiv.org/abs/2607.22036v1
• Date: Fri, 24 Jul 2026 07:02:45 GMT
• Title: On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics
• Abstract summary: We show that Reinforcement Learning Hyper-heuristic (RLHH) learns to selects appropriately for the standard LeadingOnes benchmark function.<n>Experiments show that for realistic problem sizes it is faster than the Generalised Random Gradient HH.
• Score: 8.96868555005386
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems [21.869601901930668]
  We show how to automatically set a new parameter value, relieving the user from the non-trivial task of controlling this novel algorithm parameter.<n>We prove that the resulting hyper-heuristic selects the optimal neighbourhood size in a $1-o(1)$ fraction of the iterations.
  arXiv  Detail & Related papers  (2026-05-28T13:31:16Z)
• Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization [71.33048115652474]
  Bilevel optimization (SBO) has been integrated into many machine learning paradigms recently.<n>In this paper, we provide a systematic analysis of bilevel optimization methods.<n>Results do not require re-reading and are applicable to more general objective functions.
  arXiv  Detail & Related papers  (2026-04-05T12:12:58Z)
• Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization [45.99743804547533]
  Two-way partial AUCAUC is a critical performance metric for binary classification with imbalanced data.<n>Existing algorithms for TPAUC optimization remain under-explored.<n>We introduce two innovative double-coordinate block-coordinate algorithms for TPAUC optimization.
  arXiv  Detail & Related papers  (2025-05-28T03:55:05Z)
• Efficient Differentiable Approximation of Generalized Low-rank Regularization [64.73416824444328]
  Low-rank regularization (LRR) has been widely applied in various machine learning tasks.<n>In this paper, we propose an efficient differentiable approximation of LRR.
  arXiv  Detail & Related papers  (2025-05-21T11:49:17Z)
• Combining Automated Optimisation of Hyperparameters and Reward Shape [7.407166175374958]
  We propose a methodology for the combined optimisation of hyperparameters and the reward function. We conducted extensive experiments using Proximal Policy optimisation and Soft Actor-Critic. Our results show that combined optimisation significantly improves over baseline performance in half of the environments and achieves competitive performance in the others.
  arXiv  Detail & Related papers  (2024-06-26T12:23:54Z)
• Hyperparameters in Continual Learning: A Reality Check [50.784080714897776]
  Continual learning (CL) aims to train a model on a sequence of tasks while balancing the trade-off between plasticity (learning new tasks) and stability (retaining prior knowledge)
  arXiv  Detail & Related papers  (2024-03-14T03:13:01Z)
• Deep Ranking Ensembles for Hyperparameter Optimization [9.453554184019108]
  We present a novel method that meta-learns neural network surrogates optimized for ranking the configurations' performances while modeling their uncertainty via ensembling. In a large-scale experimental protocol comprising 12 baselines, 16 HPO search spaces and 86 datasets/tasks, we demonstrate that our method achieves new state-of-the-art results in HPO.
  arXiv  Detail & Related papers  (2023-03-27T13:52:40Z)
• Towards Learning Universal Hyperparameter Optimizers with Transformers [57.35920571605559]
  We introduce the OptFormer, the first text-based Transformer HPO framework that provides a universal end-to-end interface for jointly learning policy and function prediction. Our experiments demonstrate that the OptFormer can imitate at least 7 different HPO algorithms, which can be further improved via its function uncertainty estimates.
  arXiv  Detail & Related papers  (2022-05-26T12:51:32Z)
• Min-Max Bilevel Multi-objective Optimization with Applications in Machine Learning [30.25074797092709]
  This paper is the first to propose a min-max bilevel multi-objective optimization framework. It highlights applications in representation learning and hyper-objective learning.
  arXiv  Detail & Related papers  (2022-03-03T18:56:13Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  Preconditioning is a highly effective step for any iterative method involving matrix-vector multiplication. We prove that preconditioning has an additional benefit that has been previously unexplored. It simultaneously can reduce variance at essentially negligible cost.
  arXiv  Detail & Related papers  (2021-07-01T06:43:11Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)
• Weighted Random Search for Hyperparameter Optimization [0.0]
  We introduce an improved version of Random Search (RS), used here for hyper parameter optimization of machine learning algorithms. We generate new values for each hyper parameter with a probability of change, unlike the standard RS. Within the same computational budget, our method yields better results than the standard RS.
  arXiv  Detail & Related papers  (2020-04-03T15:41:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.