Online Algorithm Selection

Hans DegrooteIJCAI 2017 · DOI

TL;DR

This paper tackles the problem of selecting the best algorithm for a given task, but with a twist: the selection model can learn and adapt while it's being used. They frame this as a "contextual multi-armed bandit" problem and propose a methodology that outperforms traditional static (offline) approaches by continuously improving its predictions with new data.

What Problem Does This Paper Address?

Many complex computational problems, like those in AI, don't have a single "best" algorithm. Instead, different algorithms excel on different types of inputs (instances). The traditional approach, "offline algorithm selection," involves training a model once on a dataset to predict the best algorithm for future instances. However, this model is static and can't improve if the real-world data it encounters differs from the training data, leading to persistently poor performance. This paper addresses the limitation of static models by proposing "online algorithm selection," where the selection model can be updated and improved as new data becomes available from running algorithms on actual problem instances.

Methods

The core of the paper's methodology is framing online algorithm selection as a contextual multi-armed bandit (CMAB) problem.

  • Contextual Multi-Armed Bandit: Imagine a gambler at a casino with multiple slot machines (arms). In a standard bandit problem, the gambler pulls arms to maximize winnings, learning which machines pay out best over time. In a contextual version, before pulling an arm, the gambler sees some information (the "context") that influences which arm is likely to pay out best. In this paper, "arms" are the algorithms, "pulling an arm" is selecting an algorithm, and the "context" is the set of features describing the problem instance.
  • Online Learning: Unlike offline methods, the CMAB framework allows for continuous learning. Every time an algorithm is selected and its performance is observed, this new data is used to update the selection model.
  • Proposed Solution: The authors propose a general procedure (Algorithm 1) where the selection mapping (the model) is updated based on all available data (training + online). They specifically mention that regression-based models (predicting performance for each algorithm) are good candidates for online strategies because they can easily incorporate new data by updating the models of the selected algorithms.

Datasets

The empirical validation was performed on 18 scenarios from the ASLIB benchmark. This benchmark is a collection of datasets designed for algorithm selection problems. The authors simulated the online setting by splitting each scenario's instances into:

  • 10% for initial model training.
  • 80% for online learning (simulating real-world usage).
  • 10% held out for final evaluation.

Key Insights and Ideas

  • Static Models are a Bottleneck: The paper highlights that offline, static algorithm selection models can lead to permanently poor performance if the initial training data doesn't perfectly capture the problem space.
  • Online Learning is Crucial for Adaptability: By allowing the selection model to learn from new data as it's encountered, online algorithm selection offers a path to sustained performance improvement, especially when training data is expensive or incomplete.
  • CMAB as a Powerful Framework: The formalization of online algorithm selection as a CMAB problem provides a robust theoretical foundation and a clear path for developing and evaluating new strategies.
  • Exploration vs. Exploitation Trade-off: The paper touches upon the classic bandit problem dilemma: should you exploit the algorithm you currently believe is best, or explore other algorithms to potentially discover an even better one? Their experiments suggest that aggressive exploration strategies might not always pay off in this context.

Key Results

  • The greedy online strategy (always picking the currently predicted best algorithm) performed better than the offline baseline (a static regression forest) in 15 out of 18 scenarios.
  • Exploring strategies (e-greedy and a UCB variant) generally performed worse than the greedy strategy and often worse than the offline baseline. This suggests that the cost of exploration (trying potentially suboptimal algorithms) was not sufficiently compensated by later gains in their experiments.
  • Figure 1 shows that all online strategies learned better models over time, as indicated by the increasing "model-quality" as more online instances were handled. However, the exploring strategies did not learn better models than the greedy strategy.

Limitations and Future Work

  • Limitations: The paper acknowledges that the exploring strategies did not yield better results than the greedy strategy, and they plan to investigate why. The empirical study, while extensive, was performed on benchmark data, which might not fully capture the nuances of real-world applications.
  • Future Work: The authors propose investigating the reasons behind the underperformance of exploratory strategies. They also aim to apply their methodology to a concrete, real-world application to gain deeper insights than what benchmark data can provide, especially by leveraging unlimited instance generation.

Summary updated

BibTeX
@inproceedings{degroote2017online,
  author = {Hans Degroote},
  title = {{Online Algorithm Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/746},
}
Figure