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.

May 25, 2026

A Context Augmented Multi-Play Multi-Armed Bandit Algorithm for Fast Channel Allocation in Opportunistic Spectrum Access

We study the restless contextual multi-play multi-armed bandit (MP-MAB) problem for channel allocation in the opportunity spectrum access (OSA) scenario. Most existing MP-MAB methods are impractical for real-world OSA systems as they assume many ideal conditions, incur a heavy computational cost, and most importantly, ignore the impact of channel noise which is directly related to the quality of service. In this study, we embody this impact by modeling channel noise as a perturbation of the arm's reward function in MP-MAB. As there is an implicit correlation between channel state information and channel noise, we take the former as a context for MP-MAB to present the perturbation caused by the latter. We investigate two types of correlation between the context and the perturbation -- linear and nonlinear, and derive two index policies, respectively. These policies learn the correlations through a linear model and a neural network, and use estimated noise value to adjust the upper confidence bound. Numerical experiments demonstrate that the proposed policies can achieve lower regret and select sub-optimal arms in a more reasonable way.

Ruiyu Li, Guangxia Li, Xiao Lu +2

School of Computer Science and Technology, Xidian University, China · 2Research and Development, Ericsson, Canada · 3Hainayun IoT Technology Ltd, China

Multi-Armed Bandits Robust Multi-Armed Bandits Wireless Resource Allocation Contextual Bandits

May 24, 2026

Active Learning for Stochastic Contextual Linear Bandits

A key goal in stochastic contextual linear bandits is to efficiently learn a near-optimal policy. Prior algorithms for this problem learn a policy by strategically sampling actions but naively (passively) sampling contexts from the underlying context distribution. However, in many practical scenarios -- including online content recommendation, survey research, and clinical trials -- practitioners can actively sample or recruit contexts based on prior knowledge of the context distribution. Despite this potential for active learning, the role of strategic context sampling in stochastic contextual linear bandits is underexplored. We propose an algorithm that learns a near-optimal policy by strategically sampling rewards of context-action pairs. We prove instance-dependent theoretical guarantees demonstrating that our active context sampling strategy can improve over the minimax rate by up to a factor of

\sqrt{d}

, where

d

is the linear dimension. We show empirically that our algorithm reduces the number of samples needed to learn a near-optimal policy, in tasks such as warfarin dose prediction and joke recommendation.

Emma Brunskill, Ishani Karmarkar, Zhaoqi Li

Stanford University

Active Learning Adaptive Sampling Contextual Bandits Policy Learning Linear Contextual Bandits

May 22, 2026

Human-in-the-Loop Contextual Bandits for Short-Term Rental Dynamic Pricing: Structural Equivalence of Historical Warm-Up and Approval-Gated Live Learning

Dynamic pricing in short-term rental (STR) markets presents a distinctive challenge for online learning algorithms: pricing decisions carry significant financial risk, operators require explainability, and market feedback is sparse (one booking outcome per listed night). We introduce the Human-in-the-Loop Gated Bandit (HITL-GB) framework, in which a contextual bandit algorithm generates price recommendations but a human agent retains authority to accept, modify, or reject each recommendation before it is applied. We show that under this approval constraint, historical pricing data -- collected under a prior deterministic policy -- is structurally equivalent to on-policy warm-up data for initialising the bandit's posterior, bypassing the weeks-to-months cold-start period that renders pure online bandit learning impractical in sparse-feedback markets. We formalise the approval-gated reward signal, derive a regularised ridge-regression warm-up procedure from historical episodes, and validate the approach on real STR production data (anonymised urban market, 2 rooms, April 2022 -- April 2026, 1,461 nightly pricing episodes). Our warm-up procedure compresses effective cold-start from ~150 episodes to ~30 episodes when initialising agents from the Hierarchical Factored Thompson Sampling (HF-TS) family. We further argue that the structural equivalence result is domain-agnostic: any high-stakes domain where human approval is legally or operationally required -- including clinical drug dosing, credit origination, content moderation, and radiological diagnosis -- satisfies the same conditions and benefits from the same warm-up strategy. In regulated industries, mandatory human oversight is thus a statistical asset rather than a deployment constraint.

Oleg Miroshnichenko

Contextual Bandits Dynamic Pricing

May 19, 2026

Active Context Selection Improves Simple Regret in Contextual Bandits

We study the contextual multi-armed bandit problem with a finite context space (a.k.a. subpopulations), where the learner recommends a best action for each context and is evaluated by context-weighted simple regret. Our guarantees are worst-case over the reward distributions, while remaining instance-dependent with respect to the context distribution vector

p

. Akin to experimental design problems where the population of interest is fixed but the sampled subpopulation can be controlled, we allow the learner to actively choose which context to sample from. For a known

p

, we characterize tight regret rates: passive sampling where contexts are randomly revealed achieves regret of order

\sqrt{n/T \, \lVert p \rVert_{1/2}}

, whereas active sampling with allocation

q_j \propto p_j^{2/3}

achieves the tight rate

\sqrt{n/T} \, \lVert p \rVert_{2/3}

. The resulting improvement can be as large as

Θ(k^{1/4})

, where

k

is the number of contexts. We further extend the analysis to budgeted active sampling, characterize the corresponding tight rate, and identify when a limited active budget suffices to recover the fully active rate. When

p

is unknown, we propose the Explore-Explore-Then-Commit (EETC) algorithm, which optimally balances estimating the context distribution and the time to switch to active allocation, such that for large horizons, it matches the known-

p

active rate up to constants. Experiments on synthetic and real-world data support our theoretical findings.

Mohammad Shahverdikondori, Jalal Etesami, Negar Kiyavash

College of Management of Technology, EPFL · Department of Computer Science, TU Munich

Multi-Armed Bandits Best-Arm Identification Adaptive Sampling Regret Minimization Contextual Bandits

May 18, 2026

Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity

Many bandit deployments (recommendation, clinical dosing, ad targeting) share two facts prior work handles only in isolation: rewards live on a low-dimensional latent subspace, and that subspace drifts. Stationary low-rank bandits exploit rank but break under subspace change; non-stationary linear bandits adapt to drift but pay ambient rate

\widetilde{O}(d\sqrt{T})

. We study piecewise-stationary low-rank linear contextual bandits with scalar feedback:

θ_t = B_k^\star w_t

with rank-

r

factor

B_k^\star\in\mathbb{R}^{d\times r}

constant within each of

K

unknown segments and able to shift at boundaries. Our results are tight along three axes. (i) Identification boundary. With single-play scalar rewards, the moving subspace is recoverable through quadratic functionals of rewards iff three probe-side conditions hold: known noise variance, bounded state-noise coupling, and full-dimensional probe support. Each is necessary in the unrestricted-second-moment problem, and jointly they are sufficient, characterizing the boundary of the solvable region. (ii) Algorithm and dynamic regret. SPSC interleaves isotropic probes with windowed projected ridge-UCB exploitation inside the learned

r

-dimensional subspace; a CUSUM-style variant discovers segment boundaries online. The costed dynamic regret is

\widetilde{O}(r\sqrt{T})+\widetilde{O}(T^{2/3})+O(W\,V_{\mathrm{in}})

, replacing the ambient

d\sqrt{T}

rate with the intrinsic rank. (iii) Empirics. On eleven benchmarks spanning synthetic, UCI/MovieLens, semi-synthetic clinical, and ZOZOTOWN production-log data, SPSC outperforms non-stationary and low-rank baselines whenever

d-r\gtrsim T^{1/6}

, matching the analytical crossover. To our knowledge, this is the first work to characterize the identification boundary and attain the intrinsic-rank dynamic-regret rate in this setting.

Hamed Khosravi, Xiaoming Huo

H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332

Multi-Armed Bandits Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

May 18, 2026

Offline Contextual Bandits in the Presence of New Actions

Automated decision-making algorithms drive applications such as recommendation systems and search engines. These algorithms often rely on off-policy contextual bandits or off-policy learning (OPL). Conventionally, OPL selects actions that maximize the expected reward from an existing action set. However, in many real-world scenarios, actions, such as news articles or video content, change continuously, and the action space evolves over time after data collection. We define actions introduced after deploying the logging policy as new actions and focus on OPL with new actions. Existing OPL methods identify optimal actions from the existing set effectively but cannot learn and select new actions because no relevant data are logged. To address this limitation, we propose a new OPL method that leverages action features. We first introduce the Local Combination PseudoInverse (LCPI) estimator for the policy gradient, generalizing the PseudoInverse estimator initially proposed for off-policy evaluation of slate bandits. LCPI controls the trade-off between reward-modeling condition and the condition for data collection regarding the action features, capturing the interaction effects among different dimensions of action features. Furthermore, we propose a generalized algorithm called Policy Optimization for Effective New Actions (PONA), which integrates LCPI, a component specialized for new action selection, with Doubly Robust (DR), which excels at learning within existing actions. We define PONA as a weighted sum of the LCPI and DR estimators, optimizing both the selection of existing and new actions, and allowing the proportion of new action selections to be adjusted by the weight parameter. Through extensive experiments, we demonstrate that PONA efficiently selects new actions while maintaining the overall policy performance as opposed to most existing methods that cannot select new actions.

Ren Kishimoto, Tatsuhiro Shimizu, Kazuki Kawamura +6

Institute of Science Tokyo · Yale University · Sony Group Corporation +1

Offline-to-Online Contextual Bandits Off-Policy Evaluation Policy Optimization Contextual Bandits

May 17, 2026

Don't Let Bandit Feedback Pull Continual LLM-Recommender Updates Off Target

Generative LLM-based recommenders (LLM-Rec) require continual post-deployment updates, yet deployment logs provide only policy-shaped contextual bandit feedback: outcomes are observed solely for items exposed by a prior serving policy, inducing exposure bias and yielding partial, asymmetric signals consisting of relatively reliable positive responses and ambiguous no-responses. We propose an Anchored Bandit Policy Optimization (ABPO) framework for continual LLM-Rec updates that combines group-relative policy optimization (GRPO) with explicit treatment of exposure bias and feedback ambiguity. Specifically, we insert the exposed recommendation as a logged anchor into each GRPO rollout group, so that group-relative normalization is calibrated against the action actually exposed by the prior policy rather than against newly sampled rollouts alone. Because both positive- and no-responses are observed only through prior-policy exposure, we apply self-normalized inverse propensity scoring to the fixed anchor for both feedback types to correct for policy mismatch. At the same time, we treat the two feedback types asymmetrically in reliability: positive responses provide relatively direct endorsement signals, whereas no-responses remain ambiguous because they may reflect either true disinterest or unobserved external factors. To avoid overly aggressive updates from ambiguous no-responses, we temper their penalties with self-certainty, using the model's output-token confidence as a verifier-free reliability signal. Across five domains from Amazon Reviews and MovieLens, our method yields consistent post-update gains in recommendation accuracy while mitigating prior-policy-induced exposure bias more effectively than prior baselines.

Taesan Kim, Hyeongjun Yun, Jaegul Choo +1

1SK Telecom · 2KAIST

Large Language Model-Based Recommendation Off-Policy RL Recommender Systems Continual Learning for LLMs Contextual Bandits RL Fine-Tuning+1

May 15, 2026

Pessimistic Risk-Aware Policy Learning in Contextual Bandits

We study risk-aware offline policy learning, aiming to learn a decision rule from logged data that is optimal under general risk criteria. This problem is crucial in high-stakes domains where online interaction is infeasible and adverse outcomes must be carefully controlled. However, existing literature on offline contextual bandits either centers on expected-reward criteria or restricts risk considerations to policy evaluation instead of optimization. In this work, we propose a unified distributional framework for optimizing Lipschitz-continuous risk functionals, a broad class of risk measures encompassing mean-variance, entropic risk, and conditional value-at-risk, among others. By developing novel empirical concentration inequalities for importance sampling-based distributional estimators, our analysis derives data-dependent suboptimality bounds with an

\tilde{\mathcal{O}}(1/\sqrt{n})

rate, without relying on restrictive uniform overlap assumptions. This rate is minimax optimal and matches that of risk-neutral offline policy optimization, indicating that optimizing general Lipschitz risk criteria incurs no additional statistical cost relative to the expected-reward.

Yilong Wan, Yuqiang Li, Xianyi Wu

Offline-to-Online Contextual Bandits Risk-Sensitive RL Contextual Bandits Statistical Learning Theory

May 14, 2026

Latency-Quality Routing for Functionally Equivalent Tools in LLM Agents

Tool-augmented LLM agents increasingly access the same tool type through multiple functionally equivalent providers, such as web-search APIs, retrievers, or LLM backends exposed behind a shared interface. This creates a provider-routing problem under runtime load: the router must choose among providers that differ in latency, reliability, and answer quality, often without gold labels at deployment time. We introduce LQM-ContextRoute, a contextual bandit router for same-function tool providers. Its key design is latency-quality matching: instead of letting low latency offset poor answers in an additive reward, the router ranks providers by expected answer quality per service cycle. It combines this capacity-aware score with query-specific quality estimation and LLM-as-judge feedback, allowing it to adapt online to both load changes and provider-quality differences. On the main web-search load benchmark, LQM-ContextRoute improves F1 by +2.18 pp over SW-UCB while staying on the latency-quality frontier. In a high-heterogeneity StrategyQA setting, LQM-ContextRoute avoids additive-reward collapse and improves accuracy by up to +18 pp over SW-UCB; on heterogeneous retriever pools, it improves NDCG by +2.91--+3.22 pp over SW-UCB. These results show that same-function tool routing benefits from treating latency as service capacity, especially when runtime pressure and provider-quality heterogeneity coexist.

Kexin Chu, Dawei Xiang, Wei Zhang

University of Connecticut

Tool-Augmented Language Model Agents LLM Tool Use LLM Agents Contextual Bandits LLM Agent Routing

May 13, 2026

Contextual Bandits for Resource-Constrained Devices using Probabilistic Learning

Contextual bandits (CB) are online sequential decision-making problems under partial feedback that underpin many adaptive services. There is a growing demand to deploy CB agents directly on-device, under strict constraints on memory, compute, and energy. However, standard linear CB algorithms are often impractical for resource-constrained devices with their unfavorable scaling in computational and memory costs. Recently, HD-CB, a CB approach based on hyperdimensional computing principles, has been proposed to model and solve CB problems by moving into high-dimensional spaces. HD-CB offers faster convergence, favorable scalability, and improves memory efficiency compared to linear CB algorithms. However, its learning rule is accumulation-based: the values of action vectors grow over time, requiring high precision. While periodic binarization can prevent overflow in low-precision components, it may discard important information about magnitudes and degrade decision quality. This paper introduces probabilistic HD-CB, a low-precision variant that replaces deterministic accumulation with a probabilistic update rule. At each step, only a random subset of vector components is updated, with a time-decaying update probability, and component values are constrained to a predefined range [-k,+k]. This approach enables low-precision components, prevents overflow without periodic binarization, and reduces the expected update cost in proportion to the fraction of updated components. Off-policy evaluation on standardized synthetic CB benchmarks using the Open Bandit Pipeline shows that probabilistic HD-CB consistently outperforms binarized HD-CB at equal precision, while approaching the performance of HD-CB with as few as 3 bits per component.

Marco Angioli, Kevin Johansson, Antonello Rosato +2

Sapienza University of Rome · Orebro University · Linkoping University +1

Hyperdimensional Computing Contextual Bandits Low-Bit Quantization On-Device Inference

May 13, 2026

Robust Sequential Experimental Design for A/B Testing

Experimental design has emerged as a powerful approach for improving the sample efficiency of A/B testing, yet existing designs rely critically on correctly specified models. We study robust sequential experimental design under model misspecification and develop a unified framework that covers both contextual bandit and dynamic settings. Theoretically, we prove that our design bounds the worst-case mean squared error of the estimated treatment effect. Empirically, we demonstrate the effectiveness of the proposed approach using synthetic and real-world datasets from a leading technology company.

Qianglin Wen, Xiangkun Wu, Chengchun Shi +4

Yunnan Key Laboratory of Statistical Modeling and Data Analysis, Yunnan University, Kunming, China · School of Mathematical Sciences, Zhejiang University, Hangzhou, China · Department of Statistics, London School of Economics and Political Science, London, United Kingdom +3

Causal Effect Estimation Model Misspecification Sequential Experimental Design A/b Testing Contextual Bandits

May 12, 2026

Multi-Task Representation Learning for Conservative Linear Bandits

This paper presents the Constrained Multi-Task Representation Learning (CMTRL) framework for linear bandits. We consider T linear bandit tasks in a d dimensional space, which share a common low-dimensional representation of dimension r, where r is much smaller than the minimum of d and T. Furthermore, tasks are constrained so that only actions meeting specific safety or performance requirements are allowed, referred to as conservative (safe) bandits. We introduce a novel algorithm, Safe-Alternating projected Gradient Descent and minimization (Safe-AltGDmin), to recover a low-rank feature matrix while satisfying the given constraints. Building on this algorithm, we propose a multi-task representation learning framework for conservative linear bandits and establish theoretical guarantees for its regret and sample complexity bounds. We presented experiments and compared the performance of our algorithm with benchmark algorithms.

Jiabin Lin, Shana Moothedath

Department of Computer Science and Technology, Qingdao University, China · Department of Electrical and Computer Engineering, Iowa State University, USA

Multi-Armed Bandits Multi-Task Learning Contextual Bandits

May 11, 2026

Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewards

We study contextual bandits with nonlinear and path-dependent rewards through a novel signature-transform-based approach. Leveraging the universal nonlinearity property of signatures, we approximate continuous path-dependent reward functionals by linear functionals in the signature space. This representation enables the use of efficient linear contextual bandit methods while preserving expressive sequential structure. Building on this framework, we propose DisSigUCB, a signature-based disjoint upper confidence bound (UCB) algorithm. Under boundedness and non-degeneracy assumptions, we prove a high-probability data-dependent sublinear regret bound of order

\tilde{\mathcal O}(\sqrt{(d+m)KT})

where

d

is the context dimension and

m

is the signature feature dimension. Synthetic experiments and numerical applications on temperature sensor monitoring, sleep-stage classification, and hospital nurse staffing demonstrate that DisSigUCB consistently outperforms classical linear and kernelized contextual bandit baselines in nonlinear and path-dependent settings.

Xin Guo, Grace He, Xinyu Li

University of California, Berkeley, Berkeley, CA · University of Oxford, Oxford, UK

Contextual Bandits UCB Algorithms

May 11, 2026

Learning to Sparsify Stochastic Linear Bandits

This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a

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

regret, where

d

is the dimension of the action vector and

T

is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a

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

α

-regret; for general compact sets lacking strong convexity, we establish a

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

α

-regret, where

α

pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments including an application to recommendation system.

Zhengmiao Wang, Ming Chi, Zhi-Wei Liu +2

School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China · Department of Electronics and Telecommunications, Politecnico di Torino, 10129 Torino, Italy

Multi-Armed Bandits Exploration-Exploitation Tradeoff Contextual Bandits

May 11, 2026

PFN-TS: Thompson Sampling for Contextual Bandits via Prior-Data Fitted Networks

Thompson sampling is a widely used strategy for contextual bandits: at each round, it samples a reward function from a Bayesian posterior and acts greedily under that sample. Prior-data fitted networks (PFNs), such as TabPFN v2+ and TabICL v2, are attractive candidates for this purpose because they approximate Bayesian posterior predictive distributions in a single forward pass. However, PFNs predict noisy future rewards, while Thompson sampling requires uncertainty over the latent mean reward function. We propose PFN-TS, a Thompson sampling algorithm that converts PFN posterior predictives into mean-reward samples using a subsampled predictive central limit theorem. The method estimates posterior variance from a geometric grid of

O(\log n)

dataset prefixes rather than the full

O(n)

predictive sequence used in previous predictive-sequence approaches, and reuses TabICL's cached representations across rounds. We prove consistency of the subsampled variance estimator and give a Bayesian regret bound that decomposes PFN-TS regret into exact posterior-sampling regret under the PFN prior plus approximation terms. Empirically, PFN-TS achieves the best average rank across nonlinear synthetic and OpenML classification-to-bandit benchmarks, remains competitive on linear and BART-generated rewards, and attains the highest estimated policy value in an offline mobile-health evaluation. Code is available at https://anonymous.4open.science/r/PFN_TS-36ED/.

Yan Shuo Tan, Kenyon Ng, Ruizhe Deng +3

National University of Singapore · Monash University · Renmin University of China +1

Thompson Sampling Prior-Data Fitted Networks Contextual Bandits

May 10, 2026

Optimal Regret for Single Index Bandits

We study the

\textit{single-index bandit}

problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function. This model extends linear and generalized linear bandits to a nonparametric setting, and is particularly relevant when the reward function is not known in advance. While optimal regret guarantees are known for monotone reward functions, the general non-monotone case remains poorly understood, with the best known bound being

\tilde{\mathcal{O}}(T^{3/4})

(under standard boundedness and Lipschitz assumptions on the reward function [Kang et al., 2025]). We close this gap by establishing the optimal regret for general single-index bandits. We propose a simple two-phase algorithm, namely, Zoomed Single Index Bandit with Upper Confidence Bound (

\texttt{ZoomSIB-UCB}

), that first estimates the projection direction via a normalized Stein estimator, and then reduces the problem to a one-dimensional bandit using discretization and finally use UCB. This approach achieves a regret of

\tilde{\mathcal{O}}(T^{2/3})

, and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of

\tildeΩ(T^{2/3})

, showing that the upper bound is essentially tight. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits. Moreover, the empirical results further demonstrate the effectiveness and robustness of our approach.

Devdan Dey, Sujoy Bhore, Avishek Ghosh

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Multi-Armed Bandits Single-Index Models Minimax Regret Regret Minimization Contextual Bandits

May 9, 2026

Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability

Kullback-Leibler (KL) regularization is ubiquitous in reinforcement learning algorithms in the form of reverse or forward KL. Recent studies have demonstrated

ε^{-1}

-type fast rates for decision making under reverse KL regularization, in contrast to the standard

ε^{-2}

-type sample complexity. However, for forward-KL-regularized objectives, existing statistical analyses are either not applicable or result in

\tilde{O}(ε^{-2})

slow rates. We take the first step towards addressing this problem via a streamlined analysis of forward-KL-regularized offline CBs. We give the first

\tilde{O}(ε^{-1})

upper bounds in tabular and general function approximation settings, both under notions of single-policy concentrability. In particular, our convex-analytical pipeline unifies these settings by exploiting the pessimism principle in a novel way and completely bypasses the proof routines in previous works based on the mean value theorem, which might be of independent interest. Moreover, we provide rate-optimal lower bounds, manifesting the tightness of our upper bounds in terms of statistical rates. Our lower bounds also demonstrate that the forward-KL-regularized sample complexity recovers the unregularized slow rate in the low-regularization regime, similarly to the reverse-KL regularization.

Qingyue Zhao, Kaixuan Ji, Heyang Zhao +1

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Offline-to-Online Contextual Bandits KL-Regularized RL Contextual Bandits Regularized RL

May 7, 2026

Constrained Contextual Bandits with Adversarial Contexts

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal

\mathsf{SquareCB}

algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most

U_T

, our algorithm achieves

O(\sqrt{KTU_T})

regret and

O(\sqrt{KTU_T}\log T)

cumulative expected cost, with high probability, improving upon the previous

O(T^{3/4})

type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.

Dhruv Sarkar, Abhishek Sinha

Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India

Contextual Bandits Adversarial Bandits

May 7, 2026

Optimal Contextual Pricing under Agnostic Non-Lipschitz Demand

We study contextual dynamic pricing with linear valuations and bounded-support agnostic noise, whose induced demand curve may be non-Lipschitz with arbitrary jumps and atoms. Such discontinuities break the cross-context interpolation arguments used by smooth-demand pricing algorithms, while the best previous method achieved only

\tilde O(T^{3/4})

regret. We propose Conservative-Markdown Redirect-UCB Pricing, a polynomial-time algorithm that combines randomized parameter estimation, conservative residual-grid probing, and confidence-based one-step redirection. Our algorithm achieves

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

optimal regret, matching the known lower bounds of Kleinberg and Leighton (2003) up to logarithmic factors and improving over the previous upper bound of Xu and Wang (2022). Under stochastic well-conditioned contexts, this closes the long-existing open regret gap in linear-valuation contextual pricing under agnostic non-Lipschitz noise distribution.

Jianyu Xu, Yu-Xiang Wang

Carnegie Mellon University Pittsburgh, PA 15213

Contextual Bandits UCB Algorithms Dynamic Pricing

May 3, 2026

Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions

We study linear dueling bandits in volatile environments characterized by the simultaneous presence of post-serving contexts, delayed feedback, and adversarial corruption. Feedback is subject to unknown stochastic or adversarial delays and a cumulative corruption budget

\mathcal{C}

. To address these challenges, we propose e RCDP-UCB, which integrates a learned approximator that predicts post-serving contexts from pre-serving information. It further employs an adaptive weighting strategy that clips feature vectors to mitigate the impact of corrupted and delayed observations simultaneously. Under standard regularity conditions and a parametric post-serving mapping, we rigorously establish that our algorithm is delay-regime-agnostic, achieving a regret upper bound of

\widetilde{\mathcal{O}}(d(\sqrt{T} + \mathcal{C} + \mathcal{D}))

, where

d

is the total feature dimension and

\mathcal{D}

encapsulates the delay complexity. Crucially, our analysis reveals an additive cost structure between corruption and delay, avoiding the multiplicative degradation typical of prior works. We further establish lower bounds that nearly match our upper bounds up to a

\sqrt{d}

factor for adversarial delays in the absence of post-serving contexts. Code is available at https://github.com/youngmin0oh/rcdp-public.

Youngmin Oh

InfiniTree, Republic of Korea

Multi-Armed Bandits Bandits with Delayed Feedback Contextual Bandits UCB Algorithms

May 1, 2026

Scaling Federated Linear Contextual Bandits via Sketching

In federated contextual linear bandits, high data dimensionality incurs prohibitive computation and communication costs: local agents perform

O(d^3)

-time determinant computation and upload

O(d^2)

parameters, making existing algorithms unscalable, where

d

is the dimension of data. To relieve these scaling bottlenecks, this paper proposes Federated Sketch Contextual Linear Bandits (FSCLB). On the computation side, FSCLB uses SVD to indirectly obtain the determinant required for communication, eliminating the prohibitive cost of direct determinant calculation and cutting complexity from

O(d^3)

to

O(l^2d)

per round, where

l< d

is the sketch size. On the communication side, FSCLB introduces a double-sketch strategy that reduces both upload and download costs from

O(d^2)

to

O(ld)

. Naively involving sketch update into federated contextual linear bandits can destroy the local increment and invalidate the asynchronous communication condition; FSCLB solves this by replacing the covariance matrix with the sketch matrix when deciding whether to communicate. Theoretically, FSCLB achieves a regret bound of

\widetilde{O} ((\sqrt{d}+\sqrt{M\varepsilon_l})\sqrt{lT})

, where

\varepsilon_l

is the upper bounded by the spectral tail of the covariance matrix; when

l

exceeds the rank of the covariance matrix, the bound simplifies to

\widetilde{O}(\sqrt{ldT})

, matching the optimal no-sketch regret. Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 % while sacrificing only a negligible amount of cumulative reward.

Hantao Yang, Hong Xie, Xutong Liu +1

University of Science and Technology of China · University of Washington Tacoma

Communication-Efficient Distributed Training Contextual Bandits Linear Contextual Bandits Federated Learning

Apr 30, 2026

Learning When to Remember: Risk-Sensitive Contextual Bandits for Abstention-Aware Memory Retrieval in LLM-Based Coding Agents

Large language model (LLM)-based coding agents increasingly rely on external memory to reuse prior debugging experience, repair traces, and repository-local operational knowledge. However, retrieved memory is useful only when the current failure is genuinely compatible with a previous one; superficial similarity in stack traces, terminal errors, paths, or configuration symptoms can lead to unsafe memory injection. This paper reframes issue-memory use as a selective, risk-sensitive control problem rather than a pure top-k retrieval problem. We introduce RSCB-MC, a risk-sensitive contextual bandit memory controller that decides whether an agent should use no memory, inject the top resolution, summarize multiple candidates, perform high-precision or high-recall retrieval, abstain, or ask for feedback. The system stores reusable issue knowledge through a pattern-variant-episode schema and converts retrieval evidence into a fixed 16-feature contextual state capturing relevance, uncertainty, structural compatibility, feedback history, false-positive risk, latency, and token cost. Its reward design penalizes false-positive memory injection more strongly than missed reuse, making non-injection and abstention first-class safety actions. In deterministic smoke-scale artifacts, RSCB-MC obtains the strongest non-oracle offline replay success rate, 62.5%, while maintaining a 0.0% false-positive rate. In a bounded 200-case hot-path validation, it reaches 60.5% proxy success with 0.0% false positives and a 331.466 microseconds p95 decision latency. The results show that, for coding-agent memory, the key question is not only which memory is most similar, but whether any retrieved memory is safe enough to influence the debugging trajectory.

Mehmet Iscan

PythaLab, Yildiz Technical University, Istanbul, Türkiye.

Selective Prediction AI Coding Agents LLM Agent Memory Contextual Bandits Agent Memory Management

Apr 29, 2026

The Bandit's Blind Spot: The Critical Role of User State Representation in Recommender Systems

With the increasing availability of online information, recommender systems have become an important tool for many web-based systems. Due to the continuous aspect of recommendation environments, these systems increasingly rely on contextual multi-armed bandits (CMAB) to deliver personalized and real-time suggestions. A critical yet underexplored component in these systems is the representation of user state, which typically encapsulates the user's interaction history and is deeply correlated with the model's decisions and learning. In this paper, we investigate the impact of different embedding-based state representations derived from matrix factorization models on the performance of traditional CMAB algorithms. Our large-scale experiments reveal that variations in state representation can lead to improvements greater than those achieved by changing the bandit algorithm itself. Furthermore, no single embedding or aggregation strategy consistently dominates across datasets, underscoring the need for domain-specific evaluation. These results expose a substantial gap in the literature and emphasize that advancing bandit-based recommender systems requires a holistic approach that prioritizes embedding quality and state construction alongside algorithmic innovation. The source code for our experiments is publicly available on https://github.com/UFSCar-LaSID/bandits_blind_spot.

Pedro R. Pires, Gregorio F. Azevedo, Rafael T. Sereicikas +2

Federal University of São Carlos Sorocaba, São Paulo, Brazil

User Modeling Recommender Systems Contextual Bandits State Representation Learning

Apr 28, 2026

Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making

Treatment allocation under budget constraints is a central challenge in digital advertising: advertisers must decide which users to show ads to while spending a limited budget wisely. The standard approach follows a two-stage offline pipeline - first collect historical data to estimate heterogeneous treatment effects (HTE), then solve a constrained optimization to allocate the budget. This works well with abundant data, but fails in cold-start settings such as new campaigns, new markets, or new customer segments where little historical data exists. We propose Budget-Constrained Causal Bandits (BCCB), an online framework that learns which users respond to ads while simultaneously spending the budget, making treatment decisions one user at a time. BCCB unifies three components into a single sequential process: learning individual-level ad effectiveness, exploring users whose response is uncertain, and pacing the budget over time. We evaluated on the Criteo Uplift dataset, a large-scale advertising dataset from a real randomized controlled trial. Our key finding is a data-efficiency crossover: offline methods require approximately 10,000 historical observations to produce reliable results, while BCCB operates effectively from the very first user. Furthermore, BCCB exhibits 3-5x lower performance variance between runs, making it more practical for real campaign planning. Among purely online methods, BCCB consistently outperforms standard Thompson Sampling, budgeted Thompson Sampling, and greedy HTE estimation across all budget levels tested.

Abhirami Pillai

utdallas

Multi-Armed Bandits Causal Effect Estimation Online Advertising Uplift Modeling Contextual Bandits Online Resource Allocation

Apr 27, 2026

Direction-Aware Offline-to-Online Learning in Linear Contextual Bandits

Many bandit systems are deployed with offline historical data, such as past logs from earlier policies. Using these data can reduce early online exploration when they remain informative for the online problem. When the offline and online environments differ, such data can be biased for the online problem. For linear (contextual) bandits, this bias is directional: offline data may be informative in some feature directions and misleading in others. However, prior work typically controls this gap through a known Euclidean bound on the model parameters, which we prove is too coarse: even with the offline parameter known, bias in a single unknown direction can force dimension-dependent regret. To address this challenge, we introduce a directional bias certificate

(M_{\mathrm{bias}},ρ)

that measures the offline-to-online gap through an

M_{\mathrm{bias}}

-induced norm and assigns different bias budgets to different directions. Building on this certificate, we propose Ellipsoidal-MINUCB, which augments the online learning with an offline-pooled branch that safely exploits historical data. When the certificate is known, we show that the algorithm matches the standard SupLinUCB rate in the worst case and improves when offline coverage aligns with low-bias directions. When the certificate is unknown, we estimate it adaptively from offline and accumulated online data and establish a corresponding regret guarantee. Numerical experiments support the theory and show gains in aligned regimes.

Zean Han, Ruihan Lin, Zezhen Ding +1

Department of Industrial Engineering and Decision Analytics The Hong Kong University of Science and Technology

Offline-to-Online Contextual Bandits Contextual Bandits UCB Algorithms Linear Contextual Bandits

Apr 24, 2026

Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions

We study the

K

-armed logistic bandit problem, where at each round, the agent observes

K

feature vectors associated with

K

actions. Existing approaches that achieve a rate-optimal

\tilde{\mathcal{O}}(\sqrt{dT})

regret bound rely heavily on context diversity assumptions, such as strict positivity of the minimum eigenvalue of a context covariance matrix. These assumptions, however, impose strong restrictions on the context process, as they rule out the situation where the context vectors are concentrated in a low-dimensional subspace. In this paper, we propose SupSplitLog, which, to the best of our knowledge, is the first algorithm for logistic bandits that achieves

\tilde{\mathcal{O}}(\sqrt{dT})

regret without any context diversity assumption. The key idea is to split the collected samples into two disjoint subsets when constructing estimators; one is used to compute an initial-point estimator, while the other is used to apply a Newton-type one-step correction procedure. The splitting rule is carefully designed to balance the accuracy requirements of the initial-point estimator and the one-step correction procedure. Moreover, SupSplitLog strictly improves on the existing algorithms in terms of the dependence on dimension

d

in the regret upper bound. Furthermore, SupSplitLog can be adapted simply to deduce a regret bound that grows with a data-dependent complexity measure, avoiding a direct dependence on

d

, which is favorable when the context vectors are concentrated in a low-dimensional subspace. We also provide experimental results that demonstrate numerically the superiority of our algorithm, validating the theoretical results.

Seoungbin Bae, Dabeen Lee

Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

Multi-Armed Bandits Contextual Bandits

Apr 21, 2026

Replicable Bandits with UCB based Exploration

We study replicable algorithms for stochastic multi-armed bandits (MAB) and linear bandits with UCB (Upper Confidence Bound) based exploration. A bandit algorithm is

ρ

-replicable if two executions using shared internal randomness but independent reward realizations produce the same action sequence with probability at least

1-ρ

. Prior approaches to this problem are elimination-based and, in linear bandits with infinitely many actions, rely on discretization, leading to suboptimal dependence on the dimension

d

and

ρ

. We develop optimistic alternatives for both settings. For stochastic multi-armed bandits, we propose RepUCB, a replicable batched UCB algorithm and show that it attains a regret

O\!\left(\frac{K^2\log^2 T}{ρ^2}\sum_{a:Δ_a>0}\left(Δ_a+\frac{\log(KT\log T)}{Δ_a}\right)\right)

. For stochastic linear bandits, we first introduce RepRidge, a replicable ridge regression estimator that satisfies both a confidence guarantee and a

ρ

-replicability guarantee. Beyond its role in our bandit algorithm, this may also be of independent interest in other statistical estimation settings. We then use RepRidge to design RepLinUCB, a replicable optimistic algorithm for stochastic linear bandits, and show that its regret is bounded by

\widetilde{O}\!\big(\big(d+\frac{d^3}ρ\big)\sqrt{T}\big)

. This improves the best prior regret guarantee by a factor of

O(d/ρ)

, showing that our optimistic algorithm can substantially reduce the price of replicability. This is the first linear-bandit algorithm with an optimal dependence on

ρ

for large number of arms. Finally, we extend our framework to stochastic generalized linear bandits by developing RepGLM, a replicable penalized GLM estimator, and RepGLMUCB, a replicable optimistic algorithm for this setting.

Rohan Deb, Udaya Ghai, Karan Singh +1

University of Illinois Urbana-Champaign · Amazon · Carnegie Mellon University

Multi-Armed Bandits Contextual Bandits ML Reproducibility UCB Algorithms Generalized Linear Bandits

Apr 17, 2026

POLAR: Online Learning for LoRA Adapter Caching and Routing in Edge LLM Serving

Edge deployment of large language models (LLMs) increasingly relies on libraries of lightweight LoRA adapters, yet GPU/DRAM can keep only a small resident subset at a time. Serving a request through a non-resident adapter requires paging its weights from storage, incurring measurable latency. This creates a two-timescale online control problem: on a slow timescale, the system selects which adapters remain resident in fast memory, while on a fast timescale it routes each request to an adapter whose context-dependent utility is unknown a priori. The two decisions are tightly coupled: the cache determines the cost of exploration, and the router determines which adapters receive informative feedback. We formulate this joint caching-and-routing problem as a two-timescale contextual bandit and propose POLAR (Paging and Online Learning for Adapter Routing). POLAR pairs a cache-aware LinUCB router with an epoch-based cache controller. We study two variants. A fixed-epoch version provides a robust baseline with worst-case regret guarantees under arbitrary contexts. An epoch-doubling version, POLAR+, adds forced exploration and improved cache optimization to achieve

\widetilde{\mathcal{O}}(d\sqrt{NT}+\sqrt{KT})

sublinear regret under stochastic regularity and cacheability conditions, where

N

is the adapter count,

K

the cache size,

d

the context dimension, and

T

the horizon. The routing term matches the standard contextual-bandit rate up to logarithmic factors, showing that the memory hierarchy does not fundamentally slow routing learning. Experiments using 15 real LoRA adapters for Qwen2.5-7B together with measured GPU paging latencies show that adaptive cache control substantially outperforms non-adaptive baselines and exhibits scaling trends consistent with the theory.

Shaoang Li, Jian Li

Stony Brook University

LLM Serving Low-Rank Adaptation LLM Routing Contextual Bandits

Apr 16, 2026

Calibration-Gated LLM Pseudo-Observations for Online Contextual Bandits

Contextual bandit algorithms suffer from high regret during cold-start, when the learner has insufficient data to distinguish good arms from bad. We propose augmenting Disjoint LinUCB with LLM pseudo-observations: after each round, a large language model predicts counterfactual rewards for the unplayed arms, and these predictions are injected into the learner as weighted pseudo-observations. The injection weight is controlled by a calibration-gated decay schedule that tracks the LLM's prediction accuracy on played arms via an exponential moving average; high calibration error suppresses the LLM's influence, while accurate predictions receive higher weight during the critical early rounds. We evaluate on two contextual bandit environments - UCI Mushroom (2-arm, asymmetric rewards) and MIND-small (5-arm news recommendation) - and find that when equipped with a task-specific prompt, LLM pseudo-observations reduce cumulative regret by 19% on MIND relative to pure LinUCB. However, generic counterfactual prompt framing increases regret on both environments, demonstrating that prompt design is the dominant factor, more important than the choice of decay schedule or calibration gating parameters. We analyze the failure modes of calibration gating on domains with small prediction errors and provide a theoretical motivation for the bias-variance trade-off governing pseudo-observation weight.

Maksim Pershin, Ivan Golovanov, Pavel Baltabaev +1

Contextual Bandits Linear Contextual Bandits Bandit Learning

Apr 9, 2026

A Direct Approach for Handling Contextual Bandits with Latent State Dynamics

We consider a linear contextual bandit model where contexts and rewards are governed by a finite hidden Markov chain. We first revisit the simplified model by Nelson et al. (2022), in which rewards are linear functions of the posterior probabilities over the hidden states given the observed contexts (called beliefs), rather than functions of the hidden states themselves. This simplified model may be handled through a direct reduction to standard linear contextual bandits. We extend the theoretical analysis of this reduction to take into account the estimation of the parameters of the hidden Markov model [HMM] in the regret bound and to provide high-probability bounds not depending anymore on the reward functions and only depending on the model through the estimation of the HMM parameters. Second, and most importantly, we instead study the more natural and more complex model incorporating direct dependencies in the hidden states (on top of dependencies on the observed contexts, as is natural for contextual bandits). Under a classic HMM forgetting condition, the main algorithmic tool introduced to cope with the various statistical dependencies that the reward structure introduces is to only periodically update reward-model parameters.

Zhen Li, Gilles Stoltz

LMO, CELESTE, HEC Paris · BNP Paribas Corporate and Institutional Banking, Paris, France · Université Paris-Saclay, CNRS, Inria, Laboratoire de mathématiques d’Orsay, 91405, Orsay, France +1

Contextual Bandits Linear Contextual Bandits Hidden Markov Models