74 - Reinforcement Learning: The Agent That Learns by Trial and Error (and the Exploration-Exploitation Dilemma)

So far every model in this series learned from examples: "here is the input, here is the right answer". Reinforcement learning (RL) changes the picture: nobody gives you the right answer. There is an agent acting in an environment, and after each action it receives a single number, a reward, which says how well it went right now. From the experience it accumulates, the agent must discover by itself what to do. It is how one learns to play, to walk, to drive a robot. In this article you fix the vocabulary, see how RL differs from supervised learning and face the most characteristic difficulty of the field, the exploration-exploitation dilemma, in the smallest possible case: the multi-armed bandit, measured on 2000 problems with a listing you can rerun.

The vocabulary, with one example for each word

Take a robot vacuum cleaner. The agent is whoever decides, that is the program that drives the robot; the environment is everything outside that decision which reacts to the actions: the house, the furniture, the floor. The state S is the description of the situation as the agent sees it (the sensor readings, the remaining charge), the action A is a choice among those available (turn left, go forward, return to the base). After every action the environment returns a reward R, a number: positive if it went well, negative if it went badly. It is the only learning signal, and the agent does not know why it received that number.

The interaction proceeds in time steps t; a complete sequence from start to finish (one cleaning run, one game, one attempt) is an episode. The policy π is the rule with which the agent chooses the action given the state, deterministic ("in this state, go right") or probabilistic, and it is what RL wants to learn. The goal is not the immediate reward but the return G, the sum of the future rewards: a robot that pushes a vase off the table to score a point right away has maximised the reward and lost the return. Finally, to exploit means to choose the action that, according to what you know, is the best, and to explore means to try others to find out whether there is a better one. Doing only one or only the other is a mistake, and the rest of the article measures how much each costs.

The analogy: choosing a restaurant in a new city

You are in a city you do not know and every evening you must choose a restaurant. After dinner you only know how much you liked it (the reward); nobody tells you which was the best in the city. The first restaurant you liked is a good candidate, but is it really the best, or just the first you tried? If you always go there (pure exploitation) you may never discover the exceptional restaurant round the corner. If you always try new restaurants (pure exploration) you never enjoy what you have learned. The sensible strategy is in between: mostly you return where you did well, now and then you try a new place. And your taste is noisy: a bad evening in an excellent restaurant should not make you discard the place. All this is, almost word for word, the multi-armed bandit.

The agent-environment loop

The drawing shows the only thing there is in the whole of RL. At every instant t: the agent observes the state S_t, chooses an action A_t according to its policy, and the environment answers with a reward R_{t+1} and a new state S_{t+1}. A trajectory is the sequence S_0, A_0, R_1, S_1, A_1, R_2, S_2, …. The return from time t, in its simplest form, is the sum of the subsequent rewards:

G_t = R_{t+1} + R_{t+2} + R_{t+3} + … + R_T

In the next pages of the series we will modify it with a discount, and we will see why it is needed (you will find it in the Bellman equation derived in full). What matters here is the idea: the agent does not maximise the last reward, but the sum of all those still to come. The same loop is the one the Gymnasium library exposes in code, with an environment that returns a new observation and a reward after every action: you get there in Gymnasium in practice.

How RL differs from supervised learning

                      Supervised                        Reinforcement learning
what it receives      the input and the right answer    a state and a reward
who gives the "right" a label, immediately              nobody: just a number, sometimes late
the data depend on    the dataset (fixed)               the agent's actions
feedback              complete (I know what I should    partial (I know how it went, not what
                      have done)                        would have happened with another action)
typical error         overfitting                       exploring too little, badly designed
                                                        reward, instability

Three difficulties follow from this table. The first is credit assignment: if you win a game after 200 moves, which move was decisive? The second is that the data are not independent: what the agent observes depends on what it has already done, so a bad policy produces poor data on what it has never tried. The third is exploration: you have to accept taking actions that look worse, in order to learn. In supervised learning (for example linear regression) the dataset stays still while the model changes; here it is the model that decides which data it will see. The bandit that follows isolates only the third difficulty, the easiest to measure.

The simplest case: the 10-armed bandit

Let us strip away everything but the essentials. There is no state (or there is just one): a slot machine with k = 10 levers, each with a different hidden mean reward. At each step you pull one lever and receive a random reward around that mean. Goal: obtain the highest total reward in 1000 pulls, without knowing which lever is the best. This is the multi-armed bandit problem, treated in the second chapter of Sutton and Barto, Reinforcement Learning: An Introduction (second edition), the reference text. The setup of the listing below is that of their "10-armed testbed" (section 2.3): 2000 randomly generated problems, true means drawn from a normal with mean 0 and variance 1, rewards with variance 1 around the mean. The numbers you read, however, are those produced by the listing on this machine, not those of the book, which I did not compare.

Estimating the value of an action and updating it without storing everything

Call q(a) the true mean reward of lever a (which we do not know) and Q_n(a) our estimate after n pulls of that lever: the mean of the rewards seen. To avoid keeping all the rewards we derive an incremental update, the same idea as section 2.4 of the book: constant memory and one computation per step.

Q_{n+1} = (1/(n+1)) · Σ_{i=1..n+1} R_i
        = (1/(n+1)) · ( R_{n+1} + Σ_{i=1..n} R_i )
        = (1/(n+1)) · ( R_{n+1} + n · Q_n )          because Σ_{i=1..n} R_i = n · Q_n
        = (1/(n+1)) · ( R_{n+1} + (n+1) · Q_n − Q_n )
        = Q_n + (1/(n+1)) · ( R_{n+1} − Q_n )

The step that carries the derivation is the third: the sum of the first n rewards is no longer needed, because it is already contained in n · Q_n. The final form has the structure we will meet throughout the series:

new estimate = old estimate + step × ( target − old estimate )

The term in brackets, R_{n+1} − Q_n, is an error: how much the reward just received differs from what we expected. If it is positive we raise the estimate, if negative we lower it, and the step 1/(n+1) says by how much. Check it with numbers: you pull a lever three times and receive 1.0, 0.0 and 2.0. After the first pull Q = 0 + 1·(1.0 − 0) = 1.0; after the second Q = 1.0 + ½·(0.0 − 1.0) = 0.5; after the third Q = 0.5 + ⅓·(2.0 − 0.5) = 1.0, exactly the mean of (1.0, 0.0, 2.0). If the step were constant (a fixed α in place of 1/n) you would get a "forgetful" mean, useful when rewards change over time; for sample means and estimates in general see also Statistics: estimating, comparing, deciding.

The ε-greedy strategy

How do you choose the lever? Two extremes. Greedy: always the lever with the highest Q. Random: always at random. The ε-greedy strategy is the simplest compromise: with probability ε you explore (random lever), with probability 1 − ε you exploit (lever with maximum Q). The listing uses numpy.random.default_rng(seed), the generator recommended by the NumPy documentation, with one seed for the bandit and a different one for the agent, so that two runs give the same output.

import numpy as np

class Bandit:
    """k-armed bandit: arm a pays a reward drawn from N(true_value[a], 1). The agent does not know true_value."""
    def __init__(self, k=10, seed=0):
        self.rng = np.random.default_rng(seed)
        self.true_value = self.rng.normal(0, 1, k)           # hidden mean reward of each arm
        self.best = int(self.true_value.argmax())
    def pull(self, a):
        return self.rng.normal(self.true_value[a], 1.0)

def run_epsilon_greedy(bandit, steps=1000, epsilon=0.1, seed=0):
    rng = np.random.default_rng(seed)
    k = len(bandit.true_value)
    Q = np.zeros(k)                                          # estimated value of each arm
    N = np.zeros(k)                                          # how many times each arm was pulled
    rewards, optimal = [], []
    for t in range(steps):
        if rng.random() < epsilon:
            a = int(rng.integers(k))                         # EXPLORE: a random arm
        else:
            a = int(Q.argmax())                              # EXPLOIT: the best arm so far
        r = bandit.pull(a)
        N[a] += 1
        Q[a] += (r - Q[a]) / N[a]                            # incremental sample average (derived in the text)
        rewards.append(r); optimal.append(a == bandit.best)
    return np.array(rewards), np.array(optimal)

The Bandit class hides a vector true_value of 10 means drawn from a standard normal; pull(a) returns a random reward around the mean of lever a (standard deviation 1). best is the index of the best lever, which the agent does not know: it is only there to measure. In run_epsilon_greedy the agent keeps Q (estimates, all zero at the start) and N (how many times it has pulled each lever). At each step, with probability epsilon it chooses at random (rng.integers(k)), otherwise it takes Q.argmax(); then it pulls the lever, increments the counter and applies the update derived above, Q[a] += (r - Q[a]) / N[a]. Two details matter. If you remove the line that increments N[a] before the update, the division by N[a] happens with N[a] = 0 the first time you touch a lever: Q becomes infinite and NumPy reports it only with a warning, not an error. And argmax in case of a tie returns the first occurrence, as the NumPy documentation states: at the start, with all estimates at zero, the greedy agent therefore always begins with lever 0.

The experiment: three values of ε on 2000 problems

A single problem is too noisy to conclude anything: the best lever might have been found by luck. We average over 2000 different bandits (each with its own 10 means), 1000 pulls each, for ε = 0 (pure greedy), 0.01 and 0.1. The code of experiment accumulates the reward and the frequency of optimal choice step by step, summing over 2000 problems (each with a different seed, hence different hidden means) and dividing. The run takes about half a minute on an ordinary CPU (28 s in one trial on this machine: an order of magnitude, not a benchmark).

# Average over 2000 independent bandit problems, so that luck washes out
def experiment(epsilon, n_problems=2000, steps=1000):
    R = np.zeros(steps); O = np.zeros(steps)
    for p in range(n_problems):
        bandit = Bandit(seed=p)
        r, o = run_epsilon_greedy(bandit, steps, epsilon, seed=10_000 + p)
        R += r; O += o
    return R / n_problems, O / n_problems

for eps in (0.0, 0.01, 0.1):
    R, O = experiment(eps)
    print(f"epsilon={eps:4.2f}   mean reward: first 10 steps {R[:10].mean():.2f}, steps 100-199 {R[100:200].mean():.2f}, last 100 steps {R[-100:].mean():.2f}"
          f"   |   optimal arm chosen in the last 100 steps: {100 * O[-100:].mean():.0f}%")

# Output (two consecutive runs, same output):
# epsilon=0.00   mean reward: first 10 steps 0.59, steps 100-199 1.02, last 100 steps 1.02   |   optimal arm chosen in the last 100 steps: 36%
# epsilon=0.01   mean reward: first 10 steps 0.59, steps 100-199 1.08, last 100 steps 1.30   |   optimal arm chosen in the last 100 steps: 59%
# epsilon=0.10   mean reward: first 10 steps 0.54, steps 100-199 1.24, last 100 steps 1.36   |   optimal arm chosen in the last 100 steps: 80%

Before reading them you need two reference points, computed with the same procedure: what a perfect agent would get and what one that chooses at random would get.

# Reference points: what would a perfect agent get? what does a random one get?
best = np.mean([Bandit(seed=p).true_value.max() for p in range(2000)])
average_arm = np.mean([Bandit(seed=p).true_value.mean() for p in range(2000)])
print(f"oracle (always the best arm): {best:.2f}     random arm: {average_arm:.2f}")

# Output:
# oracle (always the best arm): 1.53     random arm: -0.00

An omniscient agent, which always pulls the best lever, would obtain 1.53 per pull on average; one that chooses at random about 0 (the minus sign in the output is the rounding of a tiny value). Now let us read the three results.

• ε = 0 (pure exploitation). In the first 10 steps it is level with the others (0.59), but it stalls at about 1.02 and improves no more: in the last 100 steps it chooses the best lever in only 36% of cases. At the start all estimates are 0; the first lever that gives a positive reward becomes the favourite and the agent keeps pulling it, never checking the others. If it has not found the best one in the first attempts, it never will.
• ε = 0.1 (10% exploration). It starts more slowly (0.54 in the first 10 steps: it is wasting pulls on exploring), but then climbs higher: 1.24 between steps 100-199 and 1.36 at the end, with the optimal lever chosen in 80% of cases. We are close to the maximum of 1.53, and the residual 10% of exploration is part of the reason it does not reach it.
• ε = 0.01. A compromise: it explores too little to find the right lever quickly (1.08 in steps 100-199) but in the end reaches 1.30 and 59%. It needs more time to discover the best lever.

The three entries must be read as a compromise over time, not as a ranking. High exploration costs at the start (you give up rewards) but pays off later (you find better ones); low exploration earns right away and gets stuck. With a long horizon exploration is worth more; with a horizon of only 10 pulls it does not pay: in the first 10 steps ε = 0 and ε = 0.01 even do better than ε = 0.1 (0.59 and 0.59 against 0.54). The figure the listing does not show is where ε = 0.01 would stop with more than 1000 pulls: the curve is still rising, and I did not extend it.

Strategies beyond ε-greedy

ε-greedy explores at random, even when a lever is already evidently poor. The alternatives correct exactly this. Optimistic initial values start with very high Q, and the agent tries every lever in order to be "disillusioned" (section 2.6 of the book). UCB (upper confidence bound) chooses the lever with the highest estimate plus a bonus for uncertainty, so rarely tried levers get a larger bonus (section 2.7). Gradient bandits learn a preference for each lever instead of a value (section 2.8), and Thompson sampling samples from a distribution over the value of each lever; the book discusses it in the chapter summary and in the bibliographical notes. I did not reproduce any of these strategies, so I do not say which one is better.

From the bandit to a real RL problem

The bandit has a limitation that makes it "too easy": today's choice does not change tomorrow's situation. Pulling lever 3 changes neither which levers exist nor how much they pay. In real problems actions change the state: moving a piece on the board changes the board, moving in a maze changes where you are. Then the reward of an action may arrive many steps later, and credit assignment becomes the central problem. To describe this situation you need the Markov decision process, the topic of The Markov Decision Process: The Language Every RL Problem Is Written In. Then comes the Bellman equation (derived in full), which lets you compute the value of a state, and the algorithms that learn it from experience: Q-Learning and, when the states are too many for a table, Deep Q-Learning. The risk of rewarding the wrong thing is tackled by Delayed Rewards, Reward Shaping and Reward Hacking.

The trade-offs to remember

The first trade-off is that exploring costs now and pays later: the value of exploration depends on the horizon, and the longer it is the more exploring pays. The second concerns ε: a fixed value always explores, even when it has already learned, while a decreasing one explores a lot at the start and little at steady state (we will use it in Q-learning). The third concerns the update step: 1/n converges to the true mean if the rewards are stationary, while a fixed step follows a changing world better but does not converge exactly, because it oscillates around the value.

Real pitfalls

1. Judging an agent from a single episode or a single problem. With noisy rewards an excellent result can be luck: here we averaged over 2000 problems.
2. Comparing the mean reward with zero instead of with the oracle. 1.36 says nothing without knowing that the maximum is 1.53 and chance is 0.
3. Not exploring enough. Pure greedy gets "stuck" (36% optimal choice) and gives no error: it seems to work.
4. Exploring forever. With ε = 0.1, 10% of the pulls are devoted to exploration even at steady state; in a real system the reduction of exploration has to be planned.
5. Forgetting that the reward is the only signal. What you reward is what you get: if the reward does not capture the real goal, the agent will optimise another goal.

The order of the five pitfalls is not a ranking, but the first three have one thing in common: they give a result that looks good without signalling any error. A greedy agent that stays at 36% raises no exceptions, and a comparison with zero makes any positive number look brilliant. The last two concern design instead: how much to explore and what to reward are your choices, and no algorithm makes them for you.

A worked example by hand: five pulls of a three-armed bandit

Let us follow the ε-greedy algorithm with ε = 0.1 on three levers, starting from Q = [0, 0, 0] and N = [0, 0, 0]. I chose the rewards below for the demonstration (a case, not an experimental result); I rechecked the arithmetic of the five updates with a short script that applies the incremental formula.

pull 1: exploit; all Q are 0 → tie, lever 0 is chosen.  Reward 1.2
        N0 = 1,  Q0 = 0 + (1.2 − 0)/1            = 1.2
pull 2: exploit; the maximum Q is lever 0 (1.2).        Reward 0.4
        N0 = 2,  Q0 = 1.2 + (0.4 − 1.2)/2        = 0.8
pull 3: EXPLORE (random draw): lever 2.                 Reward 2.0
        N2 = 1,  Q2 = 0 + (2.0 − 0)/1            = 2.0
pull 4: exploit; the maximum Q is lever 2 (2.0).        Reward 1.0
        N2 = 2,  Q2 = 2.0 + (1.0 − 2.0)/2        = 1.5
pull 5: exploit; lever 2 (1.5).                         Reward 1.8
        N2 = 3,  Q2 = 1.5 + (1.8 − 1.5)/3        = 1.6

final state:  Q = [0.8, 0, 1.6],  N = [2, 0, 3]

Three observations. First, the estimates are corrected at every pull: after the second pull lever 0 is worth 0.8 and no longer 1.2. Second, lever 1 has never been tried: its Q = 0 is only the initial value, not an estimate. If the agent were pure greedy and the other levers had positive rewards, it would never try it: this is exactly the stall of the ε = 0 case. Third, the exploratory choice at pull 3 was lucky and found the best lever among those seen: that is the value of exploration.

Exercises with solutions

Before moving on, try to solve these exercises with pen and paper; the solution is right below each one.

1. A lever has given 2, 4, 3, 7. Compute Q with the incremental update.
   Solution: after 2: 2. After 4: 2 + (4 − 2)/2 = 3. After 3: 3 + (3 − 3)/3 = 3. After 7: 3 + (7 − 3)/4 = 4, that is the mean.
2. With ε = 0.2 and 5 levers, if the agent knows the best lever, with what probability does it choose it?
   Solution: 0.8 + 0.2/5 = 0.84: the 20% of exploration chooses at random among 5 levers, and in 1 case out of 5 it lands on the best one.
3. With ε = 0.1 and 10 levers, what is the maximum fraction of choices that can be optimal, even once the problem is solved?
   Solution: 0.9 + 0.1/10 = 0.91. The 80% measured in the experiment is below this ceiling, but the agent has not yet identified the best lever in all 2000 problems.
4. Why can an agent with ε = 0 stay stuck?
   Solution: it always chooses the lever with the highest Q; if the first one with a positive reward is not the best, it never checks the others.
5. If the rewards change over time, what do you change in the update?
   Solution: you replace 1/n with a constant step α: recent rewards weigh more and the estimates "forget" the past.

The first two exercises are arithmetic to do by hand and can be rechecked with one line of Python (the solutions above were recomputed that way). The last three are interpretation questions: if you can answer without rereading the text you have understood the substance, namely that exploration is a cost paid to obtain information, and that this cost has a computable ceiling.

Frequently asked questions

What is "regret"?

The difference between the reward you would have obtained by always using the best lever and the one actually obtained. In our experiment the maximum is 1.53 per pull: an agent at 1.36 has an average regret of about 0.17 per pull over the last 100 steps. Measuring cumulative regret is a usual way of comparing bandit algorithms.

Why not try each lever 100 times and then exploit?

It is the "explore first, then exploit" strategy. It works, but it wastes pulls on the evidently bad levers. ε-greedy spreads exploration over time; strategies such as UCB concentrate it on the uncertain levers.

What changes if the rewards vary over time?

You use a constant step α instead of 1/n, so that the estimates forget the past; the choice of α balances responsiveness and noise, as you will see in Q-Learning.

How does a bandit differ from an A/B test?

An A/B test assigns participants to fixed groups and decides at the end; a bandit gradually shifts traffic towards the best option during the experiment. The trade-off is between the speed of the gain and the statistical reliability of the conclusion.

Is ε = 0.1 fine for everything?

No: it is a typical value, not a rule. It depends on the horizon (the longer it is, the more exploration pays) and on the cost of being wrong; often ε decreases over time.

What you can do now

You can describe an RL problem with agent, environment, state, action, reward and return, and say why it is not supervised learning. You can derive the incremental mean Q ← Q + step·(target − Q), the form that returns in every later algorithm. And you have a reproducible experiment: in the 10-armed bandit, over 2000 problems, ε = 0 stalls at 36% optimal choices (reward 1.02), ε = 0.01 reaches 59% (1.30) and ε = 0.1 reaches 80% (1.36), against a maximum of 1.53. When actions change the situation you need the formalism of The Markov Decision Process, the next step of the series. If you want the picture on the risk of judging a model from a single trial, reread the process of an ML project.

In the series, the previous lesson is VAE: The Beta Weight, Posterior Collapse and Training Instabilities.