Multi-armed bandits

A stateless problem

A bandit has no states. There are k levers, each pull returns a reward drawn from an unknown distribution, and the lever you choose has no effect on what the others would have paid. You never observe the reward you did not collect, which is the whole difficulty in miniature. The name comes from gambling, but the shape is everywhere: a headline, a price, a treatment, a route. The only thing that carries between pulls is what you have learned.

It looks trivial and is not. Every question about exploration can be asked here without a world that changes underneath you: how long do you keep testing, how much does a lucky first pull cost, and what does it mean to learn efficiently when information is expensive. Solve the bandit well and the hard part of every later algorithm is already in view. The bandit is the laboratory where that question is cheapest to answer.

The estimate is an average

The value of an arm is its expected reward. After n pulls, the natural estimate is the mean of what those pulls returned, and the mean can be maintained without storing every reward: move the old estimate a fraction toward the new one, with the fraction equal to one over the count. The first pull sets the estimate outright; the hundredth moves it by one percent. The estimate is a statistic, not a memory.

That single line is the template for everything later. Q-learning moves a value toward a bootstrapped target, and policy gradients move probabilities toward actions that paid. In each case an estimate is nudged toward evidence, and the size of the nudge is the learning rate. Change the denominator and you change how much the past matters. A rate near one forgets quickly; a rate near zero barely moves.

Epsilon-greedy in a few lines

import numpy as np

counts = np.zeros(3)
values = np.zeros(3)
rates = [0.2, 0.5, 0.8]

for pull in range(1000):
    arm = int(np.argmax(values)) if np.random.rand() > 0.1 else np.random.randint(3)
    reward = np.random.binomial(1, rates[arm])
    counts[arm] += 1
    values[arm] += (reward - values[arm]) / counts[arm]

print(counts, values)

Greedy locks in

Always pulling the best current estimate is a policy that cannot correct itself. One arm that paid once looks perfect; a better arm that happened to pay zero on its only pull looks worthless, and is never tried again. The estimate is not wrong so much as never given the chance to become right. This is the cost of greed: it converts an accident into a belief.

Epsilon-greedy spends a fixed fraction of pulls on a random arm. It is crude, and it works: with probability epsilon the agent buys information, and with the rest it spends what it has. The choice of epsilon is a statement about how much you are willing to pay to be less certain. Too small and it never finds the better arm; too large and it never uses it. It is also the baseline every smarter rule has to beat.

Regret is the bill

Regret measures what you lost by not knowing: the reward the best arm would have earned, minus what you actually earned. A policy that keeps pulling a mediocre arm accumulates regret in a straight line. A policy that explores sensibly accumulates it logarithmically, because each arm only needs to be tested enough to rule it out. The curve is the clearest single picture of whether a bandit algorithm is working. A flat line means it has stopped making mistakes; a rising one means it is still paying for the same one.

Logarithmic regret is the best you can promise without assumptions about the arms. Thompson sampling gets there by keeping a distribution over each arm’s rate and sampling from it, which turns exploration into a natural consequence of uncertainty rather than a coin flip. The distribution narrows as evidence arrives, so an arm that has been tried stops being interesting without any schedule saying so. That is the difference between a schedule and a belief.