强化学习基础篇二：马尔可夫决策过程

写在前面

  本文是对李沐等“动手学强化学习”教程的个人阅读总结，原文链接：动手学强化学习。

第3章 马尔可夫决策过程

3.1 重要性

  马尔可夫决策过程是强化学习中的基础概念，强化学习中的环境就是一个马尔可夫决策过程，与多臂老虎机问题不同，马尔可夫决策过程包含状态信息以及状态之间的转移机制。后续将要介绍的强化学习算法通常都是在求解马尔可夫决策过程中的最优策略。如果要用强化学习去解决一个实际问题，第一步要做的事情就是把这个实际问题抽象为一个马尔可夫决策过程，也就是明确马尔可夫决策过程的各个组成要素。
  下文通过逐步介绍马尔可夫过程和马尔可夫奖励过程来引出马尔可夫决策过程。

3.2 马尔可夫过程

3.2.1 随机过程

  在随机过程（stochastic process）中，随机现象在某时刻 $t$ 的取值是一个向量随机变量，用 $S_t$ 表示，所有可能的状态组成状态集合 $\mathcal{S}$。随机现象便是状态的变化过程。在某时刻 $t$ 的状态 $S_t$ 通常取决于 $t$ 时刻之前的状态。将已知历史信息 $(S_1,\dots ,S_t)$ 时下一个时刻状态为 $S_{t+1}$ 的概率表示成 $P(S_{t+1}|S_1,\dots ,S_t)$。

3.2.2 马尔可夫性质

  当且仅当某时刻的状态只取决于上一时刻的状态时，一个随机过程被称为具有马尔可夫性质（Markov property），用公式表示为 $ $P(S_{t+1}|S_t)=P(S_{t+1}|S_1,\dots ,S_t)$。但注意，具有马尔可夫性并不代表这个随机过程就和历史完全没有关系。因为虽然 $t+1$ 时刻的状态只与 $t$ 时刻的状态有关，但是 $t$ 时刻的状态其实包含了 $t-1$ 时刻的状态的信息，通过这种链式的关系，历史的信息被传递到了现在。

3.2.2 马尔可夫过程

  马尔可夫过程（Markov process）指具有马尔可夫性质的随机过程，也被称为马尔可夫链（Markov chain），常用元组 $<\mathcal{S},\mathcal{P}>$ 表示，其中 $\mathcal{S}=(s_1,s_2\dots ,s_n)$ 是有限数量的状态集合， $\mathcal{P}$ 是状态转移矩阵（state transition matrix），定义了所有状态对之间的转移概率，即：
$$\mathcal{P}=\left[\begin{array}{ccc}P(s_1|s_1)& \cdots & P(s_n|s_1)\\ ⋮& \ddots & ⋮\\ P(s_1|s_n)& \cdots & P(s_n|s_n)\end{array}\right]$$
称 $P(s^{\prime }|s)$ 为状态转移函数。从某个状态出发，到达其他状态的概率和必须为 1，即状态转移矩阵 $\mathcal{P}$ 的每一行的和为 1。
  在状态集合 $\mathcal{S}$ 中，不会再转移到其他状态的那个状态（可以理解为它永远以概率 1 转移到自己）称为终止状态（terminal state）。给定一个马尔可夫过程，我可以从某个状态出发，根据状态转移矩阵生成一个状态序列（episode），这个步骤也被叫做采样（sampling）。生成序列的概率与状态转移矩阵相关。

3.3 马尔可夫奖励过程

  在马尔可夫过程的基础上加入奖励函数 $r$ 和折扣因子 $\gamma$，就可以得到马尔可夫奖励过程（Markov reward process），常用元组 $<\mathcal{S},\mathcal{P},r,\gamma >$ 表示。其中：

• $\mathcal{S}$ 是有限状态的集合。
• $\mathcal{P}$ 是状态转移矩阵。
• $r$ 是奖励函数，某个状态 $s$ 的奖励 $r(s)$ 指转移到该状态时可立即获得的奖励的期望。
• $\gamma$ 是折扣因子（discount factor），取值范围为 $[0,1)$。引入折扣因子的理由为远期利益具有一定不确定性，有时我们更希望能够尽快获得一些奖励，所以我们需要对远期利益打一些折扣。接近 1 的 $\gamma$ 更关注长期的累计奖励，接近 0 的 $\gamma$ 更考虑短期奖励。

3.3.1 回报

  在一个 MRP 中，从第 $t$ 时刻状态开始，直到终止状态时，所有奖励的衰减之和称为回报 $G_t$（Return），公式如下：
$$G_t=R_t+\gamma R_{t+1}+{\gamma }^2{R}_{t+2}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k}$$其中 $R_t$ 表示在 $t$ 时刻获得的奖励。

3.3.2 价值函数

  在 MRP 中，一个状态的期望回报（即从这个状态出发的未来累积奖励的期望）被称为这个状态的价值（value），价值函数就是输入某个状态，输出该状态的价值，记为：$V(s)=\mathbb{E}[G_t\mid S_t=s]$。结合价值函数定义、期望的性质、马尔可夫性质可推导出 MRP 中非常有名的贝尔曼方程（Bellman equation）：（推导过程参见原文）
$$V(s)=r(s)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s)V(s^{\prime })$$  求解较大规模的 MRP 中的价值函数时，可以使用动态规划（dynamic programming）算法、蒙特卡洛方法（Monte-Carlo method）和时序差分（temporal difference），这些方法将在之后的章节介绍。

3.4 马尔可夫决策过程

  马尔可夫过程和马尔可夫奖励过程都是自发改变的随机过程，如果有一个外界的“刺激”来共同改变这个随机过程，就有了马尔可夫决策过程（Markov decision process，MDP）。将这个来自外界的刺激称为智能体（agent）的动作，在马尔可夫奖励过程（MRP）的基础上加入动作，就得到了马尔可夫决策过程（MDP），常用元组 $<\mathcal{S},\mathcal{A},\mathcal{P},r,\gamma >$ 表示。其中：

• $\mathcal{S}$ 是状态的集合。
• $\mathcal{A}$ 是动作的集合。
• $\gamma$ 是折扣因子。
• $r(s,a)$ 是奖励函数，此时奖励可以取决于状态和动作，在奖励函数只取决于状态时，则退化为 $r(s)$；
• $P(s^{\prime }|s,a)$ 是状态转移函数，表示在状态 $s$ 执行动作 $a$ 之后到达状态 $s^{\prime }$ 的概率。

  MDP 与 MRP 主要区别为 MDP 中的状态转移函数和奖励函数都比 MRP 多了动作作为自变量。在 MDP 的定义中，不再使用类似 MRP 定义中的状态转移矩阵方式，而是直接表示成了状态转移函数。
  MDP 是一个与时间相关的不断进行的过程，通常存在一个智能体来执行动作，在智能体和环境之间存在一个不断交互的过程。一般而言，它们之间的交互是如下图循环过程：智能体根据当前状态 $S_t$ 选择动作 $A_t$；对于状态 $S_t$ 和动作 $A_t$，MDP 根据奖励函数和状态转移函数得到 $R_t$ 和 $S_{t+1}$ 并反馈给智能体。智能体的目标是最大化得到的累计奖励。智能体根据当前状态从动作的集合 $\mathcal{A}$ 中选择一个动作的函数，被称为策略。

3.4.1 策略

  智能体的策略（Policy）通常用字母 $\pi$ 表示。策略 $\pi (a|s)=P(A_t=a|S_t=s)$ 是一个函数，表示在输入状态 $s$ 后采取动作 $a$ 的概率。当一个策略是确定性策略（deterministic policy）时，它在每个状态时只输出一个确定性的动作，即只有该动作的概率为 1，其他动作的概率为 0；当一个策略是随机性策略（stochastic policy）时，它在每个状态时输出的是关于动作的概率分布，然后根据该分布进行采样就可以得到一个动作。在 MDP 中，由于马尔可夫性质的存在，策略只需要与当前状态有关，不需要考虑历史状态。

3.4.2 状态价值函数和动作价值函数

  在 MDP 中，基于策略 $\pi$ 的状态价值函数（state-value function）$V^{\pi }(s)$ 定义为从状态 $s$ 出发遵循策略 $\pi$ 能获得的期望回报，数学表达为：
$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s].$$  此外，由于动作的存在，额外定义一个基于策略 $\pi$ 的动作价值函数（action-value function）$Q^{\pi }(s,a)$，表示在 MDP 遵循策略 $\pi$ 时，对当前状态 $s$ 执行动作 $a$ 得到的期望回报，数学表达为：
$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a].$$

3.4.3 状态价值函数和动作价值函数的关系

  在使用策略 $\pi$ 时，状态的价值等于在该状态下基于策略采取所有动作的概率与相应的价值相乘再求和的结果：
$$V^{\pi }(s)=\sum _{a\in A}\pi (a|s)Q^{\pi }(s,a).$$  使用策略 $\pi$ 时，状态 $s$ 下采取动作 $a$ 的价值等于即时奖励加上经过衰减后的所有可能的下一个状态的状态转移概率与相应的价值的乘积：
$$Q^{\pi }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{\pi }(s^{\prime }).$$

3.5 蒙特卡洛方法

  蒙特卡洛方法（Monte-Carlo methods）也被称为统计模拟方法，是一种基于概率统计的数值计算方法。运用蒙特卡洛方法时，通常使用重复随机抽样，然后运用概率统计方法来从抽样结果中归纳出想求的目标的数值估计。
  用蒙特卡洛方法来估计一个策略在一个 MDP 中的状态价值函数的基本思路是：用策略在 MDP 上采样很多条序列，然后计算在这些序列中从这个状态出发的回报，再求其期望，当采样序列数足够大时，每一个状态计算的期望接近于其实际的期望：
$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]\approx \frac{1}{N}\sum _{i=1}^N{G}_t^{(i)}.$$  假设我们用策略 $\pi$ 从状态 $s$ 开始采样序列，据此来计算状态价值。我们为每一个状态维护一个计数器和总回报，计算状态价值的具体过程如下所示：

(1) 使用策略采样若干条序列：
$$s_0^{(i)}\stackrel{a_0^{(i)}}{\to }{r}_0^{(i)},s_1^{(i)}\stackrel{a_1^{(i)}}{\to }{r}_1^{(i)},s_2^{(i)}\stackrel{a_2^{(i)}}{\to }\cdots \stackrel{a_{T-1}^{(i)}}{\to }{r}_{T-1}^{(i)},s_T^{(i)}$$(2) 对每一条序列中的每一时间步 $t$ 的状态 $s$ 进行以下操作：

• 更新状态的计数器 $N(s)\leftarrow N(s)+1$；
• 更新状态的总回报 $M(s)\leftarrow M(s)+G_t$；

(3) 每一个状态的价值被估计为回报的平均值 $V(s)=M(s)/N(s)$。

根据大数定律，当 $N(s)\to \infty$ 时，有 $V(s)\to V^{\pi }(s)$ 。计算回报的期望时，除了可以把所有的回报加起来除以次数，还有一种增量更新的方法：

• $N(s)\leftarrow N(s)+1$
• $V(s)\leftarrow V(s)+\frac{1}{N(s)}(G-V(s))$

3.6 占用度量

  策略 $\pi$ 的占用度量（occupancy measure）表示采取 $\pi$ 时动作状态对 $(s,a)$ 被访问到的概率，定义如下：
$${\rho }^{\pi }(s,a)=(1-\gamma )\sum _{t=0}^{\infty }{\gamma }^t{P}_t^{\pi }(s)\pi (a|s)$$具有以下 2 个定理：

定理 1：智能体分别以策略 ${\pi }_1$ 和 ${\pi }_2$ 和同一个 MDP 交互得到的占用度量 ${\rho }^{{\pi }_1}$ 和 ${\rho }^{{\pi }_2}$ 满足 ${\rho }^{{\pi }_1}={\rho }^{{\pi }_2}⟺{\pi }_1={\pi }_2$。
定理 2：给定一合法占用度量 $\rho$，可生成该占用度量的唯一策略是 ${\pi }_{\rho }=\frac{\rho (s,a)}{{\sum }_{a^{\prime }}\rho (s,a^{\prime })}$。

3.7 最优策略

  最优策略可能有很多个，我们都将其表示为 ${\pi }^{\ast }$。最优策略具有相同的状态价值函数，我们称之为最优状态价值函数，表示为：
$$V^{\ast }(s)=\underset{\pi }{\max }{V}^{\pi }(s),\forall s\in \mathcal{S}$$  同理可定义最优动作价值函数:
$$Q^{\ast }(s,a)=\underset{\pi }{\max }{Q}^{\pi }(s,a),\forall s\in \mathcal{S},a\in \mathcal{A}$$

3.7.1 最优状态价值函数和最优动作价值函数的关系

  为了使 $Q^{\pi }(s,a)$ 最大，我们需要在当前的状态动作对之后都执行最优策略，于是有：
$$Q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{\ast }(s^{\prime })$$  另一方面，最优状态价值是选择此时使最优动作价值最大的那一个动作时的状态价值：
$$V^{\ast }(s)=\underset{a\in \mathcal{A}}{\max }{Q}^{\ast }(s,a)$$

3.7.2 贝尔曼最优方程

  根据 3.7.1 中描述的 $V^{\ast }(s)$ 和 $Q^{\ast }(s,a)$ 的关系，可以得到贝尔曼最优方程（Bellman optimality equation）：
$$V^{\ast }(s)=\underset{a\in A}{\max }\left\{r(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)V^{\ast }(s^{\prime })\right\}$$$$Q^{\ast }(s,a)=r(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,a)\underset{a^{\prime }\in A}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })$$