Skip to Main content Skip to Navigation
Conference papers

Minimal Exploration in Structured Stochastic Bandits

Abstract : This paper introduces and addresses a wide class of stochastic bandit problems where the function mapping the arm to the corresponding reward exhibits some known structural properties. Most existing structures (e.g. linear, Lipschitz, unimodal, combinatorial, dueling, . . . ) are covered by our framework. We derive an asymptotic instance-specific regret lower bound for these problems, and develop OSSB, an algorithm whose regret matches this fundamental limit. OSSB is not based on the classical principle of "optimism in the face of uncertainty" or on Thompson sampling, and rather aims at matching the minimal exploration rates of sub-optimal arms as characterized in the derivation of the regret lower bound. We illustrate the efficiency of OSSB using numerical experiments in the case of the linear bandit problem and show that OSSB outperforms existing algorithms, including Thompson sampling.
Document type :
Conference papers
Complete list of metadatas

Cited literature [36 references]  Display  Hide  Download

https://hal-centralesupelec.archives-ouvertes.fr/hal-02395029
Contributor : Delphine Le Piolet <>
Submitted on : Thursday, April 9, 2020 - 6:20:50 PM
Last modification on : Wednesday, October 14, 2020 - 3:57:02 AM

File

combes_minimal_exploration_nip...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02395029, version 1
  • ARXIV : 1711.00400

Citation

Richard Combes, Stefan Magureanu, Alexandre Proutiere. Minimal Exploration in Structured Stochastic Bandits. 31st Conference on Neural Information Processing Systems (NIPS), Dec 2017, Long Beach, CA, United States. ⟨hal-02395029⟩

Share

Metrics

Record views

45

Files downloads

11