Actor-Critic

Actor-Critic improves on Policy Gradients methods by introducing a critic.

Recall the objective:

$${\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}$$

The question we want to address is: can we get a better estimate of the reward-to-go?

Originally, we were using the single-trajectory estimate of the reward-to-go. If we knew the true expected reward-to-go, then we would have a lower variance version of the policy gradient.

We define the advantage function as $A^{\pi }(s_t,a_t)=Q^{\pi }(s_t,a_t)-V^{\pi }(s_t)$. $V^{\pi }(s_t)$ can be used as baseline $b$, and we obtain the objective:

$${\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)A^{\pi }(s_{i,t},a_{i,t})$$

Value Function Fitting

Recall:

$$\begin{array}{l}{Q}^{\pi }({\mathbf{s}}_t,{\mathbf{a}}_t)=\sum _{t^{\prime }=t}^T{E}_{{\pi }_{\theta }}[r({\mathbf{s}}_{t^{\prime }},{\mathbf{a}}_{t^{\prime }})|{\mathbf{s}}_t,{\mathbf{a}}_t]\\ V^{\pi }\left({\mathbf{s}}_t\right)=E_{{\mathbf{a}}_t\sim {\pi }_{\theta }\left({\mathbf{a}}_t|{\mathbf{s}}_t\right)}\left[Q^{\pi }({\mathbf{s}}_t,{\mathbf{a}}_t)\right]\\ A^{\pi }({\mathbf{s}}_t,{\mathbf{a}}_t)=Q^{\pi }({\mathbf{s}}_t,{\mathbf{a}}_t)-V^{\pi }\left({\mathbf{s}}_t\right)\\ {\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)A^{\pi }({\mathbf{s}}_{i,t},{\mathbf{a}}_{i,t})\end{array}$$

We can choose to fit $Q^{\pi }$, $V^{\pi }$ or $A^{\pi }$, each have their pros and cons.

We can write:

$$Q^{\pi }(s_t,a_t)\approx r(s_t,a_t)+V^{\pi }(s_{t+1})$$

$$A^{\pi }(s_t,a_t)\approx r(s_t,a_t)+V^{\pi }(s_{t+1})-V^{\pi }(s_t)$$

Classic actor-critic algorithms fit $V^{\pi }$, and pay the cost of 1 time-step to get $Q^{\pi }$.

We do Monte Carlo evaluation with function approximation, estimating $V^{\pi }(s_t)$ as:

$$V^{\pi }(s_t)\approx \sum _{t^{\prime }=t}^{T}r(s_{t^{\prime }},a_{t^{\prime }})$$

Our training data consists of $\left\{(s_{i,t},\sum _{t^{\prime }=t}^{T}r(s_{i,t^{\prime }},a_{i,t^{\prime }}))\right\}$, and we can just fit a neural network with regression.

Alternatively, we can decompose the ideal target, and use the old $V^{\pi }$:

$$y_{i,t}=\sum _{t^{\prime }=t}^T{E}_{{\pi }_{\theta }}[r(s_{t^{\prime }},a_t^{\prime })|s_{i,t}]\approx r(s_{i,t},a_{i,t})+{\hat{V}}_{\varphi }^{\pi }(s_{i,t+1})$$

This is a biased estimate, but might have much lower variance. This works when the policy does not change much and the previous value function is a decent estimate. Since it is using a the previous value function, it is also called a bootstrapped estimate.

Discount Factors

The problem with the bootstrapped estimate is that with long horizon problems, ${\hat{V}}_{\varphi }^{\pi }$ can get infinitely large. A simple trick is to use a discount factor:

$$y_{i,t}\approx r(s_{i,t},a_{i,t})+\gamma {\hat{V}}_{\varphi }^{\pi }(s_{i,t+1})$$

where $\gamma \in [0,1]$.

We can think of $\gamma$ as changing the MDP, introducing a death state with reward 0, and the probability of transitioning to this death state is $1-\gamma$. This causes the agent to prefer better rewards now than later.

We can then modify ${\hat{A}}^{\pi }$:

$${\hat{A}}^{\pi }(s_t,a_t)\approx r(s_t,a_t)+\gamma {\hat{V}}^{\pi }(s_{t+1})-{\hat{V}}^{\pi }(s_t)$$

$\gamma$ can be interpreted as a way to limit variance, and prevent the infinite sum (think about what happens when $\gamma$ gets bigger).

Algorithm

1. sample $\{s_i,a_i\}$ from ${\pi }_{\theta }(a\text{s})$
2. Fit ${\hat{V}}_{\varphi }^{\pi }(s)$ to the sampled reward sums
3. Evaluate ${\hat{A}}^{\pi }(s_i,a_i)=r(s_i{a}_i)+{\hat{V}}_{\varphi }^{\pi }(s_i^{\prime })-{\hat{V}}_{\varphi }^{\pi }(s_i)$
4. ${\mathrm{\nabla }}_{\theta }J(\theta )\approx \sum _i{\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }\left({\mathbf{a}}_i|{\mathbf{s}}_i\right){\hat{A}}^{\pi }({\mathbf{s}}_i,{\mathbf{a}}_i)$
5. $\theta \leftarrow \theta +\alpha {\mathrm{\nabla }}_{\theta }J(\theta )$

Online Actor-critic

online actor-critic uses a single sample batch, which is a bad idea in large neural networks. We need to use multiple samples to perform updates.

The purpose of multiple workers here is not to make the algorithm faster, but to make it work by increasing the batch size.

Generalized Advantage Estimation

$${\hat{A}}_n^{\pi }(s_t,a_t)=\sum _{t^{\prime }=t}^{t+n}{\gamma }^{t^{\prime }-t}r(s_{t^{\prime }},a_{t^{\prime }})-{\hat{V}}_{\varphi }^{\pi }(s_t)+{\gamma }^n{\hat{V}}_{\varphi }^{\pi }(s_{t+n})$$

$${\hat{A}}_{GAE}^{\pi }(s_t,a_t)=\sum _{n=1}^{\mathrm{\infty }}{w}_n{\hat{A}}_n^{\pi }(s_t,a_t)$$

is some weighted combination of n-step returns. If we choose $w_n\propto {\lambda }^{n-1}$, we can show that:

$${\hat{A}}_{GAE}^{\pi }(s_t,a_t)=\sum _{n=1}^{\mathrm{\infty }}(\gamma \lambda {)}^{t^{\prime }-t}{\delta }_{t^{\prime }}$$

where

$${\delta }_{t^{\prime }}=r(s_{t^{\prime }},a_{t^{\prime }})+\gamma {\hat{V}}_{\varphi }^{\pi }(s_{t^{\prime }+1})-{\hat{V}}_{\varphi }^{\pi }(s_{t^{\prime }})$$

the role of $\gamma$ and the role of $\lambda$ turns out to b similar, trading off bias and variance!

Need to balance between learning speed, stability.

• Conservative Policy Iteration (CPI)
  • propose surrogate objective, guarantee monotonic improvement under specific state distribution
• Trust Region Policy Optimization (TRPO)
  • approximates CPI with trust region constraint
• Proximal Policy Optimization (PPO)
  • replaces TRPO constraint with RL penalty + clipping (computationally efficient)
• Soft Actor-Critic (SAC)
  • stabilize learning by jointly maximizing expected reward and policy entropy (based on maximum entropy RL)
• Optimistic Actor Critic (OAC)
  • Focus on exploration in deep Actor critic approaches.
  • Key insight: existing approaches tend to explore conservatively
  • Key result: Optimistic exploration leads to efficient, stable learning in modern Actor Critic methods

Resources

• CS285 Fa19 9/18/19 - YouTube