首页 > 其他 > 详细

强化学习3-蒙特卡罗

时间:2019-02-17 16:03:47      阅读:299      评论:0      收藏:0      [点我收藏+]

  

之前讲到强化学习可以用马尔科夫决策过程来描述,通常情况下,马尔科夫需要知道  {S A P R γ},γ是衰减因子,那为什么还需要蒙特卡罗呢?

首先什么是蒙特卡罗?

蒙特卡罗实际上是一座赌城的名字,蒙特卡罗方法是冯 诺依曼 用这座赌城的名字起的。

蒙特卡罗方法的主要思想是:当求解的问题是某随机事件出现的概率,或者某随机变量的期望时,可以采用多次采样,以该事件出现的频率来估计其概率,以该变量的均值来估计其期望。并以此来代替问题的解。

那么为什么要用蒙特卡罗方法?

在真实的场景中,我们经常没法确定状态转移概率P,或者根本就是完全随机,那么我们就无法计算该状态的价值函数,但是依然要解决这类问题,怎么办?

一个可行的思路是:虽然没有状态转移概率,但是这个概率是存在的,或者说通过一个动作一定能够使该状态转换到另一个状态,那么我们可以重复试验很多次,然后求该状态每次试验的价值平均,这就是蒙特卡罗思想。

下面来具体看看蒙特卡罗的数学描述

1.首先蒙特卡罗问题的使用条件{S A γ} , 无需状态转移概率P , 和即使奖励R , 当然有 π(pai)是 策略评估,预测问题,无π  是策略优化,控制问题。

2.蒙特卡罗是通过试验来计算价值函数的,根据贝尔曼方程,vπ(s)=Eπ(Rt+1+γRt+2+γ2Rt+3+...|St=s) ,  需要知道整个回合episode的奖赏R , 而且有些情况下不到最后是没有奖赏的,如下棋,完了才有输赢,故蒙特卡罗需要生成整个回合。即每次试验要从起点到终点。

当然起点和终点不一定是固定的,根据具体规则来确定,如下棋,起点不一定就是开局,也可以从中间某步开始,比如街边老头摆的棋阵,再如走迷宫,可以有多个入口,多个出口,只要从大家公认的起点到终点,就算走出迷宫 。

仔细思考下,会发现如下几个问题

1. 在走迷宫时,可能经常会出现在同一个位置,绕来绕去,这相当于某个状态在整个回合中多次出现, 也有可能某个状态在整个回合中没有出现,那么这种情况如何处理呢?下面会讲到 。 

2.生成完整序列 S1,A1,R2, | S2,A2,R|...St,At,Rt+1 |,...St-1,At-1,RT, | ST , 最终状态没有动作和奖励,然后根据贝尔曼方程把 R 加起来,但是这里的 R 明明应该是动作价值函数,为什么 可以用来求状态价值?

解答:

首先,状态价值函数 vπ(s)=aAπ(a|s)qπ(s,a) ,动作价值函数的加权和;

其次,在我们生成完整序列时,在某状态下是根据我们未知(控制)或已知(预测)的策略来选择动作,从而转换到下一个状态,那么重复多次试验,在该状态转换到下一个状态的既定事实是符合 π 的,

如在s时的策略 1/3 选a , 2/3 选b, 那我们重复3次试验,最后的结果应该是 1次 s a s‘, 2次 s b s‘‘, 然后把这些动作价值函数加起来, q1+q2+q2 = 1/3 q1 + 2/3q= π * q 

 

### 需要搞清楚一点是:

策略评估求的是状态价值函数,因为策略已定,就是看这种策略下的价值大小,

而策略平均求的是动作价值函数,因为目的是找策略,就是看每个状态下不同动作的价值大小

 

下面我们来看看蒙特卡罗方法解决策略评估问题,顺便解决上个问题1

1 条件 {S A γ}

2.生成完整序列 S1,A1,R2, | S2,A2,R|...St,At,Rt+1 |,...St-1,At-1,RT, | ST   生成多个

3.计算价值函数  在每个完整序列中计算每个状态的价值函数,然后更新

  对比马尔科夫决策过程 , vπ(s)=Eπ(Gt|St=s)=Eπ(Rt+1+γRt+2+γ2Rt+3+...|St=s)

  可以看出每个状态的价值函数等于所有该状态收获的期望,同时这个收获是通过后续的奖励与对应的衰减乘积求和得到。注意:这个时候v是真实的,真实的平均。

  那么对于蒙特卡罗法来说,如果要求某一个状态的状态价值,只需要求出所有的完整序列中该状态出现时候的收获再取平均值即可近似求解,注意:这个时候v只是估计,因为你就试验了几次,不代表全部

  Gt=Rt+1+γRt+2+γ2Rt+3+...γT?t?1RT

  vπ(s)average(Gt)s.t.St=s
 
  此时就会碰到上述问题1
  / 如果在该回合中没有出现某状态,则在该回合遍历是忽略该状态的更新
  / 如果在该回合中多次出现某状态,有两种处理方式 first visit和every visit
    // first visit :只计算第一次出现时的价值

    在给定一个策略,使用一系列完整episode评估某一个状态 技术分享图片 时,对于每一个episode,仅当该状态 技术分享图片 首次出现的时间 技术分享图片 列入计算:

    状态出现的次数加1: 技术分享图片

    总的收获值更新: 技术分享图片

    状态 技术分享图片 的价值: 技术分享图片

    当 技术分享图片 时, 技术分享图片

    // every visit:每次都计算价值 

    在给定一个策略,使用一系列完整的episode评估某一个状态 技术分享图片 时,对于每一个episode,状态 技术分享图片每次出现在状态转移链时,例如,一次在时刻 技术分享图片,一次在时刻 技术分享图片,则两次对应的 技术分享图片 技术分享图片都要用于计算 技术分享图片 对应的值。

    状态出现的次数加1: 技术分享图片(每次visit状态 技术分享图片 都会+1)

    总的收获值更新: 技术分享图片(每次visit状态 技术分享图片 都会增加回报)

    状态s的价值: 技术分享图片

    当 技术分享图片 时, 技术分享图片

    // 第二种方法比第一种的计算量要大一些,但是在完整的经历样本序列少的场景下会比第一种方法适用。

4.完成

    
 
 
 
 
 
 
 

 

 

强化学习3-蒙特卡罗

原文:https://www.cnblogs.com/yanshw/p/10391106.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!