# Bandits in Prod: Hyperparameter Optimization at Inference Time

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 56 references that are in the map.
- First posted on arXiv 1 Sep 2026.

## Builds on (most cited first, 30 of 32)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [RouteLLM: Learning to Route LLMs with Preference Data](https://mlsanity.com/paper/2406.18665/) (2024)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Population Based Training of Neural Networks](https://mlsanity.com/paper/1711.09846/) (2017)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [HPOBench: A Collection of Reproducible Multi-Fidelity Benchmark Problems for HPO](https://mlsanity.com/paper/2109.06716/) (2021)
- [Bayesian Optimisation over Multiple Continuous and Categorical Inputs](https://mlsanity.com/paper/1906.08878/) (2019)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Online Hyperparameter Optimization for Class-Incremental Learning](https://mlsanity.com/paper/2301.05032/) (2023)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [BORE: Bayesian Optimization by Density-Ratio Estimation](https://mlsanity.com/paper/2102.09009/) (2021)
- [In-Context Freeze-Thaw Bayesian Optimization for Hyperparameter Optimization](https://mlsanity.com/paper/2404.16795/) (2024)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Bayesian Generational Population-Based Training](https://mlsanity.com/paper/2207.09405/) (2022)
- [BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms](https://mlsanity.com/paper/2505.15141/) (2025)
- [A General Recipe for Likelihood-free Bayesian Optimization](https://mlsanity.com/paper/2206.13035/) (2022)
- [AutoRAG-HP: Automatic Online Hyper-Parameter Tuning for Retrieval-Augmented Generation](https://mlsanity.com/paper/2406.19251/) (2024)
- [Tuning Mixed Input Hyperparameters on the Fly for Efficient Population Based AutoRL](https://mlsanity.com/paper/2106.15883/) (2021)
- [Stochastic simultaneous optimistic optimization](https://mlsanity.com/paper/2604.24537/) (2026)
- [Bandit-Based Random Mutation Hill-Climbing](https://mlsanity.com/paper/1606.06041/) (2016)
- [Tree Ensembles for Contextual Bandits](https://mlsanity.com/paper/2402.06963/) (2024)

## Abstract (arXiv)

Many production systems can assess a configuration only by using it on live requests and observing noisy feedback. Modern agentic systems are a prominent example, with inference-time choices such as model selection, retrieval depth, prompting strategy, and decoding temperature, yet often with no representative validation data. We formalize this setting as Online Hyperparameter Optimization (OHPO) and cast it as an infinitely many-armed bandit over mixed and conditional search spaces. We introduce IMABO, a general framework that combines any bandit policy for choosing among already sampled configurations with any oracle for proposing new ones. We instantiate it with IMOSS, a restart-free anytime policy whose active set grows as tβ, and prove an expected cumulative quantile-regret bound of O(pρ-1/β + T(1+β)/2), where β∈(0,1) controls active-set growth and pρ lower-bounds the probability that a proposed configuration falls in the top-ρ fraction of the search space. We combine IMOSS with three practical oracles: a Tree-structured Parzen Estimator, an incumbent-mutation oracle driven by a per-coordinate bandit, and a pretrained tabular foundation model, all three improving over the uniform random oracle baseline. IMABO outperforms all baselines in terms of regret across diverse OHPO settings, from tuning classical machine-learning models to configuring LLM-based agents. Our implementation is available at https://github.com/Tiime-Software/IMABO.