1 马尔可夫决策过程

马尔可夫决策过程（Markov decision process, MDP）是强化学习理论的重要概念。

Info

随机过程研究随时间演变的随机现象。

一般用 \(P\left(S_{t+1}|S_1, \cdots, S_t\right)\) 表示系统 t+1 时刻的状态为 \(S_{t+1}\) 的概率，受前 \(t\) 个历史状态信息影响。

如果 \(P\left(S_{t+1}|S_1, \cdots, S_t\right) = P\left(S_{t+1}|S_t\right)\) ，则称该随机过程具有 Markov 性质。换言之，当前状态是未来的充分统计量。

马尔可夫过程

马尔可夫过程（Markov process）就是具有 Markov 性质的随机过程，也被称为马尔科夫链。假定一个随机过程具有 \(n\) 个状态，其集合为 \(\mathcal{S} = \left\{s_1, \cdots, s_n\right\}\)，则可定义状态转移矩阵 \(\mathcal{P}\) ：

\[ \mathcal{P} = \begin{bmatrix}P(s_1|s_1) & \cdots & P(s_n|s_1)\\ \vdots & & \vdots\\ P(s_n|s_1) & \cdots & P(s_n|s_n)\end{bmatrix} \]

矩阵中 \(i\) 行 \(j\) 列的元素代表从状态 \(s_i\) 转移到状态 \(s_j\) 的概率。每一行的和都是 1 。基于此，我们可以用元组 \(\left<\mathcal{S}, \mathcal{P}\right>\) 定义一个马尔可夫过程

马尔可夫奖励过程

马尔可夫奖励过程（Markov reward process）是在马尔可夫过程的基础上引入奖励函数 \(r\) 和折扣因子 \(\gamma\) 的结果，表示为 \(\left<\mathcal{S}, \mathcal{P}, r, \gamma\right>\) 。奖励函数 \(r(s)\) 代表转移到该状态时可以获得奖励的期望值； \(\gamma\) 是折扣因子，取值在 \([0,1)\) ，越接近于 0，代表越重视眼前的奖励，而非长远奖励。

回报

回报 \(G_t\) 表示为从 \(t\) 时刻状态 \(S_t\) 开始，直到终止状态时，所有奖励的衰减之和。

\[ G_t = R_t + \gamma R_{t+1} + \gamma^2R_{t+2} + \cdots =\sum_{k=0}^{\infty}\gamma^k R_{t+k} \]

价值函数

在马尔可夫奖励过程中，一个状态的期望回报被称为这个状态的价值。任意状态与价值的映射关系称为价值函数（value function）：

\[\begin{aligned} V(s) &= \mathbb{E}\left[G_t|S_t = s\right]\\ &= \mathbb{E}\left[R_t+\gamma R_{t+1} + \gamma^2R_{t+2} + \cdots|S_t = s\right]\\ &= \mathbb{E}\left[R_t + \gamma V(S_{t+1})|S_t = s\right]\\ &= r\left(s\right)+\gamma\mathbb{E}\left[V(S_{t+1})|S_t=s\right] \end{aligned}\]

上式等号右边第二项，代表当前状态 \(S_t = s\) 时，下一时刻状态 \(S_{t+1}\) 可能为各个状态的情况下，其回报的期望值。因此可以推导得到著名的贝尔曼方程（Bellman equation）：

\[\begin{aligned} V(s) &= r\left(s\right)+\gamma\mathbb{E}\left[V(S_{t+1})|S_t=s\right]\\ &= r(s) + \gamma \sum_{s'\in \mathcal{S}}p\left(s'|s\right)V\left(s'\right) \end{aligned}\tag{2-3}\]

Comment

贝尔曼方程的特点是把两个时刻的价值函数联系起来了。

如果我们将所有状态的价值函数和奖励函数都写成一个列向量 \(\mathcal{V}\) 和 \(\mathcal{R}\)，则有

\[\begin{aligned} \mathcal{V} &= \mathcal{R}+\gamma\mathcal{P}\mathcal{V}\\ \begin{bmatrix}V(s_1)\\V(s_2)\\ \cdots\\ V(s_n)\end{bmatrix} &= \begin{bmatrix}r(s_1)\\r(s_2)\\ \cdots\\ r(s_n)\end{bmatrix}+\gamma\begin{bmatrix}P(s_1|s_1) & \cdots & P(s_n|s_1)\\ \vdots & & \vdots\\ P(s_n|s_1) & \cdots & P(s_n|s_n)\end{bmatrix}\begin{bmatrix}V(s_1)\\V(s_2)\\ \cdots\\ V(s_n)\end{bmatrix} \end{aligned}\]

上式的解析解为 \(\mathcal{V} = (I-\gamma\mathcal{P})^{-1}\mathcal{R}\) 。此处， \(I-\gamma\mathcal{P}\) 一定是可逆的，因为 \(\gamma < 1\) 且 \(\mathcal{P}\) 对角线上的元素也小于 1 。矩阵求逆的时间复杂度是 \(\mathcal{O}\left(n^3\right)\) ，所以解析解的方法不适用于大规模马尔可夫奖励过程的价值函数求解。

马尔可夫决策过程

上文中的马尔可夫过程和马尔可夫奖励过程都是自发改变的随机过程，如果有一个智能体（agent）参与进来，通过动作（action）使随机过程在控制作用下发生改变，就有了马尔可夫决策过程（Markov decision process）。

MDP 由元组 \(\left<\mathcal{S}, \mathcal{A}, P, r, \gamma\right>\) 组成。其中， \(\mathcal{A}\) 是动作的集合；\(P\left(s'|s,a\right)\) 是状态转移函数，表示随机过程在状态 \(s\) 执行动作 \(a\) 后，到达状态 \(s'\) 的概率。

Note

MDP 的状态转移函数有别于 MRP 的状态转移矩阵。

智能体根据当前状态 \(S_t\) 从集合 \(\mathcal{A}\) 中选择一个动作 \(A_t\) ，被称为策略。智能体的目的是最大化累计奖励。

策略

策略 \(\pi(a|s) = P(A_t=a|S_t=s)\) 代表在输入状态 \(s\) 情况下采取动作 \(a\) 的概率。在 MDP 中，由于随机过程具有 Markov 性质，因此只需要考虑当前状态即可。

状态价值函数

MDP 中基于策略 \(\pi\) 的状态价值函数（state-value function）定义为从状态 \(s\) 出发遵循策略 \(\pi\) 能获得的期望回报：

\[ V^{\pi}(s) = \mathbb{E}_\pi[G_t|S_t = s] \tag{3-1} \]

动作价值函数

MDP 中需要额外定义一个动作价值函数（action-value function），表示遵循策略 \(\pi\) ，在当前状态 \(s\) 执行动作 \(a\) 得到的期望回报：

\[ Q^{\pi}(s,a) = \mathbb{E}[G_t|S_t=s,A_t=a] \tag{3-2} \]

动作价值函数和状态价值函数满足如下关系：

\[ \begin{aligned} V^{\pi}(s) &= \sum_{a\in \mathcal{A}}\pi(a|s) Q^{\pi}(s,a) \\ Q^{\pi}(s,a) &= \mathbb{E}[G_t|S_t=s,A_t=a]\\ &= \mathbb{E}\left[R_t+\gamma R_{t+1} + \gamma^2R_{t+2} + \cdots|S_t=s,A_t=a\right]\\ &= \mathbb{E}[R_t+\gamma V^{\pi}(S_{t+1})|S_t=s,A_t=a]\\ &= r(s,a)+\gamma\sum_{s'\in \mathcal{S}}P\left(s'|s,a\right)V^{\pi}\left(s'\right) \end{aligned}\tag{3-3} \]

贝尔曼期望方程

\[\begin{align}\begin{aligned} V^{\pi}(s) &= \sum_{a\in \mathcal{A}}\pi(a|s) Q^{\pi}(s,a)\\ &= \sum_{a\in A}\pi(a|s)\left(r(s,a)+\gamma\sum_{s'\in S}P\left(s'|s,a\right)V^{\pi}\left(s'\right)\right)\\ \end{aligned}\tag{3-5}\\ \begin{aligned} Q^{\pi}(s,a) &= r(s,a)+\gamma\sum_{s'\in S}P\left(s'|s,a\right)V^{\pi}\left(s'\right)\\ &= r(s,a)+\gamma\sum_{s'\in S}P\left(s'|s,a\right)\sum_{a'\in A}\pi\left(a'|s'\right)Q^{\pi}\left(s',a'\right) \end{aligned}\tag{3-6}\end{align}\]

计算 MDP 下策略 \(\pi\) 的状态价值函数

理论求解的思路是转化为 MRP。将策略的动作选择进行边缘化（marginalization），即对于某一状态，根据策略采取某一动作的概率，将所有动作的奖励进行加权，有

\[ r'(s) = \sum_{a\in \mathcal{A}}\pi(a|s)r(s,a) \tag{3-7} \]

同理可以得到状态转移概率：

\[ P'\left(s'|s\right) = \sum_{a\in \mathcal{A}}\pi(a|s)P(s'|s,a) \tag{3-8} \]

用这个状态转移概率构造状态转移矩阵 \(\mathcal{P}'\) ，然后就构建了一个 MRP \(\left<\mathcal{S}, \mathcal{P}',r',\gamma\right>\) 。我们来看看此时，原来的 MDP 的状态价值函数变成了什么样子。考虑将（3-7）和（3-8）代入（3-5），有

\[\begin{aligned} V^{\pi}(s) &= \sum_{a\in A}\pi(a|s)\left(r(s,a)+\gamma\sum_{s'\in S}P\left(s'|s,a\right)V^{\pi}\left(s'\right)\right)\\ &= \sum_{a\in A}\pi(a|s)r(s,a)+\gamma\sum_{a\in A}\pi(a|s)\sum_{s'\in S}P\left(s'|s,a\right)V^{\pi}\left(s'\right)\\\ &= r'(s) + \gamma\sum_{s'\in S}P'\left(s'|s\right)V^{\pi}\left(s'\right) \end{aligned}\]

比较上式与（2-3）式，可见，转换前的 MDP 与转换后的 MRP 的状态价值函数完全一致。

蒙特卡洛方法

蒙特卡洛是一种求策略 \(\pi\) 的状态价值函数 \(V^{\pi}(s)\) 的方法。

首先，使用策略 \(\pi\) 采样若干条序列：

\[ s_0^{(i)}\overset{a_0^{(i)}}\longrightarrow r_0^{(i)},s_1^{(i)}\overset{a_1^{(i)}}\longrightarrow r_1^{(i)},s_2^{(i)}\overset{a_2^{(i)}}\longrightarrow\cdots\overset{a_{T-1}^{(i)}}\longrightarrow r_{T-1}^{(i)},s_T^{(i)} \]

等一条序列（从起始状态 \(s\) 按照策略到终止状态）结束后，我们得到该序列的总回报值 \(G_t\) 。接下来，考虑用增量更新的方式，更新状态 \(s\) 的计数器和平均回报：

\[\begin{aligned} N(s) &\leftarrow N(s)+1\\ V(s) &\leftarrow V(s) + \frac{1}{N(s)}(G_t-V(s)) \end{aligned}\]

式中 \(G_t\) 是当前这次采样的回报值。根据大数定律，当 \(N(s) \to \infty\) 时，有 \(V(s) \to V^{\pi}(s)\) 。

占用度量

不同策略会使智能体访问到不同概率分布，导致价值函数不同。

定义 MDP 的初始状态分布为 \(\nu_0(s)\) ；用 \(P_t^{\pi}(s)\) 表示采取策略 \(\pi\) 使得智能体在 \(t\) 时刻状态为 \(s\) 的概率，有 \(P_0^{\pi}(s) = \nu_0(s)\) 。这个状态访问概率有一个递推形式：

\[ P_t^{\pi}(s') = \int P\left(s'\right|s,a)\pi(a|s)P_{t-1}^{\pi}(s)\mathrm{d}s\mathrm{d}a \]

然后就可以定义一个策略的状态访问分布（state visitation distribution）

\[ \nu^\pi(s) = (1-\gamma)\sum_{t=0}^{\infty}\gamma^tP_t^{\pi}(s) \]

这个式子用来描述一个策略和 MDP 交互会访问到的状态的概率分布。这里用 \(\gamma\) 做折扣访问分布，越靠前的权重越高。式中 \(1-\gamma\) 是用来使概率加和为 1 的归一化因子，因为 \(\sum_{t=0}^{\infty}\gamma = \frac{1}{1-\gamma},\gamma\in[0,1)\) 。状态访问概率有如下性质：

\[\begin{aligned} \nu^{\pi}\left(s'\right) &= (1-\gamma) P_0^{\pi}\left(s'\right) + (1-\gamma)\sum_{t=1}^{\infty}\gamma^tP_t^{\pi}\left(s'\right)\\ &= (1-\gamma)\nu_0\left(s'\right) + (1-\gamma)\sum_{t=1}^{\infty}\gamma^t\int P\left(s'|s,a\right)\pi(a|s)P_{t-1}^{\pi}(s)\mathrm{d}s\mathrm{d}a\\ &\overset{k=t-1} = (1-\gamma)\nu_0\left(s'\right) + \gamma(1-\gamma)\sum_{k=0}^{\infty}\gamma^k\int P\left(s'|s,a\right)\pi(a|s)P_{k}^{\pi}(s)\mathrm{d}s\mathrm{d}a\\ &= (1-\gamma)\nu_0\left(s'\right) + \gamma\int P\left(s'|s,a\right)\pi(a|s)(1-\gamma)\sum_{k=0}^{\infty}\gamma^kP_{k}^{\pi}(s)\mathrm{d}s\mathrm{d}a\\ &= (1-\gamma)\nu_0\left(s'\right)+\gamma\int P\left(s'|s,a\right)\pi(a|s)\nu^{\pi}(s)\mathrm{d}s\mathrm{d}a \end{aligned}\]

如下定义策略的占用度量（occupancy measure）：

\[\begin{aligned} \rho^{\pi}(s,a) &= (1-\gamma)\sum_{t=0}^{\infty}\gamma^tP_t^{\pi}(s)\pi(a|s)\\ &= \nu^{\pi}(s)\pi(a|s) \end{aligned}\]

它表示动作状态对 \((s,a)\) 被访问到的概率。

【定理 1】智能体分别以策略 \(\pi_1\) 和 \(\pi_2\) 和同一个 MDP 交互，得到的占用度量 \(\rho^{\pi_1}\) 和 \(\rho^{\pi_2}\) 满足

\[ \rho^{\pi_1} = \rho^{\pi_2} \Leftrightarrow \pi_1 = \pi_2 \]

【定理 2】给定一合法占用度量 \(\rho\) ，可生成该占用度量的唯一策略是

\[ \pi_{\rho} = \frac{\rho(s,a)}{\sum_{a'}\rho\left(s,a'\right)} \]

【解读】访问到动作状态对 \((s,a)\) 的概率除以所有访问到状态 \(s\) 的概率，就是在状态 \(s\) 下采取动作 \(a\) 的概率。

最优策略

当且仅当对于任意的状态 \(s\) ，都有 \(V^{\pi}(s) \ge V^{\pi'}(s)\) ，记 \(\pi > \pi'\) 。如果是有限状态和动作集合的 MDP，肯定存在一个策略不差于其它所有策略，这个就是最优策略（optimal policy），表示为 \(\pi^{*}(s)\) 。

最优策略对应的状态价值函数是最优状态价值函数：

\[ V^{*}(s) = \max_{\pi}V^{\pi}(s), \forall s \in \mathcal{S} \]

最优策略对应的动作价值函数是最优动作价值函数：

\[ Q^{*}(s,a) = \max_{\pi}Q^{\pi}(s,a), \forall s \in \mathcal{S}, a \in \mathcal{A} \]

在当前状态动作对 \((s,a)\) 之后都执行最优策略，即可得到两式关系：

\[ Q^{*}(s,a) = r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V^{*}\left(s'\right) \]

上式与普通策略下的关系（3-3）式一致。给定一个状态，最优状态价值等于此时的最优动作价值关于动作的最大值：

\[ V^{*}(s) = \max_{a\in \mathcal{A}}Q^{*}(s,a) \]

贝尔曼最优方程

Bellman optimality equation:

\[\begin{aligned} V^{*}(s) &= \max_{a\in \mathcal{A}}Q^{*}(s,a)\\ &= \max_{a\in\mathcal{A}}\left\{r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V^{*}\left(s'\right)\right\}\\ Q^{*}(s,a) &= r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)V^{*}\left(s'\right)\\ &= r(s,a)+\gamma\sum_{s'\in\mathcal{S}}P\left(s'|s,a\right)\max_{a'\in \mathcal{A}}Q^{*}(s',a') \end{aligned}\]