深度 RL

进入深度 RL 后，model free 方法开始变得愈发重要，因为对真实世界建模绝非易事。

价值函数

当动作，状态空间无限扩大后，没有了一个表格式的 model 后，最重要的问题是如何表达原来查表可得到的价值函数 $q(s,a)$ 来指导动作选取。可以使用函数来状态动作价值函数的估计，在训练中采用近似参考值的方法来训练。

$$J(w)=\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w){)}^2],$$

这个目标函数期望是按照随机变量 $S\in \mathcal{S}$ 来计算的，$S$ 的分布情况会影响期望的计算。有两种方法来规定 $S$ 的分布：

第一种是平均分布，平等地对待每一个状态，赋予 $\frac{1}{n}$ 的权重：

$$J(ıw)=\frac{1}{\pi }\sum _{s\in S}({\nu }_{\pi }(s)-\hat{\upsilon }(s,w){)}^2.$$

但是这种方法有一种平均主义的问题：把所有状态都等权计算，这让很少访问到的状态同经常访问到的状态一样重要。

第二种是这章的重点，是应用稳态分布（stationary distribution）。如果你记录 agent 在足够多步里分别待在每个状态的比例，这个比例就近似于 stationary distribution $d_{\pi }(s)$，满足${\sum }_s{d}_{\pi }(s)=1$。形式上来说，策略 $\pi$ 作用于 MDP 后，状态的转移构成一条马尔可夫链，其转移矩阵为：

$$P_{\pi }(s^{\prime }|s)=\sum _a\pi (a|s)p(s^{\prime }|s,a)$$

如果一个分布 $d_{\pi }$ 满足：

$$d_{\pi }(s^{\prime })=\sum _s{d}_{\pi }(s)P_{\pi }(s^{\prime }|s)$$

也就是说，用 $d_{\pi }$ 作为当前分布，经过一步转移后分布不变，那它就是 stationary distribution。

$$J(w)=\sum _{s\in S}{d}_{\pi }(s)(v_{\pi }(s)-\dot{v}(s,w){)}^2,$$

有了目标函数即可利用梯度下降来求函数参数的最优值：

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\nabla }_{w}J(w_k),\\ & ={\nabla }_w\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w_k){)}^2]\\ & =\mathbb{E}[{\nabla }_w(v_{\pi }(S)-\hat{v}(S,w_k))(-\hat{v}(S,w_k){)}^2]\\ & =-2\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w_k)){\nabla }_w\hat{v}(S,w_k)].\\ & =w_k+2{\alpha }_k\mathbb{E}[(v_{\pi }(S)-\hat{v}(S,w_k)){\nabla }_w\hat{v}(S,w_k)],\end{array}$$ $$\begin{array}{l}\text{Algorithm 8.1: TD learning of state values with function approximation}\\ \\ \text{Initialization: }\text{A function }\hat{v}(s,w)\text{ that is differentiable in }w.\text{ Initial parameter }{w}_0.\\ \\ \text{Goal: }\text{Learn the true state values of a given policy }\pi .\\ \\ \text{For each episode }\{s_t,r_{t+1},s_{t+1}{\}}_t\text{ generated by }\pi ,\text{ do}\\ \text{For each sample }(s_t,r_{t+1},s_{t+1}),\text{ do}\\ \text{In the general case, }{w}_{t+1}=w_t+{\alpha }_t\left[r_{t+1}+\gamma \hat{v}(s_{t+1},w_t)-\hat{v}(s_t,w_t)\right]{\nabla }_w\hat{v}(s_t,w_t)\\ \text{In the linear case, }{w}_{t+1}=w_t+{\alpha }_t\left[r_{t+1}+\gamma {\varphi }^T(s_{t+1})w_t-{\varphi }^T(s_t)w_t\right]\varphi (s_t)\end{array}$$

而这些公式中的 $v_{\pi }(s)$ 表示的是真实的奖励函数，我们无法获取这个值，只能通过对每个 episode 的值进行采样获得。从每个 episode 中采样获得价值函数的方式也有两个，一是 MC 方法，而是 TD 方法。这两个方法均可以从Model free 基础方法中找到。

而状态价值估计到动作价值估计的外推是相当直接的，如同上一章Model free 基础方法中 Sarsa 方法的提出，函数近似的 Sarsa 也是相当好得到的：

$$w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1},w_t)-\hat{q}(s_t,a_t,w_t)]{\nabla }_w\hat{q}(s_t,a_t,w_t).$$ $$\begin{array}{l}\text{Algorithm 8.2: Sarsa with function approximation}\\ \\ \text{Initialization: }\text{Initial parameter }{w}_0.\text{ Initial policy }{\pi }_0.{\alpha }_t=\alpha >0\text{ for all }t.ϵ\in (0,1).\\ \\ \text{Goal: }\text{Learn an optimal policy that can lead the agent to the target state from an initial state }{s}_0.\\ \\ \text{For each episode, do}\\ \text{Generate }{a}_0\text{ at }{s}_0\text{ following }{\pi }_0(s_0)\\ \text{If }{s}_t(t=0,1,2,\dots )\text{ is not the target state, do}\\ \text{Collect the experience sample }(r_{t+1},s_{t+1},a_{t+1})\text{ given }(s_t,a_t):\text{ generate }{r}_{t+1},s_{t+1}\\ \text{by interacting with the environment; generate }{a}_{t+1}\text{ following }{\pi }_t(s_{t+1}).\\ \text{Update }q\text{-value:}\\ w_{t+1}=w_t+{\alpha }_t\left[r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1},w_t)-\hat{q}(s_t,a_t,w_t)\right]{\nabla }_w\hat{q}(s_t,a_t,w_t)\\ \text{Update policy:}\\ {\pi }_{t+1}(a|s_t)=1-\frac{ϵ}{|\mathcal{A}(s_t)|}(|\mathcal{A}(s_t)|-1)\text{if }a=\arg {\max }_{a\in \mathcal{A}(s_t)}\hat{q}(s_t,a,w_{t+1})\\ {\pi }_{t+1}(a|s_t)=\frac{ϵ}{|\mathcal{A}(s_t)|}\text{otherwise}\\ s_t\leftarrow s_{t+1},a_t\leftarrow a_{t+1}\end{array}$$

Q-learning 也是一样的思路：

$$w_{t+1}=w_t+{\alpha }_t[r_{t+1}+\gamma \underset{a\in A(s_{t+1})}{\max }\hat{q}(s_{t+1},a,w_t)-\hat{q}(s_t,a_t,w_t)]{\nabla }_w\hat{q}(s_t,a_t,w_t).$$ $$\begin{array}{l}\text{Algorithm 8.3: Q-learning with function approximation (on-policy version)}\\ \\ \text{Initialization: }\text{Initial parameter }{w}_0.\text{ Initial policy }{\pi }_0.{\alpha }_t=\alpha >0\text{ for all }t.ϵ\in (0,1).\\ \\ \text{Goal: }\text{Learn an optimal path that can lead the agent to the target state from an initial state }{s}_0.\\ \\ \text{For each episode, do}\\ \text{If }{s}_t(t=0,1,2,\dots )\text{ is not the target state, do}\\ \text{Collect the experience sample }(a_t,r_{t+1},s_{t+1})\text{ given }{s}_t:\text{ generate }{a}_t\text{ following }{\pi }_t(s_t);\\ \text{generate }{r}_{t+1},s_{t+1}\text{ by interacting with the environment.}\\ \text{Update }q\text{-value:}\\ w_{t+1}=w_t+{\alpha }_t\left[r_{t+1}+\gamma {\max }_{a\in \mathcal{A}(s_{t+1})}\hat{q}(s_{t+1},a,w_t)-\hat{q}(s_t,a_t,w_t)\right]{\nabla }_w\hat{q}(s_t,a_t,w_t)\\ \text{Update policy:}\\ {\pi }_{t+1}(a|s_t)=1-\frac{ϵ}{|\mathcal{A}(s_t)|}(|\mathcal{A}(s_t)|-1)\text{if }a=\arg {\max }_{a\in \mathcal{A}(s_t)}\hat{q}(s_t,a,w_{t+1})\\ {\pi }_{t+1}(a|s_t)=\frac{ϵ}{|\mathcal{A}(s_t)|}\text{otherwise}\end{array}$$

Deep Q-learning

DQN 就是指使用了神经网络作为奖励函数的 Q-learning，整体上和上文中讲的 Q-learning with function approximation 相差不大。要求的目标函数：

$$J=\mathbb{E}\left[{\left(R+\gamma \underset{a\in A(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w)\right)}^2\right],$$

这个方程可以被视为平方贝尔曼最优误差，因为下列方程可以被视为贝尔曼最优方程:

$$q(s,a)=\mathbb{E}\left[R_{t+1}+\gamma \underset{a\in A(S_{t+1})}{\max }q(S_{t+1},a)|S_t=s,A_t=a\right],\mathrm{for}\mathrm{all}s,a$$

然后对 $J$ 求梯度下降

$${\nabla }_{w}J=-\mathbb{E}\left[\left(R+\gamma \underset{a\in A(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w)-\hat{q}(S,A,w)\right){\nabla }_w\hat{q}(S,A,w)\right],$$

在利用梯度下降求解的同时需要一些技巧来使得训练更加稳定。

第一：Experience Replay

Algorithm 8.3 每收集一个 $(s_t,a_t,r_{t+1},s_{t+1})$ 就立刻拿来更新 $w$，用完就扔。问题是连续的样本之间高度相关——$s_t$ 和 $s_{t+1}$ 往往很像，这相当于给神经网络连续喂很相似的数据，容易导致训练不稳定。

DQN 把所有经验存进一个 replay buffer，更新时从中随机抽一个 mini-batch。这样一个 batch 里的样本来自不同时刻不同状态，相关性被打破，训练就稳定得多。

第二：Target Network

Algorithm 8.3 的更新目标是 $r_{t+1}+\gamma {\max }_a\hat{q}(s_{t+1},a,w_t)$，注意这里的 $w_t$ 和被更新的参数是同一个。也就是你每更新一步 $w$，target 也跟着变了，等于目标一直在动，优化器在追一个移动的靶子。

DQN 维护一个额外的 target network $w^{-}$，隔一段时间才从主网络复制参数过来。更新目标变成 $r+\gamma {\max }_a\hat{q}(s^{\prime },a,w^{-})$，这样 target 在一段时间内是固定的，优化更稳定。即对下列公式求梯度：

$${\nabla }_{w}J=-\mathbb{E}\left[\left(R+\gamma \underset{a\in A(S^{\prime })}{\max }\hat{q}(S^{\prime },a,w^{-})-\hat{q}(S,A,w)\right){\nabla }_w\hat{q}(S,A,w_t)\right],$$ $$\begin{array}{l}\text{Algorithm 8.3: Deep Q-learning (off-policy version)}\\ \\ \text{Initialization: }\text{A main network and a target network with the same initial parameter.}\\ \\ \text{Goal: }\text{Learn an optimal target network to approximate the optimal action values from the experience}\\ \text{samples generated by a given behavior policy }{\pi }_b.\\ \\ \text{Store the experience samples generated by }{\pi }_b\text{ in a replay buffer }\mathcal{B}=\{(s,a,r,s^{\prime })\}\\ \text{For each iteration, do}\\ \text{Uniformly draw a mini-batch of samples from }\mathcal{B}\\ \text{For each sample }(s,a,r,s^{\prime }),\text{ calculate the target value as }{y}_T=r+\gamma {\max }_{a\in \mathcal{A}(s^{\prime })}\hat{q}(s^{\prime },a,w_T),\\ \text{where }{w}_T\text{ is the parameter of the target network}\\ \text{Update the main network to minimize }(y_T-\hat{q}(s,a,w){)}^2\text{ using the mini-batch of samples}\\ \text{Set }{w}_T=w\text{ every }C\text{ iterations}\end{array}$$

Policy Gradiant

本文前部分讲了如何把奖励函数由表格变为函数，此前讲解的策略也大部分是通过查表选最大值的表格形式，深度 RL 也需要将策略转为函数形式：$\pi (a|s,\theta ),\theta \in {\mathbb{R}}^m$。这个函数可能是接受一个 $(s,a)$ 输出下一步策略，也可能是输入 $s$ 输出动作空间中的全部策略。

随之而来的问题是如何权衡最优的策略？在表格中，最优策略可以找到：让每一个状态的 value 都最大。这可以做到，因为存在一个策略同时在所有状态上最优。但是在参数化的策略中，参数维度有限，你没法让每个状态的 value 都同时最大。这时候你需要一个 单一的数字来评价整个策略的好坏，然后对这个数字做梯度上升。这个数字就是 scalar metric $J(\theta )$。更新策略也从直接修改表格值变为更新函数权重。

定义好 scalar metric $J(\theta )$，就可以通过Model free 基础方法中讲到的随机近似方法来去最优参数：

$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }J({\theta }_t),$$

定义这个 scalar metric 很重要，一般有几种定义方式：

第一种是平均状态价值：

$${\bar{v}}_{\pi }={\mathbb{E}}_{S\sim d}[v_{\pi }(S)].$$

此处关于 $d$ 的分布可以是平均分布，即 $d_0(s)=1/|\mathcal{S}|$ 或者对一个特定的状态感兴趣的话，比如总是从一个状态出发则可以使 $d(s_0)=1,d_0(s\ne s_0)=0$。

也可以是静态分布，即上文讲的，找到 $d_{\pi }^I{P}_{\pi }=d_{\pi }^I$ ，后利用这个分布计算。静态分布会带来很多有利于推导的性质：

• $J(\theta )=\mathbb{E}\left[{\sum }_{t=0}^{\infty }{\gamma }^t{R}_{t+1}\right]={\bar{v}}_{\pi }={\sum }_{s}d(s)v_{\pi }(s)$ 即目标函数是关于奖励函数的加权平均，而奖励函数是回报的累计折扣回报期望；
• ${\bar{v}}_{\pi }=d^T{v}_{\pi }$ 这是把求和写成向量内积的形式。它的用处是方便后面求梯度。

第二种方法是平均回报值：

$$J(\theta )=\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}\left[\sum _{t=0}^{n-1}{R}_{t+1}\right]$$

这个式子可以化成：

$$\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}\left[\sum _{t=0}^{n-1}{R}_{t+1}\right]=\sum _{s\in S}{d}_{\pi }(s)r_{\pi }(s)={\bar{r}}_{\pi }=\sum _{s\in \mathcal{S}}{d}_{\pi }(s)r_{\pi }(s)={\mathbb{E}}_{S\sim d_{\pi }}\left[r_{\pi }(S)\right]=d_{\pi }^T{r}_{\pi }$$

可以注意到平均回报值是严格依赖策略的静态分布的，因为他就是沿着策略求平均回报，并且其不带衰减，这使得这种目标函数相比第一种更加远视，适用于无终止的任务。

$$\begin{array}{cccc}\text{Metric}& \text{Expression 1}& \text{Expression 2}& \text{Expression 3}\\ {\bar{v}}_{\pi }& \sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)& {\mathbb{E}}_{S\sim d}[v_{\pi }(S)]& \underset{n\to \infty }{\lim }\mathbb{E}\left[\sum _{t=0}^{n-1}{\gamma }^t{R}_{t+1}\right]\\ {\bar{r}}_{\pi }& \sum _{s\in \mathcal{S}}{d}_{\pi }(s)r_{\pi }(s)& {\mathbb{E}}_{S\sim d_{\pi }}[r_{\pi }(S)]& \underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}\left[\sum _{t=0}^{n-1}{R}_{t+1}\right]\end{array}$$

metircs 的梯度

定义好了目标函数 $J(\theta )$，下一步就是对其求梯度。这部分的核心结论是策略梯度定理（Policy Gradient Theorem）：

$${\nabla }_{\theta }J(\theta )=\sum _{s\in \mathcal{S}}\eta (s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }\pi (a|s,\theta )q_{\pi }(s,a),$$

其中 $\eta$ 是状态分布，${\nabla }_{\theta }\pi$ 是策略对参数的梯度。更实用的是它的紧凑期望形式：

$${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{S\sim \eta ,A\sim \pi (S,\theta )}\left[{\nabla }_{\theta }\ln \pi (A,S,\theta )q_{\pi }(S,A)\right].$$

期望形式更受偏爱，原因是它可以用随机梯度来近似——用采样代替精确期望，这正是本章要讨论的内容。

为什么可以这么变形？ 关键在于一个对数求导技巧：

$${\nabla }_{\theta }\ln \pi (a|s,\theta )=\frac{{\nabla }_{\theta }\pi (a|s,\theta )}{\pi (a|s,\theta )},$$

因此：

$${\nabla }_{\theta }\pi (a|s,\theta )=\pi (a|s,\theta ){\nabla }_{\theta }\ln \pi (a|s,\theta ).$$

将这个代入原始的求和式，$\pi (a|s,\theta )$ 就把对 $a$ 的求和自然地转成了对策略的期望，从而得到上面的紧凑形式。

另一个需要注意的前提是：$\pi (a|s,\theta )$ 对所有 $(s,a)$ 必须严格为正，这样 $\ln \pi$ 才有意义。实现这一点的标准做法是用 softmax 函数：

$$\pi (a|s,\theta )=\frac{e^{h(s,a,\theta )}}{{\sum }_{a^{\prime }\in \mathcal{A}}{e}^{h(s,a^{\prime },\theta )}},a\in \mathcal{A},$$

其中 $h(s,a,\theta )$ 是神经网络输出的偏好值。Softmax 天然满足 $\pi \in (0,1)$ 且所有动作概率之和为 1，同时让策略保持随机性，这意味着策略会持续探索而不会提前坍缩成确定性选择——这是一个自带探索的好性质。

注意

书中从200页至210页左右推导不同的 metric 形式的导数，包括：

• Average statue value ${\bar{v}}_{\pi }={\sum }_{s}d(s)v_{\pi }(s)$：包括静态分布和与策略无关 $d_0$ 两种分布
• Average reward ${\bar{r}}_{\pi }={\sum }_s{d}_{\pi }(s)r_{\pi }(s)$
• 然后按照是否是 discount 分类：
  • undiscounted $\gamma <1$：Lemma 9.1 证明 ${\bar{r}}_{\pi }=(1-\gamma ){\bar{v}}_{\pi }$，所以两个 metric 等价，梯度方向一样。Theorem 9.2 给出 ${\bar{v}}_{\pi }$​ 的梯度，Theorem 9.3 给出 ${\bar{r}}_{\pi }$ 的梯度。
  • Undiscounted（$gamma=1$）：$\sum R_t$​ 会发散，必须重新定义 $v_{\pi }(s)$（每步减去 ${\bar{r}}_{\pi }$​，即 Poisson equation），然后推出 Theorem 9.5。

三种情况推出来的梯度形式几乎一样，全部被 Theorem 9.1 统一，此处省略。

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha {\nabla }_{\theta }J({\theta }_t)\\ & ={\theta }_t+\alpha \mathbb{E}[{\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)q_{\pi }(S,A)],\end{array}$$

由于真正的梯度是不知道的，所以我们可以通过用采样的方式来随机近似逼近真实的最优参数：

$${\theta }_{t+1}={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q_t(s_t,a_t),$$

用 $q_t(s_t,a_t)$ 来近似 $q_{\pi }(s_t,a_t)$。如果前者是通过蒙特卡洛方法得到的估计，这个算法就叫作 REINFORCE 或者 Monte Carlo policy gradient 。

因为 $\nabla \ln \pi (a_t|s_t,{\theta }_t)=\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}$，可以把上式重新写成：

$${\theta }_{t+1}={\theta }_t+\alpha \underset{{\beta }_t}{\underbrace{\left(\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}\right)}}{\nabla }_{\theta }\pi (a_t|s_t,{\theta }_t),$$

则当 ${\beta }_t\ge 0$ 时，选择 $(s_t,a_t)$ 的概率提升：

$$\pi (a_t|s_t,{\theta }_{t+1})\ge \pi (a_t|s_t,{\theta }_t).$$

反之，当 ${\beta }_t<0$ 时，选择 $(s_t,a_t)$ 的概率下降：

$$\pi (a_t|s_t,{\theta }_{t+1})<\pi (a_t|s_t,{\theta }_t).$$

${\beta }_t=\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}$ 同时包含了 exploit 和 explore 两个效果。

Exploit 来自分子 $q_t(s_t,a_t)$：$q$ 值越大，${\beta }_t$ 越大，更新幅度越猛，这个动作的概率被提升得越多。所以算法倾向于强化高回报的动作，这就是 exploitation。

Explore 来自分母 $\pi (a_t|s_t,{\theta }_t)$：假设某个动作 $q>0$ 但当前概率很低，那分母小，${\beta }_t$ 就会被放大。也就是说，一个被冷落但实际不错的动作，反而会得到更强的概率提升。反过来，一个已经高概率的好动作，分母大，${\beta }_t$ 被压小，提升幅度不会太大。

$$\begin{array}{l}\text{Algorithm 9.1: Policy Gradient by Monte Carlo (REINFORCE)}\\ \\ \text{Initialization: }\text{Initial parameter }\theta ;\gamma \in (0,1);\alpha >0.\\ \\ \text{Goal: }\text{Learn an optimal policy for maximizing }J(\theta ).\\ \\ \text{For each episode, do}\\ \text{Generate an episode }\{s_0,a_0,r_1,\dots ,s_{T-1},a_{T-1},r_T\}\text{ following }\pi (\theta ).\\ \text{For }t=0,1,\dots ,T-1:\\ \text{Value update: }{q}_t(s_t,a_t)=\sum _{k=t+1}^T{\gamma }^{k-t-1}{r}_k\\ \text{Policy update: }\theta \leftarrow \theta +\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,\theta )q_t(s_t,a_t)\end{array}$$

Actor-critic

现在所学的策略大致分为两种： policy-based 和 value based。前者比如 REINFORCE，Policy Gradiant 算法是直接更新模型参数，后者比如 DQN，Q-learning 直接更新价值函数。

现在的随机近似方法也大致分为两类：蒙特卡罗方法和 TD learning。上一章讲的 REINFORCE和 Policy Gradiant 都是蒙特卡洛方法，当把 TD 基础的近似方法用于 Policy gradiant 算法后可以得出 Actor-critic 算法。

$$\begin{array}{l}\text{Algorithm 10.1: The simplest actor-critic algorithm (QAC)}\\ \\ \text{Initialization: }\text{A policy function }\pi (a|s,{\theta }_0)\text{ where }{\theta }_0\text{ is the initial parameter.}\\ \text{A value function }q(s,a,w_0)\text{ where }{w}_0\text{ is the initial parameter. }{\alpha }_w,{\alpha }_{\theta }>0.\\ \\ \text{Goal: }\text{Learn an optimal policy to maximize }J(\theta ).\\ \\ \text{At time step }t\text{ in each episode, do}\\ \text{Generate }{a}_t\text{ following }\pi (a|s_t,{\theta }_t),\text{ observe }{r}_{t+1},s_{t+1},\text{ and then generate }{a}_{t+1}\text{ following }\pi (a|s_{t+1},{\theta }_t).\\ \text{Actor (policy update):}\\ {\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }{\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q(s_t,a_t,w_t)\\ \text{Critic (value update):}\\ w_{t+1}=w_t+{\alpha }_w\left[r_{t+1}+\gamma q(s_{t+1},a_{t+1},w_t)-q(s_t,a_t,w_t)\right]{\nabla }_{w}q(s_t,a_t,w_t)\end{array}$$

这个算法就是将 TD base 近似方法代入了 Policy Gradiant 后加上了一个 Sarsa 算法来更新价值函数。也就是 QAC 使用 Sarsa 算法提供的 Q 值来更新策略神经网络，相比 REINFORCE 算法直接采样一个很长的 Q 值来更新，这个算法用 Sarsa 提供的期望 Q 值来更新策略神经网络，这极大减小了方差。

上式中的 Sarsa 和前几章讲解的表格式 Sarsa 更新方式不一样，因为这个 Sarsa 也是函数式的，采用减小平方误差的方式来优化：

$$w_{t+1}=w_t+{\alpha }_w\underset{\text{TD error }{\delta }_t}{\underbrace{\left[r_{t+1}+\gamma q(s_{t+1},a_{t+1},w_t)-q(s_t,a_t,w_t)\right]}}{\nabla }_{w}q(s_t,a_t,w_t)$$

优势 Actor-Critic

Advantage actor-critic(A2C) 的核心思想就是通过引入一个 baseline 来减小估计的方差，即：

$${\mathbb{E}}_{S\sim \eta ,A\sim \pi }[{\nabla }_{\theta }\ln \pi (A|S,\theta )q_{\pi }(S,A)]={\mathbb{E}}_{S\sim \eta ,A\sim \pi }[{\nabla }_{\theta }\ln \pi (A|S,\theta )(q_{\pi }(S,A)-b(S))]$$

在末尾加上一个参数不会改变期望值，因为：

$$\begin{array}{rl}{\mathbb{E}}_{S\sim \eta ,A\sim \pi }\left[{\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)b(S)\right]& =\sum _{s\in \mathcal{S}}\eta (s)\sum _{a\in \mathcal{A}}\pi (a|s,{\theta }_t){\nabla }_{\theta }\ln \pi (a|s,{\theta }_t)b(s)\\ & =\sum _{s\in \mathcal{S}}\eta (s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }\pi (a|s,{\theta }_t)b(s)\\ & =\sum _{s\in \mathcal{S}}\eta (s)b(s)\sum _{a\in \mathcal{A}}{\nabla }_{\theta }\pi (a|s,{\theta }_t)\\ & =\sum _{s\in \mathcal{S}}\eta (s)b(s){\nabla }_{\theta }\sum _{a\in \mathcal{A}}\pi (a|s,{\theta }_t)\\ & =\sum _{s\in \mathcal{S}}\eta (s)b(s){\nabla }_{\theta }1=0.\end{array}$$

但是可以有效改变方差，可以证明最优的 baseline 是：

$$b^{\ast }(s)=\frac{{\mathbb{E}}_{A\sim \pi }\left[\Vert {\nabla }_{\theta }\ln \pi (A|s,{\theta }_t){\Vert }^2{q}_{\pi }(s,A)\right]}{{\mathbb{E}}_{A\sim \pi }\left[\Vert {\nabla }_{\theta }\ln \pi (A|s,{\theta }_t){\Vert }^2\right]}.s\in \mathcal{S}$$

但是这个基线计算太复杂了o，如果将 $\Vert {\nabla }_{\theta }\ln \pi (A|s,{\theta }_t){\Vert }^2$ 删掉，也可以得到一个次优的基线：

$$b^{†}(s)={\mathbb{E}}_{A\sim \pi }[q_{\pi }(s,A)]=v_{\pi }(s).$$

证明见书P.219。

引入基线后，更新方式变为了：

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha \mathbb{E}\left[{\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)\left(q_{\pi }(S,A)-v_{\pi }(S)\right)\right]\\ & \doteq {\theta }_t+\alpha \mathbb{E}\left[{\nabla }_{\theta }\ln \pi (A|S,{\theta }_t){\delta }_{\pi }(S,A)\right].\end{array}$$

其中 ${\delta }_{\pi }(S,A)\doteq q_{\pi }(S,A)-v_{\pi }(S)$，这被称为优势函数，这个更新的随机方式为：

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\left[q_t(s_t,a_t)-v_t(s_t)\right]\\ & ={\theta }_t+\alpha {\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t){\delta }_t(s_t,a_t),\end{array}$$

即 A2C 不再看一个动作的绝对回报，而是看这个动作相对这个状态平均回报的相对值，直觉上来讲降低了方差。当 $q_t(s_t,a_t)$ 和 $v_t(s_t)$ 是通过蒙特卡罗方法估计的时候，这个策略叫作 REINFORCE with baseline，当两者是由 TD learning 估计的时候，这个算法才被叫作 A2C。

同时可以注意到这里的优势函数是由 TD error 近似而来的：

$$\begin{array}{rl}{q}_t(s_t,a_t)-v_t\left(s_t\right)& \approx r_{t+1}+\gamma v_t\left(s_{t+1}\right)-v_t\left(s_t\right).\\ q_{\pi }(s_t,a_t)-v_{\pi }(s_t)& =\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})-v_{\pi }(S_t)|S_t=s_t,A_t=a_t],\end{array}$$

这使得我们可以仅靠维持一个神经网络追踪优势值就可以运行算法，而不是同时运行两个神经网络。当基线使用的是 TD error 的时候算法也可以被叫作 TD actor-critic。

$$\begin{array}{l}\text{Algorithm 10.2: Advantage actor-critic (A2C) or TD actor-critic}\\ \\ \text{Initialization: }\text{A policy function }\pi (a|s,{\theta }_0)\text{ where }{\theta }_0\text{ is the initial parameter.}\\ \text{A value function }v(s,w_0)\text{ where }{w}_0\text{ is the initial parameter. }{\alpha }_w,{\alpha }_{\theta }>0.\\ \\ \text{Goal: }\text{Learn an optimal policy to maximize }J(\theta ).\\ \\ \text{At time step }t\text{ in each episode, do}\\ \text{Generate }{a}_t\text{ following }\pi (a|s_t,{\theta }_t)\text{ and then observe }{r}_{t+1},s_{t+1}.\\ \text{Advantage (TD error):}\\ {\delta }_t=r_{t+1}+\gamma v(s_{t+1},w_t)-v(s_t,w_t)\\ \text{Actor (policy update):}\\ {\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }{\delta }_t{\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\\ \text{Critic (value update):}\\ w_{t+1}=w_t+{\alpha }_w{\delta }_t{\nabla }_{w}v(s_t,w_t)\end{array}$$

off-policy policy gradient

Policy based 算法基本上天生就是 On policy 的算法，如果没有针对自己的 Policy 求梯度的话，就不是针对自己的策略优化，这使得一个 Policy 只能针对现在的参数生成的轨迹求梯度，变了点参数又不能用了，使得 on-policy 的策略利用率较低。

从直觉上来说，因为 AC 是利用下一个动作的 $q(a,c)$ 来优化动作的，所以只要两个策略对于同一个状态的动作状态价值函数 $q(s,a)$ 是一样的话，在一个状态的到的导数应该是一样的，只不过因为取到这个动作的概率和这个状态在静态分布中的概率不同，所以乘上不同概率的权重即可：

$$\underset{\text{要求的分布}}{\underbrace{{\mathbb{E}}_{S\sim d_{\pi },A\sim \pi }}}\left[\underset{f(S,A,\theta )：给定(s,a)后是确定的}{\underbrace{{\nabla }_{\theta }\ln \pi (A|S,\theta )\cdot q_{\pi }(S,A)}}\right]={\mathbb{E}}_{S\sim d_{\beta },A\sim \beta }\left[\frac{\pi (A|S)}{\beta (A|S)}\cdot f(S,A,\theta )\right]$$

但是上述要求的 $q_{\pi }(a,c)=q_{\beta }(a,c)$ 并不被 Sarsa 满足，有几种方法： 第一种，critic 改用 Q-learning（$r_{t+1}+\gamma {\max }_{a^{\prime }}q(s_{t+1},a^{\prime },w)$）。这样 critic 估计的是 $q_{\ast }$​，不依赖任何策略，天然 off-policy。

第二种，critic 也加 importance sampling 修正。在 TD target 里对后续动作的采样也乘权重，让估计值收敛到 $q_{\pi }$​ 而非 $q_{\beta }$​。

第三种，也是实践中最主流的：让 $\beta$ 和 $\pi$ 不要差太远。PPO 就是这个思路——$\beta$ 是上一轮的旧策略 ${\pi }_{\text{old}}$​，用 clipping 保证新旧策略差距小，这样 $q_{{\pi }_{\text{old}}}\approx q_{\pi }$​，误差可控。严格说不完全对，但实践中足够好。

$$\begin{array}{l}\text{Algorithm 10.3: Off-policy actor-critic based on importance sampling}\\ \\ \text{Initialization: }\text{A given behavior policy }\beta (a|s).\text{ A target policy }\pi (a|s,{\theta }_0)\text{ where }{\theta }_0\text{ is the initial parameter.}\\ \text{A value function }v(s,w_0)\text{ where }{w}_0\text{ is the initial parameter. }{\alpha }_w,{\alpha }_{\theta }>0.\\ \\ \text{Goal: }\text{Learn an optimal policy to maximize }J(\theta ).\\ \\ \text{At time step }t\text{ in each episode, do}\\ \text{Generate }{a}_t\text{ following }\beta (s_t)\text{ and then observe }{r}_{t+1},s_{t+1}.\\ \text{Advantage (TD error):}\\ {\delta }_t=r_{t+1}+\gamma v(s_{t+1},w_t)-v(s_t,w_t)\\ \text{Actor (policy update):}\\ {\theta }_{t+1}={\theta }_t+{\alpha }_{\theta }\frac{\pi (a_t|s_t,{\theta }_t)}{\beta (a_t|s_t)}{\delta }_t{\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\\ \text{Critic (value update):}\\ 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)\end{array}$$

此处还有 Deterministic Policy Gradients 部分，但是目前和方向关系较弱，看了看没记笔记。