CHAPTER  2

第2章

Markov决策过程

本章介绍强化学习最经典、最重要的数学模型—Markov决策过程（Markov Decision Process，MDP）。首先我们从离散时间智能体/环境接口引入Markov决策过程的定义，然后介绍在求解Markov决策过程时会用到的重要性质，最后介绍一种求解Markov决策过程最优策略的方法。

2.1　Markov决策过程模型

在智能体/环境接口中，智能体可以向环境发送动作，并从环境得到状态和奖励信息。本节将从离散时间的智能体/环境接口出发导出离散时间Markov决策过程模型，并介绍离散时间Markov决策过程模型的关键数学概念。

2.1.1　离散时间Markov决策过程

离散时间Markov决策过程模型可以在离散时间的智能体/环境接口的基础上进一步引入具有Markov性的概率模型得到。首先我们来回顾上一章提到的离散时间智能体/环境接口。

在离散时间智能体/环境接口中，智能体和环境交互的时刻为。在时刻，依次发生以下事情。

智能体观察状态的环境，得到观测，其中是状态空间（state space），表示状态取值的综合；是观测空间（observation space），表示观测取值的集合。

智能体根据观测决定做出动作，其中是动作集合。

环境根据智能体的动作，给予智能体奖励，并进入下一步的状态。其中是奖励空间（reward space），表示奖励取值的集合，它是实数集的子集。

在运行过程中，每一步的可能取值范围不同。很多时候，这是由于在不同观测下可选的动作集合可能不同造成的。为了分析方便，往往用一个包括所有可能动作的更大的集合来表示，使得每一步的动作集合在数学上可以用同样的字母表示。

注意：① 不同的文献可能会用不同的数学记号。例如，有些文献会将动作后得到的奖赏记为，而本书记为。本书采用这样的字母是考虑到和往往是同时确定的。

② 这里的离散时间并不一定是间隔相同或是间隔预先设定好的时间。这里的离散时间指标只是表示决策和动作的指标。

一个时间离散化的智能体/环境接口可以用这样的轨道（trajectory）表示：

对于回合制的任务，可能会有一个终止状态。终止状态和其他普通的状态有着本质的不同：当达到终止状态时，回合结束，不再有任何观测或动作。所以，状态空间里的状态不包括终止状态。在回合制任务中，为了强调终止状态的存在，会将含有终止状态的状态空间记为。回合制任务的轨道形式是：

其中是达到终止状态的步数。

注意：回合制任务中一个回合的步数是一个随机变量。它在随机过程中可以视为一个停时（stop time）。

在时间离散化的智能体/环境中，如果智能体可以完全观察到环境的状态，则称环境是完全可观测的。这时，不失一般性地，可以令（），完全可观测任务的轨道可以简化为：

这样就不需要再使用字母和了。

注意：智能体/环境接口没有假设状态是完全可观测的。部分不完全可观测的问题可以建模为部分可观测的Markov决策过程（Partially Observable Markov Decision Process，POMDP），并用相应方法求解。

在上述基础上进一步引入概率和Markov性，就可以得到Markov决策过程模型。定义在时间，从状态和动作跳转到下一状态和奖励的概率为：

引入这一概念，我们就得到了Markov决策过程模型。值得一提的是，这样的概率假设认为奖励和下一状态仅仅依赖于当前的状态和动作，而不依赖于更早的状态和动作。这样的性质称为Markov性。Markov性是Markov决策过程模型对状态的额外约束，它要求状态必须含有可能对未来产生影响的所有过去信息。

注意：智能体/环境接口没有假设状态满足Markov性。Markov性是Markov决策过程的特点。另外，有时也能从不满足Markov性的观测中构造满足Markov性的状态，或者去学习Markov性。

如果状态空间、动作空间、奖励空间都是元素个数有限的集合，这样的Markov决策过程称为有限Markov决策过程（Finite Markov Decision Process，Finite MDP）。