B I T M E S R A · A I 2 0 5 · B .

T E C H A I & M L · S E M E S T E R I V

Module V — Learning
& Reinforcement Learning
Complete notes · Every key term defined · PYQ questions highlighted in gold · Learning part
only (Robotics excluded)

PYQ Asked Key Concept / Term Formula / Equation Important for Exam

Algorithm Pseudocode

CONTENTS

1. What is Learning? — Forms of Learning Syllabus §1

1.1 Inductive Learning

1.2 Explanation-Based Learning
2. Reinforcement Learning — Framework & Key Terms ★ PYQ Heavy

2.1 The RL Framework — Agent, Environment, Loop

2.2 All Key Terms: Policy, Reward, Return, Value, Q-function, Bellman
2.3 Discounted Reward — detailed explanation
2.4 Bellman Equation — derivation & intuition
3. Passive Reinforcement Learning Syllabus §2

4. Active Reinforcement Learning Syllabus §3

5. Value Iteration & Policy Iteration ★ PYQ Direct

6. Q-Learning — Full Example ★ PYQ Direct

6.1 Q-Table, Update Rule, Step-by-Step Trace

6.2 Limitations of Q-Learning
6.3 Deep Q-Network (DQN) — How limitations are overcome
7. Generalisation in RL & Policy Search

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 8. Comparison Tables & Quick Revision

1 What is Learning? — Forms of Learning

Learning (in AI)

A system learns if it improves its performance on future tasks based on
experience. Learning allows an agent to operate in environments that
were not fully anticipated at design time.

The Learning Problem — Four Components

1. Performance Element 2. Learning Element

The part of the agent that selects Responsible for making
actions. This is what we want to improvements. Uses feedback from the
improve — it's the agent's current critic to update the performance
policy. element.

3. Critic 4. Problem Generator

Tells the learning element how well the Suggests exploratory actions that may
agent is doing with respect to a fixed be suboptimal in short term but lead to
performance standard. better experiences and learning.

1.1 Inductive Learning

Inductive Learning
Learning a general rule (hypothesis) from specific examples. Given a set
of training examples (input-output pairs), the agent must infer the
underlying function that generated them.
Input: {(x₁,y₁), (x₂,y₂), …, (xₙ,yₙ)} — labelled training data

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Output: A hypothesis h(x) that approximates the true function f(x)
Goal: Generalise well to unseen examples (low test error)

Types of Inductive Learning:

Supervised learning: Labels provided — regression, classification
Unsupervised learning: No labels — clustering, dimensionality reduction
Decision tree learning: Builds tree of if-then rules from data
Neural network learning: Adjusts weights via backpropagation

Ockham's Razor (in inductive learning): Among all hypotheses consistent with
the data, prefer the simplest. Complex hypotheses risk overfitting — memorising
training noise instead of learning the true pattern.

1.2 Explanation-Based Learning (EBL)

Explanation-Based Learning
The agent already has a domain theory (background knowledge). When
given a single training example, it explains why that example is an
instance of a concept using its domain theory, then generalises this
explanation into a reusable rule.

Key difference from inductive learning: EBL needs only one example because it
uses prior knowledge. Inductive learning needs many examples because it has
no prior knowledge.

Example: Given one example of a cup holding liquid, EBL uses the domain
theory (stable base + concave shape → holds liquid) to generalise: "Any object
with a stable base and concave upper surface is a cup," without needing
thousands of cup examples.

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 2 Reinforcement Learning — Framework & All Key Terms
★ PYQ — 10 MARKS TOTAL

★ PYQ

"Explain the terms Policy, Discounted reward and Bellman equation in context to
value iteration in reinforcement learning."
End Sem 2024 — Q5(a) [5 marks]

★ PYQ

"Explain with an example Q-learning. What are its limitations. How is it overcome?"
End Sem 2024 — Q5(b) [5 marks]

★ PYQ

"Explain reinforcement learning. Differentiate between passive and active

reinforcement learning."
Makeup 2024 — Q5(a) [10 marks]

2.1 The RL Framework

Reinforcement Learning is a paradigm where an agent learns by interacting with
an environment. It receives reward signals and must discover which actions
yield the most cumulative reward — without being explicitly told what to do.

Action: aₜ
AGENT ENVIRON-
(Learner / Decision Maker) MENT
State: sₜ₊₁ Reward: rₜ₊₁

At each time step t: agent observes state sₜ, takes action aₜ, receives reward rₜ₊₁, moves to sₜ₊₁

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Core elements of RL: Agent, Environment, State (S), Action (A), Reward (R),
Policy (π), Value function (V), Q-function (Q). Every RL concept connects back to
this loop.

2.2 All Key Terms — Fully Defined

CORE TERM

State — sₜ
A complete description of the world at time t. The agent's perception of
the environment at a given moment.
State space S: Set of all possible states
Example (Grid world): State = agent's (row, column) position on the
grid
Example (Chess): State = complete board configuration

Markov Property: A state sₜ has the Markov property if P(sₜ₊₁ | sₜ, aₜ) =
P(sₜ₊₁ | s₀, a₀, …, sₜ, aₜ). The future depends only on the present, not the
past. RL assumes this property (Markov Decision Process).

CORE TERM

Action — aₜ
The choice made by the agent at time t. The agent selects an action from
the action space A.
Discrete actions: {Up, Down, Left, Right} in a grid world
Continuous actions: Torque applied to a robot joint (real number)
The action transitions the environment from state sₜ to sₜ₊₁

★ PYQ ★ PYQ TERM

Reward — Rₜ
A scalar feedback signal from the environment indicating how good or
bad the agent's action was at time t. The agent's goal is to maximise
cumulative reward, not just immediate reward.

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Positive reward: Reinforces the action (agent should repeat it)
Negative reward (penalty): Discourages the action
Zero reward: Neutral — no signal in many time steps
Example: In chess → +1 for win, −1 for loss, 0 for each move
Example: In Pac-Man → +10 for eating pellet, −500 for dying

Reward Hypothesis: All goals can be described as maximisation of

expected cumulative reward. This is the central hypothesis of RL.

★ PYQ ★ PYQ TERM

Return — Gₜ (Total Discounted Reward)
The total accumulated reward from time step t onward. This is what the
agent actually wants to maximise.

Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + … = Σ(k=0 to ∞)

γᵏ Rₜ₊ₖ₊₁
γ (gamma) = discount factor (0 ≤ γ < 1) | Rₜ₊ₖ₊₁ = reward at

future time step

This can be written recursively (very important!):

Gₜ = Rₜ₊₁ + γ · Gₜ₊₁
Current return = immediate reward + discounted future return

★ PYQ ★ PYQ TERM

Policy — π
The agent's strategy — a mapping from states to actions. The policy tells
the agent what to do in every possible situation. It is the complete
specification of agent behaviour.

Deterministic Policy Stochastic Policy

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 π(s) = a — maps state s directly to a π(a|s) = P(aₜ=a | sₜ=s) — gives a
single action a. No randomness. probability distribution over
Example: π(A) = Right, π(B) actions.
= Up Example: π(Right|A)=0.7,
π(Up|A)=0.3

Optimal Policy π*: The policy that maximises expected return from every
state. This is what RL algorithms are trying to find.

Intuition: The policy is like a "rulebook" the agent carries. A bad policy
might walk into walls repeatedly. The optimal policy always takes the best
action in every state.

2.3 Discounted Reward — Deep Explanation

★ PYQ ★ PYQ TERM

Discount Factor — γ (Gamma)
The discount factor γ ∈ [0, 1) controls how much the agent values future
rewards vs immediate rewards.

Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + γ³Rₜ₊₄ + …

γ
Behaviour Agent cares about Use case
value

γ=0 Completely Only immediate Short-term tasks,

myopic reward Rₜ₊₁ immediate feedback

γ= Moderate future Near-future rewards Balanced tasks

0.5 discount weighted more

γ= Far-sighted Rewards many steps Long-horizon tasks,

0.9 ahead still matter chess

γ→1 No discounting All future rewards Episodic tasks with

(equal weight) equally finite horizon

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Why discount? Three reasons: (1) Mathematical — ensures convergence
of infinite sums (γ < 1 → sum converges). (2) Uncertainty — future
rewards are less certain than immediate ones. (3) Financial analogy —
money now is worth more than money later (time value).

Worked Numerical Example

Reward sequence: R₁=1, R₂=2, R₃=3, R₄=4. Discount γ=0.9. Compute G₀:

G₀ = R₁ + γR₂ + γ²R₃ + γ³R₄

= 1 + (0.9)(2) + (0.9²)(3) + (0.9³)(4)

= 1 + 1.8 + 2.43 + 2.916

G₀ = 8.146

Compare with γ=0 (myopic): G₀ = 1 | γ=1 (no discount): G₀ = 1+2+3+4 = 10

2.4 Value Functions & Bellman Equation

★ PYQ ★ PYQ TERM

State Value Function — V(s) or Vπ(s)
The expected return starting from state s and following policy π
thereafter. Answers: "How good is it to be in state s?"

Vπ(s) = 𝔼π[Gₜ | sₜ = s] = 𝔼π[ Σ(k=0→∞) γᵏ

Rₜ₊ₖ₊₁ | sₜ = s ]

High V(s) → state s is good (agent expects large future reward from
here)
Low V(s) → state s is bad (agent expects low/negative future reward)
Example: In chess, V(state with queen advantage) > V(state with piece
deficit)

CORE TERM
Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 CORE TERM

Action-Value Function — Q(s, a) or Qπ(s, a)

The expected return starting from state s, taking action a, then following
policy π. Answers: "How good is it to take action a in state s?"

Qπ(s,a) = 𝔼π[Gₜ | sₜ=s, aₜ=a]

Relationship to V: Vπ(s) = Σₐ π(a|s) · Qπ(s,a)

Why Q is more useful than V: V(s) tells you how good a state is, but you
still need to know transition probabilities to pick actions. Q(s,a) directly
gives you the value of each action — you just pick argmax_a Q(s,a). This is
why Q-learning works without a model of the environment.

★ PYQ ★ PYQ TERM

Bellman Equation
The Bellman equation expresses the value of a state recursively in terms
of its successors. It is the fundamental equation of dynamic programming
in RL.

Derivation (for V)
Start from the definition:

Vπ(s) = 𝔼[Gₜ | sₜ=s]

= 𝔼[Rₜ₊₁ + γGₜ₊₁ | sₜ=s]

= 𝔼[Rₜ₊₁ + γVπ(sₜ₊₁) | sₜ=s]

Vπ(s) = Σₐ π(a|s) Σₛ' P(s'|s,a) [R(s,a,s') +

γ Vπ(s')]

Intuition
Value of current state = (weighted) sum over all actions and successor
states of: [immediate reward + discounted value of next state]

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Bellman Optimality Equation
The optimal value function V* satisfies:

V*(s) = max_a Σₛ' P(s'|s,a) [R(s,a,s') + γ

V*(s')]
The optimal policy takes the action that maximises this quantity

Q*(s,a) = Σₛ' P(s'|s,a) [R(s,a,s') + γ

max_a' Q*(s',a')]
Bellman optimality for Q-function — basis of Q-learning update

rule

Key insight: The Bellman equation gives us a way to compute V(s)

iteratively. Start with V(s)=0 for all s. Update repeatedly using the equation
until convergence. This is Value Iteration.

CORE TERM

Greedy Policy w.r.t. Value Function

Given a value function V(s) or Q(s,a), the greedy policy selects the action
that maximises the expected value:

π(s) = argmax_a Q(s,a)

In value iteration: once V* is found, the optimal policy is derived by being

greedy w.r.t. V*.

CORE TERM

Exploration vs Exploitation Tradeoff

One of the central challenges in RL:

Exploitation Exploration

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Take the action currently believed Try new, uncertain actions to
to be best. Maximises reward based gather information. May sacrifice
on current knowledge. But may immediate reward but could find
miss better options. better long-term strategies.

ε-greedy strategy: With probability ε → explore (random action). With

probability 1−ε → exploit (best known action).

aₜ = { random action with prob. ε |

argmax_a Q(s,a) with prob. 1-ε }

CORE TERM

Markov Decision Process (MDP)

The formal framework for RL. An MDP is defined by the tuple (S, A, P, R,
γ):
S = set of states
A = set of actions
P(s'|s,a) = transition probability — probability of reaching state s' from
s via action a
R(s,a,s') = reward function — reward received when moving from s to s'
via a
γ = discount factor

Model-based RL: Agent knows P and R → uses planning (value iteration).

Model-free RL: Agent does NOT know P and R → must learn from
experience (Q-learning, SARSA).

3 Passive Reinforcement Learning ★ PYQ MAKEUP

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 ★ PYQ

"Differentiate between passive and active reinforcement learning."

Makeup 2024 — Q5(a) [10 marks]

Passive RL — Definition
In passive RL, the agent's policy is fixed (given, not learned). The agent
simply executes the policy and tries to learn the value function V(s) — i.e.,
how good each state is under that policy.
The agent's task: given policy π, estimate Vπ(s) by observing outcomes of
following π.

Methods for Passive RL

METHOD 1 METHOD 2

Direct Utility Estimation Adaptive Dynamic

Run the policy many times. For Programming (ADP)
each state visited, record the Learn the transition model
total future reward obtained. P(s'|s,a) from experience, then
Average over all visits → V(s). use value iteration (Bellman
Problem: Slow to converge. equation) to find V(s).
Ignores Bellman constraint — Advantage: Efficient, uses
treats each episode Bellman constraints.
independently, losing useful Disadvantage: Requires learning
information about state the full transition model.
relationships.

METHOD 3

Temporal Difference (TD) Learning

TD learning combines ideas from DP and Monte Carlo. It updates V(s)
incrementally after every transition using the TD error:

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 V(sₜ) ← V(sₜ) + α [Rₜ₊₁ + γV(sₜ₊₁) − V(sₜ)]
α = learning rate | [Rₜ₊₁ + γV(sₜ₊₁) − V(sₜ)] = TD error (δ) — how

wrong our current estimate is

TD Error δ Bootstrap Online Learning

Rₜ₊₁ + γV(sₜ₊₁) − V(sₜ). TD uses estimate of Updates happen after
Positive δ → V(sₜ₊₁) rather than every single step, not
underestimated V(sₜ), waiting for full after full episode.
increase it. Negative episode return. This Much faster in
→ overestimated, is called practice.
decrease it. bootstrapping.

4 Active Reinforcement Learning ★ PYQ MAKEUP

Active RL — Definition
In active RL, the agent must both learn and decide what actions to take. It
learns the policy π itself by trying actions and observing outcomes. Must
balance exploration (trying new things) and exploitation (using what it
knows).

Passive vs Active — Comparison Table

Criterion Passive RL Active RL

Policy Fixed, given in advance Learned by the agent itself

Goal Estimate V(s) under given π Find optimal policy π*

Action Always follows π (no Agent decides — explore or

selection choice) exploit

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Criterion Passive RL Active RL

Key challenge Accurate value estimation Exploration-exploitation tradeoff

Algorithm TD(0), Direct Utility Est., Q-learning, SARSA, Active ADP

examples ADP

Analogy Student who only observes Student who experiments and

teacher's actions tries things themselves

5 Value Iteration & Policy Iteration ★ PYQ Q5(A) DIRECT

Value Iteration

Value Iteration — Definition

A dynamic programming algorithm that computes the optimal value
function V*(s) by repeatedly applying the Bellman optimality equation
until convergence.

Algorithm

VALUE-ITERATION(MDP, θ):
// θ = small threshold for convergence

Initialize V(s) = 0 for all s ∈ S

repeat:
Δ ← 0
for each state s ∈ S:
v ← V(s)

V(s) ← max_a Σₛ' P(s'|s,a) [R(s,a,s') + γ·V(s')]

Δ ← max(Δ, |v − V(s)|)
until Δ < θ

// Extract optimal policy

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 for each state s:
π*(s) ← argmax_a Σₛ' P(s'|s,a) [R(s,a,s') + γ·V(s')]

Step-by-Step Numerical Example — 4-State Grid World

Actions: Right

S1 S2 S3 S4
(start) (goal, R=+1)

V₀=0 V₀=0 V₀=0 V₀=0 → +1

Setup: 4 states in a row. Only action = "Right". Goal S4 gives reward +1. All others
give 0. γ = 0.9

Iteration V(S1) V(S2) V(S3) V(S4=goal)

k=0 0 0 0 0
(init)

k=1 0 0 0 + 0.9×1 = +1
0.9 (terminal)

k=2 0 0 + 0.9×0.9 0.9 1

= 0.81

k=3 0.9×0.81 = 0.81 0.9 1

0.729

Converged V(S1)=0.729 V(S2)=0.81 V(S3)=0.9 V(S4)=1

Interpretation: V(S1)=0.729 means: starting from S1 and following optimal

policy, the agent expects total discounted reward = 0.729. Closer to goal → higher
value. Discount factor reduces value for states further from the goal.

Policy Iteration (brief)

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Policy Iteration
Alternates between two steps until convergence:
Policy Evaluation: Given current policy π, compute Vπ(s) exactly (solve
Bellman equations)
Policy Improvement: For each state, make policy greedy w.r.t. current
Vπ. If π unchanged → converged → π is optimal.

Value Iteration vs Policy Iteration

Criterion Value Iteration Policy Iteration

Core idea Sweep value function until Alternate between full policy
convergence, then extract evaluation and improvement
policy

Update rule V(s) ← max_a [R + γV(s')] Evaluate Vπ exactly, then π ←

greedy(Vπ)

Convergence Slower (many sweeps) Faster (fewer iterations, each

more expensive)

Requires Yes (P and R needed) Yes (P and R needed)

model?

6 Q-Learning — Full Explanation with Example

★ PYQ Q5(B) DIRECT

★ PYQ

"Explain with an example Q-learning. What are its limitations. How is it overcome?"
End Sem 2024 — Q5(b) [5 marks]

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Q-Learning
Q-learning is a model-free, off-policy reinforcement learning algorithm.
It learns the optimal Q-function Q*(s,a) directly from interaction with the
environment — without needing a model of P or R.
Off-policy: Learns about the greedy policy while following an
exploratory (ε-greedy) behaviour policy
Model-free: No need to know transition probabilities P(s'|s,a)
Goal: Learn Q*(s,a) = optimal action-value function

Q-Learning Update Rule

★ PYQ ★ CORE FORMULA

Q-Learning Update Equation

Q(sₜ, aₜ) ← Q(sₜ, aₜ) + α [Rₜ₊₁ + γ · max_a'

Q(sₜ₊₁, a') − Q(sₜ, aₜ)]

Symbol Meaning Role in update

Q(sₜ,aₜ) Current Q-value estimate What we're updating

for (state, action)

α Learning rate (0 < α ≤ 1) How fast to update — higher α

= faster but noisier

Rₜ₊₁ Immediate reward received Observed from environment

γ Discount factor How much future matters

max_a' Best Q-value in next state Bootstrapped estimate of

Q(sₜ₊₁,a') future value

[...] = TD Difference between target Direction and magnitude of

error δ and current estimate update

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Algorithm Pseudocode

Q-LEARNING(MDP, episodes, α, γ, ε):

Initialize Q(s,a) = 0 for all s, a
for each episode:
s ← initial state

repeat (for each step in episode):

// ε-greedy action selection
if random() < ε:
a ← random action // explore

else:
a ← argmax_a Q(s,a) // exploit
Take action a, observe reward R, next state s'
// Q-learning update
Q(s,a) ← Q(s,a) + α[R + γ·max_a' Q(s',a') − Q(s,a)]

s ← s'
until s is terminal

Detailed Numerical Example — Grid World

3-state linear grid: S1 → S2 → S3(Goal). Actions: {Right, Left}. γ=0.9, α=0.5, ε=0.1
Rewards: Reaching S3 = +10. Any other transition = −1 (step penalty).

R R
S1 S2 S3
(start) GOAL R=+10
L L

Initial Q-table (all zeros):

State Q(s, Right) Q(s, Left)

S1 0 0

S2 0 0

S3 (goal) — —

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Episode 1 Trace (following ε-greedy, say ε=0 initially for clarity)
1 t=1: State=S1, Action=Right
Observe: R=−1, next state=S2
Update: Q(S1,R) ← 0 + 0.5×[−1 + 0.9×max(Q(S2,R),Q(S2,L)) − 0]
= 0 + 0.5×[−1 + 0.9×0 − 0] = 0 + 0.5×(−1) = −0.5

2 t=2: State=S2, Action=Right

Observe: R=+10, next state=S3 (terminal)
Update: Q(S2,R) ← 0 + 0.5×[10 + 0.9×0 − 0] = 0 + 5 = +5

Q-table after Episode 1:

State Q(s, Right) Q(s, Left)

S1 −0.5 0

S2 +5.0 0

Episode 2 Trace
1 t=1: State=S1, Action=Right
Observe: R=−1, next=S2, max Q(S2,·)=5
Q(S1,R) ← −0.5 + 0.5×[−1 + 0.9×5 − (−0.5)] = −0.5 + 0.5×[−1+4.5+0.5] = −0.5 + 0.5×4
= +1.5

2 t=2: State=S2, Action=Right

Q(S2,R) ← 5 + 0.5×[10 + 0 − 5] = 5 + 2.5 = +7.5
Q-table after Episode 2:

State Q(s, Right) Q(s, Left)

S1 +1.5 0

S2 +7.5 0

Convergence: Over many episodes, Q(S2,Right)→9.09, Q(S1,Right)→8.18 (≈

10×γ², 10×γ). The optimal policy: always go Right from any state.

Optimal Q-values (theoretical): Q*(S2,R) = 10 (immediate) = 10. Q*(S1,R) = −1 +

0.9×10 = 8. These are approached asymptotically as episodes → ∞.

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 6.2 Limitations of Q-Learning

PYQ direct ask — know all limitations clearly:

# Limitation Explanation

1 Curse of Q-table has size |S| × |A|. For large or continuous state
Dimensionality (Q- spaces (e.g., Atari pixels → 10⁴ states), table becomes
Table) impossibly large — cannot be stored or updated.

2 Cannot handle Q-learning requires discrete actions (to compute

continuous action max_a Q(s,a)). For continuous actions (robot joints,
spaces steering angles), this breaks down.

3 Slow convergence Requires many episodes to converge. Each (s,a) pair

must be visited many times. In complex
environments, this is impractical.

4 No generalisation Q-table treats every state independently. Learning

about state S₁ tells you nothing about similar states
S₂. Cannot generalise across similar states.

5 Overestimation bias The max operator in the update rule causes

systematic overestimation of Q-values. This is
because max of noisy estimates is biased upward.

6 Exploration challenge Simple ε-greedy exploration is inefficient in large

spaces. May never visit important states if they're
hard to reach randomly.

6.3 Deep Q-Network (DQN) — How Limitations are Overcome

★ PYQ

"What are its limitations. How is it overcome?" — The answer is Deep Q-Network
(DQN).
End Sem 2024 — Q5(b) [5 marks]

Deep Q-Network (DQN) — DeepMind, 2015

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 DQN replaces the Q-table with a deep neural network that approximates
the Q-function. Input: state s (e.g., raw pixels). Output: Q(s,a) for all
actions a simultaneously.

Q(s, a; θ) ≈ Q*(s, a)
θ = neural network parameters (weights). The network is trained to

minimise loss: L(θ) = 𝔼[(Rₜ₊₁ + γ·max_a' Q(s',a';θ⁻) − Q(s,a;θ))²]

Key Innovations in DQN

Limitation
DQN Innovation How it helps
Addressed

Q-table too large Function Network compresses Q-values into

Approximation parameters θ. Works for image inputs
(Neural Network) (Atari = 84×84 pixels).

No generalisation Neural Network Similar states produce similar

generalises outputs due to shared weights. Learns
features, not just values.

Slow convergence Experience Replay Stores past transitions in a replay

/ instability buffer. Samples random minibatches
for training. Breaks temporal
correlations → stable learning.

Overestimation Target Network Separate network θ⁻ (updated less

bias frequently) to compute target values.
Prevents moving target problem —
training becomes stable.

Continuous states Convolutional layers For image-based environments, CNNs

automatically learn spatial features
from raw pixels.

Achievement: DQN achieved superhuman performance on 49 Atari games using

only raw pixels and game scores as input — the same algorithm, same
hyperparameters, for all games. This was the breakthrough that sparked
modern deep RL.

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 DQN vs Q-Learning

Standard Q-Learning Deep Q-Network (DQN)

Q-table (explicit). Discrete, small state Neural network approximation.
spaces only. No generalisation. Tabular Handles continuous high-dimensional
updates. Simple but limited. states. Generalises. Experience replay +
target network for stability.

7 Generalisation in RL & Policy Search

Generalisation in RL

Generalisation
The ability to apply knowledge from seen (state, action) pairs to unseen
ones. Without generalisation, the agent must visit every state-action pair
— infeasible in large spaces.

Achieved through function approximation:

Linear function approximation: V(s) = wᵀ · φ(s), where φ(s) are feature
vectors of state s
Neural network approximation: V(s;θ) — network learns features
automatically
Tile coding: Discretise continuous state space into overlapping tiles

Trade-off: More expressive functions generalise better but are harder to train
(more parameters, risk of instability). Simpler approximations are stable but
may be too coarse.

Policy Search / Policy Gradient

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Policy Search
Instead of learning V(s) or Q(s,a) and deriving a policy, policy search
directly optimises the policy π(a|s;θ) as a parameterised function (e.g.,
neural network). Adjusts θ to maximise expected return.

METHOD METHOD

REINFORCE (Monte Carlo Actor-Critic

Policy Gradient) Combines policy gradient with
Update policy parameters in value function learning:
direction that increases Actor: Policy π(a|s;θ) —
probability of actions that led to decides actions
high return: Critic: Value function V(s;w)
— evaluates how good states
θ ← θ + α · Gₜ · ∇θ are
log π(aₜ|sₜ;θ) Critic reduces variance of policy
gradient estimates. More stable
Intuition: If episode went well than pure REINFORCE.
(Gₜ large), increase probability of
those actions. If poor, decrease.

SARSA — On-Policy TD Control

SARSA (State-Action-Reward-State-Action)
On-policy version of Q-learning. Updates Q using the action actually taken
in sₜ₊₁ (not the max):

Q(sₜ,aₜ) ← Q(sₜ,aₜ) + α [Rₜ₊₁ +

γ·Q(sₜ₊₁,aₜ₊₁) − Q(sₜ,aₜ)]

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 aₜ₊₁ is the action actually selected in sₜ₊₁ under current policy

(not necessarily the max)

Feature Q-Learning SARSA

Policy type Off-policy On-policy

Update max_a' Q(s',a') Q(s', actual a')

uses

Learns Optimal Q regardless of Q for current behaviour policy

behaviour

Safety Can be risky (ignores Safer — accounts for

exploration) exploration risk

Cliff Finds shortest path (but may fall Takes safer longer path away
walking off cliff) from cliff

★ Quick Revision — All Key Terms + PYQ Focus

Glossary — Every Term at a Glance

Term One-line definition Formula

Policy π Agent's strategy — maps states to π(s)=a or π(a|s)=P

actions

Reward R Scalar feedback from environment Rₜ ∈ ℝ

after each action

Return G Total accumulated (discounted) Gₜ = Σ γᵏ Rₜ₊ₖ₊₁

reward from time t

Discount γ Weight on future rewards (0=myopic, 0≤γ<1

1=far-sighted)

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 Term One-line definition Formula

V(s) Expected return from state s under Vπ(s)=𝔼[Gₜ|sₜ=s]

policy π

Q(s,a) Expected return taking action a in Qπ(s,a)=𝔼[Gₜ|sₜ=s,aₜ=a]

state s

Bellman Recursive decomposition of value V(s) = max_a Σ P[R+γV(s')]

Equation function

Optimal Policy that maximises expected π*(s)=argmax_a Q*(s,a)

policy π* return from every state

TD error δ Difference between target and δ=R+γV(s')−V(s)

current estimate

Q-Learning Off-policy model-free RL using Q- Q(s,a)←Q+α[R+γ max

table + max update Q'−Q]

DQN Q-learning with neural net + Q(s,a;θ) approximation

experience replay + target net

SARSA On-policy TD control using actual Q(s,a)←Q+α[R+γQ(s',a')

next action −Q]

Passive RL Fixed policy, learn V(s) by Uses TD, ADP, Direct util.
observation

Active RL Learn both policy and values by Q-learning, SARSA

acting

ε-greedy Explore with prob ε, exploit with Balances explore/exploit

prob 1−ε

Value Sweep Bellman update until V V(s)←max_a Σ P[R+γV(s')]

Iteration converges, then extract π

Policy Alternate: evaluate current π fully, Eval + Improve until

Iteration then improve it stable

Inductive Learn general rule from specific f: X → Y from training

Learning labelled examples data

EBL Use domain theory to generalise Prior knowledge + 1

from single example example

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF
 PYQ Answers — Direct Writeup Points

★ PYQ END SEM Q5(a) — 5 marks

"Explain Policy, Discounted Reward, Bellman Equation in
context of Value Iteration"
1. Policy: Mapping from states to actions π: S→A. In value iteration, once
optimal V* is found, optimal policy is π*(s) = argmax_a Σ P(s'|s,a)[R +
γV*(s')]
2. Discounted Reward: Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + … Discount factor γ < 1
ensures convergence and models preference for sooner rewards. In
value iteration, γ scales the value of successor states.
3. Bellman Equation: V(s) = max_a Σₛ' P(s'|s,a)[R(s,a,s') + γV(s')]. This is the
update rule in value iteration — applied repeatedly until |V_new(s) −
V_old(s)| < θ for all s. Convergence guaranteed because γ < 1 →
contraction mapping.

★ PYQ END SEM Q5(b) — 5 marks

"Q-Learning with example, limitations, and how overcome"
1. Q-Learning: Model-free off-policy RL. Update rule: Q(s,a) ← Q(s,a) +
α[R + γ·max_a'Q(s',a') − Q(s,a)]. Give the grid example (S1→S2→S3).
2. Limitations: Q-table infeasible for large states; no generalisation; slow
convergence; overestimation bias.
3. Overcome by DQN: Neural network replaces table; Experience Replay
for stability; Target Network for fixed targets. Achieved superhuman
Atari performance.

Exam Tip: For 5-mark questions in Module V — write definition + formula + 1

example + significance. For Q-learning, always draw the Q-table before and
after at least 2 update steps. For Bellman equation, always write the recursive
formula and explain each symbol.

Explore our developer-friendly HTML to PDF API Printed using PDFCrowd HTML to PDF