Policy Gradients

tags

Machine Learning Algorithms, Reinforcement Learning ⭐

Key Idea

The objective is:

$${\theta }^{\star }=\arg \underset{\theta }{max}{E}_{\tau \sim p_{\theta }(\tau )}\left[\sum _{t}r({\mathbf{s}}_t,{\mathbf{a}}_t)\right]$$

To evaluate the objective, we need to estimate this expectation, often through sampling by generating multiple samples from the distribution:

$$J(\theta )=E_{\tau \sim p_{\theta }(\tau )}\left[\sum _{t}r({\mathbf{s}}_t,{\mathbf{a}}_t)\right]\approx \frac{1}{N}\sum _i\sum _{t}r({\mathbf{s}}_{i,t},{\mathbf{a}}_{i,t})$$

Recall that:

$${\mathrm{\nabla }}_{\theta }J(\theta )\approx \frac{1}{N}\sum _{i=1}^N\underset{\sum _{t=1}^T{\mathrm{\nabla }}_{\theta }{\log }_{\theta }{\pi }_{\theta }\left({\mathbf{a}}_{i,t}|{\mathbf{s}}_{i,t}\right)}{\underbrace{{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }\left({\tau }_i\right)}}r\left({\tau }_i\right)$$

This makes the good stuff more likely, and bad stuff less likely, but scaled by the rewards.

Comparison to Maximum Likelihood

policy gradient

${\mathrm{\nabla }}_{\theta }J(\theta )\approx \frac{1}{N}\sum _{i=1}^N(\sum _{t=1}^T{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }\left({\mathbf{a}}_{i,t}|{\mathbf{s}}_{i,t}\right))\left(\sum _{t=1}^{T}r({\mathbf{s}}_{i,t},{\mathbf{a}}_{i,t})\right)$

maximum likelihood

${\mathrm{\nabla }}_{\theta }{J}_{\mathrm{ML}}(\theta )\approx \frac{1}{N}\sum _{i=1}^N(\sum _{t=1}^T{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }\left({\mathbf{a}}_{i,t}|{\mathbf{s}}_{i,t}\right))$

Partial Observability

The policy gradient method does not assume that the system follows the Markovian Assumption! The algorithm only requires the ability to generate samples, and a function approximator for ${\pi }_{\theta }(a_t|o_t)$.

Issues

• Policy gradients have high variance: the gradient is noisy, easily affected by a constant change in rewards

Properties of Policy gradients

1. On-policy

The objective is an expectation under trajectories sampled under that policy. This can be tweaked into an off-policy method using Importance Sampling.

$$\begin{array}{rlr}{\mathrm{\nabla }}_{{\theta }^{\prime }}J\left({\theta }^{\prime }\right)& =E_{\tau \sim {\pi }_{\theta }(\tau )}[\frac{{\pi }_{{\theta }^{\prime }}(\tau )}{{\pi }_{\theta }(\tau )}{\mathrm{\nabla }}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )r(\tau )]\text{ when }\theta \ne {\theta }^{\prime }& =E_{\tau \sim {\pi }_{\theta }(\tau )}\left[\left(\prod _{t=1}^T\frac{{\pi }_{{\theta }^{\prime }}\left({\mathbf{a}}_t|{\mathbf{s}}_t\right)}{{\pi }_{\theta }\left({\mathbf{a}}_t|{\mathbf{s}}_t\right)}\right)(\sum _{t=1}^T{\mathrm{\nabla }}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}\left({\mathbf{a}}_t|{\mathbf{s}}_t\right))\left(\sum _{t=1}^{T}r({\mathbf{s}}_t,{\mathbf{a}}_t)\right)\right]\end{array}$$

Problem: with large T the first term becomes extremely big or small.

Variance Reduction

Causality

The policy at time $t^{\prime }$ cannot affect the reward at time $t$ when $t<t^{\prime }$.

$${\mathrm{\nabla }}_{\theta }J(\theta )\approx \frac{1}{N}\sum _{i=1}^N(\sum _{t=1}^T{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }\left({\mathbf{a}}_{i,t}|{\mathbf{s}}_{i,t}\right))\left(\sum _{t=t^{\prime }}^{T}r({\mathbf{s}}_{i,t},{\mathbf{a}}_{i,t})\right)$$

This is still an unbiased estimator, and has lower variance because the gradients are multiplied by smaller values. This is often written as:

$${\mathrm{\nabla }}_{\theta }J(\theta )\approx \frac{1}{N}\sum _{i=1}^N\sum _{t=1}^T{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }\left({\mathbf{a}}_{i,t}|{\mathbf{s}}_{i,t}\right){\hat{Q}}_{i,t}$$

where ${\hat{Q}}_{i,t}$ is the reward-to-go.

Baseline Reduction

$${\mathrm{\nabla }}_{\theta }J(\theta )\approx \frac{1}{N}\sum _{i=1}^N{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(\tau )[r(\tau )-b]$$

Subtracting a baseline is unbiased in expectation, but may reduce the variance. We can compute the optimal baseline, by evaluating the variance of the gradient, and setting the derivative of the variance with respect to $b$ to 0:

This is just expected reward, but weighted by gradient magnitudes.

Policy Gradient in practice

• Gradients have high variance
• Consider using much larger batches
• Tweaking learning rates might be important
• Adaptive learning rates are fine, there are some policy-gradient oriented learning rate adjustment methods

REINFORCE

1. For each episode,
   1. generate $\tau =s_0,a_0,r_1,\dots ,s_{t-1},a_{t-1},r_t$ by following ${\pi }_{\theta }(a|s)$
   2. For each step $i=0,\dots ,t-1$:
      1. $R_i=\sum _{k=i}^t{\gamma }^{t-k}{r}_k$ (Unbiased estimate of remaining episode return under ${\pi }_{\theta }$ starting from $i$)
      2. $\widehat{A_i}=R_i-b$ (Advantage function: subtract base line $b$ to lower variance)
         1. Advantage function tells you how relatively good this action is
      3. $θ = $\theta +\alpha {\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a|s_i){\hat{A}}_i$

Objective: $J(\theta )=\sum _{\tau }{P}_{\theta }(\tau )R(\tau )$

$$\begin{array}{rl}{\mathrm{\nabla }}_{\theta }J(\theta )& ={\mathrm{\nabla }}_{\theta }\sum _{\tau }{P}_{\theta }(\tau )R(\tau )\\ & =\sum _{\tau }{\mathrm{\nabla }}_{\theta }{P}_{\theta }(\tau )R(\tau )\end{array}$$

Actor critics use learned estimate (e.g. $\hat{A}(s, a) = \hat{Q}(s,

1. • \hat{V}(s).)

Policy Gradients an Policy Iteration

Policy gradients involves estimating $\hat{A}s,a$, and using it to improve the policy, much like policy iteration which evaluates $A(s,a)$ and use it to create a better, deterministic policy.

$$\begin{array}{rl}J({\theta }^{\prime })-J(\theta )& =J({\theta }^{\prime })-E_{s_0\sim p(s_1)}[V^{{\pi }_{\theta }}(s_0)]\\ & =J({\theta }^{\prime })-E_{\tau \sim p_{{\theta }^{\prime }}(\tau )}[V^{{\pi }_{\theta }}(s_0)]\\ & =J({\theta }^{\prime })-E_{\tau \sim p_{{\theta }^{\prime }}(\tau )}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{V}^{{\pi }_{\theta }}(s_t)-\sum _{t=1}^{\mathrm{\infty }}{\gamma }^t{V}^{{\pi }_{\theta }}(s_t)]\\ & =J({\theta }^{\prime })+E_{\tau \sim p_{{\theta }^{\prime }}(\tau )}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t(\gamma V^{{\pi }_{\theta }}(s_{t+1})-V^{{\pi }_{\theta }})(s_t)]\\ & =E_{\tau \sim {\text{p}}_{{\theta }^{\prime }}(\tau )}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^{t}r(s_t,a_t)]+E_{\tau \sim p_{{\theta }^{\prime }}(\tau )}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t(\gamma V^{{\pi }_{\theta }}(s_{t+1})-V^{{\pi }_{\theta }})(s_t)]\\ & =E_{\tau \sim p_{{\theta }^{\prime }}(\tau )}[\sum _t{\gamma }^t{A}^{{\pi }_{\theta }}(s_t,a{,}_t)]\end{array}$$

We have an expectation under ${\theta }^{\prime }$, but samples under $\theta$. We use marginals representation, and Importance Sampling to remove the expectation under ${\pi }_{\theta }^{\prime }$, but can we ignore the other distribution mismatch?

We can bound the distribution change from $p_{\theta }(s_t)$ to $p_{{\theta }^{\prime }}(s_t)$. (See Trust Region Policy Optimization paper)

We can measure the distribution mismatch with KL divergence.

Then, we can enforce the constraint of a small KL divergence by using a loss function with the Lagrange Multiplier:

$$L({\theta }^{\prime },\lambda )=\sum _t{E}_{s_t\sim p_{\theta }(s_t)}\left[E_{a_t\sim {\pi }_{theta}(a_t|s_t)}[\frac{p_{thet{a}^{\prime }}(a_t|s_t)}{p_{\theta }(a_t|s_t)}{\gamma }^t{A}^{{\pi }_{\theta }}(s_t,a_t)]\right]-\lambda (D_{KL}({\pi }_{{\theta }^{\prime }}(a_t|s_t)||{\pi }_{\theta }(a_t|s_t))-ϵ)$$

1. Maximize $L^{\prime }$ wrt to ${\theta }^{\prime }$
2. $\lambda \leftarrow \lambda +\alpha (D_{KL}-ϵ)$

Intuition: raise $\lambda$ if constraint violated too much, else lower it.

Alternatively, optimize within some region, and use a Taylor expansion to approximate the function within that region.

Natural Gradients

Resources

• Deep Reinforcement Learning Through Policy Optimization - NIPS 2016 Tutorial
• CS285 Fa19 9/16/19 - YouTube
• CS285 Fa19 9/30/19 - YouTube