Learning Unknown Markov Decision Processes: A Thompson Sampling Approach
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Õ(HS √ 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.
The paper proposes TSDE, a posterior sampling algorithm for RL in the average reward infinite horizon setting. This algorithm uses dynamic episodes but unlike Lazy-PSRL avoids technical issues by not only terminating an episode when an observation count doubled but also terminating episodes when they become too long. This ensures that the episode length cannot grow faster than linear and ultimately a Bayesian regret bound of O(HS(AT)^.5) is shown.
Posterior sampling methods typically outperform UCB-type algorithms and therefore a posterior sampling algorithm for non-episodic RL with rigorous regret bounds is desirable. This paper proposes such an algorithm, which is of high interest. The paper is well written and overall easy to follow. I have verified all proofs but Theorem 2 and found no mistakes. The presentation is rigorous and the main insights are discussed sufficiently. This paper is therefore a good contribution to the NIPS community.
A comparison against UCRL2 with empirically tightened confidence intervals would have been interesting. An more extended comparison of TSDE for MDPs with increasing size would have also been interesting to empirically determine the dependency of the regret on the problem quantities. This would have given insights on whether we can expect to prove a tighter regret bound (e.g. with \sqrt(S) dependency) without changing the algorithm. Nonetheless, all of this is somewhat out of the scope of this paper. 
Minor detail: The condition on the bottom of page 4 should hold for all s.