Bandit Convex Optimization

Follow this topic Ask about this topic

Bandit convex optimization asks how to choose actions over time to minimize convex losses when each action reveals only its loss or a few loss evaluations, rather than the full gradient. Common approaches use randomized smoothing and one- or two-point gradient estimators with projected or mirror-descent methods; predictions and variance reduction can further improve regret when feedback is informative. The framework also covers stochastic and adversarial losses, delayed or constrained feedback, and settings with curvature or other structural assumptions. A central tension is how feedback limits and dimension affect regret: two-point feedback can enable sharper guarantees, while lower bounds show that hidden structure and high confidence can make learning substantially harder.

Latest papers

13 papers1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets
Oct 13, 2026Chen-Yu WeiFollow-the-Perturbed-Leader Adversarial Bandits
University of Virginia
Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
Sep 10, 2026Xuan LiThompson Sampling Bandit Convex Optimization
University of New South Wales, Sydney, Australia
Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
Aug 17, 2026Anling Xiang, Yuwen Yang, Yang ShenBandits with Delayed Feedback Bandit Convex Optimization
Department of Intelligent Communication, School of Journalism and Communication, Minzu University of China, Beijing, China · ZeeLin (Beijing) Technology Co., Ltd., Beijing, China · School of Journalism and Communication, Tsinghua University, Beijing, China +1
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
Jul 22, 2026Zhanyuan Cai, Emre Sahinoglu, Shahin ShahrampourOnline Convex Optimization Riemannian Optimization
Department of Mechanical & Industrial Engineering at Northeastern University, Boston, MA 02115, USA
The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization
Jul 21, 2026Nived RajaramanOnline Convex Optimization Minimax Regret
Microsoft Research
Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoOnline Convex Optimization Bandit Convex Optimization
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan
Capacity-Constrained Online Convex Optimization with Delayed Feedback
Jun 10, 2026Alexander Ryabchenko, Idan Attias, Daniel M. RoyOnline Convex Optimization Bandit Convex Optimization
Department of Statistical Sciences, University of Toronto; Vector Institute. · Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), hosted by UIC and TTIC.
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
Jun 6, 2026Wentao Zhang, Yutong Zhang, Wentao MoOnline Convex Optimization Bandit Convex Optimization
Tsinghua Shenzhen International Graduate School, Tsinghua University, China · College of Mathematics, Sichuan University, China
Bandit Convex Optimization with Gradient Prediction Adaptivity
May 21, 2026Shuche Wang, Adarsh Barik, Vincent Y. F. TanOnline Convex Optimization Dynamic Regret Minimization
Department of Mathematics, National University of Singapore, Singapore · Department of Computer Science and Engineering, Indian Institute of Technology Delhi, India · Department of Electrical and Computer Engineering, National University of Singapore, Singapore
Harnessing Unimodality in Semiparametric Contextual Pricing via Oracle Price Map Learning
May 14, 2026Yingying Fan, Yuxuan Han, Jinchi Lv +2Bandit Convex Optimization Dynamic Pricing
Data Sciences and Operations Department, University of Southern California, Los Angeles, California 90089, USA · Stern School of Business, New York University, New York, NY 10003, USA
In-Context Learning for Data-Driven Censored Inventory Control
May 14, 2026Sohom Mukherjee, Anh-Duy Pham, Richard Pibernik +1Inventory Control Bandit Convex Optimization
Julius-Maximilians-Universität Würzburg · National University of Singapore Zaragoza Logistics Center
Logarithmic High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback
Mar 26, 2026Haishan YeOnline Convex Optimization Bandit Convex Optimization
School of Management, Xi’an Jiaotong University
Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
Feb 4, 2026Hang Yu, Yu-Hu Yan, Peng ZhaoOnline Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

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

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets

Chen-Yu Wei

University of Virginia

Follow-the-Perturbed-Leader Adversarial Bandits Bandit Convex Optimization Exploration-Exploitation Tradeoff

Open paper AskPDF arXiv

We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves

\sqrt{T}

regret over general action sets. Our algorithm attains

\widetilde{\mathcal{O}}(d^{5/4}\sqrt{T})

regret using only linear optimization oracles, and the near-optimal

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

regret when an optimal-design exploration distribution is further available. This improves on the

T^{2/3}

regret of the FTPL algorithm of Dani and Hayes (2006) for general action sets, and generalizes the

\sqrt{T}

regret of Lévy et al. (2026) over two special action sets (hypercube and Euclidean ball). Compared to previous oracle-efficient linear bandit algorithms based on continuous exponential weights, the FTPL approach generally has better computational efficiency, and is much simpler to implement. The key algorithmic element is a perturbation distribution that adapts to the past reward estimators. Its simplest form, an adaptive Gaussian perturbation, is straightforward to implement and already attains the regret bound above. We further extend it to two general constructions, random-weighting and elliptical perturbations, each covering distributions from light tails (Gaussian) to heavy tails (Student-

t_2

). On the technical side, we develop a systematic way to analyze the stability term in the FTPL regret through the Fisher information of the perturbation distribution. This builds a general framework for FTPL beyond existing ones such as the hazard rate and the FTRL-FTPL duality.