RLHH achieves optimal runtime on LeadingOnes benchmark with RLS operators

A new paper accepted at PPSN 2026 provides the first rigorous runtime analysis of a Reinforcement Learning Hyper-Heuristic (RLHH) on the classic LeadingOnes benchmark function. The authors – Pietro S. Oliveto, Zhenyu Wang, Peizhou Wu, and Mengqing Xu – prove that with properly tuned parameters, an RLHH equipped with two random local search operators (RLS_1 and RLS_2) achieves the best possible expected runtime up to lower-order terms. This is a significant improvement over a previous result that showed the same HH failed to learn appropriate heuristic selection for a wide range of parameter settings.

The paper also demonstrates experimentally that the RLHH is faster than the Generalized Random Gradient Hyper-Heuristic, which was previously proven to also have optimal expected runtime. By bridging the gap between simplified selection hyper-heuristics and practical machine learning techniques, this work provides a foundation for designing RLHHs with provable performance guarantees. The authors note that while earlier studies used considerably simplified learning mechanisms, this RLHH incorporates a more realistic reinforcement learning component, making the analysis directly relevant to real-world optimization scenarios.