On Thompson Sampling and Asymptotic Optimality

Jan Leike, Tor Lattimore, Laurent Orseau, Marcus Hutter

Abstract

We discuss some recent results on Thompson sampling for nonparametric reinforcement learning in countable classes of general stochastic environments. These environments can be non-Markovian, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that (1) asymptotically its value converges in mean to the optimal value and (2) given a recoverability assumption regret is sublinear. We conclude with a discussion about optimality in reinforcement learning.
BibTeX
@inproceedings{leike2017thompson,
  author = {Jan Leike and Tor Lattimore and Laurent Orseau and Marcus Hutter},
  title = {{On Thompson Sampling and Asymptotic Optimality}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/688},
}

Loading related content...

Figure