强化学习通俗理解系列二：马尔科夫决策过程MDP

   作者：黄海安           

编辑：陈人和           

前  言

  第二篇文章是整个强化学习基础知识中最重要的，请大家保持警惕。前面系列一我把马尔科夫奖赏过程的全部内容讲完了，下面开始分析马尔科夫决策过程，写作思路依然是参考Divad Silver强化学习课程ppt,由于本人水平有限，如有问题，欢迎指正，我即时修改，谢谢！ 
       本文思路：

1. 马尔科夫决策过程的基本定义 2. 策略policy 3. 策略policy进阶 4. 值函数 5. 贝尔曼期望方程 6. 贝尔曼期望方程的矩阵形式 7. 最优值函数Optimal Value Function 8. 最优策略Optimal Policy 9. 贝尔曼最优方程 Bellman Optimality Equation 10. 总结

1

马尔科夫决策过程（Markov  Decision Process,,MDP)基础定义

马尔科夫奖赏过程是在马尔科夫过程基础上增加了奖励和衰减因子，从而引入了状态值函数，而马尔科夫决策过程MDP是在马尔科夫奖赏过程基础上引入了action或者说决策，从而将问题彻底转化为了决策问题，这才真正进入了强化学习路线！MDP问题虽然是加了决策，但是优化对象依然是值函数(当然还可以其他方式，例如最优策略)，当最优的值函数求出后，最优决策其实也就确定了，后面会细说。
       MDP的官方定义如下：

可以明显看出，和MRP的不同就是多引入了一个A，代表一系列动作集。同时需要注意了：相应的P和R都已经改变了，都是需要考虑A的，也就是说由于action的引入会影响状态转移矩阵P和相应的回报R，这是非常容易理解的，比如说平时我骂你，你可能不会转移到生气这个状态，但是如果我打你一下，再骂你的话，那么你就很可能会转移到生气这个状态了。当然回报也是有影响的。依然以学生为例，现在学生的状态转移图变成了如下图：

作为对比，可以看下以前的图：

大家发现区别了吧。同一个状态下采取不同的行为得到的即时奖励是不一样的。MRP里面的状态现在变成了MDP里面的ation，而MDP里面的状态就直接用空心圆圈代替了，也就是说MDP和MRP即使都是求最优值函数，但是意义是不一样的，MDP求出的最优值函数其实就直接表征了最优决策。大家要习惯这种转变。

2

策略policy

既然引入了动作，那么就需要引入新的概念了。策略是概率的集合或分布，其元素 为对过程中的某一状态s采取可能的行为a的概率,用表示。可能大家会很疑惑这个东西，其实它的意思是动作action是一个关于状态的布，以上图为例：在MRP图的class2状态处，我执行action{sleep，study}是有概率的，我有0.8的概率去执行study，有0.2的概率去执行sleep,这就是一个；在执行去酒吧pub的action后，学生有{0.2,0.4,0.4}的概率转向三个状态，这就是状态转移概率，可以看出和action有关，又或者举例：小型无人机特技表演，现在我发出一个往上飞的action，但是飞机就一定会进入往上飞的状态吗？其实不一定，因为还有风向、风速、干扰的影响，所以说我在某个状态下，采取的action是一个分布（policy），采用某个action后，进入某个状态也是一个分布(P)，如果我能够把风向、风速、干扰的影响完全考虑进去，那么这个MDP问题的最优决策就比较完美了，但是实际上是不可能的。
       policy的定义是：

有了上面的分析，看这个公式应该非常好理解了吧。其实可以直接理解为在每一个状态和状态中插入了一个实心黑点而已，这个黑点就是action，后面会细说。

3

策略policy进阶

刚才说过引入了策略后，状态转移概率P和回报R都和action有关了，那么公式肯定也要稍微修改一下了。

按照ppt中标准写法是：当给和一个策略，那么状态序列是一个马尔科夫过程；同样，状态和奖励序列 是一个马尔科夫奖励过程，并且在这个奖励过程中满足下面两个方程:

      举上图例子来说明：为了方便表述，将MRP中{facebook,class1,class2,class3,pass,pub,sleep}状态顺序对应的MDP中的空心圆圈状态{s1,s2,s3,s4,s5},我没有画图，大家应该知道哪个对应哪个吧？假设要计算

的值，按照公式，因为在s3状态下，执行study的概率是0.8，而在study动作下，由s3转移到s4是必然的，所以概率是1。再写一个复杂点的，计算，不好意思，我算不出了，因为路径实在是太多了，可以是sleep,s3->s5；可以是study,s3-s4，然后study,s4->s5；可以是stduy,s3->s4,然后pub,s4->s3,sleep,s3->s5，这里面还有loop，要把这些所有路径的概率求和才算完成(ps:那实际上该如何计算呢？还是迭代法求解)。同样的对于回报R，算法是完全一致的。

4

值函数

前面算了一大堆的其实本质就是为了值函数服务的，因为前面说过强化学习目的就是最大化值函数。好的，现在引入了策略，有些地方就得改改了，这就引入了两个值函数：状态值函数state-value function和动作值函数action-value funtion。完整定义如下：

状态值函数的定义没变，只不过多了一个动作值函数或者行为值函数，表示在执行策略π时，对当前状态s执行某一具体行为a所能的到的收获的期望；或者说在遵循当前策略π时，衡量对当前状态执行行为a的价值大小。这样看感觉不好理解，下面看具体例子：

       例如要求2.7那个状态下的值函数那个状态），直接算你会发现算不了，因为后续路径非常多，而要求那个状态，a=study)发现也不好算，因为路径还是很多，那么真正解决该问题的办法依然是迭代法，那么依然要引入牛逼的贝尔曼期望方程，一切问题就都不是问题。关于上图中的状态值函数具体数值，大家学到这里是肯定不知道如何算出来的，需要用到后面的贝尔曼期望方程。

5

贝尔曼期望方程

前面只是定义了MDP下的状态值函数和行为值函数，但是直接算是算不出来的，这是贝尔曼期望方程就出场了。贝尔曼期望方程是用于将值函数转化为迭代求解方程，使得问题更容易求解。大家如果理解了MRP中的贝尔曼方程，那么这里也非常好理解了。首先是状态值函数:

同样，动作值函数:

，是不是感觉很乱，看到下面的图你就会豁然开朗了：

---

图中，空心白圆圈是状态-状态值函数对；黑心实圆圈是动作-动作值函数对

---

可以看出，状态值函数v和动作值函数q是有关系的

---

如果不打算显视的求动作值函数，那么可以使用上图形式。

---

如果不打算显示的求状态值函数，那么可以使用上图形。看到了没，通过贝尔曼期望方程，这样就转化为了迭代形式了，求解就容易多了。
       依然以学生为例：

状态值函数
                

 计算时候由于箭头的原因，依然使用了上一时

的值，这是允许的，因为循环迭代更新嘛！到这里就真的可以算出每个状态的值函数了。

6

贝尔曼期望方程的矩阵形式

和MRP一样，可以写成矩阵形式：

同样的，小规模问题可以直接求解，大规模问题采用迭代法。

7

最优值函数Optimal Value Function

好了，现在我们已经能算任意给定策略action下，每个状态的值函数取值了，不管你是采用迭代法还是线性代数法。但是现在又有一个问题了：那么哪种策略下，能够使得状态s的值函数最大呢？因为一旦我们找出来最优值函数，也就是找出来最优策略，然后一直执行该策略就好了。举例说明：假设要训练一个机器人快速走迷宫，现在我给定一些策略，该策略可以使得机器人走出去，在该策略下，我通过迭代法可以求出每个状态的值函数，然后依据累积回报最大化原则，就可以选出一条当前最优的策略了，但是你确定你给的就是最优策略了吗？假设我再给其他一些策略，它得到的状态值函数更大呢，那么说明我给的策略是更优的。现在有一个疑问：既然我自己知道最优路径是哪个，那我就直接给定最优策略就好了嘛，还强化学习啥呀？其实不是的，对于特别复杂问题，我们自己也不知道最优策略是啥，只能通过机器人自己探索和开发出来，不需要人为的干扰，这就涉及到后面的策略估计和策略提升步骤了。上面我们举的学生例子，他的策略是已经给定了，虽然策略也是一个概率分布。
       上面是一些补充说明，下面是正式定义：

最优状态价值函数 指的是在从所有策略产生的状态价值函数中，选取使状态s价值最大的函数，同理，最优动作价值函数 指的是从所有策略产生的动作价值函数中，选取是状态行为对 价值最大的函数，最优价值函数确定了MDP的最优可能表现，当我们知道了最优价值函数，也就知道了每个状态的最优价值，那么此时该MDP的所有量我们已经知道，MDP问题就解决了。所以说最优值函数表达式只是给出了一个结论，具体如何算最优值函数，目前还没有说。依然以学生为例子，其最优状态值函数和最优行为值函数如图所示：

最优状态值函数如上图

最优行为值函数如上图，后面在进行分析。对于上面两幅图中的数字具体是如何算出来的，暂时可以不用管，其实可以通过后面的贝尔曼最优方程解出来的。

8

最优策略Optimal Policy

最优策略的定义如下：

关于MDP的最优策略，有如下定理：
1. 对于任何MDP问题，存在一个最优策略，好于（至少相等）任何其他策略
2. 所有的最优策略下都有相同的最优价值函数
3. 所有的最优策略下都具有相同的行为价值函数
既然有上述定理，那么寻找最优策略就可以通过最大化最优行为价值函数来得到。同时如果我们知道最优行为价值函数，则表明我们找到了最优策略，也就是说寻找最优策略可以通过寻找最优状态值函数得到。寻找最优策略的定义如下：

以学生为例子，其最优策略如下(红色的弧代表在该状态下最优的动作，所有的状态和相应的动作组合起来也就是最优的策略):

这幅图是告诉我们：如果已经求出了最优值函数，那么最优策略是非常容易求出来的；当然我也可以使用其他办法不求最优值函数，而是直接求最优策略。

9

贝尔曼最优方程 Bellman Optimality Equation

在最优值函数中，如果求出了最优状态值函数，其实也就求出了最优行为值函数，反之同理；在最优策略中，如果求出了最优值函数，那么最优策略就求出来了，反之同理；这样就把最优策略、最优状态值函数、最优行为值函数联系起来了。好的，前面假设了一大堆前提，那么如何求最优状态值函数或者最优行为值函数呢？这就需要使用本节的贝尔曼最优方程了。针对，一个状态的最优价值等于从该状态出发采取的所有行为而产生的行为价值中最大的那个行为价值

上图表示左边的action可以产生最大的价值，所以应该选择左边的策略。
       针对 ，在某个状态s下，采取某个行为的最优价值由2部分组成，一部分是离开状态 s 的即时奖励，另一部分则是所有能到达状态的最优状态价值按出现概率求和

同理，把他们合并就可以得到

以上两个方程是最重要的两个贝尔曼最优化方程，请牢记。依然以学生为例，如图所示：

图片中标注的数值是根据贝尔曼最优值函数算出来的。
       可以看出，贝尔曼最优方程含有max，他是非线性的，没有固定的解决方案，但是一般通过一些迭代方法来解决：价值迭代；策略迭代；Q学习；Sarsa等。只要采用这些方法把最优状态值函数、最优行为值函数或者最优策略求出来了，那么MDP就完全解决了。

总结

 好的，MDP的所有基础知识全部讲完了，这里来总结一下序列一和序列二：

(1) 说明了强化学习是什么？和常用的机器学习算法有啥区别？

(2) 针对马尔科夫过程进行分析，如果模型是已知的(模型的意思可以理解为对实际环境的理解，简单来说就是状态转移概率是已知的)，那么就是马尔科夫链；如果模型是未知的，那就是隐马尔科夫模型；

(3) 在马尔科夫过程基础上，添加reward，就变成了马尔科夫奖赏过程。由于reward的引入，就出现了值函数的概念，表征各状态下累积回报大小；

(4) 针对值函数求解困难问题，引入了贝尔曼期望方程，其将值函数转化为迭代方程，可以方便求解；

(5) 在马尔科夫奖赏过程基础上，引入动作action，就变成了马尔科夫决策过程；

(6) 由于action的引入，并且其也是一个关于状态的分布，故而引入policy的概念，同时状态转移概念和reward也会发生改变，都和action有关了；

(7) 由于action的引入，我们需要评估在不同状态下执行某一action后得到的累计回报大小，故而引入动作值函数；

(8) 状态值函数和动作值函数直接求解也非常困难，所以依然要引入贝尔曼期望方程，将其转化为迭代形式，方便求解；

(9) 贝尔曼期望方程虽然可以求解出某一策略下值函数的取值，但是还没有求解出最优决策，所以根据决策问题的定义，首先分析了最优值函数和最优策略一定要满足的关系式，或者说只有在达到最优策略的时候才会满足等式，即最优值函数和最优策略为我们强化学习提供了优化方向，而贝尔曼最优方程则提供了实际的解决思路。

(10) 后面的内容是：如何真正利用贝尔曼期望方程和贝尔曼最优方程解决实际问题，这就又分为两个研究分支了，如果model(P,R)已知，那么贝尔曼期望方程和贝尔曼最优方程就是用于解决规划planning问题，如果model(P,R)未知，那就是贝尔曼期望方程和贝尔曼最优方程就是用于解决Rl问题了。

由于水平有限，如有疑问，欢迎加群交流678455658。

参考资料

1. David Silvr强化学习课程，b站有视频

end

机器学习算法全栈工程师

---

                            一个用心的公众号

长按，识别，加关注

进群，学习，得帮助

你的关注，我们的热度，

我们一定给你学习最大的帮助