Boundary Crossing for General Exponential Families

Maillard, Odalric Ambrym

Type de document :

Communication dans un congrès avec actes

Titre :

Boundary Crossing for General Exponential Families

Auteur(s) :

Maillard, Odalric Ambrym [Auteur]

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 :