Refined lower bounds for adversarial bandits

Carte non disponible

Date/heure
Date(s) - 14/11/2016
14 h 30 min - 15 h 30 min

Catégories Pas de Catégories


We provide new lower bounds on the regret that must be suffered by adversarial bandit algorithms. The new results show that recent upper bounds that either (a) hold with high-probability or (b) depend on the total lossof the best arm or (c) depend on the quadratic variation of the losses, are close to tight. Besides this we prove two impossibility results. First, the existence of a single arm that is optimal in every round cannot improve the regret in the worst case. Second, the regret cannot scale with the effective range of the losses. In contrast, both results are possible in the full-information setting.

Sébastien Gerchinovitz | preprint“> Page de Sébastien Gerchinovitz | preprint

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange