马尔可夫决策过程实例讲解.pdf

Machine Learning 16—Reinforcement Learning 之前我们学过3 个部分的内容：监督学习、学习理论、半监督学习。现在我们来学 习第四部分：自增强学习。 在监督学习中，给定了训练集以及对应的标签 ，算法要做的就是令预测输出尽可能 y 地接近 。在这种情况下，算法运行过程中对应的是有正确答案的。但有些时候，在对问题 y 作出决策或者控制时，我们很难提供一个确切的正确答案。比如在四足机器人行走编程中， 我们在一开始的时候对才去怎样的行动是“正确的”根本没有概念，我们只知道这是一个足部 调节的过程，因此在这里，监督学习算法并不适用。 在自增强学习框架中，算法的核心是奖励函数，区分出学习过程中哪些行为是“好”的， 哪些行为是“坏”的。对于四足机器人行走问题，当机器人能够向前进时，我们给予积极奖励； 当机器人向后退或者跌倒时候，我们给予消极惩罚。这样，有了奖励惩罚机制，在多次训练 后，机器人会越走越好。 自增强学习成功应用在了无人机飞行、机器人行走、市场决策选择等问题上。为了正式 地定义自增强学习，我们先来看马尔科夫决策过程（Markov Decision Process,简写MDP）。 Markov Decision Process 一个马尔科夫决策过程是一个五元组(S,A,{P }, ,R ，当然有一些书籍上用四元组表示， sa  ) 本意是不变的哈。其中： S 表示状态集（states ） A 表示行为集 （actions ） , 表示状态转换分布，对于当前状态s 和当前采取的动作a，下一个状态 服从 分布（下 P s P sa sa 一个状态出现的概率依赖于前一个状态以及前状态所采取的动作），而且有 , , 。这里隐含的是马尔科夫性质：一个随机过程的未来状态的条件概 P (s ) 1, P (s ) 0 sa sa s, 率分布仅仅依赖于当前状态与该状态下的动作，换句话说，在给定现在状态的时候，它与过 去状态是条件独立的。在一些资料中将 写成矩阵形式，即状态转换矩阵。 P sa [0,1) 表示的是discount factor，具体含义稍后解释。 R：SxR  表示奖励函数。R 为实数。有时候R 只与状态S 有关 （更多时候与状态S 与行 为A 都有关），下面的例子就是如此。为了更加具体的表示五元组的含义，我们来说一个MDP 相关的具体例子： 上图的场景表征的是机器人导航任务，想象一个机器人生活在网格世界中，阴暗单元是 一个障碍。假设我希望机器人到达的目的地是右上角的格子（4,3 ），于是我用+1 奖励来 关联这个单元；我想让它避免格子（4,2 ），于是我用-1 奖励来关联该单元。现在让我们 来看看在该问题中，MDP 的五元组是什么： S ：机器人可以在11 个网格中的任何一个，那么一共有11 个状态；集合S 对应11 个可 能到达的位置。 A={N S E W} 。机器人可以做出的动作有4 个：向东 向南 向西 向北。 P ：假设机器人的行为核心设计并不是那么精准，机器人在受到相关指令后有可能会走偏 sa 方向或者行走距离不那么精确，为简化分析，建立机器人随机动态模型如下： 即命令机器人朝北（朝上）行走，他有0.1 的概率朝着左右方向，0.8 的概率朝指定方 向。当机器人撞到墙上或者要走到不是相邻的格子时，其概率为0. （当然，也有关于P