蒙特卡洛预测#

在给定一个策略$\pi$的情况下，对于某个状态$s$的价值函数$v_\pi(s)$，蒙特卡洛方法首先采集在策略$\pi$下途径状态$s$的多幕数据，得到一系列从状态$s$开始的期望回报，再对其求平均来估计$v_\pi(s)$。

在同一幕中，状态$s$可能被多次访问到，我们称第一次访问为$s$的首次访问。首次访问型MC算法用$s$的所有首次访问的回报的平均值估计$v_\pi(s)$，每次访问型MC算法则使用所有访问的回报的平均值。本章主要关注理论基础更成熟首次访问型MC算法，由每次访问型MC算法扩展而来的函数近似与资格迹方法将在后期介绍。

当$s$的访问次数趋于无穷时，首次访问型MC和每次访问型MC均收敛到$v_\pi(s)$。对于首次访问型MC，每个回报值都是对$v_\pi(s)$的一个独立同分布的估计，且估计方差有限，根据大数定律可一阶收敛到其期望值。而对于每次访问型MC，来自同一幕的回报值共享后续序列，具有高度相关性，但仍能证实其会二阶收敛到$v_\pi(s)$。限于精力和篇幅本系列不拓展算法更深入的数学原理。

一个首次访问型MC预测算法的伪代码如下：

1. 输入：待评估的策略$\pi$
2. 初始化：
   1. 对所有的$s\in\mathcal S$，任意初始化$V(s)\in\mathbb R$
   2. 对所有的$s\in\mathcal S$，$\textit{Returns}(s)\leftarrow$空列表
3. 无限循环（对每幕）：
   1. 根据$\pi$生成一幕序列：$s_0,A_0,R_1,\cdots,S_{T-1},A_{T-1},R_T$
   2. $G\leftarrow0$
   3. 对本幕中的每一步进行循环，$t=T-1,T-2,\cdots,0$：
      1. $G\leftarrow\gamma G+R_{t+1}$
      2. 除非$S_t$在$S_0,S_1,\cdots,S_{t-1}$出现过：
         1. 将$G$加入$\textit{Returns}(s)$
         2. $V(S_t)\leftarrow\mathrm{average}(\textit{Returns}(S_t))$

动作价值的蒙特卡洛估计#

在有环境模型的情况下，只需要状态价值函数就足以确定一个策略，即选取特定的动作使得当前收益与后继状态的状态价值函数之和的期望最大。但在没有环境模型的情况下，我们无法利用环境动态特性计算期望，必须显式地估计每个动作的价值函数来确定策略。

在蒙特卡洛方法中，动作价值函数的策略评估只需将对状态的访问改为对“状态-动作”二元组的访问即可。唯一的困难在于一些“状态-动作”二元组可能永远不会被访问到，尤其是在$\pi$为确定性策略的情况下，每个状态只能观测到一个动作的回报，这要求我们保证持续地试探。

一种方法是在每一幕中，人为指定“状态-动作”二元组作为起点开始采样，并保证所有的“状态-动作”二元组都有非零的概率可以被选为起点。当在采样的幕的个数趋向于无穷时，每一个“状态-动作”二元组都会被访问到无数次。该方法被称为试探性出发。另一种方法是考虑在每个状态下所有动作都有非零概率被选中的随机策略，将在后文讨论。

蒙特卡洛控制#

现在可以考虑如何使用蒙特卡洛估计来解决控制问题，即如何近似最优策略。

我们仍采用广义策略迭代（GPI）的思想。最基础地，策略评估即采用蒙特卡洛估计，策略改进则直接对动作价值的估计进行贪心，无需再计算期望：

为了保证其收敛到最优策略，我们还有两个假设。一是试探性出发，二是在策略评估中观测无限多幕样本序列。第一个假设的破除方法将在后文介绍，而第二个假设在动态规划一章中已经给出了两个方案。

第一个方案是以一个小阈值作为收敛的判断标准，只要求其在一定程度上足够逼近。第二个方案是不要求在策略改进之前完成策略评估，一种极端形式即价值迭代，在相邻的两次策略改进之间只进行一次策略评估。将后者应用到蒙特卡洛策略迭代中，则为在每次更新一个“状态-动作”二元组的动作价值后，即刻更新贪心策略在该状态选择的动作，其算法被称为基于试探性出发的蒙特卡洛（蒙特卡洛ES），它的首次访问型的伪代码如下：

1. 初始化：
   1. 对所有$s\in\mathcal S$，任意初始化$\pi(s)\in\mathcal A(s)$
   2. 对所有$s\in\mathcal S$，$a\in\mathcal A(s)$，任意初始化$Q(s,a)\in\mathbb R$
   3. 对所有$s\in\mathcal S$，$a\in\mathcal A(s)$，$\textit{Returns}(s,a)\leftarrow$空列表
2. 无限循环（对每幕）：
   1. 选择$S_0\in\mathcal S$和$A_0\in\mathcal A(S_0)$以使得所有“状态-动作”二元组的概率都$>0$
   2. 从$S_0,A_0$开始根据$\pi$生成一幕序列$S_0,A_0,R_1,\cdots,S_{T-1},A_{T-1},R_T$
   3. $G\leftarrow0$
   4. 对幕中的每一步循环，$t=T-1,T-2,\cdots,0$：
      1. $G\leftarrow\gamma G+R_{t+1}$
      2. 除非二元组$S_t,A_t$在$S_0,A_0,S_1,A_1,\cdots,S_{t-1},A_{t-1}$中已出现过：
         1. 将$G$加入$\textit{Returns}(S_t,A_t)$
         2. $Q(S_t,A_t)\leftarrow\mathrm{average}(\textit{Returns}(S_t,A_t))$
         3. $\pi(S_t)\leftarrow\underset a{\mathrm{average}}Q(S_t,a)$

同轨策略蒙特卡洛控制#

破除试探性出发假设的主要思路即考虑在每个状态下所有动作都有非零概率被选中的随机策略。有两种方法可以保证这一点，分别称为同轨策略和离轨策略。在同轨策略中，用于生成采样数据序列的策略和用于实际决策的待评估和改进的策略是相同的；在离轨策略中，用于生成采样数据序列的策略和用于实际决策的待评估和改进的策略是不同的。离轨策略在下一节介绍。

在同轨策略方法中，策略一般是“软性”的，即对于任意$s\in\mathcal S$以及$a\in\mathcal A(s)$，都有$\pi(a|s)>0$，但它们会逐渐地逼近一个确定性的策略。本节使用$\epsilon$-贪心策略进行策略改进，即设置一个小常量$\epsilon>0$，让所有的非贪心动作都有$\displaystyle\frac\epsilon{|\mathcal A(s)|}$的概率被选中，而贪心动作被选中的概率为$1-\epsilon+\displaystyle\frac\epsilon{|\mathcal A(s)|}$。$\epsilon$-贪心策略是$\epsilon$-软性策略的一个特例，$\epsilon$-软性策略只保证所有的状态和动作都有$\pi(a|s)\geqslant\displaystyle\frac\epsilon{|\mathcal A(s)|}$，而$\epsilon$-贪心策略是其中最接近贪心策略的一个。

删除蒙特卡洛ES的试探性假设，并把贪心策略替换为$\epsilon$-贪心策略，我们得到同轨策略的MC控制算法（首次访问型）伪代码如下：

1. 参数：很小的$\epsilon>0$
2. 初始化：
   1. $\pi\leftarrow$一个任意的$\epsilon$-软性策略
   2. 对所有$s\in\mathcal S$，$a\in\mathcal A(s)$，任意初始化$Q(s,a)\in\mathbb R$
   3. 对所有$s\in\mathcal S$，$a\in\mathcal A(s)$，$\textit{Returns}(s,a)\leftarrow$空列表
3. 无限循环（对每幕）：
   1. 根据$\pi$生成一幕序列$S_0,A_0,R_1,\cdots,S_{T-1},A_{T-1},R_T$
   2. $G\leftarrow0$
   3. 对幕中的每一步循环，$t=T-1,T-2,\cdots,0$：
      1. $G\leftarrow\gamma G+R_{t+1}$
      2. 除非二元组$S_t,A_t$在$S_0,A_0,S_1,A_1,\cdots,S_{t-1},A_{t-1}$中已出现过：
         1. 将$G$加入$\textit{Returns}(S_t,A_t)$
         2. $Q(S_t,A_t)\leftarrow\mathrm{average}(\textit{Returns}(S_t,A_t))$
         3. $A^*\leftarrow\underset a{\mathrm{average}}Q(S_t,a)$
         4. 对所有的$a\in\mathcal A(S_t)$：
            1. $\pi(a|S_t)\leftarrow\left\{\begin{matrix}1-\epsilon+\displaystyle\frac\epsilon{|\mathcal A(S_t)|}&\mathrm{if}a=A^*\\\displaystyle\frac\epsilon{|\mathcal A(S_t)|}&\mathrm{if}a\neq A^*\end{matrix}\right.$

我们先证明该算法的策略改进定理：对于一个$\epsilon$-软性策略$\pi$，任何一个根据$q_\pi$生成的$\epsilon$-贪心策略都是对其的一个改进。

对任意的$s\in\mathcal S$，先根据$\epsilon$-贪心策略$\pi'$选择动作后仍遵循原$\epsilon$-软性策略$\pi$，对应的动作价值函数的期望为：

而原策略$\pi$的状态价值函数可写为：

比较两者的第二项，$v_\pi(s)$的$(1-\epsilon)$后面$q_\pi(s,a)$的权重和为$1$，一定小于其最大值，故新策略比原策略更优。

接下来证明使得$q_\pi(s,\pi'(s))=v_\pi(s)$成立的充要条件为$\pi'$和$\pi$都为最优$\epsilon$-软性策略。

我们已知满足贝尔曼最优方程的策略为最优（贪心）策略，故可以考虑将$\epsilon$-软性的特性转移到环境内部，从而只需列出贝尔曼最优方程即可。在旧环境的基础上，一个可以保证每个动作都至少有$\displaystyle\frac\epsilon{|\mathcal A(s)|}$的概率被选中的新环境表现的行为如下：在状态$s$采取动作$a$时，新环境有$1-\epsilon$的概率与旧环境的表现完全相同，而有$\epsilon$的概率重新从所有动作中等概率选择一个，并仍表现得和在旧环境采取这一新选择的动作一样。

令$\tilde v_*$和$\tilde q_*$为新环境的最优价值函数，则根据贝尔曼最优方程有：

而证明中需要成立的等式可进一步写为：

除了$\tilde v_*$被替换为$v_\pi$，该等式与新环境的最优方程完全相同。由于$\tilde v_*$是唯一解，因此一定有$v_\pi=\tilde v_*$。

基于重要度采样的离轨策略#

同轨策略方法是一种妥协，它并不学习最优策略的动作值，而是接近最优而且仍能进行试探的策略的动作值。一个更加直接的方法是采用两个策略，一个用来学习并最终成为最优策略，另一个更加有试探性，用来产生智能体的行动样本。用来学习的策略被称为目标策略，用于生成行动样本的策略被称为行动策略，整个学习过程被称为离轨策略学习。

首先要解决的问题是如何根据由行动策略$b$得到的价值函数$v_b$或$q_b$来预测目标策略$\pi$的$v_\pi$或$q_\pi$。几乎所有离轨策略方法都采用了重要度采样，它是一种在给定其他分布的样本的条件下，估计另一种分布的期望值的通用方法。

状态价值函数由回报值根据其轨迹发生的概率进行加权得到，因此通过对每次采样得到的回报值，我们乘上一个该轨迹在目标策略与行动策略下出现的概率之比，在这里被称为重要度采样比，即可对根据$v_b$估计$v_\pi$。给定起始状态$S_t$，后续的状态-动作轨迹$A_t,S_{t+1},A_{t+1},\cdots,S_T$在策略$\pi$下发生的概率为：

则重要度采样比为：

环境动态特性与策略无关，因此被约去。现在根据行动策略中回报$G_t$的期望$\mathbb E[G_t|S_t=s]=v_b(s)$，我们能利用重要度采样比得到目标策略的状态价值函数：

现在我们给出利用遵循行动策略$b$的多幕采样序列来预测$v_\pi(s)$的蒙特卡洛算法。为了方便表示，我们先给出如下规定：

• 当一幕结束，新的一幕开始时，时刻不会重新从零开始，而是接续上一幕的结束继续递增，以保证所有幕中的每个时刻序号都是唯一的。
• 对于每次访问型算法，定义$\mathcal T(s)$包含所有访问过状态$s$的时刻。而首次访问型算法的$\mathcal T(s)$只包含每一幕首次访问状态$s$的时刻。
• 为了将每一幕分隔开，我们用$T(t)$表示时刻$t$所在幕的终止时刻，用$G_t$表示从时刻$t$到$T(t)$的回报值。

则每一轮采样对$v_\pi$的估计是$\rho_{t:T(t)-1}G_t$的平均。一种方法是采用简单平均的普通重要度采样：

另一种方法是采用加权平均的加权重要度采样：

普通重要度采样得到的结果是无偏的（方差的期望总是$v_\pi(s)$），但是方差一般是无界的，因为重要度采样比的方差是无界的，其估计值可能随着比例系数变得极端。而加权重要度采样的估计是有偏的，但偏差值和方差均会逐渐收敛到零，因此在实际运用中人们往往偏好加权估计，而普通重要度采样则会在后续拓展到基于函数逼近的近似方法。

增量式实现#

同轨策略和普通重要度采样的离轨策略的蒙特卡洛方法都采用了简单平均，因此仍能采用多臂赌博机一章中介绍的增量式方法，即对于旧平均值$\bar x_n$（此处下标$n$指$n$之前的平均值，与价值函数统一）和新值$x_n$，新平均值计算如下：

而对于加权重要度采样采用的加权平均，我们需要一个不同的增量式方法。对于从相同状态开始的回报序列$G_1,G_2,\cdots,G_{n-1}$及它们对应的权重$W_1,W_2,\cdots,W_{n-1}$，我们希望对如下加权平均进行估计：

为了根据新的采样值跟踪$V_n$的变化，我们还要为每个状态存储已采样回报对应的权值的累加和$C_n$。则$V_n$的更新方法为：

限于篇幅和对重点的考量，此处不作对该方法的证明。

离轨策略蒙特卡洛控制#

现在我们可以总结给出基于GPI和加权重要度采样的离轨策略蒙特卡洛控制方法的伪代码：

1. 初始化，对所有$s\in\mathcal S,a\in\mathcal A_(s)$：
   1. 任意初始化$Q(s,a)\in\mathbb R$
   2. $C(s,a)\leftarrow0$
   3. $\pi(s)\leftarrow\underset a{\mathrm{argmax}}Q(s,a)$
2. 无限循环（对每幕）：
   1. $b\leftarrow$任意软性策略
   2. 根据$b$生成一幕数据：$S_0,A_0,R_1,\cdots,S_{T-1},A_{T-1},R_T$
   3. $G\leftarrow0$
   4. $W\leftarrow1$
   5. 对幕中的每一时刻循环，$t=T-1,T-2,\cdots,0$：
      1. $G\leftarrow\gamma G+R_{t+1}$
      2. $C(S_t,A_t)\leftarrow C(S_t,A_t)+W$
      3. $Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\displaystyle\frac W{C(S_t,A_t)}[G-Q(S_t,A_t)]$
      4. $\pi(S_t)\leftarrow\underset a{\mathrm{argmax}}Q(S_t,a)$
      5. 如果$A_t\neq\pi(S_t)$，那么跳出内层循环处理下一幕数据
      6. $W\leftarrow W\displaystyle\frac1{b(A_t|S_t)}$

由于$\pi$是贪心的，因此从后往前遍历$b$采样的序列，若$b$在$S_t$随机选择的$A_t$与$\pi(S_t)$相同，则$\pi(A_t|S_t)=1$；若不同，则继续往前延伸的序列在策略$\pi$下出现的概率均为零，没有必要再遍历下去。

该方法的一个潜在问题是每次都会从幕的尾部进行学习。一方面，当出现在幕中靠后时刻状态的动作已经收敛时，仍然从尾部学习会在不必要的计算上浪费资源；另一方面，由于$b$的软性无法保证采样到与$\pi$的学习相符的动作，序列被遍历到的概率随着序列长度的延伸而减小，因此在幕中较早出现的状态会更难被学习到，极大降低了学习速度。

目前对于该问题在离轨策略蒙特卡洛方法中的严重程度尚无足够的研究和讨论，而解决该问题的一个重要方法是时序差分学习，我们将在下一章讨论。