David Silver 强化学习 第八讲

整合学习与规划

Posted by Pelhans on January 26, 2018

通过构建一个模型,个在与环境发生实际交互之前思考各种可能的行为能带给环境和自身的改变.通过个体的思考以及联合其与环境的实际交互经验,个体在解决大规模MDP问题时可以取得更好的结果.

简介

总结自叶强的David Silver强化学习公开课中文讲解及实践专栏

本讲主要讲解如何从经历中直接学习模型,如何构建一个模型,如何基于模型来进行“规划”,在此基础上将“学习”和“规划”整合起来形成Dyna算法.依赖于模型,个体可以通过模拟产生一系列虚拟的Episodes,通过使用基于模拟的搜索方法,特别是蒙特卡罗树搜索方法,找到了一条解决诸如围棋等大规模MDP问题的有效可行的算法.

基于模型的强化学习 Model Based Reinforcement Learning

个体通过经历可以学习到模型,而后个体通过与模型交互进行价值函数或策略的更新来解决MDP.随后使用这些价值函数或策略来与实际环境进行交互获得更多经历.规划,即并未实际发生的事情,个体与模型间的交互指从个体建立的模型中采样,模拟确定个体下一时刻的状态和奖励.当学习价值函数或策略较为困难是,学习模型的优势就显现出来,并使模型具备一定的推理能力.但由于基于模型的学习是对环境的模型,在此基础上再进行学习会引入二次近似,有可能带来较为严重的错误,因此要合适的选用方案.

用监督学习来构建模型

模型M是一个MDP<S,A,P,R>的参数化()形式,其中假定状态空间S和行为空间A是已知的,因此.通常我们假定状态转移函数和奖励函数是条件独立的:

我们的目标是从经历中估计出一个模型,那么若采用监督学习的标记方式,则:

从S,A学习R的过程是回归问题.从S,A学习S’的过程是一个密度估计问题.

根据使用的算法不同,可以有如下多种模型:查表式(Table lookup Model)、线性期望模型(Linear Expectation Model)、线性高斯模型(Linear Gaussian Model)、高斯决策模型(Gaussian Process Model)、和深信度神经网络模型(Deep Belief Network Model)等.以查表模型为例,它通过经历得到各种状态行为的转移概率和奖励,并把它们存入表中,使用时直接进行检索计算P,R即可.

利用模型进行”规划”

规划的过程就相当于解决一个MDP的过程,即给定一个模型,找到基于该模型的最优价值函数或最优策略,也就是在给定的状态s下确定最优的行为a.

那如何从模型中虚拟采样呢?在实际中是利用模型产生一个虚拟的状态转换,即一个时间步长的虚拟经历:

有了这些虚拟的采样,随后使用不基于模型的强化学习方法来学习得到价值或策略函数。

架构整合 Integrated Architectures

这里将把基于模型的学习和不基于模型的学习结合起来,形成一个整合的架构,这样就可以利用两者的优点来解决复杂的问题.当构建了一个环境的模型后,个体可以有两种经历来源:实际经历(real experience)、模拟经历(simulated experience)。

基于这个思想,我们可以把不基于模型的真实经历和基于模型采样得到的模拟经历结合起来,提出一种新的架构-Dyna算法.

Dyna算法

算法从实际经历中学习得到模型,然后联合使用实际经历和模拟经历一边学习,一边规划更新价值和(或)策略函数

Dyna-Q的算法流程如下

该算法在a,b,c,d,e步从实际经历中学习,d步学习价值函数,e步学习模型.在f步,个体使用模型,在之前观测过的状态空间中随机采样一个状态,同时从这个状态下曾经使用过的行为中随机选择一个行为,将两者带入模型得到新的状态和奖励,依据这个来再次更新行为价值和函数。

本部分我们讲专注于规划本身,如何高效地进行规划,把这些想法应用到基于模拟的搜索算法中,从模拟的经历中进行采样,进行较深层次的采样规划,来看看是否能够得到一些艺术级表现的搜索规划类算法。

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

蒙特卡罗树搜索是一种可以高效解决复杂问题的搜索方法。它使用当前的模拟策略构建一个基于当前状态的搜索树。和简单蒙特卡罗搜索不一样的是,蒙特卡罗树搜索方法将评估整个搜索树中每一个状态行为对的价值,并在此基础上改善我们基于模拟采样的策略。

其执行流程为:

  1. 给定一个模型.

  2. 从当前状态开始,使用当前的模拟策略,模拟生成 K 个Episodes:

  3. 构建一个包括所有个体经历过的状态和行为的搜索树.(就像围棋一样,从某一个状态开始分叉到各种的可能情况,到下一步又分叉)

  4. 对于搜索树中每一个状态行为对(s,a) ,计算从该(s,a) 开始的所有完整Episode收获的平均值,以此来估算该状态行为对的价值 Q(s,a).

  5. 当搜索过程结束,也就是所有 s,a 的 Q 值得到更新后,选择搜索树中状态 S_t 对应最大 Q 值的行为(即找到从目前状态到终止获得Q最大的那个行为):

蒙特卡罗树搜索一个特点是在构建这个搜索树的过程中,更新了搜索树内状态行为对的价值,积累了丰富的信息,利用这些信息可以更新模拟策略,使得模拟策略得到改进。

模拟

每一次模拟结束时策略都将得到改进,但有时搜索树并不包括整个状态行为对空间的Q值,会出现搜索树种不包含的状态,此时就分为两种情况进行处理:

  1. 树内确定性策略(Tree Policy):对于在搜索树中存在的状态行为对策略的更新倾向于最大化Q值,这部分策略随着模拟的进行是可以得到持续改进的;

  2. 树外默认策略(Default Policy):对于搜索树中不包括的状态,可以使用固定的随机策略

这样随着不断的重复模拟,状态行为对的价值讲得到持续的评估,同时基于-greedy的搜索策略使得搜索树将不断的扩展,策略也将不断得到改善。

前面讲解的都是蒙特卡罗搜索,它其实只是规划方法里众多有效算法中的一种,实际上不应仅局限于特定的搜索树结构、模拟策略及蒙特卡罗搜索算法。解决这一大类问题的关键理念在于“前向搜索(forward sarch)”和“采样(sampling)”。正确运用这两点,个体可以到达状态空间里许多非常优秀的状态,在此基础上把强化学习的一些不基于模型的算法应用到这些模拟产生的好的状态中,最终得到一个较优秀的策略。

如果说蒙特卡罗树搜索是对从当前状态开始的一个子MDP问题应用蒙特卡罗控制,那么TD搜索可以被看成时对从当前状态开始的一个子MDP问题应用SARSA学习。在基于模拟的搜索时,TD搜索多数时候也是优于MC搜索的,特别是TD(λ)搜索。这主要是因为使用引导(bootstrapping)数据对解决基于模拟的搜索产生的子MDP问题同样是有积极意义的。

对于TD搜索,其流程如下:

  1. 从当前实际状态 开始,模拟一系列Episodes(不必到终止状态),在这一过程中使用状态行为价值作为节点录入搜索树,

  2. 对搜索树内的每一个节点(状态行为对),估计其价值Q(s,a)(可以使用Q的近似函数表达式).

  3. 对于模拟过程中的每一步,使用Sarsa学习更新行为价值:

  4. 基于Q值,使用Ɛ-greedy或其他探索方法来生成行为。

Dyna-2算法

在之前的Dyna算法基础上应用基于模拟的前向搜索就变成Dyna-2算法.使用该算法的个体维护了两套特征权重:一套反映了个体的长期记忆,该记忆是从真实经历中使用TD学习得到,它反映了个体对于某一特定强化学习问题的普遍性的知识、经验;另一套反映了个体的短期记忆,该记忆从基于模拟经历中使用TD搜索得到,它反映了个体对于某一特定强化学习在特定条件(比如某一Episode、某一状态下)下的特定的、局部适用的知识、经验。Dyna-2算法最终将两套特征权重下产生的价值综合起来进行决策,以期得到更优秀的策略。

参考

《强化学习》第八讲 整合学习与规划