Improved regret for zeroth-order adversarial bandit convex optimisation

Abstract

We prove that the information-theoretic upper bound on the minimax regret for zeroth-order adversarial bandit convex optimisation is at most $O(d^{2.5}\sqrt{n}\log (n))$, where $d$ is the dimension and $n$ is the number of interactions. This improves on the bound of $O(d^{9.5}\sqrt{n}\log (n{)}^{7.5})$ by Bubeck et al. (2017). The proof is based on identifying an improved exploratory distribution for convex functions.