We study adaptive routing of prompts to large language model (LLM) experts to maximize response quality in an online setting with limited feedback. We formulate it as a bandit problem with K actions that represent experts and d features that encode prompts, over a horizon of T rounds. We propose algorithms that strategically select and observe rewards to minimize regret. In the full-information setting, we achieve a regret of O~(dT/m), while in the bandit setting we achieve O~(dTK/m), where m≪T is a budget on feedback. Our experiments show that we efficiently learn high-quality routing strategies across diverse LLMs from limited feedback.
The Appropriately Combined Edge-length (ACE) sequence in A-BLiN depends on the zooming dimension dz. This note removes that dependence. The next edge length is selected from the number of cubes that survive the preceding elimination. The resulting Count-Adaptive BLiN algorithm does not use dz or the zooming constant Cz, yet it attains Od(T(dz+1)/(dz+2)) regret with Od(loglogT) batches. Together with the adaptive-grid lower bound in Theorem 10 of the original paper, the optimal batch complexity remains Θd(loglogT) when dz is unknown.
We study a variant of the Thompson Sampling (TS) algorithm, called α-TS, for solving stochastic generalized linear bandit problems. Existing analyses of TS require inflating the posterior variance to derive near-optimal regret guarantees. We formalize the idea of variance inflation by introducing α-TS that uses a fractional or α-posterior instead of the standard posterior. Our main contribution is to identify general regularity conditions on the prior and reward distributions that enable a regret analysis of α-TS without assuming any tractable approximation of the posterior distribution, unlike previous works. For a specific choice of α∝d−1, our general regret bound yields the best known regret bound of O(d3/2TlogT) for both the exponential and sub-Gaussian families of reward distributions. We further provide an α-dependent lower bound showing that the regret constant depends on the product αd, and that when α∝d−1 the regret scales as Ω(d3/2T), explaining the origin of the d3/2 factor in the upper bound. Our proof technique adapts and combines recent advancements in the analysis of linear bandit problems with first- and second-order posterior concentration theory from the Bayesian statistics literature.
Daniels School of Business, Purdue University. · Department of Statistics, University of Wisconsin-Madison. · Department of Statistics, Texas A&M University.
A system often has to act long before it learns whether the act worked: a recommender sees a click in seconds and a purchase in days. With K actions and a delay of d rounds, the best rate known for this setting is O((K+d)T) over T rounds, so a longer menu is always more expensive to learn from. It need not be: if the outcome depends on the action only through the state it produced, then one late outcome informs every action that could have produced the observed state, and the price is set by how many genuinely different states the actions produce rather than by how many actions there are. We measure this using an effective dimension vt between 1 and the number of states, and prove O((d+1)VlogK) for a rotating algorithm and O(V−+dT) for the single-copy algorithm used in practice, for any budget fixed in advance; merging similar states lowers the price further, at an explicit bias. Even when given the exact losses from d rounds ago, no algorithm escapes Ω(dEmin{1+logJ,T/d}), where J counts the drifting directions and E bounds how far losses move while the learner waits. On generated data, the state channel cuts regret by up to 79 percent against action-level weighting and, on the funnel family, by 32 to 68 percent against a tuned minimax-optimal method.
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.
Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight O~(dT) regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.
Spyros Dragazis, Aldo Pacchiano
Boston University · Broad Institute of MIT and Harvard
Whittle index policies offer a scalable method for restless multi-armed bandits, but under partial observability even determining the indifference subsidy at a single belief requires solving an infinite-horizon belief-state problem with no closed-form value function. Liu [10] addresses this difficulty by linearizing the unknown decision boundary, leading to a linear system and a closed-form approximate Whittle index. However, the resulting threshold uses only a one-step active--passive comparison and does not account for longer-horizon continuation values. We extend this framework to a \emph{t-step lookahead threshold policy}. For each subsidy m, the threshold is defined by the active-minus-passive advantage under t-step finite-horizon value iteration. At t=1, the threshold is m-independent and recovers the linear threshold of Liu [10]; for t>1, it becomes subsidy-dependent through the induced first-crossing structure and tracks the exact decision boundary more closely. The proposed algorithmic framework does not require indexability as an input and includes an indexability verification. Under the original Whittle indexability, we prove that the t-step approximate Whittle index converges geometrically to the exact Whittle index,
∣Wt(ω)−W(ω)∣=O(βt).
Numerically, all 2,715 tested three-state instances are verified with computable priority index functions according to the proposed criterion. The P95 index error decreases from 2.18×10−2 at t=1 to 8.93×10−4 at t=8. In an exact-comparable instance with β=0.9999, t=2 already recovers the exact Whittle-index ordering. Moderate-depth threshold policies also outperform the one-step baseline and remain close to the optimal dynamic-programming benchmark, while runtime grows mildly with t.
Cooperative teams often need to agree on the best few options rather than simply accumulate reward, and they must do so while each member sees only a fragment of the team's collective experience. We study this as top-K joint-arm identification in multi-agent multi-armed bandits: at every round M agents simultaneously choose individual actions that compose a joint arm, and the team must ultimately return the K joint arms of highest mean reward. The difficulty is that an agent may not observe the actions of others, their rewards, or either. We treat three observability regimes---(A) shared rewards with hidden actions, (B) observed actions with private rewards, and (C) full asymmetry---and design communication-free elimination algorithms (UCB-Intervals) that reconstruct implicit coordination from whatever signal each regime leaves intact: a shared arm ordering in (A), observable deviations in (B), and enlarged confidence radii under (C). We give matching analyses in both the fixed-budget and fixed-confidence objectives, then fold all three regimes into a single meta-guarantee indexed by a multiplicity c and a consensus factor ρ. Our central result is quantitative rather than merely algorithmic: change-of-measure lower bounds show that shared-reward identification is optimal up to one universal logarithmic factor, and that the entire statistical price of removing communication is a multiplicative ρ2 in sample complexity---a fixed 4× penalty under full asymmetry. The resulting stopping time scales as O(∑aΔa2log(AM/δ)) and the fixed-budget error as exp(−Θ(T/H1)), with the dependence on the joint-action count AM shown to be unavoidable.
Larissa Xu, Jasmine Nguyen, William Chang
Department of Applied Mathematics, University of California, Los Angeles, USA
We introduce Gated Decoupled Compositional Bandits (GDCB), a family of contextual bandit algorithms with three structural innovations that jointly fall outside the taxonomy of LinUCB, LinTS, HierTS, factored bandits, neural contextual bandits, and RLHF. In a GDCB system: (i) the action delivered to the environment is the composition of a nominal arm, drawn by a discrete or hierarchical bandit, with a context-dependent scaler; (ii) the scaler parameter is learned in a separate supervised loop, not jointly with arm selection; and (iii) every action passes through a pre-execution gate that may modify or veto the composed action before it reaches the environment. We formalise this class of algorithms, prove four structural theorems characterising its statistical behaviour, and show that six industrially significant systems -- short-term rental dynamic pricing, clinical drug dosing, credit origination, grid demand response, content moderation, and LLM tool-use agents -- are all instances of GDCB, differing only in the composition operator, scaler family, and gate. The central result is the Decoupling Variance Reduction theorem: a well-calibrated scaler removes context-induced variance from the arm-to-reward mapping, turning a non-stationary bandit problem into an approximately stationary one. The Gate-Induced Equivalence theorem shows that under a stationary gate, historical data collected under any prior policy is a valid warm-up initialiser without importance-sampling correction, generalising the companion P-HITL result (arXiv:2606.02595) from human approval to arbitrary gates. In regulated, high-stakes domains, constraints usually treated as deployment frictions -- approval gates, compliance rules, safety shields -- are the mechanism that makes fast deployment possible, not an obstacle to it. The companion paper validates instance 1 (STR dynamic pricing) on real production data.
In fixed-confidence best-arm identification, proofs often use a union bound across the competing arms. From a multiple-testing point of view this can look puzzling: if the best arm is unique, only one hypothesis of the form ``arm i is best'' can be true. Why then should there be a Bonferroni-type factor of K−1? The answer is that there are two natural ways to orient the hypotheses. In one orientation, best-arm identification is literally a strong familywise-error-rate (FWER) problem with K−1 true nulls. In the opposite orientation, exactly one null is true, but a pairwise implementation can falsely reject that one null through any of K−1 comparisons. Thus the multiplicity has not disappeared; it just pops up in different places. This note makes the equivalence explicit in the terminology of both communities.
Rianne de Heide
Department of Applied Mathematics, University of Twente · Centrum Wiskunde & Informatica, Amsterdam
We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields γ~T/T=O(ε1/2) and expected average regret O(ε1/4) in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on 1/ε.
Matthias Mandl, Hanne Kekkonen
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs. We study the trade-off between worst-case regret RK,T and instability SK,T, defined as the largest standard deviation of a terminal pull count, for K arms and T rounds. We prove the finite-time lower bound RK,TSK,T≥CT3/2, where C is independent of K and T, under a finite-time regret condition and without the regularity assumptions imposed in the prior asymptotic analysis. We also introduce Stabilized Lower-Envelope UCB (\textup{SLE-UCB}), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. \textup{SLE-UCB} satisfies RK,TSK,T=O(T3/2logK), with an implicit constant independent of K and T, matching the lower bound exactly in T and within a logarithmic factor in K. To prove the instability bound, we develop a new offline top-prefix representation that removes path dependence from online decisions. Together with single-reward perturbations and the Efron--Stein inequality, this representation controls pull-count variance. Thus, regret and instability depend reciprocally on K, while their product has no polynomial dependence on K. These results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier.
Kaifei Wang, Yinyu Ye, Han Zhong
Peking University · Stanford University · Shanghai Jiao Tong University
We consider the dynamic principal-agent problem under asymmetric information, wherein a principal sequentially designs contracts to incentivize an agent with unknown preferences and hidden actions. A fundamental bottleneck in the existing literature is the assumption of deterministic agent utility, which renders the principal's expected utility discontinuous and forces computationally intractable discretizations of the contract space. In this paper, we address this limitation by introducing a stochastic counterpart into the agent's utility model, capturing the inherent physical and behavioral variations in realistic subsystems. We formally prove that this stochastic formulation restores the continuity of the principal's expected utility. Leveraging this continuous geometric structure, we formulate the interaction as a structured multi-armed bandit problem subject to heteroscedastic noise. We propose a Heteroscedastic GP-UCB algorithm that utilizes a Neural Network (Arcsin) kernel, chosen to capture the non-stationary, sigmoidal geometry of the utility landscape. For an m-dimensional compact contract space, we establish a high-probability cumulative regret bound of O(T(logT)m+1). Finally, we demonstrate the practical efficacy of our theoretical framework by formulating the Vehicle-to-Grid (V2G) incentive design problem, proving its equivalence to a dynamic principal-agent problem, and showing superior economic performance for grid aggregators.
Arghya Mallick, Anuj S. Vora, Sergio Grammatico +1
Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands · Jio Institute, Navi Mumbai, India · University of Toronto, Toronto, Canada
Large language models (LLMs) are increasingly deployed as decision-making agents in settings that require sophisticated environmental exploration. However, existing work has raised questions about how LLMs actually balance exploration and exploitation. Unlike classical agents, LLM agents engage with tasks through natural language, exposing them to semantic information with no formal counterpart in the task structure. We introduce the semantic bandit, an extension of the multi-armed bandit setting that explicitly considers the textual labels assigned to actions, and use it to study how semantic priors --- inductive biases arising from associations between language and expected reward learned during pre-training, shape LLM exploration behaviour. We find that semantically informative action labels reduce exploration in favour of exploitation, improving performance when aligned with the reward structure and severely degrading it when misaligned. We further find that negative rewards trigger substantially more exploration than equivalent positive rewards, consistent with an expected-scale bias induced by reward conventions common in pre-training data. Overall, we argue that the use of language to define the environment and rewards introduces unavoidable biases derived from the fact that the model is trained on word co-occurence, with implications for the reliability and robustness of LLM agents in real-world decision-making settings.
David Eric Austin, Kaheer Suleman, Jackie Chi Kit Cheung
McGill University · Mila – Quebec AI Institute · Skyfall AI +1
This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization. The known regret upper bounds for the widely used GP batched upper confidence bound and GP batched Thompson sampling (GP-BTS) suffer from a multiplicative factor with respect to the batch size Q. To avoid this degradation, existing analyses require a polynomial number of uncertainty sampling (US) for Q at the beginning of optimization. However, this initial US phase is often ineffective in practice. This paper shows that the regret upper bound without the multiplicative factor on Q can be achieved without the initial US phase, using GP-BTS as an example. Furthermore, we show much better regret upper bounds in the noiseless setting than in the noisy setting, as in the sequential GP bandit setting.
What is the right delay complexity when a learner can track only C pending feedback items and discarded feedback is permanently lost? Existing one-point bandit convex optimization guarantees in this model pay Tσmax, where σmax is the peak backlog, although unlimited tracking admits the sharper dtot dependence on total delay. We introduce a scheduler-side conditional-energy interface that separates rate adaptation from the one-point perturbation filtration and handles the dependent importance weights created by randomized admission. Under the same semi-clairvoyant oracle and pathwise hard-capacity contract, this yields an untuned learner whose delay term scales as O(ECdtot), with only an explicit restart factor EC; a public constant-factor peak bound removes this factor while dtot remains unknown. Under strong convexity, the same interface yields the temporal cost HA(d)=∑tσt/(A+t). Two delay vectors with identical delay multisets, dtot, σmax, and capacity can nevertheless have polynomially different minimax regret, showing that timing matters under curvature even when aggregate delay summaries agree. Finally, a continuous hard family converts tracking capacity into a zeroth-order query budget and gives a complementary capacity-starvation lower endpoint. The upper bounds require C≥lnT+1 and do not constitute a complete capacity minimax characterization.
Anling Xiang, Yuwen Yang, Yang Shen
Department of Intelligent Communication, School of Journalism and Communication, Minzu University of China, Beijing, China · ZeeLin (Beijing) Technology Co., Ltd., Beijing, China · School of Journalism and Communication, Tsinghua University, Beijing, China +1
We study second-order path-length regret in adversarial K-armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves O(K+KQ∞,1) regret, where Q∞,1 is the first-order path length, and left open whether O(poly(K)1+Q∞,2) regret is achievable under bandit feedback, where Q∞,2 is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves O(Klog(KT)+Klog(KT)(1+Q∞,2)) expected regret when Q∞,2 is known, where T is the horizon. This matches the Ω(KQ∞,2) lower bound up to logarithmic factors and additive terms. We further remove the knowledge of Q∞,2 using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.
We study generalized linear bandits with memory, an endogenous non-stationary setting in which rewards depend on past actions through a finite memory matrix. Building on prior work for linear models (Clerici et al., 2024), we show that the previously known O~(T3/4) regret bound stems from a loose analysis, and we provide a sharpened analysis that recovers a O~(T) regret rate in the linear case. We then extend this improvement to generalized linear models and propose a block-wise algorithm based on shrunken confidence bounds. Our algorithm achieves a regret bound of O~(mT+dT+κd2m1/4T1/4+κd2), where d denotes the feature dimension, m the memory length, and κ a curvature parameter of the link function. This attains a T-type rate despite nonlinear rewards and memory effects. To the best of our knowledge, this analysis provides a unified treatment of memory-induced non-stationarity and nonlinear link functions, while ensuring that the leading regret term is independent of the curvature of the link function. We conduct numerical experiments that are consistent with our theoretical findings.
Heesang Ann, Hyunjun Choi, Taehyun Hwang +3
Seoul National University, Seoul, Republic of Korea · Shinsegae, Seoul, Republic of Korea
Regret minimization (RM) and best-arm identification (BAI) are two fundamental objectives in multi-armed bandits. Among regret-minimizing algorithms, 1/2-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm: it achieves logarithmic pseudo-regret in stochastic bandits while retaining minimax-optimal regret in adversarial bandits, without knowing the environment in advance. This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably? We study this question in stochastic bandits by analyzing the failure probability Errt, defined as the probability that the empirical best arm determined by the cumulative importance-weighted loss estimates of 1/2-Tsallis-INF differs from the true optimal arm. The main difficulty is that, at the logarithmic-regret scale, suboptimal arms are sampled with probability heuristically of order 1/t. Consequently, importance weighting causes the cumulative estimator to fluctuate on the same linear scale as its mean separation. To overcome this obstacle, guided by a diffusion toy model, we construct a Lyapunov function for the gap process between the estimated cumulative loss of the optimal arm and that of the best competing arm. This leads to polynomial upper bounds on Errt: for learning rate ηt=α/t, Errt decays at rate t−2+α2μi∗/4+ρ for any ρ>0, where μi∗ denotes the mean loss of the true optimal arm. We also establish a lower bound Ω(t−2−ε) for any ε>0, showing that the exponent 2 is essentially tight.
Jingxin Zhan, Yuze Han, Zhihua Zhang
School of Mathematical Sciences, Peking University · Center for Applied Statistics and School of Statistics, Renmin University of China
The Lipschitz bandit problem extends the traditional multi-armed bandit framework to continuous action spaces by assuming that the reward functions satisfy a Lipschitz condition. This work investigates Lipschitz bandits under arbitrary feedback delays, where reward signals are not received immediately upon taking an action but after an arbitrarily chosen delay. We consider both stochastic and adversarial reward settings, proposing an elimination-based algorithm and an EXP3-based algorithm, respectively. For both settings, our algorithms achieve a regret bound of O~(Tdz+2dz+1+D) over a time horizon T with total delay D, where the main difference between settings lies in the definition of the zooming dimension dz. Our bounds match existing delay-free regret guarantees for Lipschitz bandits and characterize the additional O~(D) impact introduced by feedback delays.
Yuhao Liu, Yu Chen, Longbo Huang
Institute for Interdisciplinary Information Sciences, Tsinghua University
We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB), where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon T with regret O(KlogT) for QMAB with K arms and O(d2polylogT) for d-dimensional QLB. This leaves open the optimal dependence on K and T and whether the dependence on d can be further improved. In this work, we prove the first tight minimax regret bound of Θ(Klog(1+T/K)) for QMAB and the first lower bound of Ω(dlog(1+T/d)) for finite-action QLB, ruling out regret independent of T. Our lower bounds rely on a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. The matching QMAB upper bound is obtained using a tail bound for the Quantum Monte Carlo (QMC) estimator. For finite-action QLB, we propose a phased elimination algorithm that combines a low-bias low-variance quantum mean estimator with a small-support G-optimal design through a query allocation matched to the design weights. When the action set has size poly(d), its regret is nearly linear in d and matches our lower bound up to polylogarithmic factors.
Maoli Liu, Zhuohua Li, John C. S. Lui
The Chinese University of Hong Kong · Xidian University
In this work, we extend the Dependent Click Model (DCM) Bandits to a multiplayer information-asymmetric setting, where multiple agents interact with a shared ranked list and may observe multiple clicks per session, introducing new challenges for selection strategies. We study asymmetry in (1) actions and (2) rewards, providing sublinear regret guarantees for three settings where at least one asymmetry is present. Establishing matching information-theoretic lower bounds for these settings is left as an open problem. We further show that for small termination probabilities, the termination ranking need not be known, improving on prior single-agent results. Experiments confirm that our algorithms perform well across asymmetric environments and highlight the critical role of feedback structure, specifically the distinction between full versus first-click feedback, in coordinating exploration and minimizing regret.
Andy Wang, Charlton Shih, William Chang
Department of Mathematics University of California, Los Angeles Los Angeles, USA
Personalizing marketing messages with contextual multi-armed bandits (CMABs) drives real business value, yet the objective that ultimately matters - a downstream conversion - is observed only weeks later, too late to drive online learning. Teams therefore train the bandit on a fast proxy reward, and separately must judge whether a contextual bandit is worth its complexity over sending one best message. Settling both decisions with the usual offline checks - a batch off-policy estimate, a marginal arm-discrimination test, a confidence interval - can mislead systematically under delayed feedback. We give an ordered diagnostic protocol that screens a reward-and-policy candidate on two axes, alignment (does optimizing the reward move the north-star?) and learnability (can the bandit identify the reward-optimal policy?), before trusting any reported lift. We validate it where the truth is known - a public off-policy-evaluation benchmark and a controllable synthetic generator - and illustrate it on a deployed large-marketplace push system (where, with five arms and one split, the evidence is directional rather than powered). Two lessons recur. (N1) A single offline number can mis-rank rewards: a denser reward signal gives the bandit more to learn from, so rewards that look tied in a static estimate pull apart once learning happens online. (N2) If you cannot tell in advance which single message is best, a per-user policy partly just avoids betting on the wrong one - that looks like personalization but is really robustness, so a "personalization premium" is easily overstated. Our contribution is methodological rather than algorithmic: the ordered protocol, the two lessons it surfaces, and the end-to-end experience of applying it to a delayed-feedback CMAB.
We study the multiplayer multi-armed bandit problem with information asymmetry under Bernoulli rewards, for three information structures: asymmetry in actions, in rewards, and in both. Replacing the Hoeffding-style confidence intervals of prior work with Kullback--Leibler (KL) divergence-based bounds gives strictly tighter regret guarantees in each case. We propose mKL-UCB, mKL-UCB-Intervals and mKL-DSEE, and show that the improvement factor is at least two by Pinsker's inequality and far larger when reward means are near zero or one. For asymmetry in rewards we prove that two arms' KL intervals separate after a deterministic number of samples, and that M independent players accelerate elimination further.
Khang Nguyen, Ricardo Parada, William Chang
Dept. of Computer Science University of California, Los Angeles Los Angeles, CA, USA · Dept. of Electrical and Computer Engineering University of California, Los Angeles Los Angeles, CA, USA
The multi-armed bandit problem is a central framework in sequential decision-making, extensively studied under sub-Gaussian reward assumptions. However, real-world applications often involve heavy-tailed reward distributions and decentralized, information-asymmetric interactions. We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes: unobserved actions with common rewards, observed actions with independent rewards, and unobserved actions with independent rewards. We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates. Experiments on a Pareto-distributed reward environment validate our theoretical findings and illustrate the trade-offs between synchronization, coordination, and exploration across the three regimes.
Daphne Feng, Ricardo Parada, Lily Jiang +2
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA, USA · Department of Mathematics, University of California, Riverside, Riverside, CA, USA
Motivated by decentralized applications, we study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown. We consider three information structures: (A)~unobserved actions with common rewards, (B)~observed actions with independent rewards, and (C)~unobserved actions with independent rewards. In each case we design and analyze an algorithm that estimates the Lipschitz constant, chooses a discretization of the joint action space, and applies a cooperative bandit method to the induced discrete problem. Players never communicate once learning starts, so the central difficulty is that they must reach the same discretization from their own data. We prove regret guarantees showing that common rewards and observable actions each supply this agreement for free, and that in their absence agreement can still be bought, through a dithered quantization of the estimate, at no cost in the leading order of the regret.
Ricardo Parada, Chenzhang Zhao, William Chang
University of California, Riverside Riverside, CA, USA · University of California, Los Angeles Los Angeles, CA, USA
Large-scale learning systems often face the challenge of balancing multiple, potentially competing objectives, such as fairness, accuracy, and latency. While recent work has formalized this as an optimization problem over binary states, many real-world control parameters, such as fairness thresholds, diversity mixing rates, or resource budgets, are continuous. In this work, we extend the framework to continuous state spaces. We model the problem as minimizing a sum of linear objectives subject to movement costs that penalize system instability. We capture the local structure of the objectives using a dependency graph (or factor graph), where each objective is determined by a subset of the state attributes. To address the tension between exploration and stability, we propose Lazy Graph-LinUCB, an algorithm that performs lazy updates to minimize switching costs while maintaining near-optimal regret. Beyond stability, we introduce three advanced mechanisms to exploit the underlying graph structure: (1) an asynchronous update schedule that eliminates synchronization overhead in sparse graphs; (2) an adaptive algorithm that learns the graph structure from data; and (3) a joint estimator that leverages data sharing among correlated objectives to significantly tighten regret bounds. Empirically, we demonstrate that these structural exploitations reduce movement costs by more than a factor of three in heterogeneous systems while maintaining similar cumulative losses.
Corinna Cortes, Yishay Mansour, Mehryar Mohri
Google Research · Tel Aviv University · Courant Institute
Lipschitz bandits admit near-optimal regret Od(T(d+1)/(d+2)) with little memory under full adaptivity, or with few batches under unrestricted memory. We characterize the minimax expected pseudo-regret over T rounds with W bits of memory and at most B batches in dimension d. For every memory budget W, we prove a lower bound of order Td+3d+2(1+(B−1)W)−d(d+3)1. When W≳dlog(eT), algorithms with fixed batch boundaries attain, up to logarithmic factors, the larger of this bound and the optimal B-batch regret with unrestricted memory. The analysis separates fine-scale comparisons from the regional information needed to allocate their samples at low regret. Attaining Od(T(d+1)/(d+2)) regret requires both B=Ωd(loglogT) and (B−1)W=Ωd(Td/(d+2)). With one bit of memory, minimax regret is Θd(TB−1/(d+2)) under adaptive batch boundaries while Θd(T) under fixed boundaries.
Zicheng Lyu, Zengfeng Huang
Fudan University Shanghai, China · Fudan University Shanghai Innovation Institute Shanghai, China
Large language model (LLM) configuration evaluation is challenging due to limited evaluation budgets, varying costs, and multiple competing objectives. In this paper, we formulate LLM configuration evaluation as a cost-aware multi-objective bandit problem, where each configuration evaluation incurs a configuration-dependent cost and yields a noisy vector-valued outcome. Under this framework, we study two fundamental problems: online configuration selection and Pareto configuration identification. For online configuration selection, we propose a hypervolume-based UCB algorithm that optimizes an optimistic hypervolume-per-cost index. We establish a budgeted regret bound of order O(∑i=i⋆ΔilogB), where B is the evaluation budget, i⋆ is the optimal configuration in terms of hypervolume efficiency, and Δi is the corresponding efficiency gap of configuration i. This bound retains the logarithmic budget dependence of classical single-objective budgeted bandits. For fixed-budget Pareto identification, we develop a cost-aware empirical gap elimination algorithm and prove that its error probability is of order O(exp(−Hμ,cB)), where Hμ,c is a cost-aware Pareto identification complexity depending on configuration costs and Pareto classification gaps. This error probability decays exponentially with the evaluation budget and recovers the standard Pareto set identification guarantee when all configuration costs are identical. Experiments on LLM configuration evaluation tasks demonstrate that the proposed framework enables efficient online decision-making and accurate cost-aware Pareto identification under limited budgets.
Bo Xue, Zhi Hong, Jiayi Li +3
City University of Hong Kong · South China University of Technology · Zhejiang University
This paper studies generalized low-rank matrix bandits with multiple prioritized objectives. At each round, the learner selects a matrix-valued arm and observes a vector-valued reward, whose components correspond to multiple objectives with different priority levels. Each objective is governed by an objective-specific generalized low-rank matrix model, and the learner evaluates arms according to a lexicographic preference order, prioritizing higher-level objectives before lower-level ones. We propose Lexi-LowGLM, an efficient online algorithm that first estimates objective-specific low-rank subspaces and then performs lexicographic learning in the reduced feature spaces. Unlike existing single-objective algorithms that repeatedly solve a batch generalized linear estimator using all historical observations, Lexi-LowGLM updates each objective-specific estimator via an online Newton step, reducing the estimator-update complexity over T rounds from O(T2) to O(T). We establish a regret bound of O(Wilexm(d1+d2)rT) for each objective i∈[m], where r is an upper bound on the ranks of the objective-specific parameter matrices and Wilex characterizes the lexicographic trade-off effect. This bound depends on the effective low-rank dimension (d1+d2)r rather than the ambient dimension d1d2. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method.
Bo Xue, Ji Cheng, Haodong Jing +2
City University of Hong Kong. · Xi’an Jiaotong University. · Northwestern Polytechnical University.