# Thompson Sampling for Infinite-Horizon Discounted Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 41 references that are in the map.
- First posted on arXiv 14 May 2024.

## Builds on (most cited first, 14 of 14)

- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [Model-based Reinforcement Learning for Continuous Control with Posterior Sampling](https://mlsanity.com/paper/2012.09613/) (2020)
- [Regret Bounds for Discounted MDPs](https://mlsanity.com/paper/2002.05138/) (2020)
- [Thompson Sampling is Asymptotically Optimal in General Environments](https://mlsanity.com/paper/1602.07905/) (2016)
- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Asymptotic Convergence of Thompson Sampling](https://mlsanity.com/paper/2011.03917/) (2020)
- [Prior-dependent analysis of posterior sampling reinforcement learning with function approximation](https://mlsanity.com/paper/2403.11175/) (2024)
- [Thompson Sampling for Parameterized Markov Decision Processes with Uninformative Actions](https://mlsanity.com/paper/2305.07844/) (2023)

## Abstract (arXiv)

This paper develops a framework for learning in discounted infinite-horizon Markov decision processes (MDPs) with Borel state and action spaces, whose rewards and transitions depend on an unknown parameter.To analyze sampling-based adaptive learning algorithms in this setting, we introduce a canonical probability space that explicitly incorporates sampled parameters into the history of the process. As a performance criterion, we adopt the per-period suboptimality gap used in discounted-MDP regret analysis and specialize it to our parametrized Bayesian setting. Since this quantity captures the remaining loss in future performance from the current period onward, we refer to it as residual regret. We use the expected residual regret to connect discounted-MDP regret analysis with asymptotic discount optimality from adaptive control and the temporal-difference error perspective from reinforcement learning. We then focus on Thompson sampling (TS) in discounted infinite-horizon MDPs. Under assumptions that extend those used in prior work on finite state and action spaces to the Borel setting, we show that the expected residual regret for TS converges to zero exponentially fast. We further show that, under mild conditions ensuring the existence of the relevant limits, the ample-path residual regret converges to zero almost surely and TS achieves complete learning.