Contextual Bandits

Follow this topic Ask about this topic

Contextual bandits study how to choose an action using information about the current situation when feedback reveals the reward only for the action taken. Common approaches include linear and generalized linear models with UCB or Thompson sampling, alongside kernel, neural, and policy-based methods for richer reward patterns. Offline learning and evaluation, nonstationary or corrupted feedback, and constraints such as budgets, privacy, and safety extend these methods to settings including recommendation, pricing, and LLM routing. A central challenge is balancing exploration with reliable decisions when models are misspecified, feedback is sparse or delayed, and computational or operational costs matter.

Latest papers

152 papers20 papers in the last four weeks, up 150% on the four weeks before. 0.1% of all new papers.

Apr 7, 2026

When Do We Need LLMs? A Diagnostic for Language-Driven Bandits

We study Contextual Multi-Armed Bandits (CMABs) for non-episodic decision-making problems where the context includes both textual and numerical information (e.g., recommendation systems, dynamic portfolio adjustments, offer selection; all frequent problems in finance). While Large Language Models (LLMs) are increasingly applied to these settings, utilizing LLMs for reasoning at every decision step is computationally expensive, and uncertainty estimates are difficult to obtain. To address this, we introduce LLMP-UCB, a bandit algorithm that derives uncertainty estimates from LLMs via repeated inference. However, our experiments demonstrate that lightweight numerical bandits operating on text embeddings (dense or Matryoshka) match or exceed the accuracy of LLM-based solutions at a fraction of their cost. We further show that embedding dimensionality is a practical lever on the exploration-exploitation balance, enabling cost-performance tradeoffs without prompt complexity. Finally, to guide practitioners, we propose a geometric diagnostic based on the arms' embeddings to decide when to use LLM-driven reasoning versus a lightweight numerical bandit. Our results provide a principled deployment framework for cost-effective, uncertainty-aware decision systems with broad applicability across AI use cases.

Uljad Berdica, Fernando Acero, Anton Ipsen +3

University of Oxford · J.P. Morgan AI Research

Contextual Bandits LLM Decision-Making LLM Uncertainty Estimation

Apr 2, 2026

Jump Start or False Start? A Theoretical and Empirical Evaluation of LLM-initialized Bandits

The recent advancement of Large Language Models (LLMs) offers new opportunities to generate user preference data to warm-start bandits. Recent studies on contextual bandits with LLM initialization (CBLI) have shown that these synthetic priors can significantly lower early regret. However, these findings assume that LLM-generated choices are reasonably aligned with actual user preferences. In this paper, we systematically examine how LLM-generated preferences perform when random and label-flipping noise is injected into the synthetic training data. For aligned domains, we find that warm-starting remains effective up to 30% corruption, loses its advantage around 40%, and degrades performance beyond 50%. When there is systematic misalignment, even without added noise, LLM-generated priors can lead to higher regret than a cold-start bandit. To explain these behaviors, we develop a theoretical analysis that decomposes the effect of random label noise and systematic misalignment on the prior error driving the bandit's regret, and derive a sufficient condition under which LLM-based warm starts are provably better than a cold-start bandit. We validate these results across multiple conjoint datasets and LLMs, showing that estimated alignment reliably tracks when warm-starting improves or degrades recommendation quality.

Adam Bayley, Xiaodan Zhu, Raquel Aoki +2

Department of Electrical and Computer Engineering, Queen’s University · RBC Borealis

Contextual Bandits Large Language Model-Based Recommendation LLM Alignment

Mar 31, 2026

ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving

Multi-model LLM serving operates in a non-stationary, noisy environment: providers revise pricing, model quality can shift or regress without notice, and new models arrive regularly. More than a dozen recent methods have proposed learned routers to navigate the resulting quality--cost tradeoff across portfolios spanning a

\sim

530

\times

cost range. Despite this activity, two gaps in the current solution space limit routing effectiveness under these conditions: no existing router enforces a dollar-denominated cost ceiling in closed loop over an open-ended request stream, and none provides principled online adaptation to post-deployment shifts in pricing or model quality. We present ParetoBandit, an open-source adaptive router built on cost-aware contextual bandits that addresses both gaps. Its core contributions are: (1) an online primal--dual budget pacer that enforces a per-request cost ceiling without a known horizon, and (2) geometric forgetting on sufficient statistics that gives the bandit bounded memory for tracking quality and cost shifts. A hot-swap model registry further supports runtime model changes with budget-controlled exploration. On 1,824 benchmark prompts with a three-model portfolio, the router maintains budget compliance within 0.4%, adapts to price and quality shifts with up to +0.071 quality lift, and integrates a cold-started model within

\sim

142 steps.

Annette Taberner-Miller

Independent Researcher.

Adaptive Model Routing LLM Routing LLM Serving Non-Stationary Bandits Contextual Bandits

Mar 24, 2026

DAK-UCB: Diversity-Aware Prompt Routing for LLMs and Generative Models

The expansion of generative AI and LLM services underscores the growing need for adaptive mechanisms to select an appropriate available model to respond to a user's prompts. Recent works have proposed offline and online learning formulations to identify the optimal generative AI model for an input prompt, based solely on maximizing prompt-based fidelity evaluation scores, e.g., CLIP-Score in text-to-image generation. However, such fidelity-based selection methods overlook the diversity of generated outputs, and hence, they can fail to address potential diversity shortcomings in the generated responses. In this paper, we introduce the Diversity-Aware Kernelized Upper Confidence Bound (DAK-UCB) method as a contextual bandit algorithm for the online selection of generative models with diversity considerations. The proposed DAK-UCB method incorporates both fidelity and diversity-related metrics into the selection process. We design this framework based on prompt-aware diversity score functions that decompose to a two-sample-based expectation over prompt-output pairs in the previous generation rounds. Specifically, we illustrate the application of our framework using joint kernel distance and kernel entropy measures. Our experimental results demonstrate the effectiveness of DAK-UCB in promoting diversity-aware model selection while maintaining fidelity in the generations for a sequence of prompts. The code is available at https://github.com/Donya-Jafari/DAK-UCB.

Donya Jafari, Farzan Farnia

Sharif University of Technology · The Chinese University of Hong Kong

LLM Routing Contextual Bandits Generative Modeling

Mar 21, 2026

Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness

Contextual recommendation is a variant of contextual linear bandits in which the learner observes an (optimal) action rather than a reward scalar. Recently, Sakaue et al. (2025) developed an efficient Online Newton Step (ONS) approach with an

O(d\log T)

regret bound, where

d

is the dimension of the action space and

T

is the time horizon. In this paper, we present a simple algorithm that is more efficient than the ONS-based method while achieving the same regret guarantee. Our core idea is to exploit the improperness inherent in contextual recommendation, leading to an update rule akin to the second-order perceptron from online classification. This removes the Mahalanobis projection step required by ONS, which is often a major computational bottleneck. More importantly, the same algorithm remains robust to possibly suboptimal action feedback, whereas the prior ONS-based method required running multiple ONS learners with different learning rates for this extension. We describe how our method works in general Hilbert spaces (e.g., via kernelization), where eliminating Mahalanobis projections becomes even more beneficial.

Shinsaku Sakaue

Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan

Contextual Bandits Recommender Systems Linear Contextual Bandits

Mar 19, 2026

Kernel Single-Index Bandits: Estimation, Inference, and Learning

We study contextual bandits with finitely many actions in which the reward of each arm follows a single-index model with an arm-specific index parameter and an unknown nonparametric link function. We consider a regime in which arms correspond to stable decision options and covariates evolve adaptively under the bandit policy. This setting creates significant statistical challenges: the sampling distribution depends on the allocation rule, observations are dependent over time, and inverse-propensity weighting induces variance inflation. We propose a kernelized

\varepsilon

-greedy algorithm that combines Stein-based estimation of the index parameters with inverse-propensity-weighted kernel ridge regression for the reward functions. This approach enables flexible semiparametric learning while retaining interpretability. Our analysis develops new tools for inference with adaptively collected data. We establish asymptotic normality for the single-index estimator under adaptive sampling, yielding valid confidence regions, and derive a directional functional central limit theorem for the RKHS estimator, which provides asymptotically valid pointwise confidence intervals. The analysis relies on concentration bounds for inverse-weighted Gram matrices together with martingale central limit theorems. We further obtain finite-time regret guarantees, including

\tilde{O}(\sqrt{T})

rates under common-link Lipschitz conditions, showing that semiparametric structure can be exploited without sacrificing statistical efficiency. These results provide a unified framework for simultaneous learning and inference in single-index contextual bandits.

Sakshi Arya, Satarupa Bhattacharjee, Bharath K. Sriperumbudur

Department of Mathematics, Applied Mathematics, and Statistics, Case Western Reserve University · Department of Statistics, University of Florida · Department of Statistics, The Pennsylvania State University

Contextual Bandits Single-Index Models Semiparametric Inference Confidence Region Estimation

Mar 19, 2026

Off-Policy Learning with Limited Supply

We study off-policy learning (OPL) in contextual bandits, which plays a key role in a wide range of real-world applications such as recommendation systems and online advertising. Typical OPL in contextual bandits assumes an unconstrained environment where a policy can select the same item infinitely. However, in many practical applications, including coupon allocation and e-commerce, limited supply constrains items through budget limits on distributed coupons or inventory restrictions on products. In these settings, greedily selecting the item with the highest expected reward for the current user may lead to early depletion of that item, making it unavailable for future users who could potentially generate higher expected rewards. As a result, OPL methods that are optimal in unconstrained settings may become suboptimal in limited supply settings. To address the issue, we provide a theoretical analysis showing that conventional greedy OPL approaches may fail to maximize the policy performance, and demonstrate that policies with superior performance must exist in limited supply settings. Based on this insight, we introduce a novel method called Off-Policy learning with Limited Supply (OPLS). Rather than simply selecting the item with the highest expected reward, OPLS focuses on items with relatively higher expected rewards compared to the other users, enabling more efficient allocation of items with limited supply. Our empirical results on both synthetic and real-world datasets show that OPLS outperforms existing OPL methods in contextual bandit problems with limited supply.

Koichi Tanaka, Ren Kishimoto, Bushun Kawagishi +4

Institute of Science Tokyo Tokyo, Japan · Meiji University Tokyo, Japan · Yale University New Haven, CT, USA +2

Contextual Bandits Off-Policy RL Online Resource Allocation

Mar 17, 2026

A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems

Contextual bandits are incredibly useful in many practical problems. We go one step further by devising a more realistic problem that combines: (1) contextual bandits with dense arm features, (2) non-linear reward functions, and (3) a generalization of correlated bandits where reward distributions change over time but the degree of correlation maintains. This formulation lends itself to a wider set of applications such as recommendation tasks. To solve this problem, we introduce conditionally coupled contextual C3 Thompson sampling for Bernoulli bandits. It combines an improved Nadaraya-Watson estimator on an embedding space with Thompson sampling that allows online learning without retraining. Empirical results show that C3 outperforms the next best algorithm by 5.7% lower average cumulative regret on four OpenML tabular datasets as well as demonstrating a 12.4% click lift on Microsoft News Dataset (MIND) compared to other algorithms.

Wei Min Loh, Sajib Kumer Sinha, Ankur Agarwal +1

University of Waterloo, Vector Institute · Manulife Financial

Bandit Learning Multi-Armed Bandits Contextual Bandits Non-Stationary Bandits Thompson Sampling Recommender Systems

Mar 16, 2026

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite

(1+ε)

-th moments for some

ε\in (0,1]

. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance (i.e., finite second-moment) assumption and suffers from computational inefficiency. We propose a computationally efficient algorithm based on online mirror descent that achieves robustness to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs

\mathcal{O}(t\log T)

computational cost, our algorithm reduces this to

\mathcal{O}(1)

per round. We establish an additive regret bound consisting of a term depending on the

(1+ε)

-moment bound of the noise and a term depending on the total amount of corruption. In particular, when

ε= 1

, our result recovers existing guarantees under finite-variance assumptions. When no corruption is present, it matches the best-known rates for linear contextual bandits with heavy-tailed noise. Moreover, the algorithm requires no prior knowledge of the noise moment bound or the total amount of corruption and still guarantees sublinear regret.

Naoto Tani, Futoshi Futami

The University of Osaka · RIKEN AIP · The University of Tokyo

Contextual Bandits Linear Contextual Bandits Multi-Armed Bandits

Mar 13, 2026

Mixing Makes Markovian Contexts Cheap for Linear Bandits

Recent work shows that when contexts are drawn i.i.d., linear contextual bandits can be reduced to single-context linear bandits. This ``contexts are cheap'' perspective is highly advantageous, as it allows for sharper finite-time analyses and leverages mature techniques from the linear bandit literature, such as those for misspecification and adversarial corruption. However, this reduction crucially relies on the independence of contexts and does not extend to settings with temporally correlated (e.g., Markovian) contexts, which arise frequently in practice. Motivated by applications with temporally correlated availability, we extend this perspective to linear bandits with Markovian context processes, where the action set evolves via an exogenous Markov chain. Our main contribution is a reduction that applies under uniform geometric ergodicity. We construct a stationary surrogate action set to solve the problem using a standard linear bandit oracle, employing a delayed-update scheme to control the bias induced by the nonstationary conditional context distributions. We further provide a phased algorithm for unknown stationary distributions that learns the surrogate mapping online. In both settings, we obtain a high-probability worst-case regret bound matching that of the underlying linear bandit oracle in sufficiently fast mixing regimes. We then validate our results on a real-world instance, where we show practical gains over a LinUCB baseline.

Kaan Buyukkalayci, Osama Hanna, Christina Fragouli

University of California, Los Angeles · Meta, Superintelligence Lab

Markovian Bandits Contextual Bandits Linear Contextual Bandits

Mar 11, 2026

RIE-Greedy: Regularization-Induced Exploration for Contextual Bandits

Real-world contextual bandit problems with complex reward models are often tackled with iteratively trained models, such as boosting trees. However, it is difficult to directly apply simple and effective exploration strategies--such as Thompson Sampling or UCB--on top of those black-box estimators. Existing approaches rely on sophisticated assumptions or intractable procedures that are hard to verify and implement in practice. In this work, we explore the use of an exploration-free (pure-greedy) action selection strategy, that exploits the randomness inherent in model fitting process as an intrinsic source of exploration. More specifically, we note that the stochasticity in cross-validation based regularization process can naturally induce Thompson Sampling-like exploration. We show that this regularization-induced exploration is theoretically equivalent to Thompson Sampling in the two-armed bandit case and empirically leads to reliable exploration in large-scale business environments compared to benchmark methods such as epsilon-greedy and other state-of-the-art approaches. Overall, our work reveals how regularized estimator training itself can induce effective exploration, offering both theoretical insight and practical guidance for contextual bandit design.

Tong Li, Thiago de Queiroz Casanova, Eric M. Schwartz +3

University of Toronto Canada · Braze United States · University of Michigan United States

Contextual Bandits Exploration-Exploitation Tradeoff RL Exploration Thompson Sampling

Mar 10, 2026

What Do We Care About in Bandits with Noncompliance? BRACE: Bandits with Recommendations, Abstention, and Certified Effects

Bandits with noncompliance separate the learner's recommendation from the treatment actually delivered, so the learning target itself must be chosen. A platform may care about recommendation welfare in the current mediated workflow, treatment learning for a future direct-control regime, or anytime-valid uncertainty for one of those targets. These objectives need not agree. We formalize this objective-choice problem, identify the direct-control regime in which recommendation and treatment objectives collapse, and show by example that recommendation welfare can strictly exceed every learner-measurable treatment policy when downstream actors use private information. For finite-context square-IV problems we propose BRACE, a parameter-free phase-doubling algorithm that performs IV inversion only after matrix certification and otherwise returns full-range but honest structural intervals. BRACE delivers simultaneous policy-value validity, fixed-gap identification of the operationally optimal recommendation policy, and fixed-gap identification of the structurally optimal treatment policy under contextual homogeneity and invertibility. We complement the theory with a finite-context empirical benchmark spanning direct control, mediated present-versus-future tradeoffs, weak identification, homogeneity failure, and rectangular overidentification. The experiments show that safety appears as regret on easy problems, as abstention and wide valid intervals under weak identification, as a reason to prefer recommendation welfare under homogeneity failure, and as tighter structural uncertainty when extra instruments are available. For rich contexts, we also derive an orthogonal score whose conditional bias factorizes into compliance-model and outcome-model errors, clarifying what must be stabilized for anytime-valid semiparametric IV inference.

Nicolás Della Penna

Grouplang

Contextual Bandits Instrumental Variable Estimation Anytime-Valid Inference

Mar 10, 2026

From Weighting to Modeling: A Nonparametric Estimator for Off-Policy Evaluation

We study off-policy evaluation in the setting of contextual bandits, where we aim to evaluate a new policy using historical data that consists of contexts, actions and received rewards. This historical data typically does not faithfully represent action distribution of the new policy accurately. A common approach, inverse probability weighting (IPW), adjusts for these discrepancies in action distributions. However, this method often suffers from high variance due to the probability being in the denominator. The doubly robust (DR) estimator reduces variance through modeling reward but does not directly address variance from IPW. In this work, we address the limitation of IPW by proposing a Nonparametric Weighting (NW) approach that constructs weights using a nonparametric model. Our NW approach achieves low bias like IPW but typically exhibits significantly lower variance. To further reduce variance, we incorporate reward predictions -- similar to the DR technique -- resulting in the Model-assisted Nonparametric Weighting (MNW) approach. The MNW approach yields accurate value estimates by explicitly modeling and mitigating bias from reward modeling, without aiming to guarantee the standard doubly robust property. Extensive empirical comparisons show that our approaches consistently outperform existing techniques, achieving lower variance in value estimation while maintaining low bias.

Rong J. B. Zhu

Institute of Science and Technology for Brain-inspired Intelligence, Fudan University

Off-Policy Evaluation Inverse Probability Weighting Importance Weighting Contextual Bandits Doubly Robust Estimation

Mar 9, 2026

Learning When to Trust in Contextual Social Bandits

Robust reinforcement learning typically assumes that feedback sources are either globally trustworthy or corrupted within a fixed global budget. We identify a more subtle failure mode that escapes this dichotomy, which we call Contextual Sycophancy. In this failure, evaluators are truthful in benign contexts but systematically biased in critical ones, so that no single evaluator is reliable everywhere and the corrupt evaluators may form a majority in the contexts that matter. Our first result is an information-theoretic lower bound. We exhibit two problem instances that induce identical social-feedback distributions yet have disjoint optimal actions, proving that any algorithm relying on social feedback alone (including any robust aggregator, regardless of breakdown point) incurs

Ω(T)

latent regret. This shows that breaking contextual sycophancy is impossible without having some information. We then show that a sparse stream of ground-truth audits, available with probability

p_{\mathrm{aud}}

, is sufficient. We propose \ESA, which learns a per-evaluator contextual trust boundary from audits and re-weights feedback accordingly, and we prove a high-probability latent-regret bound of

\tilde{\mathcal{O}}\!\big(\sqrt{T\,d_{VC}/p_{\mathrm{aud}}} + d\sqrt{T} + ε_{\mathrm{tol}}T\big)

, where

d_{VC}

is the complexity of the adversary's bias strategy. The audit-dependence

1/\sqrt{p_{\mathrm{aud}}}

matches the information-theoretic necessity of audits. Empirically, \ESA\ recovers the ground truth when

80\%

of the social layer is adversarial, a regime in which median- and mean-based robust baselines fail.

Majid Ghasemi, Mark Crowley

Department of Electrical & Computer Engineering University of Waterloo, Canada

LLM Sycophancy Corruption Robustness Contextual Bandits

Mar 8, 2026

Beam-aware Kernelized Contextual Bandits for User Association and Beamforming in mmWave Vehicular Networks

Timely channel information is necessary for vehicles to determine both the serving base station (BS) and the beamforming vector, but frequent estimation of fast-fading mmWave channels incurs significant overhead. To address this challenge, we propose a Beam-aware Kernelized Contextual Upper Confidence Bound (BKC-UCB) algorithm that estimates instantaneous transmission rates without additional channel measurements by exploiting historical contexts such as vehicle location and velocity, together with past observed transmission rates. Specifically, BKC-UCB leverages kernel methods to capture the nonlinear relationship between context and transmission rate by mapping contexts into a reproducing kernel Hilbert space (RKHS), where linear learning becomes feasible. Rather than treating each beam as an independent arm, the beam index is embedded into the context, enabling BKC-UCB to exploit correlations among beams to accelerate convergence. Furthermore, an event-triggered information sharing mechanism is incorporated into BKC-UCB, enabling information exchange only when significant explorations are conducted to improve learning efficiency with limited communication overhead.

Xiaoyang He, Manabu Tsukada

Graduate School of Electronics and Communication Engineering, Sun Yat-sen University, China · Graduate School of Information Science and Technology, The University of Tokyo, Japan

Wireless Communications Wireless Resource Allocation Contextual Bandits V2X Communication

Mar 6, 2026

Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Bound

In contextual bilateral trade under full feedback, the posted price does not affect which valuations are observed. We show that in this model such action-independent feedback removes the polynomial adaptation penalty familiar from heavy-tailed bandits: fully parameter-free algorithms attain the oracle minimax

T

-exponents up to logarithmic factors, with no knowledge of the moment order

p \in (1,2)

or its scale

σ_p

, and -- in the nonparametric case -- none of the effective Hölder smoothness

β\in (0,1]

. The statistic that makes model selection possible is a paired squared-loss difference, whose noise-square term cancels exactly, leaving noise damped by the candidate gap. The resulting bilateral-trade regret rates are new. Trader valuations have bounded conditional densities and heavy tails -- finite

p

-th moments for some

p \in (1,2)

, with possibly infinite variance. An epoch-based algorithm with truncated means achieves regret

\widetilde{O}(T^{(2-p)/p})

in the parametric model and

\widetilde{O}(T^{1-2β(p-1)/(βp + d(p-1))})

when the market value function is

β

-Hölder, with matching

Ω(\cdot)

lower bounds -- under a mild nondegeneracy condition -- via Assouad's method and a fixed-support mixture construction -- characterizing the minimax rate in

T

up to logarithmic factors over the effective smoothness range

β\in (0,1]

, interpolating between the classical nonparametric rate at

p{=}2

and the trivial linear rate as

p \to 1^+

. The enabling structural step extends the self-bounding property of Bachoc et al. (ICML 2025) from bounded to real-valued valuations: within our conditionally independent, conditionally centered noise model, bounded conditional densities and finite first moments suffice for the expected regret of any price

π

to satisfy

\mathbb{E}[g(m,V,W) - g(π,V,W)] \le L|m-π|^2

-- no second moment is needed.

Hangyi Zhao

Minimax Regret Regret Minimization Contextual Bandits

Mar 6, 2026

Adapter-Augmented Bandits for Online Multi-Constrained Multi-Modal Inference Scheduling

Multi-modal large language model (MLLM) inference scheduling enables strong response quality under practical and heterogeneous budgets, beyond what a homogeneous single-backend setting can offer. Yet online MLLM task scheduling is nontrivial, as requests vary sharply in modality composition and latent reasoning difficulty, while execution backends incur distinct, time-varying costs due to system jitter and network variation. These coupled uncertainties pose two core challenges: deriving semantically faithful yet scheduling-relevant multi-modal task representations, and making low-overhead online decisions over irreversible multi-dimensional budgets. Accordingly, we propose M-CMAB (Multi-modal Multi-constraint Contextual Multi-Armed Bandit), a multi-adapter-enhanced MLLM inference scheduling framework with three components: (i) a CLS-attentive, frozen-backbone Predictor that extracts compact task representations and updates only lightweight adapters for action-specific estimation; (ii) a primal-dual Constrainer that maintains online Lagrange multipliers to enforce long-horizon constraints via per-round objectives; and (iii) a two-phase Scheduler that balances exploration and exploitation under irreversible budgets. We establish a regret guarantee under multi-dimensional knapsack constraints. On a composite multimodal benchmark with heterogeneous backends, M-CMAB consistently outperforms state-of-the-art baselines across budget regimes, achieving up to 14.18% higher reward and closely tracking an oracle-aided upper bound. Codes are available at https://anonymous.4open.science/r/M2CMAB/.

Xianzhi Zhang, Yue Xu, Yinlin Zhu +4

School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, 510006, China · School of Computing, Macquarie University, NSW 2109, Australia

LLM Inference Scheduling Multi-Armed Bandits Contextual Bandits Multimodal Large Language Models Combinatorial Multi-Armed Bandits

Mar 6, 2026

Structured Exploration vs. Generative Flexibility: A Field Study Comparing Bandit and LLM Architectures for Personalised Health Behaviour Interventions

Behaviour Change Techniques (BCTs) are central to digital health interventions, yet selecting and delivering effective techniques remains challenging. Contextual bandits enable statistically grounded optimisation of BCT selection, while Large Language Models (LLMs) offer flexible, context-sensitive message generation. We conducted a 4-week study on physical activity motivation (N=54; 9 post-study interviews) that compared five daily messaging approaches: random templates, contextual bandit with templates, LLM generation, hybrid bandit+LLM, and LLM with interaction history. LLM-based approaches were rated substantially more helpful than templates, but no significant differences emerged among LLM conditions. Unexpectedly, bandit optimisation for BCTs selection yielded no additional perceived helpfulness compared with LLM-only approaches. Unconstrained LLMs focused heavily on a single BCT, whereas bandit systems enforced systematic exploration-exploitation across techniques. Quantitative and qualitative findings suggest contextual acknowledgement of user input drove perceived helpfulness. We contribute design suggestions for reflective AI health behaviour change systems that address a trade-off between structured exploration and generative autonomy.

Dominik P. Hofer, Haochen Song, Rania Islambouli +5

Ludwig Boltzmann Institute for Digital Health and Prevention, Salzburg, Austria · University of Toronto, Toronto, Ontario, Canada · Stanford University, Stanford, California, United States of America

Personalized Language Models Contextual Bandits

Mar 4, 2026

Online Learning for Multi-Layer Hierarchical Inference under Partial and Policy-Dependent Feedback

Hierarchical inference systems route tasks across multiple computational layers, where each node may either finalize a prediction locally or offload the task to a node in the next layer for further processing. Learning optimal routing policies in such systems is challenging: inference loss is defined recursively across layers, while feedback on prediction error is revealed only at a terminal oracle layer. This induces a partial, policy-dependent feedback structure in which observability probabilities decay with depth, causing importance-weighted estimators to suffer from amplified variance. We study online routing for multi-layer hierarchical inference under long-term resource constraints and terminal-only feedback. We formalize the recursive loss structure and show that naive importance-weighted contextual bandit methods become unstable as feedback probability decays along the hierarchy. To address this, we develop a variance-reduced EXP4-based algorithm integrated with Lyapunov optimization, yielding unbiased loss estimation and stable learning under sparse and policy-dependent feedback. We provide regret guarantees relative to the best fixed routing policy in hindsight and establish near-optimality under stochastic arrivals and resource constraints. Experiments on large-scale multi-task workloads demonstrate improved stability and performance compared to standard importance-weighted approaches.

Haoran Zhang, Seohyeon Cha, Hasan Burhan Beytur +3

Department of Electrical and Computer Engineering, The University of Texas at Austin · DEVCOM Army Research Laboratory

Adaptive Model Routing Contextual Bandits Cost-Aware Inference Stochastic Optimization

Mar 4, 2026

Steering Frozen LLMs: Adaptive Social Alignment via Online Prompt Routing

Large language models (LLMs) are typically governed by post-training alignment (e.g., RLHF or DPO), which yields a largely static policy during deployment and inference. However, real-world safety is a full-lifecycle problem: static defenses degrade against evolving jailbreak behaviors, and fixed weights cannot adapt to pluralistic, time-varying safety norms. This motivates inference-time governance that steers behavior without costly retraining. To address this, we introduce the Consensus Clustering LinUCB Bandit (CCLUB), a unified framework for adaptive social alignment via system-prompt routing. CCLUB employs a conservative consensus clustering mechanism: it pools data only within the intersection of utility and safety similarity graphs, effectively preventing unsafe generalization across semantically proximal but risk-divergent contexts. Our theoretical analysis yields a sublinear regret guarantee, demonstrating near-optimal performance of CCLUB. Extensive experiments validate that CCLUB outperforms strong baselines, achieving a 10.98% improvement in cumulative reward and a 14.42% reduction in the average suboptimality gap.

Zeyu Zhang, Xiangxiang Dai, Ziyi Han +2

The Chinese University of Hong Kong · University of Washington

LLM Alignment LLM Safety Alignment Inference-Time Language Model Alignment Contextual Bandits

Mar 4, 2026

Inverse Contextual Bandits without Rewards: Learning from a Non-Stationary Learner via Suffix Imitation

We study the Inverse Contextual Bandit (ICB) problem, in which a learner seeks to optimize a policy while an observer, who cannot access the learner's rewards and only observes actions, aims to recover the underlying problem parameters. During the learning process, the learner's behavior naturally transitions from exploration to exploitation, resulting in non-stationary action data that poses significant challenges for the observer. To address this issue, we propose a simple and effective framework called Two-Phase Suffix Imitation. The framework discards data from an initial burn-in phase and performs empirical risk minimization using only data from a subsequent imitation phase. We derive a predictive decision loss bound that explicitly characterizes the bias-variance trade-off induced by the choice of burn-in length. Despite the severe information deficit, we show that a reward-free observer can achieve a convergence rate of

\tilde O(1/\sqrt{N})

, matching the asymptotic efficiency of a fully reward-aware learner. This result demonstrates that a passive observer can effectively uncover the optimal policy from actions alone, attaining performance comparable to that of the learner itself.

Yuqi Kong, Xiao Zhang, Weiran Shen

Gaoling School of Artificial Intelligence, Renmin University of China

Contextual Bandits Imitation Learning

Feb 23, 2026

No One Size Fits All: QueryBandits for Hallucination Mitigation

Advanced reasoning capabilities in Large Language Models (LLMs) have led to more frequent hallucinations; yet most mitigation work focuses on open-source models for post-hoc detection and parameter editing. The dearth of studies focusing on hallucinations in closed-source models is especially concerning, as they constitute the vast majority of models in institutional deployments. We introduce QueryBandits, a model-agnostic contextual bandit framework that adaptively learns online to select the optimal query-rewrite strategy by leveraging an empirically validated and calibrated reward function. Across 16 QA scenarios, our top QueryBandit (Thompson Sampling) achieves an 87.5% win rate over a No-Rewrite baseline and outperforms zero-shot static policies (e.g., Paraphrase or Expand) by 42.6% and 60.3%, respectively. Moreover, all contextual bandits outperform vanilla bandits across all datasets, with higher feature variance coinciding with greater variance in arm selection. This substantiates our finding that there is no single rewrite policy optimal for all queries. We also discover that certain static policies incur higher cumulative regret than No-Rewrite, indicating that an inflexible query-rewriting policy can worsen hallucinations. Thus, learning an online policy over semantic features with QueryBandits can shift model behavior purely through forward-pass mechanisms, enabling its use with closed-source models and bypassing the need for retraining or gradient-based adaptation.

Nicole Cho, William Watson, Alec Koppel +2

JPMorgan AI Research, New York, NY, USA

LLM Hallucination Mitigation Query Reformulation Contextual Bandits

Feb 11, 2026

A Jointly Efficient and Near-Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

We consider heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions and propose HCW-GLB-OMD, a simple algorithm that combines an online mirror descent (OMD)-based estimator with Hessian-based confidence weights. Although both components are well studied, establishing guarantees for the combined algorithm requires a nontrivial analysis. We establish a corruption-robust confidence sequence using technical tools not required in prior analyses, including a weighted likelihood supermartingale and a self-bounding argument. For the regret analysis, we derive a new Hessian potential lemma to handle the interaction between adversarial corruption and adaptive confidence weighting. For self-concordant GLMs, we prove a high-probability regret bound of

\widetilde{\mathcal{O}}\bigl( d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d(1+κ)(C\vee1) \bigr)

, where

\dotμ_{t,\star}

is the slope of

μ

at the optimal arm at time

t

,

g(τ_t)

is the observed dispersion,

g_{\max}=\max_t g(τ_t)

,

κ

is the worst-case inverse slope of

μ

, and

C

is the corruption budget. The algorithm attains this bound with one OMD update per round and

\mathcal{O}(d^2)

storage. We complement this guarantee with matching lower bounds for the leading

\sqrt{T}

term and, up to

κ

, the

dC

corruption term.

Sanghwa Kim, Junghyun Lee, Se-Young Yun

Kim Jaechul Graduate School of AI, KAIST Seoul 02455, Republic of Korea

Multi-Armed Bandits Online Mirror Descent Robust Multi-Armed Bandits Corruption Robustness Contextual Bandits Generalized Linear Models+1

Feb 10, 2026

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits

We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that efficiently reduces contextual bandit learning with general reward function approximation to offline regression. The framework allows near-optimal regret for contextual bandits with large action spaces with

O(\log T)

calls to an offline regression oracle over

T

rounds, and makes

O(\log\log T)

calls when

T

is known. The design of OE2D algorithm generalizes Falcon~\citep{simchi2022bypassing} and its linear reward version~\citep[][Section 4]{xu2020upper} in that it finds an action distribution that we term ``exploitative F-design'' that simultaneously guarantees low regret and good coverage, striking a balance between exploration and exploitation. Central to our regret analysis is a new complexity measure, the Decision-Offline Estimation Coefficient (DOEC), which we show is small in many settings, including bounded Eluder dimension per-context and the smoothed regret setting. We also establish a relationship between DOEC and Decision Estimation Coefficient (DEC)~\citep{foster2021statistical}, bridging the design principles of offline- and online-oracle efficient contextual bandit algorithms for the first time.

Hao Qin, Chicheng Zhang

The University of Arizona

Exploration-Exploitation Tradeoff Contextual Bandits Offline-to-Online Contextual Bandits

Feb 3, 2026

COBALT: Contextual Bandit Learning with Offline Trajectories for Multi-Turn Code Generation

Training large language models (LLMs) for multi-turn code generation typically relies on online reinforcement learning (RL), in which models learn from repeatedly generated online rollouts. Although effective, online RL can be costly and unstable. In this paper, we present contextual bandit learning with offline trajectories (COBALT), a simple method that reuses offline multi-turn trajectories to efficiently train LLMs for multi-turn code generation. Building on the observation that multi-turn code generation is a one-step recoverable Markov decision process, COBALT first collects code generation trajectories using a reference LLM and divides them into partial trajectories. Then, during online bandit learning, the LLM is trained to complete each partial trajectory through single-step code generation. On LiveCodeBench, COBALT substantially improves R1-Distill 8B and Qwen3 8B by up to 9.0 and 6.2 absolute Pass@1 points and matches the performance of two multi-turn online RL baselines using GRPO and VeRPO. We also perform a perturbation-based analysis of in-context reward hacking and show that Cobalt can improve robustness to misleading execution feedback. Overall, our results demonstrate that Cobalt is a promising solution for multi-turn code generation. Our code and data are available at https://github.com/OSU-NLP-Group/cobalt.

Ziru Chen, Dongdong Chen, Ruinan Jin +3

The Ohio State University. · Microsoft.

Code Generation RL for Code Generation Contextual Bandits Offline RL

Feb 2, 2026

Learning to Route and Schedule LLMs from User Retrials via Contextual Queueing Bandits

Explosive demands for LLMs often cause user queries to accumulate in server queues, requiring efficient routing (query-LLM matching) and scheduling (query prioritization) mechanisms. Several online algorithms are being deployed, but they overlook the following two key challenges inherent to conversational LLM services: (1) unsatisfied users may retry queries, increasing the server backlog, and (2) requests for

explicit" feedback, such as ratings, degrade user experiences. In this paper, we develop a joint routing and scheduling algorithm that leverages

implicit" feedback inferred from user retrial behaviors. The key idea is to propose and study the framework of contextual queueing bandits with multinomial logit feedback (CQB-MNL). CQB-MNL models query retrials, as well as context-based learning for user preferences over LLMs. Our algorithm, anytime CQB (ACQB), achieves efficient learning while maintaining queue stability by combining Thompson sampling with forced exploration at a decaying rate. We show that ACQB simultaneously achieves a cumulative regret of

\widetilde{\mathcal{O}}(\sqrt{t})

for routing and a queue length regret of

\widetilde{\mathcal{O}}(t^{-1/4})

for any large

t

. For experiments, we refine query embeddings via contrastive learning while adopting a disjoint parameter model to learn LLM-specific parameters. Experiments on synthetic data, offline routing datasets (SPROUT, EmbedLLM, and RouterBench), and real user conversation logs (WildChat-1M) confirm that our methods improve routing, scheduling, and queue stability against strong online and offline-trained baselines.

Seoungbin Bae, Junyoung Son, Dabeen Lee

Department of Industrial & Systems Engineering, KAIST · Graduate School of Data Science, KAIST · Department of Mathematical Sciences, Seoul National University

LLM Serving LLM Routing Contextual Bandits LLM Request Scheduling

Oct 30, 2025

Empirical Bayesian Multi-Bandit Learning

Multi-task learning in contextual bandits has attracted significant research interest due to its potential to enhance decision-making across multiple related tasks by leveraging shared structures and task-specific heterogeneity. In this article, we propose a novel hierarchical Bayesian framework for learning in various bandit instances. This framework captures both the heterogeneity and the correlations among different bandit instances through a hierarchical Bayesian model, enabling effective information sharing while accommodating instance-specific variations. Unlike previous methods that overlook the learning of the covariance structure across bandits, we introduce an empirical Bayesian approach to estimate the covariance matrix of the prior distribution. This enhances both the practicality and flexibility of learning across multi-bandits. Building on this approach, we develop two efficient algorithms: ebmTS (Empirical Bayesian Multi-Bandit Thompson Sampling) and ebmUCB (Empirical Bayesian Multi-Bandit Upper Confidence Bound), both of which incorporate the estimated prior into the decision-making process. We provide the frequentist regret upper bounds for the proposed algorithms, thereby filling a research gap in the field of multi-bandit problems. Extensive experiments on both synthetic and real-world datasets demonstrate the superior performance of our algorithms, particularly in complex environments. Our methods achieve lower cumulative regret compared to existing techniques, highlighting their effectiveness in balancing exploration and exploitation across multi-bandits.

Xia Jiang, Rong J. B. Zhu

Fudan University, Institute of Science and Technology for Brain-inspired Intelligence, Shanghai, People’s Republic of China

Contextual Bandits Empirical Bayes Hierarchical Bayesian Modeling

Oct 21, 2025

Learning Peer Influence Probabilities with Linear Contextual Bandits

In networked environments, it is common for users to share recommendations about content, products, services, and possible courses of action. Whether these recommendations are accepted and acted upon is highly context-dependent, influenced by the characteristics of the sender and recipient, the nature of their relationship, the attributes of the recommended item, and the communication context. Consequently, probabilities of peer influence exhibit substantial heterogeneity across individuals and settings. Accurate estimation of these probabilities is key to understanding information diffusion processes and to improving the effectiveness of viral marketing strategies. However, learning these probabilities from data is challenging; static data may capture correlations between peer recommendations and peer actions but fails to reveal influence relationships. Online learning algorithms can learn these probabilities from interventions but either waste resources by learning from random exploration or optimize for rewards, thus favoring exploration of the space with higher influence probabilities. In this work, we study learning peer influence probabilities under a contextual linear bandit framework. We show that a fundamental trade-off can arise between regret minimization and estimation error, characterize all achievable rate pairs, and propose an uncertainty-guided exploration algorithm that, by tuning a parameter, attains any pair within this trade-off. Our experiments on semi-synthetic network datasets show the advantages of our method over static methods and contextual bandits that ignore this trade-off.

Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena Zheleva

University of Illinois Chicago, Chicago, USA · École Polytechnique Fédérale de Lausanne, Switzerland

Multi-Armed Bandits Contextual Bandits

Oct 12, 2025

Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits

We provide a unified algorithmic framework for ensemble sampling in nonlinear contextual bandits and develop corresponding regret bounds for two most common nonlinear contextual bandit settings: Generalized Linear Model Ensemble Sampling (GLM-ES) for generalized linear contextual bandits and Neural Ensemble Sampling (Neural-ES) for neural contextual bandits. Both methods maintain multiple estimators for the reward model parameters via maximum likelihood estimation on randomly perturbed data. We prove high-probability frequentist regret bounds of

\widetilde{\mathcal{O}}(d^{3/2} \sqrt{T} + d^{4})

for GLM-ES and

\widetilde{\mathcal{O}}(\widetilde{d}^{3/2} \sqrt{T})

for Neural-ES, where

d

is the dimension of feature vectors,

\widetilde{d}

is the effective dimension of a neural tangent kernel (NTK) matrix and

T

is the number of rounds. The regret bound of GLM-ES matches the state-of-the-art result of randomized exploration algorithms in generalized linear bandit setting. In the theoretical analysis, we introduce techniques that address challenges specific to nonlinear models. Practically, we remove fixed-time horizon assumption by developing anytime versions of our algorithms, suitable when

T

is unknown. Finally, we empirically evaluate GLM-ES, Neural-ES and their anytime variants, demonstrating strong performance. Overall, our results establish ensemble sampling as a provable and practical randomized exploration approach for nonlinear contextual bandits.

Jiazheng Sun, Weixin Wang, Pan Xu

Duke University

Ensemble Learning Contextual Bandits Generalized Linear Models Generalized Linear Bandits

Oct 8, 2025

Best-of-Both Worlds for linear contextual bandits with paid observations

We study linear contextual bandits with paid observations, where at each round the learner observes a context, selects an action, and may pay a fixed cost to observe feedback from a subset of arms. We propose two Follow-the-Regularized-Leader algorithms with Best-of-Both-Worlds guarantees. The first, Agg-SPB, extends the SPB-matching framework of Tsuchiya and Ito (2024) by aggregating context-dependent stability terms, achieving the characteristic

T^{2/3}

adversarial regret rate and logarithmic dependence on

T

in stochastic environments. The second, CE-SPB, combines arm-dependent observation probabilities with an entropy-adaptive learning rate inspired by Kuroki et al. (2024). It achieves an entropy-adaptive

\widetilde{O}(T^{2/3})

adversarial guarantee and polylogarithmic stochastic regret, while avoiding the minimum-context-mass dependence arising in the stochastic analysis of Agg-SPB. Both algorithms further extend to corrupted stochastic environments with explicit corruption-dependent guarantees. These results establish that logarithmic stochastic regret is compatible with the

T^{2/3}

adversarial regime for linear contextual bandits with paid observations, while highlighting a tradeoff between sharper horizon dependence in stochastic settings and path-dependent matching without explicit minimum-context-mass dependence.

Nathan Boyer, Dorian Baudry, Patrick Rebeschini

ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford

Multi-Armed Bandits Follow-the-Regularized-Leader Contextual Bandits Adversarial Bandits Linear Contextual Bandits