MC Exploring Starts算法介绍

算法背景与目的

在介绍完mc basic算法后，我们引入mc exploring stars算法，它是mc basic的一个推广，目的是让算法变得更加高效。

mc basic的优点是能帮助我们理解如何用蒙特卡罗方法实现无模型的强化学习，但缺点是考虑因素较少，效率低，在实际中不太实用。所以我们对mc basic进行推广使其更实用。

数据利用与策略更新的优化方法

1. 数据利用方法：
   • 在一个网格世界中，遵循一个策略$\pi$得到一个episode，引入“visit”概念，即episode中每出现一次状态-动作对$(s,a)$，就称为对该$(s,a)$有一次访问。
   • mc basic中使用“initial visit”方法，例如对于一个episode，只考虑$(s_1,a_2)$，用剩下得到的return来估计$(s_1,a_2)$的action value，即$q_{\pi }(s_1,a_2)$ 。但这种方法没有充分利用episode中的数据，因为除了$(s_1,a_2)$外，还访问了$(s_2,a_4)$、再次访问$(s_1,a_2)$、$(s_2,a_3)$、$(s_5,a_1)$等。从$(s_2,a_4)$开始，不考虑前面部分，可将其当作新的episode来估计$(s_2,a_4)$的action value，同理可用于其他状态-动作对，这样能更充分利用数据。
   • 这里有“first visit”和“every visit”两种方法。“every visit”是只要访问了一次$(s,a)$，就用其后边的return来估计$(s,a)$的action value；“first visit”则是只用第一次出现$(s,a)$时其后边的return进行估计，第二次出现时不再用其后边来估计。
2. 策略更新方法：
   • mc basic中使用的策略更新方法是把从一个状态-动作对$(s,a)$出发的所有episode都收集到，然后做平均return来估计action value，但这种方法需要等待所有episode都得到才行，浪费时间，效率较低。
   • 另一种方法是得到一个episode，就用该episode的return立刻估计action value，然后直接开始改进策略，即得到一个episode就改进一次策略，这样能提升效率。虽然用一个episode来估计action value可能不准确，但这种思想在上节课讲“incremental policy iteration”时已介绍过，在做policy evaluation求当前策略的state value时，求解贝尔曼公式需要无穷多步迭代，当时采取只做有限步迭代的方式，算法仍然可行有效，这里同理。

Generalize的Policy Iteration（GPI）框架

上述这些方法属于“generalize的policy iteration”（简称gpi），gpi不是一个具体的算法，而是一大类算法，是一种思想或架构，即在policy evaluation和policy improvement中间不断切换，且policy evaluation不需要精确估计action value或state value。上节课和本节课介绍的算法都能归入gpi框架。

MC Exploring Stars算法概述

基于上述思考得到mc exploring stars算法，它是mc basic的推广，计算效率更高。

算法的伪代码主要步骤包括生成一个episode，然后进行policy evaluation和policy improvement。在计算return时，为提高计算效率采用倒推方式。例如对于一个episode$(s_1,a_1,s_2,a_2,s_3,a_3,s_4,a_4,\cdots )$ ，正常做法是遍历每个状态-动作对，把后面的reward全加起来得到return作为该状态-动作对action value的估计值。但该算法从后面开始做，假设后面已计算出的reward相加得到的return为$g$ ，计算$(s_3,a_3)$的return时，若从$(s_3,a_3)$得到的即时reward是$r$ ，则$(s_3,a_3)$出发的return为$r+\gamma g$（$\gamma$为折扣因子），这个新的$g$又可用于计算$(s_2,a_2)$的return（即从$(s_2,a_2)$出发得到的reward$r$加上$\gamma$乘以新的$g$ ），通过这种倒推方式高效计算return。

Exploring Starts条件的必要性与实际困境

1. 必要性：
   • “exploring”指从每一个状态-动作对$(s,a)$出发都要有episode，这样才能用后面生成的reward来估计return，进而估计action value。若有一个$(s,a)$未被访问到，可能会漏掉最优动作，所以要确保每一个$(s,a)$都能被访问到。
   • “starts”指访问每一个$(s,a)$并从其后面生成可用于估计return的数据，有两种方式：一是从$(s,a)$开始一个episode（即“start”）；二是从其他状态-动作对开始，但能经过当前的$(s,a)$（即“visit”）。然而“visit”无法确保，因为依赖于策略和环境，不能保证从其他状态开始一定能经过所有剩下的$(s,a)$ ，所以目前只能采用较“笨”的方法，即确保从每一个$(s,a)$都能开始一个episode。
2. 实际困境：在实际中，比如在网格世界里，若有实际机器人，让它从不同的$(s,a)$出发需要搬运并设置好程序等，操作比较麻烦，理论和实际存在差距。

后续算法引出

由于exploring starts条件在实际中难以实现，我们思考能否去掉或转化该条件，答案是可以的，这需要用到soft policies，进而引出第四部分“mc without exploring stars”，并会介绍一个算法“mc absolute grady” 。