Multi-Armed Bandits and Exploration, machine learning lesson

A routing service sends each job along route A or route B and records only whether the job succeeded on the route it took. Neither success rate is known, and the service never learns what the other route would have done with the same job. Should it keep using the route that looks best so far, or keep trying the other one in case its early results were bad luck? This lesson models the problem as a stationary multi-armed bandit, estimates action values from the rewards actually observed, compares greedy, epsilon-greedy and upper confidence bound rules, and uses regret to measure what the choices cost. The routes and their success probabilities are constructed for a simulation.

Key terms

Multi-armed bandit

Definition A stationary stochastic multi-armed bandit has a finite set of $k \ge 2$ actions, called arms, and for each arm $a$ a fixed reward distribution with a finite mean. In each round $t = 1, 2, \dots, T$ the learner chooses an arm $A_t$ and then observes a reward $R_t$ . Given $A_t = a$ and everything that happened in earlier rounds, the reward $R_t$ is a new independent draw from the distribution of arm $a$ . Stationary means that these distributions never change, neither over time nor in response to earlier actions, so there is no state for an action to alter. The learner observes only the reward of the arm it chose, and the rewards the other arms would have given in that round stay unknown. A policy is the rule that chooses $A_t$ from the earlier actions and rewards $A_1, R_1, \dots, A_{t-1}, R_{t-1}$ , possibly with the help of its own random numbers.

In plain words A bandit problem is learning by trying. Each choice earns a reward and also gathers information, but only about the arm that was chosen, so the policy decides which data will exist. This differs from supervised learning, where every training example arrives with its label, and from problems with states, where a choice also changes the situation for later rounds. If sending jobs along a route wore out its equipment or built up congestion, the reward distributions would depend on earlier actions, and a model with states such as a Markov decision process would be needed.

Example In the constructed routing simulation each job is one round with two arms. Route A succeeds with probability $0.4$ and route B with probability $0.65$ , and the reward is $1$ for a success and $0$ for a failure. The simulator knows these probabilities and the policy does not. If job 7 goes along route A and fails, the policy records a reward of $0$ for route A and learns nothing about how route B would have handled job 7.

Action value and incremental mean update

Definition The action value of arm $a$ is its expected reward

\mu_a = E[R_t \mid A_t = a],

which in a stationary bandit is the same in every round. The largest action value is $\mu^* = \max_a \mu_a$ . The learner estimates $\mu_a$ by the sample average $Q(a)$ of the rewards observed from arm $a$ , which is defined once the arm has been chosen at least once. If $Q_n$ is the average of the first $n$ rewards from arm $a$ , with the subscript counting rewards of this arm only, and the arm then gives the reward $R$ , the new average is

Q_{n+1} = Q_n + \frac{R - Q_n}{n + 1}.

This incremental mean update gives exactly the number that recomputing the average of all $n + 1$ rewards gives, and it needs only the count and the current average. With $n = 0$ it returns $Q_1 = R$ whatever starting value is stored. In a round that chooses arm $a$ , only the count and the estimate of arm $a$ change. If an arm is chosen infinitely often, its rewards are independent draws with mean $\mu_a$ , so by the law of large numbers its sample average converges to $\mu_a$ with probability $1$ .

In plain words Each update moves the old average toward the new reward by the fraction $1/(n + 1)$ of the gap between them, a fraction that shrinks as evidence accumulates. The action value is a fixed property of the arm, while the estimate is a statistic that changes with every reward and carries sampling error. An average of five rewards computed exactly is still an uncertain estimate. The estimate of an arm that is no longer chosen never changes again, however wrong it is.

Example Route A has been chosen 4 times with average reward $0.5$ , so its rewards sum to $2$ . A fifth job on route A succeeds. Recomputing gives $3/5 = 0.6$ , and the incremental update gives the same value,

0.5 + \frac{1 - 0.5}{5} = 0.6 .

The count and estimate of route B stay as they were, because route B was not chosen. The estimate $0.6$ is far from the simulator’s value $\mu_{\text{A}} = 0.4$ , which five rewards can easily produce.

Exploration and exploitation

Definition In a given round, a greedy arm is an arm with the largest current estimate $Q(a)$ , with a fixed rule for ties such as taking the arm listed first. Exploitation means choosing the greedy arm, the best arm according to the current estimates. Exploration means choosing another arm in order to learn more about it. The greedy policy exploits in every round. Because a bandit reveals only the rewards of chosen arms, exploration is the only way to correct the estimate of an arm that currently looks worse. The policies on this page first try each arm once, so that every estimate is defined.

In plain words Exploiting uses what is already known and exploring finds out more, and each round can do only one of the two. Too little exploration can lock the learner onto an inferior arm after one unlucky reward. Too much keeps spending rounds on arms already known to be worse. With rewards of $0$ and $1$ , an arm that has earned at least one reward of $1$ keeps a positive average forever, so from then on the greedy policy never chooses an arm whose rewards so far are all $0$ .

Example Each policy in the simulation tries route A and then route B. Suppose route A’s first job succeeds and route B’s fails, so $Q(\text{A}) = 1$ and $Q(\text{B}) = 0$ , although route B is the better route. After $n$ jobs on route A that include this first success, its average is at least $1/n > 0$ , so the greedy policy chooses route A in every later round and the estimate for route B stays at $0$ . This start has probability $0.4 \times 0.35 = 0.14$ . It occurred in the simulated run of 1000 jobs, where the greedy policy chose route A 999 times and route B once. Its final estimate for route A was $394/999 \approx 0.394$ , close to $0.4$ , while the estimate for route B never moved from its unlucky $0$ .

Epsilon-greedy policy

Definition Let $0 \le \epsilon \le 1$ . After each of the $k$ arms has been tried once, the epsilon-greedy policy makes an independent random decision in each round. With probability $1 - \epsilon$ it chooses the greedy arm, and with probability $\epsilon$ it chooses one of the $k$ arms uniformly at random, the greedy arm included. So the greedy arm, with ties settled by the fixed rule, is chosen with probability

1 - \epsilon + \frac{\epsilon}{k},

and every other arm with probability $\epsilon / k$ , including an arm tied for the largest estimate that the tie rule passed over. The value $\epsilon = 0$ gives the greedy policy and $\epsilon = 1$ the uniformly random policy. When $\epsilon > 0$ , every arm has probability at least $\epsilon / k$ in every round, so every arm is chosen infinitely often with probability $1$ and every estimate converges to its action value. With a fixed $\epsilon > 0$ , each arm with $\mu_a < \mu^*$ also keeps that probability in every round, so the expected number of rounds spent on it grows at least in proportion to the number of rounds.

In plain words Epsilon-greedy exploits most of the time and, in a fixed share of rounds, ignores the estimates and picks at random. The random rounds keep adding rewards for every arm, so an unlucky start can be corrected. A common slip is to read $\epsilon$ as the probability of choosing a non-greedy arm. The random rounds can also land on the greedy arm, so that probability is $\epsilon (k - 1)/k$ . They also ignore how much is already known, so they keep sampling an arm long after it is clearly worse.

Example With two routes and $\epsilon = 0.1$ , the greedy route is chosen with probability $0.9 + 0.1/2 = 0.95$ and the other route with probability $0.05$ . Before the run, the simulator drew a table of the reward each route would give in each round, hidden from the policies, and both policies used the same table, with a separate random number generator for the policy’s own choices. Epsilon-greedy therefore also started with $Q(\text{A}) = 1$ and $Q(\text{B}) = 0$ . Its random rounds tried route B again, the estimate for route B rose above that for route A, and over 1000 rounds it chose route A 113 times and route B 887 times, collecting 623 successes against 394 for the greedy policy. One seeded run shows the mechanism, and it does not by itself rank the two policies.

Regret

Definition For a bandit with action values $\mu_a$ and largest value $\mu^*$ , the gap of arm $a$ is $\Delta_a = \mu^* - \mu_a \ge 0$ . For $T$ rounds with chosen arms $A_1, \dots, A_T$ , the pseudo-regret is

\begin{aligned} \operatorname{Reg}_T &= \sum_{t=1}^{T} (\mu^* - \mu_{A_t}) \\[0.4em] &= \sum_{a} \Delta_a N_T(a), \end{aligned}

where $N_T(a)$ is the number of rounds that chose arm $a$ . It depends on the random actions, and it is never negative. Its expected value is the expected regret, and since the expected reward of a round given its action is $\mu_{A_t}$ ,

\begin{aligned} &E[\operatorname{Reg}_T] \\[0.4em] &\quad = T\mu^* - E\Bigl[\sum_{t=1}^{T} R_t\Bigr]. \end{aligned}

The realized shortfall $T\mu^* - \sum_t R_t$ is a different quantity. It also contains the luck of the reward draws, and it can be negative.

In plain words Regret adds up the expected reward given up, round by round, by not choosing the best arm. Each inferior choice costs its gap, so many choices of a slightly worse arm can cost less than a few choices of a much worse one. Computing regret requires the true action values, which a simulator knows and a real service does not. When the expected regret divided by $T$ tends to $0$ , the expected average reward per round approaches $\mu^*$ .

Example In the simulation $\mu^* = 0.65$ and route A has gap $0.25$ . The greedy run chose route A 999 times, so its pseudo-regret is $999 \times 0.25 = 249.75$ . The epsilon-greedy run chose route A 113 times, for $113 \times 0.25 = 28.25$ . The realized shortfalls are $650 - 394 = 256$ and $650 - 623 = 27$ . The epsilon-greedy shortfall is smaller than its pseudo-regret because its choices had an expected total of $113 \times 0.4 + 887 \times 0.65 = 621.75$ successes and the draws happened to give $1.25$ more. A broader comparison would repeat the run with independent seeds and report the spread of the results.

Upper confidence bound

Definition Assume a stationary bandit with rewards in $[0, 1]$ , where the rewards of each arm are independent and identically distributed and independent of the other arms. The upper confidence bound rule UCB1 first chooses each arm once. After $t \ge k$ rounds, let $N_t(a)$ be the number of times arm $a$ has been chosen, so that the counts add to $t$ , and let $Q_t(a)$ be its sample average. The next arm is one with the largest index

U_t(a) = Q_t(a) + \sqrt{\frac{2 \ln t}{N_t(a)}},

with a fixed rule for ties. The bonus is a confidence width. For a fixed number $n$ of rewards from arm $a$ , Hoeffding’s inequality bounds the probability that their average falls more than $\sqrt{2 \ln t / n}$ below $\mu_a$ by $t^{-4}$ . Under these assumptions the expected regret of UCB1 after any number $T$ of rounds satisfies

\begin{aligned} &E[\operatorname{Reg}_T] \le \sum_{a:\, \Delta_a > 0} \frac{8 \ln T}{\Delta_a} \\[0.4em] &\quad + \Bigl(1 + \frac{\pi^2}{3}\Bigr) \sum_{a} \Delta_a , \end{aligned}

so it grows at most logarithmically in $T$ .

In plain words UCB1 adds to each average a bonus that is large for an arm with few observations and shrinks as its count grows, then picks the arm with the largest optimistic value. An arm gets chosen either because its average is high or because too little is known about it to rule it out. Unlike the random rounds of epsilon-greedy, this exploration goes to the arms whose values are uncertain, and a clearly worse arm is chosen less and less often. The index is a decision score and not a probability, so it can exceed $1$ . The guarantee needs the stated assumptions. When the reward distributions drift over time, old averages and counts no longer describe the current arms and the bound does not apply.

Example After $t = 10$ rounds, suppose route A has average $0.5$ from 2 trials and route B has average $0.625$ from 8 trials. The bonuses are

\begin{aligned} \sqrt{\frac{2 \ln 10}{2}} &\approx 1.5174, \\[0.4em] \sqrt{\frac{2 \ln 10}{8}} &\approx 0.7587, \end{aligned}

so $U_{10}(\text{A}) \approx 2.0174$ and $U_{10}(\text{B}) \approx 1.3837$ . UCB1 chooses route A although route B has the higher average, because two trials leave the value of route A very uncertain. Both indices exceed $1$ , which no success probability can do.

Check yourself

Two arms give rewards of $0$ or $1$ . A greedy policy tries arm 1 and then arm 2 once each and receives $1$ and $0$ . In the next four rounds arm 1 gives $1$ , $0$ , $0$ and $0$ . Use the incremental update to find the estimate for arm 1 after each of its rewards, and explain why arm 2 is never chosen again.

Show the answer

The first reward sets the estimate to $Q_1 = 1$ . The next updates are

\begin{aligned} Q_2 &= 1 + \tfrac{1 - 1}{2} = 1, \\[0.4em] Q_3 &= 1 + \tfrac{0 - 1}{3} = \tfrac23, \\[0.4em] Q_4 &= \tfrac23 + \tfrac{0 - 2/3}{4} = \tfrac12, \\[0.4em] Q_5 &= \tfrac12 + \tfrac{0 - 1/2}{5} = \tfrac25. \end{aligned}

As a check, arm 1 has 2 successes in 5 rewards, and $2/5$ is their average. The estimate for arm 2 stays at $0$ . Arm 1 has at least one reward of $1$ , so after $n$ rewards its average is at least $1/n > 0$ , and the greedy policy chooses arm 1 in every round. The single $0$ from arm 2 may be bad luck, and only exploration could reveal that.

Three arms have estimates $0.5$ , $0.7$ and $0.7$ , ties go to the arm listed first, and $\epsilon = 0.2$ . Find the probability that the epsilon-greedy policy chooses each arm in the next round. A classmate says that the policy chooses a non-greedy arm with probability $0.2$ . Is that right?

Show the answer

The greedy arm is arm 2, the first of the two tied arms. It is chosen with probability

0.8 + \frac{0.2}{3} = \frac{13}{15} \approx 0.867,

and arms 1 and 3 are each chosen with probability $0.2/3 = 1/15 \approx 0.067$ . The three probabilities add to $1$ .

The classmate is wrong. A non-greedy arm is chosen with probability $2/15 \approx 0.133$ , because one third of the random rounds land on arm 2. The tie rule also matters, since arm 3 shares the largest estimate yet receives only the exploration probability $1/15$ .

In a constructed simulator two arms have action values $0.3$ and $0.7$ . Over 50 rounds a policy chose the inferior arm 12 times and collected 36 rewards of $1$ , the other rewards being $0$ . Find the pseudo-regret and the realized shortfall $50\mu^* - \sum_t R_t$ . A classmate concludes from the shortfall that the policy chose better than always picking the better arm. What is wrong with that reading?

Show the answer

The gap of the inferior arm is $0.7 - 0.3 = 0.4$ , so the pseudo-regret is $12 \times 0.4 = 4.8$ . The realized shortfall is $50 \times 0.7 - 36 = 35 - 36 = -1$ .

Given these choices, the expected total reward is $12 \times 0.3 + 38 \times 0.7 = 30.2$ , while always choosing the better arm has expected total $35$ . The difference $4.8$ is the pseudo-regret, the expected cost of the 12 inferior choices. The run collected $36$ , which is $5.8$ more than expected, because the reward draws were lucky. The shortfall mixes that luck with the cost of the choices, so a negative value reflects lucky draws rather than better choices, while the pseudo-regret can never be negative. Both numbers also need the true action values, which only a simulator provides.

Multi-Armed Bandits and Exploration

Key terms

Multi-armed bandit

Action value and incremental mean update

Exploration and exploitation

Epsilon-greedy policy

Regret

Upper confidence bound

Check yourself

How this lesson connects

Builds on

Used later in