大话增强学习-2

2017-12-03

大话增强学习第二篇。本系列以口语化形式，讲述理解增强学习。

蒙特卡洛

1856年，摩纳哥亲王查理三世为解决财政危机，便允许在摩纳哥老城海角上兴建一所赌场。经过一次在摩纳哥老城中失败的尝试，1862年在蒙特卡洛兴建了一所简陋的赌博娱乐场所。赌场于1863年落成，但附近一直都没有人盖房屋。直至赌场经理François Blanc接手赌场后，他凭借个人的才能与雄厚的资金建立了一座集豪华奢侈的都市。

蒙特卡洛是一座赌城，位于法国边上的摩纳哥公国。

蒙特卡洛方法

赌博就是瞎猜，聪明点就是计算概率。蒙特卡洛方法就是瞎猜很多次，得到概率或平均值。

蒙特卡洛方法用于增强学习

回顾

在大话增强学习-1中，我们得到了根据R(s,a)奖励来迭代计算出q(s,a)的方法，进而得到最大策略。

$$ q(s,a) = R(s,a) + r*max(q(s{’},a{’})) $$

$$ q_{latest} = (1-a)q_{old} + aq_{new} = q_{old} + a(q_{new} - q_{old}) $$

可如果我们不知道所有的R(s,a)该怎么办呢？又或者我们不知道准确的R(s,a)该如何呢？毕竟R(s,a)可能是有一定统计分布的，并不一定是一个固定的值。

直觉思路

既然不知道所有的R(s,a)，那我就挨个试，撞大运，赌一把，采取随机策略，在s时随机选一个a，一路走到底，得到一个v(s)。我瞎试很多次，取个平均，就很接近v(s)的值了。于是，我便有了v(s)。由于蒙特卡洛是一座赌城，我们就把这个思路叫做蒙特卡洛方法。

这里很重要的是一路走到底，得到个大结局v(s)，得有底。不说人话，这叫做episode task，直译为情节任务。人生其实也是episode task，总会衰老死亡并被历史记录或遗忘。既然人生如此，那么人工智能的很多任务自然也符合这个假设。如果一路走不到底，就没法使用这个瞎猜方法了。

以演员表演，导演评价为例，导演觉得v(s)太低，说cut，我们重来一次。演员在上一次基础上得到了些经验教训，于是以随机策略2.0再来一次，得到了个新的v(s)，这次好点了。

导演还是不满意，一次次地重来，随机策略n.0就慢慢出来了。演员演的越来越好。最后导演看差不多很难提高了，就说了句：收工。于是演员就得到了最佳策略。这叫做策略迭代和价值迭代交替进行。

以上是正常的演员。但有种很蠢的演员不能吸取教训，每次演都像电影初恋50次的女主角一样会忘光以前的记忆。这种演员走的就是拉斯维加斯算法的道路。死路一条。

值得一提的是，我们不需要R(s,a)了。导演不需要对每个动作做评价，只要对这个episode task的每一个重拍做个评分即可。

以上得到v(s)的方法，就叫做蒙特卡洛法，AlphaGo也是这么干的。

得到了v后如何更新策略呢

贪婪地挑选最大v值的s，并执行a即可。不说人话，这叫做argmax。更严谨的描述是MC Control，蒙特卡洛控制。在初期模型评估并不准确（v不准），如果简单地argmax的话，可能走歪了不能发现最佳策略。一个方案是穷举所有的可能，但是这样计算量太大。另一个方案是引入一个参数e，以一定的随机概率在top argmax中去探索策略，e越来越小，不确定性越来越小最后收敛停止探索。

更新了策略如何更新v呢

还记得大话增强学习-1中的更新q(s,a)的方法吗？我们这里也同理运用到更新v(s)上来。理解了大神怎么想的，小白也就会创新了。

$$ v_{latest} = (1-a)v_{old} + a*v_{new} = v_{old} + a(v_{new} - v_{old}) $$

可以看出，当演员想穷举各种方案一点点慢慢测试导演耐心时，可以先a=0，进入拉斯维加斯算法模式，不更新策略，搞出很多个v来做平均，得到个较为完美的新的v。然后，利用以上公式更新v，即更新了策略。周而复始。这叫first-visit。

若演员想偷懒的话，演员也可以结合e随机探索，每次重来都去更新v。这叫every-visit。

小结

我们得到了v(s)，进而知道最佳策略a。而在大话增强学习-1中，我们是得到q(s,a)进而得到a和v(s)。瞎试很多次得到v的平均值，然后利用下式更新。以e概率进行策略探索，e越来越小最后收敛。