REINFORCEMENT LEARNING

Comprehensive Study Notes

Unit Title Topics Covered

1 Introduction to Reinforcement Learning ML Paradigms | Elements of RL | History | Applications

| Limitations

2 Finite Markov Decision Processes Agent-Environment Interface | Goals & Rewards |

Returns | Policies | Value Functions | Optimality

3 Dynamic Programming Policy Evaluation | Policy Improvement | Policy Iteration

| Value Iteration | Async DP | GPI

4 Monte Carlo Methods MC Prediction | Action Values | MC Control | On/Off-

Policy | Importance Sampling

HOW TO USE THESE NOTES

YELLOW BOXES = Key Definitions & Important Formulas (must memorize)
BLUE BOXES = Formal Definitions and Mathematical Equations
GREEN BOXES = Worked Examples and Real-World Scenarios
RED BOXES = Critical Concepts and Common Mistakes
PURPLE BOXES = Algorithms and Mathematical Formulations

Each unit ends with a SUMMARY DIAGRAM — review these before exams!
All algorithms are written in pseudocode for easy understanding.

Quick Reference: RL Key Symbols

Symbol Meaning Symbol Meaning Typical Value

S Set of all states A Set of all actions Finite sets

St State at time t At Action at time t Discrete/Continuous

Rt Reward at time t Gt Return from time t Scalar values

pi Policy (strategy) pi* Optimal policy Deterministic/Stochastic

V^pi(s) State value function Q^pi(s,a) Action value function Real numbers

gamma Discount factor alpha Learning rate [0,1]

P(s'|s,a) Transition probability R(s,a) Reward function [0,1]

theta Convergence threshold epsilon Exploration rate Small positive

rho Importance sampling ratio N(s) Visit count Positive integer

 UNIT 1: INTRODUCTION TO REINFORCEMENT LEARNING

Learning Objectives: Understand the RL paradigm, its elements, history, real-world applications, and scope.

1.1 Machine Learning Paradigms

Machine Learning (ML) is broadly classified into three learning paradigms. Understanding where RL fits among
these is fundamental:

Feature Supervised Learning Unsupervised Learning Reinforcement Learning

Definition Learns from labeled input- Finds patterns in unlabeled Learns by interacting with
output pairs data environment via trial and
error

Feedback Explicit labels / correct No feedback / structure Reward signal (delayed,

answers only sparse)

Goal Predict / classify output Discover hidden structure Maximize cumulative

reward

Example Email spam detection Customer segmentation Robot learning to walk

Key challenge Overfitting / generalization Defining meaningful Exploration vs exploitation

clusters

KEY INSIGHT: What makes RL unique?

RL is the ONLY paradigm where the agent actively CHANGES the environment through its actions.
Unlike SL/UL, RL works with SEQUENTIAL decisions — each action affects future states.
RL handles the credit assignment problem: which past action caused the current reward?
Real analogy: How a baby learns to walk — no one teaches step-by-step; reward = not falling.

1.2 Elements of Reinforcement Learning

FORMAL DEFINITION
Reinforcement Learning is a computational approach to learning from interaction.
An AGENT learns to map STATES to ACTIONS to maximize a cumulative numerical REWARD signal
over time.
The agent is not told which actions to take but must discover which actions yield the most reward by
trying them.

Core Elements of RL:

Element Symbol Description Real World Example

 Agent The learner/decision Entity that perceives Chess player, robot, self-driving
maker environment and takes actions car AI

Environment Everything the agent External world that responds to Chessboard, physical world,
interacts with actions road network

State S St — state at time t Current situation/configuration Board position in chess, robot

of the environment joint angles

Action A At — action at time t Choice made by the agent that Move a piece, apply torque,
affects the state steer wheel

Reward R Rt — reward at time t Scalar feedback signal from +1 for winning, -1 for losing, -
environment 0.1 per step

Policy pi pi(a|s) or pi(s) Mapping from states to actions Always castle early in chess
— the agent's strategy opening

Value Fn V V(s) or Q(s,a) Expected cumulative reward Estimated winning probability

from a state from board position

Model P(s'|s,a), R(s,a) Agent's internal representation Knowing that rain causes
of environment (optional) slippery roads

The RL Interaction Loop (Diagrammatic Summary):

AGENT At ENVIRONMENT <--- GOAL

(Learner / Decision Maker) Action (World / Simulator) St+1 Maximize
Has: Policy pi ---> Provides: State St+1 Rt+1 SUM of
Has: Value Function V Provides: Reward Rt+1 Rewards:
Has: Model (optional) E[R1+R2+...+RT]

Fig 1.1 The Reinforcement Learning Feedback Loop — Agent takes Action At, Environment responds with new State St+1
and Reward Rt+1

CRITICAL CONCEPT: Explore vs Exploit Dilemma

EXPLOITATION: Use what you already know to maximize immediate reward.
EXPLORATION: Try new actions to discover potentially better rewards.
Example: You know a restaurant is good (exploit) BUT a new restaurant might be better (explore).
Too much exploitation => stuck in local optima. Too much exploration => low reward collected.
RL algorithms must balance BOTH — this is the fundamental challenge of RL.

1.3 Early History of Reinforcement Learning

 Era Key Figure / Event Contribution Significance

1950s Alan Turing Proposed the idea of learning machines. "Can Foundation of
machines learn?" laid groundwork for AI. Machine Learning

1954 Minsky & Clark First analog neural networks capable of First hardware RL
reinforcement-like learning (SNARC).

1959 Arthur Samuel Created self-learning Checkers program using First RL game agent
temporal difference ideas.

1960s Widrow & Hoff Developed LMS algorithm — early TD-like Gradient descent
weight update rules. ideas

1972 Minsky Published "Steps Toward Artificial Intelligence" Formal RL theory

— credit assignment problem.

1983 Sutton Formalized Temporal Difference (TD) learning Core RL algorithm

framework.

1988 Sutton Introduced TD(lambda) — unifying Monte Carlo Unified TD framework

and one-step TD.

1989 Watkins Developed Q-learning algorithm — off-policy TD Landmark RL

control. algorithm

1992 Tesauro TD-Gammon: backgammon player surpassing First superhuman RL

world champions.

1998 Sutton & Barto Published "Reinforcement Learning: An RL Bible

Introduction" textbook.

2013 DeepMind DQN: Deep Q-Network plays Atari games at Deep RL era begins
human level.

2016 DeepMind AlphaGo defeats world champion Go player Lee RL milestone

Sedol.

2017 OpenAI PPO algorithm; RL in robotics and natural Modern RL

language.

Three Threads of RL History:

RL developed from three independent research threads that eventually merged:

Trial & Error Learning -- Optimal Control & Dynamic -- Temporal Difference
(Psychology) > Programming > Learning

- Thread 1 — Psychology: Thorndike's Law of Effect (1911): actions followed by positive outcomes tend to
be repeated.
- Thread 2 — Optimal Control: Bellman's Dynamic Programming (1957): optimal decision-making through
value functions.
- Thread 3 — TD Learning: Sutton's temporal difference methods: learning from differences between
predictions.

1.4 Applications of Reinforcement Learning

GAMES & BOARD GAMES AlphaGo (Go), AlphaStar (StarCraft II), OpenAI Five (Dota 2), TD-Gammon
(Backgammon)
Key: Perfect for games with clear reward (win/lose) and simulated training
environment.

ROBOTICS Robot locomotion, manipulation, assembly, drone navigation, prosthetic limb control.
Key: RL handles continuous action spaces and physical constraints better than
classical control.

AUTONOMOUS VEHICLES Lane keeping, intersection navigation, traffic flow optimization, emergency braking
decisions.
Key: RL adapts to unseen road conditions; learns policies from simulation and real
experience.

HEALTHCARE Personalized drug dosage, treatment planning, clinical trial optimization, sepsis
management.
Key: RL optimizes sequential treatment decisions where each intervention affects
future state.

FINANCE Algorithmic trading, portfolio management, option pricing, risk management.

Key: Markets have Markov-like properties; reward = risk-adjusted profit.

NATURAL LANGUAGE Dialog systems, chatbots, text summarization, machine translation fine-tuning
PROCESSING (RLHF).
Key: RL used in RLHF (Reinforcement Learning from Human Feedback) — powers
ChatGPT!

ENERGY SYSTEMS HVAC optimization in buildings (Google DeepMind cut data center cooling by 40%),
smart grids.
Key: Continuous states and delayed rewards match RL's strengths.

RECOMMENDATION Netflix, YouTube, Spotify — sequential recommendations maximizing long-term

SYSTEMS engagement.
Key: Each recommendation affects future user behavior — inherently sequential.

REAL WORLD SPOTLIGHT: Google DeepMind + Data Centers

Problem: Google's data centers consumed enormous energy for cooling (fans, chillers).
RL Solution: DeepMind trained an RL agent with sensor data as states, cooling controls as actions.
Reward: Negative energy consumption (minimize energy = maximize reward).
Result: 40% reduction in cooling energy, 15% reduction in total data center power usage.
Why RL worked: Complex interactions between thousands of sensors make rule-based systems
ineffective.
This saved hundreds of millions of dollars and significantly reduced CO2 emissions.

1.5 Limitations and Scope of Reinforcement Learning

 LIMITATIONS SCOPE & OPPORTUNITIES

Sample Inefficiency AGI & Foundation Models

Requires millions of interactions to learn even simple RL is key to aligning large language models (RLHF in
tasks. Humans learn much faster. GPT-4, Claude).
Reward Design Scientific Discovery
Designing good reward functions is extremely difficult. Drug discovery, materials science, protein folding
Bad rewards lead to unintended behaviors (reward (AlphaFold-inspired RL).
hacking). Multi-Agent RL
Exploration vs Exploitation Multiple cooperating/competing agents — next frontier in
Balancing exploration in large state spaces is social AI.
computationally expensive. Model-Based RL
Stability & Convergence Combining RL with world models for sample-efficient
Deep RL training is notoriously unstable. Hyperparameter learning.
sensitive. Offline RL
Sim-to-Real Gap Learning from pre-collected datasets without environment
Policies trained in simulation often fail in real-world due to interaction.
distribution shift. Meta-RL
Safety Concerns Learning to learn — agents that generalize across tasks.
During exploration, agents may take dangerous actions in Hierarchical RL
real-world environments.
Breaking complex tasks into sub-tasks for efficient long-
Credit Assignment horizon planning.
Long-delayed rewards make it hard to identify which past
actions caused the reward.

Unit 1 Summary — Concept Map

REINFORCEMENT LEARNING
= Agent + Environment + Reward + Policy + Value Function
Supervised Learning (labeled data) + Unsupervised Learning (no labels) + RL (reward signal)
Applications: Games | Robotics | Healthcare | Finance | NLP | Energy | Autonomous Vehicles
Limitations: Sample inefficiency | Reward design | Safety | Stability
 UNIT 2: FINITE MARKOV DECISION PROCESSES (MDPs)

Learning Objectives: Formally define MDPs, understand state/action/reward structures, policies, value functions, and
optimality.

2.1 The Agent-Environment Interface

FORMAL DEFINITION — Finite MDP

A Finite MDP is a tuple (S, A, P, R, gamma) where:
S = Finite set of states | A = Finite set of actions
P(s'|s,a) = Transition probability: P[St+1=s' | St=s, At=a]
R(s,a,s') = Expected reward: E[Rt+1 | St=s, At=a, St+1=s']
gamma (0 to 1) = Discount factor for future rewards

The Markov Property:

MARKOV PROPERTY (Core Assumption of MDPs)

P[St+1 | St, At] = P[St+1 | S0, A0, S1, A1, ..., St, At]

Meaning: The FUTURE depends only on the PRESENT state, NOT on the history.
The current state St captures all relevant information from the past.

Counter-example of Markov Violation: A robot with a battery that drains but the state only records
position.
Fix: Include battery level in the state -> S = (position, battery_level) restores Markov property.

MDP Interaction Timeline:

MDP INTERACTION TIMELINE

t=0 t=1 t=2 t=3 ...
State: S0 --> S1 --> S2 --> S3 ...
Action: A0 --> A1 --> A2 --> A3 ...
Reward: R1 --> R2 --> R3 --> R4 ...
At each step t: Agent observes St -> takes At -> receives Rt+1 -> transitions to St+1

EXAMPLE: Grid World MDP

State S: 4x4 grid = 16 positions. Terminal states at top-left and bottom-right corners.
Action A: {UP, DOWN, LEFT, RIGHT} — 4 actions per non-terminal state.
Transition P: Deterministic (e.g., UP always moves up unless wall -> stays in place).
Reward R: -1 for every non-terminal step. +0 at terminal state. (Encourages shortest path)
Discount gamma: 1.0 (episode terminates, so undiscounted sum is fine).

At state (2,2) taking action UP: transitions to (1,2) with probability 1.0, reward = -1.
Agent goal: Reach terminal state in minimum steps to maximize reward (minimize total -1 penalties).
 2.2 Goals and Rewards

THE REWARD HYPOTHESIS

"All goals and purposes of an agent can be thought of as the maximization of the
expected value of the cumulative sum of a received scalar signal (reward)."
— Sutton & Barto

This is the CENTRAL HYPOTHESIS of RL. Everything the agent tries to achieve
must be encoded into the reward function.

Reward Signal Design Rules:

- Reward should reflect WHAT you want achieved, NOT HOW to achieve it.
- Example: For a chess agent, reward = +1 win, -1 lose, 0 draw. NOT +0.1 for capturing a piece.
- Bad reward design leads to "reward hacking" — agent finds loopholes to maximize reward without
achieving the goal.

Reward Hacking Example (Real World!)

Problem: Train a boat racing game agent to maximize score.
Intended reward: Finish the race as fast as possible.
Bad reward given: Points per ring collected (rings = score).
Agent's discovered policy: Spin in circles collecting rings WITHOUT finishing the race!
Lesson: Reward function must align with the TRUE goal, not a proxy.

2.3 Returns and Episodes

RETURN — Formal Definition

The Return Gt is the total accumulated reward from time step t onwards:

EPISODIC TASKS: Gt = Rt+1 + Rt+2 + ... + RT (finite sum to terminal state T)

CONTINUING TASKS: Gt = Rt+1 + gamma*Rt+2 + gamma^2*Rt+3 + ...

= SUM from k=0 to infinity of [gamma^k * Rt+k+1]

RECURSIVE FORM: Gt = Rt+1 + gamma * Gt+1 <-- This is KEY for DP!

gamma = 0: Agent only cares about immediate reward (myopic)

gamma = 1: Agent cares equally about all future rewards (far-sighted)
gamma in (0,1): Typical choice — balance between immediate and future

Episodic vs Continuing Tasks:

Episodic Tasks Continuing Tasks

 Termination Has a terminal state T No terminal state; runs forever

Return Finite sum (may use gamma=1) Must use gamma < 1 for finite return

Episodes Resets after each episode No reset; single continuous sequence

Examples Chess game, Maze, Atari games Robot control, Trading, Thermostat

Return formula Gt = Sum Rt+k+1 (k=0 to T-t-1) Gt = Sum gamma^k * Rt+k+1 (k=0 to inf)

Numerical Example: Computing Returns

Rewards sequence: R1=+1, R2=-1, R3=+2, R4=+3, (terminal) with gamma=0.9

G3 = R4 = 3
G2 = R3 + gamma*G3 = 2 + 0.9*3 = 2 + 2.7 = 4.7
G1 = R2 + gamma*G2 = -1 + 0.9*4.7 = -1 + 4.23 = 3.23
G0 = R1 + gamma*G1 = 1 + 0.9*3.23 = 1 + 2.907 = 3.907

Without discounting (gamma=1): G0 = 1 + (-1) + 2 + 3 = 5

With discounting (gamma=0.9): G0 = 3.907 (future rewards are worth less)

2.4 Policies and Value Functions

Policy:

POLICY DEFINITION
A Policy pi defines the agent's behavior — maps states to actions.

Deterministic Policy: pi(s) = a (one specific action per state)

Stochastic Policy: pi(a|s) = P[At=a | St=s] (probability of action a in state s)

Example (Stochastic): In state "job interview waiting room":

pi(sit quietly | waiting room) = 0.7
pi(check phone | waiting room) = 0.2
pi(pace around | waiting room) = 0.1

Value Functions:

STATE-VALUE FUNCTION V^pi(s) — Bellman Expectation Equation

V^pi(s) = E_pi[Gt | St = s]
= E_pi[Rt+1 + gamma*V^pi(St+1) | St = s]
= SUM_a pi(a|s) SUM_s' P(s'|s,a) [R(s,a,s') + gamma*V^pi(s')]

Meaning: Expected return when starting in state s and following policy pi thereafter.
V(terminal) = 0 (no future reward from terminal state)
 ACTION-VALUE FUNCTION Q^pi(s,a) — Bellman Expectation Equation
Q^pi(s,a) = E_pi[Gt | St=s, At=a]
= E_pi[Rt+1 + gamma*Q^pi(St+1, At+1) | St=s, At=a]
= SUM_s' P(s'|s,a) [R(s,a,s') + gamma * SUM_a' pi(a'|s') Q^pi(s',a')]

Meaning: Expected return when taking action a in state s, then following policy pi.
Relationship: V^pi(s) = SUM_a pi(a|s) * Q^pi(s,a)

Relationship Between V and Q (Backup Diagrams):

V^pi(s) Backup Q^pi(s,a) Backup

[State s] [State s, Action a]
pi(a|s)| P(s'|s,a)|
[a1] [a2] [a3] [s1' ] [s2' ] [s3' ]
P(s'|s,a)| pi(a'|s')|
[s'] [s'] [s'] [a'] [a'] [a']
V^pi(s) = E[R + gamma*V^pi(s')] Q^pi(s,a) = E[R + gamma*Q^pi(s',a')]

Numerical Example: Computing V^pi for Grid World

Setup: 3-state linear grid: S1 --> S2 --> S3(terminal)
Policy pi: Always move RIGHT (deterministic). Reward: -1 per step. gamma = 0.9

V^pi(S3) = 0 (terminal state)

V^pi(S2) = R + gamma * V^pi(S3) = -1 + 0.9 * 0 = -1
V^pi(S1) = R + gamma * V^pi(S2) = -1 + 0.9 * (-1) = -1 - 0.9 = -1.9

Interpretation: From S1, expected total reward following pi = -1.9 (takes 2 steps, discounted).

2.5 Optimality and Approximation

OPTIMAL VALUE FUNCTIONS & BELLMAN OPTIMALITY EQUATIONS

Optimal State-Value Function:
V*(s) = max_pi V^pi(s) for all s in S
V*(s) = max_a SUM_s' P(s'|s,a) [R(s,a,s') + gamma * V*(s')]

Optimal Action-Value Function:

Q*(s,a) = max_pi Q^pi(s,a) for all s, a
Q*(s,a) = SUM_s' P(s'|s,a) [R(s,a,s') + gamma * max_a' Q*(s',a')]

Relationship: V*(s) = max_a Q*(s,a)

Optimal Policy: pi*(s) = argmax_a Q*(s,a) = argmax_a SUM_s' P(s'|s,a)[R+gamma*V*(s')]

Key Insight — Why Optimal Policy Always Exists:

- For any finite MDP, at least one deterministic optimal policy always exists.
 - Any policy pi* that is greedy with respect to V* is an optimal policy.
- Once we have Q*(s,a), we can immediately read off the optimal action: pi*(s) = argmax_a Q*(s,a).

Approximation in RL:
In practice, exact computation of V* or Q* is infeasible for:
- Large state spaces (e.g., Go has ~10^170 possible states — larger than atoms in universe)
- Continuous state spaces (infinite states — robot arm positions)
- Solution: Use function approximation (e.g., neural networks) to approximate V*(s) ≈ V_w(s) where w are
learned weights.

Unit 2 Summary — MDP Concept Overview

Concept Formula Intuition

MDP Tuple (S, A, P, R, gamma) Complete problem specification

Return Gt = R_{t+1} + gamma*G_{t+1} Total future reward (discounted)

State Value V^pi(s) = E[Gt | St=s] How good is it to be in state s?

Action Value Q^pi(s,a) = E[Gt | St=s, At=a] How good is action a in state s?

Optimal Value V*(s) = max_pi V^pi(s) Best possible return from state s

Optimal Policy pi*(s) = argmax_a Q*(s,a) Always take the best action

Bellman Eqn (V) V^pi = R + gamma*P*V^pi Self-consistent value equations

Bellman Opt (V) V* = max_a [R + gamma*P*V*] Recursive optimality condition

 UNIT 3: DYNAMIC PROGRAMMING

Learning Objectives: Understand DP methods for solving MDPs — Policy Evaluation, Improvement, Iteration, Value
Iteration, Async DP, and GPI.

WHAT IS DYNAMIC PROGRAMMING IN RL?

Dynamic Programming (DP) = A set of algorithms to compute OPTIMAL POLICIES given a PERFECT
MODEL of the environment.

Key Requirements: (1) Complete knowledge of MDP: P(s'|s,a) and R(s,a) must be known.
(2) Finite state and action spaces.

Key Idea: Use VALUE FUNCTIONS to structure and organize the search for optimal policies.
All DP methods use the Bellman equations as iterative update rules.

Limitation: Requires a complete environment model — not practical for most real problems.
Role: Theoretical foundation — MC and TD methods approximate DP without needing a model.

3.1 Policy Evaluation (Prediction Problem)

Goal: Given a policy pi, compute V^pi(s) for all states s. This is the PREDICTION problem.

ITERATIVE POLICY EVALUATION UPDATE RULE

Vk+1(s) = SUM_a pi(a|s) SUM_s' P(s'|s,a) [R(s,a,s') + gamma * Vk(s')]

Start with V0(s) = 0 for all s

Repeatedly apply this update until |Vk+1(s) - Vk(s)| < theta (small threshold)
This is called an "expected update" — averages over all possible next states

Convergence: Guaranteed to converge to V^pi as k -> infinity (for finite MDPs, gamma < 1)

ALGORITHM: Iterative Policy Evaluation

Input: Policy pi, MDP (S, A, P, R, gamma), threshold theta > 0
Initialize V(s) = 0 for all s in S
Loop:
delta = 0
For each s in S:
v = V(s)
V(s) = SUM_a pi(a|s) SUM_s' P(s'|s,a) [R(s,a,s') + gamma*V(s')]
delta = max(delta, |v - V(s)|)
Until delta < theta
Output: V ≈ V^pi

WORKED EXAMPLE: Policy Evaluation on 4x4 Grid World

Setup: 4x4 grid, 14 non-terminal states, 2 terminal states (top-left, bottom-right).
 Policy pi: All 4 actions equally likely (pi(a|s) = 0.25 for all a).
Reward: -1 for every transition. gamma = 1.0.

After k=1 sweep:

States adjacent to terminal: V = 0.25*(-1+0) + ... = -1.0
All others: V = -1.0

After k=2 sweep:

State adjacent to terminal (1 step away): V = -1.0
State 2 steps away: V ≈ -1.75
State 3 steps away: V ≈ -2.0

As k -> inf, V^pi(s) converges to exact values ranging from -1 to -14.

Interpretation: V(s) = -(expected steps to reach terminal from s) under random policy.

3.2 Policy Improvement

Goal: Given V^pi, find a BETTER policy pi' by acting greedily with respect to V^pi.

POLICY IMPROVEMENT THEOREM

If pi and pi' are policies such that for all states s:
Q^pi(s, pi'(s)) >= V^pi(s)
Then: V^pi'(s) >= V^pi(s) for all s

Greedy Policy Improvement:

pi'(s) = argmax_a Q^pi(s,a)
= argmax_a SUM_s' P(s'|s,a) [R(s,a,s') + gamma * V^pi(s')]

If pi' = pi (no improvement possible), then pi is ALREADY OPTIMAL: pi = pi*

Proof: If Q^pi(s,pi'(s)) >= V^pi(s) but pi' = pi, then V^pi = V* (optimality conditions met).

Policy Improvement Example

State s with V^pi values for neighbors:
V(UP neighbor) = -6.0, V(DOWN neighbor) = -8.0
V(LEFT neighbor) = -5.0, V(RIGHT neighbor) = -10.0
(All deterministic transitions, R=-1, gamma=1)

Q^pi(s, UP) = -1 + V(UP) = -1 + (-6) = -7

Q^pi(s, DOWN) = -1 + (-8) = -9
Q^pi(s, LEFT) = -1 + (-5) = -6 <-- BEST!
Q^pi(s, RIGHT) = -1 + (-10) = -11

Improved policy at s: pi'(s) = LEFT (maximize Q = minimize steps to goal)

3.3 Policy Iteration

Policy Iteration alternates between Policy Evaluation and Policy Improvement until convergence to the optimal
policy pi*.

POLICY ITERATION FLOWCHART

[Initialize pi_0 randomly]
|
v
[STEP 1: Policy Evaluation] Compute V^pi_k for current policy
V0=0 -> V1 -> V2 -> ... -> V^pi (converged)
|
v
[STEP 2: Policy Improvement] pi_{k+1} = greedy(V^pi_k)
pi'(s) = argmax_a SUM P(s'|s,a)[R + gamma*V(s')]
|
v
[Check: Is pi_{k+1} = pi_k?]
NO --> Go back to STEP 1
YES --> STOP: Return pi* = pi_k (OPTIMAL!)

ALGORITHM: Policy Iteration

1. Initialize pi(s) arbitrarily for all s in S; V(s) = 0 for all s
2. POLICY EVALUATION: Iterate V(s) = SUM_a pi(a|s) SUM_s' P(s'|s,a)[R+gamma*V(s')] until
convergence
3. POLICY IMPROVEMENT:
policy_stable = true
For each s in S:
old_action = pi(s)
pi(s) = argmax_a SUM_s' P(s'|s,a) [R(s,a,s') + gamma*V(s')]
If old_action != pi(s): policy_stable = false
4. If policy_stable = true: STOP, return V and pi
Else: Go to step 2

3.4 Value Iteration

Key Idea: Instead of waiting for full policy evaluation to converge, apply ONE step of policy improvement at each
sweep. Combines evaluation and improvement into a SINGLE update.

VALUE ITERATION UPDATE RULE (Bellman Optimality Equation)

Vk+1(s) = max_a SUM_s' P(s'|s,a) [R(s,a,s') + gamma * Vk(s')]

Compare with Policy Evaluation:

Policy Eval: Vk+1(s) = SUM_a pi(a|s) SUM_s' P(s'|s,a) [R + gamma*Vk(s')] (average over pi)
Value Iter: Vk+1(s) = MAX_a SUM_s' P(s'|s,a) [R + gamma*Vk(s')] (max over all a)

Convergence: Guaranteed for gamma < 1. Extract optimal policy after convergence.
Extract pi*: pi*(s) = argmax_a SUM_s' P(s'|s,a) [R + gamma*V*(s')]

ALGORITHM: Value Iteration

 1. Initialize V(s) = 0 for all s (or any arbitrary values)
2. Loop:
delta = 0
For each s in S:
v = V(s)
V(s) = max_a SUM_s' P(s'|s,a) [R(s,a,s') + gamma*V(s')]
delta = max(delta, |v - V(s)|)
Until delta < theta
3. Output deterministic policy pi* where:
pi*(s) = argmax_a SUM_s' P(s'|s,a) [R(s,a,s') + gamma*V(s')]

WORKED EXAMPLE: Value Iteration

Setup: 3-state MDP. S={s1,s2,s3(terminal)}. gamma=0.9. R(s,a)=-1 except R(s2,RIGHT)=-1 (s2->s3).
Actions: Each state has 2 actions: LEFT (goes back) and RIGHT (goes forward).

Iteration 0: V(s1)=0, V(s2)=0, V(s3)=0

Iteration 1:
V(s2) = max[RIGHT: -1+0.9*0=−1, LEFT: -1+0.9*0=−1] = -1
V(s1) = max[RIGHT: -1+0.9*(-1)=-1.9, LEFT: -1+0.9*0=-1] = -1 (LEFT keeps at s1)
Note: V(s1,RIGHT)=-1.9 so LEFT looks better at this stage

Iteration 2:
V(s2) = max[RIGHT: -1+0.9*0=-1, LEFT: -1+0.9*(-1)=-1.9] = -1
V(s1) = max[RIGHT: -1+0.9*(-1)=-1.9, LEFT: -1+0.9*(-1)=-1.9] = -1.9

Convergence: V*(s1) = -1.9, V*(s2) = -1, V*(s3) = 0

Optimal policy: pi*(s1)=RIGHT, pi*(s2)=RIGHT (both head toward terminal).

Policy Iteration vs Value Iteration — Comparison:

Feature Policy Iteration Value Iteration

Evaluation step Full convergence (many sweeps) Single sweep (one update per state)

Speed per iteration Slow (many inner sweeps) Fast (one outer sweep)

Convergence Fewer outer iterations needed More outer iterations needed

Policy Explicit at each step Only extracted at the end

Memory V and pi stored Only V stored

Practical use When evaluation is cheap When fast iterations preferred

Update rule SUM over pi(a|s) MAX over actions

 3.5 Asynchronous Dynamic Programming

Problem with Synchronous DP: Every sweep must update ALL states before proceeding. For large state
spaces (thousands of states), each sweep is very expensive.

Asynchronous DP Solution: Update states in ANY ORDER, as many times as needed, without sweeping all
states each iteration. Can focus computation on states that matter most.

THREE TYPES OF ASYNCHRONOUS DP

1. IN-PLACE DP:
Instead of two arrays (Vold, Vnew), use a single array V.
Updates overwrite V(s) immediately — newer values used in the same sweep.
Converges faster in practice than synchronous DP.

2. PRIORITIZED SWEEPING:
Prioritize states where |Bellman error| = |V(s) - V_backup(s)| is LARGEST.
Use a priority queue to select the next state to update.
Most efficient: compute V* faster with fewer updates.

3. REAL-TIME DP (RTDP):
Update only states that are visited by the ACTUAL agent during interaction.
Focuses computation on states relevant to the agent's current experience.
Ignores irrelevant parts of the state space entirely.

Real World: Asynchronous DP in Practice

Scenario: Navigation in a large building with 1000 rooms (states).
Synchronous DP: Must update all 1000 rooms every sweep — wasteful if agent is in one wing.
Asynchronous (RTDP): Update only rooms the robot is currently navigating through.
Result: 90% reduction in computation — only rooms on the robot's path are updated frequently.
Convergence: Still guaranteed as long as all states are visited infinitely often.

3.6 Generalized Policy Iteration (GPI)

GPI DEFINITION
Generalized Policy Iteration (GPI) is the general concept of letting:
(1) Policy Evaluation: Making V consistent with the current policy pi
(2) Policy Improvement: Making pi greedy with respect to current V
interact, regardless of granularity or completeness of each process.

GPI is the UNIFYING FRAMEWORK for almost all RL algorithms!

Whether you run full evaluation or one-step TD, it's all GPI.

GENERALIZED POLICY ITERATION (GPI)

The Two Interacting Processes
 +------------------+ +------------------+
| POLICY | | VALUE |
| IMPROVEMENT | <---> | EVALUATION |
| pi = greedy(V) | | V = V^pi |
+------------------+ +------------------+
Both processes CONVERGE to the same fixed point: (pi*, V*)
Policy Iteration | Value Iteration | Monte Carlo Control | TD | Q-Learning — all are GPI!

GPI KEY INSIGHT

EVALUATION and IMPROVEMENT are COMPETING goals:
- Making V consistent with pi (evaluation) makes pi suboptimal (pi might not be greedy for new V)
- Making pi greedy w.r.t. V (improvement) makes V inconsistent (V was computed for old pi)
Yet, despite this competition, they COOPERATE and drive each other toward pi* and V*.
This is why ALL RL methods work — they're all finding the same fixed point.

Unit 3 Summary — DP Methods Hierarchy

DYNAMIC PROGRAMMING — METHODS OVERVIEW

GIVEN: Complete MDP model P(s'|s,a) and R(s,a)
PREDICTION PROBLEM (find V^pi): --> Policy Evaluation (iterative)
CONTROL PROBLEM (find pi*): --> Policy Iteration or Value Iteration
LARGE STATE SPACES: --> Asynchronous DP (In-place / Prioritized / RTDP)
UNIFYING FRAMEWORK: --> Generalized Policy Iteration (GPI)
 UNIT 4: MONTE CARLO METHODS

Learning Objectives: Understand Monte Carlo methods for prediction and control without a model — first-visit/every-
visit MC, action values, on/off-policy learning, and importance sampling.

WHAT ARE MONTE CARLO METHODS?

Monte Carlo (MC) methods learn directly from EPISODES of experience without a model of the
environment.

Key Difference from DP:

DP: Needs complete model P(s'|s,a) and R -- model-based
MC: Learns from sampled episodes (actual or simulated) -- model-FREE

Core Idea: Estimate V(s) = average of ACTUAL returns observed after visiting s
(Law of Large Numbers: as samples -> inf, average -> true expectation)

Requirements: Tasks must be EPISODIC (complete episodes needed to compute returns)

MC vs DP vs TD COMPARISON SUMMARY
DP: Model needed | Bootstraps (uses V estimates) | Full sweep of all states
MC: No model | No bootstrapping (uses actual returns) | One episode at a time
TD: No model | Bootstraps | One step at a time (online)

MC occupies the middle ground: model-free like TD, but uses full returns like DP evaluation.

4.1 Monte Carlo Prediction

Goal: Estimate V^pi(s) for all states s by averaging actual returns from episodes.

MC VALUE ESTIMATION
V(s) = (1/N(s)) * SUM of Gt for all visits to state s

Where: N(s) = number of times s has been visited

Gt = actual return from time t in each episode

Incremental Update (efficient): V(s) <- V(s) + (1/N(s)) * [Gt - V(s)]

Or with constant step size: V(s) <- V(s) + alpha * [Gt - V(s)]
(alpha = learning rate, useful in non-stationary problems)

First-Visit vs Every-Visit MC:

First-Visit MC Every-Visit MC

Definition Count state s and update V(s) only on the Count and update V(s) for EVERY visit to s in
 FIRST visit to s in each episode each episode

Bias Unbiased estimate of V^pi(s) Slightly biased (visits within episode are
correlated)

Variance Higher variance (fewer samples used) Lower variance (more samples used)

Convergence Converges to V^pi(s) as episodes -> inf Also converges to V^pi(s) as visits -> inf

When to use When state revisit within episode is common When state visits are rare; maximize data use

ALGORITHM: First-Visit Monte Carlo Prediction

Input: Policy pi, number of episodes N
Initialize: V(s) = 0 for all s; Returns(s) = empty list for all s

Loop for each episode (i = 1 to N):

1. Generate episode: S0, A0, R1, S1, A1, R2, ..., ST following policy pi
2. G = 0
3. For t = T-1, T-2, ..., 0:
a. G = gamma*G + R_{t+1}
b. If St does NOT appear in {S0, S1, ..., S_{t-1}}: [First-visit check]
- Append G to Returns(St)
- V(St) = average(Returns(St))

Output: V(s) for all s in S

WORKED EXAMPLE: First-Visit MC Prediction

Policy pi: Random walk in grid. gamma = 1.0.

Episode 1: S1->S3->S2->S4(terminal). Rewards: -1, -1, +10

G at t=2 (S2): G = 10
G at t=1 (S3): G = -1 + 1*10 = 9
G at t=0 (S1): G = -1 + 1*9 = 8
Returns: S1=[8], S3=[9], S2=[10]

Episode 2: S1->S2->S3->S4(terminal). Rewards: -1, -1, +10

G at t=2 (S3): G = 10
G at t=1 (S2): G = -1 + 10 = 9
G at t=0 (S1): G = -1 + 9 = 8
Returns: S1=[8,8], S2=[10,9], S3=[9,10]

After 2 episodes:
V(S1) = (8+8)/2 = 8.0
V(S2) = (10+9)/2 = 9.5
V(S3) = (9+10)/2 = 9.5

With more episodes, V(s) converges to true V^pi(s).

 4.2 Monte Carlo Estimation of Action Values

Why Action Values? Without a model, we cannot compute greedy policy improvement from V(s) alone (we need
P(s'|s,a)). So we estimate Q(s,a) directly.

ACTION VALUE ESTIMATION

Q(s,a) = average of returns from all episodes where action a was taken in state s

For policy improvement (model-free):

pi'(s) = argmax_a Q(s,a) [No need for transition model P!]

Vs State Values (need model for improvement):

pi'(s) = argmax_a SUM_s' P(s'|s,a) [R + gamma*V(s')] [Requires P!]

Challenge: State-action pairs (s,a) may be visited rarely -> slow convergence
Need EXPLORATION to ensure Q(s,a) is estimated for all (s,a) pairs.

Exploration Problem:
For Q(s,a) to converge, every state-action pair must be visited infinitely often.
- Problem: Deterministic greedy policy may NEVER visit (s, non-greedy action) pairs.
- Solution 1 — Exploring Starts: Start each episode at a randomly chosen (s,a) pair.
- Solution 2 — Epsilon-Soft Policy: Always maintain nonzero probability for all actions.

4.3 Monte Carlo Control

Goal: Find optimal policy pi* using MC without a model. Uses GPI framework — alternate between MC evaluation
and greedy improvement.

MONTE CARLO CONTROL (Exploring Starts)

[Initialize Q(s,a)=0, pi(s)=arbitrary for all s,a]
| Loop forever:
[STEP 1] Choose random starting (s,a), generate episode following pi
[STEP 2] For each (st,at) in episode: update Q(st,at) with observed return Gt
[STEP 3] For each st in episode: pi(st) = argmax_a Q(st, a) [Policy Improvement]
Q(s,a) -> Q*(s,a) and pi -> pi* as episodes -> infinity

ALGORITHM: MC Control with Exploring Starts

Initialize: Q(s,a) arbitrary for all s,a; pi(s) = argmax_a Q(s,a)
Returns(s,a) = empty list

Loop forever:
1. Choose S0, A0 randomly (ensuring all pairs covered = "Exploring Starts")
2. Generate episode from S0, A0 following pi: S0,A0,R1,...,ST
3. G = 0
4. For t = T-1 down to 0:
 G = gamma*G + R_{t+1}
Unless (St, At) appeared earlier in episode: [First-visit check]
Append G to Returns(St, At)
Q(St, At) = average(Returns(St, At))
pi(St) = argmax_a Q(St, a)

4.4 On-Policy and Off-Policy Learning

ON-POLICY LEARNING OFF-POLICY LEARNING

Definition Learn about and improve the SAME policy Learn about a TARGET policy while following
used to generate data a BEHAVIOR policy

Policies Single policy pi (evaluated and used for Two policies: pi=target, b=behavior
exploration)

Exploration Policy must be soft (epsilon-greedy) for Behavior policy can explore freely; target can
exploration be deterministic

Complexity Simpler implementation More complex (requires importance sampling)

Sample efficiency Less efficient (policy is forced to explore) More efficient (reuse data from any policy)

Example algo MC Control with epsilon-greedy Off-policy MC with importance sampling

Use case Online learning; single agent Learn from demonstrations; human data

On-Policy MC Control — Epsilon-Greedy Policy:

EPSILON-GREEDY POLICY (On-Policy Solution to Exploration)

pi(a|s) = 1 - epsilon + epsilon/|A(s)| if a = argmax_a Q(s,a) [greedy action]
pi(a|s) = epsilon / |A(s)| for all other actions [exploration]

Where: epsilon in [0, 1] controls exploration rate

|A(s)| = number of available actions in state s

Example: 4 actions, epsilon=0.1:

Greedy action: 1 - 0.1 + 0.1/4 = 0.925 probability
Each other action: 0.1/4 = 0.025 probability

GLIE (Greedy in Limit with Infinite Exploration):

All (s,a) visited infinitely often: SUM epsilon_k = inf
Policy converges to greedy: epsilon_k -> 0 as k -> inf
Example: epsilon_k = 1/k (decays over episodes)

Real World: On-Policy vs Off-Policy in Robotics

 Scenario: Robot arm learning to pick and place objects.

ON-POLICY approach:
Robot uses epsilon-greedy policy — mostly picks best known action but sometimes random.
Problem: Random actions (exploration) may drop or damage objects.
Policy slowly improves by balancing exploration/exploitation.

OFF-POLICY approach:
Behavior policy b: Human teleoperates robot (safe, guided exploration).
Target policy pi: Agent observes human data and learns optimal policy from it.
Advantage: Agent never takes dangerous exploratory actions; learns from human demonstrations.
Used in: Imitation learning + RL (e.g., Tesla Autopilot trained on human driving).

4.5 Importance Sampling

Problem: In off-policy MC, episodes are generated under behavior policy b, but we want to estimate values for
target policy pi. The returns are "wrong" for pi. How do we correct this?

Solution: Importance Sampling — weight each return by how likely pi would have generated that trajectory
compared to b.

IMPORTANCE SAMPLING RATIO

The ratio of probabilities of a trajectory under pi vs b:

rho_{t:T-1} = PRODUCT from k=t to T-1 of [pi(Ak|Sk) / b(Ak|Sk)]

Example: 3-step trajectory {S0,A0,S1,A1,S2,A2}:

rho = [pi(A0|S0)/b(A0|S0)] * [pi(A1|S1)/b(A1|S1)] * [pi(A2|S2)/b(A2|S2)]

Requirement: Coverage — b(a|s) > 0 whenever pi(a|s) > 0

(b must explore all actions that pi might take)

Two Types of Importance Sampling:

Feature Ordinary IS Weighted IS

Formula V(s) = SUM(rho*G) / N(s) V(s) = SUM(rho*G) / SUM(rho)

Bias Unbiased Biased (slightly)

 Variance Can be very high (unbounded) Much lower variance

Extreme case If 1 sample: returns rho*G (amplified) If 1 sample: returns G exactly (rho cancels)

Preferred? Not in practice YES — strongly preferred in practice

Convergence Unbiased but slow Faster convergence due to lower variance

ORDINARY vs WEIGHTED IMPORTANCE SAMPLING (Formulas)

Let T(s) = set of all time steps where state s is visited
rho_t = importance sampling ratio from time t to end of episode
G_t = return from time t

ORDINARY IS: V(s) = SUM_{t in T(s)} rho_t * G_t

--------------------------------
|T(s)|

WEIGHTED IS: V(s) = SUM_{t in T(s)} rho_t * G_t

--------------------------------
SUM_{t in T(s)} rho_t

Intuition for Weighted IS:

If rho >> 1 for all samples: both methods give similar results.
If only 1 sample with huge rho: Ordinary IS returns rho*G (wildly off), Weighted IS returns G.

WORKED EXAMPLE: Importance Sampling Calculation

Setup: Target policy pi: Always go RIGHT (deterministic). Behavior policy b: 50-50 random.
Episode collected under b: S1, RIGHT, R=-1, S2, RIGHT, R=+10, Terminal

Importance Sampling Ratio:

rho = [pi(RIGHT|S1)/b(RIGHT|S1)] * [pi(RIGHT|S2)/b(RIGHT|S2)]
= [1.0/0.5] * [1.0/0.5]
=2*2=4

Return from S1: G = -1 + 0.9*10 = 8 (using gamma=0.9)

Ordinary IS estimate of V^pi(S1):

V(S1) = rho * G = 4 * 8 = 32 [VERY HIGH — high variance!]

Weighted IS estimate (assuming this is the only episode):

V(S1) = (rho * G) / rho = G = 8 [Much more reasonable!]

Note: Ordinary IS is unbiased in expectation but individual estimates are extreme.

With many episodes, both converge, but weighted IS converges faster.

Off-Policy MC Control Algorithm:

 ALGORITHM: Off-Policy MC Control (Weighted IS)
Initialize: Q(s,a) = 0; C(s,a) = 0; pi(s) = argmax_a Q(s,a) (target, greedy)
b = soft/exploratory behavior policy

Loop forever:
1. Generate episode using b: S0,A0,R1,S1,A1,...,ST
2. G = 0; W = 1 (importance weight)
3. For t = T-1 down to 0:
G = gamma*G + R_{t+1}
C(St, At) += W
Q(St, At) += (W / C(St,At)) * [G - Q(St, At)]
pi(St) = argmax_a Q(St, a)
If At != pi(St): BREAK (episode diverges from target policy)
W = W * [1 / b(At|St)] (note: pi is deterministic, pi(At|St)=1)

Unit 4 Summary — Monte Carlo Methods Taxonomy

MONTE CARLO METHODS — COMPLETE TAXONOMY

PREDICTION (estimate V or Q for given pi):
First-Visit MC — unbiased; updates on first visit to each state
Every-Visit MC — biased but lower variance; updates on all visits
CONTROL (find optimal pi*):
On-Policy (Exploring Starts or epsilon-greedy) — simpler; same policy for learning and acting
Off-Policy (Importance Sampling) — behavior policy explores; target policy learns
IMPORTANCE SAMPLING:
Ordinary IS — unbiased, high variance; V(s) = SUM(rho*G) / N
Weighted IS — biased, LOW variance; V(s) = SUM(rho*G) / SUM(rho) [PREFERRED]
 MASTER SUMMARY: RL COMPLETE CONCEPT MAP

All Key Equations at a Glance:

Concept Formula Where Used

Return (discounted) Gt = Rt+1 + gamma*Rt+2 + ... = SUM gamma^k * All RL algorithms

Rt+k+1

Bellman Exp. (V) V^pi(s) = SUM_a pi(a|s) SUM_s' P[R+gamma*V^pi(s')] Policy Evaluation

Bellman Exp. (Q) Q^pi(s,a) = SUM_s' P[R+gamma*SUM_a' pi(a') MC, TD, Q-learning
Q^pi(s',a')]

Bellman Opt. (V) V*(s) = max_a SUM_s' P[R+gamma*V*(s')] Value Iteration

Bellman Opt. (Q) Q*(s,a) = SUM_s' P[R+gamma*max_a' Q*(s',a')] Q-learning

Optimal Policy pi*(s) = argmax_a Q*(s,a) All control methods

MC Value Est. V(s) <- V(s) + (1/N) * [Gt - V(s)] MC Prediction

Epsilon-Greedy pi(a|s) = 1-eps+eps/|A| (greedy); eps/|A| (others) On-Policy MC/TD

IS Ratio rho = PROD [pi(Ak|Sk) / b(Ak|Sk)] Off-Policy MC

Weighted IS V(s) = SUM(rho*G) / SUM(rho) Off-Policy MC

Policy Eval Update Vk+1(s) = SUM_a pi(a|s) SUM_s' P[R+gamma*Vk(s')] DP Prediction

Value Iter Update Vk+1(s) = max_a SUM_s' P[R+gamma*Vk(s')] DP Control

Complete RL Methods Taxonomy Diagram:

REINFORCEMENT LEARNING ALGORITHMS TAXONOMY

[RL Problem: Agent interacts with Environment seeking to maximize cumulative reward]
|
+--------------+------------------+
MODEL-BASED MODEL-FREE
(needs P, R) (learns from samples)
DYNAMIC PROGRAMMING +-------+-------+
- Policy Evaluation MONTE CARLO TD LEARNING
- Policy Iteration (Episode-based) (Step-based)
- Value Iteration - On-Policy MC - TD(0)
- Async DP - Off-Policy MC - TD(lambda)
- Importance Sampling - Sarsa / Q-Learning
UNIFYING FRAMEWORK: Generalized Policy Iteration (GPI) = Evaluation + Improvement
DEEP RL (Function Approximation): DQN | PPO | A3C | AlphaGo | ChatGPT (RLHF)
FINAL SUMMARY: When to Use Which Method?
DYNAMIC PROGRAMMING: When you have the complete MDP model (P, R). Theoretical foundation.
Use for: small, well-defined MDPs, game solving with known rules.

MONTE CARLO: When you have no model but can generate episodes.
Use for: episodic tasks, simulation environments, offline data.

ON-POLICY MC: When agent must act and learn simultaneously using same policy.

OFF-POLICY MC: When learning from demonstrations, historical data, or separate explorer.

IMPORTANCE SAMPLING: Critical for off-policy — corrects distribution mismatch between b and pi.
Weighted IS preferred over Ordinary IS for lower variance.