# Double Thompson Sampling in Finite stochastic Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 16 references that are in the map.
- First posted on arXiv 21 Feb 2022.

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Minimax Sample Complexity for Turn-based Stochastic Game](https://mlsanity.com/paper/2011.14267/) (2020)

## Abstract (arXiv)

We consider the trade-off problem between exploration and exploitation under finite discounted Markov Decision Process, where the state transition matrix of the underlying environment stays unknown. We propose a double Thompson sampling reinforcement learning algorithm(DTS) to solve this kind of problem. This algorithm achieves a total regret bound of tildeO(D√SAT)in time horizon T with S states, A actions and diameter D. DTS consists of two parts, the first part is the traditional part where we apply the posterior sampling method on transition matrix based on prior distribution. In the second part, we employ a count-based posterior update method to balance between the local optimal action and the long-term optimal action in order to find the global optimal game value. We established a regret bound of tildeO(√T/S2). Which is by far the best regret bound for finite discounted Markov Decision Process to our knowledge. Numerical results proves the efficiency and superiority of our approach.