在接触强化学习过程中，大家可能在很多场合据说蒙特卡洛这个词，例如 Monte Carlo Tree Search，Monte Carlo CFR。理论即使在策略梯度 (Policy Gradients) 算法中也应用了蒙特卡洛办法，本文将介绍 Monte Carlo 算法和在强化学习中的利用。基本概念 Monte Carlo 办法源于 20 世纪 40 年代，由冯. 诺依曼，斯塔尼斯拉夫·乌拉姆在核武器钻研过程中提出。和许多以作者名字 (如拉格朗日定理，柯西定理) 命名不同，Monte-Carlo 其实并不是某位学者名字，实际上是一座位于摩洛哥的赌场。统计和概率学常常会将概率和博彩分割在一起，或者某天也会呈现澳门葡京办法 / 定理 Monte Carlo 实质上是一种统计学办法，这类办法通过随机抽样，依据随机事件呈现的频率来估算随机变量的特色大家小时候都学过撒豆子估算不规则图形的面积，应用一个规定图形包裹不规则图形，而后将肯定数量的豆子平均的洒向这个图形，通过计算不规则图形中豆子比例和规定形态的面积，即能够估算出不规则形态的面积。随着计算机技术产生，撒豆子被随机数代替，这一类办法也被各个领域宽泛应用。如果咱们并不知道圆形面积计算公式，假如圆形半径为 1，咱们应用变长为 2 的正方形包裹这个圆形，而后平均采样，随着样点数量的减少，圆形面积将越来越靠近理论值
from math import sqrt, pi
from random import uniform
正方形边长和面积
side_length = 2.0
square_area = side_length * side_length
圆形半径
radius = side_length / 2
def in_circle(x, y):
return sqrt(x x + y y) < radius
num_sample = 10000000
num_in_circle = 0
for i in range(num_sample):
x = uniform(-1, 1)
y = uniform(-1, 1)
num_in_circle += in_circle(x, y)
落入圆形的样点个数
ratio = num_in_circle / num_sample
圆形面积
circle_area = ratio * square_area
print(‘circle area: {}, theory area: {}’.format(circle_area, pi radius radius))
执行后果 circle area: 3.1413452, theory area: 3.141592653589793
强化学习中的利用根底利用在深度学习和强化学习畛域中，许多算法实际上应用了 Monte-Carlo 办法，并没有给它冠名。这些算法如此根底，咱们常常会疏忽它的存在。例如因为计算资源受限，深度学习把一个批次样本的梯度作为整体梯度的预计，来更新模型的权重，同时通过屡次采样 (迭代次数，或者 step 数) 修改偏差。经典的强化学习算法中，无论 Q -Learning 还是 Policy Gradient 算法中，都须要估算累计收益，例如多步 TD TargetMonte-Carlo Tree Search 蒙特卡洛树搜寻蕴含两层含意，首先它是一种树搜寻办法，和深度优先、广度优先搜索算法相似，它须要对树进行遍历。其次蒙特卡洛强调了它并不是一种确定性的搜索算法，而是通过启发式的形式，让树向着最优解方向成长，升高搜寻空间，实现了相似剪枝的性能。具体流程如下：抉择 (Selection): 从根节点开始，通过 UCT(Upper Confidence Bounds to Trees) 办法向下直至抉择出一个叶子节点。UCT 办法对每个节点进行打分，通常蕴含利用 - 摸索两个重量。利用重量源于先验常识，例如之前仿真的后果，有时也会蕴含神经网络给出的评分；摸索重量个别和这个节点的拜访次数无关，如果节点拜访的越少，则摸索重量的值越大。扩大(Expansion)：抉择完结之后，咱们失去一个叶子节点。当叶子节点曾经被充沛评估时，会在这个节点根底上拓展出一个新的叶子节点。评估是否充沛个别以这个叶子节点曾经被仿真过多少次来掂量。仿真(Simulation)：从叶子节点开始游戏，直至游戏完结。反向流传(Back Propagation)：仿真完结后，咱们会失去本次模仿的后果，拿这个后果刷新沿途节点分值。Monte-Carlo CFRCFR 算法须要对博弈树进行遍历，从而计算某个动作的遗憾值。当博弈树规模十分大时，遍历整棵树的老本十分高，改良的办法：在单局博弈中，对动作进行剪枝。例如在某个信息集上，所有非法的动作有 M 个，算法人为的限度它的搜寻为 N，N 的数值还能够随着遍历层级的加深而缩小；作为补充，算法须要减少博弈的次数，尽可能笼罩更多的动作