UCB Algorithms

UCB: Upper Confidence Bound

UCB algorithms choose actions by combining estimated rewards with confidence bonuses, balancing exploration of uncertain options against exploiting promising ones. The approach spans multi-armed and linear or contextual bandits, as well as Gaussian-process optimization, with variants for nonstationary rewards, constraints, delayed feedback, and multiple objectives. Analyses typically establish regret guarantees, while benchmarks test performance in settings such as pricing, ranking, resource allocation, and adaptive model selection. A central challenge is adapting confidence bounds to realistic noise and structure without making decisions too costly or compromising safety, fairness, or valid statistical inference.

Latest papers

57 papers9 papers in the last four weeks, up 200% on the four weeks before. 0.1% of all new papers.

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds
Oct 21, 2026Yashaswini Kaluguri, Nikhil KaramchandaniMulti-Armed Bandits Bandit Learning
Department of Electrical Engineering, Indian Institute of Technology Bombay, Mumbai, India
Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
Oct 20, 2026Shion Takeno, Shogo Iwazaki, Ichiro TakeuchiGaussian Process Bandits Regret Minimization
Nagoya University · MI-6 Ltd. · RIKEN AIP
The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret
Oct 15, 2026Mohammad Pedramfar, Siamak RavanbakhshPosterior Sampling Thompson Sampling
Mila – Québec AI Institute, McGill University
Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds
Oct 15, 2026Adrien Prevost, Timothee Mathieu, Waris Radji +1Multi-Armed Bandits Transfer Learning
Equipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France
Accelerating Linear Bandits with Persistent Candidate Sets
Oct 9, 2026Bingkui Tong, Daria Korovaitceva, Marina Sheshukova +2Multi-Armed Bandits Linear Contextual Bandits
Mohamed bin Zayed University of Artificial Intelligence · HSE University · RIKEN AIP
Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime
Oct 5, 2026Yujie Liu, Vincent Y. F. Tan, Yunbei XuAdaptive Inference Contextual Bandits
National University of Singapore
Pay to Learn, Share to Earn: Incentivized Federated Multi-Player Bandits
Oct 5, 2026Pavamana K J, Chandramani SinghMulti-Armed Bandits Incentive Mechanisms for Federated Learning
Indian Institute of Science, Bengaluru, India
Ranking Bandits for Carousel Interfaces with Observable Browsing Depth
Oct 4, 2026Takuma Yasuda, Atsuyoshi Nakamura, Dai Hai NguyenThompson Sampling Multi-Armed Bandits
Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan
Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
Oct 1, 2026Taehyun Hwang, Hyunjun Choi, Heesang Ann +1Multi-Armed Bandits Stochastic Linear Dynamical Systems
Seoul National University Soeul, South Korea
Optimal Nonparametric Dynamic Pricing with Censored Demand and Adversarial Inventory
Sep 26, 2026Mengxiao Zhang, Yingfei Wang, Haipeng LuoDynamic Pricing Minimax Regret
University of Iowa · University of Washington · University of Southern California
Robust Bayesian Optimization with Q-Exponential Surrogates
Sep 26, 2026Richard Cornelius Suwandi, Zhidi Lin, Feng Yin +1Bayesian Optimization UCB Algorithms
School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen, China · School of Computing and Data Science, The University of Hong Kong, Hong Kong SAR, China · Signal Processing Group, Technische Universität Darmstadt, Germany
A Unified Optimism-Agnostic Framework for Linear Bandits over Spherical Action Sets
Sep 26, 2026Arda Güçlü, Subhonmesh Bose, John R. BirgeMulti-Armed Bandits UCB Algorithms
University of Chicago Booth School of Business, Chicago, IL 60637
Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions
Aug 27, 2026Spyros Dragazis, Aldo PacchianoContextual Bandits Multi-Armed Bandits
Boston University · Broad Institute of MIT and Harvard
Risk-Sensitive Reinforcement Learning with Smoothed Quantile Objectives
Aug 23, 2026Mohammad Alipour-Vaezi, Huaiyang Zhong, Sajad KhodadadianRisk-Sensitive RL Regret Minimization in RL
Grado Department of Industrial & Systems Engineering, Virginia Tech, Blacksburg, VA 24061, USA
Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
Aug 19, 2026Matthias Mandl, Hanne KekkonenGaussian Process Bandits Bayesian Optimization
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits
Aug 18, 2026Kaifei Wang, Yinyu Ye, Han ZhongMulti-Armed Bandits UCB Algorithms
Peking University · Stanford University · Shanghai Jiao Tong University
Reoptimization Algorithms for Contextual Bandits with Knapsack Constraints
Aug 11, 2026Zhen XuContextual Bandits UCB Algorithms
Management School, University of Liverpool, Liverpool, United Kingdom
Sharp Characterization of Bias in Post-Bandit Inference
Aug 2, 2026Lisu Wang, Yilun Chen, Jiaqi LuMulti-Armed Bandits Algorithmic Bias
School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen
Price of Fairness in Bandits: A Tight Minimax Characterization
Jul 15, 2026Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray ChowdhuryMulti-Armed Bandits Minimax Regret
1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur
Randomized Exploration for Linear Bandits via Absolute Perturbations
Jun 26, 2026Toshinori Kitamura, Shuai Liu, Csaba SzepesváriThompson Sampling Multi-Armed Bandits
Department of Computing Science, University of Alberta, Canada
Learning in Markovian bandits with non-observable states and constrained decision epochs
Jun 25, 2026Thomas Hira, Victor Boone, Urtzi Ayesta +1Multi-Armed Bandits Markov Models
IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · Ikerbasque-UPV/EHU, University of the Basque Country, Bilbao, Spain
Selective Ensemble Based on Preference-Directed Multi-Objective Bandits
Jun 20, 2026Lanjihong Ma, Zhen-Yu Zhang, Masashi Sugiyama +1Multi-Armed Bandits Ensemble Learning
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
Set Membership Estimation for Stochastic Linear Contextual Bandits
Jun 18, 2026Haonan Xu, Yingying LiMulti-Armed Bandits Contextual Bandits
The Grainger College of Engineering University of Illinois Urbana-Champaign Champaign, IL, 61801
Efficient Multinomial Logistic Bandit via Frequent Directions
Jun 10, 2026Linzhe He, Yu-Jie Zhang, Sifan Yang +1Multi-Armed Bandits Contextual Bandits
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
Bellman-sufficient Information Complexity
Jun 9, 2026Yunbei XuMulti-Armed Bandits Minimax Regret
National University of Singapore
Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
Jun 8, 2026Seoungbin Bae, Dabeen LeeExploration-Exploitation Tradeoff Regret Minimization
Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees
Jun 8, 2026Deqi Zheng, Xiaoyang Xu, Yuhong YangMulti-Armed Bandits Dynamic Regret Minimization
Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University
Regret-Based $(ε,δ)$ -optimal Stopping Criteria for Bayesian Optimization
May 21, 2026Haowei Wang, Jingyi Wang, Qiyu WeiBayesian Optimization Optimal Stopping
The University of Manchester, UK
Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewards
May 11, 2026Xin Guo, Grace He, Xinyu LiContextual Bandits UCB Algorithms
University of California, Berkeley, Berkeley, CA · University of Oxford, Oxford, UK
Beyond Static Bias: Adaptive Multi-Fidelity Bandits with Improving Proxies
May 8, 2026Muyun Lu, Haoyang Hong, Huazheng Wang +1Multi-Fidelity Optimization Multi-Armed Bandits
Department of Industrial and Systems Engineering, University of Houston · School of Electrical Engineering and Computer Science, Oregon State University

Oct 21, 2026J/K move · Enter open · S save

Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

Yashaswini Kaluguri, Nikhil Karamchandani

Department of Electrical Engineering, Indian Institute of Technology Bombay, Mumbai, India

Multi-Armed Bandits Bandit Learning Combinatorial Multi-Armed Bandits UCB Algorithms

Open paper AskPDF arXiv

We propose a novel stochastic cascading bandit setup where probing an ordered shortlist of

K

out of

L

arms incurs position-dependent costs, and the learner observes only noisy feedback regarding each arm's true output. We identify a sub-class of noise models for which the optimal shortlist can be found by sorting arms according to a per-arm score: such a score exists for both selection and ordering when the channel has no false positives, and for ordering alone (but not selection) when measurements are costless; however in general neither selection nor ordering is separable once noise and cost are both present. For the case where both selection and ordering scores exist, we provide a UCB-based algorithm with

O((L-K)\log T)

instance-dependent regret over a time horizon

T

, which matches an algorithm-agnostic lower bound (up to constant factors). For the more challenging scenario where scores don't exist, we develop a new algorithmic template, DP-UCB, that embeds optimism directly inside an exact dynamic program, yielding

O\big(LK\log T\big)

regret. Finally, we validate our theoretical results through extensive numerical evaluations and simulations over both synthetic and real-world datasets.