Model Free Reinforcement Learning(MFRL)算法：MFRL中无须知道Transition或者Reward Models。解决这类问题的方法大体上有三种：
- Value-Based Method (Q-Learning)。
- Policy-Based Method (Policy Gradient)。
- Policy and Value Based Method(Actor Critic)。
Model-Based基本思想
在model-based的RL方法中，需要学transition或者reward model，基于这个所学的model，我们做plan。由于我们可以和所学的model交互，这种做法我们会增加采样的效率。而这种方法的缺点在于使得问题变得更加复杂，并且还存在model-bias的问题。
- 举例说明：
设有三条轨迹，其状态用二元组位置坐标( a , d ) 表示,轨迹表示如下
状态转移概率可表示为：
由上述状态转移概率，依据贝尔曼方程，可得最优值函数：
所以在更新智能体算法参数之前，我们需要更新Transition或者Reward Model。采用值迭代的方法来做MBRL，可以得到MBRL-VI算法伪代码：
上述基于值迭代的算法能够计算比较简单的transition，对于Complex models可以采用function approximate的方式：
在知道了transition的情况下，我们可以采用更加高效率的算法来做MBRL,之前是基于值迭代得到model-based强化学习算法，如果用Q-Learning算法来做的话，我们可以得到MBRL-QL算法伪代码：
与model free的强化学习算法相比，MBRL由于要学一个model，因此更复杂，利用数据的方式更加高效，是利用交互数据学一个model，而不是只用来更新agent，因此泛化能力也会更强。 Partial Planning和Replay Buffer具体对比如下所示：
- Replay buffer: Simple, real samples , no generalization to other sate-action pairs.
- Partial planning with a model: Complex, simulated samples, generalization to other state -action pairs (can help or hurt)
Dyna-Q算法
MBRL的问题在于如何学一个好的model，由此有了Dyna算法，也能够直接从real experience中学。
与之前的方法不同之处在于这里还用state和reward function去更新策略或者值函数(与model-free方法一样，之前所述的MBRL算法中，这些信息只用于更新model)。可以得到Dyna-Q算法伪代码：
Model-Based中的Planning
在Dyna-Q算法中，Planning是从任意状态开始规划的，但是我们完全没有必要说从任意的状态开始规划，我们可以从当前状态(current state)开始规划。可以从当前状态展开一个tree，遍历所有的action。
用Tree Search算法主要是基于三个思想：
- Leaf nodes：Approximate leaf values with value of default policy π \piπ.
- Chance nodes：Approximate expectation by sampling from transition model.
- Decision nodes：Expand only most promising actions.
第一种方法当蒙特卡洛树中的分支因子比较大的时候计算量比较大，第二种方法相当于是一种递增式的方法。第三种方式就是一种剪枝的方法。对上述分析，Monte Carlo Tree Search(MCTS)是一种比较好的选择。
Monte Carlo Tree Search
Monte Carlo Tree Search(with upper confidence bound)算法主流程如下：
根据UCT算法的主要流程框架可以看出，里面的核心三步是TreePolicy、DefaultPolicy和Backup三个函数，其主要功能可总结为：
TreePolicy：主要是选择下一个节点，如果有未展开的节点，选择未展开的；如果全部都有被展开过，选择BestChild节点。当然依据具体情况，也不是什么时候都能完全展开，所以这里是整个MCTS树的策略部分，依据具体问题会有稍许不同。DefaultPolicy：给定一个策略用于计算当前节点的估值，大多数时候是随机rollout策略Backup：拿到结果之后往回传，将TreePolicy选中的那个节点的信息进行更新，主要是更新估值和访问次数。
下面依次对这三个部分进行详细解析：
首先是TreePolicy(node)函数主要实现节点的选择功能，依据是否展开，和是否是最好的孩子节点进行选择，这里会涉及探索和利用的平衡：
上述Expand(n o d e nodenode)针对的是确定性情况，也就是说在当前的状态s ss下，选择不同的a aa,会有一个确定的s ′ s^{\prime}s′与之对应。而如果是不确定的情况下，下一个状态s ′ s^{\prime}s′是按照一个概率分布给定的。也就是拿下一个节点是通过概率拿的。
DefaultPolicy(n o d e nodenode)主要是基于某个给定策略进行rollout，拿到最后的返回结果。主要是模拟仿真评估当前节点的好坏，需要返回对当前节点的评估信息。
而对于最后一步Backup，拿DefaultPolicy(n o d e nodenode)返回的节点评估信息(奖励)，用于更新之前被TreePolicy选定的节点的值和访问次数等统计信息。依据建模过程不同，可以分为Single Player和Two Players(adversarial)：
