# Machine Learning for Online Algorithm Selection under Censored Feedback

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 60 references that are in the map.
- First posted on arXiv 13 Sep 2021.

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

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [ASlib: A Benchmark Library for Algorithm Selection](https://mlsanity.com/paper/1506.02465/) (2015)
- [Balanced Linear Contextual Bandits](https://mlsanity.com/paper/1812.06227/) (2018)
- [Old Dog Learns New Tricks: Randomized UCB for Bandit Problems](https://mlsanity.com/paper/1910.04928/) (2019)
- [Extreme Algorithm Selection With Dyadic Feature Representation](https://mlsanity.com/paper/2001.10741/) (2020)
- [Algorithm Selection on a Meta Level](https://mlsanity.com/paper/2107.09414/) (2021)
- [Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis](https://mlsanity.com/paper/2007.02816/) (2020)
- [Bayesian Optimization With Censored Response Data](https://mlsanity.com/paper/1310.1947/) (2013)
- [Neural Model-based Optimization with Right-Censored Observations](https://mlsanity.com/paper/2009.13828/) (2020)
- [Towards Meta-Algorithm Selection](https://mlsanity.com/paper/2011.08784/) (2020)
- [Reinforcement Learning Algorithm Selection](https://mlsanity.com/paper/1701.08810/) (2017)
- [Towards White-box Benchmarks for Algorithm Control](https://mlsanity.com/paper/1906.07644/) (2019)

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

- [A Survey of Methods for Automated Algorithm Configuration](https://mlsanity.com/paper/2202.01651/) (2022)
- [A Reinforcement Learning Inspired Latent Yield Based Adaptive Algorithm Switching Mechanism](https://mlsanity.com/paper/2605.24436/) (2026)
- [RASP-QAOA: Resource-Aware Per-Instance Selection for Exact QAOA Simulation](https://mlsanity.com/paper/2608.05646/) (2026)

## Abstract (arXiv)

In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. As the latter is known to exhibit a heavy-tail distribution, an algorithm is normally stopped when exceeding a predefined upper time limit. As a consequence, machine learning methods used to optimize an algorithm selection strategy in a data-driven manner need to deal with right-censored samples, a problem that has received little attention in the literature so far. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. Moreover, we adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon. In an extensive experimental evaluation on an adapted version of the ASlib benchmark, we demonstrate that theoretically well-founded methods based on Thompson sampling perform specifically strong and improve in comparison to existing methods.