Machine Learning for Online Algorithm Selection under Censored Feedback
A. Tornede, V. Bengs, E. Hüllermeier, Proceedings of the 36th AAAI Conference on Artificial Intelligence (2022).
Download
No fulltext has been uploaded.
Preprint
| English
Department
Project
Abstract
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.
Publishing Year
Journal Title
Proceedings of the 36th AAAI Conference on Artificial Intelligence
LibreCat-ID
Cite this
Tornede A, Bengs V, Hüllermeier E. Machine Learning for Online Algorithm Selection under Censored Feedback. Proceedings of the 36th AAAI Conference on Artificial Intelligence. Published online 2022.
Tornede, A., Bengs, V., & Hüllermeier, E. (2022). Machine Learning for Online Algorithm Selection under Censored Feedback. In Proceedings of the 36th AAAI Conference on Artificial Intelligence. AAAI.
@article{Tornede_Bengs_Hüllermeier_2022, title={Machine Learning for Online Algorithm Selection under Censored Feedback}, journal={Proceedings of the 36th AAAI Conference on Artificial Intelligence}, publisher={AAAI}, author={Tornede, Alexander and Bengs, Viktor and Hüllermeier, Eyke}, year={2022} }
Tornede, Alexander, Viktor Bengs, and Eyke Hüllermeier. “Machine Learning for Online Algorithm Selection under Censored Feedback.” Proceedings of the 36th AAAI Conference on Artificial Intelligence. AAAI, 2022.
A. Tornede, V. Bengs, and E. Hüllermeier, “Machine Learning for Online Algorithm Selection under Censored Feedback,” Proceedings of the 36th AAAI Conference on Artificial Intelligence. AAAI, 2022.
Tornede, Alexander, et al. “Machine Learning for Online Algorithm Selection under Censored Feedback.” Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI, 2022.