入门级强化学习系列之二:理解马尔可夫决策过程(MDP)
强化学习基础篇(二)马尔科夫决策过程(MDP)
上一篇中主要介绍了强化学习的一些主要组成要素(智能体,环境,奖励,状态以及动作等),以及介绍了强化学习的相关概念。本节主要介绍强化学习的基本数学形式,即马尔科夫决策过程(Markov Decision Processes,MDP)。MDP是序贯决策的经典表达形式,他是强化学习在数学上的理想化形式,因为在MDP这个框架之下,我们可以进行非常精确的理论推导。为了一步步引入MDP,我们将循序渐进地从马尔科夫性质(Markov Process),马尔科夫奖励过程(Markov Reward Process,MRP),再到马尔科夫决策过程(Markov Decision Processes,MDP)。在最后对MDP进行部分扩展,如有限与连续MDPs(Infinite and continuous MDPs),部分观测MDP(Partially Observable MDPs,POMDP)以及无折扣或平均奖励MDPs(Undiscounted, average reward MDPs)。
马尔科夫决策过程形式上义了强化学习的环境,并且环境是完全可观测状态,即当前的环境状态可以完全表示过程。此外几乎所有的强化学习问题都可以转化为马尔科夫决策过程。比如在最优控制(Optimal Control)理论中主要处理连续马尔科夫决策过程,部分可观测问题也可以转换为马尔科夫决策过程。
1. 马尔科夫性质(Markov Property)
进一步了解马尔科夫决策过程之前,需要先了解马尔科夫性质(Markov Property),马尔科夫性质即未来的状态只依赖于当前状态,与过去状态无关。
正式的定义如下:
马尔科夫性质(Markov Property)定义:
在时间步时,环境的反馈仅取决于上一时间步的状态和动作,与时间步以及步之前的时间步都没有关联性。
根据定义,当前状态捕捉了历史中所有相关的信息,所以知道了状态,历史(history)就可以完全丢弃。状态是未来的充分统计。然而在实际的环境中,智能体所需完成的任务不能够完全满足马尔科夫性质,即在时间步的反馈不一定仅仅依赖于时间步的状态和动作。但是为了简化问题的求解过程,仍然假设该任务满足马尔科夫属性(Markov Property),并通过约束环境的状态使得问题满足马尔科夫属性。
2.状态转移矩阵(State Transition Matrix)
对于马尔科夫状态以及后续的状态,状态转移概率可以定义为:
状态转移矩阵是马尔科夫过程中状态之间转移的概率所组成的矩阵,因此大小是状态数n的平方。他反映了所有当前状态以及后续的状态的映射,所以他的每行概率之和必定为1。
3.马尔科夫过程(Markov Process)
马尔科夫过程是一个无记忆的随机过程。例如满足马尔科夫性质的状态一系列序列。
马尔科夫过程(Markov Process)定义:
一个马尔科夫过程(Markov Process),或者马尔科夫链(Markov Chain)由一个二元组构成:
- S为有限的状态空间集,表示时间步的状态,其中。
- 为状态转移矩阵,
接下来举个例子,这里把上课学习过程当做是一个简单的马尔科夫过程中,包含了马尔科夫链的两个元素。
这个任务中有7个状态(Facebook, Class 1, Class 2, Class 3, Pass, Pub, Sleep)。在每个状态对应着响应的转移概率,比如在Class1状态下,有0.5概率继续转移到Class2以及0.5的概率转移到Facebook,这里可以注意到每个状态转移概率之和为1。
在这里我们如果对这个马尔科夫过程,从Class1状态开始采样,将会得到很多幕(episode)的采样数据。其中每一幕序列可能为:
- Class 1, Class 2, Class 3, Pass, Sleep
- Class 1, Facebook, Facebook, Class 1, Class 2, Sleep
- Class 1, Class 2, Class 3, Pub, Class 2, Class 3, Pass, Sleep
这里的每一幕数据都会有个终点状态(这里为Sleeep)。
此外在这个例子中,状态转移矩阵为:
4.马尔科夫奖励过程(Markov Reward Process)
4.1 定义
原本的马尔科夫过程加上奖励值之后就变成了马尔科夫奖励过程,元素由变为。其中R就是奖励,是折扣因子。
马尔科夫奖励过程(Markov Reward Process)定义:
一个马尔科夫奖励过程(Markov Reward Process),由一个四元组构成:
- S为有限的状态空间集,表示时间步的状态,其中。
- 为状态转移矩阵,
- R为奖励函数,
- 为折扣因子,
我们可以将之前例子中的马尔科夫过程相应的变成如下的马尔科夫奖励过程:
红色标注的值就是奖励,注意的是,这里的奖励是即时奖励,也就是脱离状态时立刻得到的奖励,这里没有考虑下个状态可能转移到哪里。
4.2 累积奖励(Return)与折扣因子
为了找到长期累积奖励,不仅要考虑当前时间步t的奖励,还需要考虑到未来的奖励。总奖励(Total Reward)的计算公式如下:
根据总奖励R的计算公式可知,长期累积奖励从当前时间步开始,直到最终状态的奖励,得到未来累积奖励(Future Cumulative Reward)。
一般而言,环境是随机的或者未知的,这意味着下一个状态可能也是随机的。即由于所处的环境是随机的,所以无法确定下一次执行相同的动作,以及是否能够获得相同的奖励。向未来探索得越多,可能产生的分歧(不确定性)就越多。因此,在实际任务中,通常用折扣未来累积奖励(Discounted Future Cumulative Reward)来代替未来累积奖励。
如果考虑到无限时间的场景,更加通用的表示为(当前获得的奖励表示为):
其中为折扣因子(Discount Factor),是介于的常数。对于距离当前时间步越远的奖励,其重要性就越低。假设折扣因子,可以认为该策略“目光短浅”,只考虑当前的及时奖励。倘若想平衡当前时间的奖励与未来的奖励,可设置为一个较大的值,比如。如果环境是恒定的,或者说环境的所有状态是已知的(Model-based),那么未来累积奖励可以提前获得并不需要进行折扣计算,这时候可以简单的将折扣因子设置为1,看起来就像非常“有远见“。
大多数的马尔科夫奖励过程(MRP)与马尔科夫决策过程(MDP)都会使用折扣因子。主要基于如下几点考虑:
数学上计算的便利性
避免未来进入循环马尔科夫过程带来的无限大回报
未来的不可靠性
类比经济学中,眼前的利益比未来的利益更加有意义
人类的行为也更加倾向于眼前利益
退一步来说,令为1,也可以简单的转化成没有折扣因子的状态
4.3. 价值函数
价值函数是状态的长期价值表示。它是上面说的回报的期望。
在概率论和统计学中,数学期望是试验中每次可能的结果的概率乘以结果值得总和。这里回报的期望,即价值函数会会随着折扣因子的变化而取不同的值,因为回报会因为的值而改变,期望自然也就会改变。
上图是为1时,例子中的马尔科夫奖励过程,红色的就是状态的价值。暂时可以不必纠结上面的价值是怎么算出来的。通过价值函数的公式我们可以知道,要想求解一个状态的状态价值, 需要根据马尔科夫链把所有的可能列出来。每个可能都在终点终止,但是上面这个马尔科夫过程其实是有环的, 可能陷入无限循环的局面。因为折扣因子还是1,所以会导致回报G无限大,期望也就无限大,状态价值V也就无限大。下面引入贝尔曼方程就是为了更好的求解价值函数的。
4.4 马尔科夫奖励过程的贝尔曼方程(Bellman Equation)
贝尔曼方程(Bellman Equation)可以用来方便的表示和计算马尔科夫奖励过程,价值函数可以分为两个部分;
- 即时奖励
- 下一状态的折扣状态价值
MRP的贝尔曼方程可以进行如下简单的推导:
贝尔曼方程的推导过程中只是简单得使用了累积回报,以及状态价值函数的基本定义。最后即可得出当前状态价值函数的值为,在当前状态下,即时奖励与下一状态的折扣状态价值的期望之和。
其核心即阻碍与表示当前状态价值函数与下一刻状态价值函数之间的递归关系。
我们可以回溯树的方式更好的理解贝尔曼方程的计算。因回溯图中的关系是回溯运算的基础,也是强化学习的核心内容。通俗的讲,回溯操作就是讲后续状态的价值信息回传给当前时刻的状态。
其中空心圆表示一个状态,以状态作为根节点,智能体依据状态转移概率,可能会到达两个后续状态,以及在离开状态时获得的奖励。贝尔曼方程对所有可能性采用其出现概率进行了加权平均。这也就说明了起始状态的价值一定等于后续状态的(折扣)期望值加上对应收益的期望值。
这里通过之前的实例可以进行直观的验证。这里主要观测图中Class3状态下的状态值函数4.3的计算过程。
Class3状态下的即时奖励为,并有两个后续状态(0.6的概率转移到pass状态,0.4的概率转移到pub状态),同时设定了折扣系数为1。所以可以计算得出:
贝尔曼方程的矩阵形式
贝尔曼方程也可以简单得表示为矩阵的形式:
这里的价值函数是关于每个状态的价值函数的列向量,矩阵形式展开后的表示如下:
贝尔曼方程的求解
既然已经能够将贝尔曼方程表示为矩阵形式,并且其为线性方程,那么就可以直接进行求解:
对于一些低复杂度的MRP问题,这样直接计算解析解是非常快的,但是由于要计算矩阵的逆,其计算复杂度为。所以并不适用与复杂的计算场景,针对复杂MRP问题,一般用迭代的方式求解贝尔曼方程,例如:
- 动态规划(Dynamic programming)
- 蒙特卡洛方法(Monte-Carlo evaluation)
- 差分学习法(Temporal-Difference learning)
5.马尔科夫决策过程(Markov Decision Processes,MDP)
5.1 马尔科夫决策过程(Markov DecisionProcess)定义
到目前为止其实我们都没有讲到强化学习,因为我们虽然对原始的马尔科夫过程(Markov Process,MP)引入了奖励而引入马尔科夫奖励过程(Markov Reward Process,MRP),可是我们并没有决策的部分,强化学习本身是一个决策的问题。所以现在我们再引入一个因子,就是动作(Action)。从而将MRP问题变成了.马尔科夫决策过程(Markov Decision Processes,MDP)。此时才能算得上是强化学习。MDP是一个环境,里面的每个状态都满足马尔科夫性质(Markov Property)。
马尔科夫决策过程(Markov DecisionProcess)定义:
一个马尔科夫决策过程(Markov DecisionProcess),由一个五元组构成:
- S为有限的状态空间集,表示时间步的状态,其中
- A为动作空间集,表示时间步的动作,其中
- 为状态转移矩阵,表示在当前状态下执行动作后,转移到另一个状态的概率分布,可以记为
- R为奖励函数,表示在状态下执行动作后转移到另一个状态获得的奖励,
- 为折扣因子,
为了直观理解MDP过程,还是以之前的例子为例,图中红色的部分就是动作(Action)。
这里需要注意的是,因为有了动作的加入,奖励不再只和状态相关,还和动作有关。之前的奖励是离开状态就获取的即时奖励,现在是
在某个状态下采取特定动作后获取的即时奖励.
接下来我们将介绍在MDP的框架之下的一些基本要素。
5.1 策略(Policy)
策略是状态到动作的映射,在某个状态下采取什么样的动作,可以是确定的策略,也可以是一个随机策略(概率事件)。其定义如下:
- 策略完整定义了智能体的所有行为方式。
- MDP的策略只依赖于当前的状态,不依赖于历史状态。
- 策略是稳态的,不受时间约束。 即。
- 在给定一个MDP,以及一个策略,那么状态序列,可以表示的前面章节描述的马尔科夫过程(MP)为。
- 在给定一个MDP,以及一个策略,那么状态与奖励序列可以表示前面章节描述的的马尔科夫奖励过程(MRP)为。
上述中的状态转移矩阵与奖励函数定义为:
5.2 价值函数(Value Function)
MDP的价值函数和MRP的有一些不同,与策略相关。正因为有了策略,价值函数不再单纯的只和状态相关了。采取不同的策略,价值函数也会不同。因为从贝尔曼方程中我们也能看出,价值的计算和动作相关,而动作的选择就是策略。但是这里不得不提一下,这里的价值函数只是策略的价值函数,它的好坏不一定代表真正的状态的好坏,它只是根据你提供的这个策略计算出来的,提供的这个策略不一定是一个好策略,那么自然计算出来的价值不一定具有很强的参考性。
当执行到某一步时,如果需要评估当前智能体在该时间步状态的好坏程度,主要由价值函数(Value Function)来完成。由于价值函数的输入分为状态和<状态,价值>对,所以通常,当输入状态时统称为状态值函数,输入<状态,价值>对时统称为动作值函数,当不讨论其输入时,统称为价值函数。
一个马尔科夫决策过程的状态值函数是对未来奖励的预测,表示在状态下,跟随给定的策略会得到的奖励期望。
一个马尔科夫决策过程的动作值函数,表示在状态下,执行动作,并跟随给定的策略会得到的奖励期望。
5.3 马尔科夫决策过程的贝尔曼方程(Bellman Equation)
与在马尔科夫奖励过程的贝尔曼方程思想相同,状态值函数可以分解为即时奖励与下一状态的折扣状态价值的期望之和。
同时动作值函数也可以进行类似的分解:
为了方便理解,可以画出响应的状态值函数与动作值函数的回溯图。
状态值函数的回溯图
我们以根节点的空心圆表示当前的状态,以实心圆表示在当前状态智能体根据策略可能采取的动作。
状态值函数即可表示为对所有可能的动作产生的动作值函数进行了加权平均。
动作值函数的回溯图
我们以根节点的实心圆表示当前智能体根据策略已经选取的的动作,以空心圆表示在当前动作之后,智能体可能的下一步状态。其中也包含了在动作执行后得到的奖励。
动作值函数即可表示为,执行当前动作获得的奖励,加上对所有可能的未来状态的状态值函数进行了加权平均。
状态值函数的二次展开的回溯图
根据前面状态值函数的的溯图,进行下一个时间步的展开,考虑在动作后的状态。我们可以得到展开后的回溯图。
状态值函数即可表示为对所有可能的动作产生的动作值函数的详细二次分解进行了加权平均。
动作值函数的二次展开回溯图
根据前面动作值函数的回溯图,进行下一个时间步的展开,考虑在下一状态后,根据策略可能采用的新的动作。我们可以得到展开后的回溯图。
动作值函数即可表示为:
贝尔曼方程求解示例
下面我们顺着之前的例子,看看贝尔曼方程的求解过程:
这里我们需要求解Class3状态下的状态值函数。
MDP下贝尔曼方程的矩阵形式
在马尔科夫决策过程下的贝尔曼方程的矩阵形式与在马尔科夫奖励过程下的矩阵形式类似,只是考虑了策略。
其直接的解析解为:
计算复杂度为。所以并不适用与复杂的计算场景,针对复杂MRP问题,一般用迭代的方式求解贝尔曼方程。
5.3 最优值函数(Optimal Value Function)
由之前的介绍可知,强化学习的目标就是求解马尔科夫决策过程的最优策略,而值函数是对最优策略的表达。
最优值函数(Optimal Value Function)分为最优状态值函数(optimal state-value function)与最优动作值函数(optimal action_value function),他们的定义如下:
最优状态值函数(optimal state-value function)就是在所有策略当中,最大的状态值函数:
最优动作值函数(optimal action_value function)就是在所有策略当中,最大的动作值函数:
我们更希望的是最优值函数,最优值函数是与策略无关的,根据最优值函数可以直接得到最优策略。只需要沿着状态价值函数大的方向移动就行,这其实也就是强化学习中的一个流派,基于值学习的(相对于基于策略学习)。值比较大的状态就是好,比如终点前的一个状态值一般就比较大,因为下一刻就可以结束。此处用"一般"是因为考量的是状态值,如果这个状态不仅和终点相连并且还和几个失败点相连,状态值不一定大。参考贝尔曼方程计算公式,如果我们使用另一种动作值函数,代表状态下采取特定动作的价值。那么我们就可以说,终点前一个状态,采取动作可以直接到终点,这个一定是一个大值。这也提示了使用值一般比使用状态价值更好,因为考虑了动作。
最优值函数确定了马尔科夫决策过程中智能体的最优的可能表现。获得了最优值函数,也就获得了么个状态的最有价值,那么此时马尔科夫决策过程的所有变量都为已知的,接下来便能够很好的求解马尔科夫决策过程的问题。
5.3 最优策略(Optimal Policy)
最优策略(Optimal Policy)的定义为:
在状态下,当策略的价值函数优于任何其他策略的价值函数时,策略即为状态下的最优策略。关于马尔科夫决策过程的最优策略,有如下3个定理:
(1)对于任何马尔科夫决策过程问题,存在一个最优策略,其优于(至少等于)任何其他策略,即。
(2)所有最优策略下都有最优状态值函数,即
(3)所有最优策略下都有最优动作值函数,即
基于上述三个定理,寻找最优策略可以通过最优状态值函数或者最优动作值函数来得到。也就是说如果最优值函数已知,则可以获得马尔科夫决策过程的最优策略。
因此,可以通过最大化得到最优策略,具体的定义如下:
上式中,时,