强化学习基础 2：有限马尔可夫决策过程

2019-04-25 强化学习

有限马尔可夫决策过程 (finite Markov Decision Processes)，也称有限 MDPs，或简称 MDPs，是一种离散时间随机控制过程。它提供了一个数学框架来建模这样的场景：事件的结果一部分依赖于随机性，一部分依赖于决策者作出的决策。

在每个时间步 (time step)，系统处于状态 $s$，决策者可以选择任意一个在状态 $s$ 可用的动作 $a$，之后系统发生状态转移，（在下一个时间步）进入状态 $s’$，并且返回给决策者一个回报 $R_a(s,s’)$。

MDPs 实际上是马尔可夫链的一种扩展：它在马尔可夫链的基础上增加了“动作”和“回报”的概念——允许在每个状态执行不同的动作，并且每次动作执行后能够得到回报。而马尔可夫链仅仅是单纯的在概率支配下随机的状态转移。

MDPs 为强化学习提供了重要的理论基础。本文将介绍在强化学习中的这种数学上形式化的基本概念。（注：本文中的大写字母都一般代表随机变量，小写字母为实例。）

一、Agent 与 Environment 的交互

首先明晰强化学习中的几个基本元素：

以上五点是强化学习中最基本的概念，它们之间的关系为

通过 agent 和环境的这种交互，会产生一个轨迹 (trajectory) 如

$$ S_0,A_0,R_1,S_1,A_1,R_2,\dots $$

在有限 MDP 中，“有限”的意思是状态空间 $\mathcal{S}$、动作空间 $\mathcal{A}$ 和奖励空间 $\mathcal{R}$ 中的元素都是有限的。在这种情况下，通常用环境的动态 (dynamics) $p:\mathcal{S}\times\mathcal{R}\times\mathcal{S}\times\mathcal{A}\mapsto [0,1]$来定义一个环境：

$$ p(s’,r\mid s,a)\doteq\Pr(S_t=s’,R_t=r\mid S_{t-1}=s,A_{t-1}=a) $$

从上式也能看出环境具有马尔可夫特性（下一个状态仅与当前状态有关）。

二、任务的目标

在强化学习中，总目标是使得 agent 获得的长期累计 reward 最大。形式化地描述这个目标：

$$ G_t\doteq R_{t+1}+R_{t+2}+R_{t+3}+\dots R_{T} $$

它表示从时间 $t$ 一直到任务结束 agent 所获得总回报，被称为 return（注意它不是 reward，所以要做的不是最大化 reward 而是最大化 return！）.

但有些任务不会停止。强化学习中，有停止状态的任务被称为 episodic tasks，没有停止状态的任务被称为 continuing tasks。对于连续型任务，上面的定义不合适。所以引入一个在 $[0,1]$之间的折扣因子 (discount factor) $\gamma$，它使得连续型任务的 return 有定义：

$$ G_t\doteq R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\dots $$

并且它有实际意义：距离现在越远的未来不确定性也越大，所以 agent 不太在意未来的回报，而更加重视最近的回报。

实际上可以将这两种不同的任务的 return 用同样的记号来描述：

$$ G_t\doteq\sum_{k=t+1}^T\gamma^{k-t-1}R_k $$

当 $T\to\infty$ 时表示连续型任务；当 $T$ 有限时表示片段型任务。在片段型任务中，$\gamma$ 可以为 1，也可以小于 1。后文中都使用上式来统一表示我们的目标 (return)。

三、策略与价值函数

策略是强化学习的结果：强化学习就是找到一个最优的策略来指导 agent 获得最多回报。而价值函数则是我们优化策略的工具。这在后面的介绍会体现出来。

定义

一个策略 (policy) 是从状态到每个动作概率的映射，即

$$ \pi(a\mid s)\doteq\Pr(A_t=a\mid S_t=s) $$

在某个策略 $\pi​$ 下，某个状态的状态价值函数 $v_\pi(s)​$ 定义为

$$ v_\pi(s)\doteq\mathbb{E}_\pi[G_t\mid S_t=s],\quad \text{for all } s\in\mathcal{S} $$

在某个策略 $\pi​$ 下，某个状态采取某个动作的动作价值函数 $q_\pi(s,a)​$ 定义为

$$ q_\pi(s,a)\doteq\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a],\quad \text{for all } s\in\mathcal{S},a\in\mathcal{A} $$

$v_\pi​$ 和 $q_\pi​$ 可以从经验中获得的采样来估计，这种方法被称为 Monte Carlo methods。当状态空间很大时，状态函数$v_\pi​$ 和 $q_\pi​$ 也可以用参数化的函数来近似（参数个数远远少于状态个数）。

Bellman 方程

价值函数 $v_\pi$ 和 $q_\pi$ 都具有递归性（自洽性），这被称为 Bellman 方程，它能够大大简化后面的许多数学推导。

$v_\pi​$ 的 Bellman 方程为

$$ \begin{align} v_\pi(s)&\doteq\mathbb{E}_\pi[G_t\mid S_t=s]\\ &=\sum_a\pi(a\mid s)\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]\\ &=\sum_a\pi(a\mid s)\mathbb{E}_\pi[R_t+\gamma G_{t+1}\mid S_t=s,A_t=a]\\ &=\sum_a\pi(a\mid s)\Big[\mathbb{E}_\pi[R_t\mid S_t=s,A_t=a]+\gamma\mathbb{E}_\pi[G_{t+1}\mid S_t=s,A_t=a]\Big]\\ &=\sum_a\pi(a\mid s)\Big[\sum_rp(r\mid s,a)r+\gamma\sum_{s’}p(s’\mid s,a)\mathbb{E}_\pi[G_{t+1}\mid S_{t+1}=s’]\Big]\\ &=\sum_a\pi(a\mid s)\Big[\sum_r\sum_{s’}p(s’,r\mid a, s)r+\gamma\sum_{s’}\sum_{r}p(s’,r\mid a, s)\mathbb{E}_\pi[G_{t+1}\mid S_{t+1}=s’]\Big]\\ &=\sum_a\pi(a\mid s)\sum_{s’,r}p(s’,r\mid a, s)\Big[r+\gamma v_\pi(s’)\Big],\quad\text{for all } s\in\mathcal{S} \end{align} $$

式子的最后结果也很容易理解：从当前状态 $s$，可以选择任意的动作 $a$，进入一个状态 $s’$ 并获得一个回报 $r$，这个三元组 $(a,s’,r)$ 发生的概率为 $\pi(a\mid s)p(s’,r\mid a, s)$；而这个三元组导致的 return 为“这一次状态转移带来的 reward 加上下一个状态的 return”，即 $r+\gamma v_\pi(s’)$；把所有可能的情况通过概率加权求和就得到数学期望。

通过这个思想，我们可以直接写出 $q_\pi$ 的 Bellman 方程

$$ q_\pi(s,a)=\sum_{s’,r}p(s’,r\mid s,a)\Big[r+\gamma\sum_{a’}\pi(a’\mid s’)q_\pi(s’,a’)\Big] $$

四、最优策略与最优价值函数

之前提到，解决一个强化学习任务就是要找到一个最优的策略来获得最多的回报。对于有限 MDPs，我们可以对最优策略做如下的精确定义。

定义

如果用 $\pi \ge \pi’$ 表示一个策略 $\pi$ 优于或等于另一个策略 $\pi’$，则有

$$ \pi\ge\pi’\Longleftrightarrow \forall s\in\mathcal{S},, v_\pi(s)\ge v_{\pi’}(s) $$

至少存在一个策略 $\pi_\ast​$ 满足

$$ \forall \pi,,\pi_\ast\ge\pi $$

我们称这个 $\pi_\ast​$ 为最优策略。

这里定义的 $\ge$ 是一种偏序关系，所以最优策略可能不止一个。但它们都有共同的价值函数 $v_\ast$ 和 $q_\ast​$（被称为最优价值函数）：

$$ \begin{align} v_\ast(s)&\doteq\underset{\pi}{\rm max },v_\pi(s),\quad \text{for all } s\in\mathcal{S}\ q_\ast(s,a)&\doteq\underset{\pi}{\rm max },q_\pi(s,a),\quad \text{for all } s\in\mathcal{S},a\in\mathcal{A}(s) \end{align} $$

由定义，也可以把最优动作价值函数写成

$$ q_\ast(s,a)=\mathbb{E}[R_{t+1}+\gamma v_\ast(s)\mid S_t=s,A_t=a] $$

Bellman 最优方程

由于 $v_\ast$ 也是某个策略的价值函数，因此也满足 Bellman 自洽方程，只是它的形式更特别，其推导如下：

$$ \begin{align} v_\ast(s)&\doteq \max_\pi v_\pi(s)\tag{By definition}\\ &=\max_\pi\sum_a\pi(a\mid s)q_\pi(s,a)\\ &=\max_aq_\ast(s,a)\\ &=\max_a\mathbb{E}_{\pi_\ast}[G_t\mid S_t=s,A_t=a]\\ &=\max_a\mathbb{E}_{\pi_\ast}[R_{t+1}+\gamma G_{t+a}\mid S_t=s,A_t=a]\\ &=\max_a\mathbb{E}_{\pi_\ast}\Big[R_{t+1}+\gamma \mathbb{E}_{\pi_\ast}[G_{t+a}\mid S_{t+1}]\Big\vert S_t=s,A_t=a\Big]\tag{Law of total expectation}\\ &=\max_a\mathbb{E}_{\pi_\ast}[R_{t+1}+\gamma v_\ast(S_{t+1})\mid S_t=s,A_t=a]\tag{By definition}\\ &=\max_a\sum_{s’,r}p(s’,r\mid s,a)[r+\gamma v_\ast(s’)] \end{align} $$

这个方程表达了：在最优策略下，每个状态的价值等于在这个状态下选择最佳动作所产生的期望 return。所以最优策略是一种确定性策略 (deterministic policy)。

同样可以推导 $q_\pi$ 的 Bellman 最优方程：

$$ \begin{align} q_\ast(s,a)&=\mathbb{E}_{\pi_\ast}[G_t\mid S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi_\ast}[R_{t+1}+\gamma G_{t+1}\mid S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi_\ast}[R_{t+1}+\gamma v_\ast(S_{t+1})\mid S_t=s,A_t=a]\\ &=\mathbb{E}_{\pi_\ast}\left[R_{t+1}+\gamma \max_{a’}q_\ast(S_{t+1},a’)\mid S_t=s,A_t=a\right]\\ &=\sum_{s’,r}p(s’,r\mid s,a)\left[r+\gamma \max_{a’}q_\ast(s’,a’)\right] \end{align} $$

分析

对于有限 MDPs，$v_\ast​$ 的 Bellman 最优方程有唯一解。原因是：Bellman 最优方程实际上是一个方程组，每个状态有一个方程。如果有 $n​$ 个状态，就有 $n​$ 个方程；如果系统的 dynamics 已知，则可以解出这个非线性方程组。同理可以求解 $q_\ast(s,a)​$。

一旦有了 $v_\ast(s)​$，则很容易获得一个最优策略：在每个状态 $s​$ 选择那些使 Bellman 最优方程右边取最大的动作，即 ${\underset{a}{\rm argmax},\sum_{s’,r}p(s’,r\mid s,a)[r+\gamma v_\ast(s’)]}​$ 中的一个动作即可。这变成了一个“单步向前搜索”，非常迅速地就能找到解。而如果要是有了 $q_\ast(s,a)​$，连一步向前的搜索也不需要，直接选择 ${\underset{a}{\rm argmax},q_\ast(s,a)}​$ 中的一个动作即可。这就是最优价值函数的作用：它们将能够获得的最优的未来回报都提前计算好并且“缓存”下来，使得做决定时只要考虑当前状态就可以。因此可以不需要知道环境的 dynamics。

直接求解 Bellman 最优方程在绝大多数情况下行不通：这是一种穷举搜索，依赖大量计算资源。所以现实情况大多是退而求其次，通过某种方法来求近似解。例如使用启发式搜索、动态规划等。这些方法将在后面的文章一一介绍。

参考