COMP5318 — Applied Machine Learning
Week 12: Reinforcement Learning
Reinforcement learning (RL) studies how an agent should act inside an environment to maximise cumulative reward. Unlike supervised learning there are no labelled (input, output) pairs — only a scalar reward signal and a sequence of decisions. This week formalises the agent-environment loop as a Markov decision process, derives value and Q-value functions through the Bellman equation, builds tabular Q-Learning, and scales it up to Deep Q-Networks for Atari-scale problems.
Course materials
Read the slides with an Atari or grid-world example in mind. The agent-environment diagram is the single most important figure of the week; everything else (return, value, Bellman equation, Q-Learning update, DQN loss) is one step of formalisation away from it.
| File | What you should learn from it |
|---|---|
| ml12.pdf | Why RL differs from supervised learning; the agent-environment loop with state, action, reward; the Markov decision process tuple \(\langle S, A, P, R, \gamma \rangle\); policy \(\pi\) and discounted return \(G_t\); state-value \(V^\pi(s)\) and action-value \(Q^\pi(s,a)\); the Bellman equation for \(Q^*\); tabular Q-Learning update with \(\epsilon\)-greedy exploration; Deep Q-Networks (DQN) with experience replay and a target network; applications to Atari, robotics, and AlphaGo / AlphaZero. |
From supervised to reinforcement learning: the MDP
In supervised learning a teacher gives the right answer for every input. Many problems (riding a bike, playing a game, controlling a robot) instead require a sequence of decisions with no explicit per-step label — only a scalar reward telling you how well things turned out. RL formalises this as a Markov decision process (MDP).
At each step \(t\), the agent observes state \(s_t\), picks an action \(a_t\), and the environment responds with the next state \(s_{t+1}\) and a scalar reward \(r_{t+1}\). The cycle repeats. The agent's goal is to choose actions that maximise long-run cumulative reward.
The MDP tuple
An MDP is \(\langle S, A, P, R, \gamma \rangle\): a set of states \(S\), a set of actions \(A\), a transition kernel \(P(s' \mid s, a)\), a reward function \(R(s, a, s')\), and a discount factor \(\gamma \in [0, 1]\). The transitions are Markovian: the future depends only on the current state and action, not the full history.
Policy & return
A policy \(\pi(a \mid s)\) maps states to a distribution over actions — the agent's behaviour. The discounted return from time \(t\) is \(G_t = \sum_{k=0}^\infty \gamma^k r_{t+k+1}\). The discount factor \(\gamma < 1\) makes far-future rewards count less and keeps infinite sums finite.
Reward hypothesis
All goals can be described as the maximisation of expected cumulative reward. A reward \(r_t\) is a single scalar — designing it well is the engineer's responsibility.
Examples of reward
Atari: +1 for score increase, −1 for score decrease. Robot walking: positive for forward motion, negative for falling. Grid world: −1 per step until a terminal cell is reached.
Optimal policy \(\pi^*\)
\(\pi^* = \arg\max_\pi \mathbb{E}_\pi[G_0]\). Because the environment is stochastic we maximise the expected sum of rewards, not a single realisation.
Value functions and the Bellman equation
Two functions tell us how good things are under a fixed policy \(\pi\): the state value \(V^\pi(s)\) and the action value \(Q^\pi(s,a)\). They obey recursive Bellman equations that decompose long-horizon rewards into a one-step reward plus the value of what follows.
\(V^\pi(s) = \mathbb{E}_\pi[\, G_t \mid s_t = s\,]\) — the expected return when the agent starts in state \(s\) and then follows policy \(\pi\). Larger \(V\) means a more promising state.
\(Q^\pi(s, a) = \mathbb{E}_\pi[\, G_t \mid s_t = s,\, a_t = a\,]\) — the expected return when we commit to action \(a\) in state \(s\), then follow \(\pi\) thereafter. \(Q\) ranks state-action pairs and is the quantity Q-Learning estimates.
Bellman optimality (Q)
\(Q^*(s, a) = \mathbb{E}_{s'}\!\left[\, R(s,a,s') + \gamma\, \max_{a'} Q^*(s', a')\,\right]\). The optimal Q is the immediate reward plus the discounted value of the best next action.
Greedy optimal policy
Once \(Q^*\) is known, the optimal policy is simply \(\pi^*(s) = \arg\max_a Q^*(s, a)\). Solving RL is equivalent to estimating \(Q^*\).
Q-Learning: tabular off-policy TD control
Q-Learning estimates \(Q^*\) without ever knowing the transition kernel \(P\). It stores one number \(Q(s,a)\) per (state, action) pair in a table, samples transitions by acting in the environment, and nudges each \(Q(s,a)\) toward the Bellman target one step at a time.
After observing transition \((s, a, r, s')\): \[ Q(s, a) \;\leftarrow\; Q(s, a) + \alpha\Bigl[\,r + \gamma \max_{a'} Q(s', a') - Q(s, a)\,\Bigr] \] with learning rate \(\alpha \in (0, 1]\). The bracketed quantity is the TD error — target minus current estimate.
1. Initialise
Set \(Q(s, a) = 0\) (or arbitrarily) for every state-action pair, e.g. one row per action and one column per state in a grid world.
2. Act & observe
From state \(s\) pick action \(a\); the environment returns reward \(r\) and next state \(s'\). Use the update above to revise \(Q(s, a)\) toward the bootstrapped target.
3. Off-policy
The update uses \(\max_{a'} Q(s', a')\) — the value of the greedy action at \(s'\) — even when the agent itself explored a different action. This is what makes Q-Learning off-policy.
4. \(\epsilon\)-greedy
With probability \(1-\epsilon\) take the greedy action \(\arg\max_a Q(s,a)\); with probability \(\epsilon\) pick a random action. Anneal \(\epsilon\) so exploration decreases as estimates improve.
Deep Q-Networks: scaling Q-Learning to pixels
In an Atari game the state is a stack of raw frames — the table would have \(256^{210 \times 160}\) entries and is hopeless. Deep Q-Networks (DQN) replace the table with a neural network \(Q_\theta(s, a)\) that takes a state as input and outputs Q-values for every action. Training is still driven by the Bellman target, but with two crucial tricks.
\[ L(\theta) \;=\; \mathbb{E}_{(s,a,r,s')}\!\left[\bigl(\,r + \gamma \max_{a'} Q_{\bar\theta}(s', a') - Q_\theta(s, a)\,\bigr)^2\right] \] Minimise by SGD with respect to \(\theta\); the target uses frozen parameters \(\bar\theta\).
Experience replay
Store transitions \((s, a, r, s')\) in a large buffer and sample random minibatches for SGD updates. This breaks the strong temporal correlations of consecutive samples and reuses each experience many times — much more sample-efficient than learning purely online.
Target network
Keep a second copy of the network \(Q_{\bar\theta}\) whose parameters are held fixed and only periodically copied from \(Q_\theta\). The Bellman target uses \(Q_{\bar\theta}\) so it does not move every step — without this the target chases the prediction and training diverges.
End-to-end from pixels
The DQN for Atari takes a stack of 4 raw frames, passes them through convolutional layers, and outputs one Q-value per action. No hand-crafted features.
Double DQN
The plain \(\max\) over-estimates Q-values. Double DQN selects the next action with the online network but evaluates it with the target network, reducing this upward bias.
Prioritised replay
Sample transitions with probability proportional to their TD error so that the most surprising experiences are revisited more often.
Study questions to answer before moving on
An agent receives rewards \(r_1 = 0, r_2 = 0, r_3 = 1\) and then the episode ends. With discount factor \(\gamma = 0.9\), what is the return \(G_0 = r_1 + \gamma r_2 + \gamma^2 r_3\)?
\(G_0 = 0 + 0.9 \cdot 0 + 0.81 \cdot 1 = 0.81\). The single delayed reward is worth less now because of the two-step discount.
If \(\gamma = 1\) the return would be 1; if \(\gamma = 0\) it would be 0 — the agent would become myopic.
Suppose \(Q(s, a) = 2.0\), the agent takes action \(a\), receives reward \(r = 1\), and lands in \(s'\) where \(\max_{a'} Q(s', a') = 5.0\). With \(\alpha = 0.5\) and \(\gamma = 0.9\), what is the updated \(Q(s, a)\)?
Target \(= r + \gamma \max_{a'} Q(s', a') = 1 + 0.9 \cdot 5 = 5.5\). TD error \(= 5.5 - 2.0 = 3.5\). New \(Q(s, a) = 2.0 + 0.5 \cdot 3.5 = 3.75\).
Explain why DQN trains badly if the same network \(Q_\theta\) is used to compute both the prediction and the Bellman target, and what the target network does to fix it.
If the target uses the same \(\theta\) that we are updating, each gradient step shifts both prediction and target in the same direction — the target becomes a moving goalpost and SGD can oscillate or diverge. Freezing a second copy \(Q_{\bar\theta}\) keeps the target stationary for many steps; only periodically do we set \(\bar\theta \leftarrow \theta\). Combined with experience replay this is what made Atari-scale DQN learnable.
Chapter quizzes
Self-test and math questions for this week are in the Quiz Hub (practice or exam mode).