这章给出了关于model-free方法和model-based方法的一个统一观点，即将两者的思路结合起来解决问题：
model-based 方法训练采用基于model进行planning的方法，通过向后迭代(backup)来更新value function；而model-free 方法训练采用从环境抽样(sampling)来进行value function的learning，具体也是使用后续的state(action)-value来backup当前value function。两者之间同时有很多相似点，比如都会update value function，都采用backup的策略update等。可见两者的区别主要在于model的维护与否，当然这就是结合起来两种方法的训练策略。
Models and Planning
我觉得这里理解sample model就够了，sample model也是本章剩下的部分使用的planning方法的基础——从采样得到随机model进行planning。
首先理解distribution model和sample model之间的关系：
Given a state and an action, a model produces a prediction of the resultant next state and next reward.
distribution model: produce a description of all possibilities and probabilities for next state and next reward.
sample model: produce just one next state and action by sampling before.
distribution model就是在第四章使用的MDP，sample model就是利用采样得到next state，然后利用这些采样经验组成的model。
但是不管哪种模型，更新value function的方法都是一样的，即通过planning的方法来得到优化(optimal)的policy。但是从planning得到policy的具体算法还分为两类：
state-space planning：通过产生模拟的经验，通过模拟action让一个state转换到另一个state，来更新value-function从而得到优化的policy
plan-space planning：通过在plans的空间中寻找优化的plan，通过从一个plan切换到另一个plan，从而更新value-function，得到优化的policy
后者在随机序列决策问题(stochastic sequential decision problems)中应用起来比较困难，所以一般都是采用前者。
state-space planning的优化流程图：
接着给出使用sample model更新value function的伪代码，注意我们一般不会只采用模型来更新(Priority Sweeping除外)，所以这个算法会在本章后续部分和Q-Learning等model-free方法一起来完成更新:
Dyna: Integrating Planning, Acting, and Learning
这一部分提出一个重要的算法:Dyna-Q。在我们讨论这个算法之前，先来看一下model planning是如何融入之前的model-free算法的，即indirect reinforcement learning方法是如何提升value function的update的：
可以看到通过实时的经验(experience)，学习产生了model，然后通过planning也对value function进行了更新，这种方法叫做on-line planning。
好了，我们接着来看一下Dyna算法的通用体系：
右边部分阐述了model-planning的工作原理，首先需要通过实际的经验来学习得到一个model，然后剩下的和上面提到的state-space plan一致：通过model模拟experience，然后进行backup。
最后给出Dyna-Q的算法伪代码：
这里有一个使用不同的model-planning step的示例：Example 8.1 Dyna Maze
When the Model Is Wrong
如果我们正在学习的任务，它所对应的environment是变化的，那么我们学习到的model很有可能和environment之间是有差别，这一部分来探讨一下如果模型出错，Dyna方法的性能。
这里引入一种Dyna-Q的优化算法：Dyna-Q+。说优化，其实主要是Q+方法引入了一种启发式exploration：通过给sample得到的model中的state-action对添加了一个timestamp。当选择action的时候，那些current_time-timestamp值比较大的state-action说明这种state-action已经很久没有选中了，那么我们模型中关于这对state-action的动态特性很有可能已经过时了，即此时模型有可能已经和实际environment有偏差了，所以需要给这些state-action的reward附加补偿：r+k*sqrt(current_time-timestamp)。这种启发式的exploration可以有效的帮助policy的学习过程跳出局部optimal policy，同时对于变化的environment适应性更强。
关于Dyna-Q和Dyna-Q+在变化的environment中的性能，可以参考Example 8.2 Blocking Maze Example 8.3 Shortcut Maze
Prioritized Sweeping
可以看到前面建立model的时候，是把episode随机产生的state-action”喂”(feed)进model，同理从model模拟环境进行planning的时候，也是随机产生state-action的。那么我们不禁思考：可不可以优先更新那些“更新效果更好”的state-action？
答案是肯定的。因为有的state-action可能在实际的优化路径中基本不会出现，花费资源来更新这些state-action，对其他有用的state-action或者说整体所有state-action对的更新和策略的优化基本是0收益的。所以这部分提出了一种Prioritized Sweeping的方法，维护一个优先队列，只有那些更新target足够大的state-action才会添加入队列，同时队列也是按照更新概率来排序的，即abs(target) = priority。
同时Prioritized Sweeping算法的value function更新是采用backward focusing方法的。即更新的时候是利用当前Q来更新前导previous-Q。这是一种启发式的思路(P137)：
Only an update along a transition into the state just prior to the goal, or from it, will change any values. So search might be usefully focused by working backward from goal states. Of course, we do not really want to use any methods specific to the idea of “goal state.” In general, we want to work back not just from goal states but from any state whose value has changed.
理解了算法的基本原理，下面给出相应的伪代码：
注意Prioritized Sweeping算法并没有在sample阶段使用Q-Learning或者其他model-free算法来更新，原因上面也讲了，因为更新随机采样得到的state-action会引入不必要的value更新，浪费计算资源。
关于Prioritized Sweeping的例子Example 8.4 Prioritized Sweeping on Mazes
Expected vs Sample Updates
可以通过三个问题将目前我们已经学过的或者提到过的强化学习算法分为7类(理论上应该可以分为8=2^3类，但是有一种分类并没有对应具体的算法)：
(1)更新的action-value还是state-action
(2)估计value使用的是target-policy还是greedy policy
(3)更新使用的是expected还是sample update
对应的具体算法如下:
expected update使用的是bellman equation：
sample update使用的是n-step的更新公式，以Q-Learning为例：
在value估计过程中，两种方法的误差性能，可以参考Figure 8.8
Trajectory Sampling
在采样更新中，不可避免需要讨论采样方法。可以像第四章的DP方法那样，从第一个state一直顺序更新到terminal state，即完整的更新整个set of state；也可以像第六章的Temporal Difference方法那样，以Sarsa方法为例，使用policy来选择并更新action-value。
后者即这部分要讲的trajectory sampling抽样算法。trajectory sampling的思路和优先扫描(Prioritized Sweeping)的一致，都是考虑到均匀更新会浪费大量的计算资源，只按照一定的策略选择更新value，属于启发式的更新策略。
关于均匀抽样和trajectory sampling的算法性能比较，可以参考Figure 8.9
Real-time Dynamic Programming
real-time DP可以看做DP算法的trajectory sampling升级版：RTDP updates the values of states visited in actual or simulated trajectories by means of expected tabular value-iteration updates.
RTDP是一种典型的异步DP算法，异步DP算法在第四章提到的：
Asynchronous DP algorithms are not organized in terms of systematic sweeps of the state set; they update state values in any order whatsoever, using whatever values of other states happen to be available.
RTDP算法适用于一类stochastic optimal path problems(随机最优路径问题)，这类问题满足以下4个性质：
(1)每一个goal state的初始value都是0
(2)there exists at least one policy that guarantees that a goal state will be reached with probability one from any start state(懂意思但是翻译不好@_@)
(3)所有从非goal state进行的state转换，得到的reward都是负值
(4)所有的state的初始value都要不小于最终的optimal value，最简单的方法就是将initial value都设置为0
这种问题优化目的不是为了找到最高的reward总和，而是为了得到最少的cost。优化policy，使得达到goal state的负值reward和最小，即最小化cost。
和传统DP相比，RTDP收敛所需的update次数更少，因为RTDP是随着value function达到最优时，选择action的policy也同时达到最优。
但是传统的DP方法需要等待value function更新误差小于一定值才会停止更新，其实在value function停止更新前，policy其实已经达到最优了，但是如果附加程序来检查policy是否达到最优会需要相当多的额外计算。通过这点也可以看出RTDP的收敛是快于传统DP的。
Planning at Decision Time
这里提出了一种使用planning的新方法，即在给定current_state时，利用当前学习得到的model来预测并实施action，这种方法叫做planning at decision time。
这章前面的内容提到的算法，都是在后台运行planning算法，来提升整体的value function训练性能。关于两种算法，一般根据不同的情形有不同的用法：
如果对时间要求不是很高，比如棋类游戏，每一步都有几秒或者几分钟时间来思考，那么适用planning at decision time可以在这段时间向前plan几十步，选择一个合适的action，而且因为实际的state-action对很多，所以出现重复的概率比较低，相应的资源浪费也就没那么严重；
如果对时间要求比较高，那么最好在后台运行planning算法来优化policy，使得整体的value function得到提升。
Heuristic Search
使用decision time planning的state-space planning方法中，最常见的就属Heuristic Search(启发式搜索)了。
启发式搜索可以看做一个多步的greedy policy，启发式搜索算法的工作流程：
每当遇到一个状态，就以该状态为根节点，所有可能的后续state和action为leaf来创建一棵树，然后使用backup的方法计算每个节点的value，并greedy的选择action。当一个状态的planning结束之后，丢弃所有的备份值。
启发式搜索的优点主要是由decision time带来的，使得policy可以集中资源来考虑当前状态下的决策，比如在棋类游戏中，这种方法可以从当前状态开始存储更多的未来状态情况，可以更加有效的利用内存。
Rollout Algorithms
rollout algorithms是一类针对backgammon的算法，该算法是基于Monte Carlo的decision time planning算法，通过在当前state下进行Monte Carlo模拟采样来进行state的update，当然并不保留backup的值。
Rollout算法的目标是基于当前状态和给定的rollout-policy来进行planning，做出决策之后则抛弃使用的估计值，即计算得到的backup。Rollout算法只是为了在给定的rollout-policy基础上进行提升以及决策，并不是为了学习到optimal policy，所以Rollout算法严格来说并不能算是learning algorithms。
书上对Rollout Algorithms的总结比较合适：
We do not ordinarily think of rollout algorithms as learning algorithms because they do not maintain long-term memories of values or policies.However, these algorithms take advantage of some of the features of reinforcement learning that we have emphasized in this book. As instances of Monte Carlo control, they estimate action values by averaging the returns of a collection of sample trajectories, in this case trajectories of simulated interactions with a sample model of the environment. In this way they are like reinforcement learning algorithms in avoiding the exhaustive sweeps of dynamic programming by trajectory sampling, and in avoiding the need for distribution models by relying on sample, instead of expected, updates. Finally, rollout algorithms take advantage of the policy improvement property by acting greedily with respect to the estimated action values.(我们通常不把rollout算法看作学习算法，因为它们不保持对值或策略的长期记忆。然而，这些算法利用了我们在本书中强调的强化学习的一些特征。作为蒙特卡罗控制的实例，它们通过平均一组样本轨迹的reward来估计动作值，在这种情况下，是模拟与环境样本模型的交互的轨迹。通过这种方式，它们就像强化学习算法一样，通过trajectory sampling避免了进行动态规划的exhaustive sweeps，并且通过依赖样本而不是期望更新来避免对分布模型的需求。最后，展开算法利用策略改进特性，对估计的动作值greedy地操作。)
Monte Carlo Tree Search
Monte Carlo Tree Search是最近出现的比较成功的decision-planning算法(PS:花了4个小标题来阐述decision time planning算法，为什么不给个例子呢( _ゝ`))。
MCTS算法是基于Rollout算法的，但是通过累计通过Monte Carlo方法仿真得到的value estimate来更好的提升rollout-policy。
算法基本上分为一下四步：
第一步是Selection，就是在树中找到一个最好的值得探索的节点，一般策略是先选择未被探索的子节点，如果都探索过就选择UCB值最大的子节点。第二步是Expansion，就是在前面选中的子节点中走一步创建一个新的子节点，一般策略是随机自行一个操作并且这个操作不能与前面的子节点重复。第三步是Simulation，就是在前面新Expansion出来的节点开始模拟游戏，直到到达游戏结束状态，这样可以收到到这个expansion出来的节点的得分是多少。第四步是Backpropagation，就是把前面expansion出来的节点得分反馈到前面所有父节点中，更新这些节点的quality value和visit times，方便后面计算UCB值。
这里的decision time planning算法只是做了一个简单的介绍，大致介绍了一下基本思路，如果需要深入还需要阅读相关的论文。