We consider the problem of learning an unknown Markov Decision Process (MDP)
that is weakly communicating in the infinite horizon setting. We propose a
Thompson Sampling-based reinforcement learning algorithm with dynamic episodes
(TSDE). At the beginning of each episode, the algorithm generates a sample from
the posterior distribution over the unknown model parameters. It then follows
the optimal stationary policy for the sampled model for the rest of the
episode. The duration of each episode is dynamically determined by two stopping
criteria. The first stopping criterion controls the growth rate of episode
length. The second stopping criterion happens when the number of visits to any
state-action pair is doubled. We establish $\tilde O(HS\sqrt{AT})$ bounds on
expected regret under a Bayesian setting, where $S$ and $A$ are the sizes of
the state and action spaces, $T$ is time, and $H$ is the bound of the span.
This regret bound matches the best available bound for weakly communicating
MDPs. Numerical results show it to perform better than existing algorithms for
infinite horizon MDPs.

本文提出了一种基于贝叶斯的 Thompson Sampling 加持的动态时段算法 (TSDE)，尝试在无限的时间尺度内解决了一个学习未知 MDP 的问题，实现了很好的性能并达到了理论界限。