强化学习第五讲

• 蒙特卡洛方法
• 总结

一、蒙特卡洛方法(Monte Carlo Methods)

引入

在此之前我们讨论了基于模型的动态规划方法，现在考虑无模型的问题。
所谓无模型，其实就是状态转移概率 $P_{ss'}^a$ 未知，这种时候基于模型的动态规划方法就不好使了。拿策略迭代来说，先进行策略评估，算出当前策略对应的值函数；然后根据值函数进行策略改进。
而这里 $P_{ss'}^a$ 未知时，下面式子：(贝尔曼等式)

$v_{\pi{}}(s)=\sum_{a\in{}A}{\pi{}(a\mid{}s)\left(R_{s}^{a}+\gamma{}\sum_{s'\in{}S}{P_{ss'}^{a}v_{\pi{}}(s')}\right)}\tag{5.1}$

就不好计算，如果继续使用策略评估+策略改进的框架，需要采用其他方式来进行策略评估 (计算值函数)。

原理简析

回到最初的值函数计算式：

$v_{\pi}(s)=E_{\pi}\left[\sum_{k=0}^{\infin}\gamma^kR_{t+k+1}\mid{}S_t=s\right]\tag{5.2}$

可知实际是计算期望值，而蒙特卡洛方法 (MC方法) 就是利用随机样本计算经验平均来估计期望值。
这里提到的随机样本即指利用策略产生的很多幕数据 (episode) 。
例如采用策略 $\pi$ 进行的一个 episode 中有：$S_0,A_0,R_1,S_1,A_1,R_2,\cdots,S_{T-1},A_{T-1},R_T$，计算状态 $s$ 处的折扣回报：

$G_t(s)=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-t-1}R_{T}\tag{5.3}$

注：这里和深入浅出强化学习书中的公式有出入，我参考了Sutton的书，觉得应该是上式这个样子的

然后计算所有幕的均值即可，在给定的某一幕中，每次状态 $s$ 的出现被称为对 $s$ 的一次访问。而在同一幕中可能多次访问到 $s$ ，此时分为两种计算回报均值的方法：首次访问 MC 方法，和每次访问 MC 方法。区别也就是首次访问只算每幕中第一次访问状态 $s$ 的回报，根据大数定理，这个回报均值必然会收敛至其期望值，误差标准差以 $1/\sqrt{n}$ 衰减，$n$ 指被平均的回报值的个数。每次访问型 MC 方法则没有那么显然，但是同样会二阶收敛。
下面是采用首次访问 MC 估计值函数的伪代码：

[1] 输入：待评估的策略 $\pi$
[2] 初始化：
$\qquad\enspace$ 对所有 $s\in S$，任意初始化 $V(s)\in \R$
$\qquad\enspace$ 对所有 $s\in S$，$Returns(s)\gets$ 空列表
[3] 一直循环 (对每幕)：
$\qquad\enspace$ 根据 $\pi$ 生成一幕序列：$S_0,A_0,R_1,S_1,A_1,R_2,\cdots,S_{T-1},A_{T-1},R_T$
$\qquad\enspace$ $G\gets{0}$
$\qquad\enspace$ 对本幕中的每一步进行循环，$t=T-1,T-2\ldots,0$：
$\qquad\enspace\qquad$ $G\gets{\gamma{G}+R_{t+1}}$
$\qquad\enspace\qquad$ 除非 $S_t$ 在 $S_0,S_1,\ldots,S_t-1$ 中已出现过：
$\qquad\enspace\qquad\qquad$ 将 $G$ 加入 $Returns(S_t)$
$\qquad\enspace\qquad\qquad$ $V(S_t)\gets{average(Returns(S_t))}$

注意：计算回报的顺序是从 $T-1$ 到 $0$
蒙特卡洛算法的一个重要的事实是：对于每个状态的估计是独立的。它对于一个状态的估计完全不依赖于对其他状态的估计，这与 DP 完全不同。也即，MC 方法没有用到自举思想。

蒙特卡洛控制 ( MCES )

在得到值函数后，进一步的问题就是提升策略，依然采用贪心的思想：

$\pi_{l+1}(s)\in{\underset{a}{\argmax{}}q^{\pi{}_{l}}(s,a)}\tag{5.4}$

而在 MC 策略迭代中，逐幕交替的进行评估和改进。每一幕结束后，使用观测到的回报进行策略评估，然后在该幕序列访问到的每一个状态上进行策略的改进。这样被称作基于试探性出发的蒙特卡洛 (蒙特卡洛 ES) ，具体算法也就是在上述评估算法中计算 $S_t,A_t$ 二元组对应的 $Q(S_T,A_T)$ 函数然后选最好的动作作为策略即可。
但是我们如何能够遍历所有可能的状态 - 动作呢，这里就有两种方法进行保证。

同轨策略算法 ( on - policy )

同轨策略中用于生成采样数据序列的策略和用于实际决策的待评估和改进的策略是相同的。而又为了同时保证前文所述的遍历，那么这个策略一般采用 “软性” 的策略，即对于任意的 $s\in S$ 以及 $a\in A(s)$ 都有 $\pi(a\mid{}s)>0$，但它们会逐渐地逼近一个确定性的策略。(每次都更新这个软性策略，注意平分的情况！)
这样的策略叫做 $\varepsilon-soft$ 策略：

$\pi\left(a\mid{} s\right)= \begin{cases} 1-\varepsilon{}+\frac{\varepsilon{}}{\mid{} A(s)\mid{}} & if\ a=\underset{A}{\argmax{}} Q\left(a\mid s\right) \\ \frac{\varepsilon{}}{\mid{} A(s)\mid{}} & if\ a\neq{} \underset{A}{\argmax{}} Q\left(a\mid{} s\right) \end{cases}\tag{5.5}$

伪代码：

[1] 初始化，对所有 $s\in S$，$a\in A(s)$
$\qquad\enspace$ $Q(s,a)\in{\R}$ (任意值)
$\qquad\enspace$ $\pi(s)\gets$ 任意软性策略$(e.g.\enspace\varepsilon-greedy)$
[2] 一直循环 (对每幕)：
$\qquad\enspace$ 根据 $\pi$ 生成一幕数据：$S_0,A_0,R_1,S_1,A_1,R_2,\cdots,S_{T-1},A_{T-1},R_T$
$\qquad\enspace$ $G\gets{0}$
$\qquad\enspace$ 对本幕中的每一时刻进行循环，$t=T-1,T-2,\ldots,0$：
$\qquad\enspace\qquad$ $G\gets{\gamma{G}+R_{t+1}}$
$\qquad\enspace\qquad$ $C(S_t,A_t)\gets C(S_t,A_t)+1$
$\qquad\enspace\qquad$ $Q(S_t,A_t)\gets Q(S_t,A_t)+\frac{1}{C(S_t,A_t)}[\,G-Q(S_t,A_t)\,]$
$\qquad\enspace$ $\varepsilon \gets \frac{1}{T}$
$\qquad\enspace$ $\pi \gets \varepsilon-greedy(Q)$

离轨策略算法 (off - policy)

前面提到的同轨策略实际是一种妥协，因为它所学习到的并不是最优策略的动作值，而是学习一个接近最优而且仍能够试探的策略的动作值。
所以这里可以采取另一种思路，即采用两种策略，一种用于学习并最终成为最优策略，称为目标策略，用 $\pi\,(a\mid s)$ 表示；另一个更具有试探性，用于产生行动样本，用 $b\,(a\mid s)$ 表示，称为行动策略。且需要满足条件：对 $\forall\, \pi\,(a\mid s)>0$，满足 $b\,(a\mid s)>0$，称为覆盖假设。
而绝大部分离轨策略方法都采用了重要度采样，重要度采样是一种在给定来自其它分布的样本的条件下，估计某种分布的期望值的通用方法。而这里应用的具体表现是，对回报值根据其轨迹在目标策略与行动策略中出现的相对概率进行加权，这个相对概率也被称为重要度采样比，具体可用如下公式表示：

$\rho_{t:T-1}=\frac{\prod_{k=t}^{T-1}\pi\,(A_k\mid S_k)p(S_k+1\mid S_k,A_k)}{\prod_{k=t}^{T-1}b\,(A_k\mid S_k)p(S_k+1\mid S_k,A_k)}=\prod_{k=t}^{T-1}\frac{\pi\,(A_k\mid S_k)}{b\,(A_k\mid S_k)}\tag{5.6}$

这里的 $p$ 代表状态转移概率，虽然是未知的，但是由于对两种策略的 $p$ 是相等的，即可约分，所以只与策略和样本序列数据有关。而使用的方法也有两种，首先我们定义，对于每次访问型方法，所有访问过状态 $s$ 的时刻 (帧数) 集合为 $\tau(s)$；对于首次访问型方法，每幕的首次访问状态 $s$ 的时刻 (帧数) 集合为 $\tau(s)$。然后用 $T{(t)}$ 表示在时刻 $t$ 后的首次终止，用 $G_t$ 表示在 $t$ 后到达 $T{(t)}$ 时的回报值。
有：

$V(s)=\frac{\sum_{t\in{\tau(s)}}\rho_{t:T(t)-1}G_t}{|\tau(s)|}\tag{5.7}$

上式方法计算值函数被称为普通重要度采样。
另有：

$V(s)=\frac{\sum_{t\in{\tau(s)}}\rho_{t:T(t)-1}G_t}{\sum_{t\in{\tau(s)}}\rho_{t:T(t)-1}}\tag{5.8}$

上式被称为加权重要度采样。(如果分母为0时，该式值也定义为0)

一些比较：在统计学意义上，采用式 $(5.7)$ 得到的结果是无偏的，但是会出现极端的情况，也就是比例系数非常大，这将导致其方差会很大 (无界的)，而在加权估计中任何回报的最大权值都是1。但是两种的方差都能收敛到0，实际应用中偏好用加权估计，因为其方差很小。

增量式实现

针对加权重要度采样的离轨策略算法，下面介绍使用增量式算法实现对回报加权平均的计算方法。
假设有一个回报序列 $G_1,G_2,\ldots,G_{n-1}$，它们都从相同的状态开始，且每一个回报都对应一个随机权重 $W_i$ (例如 $W_i=\rho_{t:T(t)-1}$)。那么我们可以为每一个状态维护前 $n$ 个回报对应的全职的累加和 $C_n$。则有：

$V_{n+1}=V_n+\frac{W_n}{C_n}[\,G_n-V_n\,]\tag{5.9}$

以及

$C_{n+1}=C_{n}+W_{n+1}\tag{5.9}$

这里 $C_0=0$
于是我们可以得到一个伪代码：

[1] 初始化，对所有 $s\in S$，$a\in A(s)$
$\qquad\enspace$ $Q(s,a)\in{\R}$ (任意值)
$\qquad\enspace$ $C(s,a)\gets 0$
$\qquad\enspace$ $\pi(s) \gets \argmax_a{Q(s,a)}$
[2] 一直循环 (对每幕)：
$\qquad\enspace$ $b\gets$ 任意软性策略
$\qquad\enspace$ 根据 $b$ 生成一幕数据：$S_0,A_0,R_1,S_1,A_1,R_2,\cdots,S_{T-1},A_{T-1},R_T$
$\qquad\enspace$ $G\gets{0}$
$\qquad\enspace$ $W\gets{1}$
$\qquad\enspace$ 对本幕中的每一时刻进行循环，$t=T-1,T-2,\ldots,0$：
$\qquad\enspace\qquad$ $G\gets{\gamma{G}+R_{t+1}}$
$\qquad\enspace\qquad$ $C(S_t,A_t) \gets C(S_t,A_t)+W$
$\qquad\enspace\qquad$ $Q(S_t,A_t) \gets Q(S_t,A_t)+\frac{W}{C(S_t,A_t)}[\,G-Q(S_t,A_t)\,]$
$\qquad\enspace\qquad$ $\pi(S_t) \gets \argmax_a{Q(S_t,a)}$ (平分的情况选取方法应保持一致)
$\qquad\enspace\qquad$ 如果 $A_t \neq \pi(S_t)$ 则退出内层循环
$\qquad\enspace\qquad$ $W \gets W\frac{1}{b(A_t\mid S_t)}$

注：这里不使用 $\frac{\pi\,(A_k \mid S_k)}{b\,(A_k\mid S_k)}$，而为1是因为 $\pi$ 是贪心策略，满足 $\pi(a\mid s)=1$

折扣敏感的重要度采样

这里我们考虑一种情况，即幕很长且 $\gamma$较小时，那么在进行普通重要度采样时，后面时刻的比例因数虽不会改变预期的更新，但是会显著的使方差变大，(人话就是 $\gamma$ 很小后面的重要度采样比没有卵用但是会把采样估计的方差给变大，这就是导致普通重要度采样方差很大的一个原因)，为了解决这个问题，我们考虑把 $\gamma$ 视作是幕终止的概率，或者叫做部分终止的程度，可以理解为有 $\gamma$ 的概率本幕在这个时刻终止，而从开始到这个时刻的回报和称为平价部分回报，用 $\overline{G}$ 表示；有 $1-\gamma$ 的概率跳转到下一状态，那么可以将总回报 $G_t$ 看做是上述平价部分回报的总和：(可以看出来乘法原理的亚子)

$\begin{aligned} G_t & = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-t-1}R_T\\ & = (1-\gamma)R_{t+1}\\ & \quad+(1-\gamma)\gamma(R_{t+1}+R_{t+2})\\ & \quad+(1-\gamma)\gamma^2(R_{t+1}+R_{t+2}+R_{t+3})\\ & \quad \enspace \vdots \\ & \quad+(1-\gamma)\gamma^{T-t-2}(R_{t+1}+R_{t+2}+\cdots+R_{T-1})\\ & \quad+\gamma^{T-t-1}(R_{t+1}+R_{t+2}+\cdots+R_T)\\ & =(1-\gamma)\sum_{h=t+1}^{T-1}\gamma^{h-t-1}\overline{G}_{t:h}+\gamma^{T-t-1}\overline{G}_{t:T}\tag{5.10} \end{aligned}$

由此我们得到一个新的普通重要度采样器，它是式 $(5.7)$ 的推广：

$\footnotesize V(s)=\frac{\sum_{t\in{\tau(s)}}\left((1-\gamma)\sum_{h=t+1}^{T(t)-1}\gamma^{h-t-1}\rho_{t:h-1}\overline{G}_{t:h}+\gamma^{T(t)-t-1}\rho_{t:T(t)-1}\overline{G}_{t:T(t)}\right)}{|\tau(s)|}\tag{5.11}$

同理有加权重要度采样的推广：

$\footnotesize V(s)=\frac{\sum_{t\in{\tau(s)}}\left((1-\gamma)\sum_{h=t+1}^{T(t)-1}\gamma^{h-t-1}\rho_{t:h-1}\overline{G}_{t:h}+\gamma^{T(t)-t-1}\rho_{t:T(t)-1}\overline{G}_{t:T(t)}\right)}{\sum_{t\in{\tau(s)}}\left((1-\gamma)\sum_{h=t+1}^{T(t)-1}\gamma^{h-t-1}\rho_{t:h-1}+\gamma^{T(t)-t-1}\rho_{t:T(t)-1}\right)}\tag{5.12}$

总结

• 大概理论就是这个亚子，也找不到什么可以简化的感觉，基本就是照着书念了一遍，但是也让我有了一定的理解，还是结合代码更清楚一点，下周又有作业，希望不要搞太久，不得不说 github 真是好东西，直接搜 Reinforcement 就有大把的资料，虽然肯定是英文的就对了。。。要准备一些物理考试了，溜。
• 另外一提，间谍过家家好看！快给我更😍