Skip to content
CampusPrep
AD-802 (B) · Reinforcement Learning/Quick Revision Short Notes

Reinforcement Learning (AD-802 (B)) - Unit 3 Short Notes

How unit 3 is examined

This unit covers Q-learning, TD learning, eligibility traces, function approximation, least squares, incremental and batch methods, and DQN; Q-learning (7 marks) and the maximum likelihood / least-squares hypothesis (7 marks) carry the marks.

Q-learning & Temporal Difference Methods

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. The Q-function $Q(s,a)$ is the expected return obtained by taking action $a$ in state $s$ and then following a policy; Q-learning is a model-free, off-policy temporal-difference algorithm that learns the optimal action-value function $Q^*$ directly from experience.

Formula. $$Q(s,a) \leftarrow Q(s,a) + \alpha\left[r + \gamma \max_{a'} Q(s',a') - Q(s,a)\right]$$

Key points.

  1. The bracket is the TD error: the gap between the target $r+\gamma\max_{a'}Q(s',a')$ and the current estimate $Q(s,a)$, and $\alpha$ scales how far the estimate moves.
  2. It is off-policy because the target uses the greedy maximum over next actions, whatever action the behaviour policy actually takes next.
  3. Actions are chosen epsilon-greedily: a random action with probability $\epsilon$, otherwise the greedy one, to balance exploration and exploitation.
  4. It is model-free, so no transition probabilities or reward model are needed; a table of $Q$ values is enough for small problems.
  5. It converges to $Q^*$ if every state-action pair is visited infinitely often and $\alpha$ decays suitably.

Steps.

Step 1: Initialise Q(s,a) arbitrarily (0), choose alpha, gamma, epsilon.
Step 2: Observe the current state s.
Step 3: Choose a from s by epsilon-greedy on Q.
Step 4: Take a; observe reward r and next state s'.
Step 5: Update Q(s,a) with the formula above.
Step 6: Set s = s'; repeat from Step 3 until s is terminal, then start a new episode.

Example. Given $Q(s,a)=0$, $\alpha=0.5$, $\gamma=0.9$, $r=10$, $\max_{a'}Q(s',a')=20$: new $Q=0+0.5\,(10+0.9\times20-0)=$ 14.0.

<mark>Q-learning learns the optimal action-value function directly, off-policy, by bootstrapping from the maximum Q-value of the next state.</mark>

Answer frame. Open with the definition of $Q(s,a)$ as expected return; write the update formula and name each symbol; give the algorithm steps with the epsilon-greedy choice; state the off-policy point (max in the target versus epsilon-greedy behaviour); close with the numeric example and convergence.

Pitfall: Do not call Q-learning on-policy; SARSA uses the action actually taken next, Q-learning uses the max.

Asked: [7 marks] (Jun 2025) Explain the Q-Function and Q-Learning Algorithm.

Temporal-Difference Learning

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. TD learning updates a value estimate from another estimate (bootstrapping) after every step, without waiting for the episode to end.

Formula. $V(s)\leftarrow V(s)+\alpha\,[r+\gamma V(s')-V(s)]$, where $\delta=r+\gamma V(s')-V(s)$ is the TD error.

Key points.

  1. It combines Monte Carlo's learning from raw experience with dynamic programming's bootstrapping.
  2. It needs no model of the environment, only sampled transitions.
  3. It updates online, step by step, and has lower variance than Monte Carlo but some bias.
  4. TD(0) uses one-step lookahead; SARSA and Q-learning are its control versions.

Eligibility Traces

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. An eligibility trace is a decaying short-term record of how recently and how often each state was visited, so one TD error updates all recently visited states; this gives TD($\lambda$).

Formula. $e(s)\leftarrow\gamma\lambda\,e(s)$ for all $s$, then $e(S_t)\leftarrow e(S_t)+1$; update $V(s)\leftarrow V(s)+\alpha\,\delta\,e(s)$ for all $s$.

Key points.

  1. $\lambda=0$ gives one-step TD; $\lambda=1$ approaches Monte Carlo.
  2. Traces spread credit backwards to earlier states in a single step, so learning is faster on long delayed-reward tasks.
  3. $\lambda$ trades bias (low $\lambda$) against variance (high $\lambda$).
  4. The backward view (traces) is equivalent to the forward-view $\lambda$-return.

Function Approximation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Function approximation represents $V(s)$ or $Q(s,a)$ by a parametric function $\hat v(s,\mathbf w)$ instead of a table, so learning generalises to unseen states.

Formula. Linear form: $\hat v(s,\mathbf w)=\mathbf w^\top\mathbf x(s)$; gradient update $\mathbf w\leftarrow\mathbf w+\alpha\,[\text{target}-\hat v(s,\mathbf w)]\,\nabla_{\mathbf w}\hat v(s,\mathbf w)$.

Key points.

  1. Tables fail for large or continuous state spaces because of memory and because unvisited states get no information.
  2. Hand-made features $\mathbf x(s)$ with a linear model, or a neural network, supply the function.
  3. Parameters are fitted by minimising the mean squared error between target and estimate.
  4. Bootstrapping, off-policy updates and approximation together (the deadly triad) can make learning diverge.

Least Squares Methods

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. The maximum likelihood (ML) hypothesis is the hypothesis that makes the observed training data most probable: $h_{ML}=\arg\max_{h\in H}P(D\mid h)$. The least square error hypothesis is the one that minimises the sum of squared errors $\sum_i (d_i-h(x_i))^2$.

Key points.

  1. Assume targets are $d_i=f(x_i)+e_i$, where the noise $e_i$ is independent and Gaussian with zero mean and variance $\sigma^2$.
  2. Then $P(D\mid h)=\prod_i \frac{1}{\sqrt{2\pi\sigma^2}}\exp\!\left(-\frac{(d_i-h(x_i))^2}{2\sigma^2}\right)$; taking the log and dropping constants gives $h_{ML}=\arg\min_h\sum_i (d_i-h(x_i))^2$.
  3. So under Gaussian noise the ML hypothesis is exactly the least-squares hypothesis.
  4. This justifies squared-error loss in linear regression, neural-network training and least-squares TD value fitting.
  5. With non-Gaussian noise the equivalence does not hold, and the MAP form adds a prior $P(h)$.

<mark>Under Gaussian noise, the maximum likelihood hypothesis is exactly the one that minimises the sum of squared errors.</mark>

Answer frame. Open by defining $h_{ML}$ and the least square error hypothesis; state the Gaussian-noise assumption; show the likelihood, log and drop-constants steps; conclude that they coincide and where it is used in learning models.

Asked: [7 marks] (Jun 2025) Discuss Maximum Likelihood and Least Square Error Hypothesis.

Incremental Methods and Batch Methods

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Incremental methods update the parameters after each sample by stochastic gradient descent; batch methods fit the parameters to a whole stored dataset of experience.

Point Incremental Batch
Update After every sample Over the whole dataset
Data use Each sample used once Data reused many times
Efficiency Sample-inefficient Sample-efficient
Cost Cheap per step More computation and memory
Example TD(0) with SGD Least-squares TD, experience replay

Key points.

  1. Incremental methods are simple and work online, but learning is noisy and slow.
  2. Batch methods find the least-squares fit to all experience, so they use data better.
  3. Experience replay is a middle path: incremental updates on random minibatches from a stored batch.

Deep Q-Learning analysis

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Deep Q-learning replaces the Q-table by a neural network $Q(s,a;\theta)$ trained to minimise the loss $L(\theta)=\big(r+\gamma\max_{a'}Q(s',a';\theta^-)-Q(s,a;\theta)\big)^2$.

Key points.

  1. Q-learning with a nonlinear approximator can be unstable or even diverge.
  2. Successive samples are strongly correlated, which breaks the independence that gradient descent assumes.
  3. The target moves whenever $\theta$ changes, so the network chases its own output.
  4. DQN counters these with experience replay and a separate target network with frozen weights $\theta^-$.

Deep Q-Networks and Experience Replay

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A Deep Q-Network is a neural network that takes a state and outputs $Q(s,a)$ for every action; experience replay stores transitions $(s,a,r,s')$ in a buffer and trains on random minibatches from it.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="DQN loop. Env is environment, Agt is agent, Buf is replay buffer, Net is Q-network trained on random minibatches."><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57.8,132.6 Q126,158 192.3,133.3" marker-end="url(#ah2)"/><path class="e" d="M194.2,119.4 Q126,94 59.7,118.7" marker-end="url(#ah2)"/><path class="e" d="M229,117.5 L365.2,49.4" marker-end="url(#ah2)"/><path class="e" d="M384,59 L384,191" marker-end="url(#ah2)"/><path class="e" d="M367,203.5 L230.8,135.4" marker-end="url(#ah2)"/><g class="wl"><rect x="102" y="136.5" width="47.1" height="18" rx="9"/><text class="t" x="125.5" y="145.5" dy=".35em" text-anchor="middle">state</text></g><g class="wl"><rect x="99.3" y="97.5" width="54.3" height="18" rx="9"/><text class="t" x="126.5" y="106.5" dy=".35em" text-anchor="middle">action</text></g><g class="wl"><rect x="274.5" y="74" width="47.1" height="18" rx="9"/><text class="t" x="298" y="83" dy=".35em" text-anchor="middle">store</text></g><g class="wl"><rect x="360.5" y="117" width="47.1" height="18" rx="9"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">batch</text></g><g class="wl"><rect x="288.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">Q</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Env</text><circle class="n" cx="212" cy="126" r="18"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">Agt</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">Buf</text><circle class="n" cx="384" cy="212" r="18"/><text class="t" x="384" y="212" dy=".35em" text-anchor="middle">Net</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">DQN loop. Env is environment, Agt is agent, Buf is replay buffer, Net is Q-network trained on random minibatches.</figcaption></figure>

Key points.

  1. Random sampling from the buffer breaks the correlation between consecutive samples.
  2. Each transition is reused many times, which improves data efficiency.
  3. A target network, a copy of $\theta$ refreshed every $C$ steps, gives stable regression targets.
  4. Actions are chosen epsilon-greedily, and the buffer has a fixed size, dropping the oldest transitions first.

Last-minute revision

  • $Q(s,a)$ is the expected return for taking action $a$ in state $s$ and then following the policy.
  • Q-learning update: $Q\leftarrow Q+\alpha[r+\gamma\max_{a'}Q(s',a')-Q]$.
  • Q-learning is off-policy; SARSA is on-policy.
  • Behaviour policy is epsilon-greedy; the target policy is greedy.
  • Worked check: $Q=0,\alpha=0.5,\gamma=0.9,r=10,\max Q'=20$ gives $Q=14$.
  • TD error $\delta=r+\gamma V(s')-V(s)$.
  • TD($\lambda$): $\lambda=0$ is one-step TD, $\lambda=1$ is Monte Carlo.
  • $h_{ML}=\arg\max_h P(D\mid h)$; with Gaussian noise it equals $\arg\min_h\sum(d_i-h(x_i))^2$.
  • Function approximation: $\hat v=\mathbf w^\top\mathbf x(s)$, learned by gradient descent.
  • DQN uses experience replay and a target network.

Memory hooks

  • Q-learning takes the MAX: "optimistic next step", so off-policy.
  • Trace = footprints that fade with $\gamma\lambda$.
  • Gaussian noise: ML equals least squares.
  • DQN = Deep net + Replay memory + frozen Target.
  • Incremental = one bite at a time; Batch = the whole plate.

Coverage checklist

  • Q-learning & Temporal Difference Methods: Q2, Explain the Q-Function and Q-Learning Algorithm (Jun 2025).
  • Temporal- Difference Learning: no past questions.
  • Eligibility Traces: no past questions.
  • Function Approximation: no past questions.
  • Least Squares Methods: Q1, Discuss Maximum Likelihood and Least Square Error Hypothesis (Jun 2025).
  • Incremental Methods and Batch Methods: no past questions.
  • Deep Q-Learning analysis: no past questions.
  • Deep Q-Networks and Experience Replay: no past questions.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in