Titre :

On the Existence of a Complexity in Fixed Budget Bandit Identification

Auteur(s) :

Degenne, Rémy [Auteur]
Scool [Scool]

Titre de la manifestation scientifique :

Thirty Sixth Conference on Learning Theory

Ville :

Bengaluru (Bangalore)

Pays :

Inde

Date de début de la manifestation scientifique :

2023-07-12

Titre de l’ouvrage :

Proceedings of Machine Learning Research

Date de publication :

2023-06-30

Mot(s)-clé(s) en anglais :

Multi-armed bandits
fixed budget
best arm identification

Discipline(s) HAL :

Statistiques [stat]/Machine Learning [stat.ML]

Résumé en anglais : [en]

In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. It then answers a query about the set of distributions. A good algorithm will have a ...
Lire la suite >In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. It then answers a query about the set of distributions. A good algorithm will have a small probability of error. While that probability decreases exponentially with the final time, the best attainable rate is not known precisely for most identification tasks. We show that if a fixed budget task admits a complexity, defined as a lower bound on the probability of error which is attained by the same algorithm on all bandit problems, then that complexity is determined by the best non-adaptive sampling procedure for that problem. We show that there is no such complexity for several fixed budget identification tasks including Bernoulli best arm identification with two arms: there is no single algorithm that attains everywhere the best possible rate.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Tests Adaptatifs et Frugaux

Commentaire :

24 pages, 36th Annual Conference on Learning Theory, Proceedings of Machine Learning Research vol 195

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL