Bandits linéaires sur des ensembles uniformément convexes.

Résumé Les algorithmes de bandits linéaires produisent des limites de pseudo-retour de $\tilde{\mathcal{O}}(n\sqrt{T})$ sur des ensembles d'action convexes compacts $\mathcal{K}\subset\mathbb{R}^n$ et deux types d'hypothèses structurelles conduisent à de meilleures limites de pseudo-retour. Lorsque $\mathcal{K}$ est le simplexe ou une boule $\ell_p$ avec $p\in]1,2]$, il existe des algorithmes de bandits avec des limites de pseudo-retour de $\tilde{\mathcal{O}}(\sqrt{nT})$. Ici, nous dérivons des algorithmes de bandits pour certains ensembles fortement convexes au-delà de $\ell_p$ boules qui bénéficient de limites de pseudo-regret de $\tilde{\mathcal{O}}(\sqrt{nT})$, ce qui répond à une question ouverte de [BCB12, \S 5.5.]. Il est intéressant de noter que lorsque l'ensemble d'actions est uniformément convexe mais pas nécessairement fortement convexe, nous obtenons des bornes de pseudo-regret avec une dépendance de dimension plus petite que $\mathcal{O}(\sqrt{n})$. Cependant, cela se fait au détriment de taux asymptotiques en $T$ variant entre $\tilde{\mathcal{O}}(\sqrt{T})$ et $\tilde{\mathcal{O}}(T)$.