Non-Asymptotic Analysis of a UCB-based Top Two Algorithm

Jourdan, Marc; Degenne, Rémy

Document type :

Pré-publication ou Document de travail

Title :

Non-Asymptotic Analysis of a UCB-based Top Two Algorithm

Author(s) :

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

HAL domain(s) :

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

English abstract : [en]

A Top Two sampling rule for bandit identification is a method which selects the next arm to sample from among two candidate arms, a leader and a challenger. Due to their simplicity and good empirical performance, they have ...
Show more >A Top Two sampling rule for bandit identification is a method which selects the next arm to sample from among two candidate arms, a leader and a challenger. Due to their simplicity and good empirical performance, they have received increased attention in recent years. For fixed-confidence best arm identification, theoretical guarantees for Top Two methods have only been obtained in the asymptotic regime, when the error level vanishes. We derive the first non-asymptotic upper bound on the expected sample complexity of a Top Two algorithm holding for any error level. Our analysis highlights sufficient properties for a regret minimization algorithm to be used as leader. They are satisfied by the UCB algorithm and our proposed UCB-based Top Two algorithm enjoys simultaneously non-asymptotic guarantees and competitive empirical performance.Show less >

Language :

Anglais

Comment :

32 pages, 5 figures, 3 tables

Collections :

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

Source :

Harvested from HAL

Files

http://arxiv.org/pdf/2210.05431
Open access
Access the document

Non-Asymptotic Analysis of a UCB-based Top ... BibTeX CSV Excel RIS

Files

Non-Asymptotic Analysis of a UCB-based Top ...

BibTeX

CSV

Excel

RIS