欢迎转载，作者：Ling，注明出处：强化学习教程: 08-Model-Based RL Dyna and Tree Search

上一章是从经验(Experience)中学策略(Policy)

之前章节都是从经验中学值函数，包括V和Q

本章主要从经验中学模型(Model),然后用计划(Planning)来构建一个值函数或者策略

集成学习：将学习model和计划放到一个架构中

Model-Free RL VS Model-Based RL

Model-Based RL:

我们先通过现实经验，学习到一个model，或者说是虚拟的环境，然后根据虚拟环境进行采样，然后根据采样结果更新Value/Policy，根据Value/Policy在现实环境中采取行动，然后继续从现实经验学习模型，如此反复

简单说： 首先通过实际经验学习一个模型，然后根据学习的模型进行规划

Model-Based RL优劣势：

优势：

可以用监督学习有效学习模型

劣势：

学习模型会有误差，构建值函数又会有误差，误差可能加大

什么是模型：

• M是一个四元组<S, A, P, R>
• 一般A和S都是已知，主要要学习P和R,就是转移概率和Reward函数

如何学习模型：

目标：通过经验{S1, A1, R2,…,ST}训练一个模型M

输入：S,A,输出R,S

学习s,a->r 是回归问题

学习s,a->s'是分类问题

常见模型例子：

查表模型：

模型：M,P,R

学习公式：

简单说:

转移概率为：统计s->s' 采取了a, 在样本中出现的次数

奖励为：在s，采取了a在样本中获得的奖励和

有了该模型，就可以基于它，模拟采样，然后更新价值/策略函数

利用模型做Planning：

给定模型：

我们要解MDP问题：

• Value iteration
• Policy iteration
• Tree search

还有另外一种更简单的方法做Planning

Sample-based Planning:

• 利用模型产生Samples
• 然后利用model-free RL从这些sample中学习V值，并且采取行动，例如：
  • MC control
  • Sarsa
  • Q-learning

举例：查表模型

通过在实际环境中的采样，我们学习到了一个查表模型：

状态转移概率：

P(A->B, a) = 100%

P(B->终点1, b) = 75%

P(B->终点2，c)=25%

奖励函数：

P(A, a)=0

P(B,b)=1

P(B,c)=0

接下来我们就可以做计划了(Planning)： 就是根据上面的查表模型进行模拟采样(在虚拟环境中采样)，然后更新value/policy

我们得到右边的样本

根据样本我们可以通过MC学习更新V值：

V(A)=1

V(B)=0.75

问题：

如果学习到的模型，不能反应真实世界，会使得V值更新，和采取的行动偏离正轨

改进：集成架构，Dyna

原来：

通过上面我们知道，这里有两套经验，一套现实经验，一套虚拟经验，或者说模拟经验

并且之前的Model-Based RL：

也就是Value Function只从虚拟环境的样本中更新

改进：

从真实和虚拟经验同时学习更新Value Function和策略

图示：

多了一条从现实经验更新的边

算法：

a-d都是传统的根据经验，用model-free的方法学习Q

同时根据现实环境更新model

然后再根据模型，也就是虚拟环境，采样，进一步更新Q

评估结果：

在Maze中可以看出，虚拟环境n取越大效果越好

搜索树：

在虚拟环境，利用model-free更新V/Q时，之前时是普通的值迭代或者策略迭代，都会以各个状态为起始点，进行更新。

之前在实际中我们无需考虑从任何一个节点起始的V值更新，也就是无需解决整个MDP问题，只用解决一个从now开始的sub-MDP问题

实际中，我们采样都会形成从起始点St的一颗前向搜索树

当我们有了model，我们可以构造这样一颗前向搜索树

基于模拟的搜索(Simulation-Based Search) ：是前向搜索的一种形式，它从当前时刻开始， 使用基于模拟采样的规划，构建一个关注与短期未来的前向搜索树，把这个搜索树作为一个学习资源， 然后使用Model Free的强化学习来寻找最优策略。

这样我们实际上：

简单的MC Search：

说明：

只考虑从当前节点出发的Q值

只求当前节点，各个a的q值，求的方法是通过求多个样本的Gt平均值

MC Tree Search:

说明：

对比：

算法：

• 从当前实际状态 s_t 开始，模拟一系列Episodes，在这一过程中使用状态行为价值作为节点录入搜索树，
• 对搜索树内的每一个节点（状态行为对），估计其价值Q(s,a)
• 对于模拟过程中的每一步，使用MC学习更新行为价值：
• 基于Q值，使用Ɛ-greedy或其他探索方法来生成行为

下面会以一个例子说明如何更新Q值

在更新Q过程中的样本不是像简单MC Search一样，随机选择样本，每个样本选择都是朝最优目标前进的。

结合例子说明Q值更新方法：

围棋有红黑两方，所有非终结step回报都是0，终结step，如果黑方赢了，回报是1，如果白方赢了，回报是0

我们来看看如何更新每个状态的价值函数

开始，Tree搜索部分在五角星状态，发现走到尽头T是黑方赢了，所以更新五角星value为1/1

我们尝试走下一步：

尝试下一步状态，发现白方赢了，所以我们更新五角星状态value为0/1，同时我们需要更新第一个状态value为1/2，同时我们不继续从该状态出发了，换一个状态

我们发现走到最后，黑方获胜，这个时候更新所有状态值，以下类似反复操作

这样我们最终就知道从该点开始value是多少，以及接下来各点的value是多少

如果是简单MC Search，可能第二步白方赢的样本，以及从白方赢那个节点之后的样本都会在里面，

但是MC Tree Search会舍弃白方赢的节点，尽可能找黑方赢的节点包含进来，因为每次迭代，它会更新搜索树内所有节点的value，而不仅仅是Q（st a)

由于每次都是考虑完整走到最后T的样本，所以是MC Tree Search

如果只考虑下一步的Tree Search，就是TD Tree Search算法

• 从当前实际状态 s_t 开始，模拟一系列Episodes，在这一过程中使用状态行为价值作为节点录入搜索树，
• 对搜索树内的每一个节点（状态行为对），估计其价值Q(s,a)
• 对于模拟过程中的每一步，使用Sarsa学习更新行为价值：
• 基于Q值，使用Ɛ-greedy或其他探索方法来生成行为

和MC Tree Search区别仅仅是红色部分

TD(λ) Tree Search类似

Dyna-2 算法：

和Dyna一样，一边从实际经历中学习，一遍从模拟的经历中学习。

区别：将前向搜索加入到Dyna中

使用该算法的个体维护了两套特征权重：

一套反映了个体的长期记忆， 该记忆是从真实经历中使用TD学习得到，它反映了个体对于某一特定强化学习问题的普遍性的知识、经验；

 另一套反映了个体的短期记忆，该记忆从基于模拟经历中使用TD搜索得到，它反映了个体对于某一特定强化学习在特定条件 （比如某一Episode、某一状态下）下的特定的、局部适用的知识、经验。

Dyna-2算法最终将两套特征权重下产生的价值综合起来进行决策，以期得到更优秀的策略。

评估：