马尔可夫决策过程MarkovDecisionProcess,MDPKintoki

Original url:

http://www.tuicool.com/articles/b6BjAva

1. 马尔可夫模型的几类子模型

我想大家一定听说过马尔科夫链(Markov Chain)&＃xff0c; 搞机器学习的也都知 道隐马尔可夫模型(Hidden Markov Model&＃xff0c;HMM)。它们具有的一个共同性质就是马尔可夫性(无后效性)&＃xff0c;也就是指系统 的下个状态只与当前状态信息有关&＃xff0c;而与更早之前的状态无关。

马尔可夫决策过程(MDP)也具有马尔可夫性&＃xff0c;与上面不同的是MDP考虑了动作&＃xff0c;即系统下个状态不仅和当前的状态有关&＃xff0c;也和当前采取的动作有关。还是举下棋的例子&＃xff0c;当我们在某个局面&＃xff08;状态s&＃xff09;走了一步(动作a)&＃xff0c;这时对手的选择&＃xff08;导致下个状态s’&＃xff09;我们是不能确定的&＃xff0c;但是他的选择只和s和a有关&＃xff0c;而不用考虑更早之前的状态和动作&＃xff0c;即s’是根据s和a随机生成的。

我们用一个二维表格表示一下&＃xff0c;各种马尔可夫子模型的关系就很清楚了&＃xff1a;

2. 马尔可夫决策过程

一个马尔可夫决策过程由一个四元组构成(S, A, P sa , R)   [ 注]

• S: 表示状态集&＃xff08;states&＃xff09;
• A:表示一组动作&＃xff08;actions&＃xff09;
• P sa : 表示状态转移概率。P sa  表示的是在当前s ∈ S状态下&＃xff0c;经过a ∈ A作用后&＃xff0c;会转移到的其他状态的概率分布情况。比如&＃xff0c;在状态s下执行动作a&＃xff0c;转移到s’的概率可以表示为p(s’|s,a)
• R: S×A→ℝ&＃xff0c;R是回报函数&＃xff08;reward  function&＃xff09;&＃xff0c;回报函数有时也写作状态S的函数&＃xff08;只与S有关&＃xff09;&＃xff0c;这样的话&＃xff0c;R可以简化为R: S→ℝ。

MDP 的动态过程如下&＃xff1a;某个智能体(agent)的初始状态为s 0 &＃xff0c;然后从 A 中挑选一个动作a 0 执行&＃xff0c;执行后&＃xff0c;agent 按P sa 概率随机转移到了下一个s 1 状态&＃xff0c;s 1 ∈ P s 0a 0。然后再执行一个动作a 1 &＃xff0c;就转移到了s 2 &＃xff0c;接下来再执行a 2 …&＃xff0c;我们可以用下面的图表示状态转移的过程。

如果回报r是根据状态s和动作a得到的&＃xff0c;则MDP还可以表示成下图&＃xff1a;

3. 值函数(value function)与贝尔曼方程(Bellman equation)

上篇我们提到增强学习学到的是一个从环境状态到动作的映射&＃xff08;即行为策略&＃xff09;&＃xff0c;记为策略π: S→A。而增强学习往往又具有延迟回报的特点: 如果在第n步输掉了棋&＃xff0c;那么只有状态s n 和动作a n 获得了立即回报r(s n ,a n )&＃61;-1&＃xff0c;前面的所有状态立即回报均为0。所以对于之前的任意状态s和动作a&＃xff0c;立即回报函数r(s,a)无法说明策略的好坏。因而需要定义值函数(value function&＃xff0c;又叫效用函数)来表明当前状态下策略π的长期影响。

常见的值函数有以下三种&＃xff1a;

其中

a)是采用策略π的情况下未来有限h步的期望立即回报总和&＃xff1b;

b)是采用策略π的情况下期望的平均回报&＃xff1b;

c)是值函数最常见的形式&＃xff0c;式中γ∈[0,1]称为折合因子&＃xff0c;表明了未来的回报相对于当前回报的重要程度。特别的&＃xff0c;γ&＃61;0时&＃xff0c;相当于只考虑立即不考虑长期回报&＃xff0c;γ&＃61;1时&＃xff0c;将长期回报和立即回报看得同等重要。接下来我们主要讨论的是第三种形式

定义状态值函数&＃xff08;值函数&＃xff09;如下&＃xff1a;

定义动作值函数&＃xff08;Q函数&＃xff09;如下&＃xff1a;

根据动态规划相关理论&＃xff0c;给定MDP模型M&＃61;(S, A, P, γ, R)和策略π:S→A&＃xff0c;则状态值函数V π 和动作值函数Q π 满足以下的贝尔曼方程&＃xff1a;

而最优策略可以由下式表示&＃xff1a;

即我们寻找的是在任意初始条件s下&＃xff0c;能够最大化值函数的策略π*。

与最优策略π*对应的状态值函数V*与动作值函数Q*之间存在如下关系&＃xff1a;

4. 立即回报&＃xff0c;&＃xff08;状态&＃xff09;值函数&＃xff0c;Q函数的例子

上面的概念可能描述得不太清晰&＃xff0c;接下来举例说明&＃xff0c;如图所示是一个格子世界&＃xff0c;我们假设agent从左下角的start点出发&＃xff0c;右上角为目标位置&＃xff0c;称为吸收状态(Absorbing state)&＃xff0c;对于进入吸收态的动作&＃xff0c;我们给予立即回报100&＃xff0c;对其他动作则给予0回报&＃xff0c;折合因子γ的值我们选择0.9。

1.立即回报r(s,a)如下所示&＃xff0c;每个格子代表一个状态s&＃xff0c;箭头则代表动作a&＃xff0c;旁边的数字代表立即回报&＃xff0c;可以看到只有进入目标位置的动作获得了回报100&＃xff0c;其他动作都获得了0回报。

2. Q(s,a)值如下所示

3. 值函数V(s)如下所示&＃xff0c;对比上图可以看到 

至此我们了解了马尔可夫决策过程的基本概念&＃xff0c;知道了增强学习的目标&＃xff08;获得最佳策略π*&＃xff09;&＃xff0c;下一篇开始介绍求解最优策略的方法。

发现写东西还是蛮辛苦的&＃xff0c;希望对大家有用。另外自己也比较菜&＃xff0c;没写对的地方欢迎指出哈~~

[注]采用折合因子作为值函数的MDP也可以定义为五元组M&＃61;(S, A, P, γ, R)。也有的书上把值函数作为一个因子定义五元组。还有定义为三元组的&＃xff0c;不过MDP的基本组成元素是不变的。

参考资料&＃xff1a;

[1] R.Sutton et al. Reinforcement learning: An introduction , 1998

[2] T.Mitchell. 《机器学习》&＃xff0c;2003

[3] 金卓军&＃xff0c;逆向增强学习和示教学习算法研究及其在智能机器人中的应用[D]&＃xff0c;2011

[4] Oliver Sigaud et al&＃xff0c;Markov Decision Process in Artificial Intelligence[M], 2010