马尔可夫决策过程 (Markov Decision Process)
强化学习系列
范叶亮 / 2020-05-23
分类: 机器学习, 强化学习 / 标签: 强化学习, Reinforcement Learning, 马尔可夫模型, Markov Model, 马尔可夫链, Markov Chain, MC, 隐马尔可夫模型, Hidden Markov Model, HMM, 马尔可夫奖励过程, Markov Reward Process, MRP, 分幕, 马尔可夫决策过程, Markov Decision Process, MDP, 部分可观测马尔可夫决策过程, Partially Observable Markov Decision Process, POMDP / 字数: 2928
本文为《强化学习系列》文章
本文内容主要参考自:
1.《强化学习》1
2. CS234: Reinforcement Learning 2
3. UCL Course on RL 3
马尔可夫模型 #
马尔可夫模型是一种用于序列数据建模的随机模型,其假设未来的状态仅取决于当前的状态,即:
也就是认为当前状态捕获了历史中所有相关的信息。根据系统状态是否完全可被观测以及系统是自动的还是受控的,可以将马尔可夫模型分为 4 种,如下表所示:
状态状态完全可被观测 | 系统状态不是完全可被观测 | |
---|---|---|
状态是自动的 | 马尔可夫链(MC) | 隐马尔可夫模型(HMM) |
系统是受控的 | 马尔可夫决策过程(MDP) | 部分可观测马尔可夫决策过程(POMDP) |
马尔可夫链(Markov Chain,MC)为从一个状态到另一个状态转换的随机过程,当马尔可夫链的状态只能部分被观测到时,即为隐马尔可夫模型(Hidden Markov Model,HMM),也就是说观测值与系统状态有关,但通常不足以精确地确定状态。马尔可夫决策过程(Markov Decision Process,MDP)也是马尔可夫链,但其状态转移取决于当前状态和采取的动作,通常一个马尔可夫决策过程用于计算依据期望回报最大化某些效用的行动策略。部分可观测马尔可夫决策过程(Partially Observable Markov Decision Process,POMDP)即为系统状态仅部分可见情况下的马尔可夫决策过程。
马尔可夫过程 #
对于一个马尔可夫状态
状态概率矩阵
其中每一行的加和为 1。
马尔可夫过程(马尔可夫链)是一个无记忆的随机过程,一个马尔可夫过程可以定义为

从而可以产生多种不同的序列,例如:
C1 -> C2 -> C3 -> Pass -> Sleep
C1 -> FB -> FB -> C1 -> C2 -> Sleep
C1 -> C2 -> C3 -> Pub -> C2 -> C3 -> Pass -> Sleep
状态转移概率矩阵如下所示:

据此我们可以定义马尔可夫奖励过程(Markov Reward Process,MRP)为

期望回报
当
对于存在“最终时刻”的应用中,智能体和环境的交互能被自然地分成一个系列子序列,每个子序列称之为“幕(episodes)”,例如一盘游戏、一次走迷宫的过程,每幕都以一种特殊状态结束,称之为终结状态。这些幕可以被认为在同样的终结状态下结束,只是对不同的结果有不同的收益,具有这种分幕重复特性的任务称之为分幕式任务。
MRP 的状态价值函数
价值函数可以分解为两部分:即时收益
马尔可夫决策过程 #
一个马尔可夫决策过程(Markov Decision Process,MDP)定义为包含决策的马尔可夫奖励过程

策略(Policy)定义为给定状态下动作的概率分布:
一个策略完全确定了一个智能体的行为,同时 MDP 策略仅依赖于当前状态。给定一个 MDP
在策略
在策略
状态价值函数
从一个状态

从一个动作

利用后继状态价值函数表示当前状态价值函数为:

利用后继动作价值函数表示当前动作价值函数为:

最优状态价值函数
最优动作价值函数
定义不同策略之间的大小关系为:
对于任意一个马尔可夫决策过程有:
- 存在一个比其他策略更优或相等的策略,
- 所有的最优策略均能够获得最优的状态价值函数,
- 所有的最优策略均能够获得最优的动作价值函数,
一个最优策略可以通过最大化
对于任意一个 MDP 均会有一个确定的最优策略,如果已知
最优状态价值函数循环依赖于贝尔曼最优方程:




显式求解贝尔曼最优方程给出了找到一个最优策略的方法,但这种解法至少依赖于三条实际情况很难满足的假设:
- 准确地知道环境的动态变化特性
- 有足够的计算资源来求解
- 马尔可夫性质
尤其是假设 2 很难满足,现实问题中状态的数量一般很大,即使利用最快的计算机也需要花费难以接受的时间才能求解完成。
-
Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press. ↩︎
-
CS234: Reinforcement Learning http://web.stanford.edu/class/cs234/index.html ↩︎
-
UCL Course on RL https://www.davidsilver.uk/teaching ↩︎