JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Optimism & Posterior: UCB and Thompson Sampling

Two principled engines of directed exploration: be optimistic about what you don't know, or act as if a sample from your beliefs were true.

Optimism in the face of uncertainty

The single most productive idea in exploration is optimism in the face of uncertainty. The rule: when you are unsure how good an action is, assume it is good and try it. If it really is good, you gain. If it is not, you find that out quickly and stop — your optimism is self-correcting. Crucially, optimism is directed: it pushes the agent precisely toward the things it knows least about, not toward random noise.

Contrast this with the undirected methods of the last guide. ε-greedy explores blindly; optimism explores because it is uncertain. That single change is what lets the methods below come with provable guarantees on a bandit.

UCB: a bonus for being unsure

The Upper Confidence Bound (UCB) makes optimism concrete. For each action keep two numbers: its estimated mean value, and a confidence bonus that shrinks the more often you have tried it. Then act greedily on mean + bonus — the optimistic estimate. An action you have barely tried carries a large bonus, so it wins even if its current mean is mediocre; once you have tried it a lot, the bonus fades and the true mean decides.

# UCB1 for a bandit: pick the arm with the highest optimistic value
for each arm a:
    bonus[a] = c * sqrt( ln(total_pulls) / pulls[a] )
    ucb[a]   = mean_reward[a] + bonus[a]
return argmax(ucb)   # try fewer-pulled arms while their bonus is large
UCB1: the bonus grows for rarely-pulled arms and shrinks as ln(t)/n.
a_t = \arg\max_a \left[ \hat{Q}(a) + c\sqrt{\dfrac{\ln t}{N(a)}} \right]

UCB1: pick the action with the highest estimated value plus a confidence bonus that grows for rarely-tried actions and shrinks as ln(t)/N(a).

Thompson sampling: gamble on a belief

Thompson sampling reaches the same goal by a different, beautifully simple route, rooted in Bayesian thinking. Instead of a single value estimate, keep a probability distribution over each action's true value (your posterior belief). To act: draw one random sample from each action's distribution, then pick the action whose sample is highest.

Thompson sampling keeps a posterior over each action's value; this Bayesian-update widget shows beliefs sharpening as evidence arrives.

Interactive widget: a prior distribution updates into a sharper posterior as new data is observed.

This handles exploration automatically. An action you are unsure about has a wide distribution, so its sample is sometimes very high — and it gets picked, and tried. An action you are confident is poor has a narrow distribution sitting low, so it almost never wins. As evidence accumulates, every distribution tightens and the policy settles onto the truly best action. The randomness is in proportion to your uncertainty — exactly the directed behavior we want.

Posterior sampling for whole MDPs

Scaling Thompson's idea from one action to a whole environment gives posterior sampling for RL (PSRL). Keep a posterior not over action values but over entire models of the world — the transition and reward dynamics. At the start of each episode, sample one complete plausible MDP from that posterior, solve it as if it were the truth, and follow that policy for the episode. Update the posterior with what you observe, then resample next episode.

Posterior sampling draws a whole environment model each episode; this interactive Markov chain shows what a 'model of the world' — states linked by transition probabilities — actually looks like.

Interactive Markov chain: states connected by transition probabilities, representing one sampled model of the environment.

Information gain: explore to learn

A third lens makes the goal explicit: information-gain exploration. Here the agent values an action partly for the reward it brings and partly for how much it expects to learn — how much it would reduce its own uncertainty about the world. Formally, that learning is measured as the expected reduction in the entropy of the posterior. This unifies the others: optimism and Thompson sampling can both be read as efficient, tractable approximations to "act where you will learn the most."

These three principles — optimism, posterior sampling, and information gain — are the theoretical bedrock. The remaining guides are mostly about how to estimate uncertainty once states are too many to count, which is where deep RL lives.