强化学习读书笔记（3）| 有限马尔科夫决策过程（Finite Markov Decision Processes）

,

本章我们介绍有限马尔科夫决策过程(Finite MDPs），这个问题和赌博机一样涉及到评估的反馈，但这里还多了一个方面——在不同的情况做出不同的选择。MDPs是经典的序列判定决策模型，也就是说，不是做出一个选择就会马上获得reward。这与赌博机不同，赌博机只要摇一次臂即可立刻获得reward，而MDPs就像下象棋，只有结束了对局才会获得reward，但下象棋从开始到结束涉及到很多个行动，也就是要做出很多次选择才最终到对局结束。因此说MDPs的奖励是延迟的，同时MDPs还有一个即时的权值用来帮助当前决策。在赌博机情景中，我们对每一个行为a做出评估值q(a)，而在MDPs情境中，我们则需要对行为a和状态s做出评估q(s,a)，也可以估计每个给定最佳动作选择的状态的v(s)值。

MDPs有严格的数学模型，我们将介绍它的关键概念比如返回值，值函数以及贝尔曼等式，我们想通过应用来传递有限马尔科夫的结构，像所有人工智能一样，都有其应用的范围。

一、Agent–Environment交互

我们把能够学习且做决策的对象称为agent，比如在无人驾驶中，车就是agent。提供给agent学习和交互的地方就叫Environment。agent不断在环境中交互学习，而环境则给agent反馈并提供一些状态。环境中包含有一些奖励，agent就要在环境中实现奖励最大化。

大部分我们的agent都是离散行动的，比如一次做出一个选择，就像下象棋，一次进行一步，令t为步数，t=1,2,3,...；每一步agent都会获取环境状态(state)的信息，St ∈ S，一系列行为之后，agent会获得这些行为的reward之和Rt+1，然后继续寻找新的state，MDPs的决策过程如下：

几个要素:

二、目标与奖励

Goal：获取最大化的奖励总和。这意味着不能单单只看眼前的奖励，而要看长远过程下的奖励之和。

Reward：用于告诉agent最终想要得到什么，而不是怎么去得到的。奖励是由环境决定的而不是由agent决定的。

三、回报

那么agent的最大化奖励总和的目标要如何用数学的方式进行定义呢？

假设在某个时间点t之后的一系列的reward序列为：Rt+1 , Rt+2 , Rt+3 , . . .期望返回值（expected return）用Gt表示，即从该时间点往后所有获取的reward序列的某种函数。

当agent-environment交互自然地分解成子片段时，我们称之为Episodes。例如在象棋游戏中，一局比赛就是一个Episode，一旦一方被将军，那么这局Episode结束，然后环境重置，到下一个Episode重新摆好棋子继续比赛，上一局游戏和这一局游戏是相互独立的。因此，这些片段都可以被认为是以相同的终止状态结束，对不同的结果有不同的回报，带有片段式过程的任务叫做片段任务（episodic tasks）。

但有时候，我们会遇到没有终止状态的任务，比如无人驾驶，车一直开就一直学习，没有一个任务重置的节点，这类任务叫做连续任务（continuing tasks）。

在连续式任务中，很难把交互过程看成离散的时间点，所以用discounting sum进行定义：

discounting rate γ∈[0,1]，决定了未来奖励的当前价值，其含义是：在当前时间点k步之后的奖励，在当前的价值是未来的倍。当该系数小于1，最终和会收敛，只要奖励序列是有限的。当系数为0，则执行机构是短视的，只顾眼前利益；如果系数大于1，执行机构是远视的，也就是重视长远奖励。

四、 策略和值函数

几乎所有的强化学习算法都涉及到估计value function，这个function自变量是状态，用来判断在某个给定状态下做出某个动作的好坏程度。好坏程度用什么来定义呢？这里我们使用“未来的期望奖励”来定义，也可以说期望返回值。显然agent在未来期望得到的奖励取决于它做出什么决策。因此，value function在定义的时候和policy有关。

强化学习中的value function的一个重要性质是它满足一种特别的递归关系。对于任何policy 和任何状态s，当前状态的value和其后的可能状态的value之间的关系如下式：

其中r(s,a,s’)表示期望奖励，当奖励是确定性的情况下，也就等于即时奖励（immediate reward）。

该式叫做policy 的贝尔曼方程。贝尔曼方程对从当前状态起之后的所有可能性进行了平均化，并按照发生的概率给予不同的权重。

五、最优策略和最优值函数

解决一个强化学习问题，也就是意味着找到一个policy，在这个policy下可以获得最好的长期期望奖励。

最优状态值函数 (Optimal State-Value Function) ：最优策略π∗下的状态值函数，最优策略即能使值函数取到最大值的策略

最优行为值函数 (Optimal Action-Value Function) ：最优策略下的行为值函数

对于状态-动作对（s，a），此函数给出了在状态s中执行操作的预期回报，然后遵循最优策略，因此，可改写为

最优状态值函数和最优行为值函数也满足贝尔曼等式。贝尔曼最优性方程显示了最优策略下的状态价值必须等于该状态最佳行动的预期收益：

六、有限马尔科夫决策过程实例：GridWorld

接下来我们看一个简单的有限状态的马尔科夫决策过程实例。

这是一个GridWorld问题，如上图所示是一个包含5*5个元胞的网格，在每一个元胞内，agent都有四种行动可以执行，它们分别是“上”、“下”、“左”、“右”。假设agent在每个格子处采取四种行动的概率是相同的，同时未来回报的折扣因子设为0.9，而agent的状态转移以及回报值分为以下四种情况：

• 如果agent在边缘处，那么如果它此时执行的动作使它溢出网格的话，我们限制它的位置仍然固定不变，但是同时它会得到-1的回报值；
• 如果agent处在A点，那么它的任意行动都将得到10的回报值，同时下一步的状态移至A'处；
• 如果agent处在B点，那么它的任意行动都将得到5的回报值，同时下一步的状态移至B'处；
• 其他情况则会得到0的回报值，状态转移遵从格子的位置变化；

根据以上提示，我们如何计算每个元胞的状态-价值函数以及最优状态-价值函数呢？

计算状态-价值函数

根据状态-价值函数的定义，在这里我们不妨理解为agent处在每个格子的时候未来得到的回报值。可以得出以下三条判断：

• agent处在A和B处的时候状态-价值应该较大，因为当agent处在A或B时，下一步无论它采取什么行动，都会得到较大的10或5回报值；
• A或B附近处的元胞的状态-价值也要比远离A或B处元胞的状态-价值要大；
• 由于边缘处很容易得到-1的回报值，那么显然边缘处的元胞要比内部的元胞的状态-价值要小。

除此之外，我们还应该明白，在计算状态-价值函数的时候，我们是不用区分具体行动的，换句话说我们只用按照题意中的均匀概率进行决策即可。那么，每个元胞的状态-价值函数当然是包含了处在该元胞处的所有行动，因此，我们需要在遵从均匀随机决策下对所有行动进行迭代，直到所有元胞的状态-价值收敛为止，这种做法叫做迭代策略评估。

求解状态-价值函数直接按照贝尔曼方程，进行如下迭代即可：

计算最优状态-价值函数

找出agent在每个元胞处它下一步该采取什么行动可以保证状态-价值最大，按照贝尔曼最优方程，我们只用对行动a进行迭代即可，并且找出最大的价值，重复迭代，直到收敛为止。

代码编写

（1）定义好所有状态转移以及对应回报值

（2）按照贝尔曼方程计算状态-价值函数并可视化

（3）按照贝尔曼优化方程计算最优状态-价值函数并可视化：

实验结果

计算出的状态-价值函数值如下：

每个元胞的最优行动如下：

七、小结

有很多不同的决策方法可以看成是贝尔曼最优方程的近似。比如启发式搜索，可以看成是把贝尔曼最优方程等号右边部分扩展到一定深度，得到一个概率树，然后用启发式评估方法在叶子节点上进行的近似（通常启发式搜索算法大多都是基于片段式任务）。另外一个方法就是动态规划，它和贝尔曼方程的相似程度更加接近。很多强化学习的方法，都可以看成是对贝尔曼最优方程的近似求解，使用实际经历的转移情形来弥补难以完全得知环境动态性质的缺陷。我们会在后续章节陆续介绍几类方法。

然而，尽管显式地求解贝尔曼最优方程可以帮助我们求得最优policies，然而，这个方法直接用处并不太大。因为它涉及到穷尽所有的可能性。这个解法依赖于三个在实际中很难满足的假设：（1）我们精确的知道环境的动态性质；（2）我们有足够的计算资源去完成所有运算；（3）环境满足马尔科夫性质。这三个假设在我们感兴趣的问题中通常很难全部满足。比如对于西洋双陆棋来说，第一个和第三个假设可以满足，然而第二个假设很难满足，因为它有10^20个状态。因此，实际应用中，我们必须采取近似的方式。

参考资料：

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

[2]https://zhuanlan.zhihu.com/p/27414242

[3]https://blog.csdn.net/ILYPL/article/details/78940821

[4]https://www.quantinfo.com/Article/View/725/