Contextual Bandits

Ask about this topic

Overview

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

CardsList

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

Aug 27, 2026

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight O~(dT)\tilde{\mathcal{O}}(d\sqrt{T}) regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.

Spyros Dragazis, Aldo Pacchiano

Boston University · Broad Institute of MIT and Harvard

Contextual BanditsMulti-Armed BanditsUCB AlgorithmsLinear Contextual Bandits
AskPDF
Aug 22, 2026

Gated Decoupled Compositional Bandits: A Unified Theory of Contextual Bandits with Supervised-Calibrated Action Scaling and Pre-Execution Gating

We introduce Gated Decoupled Compositional Bandits (GDCB), a family of contextual bandit algorithms with three structural innovations that jointly fall outside the taxonomy of LinUCB, LinTS, HierTS, factored bandits, neural contextual bandits, and RLHF. In a GDCB system: (i) the action delivered to the environment is the composition of a nominal arm, drawn by a discrete or hierarchical bandit, with a context-dependent scaler; (ii) the scaler parameter is learned in a separate supervised loop, not jointly with arm selection; and (iii) every action passes through a pre-execution gate that may modify or veto the composed action before it reaches the environment. We formalise this class of algorithms, prove four structural theorems characterising its statistical behaviour, and show that six industrially significant systems -- short-term rental dynamic pricing, clinical drug dosing, credit origination, grid demand response, content moderation, and LLM tool-use agents -- are all instances of GDCB, differing only in the composition operator, scaler family, and gate. The central result is the Decoupling Variance Reduction theorem: a well-calibrated scaler removes context-induced variance from the arm-to-reward mapping, turning a non-stationary bandit problem into an approximately stationary one. The Gate-Induced Equivalence theorem shows that under a stationary gate, historical data collected under any prior policy is a valid warm-up initialiser without importance-sampling correction, generalising the companion P-HITL result (arXiv:2606.02595) from human approval to arbitrary gates. In regulated, high-stakes domains, constraints usually treated as deployment frictions -- approval gates, compliance rules, safety shields -- are the mechanism that makes fast deployment possible, not an obstacle to it. The companion paper validates instance 1 (STR dynamic pricing) on real production data.

Oleg Miroshnichenko

Multi-Armed BanditsContextual BanditsNon-Stationary Bandits
AskPDF
Aug 19, 2026

Learning What to Fail On: Failure-Mode Contextual Bandits for Adversarial Data Curation

We introduce a failure-aware adversarial retrieval-augmented framework for improving robustness in natural language understanding. Rather than selecting synthetic examples with a fixed reward threshold, our method formulates adversarial data curation as a failure-mode contextual bandit problem. Candidate examples are generated with retrieval-augmented prompting, filtered by the current target model, automatically validated by an LLM judge ensemble, and clustered into recurring failure modes. A stochastic policy then selects which failure modes to sample for retraining, and is updated using validation-based reward that balances robustness gains, forgetting, and data cost. This makes the data curator itself the learning agent, enabling adaptive selection of the most useful model failures across training rounds. On standard benchmarks, our approach improves RoBERTa-base accuracy from 88.48% to 92.60% on SNLI, from 75.04% to 80.95% on ANLI, and from 54.67% to 71.99% on MultiNLI, while consistently outperforming prior adversarial augmentation methods. We further demonstrate transfer to FEVER fact verification, achieving up to 79.86% FEVER score and 82.45% accuracy with RoBERTa-large. Finally, we provide a theoretical interpretation showing that, under stated assumptions, failure-mode sampling can reduce shortcut-aligned gradient contributions while inducing bounded distributional drift. By combining retrieval, automated validation, contextual-bandit failure selection, and controlled adversarial retraining, our framework enables scalable robustness improvement without additional human annotation.

Roie Kazoom, Ofir Cohen, Rami Puzis +2

Electrical and Computers Engineering, Ben Gurion University of The Negev · Software and Information Systems Engineering, Ben Gurion University of The Negev

Adversarial RobustnessTraining Data CurationAdversarial TrainingContextual Bandits
AskPDF
Aug 13, 2026

Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing

Online platforms increasingly compare many adaptive decision policies---ranking systems, recommendation algorithms, pricing rules, and language-model agents---while each reward-bearing interaction can be costly or risky. A direct A/B/n design gives each of J≥2J\ge 2 policies its own horizon-TT trajectory and therefore uses JTJT outcomes. We introduce Tree-Coupled A/B Testing (\TCAB), an exact feedback-sharing design for arbitrary history-dependent contextual-bandit policies. At each round, a predictable tree connects the current policy histories; every parent--child context--action law is maximally coupled, and one reward is shared within each component of matched tree edges. Every policy retains exactly its standalone finite-horizon trajectory law, even though the policies are deliberately dependent. If De,tD_{e,t} records a mismatch on tree edge ee at round tt, the number of reward queries satisfies the pathwise identity N(T)=T+∑t,eDe,tN(T)=T+\sum_{t,e}D_{e,t} and hence equals TT plus cumulative tree-edge total variation in expectation. This cost is conditionally optimal among exact edge-local designs on the selected tree, and a current-round minimum-spanning tree is myopically optimal among tree designs. For fixed JJ, sublinear pseudo-regret of every policy and almost-sure uniqueness of the oracle action imply E[N(T)]=T+o(T)\mathbb{E}[N(T)]=T+o(T), versus JTJT for independent runs. We also obtain finite-sample variance bounds for pairwise policy contrasts. Experiments on reward-model evaluation, multiple-choice language-model evaluation, and adaptive search policies demonstrate substantial improvements in the cost--precision frontier.

Yuxiao Wen

Courant Institute of Mathematical Sciences, New York University

Policy EvaluationA/b TestingContextual Bandits
AskPDF
Aug 12, 2026

When Offline Evaluation Misleads: A Diagnostic Protocol for Reward and Policy Selection in Delayed-Feedback Contextual Bandits

Personalizing marketing messages with contextual multi-armed bandits (CMABs) drives real business value, yet the objective that ultimately matters - a downstream conversion - is observed only weeks later, too late to drive online learning. Teams therefore train the bandit on a fast proxy reward, and separately must judge whether a contextual bandit is worth its complexity over sending one best message. Settling both decisions with the usual offline checks - a batch off-policy estimate, a marginal arm-discrimination test, a confidence interval - can mislead systematically under delayed feedback. We give an ordered diagnostic protocol that screens a reward-and-policy candidate on two axes, alignment (does optimizing the reward move the north-star?) and learnability (can the bandit identify the reward-optimal policy?), before trusting any reported lift. We validate it where the truth is known - a public off-policy-evaluation benchmark and a controllable synthetic generator - and illustrate it on a deployed large-marketplace push system (where, with five arms and one split, the evidence is directional rather than powered). Two lessons recur. (N1) A single offline number can mis-rank rewards: a denser reward signal gives the bandit more to learn from, so rewards that look tied in a static estimate pull apart once learning happens online. (N2) If you cannot tell in advance which single message is best, a per-user policy partly just avoids betting on the wrong one - that looks like personalization but is really robustness, so a "personalization premium" is easily overstated. Our contribution is methodological rather than algorithmic: the ordered protocol, the two lessons it surfaces, and the end-to-end experience of applying it to a delayed-feedback CMAB.

Sang Su Lee, Vineeth Loganathan, Shishir Dash +1

Thumbtack, Inc. San Francisco, CA, USA

Multi-Armed BanditsOff-Policy EvaluationBandits with Delayed FeedbackContextual BanditsReward Design for RLOffline-to-Online Contextual Bandits
AskPDF
Aug 11, 2026

Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints

We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of O((ln⁡T)3T)O(\frac{(\ln T)^3}{T}) where TT is the horizon length. Our bound significantly reduces the O(1T)O(\frac{1}{\sqrt{T}}) bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.

Zhen Xu

Management School, University of Liverpool, Liverpool, United Kingdom

Contextual BanditsUCB AlgorithmsLinear Contextual Bandits
AskPDF
Aug 10, 2026

Offline Policy Evaluation as a decision support tool for designing Adaptive Experiments

We investigate how historical data from fixed randomized experiments (A/B tests) can be used to inform the deployment of adaptive experiments based on contextual bandits. Given data collected under a static allocation, our goal is to assess which adaptive policies, if any, would have outperformed the original design and under what conditions. To this end, we combine off-policy evaluation (OPE) with a controlled warm-start simulation. From logged A/B test data exhibiting heterogeneous treatment effects, we estimate nuisance components and use doubly robust estimators to rank a portfolio of pre-specified adaptive and non-adaptive policies. When ground truth is available, we then deploy the same offline-trained policies in a simulator that reuses the exact data-generating reward probabilities, providing a safe, ground-truth-anchored environment to study the offline-to-online transition under warm starting. Using synthetic randomized controlled trials with known heterogeneity structures and an oracle policy, our results indicate that adaptive, context-aware policies improve upon fixed allocations when meaningful heterogeneity is present, while providing little benefit in its absence. We reinforce our findings on standard open benchmarks (Hillstrom, Criteo Uplift, and LaLonde), reinterpreted through a policy-value and regret perspective. Overall, our results provide a practical methodology for deciding when adaptive experimentation is worth deploying and how to select among competing adaptive policies using existing A/B test data.

João Victor Ferreira Alves, Eduardo Rocha Laurentino, Gustavo de Oliveira Kanno +1

Instituto de Ciência e Tecnologia Itaú (ICTi), Brasil

Contextual BanditsA/b TestingOff-Policy Evaluation
AskPDF
Aug 7, 2026

Progressive Content Refinement with Decaying Reward Joint LinUCB

Iterative refinement has significantly enhanced Large Language Model (LLM) performance; however, existing methods ranging from feedback-based Self-Refine to traditional bandit approaches often rely on static options or overlook the saturation effect. This neglect leads to over-exploitation, where the continuous use of identical prompts or arms results in diminishing rewards over time. To address this challenge, we propose a novel contextual bandit algorithm that explicitly incorporates reward decay modeling. Utilizing an Expectation-Maximization (EM) algorithm, our method simultaneously estimates both arm-specific and decay parameters. Furthermore, by embedding prompts as arms, we facilitate the joint learning of arm values, distinguishing our approach from the traditional disjoint Linear Upper Confidence Bound (LinUCB) framework. Experimental results on Sentiment Reversal and GSM8K benchmarks demonstrate that our method achieves significant performance gains over strong baselines. Finally, our ablation study confirms that the integration of reward decay modeling within the bandit framework is crucial for mitigating over-exploitation and optimizing the iterative refinement process.

Shion Ishikawa, Pablo Loyola, Young-joo Chung +1

Rakuten Group, Inc. Tokyo, Japan · Rakuten Group, Inc. San Mateo, USA

LLM Self-RefinementLarge Language Model-Guided OptimizationNon-Stationary BanditsContextual BanditsLinear Contextual Bandits
AskPDF
Aug 6, 2026

Bootstrap-Conditioned Action Selection with Tabular Foundation Models

Contextual bandits offer a natural framework for sample-efficient personalization, but practical deployment remains difficult under sparse, biased interaction data, unreliable uncertainty estimates, and severe cold starts. We study whether pre-trained tabular foundation models with in-context learning can be turned into randomized policies for online decision making. We propose BC-ICL (Bootstrap-conditioned action selection using ICL), which at each round draws a bootstrap resample of the interaction history, conditions a frozen pre-trained ICL model on that resample, scores all actions, and selects the action with the highest sampled score. We further introduce an arm-context conditioning architecture that promotes shared statistical strength across actions and helps avoid common bootstrap failure modes of isolated-arm bandits. Empirically, this policy delivers strong early-round regret and regret performance on standard contextual bandit suites, outperforming established baselines under a strict online protocol.

Devansh Gupta, Shiv Tavker, Dmitry Efimov +3

Amazon Science

Tabular Foundation ModelsRL ExplorationContextual BanditsTabular ICL
AskPDF
Aug 4, 2026

Minimax-Optimal Semiparametric Contextual Dynamic Pricing with Multimodal Revenue

We study contextual dynamic pricing with arbitrary covariate sequences and bounded, possibly nonbinary purchase quantities. Demand follows a semiparametric surplus-index model with an unknown linear valuation parameter and an unknown Hölder-smooth response. We impose neither concavity nor strong unimodality on revenue and allow nonunique optimal prices. We develop a pilot-corrected layered decision-partitioning policy that combines directional pilot estimation, local polynomial learning, predictable data assignment, and global action elimination. Pilot correction removes the first-order effect of valuation-parameter error, while permanent labels enable concentration under adaptive sampling. The policy attains the minimax smoothness-dependent horizon rate up to logarithmic factors; a matching lower bound already holds for a constant-context binary-demand subclass.

Xueping Gong, Zhuoluo Zhang, Zhaowei Miao +1

School of Management, Xiamen University · Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology

Contextual BanditsDynamic Pricing
AskPDF
Aug 2, 2026

402Pilot: An x402 Decision Layer for Autonomous Agent Micropayments

Programmable-payment protocols such as x402 enable per-request micropayments, but they do not determine which payable service an autonomous agent should buy under a finite wallet. We formulate this buyer-side problem as agent-native payment decision-making: contextual provider selection under wallet pressure, chosen-only paid feedback, and changing market conditions. We propose 402Pilot, a protocol-agnostic buyer-side decision layer between autonomous agents and payment execution that implements purchasing policies for selecting among payable providers. We instantiate it with PA-DCT, a payment-aware discounted contextual Thompson-sampling policy that adapts purchasing decisions under wallet pressure while learning from post-payment feedback. To evaluate buyer-side payment policies, we introduce 402Pilot-Bench, a frozen-replay benchmark spanning 823 tasks, five heterogeneous provider pipelines, and three market regimes, each evaluated over 30 paired seeds. PA-DCT achieves the strongest fixed-wallet adaptive trade-off among non-oracle policies: it maintains competitive service quality while spending only 39 to 43 percent of the wallet and reallocates spending as market conditions change. It attains the best non-oracle PA-gap/T under the price shock and the best mean and worst-case ranks across the nine scenario-metric combinations of quality, ROI, and PA-gap/T. Comparisons with learning baselines and component ablations further support the effectiveness and design of the proposed decision policy. These results suggest that programmable payment must be complemented by buyer-side decision-making capable of learning service value and adapting purchasing decisions accordingly.

Yin Li, Yanbo He, Boo-Ho Yang +5

The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China · MOVENSYS Inc., Seongnam-si, Republic of Korea · Schneider Electric, Shanghai, China +2

Multi-Armed BanditsNon-Stationary BanditsContextual Bandits
AskPDF
Jul 31, 2026

Personalizing Large Language Model Agents with Small Policy Models

Large language model (LLM) agents can retrieve memory, call tools, ask clarifying questions, and vary response style, yet adapting these execution decisions to an individual user remains difficult. Fine-tuning a separate LLM is costly or impossible for proprietary systems, while prompts and memory primarily expose user information to the agent rather than adapt its execution decisions from feedback. We formulate personalization of a frozen agent as online learning of a per-user execution policy from scalar feedback observed only for the executed action. We propose FABLE (Factorized Adaptive Bandit Layer for Execution), a lightweight policy layer outside a potentially black-box host agent. FABLE factorizes memory, information-acquisition, and response decisions so feedback updates related choices; filters actions through an externally specified feasible set before exploration; and learns user-specific residual preferences relative to a fixed default-and-cost score via Bayesian contextual Thompson sampling. Under a linear residual-reward model, a calibrated variant inherits an expected-regret bound against the best feasible action. We also characterize preferences unidentifiable under persistent feasibility constraints and provide anytime-valid false-promotion control. Across personalized-reasoning, controlled-feedback, and executable tool-use evaluations, FABLE improves several preference-sensitive behaviors relative to rule-only control while remaining competitive on end-to-end task performance.

Dian Jin, Zhi Zhang, Huichao Li +3

Department of Statistics and Data Science, National University of Singapore · Department of Statistics and Data Science, University of California, Los Angeles · Department of Data Science, Fudan University

LLM PersonalizationLLM AgentsContextual BanditsPolicy LearningOnline Learning
AskPDF
Jul 30, 2026

On-Policy and Off-Policy Learning for Large Action Spaces

This thesis studies policy learning in interactive systems where an agent observes a context, selects an action from a very large set, and receives partial feedback. The main framework is contextual bandits, with two paradigms: on-policy learning, where the agent interacts sequentially with the environment and minimizes regret, and off-policy learning, where it learns from logged data collected by a logging policy. In large action spaces, both settings face major challenges: inefficient exploration, sparse data coverage, high-variance importance weights, extrapolation bias, and difficult optimization landscapes. The first part develops structured Bayesian methods for on-policy learning. We introduce meTS, a mixed-effect extension of Thompson sampling, and dTS, which leverages diffusion-inspired priors to model dependencies between actions. These methods share information across actions and yield regret guarantees depending on an effective number of actions. The second part addresses off-policy learning. We propose sDM, a structured direct method based on latent variables, show that optimization error can dominate estimation error in large action spaces, and introduce concave, efficiently optimizable policy-weighted log-likelihood objectives. Finally, we develop differentiable pessimistic methods based on exponential smoothing and PAC-Bayesian bounds to control the bias-variance trade-off of regularized importance-sampling estimators.

Imad Aouali

Institut Polytechnique de Paris · Ecole nationale de la statistique et de l’administration économique · Ecole doctorale n◦574 Ecole Doctorale de Mathématique Hadamard (EDMH)

Thompson SamplingMulti-Armed BanditsOff-Policy EvaluationImportance SamplingContextual BanditsMarkovian Bandits+1
AskPDF
Jul 29, 2026

Kairos: Numerically Robust News Recommendation under Item Cold-Start via Cholesky-based LinUCB

Algorithmic news personalization in regional markets often fails because modern deep learning models require massive interaction data while real-world news has a short Time-to-Live (TTL < 48 h) and shallow article pools. This structural item cold-start deprives collaborative filtering of the data needed for robust modeling. This paper presents Project Kairos, a framework that bridges this data scarcity through a contextual online learning approach (LinUCB). To ensure numerical integrity for continuous operation, Kairos replaces error-prone Sherman-Morrison inversions with direct rank-1 updates of Cholesky factors. This preserves the positive definiteness of the covariance matrix even under ill-conditioned data scenarios. Simultaneously, Matryoshka Representation Learning (MRL) integration addresses inference latency. Empirical evaluations based on the Tagesschau API demonstrate that exploiting semantic redundancy in the feature space achieves a 4.85-fold efficiency gain without significantly compromising ranking precision. Kairos thus provides a blueprint for high-performance recommendation systems in resource- and data-constrained environments.

Finn Hertsch

DHBW Ravensburg, School of Business, Data Science and AI, Marienplatz 2, 88212 Ravensburg, Germany

Cold-Start RecommendationRecommender SystemsContextual Bandits
AskPDF
Jul 26, 2026

WISERouter: LLM Routing with Workload Budget Constraint

Large language models (LLMs) achieve impressive performance across multiple domains, but using the most capable model for every query is prohibitive at scale. LLM routing exploits diversity in model capability and cost by assigning each query to a suitable model to balance utility and budget. Current methods have two limitations: (i) they either use heuristics that do not always enforce the budget constraint or impose a fixed per-query budget that cannot adapt across the workload and leads to suboptimal performance; (ii) they require supervised learning on a dense dataset with statistics for every query-model pair, which is expensive to collect. To address these challenges, we formulate LLM routing as a constrained contextual multi-armed bandit problem and introduce WISERouter (WR for short), a framework that supports offline learning from historical interactions as well as online learning with exploration. We further prove that WR-Online achieves a sublinear regret bound of O(T)O(\sqrt{T}) over a time horizon TT. Empirical results on RouterBench and SWE-Bench demonstrate that (i) WR-Offline surpasses existing baselines in performance under a fixed budget and adheres more closely to budget constraints, and (ii) WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.

Yifei Li, Zihui Gao, Laks V. S. Lakshmanan

The University of British Columbia

LLM RoutingContextual Bandits
AskPDF
Jul 24, 2026

Cross-Domain Off-Policy Evaluation and Learning for Contextual Bandits

Off-Policy Evaluation and Learning (OPE/L) in contextual bandits is rapidly gaining popularity in real systems because new policies can be evaluated and learned securely using only historical logged data. However, existing methods in OPE/L cannot handle many challenging but prevalent scenarios such as few-shot data, deterministic logging policies, and new actions. In many applications, such as personalized medicine, content recommendations, education, and advertising, we need to evaluate and learn new policies in the presence of these challenges. Existing methods cannot evaluate and optimize effectively in these situations due to the notorious variance issue or limited exploration in the logged data. To enable OPE/L even under these unsolved challenges, we propose a new problem setup of Cross-Domain OPE/L, where we have access not only to the logged data from the target domain in which the new policy will be implemented but also to logged datasets collected from other domains. This novel formulation is widely applicable because we can often use historical data not only from the target hospital, country, device, or user segment but also from other hospitals, countries, devices, or segments. We develop a new estimator and policy gradient method to solve OPE/L by leveraging both target and source datasets, resulting in substantially enhanced OPE/L in the previously unsolved situations in our empirical evaluations.

Yuta Natsubori, Masataka Ushiku, Yuta Saito

Hakuhodo DY Holdings, Inc. · Cornell University

Off-Policy EvaluationContextual BanditsOff-Policy RLCross-Dataset Generalization
AskPDF
Jul 17, 2026

A Predict-then-Correct Loop Based on Few-Shot Continuous Contextual Bandit for Demand Forecasting

Retail demand forecasting remains difficult when demand shifts faster than static forecasting models can be retrained, especially in early demand cycles where newly observed labels are sparse. To address this, this study aims to improve adaptive retail forecasting by proposing a predict-then-correct (PtC) framework that retains a first-stage machine learning (ML) forecast and applies a few-shot continuous contextual bandit correction policy with similar-SKUs augmentation and top-p masked updating. Across Walmart retail data and an exclusive beverage dataset, PtC delivers statistically significant reductions in MAPE, MAE, and RMSE across stable & high volume, stable & low volume, and erratic & intermittent demand patterns, improves average RMSE by 9.52% over the ML-only baseline in the ablation study, and yields lower inventory costs than base-stock, proximal policy optimization, and soft actor-critic policies under the tested lead-time settings. These findings show that online forecast correction can bridge offline demand learning and real-time retail decision-making by adapting to sparse feedback without fully retraining the base forecasting model.

Zhiwei Lei, Benedict Jun Ma, Ilya Jackson

Thrust of Intelligent Transportation, Hong Kong University of Science and Technology (Guangzhou), China · Center for Transportation and Logistics, Massachusetts Institute of Technology, USA

Time Series ForecastingContextual Bandits
AskPDF
Jul 17, 2026

Information-Directed Sampling for Causal Bandits

Causal bandits exploit structural relationships among variables to share information across interventions and accelerate the identification of high-reward decisions. In many applications, however, some variables cannot be directly manipulated, even though they influence the reward and provide useful information about the underlying causal system. We study contextual causal bandits with non-manipulable variables, where context variables are observed before action selection and additional variables are observed after each intervention. Assuming a known causal graph without latent confounding, we adopt a Bayesian formulation in which the conditional probability tables of the observational distribution constitute the unknown parameter. This representation allows observations collected under one intervention to update reward estimates for other interventions through their shared causal mechanisms. We develop causal variants of Thompson Sampling and Information-Directed Sampling (IDS) for this setting. For Thompson Sampling, we establish an entropy-dependent sublinear Bayesian regret bound. For IDS, we derive an entropy-dependent regret bound that explicitly quantifies the additional error introduced by Monte Carlo approximation of the expected regret and information gain; when these quantities are available exactly, the bound recovers the standard sublinear IDS rate. The dependence of these guarantees on the action-set size is worst-case: our model contains the standard multi-armed bandit as a special case. We further provide high-probability confidence bounds for the Monte Carlo estimates. Experiments on synthetic causal bandit tasks show that the proposed methods outperform causal and non-causal baselines by effectively exploiting information shared across interventions.

Muhammad Qasim Elahi, Murat Kocaoglu, Mahsa Ghasemi

School of Electrical and Computer Engineering, Purdue University · School of Computer Science, Johns Hopkins University

Thompson SamplingMulti-Armed BanditsContextual Bandits
AskPDF
Jul 16, 2026

Kernel weighted importance sampling for off-policy evaluation in contextual bandits

This article presents a novel estimator for performing off-policy evaluation using only offline data for contextual bandits. The proposed estimator, Kernel-WIS is demonstrated to be asymptotically consistent and to empirically outperform strong baselines (including vanilla weighted importance sampling), particularly under complex conditions including behaviour policy miss-specification. The benefit of Kernel-WIS is derived from combining the bounded property of vanilla weighted importance sampling with the linearity of vanilla importance sampling.

Joshua Spear, Matthieu Komorowski, Rebecca Pope +2

Institute of Child Health, University College London · Strive Health Ltd. · National Institute for Health Research +3

Off-Policy EvaluationImportance SamplingImportance WeightingContextual Bandits
AskPDF
Jul 15, 2026

Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

We study the contextual combinatorial semi-bandit (CCSB) problem with general reward function approximation. At each round, the learner observes a context, selects a combinatorial action consisting of a subset of basic arms, and receives the reward of each selected arm; the goal is to maximize the cumulative reward over time. We propose SquareCB.Comb, a computationally efficient algorithm that, at each round, solves a convex optimization problem to sample a combinatorial action that balances exploration and exploitation. SquareCB.Comb scales to large arm sets and imposes no structural assumptions on the action set beyond a cardinality bound of mm on each combinatorial action. We prove that SquareCB.Comb achieves a minimax optimal regret bound of O(mATlog⁡∣F∣)O(\sqrt{m A T \log |\mathcal{F}|}), where AA is the number of arms, mm is the maximum number of arms in a combinatorial action, TT is the time horizon, and F\mathcal{F} is the reward function class. In the realizable setting, this bound matches the state-of-the-art regret guarantees achieved by policy search-based algorithms in the more restricted slate recommendation settings, while simultaneously generalizing to arbitrary combinatorial action structures and general reward function approximation.

Hao Qin, Chicheng Zhang

The University of Arizona

Combinatorial Semi-BanditsContextual BanditsCombinatorial Multi-Armed Bandits
AskPDF
Jul 13, 2026

Diversified Multinomial Logit Contextual Bandits

Existing contextual multinomial logit (MNL) bandits model relevance-driven choice but ignore the potential benefits of within-assortment diversity, while submodular/combinatorial bandits encode diversity in rewards but lack structured choice probabilities. We bridge this gap with the diversified multinomial logit\textit{diversified multinomial logit} (DMNL) contextual bandit, which augments MNL choice probabilities with a generally submodular diversity function, thereby formalizing the relevance--diversity trade-off within a single model. Incorporating diversity renders exact MNL assortment optimization intractable. We propose a white-box\textit{white-box} UCB-based algorithm, OFU-DMNL\texttt{OFU-DMNL}, that constructs assortments item-wise by maximizing optimistic marginal gains, avoids black-box optimization oracles. We show that OFU-DMNL\texttt{OFU-DMNL} achieves at least a (1−1e+1)(1-\frac{1}{e+1})-approximate\textit{approximate} regret bound O~(dT/K)\tilde{O}\left(d \sqrt{T/K}\right), where dd is the context dimension, KK the maximum assortment size, and TT the horizon, and attains an improved approximation factor over standard submodular baselines. Experiments demonstrate consistent gains and, relative to exhaustive enumeration, comparable regret with substantially lower runtime. Overall, DMNL bandits provide a practical foundation for diversity-aware assortment optimization under uncertainty, and OFU-DMNL\texttt{OFU-DMNL} offers a statistically and computationally efficient solution.

Heesang Ann, Taehyun Hwang, Min-hwan Oh

Seoul National University

Multi-Armed BanditsDiscrete Choice ModelingContextual BanditsAssortment Optimization
AskPDF
Jul 10, 2026

Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing

We study contextual bandit problems with correlated arms and access to surrogate reward signals produced by a machine learning model, motivated by applications such as large language model (LLM) routing. Unlike classical contextual bandits that rely solely on bandit feedback and assume conditional independence across arms, our setting allows context-dependent inter-arm correlations and auxiliary reward information that may be noisy or misspecified. We propose algorithms that leverage such surrogate rewards through two complementary designs. A coupled reward-mixing approach pools true and surrogate rewards to accelerate learning when surrogate signals are reliable, while a decoupled prediction-mixing approach maintains separate estimators for bandit feedback and surrogate rewards and adaptively combines their predictions. This decoupling yields robustness to surrogate misspecification, recovering regret guarantees comparable to reward-only bandit methods in the worst case, while achieving improved regret when surrogate predictions are sufficiently informative. We provide theoretical regret analyses for both approaches and evaluate them on LLM routing benchmarks under varying accuracy versus cost trade-offs. The results demonstrate improved sample efficiency and consistently better accuracy-cost trade-offs compared to standard contextual bandit baselines and strong static routing methods.

Ajay Narayanan Sridhar, Ronak Singh, Mehrdad Mahdavi +1

The Pennsylvania State University

Multi-Armed BanditsLLM RoutingContextual Bandits
AskPDF
Jul 9, 2026

Stochastic Linear Bandits with Partially Observed Actions

The stochastic linear bandit, where actions are represented as vectors and rewards are linear, is a central paradigm for sequential decision making. We study a partially observed variant of this problem in which the learning agent only sees a random subset of coordinates for each action. Such partial observability arises naturally in settings like recommendation and healthcare, where full action descriptions can be expensive or even impossible to obtain. In general, this makes sublinear regret information-theoretically impossible. However, we show that this barrier can be overcome when the action vectors have low intrinsic dimension. We propose an algorithm, TOFU-POV, that estimates the latent action subspace using the masked actions, imputes current actions using an epoch-wise frozen representation, and runs OFUL in the resulting low-dimensional coordinates. Our theory shows that TOFU-POV enjoys a T\sqrt{T} regret that scales with the intrinsic action subspace dimension as opposed to the ambient dimension and quantifies the interaction between these quantities and the missingness, decision set size, and subspace conditioning. We also devise a rank-adaptive algorithm that does not require the knowledge of the intrinsic dimension. We complement these guarantees with a lower bound based on a novel product construction that separates usual reward-learning uncertainty from a missingness-dependent cost intrinsic to partial observation. Synthetic and real data experiments support our theory and show that TOFU-POV can substantially improve upon natural baselines in this challenging problem.

Gautam Dasarathy, Vineet Gattani, Lalit Jain

Arizona State University · GE Vernova · Google

Multi-Armed BanditsContextual Bandits
AskPDF
Jul 8, 2026

Nonlinear Bandit

In this paper we first study the problem of generalized linear bandit (GLB) under heavy-tailed noise. The characteristics of heavy-tailed distributions are widely observed in real-world applications such as personalized recommendation, financial markets, and medical treatments. Based on the online mirror descent (OMD) method, we propose an algorithm EHM that extends the adaptive Huber loss method (Wang et al., 2025) with one-pass update (O(1)\mathcal{O}(1) computational complexity with respect to current round tt and the time horizon TT), which simultaneously achieves an almost optimal regret of O~(T11+ε)\widetilde{\mathcal{O}}(T^{\frac{1}{1+ε}}) where TT is the time horizon. In addition, by utilizing a special property of some link function (Sawarni et al., 2025), our algorithm eliminates the need to know a commonly used parameter. Next, we study the GLB problem under the case when contextual characteristic becomes piecewise constant, and we slightly revised former algorithm to obtain the PGLB-EHM algorithm. After theoretical analysis, we prove that the regret upper bound order stays the same. Furthermore, we look deeper into a special case of nonlinear bandit (NB) and present the NB-EHM algorithm with bisection method and special restriction. Eventually we utilize the affine lifting approach and show that the general NB problem can be applied with NB-EHM to achieve a sublinear regret bound.

Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou +1

School of Mathematics, Nanjing University, Nanjing, 210093, China · School of Artificial Intelligence, Nanjing University, National Key Laboratory for Novel Software Technology, Nanjing, 210023, China · School of Mathematics and Physics, Xi’an Jiaotong-Liverpool University, Suzhou, 215123, China

Multi-Armed BanditsHeavy-Tailed NoiseOnline Mirror DescentContextual BanditsGeneralized Linear Bandits
AskPDF
Jul 7, 2026

Contextual Procurement Auctions with Bandit Learning

We study repeated contextual procurement auctions in which producers have private costs and the platform must learn context-dependent product values from bandit feedback. The objective is welfare rather than revenue or a virtual-cost surrogate: regret is the total surplus loss relative to the full-information efficient procurement rule. We first show that the natural UCB allocation rule attains O~(ngT)\tilde O(\sqrt{ngT}) welfare regret under truthful bids, but its adaptive bid-dependent learning path does not by itself give a truthfulness guarantee. To obtain exact incentives, we design a bid-independent explore-then-commit mechanism with empirical critical payments; it is dominant-strategy truthful and has O~((ng)1/3T2/3)\tilde O((ng)^{1/3}T^{2/3}) regret. We then introduce frozen-payment UCB, which estimates payments in an initial bid-independent exploration phase, freezes those payment estimates, and continues adaptive UCB allocation learning afterwards. Under a smoothed truthful-path margin condition, this mechanism gives a regret-incentive tradeoff: the near-UCB tuning attains O~(ngT)\tilde O(\sqrt{ngT}) welfare regret, while the average per-round gain from any fixed deviation is at most O~(T−1/4)\tilde O(T^{-1/4}) for fixed n,gn,g. A matching lower bound shows that this frozen-payment frontier is unavoidable.

Yiling Chen, Shi Feng, Sadie Zhao

Harvard University

Mechanism DesignRegret MinimizationContextual Bandits
AskPDF
Jul 3, 2026

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve. Motivated by these applications, we study non-stationary linear bandits with round-specific feasible decision sets. Existing methods that obtain the optimal O~(T2/3PT1/3)\widetilde O(T^{2/3}P_T^{1/3}) dependence, where PTP_T is the path length of the reward-parameter sequence, impose an orthogonal-structure assumption on round-specific decision sets, which can be restrictive in contextual applications. We address this gap through a unified misspecification-reduction viewpoint: after partitioning the horizon into blocks, we relate each block's dynamic regret to regret against a fixed-parameter linear bandit benchmark, with the within-block parameter drift entering as bounded misspecification. Restarting algorithms with misspecification-dependent regret guarantees then yields the optimal T2/3PT1/3T^{2/3}P_T^{1/3} dynamic-regret dependence for both linear bandits with general compact decision sets and KK-armed contextual linear bandits.

Zihao Hu, Yuan Yao, Jiheng Zhang +1

Department of Mathematics, The Hong Kong University of Science and Technology

Dynamic Regret MinimizationNon-Stationary BanditsContextual BanditsLinear Contextual Bandits
AskPDF
Jun 30, 2026

A Contextual-Bandit Oversight Game with Two-Sided Informational Asymmetry

We study runtime human oversight of an AI agent when private information runs in both directions: the human privately knows her reward function, while the AI privately knows the quality of the action it proposes. This is the kind of asymmetry that arises naturally when an autonomous robot or software agent has inspected a situation its human supervisor cannot directly assess. Building on Cooperative Inverse Reinforcement Learning (CIRL) and the Oversight Game, we introduce a contextual-bandit team game with two-sided asymmetric information and a play/ask/trust/oversee interface. The bandit structure removes physical state transitions and thereby yields exact one-shot characterizations that would remain conjectural in the full POMDP setting, though the common belief remains a dynamically controlled state across rounds. We give two one-shot characterizations, a team optimum and a behaviorally natural myopic rule, whose gap is a slab of avoidable harm: a region in which the AI privately knows the proposed action is harmful and shutdown would help, yet a myopic human, trusting her prior, declines to oversee. We show this gap is the price of non-credible oversight communication, and give a partial analysis of how it resolves dynamically over repeated rounds through passive learning and active signaling with a one-period-lagged oversight response.

Yunjin Tong

Stanford Graduate School of Business

Reinforcement LearningImperfect-Information GamesAI Agent SafetyContextual BanditsHuman Oversight of AI
AskPDF
Jun 30, 2026

Contextual Slate GLM Bandits with Limited Adaptivity

We investigate the contextual slate bandit problem with generalized linear rewards under limited adaptivity. At each round, the learner is presented with NN sets of items, where each item is represented by a dd-dimensional feature vector. The learner then constructs a slate by selecting one item per set; the resulting slate yields a scalar reward sampled from a Generalized Linear Model (GLM). We propose algorithms under two limited-adaptivity settings: (a) Batched and (b) Rarely-Switching. For the batched setting, we introduce B-SlateGLinCB, which partitions the time horizon into O(log⁡log⁡T)\mathcal{O}(\log\log T) batches such that each batch's policy relies only on data from previous batches. For the rarely-switching setting, we propose RS-SlateGLinCB, which adaptively performs only O(Ndlog⁡T)\mathcal{O}(Nd\log T) parameter updates. Under a diversity assumption on the item sequences, we prove that B-SlateGLinCB and RS-SlateGLinCB achieve regret bounds of O(Nd3/2T)\mathcal{O}(Nd^{3/2}\sqrt{T}) and O(NdT)\mathcal{O}(Nd\sqrt{T}), respectively. Notably, both bounds are independent of the non-linearity parameter κκ that is typically found to scale the regret of GLM bandit algorithms. Our algorithms are computationally efficient, requiring only poly(N)\text{poly}(N) time per round despite 2Ω(N)2^{Ω(N)} possible slates. Simulations show our algorithms outperform existing baselines with limited adaptivity and remain competitive with Slate-GLM-OFU, a fully adaptive state-of-the-art algorithm. Notably, a slightly modified B-SlateGLinCB empirically matches this baseline. Finally, we demonstrate strong performance in a practical in-context example selection task for language models.

Tanmay Goyal, Sukruta Prakash Midigeshi, Gaurav Sinha

Microsoft Research India

Multi-Armed BanditsContextual BanditsCombinatorial Multi-Armed BanditsGeneralized Linear Bandits
AskPDF
Jun 30, 2026

Smart charging of large fleets of Electric Vehicles: Independent Multi-Agent Reinforcement Learning approaches

The electrification of transportation through electric vehicles introduces new challenges for power grid management, such as increased peak demand, voltage fluctuations, line overloads, and the integration of variable renewable energy sources. To enable efficient integration of EVs while minimizing costs for users and avoiding network overloads, implicit coordination between EVs is required. This work compares two independent multi-agent reinforcement learning approaches for optimizing such decentralized EV charging: contextual combinatorial bandits and policy gradient algorithms. Using a realistic simulation environment with autonomous agents making decisions based on local environmental information (including price signals, state-of-charge, and temporal constraints), we evaluate their performance across varying congestion levels, and mixed-strategy configurations with heterogeneous agent groups under dynamic electricity pricing derived from real photovoltaic production data.

Xavier Rate, Eloann Le Guern, Raphaël Féraud +8

Orange · ENS Rennes · IMT Atlantique +1

Multi-Agent CoordinationElectric Vehicle ChargingPolicy Gradient MethodsContextual BanditsDecentralized MARLPower Systems
AskPDF
Jun 28, 2026

Learning to Bid in Discriminatory Auctions with Budget Constraints

We study repeated bidding in multi-unit discriminatory (pay-as-bid) auctions for a single bidder with per-round utility equal to value minus αα times payment, where α∈[0,1]α\in[0,1] is a cost-of-capital parameter. The bidder aims to maximize cumulative utility over TT rounds subject to a total budget BB. The problem is challenging even without budgets: the action space is exponential in MM, the maximum demand of the bidder and the valuation vector (context) varies over time. Exploiting a decomposition of utility across units, we develop polynomial-time learning algorithms based on shortest paths in a directed acyclic graph, obtaining sublinear regret under both full-information and bandit feedback. In the bandit setting, the regret is independent of the number of contexts due to complete cross-learning: observing the utility of the chosen action under the realized context reveals the utility for the same action under all counterfactual contexts. With budget constraints, when the average normalized per-round budget ρ=BMT<1ρ=\frac{B}{MT}<1, we design a coupled primal-dual algorithm in which the DAG-based procedure uses dual-adjusted edge weights for primal updates, while online gradient descent updates the dual variable, yielding ρρ-approximate sublinear regret. Finally, we give implementations whose per-round time and space are independent of the number of contexts, enabling scalability to large or even infinite context spaces.

Negin Golrezaei, Sourav Sahoo

Sloan School of Management, Massachusetts Institute of Technology · Operations Research Center, Massachusetts Institute of Technology

Game TheoryAutomated BiddingContextual BanditsOnline Resource Allocation
AskPDF