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, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
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})$.
Complete list of metadatas

https://hal.inria.fr/hal-00659731
Contributor : Alexandra Carpentier <>
Submitted on : Wednesday, May 16, 2012 - 5:01:28 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Friday, August 17, 2012 - 2:36:53 AM

Files

SparseBanditsAISTATS.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

700

Files downloads

279