# Bandit Convex Optimisation Revisited: FTRL Achieves tildeO(t1/2) Regret

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 18 references that are in the map.
- First posted on arXiv 1 Feb 2023.

## Builds on (most cited first, 5 of 5)

- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothness](https://mlsanity.com/paper/2001.10818/) (2020)

## Abstract (arXiv)

We show that a kernel estimator using multiple function evaluations can be easily converted into a sampling-based bandit estimator with expectation equal to the original kernel estimate. Plugging such a bandit estimator into the standard FTRL algorithm yields a bandit convex optimisation algorithm that achieves tildeO(t1/2) regret against adversarial time-varying convex loss functions.