Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis

By Emilie Kaufmann, N. Korda, R´emi Munos. 2012

619 citations recorded by the source corpus.

The question of the optimality of Thompson Sampling for solving the stochastic multi-armed bandit problem had been open since 1933. In this paper we answer it positively for the case of Bernoulli rewards by providing the first finite-time analysis that matches the asymptotic rate given in the Lai and Robbins lower bound for the cumulative regret. The proof is accompanied by a numerical comparison with other optimal policies, experiments that have been lacking in the literature until now for the Bernoulli case.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research, Reinforcement Learning, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Sergey Levine
  2. Yoshua Bengio
  3. Pieter Abbeel
  4. Ruslan Salakhutdinov
  5. Chelsea Finn
  6. Quoc V. Le
  7. Mohit Bansal
  8. Jianfeng Gao

In Electrical and Electronic Engineering

  1. R´emi Munos
  2. Navin Goyal
  3. Shipra Agrawal
  4. Tor Lattimore
  5. Shimon Whiteson
  6. Csaba Szepesvari
  7. Benjamin Van Roy
  8. Elias Bareinboim

In Management Science and Operations Research

  1. R´emi Munos
  2. Ian Osband
  3. Csaba Szepesvari
  4. Tor Lattimore
  5. Benjamin Van Roy
  6. Daniel Russo
  7. Brendan O'Donoghue
  8. Nando de Freitas

In Reinforcement Learning

  1. Sergey Levine
  2. Pieter Abbeel
  3. R´emi Munos
  4. Shimon Whiteson
  5. Ian Osband
  6. Yuxi Li
  7. Chelsea Finn
  8. Brendan O'Donoghue

In Game & Decision Theory

  1. R´emi Munos
  2. Tor Lattimore
  3. Csaba Szepesvari
  4. Nando de Freitas
  5. Aurélien Garivier
  6. Daniel Russo
  7. Matthew D. Hoffman
  8. Gilles Stoltz

Citations in the corpus