主要内容：
- 介绍基于模型的强化学习
- 如果我们知晓模型的转移概率，如何进行决策控制
- 随机优化方法（Stochastic optimization methods）介绍
- MCTS(Monte Carlo tree search)算法介绍
- Trajectory优化
1. 基于模型的强化学习
引入基于模型的强化学习
首先回顾下强化学习的目标函数：
环境给出一个初始状态，然后agent根据状态给出动作，环境接受动作，根据模型给出奖励以及下一个状态,agent进一步作出决策，如此往复循环。RL的目标函数就是要找到一组参数，最大化所有trajectory上能获得的总和。
基于这个目标，首先引入了策略梯度（Policy Gradient）系列的方法，直接对这个目标函数关于参数做梯度运算，并进行梯度下降，而value based的方法则是通过找到每个状态能够获得最大期望奖励的动作，从而得到策略。而actor-critic方法则是结合两者，将value function 引入policy gradient中降低方差。
但是可以看到，这两大类方法其实都默认忽略掉了 , 这也就是为什么它们被称为model-free的方法。
从本节开始我们引入模型，首先会讨论如何在已知环境的dynamics下做规划，后续讨论如何学习dynamics，以及如何同时学习dynamic和策略。
open-loop与closed-loop
open与closed是用来描述agent和环境交互模式的概念。
在closed-loop planning中，agent在每次执行动作后得到环境的反馈，一直在和环境做交互，根据新的状态和奖励作出新的动作。
在open-loop planning中，agent仅仅在开始接收初始状态，根据初始状态作出一系列决策，并直接传给环境所有规划的一系列动作。
如果从基于模型的角度来看，open-loop planning应该是更加合理的方法，因为既然知道了模型的dynamic的情况，那么就不需要环境的反馈，agent直接进行推断就可以了。但是在实际基于模型的学习中，模型通常都是不完美的，如果仅仅在开始做规划，那么则可能造成非常大的累积误差，而closed-loop learning则可以根据每一步的反馈修正模型与规划的结果，从而使算法效果更好。
open-loop planning
在这里首先从open-loop planning开始介绍，它的整体目标是这种形式：
也就是说在给定初始状态以及dynamic得到一系列的动作，他们可以使得这个trajectory上的奖励最大化。
2. Stochastic Optimization方法
首先介绍的是基于Stochastic Optimization的一类方法，它是一种黑盒优化方法，它不关系目标是什么形式的，从而也不利用目标本身的性质，只是在优化目标本身。所以把目标当作黑盒，这样就是在优化一个不知形式的目标。
2.1 random shooting方法
首先是最简单的方法，直接从整个动作的分布中采样处若干组动作，计算每组动作能获得的奖励，选择最大的一组动作作为结果。在这种模式下，你的采样越多，得到的结果就越好。
2.2 Cross-entropy method
很自然的，随机采样并不是一种特别好的方法。那么比较直观的改进方案就是从采样方法上下手，CEM就是基于这种思路发展得到的算法。它的也不难，将采样分成多轮，在每轮采样后通过fit一个概率分布将获得reward高的action的概率提高，具体流程如下：
在第三步中，会挑选出reward比较高的action组，用分布去fit它，从而提高它与它附近的样本的采样概率，在CEM中通常会使用高斯分布作为采样的分布，这时候整体的分布相当于就是在拟合reward的分布。
基于stochastic optimization的方法的优势是它简单且速度快，而且容易并行。但是问题在于它在动作空间维度高的时候效果会变得特别差，而且它只能在open-loop planning中使用。所以在大型的场景以及closed-loop planning它还是不足的。
3. MCTS（Monte Carlo Tree Search）
3.1 Discrete planning as tree search
接下来看看close-loop planning部分。MCTS的基本思路是将discrete planning问题当作一个tree search的问题，每层都是一个动作的选择，那么最理想的情况，如果我们能够将所有的叶节点都能搜索到，自然也就能找到最优解了：
但叶节点的数量是随着树的层数指数级增长的，对于动作空间比较大的情况，要遍历完基本是不可能的。所以需要找些方法做些剪枝，MTCS就是基于对叶节点的好坏评估以及探索次数的平衡做的剪枝。
3.2 Upper Confidence bounds for Trees
在介绍算法前，首先介绍一个评分方式Upper Confidence bounds for Trees(UCT)，它的计算如下：
其中Q某个state的价值高低，N表示对某个state的探索次数，这个分数的第一项表示某个state的平均价值，第二项则表示对于探索次数的衡量，探索次数越多，第二项会越小。通过C这个常数来控制两个部分的权重，C越大，则表示算法越鼓励探索新的节点，这个也就是exploration与exploitation之间的tradeoff。在这个计算方式中，如果某个节点没有被探索过，那么它的N是零，这个时候选择它的概率最大，这个也就是后面的UCT TreePolicy首先选择没有探索过的state的原因，
3.3 BehaviorPolicy and TreePolicy
接着介绍MCTS中的两个核心概念：
首先是BehaviorPolicy，它描述的是如何判断一个节点的价值的问题，也就是如何得到上面UCT score中的Q，在许多MCTS的相关应用中都会使用random policy。
其次是UCT TreePolicy，来到一个state后如何选择哪一个分支做拓展，在这里使用了UCT，也就是说在某个state，如果存在没有充分探索的子节点，那么会先探索这些子节点，直到没有子节点，则深入到它的子节点中，而这里探索使用的就是BehaviorPolicy。
接下来用图解释一下整体过程，假设当前处于, 按照UCT TreePolicy的准则，首先选择没有探索过的子节点，所以它会依次选择
,
, 在其上使用BehaviorPolicy，从而得到两个没有探索过的子节点的Q，并将N计为1。
接着进入UCT TreePolicy的第二阶段，探索完所有子节点，那么就只能根据UCT score来计算选择哪个节点了，在上面自然是右边的节点score高，所以选择右边节点进一步搜索。在右边子节点中，按照上面的逻辑，仍然是选择新的节点，然后对整个路径上的state的Q和N都进行更新：例如此处22=12+10， 2=1+1；
接着再从开始通过计算UCT来选择节点，直到达到某种停止准则：
所以MCTS的流程就可以分为这三步进行循环，首先根据TreePolicy选择一个子节点，然后用BehaviroPolicy进行探索，最后将得到的Q和N一路更新回起点。
4. Trajectory Optimization
上节介绍了利用MCTS来解决closed-loop planning，这节介绍另外一类方法：trajectory optimization。
在介绍具体的方法之前首先对比一下两类解决方案的差异：shooting methods与collocation methods。
对于shooting mothod，它是关乎actions层面的优化，算法通过控制actions达到最优，其中dynamic只是用来提供planning的一个结果，通过带入dynamic（下面公式中的），得到一个无限制的优化问题。在这种模式下，由于对states没有控制，所以即使从同一个点开始，只要选择了不同的action，就可以得到不同的trajectory，
而另一类方法则是collocation methods，它同时针对actions和states来进行控制，这个也就是最符合直觉的约束问题 。它虽然从控制上引入了更多的变量，但是它的震荡会更小，在下图中，如果改变了第一个action，那么只有一小段局部位置会发生震荡。所以求解这个问题就变得简单了些，只需要对约束做些简单的relaxation，然后逐步求解这个问题即可。
4.1 Linear Quadratic Regulator(LQR)
4.1.1 问题描述
首先给出LQR的问题描述，其实就是说明LQR中的L和Q的含义，这里用linear表示对model的假设，它假设model是locally linear and time-varied的，而quadratic则是表示对cost function的二次假设：
推到过程有些难，基本上是先计算,然后依次向前计算。
4.1.2 LQR算法描述
4.1.3 Stochastic dynamics
前面的dynamics都是假设是deterministic的，那么LQR是否可以用在stochastic dynamics上呢？这时候其实只要用高斯分布去model这个dynamics就可以了：
4.2 Iterative Linear Quadratic Regulator（iterative LQR）
在LQR中，我们做了一个重要的假设：model是locally linear的，这很自然地也就限制了它的表达能力。那么如果将它的假设扩展到non-linear的，是否有方法能够找到合适的方法处理得这种假设呢？这也就是iLQR存在的意义了。在iLQR中，我们首先会初始化一个trajectory，通过LQR去修他进行修正，得到新的trajectory，迭代进行，直到收敛到最优解。
在具体介绍iLQR之前，需要简单地回顾一下优化中的Newton's method。在gradient dscenet利用Taylor expansion的first-order term去approximate函数，并用来找到下一次迭代的点。而在Newton's method中，则是利用同时利用first-order和second-order derivative去达到这个目的。
Newton's method做最优化就可以表达为如下的流程：
而iLQR其实就可以理解为利用Newton's method去求解原始的优化问题的过程：
伪代码可以描述为如下流程：
4.3 Differential Dynamic Programming（DDP）
在前面提到的iLQR中，虽然是对dynamic做了approximation，但是实际并没有将它扩展到second order：
所以它实际上并不算是真正使用了Newton's method，故而在这里将iLQR的dynamic扩展到second-order approximation，然后仍然按照上面的求解方式进行求解：
而在Newton's method中如果first-order derivative做得不够好，则可能造Overshoot的问题，会导致收敛性能下降，基于这个问题，一个比较简单的解决思路就是使用line search，在当前值与新的值之间按照固定间隔展开line search,在其中找到最小的值作为结果：
