The Multi-Armed Bandit

The multi-armed bandit is the simplest model of learning by trial and error: repeatedly pull one of several arms with unknown reward, aiming to maximize total reward.

The model

A K-armed bandit offers K actions (arms), each returning a reward drawn from its own fixed but unknown distribution. On each of T rounds the agent picks one arm and observes only that arm's reward. The name comes from a row of slot machines (one-armed bandits): which to play, given that each pays out at an unknown average rate? The goal is to maximize cumulative reward, equivalently to minimize regret against always playing the best arm.

The regret benchmark

Let the best arm have mean reward mu*. Regret after T rounds is T mu* minus the expected total reward collected. A good algorithm keeps regret growing only logarithmically in T, because once enough samples identify the best arm, it is played almost always. The Lai-Robbins bound proves that logarithmic regret is optimal: no algorithm can do asymptotically better, and the constant depends on how close the suboptimal arms' means are to the best.

Strategies

Several approaches achieve near-optimal regret. Epsilon-greedy exploits the best-known arm most of the time but explores randomly with small probability epsilon. Upper-confidence-bound methods play the arm with the best optimistic estimate. Thompson sampling maintains a posterior over each arm's mean and plays each in proportion to its probability of being best, sampling from the posteriors to decide.

import numpy as np

def epsilon_greedy(pull, K, T, eps=0.1):
    counts = np.zeros(K); values = np.zeros(K)
    for t in range(T):
        if np.random.rand() < eps:
            a = np.random.randint(K)      # explore
        else:
            a = int(np.argmax(values))    # exploit
        r = pull(a)
        counts[a] += 1
        values[a] += (r - values[a]) / counts[a]  # running mean
    return values

Why it endures

The multi-armed bandit strips learning down to its essence: no state transitions, just the exploration-exploitation trade-off. It is the foundation for contextual bandits, reinforcement learning, and adaptive experimentation, and its clean theory (logarithmic regret, matching lower bounds) makes it the reference point against which more complex sequential-decision methods are measured.