The simplest case: bandits and exploration

Reinforcement learning is far easier to understand if you take the states out of it first. This section does that: a fixed set of options, a reward after each choice, and nothing else, which isolates the one question that makes the whole field hard, namely when to stop trying alternatives and commit to whatever looks best so far. You implement three answers to it and compare them on a measure of what the choosing itself cost you.

Strip RL down to one decision#

Imagine three versions of a signup page. Each visitor sees one, and either signs up or does not. You do not know which version is best, and every visitor you send to a worse one is a lost signup. This is a multi-armed bandit: repeated choices, a reward after each, no states to worry about. It isolates the exploration problem cleanly.

The measure that makes the comparison honest is regret: the signups you would have had if you had known the best page from the start, minus the signups you actually got. It is not something the agent can compute — it needs the true rates — but you can compute it in a simulation, and it is the only number that scores the choosing itself rather than the luck. Everything below is measured against these three pages, whose true rates are 5, 7 and 10 per cent, which is the sort of gap a real page test lives with.

import random

RATES = [0.05, 0.07, 0.10]          # the true signup rate of each page. The agent never sees this.
BEST = max(RATES)

def visit(page):
    """One visitor sees one page and either signs up or does not."""
    return 1 if random.random() < RATES[page] else 0

def regret(plays):
    """Signups lost by not having shown the best page to every visitor."""
    return sum(BEST - RATES[p] for p in plays)

Epsilon-greedy#

Most of the time pick the action with the best average so far. With a small probability, epsilon, pick at random. Simple, and it works, but it keeps exploring obviously bad options forever at the same rate.

import random

class EpsilonGreedy:
    def __init__(self, n, eps=0.1):
        self.counts, self.means, self.eps = [0] * n, [0.0] * n, eps

    def choose(self):
        if random.random() < self.eps:
            return random.randrange(len(self.means))
        return max(range(len(self.means)), key=lambda a: self.means[a])

    def update(self, a, reward):
        self.counts[a] += 1
        self.means[a] += (reward - self.means[a]) / self.counts[a]   # running mean

Optimism: upper confidence bounds#

UCB picks the action whose plausible best case is highest: its average plus a bonus that is large when it has been tried rarely. Untried actions get explored, well-understood bad actions are dropped, and exploration fades naturally.

import math

def ucb_choose(counts, means, t):
    for a, c in enumerate(counts):
        if c == 0:
            return a                                   # try everything once
    return max(range(len(means)),
               key=lambda a: means[a] + math.sqrt(2 * math.log(t) / counts[a]))

Thompson sampling#

Keep a belief about each action's success rate as a probability distribution. Each round, draw one sample from each belief and pick the highest draw. Actions you are unsure about sometimes draw high and get tried; actions you are confident are poor rarely do. For yes or no rewards, the Beta distribution makes this a few lines.

import random

wins, losses = [1, 1, 1], [1, 1, 1]          # Beta(1, 1) prior: know nothing

def thompson_choose():
    draws = [random.betavariate(w, l) for w, l in zip(wins, losses)]
    return draws.index(max(draws))

def thompson_update(a, reward):
    if reward: wins[a] += 1
    else:      losses[a] += 1

Measuring it: regret#

Regret is the reward you missed by not always playing the best action. Plot cumulative regret over time for each strategy. A good strategy's regret curve bends and flattens; a bad one keeps climbing in a straight line.

Straight-line regret is what committing produces, and the usual alternative to a bandit is exactly that: run a fixed split for a while, declare a winner, send everything to it. Here are all of them, including that one, at two horizons, over 400 simulated runs each. Two horizons matter because a strategy that ends on the wrong page loses at a constant rate forever, so its regret grows with the length of the experiment while a bandit's does not.

def run_pilot(steps, per_page):
    """The usual thing: a fixed split, then all traffic to the winner."""
    agent, plays = EpsilonGreedy(3, eps=0.0), []
    for page in range(3):
        for _ in range(per_page):
            agent.update(page, visit(page))
            plays.append(page)
    winner = agent.choose()
    return regret(plays + [winner] * (steps - 3 * per_page)), winner

def run_epsilon(steps, eps):
    agent, plays = EpsilonGreedy(3, eps), []
    for _ in range(steps):
        a = agent.choose()
        agent.update(a, visit(a))
        plays.append(a)
    return regret(plays), max(range(3), key=lambda a: agent.counts[a])

def run_ucb(steps, c=2.0):
    counts, means, plays = [0] * 3, [0.0] * 3, []
    for t in range(1, steps + 1):
        if min(counts) == 0:
            a = counts.index(0)                          # every page once before judging any
        elif c == 2.0:
            a = ucb_choose(counts, means, t)             # the block above, textbook constant
        else:
            a = max(range(3),
                    key=lambda p: means[p] + math.sqrt(c * math.log(t) / counts[p]))
        counts[a] += 1
        means[a] += (visit(a) - means[a]) / counts[a]
        plays.append(a)
    return regret(plays), max(range(3), key=lambda a: counts[a])

def run_thompson(steps):
    wins[:] = [1, 1, 1]
    losses[:] = [1, 1, 1]                                # forget the previous run
    counts, plays = [0] * 3, []
    for _ in range(steps):
        a = thompson_choose()
        thompson_update(a, visit(a))
        counts[a] += 1
        plays.append(a)
    return regret(plays), max(range(3), key=lambda a: counts[a])

STRATEGIES = {
    "pilot of 50 each":   lambda n: run_pilot(n, 50),
    "pilot of 300 each":  lambda n: run_pilot(n, 300),
    "epsilon-greedy 0.10": lambda n: run_epsilon(n, 0.10),
    "epsilon-greedy 0.01": lambda n: run_epsilon(n, 0.01),
    "UCB, c = 2 (textbook)": lambda n: run_ucb(n, 2.0),
    "UCB, c = 0.2 (tuned)": lambda n: run_ucb(n, 0.2),
    "Thompson":            run_thompson,
}

for horizon in (2000, 20000):
    print(f"{horizon} visitors, averaged over 400 runs")
    for name, strategy in STRATEGIES.items():
        random.seed(0)
        lost, wrong = 0.0, 0
        for run in range(400):
            r, final = strategy(horizon)
            lost += r
            wrong += (final != 2)                        # page 3 is the best one
        print(f"  {name:22s} {lost/400:7.1f} signups lost   "
              f"settled on the wrong page {100*wrong/400:5.1f}%")
# 2000 visitors, averaged over 400 runs
#   pilot of 50 each          29.5 signups lost   settled on the wrong page  39.5%
#   pilot of 300 each         27.7 signups lost   settled on the wrong page  10.8%
#   epsilon-greedy 0.10       29.6 signups lost   settled on the wrong page  25.2%
#   epsilon-greedy 0.01       72.6 signups lost   settled on the wrong page  74.8%
#   UCB, c = 2 (textbook)     41.9 signups lost   settled on the wrong page   2.5%
#   UCB, c = 0.2 (tuned)      23.3 signups lost   settled on the wrong page   0.8%
#   Thompson                  17.9 signups lost   settled on the wrong page   5.5%
# 20000 visitors, averaged over 400 runs
#   pilot of 50 each         277.9 signups lost   settled on the wrong page  39.5%
#   pilot of 300 each         87.5 signups lost   settled on the wrong page  10.8%
#   epsilon-greedy 0.10       86.4 signups lost   settled on the wrong page   0.8%
#   epsilon-greedy 0.01      245.9 signups lost   settled on the wrong page  21.2%
#   UCB, c = 2 (textbook)    255.1 signups lost   settled on the wrong page   0.0%
#   UCB, c = 0.2 (tuned)      64.1 signups lost   settled on the wrong page   0.0%
#   Thompson                  33.1 signups lost   settled on the wrong page   0.0%

Start with the pilot. Fifty visitors per page sounds like a test; at those rates the standard error of each estimate is about 3 percentage points against gaps of 2 and 3, so it picks the wrong page 39.5 per cent of the time. That error is then permanent, which is why its regret rises from 29.5 to 277.9 when the experiment runs ten times longer while every bandit's rises far less. Three hundred visitors per page is a real test and gets the wrong answer 10.8 per cent of the time — better, and still linear in the horizon.

Epsilon-greedy at 0.01 is the clearest failure on the page, and it is the one people write by accident when they think a small epsilon means a careful agent. It settles on the wrong page 74.8 per cent of the time at 2,000 visitors. Its first few observations are almost all zeros — nobody signs up — and a page that scores an early success is then ahead of the others with only a one in a hundred chance per visitor of anything else being tried. It is not exploring too little in general; it is exploring too little early, when the estimates are worthless. At 0.10 it recovers and its regret is respectable, at the price of permanently sending a tenth of visitors to pages it already knows are worse, which is why its regret also grows linearly, from 29.6 to 86.4.

The two UCB rows are the trap worth taking away. The textbook bonus assumes rewards spread across the whole of 0 to 1; here they are all near 0.07, so a bonus of the square root of two log t over n swamps every real difference and the agent explores far past the point of usefulness — 255.1 lost at the long horizon, worse than epsilon-greedy, while never once ending on the wrong page. Dropping the constant to 0.2 cuts that to 64.1. A method with an exploration constant tuned for your reward scale is a different method from the one in the paper, and the constant is not optional.

Thompson sampling wins at both horizons with no tuning at all, which is the usual outcome of this comparison and the reason it is widely used in production ranking systems. Its exploration is proportional to how uncertain it actually is, so it needs no schedule and no constant, and its regret bends: 17.9 over 2,000 visitors and only 33.1 over 20,000, since almost all of the cost is paid early.

Where an engineer actually meets this#

Bandits are the one piece of reinforcement learning that turns up routinely in ordinary product work, usually without the name. Anywhere you have many candidate items, a cheap binary signal and traffic to spend, the machinery above applies directly.

• Ranking and recommendation. Which of a thousand candidate articles to put in the slot, where a click is the reward. Almost always contextual: the features of the user and the item go into a model that predicts reward, and Thompson sampling or an upper confidence bound is applied to that model's uncertainty rather than to a per-item count.
• Anything with a cold start. New items have no history, so a purely greedy ranker will never show them and they will never acquire one. This is exactly the locked-on failure above, and it is why catalogues that rank purely on measured click-through go stale.
• Model and prompt selection at serving time. Several prompts or several models, a thumbs-up or a task success signal, and a slow shift towards whichever is winning — a bandit, and a much better fit than an offline evaluation when the traffic is already there.
• Non-stationary rewards. Real click rates drift. The estimators above assume they do not, and the standard fix is to discount old evidence: an exponentially weighted mean instead of a running one, or decaying the Beta counts towards the prior so the agent stays willing to re-check.