强化学习中的算法-译 3 价值函数

价值函数

在某 MDP 中找到最优行为的明显方法是列出所有的行为,然后找出对每个初始状态给出最高可能价值的行为。由于一般来说,有太多的行为,这个计划是不可行的。一个更好的方法是基于计算价值函数。在这种方法中,人们首先要计算所谓的最优价值函数,然后可以相对容易地确定一个最优行为。当过程从状态 $x$ 开始时,状态 $x\in \mathcal{X}$的最优值 $V^\ast(x)$ 给出了最高的可实现的期望回报。函数 $V^\ast:\mathcal{X}\to\Bbb{R}$ 称为最优价值函数(optimal value function)。一个在所有状态下都能达到最优值的行为就是最优的。确定性的平稳策略(Deterministic stationary policies)[1]代表了一类特殊的行为,正如我们即将看到的,它在 MDP 的理论中发挥着重要作用。它们被某个映射 $\pi$所规范,这些映射将状态映射到动作(即$\pi:\mathcal{X}→\mathcal{A}$)。遵循 $\pi$ 意味着,在任何时间 $t\geq 0$时,动作 $$A_t = \pi(X_t) \tag{6}$$。

更一般地说,一个随机的平稳策略(stochastic stationary policy 或只是平稳策略)$\pi$ 状态映射为动作空间的分布。当提到这样的策略 $\pi$ 时,我们将使用 $\pi(a\mid x)$ 来表示在状态 $x$ 中被 $\pi$ 选择的动作 $a$ 的概率。注意,如果在 MDP 中遵循一个固定的策略,即如果 $$A_t \sim \pi(\cdot \mid X_t), t\in \Bbb{N}$$, 状态过程 $(X_t ; t \geq 0)$ 将是一个(时齐的)马尔可夫链。我们将用 $\Pi_\text{stat}$ 来表示所有平稳策略的集合。为了简洁起见,在下文中,我们常常只说 「策略」而不是 「平稳策略」,希望这不会引起混淆。

平稳策略和 MDP 引入了所谓的马尔可夫奖励过程(Markov reward processes, MRP)。一个 MRP 是由一对 $\mathcal{M} = (\mathcal{X}, \mathcal{P}_0)$ 确定的,其中 $\mathcal{P}_0$ 给每个状态分配一个 $\mathcal{X} \times \Bbb{R}$ 上的概率度量。一个MRP $\mathcal{M}$ 会产生随机过程$((X_t , R_{t+1} ); t\geq 0)$,其中$(X_t , R_{t+1} )\sim \mathcal{P}_0(\cdot\mid X_t)$ 。(注意 $(Z_t ; t \geq 0),Z_ t = (X_ t , R_ t )$ 是一个时齐的马尔可夫过程,其中 $R_0$ 是一个任意的随机变量,而 $((X_t , R_{t+1} ); t\geq 0)$是一个二阶马尔可夫过程。) 给定一个平稳策略 $\pi$和 MDP $\mathcal{M} =\ (\mathcal{X},\mathcal{A} , \mathcal{P}_0)$,由 $\pi$ 和 $\mathcal{M}$ 引入的 MRP $(\mathcal{X},\mathcal{P}_0^\pi)$的转移核用 $\mathcal{P}_0^\pi (\cdot \mid x) = \sum_{a\in \mathcal{A}} \pi(a \mid x)\mathcal{P}_0( \cdot \mid x, a)$ 来定义。如果一个 MRP 的状态空间是有限的,那么它就被称为有限的。

现在让我们来确定平稳策略的价值函数[2]。为此,让我们选择某个策略 $\pi\in\Pi_\text{stat}$。$\pi$ 下的价值函数 $V^\pi : \mathcal{X} \to \Bbb{R}$,由 $$V^\pi(x)=\Bbb{E}[\sum_{t=0}^\infty\gamma^tR_{t+1}\mid X_0=x], x\in\mathcal{X}, \tag{7}$$ 来定义,其理解为:(i)过程 $(R_t ; t \geq 1)$ 是遵循策略 $\pi$ 时获得的过程 $(X_t,A_t,R_{t+1});t \geq 0)$ 的「奖励部分」;(ii) $X_0$ 是随机选择的,以便 $\Bbb{P}(X_0 = x)\gt 0$ 对所有状态 $x$ 成立。第二个条件使得(7)中的条件期望对每个状态都是确定的。 如果初始状态分布满足这个条件,它对数值的定义没有影响。

MRP 的价值函数也是这样定义的,用 $V$ 表示:

$$V(x)=\Bbb{E}[\sum_{t=0}^\infty \gamma^tR_{t+1}\mid X_0=x], x \in \mathcal{X}$$

定义 MDP 中策略 $\pi\in\Pi_\text{stat}$ 下的动作价值函数 $Q^\pi: \mathcal{X} \times \mathcal{A}\to \Bbb{R}$,也是很有用的:假设第一个动作 $A_0$ 是随机选择的,这样 $\Bbb{P} (A_0 = a) \gt 0$ 对所有 $a\in \mathcal{A}$ 都成立,而对于决策过程的后续阶段,动作是按照策略 $\pi$ 来选择的。让 $((X_t, A_t, R_{t+1}); t \geq 0)$ 成为所产生的随机过程,其中 $X_0$ 同 $V^\pi$ 的定义。那么,$$Q^\pi(x,a)=\Bbb{E}[\sum_{t=0}^\infty\gamma^t R_{t+1}\mid X_0=x, A_0=a], x\in \mathcal{X}, a\in \mathcal{A}$$ 与 $V^\ast(x)$ 类似,在状态-动作对 $(x,a)$ 处的最优动作值 $Q^\ast(x,a)$ 被定义为在过程从状态 $x$开始,并且选择的第一个动作是 $a$ 的约束条件下的最大预期回报。函数 $Q^\ast : \mathcal{X}\times\mathcal{A} \to \Bbb{R}$ 被称为最优动作价值函数(optimal action-value function)。

最优价值函数和最优动作价值函数的联系由下面的方程描述:

$$\begin{aligned}
V^\ast(x) &= \sup_{a\in \mathcal{A}} Q^\ast (x, a), & x\in \mathcal{X}, \\
Q^\ast(x,a) &= r(x,a) +\gamma\sum_{y \in \mathcal{X}} \mathcal{P}(x, a, y) V^\ast (y), & x \in \mathcal{X}, a \in \mathcal{A}
\end{aligned}$$

在这里所考虑的一类 MDP 中,总是存在一个最优的平稳策略:$$V^\ast(x) = \sup_{\pi \in \Pi_\text{stat}}V^\ast(x)$$。

事实上,任何满足等式 $$\sum_{a\in \mathcal{A}}\pi(a \mid x)Q^\ast(x, a) = V^\ast(x) \tag{8}$$ 的策略 $\pi \in \Pi_\text{stat}$ 同时地对所有状态 $x \in \mathcal{X}$ 最优。请注意,为了使(8)成立,$\pi(\cdot \mid x)$ 必须集中于使 $Q^\ast(x, \cdot)$ 最大化的动作集合。一般来说,给定某个动作价值函数 $Q: \mathcal{X}\times\mathcal{A} \to \Bbb{R}$,对于某个状态 $x$ 来说,使 $Q(x, \cdot )$最大化的动作被称为在状态 $x$ 中相对于 $Q$ 是贪婪(greedy)的。在所有状态下,只对 $Q$ 选择贪婪动作的策略,称为关于 $Q$ 是贪婪的。

因此,关于 $Q^\ast$ 的贪婪策略是最优的,也就是说,仅对 $Q^\ast$ 的了解就足以找到最优策略。同样地,知道 $V^\ast$、$r$和$\mathcal{P}$也有助于采取最优动作。

接下来的问题是如何找到 $V^\ast$ 或 $Q^\ast$。让我们从更简单的问题开始,即如何确定策略的价值函数:

事实1 确定性策略的贝尔曼方程(Bellman Equations for Deterministic Policies):

固定一个 MDP $\mathcal{M} = (\mathcal{X}, \mathcal{A}, \mathcal{P}_0)$,一个折扣因子 $\gamma$,以及一个确定性策略 $\pi \in \Pi_\text{stat}$。令 $r$ 为 $\mathcal{M}$ 的即时奖励函数。那么 $V^\ast$ 满足 $$V^\pi(x) = r(x, \pi(x))+\gamma\sum_{y \in \mathcal{X}}\mathcal{P}(x, \pi(x),y)V^\pi(y), x\in\mathcal{X} \tag{9}$$,这个方程组被称为 $V^\pi$ 的贝尔曼方程。定义 $\pi$ 下的贝尔曼算子 $T^\pi :\Bbb{R}^\mathcal{X} \to \Bbb{R}^\mathcal{X}$:

$$(T^\pi V)(x) = r(x, \pi(x))+\gamma\sum_{y \in \mathcal{X}}\mathcal{P}(x, \pi(x),y)V(y), x\in\mathcal{X} \tag{9}$$

借助 $T^\pi$,方程(9)可以写成紧凑的形式:

$$T^\pi V^\pi = V^\pi \tag{10}$$

请注意,这是一个 $V^\pi$ 中的线性方程组,$T^\pi$ 是一个仿射线性算子。如果 $0 < \gamma < 1$,那么 $T^\pi$ 是一个最大范数的压缩映射,并且不动点方程 $T^\pi V = V$ 有一个唯一的解。

当状态空间 $\mathcal{X}$ 是有限的,例如,它有 $D$ 个状态,$\Bbb{R}^\mathcal{X}$ 可以被标识为 $D$ 维欧几里得空间,$V\in \Bbb{R}^\mathcal{X}$ 可以被认为是一个 $D$ 维向量:$V\in \Bbb{R}^D$。有了这个标识,$T^\pi V$ 也可以写成 $r^\pi + \gamma P^\pi V$,其中 $r^\pi \in \Bbb{R}^D$ 和 $P^\pi \in \Bbb{R}^{D\times D}$ 分别为适当定义的向量和矩阵。在这种情况下,(10)可以写成以下形式

$$r^\pi+\gamma P^\pi V^\pi = V^\pi \tag{11}$$

上述事实在 MRP 中也成立,其中贝尔曼算子 $T^\pi :\Bbb{R}^\mathcal{X} \to \Bbb{R}^\mathcal{X}$ 被定义为

$$(TV)(x)=r(x)+\gamma \sum_{y\in\mathcal{X}}\mathcal{P}(x, y)V(y), x\in \mathcal{X}$$

我们知道,最优价值函数满足某个不动点方程:

事实2 贝尔曼最优方程(Bellman Optimality Equations)

$$V^\ast(x) = \sup_{a\in \mathcal{A}}\lbrace r(x,a)+\gamma\sum_{y\in \mathcal{X}}\mathcal{P}(x,a,y)V^\ast(y) \rbrace, x\in \mathcal{X} \tag{12}$$

定义贝尔曼最优算子 $T^\ast :\Bbb{R}^\mathcal{X} \to \Bbb{R}^\mathcal{X}$:

$$(T^\ast V)(x) = \sup_{a \in \mathcal{A}}\lbrace r(x, a)+\gamma\sum_{y \in \mathcal{X}}\mathcal{P}(x, a,y)V(y) \rbrace, x\in\mathcal{X} \tag{13}$$

注意到由于 $\sup$ 的出现这是一个非线性算子。借助 $T^\ast$,方程(12)可以写成紧凑的形式:

$$T^\ast V^\ast = V^\ast$$

如果 $0 < \gamma < 1$,那么 $T^\ast$ 是一个最大范数的压缩映射,并且不动点方程 $T^\ast V = V$ 有一个唯一的解。

为了尽量减少混乱,在下文中,我们将把 $(T^\pi V )(x)$ 这样的表达式写成 $T^\pi V(x)$,并理解为算子 $T^\pi$ 的应用要优先于点求值算子「$\cdot(x)$」的应用。

策略(或 MRP)下的动作价值函数和最佳动作价值函数也满足某个与前面类似的不动点方程:

事实3 贝尔曼算子和动作价值函数的不动点方程(Bellman Operators and Fixed-point Equations for Action-value Functions):

稍微滥用一下符号,将 $T^\pi: \Bbb{R}^{\mathcal{X}\times \mathcal{A}} \to \Bbb{R}^{\mathcal{X}\times \mathcal{A}}$ 和 $T^\ast: \Bbb{R}^{\mathcal{X}\times \mathcal{A}} \to \Bbb{R}^{\mathcal{X}\times \mathcal{A}}$ 定义如下:

$$ T^\pi Q(x, a) = r(x,a)+\gamma\sum_{y \in \mathcal{X}}\mathcal{P}(x,a,y)Q(y,\pi(y)), (x, a)\in\mathcal{X}\times\mathcal{A}, \tag{14}$$

$$T^\ast Q(x, a) = r(x,a)+\gamma\sum_{y \in \mathcal{X}}\mathcal{P}(x,a,y)\sup_{a^\prime \in \mathcal{A}}Q(y,a^\prime), (x, a)\in\mathcal{X}\times\mathcal{A} \tag{15}$$

请注意,$T^\pi$ 又是仿射线性的,而 $T^\ast$ 是非线性的。算子 $T^\pi$ 和 $T^\ast$ 是最大范数的压缩映射。此外,$\pi$ 的动作价值函数 $Q^\pi$ 满足 $T^\pi Q^\pi = Q^\pi$,$Q^\pi$ 是这个不动点方程的唯一解。同样地,最优动作价值函数 $Q^\ast$ ,满足 $T^\ast Q^\ast= Q^\ast$,$Q^\ast$是这个不动点方程的唯一解。

解决 MDP 的动态规划算法

上述事实为价值迭代和策略迭代算法提供了基础。价值迭代产生了一连串的价值函数 $$V_{k+1} = T^\ast V_k, k\geq 0$$,其中 $V_0$ 是任意的。由于巴拿赫不动点(Banach’s fixed-point)定理,$(V_k;k\geq0)$ 以几何速度收敛到 $V^\ast$。

价值迭代也可以与动作价值函数一起使用;在这种情况下,它的形式为 $$Q_{k+1}=T^\ast Q_k, k\geq 0$$,再次以几何速度收敛到 $Q^\ast$。我们的想法是,一旦 $V_k$(或 $Q_k$)接近于 $V^\ast$(或 $Q^\ast$),对 $V_k$(或 $Q_k$)来说是贪婪的策略就会接近最优。特别是,下面的约束已知是成立的:固定一个动作价值函数 $Q$,让 $\pi$ 是一个相对于 $Q$ 的贪婪策略,那么策略 $π$ 的价值可以有如下下限(例如,Singh和Yee[3],1994,Corollary 2):

$$V^\pi(x)\geq V^\ast(x)-\frac{2}{1-\gamma}\lVert Q-Q^\ast \rVert_\infty, x\in \mathcal{X} \tag{16}$$

策略迭代(policy iteration)的工作方式如下。固定一个任意的初始策略 $\pi_0$ 。在迭代 $k>0$ 时,计算 $\pi_k$ 下的动作价值函数(这被称为策略评估步骤)。接下来,给定 $Q^{\pi_k}$,将 $\pi_{k+1}$ 定义为相对于 $Q^{\pi_k}$ 而言是贪婪的策略(这被称为策略改进步骤)。经过 $k$ 次迭代后,如果两个程序以相同的初始价值函数开始,策略迭代给出的策略不比对价值迭代的 $k$ 次迭代计算的贪婪策略差。然而,策略迭代中的一个步骤的计算成本要比价值迭代中的一个更新的计算成本高得多(因为有策略评估步骤)。


  1. 1.stationary policy,笔者这里译作平稳策略。一个平稳策略 $\pi_t$​​​​,不随时间改变,也就是,$\pi_t=\pi,\forall t \geq 0$​​​​,这里 $\pi$​​​​ 即可以是一个函数,$\pi:\mathcal{X}\to\mathcal{A}$​​​​(确定性策略),也可以是一个条件密度 $\pi(a\mid x)$​​​​(随机策略)。一个非平稳策略是不平稳的,更精确地说,对于 $i \neq j \geq 0$​​​​,$\pi_j$​​​​ 未必等于 $\pi_i$​​​​,这里 $i,j$​​​​ 代表两个不同的时间步。——笔者注
  2. 2.价值函数也可以被定义在任何行为下,类似于下面的定义。
  3. 3.Singh, S. P. and Yee, R. C. (1994). An upper bound on the loss from approximate optimalvalue functions. Machine Learning, 16(3):227–233.