Multi-armed bandits

1Values of actions

Write A_t for the spot fished on morning t and R_t for its catch. Each spot a has a value, the catch to expect when fishing it:

On the lake, q_*(pier) = 1, q_*(reeds) = 3, q_*(rocks) = 4 and q_*(bridge) = 2 fish a morning. Her estimate on morning t, Q_t(a), is the average of the catches the spot has given so far:

Here 𝟙_Ai=a is 1 if spot a was fished on morning i and 0 if not, so both sums keep only the mornings spent at a. A spot never fished gets a default estimate, such as 0. The more a spot is fished, the closer its average comes to q_*(a), by the law of large numbers: the average of more and more draws settles on their mean. This is the sample-average method.

The simplest way to choose is greedy: fish the spot with the largest estimate, the greedy action, breaking ties at random.

An ε-greedy angler is greedy on most mornings, but with a small probability ε she picks a spot at random among all k, the greedy one included. The greedy spot is then fished with probability 1 − ε + ε/k, and each other spot with ε/k. With k = 4 and ε = 0.2:

• the greedy spot gets 0.85 and each other spot 0.05;
• when two spots tie for the largest estimate, they split the 0.8 of greedy mornings, so each gets 0.4 + 0.05 = 0.45, and the other two keep 0.05.

A greedy angler who starts with every estimate at 0 can stop exploring after a single morning:

1. On the first morning all four estimates are 0, and the tie is broken at random.
2. A catch is never negative, so if the first one is above zero, that spot's estimate rises above 0 while the other three stay at 0.
3. Its average stays above 0 whatever it catches next, so the other spots are never tried again.

The figure follows one such season. Each row is a morning, with the four estimates before it; the spot fished is shaded yellow, and its catch is in red.

Over 1,000 seasons of 300 mornings, 9 greedy seasons in 10 never leave their first spot (the others caught nothing on their first morning, so the tie stayed open), and greedy fishes the rocks on about 29% of mornings all season long. Exploring fixes this:

The last column is what each angler would catch with exact estimates: 4 for greedy, the best possible, by fishing the rocks every morning, and less with ε, since exploring still sends her to worse spots on some mornings. With ε = 0.2 she finds the rocks sooner, fishing them on 76% of mornings 91–100 against 62% with ε = 0.05, but later in the season her many random mornings cost her more. Exploring costs fish today and pays later.

2Averaging as you go

Averaging every catch means storing every catch. The average can instead be updated after each one, keeping one number and one count per spot. Take a single spot and count its own mornings: R_i is now the catch of its ith morning, and Q_n its estimate after it has been fished n − 1 times:

The first n − 1 catches add up to (n − 1)Q_n, so after the nth catch the average is Q_n+1 = [R_n + (n − 1)Q_n]/n, which rearranges to

It holds for n = 1 too, giving Q₂ = R₁ whatever the starting guess Q₁. Two counters are now in play: t counts the mornings of the season, and n the mornings at one spot. Over six mornings, for the rocks:

The rocks end at 4, the plain average of 5, 3, 6 and 2. Each line of the table has the same shape:

The bracket is an error, how far the estimate is from the target, here the latest catch. A single catch is a noisy target, but on average it points the right way, and the step size, here 1/n, sets how far to move. Every method in these notes moves an estimate a step toward a target; the Monte Carlo and TD notes do it with other targets. A step size is written α, or α_n(a) when it changes from one catch to the next.

The algorithm

A simple bandit algorithm, ε-greedy with sample averages:

1. For every spot a, set Q(a) ← 0 and N(a) ← 0.
2. Choose A: with probability 1 − ε, the spot with the largest Q, breaking ties at random; with probability ε, a spot at random.
3. Fish A and observe the catch R.
4. Set N(A) ← N(A) + 1 and Q(A) ← Q(A) + [R − Q(A)]/N(A).
5. Repeat from step 2 every morning.

3When the fish move

A sample average weighs the first catch as much as the latest. That is right while the spots stay the same, but a lake changes, against the “does not change over time” of the bandit problem defined above. In a nonstationary problem the true values drift while the agent plays, and recent rewards deserve more weight. The usual way to give it is a constant step size α, with 0 < α ≤ 1:

Rewritten as αR_n + (1 − α)Q_n, it can be unrolled by putting in the same update for Q_n, then for Q_n−1, down to Q₁:

It is a weighted average of the start and every catch. Each update multiplies the old estimate by 1 − α, so a catch's weight shrinks by that factor with every later catch. The catches' weights form a geometric sum, α[1 + (1 − α) + ⋯ + (1 − α)ⁿ⁻¹] = 1 − (1 − α)ⁿ, so with Q₁'s (1 − α)ⁿ they add up to 1.

With α = 0.25 and Q₁ = 0, the rocks' four catches from section 2 (5, 3, 6 and 2) give estimates of 1.25, 1.69, 2.77 and 2.57. The figure shows the weights in the last one.

Now let the water warm at morning 151: the fish leave the rocks for the reeds, the rocks' mean falls from 4 to 1 and the reeds' rises from 3 to 5. To compare a sample average with α = 0.25 alone, suppose the angler kept fishing the rocks and every catch was exactly the mean.

With random catches and ε = 0.2, over 1,000 seasons, the share of mornings at the best spot (the rocks until the warming, the reeds after it) is:

Before the warming, the sample average does a little better, since its estimates are less noisy. After it, the sample average keeps going back to the rocks, and from morning 151 to 300 it catches 3.46 fish a morning against 4.34 with α = 0.25.

Both updates are one update with a step size α_n(a) that may change from catch to catch:

With α_n(a) = 1/n it is the sample average, and with a constant α the recency-weighted one. The estimates converge to the true values, with probability 1 (in all but impossibly unlucky seasons), when

The first sum must grow without limit, so that the steps can always overcome the start and unlucky catches; the second must stay finite, so that the steps end up small enough to settle. Sample averages meet both: the sum of 1/n reaches 7.49 by n = 1,000 and keeps growing, while the sum of 1/n² stays below 1.645. A constant α fails the second, so its estimates never settle and keep following the latest catches, which is what a changing lake needs. Schedules that meet both often learn slowly or need tuning, and since most problems change over time, a constant α is the usual choice in practice.

4Optimistic starts

Every method so far depends on the starting estimates Q₁(a): it is biased by them, its estimates pulled toward the start and so, on average, off from q_*(a). How long the bias lasts depends on the step size:

• with sample averages it disappears after a spot's first catch, since Q₂ = R₁;
• with a constant α it only shrinks, as (1 − α)ⁿ: from Q₁ = 8, the catches 5, 3, 6 and 2 with α = 0.25 still give 5.11, and 2.53 of that is the start.

So the start is a choice, a way to put in prior knowledge or to drive the exploring. The greedy angler of section 1 started at 0, below every spot's value, and stayed at her first spot. A constant α would not have freed her: a catch of 0 only multiplies her estimate by 1 − α, so it never falls back to 0. Start her at 8 instead, above every spot's mean, and almost every catch disappoints, so the greedy choice moves on to the spots still at 8, until all have been tried. The figure is drawn as in section 1.

Over 1,000 seasons, the share of mornings 291–300 spent at the rocks:

With sample averages the optimism buys about one try of each spot (a first catch of 8 or more, which is rare, keeps a spot in the running), and an unlucky first catch can still bury the rocks for good. With α = 0.25 it fades over several catches and keeps the angler trying for longer. The last two rows share a step size, which makes them the fair comparison, and the optimistic start wins.

It helps only once, at the start. If the water warms at morning 151, the start has long been forgotten, and nothing in it sends the angler to look for what changed. A third way to direct exploring, upper-confidence-bound selection, prefers spots whose estimates are still uncertain because they have been fished little; this note does not go into it.

5Preferences instead of values

Instead of estimating values, the angler can learn a preference H_t(a) for each spot and choose spots with probabilities that grow with it, by a softmax, whose exponential makes every probability positive and whose division by the sum makes them add up to 1:

Only differences between preferences matter: the softmax of 0.3, −0.1, 0.5 and 0 is 0.275, 0.185, 0.336 and 0.204, and adding 5 to every preference leaves it unchanged. The preferences start equal, here at 0, so every spot starts at 0.25. After each morning they are updated:

Here R_t, the baseline, is the average of the catches before morning t, with R₁ ≐ R₁. A catch above the baseline raises the preference of the spot fished and lowers the others; a catch below it does the opposite. The others move by their probabilities, which add up to 1 − π_t(A_t), exactly what the spot fished moves, so the sum of the preferences never changes: starting at 0, it stays 0. Replaying section 2's six mornings, the same spots and catches, with α = 0.1:

• Morning 1 changes nothing, since R₁ = R₁.
• Morning 5 is a catch of 6 at the rocks against a baseline of 2.75, the average of 2, 5, 3 and 1, and π(rocks) rises from 0.319 to 0.387.
• Morning 6 is a catch of 2 against a baseline of 3.4, and π(rocks) falls to 0.360. Had morning 6 alone used no baseline, the same catch of 2 would have raised it to 0.426.

The baseline makes a catch count as good or bad compared with the usual catch. Without it, any catch of a fish or more raises the spot fished, the poor spots included, and the angler tells the spots apart more slowly. Over 1,000 seasons:

Why the update works

The update is stochastic gradient ascent on the expected catch. Exact gradient ascent would move each preference along the slope of the expected reward:

The values q_*(x) are unknown, so this slope cannot be computed. Four steps show that the update above follows it on average:

1. A baseline adds nothing. The values q_*(x) do not depend on the preferences, so the slope reaches only the probabilities: ∂E[R_t]/∂H_t(a) = Σ_x q_*(x) ∂π_t(x)/∂H_t(a). The probabilities always sum to 1, so their changes sum to 0: Σ_x ∂π_t(x)/∂H_t(a) = 0. Any number B_t that does not depend on x can therefore be subtracted:
   ∂E[R_t]∂H_t(a) = Σ_x (q_*(x) − B_t) ∂π_t(x)∂H_t(a)
2. The sum becomes an expectation. Multiplying each term by π_t(x)/π_t(x) weights it by the probability of fishing x, which makes the sum an expected value over the spot chosen, A_t:
   = E[(q_*(A_t) − B_t) ∂π_t(A_t)∂H_t(a) / π_t(A_t)]
3. What was observed replaces what is unknown. Choose B_t = R_t, which is built from the catches before t and so does not depend on the spot chosen at t. Then put the catch R_t in place of q_*(A_t). By the law of total expectation, the expected value can be taken first over the catch for a given A_t; the other factors depend only on A_t, and E[R_t | A_t] = q_*(A_t), so the result is the same.
4. The softmax's slope. In π_t(x) = e^H_t(x)/Σ_b e^H_t(b), raising H_t(a) grows the sum, and the numerator too when x = a. By the quotient rule, the slope is π_t(a) − π_t(a)² for x = a and −π_t(x)π_t(a) for any other x; together, ∂π_t(x)/∂H_t(a) = π_t(x)(𝟙_a=x − π_t(a)), where 𝟙_a=x is 1 if a = x and 0 if not. The π_t(A_t) cancels:
   ∂E[R_t]∂H_t(a) = E[(R_t − R_t)(𝟙_a=At − π_t(a))]

One sample of this expectation in place of the slope gives

the update of the preferences in one line. With a = A_t the indicator is 1, which gives the first line of the update above, and for every other a it is 0, which gives the second. Using one sample, right only on average, in place of the exact slope is what makes the ascent stochastic. The baseline does not change the expected update, whatever number it is, as long as it does not depend on the spot chosen, but it changes how much single updates vary, and so how fast the preferences settle.

6Summary

The key ideas next to their NumPy equivalents. r holds this morning's catch and a its spot, r_hist and a_hist the earlier ones, r_a the catches of spot a so far, oldest first and this morning's included, q, n and h the estimates, counts and preferences, k the number of spots and rng a NumPy random generator.