• English
    • français
  • Aide
  •  | 
  • Contact
  •  | 
  • À Propos
  •  | 
  • Ouvrir une session
  • Portail HAL
  •  | 
  • Pages Pro Chercheurs
  • EN
  •  / 
  • FR
Voir le document 
  •   Accueil de LillOA
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • Voir le document
  •   Accueil de LillOA
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • Voir le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Boundary Crossing for General Exponential Families
  • BibTeX
  • CSV
  • Excel
  • RIS

Type de document :
Communication dans un congrès avec actes
Titre :
Boundary Crossing for General Exponential Families
Auteur(s) :
Maillard, Odalric-Ambrym [Auteur] refId
Sequential Learning [SEQUEL]
Titre de la manifestation scientifique :
Algorithmic Learning Theory
Ville :
Kyoto
Pays :
Japon
Date de début de la manifestation scientifique :
2017-10
Titre de l’ouvrage :
Journal of Machine Learning Research
Titre de la revue :
Proceedings of Algorithmic Learning Theory
Date de publication :
2017
Mot(s)-clé(s) en anglais :
Exponential Families
Bregman Concentration
Multi-armed Bandits
Optimality
Discipline(s) HAL :
Statistiques [stat]/Machine Learning [stat.ML]
Mathématiques [math]/Statistiques [math.ST]
Résumé en anglais : [en]
We consider parametric exponential families of dimension K on the real line. We study a variant of boundary crossing probabilities coming from the multi-armed bandit literature, in the case when the real-valued distributions ...
Lire la suite >
We consider parametric exponential families of dimension K on the real line. We study a variant of boundary crossing probabilities coming from the multi-armed bandit literature, in the case when the real-valued distributions form an exponential family of dimension K. Formally, our result is a concentration inequality that bounds the probability that B ψ (θ n , θ) f (t/n)/n, where θ is the parameter of an unknown target distribution, θ n is the empirical parameter estimate built from n observations, ψ is the log-partition function of the exponential family and B ψ is the corresponding Bregman divergence. From the perspective of stochastic multi-armed bandits, we pay special attention to the case when the boundary function f is logarithmic, as it enables to analyze the regret of the state-of-the-art KL-ucb and KL-ucb+ strategies, whose analysis was left open in such generality. Indeed, previous results only hold for the case when K = 1, while we provide results for arbitrary finite dimension K, thus considerably extending the existing results. Perhaps surprisingly, we highlight that the proof techniques to achieve these strong results already existed three decades ago in the work of T.L. Lai, and were apparently forgotten in the bandit community. We provide a modern rewriting of these beautiful techniques that we believe are useful beyond the application to stochastic multi-armed bandits.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Projet ANR :
BANDITS MANCHOTS POUR SIGNAUX NON-STATIONNAIRES ET STRUCTURES
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Fichiers
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-01615427/document
  • Accès libre
  • Accéder au document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-01615427/document
  • Accès libre
  • Accéder au document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-01615427/document
  • Accès libre
  • Accéder au document
Thumbnail
  • document
  • Accès libre
  • Accéder au document
Thumbnail
  • 15.pdf
  • Accès libre
  • Accéder au document
Université de Lille

Mentions légales
Université de Lille © 2017