Deep & Reinforcement Learning (CS-702 (B)) Unit 4 Notes

How unit 4 is examined

This unit covers the RL problem, bandits, MDPs, Bellman equations, dynamic programming, TD and Q-learning, and policy gradient; RL basics, policy gradient vs Q-learning, bandits, value/policy iteration with TD, and the Q-function carry the marks.

Introduction to reinforcement learning (RL)

<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">High weight</span>

Definition. <mark>Reinforcement learning is a branch of machine learning in which an agent learns, by trial and error interaction with an environment, a policy that maximises the expected cumulative reward.</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 381 80" width="381" height="80" role="img" aria-label="Agent-environment loop. Agt = agent, Env = environment; at each step the agent sends an action and receives the next state and a reward."><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="ah9" 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="ahh9" 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="M58.6,44 Q190.5,72 320.5,44.4" marker-end="url(#ah9)"/><path class="e" d="M322.4,36 Q190.5,8 60.5,35.6" marker-end="url(#ah9)"/><g class="wl"><rect x="162.9" y="49.1" width="54.3" height="18" rx="9"/><text class="t" x="190" y="58.1" dy=".35em" text-anchor="middle">action</text></g><g class="wl"><rect x="142.7" y="12.9" width="96.6" height="18" rx="9"/><text class="t" x="191" y="21.9" dy=".35em" text-anchor="middle">state,reward</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Agt</text><circle class="n" cx="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">Env</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Agent-environment loop. Agt = agent, Env = environment; at each step the agent sends an action and receives the next state and a reward.</figcaption></figure>

Key points.

There is no supervisor with labelled answers; the agent gets only a scalar reward, so learning is guided by evaluation and not by instruction.
The main elements are the agent, environment, state $s$, action $a$, reward $r$, policy $\pi(a|s)$, value function and (optionally) a model of the environment.
Feedback is delayed, so the agent must solve credit assignment: deciding which earlier action deserves the reward.
The agent faces the exploration-exploitation trade-off: try new actions to learn more, or use the best known action to earn reward.
The goal is to maximise the return $G_t=r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3}+\dots$ with discount factor $0\le\gamma\le1$.
Applications include game playing (Go, Atari), robot control, recommendation, and self-driving.

Actor-Critic method. It combines a policy-based actor and a value-based critic. The actor $\pi_\theta(a|s)$ picks actions; the critic $V_w(s)$ evaluates them through the TD error $\delta=r+\gamma V(s')-V(s)$. The actor is updated by $\theta\leftarrow\theta+\alpha\,\delta\,\nabla_\theta\log\pi_\theta(a|s)$ and the critic by $w\leftarrow w+\beta\,\delta\,\nabla_w V$. The critic's baseline lowers the variance of pure policy gradient.

Group Normalization. It divides the channels of a layer into groups and normalises each group per sample using its mean and variance: $\hat x=(x-\mu_G)/\sqrt{\sigma_G^2+\epsilon}$, followed by learnable scale $\gamma$ and shift $\beta$. It does not depend on batch size, so it works with small batches.

PCA. Principal Component Analysis reduces dimension by projecting centred data onto the top eigenvectors of the covariance matrix, which are the directions of maximum variance. Steps: centre the data, compute the covariance, find eigenvalues and eigenvectors, keep the top $k$, project.

Answer frame. Open with the definition; draw the agent-environment loop; develop points 1-6 in order; give one line each on the other two chosen notes (any three of four are needed, 14 marks); close with a real application such as game playing.

Asked: [14 marks] (Dec 2020) Write short notes (any three): i) Reinforcement Learning ii) Actor-Critic Method iii) Group Normalization iv) PCA

Bandit algorithms - UCB

Definition. <mark>A multi-armed bandit is a one-state RL problem in which an agent repeatedly picks one of $K$ arms with unknown reward distributions and must balance exploring arms against exploiting the best one to maximise total reward.</mark>

Key points.

The exploration-exploitation dilemma is central: pulling the arm that looks best earns reward now, while pulling others may reveal a better arm.
Performance is measured by regret, $\rho_T=T\mu^*-\sum_{t=1}^{T}r_t$, the reward lost compared with always pulling the best arm of mean $\mu^*$.
Action-value estimate: $Q_{n+1}=Q_n+\frac{1}{n}(r_n-Q_n)$, an incremental sample average.
Epsilon-greedy pulls the arm with the highest $Q$ with probability $1-\epsilon$ and a random arm with probability $\epsilon$; it is simple but explores blindly and keeps regret linear.
UCB picks $a_t=\arg\max_a\left[Q_t(a)+c\sqrt{\dfrac{\ln t}{N_t(a)}}\right]$, where $N_t(a)$ is the pull count, so rarely tried arms get a larger bonus; regret grows only as $O(\ln T)$.
Thompson sampling keeps a posterior over each arm's mean (Beta for Bernoulli rewards), samples one value per arm, and pulls the arm with the largest sample.
Applications: online advertising, clinical trials, recommendation and A/B testing.

Answer frame. Open with the definition and the dilemma; develop points 1-7 in order, giving the update rule of each algorithm; close with applications.

Asked: [7 marks] (Dec 2020, Nov 2023) Discuss Bandit Algorithms in details.

PAC

Definition. Probably Approximately Correct (PAC) learning asks for an algorithm that, with probability at least $1-\delta$, returns a result within $\epsilon$ of the optimum.

$\epsilon$ is the accuracy and $\delta$ the confidence, so the answer is "approximately" right and "probably" so.
Sample complexity is the number of samples needed; for $K$ arms, finding an $\epsilon$-optimal arm needs $O\!\left(\frac{K}{\epsilon^2}\ln\frac{1}{\delta}\right)$ pulls.
It gives guarantees on learning, unlike regret bounds which measure online loss.

Median Elimination

Definition. Median Elimination is a PAC algorithm that finds an $\epsilon$-optimal arm with probability $1-\delta$.

It runs in rounds: sample every remaining arm equally, then discard the half with below-median estimated reward.
Accuracy and confidence parameters are tightened each round, $\epsilon_\ell=\tfrac34\epsilon_{\ell-1}$ and $\delta_\ell=\tfrac12\delta_{\ell-1}$, so errors add up to at most $\epsilon$.
Total sample complexity is $O\!\left(\frac{K}{\epsilon^2}\ln\frac1\delta\right)$, which is optimal up to constants.

Policy Gradient

Definition. <mark>Policy gradient methods directly parameterise the policy $\pi_\theta(a|s)$ and improve $\theta$ by gradient ascent on the expected return $J(\theta)$.</mark>

Formula. $$J(\theta)=\mathbb{E}_{\tau\sim\pi_\theta}[R(\tau)],\qquad \nabla_\theta J(\theta)=\mathbb{E}\left[\sum_t \nabla_\theta\log\pi_\theta(a_t|s_t)\,G_t\right]$$ REINFORCE update: $\theta\leftarrow\theta+\alpha\,\nabla_\theta\log\pi_\theta(a_t|s_t)\,G_t$. Subtracting a baseline $b(s)$ from $G_t$ reduces variance without bias.

Key points.

The policy is learned directly, with no need to compute a value for every action, so continuous action spaces are handled naturally.
REINFORCE is a Monte Carlo method: sample an episode, compute returns $G_t$, and raise the probability of actions that led to high return.
The policy is usually stochastic (softmax or Gaussian), which gives built-in exploration and suits partially observed problems.
It is on-policy, since the gradient is estimated from trajectories of the current policy.
Gradient estimates have high variance and learning is sample inefficient; baselines and actor-critic fix this.
It converges to a local optimum, not necessarily the global one.

Comparison with Q-learning.

Aspect	Policy gradient	Q-learning
Approach	Policy-based, optimises $\pi_\theta$ directly	Value-based, learns $Q(s,a)$
Policy	Stochastic	Deterministic (greedy on $Q$)
Actions	Continuous or discrete	Discrete, needs $\max_a$
Policy type	On-policy (REINFORCE)	Off-policy TD
Update	Gradient ascent on $J(\theta)$	Bellman backup, $Q\leftarrow Q+\alpha\,\delta$
Variance / bias	High variance, unbiased	Low variance, biased bootstrap
Convergence	Local optimum, smooth	Can be unstable with approximation

Answer frame. Open with the definition and $J(\theta)$; write the gradient and REINFORCE update; then develop points 1-6; draw the comparison table (5-7 rows); close with "use PG for continuous or stochastic policies, Q-learning for small discrete actions".

Asked: [14 marks] (Jun 2025) Define the Policy Gradient method in reinforcement learning. How does it differ from Q-learning?

Full RL & MDPs

Definition. A Markov Decision Process is the tuple $(S,A,P,R,\gamma)$ with transition probabilities $P(s'|s,a)$, reward $R(s,a)$ and discount $\gamma$.

The Markov property says the next state depends only on the current state and action.
A policy $\pi(a|s)$ maps states to actions; the goal is the policy maximising expected discounted return.
Full RL is the case where $P$ and $R$ are unknown and must be learnt from experience.

Bellman Optimality

Definition. The Bellman optimality equation states that the optimal value of a state equals the best action's expected reward plus discounted optimal value of the next state. $$V^*(s)=\max_a\sum_{s'}P(s'|s,a)\left[R+\gamma V^*(s')\right],\qquad Q^*(s,a)=\sum_{s'}P(s'|s,a)\left[R+\gamma\max_{a'}Q^*(s',a')\right]$$

It is a non-linear system because of the max, so it is solved iteratively.
The optimal policy is $\pi^*(s)=\arg\max_a Q^*(s,a)$.
Value iteration and Q-learning are both methods that solve it.

Dynamic Programming - Value iteration

Definition. ==Value iteration repeatedly applies the Bellman optimality backup $V_{k+1}(s)=\max_a\sum_{s'}P(s'|s,a)[R+\gamma V_k(s')]$ to every state until $V$ converges to $V^*$.==

Steps.

Step 1: Initialise V(s) = 0 for all states.
Step 2: For each state, set V(s) to the max over actions of the expected reward plus gamma times V(next state).
Step 3: Repeat Step 2 until the largest change is below a small threshold.
Step 4: Extract the policy: pi(s) = argmax_a of the same expression.

Policy iteration. It alternates policy evaluation (solve $V^\pi$ for the current policy) with policy improvement ($\pi'(s)=\arg\max_a\sum P[R+\gamma V^\pi(s')]$) until the policy stops changing; it usually needs few iterations.

Temporal Difference learning. It learns from raw experience without a model, bootstrapping like DP and sampling like Monte Carlo: $V(s)\leftarrow V(s)+\alpha[r+\gamma V(s')-V(s)]$.

Aspect	Value iteration	Policy iteration	TD learning
Needs model $P,R$	Yes	Yes	No
Type	Planning (DP)	Planning (DP)	Learning from samples
Core step	Bellman optimality backup	Evaluation + improvement	Bootstrapped sample update
Per iteration	One sweep, cheap	Full evaluation, costly	One step
Converges to	$V^*$	$\pi^*$ in finite steps	$V^\pi$ (or $Q^*$ if control)

Answer frame. Open with the MDP setting (planning vs learning); define each of the three in order with its formula; draw the comparison table; close with model-based (DP) vs model-free (TD) and an example such as gridworld.

Asked: [7 marks] (Dec 2020, Nov 2023) Explain value iteration, policy iteration and Temporal Difference Learning.

Policy iteration

Definition. Policy iteration finds the optimal policy by alternating evaluation and greedy improvement.

Evaluation: $V^\pi(s)=\sum_a\pi(a|s)\sum_{s'}P[R+\gamma V^\pi(s')]$, solved iteratively or as linear equations.
Improvement: act greedily with respect to $V^\pi$; the new policy is never worse.
Because a finite MDP has finitely many policies, it stops at $\pi^*$ in finitely many iterations.

Q-learning & Temporal Difference Methods

Definition. ==The Q-function $Q^\pi(s,a)=\mathbb{E}_\pi[G_t\mid s_t=s,a_t=a]$ is the expected return from taking action $a$ in state $s$ and following $\pi$ afterwards; Q-learning is an off-policy TD control algorithm that learns $Q^*$ directly.==

Formula. $$Q(s,a)\leftarrow Q(s,a)+\alpha\left[r+\gamma\max_{a'}Q(s',a')-Q(s,a)\right]$$ Here $\alpha$ is the learning rate, $\gamma$ the discount, and the bracket is the TD error.

Steps.

Step 1: Initialise Q(s,a) arbitrarily (zero) for all pairs.
Step 2: In state s choose a by epsilon-greedy on Q.
Step 3: Take a, observe reward r and next state s'.
Step 4: Update Q(s,a) using the formula above.
Step 5: Set s = s' and repeat until the episode ends; run many episodes.

Key points.

It is off-policy: the update uses $\max_{a'}$ (the greedy policy) although behaviour is epsilon-greedy, so it learns the optimal policy while exploring.
It is model-free, needing no $P$ or $R$, and it bootstraps from its own estimate of the next state.
It converges to $Q^*$ with probability 1 if every state-action pair is visited infinitely often and $\sum\alpha=\infty$, $\sum\alpha^2<\infty$.
Example: with $Q=0.5$, $\alpha=0.1$, $\gamma=0.9$, $r=1$, $\max Q(s',\cdot)=2$: new $Q=0.5+0.1(1+1.8-0.5)=\mathbf{0.73}$.

Answer frame. Open with the Q-function definition and the Bellman optimality relation $Q^*=r+\gamma\max Q^*(s',a')$; write the update rule; list the steps; state convergence conditions; close with the worked update or a gridworld example.

Asked: [7 marks] (Dec 2020, Nov 2023) Explain the Q Function and Q Learning Algorithm.

Temporal-Difference Learning

Definition. TD learning updates a value estimate toward a bootstrapped target after every step: $V(s)\leftarrow V(s)+\alpha[r+\gamma V(s')-V(s)]$.

The bracket is the TD error $\delta$.
It combines Monte Carlo (learns from experience) and DP (bootstraps).
It is online and needs no episode end, so it has lower variance than Monte Carlo but some bias.
SARSA is its on-policy control form using $Q(s',a')$ of the action actually taken.

Eligibility Traces

Definition. An eligibility trace is a decaying record of recently visited states that lets one TD error update many past states, giving TD($\lambda$).

Trace update: $e(s)\leftarrow\gamma\lambda e(s)+\mathbb{1}[s_t=s]$, then $V(s)\leftarrow V(s)+\alpha\,\delta\,e(s)$ for all $s$.
$\lambda=0$ gives one-step TD(0) and $\lambda=1$ gives Monte Carlo behaviour.
It speeds credit assignment and balances bias against variance.

Function Approximation

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

Linear form: $\hat v(s;w)=w^\top\phi(s)$ with feature vector $\phi(s)$.
Semi-gradient TD update: $w\leftarrow w+\alpha[r+\gamma\hat v(s')-\hat v(s)]\phi(s)$.
It is needed for large or continuous state spaces, but combining bootstrapping, off-policy learning and approximation can diverge.

Least Squares Methods

Definition. Least-squares methods such as LSTD solve for the linear value weights in one step instead of by incremental gradient updates.

LSTD computes $w=A^{-1}b$ with $A=\sum\phi(s)(\phi(s)-\gamma\phi(s'))^\top$ and $b=\sum r\,\phi(s)$.
It is more data efficient than TD and has no step size, but costs $O(d^2)$ to $O(d^3)$ per update.
LSPI uses LSTD for the Q-function inside policy iteration.

Last-minute revision

RL: an agent learns a policy to maximise expected discounted return $G_t=\sum\gamma^k r_{t+k+1}$ from reward feedback only.
Exploration vs exploitation: epsilon-greedy, UCB, Thompson sampling; regret $=T\mu^*-\sum r_t$.
UCB rule: $Q_t(a)+c\sqrt{\ln t/N_t(a)}$, regret $O(\ln T)$.
PAC: within $\epsilon$ of optimum with probability $1-\delta$; Median Elimination halves the arms each round.
MDP $=(S,A,P,R,\gamma)$; Markov property: next state depends only on the current state and action.
Bellman optimality: $V^*(s)=\max_a\sum P[R+\gamma V^*(s')]$.
Value iteration: Bellman optimality backup; policy iteration: evaluation plus improvement; both need a model.
TD(0): $V\leftarrow V+\alpha[r+\gamma V(s')-V]$; model-free.
Q-learning: $Q\leftarrow Q+\alpha[r+\gamma\max Q(s',a')-Q]$, off-policy.
REINFORCE: $\theta\leftarrow\theta+\alpha\nabla\log\pi_\theta(a|s)G_t$, on-policy, high variance.
Actor-critic: actor is the policy, critic the value; the TD error drives both.

Memory hooks

Value iteration = "max in every sweep"; policy iteration = "evaluate, then improve".
Q-learning is off-policy because of the "max"; SARSA uses the action it took.
Policy gradient = "push up log-probability of good actions, weighted by return".
UCB = mean plus optimism bonus: unpulled arms look great.
$\lambda$ in TD($\lambda$): 0 is one step, 1 is Monte Carlo.

Coverage checklist

Introduction to reinforcement learning (RL): Dec 2020 short notes (RL, actor-critic, group normalization, PCA).
Bandit algorithms - UCB: Dec 2020, Nov 2023 bandit algorithms.
PAC: definition, sample complexity.
Median Elimination: definition, round scheme.
Policy Gradient: Jun 2025 definition and difference from Q-learning.
Full RL & MDPs: MDP tuple.
Bellman Optimality: $V^*$, $Q^*$ equations.
Dynamic Programming - Value iteration: Dec 2020, Nov 2023 value iteration, policy iteration and TD learning.
Policy iteration: evaluation and improvement.
Q-learning & Temporal Difference Methods: Dec 2020, Nov 2023 Q-function and Q-learning.
Temporal-Difference Learning: TD(0) update.
Eligibility Traces: TD($\lambda$).
Function Approximation: linear approximation.
Least Squares Methods: LSTD, LSPI.

Account

Deep & Reinforcement Learning (CS-702 (B)) - Unit 4 Short Notes

How unit 4 is examined

Introduction to reinforcement learning (RL)

Bandit algorithms - UCB

PAC

Median Elimination

Policy Gradient

Full RL & MDPs

Bellman Optimality

Dynamic Programming - Value iteration

Policy iteration

Q-learning & Temporal Difference Methods

Temporal-Difference Learning

Eligibility Traces

Function Approximation

Least Squares Methods

Last-minute revision

Memory hooks

Coverage checklist