2.1　马尔可夫基本概念

2.1.1　马尔可夫性

在介绍马尔可夫决策之前，需要先介绍马尔可夫性（Markov Property）。

如果某一状态信息蕴含了所有相关的历史信息，只要当前状态可知，所有的历史信息都不再需要，即当前状态可以决定未来，则认为该状态具有马尔可夫性。

可以用下面的状态转移概率公式来描述马尔可夫性：

P（S_t+1|S_t）=P（S_t+1|S_t，…，S₂，S₁）

可见状态S_t包含的信息等价于所有历史状态S₁，S₂，…，S_t包含的信息，状态S_t具有马尔可夫性。

例如，围棋未来的走法只和当前棋面有关，知道历史棋面信息对于当前该怎么走没有多大帮助。因此围棋的棋面是马尔可夫的，它已经涵盖了导致该种局面的所有重要信息。再如，直升机下个时刻的位置信息也仅和当前时刻的位置和速度相关，因此直升机的位置也具有马尔可夫性。

2.1.2　马尔可夫过程

凡是具有马尔可夫性的随机过程都叫马尔可夫过程（Markov Process），又叫马尔可夫链。它是一个无记忆的随机过程，可以用一个元组<S，P >表示，其中S是有限数量的状态集，P是状态转移概率矩阵。

图2-1以一个求职者找工作的例子来说明马尔可夫链的相关概念。

图2-1中，椭圆表示求职者所处的状态，方格“人工智能工作”表示求职者最终找到了满意的工作。它是一个终止状态，或者可以描述成自循环的状态，也就是此状态的下一个状态100%的概率还是自己。箭头表示状态之间的转移，箭头上的数字表示当前转移的概率。

举例说明：当求职者处在“机器学习”阶段时，他有1/3的概率会继续学习“强化学习”；有1/3的概率会放弃学习，转而继续“本职工作”；同时也有1/3的概率去找“人工智能工作”。在“本职工作”时，他有0.5的概率在下一时刻继续“本职工作”；也有0.5的概率返回“机器学习”状态。同样当求职者进入“强化学习”时，均会有1/3的概率放弃学习继续“本职工作”或继续学习“深度强化”或寻找“人工智能工作”。当求职者处于学习“深度强化”这个状态时，有0.5的概率找到“人工智能工作”，也有0.5的概率去“故宫”旅游放松。在放松的时候，又分别有0.2、0.2、0.6的概率返回“机器学习”“强化学习”“深度强化”课程重新继续学习。一个可能的求职者马尔可夫链从状态“机器学习”开始，最终结束于“人工智能工作”，其间的过程根据状态转化图可以有很多种可能性，这些都称为“样本轨迹”。以下四个轨迹都是可能的：

·　机器学习—人工智能工作；

·　机器学习—强化学习—人工智能工作；

·　机器学习—本职工作—机器学习—强化学习—深度强化—人工智能工作；

·　机器学习—强化学习—深度强化—故宫旅游—深度强化—人工智能工作。

该求职者马尔可夫过程的状态转移矩阵如下：

矩阵中的每个元素表示从当前状态s转移到状态s'的概率。矩阵中的列表示当前状态s，从上到下依次为本职工作、机器学习、强化学习、深度强化、故宫旅游、人工智能工作。矩阵中的行表示转移目的状态s'，从左到右依次为本职工作、机器学习、强化学习、深度强化、故宫旅游、人工智能工作。

2.1.3　马尔可夫决策过程

马尔可夫决策过程（Markov Decision Process，MDP）是针对具有马尔可夫性的随机过程序贯地作出决策。即根据每个时间步观察到的状态s，从可用的行动集合中选用一个行动a，环境在a的作用下，转换至新状态s'。决策者根据新观察到的状态s'，再做出新的决策，采取行为a'，依此反复地进行。环境的状态具有马尔可夫性，即下一时间步状态s'仅与当前状态s和动作a有关，而此刻之前的状态或动作不对其有任何影响。这就是马尔可夫决策过程的描述，大多数的强化学习任务都可以被描述为马尔可夫决策过程，因此马尔可夫决策过程在强化学习理论中相当重要。

一个马尔可夫决策过程由一个五元组构成：M=<S，A，P，R，γ>。

S代表环境的状态集合。状态指的是智能体所能获得的对决策有用的信息。在强化学习中，智能体是依靠当前的状态采取决策的。人在进行决策时，将眼睛看到的信息传送给大脑，经过大脑处理之后建立状态，作为决策的基础。状态的建立依赖于对现实场景的立即感知，是对原始信号高级处理的结果。强化学习中环境的状态，需要人为对环境信息进行抽象，选择对智能体有用的且能反应交互结果的信号作为状态。例如，下围棋时，当前状态为各个棋子的位置。

A代表智能体的动作集合。它是智能体在当前强化学习任务中可以选择的动作集。

P表示状态转移概率。表示在当前状态s下（s∈S），经过动作a作用后（a∈A），会转移到的其他状态s'（s'∈S）的概率。具体的数学表达式如下：

某些时候，P与动作无关，可以写为

给定一个策略π和一个马尔可夫决策过程（MDP）：M=<S，A，P，R，γ>，则在执行策略π时，状态从s转移至s'的概率等于一系列概率的和，这一系列概率指的是在执行当前策略π时，执行某一个行为a的概率π（a|s）与该行为能使状态从s转移至s'的概率的乘积。具体的数学表达式如下：

R是回报函数。表示在当前状态s（s∈S），采取动作a（a∈A）后，获得的回报。具体的数学表达式如下：

某些时候R仅与状态相关：因此可以写为。

两者之间存在如下对应关系：当前状态s下执行指定策略π得到的立即回报是该策略π下所有可能行为得到的回报与该行为发生的概率π（a|s）的乘积的和。

γ是衰减系数（Discount Factor），也叫折扣因子，γ∈[0，1]。使用折扣因子是为了在计算当前状态的累积回报时，将未来时刻的立即回报也考虑进来。这种做法符合人类的认知习惯，人类在追求眼前利益的同时，也会考虑具有不确定性的远期利益。

在同样一个马尔可夫决策过程（MDP）中，智能体遵循不同的策略相当于在某一个状态时做出不同的选择，进而又形成各种不同的马尔可夫过程，产生了不同的后续状态及对应的不同的回报。

图2-2是一个求职“马尔可夫决策过程”的例子，在“马尔可夫过程”基础上增加了针对每一个状态的可选动作，以及针对每个状态行为时的回报。此图去掉了“故宫旅游”状态，表示当选择“旅游”这个动作时，主动进入了一个临时状态（图中用黑色小实点表示），随后被动地被环境按照其动力学分配到另外三个状态，也就是说此时求职者没有选择权决定去哪一个状态。

在这个马尔可夫决策过程中，状态集合S={本职工作、机器学习、强化学习、深度强化、人工智能工作}。动作集合A={继续本职工作、学习、放弃、找工作、旅游}。状态转移矩阵中的每一项表示为，表示状态s在a行为的影响下，转换到状态s'的概率。由图可见，当求职者位于“本职工作”状态，采取行为“学习”，转移到“机器学习”的概率为1，转移到其他状态的概率为0。当求职者位于“深度强化”状态时，采取行为“旅游”时，转移到“机器学习”和“强化学习”的概率均为0.2，转移到“深度强化”的概率为0.6。此例中的回报表示为，回报和状态行为对挂钩。例如，位于“本职工作”状态，采取“学习”行为时，会得到一个10的立即回报。

假设针对每个状态，每一种可能的行为的执行概率都相同，则这个例子对应的策略是一个集合，如果将某状态下采取行为的概率都标示在对应线条上，如图2-3所示，则在当前策略下，状态“深度强化”到状态“强化学习”的转移概率为

遵循当前策略，状态“深度强化”对应的回报为