Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 37 ยท Getting Started

UCB, Thompson Sampling and Softmax Bandits

Go beyond epsilon-greedy: implement UCB1, Thompson sampling with Beta distributions and softmax gradient bandits in Python, and compare their regret.

Epsilon-greedy explores blindly. It picks a random arm even if that arm has already been tried 500 times and is clearly bad, and it picks the same random arm as likely as one that was never tried. Smarter strategies direct exploration towards arms whose value is still uncertain. This lesson covers three of them: Upper Confidence Bound (UCB), Thompson sampling, and softmax (gradient) selection.

All three are used in production systems for ad selection, A/B testing and recommendation, and the ideas carry straight into the full RL algorithms of later chapters.

Upper Confidence Bound (UCB1)

UCB follows the principle of optimism in the face of uncertainty. For each arm it computes an optimistic estimate of the true value: the average so far plus a bonus that is large when the arm has been tried few times.

score(a) = Q(a) + c * sqrt(ln(t) / N(a))

where t is the total number of pulls so far and N(a) the pulls of arm a. An arm that has never been tried (N = 0) is treated as infinite, so every arm is tried once. As N(a) grows the bonus shrinks, so an arm is chosen again only if its average is high or if it has been neglected for a while. The constant c controls how much exploration you want (a common value is 1 or 2).

Python UCB1 against epsilon-greedy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

UCB usually beats epsilon = 0.1 on this kind of testbed because its exploration is targeted and fades out. The constant matters: too small and UCB behaves like greedy, too large and it explores far too long.

Thompson sampling

Thompson sampling is a Bayesian approach and is often the best performer in practice. The idea: keep a probability distribution over each arm's true value. On every step, draw one random sample from each arm's distribution and pull the arm whose sample is largest.

Arms with a wide, uncertain distribution often produce a big sample and get tried. As an arm is pulled more, its distribution narrows around the truth, so it is chosen only if it really is good. Exploration and exploitation fall out of one mechanism with no tuning parameter.

For rewards that are 0 or 1 (click or no click, win or loss) the standard choice is a Beta distribution. Start each arm at Beta(1, 1), which is uniform. After a success increase alpha by 1; after a failure increase beta by 1. The mean of Beta(alpha, beta) is alpha / (alpha + beta).

Python Thompson sampling for click-through rates

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best ad (index 2) receives most of the traffic, yet the other ads still get a few views early on, when their distributions were wide. Compare this with a fixed A/B test, which splits traffic equally for the whole run and so wastes impressions on losing ads.

flowchart LR
    P["Beta posterior per arm"] --> D["draw one sample per arm"]
    D --> A["pull arm with largest sample"]
    A --> O["observe 0 or 1"]
    O --> U["update that arm's alpha or beta"]
    U --> P

Thompson sampling loop: uncertainty itself drives the exploration.

Softmax (Boltzmann) selection and gradient bandits

Another family chooses actions with probabilities that rise smoothly with value. Instead of values, the agent learns numerical preferences H(a), and the probability of arm a is the softmax of the preferences:

pi(a) = exp(H(a)) / sum over b of exp(H(b))

After each reward the preferences are adjusted by gradient ascent on expected reward. If the reward beat a running baseline (the average reward so far), the chosen arm's preference goes up and all others go down; if it was worse, the opposite happens. The baseline reduces variance and is a first glimpse of a trick that returns in policy gradients.

Python A gradient bandit with and without a baseline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because the true means sit around +4, rewards are almost always positive. Without a baseline every pulled arm looks "good" and gets boosted, which slows learning badly. Subtracting the running average fixes that, so the baseline version finds the best arm much more often.

Contextual bandits: a step towards full RL

In a contextual bandit you first see a context (a user's age, a time of day), then choose an arm, then get a reward. The best arm depends on the context, so the agent learns a policy that maps context to action. There is still no long-term effect: today's choice does not alter tomorrow's context. When actions do change future states, you are in a full reinforcement learning problem, which is what Markov decision processes describe.

Method Exploration comes from Needs tuning
Epsilon-greedy Random actions epsilon
UCB1 Bonus for rarely tried arms c
Thompson sampling Randomness in posterior samples Prior
Softmax / gradient Probabilities from preferences Step size, baseline

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In UCB1, what happens to the exploration bonus of an arm as it is pulled more often?

    The bonus is proportional to sqrt(ln t / N(a)), which falls as N(a) grows.
  2. 2. What does Thompson sampling do on each step?

    Randomness in the samples balances exploration and exploitation without a tuned parameter.
  3. 3. For Bernoulli (0 or 1) rewards, which distribution is the natural choice for Thompson sampling?

    The Beta distribution is conjugate to Bernoulli outcomes: each success or failure simply adds 1 to alpha or beta.
  4. 4. Why does a gradient bandit use a baseline?

    Comparing each reward with the average reward means only better-than-usual outcomes strengthen an action.

Summary

  • UCB adds an uncertainty bonus to each arm's average, so rarely tried arms get examined.
  • Thompson sampling draws from a posterior per arm and pulls the largest draw; Beta posteriors suit 0/1 rewards.
  • Gradient bandits learn softmax preferences and use a baseline to cut variance.
  • Contextual bandits let the best action depend on a context; full RL adds consequences for the future.
  • All three methods usually beat epsilon-greedy because their exploration is directed at uncertainty.

Next: Markov Decision Processes