Thompson Sampling in RL

Thompson sampling explores by acting greedily with respect to a randomly sampled belief about the world.

Probability matching

Thompson sampling (posterior sampling) maintains a probability distribution over unknowns, samples one hypothesis from it, and acts optimally as if that sample were true. Because samples are drawn in proportion to how likely each hypothesis is, actions are tried in proportion to the probability they are best, an elegant randomized exploration strategy.

The bandit case

For a Bernoulli bandit, keep a Beta posterior over each arm's success probability. Each round, draw one sample per arm and pull the arm with the highest sampled value. Arms with uncertain, possibly-high means get pulled because their posteriors have wide upper tails; as evidence accumulates the posteriors sharpen and the best arm dominates. Regret is competitive with UCB and often better in practice.

import numpy as np

def thompson_bernoulli(successes, failures):
    samples = [np.random.beta(1+s, 1+f)
               for s, f in zip(successes, failures)]
    return int(np.argmax(samples))   # pull this arm

Posterior sampling for RL

The idea extends to full MDPs as Posterior Sampling for Reinforcement Learning (PSRL). Maintain a distribution over MDPs (transition and reward parameters); at the start of each episode, sample one MDP, solve it, and follow that policy for the whole episode. Committing to one sampled model for an episode produces coherent, deep exploration and yields strong Bayesian regret bounds.

Deep approximations

Exact posteriors are intractable with neural networks, so deep RL approximates them. Bootstrapped DQN trains an ensemble of value heads on different data subsets and acts greedily with respect to one randomly chosen head per episode, mimicking posterior sampling. This provides the temporally consistent exploration that epsilon-greedy lacks, at modest extra cost.