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.

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 (

\mathcal{O}(1)

computational complexity with respect to current round

t

and the time horizon

T

), which simultaneously achieves an almost optimal regret of

\widetilde{\mathcal{O}}(T^{\frac{1}{1+ε}})

where

T

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 Bandits Heavy-Tailed Noise Online Mirror Descent Contextual Bandits Generalized Linear Bandits

Jul 8, 2026

Best-Arm Identification with Generative Proxy

Best-arm identification is a canonical model for data-driven decision-making, but in many applications each reward observation is costly. Motivated by the growing availability of cheap predictions from machine learning and large language models, we study fixed-confidence best-arm identification in which each costly reward pull is paired with a cheap but correlated proxy score. The marginal mean of the proxy can be estimated offline and is treated as known, whereas its correlation

ρ

with the reward, which governs how much the proxy helps, is unknown and must be learned online in pair with real rewards. We show that a control-variate adjustment turns this model into a heteroscedastic identification problem whose oracle sample complexity improves by residual variance

1-ρ^2

. The central difficulty is that the correlation must be learned from the same costly samples that identification consumes online, and that a plug-in estimate of the residual variance is anti-conservative and can compromise correctness. We propose PROBE (PRoxy OLS for Best-arm Exploration), a phase-elimination algorithm that directly maintains an upper certificate on the residual variance with an ordinary least squares fit, whose exact chi-square law keeps the certificate valid regardless of the unknown correlation. We prove that PROBE is

δ

-PAC and attains the known-correlation oracle sample complexity up to a constant multiplicative factor and a constant additive calibration cost. The guarantee extends to the

(ε,δ)

-PAC setting under minimal changes to the algorithm. Numerical experiments on synthetic instances and on an auto-loan pricing replay with large language model and tabular proxies confirm that the sample savings of PROBE scale with the strength of the reward-proxy correlation, exactly as the theory predicts.

Tianyi Ma, Hanzhang Qin, Ruihao Zhu +1

School of Operations Research and Information Engineering, Cornell University · Department of Industrial Systems Engineering and Management, National University of Singapore · SC Johnson College of Business, Cornell University +1

Multi-Armed Bandits Best-Arm Identification

Jul 6, 2026

Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time step and receives noisy rewards that reflect the preferences of the matched agents, following a semi-bandit feedback structure. We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability. Our work extends prior results by handling two-sided uncertainty and by exploiting partial preference information. A central ingredient is the notion of pervasive stable matching, which enables the identification of optimal stable matchings under partial preferences. We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences, and provide a refined sample-complexity analysis. Beyond pure exploration, we extend our approach to regret minimization and establish regret bounds with respect to the optimal stable matching that avoid dependence on the minimum reward gap

Δ_{\min}

.

Andreas Athanasopoulos, Anne-Marie George, Christos Dimitrakakis

University of Neuchâtel, Neuchâtel, Switzerland · University of Oslo, Oslo, Norway

Multi-Armed Bandits Preference Learning

Jul 5, 2026

Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis

This paper studies the problem of identifying the treatment that maximizes the expected natural direct potential outcome (NDPO), which captures the potential outcome of an intervention while excluding the pathway transmitted through a mediator that researchers may wish to remove from evaluation. We first establish population-level identification of the expected NDPO in a causal bandit setting using observable interventional distributions. We then develop a fixed-confidence best-arm identification (BAI) algorithm based on the Track-and-Stop (TaS) framework, employing a cutting-set method to solve the resulting semi-infinite optimization problem. The proposed algorithm achieves sample-efficient identification with a high-probability correctness guarantee. We prove that it satisfies

δ

-correctness and asymptotic optimality. Finally, we validate the approach through empirical evaluations on a large-scale real-world advertising dataset (IPinYou).

Harsh Shrivastava, Yuta Kawakami, Junpei Komiyama +1

Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi, UAE · RIKEN AIP, Tokyo, Japan

Multi-Armed Bandits Causal Effect Estimation Causal Mediation Analysis Best-Arm Identification Causal Inference

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

N

sets of items, where each item is represented by a

d

-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

\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

\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

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

and

\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

\text{poly}(N)

time per round despite

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 Bandits Contextual Bandits Combinatorial Multi-Armed Bandits Generalized Linear Bandits

Jun 28, 2026

A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming

We address the problem of online multi-human multi-robot teaming through the lens of a linear matching bandit framework, where a learner assigns robots with unknown features from a fixed pool to distinct sets of human agents over multiple rounds. To solve this problem, we propose LinMatch, an online learning algorithm that updates the confidence intervals of the unknown features and makes the optimistic matching under uncertainty. The contributions and novelty of this work are twofold. First, we recast the optimistic matching problem in each round as a linear program of maximum weighted matching, efficiently solvable by the celebrated Hungarian algorithm. Second, we provide novel bounds for matching with linear feature problems, showing an upper bound of

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

and a minimax lower bound of

Ω(d\sqrt{MKT})

, establishing a tight optimal regret rate of

\tildeΘ(d\sqrt{MKT})

. This demonstrates that LinMatch achieves strictly optimal achievable regret with respect to the total number of rounds

T

, the feature dimension

d

, and the matching parameters

M

and

K

. The proposed algorithm and bounds apply to a wide range of matching problems with applications beyond human-robot matching, such as housing allocation, recommendation systems, and more.

Yaohui Guo, X. Jessie Yang, Cong Shi

Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48105

Multi-Armed Bandits Human-Robot Collaboration Multi-Robot Task Allocation

Jun 28, 2026

Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition

We study the Bayesian fixed-budget best-arm identification problem in which a learner can abstain from making a terminal recommendation. Subject to an abstention budget

α

, we analyze the probability of undetected error--the risk of recommending a suboptimal arm without abstaining. Our central finding is that abstention induces a phase transition: without abstention, the error probability decays polynomially in the sampling budget

T

; in contrast, introducing any small positive abstention budget shifts this to an exponential decay. For Gaussian priors and rewards, in the regime

T\to\infty

followed by

α\downarrow0

, we establish exact matching information-theoretic lower bounds and algorithmic upper bounds on the optimal error exponent, which takes the form

\exp(-\frac{α^{2}T}{8κ_ν^{2}})

. The hardness parameter

κ_ν

represents the prior density of the top-two gap at zero, highlighting that nearly tied instances drive the fundamental error. We introduce an adaptive algorithm, PGWS, that successfully achieves this optimal exponent by expending its abstention budget on statistically ambiguous instances. We further demonstrate that this polynomial-to-exponential improvement is exclusively a Bayesian phenomenon--in the frequentist setting, abstention only affects lower-order exponent terms. We also extend our results beyond the Gaussian model.

Yuqi Huang, Yunlong Hou, Vincent Y. F. Tan

Department of Mathematics, National University of Singapore · Department of Electrical and Computer Engineering, National University of Singapore

Multi-Armed Bandits Best-Arm Identification Bayesian Decision Theory

Jun 26, 2026

Randomized Exploration for Linear Bandits via Absolute Perturbations

In stochastic linear bandits, the canonical Upper Confidence Bound (UCB) algorithm admits a simple frequentist regret analysis but can be computationally demanding, while Thompson Sampling (TS) is computationally attractive yet typically harder to analyze due to its non-optimistic nature. We propose Absolute Thompson Sampling (ATS), a simple modification of TS that ensures optimism in expectation by replacing the signed exploration noise with its absolute value. This preserves the computational efficiency of TS while avoiding the technically involved anti-concentration arguments common in TS analyses, enabling a simple UCB-style regret analysis. We show that ATS achieves

\tilde{O}(d^{3/2}\sqrt{K})

regret, matching existing bounds for TS in linear bandits. We further introduce Ensemble Absolute Thompson Sampling (EATS), which takes the maximum over multiple absolute perturbations with normalization by the ensemble size. As the ensemble size grows, EATS converges to the UCB objective, recovering UCB behavior in the limit. Experiments show that moderate ensemble sizes already yield strong performance. Our results point to a bridge between randomized exploration and deterministic optimism both in theory and practice.

Toshinori Kitamura, Shuai Liu, Csaba Szepesvári

Department of Computing Science, University of Alberta, Canada

Thompson Sampling Multi-Armed Bandits UCB Algorithms

Jun 26, 2026

Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

Contextual bandits with graph-structured arms arise in recommendation, citation retrieval, and social advertising, where arms connected on a graph tend to share reward signal. Standard dimensionality reduction ignores this structure, inflating exploration cost by a factor of

d/k

. We propose GraphDR-LinUCB, which projects arm features onto the graph's low-frequency spectral subspace and runs linear UCB in the resulting

k

-dimensional space. We prove the first

\wtO(k\sqrt{T})

regret bound for spectral-projection-based contextual bandits, reducing dimension dependence from

d

to

k

; a perturbation argument extends this to noisy graphs, with an explicit penalty for reward-smoothness mismatch and graph-estimation error. Our central theoretical finding is that the high-frequency reward component need not incur a worst-case linear-in-

T

penalty: its actual cost depends on its realized impact along the played path, not on its total energy. A simple spectral comparison between subspaces (

Γ_k

) predicts which reducer wins on a given dataset, correctly calling five of six real-dataset outcomes without any fitted threshold. Across a synthetic benchmark and six real datasets (MovieLens, Amazon, LastFM, ogbn-arxiv, MIND), GraphDR-LinUCB reduces cumulative regret by

15\times

over full-dimensional LinUCB and outperforms competing graph-aware methods on five of six; the single failure is precisely where the graph's spectral subspace is misaligned with the reward.

Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj Sharma

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

Multi-Armed Bandits Graph Bandits Contextual Bandits Dimensionality Reduction Linear Contextual Bandits

Jun 25, 2026

Learning in Markovian bandits with non-observable states and constrained decision epochs

This paper studies the problem of regret minimization in Markovian bandits with non-observable states and possibly constrained decision epochs. The focus is restricted to a ``pure'' regret benchmark, that compares the performance of the learning algorithm to the best pure policy which -- akin to optimal policies of stochastic bandits -- picks the optimal arm from start to finish without ever switching. We introduce a generalization of rested Markovian bandits, self-degrading Markovian bandits, for which pure policies are always asymptotically optimal.We show that without prior knowledge on the underlying bandit, the regret of algorithms that switch arms rarely necessarily scales super-logarithmically for every bandit, i.e., as

ω(\log(T))

, where

T

is the learning horizon. Despite the unreachability of the logarithmic regime, we design UCB-NOM, an optimistic algorithm inspired by UCB, of which the regret is nearly logarithmic. Lastly, we show that given prior knowledge on the Markovian bandit in the form of a bound on the bias functions of its arm, a proper instantiation of UCB-NOM achieves

O(\log(T))

regret. We further show that this prior knowledge allows for a

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

worst-case regret bound for UCB-NOM. Notably, our regret bounds do not depend on the number of states of the underlying Markov chains. Our findings suggest that the non-observability of states is a mild inconvenience in self-degrading Markovian bandits.

Thomas Hira, Victor Boone, Urtzi Ayesta +1

IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · Ikerbasque-UPV/EHU, University of the Basque Country, Bilbao, Spain

Multi-Armed Bandits Markov Models UCB Algorithms

Jun 25, 2026

Target-Aware Bandit Allocation for Scalable Surrogate Optimization in Chemical Space

Identifying high-utility candidates from massive discrete spaces under expensive evaluations is a recurring challenge across the sciences, with structure-based drug discovery as a prominent example. While surrogate-based optimization can increase sample efficiency by reducing the number of expensive evaluations, modern molecular libraries have reached billions to trillions of compounds, making full-library surrogate inference itself a major computational bottleneck. We introduce BOBa, a bandit-guided surrogate optimization framework that eliminates full-library inference by adaptively allocating computation across partitions of the action space. By treating partitions as arms in a multi-armed bandit, BOBa concentrates inference and evaluations on empirically promising partitions while maintaining principled exploration. Experiments on real-world synthesis-on-demand libraries demonstrate that optimism-under-uncertainty bandits, combined with meaningful action space partitioning, are essential for effective allocation of inference and evaluations. Our findings reveal a tunable tradeoff between screening performance and surrogate inference cost, which supports practical optimization over current libraries, and establishes a viable route to ultra-large library virtual screening.

Mohammad Haddadnia, Yuvan Chali, Abhilash Jayaraj +4

Dana-Farber Cancer Institute, Boston, MA, USA · Department of Biological Chemistry and Molecular Pharmacology, Harvard Medical School, Boston, MA, USA · Department of Biostatistics, Harvard T.H. Chan School of Public Health, Boston, MA, USA +4

Multi-Armed Bandits Molecular Optimization Surrogate-Assisted Optimization Virtual Screening Drug Discovery

Jun 22, 2026

Leveraging Similarities in Multi-Armed Bandits

In many online learning and bandit problems, the actions we consider possess inherent similarities--for instance because they share latent traits, tags, or hierarchical structure. We study online learning with a similarity-structured action set, encoded by a rooted tree whose leaves are the actions and whose levels quantify how closely two actions are related. The loss sequence is assumed tree-compatible: losses of similar actions are constrained to be close. We establish an impossibility result showing that usual one-point bandit feedback cannot, in general, leverage range or tree-induced similarity, even under very strong similarity constraints. We then provide a unified set of algorithms which adapt to a wide range of richer feedback models, from semi-bandit feedback down to multi-point bandit protocols, including the minimal two-point feedback setting. We show these algorithms exhibit best-of-both-worlds guarantees and provably exploit action similarities by replacing the number of actions

K

by a similarity-aware effective number of actions

K_{\mathrm{eff}}

in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve

\sqrt{T}

regret in Lipschitz bandits when

d \leq 2

.

Khaled Eldowa, Thibaud Rahier, Augustin Cablant +2

Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France · Criteo AI Lab, Paris, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France

Multi-Armed Bandits Adversarial Bandits

Jun 22, 2026

Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy

Minimax risk and regret are expectation-based criteria and do not capture rare but consequential failures. To address this concern, we develop a

δ

-explicit minimax-quantile theory for interactive statistical decision making (ISDM). We first provide structural relations between minimax quantiles, lower minimax quantiles, and minimax risk. This includes a quantile-to-expectation conversion and an equivalence between strict and lower minimax quantiles outside a countable set of confidence levels. We then derive two converse tools for ISDM: a high-probability interactive Fano's method and a high-probability interactive Le Cam's method. Then, we show that mutual-information (MI) privacy can be handled in the same framework by restricting the admissible decision class. For coordinatewise Gaussian privatization, we derive a two-point template that isolates the privacy-induced variance inflation. We instantiate this template for Gaussian mean estimation, and use the same two-point strategy directly for two-armed Gaussian bandits. We then derive a minimax quantile lower bound for the

K

-armed Gaussian bandit problem, showing that the interactive Fano method captures the exploration cost over multiple possible best arms. The resulting lower bounds are explicit in the confidence level

δ

and in the privacy budget for the private problems. They yield

\log(1/δ)/n

scaling for squared-error Gaussian mean estimation,

\sqrt{T\log(1/δ)}

scaling for two-armed bounded-mean Gaussian bandits, and

\sqrt{KT\log(1/δ)}

-type scaling for the

K

-armed bandits, with privacy appearing through a Gaussian variance-inflation factor for the private problems.

Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering +1

Department of Information Science and Engineering (ISE) KTH Royal Institute of Technology

Multi-Armed Bandits Decision-Making under Uncertainty Information-Theoretic Lower Bounds

Jun 20, 2026

Selective Ensemble Based on Preference-Directed Multi-Objective Bandits

Selective ensemble for modern machine learning systems requires choosing promising model candidates under limited evaluation budgets, while downstream tasks often specify only partial preferences over capabilities such as accuracy, robustness, and reasoning. This setting naturally gives rise to a sequential decision problem under partially specified linear preferences. We formalize it as preference-directed multi-objective bandits (PDMOB), where admissible trade-offs are represented by a polyhedral preference cone. Based on this formulation, we introduce Pareto

C

-optimality, which recovers standard Pareto optimality and single-weight scalarization as special cases. We then propose the preference-directed upper confidence bound (PrefUCB) algorithm, which maintains directional confidence intervals to guide exploration. We analyze both indicator-based and gap-weighted regret, and establish instance-dependent logarithmic bounds for both criteria, recovering the optimal logarithmic dependence on the horizon

T

in classical special cases. Experiments on large pre-trained model selective ensemble tasks and online asset allocation under institutional mandates validate the efficacy of our method.

Lanjihong Ma, Zhen-Yu Zhang, Masashi Sugiyama +1

Department of Computer Science, Zhejiang Gongshang University, China · Center for Advanced Intelligence Project, RIKEN, Japan · Graduate School of Frontier Sciences, The University of Tokyo, Japan +1

Multi-Armed Bandits Ensemble Learning UCB Algorithms Combinatorial Multi-Armed Bandits Pareto Optimization Preference Learning

Jun 18, 2026

Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach

This paper considers stochastic linear contextual bandits (SLCB) with bounded reward noise. Existing works typically assume sub-Gaussian reward noise and bounded expected rewards, under which the optimal regret bound scales as

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

in terms of horizon

T

. However, in many applications, realized/observed rewards are also naturally bounded, implying bounded reward noise. Bounded noise is more informative than the sub-Gaussian condition but has not been leveraged explicitly in the SLCB literature. In this paper, we propose a novel algorithm SME-OFU by utilizing an uncertainty quantification method called set-membership estimation (SME) and applying the principle of optimism in the face of uncertainty (OFU). Our algorithm enjoys an improved regret bound

O(\log T)

. Notice that this does not contradict the existing optimal bound

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

for sub-Gaussian noise because bounded noise is a stronger condition. Finally, simulations show empirical improvements of SME-OFU over a benchmark algorithm designed for sub-Gaussian noise when the reward noise is bounded.

Haonan Xu, Yingying Li

The Grainger College of Engineering University of Illinois Urbana-Champaign Champaign, IL, 61801

Multi-Armed Bandits Contextual Bandits UCB Algorithms Linear Contextual Bandits

Jun 18, 2026

Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning

We study a multi-agent multi-armed bandit problem in the competitive setup with two-sided matching markets under a human centric decision making model. To capture human preferences, we use cumulative prospect theory (CPT) that weighs the actions of the agent in a nonlinear fashion using a (

α

-Hölder continuous) weight function. CPT has been widely used in behavioral economics and risk sensitive machine learning to emulate human preferences. We analyze the state-of-the-art learning algorithm with CPT weight distorted rewards and obtain a player optimal regret of

\mathcal{O}(K\log T \left(\frac{1}Δ\right)^{2/α})

, where

K

denotes the number of arms,

T

is the learning horizon, and

Δ

represents (suitably defined) players' minimum preference gap. Noticing the dependence on

Δ

to be sub-optimal, we further improve this regret by judiciously selecting the active set of arms during exploration, which removes the dependence on

K

in the dominant term and achieves an improved (optimal) regret guarantees in the setting where the number of arms

K

is significantly larger than the number of players

N

. In addition, we consider adversarial markets where the observed rewards of the agents may be corrupted. We propose and analyze algorithms for robust markets with CPT as risk sensitive measure in both settings where the total corruption budget is known and where it is unknown, and establish logarithmic player-optimal regret guarantees in both cases.

Ananya Kunisetty, Avishek Ghosh

Indian Institute of Technology Bombay, Mumbai 400076, India

Multi-Armed Bandits Decision-Making under Uncertainty Adversarial Bandits

Jun 18, 2026

Manifold Bandits: Bayesian Curriculum Learning over the Latent Geometry of Large Language Models

Reinforcement learning (RL) is a central approach for improving reasoning capabilities in large language models (LLMs), where training efficiency depends critically on how problems are sampled during optimization. Existing adaptive curriculum learning methods typically prioritize prompts of intermediate difficulty, treating problem selection as a standard bandit problem with independent arms and overlooking the structured, heterogeneous nature of the task space. In this work, we frame problem sampling as a manifold-structured bandit problem with endogenous non-stationarity: problems are related through the model's latent representation space, and sampling decisions can steer how learning signals evolve across that space. To operationalize this perspective, we introduce Bayesian Manifold Curriculum (BMC), a structure-aware framework that organizes problems into a hierarchical task tree and applies Bayesian learning to guide sampling. Empirically, we find that different sampling strategies induce non-trivial tradeoffs between productivity (learning signal), diversity (coverage of the task manifold), and utility (evaluation relevance). These results show that prioritizing difficulty alone is insufficient for strong downstream performance, highlighting the importance of incorporating structure and type-awareness into problem sampling.

Darrien McKenzie, Nicklas Hansen, Xiaolong Wang

University of California, San Diego

Multi-Armed Bandits RL for Language Model Reasoning Curriculum RL

Jun 17, 2026

Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits

Identifying Pareto optimal solutions is critical to support multi-objective decision-making. We introduce the first anytime Multi-Objective Multi-Armed Bandit algorithm for the Pareto Set Identification problem, taking a Bayesian approach: Top-Two Pareto Front Thompson Sampling (TTPFTS). We benchmark TTPFTS against state-of-the-art fixed-budget Pareto Set Identification algorithms on synthetic environments. Next, we demonstrate its practical utility in a challenging multi-objective molecular discovery setting by efficiently exploring an ultra-large synthesis-on-demand molecular library. Furthermore, we introduce a novel uncertainty quantification metric that estimates our algorithm's confidence in the predicted Pareto set. We demonstrate that this metric effectively proxies true performance, yielding a robust methodology for monitoring learning progress in complex settings. Finally, we complement these empirical findings with a theoretical proof of the algorithm's asymptotic correctness.

Lennert Saerens, Bram Silue, Eleni Litsa +2

Artificial Intelligence Lab, Departement of Computer Science, Vrije Universiteit Brussel, Brussels, Belgium · imec, Leuven, Belgium

Thompson Sampling Multi-Armed Bandits Combinatorial Multi-Armed Bandits Pareto Optimization

Jun 16, 2026

Sequential Hiring of Contingent Workers Through Learning-Based Optimization

In this paper, we study a sequential workforce management problem in a contingent labor setting with uncertainty in both worker production and labor supply. A firm seeks to maximize cumulative profit by maintaining an active team of fixed size while learning worker productivity over time. We emphasize two critical operational frictions in this problem: replacing workers is costly, and workers may not be available immediately for hiring because of, for example, prior job commitments, scheduling constraints, or onboarding procedures. Thus, hiring decisions take effect only after a random delay. We formulate this problem as a stochastic multi-play bandit with costly switching and delayed actions, and develop a learning-based hiring policy, DR-UCB (DelayedReplacement-UCB), that makes replacement and hiring decisions sequentially through learning cycles. In each cycle, the policy uses real-time production data to determine when to initiate workforce changes and which workers to replace and hire. We show that the leading-order regret of the proposed policy matches its lower bound in its dependence on the time horizon. Our numerical experiments show that DR-UCB outperforms benchmark policies.

Chris Lee, Xiuli Chao, Izak Duenyas

Department of Industrial and Operations Engineering, University of Michigan · Ross School of Business, University of Michigan

Multi-Armed Bandits Bandits with Delayed Feedback

Jun 16, 2026

Online LLM Selection via Constrained Bandits with Time-Varying Demand

Large Language Models (LLMs) are increasingly deployed in edge-cloud inference systems to handle diverse user tasks with heterogeneous accuracy, latency, and cost profiles. Selecting the appropriate LLM for each incoming task is critical for ensuring service quality and efficient resource utilization. However, model heterogeneity, stochastic and unknown performance characteristics, and time-varying task demands make static selection strategies inadequate. Real-world deployments often impose hard resource budgets such as monetary expenditure limits, along with soft service-level requirements such as latency guarantees. These constraints introduce additional challenges for online decision-making. We formulate this problem as a constrained stochastic bandit learning task, where the learner sequentially selects models under both packing-type (hard) and covering-type (soft) constraints, while adapting to time-varying task demand. The learner operates without access to the underlying reward, cost, or latency distributions and must rely on partial feedback. We develop a novel online learning algorithm that leverages confidence-bound estimates and demand predictions to balance reward maximization with long-term constraint satisfaction. We provide theoretical guarantees showing sublinear regret and sublinear covering constraint violations compared to an offline benchmark with full information. Experimental results on synthetic workloads demonstrate the effectiveness and robustness of our approach in dynamic, resource-constrained environments.

Yin Huang, Qingsong Liu, Jie Xu

Department of Electrical and Computer Engineering, University of Florida · Manning College of Information and Computer Sciences, University of Massachusetts Amherst

Multi-Armed Bandits Cost-Aware Inference Non-Stationary Bandits LLM Routing

Jun 12, 2026

A Complexity Measure for Active Learning in Multi-group Mean Estimation

We study a max-risk objective for active learning in a multi-group mean estimation

d

-armed bandits: a learner adaptively allocates a budget of

T

samples across

d

groups to minimize the worst-case uncertainty index

\max_{k\in[d]}σ_k^2/n_k

, where

σ_k

is the standard deviation of the distribution of arm

d

, and

n_k

is the number of times arm

d

is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a budget term, a heteroscedasticity index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the Variance Local Curvature (

\mathrm{VLC}

), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the

\mathrm{VLC}

is a reparametrization of a variance--Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced

\ell_1

geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.

Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub

Department of Industrial Engineering and Operations Research & Data Science Institute, Columbia University

Multi-Armed Bandits Active Learning Minimax Estimation Adaptive Sampling

Jun 12, 2026

Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals

The identification of optimal structures within vast arrays of interconnected data necessitates significant sampling- and computational effort. Learning and leveraging underlying signal dependencies can improve efficiency and predictive capabilities considerably, but the ubiquity of nonlinear statistical relations amplifies the complexity of such undertakings. In this paper, we develop novel generic and adaptive strategies equipped with routines for graph-based causal reward modeling, analytic reproducing kernel methods, and Taylor approximation of functional processes. We establish theoretical performance guarantees sublinear in time and linear in data volume over time. Our analyses cover robustness to a multitude of uncertainties arising from noise interference, gradual model convergence, and solution space mismatch. The framework's general appeal is substantiated by a minimalistic set of conditions or reliance on prior estimates, while various outlined modifications address specific or extended settings. To demonstrate practical effectiveness, we conduct numerical experiments using both benchmarked synthetic and real-world transportation datasets.

Christoph Bauschmann, Setareh Maghsudi

Department of Electrical Engineering and Information Technology Ruhr University Bochum Bochum, Germany

Reward Modeling Multi-Armed Bandits Graph Bandits

Jun 12, 2026

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms

N

. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in

N

. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an

O(1/\sqrt{N})

optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.

Tianhao Wu, Matthew Zurek, Weina Wang +1

Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University

Multi-Armed Bandits Robust Markov Decision Processes Markov Decision Processes Reinforcement Learning Average-Reward RL Markov Models+2

Jun 10, 2026

Efficient Multinomial Logistic Bandit via Frequent Directions

This paper studies efficient online algorithms for multinomial logistic bandits (MLogB), where the feedback distribution over

K+1

outcomes follows a multinomial logistic model of

d

-dimensional action vectors. A representative UCB-type algorithm, OFUL-MLogB, achieves a regret bound of

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

, but still requires

\mathcal{O}(K^3d^3)

time and

\mathcal{O}(K^2d^2)

space per round due to parameter estimation and optimistic reward construction, which is prohibitive in high-dimensional settings. To address this limitation, we propose EOFD-MLogB, which integrates frequent directions matrix sketching into OFUL-MLogB. By maintaining a low-rank SVD sketch of the accumulated Hessian, constrained online Newton updates in parameter estimation and

Kd \times K

spectral-norm computations in the reward bonus are reduced to one-dimensional root-finding tasks and

K \times K

eigenvalue computations, respectively. This yields dominant per-round time complexity

\mathcal{O}(Kd(m+K)^2)

and space complexity

\mathcal{O}(Kd(m+K))

, where

m \ll d

is the sketch size. We further prove a regret bound of

\tilde{\mathcal{O}}(Δ_T(Kd\lnΔ_T+m)\sqrt{T})

, where the sketching error factor

Δ_T

is controlled by the

m

-truncated spectral tail of the Hessian. Thus, when the Hessian is approximately low-rank, the regret is close to that of OFUL-MLogB. Experiments validate the computational efficiency and competitive performance.

Linzhe He, Yu-Jie Zhang, Sifan Yang +1

State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · Paul G. Allen School of Computer Science & Engineering, University of Washington, USA

Multi-Armed Bandits Contextual Bandits UCB Algorithms

Jun 9, 2026

Annealed Entropic Allocation for Ranking and Selection

We propose annealed entropic allocation, an adaptive sampling policy based on an annealed, weighted soft-min formulation of static budget allocation. We replace the maximin large-deviation rate objective with a weighted log-sum-exp surrogate that blends challenger-specific pairwise scores through soft-min weights, avoiding hard switching when several challengers are nearly active. To capture tail behavior beyond the leading exponent, the surrogate incorporates saddlepoint prefactors from refined pairwise tail asymptotics. Because these corrections are subexponential, decreasing the annealing temperature with the budget preserves the same first-order target allocation. For the static problem, we prove uniform convergence to the hard minimum, concentration of soft-min weights on active challengers, and continuity of the induced target-allocation map under fixed weights. Experiments show that the proposed methods are consistently competitive: the no-saddlepoint ablation performs best in symmetric Gaussian and exponential slippage settings, while saddlepoint weighting can help in heterogeneous or asymmetric cases.

Xin Fei, Juergen Branke

Business School · The University of Edinburgh, Edinburgh, UK · Warwick Business School +1

Multi-Armed Bandits Adaptive Sampling

Jun 9, 2026

Bellman-sufficient Information Complexity

We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains enough of the history to close the controlled recursion, while an index

Y=χ(Ω)

specifies the decision-relevant information being charged. The upper bound is a log-penalized Bellman program; the lower bound is a Bellman--Fano comparison along an algorithm-dependent reference trajectory. If the two values match at a common localization scale and the stated admissibility, calibration, and growth conditions hold, they form an information-risk sandwich. UCB, E2D, and AMS/EBO control or relax the upper Bellman bracket in different ways. For the main application, we give a negative answer to a widely studied form of the GP--UCB minimax-optimality question. For every

0<α<1/4

, we construct one bounded continuous kernel whose minimax regret is

Θ(T^{1-α})

along an infinite sequence of horizons, while two globally calibrated GP--UCB rules incur linear regret under one fixed truth. An epochwise finite-marginal action-index AIR Bellman policy, implemented through robust AIR/AMS/EBO control, attains the minimax order. The construction separates realized information from the cost of uniform optimism: many low-value directions inflate the exploration multiplier and change the trajectory. Through the canonical RKHS feature map, it also yields a finite-horizon polynomial minimax separation for the specified maximal-information-calibrated LinUCB rule. A reproducible experiment illustrates the mechanism.

Yunbei Xu

National University of Singapore

Multi-Armed Bandits Minimax Regret Regret Minimization UCB Algorithms Information-Theoretic Lower Bounds

Jun 8, 2026

Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts

We consider a variant of the linear contextual stochastic multi-armed bandits, where the learner must provide recommendations to a group of users, each having its personalized preference vector, and in the presence of context distributions that are drifting over time. Under practitioner-friendly assumptions, we reduce this setting to linear bandit with stationary mean but heteroskedastic and non-stationary noise. We further study the case when the learner must ensure the mean reward of each decision must exceed that of a baseline strategy

\boldsymbolπ_0

at each decision step. We introduce Dri-MED, an algorithm inspired from the linear version of the MED strategy, and carefully adapted to handle the non-stationary heteroskedastic noise. We show that the instance-dependent regret scales as

\tilde{\mathcal O}\left(\fracκ{\tildeΔ}d^2(\log(T)\right)

, where

\tildeΔ

is the constraint-aware sub-optimality gap subject to policy

π_0

, with variance-aware multiplicative term

κ

that we carefully handle using heteroskedastic regression. We further show Dri-MED enjoys

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

expected constraint violations. Our numerical results suggest that Dri-MED significantly outperforms conservative baselines that ignores the drift and preference structure.

Udvas Das, Waris Radji, Debabrota Basu +1

Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL F-59000 Lille, France

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

Jun 8, 2026

Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

We prove that

ρ\text{-}\mathrm{NPTS}_{\mathrm{SG}}

, an anchor-free nonparametric Thompson Sampling algorithm for risk-averse bandits, achieves regret matching the instance-dependent lower bound to leading order in

\log n

, establishing it as asymptotically optimal for any continuous risk functional

ρ

(CVaR, mean-variance, Sharpe ratio, distortion risk measures, and more) on the class of distributions with bounded density and sub-Gaussian tails, including Gaussian arms. Both this result and its bounded-support counterpart require only continuity of

ρ

: strictly weaker than the dominance condition of prior parametric Thompson Sampling results, and strictly weaker than the Lipschitz condition of UCB-type algorithms, yielding the first instance-optimal guarantees for non-Lipschitz functionals such as the Sharpe ratio without parametric reward assumptions. The bounded-support case is developed first as a stepping stone sharing the same proof structure. The key technical contributions are a discretisation lemma (bounded support) and a truncated discretisation lemma (sub-Gaussian tails), each projecting the growing-alphabet Dirichlet posterior onto a fixed grid via the Dirichlet aggregation property, holding all polynomial prefactors at fixed degree independent of sample size and breaking the super-exponential barrier that blocked prior proofs.

Joel Q. L. Chang

Thompson Sampling Multi-Armed Bandits

Jun 8, 2026

Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees

We study a stochastic multi-armed bandit problem in which the set of available arms expands over time. This setting arises in sequential experimentation when new actions or treatments become available during an ongoing study, making regret against a single best arm in hindsight inappropriate. We instead evaluate performance relative to the best arm currently available, leading to a dynamic-regret criterion for arriving-arm environments. To address the resulting challenges of arrival information discrepancy (AID) and a drifting benchmark (DB), we propose UCB for Arriving Arms (UCB-AA), an elimination-based procedure with an aiding preliminary screening step for newly arrived arms before full competition with incumbent arms. We show that UCB-AA attains regret bounds that depend explicitly on the arrival process, achieves sublinear dynamic regret under regularity conditions on gap evolution, and admits an online extension for unknown horizons. Simulation results show that UCB-AA reduces wasted pulls and maintains a smaller active arm set while preserving competitive regret performance.

Deqi Zheng, Xiaoyang Xu, Yuhong Yang

Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University

Multi-Armed Bandits Dynamic Regret Minimization Sequential Decision Making UCB Algorithms

Jun 8, 2026

Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

Motivated by the recency effect in online learning, we study algorithms for single-pass sliding-window streaming multi-armed bandits (MABs) in this paper. In this setting, we are given

n

arms with unknown sub-Gaussian reward distributions and a parameter

W

. The arms arrive in a single-pass stream, and only the most recent

W

arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Vladimir Braverman, Chen Wang, Liudeng Wang +1

Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University

Multi-Armed Bandits Best-Arm Identification Streaming Algorithms