Research map / Bandits and online learning / Multi-armed bandits
Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MaxUCB, a max K-armed bandit with a distribution-adapted exploration bonus (alpha log t / n)^2 for two-level CASH, justified by a data analysis showing light-tailed, bounded, left-skewed HPO reward distributions.
Problem
Combined algorithm selection and hyperparameter optimization (CASH) in AutoML, framed as allocating HPO budget across model classes so as to maximize the best observed reward (max K-armed / extreme bandit problem).
Approach
Replaces the UCB mean-plus-sqrt bonus with a max-reward estimate plus a squared-log bonus (alpha log t / n)^2, tailored to bounded, left-skewed, light-tailed reward distributions observed in HPO runs, with regret bounds under a linear-near-max survival function assumption.
Key results
- MaxUCB achieves 186 wins / 4 ties / 10 losses against combined search on TabRepo with sign-test p-value below 0.00001.
- On TabRepoRaw (SMAC), MaxUCB obtains 24 wins vs 6 losses against combined search with p=0.00072, one of only two methods significantly beating combined search there alongside Quantile Bayes UCB.
- Theory gives a regret bound of O(K log T / sqrt(T) * max b_i) under known L and minimum suboptimality gap, with alpha around 0.5 giving a robust trade-off.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use two-level MaxUCB bandit allocation instead of combined search | CASH optimization · TabRepo [RS] | performance versus combined search: 186/$4$/$10$ wins/ties/losses; p-value $\mathbf{\underline{0.00000}}$ | Helped |
| Use two-level MaxUCB bandit allocation instead of combined search | CASH optimization · TabRepoRaw [SMAC] | performance versus combined search: 24/$0$/$6$ wins/ties/losses; p-value $\mathbf{\underline{0.00072}}$ | Helped |
| Use two-level MaxUCB bandit allocation instead of combined search | CASH optimization · YaHPOGym [SMAC] | performance versus combined search: 64/$0$/$39$ wins/ties/losses; p-value $\mathbf{0.00880}$ | Helped |
| Use Rising Bandits instead of MaxUCB | CASH optimization · YaHPOGym [SMAC] | normalized average performance | Helped |
| Use MaxUCB instead of other bandit methods | CASH optimization · AutoML benchmarks | average rank | Helped |
| Increase the exploration parameter α (ablation) | MaxUCB · AutoML tasks, small budgets | performance | Hurt |
| Increase the exploration parameter α (ablation) | MaxUCB · AutoML tasks, sufficient time | final performance | Helped |
Surprising findings
- Rising Bandits outperforms MaxUCB on YAHPO Gym in normalized average performance, attributed to non-stationary optimal arms in that benchmark.
- Classical UCB and extreme bandits such as QoMax-SDA perform worst among bandit methods, and Max-Median wins early but declines with more iterations.
Limitations
- Assumes stationary reward distributions, which may not hold early in HPO runs; a burn-in phase may be needed.
- Performance deteriorates when the sub-optimality gap is near zero or L of the optimal arm is very small; tuned for bounded, skewed distributions.
- Hyperparameter alpha has no adaptive rule and its optimal value depends on unknown problem quantities.
Experimental setup
Datasets: TabRepo TabRepoRaw YAHPO Gym HEBO
Benchmarks: TabRepo TabRepoRaw YAHPO Gym HEBO
Metrics: average rank over time wins/ties/losses sign test p-value regret bound
Baselines: Quantile Bayes UCB ER-UCB-S Rising Bandits QoMax-SDA Max-Median UCB SMAC random search
Builds on: UCB Extreme-Region UCB (ER-UCB) Rising Bandits Quantile Bayes UCB SMAC
Closest papers by meaning
- Efficient Automatic CASH via Rising Bandits (AAAI 2020 · similarity 0.91)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.87)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.86)
- Bandits with Preference Feedback: A Stackelberg Game Perspective (NeurIPS 2024 · similarity 0.85)
- New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem (AAAI 2024 · similarity 0.85)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.