1、introduction
第7章节，讲了PG，从episode经验学习到 策略 policy 之前的章节，讲了从episode 经验学习到 价值函数
本章，从过去经验学习到环境模型
通过规划的手段，构建值函数或者策略
- Model-free
- 没有模型
- 从经验中学习，得到价值函数
- Model-based
- 有模型
- 根据模型规划价值函数
本讲指出解决这类问题的关键在于“前向搜索”和“采样”，通过将基于模拟的前向搜索与各种不依赖模型的强化学习算法结合，衍生出多个用来解决类似大规模问题的切实可行的算法，如：Dyna-2算法之类。
2、Model-based reinforcement learning
当学习价值函数或策略变得很困难的时候，学习模型可能是一条不错的途径，像下棋这类活动，模型是相对直接的，相当于就是游戏规则。
- 优点
- 用监督学习高效实现建模
- 推断模型不确定性
- 缺点
- 第一步建模，第二步构建价值函数，两个过程带来双重的估计误差
模型，我们要做什么
Model learning
模型实例
- Table lookup model
- Linear expectation model
- Linear Gaussian model
- Gaussian Process model
- Deep Belief Network model
例子 Table lookup example
Planning with a model
Planning with an inaccurate Model
显然，模型的准确性，直接制约了Model-based RL 性能的上限
Solution：
- 模型错误的情况，直接model-free RL，并且从env中采样
- 明确模型不确定性的原因
3、integrated architectures
本节将把基于模型的学习和不基于模型的学习结合起来，形成一个整合的架构，利用两者的优点来解决复杂问题。从两种渠道进行采样 - Env 真实MDP - Model 估计MDP
- 集成学习和规划 Dyna
Dyna
Dyna是并列、综合与model-free、model-based的学习方法
- Model-free RL
- 无模型
- 从真实环境Env采样，学习价值函数
- Model-based RL
- 从真实环境Env中学习，建模Model
- 从Model虚拟采样，规划价值函数
- Dyna
- 从真实环境Env中学习，建模Model
- 根据Env 和 Model采样，同时学习 并 规划 价值函数
Dyna-Q 算法框图
a,b,c,d,和e都是从实际经历中学习，d过程是学习价值函数，e过程是学习模型。 在f步，给以个体一定时间（或次数）的思考。在思考环节，个体将使用模型，在之前观测过的状态空间中随机采样一个状态，同时从这个状态下曾经使用过的行为中随机选择一个行为，将两者带入模型得到新的状态和奖励，依据这个来再次更新行为价值和函数。
类似监督学习里，用数据增强，来丰富数据集。
- 例子 将规划引入RL之后，规划比学习具有更小的抖动和噪声，稳定性好
Dyna-Q with 不准确模型
由于Dyna综合了实际和模拟两种情况，在实际环境改变时，错误的模型会被逐渐更正。
- 环境剧烈改变
我们可以发现，不同算法对环境改变的适应性，相差悬殊
- 环境柔和改变
Q 算法，奖励函数里 鼓励 episode 探索新的状态
4、simulation-based search
搜索相对于规划，区别之一就是，不搜索整个空间，用采样的方法来优化
Forward search
两个重要特征：
- 不求解整个MDP，以当前状态为起始状态
- 使用基于采样的规划
两点都可以显著降低计算量
步骤：
MC search
Simple MC search
MC tree search (evaluation)
对于真正的MC tree search，Q值的构建，包含了所有状态s和动作a 估计步骤：
MC tree search (Simulation)
例子：围棋Go
Position evaluation in go
MC evaluation in go
MCTS 步骤：
- 第一次迭代：如下图所示，五角形表示的状态是个体第一次访问的状态，也是第一次被录入搜索树的状态。我们构建搜索树：将当前状态录入搜索树中。使用基于蒙特卡罗树搜索的策略（两个阶段），由于当前搜索树中只有当前状态，全程使用的应该是一个搜索第二阶段的默认随机策略，基于该策略产生一个直到终止状态的完整Episode。图中那些菱形表示中间状态和方格表示的终止状态，在此次迭代过程中并不录入搜索树。终止状态方框内的数字1表示（黑方）在博弈中取得了胜利。此时我们就可以更新搜索树种五角形的状态价值，以分数1/1表示从当前五角形状态开始模拟了一个Episode，其中获胜了1个Episode。这是第一次迭代过程。
- 第二次迭代：如下图所示，当前状态仍然是树内的圆形图标指示的状态，从该状态开始决定下一步动作。根据目前已经访问过的状态构建搜索树，依据模拟策略产生一个行为模拟进入白色五角形表示的状态，并将该状态录入搜索树，随后继续该次模拟的对弈直到Episode结束，结果显示黑方失败，因此我们可以更新新加入搜索树的五角形节点的价值为0/1，而搜索树种的圆形节点代表的当前状态其价值估计为1/2，表示进行了2次模拟对弈，赢得了1次，输了1次。第二次迭代结束。
经过前两次的迭代，当位于当前状态（黑色圆形节点）时，当前策略会认为选择某行为进入上图中白色五角形节点状态对黑方不利，策略将得到更新：当前状态时会个体会尝试选择其它行为。
- 第三次迭代：如下图，假设选择了一个行为进入白色五角形节点状态，将该节点录入搜索树，模拟一次完整的Episode，结果显示黑方获胜，此时更新新录入节点的状态价值为1/1，同时更新其上级节点的状态价值，这里需要更新当前状态的节点价值为2/3，表明在当前状态下已经模拟了3次对弈，黑方获胜2次。
随着迭代次数的增加，在搜索树里录入的节点开始增多，树内每一个节点代表的状态其价值数据也越来越丰富。在搜索树内依据Ɛ-greedy策略会使得当个体出于当前状态（圆形节点）时更容易做出到达图中五角形节点代表的状态的行为。
- 第四次：如下图，当个体位于当前（圆形节点）状态时，树内策略使其更容易进入左侧的蓝色圆形节点代表的状态，此时录入一个新的节点（五角形节点），模拟完Episode提示黑方失败，更新该节点以及其父节点的状态价值。该次迭代结束。
- 第五次迭代：如下图，更新后的策略使得个体在当前状态时仍然有较大几率进入其左侧圆形节点表示的状态，在该节点，个体避免了进入刚才失败的那次节点，录入了一个新节点，基于模拟策略完成一个完整Episode，黑方获得了胜利，同样的更新搜索树内相关节点代表的状态价值。
随着迭代次数增加：
- 当个体处于当前状态时，其搜索树将越来越深，那些能够引导个体获胜的搜索树内的节点将会被充分的探索，其节点代表的状态价值也越来越有说服力；
- 搜索树内的节点越来越多，代表着搜索树外的节点将逐渐减少，少量的随机行为并不会影响个体整体的决策效果。
MCTS 优点
- 选择性好，好的结果被优先选择
- 动态的评估状态（立足当前状态），不是动态规划（没有离线的评估整个状态空间）
- 使用采样方法，不在全部状态空间搜索，避免了维度灾难
- 采样所以具有黑盒特性，对黑盒模型同样有效
- 可以异步、并行计算，高效
TD search
- simulation-based search
- 自举特性Bootstrapping， TD而不是MC
- MCTS 将 MC control 应用于 子MDP from now
- TD search 将 Sarsa 应用于 子MDP from now
MC vs TD search
步骤
Dyna-2
与Dyna-Q不同，dyna-Q只有一套参数，虽然经验有2个source（env和model）
Dyna-2 特征权重来源于两部分
- Long-term memory
- 长期记忆 从真实经验中获取， 方法使用TD learning 通用的知识，可以应用于任何episode
- Short-term（working） memory
- 短期记忆 从仿真经验中获取， 方法用TD search 特定的局部知识，对当前状态有效
- 总的价值函数 = 两部分之和
显而易见，将仿真产生数据应用于搜索，并将搜索结合到学习中，增强了数据，会产生显著的提升
