欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

强化学习(5)-蒙特卡洛

Pi_30K

了解「概率模拟」的应该都熟悉这个方法,LDA的Gibbs Sample就用到了这个方法。蒙特卡洛方法,不需要对环境建立「完美」模型。本文用大白话总结就是:通过数数实现action的价值预估。

QQ20170501-223310

上面流程非常简单,就是基于基本的统计(平均)作为预估,并且每一个状态价值的预估和别的状态之间是「独立」的,当状态很多的时候这个方式的效率就会得到体现;同时,如果某一个状态下样本太少,也可以通过直接「模拟」的方式生成样本从而统计,达到预估的目的。

Monte Carlo Estimation of Action Values

如果模型不好建立,直接对action value进行预估达到一步到位,不用绕路去预估state value。在有一个模型的时候,通过state value可以简单的得到决策的action(例如贪心策略);

做决策的时候,我们必须预估每一个action带来的收益,Monte Carlo的方法就是直接对action value进行预估,得到最优的 \(q_*\)

当state或者action空间较大,会导致我们样本中出现的pair(state,action)并不能覆盖所有情况,这样会导致得不到全局最优的action。解决这个问题典型的方式就是解决Bandit问题的EE相关的算法。

Monte Carlo Control

QQ20170507-124524

evaluation的过程将策略价值估准确,improvement过程更好的使用上一步预估好的价值挑选「最大收益」的策略。可以发现,这两个过程也可以和计算广告和推荐系统中的模型和策略对应起来;一个是「估准确」另一个是「用好」。

两个假设

蒙特卡洛方法可以很好地工作有两个假设,分别为:

  1. 初始选择概率(explore出更好的action)
  2. 无限次数的迭代(无数条样本,理论上可以收敛到最优位置)

如果想要打破第二假设,有两种方式,一个是当迭代次数达到一定程度(例如变化小于某个值)就停止;另一个是evaluation的时候只针对部分pair(state,action)进行计算,从而减少计算量。

On-Policy Monte Carlo Control

就是EE在选择action的具体应用,采用 \(\xi -greedy\) 策略。下图为具体的算法过程:

QQ20170508-153406

Off-Policy Monte Carlo Control

基本思路就是通过策略 \(u\) 生成样本,然后用一个贪心策略 \(\pi\) 和他对比(在数据量充足的情况下,贪心是最优策略),如果发现不一致,就说明需要更新价值函数。更新的时候需要添加权重,距离结束越远权重越小。具体算法流程为:

QQ20170508-154527

 

资料

《Reinforcement Learning: An Introduction》

 

未经允许不得转载:大数据算法 » 强化学习(5)-蒙特卡洛

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站