强化学习基础学习系列之model-free/planning/model-base/dyna方法总结_model base 耗时

介绍

前面说的value-base方法（除了动态规划）也好，policy-base的方法也好，都是假设没有模型而直接与实际环境交互来学习的，我们把没有用到模型的方法叫做model-free方法，但并不是说value-base和policy-base方法都是model-free的方法，value-base和policy-base是根据方法学习策略的角度划分的，model-base和model-free是根据方法有没有关于model的学习来划分的，两者划分的角度不同，只不过前面在讲value-base和policy-base方法是都是假设没有模型来说的，所以它们也是model-free的方法，下面就讨论下各类型的方法。简要说明下，model-free方法是指没有用到模型，直接与实际环境交互来学习到最优策略;planning是指已经有了模型，然后怎样使用模型来得到最优的策略;model-base是指根据环境中的经验学习模型，然后用这个模型做planning;dyna在model-base的基础上再加上直接的model-free学习。
下面的很多内容都有蛮大一部分是自己对视频的理解和总结，优缺点后面的括号是对该点为什么存在的解释，可能有很多不对或不准确的地方，如果有不同的看法或者不赞同的意见欢迎指出~

model-free 方法

• 没有模型，直接与环境交互来学到最优策略
• 包括之前提到MC/TD方法还有像REINFORCE和Actor-critic
• 优点
  
  • 不需要具体的环境模型 （sample）
  • 缓解了维数灾难（sample，函数近似）
  • 使用时做出决策的时间快 （训练好了直接用）
• 缺点
  
  • 比较难适应变化的环境，变化的环境意味着分布可能与训练时不同（训练好了直接用）
  • 优化过程可能不稳定且不收敛（函数估计，数据iid，随机梯度下降）

planning

• 已经有了环境模型，然后利用模型来得到最优策略
• 方法分类
  
  • 对整个状态动作空间做规划：value-base方法里的动态规划
  • 只对从当前状态开始的部分状态空间做规划，也叫forward search
    
    • forward seach时对所有情况都考虑：一些传统的树搜索方法，像min-max tree，A星等
    • forward search时用sample的方法：蒙特卡罗搜索，蒙特卡罗树搜索（MCTS）等
      （关于MCTS的介绍：https://www.leiphone.com/news/201702/poAxdPGhfQFrxsXS.html?vt=4）
• 优点
  
  • 非动态规划的方法能够适应环境的变化（forward search）
  • 动态规划方法使用时做出决策的时间快 （训练好了直接用）
• 缺点
  
  • forward search时所用情况都考虑的方法会遇到维数灾难的问题（暴力穷举，当然使用sample的话就可以缓解这个问题）
  • 动态规划一样不适合变化的环境（训练好了直接用）
  • 比较耗时 （做决策时才学习）

model-base 方法

• 先学模型，再对学到的模型做planning
  
• 优点
  
  • 有时直接从环境中学到值函数较难，而模型P(s’|s,a)和R(r|s,a)很容易就能用监督学习去学（gronth truth的标签很容易获得）
  • 在不易变化的环境中，如果planning时使用model-free的方法，而且模型学得比较好，那比起纯粹的model free方法则会更快
  • 在变化的环境中，而且直接能获得环境模型，貌似比起planning没什么优势，毕竟用的近似的模型，但比起纯粹的model-free方法，一旦获得了变化的信息，则能更快的调整
  • 没有真实环境模型而又想适应环境变化时，model learning + froward search可能是一种折中的方法，如果模型能获得到环境的变化，那么可能就比model-free的方法要好

• 缺点

  • 误差来源多了model拟合的误差

• 个人感觉model-base跟人类学习比较像，之前也提到过人类学习很大的不同是”先验规则+想象+记忆”，人类学习时与环境交互中学到周围环境的表征，也就是模型，planning的过程就相当于在脑海中不断地想象。
  先验规则->有一定的正确度的模型
  想象->planning

dyna方法

• model-base learning同时直接model-free leanring，整合所有信息
  
  一种学习算法，dyna-q：
  

关于使用sample的forward search方法的理解

forward search + samle相当于用model-free的方法解决一个部分MDP的问题，它所关注的是在当前状态下应该采取什么动作是最好的，而不是关注整个状态空间中应该采取什么策略是最优的。


它们的过程类似于也是在部分MDP问题中采用策略迭代。
对于蒙特卡罗搜索 ：

先是估计一个随机策略的价值函数 （也就是simulation policy）,注意的是不管其他状态这个价值函数是否准确，但当前状态上是一定准的，这个部分MDP关注的是当前状态，然后做一次策略提升，也就是greedy的操作选择最好的动作，可以想象新的策略对当前状态来说只是做了一次更新，所以在当前状态上就比simulation policy好一些，如果simulation policy不好的话，那么更新后的策略效果也不会很好因为只做了一次更新，如果simulation policy在当前状态上本来就比较好的话，那么更新后的策略在当前状态上也会更好。所以simulation policy的选择很重要。
对于蒙特卡罗树搜索 ：



它更像是蒙特卡罗搜索中做策略更新做多几次，selection相当于在做策略提升，而expansion,simulation 和backpropation则是在做策略估计。随着策略迭代的进行，树上的节点的值越来越趋向于当前策略的值函数。

各种机制的总结

感觉各种优缺点写的优点乱，可能把它们分解成各种机制好一些,顺便把之前的一些机制也总结下吧。

• bootstrap
  
  • 类似于动态规划里的最优子结构
  • 优点：收敛快，提高稳定性(减小variance)
  • 缺点：可能会引入bias导致不收敛
• sampling（sample）
  
  • 用采样来代替暴力枚举
  • 优点：缓解了维度灾难的问题，计算量小了
  • 缺点：引入variance导致算法不稳定
• advantage function
  
  • 用归一化的形式
  • 优点 ：减小算法方差
  • 缺点 : 增加计算量？
• function approximation
  
  • 把状态和动作当作是依据信息，能够根据它们得到价值函数
  • 优点 ：缓解了维度灾难问题，引入了监督学习
  • 缺点 ：监督学习的iid假设往往不成立
• batch gradient descent
  
  • 用更多的样本作为输入计算梯度
  • 优点 ：缓解了iid问题，增加了算法的稳定性
  • 缺点 ：增加了计算量
• off-policy
  
  • 解决控制问题时样本来自任意的策略
  • 优点 ： 能够更好地利用数据(任何策略的数据都可以使用)
  • 缺点 ：类似于importance sampling的方法会大大地加入方差
• fix target
  
  • 在优化的一段时间内固定目标函数
  • 优点 ：让算法更好地收敛(有固定的目标函数)
  • 缺点 ：未知
• forward search
  
  • 解决部分MDP问题，只关注从当前状态开始的问题
  • 优点 ：更能适应变化的环境
  • 缺点 ：lazy-learning式的学习会增加使用策略时的时间
• model learning
  
  • 学习实际环境模型的一个近似模型
  • 优点 ：引入监督学习且grown truth的标签容易得到，能增加不用model的算法的planning的特性
  • 缺点 ：增加了算法的误差来源 （模型的拟合误差）

首先先有一些基本的算法：动态规划（DP），policy-gradient的公式（PG）
然后可以看成 ：
MC = DP + sampling （+function approximation）
TD = DP +sampling + bootstrap （+function approximation）
MC-PG = PG + sampling
ActorCritic-PG = PG + sampling + bootstrap + function approximation
MCTS = forward search + sampling

使用哪一类的方法取决于具体的应用场景，要考虑几个因素：
1. 有没有真实的环境模型可用
2. 环境是否在不断变化的
3. 需不需要一边学一边做决策
4. 存不存在维数灾难问题
5. 计算耗时如何
6. 价值函数是否难得到
……