Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 37 ยท Getting Started

Exploration vs Exploitation and Epsilon-Greedy Bandits

Understand the exploration-exploitation trade-off with the multi-armed bandit problem: sample-average estimates, epsilon-greedy action selection, optimistic starts and regret.

Imagine ten slot machines in a casino. Each pays out at a different, unknown average rate. You have 1,000 pulls. Do you keep pulling the machine that has paid best so far, or do you test the others in case one is better? That tension is the heart of reinforcement learning, and the multi-armed bandit is its cleanest form.

A bandit has no states and no long-term consequences: every pull is independent, you choose an action, you get a reward. Because it strips RL down to one question, how should I balance trying new things against using what I know?, it is the best place to study exploration before adding states in the next chapter.

The problem

There are k actions (arms). Pulling arm a gives a random reward with an unknown mean q*(a). You want to maximize the total reward over T pulls. If you knew q* you would pull the best arm every time; since you do not, you must estimate it.

  • Exploit: choose the arm that currently looks best. Safe now, but you may be stuck with a mediocre arm forever.
  • Explore: choose another arm. Costly now, but it improves your estimates.

You cannot do both on the same pull, so you must mix them.

Estimating action values

Let N(a) be how many times you pulled arm a, and Q(a) your estimate of its mean. The natural estimate is the sample average. You do not need to store every reward: an incremental update gives the same result.

Q(a) <- Q(a) + (1 / N(a)) * (reward - Q(a))

The pattern new estimate = old estimate + step size * (target - old estimate) appears in nearly every algorithm in this course. The term in brackets is the error; the step size says how far to move toward the target.

Epsilon-greedy

The simplest way to mix exploration and exploitation: with probability epsilon pick a random arm, otherwise pick the arm with the highest Q. A typical epsilon is 0.1 or 0.01.

Python A 10-armed bandit and an epsilon-greedy agent

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How much exploration is right?

One run is noisy. To compare settings fairly, average over many random bandit problems. The code below runs 300 independent problems at once, using array operations across problems, and compares three agents:

  • epsilon = 0 (pure greedy): never explores after its first pull.
  • epsilon = 0.01: explores rarely.
  • epsilon = 0.1: explores often.
Python Comparing epsilon values on 300 bandit problems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see the classic pattern (the run prints about 1.01, 1.25 and 1.34 average reward, and about 36%, 57% and 84% optimal actions). Greedy gets stuck: in most problems it locks onto a suboptimal arm and its average stays lowest. epsilon = 0.1 finds the best arm fastest, but it will always waste 10% of pulls on random choices, so its best-arm percentage can never pass about 91%. epsilon = 0.01 improves more slowly; given a much longer run its smaller waste lets it catch up and overtake. There is no universal best epsilon: it depends on how long you run and how noisy the rewards are.

flowchart TD
    S["Choose an action"] --> D{"random number < epsilon?"}
    D -->|"yes: explore"| R["pick any arm at random"]
    D -->|"no: exploit"| G["pick arm with highest Q"]
    R --> U["observe reward, update Q"]
    G --> U

Epsilon-greedy in one picture.

Optimistic initial values

A cheap alternative to random exploration: start every Q(a) at an unrealistically high number, say +5 when true means are near 0. Every arm disappoints when tried, so the agent keeps switching to arms it has not tried yet. Exploration happens "for free" at the start and then fades by itself. It works for stationary problems and does nothing for a world that changes later.

Nonstationary problems and a constant step size

If the arms' true means drift over time, old rewards should count less. Replace 1 / N(a) with a constant step size alpha, for example 0.1. Then Q becomes an exponential moving average: recent rewards weigh most, and the weight of a reward decays by a factor of (1 - alpha) each time a new one arrives. This idea returns in every RL algorithm that learns in a changing world, which includes the agent's own improving policy.

Python Sample average vs constant step size on a drifting bandit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both use epsilon 0.1. The constant step size wins here because it forgets stale information; the sample average treats a reward from step 5 as important as one from step 2000.

Regret

A common way to score a bandit algorithm is regret: the reward you lost compared with always pulling the best arm. After T steps, regret = T * max q* - sum of the means of the arms you chose. Epsilon-greedy with a fixed epsilon has regret that grows linearly forever, because it keeps exploring at the same rate. Better algorithms, shown in UCB and Thompson sampling, make exploration shrink as knowledge grows.

Real-world bandits are everywhere: choosing which headline, price or recommendation to show next. The "arms" are options, the "reward" is a click or a sale, and the same trade-off applies.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In epsilon-greedy with epsilon = 0.1, how often does the agent pick a random action?

    With probability epsilon the agent explores with a random action; otherwise it picks the highest-valued one.
  2. 2. What is the incremental sample-average update?

    Moving Q a fraction 1/N toward each new reward gives exactly the average of all rewards seen so far.
  3. 3. Why does a pure greedy agent (epsilon = 0) often do poorly?

    Without exploration, an early lucky pull on a mediocre arm can make it look best forever.
  4. 4. When would you prefer a constant step size alpha over 1/N?

    A constant step size forgets old data at a steady rate, which tracks changing values; 1/N weights all history equally.
  5. 5. What do optimistic initial values do?

    High initial estimates are brought down by real rewards, pushing the agent to try untested arms first.

Summary

  • A bandit is the simplest RL problem: actions and rewards, no states.
  • The agent must balance exploiting the best-known arm and exploring others.
  • Estimate arm values with the incremental update Q = Q + step * (reward - Q).
  • Epsilon-greedy explores randomly with probability epsilon; optimistic initial values explore by disappointment.
  • Use a constant step size when values change over time; regret measures the cost of not knowing.

Next: UCB and Thompson Sampling