Thompson Sampling is Asymptotically Optimal in General Environments
  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.
