POLICY GRADIENT

METHODS IN
REINFORCEMENT LEARNING
SAN DIEGO MACHINE LEARNING
JULY 31, 2021

1
HOW TO PARTICIPATE
• One discussion leader, and everyone welcome to participate
• Majority of material comes from Reinforcement Learning
by Sutton and Barto
• Options to approach the content:
• Treat this as a standalone webinar
• Read the book first, and come with questions and discussion items
• Use this meetup as a primer and read the chapters afterward
• Ask questions
• Give feedback. Too fast or too slow? Want to see more of something
or less of something else?
• Have fun!
2
AGENDA
• Recap what reinforcement learning (RL) is
• Elements and formulation as Markov decision processes (MDP)
• Terminology and notation used in RL
• The Bellman equations
• Generalized policy iteration
• Policy gradient methods
• Policy gradient
• REINFORCE algorithm
• Actor-critic methods
• List some policy gradient methods

3
REINFORCEMENT LEARNING
• Reinforcement learning (RL) is about an agent learning from
interacting with its uncertain environment
• The agent interacts by choosing from a set of allowed actions
• It gets feedback from a numeric reward signal
• Goal is to maximize the return, which is the total rewards received
• Reinforcement learning is about exploring the environment and
recording useful information for the future
• RL is sequential decision making; time is intrinsic

4
MARKOV DECISION PROCESSES
• Elements of the fully observable Markov Decision Process (MDP):
• State - at each time step t, the environment is in some state St
• Action - at each time step t, the agent chooses an action At
• Reward - after taking the action, the agent is given a reward signal Rt+1
and subsequently finds itself in a new state St+1

• In a Markov Decision Process, the transition at any given time t

5
only depends on the state St and action chosen At
MDPS AS A GRAPH
• Sometimes it is easier to visualize a MDP as a directed graph
• The states are nodes (big white circles)
• The actions are edges leading from nodes (here with small black circles)
• The rewards are values along
directed edges that take you
to a new state
• Here is the recycling robot
from the book:

6
REINFORCEMENT LEARNING NOTATION
Letter Used for
s State
a Action
r Reward
γ Discount rate
G Return – sum of all future rewards
p Transition probability
v Value function for states
q Value function for state-action pairs
π Policy (πολιτική)
* Optimal choices, e.g. π*
7
BELLMAN EQUATION
• The value function for state s under policy π is a sum of the
rewards received and the value functions for each future state s’
times the probability of winding up there
• Formally:
𝑣π 𝑠 = ෍ π(𝑎, 𝑠) ෍ 𝑝(𝑠 ′ , 𝑟|𝑠, 𝑎) 𝑟 + γ𝑣π 𝑠 ′
𝑎 𝑠 ′ ,𝑟

Probability you Probability you Reward plus

take action a get reward r discounted value
and end in state s' of new state s’
8
BELLMAN EQUATION VISUALIZED
This is a backup diagram
for vπ(s). To compute it:
• We need to sum over each
branch of π(), based on the
probability of each action a
• And sum over of each branch
of p(), based on probability
we wind up in state s’
• The quantity we sum is the 𝑣π 𝑠 = ෍ π(𝑎, 𝑠) ෍ 𝑝(𝑠 ′ , 𝑟|𝑠, 𝑎) 𝑟 + γ𝑣π 𝑠 ′
reward and the discounted 𝑎 𝑠 ′ ,𝑟

value of possible state s’ 9

BELLMAN OPTIMALITY EQUATIONS – V()
• The Bellman optimality equation says the
optimal value for a state must be the same as
the return from the best action
• We can rewrite it recursively

10
BELLMAN OPTIMALITY EQUATIONS – Q()
• The Bellman optimality equation for
state-action pairs is very similar.
• The optimal value for a state-action pair
must be the same as the return from the
reward and best next action
• It also can be written recursively

11
POLICY ITERATION
• The book shows a sequence like this:
𝐸 𝐼 𝐸 𝐼 𝐸 𝐼 𝐸
π0 ՜ 𝑣π0 ՜ π1 ՜ 𝑣π1 ՜ π1 ՜ … ՜ π∗ ՜ 𝑣∗
• The arrows with E’s are full
cycles of iterative policy
evaluation
• And the arrows with I’s are
policy improvement

12
GENERALIZED POLICY ITERATION
• The term generalized policy iteration (GPI)
refers to the general idea of letting policy
evaluation and policy improvement
processes interact
• Doesn’t matter how fully each evaluation or
improvement step runs, or if they exactly
alternate

13
REINFORCEMENT LEARNING CONTROL
• With this foundation, there’s a lot we can tackle
• Algorithms for learning
• Dealing with memory and compute limitations
• Getting models to converge quickly
• We also still have many challenges
• Reward design – effectively communicating the real goal
• Sparse rewards
• Credit assignment – which actions in trajectory contributed
• Exploration vs. exploitation

14
MONTE CARLO EXPLORING STARTS

15
TD(0)

16
POLICY GRADIENT METHODS

17
POLICY GRADIENTS
• Prior discussions were all about estimating value functions,
and then using those to derive good policies
• With policy gradients, you build a parameterized policy
• Start with some parameters θ (a vector)
• Build a complex function f() which outputs a vector of action probabilities
• So we are generating actions without needing models or value
functions as intermediaries
• The book uses the notation:
• π(𝑎|𝑠, θ)=Pr 𝐴𝑡 = 𝑎|𝑆𝑡 = 𝑠, θ𝑡 = θ
• I’m saying in simpler language:
• π(𝑎|𝑠, θ)=f(s,θ)
18
PARAMETERIZED POLICY
• A neural network example to construct this function f():
Softmax activation

probabilities
State info (s)

Action

(π)
Neural network weights (θ)
19
HOW POLICY GRADIENTS WORK
• After parameterizing our policy on θ…
• We create a scalar performance measure J(θ)
• This function J(θ) clearly must have something to do with the rewards
that we get, in order to be helpful
• For episodic MDPs starting in state s0, we define 𝐽(𝜃) =ሶ 𝑣𝜋𝜃 (𝑠0 )
• We’re familiar with a scalar loss function L(θ) for neural networks
• We wish to maximize performance, so we perform gradient ascent
• Again, this is analogous to gradient descent on our loss function
• We can iterate small tweaks to θ with learning rate α:
θ𝑡+1 = θ𝑡 + α ∙ ∇J(θ𝑡 )
20
ADVANTAGES OF POLICY-BASED RL
• Before getting into more details about how policy gradients work:
• Advantages
• Sometimes policy space is simpler than value space
• Better convergence properties
• Effective in high-dimensional and continuous action spaces
• Can learn stochastic (mixed) policies
• Disadvantages
• Alternatively, sometimes the value space is simpler than the policy space
• Typically converges to a local optimum, not the global optimum
• Evaluating a policy is typically (sample) inefficient and high variance
21
CALCULATING THE POLICY GRADIENT
• Conceptually, we will tweak our parameters based on the gradient of
the performance function, ∇J(θ𝑡 ), but how do we calculate this
gradient?
• In supervised learning, the loss function is usually relatively simple,
and we can easily calculate the partial derivative analytically
• Here, return is a long sum of products involving the environment’s
dynamics
• In the Andrew Ng ML course the gradient is calculated by finite
differences, where you perturb each dimension by a small ϵ
𝜕𝐽(𝜃) 𝐽 𝜃 + 𝜖𝑢𝑘 − 𝐽(𝜃)
≈
𝜕𝜃𝑘 𝜖
where 𝑢𝑘 is the unit vector in the kth dimension of θ
22
POLICY GRADIENT THEOREM
• We might expect it to be difficult to tweak θ to steadily improve
J(θ), because changing θ not only changes the policy’s actions,
but also indirectly changes the distribution of states you visit
• We’re assuming we are doing model-free learning, and don’t
know the state distribution function of the environment
• The policy gradient theorem provides an analytic expression for
the gradient of performance that does not use the derivative of
the state distribution
• So we can calculate the gradient analytically without knowing the
model dynamics
23
POLICY GRADIENT THEOREM [2]
• The policy gradient theorem tells us the gradient is proportional to
the following quantity:

where μ(s) is the distribution of states when following policy π

• The constant of proportionality has to do with the length of the episode,
but since we are multiplying the gradient by a step size α, we can absorb
this scaling factor into our choice of α
• We can reformulate the above as:
∇𝐽 𝜃 = 𝐸 𝑞𝜋 (𝑠, 𝑎)∇ log 𝜋(𝑎|𝑠, 𝜃)

24
REINFORCE: MONTE CARLO POLICY GRADIENT
• If we consider the perspective of a given state St and action At in an
episodic MDP, the previous equation becomes:
∇𝐽 𝜃 = 𝐸 𝐺𝑡 ∇ log 𝜋(𝐴𝑡 |𝑆𝑡 , 𝜃)
• And our update rule is:
𝜃𝑡+1 = 𝜃𝑡 + 𝛼𝐺𝑡 ∇ log 𝜋(𝐴𝑡 |𝑆𝑡 , 𝜃𝑡 )

25
REINFORCE WITH BASELINE
• The REINFORCE algorithm is the simplest form of policy gradient
control
• The returns Gt are an unbiased estimate of 𝑞𝜋 (𝑠, 𝑎), but they are
high variance
• It can be shown that REINFORCE remains unbiased if you
subtract a baseline that can depend on the state, but not the
action. Our new update is:
𝜃𝑡+1 = 𝜃𝑡 + 𝛼 𝐺𝑡 − 𝑏(𝑆𝑡 ) ∇ log 𝜋(𝐴𝑡 |𝑆𝑡 , 𝜃𝑡 )
• A natural choice for b() would be the estimated value function v(St)
• We can use our Monte Carlo samples to simultaneously update our
estimate of the value function and do our policy gradient updates
26
ACTOR-CRITIC METHODS
• In actor-critic methods, our policy gradient learner is the actor,
and the critic is a learned value function that provides some form
of guidance/feedback to the way the actor learns
• A simple thing we can do is
use one-step reward signal
instead of full episodic returns,
the same way we moved from
Monte Carlo methods to
temporal-difference learning
• And just like TD, this introduces
bias, but reduces variance
27
ONE-STEP ACTOR-CRITIC

28
SOME POLICY GRADIENT METHODS
• A2C – Advantage Actor-Critic (synchronous). Multiple actors; the
advantage is the reward minus the average reward
• DDPG – Deep Deterministic Policy Gradient. Deterministic policies
• TRPO – Trust Region Policy Optimization. Clip max value of updates
• PPO – Proximal Policy Optimization. Simpler clipping that TRPO
• SAC – Soft Actor-Critic. Incorporates entropy of policy to encourage
exploration
• TD3 – Twin Delayed Deep Deterministic. Uses tricks from Double
DQN applied to DDPG
[Link]
29
RECAP
• Review what reinforcement learning (RL) is
• Elements and formulation as Markov decision processes (MDP)
• Terminology and notation used in RL
• The Bellman equations
• Generalized policy iteration
• Policy gradient methods
• Policy gradient
• REINFORCE algorithm
• Actor-critic methods
• List some policy gradient methods

30
QUESTIONS

&

DISCUSSION

31
NEXT SESSION
• In two weeks, Sat. August 14, Ryan will talk about reinforcement
learning techniques in AlphaGo

32