Thompson sampling is asymptotically optimal in general environments. (Leike, J., Lattimore, T., Orseau, L. & Hutter, M. (2016). Proceedings of the Thirty-Second Uncertainty in Artificial Intelligence Conference)
We discuss a variant of Thompson sampling for nonparametric reinforcement learning in countable classes of general stochastic environments. These environments can be non-Markov, nonergodic, 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.
