强化学习中的算法-译 2 马尔可夫决策过程

本节的目的是介绍后续部分将使用的符号,以及我们在本书其余部分将需要的马尔可夫决策过程(Markov Decision Processes, MDPs)理论中的最基本事实。熟悉 MDP 的读者可以略读本节,熟悉一下符号。不熟悉 MDP 的读者,建议花足够的时间来了解本节的细节。大多数结果的证明(有一些简化)都在附录 A 中。建议有兴趣了解更多关于 MDP 的读者参考许多关于该主题的优秀书籍,如Bertsekas和Shreve(1978)[1]、Puterman(1994)[2]的书,或Bertsekas(2007a[3],b[4])的两卷书。

预备工作

记 $\Bbb{N}$ 为自然数的集合,即 $\Bbb{N}=\{0,1,2,\dots\}$。记 $\Bbb{R}$ 为实数的集合。我们说向量 $v$(其转置为 $v^\top$)为列向量。两个有限维的向量 $u, v \in \Bbb{R}$ 的内积为 $\langle u, v \rangle = \sum_{i=1}^du_id_i$,因此向量 $u$ 的 2-范数为 $\lVert u \rVert^2=\langle u,u\rangle$。向量的最大范数定义为 $\lVert u\rVert_\infty=\max_{i=1,\dots,d}\lvert u_i \rvert$,对于函数 $f:\mathcal{X}\to \Bbb{R}$,$\lVert \cdot\rVert_\infty$ 定义为 $\lVert f\rVert_\infty=\sup_{x\in\mathcal{X}}\lvert f(x) \rvert$。度量空间 $(M_1, d_1),(M_2, d_2)$ 间的映射 $T$ ,对于任意的 $a, b \in M_1$有 $d_2(T(a),T(b)) \leq Ld_1(a,b)$,我们称 $T$ 为利普希茨(Lipschitz)映射,模为$L\in\Bbb{R}$。如果 $T$ 为模 $L \leq 1$ 的利普希茨映射,它也叫非扩展映射。如果 $L \lt 1$,它叫压缩映射。事件 $S$ 的指示函数记作 $\Bbb{I}_{\lbrace S \rbrace}$,也就是说如果 $S$ 发生,那么 $\Bbb{I}_{\lbrace S \rbrace}=1$,反之为 0。如果 $v = v(\theta,x)$,则 $v$ 对于 $\theta$ 的偏导为$\frac{\partial}{\partial \theta}v$,如果 $\theta \in \Bbb R$,则其为一个 $d$ 维的行向量。某个表达式 $v$ 对于 $\theta$ 的总导数为 $\frac{d}{d \theta}v$(并且也被视作行向量)。更进一步地,$\nabla_\theta v = (\frac{d}{d \theta}v)^\top$。如果 $P$ 是一个分布或概率测度,则 $x\sim P$ 意味着 $x$ 是从 $P$ 中抽取的随机变量。

马尔可夫决策过程

为了便于阐述,我们将注意力限制在可数 MDP 和折扣总期望奖励准则上。然而,在一些技术条件下,这些结果也可以扩展到连续状态-动作 MDP。这在本书后面部分的结果中也同样成立。

一个可数的 MDP 定义为一个三元组 $\mathcal{M}=(\mathcal{X},\mathcal{A},\mathcal{P}_0)$,这里 $\mathcal{X}$ 为可数非空的状态集,$\mathcal{A}$ 为可数非空的动作集。转移概率核 $\mathcal{P}_0$ 给每个状态-动作对 $(x, a)\in\mathcal{X}\times \mathcal{A}$ 分配了一个 $\mathcal{X}\times\Bbb{R}$ 上的概率测度,记作 $\mathcal{P}_0(\cdot\mid x,a)$。$\mathcal{P}_0$ 的语义为,对于 $U\subset \mathcal{X}\times\Bbb{R}$,给定当前状态 $x$,采取动作 $a$,$\mathcal{P}_0(U\mid x,a)$给出了下一个状态和奖励属于集合 $U$ 的概率[5]。我们还有一个 $0\leq\gamma\leq1$ 的折扣系数,其作用稍后阐明。

转移概率核给出了状态转移概率核,$\mathcal{P}$,即对于任何三元组 $(x,a,y)\in\mathcal{X}\times \mathcal{A}\times\mathcal{X}$,只要在状态 $x$ 中选择了动作 $a$,就可以得出从状态 $x$ 到其他状态 $y$ 的概率:$$\mathcal{P}(x,a,y)=\mathcal{P}_0(\lbrace y\rbrace\times\Bbb{R}\mid x, a)$$

除了 $\mathcal{P}$ 之外,$\mathcal{P}_0$ 还产生了即时奖励函数 $r:\mathcal{X}\times\mathcal{A}\to\Bbb{R}$,它给出了在状态 $x$ 中选择动作 $a$ 时得到的期望即时奖励:如果 $(Y_{(x,a)}, R_{(x,a)})\sim \mathcal{P}_0(\cdot\mid x, a)$, 那么 $$r(x, a) = \Bbb{E}[R_{(x,a)}]$$

在下文中,我们将假设奖励被某个量 $\mathcal{R}\gt 0$ 所约束:对于任何 $(x,a)\in\mathcal{X}\times \mathcal{A}$,$\lvert R_{(x,a)}\rvert\leq \mathcal{R}$ 几乎必然成立[6]。直接地,如果随机奖励被 $\mathcal{R}$ 约束,那么 $\lVert r\rVert_\infty = \sup_{(x,a)\in\mathcal{X}\times \mathcal{A}}\lvert R_{(x,a)}\rvert\leq \mathcal{R}$ 也成立。一个 MDP 被称为 有限的,当 $\mathcal{X}$ 和 $\mathcal{A}$ 二者都有限时。

马尔可夫决策过程是一种对顺序决策问题进行建模的工具,其中决策者以顺序方式与系统进行交互。给定一个 MDP $\mathcal{M}$,这种交互发生如下:令 $t\in\Bbb{N}$ 为当前时间(或阶段),$X_t\in\mathcal{X}, A_t\in\mathcal{A}$ 分别表示系统的随机状态和决策者在时刻 $t$ 选择的动作。一旦动作被选择,它就被发送到系统中,由系统作出转换:$$(X_{t+1}, R_{t+1})\sim \mathcal{P}_0(\cdot\mid X_t,A_t) \tag{1}$$

特别地,$X_{t+1}$ 是随机的,且对于任何 $x, y\in\mathcal{X}, a\in\mathcal{A}$,$\Bbb{P}(X_{t+1}=y\mid X_t=x,A_t)=\mathcal{P}(x,a,y)$ 成立。更近一步地,$\Bbb{E}[R_{t+1}\mid X_t, A_t]=r(X_t,A_t)$。然后决策者观察下一状态 $X_{t+1}$ 和奖励 $R_{t+1}$,选择一个新的动作 $A_{t+1}\in \mathcal{A}$,这个过程重复进行。决策者的目标是想出一种选择行动的方法,以便最大化总折扣奖励期望。

决策者可以根据观察到的历史在任何阶段选择其动作,一个描述动作选择方式的规则被称之为行为(behavior)。决策者的行为和一些初始随机状态 $X_0$ 共同定义了一个随机状态-动作-奖励序列($(X_t,A_t,R_{t+1});t\geq 0$),其中 $(X_{t+1}, R_{t+1})$ 通过(1)与 $(X_t, A_t)$ 相联系,$A_t$ 是行为根据历史 $X_0,A_0,R_1,\dots,X_{t-1},A_{t-1},R_t,X_t$ 指定的动作[7]。一个行为下的回报(return)定义其引起的奖励的全部折扣和:$$\mathcal{R}=\sum_{t=0}^\infty\gamma^tR_{t+1}$$

因此,如果 $\gamma \leq 1$,那么未来的奖励就会以指数形式小于第一阶段获得的奖励。当回报由这个公式定义时,一个 MDP 被称为折扣奖励 (discounted reward)MDP。当 $\gamma = 1$ 时,该 MDP 被称为未折扣的(undiscounted)。

决策者的目标是选择一种使预期回报最大化的行为,而不考虑过程是如何开始的。这样一个最大化的行为被称为最优(optimal)。

例一(由销售损失的库存控制)

考虑在需求不确定的情况下,对最大尺寸固定的库存进行日常控制的问题:每天晚上,决策者必须决定第二天的订货量。早上,订购的数量到了,库存就被填满了。在一天中,有一些随机的需求出现,这里需求是独立的,具有共同的固定分布。库存经理的目标是管理库存,以使未来预期总收入的现时货币价值最大化。

时间步骤 $t$ 的报酬确定如下:与购买 $A_t$ 物品相关的成本是 $K\Bbb{I}_{\lbrace A_t\gt0\rbrace} + cA_ t$。因此,订购非零个物品有一个固定的进入成本 $K$,每件物品必须以固定的价格 $c$ 购买。这里,$K, c \gt 0$。此外,还有一个持有大小为 $x\gt0$ 的库存的成本,在最简单的情况下,这个成本与大小成正比,比例系数 $h\gt0$。最后,在卖出 $z$ 个单位后,经理得到 $p z$ 的货币金额,其中 $p>0$。为了让问题变得有趣,我们必须让 $p>h$,否则就没有动力去订购新的物品。

这个问题可以表述为一个 MDP,如下所示:令 $t\geq0$ 日的状态 $X_t$ 为当天晚上的库存大小。因此,$\mathcal{X}={0,1,\dots,M}$,其中 $M\in\Bbb{N}$,是最大的库存规模。动作 $A_t$ 给出了第 $t$ 天晚上订购的物品数量。因此,我们可以选择 $\mathcal{A}={0,1,\dots,M}$,因为没有必要考虑大于库存规模的订单。给定 $X_t$ 和 $A_t$,下一个库存的大小由 $$X_{t+1}=((X_t+A_t)\land M-D_{t+1} )^+ \tag{2}$$ 给出,其中,$a\land b$ 是数字 $a$、$b$ 的最小值的速记符号。$(a)^+=a\lor 0=\max{\lbrace a,0\rbrace}$,是 $a$ 的正数部分。$D_{t+1}\in\Bbb{N}$ 是第 $t+1$ 天的需求。根据假设,$(D_t;t\gt0)$ 是一个独立同分布(i.i.d)的整数值随机变量的序列。第 $t+1$ 天的收入为: $$R_{t+1} = -K\Bbb{I}_{\lbrace A_t\gt0\rbrace} - c((X_t+A_ t)\land M-X_t)^+ -hX_t+p((X_t+A_ t)\land M-X_{t+1})^+\ \tag{3}$$

方程(2,3)可以写成紧凑的形式:$$(X_{t+1},R_{t+1})=f(X_t,A_t,D_{t+1}) \tag{4}$$ ,这里的 $f$ 为适当选择的函数。因此, $\mathcal{P}_0$ 由 $$\mathcal{P}_0(U\mid x, a)=\Bbb{P}(f(x,a,D))=\sum_{d=0}^\infty\Bbb{I}_{\lbrace f(x,a,d)\in U\rbrace} p_D(d)$$ 给出。

这里 $p_D(\cdot)$ 是随机需求的概率质量函数,且 $D\sim p_D(\cdot)$。到这就完成了对库存优化问题下的MDP 定义。

库存控制只是产生 MDP 的众多运筹学问题中的一个,其他问题包括优化运输系统、优化时间表或生产。MDP 也自然地出现在许多工程优化控制问题中,如化学、电子或机械系统的优化控制(后者包括控制机器人的问题)。相当多的信息论问题也可以表示为 MDP(例如,最优编码、优化信道分配或传感器网络)。另一类重要的问题来自于金融,这些问题包括最优投资组合管理和期权定价。
在库存控制问题中,MDP 被方便地用一个转移函数 $f$ 来定义(参见(4))。事实上,转移函数和转移核一样强大:任何 MDP 都会产生某个转移函数 $f$,任何转移函数 $f$ 都会产生某个 MDP。

在某些问题中,并非所有的动作在所有的状态下都是有意义的。例如,订购超过库存空间的物品并没有什么意义。然而,这种无意义的动作(或被禁止的动作)总是可以被重新转换为其他动作,就像上面做的那样。在某些情况下,这是不自然的,并导致了一种错综复杂的动态。那么,引入一个额外的映射,将可接受的(admissible)动作集分配给每个状态,可能会更好。

在某些 MDP 中,有些状态是不可能离开的:如果 $x$ 是这样的状态,那么只要 $X_t = x$,在任何 $s \geq 1$ 的情况下,$X_{t+s} = x$ 几乎必然成立,无论在时刻 $t$ 之后选择什么动作。按照惯例,我们将假设在这种终结(terminal)或吸收(ansorbing)状态下不产生任何奖励。具有这种状态的 MDP 被称为情节性(episodic)的。那么,一个情节(episode)是指从时间的开始到达到终端状态的(一般是随机的)时间段。在一个情节性的 MDP 中,我们经常考虑未折扣的奖励,即 $γ=1$。

例二(赌博)

一个赌徒进入一个独具,她可以用她当前财富 $X_t \geq 0$ 的任何部分 $A_t\in[0, 1]$ 作为赌注。她以概率$p\in[0, 1]$赢回她的赌注和更多,而她以概率 $1-p$ 输掉她的赌注。因此,这个赌徒的财富根据 $$X_{t+1}=(1+S_{t+1}A_t)X_t$$ 变化。

这里,${S_t;t\geq 1}$ 是一个独立随机变量的序列,取值范围为 ${-1,+1}$,并有 $\Bbb{P}(S_{t+1}=1)=p$。赌徒的目标是使她的财富达到先验给定值 $w^\ast \gt 0$ 的概率最大化,假设初始财富在 $[0, w^\ast]$ 之间。这个问题可以表示为一个情节性的 MDP,其中状态空间为 $\mathcal{X}=[0,w^\ast]$,动作空间为 $\mathcal{A}=[0,1]$。我们令 $w^\ast$ 为一个终结状态:如果 $X_t=w^\ast$,有$X_{t+1}=X_t$;当 $0\leq X_t \lt w^\ast$ 时,定义 $$X_{t+1}=(1+S_{t+1}A_t)X_t\land w^\ast \tag{5}$$。

只要 $X_{t+1}\lt w^\ast$,即时奖励为 0,当状态首次到达 $w^\ast$ 为 1:

$$R_{t+1} = \begin{cases}1, X_t < w^\ast \text{and} X_{t+1}=w^\ast \\ 0, \text{otherwise} \end{cases}$$

如果我们把折扣系数设为 $1$,那么沿着任何轨迹的总奖励将是 1 或 0,这取决于财富是否达到 $w^\ast$ 。因此,总奖励期望是赌徒的财富达到 $w^\ast$ 的概率。

基于到目前为止的两个例子,不熟悉 MDP 的读者可能会认为所有的 MDP 都有方便的一维状态和动作空间。如果这是真的就好了! 事实上,在实际应用中,状态空间和动作空间往往是非常大的多维空间。例如,在机器人控制应用中,状态空间的维度可能是机器人关节数的 3-6 倍。一个工业机器人的状态空间可能很容易达到 12-20 维,而一个仿人机器人的状态空间可能很容易有 100 维。在现实世界的库存控制应用中,物品会有多种类型,价格和成本也会根据「市场」的状态而改变,因此,市场的状态也会成为MDP 状态的一部分。因此,在任何这样的实际应用中,状态空间将是非常大和非常高维的。动作空间也是如此。因此,处理大的、多维的状态和动作空间应该被认为是正常情况,而本节所介绍的具有一维的、小的状态空间的例子应该被看作是例外。


  1. 1.Bertsekas, D. P. and Shreve, S. (1978). Stochastic Optimal Control (The Discrete Time Case). Academic Press, New York.
  2. 2.Puterman, M. (1994). Markov Decision Processes — Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY.
  3. 3.Bertsekas, D. P. (2007a). Dynamic Programming and Optimal Control, volume 1. Athena Scientific, Belmont, MA, 3 edition.
  4. 4.Bertsekas, D. P. (2007b). Dynamic Programming and Optimal Control, volume 2. Athena Scientific, Belmont, MA, 3 edition.
  5. 5.仅当 $U$​​ 为博雷尔可测(Borel-measurable)集时,$\mathcal{P}_0(U\mid x,a)$​​ 有定义。博雷尔可测性是一个技术概念,其目的是为了杜绝一些病态。$\mathcal{X}\times\Bbb{R}$​​ 的博雷尔可测子集的集合实际上包括了 $\mathcal{X}\times\Bbb{R}$​​ 的所有「有趣」的子集。特别地,它们包括了形式为 ${x}\times[a, b]$​​ 的子集,以及可以通过取其补集或以递归方式取此类集合的至多可数集合的并集(交集)而从此类子集获得的子集。
  6. 6.「几乎必然(almost surely)」与「以概率一(with probability one)」意思相同,用来指这样的一个事实:有关陈述在概率空间中的所有地方都成立,除了一组测度为0的事件外。
  7. 7.数学上,一个行为是一个概率核 $\pi_0,\pi_1,\dots,\pi_t,\dots,$ 的有限序列,这里 $\pi_t$ 将长度为 $t$ 的历史映射到动作空间 $\mathcal{A}$ 上的概率分布:$\pi_t = \pi_t(\cdot\mid x_0,a_0,r_0,\dots,x_{t-1},a_{t-1}.r_{t-1},x_t)$。