（三）表格型方法

当看到这一章名字的时候，应该首先考虑到三个问题：
  1）这里的表格指的是什么？
  2）表格型方法是用来解决什么问题的？
  3）表格型方法中具体有哪些方法？
  随着后面的介绍，将陆续解开神秘的面纱。
  前面已经介绍了马尔可夫决策过程，可以使用<s,a,p,r>这个四元组表示。而且从马尔可夫决策过程中，我们推导出了贝尔曼期望方程。之前也介绍过有模型和免模型的概念，区别在于是否已知状态转移和奖励函数。大多数情况最开始是没有和现实世界有接触的，所以我们更加关注于免模型，后面的讨论都是基于免模型展开。
  在上一章介绍过，我们使用价值函数V来评价策略的好坏。用Q函数(也就是状态动作价值函数)来判断在什么动作下能够拿到最大奖励。这个奖励是个总体的奖励，是后面状态的累加和。要清楚的意识到，奖励的本质也是价值。
从Q函数的定义中知道，它就是在某一个状态下执行某一个动作的价值。设想如果我们能够记录下来所有的Q函数值，也就是知道了一个状态下执行每一个动作的价值有多少。那不是可以选取最高价值的动作了吗？这不就是最优策略！把所有的状态对应所有的动作的价值都记录下，就会形成一张表格，这就是Q表格。也是本篇主要的研究对象。当然最开始生成的Q表格因为与环境交互少，效果不一定好。所以Q表格内容也是在不断优化更新的。Q表格中纵轴是状态，横轴是动作
  这里解释一个问题：为什么可以用未来的总收益来评价当前动作的好坏？
  首先想想强化学习最根本的目标就是回报最大化。回报也是分为两部分：当前回报和未来回报。有的人会认为未来回报都不重要，直接抹杀。但举这样一个例子：红灯情况下，普通车如果直接通过，它的收益会比较低。因为未来不会有什么大的收益奖励它。但如果是消防车，虽然闯了红灯，但把病人及时送到医院收益会很高。所以当前状态有可能是受未来收益影响，所以要考虑这点。也不总是这种情况，像股票这类的希望即时收益。所以要加上折扣因子。
  再次重申下Q表格数据的意义：在状态S下采取动作a的总回报
  现在的主要问题变成了：在没有马尔可夫决策过程的模型情况下如何能估计给定策略的价值。求给定策略的价值，是不是有点儿熟悉？这不就是上一张的马尔可夫奖励做的事情吗？所以求解方法有三种迭代方法：蒙特卡罗法、动态规划法、时序差分法。下面来详细介绍一下它们吧！
  1）蒙特卡罗法(Monte Carlo，简称MC)
  蒙特卡罗(其实有的时候也叫蒙特卡洛，傻傻分不清，知道这个意思就行了)。它的思想非常简单，就是采样取均值。之前介绍过，价值是当前状态下的累计回报。如果取样到很多轨迹，然后取平均值，数量足够多的情况下，大数定律告诉我们这个是可以来近似价值的。
  先来看看常规的MC：

  看了上面这个图，很明确吧。不需要多说了。但总觉得这种好像有点儿过于粗暴，我们希望迭代一次就能更新一次系数。所以提出了增量式MC：

  增量式MC，基于普通MC，相当于把经验均值转换成增量均值。具体的推导过程如下图所示：

  有的时候会为了简便，把分数替换成学习率α，写成下面这个样子：

  了这种求价值函数的方法，再来看看他的优缺点吧！
  优点：免模型，不需要自举不断更新(因为没有估计量都是测量的量)
  缺点：必须完整完成一次轨迹采样，适用情况受限。比如对于轨迹无终止的情况就不适用。
  可能会有疑惑，==怎么看出来是免模型的？==其实这个很好判断，之前说过有模型和免模型最大的差距在于是否对环境建模。具体一点儿就是有没有奖励函数和状态转移函数。从上面的表达式上看，没有的就是免模型。下面的就是有模型。
  2）动态规划(自举，用于有模型)：
  数学表达式如下：

  动态规划的实现原理是基于贝尔曼期望备份，用上一时刻的v来更新当前的v。贝尔曼期望备份图如下：

  注意s’和s与之前的不一样了，这里面的s’是上一时刻而不是下一时刻。从表达式中可以看出来用两次加和，算了两次期望。在期望的计算中，更新了相关的所有状态。这点和蒙特卡罗是不同的，蒙特卡洛只更新了一条轨迹上所有的状态
  3）时序差分(Temporal-Difference，简称TD)：
  回想一下，上一章对于TD的引入。是因为MC要完整的采样一条轨迹，而有时这样的条件是没有的。我们希望状态更新一次就能优化一遍价值。这里取决于一种思想：下一个状态的价值是可以不断地取强化影响上一个状态的价值的。这里依旧需要进行一次采样
  先给出TD的更新表达式，如下：

  首先可以明确，TD适用的情况是免模型的。因为没有状态转移函数和奖励函数
  来看一看它是怎么实现更新的，主要是关注一下α后面括号里的内容，
  前面的内容叫做是估计回报，也叫做时序差分目标：

  括号内的整体叫做时序差分误差：

  估计回报的推导过程如下图：

  它的思想也非常简单，通过对V的更新不断减少时序差分误差。当时序差分误差减少到可以接受的值时就结束。
  有一个问题需要注意：时序差分目标其实是一个估计值，因为每一个v都是估计出来的，并不是真实的V(Π)(???)
  的TD实现1步就可以更新价值函数，这种叫TD(0)。当然也可以做调整，几步之后再更新价值函数，也就是TD(n)。区别就在于G(t)的表达上：

  当然如果n趋向于∞的话就会退化为MC了(相当于完成了一次轨迹采样了)
  TD优点：
    1）一步/几步就可以更新，效率高
    2）可以从那个不完整序列进行学习(MC必须是完整)
    3）可以在没有中止环境下学习
  时序差分可以称为是MC和DP的结合版。因为其中既有采样，又有自举。时序差分 = 采样(R(t))+自举(后面的回报)
  ==那以上三种方法有什么关系呢？==其实如果以之前说过的备份图来代表一个过程的话，TD代表两个状态转换那一段、MC代表从一个状态直到最终的一条、动态规划是从一层的状态转移到下一层的状态。如果没明白，请看下面这个图：

  我们来理理思路，以上主要介绍了两种方法：MC和TD，两种方法都是来求解价值的。也就是策略迭代中的一部分。那什么是策略迭代呢？

  策略迭代：
  如上图所示，策略迭代就是在策略和价值中循环迭代。先评估策略的价值，然后选价值最大的作为策略(这里的贪心就是让总价值最大，不是单步的贪心)。
  数学化的表达就是：

  从上面这个表达式来看，==是针对于有模型的。那没有模型的咋办呢？==这就涉及到广义策略迭代
  广义策略迭代：不知道奖励函数和状态转移时(无模型情况)，如何进行策略的优化
  它的实现思想就是把状态价值变成动作价值，如下图

  如果这种方法行得通的话，一个重要的问题就是：在不知道奖励函数和状态转移时，怎么完成Q和Π之间的交互？方法是把之前对于V的估计要变成对Q的估计。
  广义的策略迭代对策略迭代的策略评估部分进行了修改，用MC的方法代替DP的方法去估计Q函数。
  复习：策略迭代包括策略评估和策略改进两部分
  那现在问题就是 如何用MC来进行估计Q函数？
  这里涉及到一个假设，也算是给Q函数一个初始化值。假设回合有探索性开始，这个保证了所有的状态和动作都能够在无限步执行后被采样到。还记得上面的Q表格吗！现在是MC的方式，就可以执行每一条轨迹获得价值后填到Q表格中。所以设计算法的时候核心思想就是使用MC来填充Q表格。算法过程如下：

  上面这个算法只是说了需要探索性。但没有明确具体探索的方式，这里介绍一下常见的探索方式：ε-贪心(ε-greedy)探索。来看看这个的思想，现在我们有了Q函数，要利用Q函数来改进策略。但MC是要实际做动作的，也就是说要根据Q函数确定动作。之前说过动作的选择有探索和利用两种思想，从Q函数确定动作就是利用，在Q函数不是很好的时候利用是没有效果的，更希望使用探索来做。ε-贪心就是通过设置ε值。1-ε的概率选择Q函数决定动作，ε的概率选择随即动作(探索)。不过Q函数不断完善时，ε值会减少。由Q函数决定的程度会增大。
  使用MC+ε-贪心形式时，可以保证Q函数是单调的改进的，具体的证明过程如下：

  将MC和ε-贪心结合，就会得到以下的算法伪代码：

  既然MC可以，那TD应该也可以。而且TD有低方差、在线学习、不完整序列学习这几个优点。用TD估计Q表格，这样也是好处多多。下面来介绍两种TD框架来估计Q函数的方法吧。
  在此之前我们先回顾一下TD的数学式吧：

  在介绍两种方法之前，先做一点儿基础知识学习：关于同策略和异策略。
  同策略：学习的智能体与和环境交互的智能体是同一个
  异策略：学习的智能体与和环境交互的智能体不是同一个
  所以对于同策略和异策略最大区别就是优化的对象不同
  1）Saras：同策略时序差分控制
  Saras做出的改变很简单，就是V变Q，也就是这样：

  按照前面的，时序差分目标：

  时序差分误差：

  看这个表达式，有了哪几项我们可以进行更新：S(t) 、A(t)、R(t+1)、S(t+1)、A(t+1)。这些都是可以根据一步更新拿到的。这五项练起来就是SARAS,也是名字的由来。
  TD有N步更新，自然可以把这种思想迁移过来，形成n步Saras，具体的算法如下：

  2）Q学习：异策略时序差分控制
  Saras是一种同策略算法，优化的是它执行的策略。而Q学习用异策略优化目标函数。Q学习中有两种策略：行为策略和目标策略。。如果还是不明白异策略，那就看看下面这幅图：

  行为策略与环境交互，采集大量的经验。而目标策略从这些经验中进行学习，而且因为是完全独立，所以目标策略可以任意选择，直接选最优的，不需要任何顾虑。那什么是有顾虑的呢？以躲避悬崖为例，在异策略情况下目标策略进行优化时是不管行为策略的行为的，哪怕行为策略掉进了悬崖，但目标策略得到了很大的回报，也是可以选择的。但对于同策略来说，它是一体的，要保证自己既能优化又能探测，所以会刻意避开悬崖，保持在安全范围内。

  目标策略Π直接在Q表格上使用贪心策略，状态的策略就是选最好的状态动作。
  现在了解到Q学习每一个动作都是通过argmax选出来的，所以可以得到下式(代表就是单步的价值)，

  也可以把它换成增量学习方式，数学式如下：

  从上面这个式子中看出，Q-learning更新一次，需要四个变量:S(t)、A(t)、S(t+1)、R(t+1)。这个比之前的少了一个A(t+1)。原因在于，而Sarsa中的A’是下一步骤一定会执行的动作，而Q-learning默认的下一个动作不是通过行为策略来选取的。而是直接从Q表格中选择的是最大值，只要保证这个动作的价值最大就可以。
  现在来讨论一下Q学习和Sarsa的区别，首先它们的目标不同，下面这张图可以说明(上面是sarsa，下面是Q学习)：

  学到这儿，这一章已经接近尾声了。这章我们学习了表格型方法，学习了Q表格，并在此基础上学习了基于Q表格的多种求解策略价值的方法。并将策略迭代推广到广义的策略迭代，用TD改进了MC。像下面这张图一样：

  老规矩，课后题来喽：


因作者水平有限，如有错误之处，请在下方评论区指出，谢谢！</s,a,p,r>