前面好几篇文章都在介绍强化学习(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](https://yqfile.alicdn.com/img_2de1d3996259c1b48c975315a0f7d136.png?x-oss-process=image/resize,w_1400/format,webp)
举个栗子:
如下图,一个学生学习一门课程,有6个状态:从Class1 到 Class 3 的学习,到Pass再到去Sleep。中间可能去刷Facebook, 去Sleep或者去酒吧(Pub)喝酒。
![img_151a192b20b06307dc3499a76f99ead8.png](https://yqfile.alicdn.com/img_151a192b20b06307dc3499a76f99ead8.png?x-oss-process=image/resize,w_1400/format,webp)
其中,那些数字(0.9,0.1)和箭头就代表了Pss' 的数值和状态转移的方向。Pss' 实际上是一个矩阵,如下图:
![img_bddcb112c8f282f3d237ecf663744102.png](https://yqfile.alicdn.com/img_bddcb112c8f282f3d237ecf663744102.png?x-oss-process=image/resize,w_1400/format,webp)
3. 马可夫奖励过程(Markov Reward Process)
奖励R是环境的反馈,当然这个反馈是与行动A, 相关的。在还没引入行动这个概念之前,暂且认为只与状态S有关。下图是加上了奖励参数的样子:
![img_cf431fb2e538bbc3ddaff8ff3cf0f166.png](https://yqfile.alicdn.com/img_cf431fb2e538bbc3ddaff8ff3cf0f166.png?x-oss-process=image/resize,w_1400/format,webp)
我们的目标Gt是获得奖励,有了R,有了S,有了Pss' 矩阵,实际上我们就能够估算出每一个S上的Gt:E(Gt|St = S)。
Gt 是这样定义的:
![img_a29fb0569619949c16acc6d3731857b5.png](https://yqfile.alicdn.com/img_a29fb0569619949c16acc6d3731857b5.png?x-oss-process=image/resize,w_1400/format,webp)
G t的物理意义就是之后状态的所有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](https://yqfile.alicdn.com/img_557c673ae92ccdcc2c513fdc7d902143.png?x-oss-process=image/resize,w_1400/format,webp)
R s是这个状态的奖励,S' 是下一个状态(下个可能的状态可能不止一个),P ss'就是之前提到的State transition probability matrix。
这个公式的物理意义也很简单,就是这个状态的奖励加上所有可能的下一个状态的v(S')和对应的Pss' 的乘积之和,再乘以衰减值γ。
我们可以轻易验证4.3这个v(s) 是否正确,如下图(γ=1)
![img_795c12fdc4c083470be0f3e16e4f28ed.png](https://yqfile.alicdn.com/img_795c12fdc4c083470be0f3e16e4f28ed.png?x-oss-process=image/resize,w_1400/format,webp)
5. MDP(Markov Decision Processes马可夫决策过程)
有了前面MP的铺垫,加上D(Decision)就是MDP(马可夫决策过程了)。这个决策是要决策什么呢?就是要决策行动(Action)。
正如之前提到的,行动A的奖励R不仅跟状态S相关,而且与行动A也是相关的,还是之前学生学习课程的例子,加上行动和与行动相关的R,如图:
![img_23c86864072a3e690820f83981ba9fc1.png](https://yqfile.alicdn.com/img_23c86864072a3e690820f83981ba9fc1.png?x-oss-process=image/resize,w_1400/format,webp)
(注意pub 那个黑点这里变成了行动,而不是状态,主要是为了后面区分sate-value function 和 action-value function)
6. 策略(Policy)
DP是一个随机的过程,在有了策略 (policy)π之后才整个过程才有了规律,策略也是一个概率分布,体现了在给定状态下采取行动的概率。
![img_e25f538e9b359f0453dda97e1f603e21.png](https://yqfile.alicdn.com/img_e25f538e9b359f0453dda97e1f603e21.png?x-oss-process=image/resize,w_1400/format,webp)
策略是用来指导行动的,不要与描述状态间的Pss' 混淆了。当然两者是有联系的,后面将会提到。
7. Value Function(值函数)
这是MDP最重要的的概念。前面已经提到了状态值函数(State-Value Function)v(S)(后面简称V函数),但是没有机器人,没有策略指导机器人的行动。
有了策略π之后vπ(s)的物理意义就是,在该策略的指导下,在目前这个状态下,之后能够预期的到的的奖励是多少。
![img_883ea4068de25a6cb0d7b6a097f369f2.png](https://yqfile.alicdn.com/img_883ea4068de25a6cb0d7b6a097f369f2.png?x-oss-process=image/resize,w_1400/format,webp)
当然我们更关心策略是如何指导行动的,我们引入行动值函数(Action-Value Function) qπ(s,a) 的概念。看起来是不是很眼熟,因为我们通常又叫他q函数,参见之前的文章Q-Learning。
因为加入了行动,所以q函数的物理意义就是,在当前策略的指导下,在当前状态下,采取行动a之后所能预期得到的奖励是多少。
![img_cb739165d1f714c44b48c8666bdb48ef.png](https://yqfile.alicdn.com/img_cb739165d1f714c44b48c8666bdb48ef.png?x-oss-process=image/resize,w_1400/format,webp)
8. V函数和Q函数的关系
V函数和Q函数都是递归关系,这个通过Bellman 等式也可以证明,这里也不再赘述。
![img_896c061dbe373536ff18637ac441cdc9.png](https://yqfile.alicdn.com/img_896c061dbe373536ff18637ac441cdc9.png?x-oss-process=image/resize,w_1400/format,webp)
![img_6af5a348d00d70ea33a24c0aa80b2ed8.png](https://yqfile.alicdn.com/img_6af5a348d00d70ea33a24c0aa80b2ed8.png?x-oss-process=image/resize,w_1400/format,webp)
通过Q函数来求V函数:
![img_fe9633d8ec6177b66b1be7aa62f85b78.png](https://yqfile.alicdn.com/img_fe9633d8ec6177b66b1be7aa62f85b78.png?x-oss-process=image/resize,w_1400/format,webp)
上图,空心代表状态,实心代表行动。所有行动的策略π(a|s)与Q函数qπ()的乘积之和就能得到V函数。
![img_0a5e8db75457ee8f3f2666b3a014645f.png](https://yqfile.alicdn.com/img_0a5e8db75457ee8f3f2666b3a014645f.png?x-oss-process=image/resize,w_1400/format,webp)
同样的,所有下一个状态的V函数与对应的Pss'乘积之和再加上采取该行动的奖励就能求得Q函数。
再次注意,Pss'反映的是状态间的转移概率,π(a|s)是状态和行动间的策略概率
当然上面两图组合(公式的带入)就能反映该状态的V函数和下一个状态的V函数的递归关系。
![img_6c989721f660be88f2af126ad95f19b9.png](https://yqfile.alicdn.com/img_6c989721f660be88f2af126ad95f19b9.png?x-oss-process=image/resize,w_1400/format,webp)
倒过来组合(公式带入)就能反映该行动下的Q函数和下一个行动的Q函数的递归关系。
![img_372cdd096a0712cc9920846f86a9a1bb.png](https://yqfile.alicdn.com/img_372cdd096a0712cc9920846f86a9a1bb.png?x-oss-process=image/resize,w_1400/format,webp)
。
利用上面的公式我们可以轻易验证例子中pass的V函数:
注意:π(a|study)= π(a|pub) =0.5
![img_581173e9966970342caae66415a2c156.png](https://yqfile.alicdn.com/img_581173e9966970342caae66415a2c156.png?x-oss-process=image/resize,w_1400/format,webp)
总结
本文介绍了MDP的基本概念,然而我们了解MDP的概念是为了指导我们的行动,从而得到最优的结果。换句话说就是选择最优的策略,得到最多的奖励。再换句话说就是求最大的V函数和Q函数,这些内容将放到下一篇文章再做介绍。
文章首发steemit.com 为了方便墙内阅读,搬运至此,欢迎留言或者访问我的Steemit主页