10-703 Fall 2026

Recitation 2

MDPs, Policy Gradient, HW1

Vansh Kapoor

1

Markov Decision Process (MDP)

• Simple way to represent the idea of “state”
• The actions you take will result in new places with new reward/transition functions
• Represented oftentimes by 5 main items
• State Space (S)
• Action Space (A)
• Transition Function (T:SxAxS → Real)
• Represents P(s’|s, a)
• Reward Function (R:SxA → Real)
• Discount Factor (γ)
• The above formulation can also represent
• Reward functions of the form:

R : S × A × S → Real, i.e., R(s, a, s’)

2

MDP Example

3

Markov Decision Process (MDP)

• Markov Property
• The idea of state encapsulating all past information (trajectory)

4

MDP - What can we do?

• Goal - Learn policy π: S → A
• Maximize discounted reward
• Discounting rewards
• Deals with infinite trajectories
• Incentivizes early action
• Discount factor γ

5

MDP - Learning the Policy

• Value function (V: S → Real)
• Represents the estimated value of being in a state while following policy
• Q-value (Q: SxA → Real)
• Represents the estimated value of being in a state and taking an action, then following policy

6

Where does the REINFORCE/A2C

equation come from?

7

Derivatives of the policy objective

8

Derivatives of the policy objective

9

Derivatives of the policy objective

10

Policy Gradient Theorem

Proof:

The term A is unaffected by ah; when we take the expectation outside, the term A evaluates

to zero. Term B in expectation is simply Qπθh (sh, ah).

11

Policy Gradient Theorem

However, since we are in a learning (RL) setup, we cannot calculate this expectation explicitly.

We therefore use Monte Carlo estimation:

1. We first roll out N trajectories

following the policy πθ.

2. The gradient estimate for REINFORCE is given by

3. Similarly, the gradient estimate for the Q-version is given by

However, the Monte-Carlo sampling method often results in a gradient estimate with high variance.

12

For any function b(s) that only depends on the state, we have

The Advantage version is obtained by subtracting the baseline bₕ(s) = Vₕ(sₕ) (independent of aₕ):

where

14

To reduce variance, we replace G with G - v(S_t, w) (this is called the advantage function)

Note: Actions achieving a higher score than the value function have a positive advantage, while actions with a lower score than the value function have a negative advantage. (and adding a baseline doesn’t change expected gradient !)

15

16

Advantage Actor-Critic

17

Some Questions to Think About

1) Can we use policy gradient methods to solve the planning problem in MDPs, i.e., to find the optimal policy?

2) What could be the possible drawbacks?

(Hint: Think about the drawbacks of gradient descent.)

18

A2C/Reinforce/Reinforce with Baseline

Actor outputs probability of picking each action given a state

Critic outputs the predicted value for a given state

Hint 1: Actor and Critic networks should be the same except for input dimension, output dimension, and activation (probability distribution versus value function)

​

Q: Why don’t we use the same backbone w/ different heads here?

19

Generate Episode: run the actor/policy, and save the list of states, actions, and rewards generated (needed for training)

Evaluate Policy: run the actor/policy, and save the undiscounted sum of rewards/length of trajectory (needed for plot creation/testing)

Train: you should have different cases for reinforce, reinforce with baseline, and A2C

Define the losses for each of these and run training (optimizer.zero_grad(), loss.backward(), optimizer.step()) etc)

Run: Within each episode, call env.reset() and step through for max_steps. If terminated, then break and move on to the next episode (make sure to update the states, actions and rewards you've seen in that episode)

20

Compute goal / advantage: Watch out for off-by-one errors in the n-step bootstrap!

Questions?

21

References

Some of the slides are heavily inspired by the notes from the class

17-740: Algorithmic Foundations of Interactive Learning,

and some are directly taken from Sutton & Barto’s Reinforcement Learning: An Introduction

22