Policy Gradients

Policy Gradients

”REINFORCE algorithm”

Remember: Direct gradient descent on RL objective

Note: We don’t know anything about the $p(s_1)$ and $p(s_{i+1}|a_i, s_i)$, but we can approximate it.

We will use a convenient identity to rewrite this equation so that it can be evaluated without knowing the distribution for $p_\theta(\tau)$

Using this identity, we can rewrite the equation

Note:

So if we consider the $\nabla_\theta J(\theta)$, especially the $\nabla_\theta \log p_\theta(\tau)$, we see that

So therefore

Improve by

”REINFORCE algorithm” on continuous space

e.g. We can represent $p_\theta(a_t|s_t)$ as $N(f_{\text{neural network}}(s_t);\Sigma)$ ⇒

1. Sample $\{\tau^i\}$ from $\pi_\theta(a_t|s_t)$ (run it on the robot)

2. $\nabla_\theta J(\theta) \approx \sum_i(\sum_t \nabla_\theta \log \pi_\theta(a_t^i|s_t^i))(\sum_t r(s_t^i, a_t^i))$

3. $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

Partial Observability

What’s wrong?

We see huge differences in fitted policy distributions ⇒ we have a high variance problem

How we can modify policy gradient to reduce variance?

We want to show that the expectation of the previous rewards would converge to 0 so we can rewrite the summation. Note that removing those terms in finite time would change the estimator but it is still unbiased.

We have removed some items from the sum therefore the variance is lower.

With discount factors

The power on the $\gamma$ ⇒ $t’ - t$ is important because now the gradient is NOT decresing with t stepping ⇒ we’re putting less focus on the future rewards in the current step, but in future steps those rewards will be valued more again.

If we let the power be $t’ - 1$ or $t-1$ ⇒ then as we train from $t=0$ to $t \rightarrow \infin$, the gradient would decrease as $t$ increases

Baselines

We want policy gradients to optimize reward actions that are above average and penalize reward actions that are below average.

Without baseline (b = 0), but with baseline, set b as

Changing b will keep the esitimator unbiased but will change the variance!

Average reward is not the best baseline, but it’s pretty good!

Let’s first write down variance

So optimal value of b

Intuition: Different baseline for every entry in the gradient, the baseline for every parameter value is the expected value of the reward weighted by the magnitude of the gradient for the parameter value

Off-policy setting

Policy gradient is defined to be on-policy

The expectatio causes us to need to update samples every time we have updated the policy, but problem is Neural Nets only change a bit with each gradient step.

So we can modify the policy a bit

Instead of having samples from $p_\theta(\tau)$, we have samples from $\bar{p}(\tau)$

We can use importance sampling to accomodate this case

Due to this expectation, we see that our objective becomes this

Where

Therefore,

So… we can estimate the value of some new parameters $\theta '$

We can consider causality(the fact that current action does not affect past rewards) and

Some important terms in this equation:

$\prod_{t’=1}^t \frac{\pi_{\theta ‘}(a_{t ‘} | s_{t ’})}{\pi_{\theta}(a_{t ‘} | s_{t ’})}$ ⇒ future actions won’t affect current weight ⇒ however, looks like we still have the term at the end ⇒ its also a trouble because it’s exponential in $T$

$\prod_{t''=t}^{t'}\frac{\pi_{\theta '}(a_{t ''}|s_{t ''})}{\pi_\theta(a_{t ''} | s_{t ''})}$ ⇒ we cannot complete ignore this because stripping this term would not be gradient descent but actually”Policy Iteration” algorithm

Since the first term is exponential, we can try to write the objetive a bit differently

On-policy policy gradient

Off-policy policy gradient

This does not necessarily give the optimal policy, but its a reasonable approximation.

Policy Gradient with Automatic Differentiation

We don’t want to be inefficient at computing gradients ⇒ use backprop trick

So why don’t we start from the MLE approach to Policy Gradients?

To start doing backprop, let’s define the objective function first.

So we will define our “pseudo-loss” approximation as weighted maximum likelihood

A few reminders about tuning hyper-parameters

1. Gradients has very high variance
   1. Isn’t the same as supervised learning

2. Consider using much larger batches

3. Tweaking learning rates is VERY hard
   1. Adaptive step size rules like ADAM can be OK-ish

Covariant/natural policy gradient

We can view the first order gradient descent as follows

Thank about $\epsilon$ as a high-dimensional sphere.

We can instead put constraint on the distribution of the policy

Where $D(\cdot, \cdot)$ is a distribution dimension measure.

So we want to choose some parameterization-independent divergence measure

Usually KL-divergence

A but hard to plug into our gradient descent ⇒ we will approximate this distance using 2nd order Taylor expansion around the current parameter value $\theta$

Advanced Policy Gradients

Why does policy gradient work?

1. Estimate $\hat{A}^\pi (s_t,a_t)$ (Monte-carlo or function approximator) for current policy $\pi$

2. Use $\hat{A}^\pi(s_t,a_t)$ to get improved policy $\pi '$

We are going back and forth between (1) and (2)

Looks familiar to policy iteration algorithm!

Nice thing about policy gradients:

1. If advantage estimator is perfect, we are just moving closer to the “optimal” policy for the advantage estimator not jumping to the optimal

But how do we formalize this?

If we set the loss function of policy gradient as

Then we can calculate how much we improved by

Here we claimed that $J(\theta’) - J(\theta)$ is equal to the expectation of all discounted advantage estimates in the new trajectory that the new policy would explore.

We will prove by:

But how does this relate to our policy gradient?

We want this approximation to be true so that

And then we can use

to optimize our policy

And use $\hat{A}^\pi(s_t,a_t)$ to get improved policy $\pi’$

But when is this true?

Bounding the distribution change (deterministic)

We will show:

We will assume that $\pi_\theta$ is a deterministic policy $a_t = \pi_\theta(s_t)$

We define closeness of policy as:

$\pi_{\theta’}$ is close to $\pi_\theta$ if $\pi_{\theta’}(a_t \ne \pi_\theta(s_t)|s_t) \le \epsilon$

Implies that we can write the total variation divergence as

Bounding the distribution change (arbitrary)

Schulman, Levine, Moritz, Jordan, Abbeel, “Trust Region Policy Optimization”

We will show:

Closeness:

$\pi_{\theta’}$ is close to $\pi_\theta$ if $|\pi_{\theta’}(a_t|s_t) - \pi_\theta(a_t|s_t)| \le \epsilon$ for all $s_t$

Useful Lemma:

If $|p_X(x) - p_Y(y)| = \epsilon$, there exists $p(x,y)$ such that $p(x) = p_X(x)$ and $p(y) = p_Y(y)$ and $p(x=y) = 1 - \epsilon$

Says:

1. $p_X(x)$ agrees with $p_Y(y)$ with probability $\epsilon$

2. $\pi_{\theta'}(a_t|s_t)$ takes a different action than $\pi_{\theta}(a_t|s_t)$ with probability at most $\epsilon$

Therefore

Bounding the objective value

Assume $|p_{\theta’}(s_t)-p_{\theta}(s_t)| \le 2\epsilon t$

For the objective value, we can bound it by

Where $C$ is a constant being the largest value that the thing in the state exepectation can take on ⇒ its a probability times an advantage ⇒ largest possible reward times the number of time steps.

So:

Therefore for small enought $\epsilon$, $\bar{A}^{\pi}(\theta ')$ is guarenteed to be similar to the true RL objective

Policy Gradients with Constraints

We want to constrain:

It which will result in

A more convenient bound:

We see that the KL divergence bounds the state marginal difference

Note:

So contraining our objective, we have:

For small $\epsilon$, this is guaranteed to improve $J(\theta’) - J(\theta)$

“Dual Gradient Descent” Alternate between:

1. Maximize $L(\theta’, \lambda)$ with respect to $\theta’$

2. $\lambda \leftarrow \lambda + \alpha(D_{KL}(\pi_{\theta’}(a_t|s_t),\pi_\theta(a_t|s_t)) - \epsilon)$

Intuition: raise $\lambda$ if constraint is violated too much

Natural Gradient

As usual, we denote $\bar{A}(\theta’)$ as

When we are doing gradient descent, we are actually optimizing near a region(trust region) in the first order taylor expansion of the objective.

Can we use this fact to simplify the optimization step and use one easy algorithm to take care of this constrained optimization problem?

Let’s look at the gradient of $\bar{A}(\theta’)$

Evaluating this at point $\theta’ = \theta$

Can we just use the gradient then?

Remember in the original policy gradient algorithm, $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

But some parameters change probabilities a lot more than others, we are not considering the KL Divergence in this case

But it seems like the problem can be fixed, notice that

Gradient Descent still poses some kind of constraint $||\theta - \theta’||^2 \le \epsilon$

Think about in parameter space, we are constrained to within some fixed distance(inside a circle) from the original parameter. ⇒ Indeed the learning rate $\alpha = \sqrt{\frac{\epsilon}{||\nabla_\theta J(\theta)||^2}}$ can satisfy this constraint.

But in KL divergence, maybe we want an ellipse? (we want a circle in distribution space)

We will use second order taylor expansion to approximate the KL divergence to make it easier to calculate.

Now we see that the shape of the new ellipse in parameter space is determined by the matrix $F$

We can estimate this $F$ expectation using samples