马尔可夫决策过程(MDP)

马尔可夫决策过程(Markov Decision Processes,MDP)是对强化学习中环境(Environment)的形式化的描述,或者说是对于智能体所处的环境的一个建模。在强化学习中,几乎所有的问题都可以形式化地表示为一个马尔可夫决策过程。

简化一下“Frozen Lake”(无风模式),并且不考虑起点和终点,如图 1 所示。
简化的“Frozen Lake”游戏
图 1:简化的“Frozen Lake”游戏

图 1 中右侧的状态转换图,表示从每个状态转移到下一个状态的概率及能获得的相应奖励。例如在状态 S1 时,可以转移到 S2 状态,也可以转移到 S3 状态,或者不移动,留在 S1 状态,其概率分别为 0.3、0.5 和 0.2,获得的相应奖励分别为 2、2 和 1。对于每一个状态来说,出边的概率和必为 1。

1. 马尔可夫过程(Markov Process)

在一个随机过程 s0,s1,…,sn 中,已知时刻 ti 所处的状态 si,如果在时刻 ti+1 时的状态 si+1 只与状态 si 相关,而与 ti 时刻之前的状态无关,则称这个过程为马尔可夫过程。

例如图 1 中的例子,智能体从 S1 状态移动到 S3 状态后,至于下一个状态是什么已经与 S1 无关了,只取决于当前的 S3 状态。这种特性称为随机过程的马尔可夫性(或称为“无后效性”)。具有马尔可夫性的随机过程 s0,s1,…,sn 称为马尔可夫链(Markov Chain)。

2. 马尔可夫回报过程(Markov Reward Process)

前面在讨论计算累积奖励的时候给出了 2 个公式。这两个公式考虑的是最简单的情况(即智能体每执行一个动作后,到达的下一个状态是确定的),因此仅需要将智能体每一步获得的奖励累加起来。

然而,很多时候,状态是不确定的,例如在“Frozen Lake”游戏的“有风”模式下,智能体执行一个动作后会以一定的概率转移到另一个状态,因此,得到的奖励也与这个概率相关。所以在计算累积奖励的时候,通常是计算奖励的期望,用 V 表示奖励的期望,则状态 s 的期望奖励值表示为:

V(s)=E[Gt|St=s]


所以 Gt=rt+1+rt+2+...+rt+T 可表示为如下形式:


累积奖励”的第二个公式考虑折扣因子则表示为:

3. 马尔可夫决策过程(Markov Decision Process)

在图 1 中只考虑了“Frozen Lake”游戏的“无风”模式,因为在“无风”模式下,智能体执行了一个动作后到达的下一个状态是确定的,所以只考虑状态的转移而无须考虑具体的动作。然而在“有风”模式下,根据执行的动作不同,状态的转移概率也不同。

依然以图 1 中简化后的“Frozen Lake”游戏例子,假如当前状态为 S1,在“有风”模式下,根据执行的动作不同,状态转移概率如表 1 所示。

表 1:“有风”模式下智能体在 S1 状态时执行不同动作的状态转移概率
动作|下一状态 S1 S2 S3
右移 0.35 0.4 0.25
下移 0.3 0.35 0.35

什么是马尔可夫决策过程?我们将马尔可夫决策过程定义为一个五元组:M=(S,A,R,P,γ)
  • S:状态空间,例如在“Frozen Lake”游戏中,总共有 16 个状态(Start,S2,…,S15,Goal);
  • A:动作空间,在“Frozen Lake”游戏中,每个状态下可以执行的动作有四个(上、下、左和右);
  • R:奖励函数,在某个状态 St 下执行了一个动作并转移到下一个状态 St+1,就会得到一个相应的奖励 rt+1
  • P:状态转移规则,可以理解为我们之前介绍的状态转移概率矩阵。在某个状态 St 下执行了一个动作,就会以一定的概率转移到下一个状态 St+1

现在总结一下,强化学习要解决的问题是:智能体需要学习一个策略 π,这个策略 π 定义了从状态到动作的一个映射关系 π:S→A,也就是说,智能体在任意状态 st 下所能执行的动作为 at=π(st),并且有

用价值 Vπ 来衡量这个策略 π 的好坏,价值 Vπ(st) 代表的是智能体从状态 st 开始,在遵循策略 π 的前提下执行一系列动作后获得的累积奖励的期望值(事实上,当策略 π 确定后,MDP 中的状态转移概率也就确定了,此时可以简单地看成马尔可夫回报过程,即可使用求解马尔可夫回报过程的方法求解回报):
马尔可夫回报过程的方法求解回报
这里的价值是在遵循策略 π 的情况下的价值。