强化学习【二】马尔科夫决策过程
求解强化学习问题可以理解为如何最大化个体在与环境交互过程中获得的累积奖励。环境的动力学特征确定了个体在交互时的状态序列和即时奖励，环境的状态是构建环境动力学特征所需要的所有信息。当环境状态是完全可观测时，个体可以通过构建马尔科夫决策过程来描述整个强化学习问题。有时候环境状态并不是完全可观测的，此时个体可以结合自身对于环境的历史观测数据来构建一个近似的完全可观测环境的描述。从这个角度来说，几乎所有的强化学习问题都可以被认为或可以被转化为马尔科夫决策过程。正确理解马尔科夫决策过程中的一些概念和关系对于正确理解强化学习问题非常重要。
马尔科夫过程
在一个时序过程中，如果t+1时刻的状态仅取决于t时刻的状态S_t而与t时刻之前的任何状态都无关时，则认为t时刻的状态S_t具有马尔科夫性(Markov property)。若过程中的每一个状态都具有马尔科夫性，则这个过程具备马尔科夫性。具备了马尔科夫性的随机过程称为马尔科夫过程(Markov process)，又称马尔科夫链(Markov chain)。马尔科夫过程中的每一个状态St记录了过程历史上所有相关的信息，而且一旦S_t确定了，那么历史状态信息S_1....S_t1对于确定S_t+1均不再重要，可有可无。描述一个马尔科夫过程的核心是状态转移概率矩阵：
状态转移概率矩阵定义了从任意一个状态s到其所有后继状态s’的状态转移概率：
其中，矩阵P中每一行的数据表示从某一个状态到所有n个状态的转移概率值。每一行的这些值加起来的和应该为1。
通常使用一个元组〈S; P〉来描述马尔科夫过程，其中S是有限数量的状态集，P是状态转移概率矩阵。
下图描述了一个假想的学生学习一门课程的马尔科夫过程。在这个随机过程中，学生需要顺利完成三节课并且通过最终的考试来完成这门课程的学习。
当学生处在第一节课中时，会有50%的几率拿起手机浏览社交软件信息，另有50%的几率完成该节课的学习进入第二节课。一旦学生在第一节课中浏览手机社交软件信息，则有90%的可能性继续沉迷于浏览，而仅有10%的几率放下手机重新听讲第一节课。学生处在第二节课的时有80%的几率听完第二节课顺利进入到第三节课的学习中，也有20%的几率因课程内容枯燥或难度较大而休息或者退出。学生在学习第三节课内容后，有60%的几率通过考试继而100%的进入休息状态，也有40%的几率因为过于兴奋而出去娱乐泡吧，随后可能因为忘掉了不少学到的东西而分别以20%,40%和50%的概率需要重新返回第一、二、三节课中学习。图中，我们使用内有文字的空心圆圈来描述学生可能所处的某一个状态。这些状态有：第一节课（C1）、第二节课（C2）、第三节课（C3）、泡吧中（Pub）、通过考试（Pass）、浏览手机（FB）、以及休息退出（Sleep）共7个状态，其中最后一个状态是终止状态，意味着学生一旦进入该状态则永久保持在该状态，或者说该状态的下一个状态将100%还是该状态。连接状态的箭头表示状态转移过程，箭头附近的数字表明着发生箭头所示方向状态转移的概率。假设学生现处在状态“第一节课（C1）”中，我们按照马尔科夫过程给出的状态转移概率可以得到若干学生随后的状态转化序列。
例如下面的这4个序列都是可能存在的状态转化序列：
-C1 - C2 - C3 - Pass - Sleep
-C1 - FB - FB - C1 - C2 - Sleep
-C1 - C2 - C3 - Pub - C2 - C3 - Pass - Sleep
-C1 - FB - FB - C1 - C2 - C3 - Pub - C1 - FB - FB - FB - C1 - C2 - C3 - Pub - C2 - Sleep
从符合马尔科夫过程给定的状态转移概率矩阵生成一个状态序列的过程称为采样（sample）。采样将得到一系列的状态转换过程，本书我们称为状态序列(episode)。当状态序列的最后一个状态是终止状态时，该状态序列称为完整的状态序列(complete episode)。状态序列大多数指的都是完整的状态序列。
马尔科夫奖励过程
马尔科夫过程只涉及到状态之间的转移概率，并未触及强化学习问题中伴随着状态转换的奖励反馈。如果把奖励考虑进马尔科夫过程，则成为马尔科夫奖励过程（Markov reward process,MRP）。
很多人纠结为什么奖励是t+1时刻的。照此理解起来相当于离开这个状态才能获得奖励而不是进入这个状态即获得奖励。David指出这仅是一个约定，为了在描述RL问题中涉及到的观测O、行为A、和奖励R时比较方便。这点不要纠结。把他理解为s状态的即时奖励即可。
在强化学习中，我们给累计奖励一个新的名称“收获”。
收获（return）是一个马尔科夫奖励过程中从某一个状态S_t开始采样直到终止状态时所有奖励的有衰减的之和。数学表达式如下：
收获有时也被翻译为回报。从式中可以看出，收获是对应于状态序列中的某一时刻的状态的，计算从该状态开始直至结束还能获得的累积奖励。在一个状态序列中，不同时刻的状态一般对应着不同的收获。从该式中我们还可以看出，收获并不是后续状态的奖励的直接相加，而是引入了一个取值范围在[0，1]间的衰减系数γ。引入该系数使得后续某一状态对当前状态收获的贡献要小于其奖励。这样设计从数学上可以避免在计算收获时因陷入循环而无法求解，从现实考虑也反映了远期奖励对于当前状态具有一定的不确定性，需要折扣计算。当γ取0时，表明某状态下的收获就是当前状态获得的奖励，不考虑后续状态，这属于“短视”行为，当γ取1时，表明将考虑所有的后续状态，属于有“长远眼光”的行为。求解实际问题时，模型构建者可根据实际问题的特点来设定γ值。
可以认为，收获间接给状态序列中的每一个状态设定了一个数据标签，反映了某状态的重要程度。由于收获的计算是基于一个状态序列的，从某状态开始，根据状态转移概率矩阵的定义，可能会采样生成多个不同的状态序列，而依据不同的状态序列得到的同一个状态的收获值一般不会相同。如何评价从不同状态序列计算得到的某个状态的收获呢？此外，一个状态还可能存在于一个状态序列的多个位置，可以参考学生马尔科夫过程的第四个状态序列中的状态“第一节课”，此时在一个状态序列下同一个状态可能会有不同的收获，如何理解这些不同收获的意义呢？不难看出收获对于描述一个状态的重要性还存在许多不方便的地方，为了准确描述一个状态的重要性，我们引入状态的“价值”这个概念。
价值（value）是马尔科夫奖励过程中状态收获的期望。数学表达式为：
可以看出，一个状态的价值是该状态的收获的期望，也就是说从该状态开始依据状态转移概率矩阵采样生成一系列的状态序列，对每一个状态序列计算该状态的收获，然后对该状态的所有收获计算平均值得到一个平均收获。当采样生成的状态序列越多，计算得到的平均收获就越接近该状态的价值，因而价值可以准确地反映某一状态的重要程度。
从状态的价值的定义可以看出，得到每一个状态的价值，进而得到状态的价值函数对于求解强化学习问题是非常重要的。但通过计算收获的平均值来求解状态的价值不是一个可取的办法，因为一个马尔科夫过程针对一个状态可能可以产生无穷多个不同的状态序列。我们对价值函数中的收获按照其定义进行展开：
这个推导过程相对简单，在导出最后一行其理由是收获的期望等于收获的期望的期望。
上式中，根据马尔科夫奖励过程的定义，R_t+1的期望就是其自身，因为每次离开同一个状态得到的奖励都是一个固定的值。而下一时刻状态价值的期望，可以根据下一时刻状态的概率分布得到。如果用s′表示s状态下一时刻任一可能的状态：
上式称为马尔科夫奖励过程中的贝尔曼方程（Bellman equation），它提示一个状态的价值由该状态的奖励以及后续状态价值按概率分布求和按一定的衰减比例联合组成。
根据奖励值和衰减系数的设定给出了学生马尔科夫奖励过程中各状态的价值，并对状态“第三节课”的价值进行了验证演算。读者可以根据上述方程对其它状态的价值进行验证。
计算这类问题的时间复杂度是O(n^3)，其中n是状态的数量。这意味着，对于学生马尔科夫奖励过程这类状态数比较少的小规模问题，直接求解是可行的，但如果问题涉及到的状态数量增多，这种解法就不现实了。后续会陆续介绍其它行之有效的求解方法。
在强化学习问题中，如果个体知道了每一个状态的价值，就可以通过比较后续状态价值的大小而得到自身努力的方向是那些拥有较高价值的状态，这样一步步朝着拥有最高价值的状态进行转换。但是我们知道，个体需要采取一定的行为才能实现状态的转换，而状态转换又与环境动力学有关。很多时候个体期望自己的行为能够到达下一个价值较高的状态，但是它并不一定能顺利实现。这个时候个体更需要考虑在某一个状态下采取从所有可能的行为方案中选择哪个行为更有价值。要解释这个问题，需要引入马尔科夫决策过程、行为、策略等概念。
马尔科夫决策过程（Markov decision process, MDP）
相较于马尔科夫奖励过程，马尔科夫决定过程多了一个行为集合A，它是这样的一个元组: <S, A, P, R, γ>。看起来很类似马尔科夫奖励过程，但这里的P和R都与具体的行为a对应，而不像马尔科夫奖励过程那样仅对应于某个状态，A表示的是有限的行为的集合。具体的数学表达式如下：
- 示例——学生MDP
下图给出了一个可能的MDP的状态转化图。图中红色的文字表示的是采取的行为，而不是先前的状态名。对比之前的学生MRP示例可以发现，即时奖励与行为对应了，同一个状态下采取不同的行为得到的即时奖励是不一样的。由于引入了Action，容易与状态名混淆，因此此图没有给出各状态的名称；此图还把Pass和Sleep状态合并成一个终止状态；另外当选择”泡吧”这个动作时，主动进入了一个临时状态（图中用黑色小实点表示），随后被动的被环境按照其动力学分配到另外三个状态，也就是说此时Agent没有选择权决定去哪一个状态。
注意，学生马尔科夫决策过程示例虽然与之前的学生马尔科夫奖励过程示例有许多相同的状态，但两者还是有很大的差别，建议读者将这两个示例完全区分开来理解。
Agent在给定状态下从行为集中选择一个行为的依据则称为策略(policy)，用字母π表示。策略π是某一状态下基于行为集合的一个概率分布，其元素π(a|s)为过程中的某一状态s采取可能的行为a的概率。用π(a|s)表示。
值得注意的是：下图的0.2，0.4，0.4是由环境决定的概率，并非策略，策略是智能体来选择行为的时候的概率，例如，第一个节点选择FB和Stu的概率，并未在下图表注，千万不要混淆。
一个策略完整定义了个体的行为方式，也就是说定义了个体在各个状态下的各种可能的行为方式以及其概率的大小。Policy仅和当前的状态有关，与历史信息无关；同时某一确定的Policy是静态的，与时间无关；但是个体可以随着时间更新策略。
当给定一个MDP: M = <S, A, P, R, γ> 和一个策略π，那么状态序列 S_{1},S_{2},… 是一个马尔科夫过程 <S, P^{π}> ；同样，状态和奖励序列 S{1}, R{2}, S{2}, R{3}, S{3}, … 是一个马尔科夫奖励过程 <S, P^{π}, R^{π}, γ> ，并且在这个奖励过程中满足下面两个方程：
第一个用文字描述是这样的，在执行策略 π时，状态从s转移至 s' 的概率等于一系列概率的和，这一系列概率指的是在执行当前策略时，执行某一个行为的概率与该行为能使状态从s转移至s’的概率的乘积。
第二个用文字表述是这样的：当前状态s下执行某一指定策略得到的即时奖励是该策略下所有可能行为得到的奖励与该行为发生的概率的乘积的和。
策略在MDP中的作用相当于agent可以在某一个状态时做出选择，进而有形成各种马尔科夫过程的可能，而且基于策略产生的每一个马尔科夫过程是一个马尔科夫奖励过程，各过程之间的差别是不同的选择产生了不同的后续状态以及对应的不同的奖励。因此在马尔科夫决策过程中，有必要扩展先前定义的价值函数。
未完待续/