Reinforcement Learning (AD-802 (B)) Unit 4 Notes

How unit 4 is examined

This unit covers batch fitted Q, the failure modes of deep Q-learning and their fixes, imitation learning, and the policy-gradient, hierarchical and partially observable extensions of RL; the marks sit in DQN and Policy Gradient (14 marks with HRL and POMDPs) and in three 7-mark explain questions.

Fitted Q

<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. ==Fitted Q iteration (FQI) is a batch value-based method that repeatedly fits a function approximator to regression targets $y=r+\gamma\max_{a'}Q_k(s',a')$ built from a fixed set of stored transitions.==

Key points.

The dataset $\{(s_i,a_i,r_i,s'_i)\}$ is collected once (or replayed), so learning is offline and sample-efficient.
Each iteration computes a target $y_i=r_i+\gamma\max_{a'}Q_k(s'_i,a')$ with the current Q-function.
A regressor (linear model, trees, neural network) is trained so that $Q_{k+1}(s_i,a_i)\approx y_i$; then $k\leftarrow k+1$.
With a neural network as regressor and a target network, FQI becomes Neural Fitted Q and is the ancestor of DQN.
Function approximation with bootstrapped targets can diverge, so FQI is only reliable with stable regressors and good data coverage.

Asked: [7 marks] (Jun 2025) Explain Fitted-Q and Deep Q-Learning Problems.

Deep Q-Learning problems

Definition. Deep Q-learning trains a neural network $Q(s,a;\theta)$ by minimising $\big(r+\gamma\max_{a'}Q(s',a';\theta^-)-Q(s,a;\theta)\big)^2$, and it suffers from the "deadly triad" of function approximation, bootstrapping and off-policy learning.

Key points.

Instability and divergence occur because the target moves every time the same weights are updated.
Correlated consecutive samples break the i.i.d. assumption of gradient descent; fixed by experience replay.
Overestimation bias arises because $\max$ over noisy estimates is biased upward; fixed by Double DQN.
Catastrophic forgetting, sparse rewards and sensitivity to hyper-parameters make training brittle; target networks and reward clipping help.

Advanced Q-learning algorithms

Definition. <mark>Double DQN reduces overestimation by letting the online network choose the next action and the target network evaluate it.</mark>

Formula. Vanilla target: $y=r+\gamma\max_{a'}Q(s',a';\theta^-)$. Double DQN target: $y=r+\gamma\,Q\big(s',\arg\max_{a'}Q(s',a';\theta);\theta^-\big)$.

Key points.

Vanilla DQN uses the same values to select and evaluate an action, so noise is picked up as a maximum and Q is overestimated.
Double DQN separates selection (online weights $\theta$) from evaluation (target weights $\theta^-$), with no extra network.
Dueling DQN splits the network into value $V(s)$ and advantage $A(s,a)$ streams: $Q=V+A-\tfrac{1}{|\mathcal A|}\sum_{a'}A(s,a')$.
Benefit: more stable learning and higher scores on Atari-type games and control tasks.

Answer frame. Open with the overestimation problem; write the two targets; list points 1-4; close with Atari application.

Asked: [7 marks] (Jun 2025) Explain any one advanced Q-learning algorithms.

Learning policies by imitating optimal controllers

Definition. <mark>Imitation learning trains a policy $\pi_\theta(a|s)$ by supervised learning on state-action demonstrations from an expert or optimal controller (behavioural cloning).</mark>

Key points.

An optimal controller (for example MPC or LQR) generates demonstrations $\{(s_i,a_i^*)\}$ that are trusted as optimal.
Steps: collect demonstrations, then minimise $\sum_i\|\pi_\theta(s_i)-a_i^*\|^2$ (or cross-entropy for discrete actions), then deploy the policy.
It needs no reward function and avoids exploration, so it is fast and safe to train.
Limitation: distribution shift, since small errors move the learner to states the expert never visited, and errors compound over the horizon.
DAgger fixes this by running the learner, asking the expert to label the visited states, and retraining on the aggregated data.

Asked: [7 marks] (Jun 2025) Explain learning policies by imitating optimal controllers.

DQN & Policy Gradient

Definition. <mark>DQN approximates the action-value function with a deep network trained with experience replay and a target network, whereas policy gradient methods directly optimise a parametrised policy $\pi_\theta$ by gradient ascent on expected return.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 372.4 252" width="372.4" height="252" role="img" aria-label="DQN loop. Env = environment, Buf = replay buffer, Net = online Q-network, Tgt = target network (copied every C steps)"><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" 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="ahh3" 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="M56.4,116.4 L168.1,50.6" marker-end="url(#ah3)"/><path class="e" d="M202.6,49.6 L314.3,115.4" marker-end="url(#ah3)"/><path class="e" d="M313.4,126 L61,126" marker-end="url(#ah3)"/><path class="e" d="M316,135.6 L204.3,201.4" marker-end="url(#ah3)"/><g class="wl"><rect x="72" y="74" width="82.2" height="18" rx="9"/><text class="t" x="113.1" y="83" dy=".35em" text-anchor="middle">transition</text></g><g class="wl"><rect x="221.3" y="74" width="75.9" height="18" rx="9"/><text class="t" x="259.3" y="83" dy=".35em" text-anchor="middle">minibatch</text></g><g class="wl"><rect x="159" y="117" width="54.3" height="18" rx="9"/><text class="t" x="186.2" y="126" dy=".35em" text-anchor="middle">action</text></g><g class="wl"><rect x="238.9" y="160" width="40.8" height="18" rx="9"/><text class="t" x="259.3" y="169" dy=".35em" text-anchor="middle">copy</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="186.2" cy="40" r="18"/><text class="t" x="186.2" y="40" dy=".35em" text-anchor="middle">Buf</text><circle class="n" cx="332.4" cy="126" r="18"/><text class="t" x="332.4" y="126" dy=".35em" text-anchor="middle">Net</text><circle class="n" cx="186.2" cy="212" r="18"/><text class="t" x="186.2" y="212" dy=".35em" text-anchor="middle">Tgt</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">DQN loop. Env = environment, Buf = replay buffer, Net = online Q-network, Tgt = target network (copied every C steps)</figcaption></figure>

Key points.

DQN takes the raw state (for example image frames) as input and outputs one $Q(s,a;\theta)$ per action.
Experience replay stores transitions in a buffer and samples random minibatches, which breaks correlation and reuses data.
A target network with frozen weights $\theta^-$, copied every $C$ steps, keeps the regression target stable.
Actions are chosen $\epsilon$-greedily; the loss is $L=\mathbb E\big[(r+\gamma\max_{a'}Q(s',a';\theta^-)-Q(s,a;\theta))^2\big]$.
Policy gradient instead outputs action probabilities and follows $\nabla_\theta J=\mathbb E\big[\nabla_\theta\log\pi_\theta(a|s)\,G_t\big]$ (REINFORCE).
Policy gradient handles continuous actions and stochastic policies, but its gradient has high variance; a baseline $b(s)$ reduces it.
DQN is off-policy and sample-efficient with discrete actions; policy gradient is on-policy and needs more samples but converges more smoothly.

Answer frame. For part (i) open with both definitions; draw the DQN loop; develop points 1-4, then 5-6, then the comparison in 7; close by saying actor-critic combines both. For a 14-mark answer, give (i) about 5 lines, then 4 lines each on (ii) Hierarchical RL and (iii) POMDPs from the next two sections.

Asked: [14 marks] (Jun 2025) Explain the following. i) DQN and Policy Gradient ii) Hierarchical RL iii) POMDPs.

Policy Gradient Algorithms for Full RL

Definition. Policy gradient algorithms for full RL optimise $J(\theta)=\mathbb E_{\pi_\theta}[\sum_t\gamma^t r_t]$ over multi-step MDPs, using the policy gradient theorem.

Key points.

Theorem: $\nabla_\theta J=\mathbb E\big[\sum_t\nabla_\theta\log\pi_\theta(a_t|s_t)\,Q^{\pi}(s_t,a_t)\big]$.
REINFORCE estimates $Q$ by the Monte-Carlo return $G_t$; it is unbiased but high-variance.
Subtracting a baseline $V(s_t)$ gives the advantage $A=Q-V$ and lowers variance without adding bias.
Actor-critic learns $V$ with a critic and updates the actor with TD errors (Unit 5).

Hierarchical RL

Definition. Hierarchical RL breaks a long task into sub-tasks by learning temporally extended actions called options (skills), which a high-level policy selects.

Key points.

An option is a triple $(I,\pi,\beta)$: initiation set, intra-option policy, and termination condition.
A manager (meta-controller) picks an option or sub-goal, and a worker executes primitive actions until it terminates.
The decision process becomes a semi-Markov decision process over options.
Benefits: faster credit assignment over long horizons, reusable skills, and better exploration on sparse-reward tasks such as navigation.

POMDPs

Definition. A partially observable MDP is a tuple $(S,A,T,R,\Omega,O,\gamma)$ in which the agent sees only an observation $o\sim O(o|s',a)$ and not the true state.

Key points.

The agent keeps a belief state $b(s)$, a probability distribution over states, as a sufficient statistic of the history.
Belief update: $b'(s')=\eta\,O(o|s',a)\sum_s T(s'|s,a)\,b(s)$, with $\eta$ normalising.
A POMDP is an MDP over belief states, so optimal policies map beliefs to actions.
Exact solution is intractable, so practical methods use recurrent networks (DRQN) or history stacking.

Last-minute revision

FQI: repeated regression to targets $r+\gamma\max Q_k(s',a')$ on a fixed batch.
Deadly triad: function approximation, bootstrapping, off-policy learning.
Replay breaks correlation; target network fixes the moving target.
Double DQN: online network selects the action, target network evaluates it.
Dueling: $Q=V+A-\text{mean}(A)$.
Behavioural cloning is supervised learning on expert pairs; it suffers distribution shift, and DAgger fixes it.
REINFORCE gradient: $\nabla\log\pi(a|s)\,G_t$; a baseline cuts variance.
Option = (initiation set, policy, termination).
Belief state is a probability distribution over hidden states, updated by Bayes rule.
DQN is off-policy with discrete actions; policy gradient is on-policy and suits continuous actions.

Memory hooks

"Select with online, judge with target" for Double DQN.
"R-T-B": Replay, Target, Buffer for DQN stability.
"Clone, drift, DAgger": imitation problem and fix.
"IPT": option = Initiation, Policy, Termination.
"Belief = history in a bag of probabilities" for POMDPs.

Coverage checklist

Fitted Q: definition, iteration steps, link to DQN (Q3).
Deep Q-Learning problems: instability, correlation, overestimation, fixes (Q3).
Advanced Q-learning algorithms: Double DQN, Dueling DQN (Q2).
learning policies by imitating optimal controllers: behavioural cloning, distribution shift, DAgger (Q4).
DQN & Policy Gradient: DQN loop, REINFORCE, comparison (Q1 part i).
Policy Gradient Algorithms for Full RL: theorem, baseline, actor-critic.
Hierarchical RL: options and manager-worker (Q1 part ii).
POMDPs: belief state and update (Q1 part iii).

Account

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

How unit 4 is examined

Fitted Q

Deep Q-Learning problems

Advanced Q-learning algorithms

Learning policies by imitating optimal controllers

DQN & Policy Gradient

Policy Gradient Algorithms for Full RL

Hierarchical RL

POMDPs

Last-minute revision

Memory hooks

Coverage checklist