6a5889bb0190d0211a991f47bb19a777-Reviews.html

Summary: this paper gives a regret analysis for an episodic reinforcement learning motivated by posterior sampling (as known as Thompson sampling). The idea is to sample, from the posterior, an MDP model at the beginning of each episode, follow this MDP's optimal policy in that episode, update the model posterior, and then repeat. In the past, despite good empirical performance, this algorithm (called PSRL) remains a heuristic approach without strong theoretical guarantees. This paper provides the first regret analysis, with a bound of O(\tau * S * \sqrt{A * T}), where H is the length of the episode and T is the total number of stpes. Numerical experiments on very simple MDPs show PSRL significantly outperform the other algorithm UCRL2 that enjoys a similar regret bound.