Titre :

Cheap Bandits

Auteur(s) :

Hanawal, Manjesh Kumar [Auteur]
Department of Electrical and Computer Engineering [Boston University] [ECE]
Saligrama, Venkatesh [Auteur]
Department of Electrical and Computer Engineering [Boston University] [ECE]
Valko, Michal [Auteur]
Sequential Learning [SEQUEL]
Munos, Rémi [Auteur]
Sequential Learning [SEQUEL]

Titre de la manifestation scientifique :

International Conference on Machine Learning

Ville :

Lille

Pays :

France

Date de début de la manifestation scientifique :

2015

Discipline(s) HAL :

Statistiques [stat]/Machine Learning [stat.ML]
Informatique [cs]/Recherche d'information [cs.IR]

Résumé en anglais : [en]

We consider stochastic sequential learning problems where the learner can observe the average reward of several actions. Such a setting is interesting in many applications involving monitoring and surveillance, where the ...
Lire la suite >We consider stochastic sequential learning problems where the learner can observe the average reward of several actions. Such a setting is interesting in many applications involving monitoring and surveillance, where the set of the actions to observe represent some (geographical) area. The importance of this setting is that in these applications , it is actually cheaper to observe average reward of a group of actions rather than the reward of a single action. We show that when the reward is smooth over a given graph representing the neighboring actions, we can maximize the cumulative reward of learning while minimizing the sensing cost. In this paper we propose CheapUCB, an algorithm that matches the regret guarantees of the known algorithms for this setting and at the same time guarantees a linear cost again over them. As a by-product of our analysis , we establish a ⌦(p dT) lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension d.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Extraction et transfert de connaissances dans l'apprentissage par renforcement

Collections :

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

Source :

Harvested from HAL