# When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 8 Apr 2026.

## Builds on (most cited first, 7 of 7)

- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [First Steps Towards a Runtime Analysis When Starting With a Good Solution](https://mlsanity.com/paper/2006.12161/) (2020)
- [To Switch or not to Switch: Predicting the Benefit of Switching between Algorithms based on Trajectory Features](https://mlsanity.com/paper/2302.09075/) (2023)
- [Towards Dynamic Algorithm Selection for Numerical Black-Box Optimization: Investigating BBOB as a Use Case](https://mlsanity.com/paper/2006.06586/) (2020)
- [Lower Bounds from Fitness Levels Made Easy](https://mlsanity.com/paper/2104.03372/) (2021)
- [Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator](https://mlsanity.com/paper/2506.01107/) (2025)

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

- [Reinforcement learning to choose optimizers](https://mlsanity.com/paper/2609.01811/) (2026)

## Abstract (arXiv)

Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups (apart from some artificial examples for hyper-heuristics). Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing. In this paper, we present the first theoretical example in which switching between two algorithms -- the (1+λ) EA and the (1+(λ,λ)) GA -- solves the OneMax problem asymptotically faster than either algorithm used in isolation. We show that an appropriate choice of population sizes for the two algorithms allows the optimum to be reached in O(nloglog n) expected time, faster than the Theta(n√fraclog n logloglog nloglog n) runtime of the best of these two algorithms with optimally tuned parameters. We first establish this bound under an idealized switching rule that changes from the (1+λ) to the (1+(λ,λ)) GA at the optimal time. We then propose a realistic switching strategy that achieves the same performance. Our analysis combines fixed-start and fixed-target perspectives, illustrating how different algorithms dominate at different stages of the optimization process. This approach offers a promising path toward a deeper theoretical understanding of OAS.