# Bandit Convex Optimization: sqrt{T} Regret in One Dimension

arXiv: https://arxiv.org/abs/1502.06398 · HTML: https://mlsanity.com/paper/1502.06398/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2015.

## Built on by (most cited first, 10 of 10)

- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Think Smarter not Harder: Adaptive Reasoning with Inference Aware Optimization](https://mlsanity.com/paper/2501.17974/) (2025)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifolds](https://mlsanity.com/paper/2108.07406/) (2021)
- [A Bit Better? Quantifying Information for Bandit Learning](https://mlsanity.com/paper/2102.09488/) (2021)
- [Minimax Regret for Bandit Convex Optimisation of Ridge Functions](https://mlsanity.com/paper/2106.00444/) (2021)
- [Adaptive Bandit Convex Optimization with Heterogeneous Curvature](https://mlsanity.com/paper/2202.06150/) (2022)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)
- [Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses](https://mlsanity.com/paper/2606.19891/) (2026)

## Abstract (arXiv)

We analyze the minimax regret of the adversarial bandit convex optimization problem. Focusing on the one-dimensional case, we prove that the minimax regret is widetildeTheta(√T) and partially resolve a decade-old open problem. Our analysis is non-constructive, as we do not present a concrete algorithm that attains this regret rate. Instead, we use minimax duality to reduce the problem to a Bayesian setting, where the convex loss functions are drawn from a worst-case distribution, and then we solve the Bayesian version of the problem with a variant of Thompson Sampling. Our analysis features a novel use of convexity, formalized as a "local-to-global" property of convex functions, that may be of independent interest.