第二课马尔科夫决策过程

本章主要讲解马尔科夫决策过程的基础知识，课程组提到几乎所有的强化学习问题都可以表示为马尔科夫决策过程。这里注意本章讲解的马尔科夫决策过程的环境是完全可观测的，一般强化学习问题的环境是部分可观测，所以也存在部分可观测的马尔科夫决策过程。

1 马尔科夫性

当前的状态可以充分地表示未来信息（由当前状态就可以知道下一刻的状态转移概率和奖励），则称该状态满足马尔可夫性。在上一节课中提到，已知马尔科夫状态，就可以取代历史信息Ht。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FzgrVRYL-1598088935092)(images/image-20200817213706083.png)]

由定义可以看到下一状态只和当前状态有关，和之前的状态无关。（这里和上一节提到的动作具有长期效用是不矛盾的）

2 马尔科夫过程

马尔科夫过程是一个无记忆的随机过程，在这个过程中每个状态均满足马尔科夫性。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yI6gGCT4-1598088935095)(images/image-20200817214045728.png)]

课程给了一个学生马尔科夫链，在每一个状态下，学生有不同的概率转移到下一状态。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fJ0F3c4l-1598088935098)(images/image-20200817214200744.png)]

3 马尔科夫奖励过程

马尔科夫奖励过程是在马尔科夫过程的基础上增加了奖励和衰减系数，表示为一个四元组。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0E7pIHK1-1598088935101)(images/image-20200817214530683.png)]

R是从某一状态转移到下一状态获得的奖励的函数，课程提到写成Rt+1和Rt取决于规定。γ∈[0,1]表示衰减系数，可以理解为对未来所获得的奖励的可信度，用来定义回报Gt，也就是从某一时刻起到开始累积的奖励。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jyf0rSdG-1598088935103)(images/image-20200817215014465.png)]

为了评级某一状态的好坏/价值，引入了状态值函数V(s)，它表示处在当前状态下未来获得的回报。因为状态转移是随机过程，因此用期望回报表示V(s)。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B3emGcjJ-1598088935105)(images/image-20200817215339377.png)]

4 贝尔曼方程—MRPs

贝尔曼方程给出了状态值函数V(s)的递归形式：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RwF9eAkU-1598088935107)(images/image-20200817220058855.png)]

如果知道状态转移概率，那么状态值函数可以表示为：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KpSEupzr-1598088935108)(images/image-20200817220227606.png)]

可以看到MRPs中某一状态下的状态值函数可以通过下一状态的状态值函数求解，这本质上是一个递归过程。

矩阵形式的贝尔曼方程可以表示为：

在这里插入图片描述

因为它是线性方程，可以直接求解：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bXHrDb2f-1598088935111)(images/image-20200817220537122.png)]

直接求解适合小规模的MRP问题。大规模MRP的求解通常使用迭代法。常用的迭代方法有：动态规划Dynamic Programming、蒙特卡洛评估Monte-Carlo evaluation、时序差分学习Temporal-Difference。求解强化学习问题也是首先想到这三种方法。

5 马尔科夫决策过程

在马尔科夫奖励过程的基础上加入了动作集，也就是说在状态s下做出了某种动作a才会进行状态转移。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-94f9sK6O-1598088935112)(images/image-20200817220707445.png)]

这里面奖励函数和状态转移矩阵都与状态s下的动作a有关系。

为了描述状态s和动作a的关系，引入了策略，也就是状态s下动作a的分布（策略分为确定性策略和随机策略两种）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NIuvimRv-1598088935113)(images/image-20200817220929420.png)]

MDPS满足以下两个条件：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hDJIZoUJ-1598088935114)(images/image-20200817222111902.png)]

刚刚在MRPs中讨论了V(s)，在这里为了描述某一状态下选择某一动作的好坏/价值，引入状态动作值函数Q(s,a)，也表示未来的期望回报：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vy7qtX1Y-1598088935116)(images/image-20200817221254151.png)]

6 贝尔曼方程—MDPs

贝尔曼期望方程

同样的，贝尔曼方程给出了Q(s,a)的递归形式：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3Dnh8AYU-1598088935117)(images/image-20200817221437953.png)]

因为MDPs中状态的转移和动作a有关，因此引入策略π(a|s)（这里是概率分布），Vπ(s)可以表示为：

而qπ(s,a)又可以表示为：

将qπ(s,a)带入Vπ(s)，得到vπ的贝尔曼期望方程：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N46U0G2G-1598088935118)(images/image-20200817222937916.png)]

反过来将Vπ(s)带入qπ(s,a)，得到qπ(s,a)的贝尔曼期望方程：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PdhdIH1N-1598088935119)(images/image-20200817223038185.png)]

可以看到，MDPs中贝尔曼期望方程展示了一种递归关系：当前状态下的状态值函数/状态动作值函数可以由下一时刻的状态值函数/状态动作值函数表示。

贝尔曼最优方程

两种值函数评价了在某个策略下，某个状态或某个状态动作的未来期望回报。强化学习的目的就是最大化累积奖励，因此定义最优值函数表示最优的策略下状态/状态动作的价值：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lYUlS2kq-1598088935120)(images/image-20200817224653526.png)]

定义一个偏序关系，如果策略π优于π‘，那么vπ(s)>vπ’(s)：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PW1r1WoF-1598088935121)(images/image-20200817225205757.png)]

那么满足定理：1 存在一个最优策略π*优于其它所有策略π。2 所用最优策略下的状态值函数和状态动作值函数相同

我们如何找到最优策略呢？一个策略表示了状态s下的动作a的概率分布，那么在状态s下肯定存在某个最优的动作a（体现在使得未来累积奖励最大，也就是q值最大），我们只需要在此状态下选择该动作就行了：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XztoAg2I-1598088935122)(images/image-20200817225659177.png)]

注意对于任何的MDP总是有一个确定的最优策略（这里是value-based，在police-based中可以产生随机策略），并且如果知道了q*(s,a)，那么也就知道了最优策略。换句话说，通过最大化价值函数间接的寻找最优策略。

现在有了寻找最优策略的思路，那么利用贝尔曼方程推导出贝尔曼最优方程的过程如下：

首先在某个s下我们要选择一个确定的动作使得累积奖励最大，所以有v*(s)=q*(s,a)：

接着，由于存在状态转移概率，q*(s,a)是多个可能状态下的最大状态值函数的期望：

将q(s,a)带入v*(s)得到状态值函数的贝尔曼最优方程：*

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tQNfkQxh-1598088935123)(images/image-20200817230457642.png)]

同理，得到状态动作值函数的贝尔曼最优方程：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yR2tj6QX-1598088935123)(images/image-20200817230606202.png)]