第5章 蒙特卡洛法
动态规划法属于基于模型的MDP问题求解方法。在环境模型已知的情况下，动态规划法不需要对环境采样，只需要通过迭代计算，就可以得到问题的最优策略。然而在实际任务中，完整的环境模型通常是难以获取的。无模型的强化学习，状态转移概率是未知的，也就是说无模型强化学习无法利用动态规划方法来求解值函数。不妨尝试通过值函数的原始定义来求解无模型强化学习问题：
vπ(s)=Eπ(Gt|St=s)
qπ(s,a)=Eπ(Gt|St=s,At=a)
本章将主要介绍如何利用蒙特卡洛法(Monte Carlo，MC)来求解无模型强化学习问题，以GPI来保证其最优性。这里首先考虑预测问题中的策略评估，然后再考虑控制问题中的策略改进。
在线视频19
5.1蒙特卡洛法的基本概念
在实际问题中，通常不易获得完整的环境知识。例如在21点游戏中，只根据玩家已知的牌面，无法直接获得状态转移概率。相对而言，采样数据则更容易获得。例如可以多次进行游戏对弈，然后估计专家的叫牌和停牌套路，计算出最优的游戏策略。这种基于统计学的思想，通过大量采样获取数据来进行学习的方法称为经验方法。MC正是基于经验方法，在环境模型未知的情况下，采用时间步有限的、完整的情节，根据经验进行学习，并通过平均采样回报来解决强化学习问题。
5.1.1MC的核心要素
(1) 经验(experience)： 经验是从环境交互中获得的(s,a,r)序列，它是情节的集合，也就是样本集。经验既可以是真实经验(real experience)，也可以是模拟经验(simulator experience)。其中模拟经验是通过模拟模型(simulated model)得到的，这里的模拟模型只需要生成状态转移的一些样本，不需要像DP那样需要环境中所有可能的状态转移概率。
(2) 情节(episode)： 一段经验可以分为多个情节，每一情节都是一个完整的(s,a,r)序列，即必有终止状态，形如s0,a0,r1,…,sT-1,aT-1,rT,sT。经常与情节混淆的概念是轨迹(trajectory)，轨迹可以没有终止状态，形如s0,a0,r1,s1,a1,r2,…。所以通常情况下，可以认为：
序列情节经验(轨迹)
(3) 完整回报(full return)与目标值： 因为只有到达终止状态才能计算回报，所以将情节的回报Gt称为完整回报。此外，Gt也称为MC的目标值。
5.1.2MC的特点
(1) 不需要知道状态转移概率p，直接从环境中进行采样来处理无模型任务。
(2) 利用情节进行学习，并采用情节到情节(episodebyepisode)的离线学习(offline)方式来求解最优策略π*。与之相对的，DP和后续介绍的时序差分算法则采用步到步(stepbystep)的在线学习(online)方式来求解最优策略。
离线学习： 先完整地采集数据，然后以离线方式优化学习目标。
在线学习： 边采集数据边优化学习目标。
(3) MC是一个非平稳问题，其表现在： 某个状态采取动作之后的回报，取决于在同一个情节内后续状态所采取的动作，而这些动作通常是不确定的。如果说DP是在MDP模型中计算值函数，那么MC就是学习值函数。
(4) 在MC中，对每个状态值函数的估计都是独立的。也就是说，对状态的值函数估计不依赖于其他任何状态，这也说明了MC不是自举过程。
(5) MC在估计每个状态的值函数时，其计算成本与状态总数无关，因为它只需要计算指定状态的回报，不需要考虑所有的状态。
实际上，MC泛指任何包含大量随机成分的估计方法，通常利用采样数据来估算某一事件的发生概率。在数学领域中，它的应用可以用例5.1来说明。
例5.1在边长为1米的正方形S1内构建一个扇形S2，如图5.1所示。利用扇形面积计算公式，可以计
图5.1用MC方法计算扇形面积(见彩插)
算出S2=14πr2≈14×3.14×12=0.785。现在利用MC方法计算S2的面积。均匀地向S1内撒n个黄豆，经统计得知有m个黄豆在S2内部，那么有S2S1≈mn，即S2≈mnS1，且n越大，计算得到的面积越精确。
在程序中分别设置n=100、10000和1000000共3组数据，统计结果如表5.1所示。
表5.1MC方法计算扇形面积结果统计表
n
S1
S2
m
mn
100
1.0
0.785
79
0.79
10000
1.0
0.785
7839
0.7839
1000000
1.0
0.785
786018
0.786018
由实验数据可知，当n值越大时，得到的扇形面积越精确，即接近0.785。
由此获得的MC采样公式为
Ex~p［f(x)］=∑xp(x)f(x)≈1N∑Nxi~p,i=1f(xi)(5.1)
在线视频20
5.2蒙特卡洛预测
根据状态值函数的初始定义，MC预测算法以情节中初始状态s的回报期望作为其值函数vπ(s)的估计值，对策略π进行评估。在求解状态s的值函数时，先利用策略π产生n个情节s0,a0,r1,…,sT-1,aT-1,rT,sT，然后计算每个情节中状态s的折扣回报：
G(i)t=rt+1+γrt+2+…+γT-t-1rT
这里，G(i)t表示在第i个情节中，从t时刻到终点时刻T的回报。该回报是基于某一策略下的状态值函数的无偏估计(由于Gt是真实获得的，所以属于无偏估计，但是存在高方差)。
在MC中，每个回报都是对vπ(s)独立同分布的估计，通过对这些折扣回报求期望(均值)来评估策略π为
vπ(s)=Eπ(Gt|s∈S)=average(G(1)t+G(2)t+…+G(i)t+…+G(n)t|s∈S)
在一组采样(一个情节)中状态s可能多次出现，以更新图的方式表示，如图5.2所示。对同一情节中重复出现的状态s，有如下两种处理方法。
图5.2在情节中状态s的出现情况(MC更新图)（见彩插）
(1) 首次访问(firstvisit)： 在对状态s的回报vπ(s)进行估计时，只对每个情节中第1次访问到状态s的回报值作以统计：
V(s)=G(1)(1)t(s)+G(2)(1)t(s)+…+G(i)(1)t(s)i(5.2)
(2) 每次访问(everyvisit)： 在对状态s的回报vπ(s)进行估计时，对所有访问到状态s的回报值都作以统计：
V(s)=G(1)(1)t(s)+G(1)(2)t(s)+…+G(2)(1)t(s)+…+G(i)(1)t(s)+…+G(i)(j)t(s)N(s)
(5.3)
其中，i表示第i个情节; j表示第j次访问到状态s； N(s)表示状态s被访问过的总次数。根据大数定理，当MC采集的样本足够多时，计算出来的状态值函数估计值Vπ(s)就会逼近真实状态值函数vπ(s)。
从图5.2中可以看出，MC更新图只显示在当前情节中，采样得到的状态转移，且包含了到该情节结束为止的所有状态转移； 而DP更新图显示在当前状态下所有可能的状态转移，且仅包含单步转移。
基于首次访问的MC预测算法，如算法5.1所示。
算法5.1基于首次访问的MC预测算法
输入： 待评估的随机策略π(a|s)
初始化：
1.对所有s∈S，初始化V(s)∈R，V(sT)=0； 状态s被统计的次数count(s)=0
2. repeat 对每一个情节k=0,1,2,…
3.根据策略π(a|s)，生成一个情节序列S0,A0,R1,…,ST-1,AT-1,RT,ST
4.G←0
5.for 本情节中的每一步t=T-1downto0 do
6.G←γG+Rt+1
7.if St{S0,S1,…,St-1} then
8.count(St)←count(St)+1
9.V(St)←V(St)+1count(St)(G-V(St))
10. end if
11. end for
输出： vπ=V
例5.2以例3.1扫地机器人为例。给出机器人经过图5.3的每条轨迹后，相对应的状态值。
图5.3经过状态16的其中5个情节（见彩插）
如图5.3所示，选取了5个经过状态16的情节，5个情节依次设置为情节1、情节2、情节3、情节4和情节5。
情节1： 16→15→10→5→0
G(1)(1)16=0+0.8×(0+0.8×(0+0.8×(1+0.8×0)))=0.83×1=0.512
情节2： 16→17→17→18→19
G(2)(1)16=0+0.8×(-10+0.8×(0+0.8×(3+0.8×0)))
=0.8×(-10)+0.83×3=-6.464
情节3： 16→11→6→7→8→9→14→19
G(3)(1)16=0+0.8×(0+0.8×(0+0.8×(0+0.8×(0+0.8×
(0+0.8×(3+0.8×0))))))=0.86×3≈0.786
也可以直接利用关于回报的定义计算：
G(3)(1)16=0+0.8×0+0.82×0+0.83×0+0.84×0+0.85×0+0.86×3
=0.86×3≈0.786
情节4： 16→11→6→7→8→13→18→19
G(4)(1)16=0+0.8×(0+0.8×(0+0.8×(0+0.8×(0+0.8×
(0+0.8×(3+0.8×0))))))=0.86×3≈0.786
情节5： 首次访问状态16： 16→11→6→7→8→13→18→17→16→15→10→5→0
G(5)(1)16=0+0.8×(0+0.8×(0+0.8×(0+0.8×(0+0.8×(0+0.8×(0+0.8×
(0+0.8×(0+0.8×(0+0.8×(0+0.8×(1+0.8×0)))))))))))
=0.811×1≈0.086
第2次访问状态16： 16→15→10→5→0
G(5)(2)16=0+0.8×(0+0.8×(0+0.8×(1+0.8×0)))=0.83×1=0.512
在情节5中状态16被访问了两次。利用首次访问的MC预测方法时，计算累计回报值只使用该情节中第一次访问状态16的回报，即G(5)(1)16。所以使用这5条情节，利用首次访问方式计算状态16的估计值为V(S16)=(G(1)(1)16+G(2)(1)16+G(3)(1)16+G(4)(1)16+G(5)(1)16)/5=-0.859； 而利用每次访问方式计算状态16的估计值为V(S16)=(G(1)(1)16+G(2)(1)16+G(3)(1)16+G(4)(1)16+G(5)(1)16+G(5)(2)16)/6=-0.630。
在线视频21
5.3蒙特卡洛评估
由最优策略的两种求解方式可知，利用动作值函数更适合于无模型求解最优策略。于是将估计状态值函数的MC预测问题转化为估计动作值函数的MC评估问题，也就是说，对状态动作对(s,a)进行访问而不是对状态s进行访问。根据策略π进行采样，记录情节中(s,a)的回报Gt，并对(s,a)的回报求期望，得到策略π下的动作值函数qπ(s,a)的估计值。同样地，MC评估方法对每一组状态动作对(s,a)的评估方法也分为首次访问和每次访问两种。
为了保证算法中值函数和策略的收敛性，DP算法会对所有状态进行逐个扫描。在MC评估方法中，根据动作值函数计算的性质，必须保证每组状态动作对(s,a)都能被访问到，即得到所有(s,a)的回报值，才能保证样本的完备性。针对该问题，我们设定探索始点(exploring starts)： 每一组(s,a)都有非0的概率作为情节的起始点(s0,a0)。
实际上，探索始点在实际应用中是难以达成的，需要配合无限采样才能保证样本的完整性。通常的做法是采用那些在每个状态下所有动作都有非0概率被选中的随机策略。这里我们先从简单的满足探索始点的MC控制算法开始讨论，然后引出基于同策略和异策略方法的MC控制算法。
5.4蒙特卡洛控制
预测和控制的思想是相同的，它们都是基于带奖赏过程的马尔可夫链来对目标进行更新，其区别在于以下两点。
(1) MC预测： 求解在给定策略π下，状态s的状态值函数vπ(s)。
(2) MC控制： 基于GPI，包含策略评估和策略改进两部分。这里的策略评估是求解在给定策略π下，状态动作对(s,a)的动作值函数qπ(s,a)。其策略迭代过程为
π0Eqπ0Iπ1Eqπ1I…Iπ*Eq*
5.4.1基于探索始点的蒙特卡洛控制
当采样过程满足探索始点时，对任意策略πk，MC算法都可以准确地计算出指定状态动作对的值函数qπk(s,a)。一旦得到了动作值函数，可以直接利用基于动作值函数的贪心策略来对策略进行更新。此时对于所有s∈S，任意策略πk以及更新后的πk+1都将满足策略改进原理：
qπk［s,πk+1(s)］=qπk［s,argmaxa qπk(s,a)］——根据πk+1(s)= argmaxa qπk(s,a)
= maxa qπk(s,a)——将最优策略提到公式外面
≥qπk［s,πk(s)］——使用上一个策略的动作值函数
≥vπk(s)(5.4)
式(5.4)表明，采用基于动作值函数的贪心策略，改进后的策略πk+1一定优于或等价于πk。这一过程保证了MC控制算法能够收敛到最优动作值函数和最优策略。
对于5.3节介绍的无穷采样假设，由于在实际环境中无法实现这一条件，我们使用基于探索始点的蒙特卡洛(Monte Carlo based on Exploring Starts，MCES)控制算法来进行规避。MCES控制算法通过情节到情节的方式对策略进行评估和更新，每一情节结束后，使用观测到的回报进行策略评估，然后在该情节访问到的每一个状态上进行策略改进。
MC控制算法主要分为以下两个阶段。
(1) 策略评估： 根据当前策略π进行采样，得到一条完整情节，估计每一组(s,a)的动作值函数。
(2) 策略改进： 基于动作值函数qπ(s,a)，直接利用贪心策略对策略进行改进。
算法5.2给出了MCES控制算法。
算法5.2MCES控制算法
输入： 待评估的确定策略π(s)
初始化：
1.对所有s∈S+，a∈A(s)，初始化Q(s,a)∈R，Q(sT,a)=0
2.对所有s∈S+，a∈A(s)，状态动作对(s,a)被统计的次数count(s,a)=0
3.repeat 对每一个情节k=0,1,2,…
4.以非0概率随机选取初始状态动作对(S0,A0)
5.根据策略π(s)，从初始状态动作对(S0,A0)开始，生成一个情节序列：
S0,A0,R1,…,ST-1,AT-1,RT,ST
6.G←0
7. for 本情节中的每一步t=T-1downto0 do
8.G←γG+Rt+1
9.if St,At{S0,A0,S1,A1,…,St-1,At-1} then
10. count(St,At)←count(St,At)+1
11. Q(St,At)←Q(St,At)+1count(St,At)［G-Q(St,At)］
12. end if
13. π(St)←argmaxa Q(St,a)
14.end for
输出： π*=π
在算法5.2中，Q(s,a)的初始值一般设置为0。若使用非0初始化，则可以通过Q［s］［a］=random()/10来控制。Q(s,a)表示动作值函数估计值，所以使用大写Q表示。在程序中，常以defalutdict()声明未定型字典Q(s,a)，其参数可表示为{s:(action1_value,action2_value),…}形式，并通过Q［s］［a］来调用(s,a)的动作值函数。
虽然可以通过探索始点来弥补无法访问到所有状态动作对的缺陷，但这一方法并不合理，普遍的解决方法就是保证Agent能够持续不断地选择所有可能的动作，这也称为无探索始点方法，该方法分为同策略方法与异策略方法两种。
在线视频22
5.4.2同策略蒙特卡洛控制
在同策略MC控制算法中，策略通常是软性的(soft)，即对于所有的s∈S、a∈A(s)，均有π(a|s)>0。但策略都必须逐渐变得贪心，以逐渐逼近一个确定性策略。同策略方法使用ε贪心策略(εgreedy policy)，其公式为
π(a|s)←1-ε+εA(s)当a=A*时，以概率1-ε+εA(s)
选择具有最大价值的动作
εA(s)当a≠A*时，以概率εA(s)随机选择动作(5.5)
其中，A(s)表示状态s的动作空间;A(s)表示状态s可采取的动作总数； A*表示最优动作。
GPI并没有要求必须使用贪心策略，只要求采用的优化方法逐渐逼近贪心策略即可。根据策略改进定理，对于一个ε软性策略π，任何根据qπ生成的ε贪心策略都是对其所做的改进。下面对ε软性策略改进定理进行证明。
假设π′为εgreedy策略，对任意状态s∈S有
qπ［s,π′(s)］=∑aπ′(a|s)qπ(s,a)
=ε|A(s)|∑aqπ(s,a)+(1-ε)maxa qπ(s,a)
≥ε|A(s)|∑aqπ(s,a)+(1-ε)∑aπ(a|s)-ε|A(s)|1-εqπ(s,a)
=ε|A(s)|∑aqπ(s,a)-ε|A(s)|∑aqπ(s,a)+∑aπ(a|s)qπ(s,a)
=vπ(s)（5.6）
所以，根据策略改进定理，π′≥π。
基于同策略首次访问εgreedy策略的MC算法，如算法5.3所示。
算法5.3基于同策略首次访问εgreedy策略的MC算法
输入： 待评估的εgreedy策略π(a|s)
初始化：
1.对所有s∈S+，a∈A(s)，初始化Q(s,a)∈R，Q(sT,a)=0
2.对所有s∈S+，a∈A(s)，状态动作对(s,a)被统计的次数count(s,a)=0
3.ε←(0,1)为一个逐步递减的较小的实数
4. repeat 对每一个情节k=0,1,2,…
5.根据策略π(a|s)，生成一个情节序列S0,A0,R1,…,ST-1,AT-1,RT,ST
6.G←0
7.for 本情节中的每一步t=T-1downto0 do
8.G←γG+Rt+1
9.if St,At{S0,A0,S1,A1,…,St-1,At-1} then
10. count(St,At)←count(St,At)+1
11. Q(St,At)←Q(St,At)+1count(St,At)［G-Q(St,At)］
12. A*←argmaxa Q(St,a)
13. for a∈A(St) do
14. if a==A* then
15. π(a|St)←1-ε+εA(St)
16. else
17. π(a|St)←εA(St)
18. end if
19. end for
20. end if
21.end for
输出： q*=Q； π*=π
在算法5.3中，基于动作值函数Q的ε贪心策略，对于贪心动作给予π(a|St)←1-ε+εA(St)的概率，其他动作给予π(a|St)←εA(St)概率。
阅读代码14
例5.3利用同策略首次访问ε贪心策略MC算法，给出扫地机器人的最优策略。扫地机器人通过多次实验，不断地更新Q值，最终收敛到最优策略，并得到一条回报最大的路径。同策略蒙特卡洛首次访问控制算法中，对动作值函数Q的计算，也是通过对每一情节中第一次访问到的该状态动作对的回报进行平均，然后选择使该动作值函数Q最大的动作，作为该状态下应该采取的动作。表5.2给出5个代表性状态，基于同策略首次访问MC算法的扫地机器人最优策略的求解过程。
在线表格07
表5.2基于同策略首次访问MC算法的扫地机器人最优策略计算过程（ε0=0.1）
S5
…
S10
…
S18
…
S20
…
S24
Q0
0.000;0.000;
*.***;0.000
…
0.000;0.000;
*.***;0.000
…
0.000;0.000;
0.000;0.000
…
*.***;0.000;
*.***;0.000
…
*.***;0.000;
0.000;*.***
π0
0.667;0.167;
0.000;0.167
…
0.667;0.167;
0.000;0.167
…
0.625;0.125;
0.125;0.125
…
0.000;0.750;
0.000;0.250
…
0.000;0.750;
0.250;0.000
A0
1;0;0;0
…
0;1;0;0
…
1;0;0;0
…
0;1;0;0
…
0;1;0;0
Q1
0.000;0.000;
*.***;0.000
…
0.000;0.000;
*.***;0.000
…
-5.120;0.000;
0.000;3.000
…
*.***;-0.269;
*.***;-1.605
…
*.***;0.000;
0.000;*.***
π1
0.667;0.167;
0.000;0.167
…
0.667;0.167;
0.000;0.167
…
0.125;0.125;
0.125;0.625
…
0.000;0.750;
0.000;0.250
…
0.000;0.750;
0.250;0.000
A1
1;0;0;0
…
1;0;0;0
…
0;0;0;1
…
0;1;0;0
…
0;1;0;0
︙
︙
︙
︙
︙
︙
︙
︙
︙
︙
Q7500
0.391;1.000;
*.***;0.368
…
0.326;0.641;
*.***;-0.546
…
1.530;0.667;
0.265;3.000
…
*.***;0.396;
*.***;0.710
…
*.***;3.000;
1.605;*.***
π7500
0.104;0.792;
0.000;0.104
…
0.104;0.792;
0.000;0.104
…
0.078;0.078;
0.078;0.766
…
0.000;0.156;
0.000;0.843
…
0.000;0.843;
0.156;0.000
A7500
0;1;0;0
…
0;0;0;1
…
0;0;0;1
…
0;0;0;1
…
0;1;0;0
︙
︙
︙
︙
︙
︙
︙
︙
︙
︙
续表
S5
…
S10
…
S18
…
S20
…
S24
Q12500
0.402;1.000;
*.***;0.379
…
0.342;0.661;
*.***;-0.575
…
1.580;0.756;
0.486;3.000
…
*.***;0.436;
*.***;0.808
…
*.***;3.000;
1.646;*.***
π12500
0.062;0.875;
0.000;0.062
…
0.062;0.875;
0.000;0.062
…
0.047;0.047;
0.047;0.859
…
0.000;0.094;
0.000;0.906
…
0.000;0.906;
0.094;0.000
A12500
0;1;0;0
…
0;0;0;1
…
0;0;0;1
…
0;1;0;0
…
0;1;0;0
︙
︙
︙
︙
︙
︙
︙
︙
︙
︙
Q19999
0.405;1.000;
*.***;0.382
…
0.342;0.668;
*.***;-0.565
…
1.590;0.752;
0.553;3.000
…
*.***;0.469;
*.***;0.935
…
*.***;3.000;
1.680;*.***
π19999
0.000;1.000;
0.000;0.000
…
0.000;1.000;
0.000;0.000
…
0.000;0.000;
0.000;1.000
…
0.000;0.000;
0.000;1.000
…
0.000;1.000;
0.000;0.000
A19999
0;1;0;0
…
0;1;0;0
…
0;0;0;1
…
0;0;0;1
…
0;1;0;0
︙
︙
︙
︙
︙
︙
︙
︙
︙
︙
Q20000
0.405;1.000;
*.***;0.382
…
0.342;0.668;
*.***;-0.565
…
1.590;0.752;
0.553;3.000
…
*.***;0.469;
*.***;0.935
…
*.***;3.000;
1.680;*.***
π20000
0.000;1.000;
0.000;0.000
…
0.000;1.000;
0.000;0.000
…
0.000;0.000;
0.000;1.000
…
0.000;0.000;
0.000;1.000
…
0.000;1.000;
0.000;0.000
A20000
0;1;0;0
…
0;1;0;0
…
0;0;0;1
…
0;0;0;1
…
0;1;0;0
π*
0;1;0;0
…
0;1;0;0
…
0;0;0;1
…
0;0;0;1
…
0;1;0;0
另外，常用ε柔性策略公式还有以下4种。
(1) 随机贪心策略。基于随机数，用一个较小的阈值ε来控制策略的探索性：
π(a|St)←A*,rand()>ε
rand(A),rand()≤ε（5.7）
当随机数大于ε时，选择最大动作值函数对应的动作； 当随机数小于或等于ε时，随机地选择动作rand(A)。
(2) 玻耳兹曼探索。定义t时刻选择动作At的概率，其公式为
π(At|St)=eQt(st,At)/τt∑aeQt(st,a)/τt（5.8）
其中，τt≥0表示温度参数，控制探索的随机性。当τt→0时，选择贪心动作； 当τt→∞时，随机选择动作。
(3) 最大置信上界法。虽然贪心策略选取的动作在当前时刻看起来是最好的，但实际上其他一些没有选取到的动作可能从长远看更好。在这些动作中，通常是根据它们的潜力来选择可能最优的动作，因此在选择动作时，一方面要考虑其估计值最大，另一方面也要考虑探索长时间没有访问到的动作，以免错过更好的动作。一个有效的方法是按照以下公式来选择动作：
At= argmaxa Qt(s,a)+clntNt(s,a)（5.9）
其中，lnt表示t的自然对数; Nt(s,a)表示当前状态s; 在时刻t之前动作a被选择的次数; c是一个大于0的数，用来控制探索的程度。如果Nt(s,a)=0，则动作a就被认为是当前状态s下满足最大化条件的动作。
(4) 乐观初始值方法。给值函数赋予一个比实际价值大得多些的乐观初始值。这种乐观估计会鼓励不断地选取收益接近估计值的动作。但无论选取哪一种动作，收益都比最初始的估计值小，因此在估计值收敛之前，所有动作都会被多次尝试。即使每一次都按照贪心法选择动作，系统也会进行大量的探索。
在线视频23
5.4.3异策略与重要性采样
另一种常用的无探索始点蒙特卡洛方法为异策略MC方法。在介绍异策略方法之前，我们先来了解重要性采样，因为几乎所有的异策略方法都使用到重要性采样。所谓的重要性采样是利用来自其他分布的样本，估计当前某种分布期望值的通用方法。在引出异策略MC控制之前，首先阐述预测问题的重要性采样(importance sampling)。
1. 重要性采样
以离散型数据为例，假设f(x)是一个服从p(x)分布的函数，其期望公式为
Ex~p［f(x)］=∑xp(x)f(x)（5.10）
其中，x~p表示x服从p(x)分布，也可记为f(x)~p。
通常情况下，可以在服从p(x)分布的离散型数据中进行采样，得到样本集x1,x2,…,xN，则f(x)在p(x)分布下的期望为
Ex~p［f(x)］≈1N∑Nxi~p,i=1f(xi)（5.11）
在有些任务中，为了得到分布函数p(x)，需要采集大量的样本才能拟合原期望，或存在部分极端、无法代表分布的样本。针对这些任务，在服从p(x)分布的数据中采样存在困难的问题，根据重要性采样原则，可以将该任务转化为从服从简单分布q(x)的数据中进行采样，得到的样本集为x1,x2,…,xN。此时f(x)在p(x)分布下的期望为
Ex~pf(x)=∑xp(x)f(x)=∑xq(x)p(x)q(x)f(x)=Ex~qp(x)q(x)f(x)
(5.12)
其中，Ex~qp(x)q(x)f(x)表示函数p(x)q(x)f(x)在q(x)分布下的期望。
根据MC采样思想，在采样数据足够多时，f(x)在p(x)分布下的期望近似为
Ex~pf(x)=Ex~qp(x)q(x)f(x)≈1N∑Nxi~q,i=1p(xi)q(xi)f(xi)=1N∑Nxi~q,i=1ω(xi)f(xi)(5.13)
其中，ω(x)为重要性采样比率(importancesampling ratio)，有ω(x)=p(x)/q(x)。
由此，我们将求解f(x)在p(x)分布下的函数期望问题，转换为求解包含重要性采样比率ω的f(x)在q(x)分布下的函数期望。
重要性采样的特点：
（1） q(x)与p(x)具有相同的定义域。
（2） 采样概率分布q(x)与原概率分布p(x)越接近，方差越小； 反之，方差越大。
通常采用加权重要性采样来减小方差，即用∑Nj=1ω(xj)替换N。
① 普通重要性采样(ordinary importance sampling)的函数估计为
Ex~pf(x)≈∑Nxi~q,i=1ω(xi)f(xi)/N(5.14)
② 加权重要性采样(weighted importance sampling)的函数估计为
Ex~pf(x)≈∑Nxi~q,i=1ω(xi)f(xi)/∑Nj=1ω(xj)(5.15)
2. 基于重要性采样的异策略方法
异策略方法目标策略和行为策略是不同的。这里假设目标策略为π，行为策略为b，所有情节都遵循行为策略b，并利用行为策略b产生的情节来评估目标策略。这样需要满足覆盖条件，即目标策略π中的所有动作都会在行为策略b中被执行。也就是说，所有满足π(a|s)>0的(s,a)均有b(a|s)>0。根据轨迹在两种策略下产生的相对概率来计算目标策略π的回报值，该相对概率称为重要性采样比率，记为ρ。
以St作为初始状态，其采样得到的后续状态动作对序列为： At,St+1,…,ST-1,AT-1,ST。在任意目标策略π下发生的概率如式(5.16)所示，在任意行为策略b下发生后的概率如式(5.17)所示。
P(At,St+1,At+1,…,ST|St,At:T-1~π)
=π(At|St)p(St+1|St,At)π(At+1|St+1)…p(ST|ST-1,AT-1)
=∏T-1k=tπ(Ak|Sk)p(Sk+1|Sk,Ak)(5.16)
P(At,St+1,At+1,…,ST|St,At:T-1~b)
=b(At|St)p(St+1|St,At)π(At+1|St+1)…p(ST|ST-1,AT-1)
=∏T-1k=tb(Ak|Sk)p(Sk+1|Sk,Ak)(5.17)
其中，p表示状态转移概率； T是该情节的终止时刻。注意： 公式累乘符号的上标为T-1，因为最后一个动作发生在T-1时刻。St,At:T-1~π表示该情节服从目标策略π。
这样某一情节在目标策略和行为策略下发生的相对概率为
ρt:T-1=∏T-1k=tπ(Ak|Sk)p(Sk+1|Sk,Ak)∏T-1k=tb(Ak|Sk)p(Sk+1|Sk,Ak)=∏T-1k=tπ(Ak|Sk)b(Ak|Sk)(5.18)
其中，ρt:T-1表示某一情节从t到T时刻的重要性采样比率，也就是基于两种策略采取动作序列At,At+1,…,AT-1的相对概率，与重要性采样比率ω(x)相对应。从式(5.12)可以看出，尽管情节的形成依赖于状态转移概率p，但由于分子分母中同时存在p，可以约去，所以重要性采样比率仅仅依赖于两个策略，而与状态转移概率无关。
行为策略中的回报期望是不能直接用于评估目标策略的。根据重要性采样原则，需要使用比例系数ρt:T-1对回报进行调整，使其矫正为正确的期望值：
E［Gt|St=s］=vb(s)vπ(s)=E［ρt:T-1Gt|St=s］(5.19)
假设遵循行为策略b采样得到了一系列情节。为方便计算，将这些情节首尾相连，并按时刻状态出现的顺序进行编号。例如第1个情节在时刻100状态结束，则第2个情节的编号就在时刻101状态开始，以此类推。在每次访问方法中，存储所有访问过状态s的时间步，记为T(s)，并以T(s)表示状态s被访问过的总次数。在首次访问方法中，T(s)只包括这些情节中第一次访问到s的时间步。此外，以T(t)表示在t时刻后的第一个终止时刻，以Gt表示从t到T(t)时刻的回报，以ρt:T(t)-1表示回报Gt的重要性采样比率(在增量式计算中常简写为Wi)。
根据重要性采样思想，状态值函数的计算方法分为两种。
1） 普通重要性采样
将回报按照权重缩放后进行平均。属于无偏估计，具有方差无界的特点。其计算如式(5.20)所示：
V(s)=∑t∈T(s)ρt:T(t)-1GtT(s)(5.20)
2) 加权重要性采样
将回报进行加权平均。属于有偏估计，具有方差较小的特点。其计算如式(5.21)所示：
V(s)=∑t∈T(s)ρt:T(t)-1Gt∑t∈T(s)ρt:T(t)-1(5.21)
分母为0时，V(s)=0。
两种方法的主要差异在于偏差和方差的不同。后面将讨论它们在首次访问方法下，获得单一情节回报后的值函数估计值。
1） 普通重要性采样的偏差与方差
采用某种方法估计值函数，当估计结果的期望恒为vπ(s)时，该方法是无偏估计，但其方差可能是无界的。当ρ=10时，表明该轨迹在目标策略下发生的可能性是行为策略下的10倍，V(s)=10Gt，根据普通重要性采样得到的估计值Vπ(x)是回报值的10倍，这就存在高方差。
2） 加权重要性采样的偏差与方差
由于比例系数ρ被消去，所以加权重要性采样的估计值就等于回报值，与重要性采样比例无关。因为该回报值是仅有的观测结果，所以是一个合理的估计，但它的期望是vb(s)而非vπ(s)，所以该方法属于有偏估计。此外，由于加权估计中回报的最大权重是1，所以其方差会明显低于普通估计。
而实际上，由于重要性采样比率涉及所有状态的转移概率，因此有很高的方差，从这一点来说，MC算法不太适合于处理异策略问题。异策略MC算法只有理论研究价值，实际应用的效果并不明显，难以获得最优动作值函数。
5.4.4蒙特卡洛中的增量式计算
增量式计算在强化学习中具有很重要的应用价值。本节在说明MC增量式计算之前，先来了解经典的增量式计算。
1. 经典的增量式计算
计算一组数据的均值，最简单的方法是使用采样平均法，即将所有的历史信息记录下来，然后求平均。假设有一组实数数据，其形式为x1,x2,…,xk,xk+1,…。令xk为第k个数据的数值，uk为前k个数据的平均值，有：
uk=1k∑ki=1xi(5.22)
使用式(5.22)计算前k个数据的平均值时，需要对这k个数据进行存储，然后再求平均值。这种方法容易产生计算量大和存储消耗量大的问题。根据数学中的迭代思想，引入增量式计算方法，以简化求解过程。增量式推导如下所示：
uk=1k∑ki=1xi
=1k(xk+∑k-1i=1xi)
=1k(xk+(k-1)uk-1)
=uk-1+1k(xk-uk-1)
根据上式的规律，构建经典增量式公式，如式(5.23)所示：
NewEstimate←OldEstimate+StepSize(Target-OldEstimate)(5.23)
其中对式(5.23)中变量说明如下：
Target： 表示当前采样值，称其为目标值，通常伴随着噪声，即存在偏差。
OldEstimate，NewEstimate： 表示真实值的估计值，可理解为V或Q，其目的是逼近真实目标值v或q。
Target-OldEstimate： 表示评估误差，通常记为δ。在递增公式中，通过向Target趋近而使得δ逐步减少。
StepSize： 表示步长(学习率)，通常记为α。在这里用一个较小值α来替代1/k，使公式更具一般性。
需要说明的是，之所以将Target称为目标值，是因为从单次更新过程来看，OldEstimate是朝着Target移动的。而从全部更新结果来看，OldEstimate是朝着真实目标值移动的。在自举方法中，Target也常被称为自举估计值(bootstrapping estimate)。
由此可见，增量式计算方法是一种基于样本Target的随机近似过程，拆分了均值求解过程，减少了存储消耗，简化了计算过程。
2. MC的增量式
对于MC预测问题，在采集情节的基础上也可以使用增量式的实现方法。其增量式的实现可以分为同策略和异策略两种模式。
同策略MC： 使用传统增量式计算公式，不涉及重要性采样，t时刻状态St的状态值函数更新递归式如下所示：
V(St)←V(St)+α［Gt-V(St)］(5.24)
公式右侧的V(St)为历史状态值函数的均值，表示估计值，即OldEstimate。
Gt为t时刻的回报，表示目标值，即Target。
α为步长，当α是固定步长时，该式称为恒定α MC。
异策略MC： 假设已经获得了状态s的回报序列G1,G2,…,Gn-1，每个回报都对应一个随机重要性权重Wi(Wi=ρt:T(t)-1)。当获得新的回报值Gn时，我们希望以增量式的方式，在状态值函数估计值Vn的基础上估计Vn+1。
在普通重要性采样中，仅仅需要对回报赋予权重Wi，其增量式与经典增量式方程基本一致：
V(s)←V(s)+α［WG-V(s)］(5.25)
在加权重要性采样中，需要为每一个状态计算前n个回报的累积权重Cn：
Cn=∑nk=1WkCn=Cn-1+Wn(C0=0)(5.26)
其中，Cn表示前n个回报的重要性权重之和，右式是其增量形式。由此得到Vn的更新递归式为
Vn+1=Vn+WnCn(Gn-Vn)(n≥1)(5.27)
推导过程为
Vn+1=∑nk=1WkGkCn=∑n-1k=1WkGk+WnGnCn
=∑n-1k=1WkGkCn+WnGnCn=∑n-1k=1WkGk∑n-1k=1Wk·∑n-1k=1WkCn+WnGnCn
=Vn·Cn-WnCn+WnGnCn
=Vn+WnCn(Gn-Vn)(n≥1)
3. 随机近似条件
由于MC是基于采样方法进行更新的，当状态和动作空间是离散且有穷时，只要满足如下两个条件，动作值函数估计值Qπ(s,a)就能收敛于真实动作值函数qπ(s,a)。
（1） 满足∑∞t=1αt=∞，∑∞t=1α2t<∞(5.28)
（2） 所有的状态动作对都能够渐近地被无限次访问到。
若α根据随机近似条件逐渐变小，则它能以概率1收敛。以上收敛条件均适用于其他采样模型。所以只要所有(s,a)都能被无限多次地访问到，且贪心策略在极限情况下能够收敛(ε衰减为0)，那么采样模型就能以1的概率收敛到最优动作值函数和最优策略。
5.4.5异策略蒙特卡洛控制
异策略MC控制算法与异策略MC预测算法的原理一致，动作值函数更新递归式为
Q(St,At)←Q(St,At)+WC(St,At)［G-Q(St,At)］(5.29)
算法5.4给出了用于估算最优策略的异策略MC控制算法。
算法5.4异策略MC控制算法
初始化：
1.对所有s∈S+，a∈A(s)，初始化Q(s,a)∈R，Q(sT,a)=0，C(s,a)=0
2.ε←(0,1)为一个逐步递减的较小的实数
3.π(s)←argmaxa Q(s,a)
4.repeat 对每一个情节k=0,1,2,…
5.b←任意软性策略
6.根据策略b(s)，从初始状态动作对(S0,A0)开始，生成一个情节序列S0,A0,R1,…,ST-1,AT-1,RT,ST
7.G←0
8.W←1
9.for 本情节中的每一步t=T-1downto0 do
10. G←γG+Rt+1
11. C(St,At)←C(St,At)+W
12. Q(St,At)←Q(St,At)+WC(St,At)G-Q(St,At)
13. π(St)←argmaxa Q(St,a)
14. if At=π(St) then W←W1b(At|St)
else break
15.end for
输出： π*=π
在算法5.4第14行，如果行为策略b采样的动作与目标策略π采取的动作不同，则π(At|St)=0，重要性权重为0，无法更新值函数，退出本次情节的迭代。从这一步可以看出，每一次迭代都会很快停止，效率不会很高，这一点也是异策略MC应用性不强的原因之一； 第14行： 当At=π(St)时，π(At|St)=1，重要性权重更新递归式就简写为W←W1b(At|St)。
阅读代码15
例5.4对于扫地机器人问题，通过行为策略来生成情节，然后利用每次访问和重要性采样比率计算动作值函数Q(St,At)，如果行为策略采样的动作不是目标策略采取的动作，则会结束该循环开始新一轮循环。这样也就产生很多无用的数据，使得学习效率不高。表5.3为异策略每次访问MC控制算法的Q值更新表。
在线表格08
表5.3异策略每次访问MC控制算法的Q值更新过程
S5
…
S10
…
S18
…
S20
…
S24
Q0
0.000;0.000;
*.***;0.000
…
0.000;0.000;
*.***;0.000
…
0.000;0.000;
0.000;0.000
…
*.***;0.000;
*.***;0.000
…
*.***;0.000;
0.000;*.***
b1
0.333; 0.333;
0.000; 0.333
…
0.333; 0.333;
0.000; 0.333
…
0.250; 0.250;
0.250; 0.250
…
0.000; 0.500;
0.000; 0.500
…
0.000; 0.500;
0.500; 0.000
π0
1.000; 0.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
0.000; 1.000;
0.000; 0.000
…
0.000; 1.000;
0.000; 0.000
Q1
0.000;0.000;
*.***;0.000
…
0.000;0.000;
*.***;0.000
…
1.920;0.000;
0.000;0.000
…
*.***;0.000;
*.***;0.000
…
*.***;3.000;
0.000;*.***
b1
0.333; 0.333;
0.000; 0.333
…
0.333; 0.333;
0.000; 0.333
…
0.250; 0.250;
0.250; 0.250
…
0.000; 0.500;
0.000; 0.500
…
0.000; 0.500;
0.500; 0.000
π1
1.000; 0.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
0.000; 1.000;
0.000; 0.000
…
0.000; 1.000;
0.000; 0.000
︙
︙
…
︙
…
︙
…
︙
…
︙
Q7500
0.960;1.000;
*.***;0.977
…
1.215;0.799;
*.***;1.208
…
1.917;1.889;
1.894;3.000
…
*.***;1.181;
*.***;1.229
…
*.***;3.000;
1.916;*.***
b7500
0.333; 0.333;
0.000; 0.333
…
0.333; 0.333;
0.000; 0.333
…
0.250;0.250;
0.250; 0.250
…
0.000; 0.500;
0.000; 0.500
…
0.000; 0.500;
0.500; 0.000
π7500
0.000; 1.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 1.000;
0.000; 0.000
︙
︙
…
︙
…
︙
…
︙
…
︙
Q12500
0.975;1.000;
*.***;0.979
…
1.220;0.800;
*.***;1.215
…
1.918;1.899;
1.904;3.000
…
*.***;1.200;
*.***;1.229
…
*.***;3.000;
1.914;*.***
b12500
0.333; 0.333;
0.000; 0.333
…
0.333; 0.333;
0.000; 0.333
…
0.250; 0.250;
0.250; 0.250
…
0.000; 0.500;
0.000; 0.500
…
0.000; 0.500;
0.500; 0.000
π12500
0.000; 1.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 1.000;
0.000; 0.000
︙
︙
…
︙
…
︙
…
︙
…
︙
Q19999
0.978;1.000;
*.***;0.977
…
1.223;0.800;
*.***;1.221
…
1.917;1.906;
1.906;3.000
…
*.***;1.209;
*.***;1.228
…
*.***;3.000;
1.916;*.***
b19999
0.333; 0.333;
0.000; 0.333
…
0.333; 0.333;
0.000; 0.333
…
0.250; 0.250;
0.250; 0.250
…
0.000; 0.500;
0.000; 0.500
…
0.000; 0.500;
0.500; 0.000
续表
S5
…
S10
…
S18
…
S20
…
S24
π19999
0.000; 1.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 1.000;
0.000; 0.000
Q20000
0.978;1.000;
*.***;0.977
…
1.223;0.800;
*.***;1.221
…
1.917;1.906;
1.906;3.000
…
*.***;1.209;
*.***;1.228
…
*.***;3.000;
1.916;*.***
b20000
0.333; 0.333;
0.000; 0.333
…
0.333; 0.333;
0.000; 0.333
…
0.250; 0.250;
0.250; 0.250
…
0.000; 0.500;
0.000; 0.500
…
0.000; 0.500;
0.500; 0.000
π20000
0.000; 1.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 1.000;
0.000; 0.000
π*
0.000; 1.000;
0.000; 0.000
…
1.000; 0.000;
0.000; 0.000
…
0.000;0.000;
0.000; 1.000
…
0.000; 0.000;
0.000; 1.000
…
0.000; 1.000;
0.000; 0.000
5.5小结
本章介绍了从经验中学习价值函数和最优策略的蒙特卡洛方法，这些“经验”主要体现在从多个情节采样数据。与DP方法相比，其优势主要在以下3个方面： ①MC方法不需要完整的环境动态模型，而可以直接通过与环境的交互来学习最优的决策行为。②MC方法可以使用数据仿真或采样模型。在很多应用中，构建DP方法所需要的显式状态概率转移模型通常很困难，但是通过仿真采样得到多情节序列数据却很简单。③MC方法可以简单、高效地聚焦于状态的一个小的子集，它可以只评估关注的区域而不评估其他的状态。
5.6习题
1. 举例说明蒙特卡洛首次访问和每次访问的异同点。
2. 蒙特卡洛方法可以解决哪些强化学习问题？
3. 给出蒙特卡洛估计qπ(s,a)值的更新图。
4. 修改异策略蒙特卡洛控制算法，使之可以递增计算加权的平均值，并给出伪代码。
5.（编程）通过蒙特卡洛法计算： 第3章习题2（图3.12）扫地机器人在等概率策略的情况下，分别给出实验次数为5000和50000时，每个状态的价值vπ(s)。