Multi-Armed Bandits

The bandit is RL stripped to one decision: choose among actions with unknown payoffs to maximize total reward.

The simplest RL problem

A multi-armed bandit offers K actions (arms), each returning a reward from an unknown distribution. There is no state and no transition dynamics, just repeated choice. This makes the bandit the cleanest laboratory for the exploration-exploitation trade-off, and its algorithms underpin recommendation, clinical trials, and online experimentation.

Regret

Kronos motion — reward

Performance is measured by regret: the difference between the reward of always pulling the best arm and the reward actually earned. The Lai-Robbins bound shows regret must grow at least logarithmically in the number of pulls for any good algorithm, and UCB and Thompson sampling both achieve this optimal rate.

Core algorithms

Epsilon-greedy: exploit the best arm, explore randomly a fraction of the time
UCB: pull the arm with the highest optimistic value estimate
Thompson sampling: sample each arm's mean from a posterior, pull the highest sample

Contextual bandits

The contextual bandit adds side information: before each choice the agent sees a context (features), and rewards depend on both context and arm. This bridges bandits and full RL, capturing personalization where the best action depends on the situation but choices do not change future states. LinUCB and Thompson sampling with linear models are standard.

python

# epsilon-greedy bandit
if random() < epsilon:
    arm = randint(K)                 # explore
else:
    arm = argmax(estimated_means)    # exploit
reward = pull(arm)
counts[arm] += 1
estimated_means[arm] += (reward - estimated_means[arm]) / counts[arm]

Why bandits matter

Bandits isolate exploration from the credit-assignment complexity of sequential RL, so their theory is sharp and their algorithms transfer upward: UCB drives MCTS, Thompson sampling generalizes to posterior sampling for MDPs. Master the bandit and much of exploration in full RL follows.