Linear Bandits on Uniformly Convex Sets

By Thomas Kerdreux, Christophe Roux, Alexandre d'Aspremont, Sebastian Pokutta. 2021

10 citations recorded by the source corpus.

Linear bandit algorithms yield $\tilde{\mathcal{O}}(n\sqrt{T})$ pseudo-regret bounds on compact convex action sets $\mathcal{K}\subset\mathbb{R}^n$ and two types of structural assumptions lead to better pseudo-regret bounds. When $\mathcal{K}$ is the simplex or an $\ell_p$ ball with $p\in]1,2]$, there exist bandits algorithms with $\tilde{\mathcal{O}}(\sqrt{nT})$ pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond $\ell_p$ balls that enjoy pseudo-regret bounds of $\tilde{\mathcal{O}}(\sqrt{nT})$, which answers an open question from [BCB12, \S 5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than $\mathcal{O}(\sqrt{n})$. However, this comes at the expense of asymptotic rates in $T$ varying between $\tilde{\mathcal{O}}(\sqrt{T})$ and $\tilde{\mathcal{O}}(T)$.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

Citations in the corpus

• The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “…al. [45], Mokhtari et al. [61], Anari et al. [1], Anari et al. [2], Mokhtari et al. [62], Bach [4]), online learning (see, e.g., Hazan and Kale [46], Zhang et al. [86], Chen et al. [20], Garber and Kretzu [39], Kerdreux et al. [51], Zhang et al. [87]) and many more (see, e.g., Bolte et al. [6],…”