Bandits in Prod: Hyperparameter Optimization at Inference Time

TL;DR - This paper formulates inference-time configuration tuning on live, noisy requests as Online Hyperparameter Optimization and introduces IMABO, an infinitely many-armed bandit framework. It enables production systems, including LLM agents, to optimize choices without representative validation data.

• IMABO separates selecting previously sampled configurations via a bandit policy from proposing new configurations via an interchangeable oracle.
• Its IMOSS policy grows the active configuration set as (t^\beta) and provides an expected cumulative quantile-regret bound of (O(p_\rho^{-1/\beta} + T^{(1+\beta)/2})).
• Tree-structured Parzen Estimation, incumbent mutation, and a pretrained tabular foundation model all improve over uniform-random configuration proposals.
• IMABO achieves the lowest cumulative regret across the evaluated settings, spanning classical ML tuning and LLM-agent configuration.