Titre :

Covariance-adapting algorithm for semi-bandits with application to sparse outcomes

Auteur(s) :

Perrault, Pierre [Auteur]
Scool [Scool]
Sequential Learning [SEQUEL]
Ecole Normale Supérieure Paris-Saclay [ENS Paris Saclay]
Perchet, Vianney [Auteur]
Ecole Nationale de la Statistique et de l'Analyse Economique [ENSAE]
Valko, Michal [Auteur]
DeepMind [Paris]

Titre de la manifestation scientifique :

Conference on Learning Theory

Ville :

Graz

Pays :

Autriche

Date de début de la manifestation scientifique :

2020

Date de publication :

2020

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

combinatorial stochastic semi-bandits
covariance
confidence ellipsoid
sparsity

Discipline(s) HAL :

Mathématiques [math]
Mathématiques [math]/Statistiques [math.ST]
Informatique [cs]
Informatique [cs]/Apprentissage [cs.LG]

Résumé en anglais : [en]

We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits). Typical distributions considered depend ...
Lire la suite >We investigate stochastic combinatorial semi-bandits, where the entire joint distribution of outcomes impacts the complexity of the problem instance (unlike in the standard bandits). Typical distributions considered depend on specific parameter values, whose prior knowledge is required in theory but quite difficult to estimate in practice; an example is the commonly assumed sub-Gaussian family. We alleviate this issue by instead considering a new general family of sub-exponential distributions, which contains bounded and Gaussian ones. We prove a new lower bound on the regret on this family, that is parameterized by the unknown covariance matrix, a tighter quantity than the sub-Gaussian matrix. We then construct an algorithm that uses covariance estimates, and provide a tight asymptotic analysis of the regret. Finally, we apply and extend our results to the family of sparse outcomes, which has applications in many recommender systems.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Au delà de l'apprentissage séquentiel pour de meilleures prises de décisions

Collections :

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

Source :

Harvested from HAL