Reinforcement learning

Advanced

Introduction

Value iteration needs the MDP's transition probabilities and rewards. Often nobody knows them: how a game opponent will respond, how a robot's joints behave, which advert a customer will click. Reinforcement learning (RL) learns good behaviour directly from experience: the agent acts, receives rewards, and gradually learns which actions pay off. It is how programs learned to play Atari games and Go, and how robots learn to walk in simulation.

How it works

The agent's aim is a large return: the sum of rewards, discounted by γ for each step into the future. For rewards r₁, r₂, r₃ the return from the start is r₁ + γ r₂ + γ² r₃; it can be computed backwards, Gₜ = rₜ₊₁ + γ Gₜ₊₁.

Temporal-difference learning estimates state values while acting. After moving from s to s′ with reward r, it nudges V(s) towards the target r + γ V(s′):

V(s) ← V(s) + α (r + γ V(s′) − V(s))

The bracket is the TD error: how much better or worse things went than expected. α, the learning rate, controls the size of the step.

Q-learning learns action values Q(s, a) in the same way, using the best action in the next state as the target:

Q(s, a) ← Q(s, a) + α (r + γ maxₐ′ Q(s′, a′) − Q(s, a))

At a terminal state the target is just r. Q-learning is off-policy: it learns the values of acting optimally even while it sometimes acts randomly. Once Q is learned, the policy is simply the action with the largest Q in each state.

The agent must explore to discover rewards and exploit what it has learned to collect them. ε-greedy does both: with probability ε it picks a random action, otherwise the best one so far. Many agents reduce ε over time.

Syntax

a = random.choice(actions) if random.random() < epsilon else best_action(s)
s2, r = environment.step(s, a)
target = r if terminal(s2) else r + gamma * max(Q[(s2, b)] for b in actions)
Q[(s, a)] += alpha * (target - Q[(s, a)])

Example

import random

random.seed(7)
CELLS, GOAL = 6, 5
ACTIONS = ["left", "right"]
ALPHA, GAMMA, EPSILON = 0.5, 0.9, 0.2
Q = {(s, a): 0.0 for s in range(CELLS) for a in ACTIONS}


def best_action(s):
    return max(ACTIONS, key=lambda a: Q[(s, a)])


steps_per_episode = []
for episode in range(1, 51):
    s, steps = 0, 0
    while s != GOAL:
        a = random.choice(ACTIONS) if random.random() < EPSILON else best_action(s)
        s2 = min(s + 1, GOAL) if a == "right" else max(s - 1, 0)
        reward = 10 if s2 == GOAL else -1
        target = reward if s2 == GOAL else reward + GAMMA * max(Q[(s2, b)] for b in ACTIONS)
        Q[(s, a)] += ALPHA * (target - Q[(s, a)])
        s, steps = s2, steps + 1
    steps_per_episode.append(steps)

print("steps in episodes 1 to 5:", steps_per_episode[:5])
print("steps in episodes 46 to 50:", steps_per_episode[-5:])
for s in range(GOAL):
    print(f"cell {s}: left {Q[(s, 'left')]:6.2f}  right {Q[(s, 'right')]:6.2f}  -> {best_action(s)}")
Open in compiler

Line by line

  1. The world is a corridor of six cells; reaching the right end earns 10, and every other step costs 1.
  2. All Q-values start at 0, and ties go to "left", so at first the agent wanders.
  3. Each step chooses an action ε-greedily, observes the result and moves Q(s, a) halfway towards the target.
  4. The first episodes take many steps; by the last episodes the agent walks almost straight to the goal.
  5. The learned values grow towards the goal, and "right" has become the best action in every cell.

Expected result

steps in episodes 1 to 5: [24, 13, 6, 7, 6]
steps in episodes 46 to 50: [5, 7, 5, 5, 8]
cell 0: left   1.77  right   3.12  -> right
cell 1: left   1.78  right   4.58  -> right
cell 2: left   2.97  right   6.20  -> right
cell 3: left   4.38  right   8.00  -> right
cell 4: left   5.98  right  10.00  -> right

In the real world

DeepMind's DQN combined Q-learning with a neural network to play dozens of Atari games from pixels. AlphaGo and AlphaZero used reinforcement learning through self-play. Large language models are tuned with reinforcement learning from human feedback, and RL controls data-centre cooling and robot hands in simulation. Its weakness is data hunger: learning often needs millions of trials, which is why simulators matter.

Common mistakes

  • Never exploring, so the agent settles on the first action that seemed fine.
  • Using the next state's value at a terminal state, which should be 0.
  • A learning rate that is too large, so estimates jump around, or too small, so learning crawls.
  • Forgetting the discount, which in long or endless tasks makes values grow without bound.

Best practices

  • Plot or print the steps per episode; falling numbers show learning is working.
  • Fix the random seed while debugging, so runs can be repeated.
  • Start with a small, fully understood environment before scaling up.

Summary

Reinforcement learning learns from rewards without a model. The return adds discounted future rewards; TD learning moves value estimates towards the reward plus the next estimate; Q-learning does the same for action values with the best next action as the target. ε-greedy exploration makes sure better actions are found.

Quick check

1. What is the return for rewards 1, 2, 3 with γ = 0.5?
2. What does the TD error measure?
3. Why is Q-learning called off-policy?
4. Why does an agent need exploration?

Key takeaways

  • Reinforcement learning needs no model of the world, only experience of states, actions and rewards.
  • TD and Q-learning update after every step, using their own estimates of the next state.
  • Without exploration an agent may never discover better actions.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.