【Reinforcement Learning】蒙特卡洛算法

强化学习相关的蒙特卡洛算法的介绍。此处笔记根据B站课程，王树森老师的强化学习记录而来。6.蒙特卡洛 Monte Carlo(Av374239425,P6)_哔哩哔哩_bilibili

1.Monte Carlo Algorithms蒙特卡洛算法

蒙特卡罗算法是随机算法的一种， 本质是使用随机样本估计真实值。最终的值是错的，但是它靠近真实值，像是难以求解解析解的积分、神经网络等，使用近似解就可以了，蒙特卡洛算法就是常用的近似算法之一。

2.例1——使用几何方式近似Π

正方形的面积是A1=2*2=4,圆的面积是A2=Π*1^2=Π

在正方形内采用均匀随机抽样，抽点(x,y),点在圆上的概率为p=A2/A1=Π/4。抽取n个点，期望为E(x)=Π*n/4。如何判断点是否在圆上，如x^2+y^2<=1时，点在圆上，否则点不在圆上。

已知均匀抽样n个点，其中m个点在圆上，则可以用m近似Π*n/4，则可以用4m/n近似Π。大数定理保证了蒙特卡洛搜索的正确性，n越大，近似越准确。

 

3.例2——投针算法

Buffon's Needle Problem布芬投针实验

 一组平行线，间距为d, 针长为l, 随机投针，计算针与平行线有交点的概率。p=2l/Πd，n个针投针实验期望为E(X)=np=2ln/Πd

l越大，p越大，d越大，p越小。

使用n个针进行投针实验，有m个针与平行线有交点，则有m近似2ln/Πd, 则2ln/dm可以近似Π。

 验证的一种方法：根据概率不等式, 近似精度反比根号n

4.例3——估计阴影布芬面积，近似Π

正方形面积为2*2=4，在正方形内随机均匀采样点(x,y)，

若点在圆内，则有（x-1)^2+(y-1)^2<=1

若点在扇外，则有  x^2+y^2>2

 则阴影部分，在圆内扇外，设其面积为A2, 正方形为A1=4,则点在阴影部分的概率为p=A2/4。抽n个点，则期望为E(x)=np=n*A2/4。 其中m个点在阴影内，则可用m近似n*A2/4, 则A2的面积可近似为4*m/n

 

5.例4——近似求积分

复杂积分没有数值解，只能近似，常用蒙特卡罗算法近似。

 一元积分：

 

多元积分，如二元函数近似Π

 

 

 

6.例5——近似期望

 

  

7.Monte Carlo相关

Monte Carlo的名字来自赌场，algorithm that rely on repeated random sampling to obtain numerical results.

结果是错的但是接近真实值。

随机快排：随机性不影响正确性，总是正确的

大西洋算法： 正确率高达75%