提示：
通过换分布进行蒙特卡罗试验（采样）来实现。
求期望时“换分布”的想法及公式，有点像求对数时的“换底”

异策略蒙特卡罗强化学习算法

先看两个数学技巧：

(i) 函数的数学期望可以通过对函数的采样时行估计（这是由大数定律来保证的，参见14.6 采样：马尔可夫链蒙特卡罗MCMC方法之为何要采样？或【西瓜书第14.5.1节】），用MCMC的目的就是为了使用该技巧——应用大数定律：用【西瓜书式(14.22)】作为【西瓜书式(14.21)】的无偏估计，类似地，这里用【西瓜书式(16.23)】作为【西瓜书式(16.21)】的无偏估计、用【西瓜书式(16.24)】作为【西瓜书式(16.22)】的无偏估计。

(ii) 函数的数学期望有两种不同的等价形式，即【西瓜书式(14.21)】与【西瓜书式(14.23)】，即
$$\begin{array}{r}\underset{p}{\mathbb{E}}[f]=\underset{q}{\mathbb{E}}[\frac{p}{q}f]\end{array}\text{\hspace{1em}(16.55)}$$
对式(16.55)左右两端分别按分布$p$和分布$q$采样，再应用大数定律，则分别得到【西瓜书式(16.22)】和【西瓜书式(16.24)】。
记住：求期望时“换分布”的想法及公式，有点像求对数时的“换底”。

现在以轨线$s$作为变量，$R(s)$表示轨线上自状态$x$至结束的累积奖赏，即
$$\begin{array}{r}\{\begin{array}{ll}R(s)& =\frac{1}{T}{\sum }_{t=1}^T{r}_t^s{|}_{x_0=x,a_0=a}\text{当“T型”时}\\ R(s)& ={\sum }_{t=0}^{+\infty }{\gamma }^t{r}_t^s{|}_{x_0=x,a_0=a}\text{当“γ型”时}\end{array}\end{array}\text{\hspace{1em}(16.56)}$$
$p(s)$为策略$\pi$对应的轨线分布，由【西瓜书式(16.6)】有
$$\begin{array}{r}Q(x,a)=\underset{p}{\mathbb{E}}[R]\end{array}\text{\hspace{1em}(16.57)}$$
对式(16.57)右侧应用【西瓜书式(16.22)】得
$$\begin{array}{r}Q(x,a)=\frac{1}{m}\sum _{i=1}^{m}R(s_i)\end{array}\text{\hspace{1em}(16.58)}$$
将$R(s_i)$简记为$R_i$，即为【西瓜书式(16.25)】。

设$q(s)$为策略${\pi }^{\prime }$对应的轨线分布，取$f(s)=R(s)$，由式(16.55)、式(16.57)有
$$\begin{array}{r}Q(x,a)=\underset{q}{\mathbb{E}}[\frac{p}{q}R]\end{array}\text{\hspace{1em}(16.59)}$$
现基于$q(s)$进行采样，得$m$条轨线 { s i } i = 1 m \{s_i\}_{i=1}^m {si​}i=1m​，对式(16.57)右侧应用【西瓜书式(16.24)】得
$$\begin{array}{rl}Q(x,a)& =\frac{1}{m}\sum _{i=1}^m\frac{p(s_i)}{q(s_i)}R(s_i)\\ & =\frac{1}{m}\sum _{i=1}^m\frac{P_i^{\pi }}{P_i^{{\pi }^{\prime }}}{R}_i\end{array}\text{\hspace{1em}(16.60)}$$
基于$q(s)$进行采样得到的轨线$s_i$即为【西瓜书式(16.24)】中的$x_i^{\prime }$。

$P_i^{\pi }$与$P_i^{{\pi }^{\prime }}$为不同策略下产生轨线的概率，由16.3 有模型迭代式的详细推导图 16.5及马尔可夫链性质，$P_i^{\pi }$与$P_i^{{\pi }^{\prime }}$都为【西瓜书式(16.27)】的形式，故二者的比值为【西瓜书式(16.28)】。

比较式(16.48)与式(16.60)，式(16.48)有递推式(16.50)，故将式(16.50)中的$R_s$换为$\frac{P_i^{\pi }}{P_i^{{\pi }^{\prime }}}{R}_i$即为式(16.60)的递推式，下面讨论后者的变形。

为简便，我们以轨线$s$编号起代$s_i$，即式(16.60)变为
$$\begin{array}{r}Q(x,a)=\frac{1}{m}\sum _{s=1}^m\frac{P_s^{\pi }}{P_s^{{\pi }^{\prime }}}{R}_s\end{array}\text{\hspace{1em}(16.61)}$$
将轨线$s$截去头部$t$步后，视为一条起始点为$(x_t,a_t)$长度为$T-t$的轨线，以下标“$t+1:T$”表示（即轨线$s$上从$t+1$步到$T$步）。
$$\begin{array}{rl}{\tilde{R}}_{s,t}& ={\left[\frac{P_s^{\pi }}{P_s^{{\pi }^{\prime }}}{R}_s\right]}_{t+1:T}\\ & ={\left[\frac{P_s^{\pi }}{P_s^{{\pi }^{\prime }}}\right]}_{t+1:T}{\left[R_s\right]}_{t+1:T}\\ & ={\left[\prod _{i=0}^{T-1}\frac{\pi (x_i,a_i)}{{\pi }^{\prime }(x_i,a_i)}\right]}_{t+1:T}{\left[R_s\right]}_{t+1:T}\text{（由【西瓜书式(16.28)】）}\\ & =\prod _{i=t+1}^{T-1}\frac{\pi (x_i,a_i)}{{\pi }^{\prime }(x_i,a_i)}\left(\frac{1}{T-t}\sum _{i=t+1}^T{r}_i\right)\end{array}\text{\hspace{1em}(16.62)}$$

现在定义两个策略：

（1）$\pi$为依最大化进行改进所形成的策略，即
$$\begin{array}{r}\{\begin{array}{l}\pi (x_i)=\underset{a\in A}{\mathrm{argmax}}Q(x_i,a)\\ \pi (x_i,a_i)=\mathbb{I}(a_i=\pi (x_i))\end{array}\end{array}\text{\hspace{1em}(16.63)}$$
显然，它是一个确定性策略。
注：当式(16.63)中的最大值唯一时，动作$a_i$被$x_i$唯一确定，在实际编写程序时，应考虑多处取相同的最大值的情况，这时，式(16.63)变为
{ { a i } = arg ⁡ max ⁡ a ∈ A Q ( x i , a ) π ( x i , a i ) = 按均匀分布从集合 { a i } 中取出一个元素 \begin{align} \begin{cases} \{a_i\}=\mathop{\arg\max}\limits_{a\in A}Q(x_i,a) \\ \pi(x_i,a_i)=\text{按均匀分布从集合$\{a_i\}$中取出一个元素} \\ \end{cases} \tag{16.64} \end{align} ⎩ ⎨ ⎧​{ai​}=a∈Aargmax​Q(xi​,a)π(xi​,ai​)=按均匀分布从集合{ai​}中取出一个元素​​(16.64)​
式(16.64)仍称为确定性策略。

另外，即使所有$x$处的动作$a$是唯一确定的，从$x_0$出发的轨线也不唯一，因为还有$P_{x\to x^{\prime }}^a$使得$a\to x^{\prime }$具有随机性，参见16.3 有模型迭代式的详细推导图 16.10
。

（2）${\pi }^{\prime }$为$\pi$的$ϵ$-贪心策略，即为满足式(16.54)的${\pi }^{ϵ}$，若将${\pi }^{\prime }(x_i,a_i)$记为$p_i$，则
$$\begin{array}{r}{p}_i=\{\begin{array}{ll}1-ϵ+\frac{ϵ}{|A|}& \text{（当ai=π(xi)）}\\ \frac{ϵ}{|A|}& \text{（当ai=π(xi)）}\end{array}\end{array}\text{\hspace{1em}(16.65)}$$

将两策略代入式(16.62)，有
$$\begin{array}{rl}{\tilde{R}}_{s,t}& =\prod _{i=t+1}^{T-1}\frac{\mathbb{I}(a_i=\pi (x_i))}{p_i}\left(\frac{1}{T-t}\sum _{i=t+1}^T{r}_i\right)\end{array}\text{\hspace{1em}(16.66)}$$

对应于式(16.52)，现在，点$(x_t,a_t)$处$Q$的递推式为
$$\begin{array}{r}\{\begin{array}{l}{Q}_s(x_t,a_t)=\frac{(s-1)Q_{s-1}(x_t,a_t)+{\tilde{R}}_{s,t}}{s}\\ {\tilde{R}}_{s,t}={\prod }_{i=t+1}^{T-1}\frac{\mathbb{I}(a_i=\pi (x_i))}{p_i}\left(\frac{1}{T-t}{\sum }_{i=t+1}^T{r}_i\right)\end{array}\end{array}\text{\hspace{1em}(16.67)}$$
其中，$t=0,1,2,\cdots ,T-1$，而$Q_{s-1}(x_t,a_t)$指当前值，由此完成了轨线$s$式(16.47)上所有点的$Q$值更新。

基于上述讨论，就可以改造【西瓜书图16.10】为【西瓜书图16.11】异策略蒙特卡罗强化学习算法，要点：

(i) 用$\pi$产生${\pi }^{\prime }$，再依${\pi }^{\prime }$产生轨线$s$，由第3-4句。

(ii) 用递推式(16.67)更新轨线$s$上所有点的$Q$值（策略评估），由第5-9句实现。

(ii) 第10句对策略$\pi$的“局部”进行优化，即： 对轨线$s$上所有$x$处，根据已探索到的新$Q$值，应用式(16.63)优化策略$\pi$。

由于算法涉及两个策略：$\pi$及${\pi }^{\prime }$（$\pi$的$ϵ$-贪心策略），在策略评估时，用$ϵ$-贪心策略${\pi }^{\prime }$，在策略改进时基于原策略$\pi$，故称为“异策略”。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：16.7 同策略蒙特卡罗强化学习
下一篇：16.9 时序差分学习（Sara算法与Q-学习算法）