马尔可夫决策过程

编辑 锁定 讨论999
马尔可夫决策过程(Markov Decision Process, MDP)是序贯决策(sequential decision)的数学模型,用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报 [1-2]  。MDP的得名来自于俄国数学家安德雷·马尔可夫(Андрей Андреевич Марков),以纪念其为马尔可夫链所做的研究 [3] 
MDP基于一组交互对象,即智能体和环境进行构建,所具有的要素包括状态、动作、策略和奖励 [2]  [4]  。在MDP的模拟中,智能体会感知当前的系统状态,按策略对环境实施动作,从而改变环境的状态并得到奖励,奖励随时间的积累被称为回报 [4] 
MDP的理论基础是马尔可夫链,因此也被视为考虑了动作的马尔可夫模型 [2]  。在离散时间上建立的MDP被称为“离散时间马尔可夫决策过程(descrete-time MDP)”,反之则被称为“连续时间马尔可夫决策过程(continuous-time MDP)” [1]  。此外MDP存在一些变体,包括部分可观察马尔可夫决策过程、约束马尔可夫决策过程和模糊马尔可夫决策过程。
在应用方面,MDP被用于机器学习强化学习(reinforcement learning)问题的建模 [1]  [4]  。通过使用动态规划随机采样等方法,MDP可以求解使回报最大化的智能体策略 [4-5]  ,并在自动控制推荐系统等主题中得到应用 [4] 
中文名
马尔可夫决策过程
外文名
Markov Decision Processes, MDP
类    型
马尔可夫模型,决策模型
提出者
Richard Bellman,Ronald Howard,David Blackwell [5] 
提出时间
1957-1962年 [6] 
学    科
统计学,机器学习
应    用
运筹学,自动控制,机器人学

马尔可夫决策过程历史

编辑
MDP的历史可以追溯至20世纪50年代动力系统研究中的最优控制(optimal control)问题,1957年,美国学者Richard Bellman通过离散随机最优控制模型首次提出了离散时间马尔可夫决策过程 [6]  。1960年和1962年,美国学者Ronald A. Howard和David Blackwell提出并完善了求解MDP模型的动态规划方法 [5]  [7] 
进入1980s后,学界对MDP的认识逐渐由“系统优化”转为“学习” [1]  。1987年,美国学者Paul Werbos在研究中试图将MDP和动态规划与大脑的认识机制相联系 [8]  。1989年,英国学者Chris Watkins首次在强化学习中尝试使用MDP建模 [9]  。Watkins (1989)在发表后得到了机器学习领域的关注,MDP也由此作为强化学习问题的常见模型而得到应用 [1] 

马尔可夫决策过程定义

编辑
MDP中智能体与环境的交互 MDP中智能体与环境的交互 [1]
MDP是在环境中模拟智能体的随机性策略(policy)与回报的数学模型,且环境的状态具有马尔可夫性质
交互对象与模型要素
由定义可知,MDP包含一组交互对象,即智能体和环境 [4] 
  • 智能体(agent):MDP中进行机器学习的代理,可以感知外界环境的状态进行决策、对环境做出动作并通过环境的反馈调整决策。
  • 环境(environment):MDP模型中智能体外部所有事物的集合,其状态会受智能体动作的影响而改变,且上述改变可以完全或部分地被智能体感知。环境在每次决策后可能会反馈给智能体相应的奖励。
按定义,MDP包含5个模型要素,状态(state)、动作(action)、策略(policy)、奖励(reward)和回报(return),其符号与说明在表中给出 [4] 
名称符号说明
状态
状态空间
状态是对环境的描述,在智能体做出动作后,状态会发生变化,且演变具有马尔可夫性质。MDP所有状态的集合是状态空间。状态空间可以是离散或连续的。
动作
动作空间
动作是对智能体行为的描述,是智能体决策的结果。MDP所有可能动作的集合是动作空间。动作空间可以是离散或连续的。
策略
MDP的策略是按状态给出的,动作的条件概率分布,在强化学习的语境下属于随机性策略。
奖励
智能体给出动作后环境对智能体的反馈。是当前时刻状态、动作和下个时刻状态的标量函数
回报
回报是奖励随时间步的积累,在引入轨迹的概念后,回报也是轨迹上所有奖励的总和。

  在表中建模要素的基础上,MDP按如下方式进行组织:智能体对初始环境
进行感知,按策略
实施动作
,环境受动作影响进入新的状态
,并反馈给智能体一个奖励
。随后智能体基于
采取新的策略,与环境持续交互。MDP中的奖励是需要设计的,设计方式通常取决于对应的强化学习问题。
连续与离散MDP
MDP的指数集(index set)是时间步:
,并按时间步进行演化(evolution)。时间步离散的MDP被称为离散时间马尔科夫决策过程(descrete-time MDP),反之则被称为连续时间马尔科夫决策过程(continuous-time MDP),二者的关系可类比连续时间马尔可夫链与离散时间马尔可夫链。
图模型
MDP的图模型表示 MDP的图模型表示 [4]
MDP可以用图模型表示,在逻辑上类似于马尔可夫链的转移图。MDP的图模型包含状态节点和动作节点,状态到动作的边由策略定义,动作到状态的边由环境动力项(参见求解部分)定义。除初始状态外,每个状态都返回一个奖励 [4] 
解释性的例子:多臂赌博机
多臂赌博机问题(multi-armed bandit problem)的设定如下:给定K个不同的赌博机,拉动每个赌博机的拉杆,赌博机会按照一个事先设定的概率掉钱或不掉钱。每个赌博机掉钱的概率不一样。MDP可以模拟智能体选择赌博机的策略和回报 [1]  。在该例子中,MDP的要素有如下对应:
“环境”是K个相互独立的赌博机;“状态”是“掉钱”和“不掉钱”,其马尔可夫性质在于每次使用赌博机,返回结果都与先前的使用记录无关;“动作”是使用赌博机;“策略”是依据前一次操作的赌博机和其返回状态,选择下一次使用的赌博机;“奖励”是一次使用赌博机后掉钱的金额;回报是多次使用赌博机获得的总收益 [1] 
与多臂赌博机类似的例子包括广告推荐系统和风险投资组合,在MDP建模后,此类问题被视为离散时间步下的纪元式强化学习 [4] 

马尔可夫决策过程理论与性质

编辑

马尔可夫决策过程转移理论

马尔可夫性质与转移概率
按定义,MDP具有马尔可夫性质,按条件概率关系可表示如下 [4] 
即当前时刻的状态仅与前一时刻的状态和动作有关,与其他时刻的状态和动作条件独立。等式右侧的条件概率被称为MDP的状态间的转移概率 [4]  。马尔可夫性质是所有马尔可夫模型共有的性质,但相比于马尔可夫链,MDP的转移概率加入了智能体的动作,其马尔可夫性质也与动作有关。
MDP的马尔可夫性质是其被应用于强化学习问题的原因之一,强化学习问题在本质上要求环境的下个状态与所有的历史信息,包括状态、动作和奖励有关,但在建模时采用马尔可夫假设可以在对问题进行简化的同时保留主要关系,此时环境的单步动力学就可以对其未来的状态进行预测。因此即便一些环境的状态信号不具有马尔可夫性,其强化学习问题也可以使用MDP建模 [1] 
轨迹
在此基础上,类比马尔可夫链中的样本轨道(sample path),可定义MDP的轨迹(trajectory) [4] 
即环境由初始状态
按给定策略
演进至当前状态
的所有动作、状态和奖励的集合。由于MDP的策略和状态转移具有随机性,因此其模拟得到的轨迹是随机的,且该轨迹出现的概率有如下表示 [4] 
一般地,MDP中两个状态间的轨迹可以有多条,此时由Chapman-Kolmogorov等式可知,两个状态间的n步转移概率是所有轨迹出现概率的和。

马尔可夫决策过程折现

MDP的轨迹与回报计算示例,方形为终止状态 MDP的轨迹与回报计算示例,方形为终止状态 [1]
MDP的时间步可以是有限或无限的。时间步有限的MDP存在一个终止状态(terminal state),该状态被智能体触发后,MDP的模拟完成了一个纪元(episode)并得到回报。与之对应的,环境中没有终止状态的MDP可拥有无限的时间步,其回报也会趋于无穷 [1]  [2] 
在对实际问题建模时,除非无限时间步的MDP有收敛行为,否则考虑无限远处的回报是不适合的,也不利于MDP的求解。为此,可引入折现机制并得到折现回报(discounted return) [1]  [2] 
式中
为一常数,被称为折现系数。由几何级数的极限可知,无限时间步MDP的折现回报是有限的 [2] 
因此折现回报在考虑了无穷远处奖励的同时,使MDP的求解变得可行。此外为便于计算,折现回报可以表示为递归形式 [1]  [2] 
式中
的下标表示轨迹开始的时间步,对应轨迹
的回报。

马尔可夫决策过程值函数

参见:强化学习
MDP的每组轨迹都对应一个(折现)回报。由于MDP的策略和状态转移都是条件概率,因此在考虑模型的随机性后,轨迹的折现回报可以由其数学期望表示,该数学期望被称为目标函数 [4] 
MDP的轨迹依赖于给定的策略,因此目标函数也是控制策略
的参数的函数:
。例如,若策略由其它机器学习模型,例如神经网络给出,则参数
是权重系数 [4]  。此外对状态收敛的无限时间步MDP,其目标函数也可以是其进入平稳分布时单个时间步的奖励的数学期望 [4] 
状态值函数(state value function)
在MDP模拟的一个纪元中,目标函数与初始状态
有关,因此按定义,目标函数有可有如下展开 [2] 
目标函数中包含初始状态的条件数学期望被定义为状态值函数:
,即智能体由初始状态开始,按策略
决定后续动作所得回报的数学期望 [1] 
式中的数学期望同时考虑了策略的随机性和环境的随机性,为求解值函数,上式可通过折现回报的递归形式改写为贝尔曼方程(Bellman equation) [1] 
上式后两行中的第一个求和表示对策略的随机性求数学期望、第二个求和表示对环境,包括状态和奖励的随机性求期望(参见动作值函数)。说明性地,这两个求和将时间步内所有可能的动作、状态和奖励加权求和。由贝尔曼方程的性质可知,给定MDP的策略
、转移概率
和奖励
,状态值函数可以按迭代的方式进行计算 [2] 
动作值函数(action value function)
状态值函数中的条件概率:
表示环境对动作的响应,该项也被称为环境动力项(environment dynamics)。环境动力项不受智能体控制,其数学期望可以定义为动作值函数或Q函数:
,表示智能体由给定的状态
和动作
开始,并按策略
决定后续动作所得到的回报数学期望 [1] 
上式为动作值函数的贝尔曼方程,式中关于
的动作值函数包含了
的状态值函数,联合上式与动作值函数的贝尔曼方程可以得到二者的相互关系 [1] 
式中第二行是另一种形式的动作值函数贝尔曼方程。上式表明,给定策略值函数和动作值函数的贝尔曼方程,可以得到动作值函数的贝尔曼方程。
状态值函数和动作值函数是一些MDP算法需要使用的,目标函数的变体,其实际意义是对策略的评估。例如在状态
,若有一个新的动作
使得
,则实施新动作比当前策略
给出的动作要好,因此可通过算法增加新动作所对应的策略
的概率 [4] 

马尔可夫决策过程算法

编辑
参见:强化学习
在MDP模型建立后,强化学习算法能够求解一组贯序策略:
,使得目标函数,即智能体的折现回报,取全局最大值 [2] 
按求解途径,MDP适用的强化学习算法分为两类:值函数算法和策略搜索算法。值函数算法通过迭代策略的值函数求得全局最优;策略搜索算法则通过搜索策略空间得到全局最优 [4] 

马尔可夫决策过程值函数算法

动态规划(dynamic programming)
参见:动态规划
作为贝尔曼最优化原理(Bellman's principle of Optimality)的推论,有限时间步的MDP至少存在一个全局最优解,且该最优解是确定的(deterministic),可使用动态规划求得 [2]  [10] 
使用动态规划求解的MDP属于“基于模型的强化学习(model-based reinforcement learning),因为要求状态值函数和动作值函数的贝尔曼方程已知,而后者等价于MDP的环境不是”黑箱“,其环境动力项
是已知的。MDP的动态规划分为策略迭代(policy iteration)和值迭代(value iteration)两种,其核心思想是最优化原理:最优策略的子策略在一次迭代中也是以该状态出发的最优策略,因此在迭代中不断选择该次迭代的最优子策略能够收敛至MDP的全局最优 [2] 
以策略迭代为例,在对MDP的建模要素初始化后,其每次迭代都使用贝尔曼方程计算状态值函数以评估策略,并按动作值函数对状态值函数的贝尔曼方程确定当前状态下的最优动作和策略:
,迭代在策略的前后变化小于迭代精度时收敛 [4] 
随机模拟
蒙特卡罗方法和时序差分学习(temporal-difference learning)为代表的MDP算法属于“无模型的强化学习(model-free reinforcement learning)”,适用于MDP的环境动力项未知的情形。在MDP的转移概率未知时,状态值函数
无法参与优化,因此随机模拟方法通过生成随机数直接估计动作值函数的真实值并求解MDP。
对给定的初始状态和动作,蒙特卡罗方法按N次随机游走试验所得回报的平均估计动作值函数 [4] 
在动作值函数的随机游走收敛后,蒙特卡罗方法按策略迭代寻找最优动作并迭代完成MDP的求解。蒙特卡罗算法在总体上是一个泛用性好但求解效率低下的算法,按确定策略采样的蒙特卡罗收敛缓慢,在本质上是智能体对环境单纯的“试错”。一些引入了探索机制的改进版本,例如ϵ-贪心算法(ϵ-greedy method)也需要采样整个轨迹后才能评估和改进策略,在求解复杂MDP时会带来相当的计算开销 [4] 
时序差分学习可视为蒙特卡罗方法和动态规划的结合。在使用采样方法估计动作值函数时,时序差分学习将采样改写为贝尔曼方程的形式,以更高的效率更新动作值函数的取值。求解MDP可用的时序差分学习算法包括SARSA 算法(State Action RewardState Action, SARSA)和Q学习(Q-Learning)算法 [11]  ,二者都利用了MDP的马尔可夫性质,但前者的改进策略和采样策略是同一个策略,因此被称为“同策略(on policy)”算法,而后者采样与改进分别使用不同策略,因此被称为“异策略(off policy)”算法 [4] 

马尔可夫决策过程策略搜索算法

参见:策略搜索
策略搜索(policy search)可以在策略空间直接搜索MDP的最优策略完成求解。策略搜索算法的常见例子包括REINFORCE算法和演员-评论员算法(Actor-Critic Algorithm)。REINFORCE算法使用随机梯度上升求解(可微分的)策略函数的参数使得目标函数最大,一些REINFORCE算法的改进版本通过引入基准线加速迭代的收敛 [4]  [12]  。演员-评论员算法是一种结合策略搜索和时序差分学习的方法。其中“演员(actor)”是指策略函数,即学习一个策略来得到尽量高的回报,“评论员(critic)”是状态值函数,对当前策略的值函数进行估计,即评估演员的好坏。借助于值函数,Actor-Critic 算法可以进行单步更新参数 [4] 

马尔可夫决策过程推广

编辑
约束马尔可夫决策过程
约束马尔可夫决策过程(Constrained MDP, CMDP)是对智能体施加了额外限制的MDP,在CMDP中,智能体不仅要实施策略和获得回报,还要确保环境状态的一些指标不超出限制。例如在基于MDP的投资组合问题中,智能体除了最大化投资回报,也要求限制投资风险;在交通管理中,智能体除了最大化车流量,也要求限制车辆的平均延迟和特定路段的车辆通行种类 [13] 
相比于MDP,CMDP中智能体的每个动作都对应多个(而非一个)奖励。此外,由于约束的引入,CMDP不满足贝尔曼最优化原理,其最优策略是对初始状态敏感的,因此CMDP无法使用动态规划求解。离散CMDP的常见解法是线性规划(linear programming) [13] 
模糊马尔可夫决策过程
模糊马尔可夫决策过程(Fuzzy MDP, FMDP)是使用模糊动态规划(fuzzy dynamic programming)求解的MDP模型,是MDP的推广之一。FMDP的求解方法属于值函数算法,其中策略评估部分与传统的动态规划方法相同,但策略改进部分使用了模糊推理(fuzzy inference),即值函数被用作模糊推理的输入,策略的改进是模糊推理系统的输出 [14] 
部分可观察马尔可夫决策过程
在一些设定中,智能体无法完全观测环境的状态,此类MDP被称为部分可观察马尔可夫决策过程(Partially Observable MDP,POMDP)。POMDP是一个马尔可夫决策过程的泛化。POMDP与MDP的马尔可夫性质相同,但是POMDP框架下智能体只能知道部分状态的观测值。比如在自动驾驶中,智能体只能感知传感器采集的有限的环境信息。与MDP相比,POMDP包含两个额外的模型要素:智能体的观测概率
和观测空间

马尔可夫决策过程应用

编辑
作为强化学习的模型,MDP适用于很多与强化学习有关的实际问题,包括自动控制领域的人机交互系统自动驾驶系统导航系统 [1]  [4] 运筹学领域的广告/销售问题、投资组合问题等 [4]  。MDP也可以作为模型构建一些具有博弈性质的强化学习系统,例如国际象棋围棋AI [15] 
参考资料
  • 1.    Sutton, R.S. and Barto, A.G. .Reinforcement learning: An introduction (Second edition):MIT press,2018:Chapter 1-3
  • 2.    Panin, A. and Shvechikov, P., Practical Reinforcement Learning  .Coursera and National Research University Higher School of Economics.2017[引用日期2019-05-16]
  • 3.    Gagniuc, P.A..Markov Chains: From Theory to Implementation and Experimentation:John Wiley & Sons,2017
  • 4.    邱锡鹏 著,神经网络与深度学习,第十四章 深度强化学习 .Github Inc..2018[引用日期2018-11-16]  .Github Inc..2019[引用日期2019-05-16]
  • 5.    Howard, R.A..Dynamic Programming and Markov Processes.Cambridge, Massachusetts:Technology Press-Wiley,1960
  • 6.    Bellman, R.E., 1957. A Markov decision process. Journal of Mathematical Mechanics, 6, pp.679-684.
  • 7.    Blackwell D., 1962. Discrete dynamic programming. Ann Math Stat 33: 719-726.
  • 8.    Werbos, P.J., 1987. Building and understanding adaptive systems: A statistical/numerical approach to factory automation and brain research. IEEE Transactions on Systems, Man, and Cybernetics, 17, pp.7-20.
  • 9.    Watkins, C., 1989. Learning from Delayed Rewards. PhD Thesis. Cambridge University.
  • 10.    史永东.金融经济学:东北财经大学出版社 , 2012.03:167页
  • 11.    Watkins, C. and Dayan, P., 1992. Q-learning. Machine learning, 8(3), pp.279-292.
  • 12.    Williams, R.J., 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229–256.
  • 13.    Goncalves, N., Constrained Markov Decision Processes. In: Sequential Decision Making under Uncertainty  .Institute for Systems and Robotics, University of Lisbon.2007-4-16[引用日期2019-05-24]
  • 14.    Bellman, R.E. and Zadeh, L.A., 1970. Decision-making in a fuzzy environment, Management Science Series. B(17), pp.141-164.
  • 15.    Littman, M.L., 1994. Markov games as a framework for multi-agent reinforcement learning. In 11th International Conference on Machine Learning, pp.157–163.
展开全部 收起