5、Algorithm propertiesTD算法与蒙特卡洛算法比较尽管TD learning和MC learning都是model-free方法与MC learning相比TD learning的优点和缺点分别是什么呢TD/Sarsa learningMC learning在线学习时差学习是在线的。在接收到奖励后它可以立即更新状态/动作值。蒙特卡洛学习是离线的。它必须等待直到一整个回合episode完全收集完毕后才能进行更新。持续任务由于时差学习是在线的因此它可以处理episodic任务和continuing任务。一次性任务由于蒙特卡洛学习是离线的因此它只能处理具有终止状态的episodic任务。Bootstrapping时差学习自提升因为值的更新依赖于对该值的先前估计。因此它需要初始猜测。非Bootstrapping蒙特卡洛学习不是自提升因为它可以直接估计状态/动作值无需任何初始猜测。低方差时差学习的估计方差较低因为涉及到的随机变量比较少。例如Sarsa需要Rt1,St1,At1R_{t1},S_{t1},A_{t1}Rt1​,St1​,At1​。高估计方差为了估计qπ(st,at)q_\pi(s_t,a_t)qπ​(st​,at​)我们需要Rt1γRt2γ2Rt3…R_{t1}\gamma R_{t2}\gamma^{2}R_{t3}\ldotsRt1​γRt2​γ2Rt3​…的样本。假设每个回合的长度为LLL。有∣A∣L|A|^L∣A∣L种可能的回合。Bootstrapping方法bootstrapping的意思就是说我之前对一个状态的state value已经有了一个初始的猜测然后基于这个初始的猜测再加上一些新的信息我可以得到一个新的猜测。MC learning它不是一个bootstrapping它就是直接根据当前的episode计算出来return我就用这个return来直接作为action value或者state value的这样一个估计值这里边不涉及到之前的一些估计值。另外一个性质就是TD它的估计的variance相对来说是比较小的为什么呢就是因为在算法过程当中它涉及到的随机变量是比较少的。那因为这个比较少所以相对来说我如果只用一次这个采样那它的variance是比较低的。但是相反MC learning它会涉及到非常多的variable因为它需要一个episode这episode第一步会有一个reward第二步会有一个reward第三步就是会有很多个随机变量进来然后我有很多个随机变量那我只用一次的采样相对来说这次采样它的variance会比较高一些。举一个比较直观的例子假如说我现在这个episode它的长度是100每经过一个state假如说有5个action可以来做选择然后那我一共实际上是有51005^1005100个episode。也就是我从当前出发进行随机的采样可能会有51005^1005100个episode但是我现在只用了一个episode的数据来进行估计你可以想象它的variance会是比较大的。另外一个方面就是随机变量实际上有两个性质第一个是variance第二个是它的expectation或者是mean。虽然这个TD算法它的variance是比较小的但是它的mean或者expectation是有bias的。为什么呢因为它是bootstrapping它依赖于初始的估计如果初始的估计不太准确的话那么这个不准确的估计会进入到这个估计的过程中造成bias。当然随着越来越多的数据进来会逐渐把bias给抵消掉直到最后能够收敛到一个正确的估计值。相反MClearning虽然有比较高的variance但是因为它不涉及任何的初始值它的expectation实际上就直接等于它真实的action value或者是state value所以它是无偏估计。刚刚我们介绍了TD learning的基本的性质下面我们把TD learning和之前我们介绍的基于蒙特卡洛方法的这个MC learning加以比较那MC learning是我们这个课程当中介绍的第一个model-free的强化学习的方法然后TD learning是我们介绍的第二个那它们分别有什么优劣势呢我们来看一下 我们一个一个讲它们的优劣势这里边值得指出的一点其实这里边我除了TD之外我还写了一个Sarsa这个Sarsa是什么呢是我们接下来马上要讲的一个算法它可以直接来估计action value然后这个Sarsa和我们之前讲的TD算法它的表达式基本上是一模一样的所以我就直接拿过来也比较一下 第一个性质是什么呢第一个性质是TD算法它是一个online在线的 什么意思呢就是说我现在得到了一个reward我跳到了下一个状态我就立刻可以用这些信息来更新我当前的一些估计状态的值但是相比之下这个MC learning它是offline 什么意思呢就虽然我现在在采样我得到了一些采样但是我不可能立刻用 为什么呢我必须要一直采下去等到这个episode结束之后我才能计算从当前的s然后到最后它的这个return是多少然后我用那个return来作为一个估计值也正因为TD它是online的所以它能够来处理这种continuing task当然它也能够处理episodic task所以两类都可以continuing task是什么呢就是这个task它不会停止它会一直持续下去那这时候我要更新的话我必须是在线的更新因为我不能等它停下来当然实际当中是不存在一直持续下去的任务的但是你可以想象它是一个非常长的任务然后MC learning因为它是offline的所以它只能处理这个episodic task也就是必须要等到它停止之后我才能去用这个MC的算法所以在这两个方面来说TD learning还是略胜一筹的下面我们来接着看 TD它的另外一个性质就是它是bootstrapping bootstrapping的意思就是说我之前对一个状态的state value已经有了一个初始的猜测然后基于这个初始的猜测再加上一些新的信息我可以得到一个新的猜测那么MC learning它不是一个bootstrapping为什么呢它就是直接根据当前的episode然后我计算出来return我就用这个return来直接作为action value或者state value的这样一个估计值那这里边不涉及到之前的一些估计值另外一个性质就是TD它的估计的variance相对来说是比较小的 为什么呢就是因为在算法过程当中它涉及到的随机变量是比较少的比如说从当前的状态出发然后我会得到一个采样是关于这个reward的一个采样 然后会得到另一个采样是关于下一个状态的采样 如果是Sarsa的话它还会对下一个时刻的action再进行采样但是总的来说所涉及到的随机变量是比较少的那因为这个比较少所以相对来说我如果只用一次这个采样那它的variance是比较低的但是相反MC learning它会涉及到非常多的variable为什么呢因为它需要一个episode 这episode第一步会有一个reward第二步会有一个reward第三步就是会有很多个随机变量进来然后我有很多个随机变量那我只用一次的采样相对来说这次采样它的variance会比较高一些那我们举一个比较直观的例子假如说我现在这个episode它的长度是L假如说这个长度是100 然后我每经过一个state假如说有5个action可以来做选择然后那我一共实际上是有5的100次方个episode也就是我从当前出发 我进行随机的采样可能会有5的100次方这样个episode但是我现在只用了一个episode的数据来进行估计你可以想象它的variance会是比较大的另外一个方面就是随机变量它实际上有两个性质第一个是variance第二个是它的expectation或者是mean虽然这个TD算法它的variance是比较小的但是它的这个mean或者expectation它是有bias的为什么呢就是因为它是bootstrapping它依赖于初始的估计 如果初始的估计不太准确的话这个不准确的估计会进到这个估计的过程当中造成bias当然随着越来越多的数据进来 这个会把这个bias给抵消掉直到最后能够收敛到一个正确的一个估计值那么相反这个MC learning虽然它有比较高的variance但是因为它就是不涉及到任何的初始值所以我对它求expectation 那么它的expectation实际上就直接等于它真实的action value或者是state value 所以它是无偏估计