Thompson Sampling is Asymptotically Optimal in General Environments

By Jan Leike, Jan Leike, Tor Lattimore, Laurent Orseau, Marcus Hutter. 2016

40 citations recorded by the source corpus.

We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov, non-ergodic, and partially observable. We show that Thompson sampling learns the environment class in the sense that (1) asymptotically its value converges to the optimal value in mean and (2) given a recoverability assumption regret is sublinear.

Subfields: Artificial Intelligence, Management Science and Operations Research, Modeling and Simulation, Reinforcement Learning

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. Pieter Abbeel
3. Yoshua Bengio
4. Marc G. Bellemare
5. Chelsea Finn
6. Ruslan Salakhutdinov
7. Yuxi Li
8. R´emi Munos

In Management Science and Operations Research

1. Marc G. Bellemare
2. R´emi Munos
3. Ian Osband
4. Nando de Freitas
5. Sergey Levine
6. Georg Ostrovski
7. John Aslanides
8. Pieter Abbeel

In Reinforcement Learning

1. Sergey Levine
2. Pieter Abbeel
3. Marc G. Bellemare
4. R´emi Munos
5. Yuxi Li
6. Ian Osband
7. Shimon Whiteson
8. Chelsea Finn

Citations in the corpus

• Shaking the foundations: delusions in sequence models for interaction and control (2021, background): “In addition, the resulting policy is adaptive—essentially, it is Thompson sampling—and will converge to the expert’s policy under broad conditions [12, 14, 16].”
• Unifying Count-Based Exploration and Intrinsic Motivation (2016, background): “Mohamed and Rezende (2015) also considered a variational approach to the different problem of maximizing an agent’s ability to influence its environment.”
• Randomized Prior Functions for Deep Reinforcement Learning (2018, background): “1This heuristic is general in the sense that Thompson sampling can be theoretically justified in many of the domains where these other approaches fail [1, 48, 34, 58].”
• A Formal Solution to the Grain of Truth Problem (2016, background): “Together with Theorem 6 and the asymptotic optimality of the Thompson sampling policy [LLOH16, Thm. 4] that is reflective-oracle computable we get the following corollary.”
• Self-Modification of Policy and Utility Function in Rational Agents (2016, unknown): “A I] 1 0 M ay 2 01 6”