Reinforcement Learning: Learning by Trial and Error

Learning from rewards

Supervised learning needs the right answer for every example. Reinforcement learning (RL) needs only a score. An agent acts in an environment, sees what happens, and receives a reward, and over many attempts it learns which actions lead to the most reward.

Nobody tells the agent which action was right. It has to work out which of its earlier actions deserve the credit for a reward that may arrive much later, the credit assignment problem.

Returns and discounting

The agent's aim is to maximise its return: the total reward from now on. Rewards further in the future are usually discounted by a factor γ (gamma) between 0 and 1 for every step of delay:

With γ = 0.9, a reward of 10 that arrives four steps from now is worth 10 × 0.9³ = 7.29 today. Discounting makes sooner rewards worth more, reflects that the future is uncertain, and keeps the sum finite in tasks that never end. A γ near 0 makes a short-sighted agent; a γ near 1, a patient one.

Policies and values

A policy says what to do in each state. To find a good one, RL estimates how good each state is:

• The value of a state, V(s), is the return the agent can expect from there, if it then acts well.
• The action value, Q(s, a), is the return it can expect if it takes action a in state s first.

Once the values are known, a good policy is simply: in every state, take the action that leads to the highest value.

In this grid world, reaching G pays +10, falling into X costs −10, and every other step costs 0.1, so the agent prefers short routes. Values are highest next to the goal and fall away with distance, and the arrows, which simply point uphill in value, steer clear of the trap.

The Bellman equation

In 1957 Richard Bellman noticed that a state's value can be written in terms of its neighbours' values:

That turns finding values into a repeated sum. Value iteration starts with every value at 0 and applies the equation to every state, again and again, until the values stop changing. Information about the reward spreads backwards one step per sweep.

In a corridor with a reward of 10 for stepping onto the goal and γ = 0.9, the cells before the goal settle at 10, 9, 8.1, 7.29 and 6.56: each is 0.9 times the next one.

Q-learning: learning without the rules

Value iteration needs to know where every move leads. Usually an agent does not: it only experiences one move at a time. Q-learning (1989) learns Q-values from experience alone. After each move from state s with action a, landing in s′ with reward r:

The bracket is the temporal difference error: how much better or worse the move turned out than expected. The learning rate α decides how far each surprise moves the estimate.

A worked step, with α = 0.5 and γ = 0.9: Q(s, right) is 2.0, the move earns r = −1, and the best Q in the new state is 6.0. The target is −1 + 0.9 × 6.0 = 4.4, the error is 4.4 − 2.0 = 2.4, and the new estimate is 2.0 + 0.5 × 2.4 = 3.2.

Try it: build a maze, train an agent, and watch the values spread out from the goal.

Explore or exploit?

An agent that always takes the action that looks best so far may never discover a better one. One that always experiments never cashes in on what it knows. This is the exploration–exploitation trade-off.

The simplest answer is ε-greedy: with probability ε (say 0.1) take a random action, otherwise take the best-looking one. Often ε starts high and shrinks as the agent learns.

The classic test is the multi-armed bandit: a row of slot machines with hidden payout rates. Pull too few times and you misjudge a good machine; pull a bad one too often and you waste money. Smarter rules such as UCB (upper confidence bound) add a bonus to machines that have been tried less, so uncertainty itself attracts exploration.

Deep reinforcement learning

A Q-table needs one entry for every state and action. A video game screen has more possible states than there are atoms in the universe, so a table is hopeless. Deep RL replaces the table with a neural network that estimates Q from the raw input.

DQN needed two tricks to train stably: experience replay, which stores past moves and learns from random batches of them, and a slowly updated target network. Other methods learn the policy directly: policy gradient methods nudge the probability of actions that led to high returns, and PPO (2017) is the version used to train robots and to fine-tune language models.

When rewards go wrong

An RL agent optimises exactly the reward it is given, not what its designer meant. In 2016, OpenAI trained an agent on the boat racing game CoastRunners, rewarding points. The agent found a lagoon where three targets kept reappearing and circled there forever, catching fire and crashing into other boats, scoring more than human players without ever finishing the race.

This is reward hacking, or specification gaming. It is funny in a game and serious in the real world: a recommendation system rewarded for watch time may learn to promote outrage. Designing rewards that capture what we really want is part of the alignment problem in Level 15.

Hands-on: reinforcement learning from scratch

Value iteration on a grid world

ROWS = ["....G",
        ".#.#X",
        ".....",
        "S#..."]
GAMMA = 0.9
REWARD = {"G": 10, "X": -10}
MOVES = {"^": (-1, 0), "v": (1, 0), "<": (0, -1), ">": (0, 1)}
cells = [(r, c) for r in range(len(ROWS)) for c in range(len(ROWS[0])) if ROWS[r][c] != "#"]

def step(r, c, move):
    dr, dc = MOVES[move]
    nr, nc = r + dr, c + dc
    if 0 <= nr < len(ROWS) and 0 <= nc < len(ROWS[0]) and ROWS[nr][nc] != "#":
        return nr, nc
    return r, c                                  # bumping into a wall: stay put

def score(r, c, m):
    nr, nc = step(r, c, m)
    return REWARD.get(ROWS[nr][nc], -0.1) + GAMMA * V[(nr, nc)]     # a small cost for every step

V = {cell: 0.0 for cell in cells}
for sweep in range(1, 30):
    new = {}
    for (r, c) in cells:
        if ROWS[r][c] in REWARD:                 # the episode ends on G or X
            new[(r, c)] = 0.0
        else:
            new[(r, c)] = max(score(r, c, m) for m in MOVES)
    change = max(abs(new[k] - V[k]) for k in V)
    V = new
    if change < 0.001:
        break

print("values after", sweep, "sweeps:")
for r in range(len(ROWS)):
    print(" ".join("  ###" if ROWS[r][c] == "#" else f"{ROWS[r][c]:>5}" if ROWS[r][c] in REWARD
                   else f"{V[(r, c)]:5.1f}" for c in range(len(ROWS[0]))))
print("best move in each cell:")
for r in range(len(ROWS)):
    print(" ".join(ROWS[r][c] if ROWS[r][c] in "#GX" else max(MOVES, key=lambda m: score(r, c, m))
                   for c in range(len(ROWS[0]))))

Q-learning in a corridor

The agent starts at the left of six cells and does not know where the treasure is. Every step costs 1; the treasure is worth 10.

import random

random.seed(4)
N, GOAL = 6, 5                      # actions: 0 = left, 1 = right
Q = [[0.0, 0.0] for _ in range(N)]
alpha, gamma, epsilon = 0.5, 0.9, 0.2

for episode in range(1, 201):
    s, steps = 0, 0
    while s != GOAL and steps < 100:
        if random.random() < epsilon:
            a = random.randrange(2)                       # explore
        else:
            a = 0 if Q[s][0] > Q[s][1] else 1             # exploit (ties go right)
        s2 = max(0, s - 1) if a == 0 else min(N - 1, s + 1)
        r = 10 if s2 == GOAL else -1
        target = r + (0 if s2 == GOAL else gamma * max(Q[s2]))
        Q[s][a] += alpha * (target - Q[s][a])             # the Q-learning update
        s, steps = s2, steps + 1
    if episode in (1, 2, 5, 20, 200):
        print(f"episode {episode:3}: took {steps:2} steps; Q(start, right) = {Q[0][1]:6.2f}")

print("learned policy:", " ".join("<" if q[0] > q[1] else ">" for q in Q[:GOAL]), "G")

Q(start, right) settles at 3.12, exactly −1 + 0.9 × (−1 + 0.9 × (−1 + 0.9 × (−1 + 0.9 × 10))): four steps that cost 1, then the treasure.

A five-armed bandit

import random

random.seed(1)
true_payout = [0.2, 0.5, 0.35, 0.8, 0.1]       # chance each slot machine pays out (hidden)
estimates = [0.0] * 5
pulls = [0] * 5
total = 0
epsilon = 0.1
for t in range(1000):
    if random.random() < epsilon:
        arm = random.randrange(5)                                  # explore
    else:
        arm = max(range(5), key=lambda a: estimates[a])            # exploit
    reward = 1 if random.random() < true_payout[arm] else 0
    pulls[arm] += 1
    estimates[arm] += (reward - estimates[arm]) / pulls[arm]       # running average
    total += reward
for a in range(5):
    print(f"machine {a}: true {true_payout[a]:.2f}  estimate {estimates[a]:.2f}  pulled {pulls[a]:4} times")
print("total reward", total, "out of 1000 pulls; always picking the best would expect", round(1000 * max(true_payout)))

Try this

1. In the grid world, change the step cost from −0.1 to −2. Does the policy ever choose to jump into X to end the pain sooner?
2. In the corridor, set epsilon to 0. Does the agent still find the treasure? Why does the tie-breaking rule matter?
3. In the bandit, try epsilon = 0.01 and epsilon = 0.3. Which earns more, and why?

Level check

• Describe the agent–environment loop: state, action, reward, episode and policy
• Calculate a discounted return, and explain what γ does
• Explain state values and action values, and how a policy follows from them
• Apply the Bellman equation, and describe value iteration
• Carry out a Q-learning update by hand
• Explain the exploration–exploitation trade-off and ε-greedy
• Explain why deep RL uses neural networks, and name its milestones
• Explain reward hacking with an example

Key terms you must be able to define

Reinforcement learning

Learning which actions to take from rewards, by trial and error.

Agent

The learner that observes states and chooses actions.

Environment

Everything the agent interacts with, which responds to its actions with new states and rewards.

Reward

A number the environment gives after an action, saying how good the outcome was.

Policy

The agent's rule for choosing an action in each state.

Return

The total of the future rewards, usually discounted.

Discount factor (γ)

A number between 0 and 1 that makes later rewards count for less.

Value

The return an agent can expect from a state, or from taking an action in a state (a Q-value).

Bellman equation

A state's value equals the best immediate reward plus the discounted value of where it leads.

Q-learning

Learning action values from experience by nudging each towards reward + γ × the best next Q-value.

Exploration

Trying actions that do not currently look best, to learn more about them.

ε-greedy

Acting randomly with probability ε, and otherwise taking the best-looking action.

Reward hacking

An agent maximising its reward in a way its designers did not intend.

Flashcards

Go further: notes for future AI engineers

On-policy and off-policy

Q-learning is off-policy: its update uses the best next action, whatever the agent actually does next, so it learns the value of acting well even while it explores. SARSA, its close cousin, uses the action the agent really takes next, so it learns the value of its own exploring policy. Near a cliff, SARSA learns to keep a safe distance, because it knows it will sometimes stumble; Q-learning learns the shortest route along the edge.

Model-based RL

Q-learning is model-free: it never learns how the world works, only how good actions are. Model-based methods also learn a model that predicts the next state and reward, and then plan inside that model, which can need far less real experience. MuZero (2019) learned its own model of each game and planned with it, mastering Atari, chess and Go without being told their rules.

Misconceptions to avoid