First-order regret bounds for combinatorial semi-bandits - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

First-order regret bounds for combinatorial semi-bandits

Gergely Neu
  • Fonction : Auteur
  • PersonId : 961179

Résumé

We consider the problem of online combinatorial optimization under semi-bandit feedback, where a learner has to repeatedly pick actions from a combinatorial decision set in order to minimize the total losses associated with its decisions. After making each decision, the learner observes the losses associated with its action, but not other losses. For this problem, there are several learning algorithms that guarantee that the learner's expected regret grows as O(√ T) with the number of rounds T. In this paper, we propose an algorithm that improves this scaling to O(√ L * T), where L * T is the total loss of the best action. Our algorithm is among the first to achieve such guarantees in a partial-feedback scheme, and the first one to do so in a combinatorial setting.
Fichier principal
Vignette du fichier
firstorder_colt.pdf (275.11 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01215001 , version 1 (13-10-2015)

Identifiants

  • HAL Id : hal-01215001 , version 1

Citer

Gergely Neu. First-order regret bounds for combinatorial semi-bandits. Proceedings of the 28th Annual Conference on Learning Theory (COLT), Jul 2015, Paris, France. pp.1360-1375. ⟨hal-01215001⟩
113 Consultations
71 Téléchargements

Partager

Gmail Facebook X LinkedIn More