# On First-Order Bounds, Variance and Gap-Dependent Bounds for Adversarial Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2019.

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

- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)

## Abstract (arXiv)

We make three contributions to the theory of k-armed adversarial bandits. First, we prove a first-order bound for a modified variant of the INF strategy by Audibert and Bubeck [2009], without sacrificing worst case optimality or modifying the loss estimators. Second, we provide a variance analysis for algorithms based on follow the regularised leader, showing that without adaptation the variance of the regret is typically Omega(n2) where n is the horizon. Finally, we study bounds that depend on the degree of separation of the arms, generalising the results by Cowan and Katehakis [2015] from the stochastic setting to the adversarial and improving the result of Seldin and Slivkins [2014] by a factor of log(n)/log(log(n)).