Deep RL 5 Actor Critic

Actor-critic algorithms build on the policy gradient framwork that we discussed in the previous lecture, but also augment it with learning value functions and Q-functions. The goal of this augmentation is still reducing variance, but from a slightly different angle.

Let’s take a look at the original policy gradient and it’s Monte Carlo approximator:

In equation $\text{2}$, $N$ sample trajectories is used to approximate the expectation ${\mathbb{E}}_{\tau \sim p_{\theta }(\tau )}$, but in equation $\text{2}$ there are still one quantity that are approximated, i.e. the reward function $r(r_t^i,a_t^i)$, and unfortuately, we are only using one sample $r_t^i$ to approximate it.

Even with the use of causality and baseline, which gives

with $b=\frac{1}{N}\sum _{i=1}^N\sum _{t^{\prime }=t}^T{r}_t^i$, we are improving the variance in terms of expectation over trajectories (${\mathbb{E}}_{\tau \sim p_{\theta }(\tau )}$) but not the estimation of reward to go (or better-than-average reward to go).

Actor-critic algorithms aims at better estimating the reward to go.

1 Fit the Value FunctionPermalink

We start by recalling the goal of reinforcement learning:

Now define the Q-function:

Q-function is exactly the expected reward to go from step $t$ given the state and action $(s_t,a_t)$.

How about the baseline $b$ in $\text{3}$? We can also replace it with lower variance estimate. To do that, we define the value function:

Value function measures how good the state is (i.e. the value of the state). This is exactly the expected reward of state averaged over different actions.

In addition, we define the advantage

In fact, $\sum _{t^{\prime }=t}^T{r}_t^i-\frac{1}{N}\sum _{i=1}^N\sum _{t^{\prime }=t}^T{r}_t^i$ in equation $\text{3}$ looks very much just like the one sample estimate of the advantage $A^{\pi }(s_t,a_t)$. In fact, $\sum _{t^{\prime }=t}^T{r}_t^i$ is an one sample estimate of The Q-function $Q^{\pi }(s_t,a_t)$, however, $\frac{1}{N}\sum _{i=1}^N\sum _{t^{\prime }=t}^T{r}_t^i$ is not a estimate of $V^{\pi }(s_t)$ (actually if the state space is continuous, we will only have an one sample estimate of $V^{\pi }(s_t)$, which is also the $\sum _{t^{\prime }=t}^T{r}_t^i$, which is the same as the one sample estimate of $Q^{\pi }(s_t,a_t)$. We only have an one sample estimate because we will never visit the state again). But $V^{\pi }(s_t)$ is intuitively better than $\frac{1}{N}\sum _{i=1}^N\sum _{t^{\prime }=t}^T{r}_t^i$ even if we don’t consider the variance, because the former is the expected reward for state $s_t$, and the later is an estimate of expected reward at time step $t$ averaged over all possibly state. Since we want to know how good the action is in the current state, rather than in the current time step, we prefer the former.

If we have Q-function and value function, we can plug them in the original policy gradient and get the most ideal estimator:

However, we do not have $Q^{\pi }(s_t,a_t)$ or $V^{\pi }(s_t)$ and therefore we want to estimate them. Instead of using Monte Carlo estimate, we use function approximation, which might lead to a biased estimatio, but will give enormous variance reduction, in practice, the later usually brings more benefits than the hurts the former brings.

So we want to fit two neural networks to approximate $Q^{\pi }(s_t,a_t)$ or $V^{\pi }(s_t)separately$? Well, it’s actually not necessary if we notice the relationship between the two functions:

And in practice we use one sample estimation to approximate ${\mathbb{E}}_{s_{t+1}\sim p(s_{t+1}\mid s_t,a_t)}$, then we have

Therefore, we only need to fit $V^{\pi }$. For training data, since $V^{\pi }(s_t)={\mathbb{E}}_{p_{\theta }}[\sum _{t^{\prime }=t}^{T}r(s_{t^{\prime }},a_{t^{\prime }})\mid s_t]$, ideally for every state $s_t$, we want to have a bunch of differernt rollouts and rewards collected starting from that state, and then use the sample mean of rewards as the estimate of $V^{\pi }(s_t)$. But this require reseting the simulator and actually impossible in the real world. Therefore, we have one sample estimator $\sum _{t^{\prime }=t}^T{r}_{t^{\prime }}$,

So, we use training data $\{(s_t^i,\sum _{t^{\prime }}^T{r}_{t^{\prime }}^i){\}}_{i=1,t=1}^{N,T}$ to train a neural network $V_{\varphi }^{\pi }$ in a supervised way. But we can further reduce the variance even if we only have one sample estimation of the expected reward — we can again apply the function approximation idea and replace $\sum _{t^{\prime }}^T{r}_{t^{\prime }}^i$ with $r_t^i+V_{{\varphi }^{\prime }}^{\pi }(s_{t+1}^i)$ in the training data, where $V_{{\varphi }^{\prime }}^{\pi }$ is the previously fitted value function (i.e. ${\varphi }^{\prime }$ is one gradient step before $\varphi$). $r_t^i+V_{{\varphi }^{\prime }}^{\pi }(s_{t+1}^i)$ is called the Bootstrapp estimate of the value function. In summary, we fit $V_{\varphi }^{\pi }$ to $V^{\pi }$ by minimizing

where $y_t^i=\sum _{t^{\prime }}^T{r}_{t^{\prime }}^i$ or $r_t^i+V_{{\varphi }^{\prime }}^{\pi }(s_{t+1}^i)$ and the later usually works better.

With fitted value function $V_{\varphi }^{\pi }$, we can estimate the Q-function (Q-value) by

and therefore the advantage:

And our actor-critic policy gradient is

The batch actor-critic algorithm is:

1. run current policy ${\pi }_{\theta }$ and get trajectories $\{{\tau }^i{\}}_{i=1}^N$ and rewards $\{r_t^i{\}}_{i,t=1,1}^{N,T}$
2. fit value function $V_{\varphi }^{\pi }$ by minimizing equation $\text{12}$
3. calculate the advantage of each state action pair ${\hat{A}}^{\pi }(s_t^i,a_t^i)=r_t^i+V_{\varphi }^{\pi }(s_{t+1}^i)-V_{\varphi }^{\pi }(s_t^i)$
4. calculate actor-critic policy gradient ${\mathrm{\nabla }}_{\theta }J(\theta )=\frac{1}{N}\sum _{i=1}^N\sum _{t=1}^T{\mathrm{\nabla }}_{\theta }{\pi }_{\theta }(a_t^i\mid s_t^i){\hat{A}}^{\pi }(s_t^i,a_t^i)$
5. gradient update: $\theta \leftarrow \theta +\alpha {\mathrm{\nabla }}_{\theta }J(\theta )$

We call it batch in that for each policy update we collect a batch of trajectories. We can also update the policy (and value function) using only one step of data i.e. $(s_t,a_t,r_t,s_{s+1})$, which leads to the online actor-critic algorithm which we will introduce later.

2 Discount FactorPermalink

Our previous discussion on policy gradient and actor-critic algorithms are all within the finite horizon or episodic learning scenario, where there is an ending time step $T$ for the task. What about the infinite horizon scenario i.e. $T=\mathrm{\infty }$?

Well in that case the original algorithm can run into problems because at the second step, $V_{\varphi }^{\pi }$ can get infinitely large in many cases. Or in vanilla policy gradient method, the sum of reward can get infinitely large.

To remedy that, we introduce the discount factor $\gamma \in (0,1)$ and define the discounted expected reward, value function, and Q-function to be

Therefore, the policy gradient and actor-critic policy gradient are $\begin{array}{}\text{(21)}& {\mathrm{\nabla }}_{\theta }{J}_{\text{PG}}(\theta )& =\frac{1}{N}\sum _{i=1}^N\sum _{t=1}{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t^i\mid s_t^i)(\sum _{t^{\prime }=t}{\gamma }^{t^{\prime }-t}{r}_{t^{\prime }}^i-b)\text{(22)}& {\mathrm{\nabla }}_{\theta }{J}_{\text{AC}}(\theta )& =\frac{1}{N}\sum _{i=1}^N\sum _{t=1}{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a_t^i\mid s_t^i)(r_t^i+\gamma V_{\varphi }^{\pi }(s_{t+1}^i)-v_{\varphi }^{\pi }(s_t^i))\end{array}$

where in $J_{\text{PG}}(\theta )$, $b$ is also a discounted baseline e.g. $\frac{1}{N}\sum _{i=1}^N\sum _{t^{\prime }=t}{\gamma }^{t^{\prime }-t}{r}_{t^{\prime }}^i$.

Usually we set $\gamma$ to be something like $0.99$. It can be proved that discount factor can prevent the expected reward from being infinity and reduce the variance. Therefore, actually in most cases, no matter it’s finite of infinite horizon, people use discounted policy gradient, i.e. equation $\text{21}\text{ and }\text{22}$, rather than the original ones.

3 Online Actor-critic algorithmsPermalink

So far we’ve been discussing the batch actor-critic algorithm, which for each gradient update, we need to run the policy to collect a batch of trajectories. In this section, we introduce online actor-critic algorithms, which allow faster neural network weights update, and with some techniques can work better than batch actor-critic algorithms in some cases.

The simplest version of online actor-critic algorithm is similar to online learning, where instead of calculating the gradient using a batch of trajectories and rewards, it only uses one transition tuple $(s,a,s^{\prime },r)$. The algorithm is the following:

1. run policy ${\pi }_{\theta }$ for one time step and collect $(s,a,s^{\prime },r)$
2. gradient update $V_{\varphi }^{\pi }$ using (s, r + V^{\pi}_{\phi}(s’))$$
3. evaluate ${\hat{A}}^{\pi }(s)=r+\gamma V_{\varphi }^{\pi }(s^{\prime })-V_{\varphi }^{\pi }(s)$
4. calculate policy gradient ${\mathrm{\nabla }}_{\theta }J(\theta )={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a\mid s){\hat{A}}^{\pi }(s)$
5. gradient update: $\theta \leftarrow \theta +\alpha {\mathrm{\nabla }}_{\theta }J(\theta )$

However, this algorithm does not really work in most cases, because one sample estimate has very high variance, coupled with policy gradient, the variance can be notoriously high. To deal with the high variance problem, we introduce the synchronized parallel actor-critic algorithm, which is basically several agent running basic online actor-critic algorithm but using and updating the shared policy and value network ${\pi }_{\theta }\text{ and }{V}_{\varphi }^{\pi }$. See the following figure:

This can be very easily realized by just changing the the random seeds of the code.

Another variants which has been proved to work very well when we have a very large pool of workers is called the asynchronized parallel actor-critic algorithm:

Each worker (agent) send the one step transition data to the center to update the parameters (both $\theta$ and $\varphi$), but do not wait for the updated weights to be deployed before it execute the next step in the environment. This is a little counterintuitive, because in this way, the worker might not using the latest policy to decide actions. But it turns out that the policy network will be very similar in the near time steps and since the algorithm is run asychronizely, it can be very efficient.

4 Variance/Bias Tradeoff in Estimating the AdvantagePermalink

In this section we go back to the actor critic gradient, what distinguishes it from the vanilla policy gradient is that it uses the advantage ${\hat{A}}^{\pi }(s_t,a_t)$ to replace the original one sample estimate of the expected discounted reward $\sum _{t^{\prime }=t}{\gamma }^{t^{\prime }-t}{r}_{t^{\prime }}^i$. The advantage has smaller variance, but it can be biased as $V_{\varphi }^{\pi }(s_t)$ can be an imperfect estimation of the value function.

A question would be, can we bring the best from the two worlds and get a unbiased estimate of advantage while keep the variance low? Or further, can be develop a machanism that allows us to tradeoff the variance and bias in estimating the advantage?

The answer is yes and the rest of this section will introduce three advantage estimator that gives different variance bias tradeoff.

Recall that the original advantage estimator in actor-critic algorithm is:

4.1 critic as baseline (state dependent baseline )Permalink

The first advantage estimator is $\begin{array}{}\text{(25)}& {\hat{A}}^{\pi }=\sum _{t^{\prime }=t}^T{\gamma }^{t^{\prime }-t}{r}_t-V_{\varphi }^{\pi }(s_t)\end{array}$

Compare to equation $\text{24}$, we replace the neural estimation of discounted expected reward to go with the one sample estimaion $\sum _{t^{\prime }=t}^T{\gamma }^{t^{\prime }-t}{r}_t$ used in policy gradient. This estimator has give lower variance than policy gradient whose baseline is a constant Greensmith et al. 04’ (but the variance is still higher than the actor-critic gradient). But is this advantage estimator really leads to an unbiased gradient estimator?

We can actually show that any state dependent baseline in policy gradient can lead to unbiased gradient estimator. I.e. we want to prove

let’s take one element from the summation $\sum _{t=1}^T$ out:

4.2 state-action dependent baselinePermalink

To be updated, material is in Gu et al. 16’

4.3 Generalized Advantage Estimation (GAE)Permalink

Lastly let’s compare the advantage estimation introduced in section 4.1 (let’s call it $A_{\text{MC}}^{\pi }$) and the advantage estimation used in vanilla actor-critic algorithm (let’s call it $A_{\text{C}}^{\pi }$)

$A_{\text{MC}}^{\pi }$ has higher variance because of the one sample estimation $\sum _{t^{\prime }=t}^T{\gamma }^{t^{\prime }-t}{r}_t$, while $A_{\text{C}}^{\pi }$ is biased because $r_t+\gamma V_{\varphi }^{\pi }(s_{t+1})$ might be an biased estimator of $Q^{\pi }(s_{t+1})$.

Stare at these two estimators for a while, you might notice that the essential part that decide variance bias tradeoff is the estimation of $Q^{\pi }$, one sample estimation has high variance while neural estimation can be biased. We can combine the two and use one sample estimation for the first $n$ steps and use neural estimation for the rest. i.e.

This also make sense intuitively, because the more distant from the current time step, the higher the variance will be. On the other hand, although $V_{\varphi }^{\pi }$ can be biased, when being multiplied by ${\gamma }^l$, the effect can be small. Therefore, $l$ controls the variance bias tradeoff of the advantage estimation. let $l=1$, we recover $A_{\text{C}}^{\pi }$, which has the highest bias and lowest variance, let $l=\mathrm{\infty }$, we recover $A_{\text{MC}}^{\pi }$, which is unbiased by has the highest variance.

$A_{GAE}^{\pi }$ is defined as a exponentially weighted sum of $A_l^{\pi }$’s:

where $w_l\propto {\lambda }^{l-1}$

It can be shown that $A_{GAE}^{\pi }$ can be equivalently writen as

Where

5 Demo: DeepMind A3CPermalink