Actor-Critic Algorithm（表演者-评述者算法）

将策略梯度与值函数近似结合起来，就得到了 AC 算法，可以看作是特殊的 PG 算法。

1 QAC

QAC 是最基本的 AC 类算法，与策略梯度的算法有相同的目标函数，相同的目标函数的梯度，${\nabla }_{\theta }J(\theta )=E_{S\sim \eta ,A\sim \pi }[{\nabla }_{\theta }ln(\pi (A|S,\theta ))q_{\pi }(S,A)]$。与之不同的是$q(S,A)$被值函数$q(S,A,w)$替代。与 ReinForce 计算 q 值的方法不同，不再使用 MC 算法更新，而是 TD 算法更新。同时因为更新的值是 Q 值，所以被称为 QAC

1.1 生成数据

由于目标函数的梯度里的随机变量$A$需要服从将要更新的策略$\pi$，所以这是一种 on-policy 的方法。需要使用策略生成{st,at,rt+1,st+1,at+1}\{s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\}{st​,at​,rt+1​,st+1​,at+1​}。

1.2 值更新（value update）(Critic)

因为值可以用来衡量策略好坏，相当于评论家，这步就是 Critic。由于策略用到$q$值，所以采用与 Sarsa 与值函数结合相同的方法更新值。
$w_{t+1}=w_t+{\alpha }_w(r_{t+1}+\gamma q(s_{t+1},a_{t+1},w_t)-q(s_t,a_t,w_t)){\nabla }_{w}q(s_t,a_t,w_t)$

1.3 策略更新（policy update）(Actor)

与 PG 算法相同的方式更新策略。将更新后的$q$值代入。
${\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }{\nabla }_{\theta }ln(\pi (a_t|s_t,{\theta }_t))q(s_t,a_t,w_{t+1})$

2 A2C（Advantage Actor Critic）

为了解决 QAC 策略更新时，使用随机梯度下降采样的样本值方差大的问题，在目标函数引入一个 baseline。
${\nabla }_{\theta }J(\theta )=E_{S\sim \eta ,A\sim \pi }[{\nabla }_{\theta }ln(\pi (A|S,\theta ))(q_{\pi }(S,A)-b(S))]=E[X]$
这个 baseline 不会使这个梯度发生变化，却能够改变随机变量$X$的方差。
通过推导发现，使随机变量$X$方差最小的$b^{\ast }(s)=\frac{E_{A\sim \pi }[\Vert {\nabla }_{\theta }\pi (A|s,\theta ){\Vert }^2{q}_{\pi }(s,A)]}{E_{A\sim \pi }[\Vert {\nabla }_{\theta }\pi (A|s,\theta ){\Vert }^2]}$
简化得到次优解$b^{\ast }(s)=E_{A\sim \pi }[q_{\pi }(s,A)]=v_{\pi }(s)$
所以
$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& =E_{S\sim \eta ,A\sim \pi }[{\nabla }_{\theta }ln(\pi (A|S,\theta ))(q_{\pi }(S,A)-v_{\pi }(S))]\\ & =E_{S\sim \eta ,A\sim \pi }[{\nabla }_{\theta }ln(\pi (A|S,\theta ))(R+v_{\pi }(S^{\prime })-v_{\pi }(S))],（可以只使用一个网络V，避免使用两个网络）\end{array}$$
并称${\delta }_{\pi }(S,A)=q_{\pi }(S,A)-v_{\pi }(S)$为 Advatage funtion，因为它表示当前动作值与当前状态所有动作值得期望的差。因此该算法也叫 Advantage Actor Critic。

2.1 生成数据

由于目标函数的梯度里的随机变量$A$需要服从将要更新的策略$\pi$，所以这是一种 on-policy 的方法。需要使用策略生成{st,at,rt+1,st+1}\{s_t,a_t,r_{t+1},s_{t+1}\}{st​,at​,rt+1​,st+1​}。

2.2 值更新（value update）(Critic)

因为值可以用来衡量策略好坏，相当于评论家，这步就是 Critic。由于策略用到$v$值，所以采用与 TD 与值函数结合相同的方法更新值。
可以先计算 advantage funtion ${\delta }_t=r_{t+1}+\gamma v(s_{t+1},w_t)-v(s_t,w_t)$
$w_{t+1}=w_t+{\alpha }_w{\delta }_t{\nabla }_{w}v(s_t,w_t)$

2.3 策略更新（policy update）(Actor)

与 PG 算法相同的方式更新策略。将更新后的$\delta$值代入。
${\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }{\nabla }_{\theta }ln(\pi (a_t|s_t,{\theta }_t)){\delta }_t$

3 off-policy AC

前面的 AC 算法都是 on-policy 的，通过重要性采样就可以变成 off-policy。

3.1 重要性采样（important sampling）

为了实现 off-policy 就需要解决策略梯度${\nabla }_{\theta }J(\theta )=E_{S\sim \eta ,A\sim \pi }[{\nabla }_{\theta }ln(\pi (A|S,\theta ))q_{\pi }(S,A)]$，$A$服从$\pi$的分布。思路是通过不同分布的采样，求到相同的期望。
$E_{X\sim p_0}[X],E_{Y\sim p_1}[Y]$，$X$和$Y$服从不同的分布，但可以通过对$Y$进行$\frac{p_0(y)}{p_1(y)}y$称为$f(y)$的采样，求平均$\bar{f}=\frac{1}{n}\sum _{n}f(y)\approx E_{X\sim p_0}[X]$得到$p_0$分布下的期望。

3.2 区别

与 A2C 算法基本相同，有以下几点区别。

1. 采样与更新不再需要同一个策略，采样时使用 behavior policy——$\beta$
2. 由于不再动作的采样不再是同个分布，采用重要性采样，值更新时与 A2C 相比变成 $w_{t+1}=w_t+{\alpha }_w\frac{\pi (a_t|s_t,{\theta }_t)}{\beta (a_t|s_t)}{\delta }_t{\nabla }_{w}v(s_t,w_t)$
3. 策略更新也采用重要性采样 ${\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }\frac{\pi (a_t|s_t,{\theta }_t)}{\beta (a_t|s_t)}{\nabla }_{\theta }ln(\pi (a_t|s_t,{\theta }_t)){\delta }_t$

4 DPG（Deterministic Policy Gradient）

AC 和 PG 算法的策略都是 stochastic policy，为了应对动作空间无穷大时，采用确定性的策略可以更好的应对。

4.1 确定性策略（deterministic policy）

由$\pi (a|s,\theta )$输出的是一个概率变成$\mu (s,\theta )$直接输出一个动作值。
目标函数依然是${\bar{v}}_{\mu }$和${\bar{r}}_{\mu }$。梯度变成了$\nabla J(\theta )=\sum _s{\rho }_{\mu }(s){\nabla }_{\theta }\mu (s)({\nabla }_a{q}_{\mu }(s,a)){|}_{a=\mu (s)}=E_{S\sim {\rho }_{\mu }}[{\nabla }_{\theta }\mu (S)({\nabla }_a{q}_{\mu }(S,a)){|}_{a=\mu (s)}]$
由于目标函数梯度不需要对动作进行采样，也就跟策略无关，所以 DPG 是 off-policy 的。

4.2 步骤

1. 采样：根据 behaviour policy——$\beta$采样得到{st,at,rt+1,st+1}\{s_t,a_t,r_{t+1},s_{t+1}\}{st​,at​,rt+1​,st+1​}，再根据 target policy——$\mu$ 采样得到${\tilde{a}}_{t+1}$。注意的是${\tilde{a}}_{t+1}$不会被用于下一次与环境的交互，所以它依然是 off-policy 的。
2. 值更新：$w_{t+1}=w_t+{\alpha }_w(r_{t+1}+\gamma q(s_{t+1},{\tilde{a}}_{t+1},w_t)-q(s_t,a_t,w_t)){\nabla }_{w}q(s_t,a_t,w_t)$
3. 策略更新：${\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }{\nabla }_{\theta }\mu (s_t,{\theta }_t)({\nabla }_a{q}_{\mu }(s_t,a,w_{t+1})){|}_{a=\mu (s)}$