Multi-Armed Bandits

Follow this topic Ask about this topic

Latest papers 332

48 papers in the last four weeks, up 109% on the four weeks before. 0.3% of all new papers.

Aug 5, 2026

Cost-Aware Multi-Objective Bandits: Theory and Application to Budgeted LLM Configuration Evaluation

Large language model (LLM) configuration evaluation is challenging due to limited evaluation budgets, varying costs, and multiple competing objectives. In this paper, we formulate LLM configuration evaluation as a cost-aware multi-objective bandit problem, where each configuration evaluation incurs a configuration-dependent cost and yields a noisy vector-valued outcome. Under this framework, we study two fundamental problems: online configuration selection and Pareto configuration identification. For online configuration selection, we propose a hypervolume-based UCB algorithm that optimizes an optimistic hypervolume-per-cost index. We establish a budgeted regret bound of order

O\bigl(\sum_{i\ne i^\star}\frac{\log B}{Δ_i}\bigr)

, where

B

is the evaluation budget,

i^\star

is the optimal configuration in terms of hypervolume efficiency, and

Δ_i

is the corresponding efficiency gap of configuration

i

. This bound retains the logarithmic budget dependence of classical single-objective budgeted bandits. For fixed-budget Pareto identification, we develop a cost-aware empirical gap elimination algorithm and prove that its error probability is of order

O\bigl(\exp(-\frac{B}{H_{μ,c}})\bigr)

, where

H_{μ,c}

is a cost-aware Pareto identification complexity depending on configuration costs and Pareto classification gaps. This error probability decays exponentially with the evaluation budget and recovers the standard Pareto set identification guarantee when all configuration costs are identical. Experiments on LLM configuration evaluation tasks demonstrate that the proposed framework enables efficient online decision-making and accurate cost-aware Pareto identification under limited budgets.

Bo Xue, Zhi Hong, Jiayi Li +3

City University of Hong Kong · South China University of Technology · Zhejiang University

Multi-Armed Bandits LLM Evaluation Multi-Objective Optimization Pareto Optimization

Aug 5, 2026

Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

This paper studies generalized low-rank matrix bandits with multiple prioritized objectives. At each round, the learner selects a matrix-valued arm and observes a vector-valued reward, whose components correspond to multiple objectives with different priority levels. Each objective is governed by an objective-specific generalized low-rank matrix model, and the learner evaluates arms according to a lexicographic preference order, prioritizing higher-level objectives before lower-level ones. We propose Lexi-LowGLM, an efficient online algorithm that first estimates objective-specific low-rank subspaces and then performs lexicographic learning in the reduced feature spaces. Unlike existing single-objective algorithms that repeatedly solve a batch generalized linear estimator using all historical observations, Lexi-LowGLM updates each objective-specific estimator via an online Newton step, reducing the estimator-update complexity over

T

rounds from

O(T^2)

to

O(T)

. We establish a regret bound of

\widetilde O\left(W_i^{\rm lex}\sqrt{m}\,(d_1+d_2)r\sqrt{T}\right)

for each objective

i\in[m]

, where

r

is an upper bound on the ranks of the objective-specific parameter matrices and

W_i^{\rm lex}

characterizes the lexicographic trade-off effect. This bound depends on the effective low-rank dimension

(d_1+d_2)r

rather than the ambient dimension

d_1d_2

. Numerical experiments further validate the effectiveness and computational efficiency of the proposed method.

Bo Xue, Ji Cheng, Haodong Jing +2

City University of Hong Kong. · Xi’an Jiaotong University. · Northwestern Polytechnical University.

Multi-Armed Bandits Combinatorial Multi-Armed Bandits Generalized Linear Bandits

Aug 4, 2026

Dynamically Allocating Evaluation Effort for Model Ranking

While human evaluation is the gold standard in many NLP tasks, it suffers from prohibitive costs and poor scalability. When identifying top-performing models, typical evaluation protocols waste effort by exhaustively evaluating all models on the entire benchmark, a safe but inefficient approach. In this work, we formalize multi-model human evaluation as a best-arm identification problem in a multi-armed bandit setup with correlated arms, where pulling an arm corresponds to human-evaluating a model. By sampling adaptively based on the intermediate model rankings obtained on the samples so far, we can focus the annotation budget on the most competitive models. We prove the optimality of the proposed algorithms and show that it improves discrimination between top-performing models. This makes evaluations faster, cheaper and more aligned with large-scale competition evaluation goals.

Vilém Zouhar, Julia Kreutzer, Alon Lavie +4

ETH Zurich · Cohere Labs · Carnegie Mellon University +3

Model Selection Multi-Armed Bandits Human-in-the-Loop Evaluation Best-Arm Identification

Aug 2, 2026

Dominant Arm Identification with Mixing and Recycling Observed Samples

We study the problem of identifying the dominant arm in multi-armed bandits, where the objective is to find the action with the highest probability of exceeding the realized rewards of all other actions. Conventional mean-based and pairwise comparison-based algorithms often fail to identify the arm with the highest realized reward. To address this challenge, we introduce a novel dominant arm criterion and an efficient estimator with theoretical guarantees. Our approach relies on two key technical innovations: (i) a dominance score criterion that an arm beats the locally dominant over the partitioned reward space and (ii) a joint mixing and recycling mechanism coupled with a doubly robust estimator that guarantees simultaneous convergence of the empirical distribution functions for all arms. These key innovations pave a way to efficient computation of global arm dominance. Our proposed elimination algorithm identifies the best dominant arm with nearly optimal rate of sample complexity. Numerical experiments demonstrate that our algorithm consistently achieves exact recovery of the true dominant arm, outperforming existing baselines.

Jonghyun Sim, Wonyoung Kim

Chung-Ang University, Seoul, Republic of Korea.

Multi-Armed Bandits Best-Arm Identification

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 Bandits Non-Stationary Bandits Contextual Bandits

Aug 2, 2026

Sharp Characterization of Bias in Post-Bandit Inference

Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected

Z

-statistic, in bandit experiments of fixed horizon

T

. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order

\sqrt{\log T}

, and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate

1/\sqrt{\log T}

. We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. We further show how bias most severely distorts confidence intervals and hypothesis tests when the tested arm is one of the tied-optimal arms. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm's sampling dynamics, which may be of independent interest.

Lisu Wang, Yilun Chen, Jiaqi Lu

School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen

Multi-Armed Bandits Algorithmic Bias UCB Algorithms

Jul 31, 2026

Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment

This paper studies the policy gradient update for a multi-arm bandit problem in diffusion environment that is described by a stochastic differential equation (SDE) under the continuous-time reinforcement learning framework by Wang et al. (2020), Jia and Zhou (2022b). With the logit parameterization for the stochastic policy, we show that it converges almost surely to the optimal arm under an arbitrary constant learning rate. Furthermore, we derive the non-asymptotic regret upper bound when the constant learning rate is below a time-invariant threshold; and the regret bound has order

O(\log T)

. We improve the analysis in Lattimore (2026a) for the same SDE by constructing a novel Lyapunov function and demonstrate the transparency of analyzing policy gradient using the tools in SDEs. In addition, the same Lyapunov function is also helpful in analyzing the discrete-time policy gradient algorithm.

Yanwei Jia, Du Ouyang

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong SAR · Department of Mathematical Sciences, Tsinghua University, Beijing, Beijing 100084, China

Multi-Armed Bandits Regret Minimization in RL Continuous-Time RL Policy Gradient Methods Policy Learning

Jul 31, 2026

Parameter-Free Heavy-Tailed Bandits

Heavy-tailed distributions arise naturally in sequential decision-making problems such as financial investment, online advertising, and network management, where rare but extreme outcomes can dominate performance. Heavy-tailed bandits model online decision-making in these settings by assuming only that rewards

X

satisfy

\mathbb{E}[|X|^{1+ε}]\leq u

, for some tail exponent

ε\in(0,1]

and moment bound

u<+\infty

. However, most existing regret minimization algorithms require these parameters to be known. This assumption is particularly restrictive in practice:

ε

and

u

govern the frequency and magnitude of rare events and are therefore precisely the quantities that are hardest to infer reliably from limited observations. Motivated by an open problem posed by Genalti and Metelli at COLT 2025, we resolve the assumption-free adaptation problem for heavy-tailed bandits and characterize the price in the regret of not knowing the tail parameters. We first study adaptation to the moment bound

u

for a fixed tail exponent

ε

. We prove that every algorithm unaware of

u

, or of any upper bound on it, must obey a sharp trade-off between its distribution-dependent and distribution-free regret guarantees. We then introduce a scheduled-exploration algorithm that requires no knowledge of

u

and matches the resulting adaptation frontier up to logarithmic factors. Finally, we show that the same algorithm can be instanced without knowing

ε

by calibrating its exploration schedule to the endpoint

ε=1

. It achieves sublinear regret for every fixed

ε>0

, while no algorithm can guarantee sublinear regret uniformly over all

ε\in(0,1]

. Altogether, our results resolve the COLT open problem without additional distributional assumptions and provide a sharp characterization of the statistical cost of adapting to unknown heavy tails.

Gianmarco Genalti, Alberto Maria Metelli

Politecnico di Milano

Multi-Armed Bandits Heavy-Tailed Noise Heavy-Tailed Distributions

Jul 31, 2026

The Greedy Advantage in Finite-Horizon Bandits

Organizations increasingly rely on sequential experimentation to improve decision-making. While the multi-armed bandit literature has developed algorithms with strong asymptotic regret guarantees, many practical applications operate over finite and externally imposed horizons. Motivated by the finite-horizon setting, we develop a class of regularized greedy algorithms for multi-armed Bernoulli bandits. We derive the first finite-horizon regret envelopes for regularized greedy bandits, showing that finite-horizon regret decomposes into transient exploration costs and a suboptimal convergence term that decays exponentially with the regularization strength. This characterization yields principled calibration rules for the regularization parameters and, as a limiting case, sharper regret guarantees for the classical greedy policy. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms. These results suggest that regularized greedy policies can provide an effective approach for finite-horizon bandit problems.

Kai Zhou, Michael Lingzhi Li, Kai Wang

Tsinghua University · Harvard Business School

Multi-Armed Bandits

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 Sampling Multi-Armed Bandits Off-Policy Evaluation Importance Sampling Contextual Bandits Policy Learning

Jul 28, 2026

Top- $k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection

We consider a stochastic multi-objective bandit problem where, at each round, the agent selects a slate of

k

arms and observes their

d

-dimensional reward vectors under semi-bandit feedback. We do not aim at identifying a single optimal arm; instead, we consider the problem of maintaining a small set of actions that jointly approximate the Pareto frontier. We formalize this objective through the dominated hypervolume induced by the selected subset of arms, and define an

α

-approximate hypervolume regret with respect to the best size-

k

subset achievable in hindsight, where

α= 1 - 1/e

reflects the approximation guarantee of greedy maximization for monotone submodular functions. To address this problem, we introduce THV-UCB, an optimistic algorithm that selects arms greedily based on optimistic estimates of their marginal hypervolume contributions. We establish a gap-free regret bound

\tilde{O}(d\sqrt{nkT})

that holds on every instance, together with a gap-dependent bound

\tilde{O}(nk^{2.5}/Δ_{\min})

that becomes polylogarithmic in

T

once the arms are sufficiently well separated. Our results provide theoretical support for using small subsets to approximate Pareto fronts in various multi-objective applications.

Nicolas Gutowski, Fabien Chhel, Alexandre Letard +1

Université d’Angers, LERIA, SFR MATHSTIC, Angers, France · ESEO, ERIS, Angers, France · AlphaEdge, Saint-Barthélémy-d’Anjou, France +1

Multi-Armed Bandits Combinatorial Multi-Armed Bandits Multi-Objective Optimization Pareto Optimization

Jul 27, 2026

Co-planning of Flight Corridors and Communication Infrastructure for Urban Drone Logistics Networks

Reliable wireless connectivity is essential for urban air mobility (UAM) networks in dense urban environments. It is therefore imperative to carefully plan the supporting communication infrastructure for UAM flight corridors. Most existing works optimize communication infrastructure and UAV flight paths independently, often leading to unnecessary base station (BS) deployment or excessive flight detours. This paper studies the joint optimization of BS deployment and UAV flight corridors in complex urban environments, aiming to minimize both infrastructure investment and flight distance while satisfying communication quality constraints. We propose CR-CMAB, a channel reciprocity-guided combinatorial multi-armed bandit framework. The framework constructs high-fidelity radio maps using 3D ray tracing, selects BS combinations via coverage-aware CMAB search, and dynamically expands the search space by identifying promising BS locations through channel reciprocity. Experimental results from a detailed case study demonstrate that CR-CMAB outperforms baseline methods with moderate computational time, yielding more strategically positioned BSs and shorter flight corridors. This study offers a practical planning perspective for cost-effective and communication-reliable UAM deployment in future smart cities.

Yingjie He, Yikang Wang, Zhenyu Gao

Multi-Armed Bandits UAV Navigation Wireless Communications Combinatorial Multi-Armed Bandits

Jul 26, 2026

Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set

Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning. In these works, the cumulative variance of the noise

Λ= \sum_{t=1}^T σ_t^2

, where

σ_t^2

is the variance of the noise at round

t

, is used to characterize the statistical complexity of the problem, yielding simple regret bounds of order

\tilde{\cal{O}}(d \sqrt{Λ/ T^2})

for

d

-dimensional linear bandits with heteroscedastic noise. However, with a closer look,

Λ

remains the same order even if the noise is close to zero at half of the rounds, which indicates that the

Λ

-dependence is not optimal. In this paper, we revisit the stochastic linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process. We propose a novel variance-adaptive algorithm VAEE (Variance-Aware Exploration with Elimination) for large action set, which actively explores actions that maximizes the information gain among a candidate set of actions that are not eliminated. With the active-exploration strategy, we show that VAEE achieves a simple regret with a nearly harmonic-mean dependent rate. For finitely many actions, we propose a variance-aware variant of G-optimal design based exploration, which achieves a simple regret with sharper dependence on

d

. We also establish a nearly matching lower bound for the fixed action set setting indicating that harmonic-mean dependent rate is unavoidable. To the best of our knowledge, this is the first work that breaks the

\sqrtΛ

barrier for stochastic linear bandits with heteroscedastic noise.

Heyang Zhao, Tianyuan Jin, Weixin Wang +3

Department of Computer Science, University of California, Los Angeles · Department of Electrical and Computer Engineering, National University of Singapore · Department of Biostatistics & Bioinformatics, Duke University +2

Multi-Armed Bandits

Jul 26, 2026

Experimentation and Commitment under Reward Shifts

Decision-makers in learning environments face a dilemma when their short-term optimal actions may not favor their long-term benefits the most. To understand the fundamental tradeoff behind the dilemma, we study adaptive experimentation with post-commitment reward shifts. During an experiment phase, the decision-maker may adaptively test multiple options; during a subsequent commitment phase, the decision-maker must commit to a single option, whose reward may differ from its pre-commitment reward. We propose the Reserved Arm Eliminations for Commitment (RAEC) algorithm, which reserves a predetermined portion of the experiment phase to identify the best post-shift option while using the remaining rounds to minimize short-run regret. We establish regret upper bounds for RAEC across all parameter regimes and matching minimax lower bounds, providing a tight characterization of the cost of balancing short-term performance and long-term commitment. A key implication is that deciding in advance how much of the experiment phase to reserve for the commitment decision is sufficient to achieve the best possible worst-case regret rate; adapting this amount as more data are observed does not improve the rate. We further study extensions with structural knowledge of reward shifts and with concave commitment rewards and portfolio choice. Numerical experiments confirm that our proposed algorithms achieve the regret predicted by our theory and outperform other baselines.

Puping Jiang, Wei Tang, Renyu +1

Philip

Multi-Armed Bandits Exploration-Exploitation Tradeoff Minimax Regret Non-Stationary Bandits

Jul 24, 2026

Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

Minimum-exposure constraints arise in recommendation, content curation, and regulated allocation when each provider, arm, or group must receive guaranteed exposure inside a period rather than only in aggregate. We study stochastic bandits with exact exposure floors and show that the right object is a rounding problem: a fractional fair schedule is realized as integral pulls, and the exposure error is exactly a discrepancy vector. The main contribution is a blockwise model with time-varying floors. BDQ-UCB satisfies every block floor deterministically and has fair regret governed by the nonmandatory budget

R

, not the horizon

T

, with high-probability regret

O(\sqrt{KR\log(KT)})

. A MOSS residual variant attains

O(\sqrt{KR})

, and a matching lower bound gives the minimax rate

Θ(\sqrt{KR})

, even with positive mandatory exposure; a kl-UCB

^{++}

residual rule adds instance-dependent optimality. The formulation becomes essential for overlapping group floors: per-arm rounding can violate a group constraint by

Ω(s)

in the group size, whereas Beck--Fiala null-space rounding meets every group floor within the block budget with violation below the arm degree

t

, and composes with UCB at the same

R

-parametrized regret. For learned group plans, we close disjoint systems at

\widetildeΘ(\sqrt{KT})

, give a dual-ledger decomposition explaining why naive index rules fail under overlap, and prove a plan-sampling rule that is pathwise feasible under an initial cover-slack condition and attains a conditional

\widetilde O(\sqrt{KT})

guarantee, leaving the condition-free overlap rate open. Experiments on synthetic floors, MovieLens-100k genre exposure, and deployment stress tests show exact feasibility without penalty tuning and regret competitive with tuned Lagrangian baselines.

Ibne Farabi Shihab, Joyanta Jyoti Mondal, Anuj Sharma

Department of Computer Science, Iowa State University, USA · Department of Computer and Information Sciences, University of Delaware, USA · Department of Civil, Construction & Environmental Engineering, Iowa State University, USA

Multi-Armed Bandits Fair Resource Allocation Group Fairness

Jul 22, 2026

Algorithmic Approaches to Sequential Decision-Making and Social Epistemology

As humans, we face many decisions that require us to choose between sticking to something and giving up. This thesis uses algorithmic tools to derive insights about such decision-making problems in theoretical models, studying both near-optimal methods and outcomes of social and behavioral influences. Along the way, this thesis sheds light on what we gain and what we lose as we move from a messy and complex real world setting to a very general abstract model by studying various points along this spectrum. In Part I, we study algorithms for sequential decision-making in the improving multi-armed bandits problem. We provide nearly matching upper and lower bounds in the general case. Then, we then ask what is possible if we have access to similar instances to the one we wish to deploy our algorithm on. To that end, we provide guarantees in the data-driven algorithm design framework, showing that a polynomial number of samples is sufficient for learning good algorithms from a class of algorithms. In Part II, we study algorithmic approaches for problems in social epistemology. We start by analyzing what role theoretical models can play in the study of social problems. We then study social and behavioral influences in decision-making requiring investment. First, we provide mathematical formalism in which to study the formation of pessimism traps, a phenomenon identified by philosophers in which agents are influenced by their predecessors to engage in less-ambitious goals. We develop financial interventions to sustainably shift communities out of these traps. The second problem we study is the influence of grit as a behavioral trait in ambitious decision-making. Overall, these works seek to theoretically model phenomena in social epistemology and provide a framework for intervening algorithmically.

Kavya Ravichandran

Toyota Technological Institute at Chicago, Chicago, IL · at the Toyota Technological Institute at Chicago Chicago, IL

Multi-Armed Bandits Sequential Decision Making Robust Multi-Armed Bandits

Jul 22, 2026

Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs

We study regret minimization for learning CDF-related objectives of the form

g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x),

over

[0,1]^2

, where

g

is a known Lipschitz function and

\mathcal{D}

is an unknown distribution. At each round

t

, the learner selects a point

x_t

and observes the binary feedback

\mathbb{I}(X_t\le x_t)

, where

X_t\sim\mathcal{D}

. We design an algorithm achieving regret

\widetilde{\mathcal{O}}(T^{7/10})

, improving over the previous best-known bound of

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

and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the

Ω(T^{2/3})

lower bound. As an application, our techniques yield the same

\widetilde{\mathcal{O}}(T^{7/10})

regret bound for profit maximization in repeated bilateral trade with fixed prices.

Matteo Castiglioni, Anna Lunghi, Alberto Marchesi

Politecnico di Milano

Multi-Armed Bandits Regret Minimization

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 Sampling Multi-Armed Bandits Contextual Bandits

Jul 16, 2026

MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

We design and analyze Mechanism-Enforced Sequential HAlving (MESHA), an algorithm for Best Arm Identification (BAI) in strategic linear bandits. In this setting, each arm may strategically misreport its feature vector to maximize the probability of being identified as the best arm, when rewards are generated from the arms' true but unobservable features. The design of MESHA applies the naïve uniform sampling rule and an epoch-wise Grim Trigger Condition (GTC): the former reduces the impact of arms' strategic behaviours and the latter eliminates arms whose reported features severely deviate from the ground truth. Considering an arbitrary Nash Equilibrium, we prove that any arm would attempt to pass the GTC check to maximize its identified probability and derive an upper bound on the failure probability of MESHA within a fixed budget

T

. We also show that state-of-the-art linear BAI algorithms with

G

-optimal design would fail in such strategic environment, as the optimal design (OD)-based sampling rule based on strategically reported features may {\it starve} the optimal arm of any sampling budget. Finally, extensive numerical experiments indicate that MESHA outperforms baselines that rely on OD-based sampling rules as well as the feature-agnostic baselines, corroborating the efficacy of MESHA.

Xin Li, Zixin Zhong

Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou)

Multi-Armed Bandits Mechanism Design Sequential Decision Making Best-Arm Identification

Jul 15, 2026

Adaptive Ad Load Design for Sponsored Search Markets: Evidence, Theory, and Deployment

Ad-load design is a central supply-side decision in sponsored search: more sponsored slots can raise revenue, but may crowd out organic results and degrade user outcomes. We study this trade-off using a large-scale randomized field experiment on an Android app store, where over five million users are exposed to one through six sponsored slots. Increasing ad load raises revenue by up to 43%, but reduces total search conversions by up to 5% and daily engagement by up to 2.2%. These average effects mask substantial heterogeneity: additional slots generate large revenue gains for high-ad-conversion queries, but little or negative marginal revenue for low-conversion queries. The trade-off also shifts within query as advertiser composition changes, such as brand-advertiser presence. Motivated by these findings, we design and deploy a novel adaptive algorithm -- exploration-augmented Locally Adaptive Ad Load (e-LAAL). e-LAAL combines LAAL, a model-free query-level decision rule that updates ad-load recommendations using recent outcomes, with static exploration arms that maintain support and provide fixed-policy counterfactual benchmarks. We provide a finite-time dynamic-regret guarantee for the e-LAAL architecture. In a platform-level production deployment serving 22.3 million users and 77.6 million searches, e-LAAL improves the empirical revenue--conversion trade-off relative to deployed static benchmarks and outperforms uniform and historical query-dependent static benchmarks.

Mohammad Rashid, Hema Yoganarasimhan

University of Washington

Multi-Armed Bandits Online Advertising

Jul 15, 2026

From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing

Mobile crowdsensing (MC) recruits mobile users to perform sensing tasks using their smartphones, enabling large-scale applications such as traffic monitoring and environmental sensing. A fundamental challenge is online worker recruitment under uncertainty, where the platform must learn workers' sensing performance while operating with a limited budget. Existing learning-based MC recruitment methods typically assume that each worker's sensing quality is stationary with a fixed mean over time. In practice, however, worker performance often improves with experience and eventually stabilizes, while the incurred sensing cost can be unknown in advance due to time-varying device and context states. In this paper, we study a budget-constrained online recruitment problem in which the platform selects one worker in each round, observes the sensing quality and incurred cost, where the expected sensing quality of each worker increases with experience and eventually converges to a plateau, and repeats until the budget is exhausted. We formulate this problem as a structured bandit model where each worker's expected reward evolves according to an unknown increasing-then-converging function of its participation count, and each worker has an unknown expected cost. We develop a cost-aware online learning framework that jointly learns evolving reward trajectories and heterogeneous costs, detects performance saturation, and allocates the limited budget to maximize long-term sensing utility. We provide theoretical performance guarantees and validate the proposed approach through extensive experiments, demonstrating consistent improvements over baselines that ignore experience-driven dynamics or assume known costs.

Yin Huang, Qingsong Liu, Jie Xu

Manning College of Information and Computer Sciences, University of Massachusetts Amherst

Multi-Armed Bandits Non-Stationary Bandits Online Resource Allocation

Jul 15, 2026

Price of Fairness in Bandits: A Tight Minimax Characterization

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized

p

-mean, interpolating between utilitarian welfare (

p=1

), Nash welfare (

p\to0

), and Rawlsian fairness (

p\to-\infty

). Although tight guarantees are known for

p\ge0

, the strictly fair regime

q=-p>0

remains unresolved because negative-power means are dominated by the smallest per-round rewards. For

σ

-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret

O(k^{(q+1)/2}/\sqrt{T})

, while the only general lower bound was the classical

Ω(σ\sqrt{k/T})

. Thus it was unclear whether the extra dependence on

k

was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound

Ω(σ\sqrt{k^{\max(1,q)}/T})

; for

q>1

, this shows that the penalty

k^{q/2}

is information-theoretically unavoidable. We then introduce UCB-HARE (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is

\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})

, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that UCB-HARE improves over uniform-exploration baselines, with gains increasing as

q

grows.

Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury

1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur

Multi-Armed Bandits Minimax Regret Fair Resource Allocation Algorithmic Fairness UCB Algorithms Information-Theoretic Lower Bounds

Jul 14, 2026

Thompson Sampling Is 2-Competitive for Mistakes

We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor

2

is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.

Mark Sellke, Gregory Valiant

Thompson Sampling Multi-Armed Bandits

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

\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

\textit{white-box}

UCB-based algorithm,

\texttt{OFU-DMNL}

, that constructs assortments item-wise by maximizing optimistic marginal gains, avoids black-box optimization oracles. We show that

\texttt{OFU-DMNL}

achieves at least a

(1-\frac{1}{e+1})

-

\textit{approximate}

regret bound

\tilde{O}\left(d \sqrt{T/K}\right)

, where

d

is the context dimension,

K

the maximum assortment size, and

T

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

\texttt{OFU-DMNL}

offers a statistically and computationally efficient solution.

Heesang Ann, Taehyun Hwang, Min-hwan Oh

Seoul National University

Multi-Armed Bandits Discrete Choice Modeling Contextual Bandits Assortment Optimization

Jul 13, 2026

Fundamental Limitations of Fixed-Budget Best-Arm Identification

In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across

K

arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any

K\ge 3

and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most

\left(1 + \frac{\log(K)}{8}\right)^{-1}

times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.

Motti Goldberger

Yale University

Multi-Armed Bandits Best-Arm Identification Information-Theoretic Lower Bounds

Jul 13, 2026

Link Adaptation Using Joint-Thompson Sampling

The choice of Modulation and Coding (MCS) type for a particular channel condition is made through link adaptation (LA) algorithms that operate at the MAC layer. These algorithms rely on the ACK/NACK statistics and the channel quality index (CQI) feedback. Several existing works model LA as a multi-armed bandit (MAB) problem across cellular and Wi-Fi links. In the MAB formulation, each available MCS is a Bernoulli arm parameterized by its transmission success probability, and the goal is to design a selection strategy that accrues maximum reward. Several popular MAB algorithms, such as upper confidence bound (UCB) and Thompson Sampling (TS), have been proposed in the literature. Using the fact that MCS success probabilities are ordered, we propose the Joint-Thompson Sampling (Joint-TS) algorithm. Unlike classical TS, which assumes independent Beta distributions for each arm, Joint-TS utilizes a multivariate ordered Beta distribution as the prior to preserve the inherent monotonicity of success probabilities. Our simulation results show that while existing MAB algorithms fail in specific scenarios, Joint-TS delivers competitive throughput with robust, consistent performance in all scenarios.

Vignatha Vinjam, Manjunath Kolavennu, Myna Vajha +1

Department of EE, IIT Hyderabad · Department of AI, IIT Hyderabad

Thompson Sampling Multi-Armed Bandits Wireless Communications Wireless Resource Allocation

Jul 12, 2026

Learning from Local Walks on Dynamic Graphs with Bandit Feedback

We study stochastic multi-armed bandits on dynamic graphs, where arms correspond to the vertices of a network with time-varying edges. In this setting, the learner is restricted to local movement, selecting only its current node or an immediate neighbor at each round. This constraint decouples best-arm identification from exploitation: even after the optimal arm is identified, the learner may remain unable to reach it through the evolving topology. We identify a process-agnostic structural condition, based on sliding-window mixing, that ensures the graph's intrinsic walk remains stable for both exploration and navigation. Under this regime, we analyze a family of local explore-then-commit algorithms and establish sublinear expected regret. Our framework includes a reward-aware strategy, for which we prove a worst-case safety theorem and a separate performance gain theorem.

Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1

Department of Computer Science, University of Colorado, Boulder, CO 80309, USA · INRIA, Paris, France

Multi-Armed Bandits Graph Bandits Exploration-Exploitation Tradeoff

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 Bandits LLM Routing Contextual Bandits

Jul 9, 2026

Optimal Top- $k$ Identification from Pairwise Comparisons

We study the active learning problem of fixed-confidence top-

k

identification from noisy pairwise comparisons. In this problem, an algorithm sequentially chooses pairs of items to compare, observes the outcomes, and stops when it can return the set of top-

k

items with error probability at most

δ

. The objective is to design such a

δ

-correct procedure that minimizes the expected number of comparisons (the sample complexity). This problem falls within the broader literature on fixed-confidence pure exploration in bandit models, where a common target is asymptotic optimality: the algorithm's expected sample complexity matches the information theoretic lower bound as

δ\to 0

. Asymptotically optimal procedures have been developed for a range of fixed-confidence pure-exploration problems, however to the best of our knowledge, for top-

1

, or more generally top-

k

identification from pairwise comparisons under latent utility models an asymptotically optimal algorithm has not been established. In this setting, we develop such an algorithm. We characterize the structure of the lower bound and formulate it as a saddle-point problem. This structure enables a computationally efficient primal-dual procedure that learns the asymptotically optimal comparison allocation online. We then construct an adaptive comparison-allocation algorithm that tracks the allocation learned by the primal-dual procedure and prove it is asymptotically optimal.

Motti Goldberger, Nils Rudi

Yale University, New Haven, CT, USA.

Pairwise Preference Learning Multi-Armed Bandits Pairwise Comparison Pairwise Preference Evaluation Pairwise Ranking Best-Arm Identification

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

\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 Bandits Contextual Bandits