Reinforcement Learning Notes

Lecture Notes for CSCI 6904 (Deep Reinforcement Learning)

August 19, 2025

Contents
1 Formalization of the RL Problem 6
1.1 Markov Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Markov Decision Process (MDP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Goals and Rewards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Reward Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Reward Representation Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Discount Rate γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Returns and Episodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.1 Problem (Important) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.2 Problem (Important) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Partially Observable MDP (POMDP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Major Components of an RL Agent 9

2.1 Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Value Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Optimal Value Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Bellman Expectation Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Optimality in the Bellman Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Recap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.7 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.8 Categorizing RL Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Introduction to Policy Gradient Methods 11

3.1 Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Policy Gradients for One-Step MDPs / Contextual Bandits 12

4.1 Algorithm (∼ REINFORCE for one-step) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Step-by-Step Derivation of the Policy Gradient (Very important) . . . . . . . . . . . . . . 13

5 Policy Gradients for Multi-Step MDPs 14

5.1 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.2 Policy Gradient Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.3 REINFORCE Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.4 REINFORCE with Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.4.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1
6 Off-Policy Policy Gradients 15
6.1 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.3 Off-Policy REINFORCE with Importance Sampling . . . . . . . . . . . . . . . . . . . . . . 15

7 Case Study: Dialog Systems like ChatGPT 16

7.1 Training Phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.2 Reinforcement Learning with Human Feedback (RLHF) . . . . . . . . . . . . . . . . . . . . 16

8 Actor-Critic Methods 17
8.1 Recap: Policy Gradient Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8.1.1 Monte-Carlo Policy Gradient (REINFORCE) . . . . . . . . . . . . . . . . . . . . . 17
8.1.2 REINFORCE with Baseline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8.2 Actor-Critic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8.2.1 Core Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8.2.2 Advantage Actor-Critic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.2.3 (Batch) Advantage Actor-Critic Algorithm . . . . . . . . . . . . . . . . . . . . . . 18
8.2.4 Network Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9 Dynamic Programming (DP) 19

9.1 Bellman Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.2 Iterative Policy Evaluation (Prediction) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.3 Policy Iteration (Control) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
9.4 Value Iteration (Control) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

10 Asynchronous Dynamic Programming 20

10.1 Synchronous Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
10.2 Asynchronous Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
10.2.1 In-Place Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
10.2.2 Prioritized Sweeping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
10.2.3 Real-Time Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

11 Model-Free Prediction 22
11.1 Monte-Carlo (MC) Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.2 Temporal-Difference (TD(0)) Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.3 n-Step TD Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

12 Unified View 22

13 TD(λ): Simple Example with λ = 1/2 23

13.1 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
13.2 Easy Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

14 Model-Free Control 24
14.1 On-Policy Monte Carlo (MC) Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
14.1.1 Concept: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
14.2 Sarsa (On-Policy TD Control) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
14.3 Q-Learning (Off-Policy TD Control) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
14.4 n-Step Sarsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
14.5 Practical Considerations (All Methods) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
14.6 Algorithm Boxes (Tabular) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2
 14.7 Conceptual Differences Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

15 Deep Q-Networks and DDQN (DQN) 29

15.1 Deep Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
15.2 DQN Algorithm (with Experience Replay and Target Network) . . . . . . . . . . . . . . . 29
15.3 Double DQN: Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
15.4 Prioritized Experience Replay Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
15.5 Improvements to DQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
15.5.1 Why N-step Returns Don’t Work Simply in DQN . . . . . . . . . . . . . . . . . . . 30

16 Continuous Control with Q-Learning 31

16.1 Why DQN Fails for Continuous Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.2 Action Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.2.1 Random Shooting Method For DQN . . . . . . . . . . . . . . . . . . . . . . . . . . 31
16.3 Stochastic Optimization (CEM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
16.4 Deep Deterministic Policy Gradient (DDPG) . . . . . . . . . . . . . . . . . . . . . . . . . . 32
16.4.1 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
16.5 TD3 - (Not needed for exam) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
16.5.1 Algorithm (Simplified) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
16.6 DDPG vs. TD3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

17 Offline Reinforcement Learning 34

17.1 What is Offline RL? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
17.2 How is Offline RL Possible? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
17.3 Why is Offline RL Hard? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
17.4 Policy Constraint Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
17.5 Conservative Q-Learning (CQL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
17.5.1 CQL Algorithm Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
17.6 Additional Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

18 Actor-Critic Methods - Part 3 36

18.1 Batch Advantage Actor-Critic (A2C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
18.1.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
18.2 PPO - Broken Versions Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
18.3 Trust Region Policy Optimization (TRPO) . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
18.4 Proximal Policy Optimization (PPO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
18.4.1 PPO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

19 Off-Policy Actor-Critic Methods 38

19.1 Online Actor-Critic (On-Policy) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
19.2 Why Off-Policy Actor-Critic? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
19.3 Off-Policy Actor-Critic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
19.4 Deep Deterministic Policy Gradient (DDPG) . . . . . . . . . . . . . . . . . . . . . . . . . . 39
19.4.1 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

20 Soft Actor-Critic (SAC) 41

20.1 Maximum Entropy Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 41
20.2 Soft Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
20.3 SAC Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3
21 Model-Based Reinforcement Learning 42
21.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
21.1.1 Model-Free vs. Model-Based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
21.2 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
21.2.1 Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
21.2.2 Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

22 Model Learning 43
22.1 Types of Dynamics Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
22.2 Combining Model-Free RL with a Model - Background Planning . . . . . . . . . . . . . . . 43
22.2.1 Model-Based RL: Broken → Fixed Progression (MBPO) . . . . . . . . . . . . . . . 44
22.2.2 Dyna-Q Style Algorithm - MBPO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
22.2.3 Direct Policy Learning with a Model . . . . . . . . . . . . . . . . . . . . . . . . . . 45

23 Model Based - Decision-Time Planning 46

23.1 Stochastic Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
23.2 Monte Carlo Tree Search (MCTS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
23.3 Model-Based RL with Decision-Time Planning . . . . . . . . . . . . . . . . . . . . . . . . . 47
23.4 Uncertainty in RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
23.4.1 Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
23.4.2 In Model-Based RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
23.4.3 Mitigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
23.5 Uncertainty in Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
23.5.1 Estimate model uncertainty (how unsure the parameters are) . . . . . . . . . . . . . 48
23.5.2 Bootstrap Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
23.5.3 Bayesian Neural Networks (BNNs) . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
23.6 Latent Space Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

24 Safe Reinforcement Learning 49

24.1 Overview of Safety Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
24.2 Constrained Markov Decision Processes (CMDP) . . . . . . . . . . . . . . . . . . . . . . . 50
24.2.1 Machiavelli Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
24.2.2 Optimally Safe Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
24.3 Solving CMDPs: Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
24.3.1 Constrained Policy Optimization (CPO) . . . . . . . . . . . . . . . . . . . . . . . . 50
24.3.2 Primal-Dual Methods (Lagrangian) . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
24.3.3 State Augmentation (SauteRL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
24.3.4 Action Selection (MASE) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
24.4 Frontiers in Safe RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

25 Exploration in RL 54
25.1 Random Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
25.2 Novelty Seeking Exploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
25.3 Posterior Sampling Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

26 Transfer Learning in RL 55
26.1 Domain Adaptation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
26.2 Domain Randomization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
26.3 Multi-Task Transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4
27 Frontiers in RL 56
27.1 Meta-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
27.2 Inverse Reinforcement Learning (IRL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
27.3 Hierarchical RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
27.4 Foundation Models for RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
27.5 Continual RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

28 Sample Question and Answer 56

5
1 Formalization of the RL Problem
1.1 Markov Property
A state St is Markov if p(St+1 | St ) = p(St+1 | S1 , . . . , St ). This means the future is conditionally
independent of the past, given the present state.
Or
The Markov property, also known as the “memoryless property”, is a characteristic of stochastic processes
where the future state of a system depends only on its current state, not on its past history.

1.2 Markov Decision Process (MDP)

An MDP is defined as a tuple ⟨S, A, P, R, γ⟩ where:

• S: The set of states.

• A: The set of actions.

• P : The state-transition probability matrix, where p(s′ |s, a) = Pr{St = s′ | St−1 = s, At−1 = a}.

• R: The reward function, where r(s, a) = E[Rt | St−1 = s, At−1 = a].

• γ ∈ [0, 1]: The discount rate.

Goal: Find the optimal policy π ∗ (a|s) = arg maxπ Eπ [Rt+1 + γRt+2 + γ 2 Rt+3 + · · · | St = s].

1.3 Goals and Rewards

Rewards define the objective of the problem. A policy’s goal is to maximize the expected cumulative
discounted rewards over time.

1.3.1 Reward Hypothesis

“Reward Hypothesis” states that:

“That all of what we mean by goals and purposes can be well thought of as the maximization
of the expected value of the cumulative sum of a received scalar signal (called reward).”

This foundational perspective frames reinforcement learning as a way to encode objectives through
appropriate design of the reward function.

1.3.2 Reward Representation Strategies

Two common approaches for encoding task objectives in RL are:

• Goal-Reward Representation: The agent receives a positive signal (e.g., +1) only upon success-
fully reaching the goal state; all other transitions yield zero reward.

– Pros: Encourages direct focus on achieving the goal.

– Cons: Rewards are sparse ⇒ learning signal is weak; high probability the agent never stumbles
upon the goal during exploration.

• Action-Penalty Representation: The agent receives a constant negative penalty (e.g., −1) for
each non-terminal action, with zero reward at the goal state.

6
 – Pros: Provides a denser learning signal pushing the agent toward shorter paths.
– Cons: Poorly balanced penalties may discourage exploration; in some cases, the agent may
prefer early termination or fail to reach the goal at all if penalties outweigh sparse terminal
rewards.

Both schemes highlight the central challenge of reward design: a misspecified objective can lead to ineffec-
tive or unintended behavior, despite the reward hypothesis being conceptually sound.

1.4 Discount Rate γ

The discount rate γ controls the preference for immediate versus future rewards. A value of γ = 0 results
in a myopic agent that only considers immediate rewards, while γ = 1 makes the agent treat all future
rewards equally, assuming the task eventually terminates.

1.5 Returns and Episodes

The return Gt is the total discounted reward from time step t. It is defined as:
• For continuing tasks: Gt = ∞ k
P
k=0 γ Rt+k+1 .
PT −t−1 k
• For episodic tasks: Gt = k=0 γ Rt+k+1 , where T is the terminal time step.
The return can be expressed recursively as Gt = Rt+1 + γGt+1 , with GT = 0.

Why the discounted return Gt is finite in continuing tasks

1. What are we worried about? The return is an infinite sum:

Gt = Rt+1 + γRt+2 + γ 2 Rt+3 + · · ·

Since the task does not terminate, we must ensure this sum does not diverge.

2. Why does discounting help? Each later reward is multiplied by γ k . If 0 ≤ γ < 1, the factors
1, γ, γ 2 , . . . shrink to 0, so later terms contribute less and less.

3. Bounding the rewards Assume rewards are bounded: |Rt | ≤ Rmax for all t.

4. Compare with a simpler “worst case” If every reward took its largest magnitude Rmax , then

Gt ≤ Rmax 1 + γ + γ 2 + γ 3 + · · · .

5. Why does the geometric series converge? For 0 ≤ γ < 1,

1
1 + γ + γ2 + · · · = .
1−γ
If γ = 1, the terms never shrink, and the sum goes infinite.

6. Therefore
Rmax
|Gt | ≤ ,
1−γ
which is finite. Hence the discounted return Gt is finite in continuing tasks.

7
Intuition. Discounting makes later rewards smaller; bounded rewards prevent any term from being too
large. Summing many shrinking, bounded terms yields a finite result (e.g., 1 + 12 + 14 + · · · = 2).

1.5.1 Problem (Important)

Question: Given a discount factor γ = 0.8 and a reward sequence where R1 = 5 and Rt = 10 for all t ≥ 2.
Find the return from time 0, G0 .

Step-by-Step Solution
1. Define the return formula: The return from time 0 is given by the discounted sum of all future
rewards:
G0 = R1 + γR2 + γ 2 R3 + γ 3 R4 + . . .

2. Substitute the given rewards and discount factor:

G0 = 5 + (0.8)(10) + (0.8)2 (10) + (0.8)3 (10) + . . .

3. Separate the first term and factor out the reward from the remaining terms:

G0 = 5 + 10 0.8 + (0.8)2 + (0.8)3 + . . .

The terms inside the parentheses form a geometric series.

4. Sum the geometric series: The sum of an infinite geometric series of the form x + x2 + x3 + . . .
x
where |x| < 1 is 1−x . In this case, x = 0.8.

0.8 0.8
Sum = = =4
1 − 0.8 0.2

5. Calculate the total return: Substitute the sum of the geometric series back into the equation for
G0 :
G0 = 5 + 10 × 4 = 5 + 40 = 45

1.5.2 Problem (Important)

Given a discount factor γ = 0.8, a sequence of rewards R1 = −3, R2 = 5, R3 = 2, R4 = 7, and R5 = 1.
The terminal time is T = 5, which means there are no future rewards after time 5, so G5 = 0. Calculate
the return from time 0, G0 , using the relationship Gt = Rt+1 + γGt+1 .

Step-by-Step Solution
1. Start from the terminal state and work backward: The terminal return is given as G5 = 0.

2. Calculate G4 : Using the formula G4 = R5 + γG5 :

G4 = 1 + (0.8)(0) = 1

3. Calculate G3 : Using the formula G3 = R4 + γG4 :

G3 = 7 + (0.8)(1) = 7.8

8
 4. Calculate G2 : Using the formula G2 = R3 + γG3 :
G2 = 2 + (0.8)(7.8) = 2 + 6.24 = 8.24

5. Calculate G1 : Using the formula G1 = R2 + γG2 :

G1 = 5 + (0.8)(8.24) = 5 + 6.592 = 11.592

6. Calculate G0 : Using the formula G0 = R1 + γG1 :

G0 = −3 + (0.8)(11.592) = −3 + 9.2736 = 6.2736

1.6 Partially Observable MDP (POMDP)

A POMDP is a generalization of an MDP defined as a tuple ⟨S, A, O, P, R, E, γ⟩, which includes a set of
observations O and an emission probability E, defined as p(ot | st ). In a POMDP, the agent’s policy is
based on observations, π(a|o), rather than states.

2 Major Components of an RL Agent

2.1 Policy
An agent’s behavior maps states to actions.
• Deterministic: a = π(s).
• Stochastic: π(a|s) = p(a|s).

2.2 Value Function

Prediction of expected return.
P∞
• State-value: vπ (s) = Eπ [Gt | St = s] = Eπ [ k=0 γ k Rt+k+1 | St = s].
• Action-value (Q-function): qπ (s, a) = Eπ [Gt | St = s, At = a].
If we represent Vπ (s) in terms of Q value, then:
X
Vπ (s) = π(a|s)Qπ (s, a)]
a

Bellman Equation
The Bellman equation relates a state’s value to its immediate reward and the discounted value of the next
state.
For a policy π (state-value form):
X X
Vπ (s) = π(a|s) P (s′ |s, a)[R(s, a, s′ ) + γVπ (s′ )]
a s′

Meaning:
• Weight actions by policy probability.
• Weight next states by transition probability.
• Add immediate reward + discounted future value.

9
2.3 Optimal Value Function
For optimal V∗ (s): X
V∗ (s) = max P (s′ |s, a)[R(s, a, s′ ) + γV∗ (s′ )]
a
s′

Replace sum over actions with max for best choice.

2.4 Bellman Expectation Equation

The Bellman expectation equation for the state-value function Vπ (s) is:

Vπ (s) = Eπ [Rt+1 + γVπ (St+1 ) | St = s]

Here, the expectation operator Eπ represents an average over actions selected by the policy π and the
subsequent next states produced by the environment’s dynamics. It can be conceptually understood as
answering the question: “On average, if I follow policy π from this state, what will I get?”

2.5 Optimality in the Bellman Equation

The relationship between prediction and control problems is central to Reinforcement Learning:

• Prediction problem: Given a policy π, find its value function Vπ .

• Control problem: Find the optimal policy π∗ that maximizes the return.

The Bellman optimality equation is what we solve to find the optimal value function V∗ :
 
V∗ (s) = max E Rt+1 + γV∗ (St+1 ) | St = s, At = a
a

Once we have the optimal value function V∗ , the optimal policy π∗ can be found by acting greedily with
respect to it: X
P (s′ |s, a) R(s, a, s′ ) + γV∗ (s′ )
 
π∗ (s) = arg max
a
s′

2.6 Recap
• Bellman expectation: value = average reward + average future value under π.

• Bellman optimality: value = best reward + best future value possible.

2.7 Model
An agent’s representation of its environment.

• Dynamics: p(s′ , r|s, a) = Pr{St+1 = s′ , Rt+1 = r | St = s, At = a}.

• State transition: p(s′ |s, a).

• Reward: r(s, a) = E[Rt+1 | St = s, At = a].

10
2.8 Categorizing RL Agents
• Policy-based: A policy, but no value function.
• Value-based: A value function, with an implicit policy.
• Actor-Critic: Both a policy and a value function.
• Model-free: Learns policy or value function, but no model. Learns directly from experience without
building model of the environment.
• Model-based: A policy or value function, plus a model. Learns the p(s′ , r|s, a) (state transition
probability and the reward) and uses it for planning.
Category Core Idea How It Works Pros Cons
Policy-based Learn the pol- Use gradients to ad- Handles continuous Can be sample-
icy directly just policy parame- actions well; learns inefficient and
(e.g., RE- ters, often with ran- varied strategies. unstable.
INFORCE, domness.
PPO).
Value-based Learn a value Update values (like Efficient for discrete Struggles with con-
function, Q-values) and act tasks; stable targets. tinuous actions; risk
pick best greedily. of overestimation.
actions (e.g.,
DQN, Double
DQN).
Actor-Critic Combine pol- Actor chooses ac- Merges strengths of Coupled training can
icy and value tions, critic evaluates both; handles contin- be unstable; needs
function (e.g., them. uous actions well. careful tuning.
A2C, SAC).
Model-free Learn from Learn policy/values Simple and robust Needs lots of data; no
direct experi- via trial and error. when modeling is lookahead planning.
ence only (e.g., hard.
PPO, DQN).
Model-based Learn/use envi- Simulate future steps Efficient; allows long- Model errors can
ronment model to improve. term planning. mislead; hard to
(e.g., Dyna-Q, learn accurate mod-
Dreamer). els.

3 Introduction to Policy Gradient Methods

Policy gradient method means it directly optimizes the policy by taking steps in the direction of the
gradient of some objective function.

3.1 Policy
The parameterized policy is defined as: π(a|s, θ) = Pr(At = a | St = s, θt = θ).
h(s,a,θ)
• Discrete Actions: A softmax policy, where π(a|s, θ) = Pe h(s,b,θ) , and h(s, a, θ) is a numerical
be
preference for action a.
• Continuous Actions: A Gaussian policy, where the action is sampled from a normal distribution,  
2
a ∼ N (µ(s, θ), σ 2 (s, θ)). The probability density function is given by π(a|s, θ) = σ (s)1√2π exp − (a−µθ (s))
2
2σ (s)
.
θ θ

11
3.2 Objective
The objective is to find the parameter θ that maximizes the expected return J(θ), which is defined as:
.
J(θ) = Eπθ [Gt | St = s0 ] = vπθ (s0 )

Policy gradient methods achieve this by using an iterative update rule, often referred to as Gradient
Ascent:
θt+1 = θt + α∇θ J(θt )

4 Policy Gradients for One-Step MDPs / Contextual Bandits

One-step MDPs are defined as a process where an agent:

• Starts in a state s sampled from a distribution d(s).

• Takes an action a sampled from the policy πθ (a|s).

• Receives a reward r = Rs,a and the episode terminates.

Example: An online ad system

• States = user contexts: {sports-fan, tech-enthusiast, foodie}.

• The platform sees users with frequencies: d(sports) = 0.5, d(tech) = 0.3, d(foodie) = 0.2 (this is
d(s)).

• Each time a user arrives:

– The system observes s sampled from d(s).

– Chooses an ad (action).
– Gets a click/no-click reward.
– The interaction ends.

The objective is to maximize the expected reward, given by:

X X
J(θ) = Eπθ [r] = d(s) πθ (a|s)Rs,a
s a

The policy gradient is then calculated as:

1 X
∇θ J(θ) = Eπθ [∇θ log πθ (a|s) · r] ≈ ∇θ log πθ (Ai |Si ) · RSi ,Ai
N i

The policy parameters are updated using a gradient ascent rule:

θ ← θ + α∇θ J(θ)

This approach differs from Supervised Learning (SL) Maximum Likelihood in that the RL update is
weighted by the reward r, whereas the SL update is an unweighted average.

12
4.1 Algorithm (∼ REINFORCE for one-step)
1. Run the policy: Sample a state s ∼ d(s) and an action a ∼ πθ (a|s).

2. Compute the gradient estimate: ∇θ J(θ) = N1 i ∇θ log πθ (Ai |Si )RSi ,Ai .
P

3. Update the policy parameters: θ ← θ + α∇θ J(θ).

4.2 Step-by-Step Derivation of the Policy Gradient (Very important)

1. Objective Function: Expected Reward
We want to maximize the expected reward under the current policy:
X X
J(θ) = Eπθ [r] = d(s) πθ (a|s)Rs,a (1)
s a

Here:

• d(s) is the distribution over states.

• πθ (a|s) is the probability of taking action a in state s under policy parameters θ.
• Rs,a is the reward received when taking action a in state s.

2. Taking the Gradient

We want to compute the gradient ∇θ J(θ) so we can improve the policy using gradient ascent.
X X
∇θ J(θ) = d(s) ∇θ πθ (a|s)Rs,a (2)
s a

Note: d(s) and Rs,a do not depend on θ, so they are treated as constants.

3. Using the Log Derivative Trick

Start with the chain rule. We want the gradient of a log:
1
∇θ log πθ (a|s) = ∇θ πθ (a|s)
πθ (a|s)

Now multiply both sides by πθ (a|s):

πθ (a|s)∇θ log πθ (a|s) = ∇θ πθ (a|s)

∇θ πθ (a|s) = πθ (a|s)∇θ log πθ (a|s) (3)

Plug this into our gradient:
X X
∇θ J(θ) = d(s) πθ (a|s)∇θ log πθ (a|s)Rs,a (4)
s a

4. Writing as an Expectation
This can now be written as an expectation over samples (s, a) ∼ d(s)πθ (a|s):

∇θ J(θ) = Eπθ [∇θ log πθ (a|s) · r] (5)

13
Interpretation
This is the policy gradient formula for a one-step MDP:
• It tells us to increase the log-probability of actions that result in high reward.
• This is REINFORCE, simplified to the contextual bandit case.

5 Policy Gradients for Multi-Step MDPs

5.1 Objective
The objective is to maximize the expected return from a starting state, which is equivalent to the state-
value function:
J(θ) = Eπθ [Gt | St = s0 ] = vπθ (s0 )

5.2 Policy Gradient Theorem

The policy gradient theorem provides a way to compute the gradient of the objective function:
∇θ J(θ) ∝ Eπθ [∇θ log πθ (a|s) · qπ (s, a)]
This is often approximated with the Monte Carlo return Gt :
∇θ J(θ) ≈ Eπθ [∇θ log πθ (a|s) · Gt ]
This replaces the instantaneous reward with a long-term value qπ (s, a) to guide learning.

5.3 REINFORCE Algorithm

1. Sample trajectories {τi } from the policy πθ .
PT
2. For each time step t in a trajectory, compute the return Git = k=t+1 γ k−t−1 Rki .
3. Estimate the policy gradient:
N Ti
1 XX
∇θ J(θ) ≈ ∇θ log πθ (Ait |Sti )Git
N i=1 t=1

4. Update the policy parameters: θ ← θ + α∇θ J(θ).

Note: This algorithm encourages good trajectories by increasing the probability of actions that lead to
high returns.
• Discrete actions: Use a softmax policy.
• Continuous actions: Use a Gaussian policy.
This method suffers from high variance in gradient estimates.

5.4 REINFORCE with Baseline

A baseline b(s) (e.g., the state-value function v(s)) can be subtracted from the return to reduce variance
without changing the expected value of the gradient.
∇θ J(θ) ∝ Eπθ [∇θ log πθ (a|s) · (qπ (s, a) − b(s))]

14
5.4.1 Algorithm
1. Sample trajectories {τi } from πθ .

2. Compute returns Git .

3. Estimate the policy gradient using a learned state-value function v̂w (s) as the baseline:
N Ti
1 XX
∇θ J(θ) ≈ ∇θ log πθ (Ait |Sti )(Git − v̂w (Sti ))
N i=1 t=1

4. Update the policy parameters: θ ← θ + αθ ∇θ J(θ).

5. Define the value function loss:

N Ti
1 XX
L(w) = (Git − v̂w (Sti ))2
N i=1 t=1

6. Update the value function parameters: w ← w − αw ∇w L(w).

6 Off-Policy Policy Gradients

6.1 Concepts
• On-policy methods learn a policy from experience collected by that same policy.

• Off-policy methods learn a target policy π using data generated by a different behavior policy µ.

Off-policy learning offers key advantages: it can reuse old data, allows the agent to learn an optimal policy
while actively exploring with a different behavior policy, and enables learning about multiple policies
simultaneously.

6.2 Importance Sampling

Importance sampling is a technique that allows us to estimate the expected value of a function under one
distribution, using samples from another. This is the core of off-policy policy gradients.
 
p(x)
Ex∼p [f (x)] = Ex∼q f (x)
q(x)
p(x)
The term q(x)
is the importance sampling weight, which corrects for the difference between the two distri-
butions.

6.3 Off-Policy REINFORCE with Importance Sampling

This method adapts REINFORCE to an off-policy setting by using importance sampling. It allows the
algorithm to learn from data collected by an older policy, πθold . The gradient is estimated using the
importance sampling weight to correct for the change in policy:
N Ti
1 XX πθ (Ait |Sti )
∇θ J(θ) ≈ ∇θ log πθ (Ait |Sti )Git
N i=1 t=1 πθold (Ait |Sti )

15
The parameters are then updated:
θ ← θ + α∇θ J(θ)
After the update, the old policy is replaced by the new one:

θold ← θ

This approach is notably used in algorithms like Proximal Policy Optimization (PPO), which is essential
for training large language models like those in ChatGPT. PPO clips the importance sampling weight to
prevent excessively large updates, which helps stabilize learning.

7 Case Study: Dialog Systems like ChatGPT

7.1 Training Phases
The development of advanced dialog systems like ChatGPT typically follows three key phases:

1. Pretraining (LM): A large language model (LM) is first pretrained on a vast corpus of text to
learn language patterns and predict the next token.

2. Instruction Finetuning (SL): The pretrained model is then finetuned on a dataset of high-quality
instructions and responses using supervised learning (SL) to better follow directions.

3. Reinforcement Learning with Human Feedback (RLHF): The model is further aligned with
human preferences using reinforcement learning.

7.2 Reinforcement Learning with Human Feedback (RLHF)

RLHF leverages policy gradients to refine the model’s behavior based on human input. The process
involves:

1. Response Sampling: The policy πθ generates a response (action a) to a given prompt (state s).

2. Human Feedback: Human labelers provide feedback on the responses, often by ranking them.

3. Reward Model Training: A separate reward model, rψ (s, a), is trained to predict the human
preference score for any response, learning from the collected rankings.

4. Policy Update: The policy is updated using a policy gradient algorithm with the reward signal
from the reward model. A simplified update rule is:
N
1 X
∇θ J(θ) ≈ ∇θ log πθ (Ai |Si )r(Si , Ai )
N i=1

5. Over Optimization in Dialog systems: J(θ) = Eπθ [r] − βDKL (πθ ||πβ )

6. Off-Policy Considerations: To improve sample efficiency, off-policy methods with importance

sampling are used. A KL-divergence penalty is also added to the loss function to prevent the new
policy from deviating too drastically from the reference policy, thus maintaining model stability and
preventing reward hacking.

16
8 Actor-Critic Methods
8.1 Recap: Policy Gradient Methods
8.1.1 Monte-Carlo Policy Gradient (REINFORCE)
• Objective: The goal is to maximize the expected return from a starting state, represented by the
state-value function:
J(θ) = Eπθ [Gt | St = s0 ] = vπθ (s0 )

• Policy Gradient Theorem: The gradient is estimated as the expectation of the log-policy gradient
scaled by the action-value function:

∇θ J(θ) ∝ Eπθ [∇θ log πθ (a|s)qπ (s, a)]

• Update Rule: The parameters are updated in the direction of the sampled return Gt , which is a
Monte-Carlo estimate of qπ (s, a):

θt+1 = θt + α∇θ log πθ (At |St )Gt

This method estimates the action-value function using a complete trajectory’s return, which, while unbi-
ased, can have high variance.

8.1.2 REINFORCE with Baseline

To address the high variance of REINFORCE, a baseline b(s) is introduced.
• Modified Gradient: The gradient is now proportional to the advantage function, which is the
difference between the action-value and a state-dependent baseline. This reduces variance without
changing the expected value of the gradient.

∇θ J(θ) ∝ Eπθ [∇θ log πθ (a|s)(qπ (s, a) − b(s))]

• Update Rule: The update is based on the advantage estimate:

θt+1 = θt + α∇θ log πθ (At |St )(Gt − b(St ))

• A common and effective baseline is a learned value function, b(St ) = v̂(St , w).

8.2 Actor-Critic Methods

8.2.1 Core Concepts
Actor-Critic methods combine a policy network (the actor) with a value function network (the critic).
• The actor is the policy, parameterized by θ, which chooses the action.
• The critic is a value function, parameterized by w, which estimates the value of the state or state-
action pair.
• Instead of waiting for a full trajectory’s return (Monte Carlo), the actor-critic method uses the critic’s
value estimate to update the actor. This allows for updates at every step, reducing the variance and
speeding up learning.
The critic is used to bootstrap, providing a value estimate to guide the actor.

17
8.2.2 Advantage Actor-Critic
This approach uses the advantage function as the critic’s signal to the actor. The advantage function,
Aπ (s, a), measures how much better a specific action a is compared to the expected value of
the state, V π (s).

• Advantage function: Aπ (s, a) = Qπ (s, a) − V π (s)

or using the Bellman equation: Aπ (s, a) = r + γV π (s′ ) − V π (s)

• Advantage estimate: A common way to estimate the advantage is with the Temporal-Difference
(TD) error:
Â(St , At ) = Rt+1 + γv̂w (St+1 ) − v̂w (St )
This is an estimate of how much the reward was better (or worse) than expected.

• Gradient Update: The policy gradient is then estimated using this advantage signal:

∇θ J(θ) ≈ ∇θ log πθ (At |St )Â(St , At )

8.2.3 (Batch) Advantage Actor-Critic Algorithm

This algorithm trains both the actor and the critic networks simultaneously using a batch of sampled
trajectories.

1. Sample Trajectories: Collect a set of trajectories {τi } using the current policy πθ .

2. Update Critic: The critic network’s parameters w are updated to minimize the squared TD-error
loss.
N Ti
1 XX i i
L(w) = (Rt+1 + γv̂w (St+1 ) − v̂w (Sti ))2
N i=1 t=1
The parameters are updated via gradient descent: w ← w − αw ∇w L(w).

3. Evaluate Advantage: For each step in the batch, the advantage estimate is calculated using the
updated critic.
Â(Sti , Ait ) = Rt+1
i i
+ γv̂w (St+1 ) − v̂w (Sti )

4. Update Actor: The actor network’s parameters θ are updated using the batch of advantage esti-
mates.
N Ti
1 XX
∇θ J(θ) ≈ ∇θ log πθ (Ait |Sti )Â(Sti , Ait )
N i=1 t=1
The parameters are updated via gradient ascent: θ ← θ + αθ ∇θ J(θ).

8.2.4 Network Designs

• Two-Network Design: The actor and critic are two separate neural networks with their own
parameters.

• Shared-Network Design: A single network is used, with a shared trunk that processes the state
input, and two separate heads for outputting the policy (actor) and the value estimate (critic). This
can be more parameter-efficient.

18
 A shared network design is considered parameter efficient because it uses each parameter (a weight
in the model) for many different parts of the task.
This approach reduces the total number of parameters required. This, in turn, leads to several
benefits for the model, including:

– Faster processing
– Less memory usage
– Better generalization to new tasks

This idea is a core principle in modern deep learning and multi-task learning systems.

9 Dynamic Programming (DP)

9.1 Bellman Equations
• State-value: vπ (s) = π(a|s) s′ ,r p(s′ , r|s, a)[r + γvπ (s′ )].
P P
a

• Action-value: qπ (s, a) = s′ ,r p(s′ , r|s, a)[r + γ a′ π(a′ |s′ )qπ (s′ , a′ )].
P P

• Optimal state-value: v ∗ (s) = maxa s′ ,r p(s′ , r|s, a)[r + γv ∗ (s′ )].

P

• Optimal action-value: q ∗ (s, a) = s′ ,r p(s′ , r|s, a)[r + γ maxa′ q ∗ (s′ , a′ )].

P

9.2 Iterative Policy Evaluation (Prediction)

“If I follow this strategy, how good is each situation I’ll encounter?” This process does not alter the policy;
it simply evaluates it. The algorithm estimates the “value” (long-term expected reward) of each state
under a fixed policy π.

Why is this useful? You need to know if a policy is good before improving it. This is the “prediction”
part of RL.

Input: An MDP ⟨S, A, P, R, γ⟩ and a policy π.

Output: vπ .

1. Start with an initial guess. Initialize v0 (s) = 0 for all s ∈ S.

2. Repeat until convergence: vk+1 (s) = a π(a|s) s′ ,r p(s′ , r|s, a)[r + γvk (s′ )] (Bellman equation).
P P

3. Stop when values stop changing much

9.3 Policy Iteration (Control)

This algorithm finds an optimal policy π ∗ (the best actions to take in each state) and its corresponding
optimal value function V ∗ .

PolicyIteration = Policy Evaluation + Policy Improvement (This is done iteratively)

It operates by alternating between evaluating the current policy and improving it, a process known as
policy iteration.

19
 Why it is useful: Policy iteration is a control method, not just a prediction one. Its goal is to find
the best possible strategy to maximize long-term rewards, making it a foundational algorithm for solving
control problems in reinforcement learning.

Input: MDP ⟨S, A, P, R, γ⟩.

Output: v ∗ , π ∗ .
1. Initialize π0 arbitrarily (e.g., random actions).
2. Policy Evaluation: Compute vπk using iterative evaluation (section 9.2).
3. Policy Improvement: πk+1 (s) = arg maxa qπk (s, a) = arg maxa s′ ,r p(s′ , r|s, a)[r + γvπk (s′ )] (greedy
P
choice based on current v).
4. Repeat until πk+1 = πk .

9.4 Value Iteration (Control)

Similar to Policy Iteration, this algorithm finds an optimal policy π ∗ and its value function V ∗ . It combines
the evaluation and improvement steps into one by repeatedly applying the Bellman optimality equation
to directly compute the optimal value function V ∗ , from which the optimal policy can be extracted.

Why it is useful Value Iteration is a control method: it not only predicts but also finds the best
strategy. It is simpler and often converges faster than Policy Iteration for large problems because it does
not require a separate, exhaustive policy evaluation phase – because it combines policy improvement and
evaluation into a single update.

1. Initialize v0 (s) = 0.
p(s′ , r|s, a)[r + γvk (s′ )].
P
2. Repeat until convergence: vk+1 (s) = maxa s′ ,r

3. Once converged, get Optimal policy: π ∗ (s) = arg maxa s′ ,r p(s′ , r|s, a)[r + γv ∗ (s′ )].
P

10 Asynchronous Dynamic Programming

Asynchronous value iteration is a method for finding the best policy in a Markov Decision Process (MDP)
by updating the value of states one at a time, or in small groups, without waiting for a full sweep of all
states. This contrasts with traditional, synchronous methods that update all states simultaneously. This
flexibility often leads to faster convergence, especially for large state spaces.

How It Works
Imagine a problem of finding the shortest path on a map with many cities (states).
Synchronous Value Iteration would be like a team of people simultaneously calculating the shortest
distance from every single city to a destination. They all work on their assigned city at the same time
and then, after everyone has finished, they collectively share and update their findings. If the map has
a million cities, this is inefficient because the entire team must wait for the slowest person to finish their
calculation before the next round of updates can begin.
Asynchronous Value Iteration is like having the same team work independently. One person
calculates the distance for City A, another for City B, and so on. As soon as one person finds a new,

20
better route for their city, they immediately update that city’s value. This new information is instantly
available for everyone else to use in their ongoing calculations. This continuous and immediate sharing of
information allows the process to converge more quickly because no one is idle, waiting for the entire set
of calculations to complete.

10.1 Synchronous Dynamic Programming

• All states are updated in parallel at each iteration.

• Example: Value Iteration.

• For all s ∈ S: X
p(s′ , r|s, a) r + γvk (s′ )
 
vk+1 (s) = max
a
s′ ,r

• Each vk+1 (s) update uses the previous vk (s′ ) values.

10.2 Asynchronous Dynamic Programming

• States can be updated in any order, possibly one at a time.

• Does not require full-sweep of all states per iteration.

• Converges as long as all states continue to be selected for updates.

10.2.1 In-Place Dynamic Programming

• Use the latest available values for v(s) during updates, not just those from previous iteration.

• For all s ∈ S: X
v(s) ← max p(s′ , r|s, a)[r + γv(s′ )]
a
s′ ,r

10.2.2 Prioritized Sweeping

• Prioritize updates for states with largest Bellman error.

• Leads to faster convergence by focusing computation on relevant parts of the state space.

10.2.3 Real-Time Dynamic Programming

• Updates guided by agent’s actual experience.

• Utilizes the environment’s feedback to steer which states are updated.

• Helps agent focus learning on states most relevant to its current task.

Pseudocode: Asynchronous Value Iteration

for iteration k = 1..K:
for each selected state s (order may vary):

v(s) ← maxas′ ,r p(s′ , r|s, a)[r + v(s′ )]

21
11 Model-Free Prediction
11.1 Monte-Carlo (MC) Learning
• Learn vπ (s) = Eπ [Gt | St = s].
• MC Update: V (s) ← V (s) + α(Gt − V (s)).
• Incremental: N (s) ← N (s) + 1; Where N(s) is the total number of visits to state s so far (i.e., a
state-visitation count)
V (s) ← V (s) + N1(s) (Gt − V (s)).

11.2 Temporal-Difference (TD(0)) Learning

• Update: V (St ) ← V (St ) + α(Rt+1 + γV (St+1 ) − V (St ).
Where :
T [Link] = Rt+1 + γV (St+1 ) − V (St )
T arget = (Rt+1 + γV (St+1 )

• TD error: δt = Rt+1 + γV (St+1 ) − V (St ).

11.3 n-Step TD Learning

• n-step return: Gt:t+n = Rt+1 + γRt+2 + · · · + γ n−1 Rt+n + γ n V (St+n ).
• Update: V (St ) ← V (St ) + α(Gt:t+n − V (St )).

12 Unified View

Figure 1: Unified View

What do “depth” and “width” mean?

Depth (length of update): Refers to how far into the future each update looks.

22
 • Short depth: Update uses immediate next state (e.g., TD learning).

• Long depth: Update could use entire episode or tree (e.g., Monte Carlo, exhaustive search).

Width (branching in update): How many alternative actions or transitions are considered in each
update.

• Narrow width: Single trajectory or outcome (e.g., real experience).

• Wide width: All possible actions/states (e.g., dynamic programming, exhaustive search).

13 TD(λ): Simple Example with λ = 1/2

13.1 Idea
• TD(λ) averages several n-step returns, with weights λn−1 .

• When λ = 0: Only uses 1-step TD (TD(0)).

• When λ = 1: Uses full return (Monte Carlo).

• At λ = 21 : Each longer return is included but weighted less. The 1-step return gets weight 1/20 = 1,
the 2-step return gets weight 1/21 = 0.5, the 3-step return gets weight 1/22 = 0.25, and so on.

.
Gt:t+n = Rt+1 + γRt+2 + · · · + γ n−1 Rt+n + γ n v̂(St+n , wt+n−1 ), 0 ≤ t ≤ T − n,

PT −t−1
Gλt = (1 − λ) n=1 λn−1 Gt:t+n + λT −t−1 Gt

.
wt + 1 = wt + α Gλt − v̂(St , wt ) ∇v̂(St , wt ),
 
t = 0, . . . , T − 1.

13.2 Easy Example

Suppose an episode starts in state S0 , and we observe: R1 = 2, R2 = 3, R3 = 4, γ = 1 (no discount), and
V (S3 ) = 0 (terminal).
Possible returns:
(1)
1-step: G1 = R1 + V (S1 )
(2)
2-step: G1 = R1 + R2 + V (S2 )
(3)
3-step: G1 = R1 + R2 + R3 + V (S3 )

But let’s say V (S1 ) = V (S2 ) = V (S3 ) = 0 for simplicity.

So:
(1)
G1 = 2
(2)
G1 = 2 + 3 = 5
(3)
G1 = 2 + 3 + 4 = 9

23
 TD(λ) average for λ = 1/2:
h i
(λ) (1) (2) (3)
G1 = (1 − λ) G1 + λG1 + λ2 G1 + · · ·
= (1 − 0.5) [2 + 0.5 × 5 + 0.25 × 9]
= 0.5 [2 + 2.5 + 2.25]
= 0.5 × 6.75 = 3.375

Interpretation: With λ = 1/2, TD(λ) mixes short and long returns: - Gives most weight to 1-step
(TD), some to 2-step, less to 3-step, etc. - This offers a balance between quickly updated, low-variance
estimates and longer-term, low-bias returns.

Table 1: Summary of TD(λ) returns and weights

n-step Return Weight (λn−1 ) Included Value
1-step 1 2
2-step 0.5 5
3-step 0.25 9

TD(λ = 1/2) = 0.5 × (2 + 2.5 + 2.25) = 3.375

This shows how TD(λ) blends multiple returns, with the influence tailing off for longer returns as λ
gets smaller.

14 Model-Free Control
We consider a Markov Decision Process (MDP) with a finite state space S, action space A, transition
kernel p(s′ , r | s, a), and a discount factor γ ∈ [0, 1). The goal of control is to find an optimal policy π ⋆
that maximizes the expected discounted return. All methods below learn an action-value function Q(s, a)
directly from experience without an explicit model of the environment’s dynamics.

14.1 On-Policy Monte Carlo (MC) Control

Monte Carlo (MC) control improves a policy using returns from complete sampled episodes, following the
policy it is evaluating (typically with ϵ-greedy exploration).
(
arg maxa Q(St , a), with probability 1 − ϵ,
π ′ (St ) =
a random action, with probability ϵ

14.1.1 Concept:
• The agent interacts with the environment using an ϵ-greedy policy for exploration.

• After each episode, it computes the returns Gt for each state-action pair (St , At ).

• Updates action-value estimates Q(St , At ) using the averages of observed returns.

• The policy is updated to be greedy w.r.t. current Q (or remains ϵ-greedy for continued exploration).

Algorithm Outline:

1. Initialize Q(s, a) arbitrarily, π as ϵ-greedy w.r.t. Q.

24
 2. For each episode:

(a) Generate episode following π.

(b) For every (St , At ) pair in episode:
• Compute return Gt from t to episode end.
• Store all occurrences of (St , At ).
• Average all observed returns Gt for (St , At ):

Q(St , At ) ← average of all returns Gt for (St , At )

• Improve policy: Set π to be ϵ-greedy w.r.t. new Q.

Key Points:

• No bootstrapping—uses actual returns (Monte Carlo).

• Must visit all state-action pairs infinitely often (usually with ϵ-greedy).

• Resulting Q converges to optimal values as episodes accumulate.

• Policy is continually improved as action-value estimates become more accurate.

Control Loop (GLIE in practice)

Repeatedly:

1. Generate an episode by following the current ϵ-greedy policy π.

2. For each visited state-action pair (St , At ), compute Gt and update Q as described above.

3. Improve π to be ϵ-greedy with respect to the updated Q.

To ensure convergence
P (in tabular finite MDPs), use GLIE (greedy in the limit with infinite exploration),
e.g., ϵk ↓ 0 but k ϵk = ∞. (ϵ will be decrease, and at infinity ϵ will be 0, so it will be acting greedy. So
to ensure exploration, you need to set epsilon in such a way that sum of all epsilons is equal to ∞).

Notes
• Pros: Unbiased targets (true returns), conceptually simple.

• Cons: Requires full episodes; high-variance targets; can be slow for long episodes.

14.2 Sarsa (On-Policy TD Control)

Sarsa learns on-policy using one-step bootstrapping.

Update
At each step (St , At , Rt+1 , St+1 , At+1 ):
 
Q(St , At ) ← Q(St , At ) + α Rt+1 + γQ(St+1 , At+1 ) − Q(St , At ) .

This is a TD(0) update on the action-value function.

25
Policy for Exploration
The actions At and At+1 are both chosen from the same ϵ-greedy policy π with respect to the Q-function
(on-policy).

Control Loop
1. Initialize Q(s, a) arbitrarily; choose ϵ, α.

2. For each episode:

(a) Initialize state S0 , choose action A0 ∼ ϵ-greedy(Q(S0 , ·)).

(b) For t = 0, 1, 2, . . . until terminal:
• Take action At , observe reward Rt+1 and next state St+1 .
• Choose next action At+1 ∼ ϵ-greedy(Q(St+1 , ·)).
• Update Q(St , At ) with the Sarsa rule.

Notes
• The on-policy nature makes the learned Q reflect exploratory actions, which can be safer (e.g., in a
cliff-walking environment).

• Bootstrapped targets reduce variance compared to MC but may introduce bias.

14.3 Q-Learning (Off-Policy TD Control)

Q-learning learns the value of the greedy policy while potentially behaving ϵ-greedily for exploration; it is
off-policy via a max target.

Update
 
′
Q(St , At ) ← Q(St , At ) + α Rt+1 + γ max
′
Q(St+1 , a ) − Q(St , At ) .
a

Behavior vs. Target Policies

• Behavior policy: The policy used for generating experience (e.g., ϵ-greedy w.r.t. Q).

• Target policy: The greedy policy with respect to the current Q-function (implicit in the maxa′
operator).

Convergence (Tabular)
Under standard assumptions (finite MDP, sufficient exploration, appropriate stepsizes), Q-learning con-
verges to Q⋆ with probability 1.

Notes
• It’s off-policy and bootstrapped; it can be sensitive to overestimation bias (mitigated by Double
Q-learning).

• Often more sample-efficient than MC and is a widely used baseline.

26
14.4 n-Step Sarsa
n-step Sarsa trades off bias and variance by bootstrapping after n rewards.

Forward n-Step Return

For a transition starting at time t, the truncated return is defined as:

Gt:t+n = Rt+1 + γRt+2 + · · · + γ n−1 Rt+n + γ n Q(St+n , At+n )

with the convention that if the episode terminates before t + n, then Q(St+n , At+n ) is omitted (or treated
as 0).

Update


Q(St , At ) ← Q(St , At ) + α Gt:t+n − Q(St , At ) .

Scheduling
At each time t, an update for a prior time step τ = t − n + 1 is performed. This yields a pipeline of delayed
updates. As n → 1, we recover Sarsa; as n approaches the episode length, we approach on-policy MC.

Notes
• Larger n: lower bias, higher variance, and more delay.

• Smaller n: higher bias, lower variance, and faster updates.

• Backward-view equivalents use eligibility traces (e.g., Sarsa(λ)) to implement an exponentially weighted
average over different values of n.

14.5 Practical Considerations (All Methods)

• Initialization: Optimistic Q0 values can encourage exploration.

• Stepsize: A constant α is good for nonstationary settings, while a diminishing αt (e.g., Robbins–
Monro) supports convergence proofs.

• Exploration scheduling: GLIE strategies (e.g., ϵt ↓ 0) balance exploration and exploitation.

• Terminal handling: Set Q-values at terminal states to 0.

• Continuous actions: The ‘max‘ operator in Q-learning is difficult; consider actor-critic or deter-
ministic policy gradient methods instead.

14.6 Algorithm Boxes (Tabular)

On-Policy MC Control (Every-Visit, Incremental)

1. Initialize Q(s, a) arbitrarily; choose ϵ ∈ (0, 1), α ∈ (0, 1].

2. Loop for each episode:

(a) Generate episode (S0 , A0 , R1 , . . . , ST −1 , AT −1 , RT ) using an ϵ-greedy policy derived from Q.

27
 (b) For t = 0, . . . , T − 1:
−t−1
TX
Gt ← γ k Rt+1+k
k=0


Q(St , At ) ← Q(St , At ) + α Gt − Q(St , At ) .

Sarsa (On-Policy TD(0) Control)

1. Initialize Q(s, a) arbitrarily; choose ϵ, α.
2. Loop for each episode:
(a) Initialize state S0 , choose action A0 ∼ ϵ-greedy(Q(S0 , ·)).
(b) For t = 0, 1, 2, . . . until terminal:
• Take At , observe Rt+1 , St+1 .
• Choose At+1 ∼ ϵ-greedy(Q(St+1 , ·)).
• Update Q(St , At ) using the Sarsa rule:


Q(St , At ) ← Q(St , At ) + α Rt+1 + γQ(St+1 , At+1 ) − Q(St , At ) .

Q-Learning (Off-Policy TD Control)

1. Initialize Q(s, a) arbitrarily; choose ϵ, α.
2. Loop for each episode:
(a) Initialize state S0 .
(b) For t = 0, 1, 2, . . . until terminal:
• Choose At ∼ ϵ-greedy(Q(St , ·)).
• Take At , observe Rt+1 , St+1 .
• Update Q(St , At ) using the Q-Learning rule:
′


Q(St , At ) ← Q(St , At ) + α Rt+1 + γ max
′
Q(St+1 , a ) − Q(St , At ) .
a

n-Step Sarsa (Forward View)

1. Initialize Q(s, a) arbitrarily; choose ϵ, α, n ≥ 1.
2. Loop for each episode:
(a) Generate a trajectory (S0 , A0 , R1 , S1 , A1 , . . . ) using an ϵ-greedy policy derived from Q.
(b) For t = 0, 1, 2, . . . until all updates applied:
• Let τ ← t − n + 1.
• If τ ≥ 0, define the n-step return:
n−1
X
Gτ :τ +n = γ k Rτ +1+k + γ n Q(Sτ +n , Aτ +n )
k=0

(with truncation at terminal states), and update:

Q(Sτ , Aτ ) ← Q(Sτ , Aτ ) + α Gτ :τ +n − Q(Sτ , Aτ ) .

28
14.7 Conceptual Differences Summary
• Target: MC uses the full return Gt ; Sarsa uses a one-step bootstrapped target Rt+1 +γQ(St+1 , At+1 );
Q-learning uses a max-operator bootstrapped target Rt+1 + γ maxa′ Q(St+1 , a′ ); n-step Sarsa uses an
intermediate n-step return Gt:t+n .

• On- vs Off-Policy: MC control and Sarsa are on-policy; Q-learning is off-policy.

• Bias/Variance: MC has low bias but high variance; TD methods have more bias but lower variance.
The n-step methods provide a spectrum to balance this trade-off by adjusting the step size n.

15 Deep Q-Networks and DDQN (DQN)

15.1 Deep Q-Learning
• Represent Q(s, a; w) ≈ q ∗ (s, a).

• Loss: L(w) = N1 i (yi − Q(si , ai ; w))2 , where yi = ri + γ maxa′ Q(s′i , a′ ; w− ).

P

• Update w via stochastic gradient descent (SGD).

15.2 DQN Algorithm (with Experience Replay and Target Network)

1. Initialize replay buffer B; initialize online Q-network Q(s, a; w); initialize target network Q(s, a; w− ) ←
Q(s, a; w).

2. For episode = 1, . . . :

(a) Reset env, receive initial state s0 ; set t ← 0.

(b) While not done:
[Link] at via ϵ-greedy from Q(·; w) given st .
[Link] at , observe rt+1 , next state st+1 , and done flag dt+1 ∈ {0, 1}.
[Link] (st , at , rt+1 , st+1 , dt+1 ) in B.
iv. Sample a mini-batch {(si , ai , ri , s′i , di )}N
i=1 from B.
v. Compute targets: yi = ri + γ(1 − di ) maxa′ Q(s′i , a′ ; w− ).

2
vi. Update w by minimizing L(w) = N1 i yi − Q(si , ai ; w) (often Huber loss).
P

vii. Every N steps: update target, e.g., hard w− ← w or Every K steps soft w− ← τ w− + (1 −
τ )w.
viii. Optionally anneal ϵ; t ← t + 1; st ← st+1 .

15.3 Double DQN: Steps

1. Store transition: Take action At , store (St , At , Rt+1 , St+1 ) in the replay buffer B.

2. Sample mini-batch: Randomly pick a mini-batch of transitions {(S, A, R, S ′ )} from B.

3. Calculate target:

• DQN target: yi = Ri+1 + γ q̂w− (Si+1 , arg maxa′ q̂w (Si+1 , a′ ))

• Double DQN target: yi = Ri+1 + γ q̂w− (Si+1 , arg maxa′ q̂w (Si+1 , a′ ))

29
 − q̂(Si , Ai , w))2
P
4. Calculate loss: L(w) = i (yi

5. Update weights: Adjust w to minimize L(w).

6. Target network update: Set w− ← w every N steps.

Alternative target network update: w− ← τ w− + (1 − τ )w, e.g., τ = 0.999 every step.

15.4 Prioritized Experience Replay Steps

1. Store transition: Take action At , and store (St , At , Rt+1 , St+1 ) in replay buffer B with maximal
priority pt = maxi pi .

2. Sample mini-batch: Sample transitions from B using prioritized experience replay: probability
pα
j
P (j) = P
pα
i i

 β
1
3. Importance-sampling: Compute weight λi = N P (i)
/ maxi λi

4. Update priority: Set pj ← |δj | + ε for sampled transitions.

5. Calculate target: yi = Ri+1 + γ ŵ− (Si+1 , arg maxa′ ŵ(Si+1 , a′ ))

6. Calculate loss: L(w) = i λi (yi − q̂(Si , Ai , w))2

P

7. Update w: Minimize L(w) and update network parameters.

8. Update target network: w− ← τ w− + (1 − τ )w every step.

15.5 Improvements to DQN

• Double DQN: Target yi = ri + γQ(s′i , arg maxa′ Q(s′i , a′ ; w), w− ) to reduce overestimation.

• Prioritized Replay: Sample transitions with priority pi ∝ |δi |+ϵ; update with importance sampling
weights.

• Multi-step Returns: yi = nk=1 γ k−1 ri+k + γ n maxa′ Q(s′i+n , a′ ; w− ).

P

15.5.1 Why N-step Returns Don’t Work Simply in DQN

Only actually correct when learning on-policy. Let’s assume the experience replay buffer (ERB)
contains a sequence of transitions:

{(St , At , Rt+1 , St+1 , At+1 , Rt+2 , St+2 ), . . . }

This sequence was collected using an ϵ-greedy behavior policy.

For a single-step return, the tuple (St , At , Rt+1 , St+1 ) can be safely used. The reward Rt+1 is determined
entirely by the environment and does not depend on the specific Q-network that generated the action At .

However, for an N-step return, we also need the subsequent actions, such as At+1 , from state St+1 .
In standard Deep Q-Networks (DQN), the target is computed using the target network, specifically with
maxa′ Qtarget (S ′ , a′ ), not the action actually taken by the behavior policy.

If we directly use At+1 from the Experience Replay Buffer, we are implicitly assuming that it was
chosen according to the target network’s policy. In reality, At+1 was selected by the older behavior policy.

30
Since the Q-network parameters may have changed significantly since that transition was collected, this
assumption is incorrect and introduces an off-policy bias into the N-step return calculation.

Simple example:
• Step 1: Agent uses policy π1 (old) to generate transition
• Step 2: Agent uses policy π2 (newer) to generate next transition
• Step 3: We sample both from replay buffer and compute n-step return
• Problem: N-step assumes single policy, but we mixed π1 and π2 !
Solution:
• Ignore the problem – often works very well for DQN.
• Collect transitions {S, A, R, S ′ , A′ , R′ , S ′′ } and keep the n-step trace only if the target network’s
action for S ′ (and for any subsequent states) matches the recorded actions; otherwise, cut the trace.
• Importance sampling
Key insight: Actor-critic learns from fresh on-policy data. DQN learns from mixed old/new off-policy
data stored in replay buffer.

16 Continuous Control with Q-Learning

16.1 Why DQN Fails for Continuous Actions
Problem: DQN is designed for discrete action spaces.
1. Q-value maximization: DQN requires computing maxa Q(s, a) over all possible actions a. For
continuous actions, this would mean searching an infinite number of actions—impractical to compute
or represent exactly.
2. Action selection: The neural network output must be one value per action. In continuous control,
there are infinitely many actions, so mapping actions to outputs is not feasible.
3. Argmax not tractable: For continuous actions, finding the action a that maximizes Q(s, a) is a
complex optimization problem, not just selecting the highest output.
Conclusion: DQN cannot be directly applied for environments where the action space is continuous.
Instead, algorithms like DDPG or SAC are used for such cases.

16.2 Action Discretization

• Discretize continuous actions into bins (e.g., 10 bins per dimension).

16.2.1 Random Shooting Method For DQN

• Randomly sample N possible continuous actions {a1 , a2 , . . . , aN }.
• Evaluate each action using Q-function: q̂w (s, ai ).
• Pick the action with the highest value: maxi q̂w (s, ai ) ε greedy times and put them into the Experience
Replay Buffer.
• As N increases, the approximation to the optimal action improves.

31
16.3 Stochastic Optimization (CEM)
1. Sample M actions from distribution p(a) (e.g., Gaussian N (µ, σ 2 )).

2. Evaluate Q(s, ai ) for each.

3. Select top K elites.

4. Refit p(a) to elites (e.g., update µ, σ).

5. Best action: arg maxa Q(s, a) ≈ elite mean or max.

16.4 Deep Deterministic Policy Gradient (DDPG)

• DDPG is an actor-critic method for handling continuous action spaces.

• The actor network µθ outputs the best action for a given state S. It is called the critic network
because now the objective is to maximize the critic.

• The critic network Qw (S, A) estimates the action-value function.

• The network has two parts: an actor µ(s) and a critic Q(s, a).

• The “deterministic” in DDPG refers to the type of policy the algorithm learns. A deterministic
policy outputs a specific action for each given state, as opposed to a stochastic policy which outputs
a probability distribution over actions.

16.4.1 Pseudocode
1. Initialize actor and critic networks µ and Q with parameters θ and w.

2. Initialize target networks µ− and Q− with parameters θ− ← θ and w− ← w.

3. Initialize replay buffer B.

4. For each episode:

(a) Initialize a random process N for exploration.

(b) Receive initial state S.
(c) For t = 1, T :
i. Select action A = µθ (S) + Nt (Noise).
ii. Execute action A and observe new state S ′ and reward R.
iii. Store transition (S, A, R, S ′ ) in B.
iv. Sample a random minibatch of N transitions from B.
v. For each sampled transition (Si , Ai , Ri , Si′ ), calculate the target value:

yi = Ri + γQw− (Si′ , µθ− (Si′ ))

vi. Update the critic network by minimizing the loss:

1 X
L(w) = (yi − Qw (Si , Ai ))2
N i

32
 vii. Update the actor network using the sampled policy gradient:
1 X
∇θ J ≈ ∇A Qw (Si , A)|A=µθ (Si ) ∇θ µθ (Si )
N i

– Now the objective is to maximize the critic.

viii. Soft update the target networks:
w− ← τ w + (1 − τ )w−
θ− ← τ θ + (1 − τ )θ−

16.5 TD3 - (Not needed for exam)

Twin Delayed Deep Deterministic Policy Gradient

Key Idea: TD3 = DDPG + 3 stability fixes to reduce overestimation bias.

1. Twin Critics: Use Qθ1 , Qθ2 and take:
y = r + γ min Qθi′ (s′ , a′ )
i=1,2

to avoid optimistic bias.

2. Target Policy Smoothing: Add small clipped noise to target action:
a′ = πϕ′ (s′ ) + ϵ, ϵ ∼ clip(N (0, σ), −c, c)
for smoother policies.
3. Delayed Policy Updates: Update actor & targets every d steps, letting critics learn first.

16.5.1 Algorithm (Simplified)

1. Init Qθ1 , Qθ2 , πϕ , target networks Qθ1′ , Qθ2′ , πϕ′ , and replay buffer B.
2. For each step:
(a) Execute at = πϕ (st ) + exploration noise, store (st , at , rt , st+1 ) in B.
(b) Sample minibatch from B.
(c) Compute target:
y = r + γ min Qθi′ (s′ , πϕ′ (s′ ) + ϵ)
i=1,2

(d) Update critics by MSE to y.

(e) If t mod d = 0:
1 X
∇ϕ J(ϕ) = Qθ1 (s, πϕ (s))
N
θi′ ← τ θi + (1 − τ )θi′ , ϕ′ ← τ ϕ + (1 − τ )ϕ′

16.6 DDPG vs. TD3

Feature DDPG TD3
Critics 1 2 (take min)
Target smoothing No Yes
Actor update frequency Every step Delayed (e.g. every 2)

33
17 Offline Reinforcement Learning
17.1 What is Offline RL?
Offline RL (also known as batch RL or fully off-policy RL) is a subfield of reinforcement learning where
the goal is to learn an optimal policy π from a fixed, pre-collected dataset D = {(si , ai , s′i , ri )} without any
further interaction with the environment. The dataset can be collected by any behavior policy πβ (e.g., a
random policy, an expert human, or a series of past RL runs).
The objective is to find a policy π that maximizes the expected cumulative reward:
T
X
max Est ∼dπ ,at ∼π(a|s) [r(st , at )]
π
t=0

Once learned, the policy is deployed in the real environment. A related task is Off-Policy Evaluation
(OPE),
P which aims to estimate the value of a given policy π from the offline dataset D, i.e., J(π) =
Eπ [ Tt=1 r(st , at )].

17.2 How is Offline RL Possible?

Offline RL can be effective by:

• Extracting good behaviors: Learning to distinguish between high-reward and low-reward behav-
iors within a mixed-quality dataset.

• Generalization: A good action observed in one state can inform the model about good actions in
similar, unseen states.

• Stitching: The algorithm can recombine segments of different trajectories from the dataset to form
a new, superior policy. This is sometimes more powerful than imitation learning, as it can create
behaviors that were never seen in their entirety.

A key example is offline QT-Opt for robotic grasping, which achieved a high success rate by learning from
a large, fixed dataset of grasping attempts.

17.3 Why is Offline RL Hard?

The primary challenge in offline RL is the distribution shift between the learned policy π and the
data-collecting behavior policy πβ .

• Counterfactual queries: The learned policy may select out-of-distribution (OOD) actions that
are not present in the dataset. Since the value function is only trained on in-distribution actions, it
may produce wildly inaccurate and overly optimistic Q-value estimates for these OOD actions.

• Generalization issues: Function approximation, especially with deep neural networks, can amplify
these errors, leading to a policy that learns to exploit these erroneous Q-values and performs poorly
in the real environment. This is a common failure mode, where naive applications of off-policy
algorithms like DQN can lead to a significant overestimation of Q-values on offline data.

34
17.4 Policy Constraint Methods
One way to mitigate distribution shift is to constrain the learned policy to stay close to the behavior policy.
This can be formalized as:

π(a|s) = arg max E[Q(s, a)] s.t. DKL (π||πβ ) ≤ ϵ

π

This approach can be difficult because the behavior policy πβ is often unknown. Moreover, if the constraint
is too strict, the policy may not be able to improve, and if it’s too loose, the distribution shift problem
persists.

17.5 Conservative Q-Learning (CQL)

Conservative Q-Learning (CQL) is a method that directly addresses the overestimation problem by mod-
ifying the Q-learning objective. Its goal is to conservatively lower the Q-values for OOD actions
while keeping the Q-values for in-distribution actions high. The CQL loss function is:
h

2 i
′ ′


LCQL (Q) = α Es∼D,a∼µ(a|s) [Q(s, a)] − E(s,a)∼D [Q(s, a)] +E(s,a,s )∼D Q(s, a) − r(s, a) + γEa ∼π(a |s ) [Q(s , a )]
′ ′ ′ ′

• Where µ is the sampling distribution over actions (Softmax).

The first term is the key addition: it pushes down the Q-values on a set of sampled OOD actions (e.g.,
from a uniform distribution µ) while pushing up the Q-values for actions present in the dataset.

17.5.1 CQL Algorithm Pseudocode

1. Initialize the Q-network Q(s, a; w), policy network π(a|s; θ), and populate a replay buffer with the
offline dataset D.

2. For each training step:

3. Sample a mini-batch of transitions from D.

4. Update the Q-network parameters w using a stochastic gradient descent (SGD) step on the LCQL (Q)
loss.

5. Update the policy parameters θ:

• For discrete actions: The policy is updated to be greedy with respect to the learned Q-values:
π(a|s) = arg maxa′ Q(s, a′ ).
• For continuous actions: The policy is updated to maximize the expected Q-value: θ ←
θ + α∇θ Ea∼π(a|s) [Q(s, a)].

17.6 Additional Methods

• Implicit Q-Learning (IQL): A method that avoids explicitly querying OOD actions by using an
expectile regression loss.

• Advantage-Weighted Actor-Critic (AWAC): An algorithm that performs policy updates by

weighting offline samples based on their estimated advantage.

35
 • Model-Based Methods: Algorithms like MOPO (Model-based Offline Policy Optimization) and
COMBO (Conservative Model-Based Optimization) learn a world model from the offline data and
use it to generate synthetic transitions, while often incorporating a conservative penalty to avoid
model-exploitation.

• Sequence Modeling: Methods like the Trajectory Transformer treat RL as a sequence modeling
problem, learning to predict future returns and actions from past trajectories.

18 Actor-Critic Methods - Part 3

18.1 Batch Advantage Actor-Critic (A2C)
A2C is a stable on-policy method that reduces variance compared to REINFORCE by using a learned
value function to estimate the advantage.

• Advantage function: The advantage is estimated using the TD-error:

Â(St , At ) = Rt+1 + γv̂w (St+1 ) − v̂w (St )

18.1.1 Algorithm
1. Sample a batch of trajectories {τi } using the current policy πθ (a|s).

2. Critic Update: Update the critic network parameters w to minimize the Mean Squared Error
(MSE) loss on the TD-error:
1 XX i i

2
L(w) = Rt+1 + γv̂w (St+1 ) − v̂w (Sti )
N i t

w ← w − αw ∇w L(w)

3. Advantage Evaluation: Calculate the advantage estimate for each time step in the batch.

4. Actor Update: Update the actor network parameters θ using the advantage-weighted policy gra-
dient:
1 XX
∇θ J(θ) ≈ ∇θ log πθ (Ait |Sti )Â(Sti , Ait )
N i t
θ ← θ + αθ ∇θ J(θ)

18.2 PPO - Broken Versions Discussions

1. PPO v0.5 — Broken
What it does:

• Runs like a standard Advantage Actor-Critic (A2C) update but just uses new parameters θ every
iteration:
1 X
∇J(θ) ≈ ∇θ log πθ (ai |si ) Â(si , ai )
N
• Data is collected with πθold , but the log-probability ratio πθπθ is not used — it ignores that the policy
old
changed between data collection and gradient computation.

36
 Why is this broken:

• Large gradient steps can move πθ far from πθold in one update.

• On-policy assumption is violated because the collected batch no longer reflects the updated policy.

• Can cause destructive policy updates (performance collapse after one bad step).

2. PPO v0.8 — Still Broken (But Closer)

What it adds:

• Introduces the ratio term:

 
πθ (a|s)
JPPO (θ) = Eπθold Âπ (s, a)
πθold (a|s) θold

• This is the importance-sampled surrogate objective from TRPO theory.

Why still broken:

• The ratio is used, but there’s no constraint or clipping — the ratio can still blow up.

• High variance and instability remain because a single large update can overly increase/decrease action
probabilities.

18.3 Trust Region Policy Optimization (TRPO)

Policy gradient methods are susceptible to large updates that can destabilize training. If a policy update
is too large, it can cause a catastrophic drop in performance.

TRPO addresses this by introducing the concept of a “trust region.” It aims to find the largest possible
step that improves the policy, while ensuring that the new policy is not too far from the old policy. ”Too
far” is measured by the Kullback-Leibler (KL) divergence.
 
πθ (At |St )
max Eπθold Aπ (St , At )
θ πθold (At |St ) θold
s.t. Eπold [DKL (πold ||πθ )] ≤ δ

• δ is a small hyperparameter controlling the maximum allowed KL divergence.

How do we ensure we don’t go too far:

Using Hessian (second order derivative) TRPO ensures it doesn’t violate the KL divergence constraint δ.

But! This method is complex to implement due to the second-order optimization required to handle
the constraint.

37
18.4 Proximal Policy Optimization (PPO)
PPO is a popular, simpler alternative to TRPO that uses a clipped surrogate objective to achieve a similar
effect of constraining policy updates.
h  i
J P P O (θ) = max Eπθold min rt (θ)Ât , clip(rt (θ), 1 − ϵ, 1 + ϵ)Ât
θ

• ϵ is a hyperparameter (e.g., 0.1 or 0.2) that defines the “clipping range.”

• If Advantage is positive:
   
PPO πθ (At |St )
J (θ) = Eπθold min , 1 + ϵ Aπθold (St , At )
πθold (At |St )

• If Advantage is negative:
   
PPO πθ (At |St )
J (θ) = Eπθold max , 1 − ϵ Aπθold (St , At )
πθold (At |St )

where rt (θ) = πθπθ (A(At |St |St )t ) is the probability ratio and Ât is the advantage estimate. The ‘clip‘ function
old
prevents the policy from making excessively large changes, thereby avoiding catastrophic updates.

• If At > 0 (good action): We want to increase the probability of this action. The objective takes the
minimum of rt (θ)At and (1 + ϵ)At . If rt (θ) goes above 1 + ϵ, it gets clipped. This prevents updates
from becoming too large and making the new policy vastly different from the old one, even if the
action is very good.

• If At < 0 (bad action): We want to decrease the probability of this action. The objective takes
the minimum of rt (θ)At and (1 − ϵ)At . If rt (θ) goes below 1 − ϵ, it gets clipped. This prevents the
policy from being penalized too much for actions that were just slightly worse than average. It avoids
pushing the policy too far away from the old policy.

18.4.1 PPO Algorithm

The PPO algorithm is similar to Batch A2C but uses the PPO clipped objective for the actor update.

1. Sample trajectories {τi } from the current policy πθold .

2. Update the critic network (as in A2C).

3. Evaluate the advantage function (as in A2C).

4. Update the actor network for multiple epochs using the PPO objective on the same batch of data.

5. Set the old policy parameters: θold ← θ.

19 Off-Policy Actor-Critic Methods

19.1 Online Actor-Critic (On-Policy)
The basic actor-critic algorithm updates after each single time step. While simple, it has issues with
instability when used with deep neural networks.

38
 1. Take action At ∼ πθ (·|St ), observe St , At , Rt+1 , St+1 .

2. Critic Update: Update the value function v̂w towards the target yt = Rt+1 + γv̂w (St+1 ).

3. Actor Update: Update the policy πθ using the TD-error as the advantage signal: Â(St , At ) =
yt − v̂w (St ).

In the on-policy version, the data used for learning comes from the same policy that’s being updated.
This can be inefficient because each data sample can only be used once.

19.2 Why Off-Policy Actor-Critic?

• Off-policy allows you to learn from any past experience, not just from the current policy’s behavior.

• This is made possible through the use of a replay buffer (which stores past experiences) and target
networks (which stabilize learning).

• Instead of learning the state value V (s), which is tricky off-policy, we learn the action value Q(s, a),
as Q can be estimated from replay buffer samples without bias from old policies.

19.3 Off-Policy Actor-Critic

This is a more modern approach that combines the benefits of actor-critic methods with a replay buffer,
allowing it to be off-policy. To support off-policy learning, it typically uses a Q-function instead of a
V-function.

1. Take action At from the current policy πθ and store the transition (St , At , Rt+1 , St+1 ) in a replay
buffer B.

2. Sample a mini-batch of transitions from B.

3. Critic Update: Update the critic’s Q-network q̂w towards a target value yi .

yi = Ri+1 + γ q̂w− (Si+1 , Aπi+1

θ
)

where Aπi+1
θ
∼ πθ (·|Si+1 ) is a sampled action from the current policy.

4. Actor Update: Update the actor πθ to maximize the Q-values.

1 X
∇θ J(θ) ≈ ∇θ log πθ (Aπi θ |Si )q̂w (Si , Aπi θ )
N i

5. Target Network Update: The target critic network w− is updated slowly using a soft update:
w− ← τ w− + (1 − τ )w.

19.4 Deep Deterministic Policy Gradient (DDPG)

As discussed in Section 16.4 DDPG is an off-policy, actor-critic algorithm for continuous action spaces. It
uses a deterministic policy µθ (s) for acting, with added noise for exploration, At = µθ (St ) + Nt .

39
19.4.1 Pseudocode
1. Initialize actor and critic networks µ and Q with parameters θ and w.
2. Initialize target networks µ− and Q− with parameters θ− ← θ and w− ← w.
3. Initialize replay buffer B.
4. For each episode:
(a) Initialize a random process N for exploration.
(b) Receive initial state S.
(c) For t = 1, T :
i. Select action A = µθ (S) + Nt .
ii. Execute action A and observe new state S ′ and reward R.
iii. Store transition (S, A, R, S ′ ) in B.
iv. Sample a random minibatch of N transitions from B.
v. For each sampled transition (Si , Ai , Ri , Si′ ), calculate the target value:
yi = Ri + γQw− (Si′ , µθ− (Si′ ))
vi. Update the critic network by minimizing the loss:
1 X
L(w) = (yi − Qw (Si , Ai ))2
N i

vii. Update the actor network using the sampled policy gradient:
1 X
∇θ J ≈ ∇A Qw (Si , A)|A=µθ (Si ) ∇θ µθ (Si )
N i

Now the objective is to maximize the critic.

viii. Soft update the target networks:
w− ← τ w + (1 − τ )w−
θ− ← τ θ + (1 − τ )θ−

1. Broken Version — Off-Policy Actor-Critic v0.5

What it does:
• Uses a replay buffer but still tries to learn V (s) directly from old (off-policy) samples.
• Critic target:
yt = rt+1 + γ v̂w− (st+1 )

• Actor uses advantages computed from V estimates.

Why it’s broken:
• Off-policy issue: You can’t directly learn V (s) from replay buffer samples collected by older policies.
• The state and action distributions no longer match the current policy, making Bellman targets biased.
• This leads to incorrect value targets and unstable learning.

40
2. The Fix — Learn Q(s, a) Instead (Off-Policy Actor-Critic v0.8)
Key change:
• Replace V -learning with a Q-learning style target:


yt = rt+1 + γ q̂w− st+1 , at+1 ∼ πθ (·|st+1 )

• Here, at+1 is sampled from the current policy, not the replay buffer.
Why it works:
• Q(s, a) Bellman targets remain valid off-policy — you only need the next action from the current
policy.
• Advantage can now be computed as:
Â(si , ai ) = q̂w (si , ai ) − v̂(si )

• With: X
v̂(si ) = πθ (a|si ) q̂w (si , a)
a

20 Soft Actor-Critic (SAC)

Standard RL: “I’ll keep doing what seems best right now.”
SAC: “I’ll do what seems best on average, but keep some healthy randomness so I don’t miss a better
long-term strategy.”

20.1 Maximum Entropy Reinforcement Learning

Instead of just maximizing reward, maximum entropy reinforcement learning adds an entropy bonus to
the objective: "∞ #
X
γ t Rt+1 + α H(π(·|St ))


J(π) = E
t=0
Here, the entropy of the policy π at state St is defined as:
X
H(π(·|St )) = − π(a|St ) log π(a|St )
a

Entropy measures the randomness in the policy’s action choices. The parameter α is the temperature,
which determines how much weight is given to the entropy bonus relative to the reward.

• SAC is a model-free, off-policy, actor-critic algorithm that aims to find a policy that
not only maximizes the reward but also has high entropy.
• This encourages exploration and leads to more stable policies.
• The objective function is augmented with an entropy term:
X
π ∗ = arg max Eρπ [r(st , at ) + αH(π(·|st ))]
π
t

where H(π(·|st )) = Eat ∼π [− log π(at |st )] is the policy’s entropy and,
• α is the temperature parameter that controls the trade-off between reward and entropy.

41
20.2 Soft Value Functions
The Bellman equations are modified to include the entropy term, resulting in “soft” value functions.
Generally :
V π (st ) = Eat ∼π [Qπ (st , at )]
Soft state-value:
V π (st ) = Eat ∼π [Qπ (st , at ) − α log π(at |st )]
Soft action-value:
Qπ (st , at ) = r(st , at ) + γEst+1 [V π (st+1 )]

• In optimization, a soft maximum (or soft value) means we do not pick the single best action
deterministically.
• Instead, we average over all actions, weighting them by their probability under π, and encourage a
broader distribution.
• This avoids hard-max selection from Q-values (as in DQN), which can lead to premature convergence.

20.3 SAC Algorithm

SAC uses a stochastic policy and two Q-networks to mitigate overestimation bias. It is particularly effective
for continuous control tasks.
1. Sample action At from the policy πθ , execute it in the environment, and store the transition in a
replay buffer D.
2. Sample a mini-batch of transitions from D.
3. Critic Update: Update both Q-networks to minimize the MSE loss against a soft Q-target, which
is constructed using the minimum of the two Q-networks to reduce overestimation.
"   2 #
′ ′ ′ ′
JQ (ϕ) = E(s,a,s′ )∼D Qϕ (s, a) − r + γ min Qϕ−j (s , ã ) − α log πθ (ã |s )
j=1,2

where ã′ is a sampled action from the current policy.

4. Actor Update: Update the actor to minimize the expected Kullback-Leibler (KL) divergence the
softmax over Q-Values and the policy πθ to maximize the objective Jπ (θ) .

Jπ (θ) = Es∼D,a∼πθ [Qϕ (s, a) − α log πθ (a|s)]

For continuous actions, a reparameterization trick is used to make this differentiable.

5. Update the temperature parameter α (optional) and perform soft updates on the target networks.

21 Model-Based Reinforcement Learning

21.1 Overview
Model-based RL is a paradigm where an agent learns a model of the environment’s dynamics from its
experience. This model is then used for planning to inform and construct better policies or value functions.
This contrasts with model-free RL, which learns policies and value functions directly from experience
without explicitly learning a model.

42
21.1.1 Model-Free vs. Model-Based
• Model-Free RL: The agent learns a policy π(a|s) or a value function Q(s, a) directly from interac-
tions with the environment. Examples include DQN and Policy Gradient methods.
• Model-Based RL: The agent learns a dynamics model p(s′ , r|s, a) that predicts the next state
s′ and reward r given the current state s and action a. This model is then used to simulate new
experiences and improve the policy.

21.2 Advantages and Disadvantages

21.2.1 Advantages
• High Sample Efficiency: By simulating experience from the learned model, the agent can learn a
good policy with far fewer real-world interactions.
• Rapid Adaptation: The model can be quickly updated with new data, allowing the agent to adapt
to changes in the environment or new tasks.
• Efficient Model Learning: Learning a predictive model is a supervised learning problem, which
is often more stable and data-efficient than learning a policy via trial and error.

21.2.2 Disadvantages
• Two Sources of Error: Performance is sensitive to both the accuracy of the learned model and
the effectiveness of the planning algorithm used with the model. Errors can compound over long
planning horizons.

22 Model Learning
Learning a dynamics model is a supervised learning task. Given a dataset of transitions D = {(si , ai , ri+1 , s′i+1 )},
the model learns to predict the next state and reward.
• Reward Model: A regression model predicts the reward, ri+1 = frη (si , ai ).
• State Transition Model: A regression or density estimation model predicts the next state, s′i+1 ∼
fsη (si , ai ).

22.1 Types of Dynamics Models

• Deterministic Models: The model outputs a single predicted next state, s′i+1 = fsη (si , ai ). This
is suitable for environments with low stochasticity.
• Stochastic Models: The model outputs a probability distribution over the next state, from which
a sample can be drawn. This is more robust for uncertain environments.

22.2 Combining Model-Free RL with a Model - Background Planning

A common approach is to use a learned model to generate synthetic data, which is then used to train
a separate model-free RL algorithm. This is a powerful way to boost sample efficiency. However, major
challenges is:
• Distribution shift: the model’s accuracy is limited to the states it has seen.
• Long synthetic rollouts can accumulate prediction errors, leading to a “bad” policy.

43
22.2.1 Model-Based RL: Broken → Fixed Progression (MBPO)
1. Naı̈ve Model-Based RL (v0.5) — Broken
Algorithm:

1. Collect initial dataset Denv in the real environment using policy πθ .

2. Loop:

(a) Model learning: Fit dynamics model P̂ (s′ |s, a) on Denv .

(b) Policy updates:
i. Simulate full trajectories entirely in P̂ starting from the initial state distribution.
ii. Update πθ to maximize returns in P̂ .
(c) No new real data collected here — major flaw.

Why broken:

• Severe distribution shift and compounding model errors when rollouts go far from seen states.

2. Interleaving with Real Data (v0.8)

Algorithm:

1. Initialize Denv with real transitions from an initial policy πθ .

2. Loop:

(a) Model learning: Train dynamics model P̂ on Denv .

(b) Policy updates:
i. Simulate trajectories entirely in P̂ to create Dmodel .
ii. Update πθ using Dmodel .
(c) Collect real data: Deploy πθ in the real environment for N steps and add to Denv . ← new change

Improvement:

• Model continuously updated with states from current policy.

Still broken:

• Long simulated rollouts still accumulate large prediction errors.

3. Short Model Rollouts from Real States (v1.0)

Algorithm:

1. Initialize Denv with real transitions from an initial policy πθ .

2. Loop:

(a) Collect real data: Deploy πθ in the real environment for N steps and add to Denv .
(b) Model learning: Train dynamics model P̂ on Denv .
(c) Policy updates:

44
 i. Sample real states from Denv .
ii. Perform short rollouts (1–5 steps) in P̂ from those states to create Dmodel . ← new change
iii. Train πθ on Dmodel ∪ Denv . ← new change

Improvement:

• Reduces distribution shift since all rollouts start from real states.

• Limits compounding errors with short horizons.

22.2.2 Dyna-Q Style Algorithm - MBPO

This algorithm uses a model to supplement real-world experience, often in a continuous loop.
Algorithm:

1. Run base policy π0 (a|s) in the real environment to collect Denv = {(s, a, r, s′ )}i .

2. Learn environment model fη (s, a) using Denv .

3. Pick states Si from Denv , use fη (s, a) to make short rollouts; add to Dmodel .

4. Use both Denv and Dmodel to update πθ (a|s) via any off-policy RL algorithm (e.g., DQN, SAC).
← picks states from both env and the model

5. Deploy πθ (a|s) in the real environment, appending (s, a, r, s′ ) to Denv and repeat.

This approach uses short rollouts from the model to avoid accumulating errors and combines real data
to anchor learning, leading to more stable performance.
Improvement:

• Combines sample efficiency of model rollouts with realism of real data.

State coverage advantage:

• Model rollouts may reach states not yet visited in the real environment (from s0 ).

• Expands exploration coverage without costly real-environment interaction.

22.2.3 Direct Policy Learning with a Model

This approach directly optimizes the policy by backpropagating gradients through the learned dynamics
model. The key idea is to treat the environment model as part of the computational graph.

1. Run the policy πθ in the real environment to collect a dataset Denv .

2. Learn a dynamics model fη (s, a) from Denv .

3. To improve the policy, unroll the policy’s actions through the model’s dynamics for a few steps. The
reward from this unrolling is used to compute a loss.

4. Backpropagate the gradients of this loss through the dynamics model and into the policy network to
update the policy parameters θ.

5. Repeat the process by running the updated policy in the real environment to collect new data.

45
This method can be very sample-efficient, but it can suffer from issues like vanishing or exploding gradients
when unrolling over many time steps, and its effectiveness is highly dependent on the accuracy of the learned
model.
Benefit:

• End-to-end differentiable optimization.

Downside:

• Sensitive to model inaccuracies.

• Gradient instability for large H (Vanishing/Exploding gradients).

Summary Table

Version Change Main Benefit Remaining Problem

v0.5 Train policy only in model High sample efficiency Severe shift, compounding error
v0.8 Periodic real data collection Reduces shift Still long rollout errors
v1.0 Short rollouts from real states Limits error growth Short horizon only
MBPO Mix real + model data Stable + efficient Needs tuning
Direct BP Backprop through model Gradient-based planning Numerical instability

23 Model Based - Decision-Time Planning

The goal is to find the action sequence that maximizes the sum of future reward.
In contrast to background planning, which improves the policy over time, decision-time planning uses the
model to select the best action for the current state. The model is essentially used as a simulator to find an
optimal action sequence. The goal is to find an action sequence that maximizes the sum of future rewards:
T
X
a1 , . . . , aT = arg max γ t−1 rη (st , at ) s.t. st+1 = fη (st , at )
a1 ,...,aT
t=1

23.1 Stochastic Optimization

• Random Shooting Method: This method samples a large number of random action sequences
and evaluates each one using the learned model. The first action of the best-performing sequence is
then executed. This is simple but can be inefficient in high-dimensional or long-horizon problems.

• Cross-Entropy Method (CEM): CEM is an iterative optimization algorithm that refines a dis-
tribution of action sequences.

1. Sample a number of action sequences from a distribution (e.g., a Gaussian).

2. Evaluate the performance of each sequence using the model.
3. Select the top-performing “elite” sequences.
4. Fit a new distribution to these elite sequences to generate the next batch of samples.
5. Repeat until convergence.

46
23.2 Monte Carlo Tree Search (MCTS)
MCTS is a planning algorithm that explores a search tree to find the best action. It is commonly used in
game-playing (e.g., AlphaGo).

1. Selection: Starting from the root, traverse the tree by choosing actions that balance exploration
(visiting less-explored nodes) and exploitation (choosing nodes with high value estimates) until a leaf
node sL is reached. A common selection strategy is the UCT formula:
s
log N (s)
Q(s, a) + c
N (s, a)

2. Expansion: If the selected leaf node has not been fully expanded, create a new child node for an
unvisited action.

3. Simulation: From the new leaf node, run a simulation (a “rollout”) using a fast default policy until
a terminal state is reached.

4. Backpropagation: The result of the simulation is used to update the value estimates and visit
counts of all nodes from the leaf back to the root.

23.3 Model-Based RL with Decision-Time Planning

This approach, often called Model Predictive Control (MPC), combines a learned model with decision-time
planning.

1. Collect data using an initial policy and learn a dynamics model fη (s, a).

2. For a given state, use the learned model and a planning algorithm (e.g., CEM or MCTS) to find the
best sequence of actions.

3. Execute only the first action of this sequence in the real environment.

4. Observe the next state, add the transition to the dataset, and repeat the process for the new state.

This is a robust method because it uses the model for planning, but only commits to the first action,
allowing it to replan at every step with new, real-world information.

23.4 Uncertainty in RL
23.4.1 Sources
• Epistemic (model uncertainty): Due to limited data; reduces with exploration.

• Aleatoric (intrinsic randomness): Due to stochasticity in environment; cannot be reduced.

23.4.2 In Model-Based RL
Learned dynamics model fη (s, a) may be inaccurate in unexplored regions → planning might exploit these
errors.

• Example: MPC planning might choose actions leading into regions of high prediction uncertainty
(red circled areas in plots).

47
23.4.3 Mitigation
• Use ensembles or Bayesian models to estimate epistemic uncertainty.
• Penalize reward in high-uncertainty states (uncertainty-aware planning).
• Combine real and simulated rollouts cautiously; trust short rollouts more in uncertain regions.

23.5 Uncertainty in Neural Networks

23.5.1 Estimate model uncertainty (how unsure the parameters are)
How probable is θ given the dataset. This probability will have an entropy, which will say how uncertain
the model is.
• Find p(θ | D) — distribution of parameters given data.
• Entropy of p(θ | D) = how uncertain the model is.
Prediction Average over possible parameters:
Z
p(st+1 | st , at , D) = p(st+1 | st , at , θ) p(θ | D) dθ

Avoid overconfident exploitation of model errors; uncertainty estimates guide safer, more reliable ex-
ploration and planning.

23.5.2 Bootstrap Ensembles

If you have K environment models of the environment and they all predict the same state transition -
p(st+1 | st , at , θ), the uncertainty is low; if their predictions differ, the uncertainty is high.

Method:
• Dataset: D = {(s, a, r, s′ )}i .
• Train K models.
• For each model, sample batches D1 , D2 , . . . , DK with replacement from D.
Before: Plan using one model:
T
X
a1:T = arg max γ t rη (st , at ) s.t. st+1 = fη (st , at )
a1:T
t=1

Now: Plan using K models (ensemble) and average rewards:

K X
X T
a1:T = arg max 1
K
γ t rηi (st,i , at )
a1:T
i=1 t=1

where st+1,i = fηi (st,i , at ).

Key idea: Choose actions that perform well on average across all models → robust to model uncer-
tainty.

Diversity in environment model comes from:

48
 • Different neural network initializations.

• Different training samples for each model.

Benefit: Differences between models give an estimate of epistemic uncertainty.

23.5.3 Bayesian Neural Networks (BNNs)

• Goal: Capture model uncertainty by learning a distribution over network weights.

• Parameter Uncertainty: Estimate the posterior p(θ | D).

• Uncertainty Measure: Entropy of p(θ | D) indicates model uncertainty.

• Prediction: Average over possible parameter values:

Z
p(st+1 | st , at , D) = p(st+1 | st , at , θ), p(θ | D), dθ

• Benefit: Earlier we had scalar values for the parameter (θ), now we will have µ and σ from which
we can see for a given input how much the output can vary. Here we are directly encoding the
probability of θ.

23.6 Latent Space Models

In RL, especially when observations are high-dimensional (e.g., images), we often compress them into a
low-dimensional latent state space st using an encoder.
Then, the environment’s components are modeled separately in this latent space:

• Observation Model p(ot | st ): Maps latent state st back to observation ot . Handles high-
dimensional data (like pixels). Doesn’t need to model temporal dynamics.

• Dynamics Model p(st+1 | st , at ): Predicts the next latent state from the current one and the action.
Low-dimensional but must capture temporal dependencies.

• Reward Model p(rt | st , at ): Predicts reward from latent state and action.

24 Safe Reinforcement Learning

24.1 Overview of Safety Problems
Safe Reinforcement Learning (Safe RL) is a field dedicated to ensuring that an agent’s behavior adheres
to constraints and avoids undesirable, potentially harmful, outcomes. Standard RL aims to maximize a
single reward function, which may not be sufficient to guarantee safety. Key issues in Safe RL include:

• Optimal but Unsafe Behavior: An optimal policy can lead to high rewards but also high-risk
actions that should be avoided.

• Safe Exploration: The agent must act safely not only at convergence but also during the training
process, where it actively explores the environment.

• Irreversible States: Preventing the agent from entering states from which a return to a safe state
is impossible.

49
24.2 Constrained Markov Decision Processes (CMDP)
To formalize safety, Safe RL often uses the Constrained Markov Decision Process (CMDP) framework. A
CMDP extends a standard MDP by adding one or more cost functions and associated thresholds.

• Classic MDP: ⟨S, A, P, R, γ⟩, where the objective is to maximize V (s0 ) = Eπ [ ∞ t

P
t=0 γ R(st , at )].

• CMDP: A CMDP adds a cost function C : S × A → R and a set of thresholds bi . The objective is
to maximize the expected return subject to a set of constraints on the expected cumulative cost.

24.2.1 Machiavelli Benchmark

• The Machiavelli Benchmark is a safety-focused evaluation framework for reinforcement learning and
language model agents, designed to test whether they can achieve goals without engaging in unethical
or harmful behaviors.
• Observation: narrative state (NPC offers collusion under threat).
• Actions:
– Deceptive collusion (advance ambitions quickly).
– Honest cooperation (pretend to help, secretly oppose).
– Self-sacrifice (enter the mines to investigate).

24.2.2 Optimally Safe Policies

An optimally safe policy πc∗ is one that achieves the highest possible return while satisfying all safety
constraints.
πc∗ = arg max V (s0 )
πc ∈Πc

where Πc is the set of all policies that satisfy the constraints. These constraints can be on the expected
total cost or on the probability of a catastrophic event.

• Expected Safety: The expected cumulative cost must be below a threshold:

"∞ #
X
fc (π) = Eπ γ t C(st , at ) ≤ bi
t=0

• Almost Surely Safe: The probability of the cumulative cost exceeding the threshold is zero.
∞
!
X
Pπ γ t C(st , at ) ≤ bi = 1
t=0

24.3 Solving CMDPs: Methods

A variety of methods exist to solve CMDPs, including policy constraint algorithms, reward shaping, and
modified action selection strategies.

24.3.1 Constrained Policy Optimization (CPO)

CPO is an extension of the TRPO algorithm that adds a safety constraint. It finds a policy update that
maximizes the objective while ensuring the KL divergence from the old policy and the cumulative cost are
within specified bounds.  
T RP O πθ (ai |si )
max J (θ) = Eπold Aπ (si , ai )
θ πold (ai |si ) old

50
 s.t. Eπθold [DKL (πθold ||πθ )] ≤ δ and Eπθold [C(s, a)] ≤ bi
Insights from TRPO:
• Monotonic Performance Improvement (each time the policy is updated, its expected return (or value)
will be at least as good as, and typically better than, the previous policy).

• Satisfy constraints

24.3.2 Primal-Dual Methods (Lagrangian)

Lagrangian methods convert a constrained optimization problem into an unconstrained one by introducing
a Lagrange multiplier λ for each constraint. The objective is to find a saddle point of the Lagrangian
function.
min max L(θ, λ) = Eπ [R(s, a)] − λ (Eπ [C(s, a)] − b)
λ θ

The method iteratively updates the policy to maximize this objective and the multiplier to enforce the
constraint.
1. Initialize policy parameters θ and Lagrange multiplier λ ≥ 0.

2. For each iteration, compute policy and value losses. The actor loss is augmented with the cost term:

Lθ = −Eπ [log πθ (a|s) · A] − λ (Eπ [C(s, a)] − b)

3. Update θ via a gradient step on Lθ .

4. Update the Lagrange multiplier: λ ← λ + α (Eπ [C(s, a)] − b). This increases λ if the cost constraint
is violated, penalizing future cost increases.
Primal-Dual Methods: Example

• Primal Problem: The original constrained optimization problem is

max f (x) = 3x subject to x − 4 ≤ 0 (or x ≤ 4).

The optimal value is achieved at x = 4, giving f (4) = 12.

• Unconstrained Lagrangian: The constraint is incorporated using a Lagrange multiplier λ, creating

the Lagrangian:
L(x, λ) = 3x − λ(x − 4).

• Dual Problem: The dual method reverses the order of optimization:

min max [3x − λ(x − 4)] .

λ x

We first maximize with respect to x for fixed λ, and then minimize with respect to λ.

Solving via Table Analysis

The values of L(x, λ) are computed in a table for x = 3, 4, 5 and λ = 2, 3, 4:

λ x=3 x=4 x=5

2 10 12 13
3 12 12 12
4 13 12 11

51
 Optimization Steps:

• For each λ, find the maximum value in the row (max over x).

• For λ = 2: max{10, 12, 13} = 13

• For λ = 3: max{12, 12, 12} = 12

• For λ = 4: max{13, 12, 11} = 13

• Now, minimize these maxima over λ: min{13, 12, 13} = 12

So, λ∗ = 3 yields the minimum of the maximum Lagrangian value.

Conclusion

• λ = 3 is the optimal solution to the dual problem,

• The optimal dual value equals the optimal primal value (12).

• This confirms strong duality for this simple linear program.

Summary Table:

λ maxx L(x, λ)
2 13
3 12
4 13
Optimal λ∗ = 3, value = 12.

Limitations of Lagrangian:
You can’t guarantee that the safety constraint will be satisfied. For example, your budget may be to not
exceed 5 speed violations in an autonomous car, but with a Lagrangian method there can still be a 6th
violation, because it only enforces the limit on average rather than in every episode.

24.3.3 State Augmentation (SauteRL)

This method reformulates a CMDP as a standard MDP by augmenting the state with a “safety budget.”
The budget decreases with each cost incurred.

• Augmented State: The state becomes S̃ = S × Z, where Z is a variable that tracks the remaining
safety budget.

• Modified Reward: The agent receives the original reward R(s, a) only if the safety budget is
non-negative (z ≥ 0). Otherwise, the reward is zero.

• Budget Update: The budget is updated at each step: zt+1 = zt − fc (st , at ), with an initial budget
z0 = bi .

A standard RL algorithm (e.g., PPO or SAC) can then be used to solve this augmented MDP. This allows
the policy to generalize across different constraints by simply changing the initial budget.

52
24.3.4 Action Selection (MASE)
The Meta-Algorithm for Safe Exploration (MASE) is a high-level approach that guides exploration to
prevent unsafe actions. It assumes a safety margin and an emergency stop action.
• Uncertainty Quantification: A model estimates the cost of an action and its uncertainty, Γ(s, a).
• Safe Actions: A set of “safe” actions is defined as those where the estimated cost plus uncertainty
does not exceed the safety threshold, i.e., A+ = {a | µ(s, a) + Γ(s, a) ≤ bi }.
• Exploration: The agent’s policy is restricted to choosing actions from the safe set A+ . If no safe
actions are available, an emergency action (e.g., stopping) is taken.
This ensures the agent acts safely during training while learning a policy that is also safe at convergence.

Definition of a Safe Action in MASE

An action is safe if:
a ∈ A and µ(si , a) + Γ(si , a) ≤ bi
where:
• µ(si , a) → predicted safety cost (learned with a neural net, for example)
• Γ(si , a) → uncertainty bound on the prediction. (Γ - Capital Gamma)
• bi → maximum allowed cost
Safety means: Even in the worst case (prediction + uncertainty), the cost stays within the limit.

How MASE Works (Step-by-Step)

At each time step h:
1. The agent is in state sh .
2. It looks at the set of safe actions:
A+
h = {a | µ(sh , a) + Γ(sh , a) ≤ b}

3. If safe actions exist (A+

h ̸= ∅):

• Pick one (via your RL policy) and execute it.

• Continue exploring.
4. If no safe action exists (A+
h = ∅):

• Trigger emergency stop action â (from Assumption 2).

• This keeps the agent in a safe state but comes with a large penalty so it learns to avoid such
dead ends.

Why it works:
This guarantees almost sure safety because at every step:
• You either take a provably safe action.
• Or you stop immediately before violating constraints.

53
24.4 Frontiers in Safe RL
Safe RL is a rapidly evolving field with ongoing research in several key areas:

• Safe Offline RL: Learning safe policies from a fixed dataset without further interactions.

• Safe Model-Based RL: Using a learned model to plan for safe, long-horizon behaviors.

• Safe Exploration: Developing methods to learn and explore safely in the real world.

• Reward Hacking: Preventing agents from finding unintended ways to get high rewards that violate
human-defined safety principles.

25 Exploration in RL
25.1 Random Exploration
Random exploration is a fundamental strategy for balancing the trade-off between exploration (trying
new actions to find better policies) and exploitation (choosing the best-known action).

• ϵ-Greedy: This is a simple but effective strategy where, with a probability of 1 − ϵ, the agent selects
the action with the highest estimated value (Q-value). With probability ϵ, it chooses a random
action. The value of ϵ is often decayed over time to shift the balance from exploration to exploitation
as the agent learns more about the environment.

• In Deep RL: For continuous action spaces, exploration can be achieved by adding noise (e.g.,
Gaussian noise) to the agent’s deterministic policy output. For discrete actions, a softmax function
over the Q-values or an entropy regularization term in the policy’s objective can be used to encourage
randomness.

25.2 Novelty Seeking Exploration

Novelty-seeking methods provide an intrinsic reward to the agent for visiting new or less-explored states.
This encourages the agent to actively seek out new information.

• Count-Based Exploration: A bonus reward is given for visiting a state. The bonus is inversely
proportional to p
the number of times the state has been visited. For example, the bonus could be
B(N (s, a)) = 1/ N (s, a), where N (s, a) is the visit count for a state-action pair.

• Pseudo-Counts: For environments with large or continuous state spaces, it’s not feasible to keep
a simple count. Pseudo-count methods use a density model to approximate how many times a state
has been visited. The bonus is based on the novelty of a state as measured by this model.

• Prediction Errors: The agent’s bonus reward is proportional to the error of a predictive model
(e.g., a neural network) trying to predict the next state. High prediction error suggests a novel state,
encouraging the agent to explore it further.

25.3 Posterior Sampling Methods

These methods, also known as Bayesian exploration, model the uncertainty in the value function or model
of the environment.

54
 • Upper Confidence Bound (UCB): An optimistic exploration strategy that p adds a bonus to the
Q-value based on the uncertainty of the action’s value. The bonus term, c ln t/Nt (a), encourages
the agent to choose actions with high estimated values and actions that have been tried less often
(Nt (a) is low).

• Bootstrapped DQN: An ensemble of K Q-networks is trained on bootstrapped samples from the

replay buffer. At the start of each episode, one Q-network is randomly selected, and the agent follows
its greedy policy. This method effectively samples from a posterior distribution over Q-functions.

26 Transfer Learning in RL
Transfer learning aims to leverage knowledge from a source task to accelerate learning in a new, target
task.

26.1 Domain Adaptation

Domain adaptation addresses the challenge of transferring a policy from a source environment (e.g., a
simulator) to a target environment (e.g., the real world) where the observations or dynamics may be
different.

• Observation Adaptation: This involves learning a representation of the state that is invariant
to the domain (e.g., ignoring visual differences between a simulated and real robot arm). Adver-
sarial methods are a common approach, where a domain classifier is trained to distinguish between
source and target observations, while an encoder is simultaneously trained to fool the classifier, thus
producing a domain-invariant representation.

• Dynamics Adaptation: When the physics of the two environments differ, the dynamics model
can be adapted. This can be done by using a penalty on transitions that are unlikely in the target
environment.

26.2 Domain Randomization

Instead of trying to match the source domain to the target, domain randomization varies the source
domain’s parameters (e.g., friction, lighting, textures) to such a degree that the learned policy becomes
robust enough to generalize to the real-world target domain.

26.3 Multi-Task Transfer

This involves learning a single policy that can solve multiple tasks simultaneously or a policy that can
quickly adapt to a new task.

• Contextual Policies: A policy takes both the state and a task-specific context as input: π(a|s, context).
The context can be a one-hot vector representing the task ID or a continuous vector embedding of
the task.

• Goal-Conditioned Policies: The policy is trained to reach any of a set of goals, which are provided
as a part of the input. Hindsight Experience Replay (HER) is a technique that can make this more
data-efficient by “relabeling” past trajectories with the goal that was actually achieved, even if the
intended goal was not met.

55
27 Frontiers in RL
RL is a rapidly advancing field with many open challenges and new research directions.

27.1 Meta-Learning
Meta-learning, or “learning to learn,” aims to create agents that can quickly adapt to new tasks from a
distribution of tasks.

• Model-Agnostic Meta-Learning (MAML): An algorithm that learns a good set of initial policy
parameters such that a policy can be adapted to a new task with only a few gradient steps.

27.2 Inverse Reinforcement Learning (IRL)

IRL addresses the reward specification problem by inferring a reward function from expert demon-
strations. Instead of manually designing a reward, the agent learns what the expert’s goal is by observing
their behavior.

27.3 Hierarchical RL
Hierarchical RL introduces a hierarchy of policies to solve complex, long-horizon problems. A high-level
policy selects a “sub-goal” or “option,” which is then executed by a lower-level policy. This provides a
temporal abstraction that can make learning more efficient.

27.4 Foundation Models for RL

Recent research explores using large pre-trained models (e.g., LLMs) to provide high-level planning, world
models, or reward functions. The idea is to pre-train a model on a vast amount of data and use it as a
foundation for decision-making.

27.5 Continual RL
Continual RL focuses on agents that operate in vast, non-stationary worlds without a clear start or end,
where rewards are sparse, and the environment changes over time. Challenges include irreversibility, rich
observations, and catastrophic forgetting.

28 Sample Question and Answer

Question 1: REINFORCE with Baseline
The policy gradient update with a baseline is given by θt+1 = θt + α∇θ log πθ (At |St )(Gt − b(St )),
where Gt is the Monte-Carlo return and b(St ) is a learned value function v̂(St , w).

1. Why is it mathematically valid to subtract a baseline b(St ) that only depends on the
state? Explain why this does not introduce bias into the policy gradient estimate. ( 2
sentences)
Answer: Subtracting a state-dependent baseline b(St ) is valid because its expected value, when
multiplied by the score function ∇θ log πθ (a|s), is zero. This property ensures that the expectation
of the overall gradient estimate remains unchanged, meaning the update is still an unbiased estimate
of the true policy gradient.

56
 2. What is the primary practical benefit of using a baseline in policy gradient methods,
and how does the term (Gt − b(St )) relate to the advantage function? ( 3 sentences)
Answer: The primary benefit of using a baseline is to reduce the variance of the policy gradient
estimates, which leads to more stable and faster learning. The term (Gt − b(St )) is a Monte-Carlo
estimate of the advantage function A(St , At ). This is because Gt is an estimate of the Q-value
qπ (St , At ) and the baseline b(St ) is an estimate of the state-value vπ (St ).

Question 2: Proximal Policy Optimization (PPO)

The PPO algorithm uses a clipped surrogate objective:
h  i
max Eπθold min rt (θ)Ât , clip(rt (θ), 1 − ϵ, 1 + ϵ)Ât
θ

πθ (At |St )
where rt (θ) = πθold (At |St )
.

1. What is the fundamental problem that the clip function is designed to prevent?
Answer: The clip function is designed to prevent the policy from making excessively large updates
by discouraging the probability ratio rt (θ) from moving too far from 1. This avoids catastrophic
performance collapses that can occur with unconstrained on-policy updates, effectively creating a
“trust region.”

2. How does this objective offer a simpler and more practical alternative to its predecessor,
TRPO?
Answer: PPO’s clipped objective provides a simpler, first-order optimization method to constrain
the policy update. This avoids the complex and computationally expensive second-order optimization
(like conjugate gradient) required by TRPO to solve its KL-divergence constraint.

Question 3: Soft Actor-Critic (SAC)

The SAC objective function is augmented with an entropy term:
X
π ∗ = arg max Eρπ [r(st , at ) + αH(π(·|st ))]
π
t

1. What is the primary role of the temperature parameter α? Answer: The temperature
parameter α controls the trade-off between maximizing the cumulative reward and maximizing the
policy’s entropy.

2. What are two key benefits of maximizing policy entropy in addition to the expected
reward, and how is this reflected in the soft Q-function update? Answer: Maximizing
entropy encourages better exploration by preventing premature convergence to a suboptimal policy
and leads to more robust, stable policies. This is reflected in the soft Q-function update by adding
the entropy of the next state’s policy to the target value: yi = ri + γ(minj Qj (s′ , a′ ) − α log π(a′ |s′ )).
This modification ensures that the value functions account for the future entropy rewards.

Question 4: Offline Reinforcement Learning (CQL)

Offline RL learns from a fixed dataset, which presents a major challenge known as distribution shift.

57
 1. Briefly explain why out-of-distribution (OOD) actions are problematic for standard off-
policy algorithms like Q-learning in the offline setting. Answer: Standard Q-learning can
produce erroneously high Q-values for OOD actions not present in the data because the function
approximator has no data to constrain its estimates for those actions. The policy then learns to
exploit these errors, leading to poor performance when deployed in the real world.

2. The Conservative Q-Learning (CQL) algorithm adds a specific regularizer to the Bell-
man error loss. What is the high-level goal of this regularizer, and what two things
does it do to the Q-function? Answer: The high-level goal of the CQL regularizer is to combat
Q-value overestimation for OOD actions. It explicitly pushes down the Q-values for actions that
are likely OOD (sampled from a distribution µ(a|s)). Simultaneously, it pushes up the Q-values for
actions that are actually present in the dataset.

Question 5: Dynamic Programming vs. Model-Free Control

Consider two fundamental algorithms: Value Iteration (a Dynamic Programming method) and Q-Learning
(a Model-Free Control method). Both aim to find the optimal action-value function q ∗ .

1. What is the single most important difference in the assumptions these two algorithms
make about the environment? ( 2 sentences) Answer: Value Iteration assumes a complete
model of the environment is known, meaning it requires the full transition probabilities p(s′ , r|s, a)
and reward function R(s, a). Q-Learning, being model-free, makes no such assumption and can learn
directly from sampled experiences (s, a, r, s′ ) without knowing the underlying dynamics.

2. Given that Value Iteration can be more computationally efficient for small, known
environments, why is Q-Learning often more practical for solving large-scale or real-
world problems? ( 2 sentences) Answer: In most real-world problems, the true dynamics of
the environment are unknown and far too complex to be explicitly defined or stored. Q-Learning’s
ability to learn from direct interaction and experience makes it applicable to these complex scenarios
where building an explicit model is infeasible.

Question 6: On-Policy vs. Off-Policy Learning

Sarsa is a classic on-policy TD control algorithm, while Q-Learning is its off-policy counterpart.

1. Explain the difference in their update rules and how it relates to their on-policy vs.
off-policy nature. ( 2 sentences)

• SARSA update: Q(St , At ) ← Q(St , At ) + α[Rt+1 + γQ(St+1 , At+1 ) − Q(St , At )]

• Q-Learning update: Q(St , At ) ← Q(St , At ) + α[Rt+1 + γ maxa′ Q(St+1 , a′ ) − Q(St , At )]

Answer: Sarsa is on-policy because it uses the action At+1 actually taken by the current policy
to form its target, learning the value of the policy it is currently following. Q-Learning is off-policy
because it uses the greedy action maxa′ Q(St+1 , a′ ) to form its target, learning the value of the optimal
(greedy) policy, regardless of which exploratory action was actually taken.

2. What is the main advantage of off-policy learning (like Q-Learning) over on-policy learn-
ing (like Sarsa) in terms of data efficiency? Why might an on-policy method sometimes
be preferred? ( 3 sentences) Answer: The main advantage of off-policy learning is data effi-
ciency, as it can learn the optimal policy from data generated by any behavior policy, including old
data stored in a replay buffer. On-policy methods, in contrast, must discard data after each policy

58
 update. However, an on-policy method might be preferred for its stability, as it directly learns about
the consequences (the feedback you get from the environment is of the current policy and not using
a different policy like off-policy) of the policy it’s actually executing, which can lead to smoother
convergence, especially in the presence of function approximation.

Question 7: Model-Based Reinforcement Learning

Model-based RL approaches learn a model of the environment to aid in policy learning.

1. What is the primary advantage and a key disadvantage of model-based RL? ( 2 sen-
tences) Answer: The primary advantage is sample efficiency, as the learned model can generate
many simulated experiences, reducing the need for real-world interaction. A key disadvantage is that
the performance is limited by the accuracy of the learned model; errors in the model can be exploited
by the policy, leading to poor real-world performance.

2. How does the “Dyna-Q” style algorithm, which combines model-based and model-free
elements, attempt to mitigate this key disadvantage? ( 2 sentences) Answer: Dyna-
Q mitigates the problem of model error by continuously updating the model with real experience
collected from the environment. It combines planning with model-generated data and learning from
real data, which helps to correct for inaccuracies in the model and ground the policy in reality.

Question 8: Deep Deterministic Policy Gradient (DDPG)

DDPG is an off-policy algorithm designed for continuous control.

1. Why is DDPG considered an “Actor-Critic” algorithm? Briefly describe the roles of

the actor and the critic. ( 2 sentences) Answer: DDPG is an Actor-Critic algorithm because it
uses two separate networks: an actor that learns a deterministic policy (µθ (s)) to select actions, and
a critic that learns a Q-function (Qw (s, a)) to evaluate those actions. The critic guides the actor’s
learning by providing a gradient signal, telling the actor how to adjust its policy to select actions
that lead to higher Q-values.

2. Since the actor’s policy is deterministic, how does DDPG ensure sufficient exploration of
the state-action space during training? ( 1 sentence) Answer: DDPG ensures exploration by
adding noise (typically from a stochastic process like Ornstein-Uhlenbeck or simple Gaussian noise)
to the actions selected by the deterministic actor during the training phase.

Question 9: DDPG vs. SAC: A Mathematical Comparison

1. Deep Deterministic Policy Gradient (DDPG) Equations
DDPG is an off-policy actor-critic algorithm that uses a deterministic policy and a single critic.

Target value:
y DDPG = r + γ Qθ− s′ , µϕ− (s′ )

Where:

• Qθ → critic (estimates Q(s, a)).

• Qθ− → target critic network.

• µϕ → deterministic actor network.

59
 • µϕ− → target actor network.

• r → reward received.

• γ → discount factor.

Critic loss: h
2 i
L(θ) = E(s,a,r,s′ )∼D Qθ (s, a) − y DDPG
Actor loss: 

Jµ (ϕ) = −Es∼D Qθ s, µϕ (s)
The actor maximizes the critic’s Q-value for its chosen actions.
Key features:

• Deterministic policy (no entropy term).

• Single critic network (plus its target copy).

• Policy updates come from deterministic policy gradient.

2. Soft Actor-Critic (SAC) Equations

SAC extends the actor-critic framework with maximum entropy RL and twin critics.

Target value (Clipped Double Q-learning):

h i
y SAC = r + γ Ea′ ∼πϕ min Qθi (s′ , a′ ) − α log πϕ (a′ |s′ )
i∈{1,2}

Where:

• Two critics Qθ1 , Qθ2 — take the minimum to reduce overestimation.

• πϕ (a|s) → stochastic policy (actor network).

• α → temperature parameter controlling entropy weight.

• −α log πϕ (a′ |s′ ) → entropy bonus (encourages exploration).

Critic loss: h
2 i
L(θi ) = E(s,a,r,s′ )∼D Qθi (s, a) − y SAC , i = 1, 2
Actor loss:
Jπ (ϕ) = Es∼D [α log πϕ (a|s) − Qθ1 (s, a)]
The actor trades off between high Q-value and high entropy.
Key features:

• Stochastic policy.

• Two critics with minimum selection.

• Explicit entropy regularization in both target and policy objective.

60
3. Side-by-Side Equation Comparison
Concept DDPG SAC
Policy type Deterministic µϕ (s) Stochastic πϕ (a|s)
Action in target µϕ− (s′ ) a′ ∼ πϕ (a|s′ )
Critics One critic (and target) Two critics (min for stability)
Entropy term None −α log πϕ (a′ |s′ )
Policy update Maximize Q-value deterministically Maximize Q-value + entropy

4. Key Takeaways
• DDPG optimizes a deterministic policy to maximize Q-values, without explicit exploration bonuses.

• SAC optimizes a stochastic policy, balancing exploitation (high Q) and exploration (high entropy).

• SAC’s twin-critic and entropy framework make it generally more stable and robust, especially in
environments where exploration is important.

Question 10: Policy Gradient Derivation: Fill-in-the-Blank Question

In a one-step MDP (contextual bandit), the agent observes a state s ∼ d(s), takes an action a ∼ πθ (a | s),
receives a reward r = Rs,a , and the episode ends.
Let the objective be the expected reward:

J(θ) = Eπθ [r]

Use the score function trick to derive the gradient of J(θ) with respect to θ.
Question: Complete the missing steps Fill in the missing Line 2 and Line 3 below.
Step Equation
P P
Line 1 J(θ) = s d(s) a πθ (a|s)Rs,a
Line 2 You fill this in
Line 3 You fill this in
Line 4 = Eπθ [∇θ log πθ (a|s) · r]

Step Equation
P P
Line 1 J(θ) = sP d(s) aP πθ (a|s)Rs,a
Answer: Line 2 ∇θP
J(θ) = Ps d(s) a ∇θ πθ (a|s)Rs,a
Line 3 = s d(s) a πθ (a|s)∇θ log πθ (a|s)Rs,a
Line 4 = Eπθ [∇θ log πθ (a|s) · r]

Refer to section 4.2 for a detailed answer.

Question 11: What is Conservative Q-Learning (CQL) and what problem does it aim to solve
in Reinforcement Learning?
Refer to section 17.5 for detailed explanation.

Answer:

• Conservative Q-Learning (CQL) is an offline reinforcement learning algorithm designed to learn

effective policies from fixed datasets without additional environment interaction.

61
 • The key problem CQL addresses is overestimation of Q-values for out-of-distribution (OOD)
actions — i.e., actions not well-represented in the offline dataset. Traditional Q-learning methods
can assign high values to these unseen actions, leading to poor policy performance when deployed.
• CQL solves this by penalizing the Q-function for assigning high values to unseen or less-
likely actions. It enforces a form of conservatism by encouraging the learned Q-values to remain
low for actions outside the data distribution, thus avoiding optimistic extrapolation.
Mathematically, CQL modifies the Q-learning objective by adding a term like:


CQL Objective: min Bellman Error} +α Ea∼π(·|s) [Q(s, a)] − Ea∼D [Q(s, a)]
Q | {z
TD Loss

where:
• D is the dataset distribution,
• π is the learned policy,
• α is a regularization coefficient.
This discourages the policy from assigning high value to actions that are not supported by the dataset.

Question 12: DQN suffers from the problem of overestimation of Q values. The loss function
used in DQN is 2
X
′
L(w) = Ri+1 + γ max
′
q̂ w − (Si+1 , a ) − q̂ w (Si , Ai )
a
i

where w− is the parameters of the target network. Double DQN – an improvement to DQN –
mitigates the issue of overestimation in DQN. Double DQN uses the following loss function:
X   2
′
L(w) = Ri+1 + γ q̂w− Si+1 , arg max
′
q̂w (Si+1 , a ) − q̂w (Si , Ai )
a
i

a. [2 points] Explain using the loss function used for training DQN, what causes the overestimation
problem in DQN ( 2 sentences)
Answer:
• q̂w− (Si+1 , a′ ) is a noisy estimate.

• maxa′ q̂w− (Si+1 , a′ ) systematically always picks up the max positive noise resulting in overesti-
mation.
b. [3 points] Explain how the loss function used in Double DQN addresses the overestimation problem
in DQN ( 3 sentences)
Answer:
• Double DQN aims to decorrelate the network that selects the max action, and the network that
gives the action value corresponding to the selected max action.
• The two networks can have different noisy estimates for action values in a state.
• This reduces the chance of overestimation as for overestimation to happen both networks would
need to have high positive direction noise for the same action in a given state.

62