Markov Decision Process (MDP)
Table of Contents
1. Markov Decision Processes 简介
Markov decision processes (MDPs) provide a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker.
1.1. 一个例子
假设一个智能体(Agent)在图 1 中所示的
Figure 1: (a) 一个简单的
如果环境是确定的,得到一个解很容易:[Up, Up, Right, Right, Right]。不幸的是,由于行动是不可靠的(比如对机器人的控制不可能完全精确),所以环境不一定沿着这个解发展。图 1 (b) 是一个环境转移模型的示意,每步行动以
我们用
对于完全可观察的环境,马尔可夫决策过程可表示为:
1、初始状态:
2、转移模型:
3、回报函数:
那么,上面问题的解是什么样的?显然任何固定的行动序列都无法解决这个问题,这是因为智能体可能最后移动到非目标的其他状态。因此, MDP 问题的解必须指定在智能体可能到达的任何状态下,智能体应当采取什么行动。这种类型的解称为策略(policy)。 通常我们用
策略
图 2 (a)是对于非终止状态中
Figure 2: (a) 是对于非终止状态中
图 2 (a)是对于图 1 环境的一个最优策略。注意,因为多走一步的代价与偶然结束在状态
参考:
http://lanbing510.info/2015/11/17/Master-Reinforcement-Learning-MDP.html
http://lanbing510.info/2018/07/16/DQN.html
http://lanbing510.info/2018/07/17/DQN.html
1.2. “累加回报”和“折扣回报”
1.3. 用 MDP 对“给西瓜浇水问题”进行建模
我们考虑一下如何种西瓜。种瓜有许多步骤,从一开始的选种,到定期浇水、施肥、除草、杀虫,经过一段时间才能收获西瓜。通常要等到收获后,我们才知道种出的瓜好不好。若将得到好瓜作为辛勤种瓜劳动的奖赏,则在种瓜过程中当我们执行某个操作(例如,施肥)时, 并不能立即获得这个最终奖赏,甚至难以判断当前操作对最终奖赏的影响,仅能得到一个当前反馈(例如,瓜苗看起来更健壮了)。我们需多次种瓜,在种瓜过程中不断摸索,然后才能总结出较好的种瓜策略。这个过程抽象出来,就是“强化学习”(reinforcement learning)。强化学习任务通常用马尔可夫决策过程来描述。
Figure 3: “给西瓜浇水问题”的马尔可夫决策过程
图 3 给出了一个简单的例子:给西瓜浇水的马尔可夫决策过程。该任务中只有四个状态(健康、缺水、溢水、凋亡)和两个动作(浇水、不浇水),在每一个步转移后,若状态是保持瓜苗健康则获得奖赏
本节的例子摘自:机器学习,周志华,第 16 章,强化学习
2. 求解 MDP
2.1. Value iteration (a.k.a. dynamic programming)
2.1.1. 状态的效用值
在节 1.2 中已经介绍过“状态的效用值是通过状态序列的效用值来定义的”,这里把它描述得更加正式一些。
粗略地说, 一个状态的效用值就是“可能跟随它出现的所有状态序列”的期望效用值。 显然,状态序列取决于执行的策略,在策略
上式也称为 策略
可以证明,最优策略对应的值函数
如果回报函数
上式中,
注 1:贝尔曼是动态规划(Dynamic Programming)的创始人。
注 2:贝尔曼等式表明:一个状态的效用值是“转移到下一个状态的回报加上下一个状态效用值”的最大值。
注 3:这里不证明为什么
一旦我们求得了所有状态
2.1.2. 求解状态效用值(求解贝尔曼等式)
贝尔曼等式是求解 MDP 的基础。如果有
其它每个状态也都有一个相应的贝尔曼等式。这
下面介绍使用“迭代法”求解贝尔曼等式组成的方程组。从任意的初始值开始,我们算出等式右边的值,再把它代入到左边——这相当于 根据它们的邻接状态的效用值来更新每个状态的效用值。如此重复直到达到一种均衡(即各个状态效用值不再变化)。
设
注:多次应用贝尔曼更新,它一定会达到均衡,而且均衡时的效用值一定是贝尔曼方程组的唯一解。这里不证明为什么会这样,感兴趣的读者可以参考:《人工智能:一种现代方法(第二版)》17.2.3 价值迭代的收敛。
图 4 是对节 1.1 所示例子进行贝尔曼更新的实例(图片摘自http://mas.cs.umass.edu/classes/cs683/lectures-2010/Lec13_MDP2-F2010-4up.pdf)。
Figure 4: 贝尔曼更新的迭代实例(红色数字为迭代次数)
2.1.3. 求解最优策略
2.1.4. 总结:价值迭代算法
前面完整地介绍了价值迭代算法的细节,可总结为图 6 所示(摘自 Markov Decision Processes in Artificial Intelligence, 1.6.2.2 The value iteration algorithm),这个图中
Figure 6: 使用“价值迭代”算法求解 MDP 问题的最优策略
2.2. Policy iteration
策略迭代是求解 MDP 的一种通用框架,思想比较简单。
策略迭代算法从某个初始策略
(1) 策略评价(Policy Evaluation):给定策略
(2) 策略改进(Policy Improvement):已知状态效用值,计算新策略
当上面两个步骤没有产生效用值的改变(或策略的改变)时,算法终止。
“策略迭代”算法如图 7 所示,这个图中
Figure 7: 使用“策略迭代”算法求解 MDP 问题的最优策略
给定策略
假设
可以看到上面式子中没有贝尔曼等式中的“max”运行算,它们是普通的线性方程组!采用标准的线性代数方法可以在
2.2.1. Value iteration VS. Policy iteration
对于小的状态空间,策略迭代一般能够更快的收敛;但对于状态规模很大的 MDP,策略迭代中求每个状态的效用值
价值迭代(动态规划思想)要求在一个完全已知的环境模型中,这在现实中很少存在。
3. 参考
《人工智能:一种现代方法》第 17 章 制定复杂决策
Markov Decision Processes in Artificial Intelligence