cs285-lec6-actor critic

Summary

1. sample $\{ s_i, a_i \}$ from $\pi_\theta(a|s)$ (run it over data)
2. fit $\hat{V}_\phi(s)$ to sampled reward sums: $\{ (s_{i, t}, \underbrace{r(s_{i,t}, a_{i,t}) + \text{model}(s_{i,t+1})}_{y_{i,t}}) \}$
3. evaluate $\hat{A}^\pi(s_i, a_i) = r(s_i, a_i) + \gamma \hat{V}^\pi_\phi(s'_i) - \hat{V}^\pi_\phi(s_i)$
4. $\nabla_\theta J(\theta) \approx \frac{1}{N}\sum_i \nabla_\theta \log \pi_\theta(a_i | s_i) \hat{A}^\pi(s_i, a_i)$
5. $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

Recap: policy gradient

target function：

$\begin{aligned} \nabla_\theta J(\theta) \approx \frac{1}{N}\sum_{i = 1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t} | s_{i,t}) \hat{Q}_{i,t} \end{aligned}$

notes: $\hat{Q}_{i,t}$ is the reward-to-go, the estimated expected reward if the agent takes $a_{i,t}$ at $s_{i,t}$，that is：

$\hat{Q}_{i,t} \approx \sum_{t' = t}^Tr(s_{i,t}, a_{i,t})$

A better estimate rather than a single one will be:

$\hat{Q}_{i,t} \approx \sum_{t' = t}^TE_{\pi_\theta}[r(s_{t'}, a_{t'})|s_t, a_t]$

Use expected estimates $\hat{Q}_{i,t}$ to replace single ones could also reduce vairance.

To futher reduce variance, reduce a baseline from Q. This baseline could be the expected value of Q(use average to approximate):

$b_t = \frac{1}{N}\sum_iQ(s_{i,t}, a_{i,t})$

So the target function will be:

$\begin{aligned} \nabla_\theta J(\theta) &\approx \frac{1}{N}\sum_{i = 1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t} | s_{i,t}) \hat{Q}_{i,t} \\ &\approx \frac{1}{N}\sum_{i = 1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t} | s_{i,t}) \Big( \sum_{t'=1}^Tr(s_{i, t'}, a_{i, t'}) - b \Big) \end{aligned}$

Because policy gradient calculates on every single sample, it’s unbiased but has high vairance.

To deal with this high variance, we introduce Actor-Critic.

Terminology Definition

Consider state-action value function, that is total reward from taking $a_t$ at $s_t$:

$Q^\pi(s_t, a_t) = \sum_{t' = t}^TE_{\pi_\theta}[r(s_{t'}, a_{t'})|s_t, a_t]$

Consider state value function, that is average rewards from $s_t$:

$V^\pi(s_t) = E_{a_t \sim \pi_\theta(a_t|s_t)}[Q^\pi(s_t, a_t)]$

In this way we could use $A^\pi$ to denote how much better is $a_t$ than the average actions accroding to $\pi$:

$A^\pi(s_t, a_t) = Q^\pi(s_t, a_t) - V^\pi(s_t)$

And the target function will be:

$\begin{aligned} \nabla_\theta J(\theta) &\approx \frac{1}{N}\sum_{i = 1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t} | s_{i,t}) \hat{Q}_{i,t} \\ &\approx \frac{1}{N}\sum_{i = 1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t} | s_{i,t}) A^\pi(s_{i,t}, a_{i,t}) \end{aligned}$

which one to fit?

We now have 3 options to optimize: $Q,V,A$

For $Q$ we could rewrite it as:

$\begin{aligned} Q^\pi(s_t, a_t) &= \sum_{t' = t}^TE_{\pi_\theta}[r(s_{t'}, a_{t'})|s_t, a_t] \\ &= r(s_t, a_t) + \sum_{t' = t+1}^TE_{\pi_\theta}[r(s_{t'}, a_{t'})|s_t, a_t] \\ &= r(s_t, a_t) + E_{s_{t+1} \sim p(s_{t+1}|s_t, a_t)}[V^\pi(s_{t+1})] \\ &\approx r(s_t, a_t) + V^\pi(s_{t+1}) \end{aligned}$

Then we get:

$\begin{aligned} A^\pi(s_t, a_t) &= Q^\pi(s_t, a_t) - V^\pi(s_t) \\ &\approx r(s_t, a_t) + V^\pi(s_{t+1}) - V^\pi(s_t) \end{aligned}$

So we choose to fit $V^\pi(s)$ since it has the least parameters to learn.

policy evaluation: fit $V^\pi(s)$

To perform optimization, like what the policy gradient does, we could use monte-carlo to get the estimated expected value:

$\begin{aligned} V^\pi(s_t) &= E_{a_t \sim \pi_\theta(a_t|s_t)}[Q^\pi(s_t, a_t)] \\ &\approx \sum_{t'=t}^Tr(s_{t'}, a_{t'}) \\ &\approx \frac{1}{N}\sum_{n=1}^N\sum_{t'=t}^Tr(s_{t'}, a_{t'}) \end{aligned}$

Ideally, we need to collect all possible trajectories from $s_{t'}$, but actually we could not start with certain state, generally we could only start in the initial state.

But if we use a neural network to fit $V^\pi(s_t)$ in a single trajectory, it will generalize to all trajectories (generation in ML).

training set: $\{ (s_{i, t}, \underbrace{V^\pi(s_t) \approx \frac{1}{N}\sum_{n=1}^N\sum_{t'=t}^Tr(s_{t'}, a_{t'})}_{y_{i,t}} ) \}$
Likely, $y_{i,t}$ here is a monte-carlo approximation, the actual $y_{i,t}$ is:

$\begin{aligned} y_{i,t} &= V^\pi(s_t) \\ &= \sum_{t' = t}^TE_{\pi_\theta}[r(s_{t'}, a_{t'})|s_t, a_t] \\ &\approx r(s_t, a_t) + \sum_{t' = t+1}^TE_{\pi_\theta}[r(s_{t'}, a_{t'})|s_t, a_t] \\ &= r(s_t, a_t) + E_{s_{t+1} \sim p(s_{t+1}|s_t, a_t)}[V^\pi(s_{t+1})] \\ &\approx r(s_t, a_t) + V^\pi(s_{t+1}) \end{aligned}$

Since we don’t know $V^\pi(s_{t+1})$, we use the previous fitted $\hat{V}(s_{t+1})$.

Thus the training set is: $\{ (s_{i, t}, \underbrace{r(s_{i,t}, a_{i,t}) + \hat{V}^\pi_\phi(s_{i,t+1})}_{y_{i,t}}) \}$

Use supervised regression loss to optimize:

$\mathcal{L}(\phi) = \frac{1}{2}\sum_i || \hat{V}^\pi_\phi(s_i) - y_i ||^2$

This “bootstrapped” estimate has lower variance because it’s using $\hat{V}^\pi_\phi(s_i)$ as an estimator, and it has higher bias because $\hat{V}^\pi_\phi(s_i)$ might be incorrect.

discount factors

If T (episode length) is $\infin$, $\hat{V}^\pi_\phi(s_i)$ can get infinitely large in many cases, so we introduce a discount factor in $y_{i,t}$:

$y_{i,t} = r(s_{i,t}, a_{i,t}) + \gamma \hat{V}^\pi_\phi(s_{i,t+1})$

actor-critic algorithm

batch actor-critic algorithm (with discount factor):

1. sample $\{ s_i, a_i \}$ from $\pi_\theta(a|s)$ (run it over data)
2. fit $\hat{V}_\phi(s)$ to sampled reward sums.
3. evaluate $\hat{A}^\pi(s_i, a_i) = r(s_i, a_i) + \gamma \hat{V}^\pi_\phi(s'_i) - \hat{V}^\pi_\phi(s_i)$
4. $\nabla_\theta J(\theta) \approx \frac{1}{N}\sum_i \nabla_\theta \log \pi_\theta(a_i | s_i) \hat{A}^\pi(s_i, a_i)$
5. $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

online actor-critic:

1. take action $a \sim \pi_\theta(a|s)$, get$(s, a, s', r)$, store in $\mathcal{R}$
2. sample a batch $\{s_i, a_i, r_i, s_i'\}$ from buffer $\mathcal{R}$
3. update $\hat{Q}^\pi_\phi$ using $y_i = r_i + \gamma \hat{Q}^\pi_\phi(s_i',a_i'), \forall s_i, a_i$
4. $\nabla_\theta J(\theta) \approx \frac{1}{N}\sum_i \nabla_\theta \log \pi_\theta(a | s) \hat{Q}^\pi(s_i, a_i^\pi)$
5. $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

In online actor-critic, we need to fit $Q(s,a)$ instead of $V(s)$ because we need to calculate $y_i$ based on the policy when these actions and states were added in the buffer. Current policy might differ from the policy at buffer.

Two separate networks for actor and critic
In deep learning, we train two separate networks for value function and policy. This way is simple & stable, but the downside is there’s no shared feature between actor and critic.

Or we could train a shared bottom with two different heads.

how to generate a batch?

In deep learning we usually update $\hat{V}^\pi_\phi \leftarrow r + \gamma \hat{V}^\pi_\phi(s')$ with a batch of data. So how to generate the batch?

synchronized parallel actor-critic
run multiple simulators at a time, sometimes too expensive, need to run n simulators if the batch size is n

asynchronous parallel actor-critic
pull in the latest parameters, update them for that thread. The downside is maybe some of the policies pulled is old policies, but it’s acceptable because usually these policiese are not too old.

off-policy actor-critic

use replay buffer

Eligibility traces & n-steps returns

Actually we could see actor-critic as calculating $\hat{A}^\pi(s_i, a_i) = r(s_i, a_i) + \gamma \hat{V}^\pi_\phi(s'_i) - \hat{V}^\pi_\phi(s_i)$ using rewards at current step, and policy gradient using rewards from all steps: $\hat{A}^\pi(s_i, a_i)=\sum_{t' = t}^T \gamma^{t'-t}r(s_{i,t'}, a_{i, t'}) - \hat{V}^\pi_\phi(s_{i,t})$.

As we mentioned above, actor-critic has lower variance but high bias (if the estimated value is wrong, which is very common), while policy gradient has no bias but high variance (because it estimates on every single sample).

So maybe we could find a point between these two, using rewards from some steps to calculate $\hat{A}^\pi(s_i, a_i)$:

$\hat{A}^\pi(s_t, a_t) = \sum_{t' = t}^{t+n} \gamma^{t'-t}r(s_{t'}, a_{t'}) - \hat{V}^\pi_\phi(s_{t}) + \gamma^n \hat{V}^\pi_\phi(s_{t+n})$

Moreover, we could use attention-like mechanism to get a weighted combination of n-step returns:

$\begin{aligned} \hat{A}^\pi_{GAE}(s_t, a_t) &= \sum_{n=1}^\infin w_n \hat{A}^\pi_n(s_t, a_t) \\ &= \sum_{t'=t}^\infin (\gamma \lambda)^{t'-t} \underbrace{\Big(r(s_i, a_i) + \gamma \hat{V}^\pi_\phi(s'_i) - \hat{V}^\pi_\phi(s_i)\Big)}_{\delta_{t'}} \end{aligned}$

The $\gamma \lambda$ here plays a similar role as discount factor, which will reduce variance.

Implementation

实现思路很简单，用actor_net，输入state，输出action。用critic_net，输入state，输出dim=1的值（value）。
优化actor_net时，最大化这个obs和action对应的critic的输出值
优化critic_net时，优化（critic_net对states输出的值，env返回的实际值）