Bandits in Prod: Hyperparameter Optimization at Inference Time

• URL: http://arxiv.org/abs/2609.01335v2
• Date: Wed, 02 Sep 2026 13:43:07 GMT
• Title: Bandits in Prod: Hyperparameter Optimization at Inference Time
• Abstract summary: IMOSS is a restart-free anytime policy whose active set grows as $t$.<n>IMABO combines any bandit policy for choosing among already sampled configurations with any oracle for proposing new ones.<n>IMABO outperforms all baselines in terms of regret across diverse OHPO settings.
• Score: 2.575221263525409
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $β\in(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.

Related papers

• ZOMP: Zeroth-Order Multi-Modal Prompt Tuning for Vision-Language Models [14.64726819144383]
  ZOMP is a query-efficient, fully forward-only prompt-tuning method.<n>It consistently outperforms prior BP-free prompt-tuning methods in both few-shot accuracy and query efficiency.<n>Our results show that jointly exploiting multimodality and low-rank structure is an effective route to practical, practical BP-free prompt tuning.
  arXiv  Detail & Related papers  (2026-08-08T10:55:58Z)
• POETS: Uncertainty-Aware LLM Optimization via Compute-Efficient Policy Ensembles [35.88280776565273]
  POETS is a novel framework that bridges uncertainty quantification and policy optimization.<n>Our approach is grounded in the insight that policies trained with Kullback-Leibler (KL) regularization implicitly encode an underlying reward function.<n>We demonstrate POETS achieves state-of-the-art sample efficiency across diverse scientific discovery domains.
  arXiv  Detail & Related papers  (2026-05-08T14:16:32Z)
• Multi-User Contextual Cascading Bandits for Personalized Recommendation [2.506355754272765]
  Multi-User Contextual Cascading Bandit model captures realistic online advertising scenarios where multiple users interact with sequentially displayed items simultaneously.<n>We first propose Upper Confidence Bound with Backward Planning (UCBBP), a UCB-style algorithm tailored to this setting, and prove that it achieves a regret bound of $widetildeO(sqrtTHN)$ over $T$ episodes, $H$ session steps, and $N$ contexts per episode.<n>Motivated by the fact that many users interact with the system simultaneously, we introduce a second algorithm, termed Active Upper Confidence Bound with
  arXiv  Detail & Related papers  (2025-08-19T16:14:33Z)
• Adversarial Bandit over Bandits: Hierarchical Bandits for Online Configuration Management [37.696481970844054]
  This work studies the nonstochastic multi-armed bandit (MAB) problem in metric action spaces with oblivious Lipschitz adversaries.<n>We propose ABoB, a hierarchical Adversarial Bandit over Bandits algorithm that can use state-of-the-art existing "flat" algorithms.
  arXiv  Detail & Related papers  (2025-05-25T09:30:47Z)
• Not All Rollouts are Useful: Down-Sampling Rollouts in LLM Reinforcement Learning [55.15106182268834]
  Reinforcement learning with verifiable rewards (RLVR) has emerged as the leading approach for enhancing reasoning capabilities in large language models.<n>It faces a fundamental compute and memory asymmetry: rollout generation is embarrassingly parallel and memory-light, whereas policy updates are communication-heavy and memory-intensive.<n>We introduce PODS (Policy Optimization with Down-Sampling), which decouples rollout generation from policy updates by training only on a strategically selected subset of rollouts.
  arXiv  Detail & Related papers  (2025-04-18T17:49:55Z)
• RePO: Understanding Preference Learning Through ReLU-Based Optimization [66.098833436503]
  We propose ReLU-based Preference Optimization (RePO), a streamlined algorithm that eliminates $beta$ via two advances.<n>RePO is characterized as SimPO's limiting case ($beta to infty$), where the logistic weighting collapses to binary thresholding.<n> Empirical results on AlpacaEval 2 and Arena-Hard show that RePO outperforms DPO and SimPO across multiple base models.
  arXiv  Detail & Related papers  (2025-03-10T15:11:07Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$ estimates the optimal value function for a target reward $r$ through a baseline model. Our approach significantly reduces the sub-optimality gap observed in prior SoTA methods.
  arXiv  Detail & Related papers  (2024-05-30T21:36:12Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
  In contextual bandits, an agent sequentially makes actions from a time-dependent action set based on past experience. We propose the first online continuous hyperparameter tuning framework for contextual bandits. We show that it could achieve a sublinear regret in theory and performs consistently better than all existing methods on both synthetic and real datasets.
  arXiv  Detail & Related papers  (2023-02-18T23:31:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.