Dynamic programming, 动态规划

以下属于 Model-based 算法，其中 Model 指某个状态下执行某个行为后，获得的奖励概率 $p(r|s,a)$ 和转移到其他状态的概率 $p(s^{\prime }|s,a)$，Model-based 说明是在已知这些信息的条件下求解。

Value iteration

$$v_{k+1}=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}_k),k=0,1,2\cdots$$

WARNING

这里的 $v$ 并不表示价值，而只是一个普通的向量或数值。因为迭代算法的目的是求解贝尔曼最优公式，即找到一个最优的策略和其对应的价值，所以在迭代收敛前 $v$ 都不能赋予价值的含义。

1. 初始化 $v_0$ 向量，其表示每个状态的值
2. 计算 $v_k$ 对应的最优策略 ${\pi }_{k+1}$
   对于每个状态 $s$
   1. 计算每个行为的值 $q_k(s,a)$
   2. 选取 $q_k$ 最大的行为 $a^{\ast }(s)$
   3. 得到该状态下的最优策略 ${\pi }_{k+1}(s)=\{\begin{array}{ll}1& a=a^{\ast }(s)\\ 0& a\ne a^{\ast }(s)\end{array}$
3. 通过 $v_k$ 和 ${\pi }_{k+1}$ 计算新值 $v_{k+1}$。因为使用贪婪策略，所以新值等于各状态下最大的 $q_k$
4. 如果 $|v_k-v_{k-1}|$ 低于设定阈值, 则表示收敛

Policy iteration

1. 初始化策略 ${\pi }_0$
2. Policy evaluation, PE
   已知策略 ${\pi }_k$，代入贝尔曼方程，求解价值向量 $v_{{\pi }_k}$
   • 矩阵求解: $v_{{\pi }_k}=(I-\gamma P_{{\pi }_k}{)}^{-1}{r}_{{\pi }_k}$ (计算开销大)
   • 迭代求解: 先假定一个 $v_{{\pi }_k}^j$, 再通过贝尔曼方程算出 $v_{{\pi }_k}^{j+1}$, 如此迭代直至收敛
3. Policy improvement, PI
   计算 $v_{{\pi }_k}$ 对应的最优策略 ${\pi }_{k+1}$，同值迭代

Truncated policy iteration

对比 2 种迭代算法：

值迭代: $v_0\to {\pi }_1\to v_1\to {\pi }_2\cdots$

策略迭代: ${\pi }_0\to v_{{\pi }_0}\to {\pi }_1\to v_{{\pi }_1}\cdots$

其中 $v\to \pi$ 的步骤是一样的，关键区别在于 $\pi \to v$ 的步骤。 其中值迭代只进行一次计算: $v_k,{\pi }_{k+1}\to v_{k+1}$, 而策略迭代进行多次计算: $v_{{\pi }_k}^j,{\pi }_k\to v_{{\pi }_k}^{j+1}$。

所以我们可以把 $\pi \to v$ 变成更一般化的形式，即用参数 $j$ 表示在求 $v$ 过程中的迭代次数。当 $j=1$ 就是值迭代，当 $j=\mathrm{\infty }$ 就是策略迭代。

这个算法和策略迭代几乎一样，除了在 $\pi \to v$ 步骤中的迭代终止条件由是否收敛变成了是否达到迭代次数 $j$。

Monte Carlo, 蒙特卡洛

本节及其后均属于 Model-free 算法，即在不知道 Model 的情况下进行求解。

MC Basic

Model-free 的主要思想是把策略迭代中关于 Model 的部分移除。 在 $v\to \pi$ 步骤中，原本需要通过 Model 计算 $q_k$，现在直接用 $N$ 次采样得到的数据估计 $q_k$:

$$q_k(s,a)\approx \frac{1}{N}\sum _{i=1}^N{g}_k^i(s,a)$$

采样表示让智能体与环境进行一次交互。在状态 $s$ 采用行为 $a$ 后，每次到达一个新状态都随机选择一个行为，形成一条长度为 $j$ 的路径 $s\stackrel{a}{\to }{s}_1^{\prime }\stackrel{a_1^{\prime }}{\to }\cdots \stackrel{a_{j-1}^{\prime }}{\to }{s}_j^{\prime }$，则第 $i$ 次交互得到路径对应的奖励总和为:

$$g_k^i(s,a)=r(s,a)+\gamma r(s_1^{\prime },a_1^{\prime })+\cdots +{\gamma }^{j-1}r(s_{j-1}^{\prime },a_{j-1}^{\prime })$$

每次交互可以看作一次探索，而 $j$ 表示探索步数。探索步数需要足够长，才能保证可以从每个初始状态到达目标状态，否则有些初始状态将无法达到目标状态。

Exploring Starts

考虑从 $s_1,a_1$ 开始交互得到的某条路径: $s_1\stackrel{a_1}{\to }{s}_2\stackrel{a_2}{\to }{s}_3\stackrel{a_3}{\to }\cdots$，这条路径同时也包含了从 $s_2,a_2$ 开始的路径：$s_2\stackrel{a_2}{\to }{s}_3\stackrel{a_3}{\to }\cdots$，同时也包含了从 $s_3,a_3$ 开始的路径：$s_3\stackrel{a_3}{\to }\cdots$，以此类推。 这意味着，仅计算这一条路径就可以同时估计 $q(s_1,a_1),q(s_2,a_2),q(s_3,a_3),\cdots$。对于每条路径，有两种使用方法：

• first-visit: 仅在第一次遇到 $s_i,a_i$ 时估计
• every-visit: 每次遇到相同的 $s_i,a_i$ 时估计

在每次迭代中，对 $q_k$ 的估计也分为两类方法：

• 对于每个 $s_i,a_i$，多次采样取均值，见 MC Basic
• 对于每个 $s_i,a_i$，只采样一次，但控制探索步数

由于使用贪婪策略，使得每次 $\pi \to v$ 步骤只会选取一个行为，则无法保证每次交互能够达到所有 $s,a$，所以这种算法需要满足 exploring starts 条件，即对每个 $s,a$ 从头开始探索。

epsilon-Greedy

为了突破 exploring starts 条件，可以采用 $\epsilon$-贪婪策略：

$$\pi (a|s)=\{\begin{array}{ll}1-{\displaystyle \frac{\epsilon }{|A(s)|}}(|A(s)|-1)& a=a^{\ast }\\ {\displaystyle \frac{\epsilon }{|A(s)|}}& a\ne a^{\ast }\end{array}$$

其中 $\epsilon \in [0,1]$, $|A(s)|$ 表示状态 $s$ 下的行为数量，通过这种方法平衡了探索（exploration）和利用（exploitation）。当 $\epsilon =0$ 时，变成贪婪策略，表示对数据的充分利用；当 $\epsilon =1$ 时，变成随机策略，表示不依赖数据的完全探索。

这样可以保证在一次交互中，只要探索步数足够长，智能体就可以达到所有的 $s,a$。

INFO

这里实际上将求解贝尔曼最优公式的目的从“从所有可能的策略中找到最优策略”变成“从所有可能的 $\epsilon$-贪婪策略中找到最优策略”，即找到最优 $\epsilon$。这样牺牲了求解出策略的最优性，最优策略应该是贪婪策略，所以可以在迭代过程中使 $\epsilon \to 0$。

Temporal-Difference, TD, 时序差分

所有 TD 算法都可以看作使用 随机近似 算法求解贝尔曼方程或贝尔曼最优方程，它们的更新公式都可以表示为：

$$v_{t+1}=v_t-{\alpha }_t[v_t-{\overline{v}}_t]$$

其中 $v_t$ 表示在时间步 $t$ 下的状态价值或行为价值，${\overline{v}}_t$ 是 TD 目标，$v_t-{\overline{v}}_t$ 是 TD 误差。不同算法的区别在于 TD 目标不同。

通过不断迭代更新，$v_t$ 将逐渐逼近 TD 目标

$$\begin{array}{rl}{v}_{t+1}& =v_t-{\alpha }_t[v_t-{\overline{v}}_t]\\ v_{t+1}-{\overline{v}}_t& =v_t-{\overline{v}}_t-{\alpha }_t[v_t-{\overline{v}}_t]\\ v_{t+1}-{\overline{v}}_t& =[1-{\alpha }_t][v_t-{\overline{v}}_t]\\ 0<\frac{v_{t+1}-{\overline{v}}_t}{v_t-{\overline{v}}_t}& =1-{\alpha }_t<1\end{array}$$

可以发现，随着时间步 $t$ 的增大，$v_t$ 到 ${\overline{v}}_t$ 的距离逐渐缩小。

TD, 估计状态价值

该算法用于求解在给定策略 $\pi$ 下的 $v_{\pi }$。由于不知道 Model 信息，所以考虑贝尔曼期望方程：

$$v_{\pi }(s)=\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|S=s],s\in S$$

使用 RM 算法逼近 $v_{\pi }$：

$$\begin{array}{rl}g(v(s))& =v(s)-v_{\pi }(s)\\ \tilde{g}(v(s))& =g(v(s))+\eta \\ & =v(s)-v_{\pi }(s)+v_{\pi }(s)-[r+\gamma v_{\pi }(s^{\prime })]\\ & =v(s)-[r+\gamma v_{\pi }(s^{\prime })]\\ v_{k+1}(s)& =v_k(s)-{\alpha }_k[v_k(s)-[r+\gamma v_{\pi }(s^{\prime })]],k=1,2,3,\cdots \end{array}$$

从公式中可看出，要想对价值估计值 $v$ 进行一次更新，至少需要 3 个信息：

• 当前状态 $s$
• 及时奖励 $r$
• 下一个状态 $s^{\prime }$

于是通过采样得到 $(s_0,r_1,s_1,\cdots ,s_t,r_{t+1},s_{t+1},\cdots )$，这些数据以 $(s_t,r_{t+1},s_{t+1})$ 为一组，每组仅能用于更新该组初始状态的价值估计：

$$v_{t+1}(s_t)=v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]]$$

由于 $v_{\pi }$ 未知，所以这里使用 $v_t$ 估计 $v_{\pi }$。

Sarsa, 估计行为价值

该算法用于求解在给定策略 $\pi$ 下的 $q_{\pi }$，将贝尔曼期望方程改写成 $q_{\pi }$ 形式：

$$q_{\pi }(s,a)=\mathbb{E}[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|S=s,A=a],s\in S,a\in A(s)$$

和 TD 一样，使用 RM 算法逼近 $q_{\pi }$。要想进行一次价值估计的更新，则需要 $(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$：

$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]]$$

这种算法在 $\pi \to v$ 步骤中只进行一次 $q(s,a)$ 更新，接着在 $v\to \pi$ 步骤使用 $\epsilon$-greedy 。

Expected Sarsa

该算法对应的贝尔曼期望方程为：

$$\begin{array}{rl}{q}_{\pi }(s,a)& =\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|S=s,A=a],s\in S,a\in A(s)\\ & =\mathbb{E}[R+\gamma \mathbb{E}[q_{\pi }(S^{\prime },A^{\prime })]|S=s,A=a]\end{array}$$

更新需要 $(s_t,a_t,r_{t+1},s_{t+1})$。由于 $v_{\pi }$ 未知，所以使用 $q$ 估计 $v_{\pi }$：

$$\begin{array}{r}{q}_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma v_t(s_{t+1})]]\\ v_t(s_{t+1})=\sum _a{\pi }_t(a|s_{t+1})q_t(s_{t+1},a)\end{array}$$

$n$-step Sarsa

该算法对应的贝尔曼期望方程为：

$$q_{\pi }(s,a)=\mathbb{E}[G|S=s,A=a],s\in S,a\in A(s)$$

其中 $G$ 表示从 $s,a$ 开始的累积奖励：

$$G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})$$

其中 $n$ 表示表达式的展开步数，无论 $n$ 取值多少，这些表达式都等价。对应的迭代更新公式为：

$$\begin{array}{r}{q}_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-g_t^{(n)}]\\ g_t^{(n)}=r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(s_{t+n},a_{t+n})\end{array}$$

由公式可知，当 $n=1$ 时，得到 Sarsa；当 $n=\mathrm{\infty }$ 且 ${\alpha }_t=1$ 时，得到 Monte Carlo。

INFO

这里的 $n$ 表示更新价值估计所需的步数。$n=1$ 说明在每次采样中，智能体每走一步就更新一次价值估计和策略，这形成了增量更新。

Q-learning, 估计最优行为价值

该算法并不求解给定策略 $\pi$ 对应的 $v_{\pi }$ 或 $q_{\pi }$，而是直接求解最优的 $q$，表示为贝尔曼最优方程的 $q$ 形式：

$$q(s,a)=\mathbb{E}[R+\gamma \underset{a}{max}q(S^{\prime },a)|S=s],s\in S,a\in A(s)$$

更新公式为：

$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma \underset{a}{max}{q}_t(s_{t+1},a)]]$$

INFO

RL 中有两种策略：

• behavior policy：用于从环境中采样数据
• target policy：被迭代优化的策略

由此分为两大类学习算法：

• on-policy：behavior policy 与 target policy 相同
  即在每一次迭代中，用优化后的策略进行下一次采样。
• off-policy：behavior policy 与 target policy 不同
  即用 behavior policy 采样的数据训练 target policy。

Q-learning 可以分为 on-policy 和 off-policy 两种版本。 由于 on-policy 版需要用 target policy 采样数据，要想保证探索性的话，就需要让 target policy 为 $\epsilon$-greedy。 而 off-policy 版不需要用 target policy 采样数据，所以可以直接使用 greedy。

Value Function Approximation, VFA, 价值函数近似

基于表格的 TD 中，$v$ 和 $q$ 都是离散的，即可以用一个表格来装满所有可能的 $v$ 或 $q$ 值。但对于复杂的现实世界，状态空间或行为空间很可能是无限的，这时候需要使用函数近似来表示 $v$ 或 $q$。这个函数可以是一个线性的多项式，也可以是非线性的神经网络。

VFA 基本思路

给定一个策略 $\pi$，要找到函数 $\hat{v}(s,w)$ 使其最接近真值 $v_{\pi }(s)$。也就是找到一个 $w$ 使目标函数 $J(w)$ 达到最小值：

$$\begin{array}{rl}J(w)& =\mathbb{E}[[\hat{v}(S,w)-v_{\pi }(S){]}^2]\\ & =\sum _{s\in S}{d}_{\pi }(s)[\hat{v}(s,w)-v_{\pi }(s){]}^2\end{array}$$

由于 $J(w)$ 是一个期望值，即一个无限采样求均值的过程，所以我们需要知道状态 $S$ 的概率分布，也就是在每次采样时出现状态 $s$ 的概率 $d_{\pi }(s)$。由于状态转移的马尔可夫性质，最终的状态概率分布是一种稳态分布，它表示当智能体执行了无数次行为后到达各状态的频率分布：

$$\begin{array}{rl}{d}_{\pi }(s)& =\underset{N\to \mathrm{\infty }}{lim}\frac{n_{\pi }(s)}{N}\\ P_{\pi }^T{d}_{\pi }& =d_{\pi }\end{array}$$

其中 $P_{\pi }$ 是贝尔曼方程中的状态转移矩阵，$d_{\pi }$ 是表示状态概率分布的列向量。

要找到 $J(w)$ 最小值对应的 $w$，通常使用 梯度下降：

$$w_{k+1}=w_k-{\alpha }_k{\mathrm{\nabla }}_{w}J(w_k)$$$$\begin{array}{rl}{\mathrm{\nabla }}_{w}J(w)& ={\mathrm{\nabla }}_w\mathbb{E}[[\hat{v}(S,w)-v_{\pi }(S){]}^2]\\ & =2\mathbb{E}[[\hat{v}(S,w)-v_{\pi }(S)]{\mathrm{\nabla }}_w\hat{v}(S,w)]\end{array}$$

由于 $J(w)$ 的梯度是一个期望值，通常使用一次采样估计真实梯度，即 SGD。这里的常数项 $2$ 被并入 ${\alpha }_k$：

$$w_{k+1}=w_k-{\alpha }_k[\hat{v}(s,w)-v_{\pi }(s)]{\mathrm{\nabla }}_w\hat{v}(s,w)$$

这个更新公式中的 $v_{\pi }$ 也是未知的，于是进行估计：

• MC 使用奖励总和 $g_t$ 估计
• TD 使用 TD target 估计

INFO

以 Sarsa 为例。 不同与传统算法的更新 $q(s,a)$，基于函数近似的算法是更新行为价值函数 $\hat{q}(s,a,w)$ 的参数 $w$，然后再用新参数计算行为价值：

$$w_{t+1}=w_t-{\alpha }_t[\hat{q}(s_t,a_t,w_t)-[r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1},w_t)]]{\mathrm{\nabla }}_w\hat{q}(s_t,a_t,w_t)$$$$q(s_t,a_t)=\hat{q}(s_t,a_t,w_{t+1})$$

Deep Q-learning, DQN

即 Deep Q-network

和 Q-learning 一样，该算法对最优策略下的行为价值进行估计：

$$q_{\pi }(s,a)=r+\gamma \underset{a\in A(s^{\prime })}{max}\hat{q}(s^{\prime },a,w)$$

则目标函数或损失函数为：

$$J(w)=[\hat{q}(s,a,w)-[r+\gamma \underset{a\in A(s^{\prime })}{max}\hat{q}(s^{\prime },a,w_T)]{]}^2$$

其中包含两个相同的神经网络：$\text{main network}$ 和 $\text{target network}$，每次迭代都会更新主网络参数 $w$，迭代一定次数后再将 $w$ 赋给目标网络参数 $w_T$。之所以分成两个网络，是因为计算目标网络参数的梯度过于复杂，于是采取延迟更新的方法。

参考 off-policy 版本的伪代码：

1. 根据给定策略 $\pi$ 进行采样，得到以 $(s,a,r,s^{\prime })$ 为元素的集合 $B$，其称为 replay buffer
2. 对目标网络进行迭代训练，每次迭代进行 MBGD：
   1. 从 $B$ 中随机均匀地进行一些采样得到小批量样本集，对于每个样本 $(s,a,r,s^{\prime })$：
      1. 使用目标网络计算 $y_T=r+\gamma \underset{a\in A(s^{\prime })}{max}\hat{q}(s^{\prime },a,w_T)$
      2. 使用 $(s,y_T)$ 更新主网络参数 $w$，以最小化损失值 $[y_T-\hat{q}(s,a,w){]}^2$
3. 每迭代 $C$ 次后，更新目标网络权重 $w_T=w$

INFO

在 基本思路 中提到 $J(w)$ 的理论值是一个包含了状态概率分布信息的期望值，而这里却使用随机均匀抽样从 $B$ 中获取样本集。这是因为我们并不知道最优策略及其对应的状态概率分布，所以需要确保每个状态被探索的概率均等。

另一方面，因为 $B$ 是在给定策略下的采样数据，所以满足该策略下的状态概率分布，而不一定是均匀分布。所以需要打乱样本，以破坏样本间关系。

Policy Gradient, PG, 策略梯度

即 Policy Function Approximation，策略函数近似

像 VFA 一样，我们也可以用函数表示策略 $\pi (a|s,\theta )$，其中 $\theta$ 是策略函数的参数。为了找到最优策略，需要构建一个 metric 函数 $J(\theta )$，函数值越大则策略越好。所以问题变成了找一个参数 $\theta$ 使 $J(\theta )$ 达到最大值，这通常使用梯度上升解决。

Metric

在 VFA 基本思路 中提到每个策略 $\pi$ 都对应一个状态概率分布 $d_{\pi }$，一个好的策略应该能够更多地访问高价值的状态，于是用状态价值的加权平均衡量策略的优劣：

$$\begin{array}{rl}{\overline{v}}_{\pi }& =\sum _{s\in S}d(s)v_{\pi }(s)\\ & =d^T{v}_{\pi }\\ {\overline{v}}_{\pi }& =\mathbb{E}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{R}_{t+1}]\end{array}$$

其中 $d$ 表示状态概率向量，是可设置的。通常我们将 $d=d_{\pi }$，表示寻找从任意初始状态出发都能找到最优路径的策略；如果 $d={\left[\begin{array}{cccc}1& 0& \cdots & 0\end{array}\right]}^T$，则表示只寻找从 $s_1$ 出发的最优策略。

也可以使用奖励的加权平均作为优劣指标，它也表示从任意状态出发走无数步后获得的平均奖励：

$$\begin{array}{rl}{\overline{r}}_{\pi }& =\sum _{s\in S}{d}_{\pi }(s)r_{\pi }(s)\\ r_{\pi }(s)& =\sum _{a\in A}\pi (a|s)r(s,a)\\ r(s,a)& =\sum _{r}p(r|s,a)r\\ {\overline{r}}_{\pi }& =\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\mathbb{E}[\sum _{k=1}^n{R}_{t+k}]\end{array}$$

当 $\gamma \in [0,1)$，这两个指标是等价的：

$${\overline{r}}_{\pi }=(1-\gamma ){\overline{v}}_{\pi }$$

Metric 梯度

对于 ${\overline{r}}_{\pi }$, ${\overline{v}}_{\pi }$, 和给定状态概率分布 $d$ 情况下的 ${\overline{v}}_{\pi }^0$，其梯度大致满足以下关系：

$$\begin{array}{rl}{\mathrm{\nabla }}_{\theta }J(\theta )& =\sum _{s\in S}\eta (s)\sum _{a\in A}{\mathrm{\nabla }}_{\theta }\pi (a|s,\theta )q_{\pi }(s,a)\\ & =\mathbb{E}[{\mathrm{\nabla }}_{\theta }\ln \pi (A|S,\theta )q_{\pi }(S,A)],S\sim \eta ,A\sim \pi (A|S,\theta )\end{array}$$

该式在不同指标间存在一些差异

令 $h(s,a)={\mathrm{\nabla }}_{\theta }\pi (a|s,\theta )q_{\pi }(s,a)$，则：

$$\begin{array}{rl}& {\mathrm{\nabla }}_{\theta }{\overline{r}}_{\pi }\{\begin{array}{ll}\approx \sum _s{d}_{\pi }(s)\sum _{a}h(s,a)& \gamma \in (0,1)\\ =\sum _s{d}_{\pi }(s)\sum _{a}h(s,a)& \gamma =1\end{array}\\ & {\mathrm{\nabla }}_{\theta }{\overline{v}}_{\pi }=\frac{1}{1-\gamma }{\mathrm{\nabla }}_{\theta }{\overline{r}}_{\pi }\\ & {\mathrm{\nabla }}_{\theta }{\overline{v}}_{\pi }^0=\sum _s{\rho }_{\pi }(s)\sum _{a}h(s,a)\end{array}$$

把梯度写成期望值的形式，就可以使用 SGD 进行优化。对于这个公式，需要保证 $\pi (a|s,\theta )>0$ 才有意义，所以使用 softmax 进行归一化，也就是让 $\pi (a|s,\theta )$ 满足：

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

其中 $h(s,a,\theta )$ 表示 $s,a$ 的特征函数，通常是一个神经网络。

PG 参数更新

为了找到 $J(\theta )$ 最大值对应的 $\theta$，使用随机梯度上升：

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

由于 $q_{\pi }$ 未知，所以使用 $q_t$ 估计：

• 使用 MC 估计，则得到 REINFORCE 算法
• 使用 TD 估计，则得到 Actor-Critic-* 算法

无论哪种估计方法，都需要先采样，这就涉及到 $S,A$ 的概率分布问题。理论中 $S\sim \eta$，由于环境信息未知，所以实际中难以满足；$A\sim \pi (A|S,\theta )$ 说明每次的行为 $a_t$ 都应该由 $\pi ({\theta }_t)$ 进行采样，因此策略梯度算法是 on-policy 的。

对更新公式进一步转化：

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha {\mathrm{\nabla }}_{\theta }\ln \pi (a_t|s_t,{\theta }_t)q_t(s_t,a_t)\\ & ={\theta }_t+\alpha \frac{{\mathrm{\nabla }}_{\theta }\pi (a_t|s_t,{\theta }_t)}{\pi (a_t|s_t,{\theta }_t)}{q}_t(s_t,a_t)\\ & ={\theta }_t+\alpha {\beta }_t{\mathrm{\nabla }}_{\theta }\pi (a_t|s_t,{\theta }_t),{\beta }_t=\frac{q_t(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}\end{array}$$

这表明更新公式实际上是在更新 $\pi (a_t|s_t,{\theta }_t)$，其步长为 $\alpha {\beta }_t$。${\beta }_t$ 越大，则 $\pi (a_t|s_t,{\theta }_{t+1})$ 增大，说明策略 $\pi$ 将在状态 $s_t$ 时更倾向选 $a_t$。${\beta }_t$ 也体现了探索和利用的平衡，${\beta }_t\propto q_t$ 表示利用，${\beta }_t\propto {\displaystyle \frac{1}{\pi (a_t|s_t,{\theta }_t)}}$ 表示探索。

REINFORCE

在每次迭代中：

1. 选择初始状态 $s_0$，使用 $\pi ({\theta }_k)$ 进行采样，对于每个样本 $(s_t,a_t,r_{t+1})$：
   1. 计算 $q_t(s_t,a_t)$ 为折扣奖励总和
   2. 更新 ${\theta }_t$
2. 将最后一次 ${\theta }_t$ 赋给 ${\theta }_k$

Actor-Critic, AC

Actor 表示通过 PG 进行策略更新，Critic 表示用结合 VFA 的 TD 进行价值估计。

Q actor-critic, QAC

使用 Sarsa 进行价值估计。在 Critic 阶段进行价值函数参数更新：

$$w_{t+1}=w_t-{\alpha }_t[q(s_t,a_t,w_t)-[r_{t+1}+\gamma q(s_{t+1},a_{t+1},w_t)]]{\mathrm{\nabla }}_{w}q(s_t,a_t,w_t)$$

在 Actor 阶段进行策略函数参数更新：

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

Advantage actor-critic, A2C

向策略函数参数梯度公式中引入偏置量：

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

$b(S)$ 不影响采样梯度的期望值，但可以影响方差。所以通过控制 $b(S)$ 使方差最小，以减小对梯度的抽样误差。计算理论最优偏置量 $b^{\ast }$ 过于复杂，通常使用估计值：

$$\begin{array}{rl}{b}^{\ast }(s)& =\frac{\mathbb{E}[||{\mathrm{\nabla }}_{\theta }\ln \pi (A|s,{\theta }_t)|{|}^{2}q(s,A)]}{\mathbb{E}[||{\mathrm{\nabla }}_{\theta }\ln \pi (A|s,{\theta }_t)|{|}^2]},s\in S,A\sim \pi (A|s)\\ & \approx \mathbb{E}[q(s,A)]=v_{\pi }(s)\end{array}$$

代入参数更新公式：

$$\begin{array}{r}{\theta }_{t+1}={\theta }_t+{\alpha }_t{\mathrm{\nabla }}_{\theta }\ln \pi (a_t|s_t,{\theta }_t)A(s_t,a_t)\\ A(s,a)=q_{\pi }(s,a)-v_{\pi }(s)\end{array}$$

其中 $A$ 称为 advantage function 优势函数，$v_{\pi }$ 可以看作 $q_{\pi }$ 的均值，则 $A$ 表示某个行为的价值比平均行为价值多出的部分，即该行为的优势。再考虑更新公式中的步长 ${\beta }_t$，见 PG 参数更新：

$${\beta }_t=\frac{A(s_t,a_t)}{\pi (a_t|s_t,{\theta }_t)}$$

其中分子部分表示对数据的充分利用，相比之前的绝对行为价值 $q_t(s_t,a_t)$，使用相对行为价值 $A(s_t,a_t)$ 能更好地评估行为的优劣。

结合 TD 得到具体更新公式，其中 $A_t$ 也表示 TD 误差：

$$\begin{array}{rl}{A}_t& =r_{t+1}+\gamma v(s_{t+1},w_t)-v(s_t,w_t)\\ w_{t+1}& =w_t-{\alpha }_w(-A_t){\mathrm{\nabla }}_{w}v(s_t,w_t)\\ {\theta }_{t+1}& ={\theta }_t+{\alpha }_{\theta }{A}_t{\mathrm{\nabla }}_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\end{array}$$

off-policy actor-critic

由于 ${\mathrm{\nabla }}_{\theta }J(\theta )$ 是一个满足 $A\sim \pi (A|S,\theta )$ 的期望值，即用于采样的策略同时也是需要进行迭代更新的策略，所以使用 on-policy 算法，见 PG 参数更新。如果我们想利用已有策略的经验训练新策略，则需要使用 off-policy 算法。

由于 behavior policy $\beta$ 与 target policy $\pi$ 不同，所以其对应的状态概率分布 $d_{\beta }$ 和 $d_{\pi }$ 不同，那么就需要引入新 metric：

$$\begin{array}{rl}J(\theta )& =\mathbb{E}[v_{\pi }(S)],S\sim d_{\beta }\\ {\mathrm{\nabla }}_{\theta }J(\theta )& =\mathbb{E}[\frac{\pi (A|S,\theta )}{\beta (A|S)}{\mathrm{\nabla }}_{\theta }\ln \pi (A|S,\theta )q_{\pi }(S,A)],S\sim d_{\beta },A\sim \beta \end{array}$$

Importance Sampling

对于 off-policy 算法，需要引入 importance sampling，即在更新参数时，使用旧策略的采样结果来估计新策略的期望。

由此得到 $\theta$ 更新公式：

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+{\alpha }_{\theta }\frac{\pi (a_t|s_t,{\theta }_t)}{\beta (a_t|s_t)}{\mathrm{\nabla }}_{\theta }\ln \pi (a_t|s_t,{\theta }_t)A_t(s_t,a_t)\\ & ={\theta }_t+{\alpha }_{\theta }\frac{A_t(s_t,a_t)}{\beta (a_t|s_t)}{\mathrm{\nabla }}_{\theta }\pi (a_t|s_t,{\theta }_t)\end{array}$$

其中步长的分母 $\beta (a_t|s_t)$ 是一个定值，则表示不进行任何探索，也就是使用已有策略 $\beta$ 的经验进行更新。

Deterministic actor-critic, DPG

之前选择行为的概率都满足 $\pi (a|s)\in (0,1)$，但理论最优策略应该是一个确定性策略，即只选择价值最大的行为。只考虑确定性策略时，$a$ 可以表示成一个连续值，用 $S\to A$ 的映射表示策略：

$$a=\mu (s,\theta )$$

$\mu$ 函数简写为 $\mu (s)$，通常是一个神经网络。由此得到 metric 函数：

$$\begin{array}{rl}J(\theta )& =\mathbb{E}[v_{\mu }(S)],S\sim d\\ {\mathrm{\nabla }}_{\theta }J(\theta )& =\mathbb{E}[{\mathrm{\nabla }}_{\theta }\mu (S){\mathrm{\nabla }}_a{q}_{\mu }(S,a)],a=\mu (S),S\sim {\rho }_{\mu }\end{array}$$

其中 $d$ 是一个可设置的状态概率分布，见 Metric。${\rho }_{\mu }$ 是另一个由 $d$ 推导出的状态概率分布。代入更新公式：

$$\begin{array}{rl}{\eta }_t& =r_{t+1}+\gamma q(s_{t+1},\mu (s_{t+1},{\theta }_t),w_t)-q(s_t,a_t,w_t)\\ w_{t+1}& =w_t-{\alpha }_w(-{\eta }_t){\mathrm{\nabla }}_{w}q(s_t,a_t,w_t)\\ {\theta }_{t+1}& ={\theta }_t+{\alpha }_{\theta }{\mathrm{\nabla }}_{\theta }\mu (s_t,{\theta }_t){\mathrm{\nabla }}_{a}q(s_t,a,w_{t+1}),a=\mu (s_t,{\theta }_t)\end{array}$$

如果要把该算法改成 on-policy，即使用 target policy $\mu$ 进行采样，会存在一个问题：$\mu$ 是一个确定性策略，即遇到相同的 $s$ 只选相同的 $a$，所以失去了探索的机会。这时可以向 $\mu$ 函数中加入噪声，使其不确定性增加，从而增加探索的机会。

该算法还涉及 $q$ 函数的选取，如果使用神经网络则得到 Deep Deterministic Policy Gradient, DDPG。