Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit

Alexandra Carpentier 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : We consider a linear stochastic bandit problem where the dimension $K$ of the unknown parameter $\theta$ is larger than the sampling budget $n$. In such cases, it is in general impossible to derive sub-linear regret bounds since usual linear bandit algorithms have a regret in $O(K\sqrt{n})$. In this paper we assume that $\theta$ is $S-$sparse, i.e.~has at most $S-$non-zero components, and that the space of arms is the unit ball for the $||.||_2$ norm. We combine ideas from Compressed Sensing and Bandit Theory and derive algorithms with regret bounds in $O(S\sqrt{n})$.
Liste complète des métadonnées

https://hal.inria.fr/hal-00659731
Contributeur : Alexandra Carpentier <>
Soumis le : mercredi 16 mai 2012 - 17:01:28
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 17 août 2012 - 02:36:53

Fichiers

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

Identifiants

  • HAL Id : hal-00659731, version 2
  • ARXIV : 1205.4094

Collections

Citation

Alexandra Carpentier, Rémi Munos. Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit. [Technical Report] 2012. 〈hal-00659731v2〉

Partager

Métriques

Consultations de la notice

658

Téléchargements de fichiers

227