Thompson sampling (in RL)

Thompson sampling explores by gambling on its own beliefs. Instead of committing to a single best estimate, the agent keeps a probability distribution — a posterior — over how good each action or the whole environment might be. To act, it draws one sample from that posterior and behaves as if that sample were the truth. Actions it is uncertain about get chosen whenever a hopeful sample lands on them, so uncertainty naturally drives exploration.

This elegant rule of acting greedily with respect to a sampled belief automatically balances exploration and exploitation: as evidence accumulates the posterior tightens, the samples agree, and the agent settles on the true best. It often matches or beats UCB in practice and enjoys strong regret guarantees in bandits. The hard part in full RL is maintaining and sampling from a posterior over value functions or models when the state space is large.