posterior sampling for RL (PSRL)

Posterior sampling is Thompson sampling lifted from single actions to whole environments. The agent holds a posterior distribution over which MDP it might be living in — over the unknown transition and reward dynamics. At the start of each episode it draws one complete MDP from that posterior, solves it as if it were certainly true, and follows that optimal policy for the entire episode before sampling again.

Committing to one sampled world for a whole episode is what gives PSRL its power: the policy is internally consistent and pursues a coherent plan, producing deep, directed exploration rather than the dithering you get from per-step randomness. This makes it dramatically more efficient than epsilon-greedy on problems needing long sequences of purposeful actions, and it carries some of the best-known regret bounds — though sampling and solving an MDP each episode is computationally demanding.