Online combinatorial optimization with stochastic decision sets and adversarial losses

Gergely Neu 1 Michal Valko 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 : Most work on sequential learning assumes a fixed set of actions that are available all the time. However, in practice, actions can consist of picking subsets of readings from sensors that may break from time to time, road segments that can be blocked or goods that are out of stock. In this paper we study learning algorithms that are able to deal with stochastic availability of such unreliable composite actions. We propose and analyze algorithms based on the Follow-The-Perturbed-Leader prediction method for several learning settings differing in the feedback provided to the learner. Our algorithms rely on a novel loss estimation technique that we call Counting Asleep Times. We deliver regret bounds for our algorithms for the previously studied full information and (semi-)bandit settings, as well as a natural middle point between the two that we call the restricted information setting. A special consequence of our results is a significant improvement of the best known performance guarantees achieved by an efficient algorithm for the sleeping bandit problem with stochastic availability. Finally, we evaluate our algorithms empirically and show their improvement over the known approaches.
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 [17 références]  Voir  Masquer  Télécharger

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

Fichier

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

Identifiants

  • HAL Id : hal-01079355, version 2

Citation

Gergely Neu, Michal Valko. Online combinatorial optimization with stochastic decision sets and adversarial losses. Neural Information Processing Systems, Dec 2014, Montréal, Canada. 〈hal-01079355v2〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

91