# Thompson Sampling is Asymptotically Optimal in General Environments

arXiv: https://arxiv.org/abs/1602.07905 · HTML: https://mlsanity.com/paper/1602.07905/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2016.

## Built on by (most cited first, 8 of 8)

- [Shaking the foundations: delusions in sequence models for interaction and control](https://mlsanity.com/paper/2110.10819/) (2021)
- [On the Convergence of Bounded Agents](https://mlsanity.com/paper/2307.11044/) (2023)
- [Output-Weighted Sampling for Multi-Armed Bandits with Extreme Payoffs](https://mlsanity.com/paper/2102.10085/) (2021)
- [Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games](https://mlsanity.com/paper/2508.16245/) (2025)
- [A Model-Free Universal AI](https://mlsanity.com/paper/2602.23242/) (2026)
- [Cost Aware Asynchronous Multi-Agent Active Search](https://mlsanity.com/paper/2210.02259/) (2022)
- [Thompson Sampling for Infinite-Horizon Discounted Decision Processes](https://mlsanity.com/paper/2405.08253/) (2024)
- [Partition Tree Weighting for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2502.19325/) (2025)

## Abstract (arXiv)

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.