Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit - Archive ouverte HAL Access content directly
Reports (Technical Report) Year : 2012

Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit

(1) , (1)
1
Alexandra Carpentier
  • Function : Author
  • PersonId : 910455
Rémi Munos
  • Function : Author
  • PersonId : 836863

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})$.
Fichier principal
Vignette du fichier
SparseBanditsAISTATS.pdf (1.22 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00659731 , version 1 (13-01-2012)
hal-00659731 , version 2 (16-05-2012)

Identifiers

Cite

Alexandra Carpentier, Rémi Munos. Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit. [Technical Report] 2012. ⟨hal-00659731v2⟩
328 View
265 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More