Efficient learning by implicit exploration in bandit problems with side observations

Tomáš Kocák 1 Gergely Neu 1 Michal Valko 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : We consider online learning problems under a a partial observability model capturing situations where the information conveyed to the learner is between full information and bandit feedback. In the simplest variant, we assume that in addition to its own loss, the learner also gets to observe losses of some other actions. The revealed losses depend on the learner's action and a directed observation system chosen by the environment. For this setting, we propose the first algorithm that enjoys near-optimal regret guarantees without having to know the observation system before selecting its actions. Along similar lines, we also define a new partial information setting that models online combinatorial optimization problems where the feedback received by the learner is between semi-bandit and full feedback. As the predictions of our first algorithm cannot be always computed efficiently in this setting, we propose another algorithm with similar properties and with the benefit of always being computationally efficient, at the price of a slightly more complicated tuning mechanism. Both algorithms rely on a novel exploration strategy called implicit exploration, which is shown to be more efficient both computationally and information-theoretically than previously studied exploration strategies for the problem.
Type de document :
Communication dans un congrès
Neural Information Processing Systems, Dec 2014, Montréal, Canada
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01079351
Contributeur : Michal Valko <>
Soumis le : lundi 3 novembre 2014 - 13:30:10
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Fichier

kocak2014efficient.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01079351, version 2

Citation

Tomáš Kocák, Gergely Neu, Michal Valko, Rémi Munos. Efficient learning by implicit exploration in bandit problems with side observations. Neural Information Processing Systems, Dec 2014, Montréal, Canada. 〈hal-01079351v2〉

Partager

Métriques

Consultations de la notice

415

Téléchargements de fichiers

158