Reinforcement learning playgroundMiddleLesson 2906 min read

Multi-armed bandits

The simplest RL game: many choices, each with a hidden chance of reward. Learn epsilon-greedy, the classic way to balance trying and using.

✦ Ask the tutor 🧪 Lab · 25 min 📝 Lesson test

Speed

Lesson in motion

In 60 seconds

Multi-armed bandits

The simplest RL game: many choices, each with a hidden chance of reward. Learn epsilon-greedy, the classic way to balance trying and using.

1/4

In simple words

A new railway station has five chai stalls. Some make great chai, some make weak chai, but you cannot tell by looking. If you always go back to the first stall you liked, you might miss a better one. If you try a random stall every day, you drink a lot of bad chai. How do you choose?

A multi-armed bandit is a game with several choices, called arms. The name comes from casino slot machines, once called "one-armed bandits". Each arm gives a reward with some hidden average. There is only one state: every round, you face the same choices again. So the only question is: which arm, this time?

Keeping score: the running average

For each arm, the agent keeps an estimate Q[arm] of its average reward, and a count N[arm] of how often it was tried. After each pull it nudges the estimate toward the new reward:

The running-average updatepython

Q, N = [0.0, 0.0, 0.0], [0, 0, 0]    # estimates and counts for three stalls
arm = 2
for reward in [1, 0, 1, 1]:           # four visits to stall 2
    N[arm] += 1
    Q[arm] += (reward - Q[arm]) / N[arm]    # move a bit toward the new reward
    print(f"after reward {reward}: Q[2] = {Q[arm]:.3f}")

This gives exactly the average of all rewards from that arm, without storing the whole list. The same "old estimate plus a step toward the new information" pattern will return in Q-learning.

Explore or exploit?

Always exploit (greedy)

Always picks the arm that looks best so far
Can lock onto an arm that got lucky early
Never discovers that another arm is better

Always explore (random)

Picks any arm with equal chance
Learns about every arm
Keeps wasting pulls on bad arms forever

Epsilon-greedy mixes the two. Pick a small number epsilon, such as 0.1. Each round, with chance epsilon pick a random arm (explore). Otherwise pick the arm with the highest Q (exploit). If two arms tie, pick one of them at random, so no arm is favoured by accident.

Python: a greedy agent can get stuckpython

import random

probs = [0.4, 0.8]           # arm 1 is clearly better, but the agent does not know
def run(epsilon, seed):
    rng = random.Random(seed)
    Q, N = [0.0, 0.0], [0, 0]
    for t in range(500):
        if rng.random() < epsilon:
            arm = rng.randrange(2)
        else:
            arm = 0 if Q[0] >= Q[1] else 1       # greedy; ties go to arm 0
        r = 1 if rng.random() < probs[arm] else 0
        N[arm] += 1
        Q[arm] += (r - Q[arm]) / N[arm]
    return N

for eps in (0.0, 0.1):
    print(f"epsilon={eps}: pulls per arm = {run(eps, seed=3)}")

With epsilon=0, the agent tries arm 0 first, gets some reward, and never has a reason to try arm 1. With a little exploration, it soon discovers that arm 1 is better and uses it most of the time.

Where bandits show up

Testing designs: some websites and apps use bandit methods to try several versions of a button or headline, and slowly send more people to the one that works best.
Recommendations: choosing which item to show, while still trying new items so they get a fair chance.
Everyday life: picking a restaurant, a route to college, or a tuition teacher is a bandit problem too.

Watch out

When real people are the "arms" or the audience, exploration is not free. Showing someone a worse option has a real cost. Serious uses need care, limits and, for things like health or loans, human review and the rules of that field.

Note

Other bandit methods explore more cleverly than epsilon-greedy. Two well-known families are upper confidence bound (UCB), which gives a bonus to arms tried only a few times, and Thompson sampling, which picks arms in proportion to how likely each is to be the best. Epsilon-greedy is the simplest place to start.

Try this. In the code above, change probs to [0.75, 0.8]. The arms are now very close. Does epsilon = 0.1 still find the better one in 500 rounds? Why is it harder?

Watch and read more

Lab

An epsilon-greedy chai-stall agent that finds the best stall and uses it most of the time.

~25 min

The problem

Five chai stalls each serve a great cup (reward 1) with a hidden chance. The starter's choose ignores everything it learned and always picks at random.

Press Run. Every epsilon gives the same poor result, because choose never uses epsilon or Q.
Write epsilon-greedy in choose: with chance epsilon return a random stall; otherwise return the stall with the highest Q. If several stalls tie for highest, pick one of them at random using rng.
Run again and compare epsilon = 0, 0.1, 0.3 and 1.0. Which one has the best average reward? Which one finds the best stall most often?
Press Check. It tests your agent on six new station layouts.
Write two sentences on why epsilon = 0 sometimes does well and sometimes badly.

Practice lab

Edit the code and run it. Python runs in your browser — nothing is sent to our server.

Ctrl + Enter to run

import random

# Five chai stalls. PROBS holds each stall's hidden chance of a great cup.
PROBS = [0.3, 0.55, 0.2, 0.75, 0.45]

def choose(Q, epsilon, rng):
    """Epsilon-greedy: with chance epsilon pick a random stall, else the best-looking one."""
    # TODO: this version always picks at random. Use epsilon and Q.
    return rng.randrange(len(Q))

def update(Q, N, arm, reward):
    """Running average of the rewards seen from each stall."""
    N[arm] += 1
    Q[arm] += (reward - Q[arm]) / N[arm]

def run(probs, steps=2000, epsilon=0.1, seed=0):
    rng = random.Random(seed)
    Q, N = [0.0] * len(probs), [0] * len(probs)
    picks, total = [], 0
    for _ in range(steps):
        arm = choose(Q, epsilon, rng)
        reward = 1 if rng.random() < probs[arm] else 0
        update(Q, N, arm, reward)
        picks.append(arm)
        total += reward
    return picks, total / steps, Q

best = PROBS.index(max(PROBS))
for eps in (0.0, 0.1, 0.3, 1.0):
    avgs, shares = [], []
    for seed in range(5):                       # five runs, each with its own luck
        picks, avg, Q = run(PROBS, epsilon=eps, seed=seed)
        avgs.append(avg)
        shares.append(picks[-1000:].count(best) / 1000)
    per_seed = " ".join(f"{x:.0%}" for x in shares)
    print(f"epsilon={eps:<4} average reward={sum(avgs) / 5:.3f}   best stall share in last 1000, per seed: {per_seed}")

Output

No output. Add print(...) to see values.

You are done when

choose returns a random stall with chance epsilon and the highest-Q stall otherwise
Ties are broken at random, not always toward the first stall
The comparison shows epsilon = 1.0 has the lowest average reward, and a small epsilon does best overall
The written answer explains that epsilon = 0 depends on early luck

Hard questions

Try to answer before you reveal. If you can answer these, you understood the lesson.

Q1With epsilon = 0.1 and five stalls, what is the highest share of visits the best stall can get in the long run?Reveal

About 92%. The agent exploits 90% of the time and picks the best stall then. When it explores (10%), it picks at random, and one time in five that random pick is also the best stall: 0.9 + 0.1 x 0.2 = 0.92. This ceiling is why people lower epsilon over time.

Q2All estimates start at 0. What happens if you start them at 1.0 instead, with epsilon = 0?Reveal

This is called optimistic initial values. Every untried stall looks perfect, so the greedy agent tries it, gets disappointed (the average drops below 1), and moves on to the next untried stall. So it explores every stall early, even with no randomness. It is a neat trick for simple problems, but it only encourages exploring at the start.

Please sign in to continue.

Questions people ask

Why not explore for a while, then exploit forever?

That is a fair strategy, called "explore then commit". Its weakness is choosing how long to explore: too short and you may commit to the wrong arm, too long and you waste pulls. Epsilon-greedy keeps a small amount of exploring forever, which also helps if the arms change over time.

What if the rewards change over time?

Then a plain average learns too slowly, because old rewards count as much as new ones. A common fix is a constant step size, such as Q += 0.1 * (reward - Q), which gives recent rewards more weight.

Is 0.1 always the right epsilon?

No. It is a common starting value. The lab lets you compare values. The next unit shows how to start high and lower epsilon over time.

Why is it called 'bandit'?

Old slot machines had one lever (an "arm") and took people's money, so people called them "one-armed bandits". A game with many levers became a "multi-armed bandit". Please do not try this on real gambling machines.

Lesson test

5 questions. Get 3 right (60%) to pass and complete this lesson.