A multi-armed bandit is a repeated choice among actions, or “arms,” with uncertain rewards. Each arm has a reward distribution. The agent tries to maximize total reward by learning which choices pay off, but its actions do not change the environment’s state. Unlike a Markov decision process, the choice does not require planning through state transitions. section 12.1.6 section 12.1
Three slot machines
Imagine 90 pulls across three machines whose payoff means and standard deviations are (8, 0.5), (10, 0.7), and (5, 0.45). Machine 2 has the highest mean, but each pull produces a sampled payoff. Choosing among them illustrates the tension: try other machines to learn, or keep choosing the one that currently looks best. section 12.1.6
Several strategies make that trade-off differently:
- Explore only: choose an arm at random on every trial. section 12.1.6
- Exploit only: choose the arm with the highest supplied mean payoff. section 12.1.6
- Epsilon-greedy: choose randomly with probability epsilon; otherwise choose the highest-mean arm. The example uses epsilon = 0.1. section 12.1.6
- Upper confidence bound (UCB): sample every arm first, then combine its average observed reward with an exploration term that favors less-played arms. The example uses an exploration parameter of 2. section 12.1.6
Compare strategies using average regret: the gap between the best arm’s mean payoff and the sampled reward, averaged over trials. In the illustrated run, UCB and greedy exploitation have lower reported average regret than random exploration. Treat that comparison carefully: the greedy and epsilon-greedy examples select using the payoff means supplied in the simulation, rather than estimating those means from observations. section 12.1.6
def ucb(c):
num_plays = np.zeros(K) #1
sum_rewards = np.zeros(K) #2
total_regret = 0 #3
for i in range(K): #4
reward = sample_payoff(i)
num_plays[i] += 1
sum_rewards[i] += reward
for t in range(K, num_trials): #5
ucb_values = sum_rewards / num_plays + c * np.sqrt(np.log(t) / num_plays) #6
selected_machine = np.argmax(ucb_values)
reward = sample_payoff(selected_machine)
num_plays[selected_machine] += 1
sum_rewards[selected_machine] += reward
optimal_reward = max_reward
regret = optimal_reward - reward
total_regret += regret
average_regret = total_regret / num_trials
return average_regret
The UCB listing shows the practical sequence: sample each arm, track play counts and reward sums, then choose using average reward plus an exploration term. section 12.1.6
