Multi-Armed Bandits: The Exploration–Exploitation Dilemma

Imagine a row of slot machines ("one-armed bandits"), each paying out with an unknown probability. You have 1,000 coins. Which machines do you play? Playing the machine that seems best so far (exploitation) risks missing a better one; trying others (exploration) costs coins. The multi-armed bandit problem isolates this exploration–exploitation dilemma without the complications of states and delayed rewards. It is also directly useful: adaptive clinical trials, website optimisation, news recommendation and choosing which message format gets the best response.

The problem#

There are $K$ actions (arms). Pulling arm $a$ yields a random reward with unknown mean $q_*(a)$. At each round $t$ the agent picks $A_t$ and observes $R_t$. The goal is to maximise total reward — equivalently, minimise regret:

the reward lost relative to always playing the best arm $a^*$. Lai and Robbins (1985) showed that any algorithm must suffer regret growing at least logarithmically in $T$; good algorithms achieve $O(\log T)$.

Action-value estimates#

Estimate each arm's mean by its sample average, updated incrementally:

Strategy 1: ε-greedy#

Choose the best-looking arm with probability $1 - \varepsilon$, a random arm with probability $\varepsilon$. Simple and robust, but it explores uniformly (wasting pulls on clearly bad arms) and forever (constant ε gives linear regret; decaying ε helps).

Strategy 2: optimistic initialisation#

Start all estimates at a high value (e.g. $Q_0 = 5$ when rewards are in $[0, 1]$). Each arm disappoints when tried, so the agent naturally tries them all. A neat trick for stationary problems, but it only drives initial exploration.

Strategy 3: Upper Confidence Bound (UCB)#

Optimism in the face of uncertainty: prefer arms that could plausibly be best. UCB1 (Auer, Cesa-Bianchi & Fischer, 2002) selects

The bonus is large for rarely tried arms and shrinks as an arm is sampled; it grows slowly with time so no arm is abandoned forever. UCB1 achieves logarithmic regret. (The same formula drives Monte Carlo Tree Search — UCT — from the Foundations track.)

Strategy 4: Thompson sampling#

A Bayesian approach (Thompson, 1933). Keep a posterior over each arm's mean; each round, sample a plausible mean from each posterior and play the arm with the highest sample. For Bernoulli rewards with Beta priors, the update is simple counting:

Arms are chosen with probability equal to the posterior probability that they are best ("probability matching"). Thompson sampling performs excellently in practice and achieves near-optimal regret.

import numpy as np

true_p = np.array([0.04, 0.05, 0.07, 0.045])      # e.g. response rates of four message variants
T, K = 20_000, len(true_p)

def simulate(strategy, seed=0):
    rng = np.random.default_rng(seed)
    n, s = np.zeros(K), np.zeros(K)               # pulls and successes
    a_, b_ = np.ones(K), np.ones(K)               # Beta posteriors
    reward = 0
    for t in range(1, T + 1):
        q = np.divide(s, n, out=np.zeros(K), where=n > 0)
        if strategy == "eps-greedy":
            a = rng.integers(K) if rng.random() < 0.1 else int(np.argmax(q))
        elif strategy == "ucb":
            a = t - 1 if t <= K else int(np.argmax(q + np.sqrt(2 * np.log(t) / n)))
        else:                                      # thompson
            a = int(np.argmax(rng.beta(a_, b_)))
        r = rng.random() < true_p[a]
        n[a] += 1; s[a] += r; a_[a] += r; b_[a] += 1 - r; reward += r
    return T * true_p.max() - reward, n.astype(int)

for strat in ["eps-greedy", "ucb", "thompson"]:
    regret, pulls = simulate(strat)
    print(f"{strat:<11} regret={regret:7.1f}  pulls per arm={pulls}")

Thompson sampling and UCB concentrate pulls on the best arm far more efficiently than ε-greedy.

Bandits vs A/B testing#

A classic A/B test splits traffic evenly for a fixed period, then picks a winner — clean statistical inference but costly exploration. Bandits adaptively shift traffic towards better variants, reducing regret. Trade-off: adaptive allocation complicates unbiased inference about effect sizes. Choose based on whether your priority is learning (A/B test) or earning (bandit).

Contextual bandits#

Often the best action depends on context — a user's language, device or location. Contextual bandits observe a feature vector $\mathbf{x}_t$ before choosing. LinUCB (Li et al., 2010, used for news recommendation) models reward as linear in features per arm and adds a confidence bonus from the estimate's uncertainty. Contextual bandits are widely used for personalisation and are the one-step special case of full RL.