COMP5318 — Week 12 Supplement
Mathematical Foundations
The MDP tuple, discounted return, Bellman optimality equations, the tabular Q-Learning update, and the squared-TD-error DQN loss with a frozen target network.
Markov decision process and return
An MDP formalises sequential decision making. At every step the agent picks an action, the environment emits a reward and a next state, and we want to maximise the expected discounted sum of rewards.
MDP tuple
\[ \mathcal{M} \;=\; \langle\, S,\; A,\; P,\; R,\; \gamma\,\rangle \]
\(S\) states, \(A\) actions, transition kernel \(P(s' \mid s, a)\), reward \(R(s, a, s')\), discount \(\gamma \in [0, 1]\). The Markov property says \(P(s_{t+1} \mid s_t, a_t) = P(s_{t+1} \mid H_t, a_t)\) — the past beyond \(s_t\) is irrelevant.
Discounted return
\[ G_t \;=\; \sum_{k=0}^{\infty} \gamma^k\, r_{t+k+1} \;=\; r_{t+1} + \gamma\, r_{t+2} + \gamma^2\, r_{t+3} + \cdots \]
With \(\gamma < 1\) the sum converges for bounded rewards. The agent's objective is \(\pi^* = \arg\max_\pi \mathbb{E}_\pi[G_0]\).
Bellman optimality equations
Value functions decompose into a one-step reward plus the discounted value of the successor. For the optimal value the recursion picks the best action.
State-value and action-value (under policy \(\pi\))
\[ V^\pi(s) = \mathbb{E}_\pi[\, G_t \mid s_t = s\,], \qquad Q^\pi(s, a) = \mathbb{E}_\pi[\, G_t \mid s_t = s,\, a_t = a\,] \]
Bellman optimality for \(Q^*\)
\[ Q^*(s, a) \;=\; \mathbb{E}_{s' \sim P(\cdot \mid s, a)}\!\Bigl[\, R(s, a, s') + \gamma\, \max_{a'} Q^*(s', a')\,\Bigr] \]
The corresponding optimal policy is greedy: \(\pi^*(s) = \arg\max_a Q^*(s, a)\).
Bellman optimality for \(V^*\)
\[ V^*(s) \;=\; \max_a\, \mathbb{E}_{s'}\!\Bigl[\, R(s, a, s') + \gamma\, V^*(s')\,\Bigr] \]
Tabular Q-Learning update
Q-Learning solves the Bellman optimality equation by sampling. It needs no knowledge of \(P\) — only experience tuples \((s, a, r, s')\) collected by acting.
Update rule
\[ Q(s, a) \;\leftarrow\; Q(s, a) + \alpha\,\underbrace{\Bigl[\, r + \gamma\, \max_{a'} Q(s', a') - Q(s, a)\,\Bigr]}_{\text{TD error}\;\delta} \]
\(\alpha \in (0, 1]\) is the learning rate. Behaviour is typically \(\epsilon\)-greedy: with probability \(1-\epsilon\) act greedily and with probability \(\epsilon\) act uniformly at random.
The target \(r + \gamma \max_{a'} Q(s', a')\) evaluates the greedy policy at \(s'\), even though the behaviour policy collecting data is \(\epsilon\)-greedy. That separation is what makes Q-Learning off-policy — and why convergence holds under appropriate \(\alpha\) schedules as long as every \((s,a)\) is visited infinitely often.
Worked Example: one Q-Learning update on a 1×3 grid
A tiny world has three cells: start (\(s_1\)) — middle (\(s_2\)) — goal (\(s_3\)). Actions are Right (R) and Left (L). Stepping right from \(s_2\) to \(s_3\) gives reward \(r = +1\); any other transition gives \(r = 0\). Take \(\alpha = 0.5\), \(\gamma = 0.9\).
Before the step
Initialise all Q-values to zero. Suppose after some earlier exploration we already have \(Q(s_3, R) = 1.5\), \(Q(s_3, L) = 0.7\), and \(Q(s_2, R) = 0.4\). The agent is now in \(s_2\) and takes action R.
Compute the TD target
It receives reward \(r = 1\) and transitions to \(s_3\). The greedy next-state value is \(\max_{a'} Q(s_3, a') = \max(1.5, 0.7) = 1.5\). So the target is \(1 + 0.9 \cdot 1.5 = 2.35\).
Deep Q-Network loss
When \(|S|\) is too large for a table, parametrise \(Q\) with a neural network \(Q_\theta(s, a)\). Train by minimising the squared TD error using a frozen target network \(Q_{\bar\theta}\) and sampling transitions from a replay buffer \(\mathcal{D}\).
DQN loss
\[ L(\theta) \;=\; \mathbb{E}_{(s, a, r, s') \sim \mathcal{D}}\!\left[\,\Bigl(\, r + \gamma\, \max_{a'} Q_{\bar\theta}(s', a') \;-\; Q_\theta(s, a)\,\Bigr)^2\,\right] \]
Gradients are taken only through the predicted \(Q_\theta(s, a)\); the target uses frozen parameters \(\bar\theta\) that are periodically copied from \(\theta\). Without this freezing the target moves with each update and training diverges.
Experience replay stores past \((s, a, r, s')\) and samples uniform minibatches, breaking the strong temporal correlation of consecutive transitions. Target network keeps the bootstrapped target stationary for many gradient steps.