  Thompson Sampling is one of the most effective methods for contextual bandits
and has been generalized to posterior sampling for certain MDP settings.
However, existing posterior sampling methods for reinforcement learning are
limited by being model-based or lack worst-case theoretical guarantees beyond
linear MDPs. This paper proposes a new model-free formulation of posterior
sampling that applies to more general episodic reinforcement learning problems
with theoretical guarantees. We introduce novel proof techniques to show that
under suitable conditions, the worst-case regret of our posterior sampling
method matches the best known results of optimization based methods. In the
linear MDP setting with dimension, the regret of our algorithm scales linearly
with the dimension as compared to a quadratic dependence of the existing
posterior sampling-based exploration algorithms.
