• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

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

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
Thumbnail
  • http://arxiv.org/pdf/2210.05431
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017