Double Thompson Sampling in Finite stochastic Games
This work addresses a fundamental challenge in reinforcement learning for decision-making under uncertainty, representing an incremental improvement with a new regret bound.
The authors tackled the exploration-exploitation trade-off in finite discounted Markov Decision Processes with unknown transition matrices by proposing a Double Thompson Sampling (DTS) reinforcement learning algorithm, achieving a total regret bound of $ ilde{\mathcal{O}}(D\sqrt{SAT})$ and proving it to be the best known bound for this problem.
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 $\tilde{\mathcal{O}}(D\sqrt{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 $\tilde{\mathcal{O}}(\sqrt{T}/S^{2})$. 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.