Thompson Sampling for RL
What you'll learn: How to explore intelligently by sampling actions from probability distributions that reflect your uncertainty about their true value.
The Core Idea
Thompson Sampling is a probability matching approach where you maintain a distribution over each action's expected value rather than a single point estimate. At each decision step, you sample a value from each action's distribution and pick the action whose sample is highest. Actions you're uncertain about have wider distributions, so they occasionally produce high samples—giving them chances to be explored.
Think of it like this: imagine choosing between restaurants, but instead of remembering exact star ratings, you remember ranges of plausibility. A new restaurant might be "probably 3-5 stars" (wide uncertainty), while your favorite is "definitely 4.5 stars" (narrow). Thompson Sampling says: randomly draw a rating from each range and visit whichever gets the highest draw. Sometimes the new place will get lucky and win, naturally balancing exploration and exploitation.
How It Works in RL
- Initialize: Start with prior distributions over Q-values for each state-action pair (often Gaussian or Beta distributions)
- Sample: In state s, draw one sample from each action's distribution
- Act: Execute the action whose sample is highest
- Update: After observing reward, update that action's distribution (tighten it around observed values using Bayesian updates)
The beauty: actions with high uncertainty get explored proportionally to the probability they might be optimal. No need for epsilon schedules or confidence bonuses—uncertainty naturally drives exploration, and as you learn, distributions narrow and exploitation dominates.
Key Takeaway: Thompson Sampling explores by sampling from posterior distributions over action values, naturally matching exploration to uncertainty and requiring no manual tuning of exploration parameters.