第二章 马尔可夫决策过程(MDP)¶
关键词¶
马尔可夫性质(Markov property,MP):如果某一个过程未来的状态与过去的状态无关,只由现在的状态决定,那么其具有马尔可夫性质。换句话说,一个状态的下一个状态只取决于它的当前状态,而与它当前状态之前的状态都没有关系。
马尔可夫链(Markov chain): 概率论和数理统计中具有马尔可夫性质且存在于离散的指数集(index set)和状态空间(state space)内的随机过程(stochastic process)。
状态转移矩阵(state transition matrix):状态转移矩阵类似于条件概率(conditional probability),其表示当智能体到达某状态后,到达其他所有状态的概率。矩阵的每一行描述的是从某节点到达所有其他节点的概率。
马尔可夫奖励过程(Markov reward process,MRP): 本质是马尔可夫链加上一个奖励函数。在马尔可夫奖励过程中,状态转移矩阵和它的状态都与马尔可夫链的一样,只多了一个奖励函数。奖励函数是一个期望,即在某一个状态可以获得多大的奖励。
范围(horizon):定义了同一个回合(episode)或者一个完整轨迹的长度,它是由有限个步数决定的。
回报(return):把奖励进行折扣(discounted),然后获得的对应的奖励。
贝尔曼方程(Bellman equation):其定义了当前状态与未来状态的迭代关系,表示当前状态的价值函数可以通过下个状态的价值函数来计算。贝尔曼方程因其提出者、动态规划创始人理查德
蒙特卡洛算法(Monte Carlo algorithm,MC algorithm): 可用来计算价值函数的值。使用本节中小船的例子,当得到一个马尔可夫奖励过程后,我们可以从某一个状态开始,把小船放到水中,让它随波流动,这样就会产生一个轨迹,从而得到一个折扣后的奖励
动态规划算法(dynamic programming,DP): 其可用来计算价值函数的值。通过一直迭代对应的贝尔曼方程,最后使其收敛。当最后更新的状态与上一个状态差距不大的时候,动态规划算法的更新就可以停止。
Q函数(Q-function): 其定义的是某一个状态和某一个动作所对应的有可能得到的回报的期望。
马尔可夫决策过程中的预测问题:即策略评估问题,给定一个马尔可夫决策过程以及一个策略
马尔可夫决策过程中的控制问题:即寻找一个最佳策略,其输入是马尔可夫决策过程,输出是最佳价值函数(optimal value function)以及最佳策略(optimal policy)。其可以通过动态规划算法解决。
最佳价值函数:搜索一种策略
习题¶
2-1 为什么在马尔可夫奖励过程中需要有折扣因子?
(1)首先,是有些马尔可夫过程是环状的,它并没有终点,所以我们想避免无穷的奖励。
(2)另外,我们想把不确定性也表示出来,希望尽可能快地得到奖励,而不是在未来的某个时刻得到奖励。
(3)接上一点,如果这个奖励是有实际价值的,我们可能更希望立刻就得到奖励,而不是后面才可以得到奖励。
(4)还有,在有些时候,折扣因子也可以设为0。当它被设为0后,我们就只关注它当前的奖励。我们也可以把它设为1,设为1表示未来获得的奖励与当前获得的奖励是一样的。
所以,折扣因子可以作为强化学习智能体的一个超参数进行调整,然后就会得到不同行为的智能体。
2-2 为什么矩阵形式的贝尔曼方程的解析解比较难求得?
通过矩阵求逆的过程,我们就可以把
2-3 计算贝尔曼方程的常见方法有哪些,它们有什么区别?
(1)蒙特卡洛方法:可用来计算价值函数的值。以本书中的小船示例为例,当得到一个马尔可夫奖励过程后,我们可以从某一个状态开始,把小船放到水中,让它“随波逐流”,这样就会产生一条轨迹,从而得到一个折扣后的奖励
(2)动态规划方法:可用来计算价值函数的值。通过一直迭代对应的贝尔曼方程,最后使其收敛。当最后更新的状态与上一个状态区别不大的时候,通常是小于一个阈值
(3)以上两者的结合方法:我们也可以使用时序差分学习方法,其为动态规划方法和蒙特卡洛方法的结合。
2-4 马尔可夫奖励过程与马尔可夫决策过程的区别是什么?
相对于马尔可夫奖励过程,马尔可夫决策过程多了一个决策过程,其他的定义与马尔可夫奖励过程是类似的。由于多了一个决策,多了一个动作,因此状态转移也多了一个条件,即执行一个动作,导致未来状态的变化,其不仅依赖于当前的状态,也依赖于在当前状态下智能体采取的动作决定的状态变化。对于价值函数,它也多了一个条件,多了一个当前的动作,即当前状态以及采取的动作会决定当前可能得到的奖励的多少。
另外,两者之间是有转换关系的。具体来说,已知一个马尔可夫决策过程以及一个策略
2-5 马尔可夫决策过程中的状态转移与马尔可夫奖励过程中的状态转移的结构或者计算方面的差异有哪些?
对于马尔可夫链,它的转移概率是直接决定的,即从当前时刻的状态通过转移概率得到下一时刻的状态值。但是对于马尔可夫决策过程,其中间多了一层动作的输出,即在当前这个状态,首先要决定采取某一种动作,再通过状态转移函数变化到另外一个状态。所以在当前状态与未来状态转移过程中多了一层决策性,这是马尔可夫决策过程与之前的马尔可夫过程的不同之处。在马尔可夫决策过程中,动作是由智能体决定的,所以多了一个组成部分,智能体会采取动作来决定未来的状态转移。
2-6 我们如何寻找最佳策略,寻找最佳策略方法有哪些?
本质来说,当我们取得最佳价值函数后,我们可以通过对Q函数进行最大化,从而得到最佳价值。然后,我们直接对Q函数取一个让动作最大化的值,就可以直接得到其最佳策略。具体方法如下,
(1)穷举法(一般不使用):假设我们有有限个状态、有限个动作可能性,那么每个状态我们可以采取
(2)策略迭代: 一种迭代方法,其由两部分组成,以下两个步骤一直在迭代进行,最终收敛,其过程有些类似于机器学习中的EM算法(期望-最大化算法)。第一个步骤是策略评估,即当前我们在优化这个策略
(3)价值迭代: 我们一直迭代贝尔曼最优方程,通过迭代,其能逐渐趋向于最佳策略,这是价值迭代方法的核心。我们为了得到最佳的
面试题¶
2-1 友善的面试官:请问马尔可夫过程是什么?马尔可夫决策过程又是什么?其中马尔可夫最重要的性质是什么呢?
马尔可夫过程是一个二元组
马尔可夫决策过程是一个五元组
马尔可夫最重要的性质是下一个状态只与当前状态有关,与之前的状态无关,也就是
2-2 友善的面试官:请问我们一般怎么求解马尔可夫决策过程?
我们求解马尔可夫决策过程时,可以直接求解贝尔曼方程或动态规划方程:
特别地,其矩阵形式为
2-3 友善的面试官:请问如果数据流不具备马尔可夫性质怎么办?应该如何处理?
如果不具备马尔可夫性,即下一个状态与之前的状态也有关,若仅用当前的状态来求解决策过程,势必导致决策的泛化能力变差。为了解决这个问题,可以利用循环神经网络对历史信息建模,获得包含历史信息的状态表征,表征过程也可以使用注意力机制等手段,最后在表征状态空间求解马尔可夫决策过程问题。
2-4 友善的面试官:请分别写出基于状态价值函数的贝尔曼方程以及基于动作价值函数的贝尔曼方程。
(1)基于状态价值函数的贝尔曼方程:
(2)基于动作价值函数的贝尔曼方程:
2-5 友善的面试官:请问最佳价值函数
最佳价值函数的定义为
2-6 友善的面试官:能不能手写一下第