AI学习笔记——MDP(Markov Decision Processes马可夫决策过程)简介

  1. 云栖社区>
  2. 博客>
  3. 正文

AI学习笔记——MDP(Markov Decision Processes马可夫决策过程)简介

hongtao2018 2018-09-21 20:10:00 浏览641
展开阅读全文

前面好几篇文章都在介绍强化学习(RL),以及强化学习的一些具体算法,但是强化学习中用到的最重要的理论MDP却还没提到。这篇文章就来说说MDP。

讲MDP的文章和资料非常多,理论和数学公式也能轻易找到,所以本文并不是要严谨地推导MDP,而是想让读者感性地认识MDP以及它对强化学习的重要性。本文主要的参考资料来自于David Silver 教授(DeepMind 的创始人)在UCL的课程以及Richard S. Sutton and Andrew G. Barto的经典书籍:Reinforcement Learning: An Introduction

1. MDP需要满足的条件

RL是要通过对环境不停地试错来学习的,MDP就是用来描述RL中的环境。

  • 这个环境必须是完全可观测的(Fully Observable)。几乎所有的RL问题都可以转换成MDP的环境。
  • 未来只与当前的状态有关,与之前的历史没有关系。换句话说就是当前的状态一旦确定了,之前的历史就可以抛弃了,因为未来只与当前有关。
2. MP(Markov Process 马可夫过程)

注意,MDP除去决策"D",就是MP。MP是一个随机过程。从现在状态 S下一个状态 S' 通过Pss' 状态转移概率矩阵(State transition probability matrix)来完成这个过程, Pss'只是概率,所以MP还是随机的。

img_2de1d3996259c1b48c975315a0f7d136.png

举个栗子:
如下图,一个学生学习一门课程,有6个状态:从Class1 到 Class 3 的学习,到Pass再到去Sleep。中间可能去刷Facebook, 去Sleep或者去酒吧(Pub)喝酒。


img_151a192b20b06307dc3499a76f99ead8.png

其中,那些数字(0.9,0.1)和箭头就代表了Pss' 的数值和状态转移的方向。Pss' 实际上是一个矩阵,如下图:

img_bddcb112c8f282f3d237ecf663744102.png
3. 马可夫奖励过程(Markov Reward Process)

奖励R是环境的反馈,当然这个反馈是与行动A, 相关的。在还没引入行动这个概念之前,暂且认为只与状态S有关。下图是加上了奖励参数的样子:


img_cf431fb2e538bbc3ddaff8ff3cf0f166.png

我们的目标Gt是获得奖励,有了R,有了S,有了Pss' 矩阵,实际上我们就能够估算出每一个S上的Gt:E(Gt|St = S)。
Gt 是这样定义的:

img_a29fb0569619949c16acc6d3731857b5.png

Gt的物理意义就是之后状态的所有R的总和。

γ为衰减值(0到1之间),我们在之前Q-Learning中已经介绍过了,就不多说了。

这个估算出来的Gt就叫做这个状态S上的Sate Value function(状态值函数): v(S)

4. Bellman 等式

v(S)很明显是一个递归的过程,也就是说知道了最终状态v(S最终)(上面那个例子是Sleep)就可以倒推到初始状态的v(S初始),这个关系就是用Bellman 等式表达出来的。

在任意一个状态S如何求v(S)呢?需要用到下面这个公式

img_557c673ae92ccdcc2c513fdc7d902143.png

Rs是这个状态的奖励,S' 是下一个状态(下个可能的状态可能不止一个),Pss'就是之前提到的State transition probability matrix。

这个公式的物理意义也很简单,就是这个状态的奖励加上所有可能的下一个状态的v(S')和对应的Pss' 的乘积之和,再乘以衰减值γ。

我们可以轻易验证4.3这个v(s) 是否正确,如下图(γ=1)


img_795c12fdc4c083470be0f3e16e4f28ed.png
5. MDP(Markov Decision Processes马可夫决策过程)

有了前面MP的铺垫,加上D(Decision)就是MDP(马可夫决策过程了)。这个决策是要决策什么呢?就是要决策行动(Action)

正如之前提到的,行动A的奖励R不仅跟状态S相关,而且与行动A也是相关的,还是之前学生学习课程的例子,加上行动和与行动相关的R,如图:


img_23c86864072a3e690820f83981ba9fc1.png

(注意pub 那个黑点这里变成了行动,而不是状态,主要是为了后面区分sate-value function 和 action-value function)

6. 策略(Policy)

DP是一个随机的过程,在有了策略 (policy)π之后才整个过程才有了规律,策略也是一个概率分布,体现了在给定状态下采取行动的概率。


img_e25f538e9b359f0453dda97e1f603e21.png

策略是用来指导行动的,不要与描述状态间的Pss' 混淆了。当然两者是有联系的,后面将会提到。

7. Value Function(值函数)

这是MDP最重要的的概念。前面已经提到了状态值函数(State-Value Function)v(S)(后面简称V函数),但是没有机器人,没有策略指导机器人的行动。

有了策略π之后vπ(s)的物理意义就是,在该策略的指导下,在目前这个状态下,之后能够预期的到的的奖励是多少。

img_883ea4068de25a6cb0d7b6a097f369f2.png

当然我们更关心策略是如何指导行动的,我们引入行动值函数(Action-Value Function) qπ(s,a) 的概念。看起来是不是很眼熟,因为我们通常又叫他q函数,参见之前的文章Q-Learning

因为加入了行动,所以q函数的物理意义就是,在当前策略的指导下,在当前状态下,采取行动a之后所能预期得到的奖励是多少。


img_cb739165d1f714c44b48c8666bdb48ef.png
8. V函数和Q函数的关系

V函数和Q函数都是递归关系,这个通过Bellman 等式也可以证明,这里也不再赘述。


img_896c061dbe373536ff18637ac441cdc9.png

img_6af5a348d00d70ea33a24c0aa80b2ed8.png

通过Q函数来求V函数:


img_fe9633d8ec6177b66b1be7aa62f85b78.png

上图,空心代表状态,实心代表行动。所有行动的策略π(a|s)与Q函数qπ()的乘积之和就能得到V函数。

img_0a5e8db75457ee8f3f2666b3a014645f.png

同样的,所有下一个状态的V函数与对应的Pss'乘积之和再加上采取该行动的奖励就能求得Q函数。

再次注意,Pss'反映的是状态间的转移概率,π(a|s)是状态和行动间的策略概率

当然上面两图组合(公式的带入)就能反映该状态的V函数和下一个状态的V函数的递归关系。


img_6c989721f660be88f2af126ad95f19b9.png

倒过来组合(公式带入)就能反映该行动下的Q函数和下一个行动的Q函数的递归关系。


img_372cdd096a0712cc9920846f86a9a1bb.png

利用上面的公式我们可以轻易验证例子中pass的V函数:
注意:π(a|study)= π(a|pub) =0.5


img_581173e9966970342caae66415a2c156.png
总结

本文介绍了MDP的基本概念,然而我们了解MDP的概念是为了指导我们的行动,从而得到最优的结果。换句话说就是选择最优的策略,得到最多的奖励。再换句话说就是求最大的V函数和Q函数,这些内容将放到下一篇文章再做介绍。


文章首发steemit.com 为了方便墙内阅读,搬运至此,欢迎留言或者访问我的Steemit主页

网友评论

登录后评论
0/500
评论
hongtao2018
+ 关注