人工智能强化学习11|小白都能秒懂的蒙特卡罗
蒙特卡罗方法（Monte Carlo Methods）一词最早是由计算机之父冯·诺伊曼等人于20世纪40年代提出的。Monte Carlo本身是一座非常著名的赌城，所以这一算法与“赌”就结下了不解之缘。如今，蒙特卡罗方法在金融工程学、宏观经济学、生物医学、计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算、核工程）等领域都获得了广泛的应用。在人工智能（AI）领域，蒙特卡罗方法则是强化学习的三大基本学习方法之一。
本篇是蒙特卡罗方法的上篇，旨在解释蒙特卡罗方法的基本算法规则。如果您一直有跟读强化学习系列的文章，就会发现之前有数篇文章对动态规划算法进行了讲解。不论是动态规划还是蒙特卡罗方法，都旨在实现最优控制的目标。这种最优控制可以理解为最优的选路、最优的舞蹈动作、最优的音乐演奏、最优的生产流程控制等。总之，只要现实世界中存在选择题，就有蒙特卡罗方法下手的地方。当我们编写程序，由程序来控制一架无人机进行隧道探索时，可以人工设定全过程的参数（例如PID控制），能让无人机在隧道中不受阻碍的飞行说明控制者经验丰富，他能够在全过程中设置相对最优的参数。如果让人工智能程序来控制这些参数呢，人工智能程序如何才能学会合理的控制无人机呢？蒙特卡罗方法恰好可以做这件事。
环境（environment）
我们先来看看最简单的一个环境，Random walk：
A – B – C – D – E – end
·动作（A）：我们的人工智能位于C点，它有两个动作可以选择（向左行走一步或向右行走一步），但凡它走一步我们就称为度过了一个时间步（time-step）；
·奖励（R）：我们规定每当它走一步，只要没有走到最终点end，那么就给予 -1 分的奖励（实际上是惩罚），而如果它走到终点end了，则给予 +20分的奖励，以此激励它选择倾向于终点的走法（控制方法）；
·状态（S）：状态的规定方法可以有很多种，在这个例子中我们把所有的位置都定义为一个状态，即本环境存在5个一般状态与1个结束状态；
预测（prediction）
学习这种最优控制方法，我们通常会先简化控制问题为一个预测问题。所谓控制问题就是给予AI一个初始化的策略（通常这个策略很烂），然后让它在环境中游玩，获取经验并改善这个策略，而预测问题则是人工指定一个相对感觉不错的策略，来看看AI能否按照这个策略玩下去。
我们首先让AI出生在C点，这时候时间步为0，我们称AI处于S0 = C，然后给AI一个人工指定策略（例如40%可能性向左，60%可能性向右），这时候AI按策略执行了动作A0向右。接下来时间步增加1，并且环境给予AI相应的反馈：由于AI从C点向右走到了D点，所以获得奖励值R1 = -1 ，并且进入到下一个状态S1 = D。从这一套玩法我们可以得到一个类似回合的流程S0 – A0 – R1 – S1，其实我们可以把这一回合设定为S0 – A0 – R1就很合理了，如果这个游戏可以一直玩下去，我们就可以得到一连串的回合。
S0 – A0 – R1 – S1 – A1 – R2 – S2 – A2 – R3 – S3 – A3 – R4 ……
现在我们假设AI已经玩完这个游戏了，最终它按照这样的行走顺序到达了end点，C – D – C – D – E – D – E – end，第一次走到D点时它获得奖励 -1分，然后再走到C点又获得奖励 -1 分就共计 -2 分了，直到最后它才能获得 +20 分的正面奖励，所以你能算算它的最后得分吗？
我们刚刚说到它“第一次走到D点”这个第一次成为对状态D的first-visit，之后再次到达D点就是second-visit等等。我们现在就来评估一下D点的价值，我们先只看first-visit就是第一次到达D点之后的结果，即只计算这一段经历的最后得分D – C – D – E – D – E – end 这个方法称为first-visit蒙特卡罗方法，其伪代码如下：
我们可以清楚地看到代码最下端有个单词 average。没错，这里要计算平均值。我们都知道AI是要进行训练的，这个训练过程就是让它反复玩这个游戏环境，每一次都从C点开始直至它走到end点或者人为停止游戏。那么每一次游玩成为一个场景（epsiode），就跟拍电影的时候导演会喊“咔”一样，一个场景往往会被拍N遍直到导演满意，我们的AI也要在这个场景中玩N遍，每一遍都可能会经历D点，每一遍我们都从它第一次经历D点开始记录分数，直至累计到它完成这一次游戏。聪明的你可能会发现D点应该是每次肯定要经历的，不然它不会走到end点，然而A点或者B点就不一定了，像这种A点没有出现的情况，我们就认为A点在本次游戏中的得分为0。当AI玩了3000遍以后，我们分别记录了A、B、C、D、E点在这3000遍所累计的由first-visit蒙特卡罗方法配合我制定的策略（40%可能性向左，60%可能性向右）所得到得分（每个点应该有3000个最终得分），最后计算一个平均值，就得到了目前状态下这5个点的价值，这时让AI总是走向价值较高的点就是最优的路线。
以上就是最简单的first-visit蒙特卡罗方法的预测算法，下一篇我们会进阶到every-visit与控制算法。
往期回顾：
