强化学习——AC算法（十）

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 的方法。需要使用策略生成$\{s_t,a_t,r_{t+1},s_{t+1},a_{t+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^*(s) = \Large \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^*(s) = E_{A \sim \pi}[q_\pi(s,A)] = v_\pi(s)$
所以

并称$\delta_\pi(S,A) = q_\pi(S,A) - v_\pi(S)$为 Advatage funtion，因为它表示当前动作值与当前状态所有动作值得期望的差。因此该算法也叫 Advantage Actor Critic。

2.1 生成数据

由于目标函数的梯度里的随机变量$A$需要服从将要更新的策略$\pi$，所以这是一种 on-policy 的方法。需要使用策略生成$\{s_t,a_t,r_{t+1},s_{t+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)$的采样，求平均$\displaystyle \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 \Large{\frac{\pi(a_t|s_t,\theta_t)}{\beta(a_t|s_t)}} \normalsize \delta_t \nabla_w v(s_t,w_t)$
3. 策略更新也采用重要性采样 $\theta_{t+1}= \theta_{t} + \alpha_\theta \Large{\frac{\pi(a_t|s_t,\theta_t)}{\beta(a_t|s_t)}} \normalsize \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) = \displaystyle \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$采样得到$\{s_t,a_t,r_{t+1},s_{t+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)}$