Bandits in Prod: Hyperparameter Optimization at Inference Time
Louis Abraham, Tuan-Anh Nguyen, Nicolas Devatine
cs.LG · cs.AI
Quick verdict
Casts online HPO as infinite-armed bandit with oracle arms; solid anytime regret theory, but 'beats all baselines' outruns its own HotpotQA results.
Summary
The paper formalizes Online Hyperparameter Optimization (OHPO): tuning inference-time settings (model, prompt, retrieval depth, temperature) of production systems by serving configurations on live traffic and observing noisy rewards, with no validation set. It casts OHPO as an infinitely many-armed bandit and proposes IMABO, a framework combining any bandit policy over a growing active set with any oracle proposing new arms. Its policy, IMOSS, is a restart-free anytime adaptation of MOSS whose active set grows as t^β; the authors prove an expected cumulative quantile-regret bound O(p_ρ^{-1/β}+T^{(1+β)/2}) (Appendix A). Three oracles are instantiated — a Tree-structured Parzen Estimator, incumbent mutation driven by a per-coordinate KL-UCB bandit, and TabPFN-3 scoring candidate pools. Experiments cover four 4-D toy functions (20 seeds) against StoSOO, HOO-T, StroquOOL and Hier-MAB-11; HPOBench tasks; a HotpotQA RAG pipeline (5 seeds, 5000 online questions); and a delayed/censored-feedback extension on LCBench/YAHPO-Gym where a delay-aware throttling rule recovers most of the gap to the no-delay skyline under ~81% feedback loss. An oracle ablation (Appendix C) shows local mutation proposals usually suffice and TabPFN helps only when good configurations require joint coordinate settings (higgs). Main limitation: the abstract's claim that IMABO outperforms all baselines is not fully supported — on HotpotQA, IMOSS-TPE trails Hier-MAB on both online and simple regret.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Online hyperparameter optimization — serving configurations on live requests with only noisy reward feedback — is exactly an infinitely many-armed bandit in which any bandit policy over a growing active set can be paired with any arm-proposing oracle (IMABO, Algorithm 1).
- IMOSS, a restart-free anytime adaptation of MOSS whose active set grows as Θ(t^β), achieves expected cumulative quantile regret O(p_ρ^{-1/β} + T^{(1+β)/2}) (Lemma 1 + Theorem 1, Appendix A).
- All three learned proposal oracles — TPE, best-arm mutation with per-coordinate KL-UCB, and TabPFN-3 — improve on the uniform random oracle.
- A delay-aware admission rule based on the effective reward count Ñt recovers most of the no-delay skyline performance under ~81% feedback loss on LCBench surrogates (Figs. 7–8).
- The abstract claims IMABO outperforms all baselines in regret across diverse OHPO settings, which the HotpotQA results (Fig. 6) only partially support.
Strengths
Clean problem formalization filling a real gap
Section 3 defines OHPO with quantile regret against a P0-induced top-ρ threshold — the right target when the global optimum of a continuous/mixed space is provably unreachable within any realistic request stream, and every evaluation costs a served request.
Genuine theoretical contribution
Lemma 1 extends the MOSS allocation bound to a growing active set via a regular-growth sandwich (t/Kt ≤ λ·T/K), and the Appendix A proof decomposes regret into discovery (O(p_ρ^{-1/β}) via a Gamma-integral under conditional coverage), expansion (O(T^β)) and exploitation (O(T^{(1+β)/2})). The combination restart-free + anytime + cumulative quantile regret is new relative to QRM1/QRM2's doubling restarts and UCB-AIR's fixed reservoir.
Unusually honest oracle engineering and ablation
Deployment-realistic extension with mechanism evidence
Broad evaluation and public code
Weaknesses
Abstract overclaims against its own headline LLM experiment
Statistical reporting below the bar for the claims made
Theory–practice gap around the bound's constants
Fragile, proxy-based LLM experiment
Synthetic delay model
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets Online Hyperparameter Optimization (OHPO, §3): a production system commits a full configuration (model, prompt, retrieval depth, temperature) before each request and learns only from the noisy reward it earns, with no validation set and an unknown horizon. Since the global optimum of a continuous/mixed space is unreachable, performance is measured by cumulative ρ-regret against the top-ρ quantile of mean reward under a baseline sampler P0. Four claims are made: (1) OHPO is exactly an infinitely many-armed bandit in which an oracle replaces the fixed reservoir (IMABO, §4, Algorithm 1); (2) the IMOSS policy — an anytime-MOSS index (Eq. 1) over an active set growing as Θ(t^β), restart-free — achieves expected cumulative quantile regret O(p_ρ^{-1/β} + T^{(1+β)/2}) (Appendix A); (3) three learned proposal oracles — TPE (§4.1.3), best-arm mutation driven by a per-coordinate KL-UCB bandit with 1-D Parzen proposals (§4.1.4), and TabPFN-3 scoring a 100-candidate pool by the q=0.975 predictive quantile (§4.1.5) — all beat uniform sampling; (4) IMABO 'outperforms all baselines in terms of regret across diverse OHPO settings' (Abstract).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is online hyperparameter optimization (OHPO)?
Tuning a system's inference-time settings (model, temperature, prompt, retrieval depth) by serving configurations on real traffic and learning only from the observed rewards, with no offline validation set. This paper formalizes it as a bandit problem where each served request is one arm pull.
What are IMABO and IMOSS?
IMABO is the paper's framework pairing any bandit policy over the configurations tried so far with any oracle that proposes new configurations. IMOSS is its anytime MOSS-based policy whose active set grows as t^β and which carries a proven quantile-regret bound O(p_ρ^{-1/β} + T^{(1+β)/2}).
Does the method beat existing baselines?
Partially. On toy and tabular benchmarks the IMABO variants lead on cumulative regret, and on the HotpotQA RAG experiment the mutation and TabPFN oracles beat Random and Hier-MAB online. However, the TPE variant trails Hier-MAB on both metrics there, so the abstract's 'outperforms all baselines' is stronger than the reported results.
Is code available for this paper?
Yes. The authors state the implementation is public at github.com/Tiime-Software/IMABO, and the benchmarks used (toy functions, HPOBench, YAHPO-Gym/LCBench, HotpotQA via BEIR) are public.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt: parts of §4.1.2–4.1.3 (expansion rule, TPE oracle), §5.3, §5.4, the middle of the Appendix A proof, and Appendix C.2–C.3 (including Table 3's column header) fall inside '[...sampling gap...]' blocks; judgments about those parts rely on the surrounding visible text only.
- Figure panels are known via captions and the surrounding narrative; plotted values could not be independently read from the text.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.