DSE: REINFORCEMENT LEARNING

[Link].(H) Computer Science / [Link]. / B.A. · Semester VIII · NEP UGCF 2022
5 Units 45 Hours Ref: Sutton & Barto (2018) Effective: 2024–25

UNIT 1 Chapters: Ch 1 (1.1–1.6) ■ 5 hrs

Introduction to Reinforcement Learning

What is Reinforcement Learning?

Reinforcement Learning (RL) is a type of machine learning where an agent learns to make decisions by interacting with
an environment. The agent receives rewards or penalties for its actions and aims to maximise cumulative reward over
time — without being explicitly told what to do.

Core Terminology

• Agent — The learner/decision-maker that interacts with the environment.

• Environment — Everything the agent interacts with; responds to actions and provides observations/rewards.

• State (S) — A representation of the current situation of the agent.

• Action (A) — The set of all possible moves the agent can make.

• Reward (R) — Scalar feedback signal; the goal is to maximise total reward.

• Policy (π) — The agent's strategy: mapping from states to actions (π: S → A).

• Value Function V(s) — Expected cumulative reward from state s under policy π.

• Episode — A complete sequence from start to terminal state.

RL vs Other ML Paradigms
Aspect Supervised Learning Unsupervised Learning Reinforcement Learning

Data Labelled examples Unlabelled data Interaction with environment

Feedback Correct answer given No feedback Scalar reward signal

Goal Predict output Find structure Maximise cumulative reward

Example Image classification Clustering Game playing, Robotics

Elements of RL
Policy (π) Value Function V(s)

• Deterministic: π(s) = a • Vπ(s) = E[Gt | St=s]

• Stochastic: π(a|s) = P(A=a|S=s) • Long-term reward from state s

• Maps each state to an action (or distribution) • Bellman eq.: V(s) = R + γ·V(s')

Reward Function R Bellman Equation

• R(s, a, s') → scalar signal • V(s) = Σ π(a|s) Σ P(s'|s,a)[R + γV(s')]

• Immediate feedback on action quality • Recursive relation for value functions

• Goal: maximise expected total reward • Foundation for DP, TD, MC methods
Return & Discounting
Return Gt G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + ... = Σ γ■ R_{t+k+1}

Discount factor γ 0 ≤ γ ≤ 1 (γ=0: myopic; γ=1: far-sighted)

Libraries & Tools (Python)

Library Use Case Install

gymnasium Standard RL environments (CartPole, MountainCar…) pip install gymnasium

stable-baselines3 Pre-built RL algorithms (PPO, DQN, A2C…) pip install stable-baselines3

TensorFlow / Keras Deep neural network function approximators pip install tensorflow

PyTorch Flexible deep learning for custom RL models pip install torch

numpy / matplotlib Numerical ops & plotting learning curves pip install numpy matplotlib
 Chapters: Ch 3 (3.1–3.7), Ch 4
UNIT 2 ■ 10 hrs
(4.1–4.7), Ch 5 (5.3)

Markov Decision Process & Dynamic Programming

Markov Property & MDP

A state St satisfies the Markov Property if the future is independent of the past given the present: P(St+1 | St) = P(St+1 |
S1, …, St). An MDP formalises the sequential decision-making problem.

MDP = (S, A, P, R, γ)

• S — Finite set of states

• A — Finite set of actions

• P(s'|s,a) — State transition probability

• R(s,a,s') — Expected immediate reward

• γ ∈ [0,1] — Discount factor

• Goal: Find optimal policy π* that maximises expected discounted return Gt

Bellman Optimality Equations

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

Optimal Q-value Q*(s,a) = Σ P(s'|s,a)[R(s,a,s') + γ max_a' Q*(s',a')]

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

Dynamic Programming Algorithms

Algorithm: Policy Evaluation (Iterative)

Input: policy π, threshold θ

Initialise V(s) = 0 for all s
Loop until ∆ < θ:
For each s in S:
v ← V(s)
V(s) ← Σ_a π(a|s) Σ_s' P(s'|s,a)[R + γV(s')]
∆ ← max(∆, |v - V(s)|)
Output: V ≈ V^π

Algorithm: Policy Iteration

1. Initialise π arbitrarily
2. Policy Evaluation: compute V^π
3. Policy Improvement:
For each s: π'(s) ← argmax_a Σ P(s'|s,a)[R + γV(s)]
4. If π' ≠ π: π ← π', go to step 2
5. Else: π* = π (STOP)

Algorithm: Value Iteration

Initialise V(s) = 0
Loop until ∆ < θ:
For each s:
V(s) ← max_a Σ P(s'|s,a)[R + γV(s')]
 Extract π*(s) = argmax_a Σ P(s'|s,a)[R + γV(s')]

Comparison: DP Methods
Method Updates Convergence Best For

Policy Evaluation Sweep all states Iterative until stable Compute V^π for given π

Policy Iteration Eval + Improve Faster (fewer sweeps) Finding π* (small MDP)

Value Iteration One-step lookahead Direct to V* Large state spaces

Generalised PI Interleaved eval/improve Flexible General framework

UNIT 3 Chapters: Ch 5 (5.1–5.2, 5.4) ■ 6 hrs

Monte Carlo Methods

Overview
Monte Carlo (MC) methods learn from complete episodes of experience. Unlike DP, they do not require full knowledge
of the environment (model-free). Value estimates are based on sample averages of actual returns.

First-Visit MC On-Policy Learning

• Estimate V(s) using return from FIRST visit to s in • Evaluates/improves the policy being used
each episode
• ε-greedy: π(a|s) = 1–ε for greedy, ε/|A| otherwise
• Unbiased estimator of V^π(s)
• Simpler but explores less
• Updates: V(s) ← average of G whenever s first
Off-Policy Learning
visited
• Uses behaviour policy b to generate data
Every-Visit MC
• Evaluates/improves target policy π
• Average returns from ALL visits to s
• More flexible, requires importance sampling
• Biased but consistent

• Simpler implementation

Importance Sampling
Used in off-policy MC to correct for the difference between behaviour policy b and target policy π.

IS Ratio (ρ) ρ_{t:T-1} = Π_{k=t}^{T-1} π(A_k|S_k) / b(A_k|S_k)

Ordinary IS V(s) = Σ ρ·G / n (unbiased, high variance)

Weighted IS V(s) = Σ ρ·G / Σ ρ (biased, lower variance)

Algorithm: Monte Carlo Control (On-Policy, ε-greedy)

Initialise Q(s,a) arbitrarily; policy π ← ε-greedy

Loop for each episode:
Generate episode: S0,A0,R1,...,ST using π
G ← 0
For t = T-1 down to 0:
G ← γG + R_{t+1}
Unless (St,At) appears earlier in episode:
Append G to Returns(St,At)
Q(St,At) ← average(Returns(St,At))
π(St) ← argmax_a Q(St,a) [greedy w.r.t. Q]
 Chapters: Ch 6 (6.1,6.4,6.5), Ch
UNIT 4 ■ 12 hrs
7 (7.1–7.3), Ch 12 (12.1,12.2)

Temporal Difference (TD) Learning

TD Learning Overview
TD learning combines ideas from DP (bootstrapping) and MC (model-free, sample-based). Unlike MC, TD updates occur
after each step — no need to wait for episode end.

Core Algorithms
Algorithm: TD(0) — One-step TD Prediction

Input: policy π, step-size α, discount γ

Initialise V(s) = 0 for all s
For each episode:
Initialise S
For each step t:
A ← π(S)
Take action A; observe R, S'
V(S) ← V(S) + α[R + γV(S') - V(S)] ← TD update
S ← S' (until terminal)

TD Error δt δ_t = R_{t+1} + γV(S_{t+1}) - V(S_t)

SARSA (On-Policy TD) Q-Learning (Off-Policy TD)

• Updates Q(S,A) after each step • Updates Q towards greedy next action

• Uses (S, A, R, S', A') — 5-tuple • Q(S,A) ← Q(S,A) + α[R + γ max_a' Q(S',a') -
Q(S,A)]
• Q(S,A) ← Q(S,A) + α[R + γQ(S',A') - Q(S,A)]
• Off-policy: learns optimal Q regardless of
• Converges to optimal policy for ε-greedy
exploration
• On-policy: explores with same policy
• Converges to Q* directly

• More aggressive — can diverge with function

approx.

SARSA vs Q-Learning Comparison

Property SARSA Q-Learning

Type On-Policy Off-Policy

Update Target R + γQ(S',A') R + γ max Q(S',a')

Exploration Explores via behaviour policy Learns optimal Q* regardless

Convergence To π_ε (near-optimal) To Q* (optimal)

Cliff Walking Safer path (avoids cliff) Optimal but risky path

Use case Risk-sensitive tasks General control

n-Step TD & TD(λ)

n-step Return G_{t:t+n} = R_{t+1} + γR_{t+2} + ... + γ■V(S_{t+n})

TD(λ) Return G_t^λ = (1-λ) Σ_{n=1}^∞ λ^{n-1} G_{t:t+n}

Eligibility Traces

• TD(λ) uses eligibility traces — a memory of recently visited states

• e_t(s) = γλ·e_{t-1}(s) + 1 if s=S_t, else γλ·e_{t-1}(s)

• λ=0: pure TD(0); λ=1: equivalent to MC

• Forward view (theoretical) vs Backward view (implementable with traces)

• TD(1) ≡ MC for episodic tasks with offline updates

 Chapters: Ch 9 (9.1–9.3), Ch 13
UNIT 5 ■ 12 hrs
(13.1–13.3, 13.5)

Approximation Methods & Policy Gradient

Function Approximation
Tabular methods fail for large/continuous state spaces. Function approximation parameterises V or Q with weights w:
V■(s;w) ≈ V(s). The goal is to minimise the Mean Squared Value Error (MSVE).

MSVE MSVE(w) = Σ_s µ(s) [V^π(s) - V■(s;w)]²

SGD Update w ← w + α[G_t - V■(S_t;w)] ∇V■(S_t;w)

Gradient MC Linear Approx.

• Uses full return G_t as target • V■(s;w) = w^T x(s) (x = feature vector)

• Unbiased but high variance • Guaranteed convergence in TD

• w ← w + α[G_t - V■(S_t;w)] ∇V■(S_t;w) • Least-Squares TD (LSTD): solve directly

• Convergence: global minimum for linear approx. Nonlinear (DNN)

Semi-Gradient TD(0) • V■(s;w) = neural_network(s; w)

• Bootstrap: target = R + γV■(S';w) • DQN: combines Q-learning + deep networks

• Target depends on w — not true gradient • Experience replay + target network for stability

• w ← w + α·δ_t·∇V■(S_t;w)

• Faster but may diverge with nonlinear approx.

Policy Gradient Methods

Instead of learning a value function, policy gradient methods directly optimise the policy π_θ parameterised by θ. The
objective J(θ) = V^{π_θ}(s0) is maximised via gradient ascent.

Policy Gradient Theorem ∇J(θ) ∝ Σ_s µ(s) Σ_a Q^π(s,a) ∇π(a|s;θ)

Algorithm: REINFORCE (Naive Policy Gradient)

Input: π_θ (differentiable policy), step-size α

Loop forever:
Generate episode: S0,A0,R1,...,ST using π_θ
For each t = 0 to T-1:
G ← Σ_{k=t+1}^{T} γ^{k-t-1} R_k (return from t)
θ ← θ + α γ^t G ∇ln π(A_t|S_t;θ) ← gradient ascent

Variance Reduction
Baselines & Advantage Function

• REINFORCE has high variance due to Monte Carlo returns.

• Baseline b(s): subtract from return to reduce variance without introducing bias.

Update: θ ← θ + α(G_t - b(S_t)) ∇ln π(A_t|S_t;θ)

• Common baseline: V■(S_t;w) (current value estimate)

• Advantage Function: A(s,a) = Q(s,a) - V(s) — how much better is action a vs average?

• Using A reduces variance significantly while keeping the update unbiased.

Actor-Critic Methods
Actor Critic

• Parameterised policy π_θ(a|s) • Parameterised value function V■_w(s)

• Updated via policy gradient • Updated via TD error δ

• Uses critic's value estimate as baseline • δ = R + γV■(S';w) - V■(S;w)

• θ ← θ + α_θ δ ∇ln π(A|S;θ) • w ← w + α_w δ ∇V■(S;w)

Introduction to Deep RL
Key Deep RL Algorithms

• DQN (Deep Q-Network): Q-learning + CNN, experience replay, target network

• A3C/A2C: Asynchronous/Advantage Actor-Critic — parallel workers collect experience

• PPO (Proximal Policy Optimisation): Clips policy update for stability; most widely used

• SAC (Soft Actor-Critic): Entropy-regularised; excellent for continuous action spaces

• DDPG: Deterministic policy gradient for continuous actions; off-policy actor-critic

 PRACTICAL LIST

Dynamic Programming — Policy Evaluation

1 Environment: GridWorld, Blackjack, WindyGridWorld

Dynamic Programming — Policy Iteration

2 Environment: GridWorld, Blackjack, WindyGridWorld

Dynamic Programming — Value Iteration

3 Environment: GridWorld, Blackjack, WindyGridWorld

Monte Carlo Prediction

4 Environment: GridWorld, Blackjack, WindyGridWorld

Off-Policy MC Control with Importance Sampling

5 Environment: GridWorld, Blackjack, WindyGridWorld

SARSA — On-Policy TD Learning

6 Environment: GridWorld, Blackjack, WindyGridWorld

Q-Learning — Off-Policy TD Learning

7 Environment: GridWorld, Blackjack, WindyGridWorld

Policy Gradient REINFORCE Algorithm

8 Environment: CartPole, CartPoleRaw

Policy Gradient Actor-Critic Algorithm

9 Environment: CartPole, CartPoleRaw

REFERENCES
[1] Richard S. Sutton & Andrew G. Barto — Reinforcement Learning: An Introduction, 2nd Ed., MIT Press, 2018.

[2] Enes Bilgin — Mastering Reinforcement Learning with Python, 1st Ed., Packt Publishing, 2020.