第四章：序列决策问题

笔记整理

4.1 问题的形式化描述

4.1.1 马尔可夫决策过程（MDP）

马尔可夫决策过程（Markov Decision Process, MDP）是序贯决策问题的标准数学框架。在MDP中，智能体在时刻$t$基于观察到的状态$s_t$选择动作$a_t$，然后获得奖励$r_t$。状态的转移遵循马尔可夫假设，即下一状态仅依赖于当前状态和当前动作，而与之前的历史无关。

MDP可以由决策网络表示（见原书图4.1a）。信息边从$A_{0:t-1}$和$S_{0:t}$指向$A_t$，效用函数被分解为奖励$R_{0:t}$。

注（注释）：马尔可夫假设是MDP的核心假设，它大大简化了问题的复杂度。如果这一假设不成立，我们需要使用更复杂的模型，如部分可观测马尔可夫决策过程（POMDP），这将在下一章讨论。

本书主要关注平稳MDP（Stationary MDP），其中转移概率$P(S_{t+1}|S_t, A_t)$和奖励分布$P(R_t|A_t, S_t)$不随时间变化。平稳MDP可以用动态决策图紧凑表示（见原书图4.1b）。状态转移函数$T(s'|s, a)$表示在状态$s$下执行动作$a$后转移到状态$s'$的概率。奖励函数$R(s, a)$表示在状态$s$执行动作$a$的期望奖励。

飞机碰撞规避问题示例：飞机的碰撞规避问题可以形式化为MDP。状态表示本机与入侵飞机的位置和速度，动作表示爬升、下降或保持高度。当与另一飞机发生碰撞时获得大的负奖励，当爬升或下降时获得小的负奖励。

4.1.2 效用与奖励

MDP中的奖励被处理为加性分解效用函数的组成部分。对于有限视野问题（$n$个决策），奖励序列$r_{0:n-1}$的效用为：

\[ U(r_{0:n-1}) = \sum_{t=0}^{n-1} r_t \tag{4.1} \]

注：这个简单的加性形式假设每个时间步的奖励可以直接相加。在某些应用中，可能需要使用其他效用函数形式，但加性形式在理论和实践上都更易处理。

对于无限视野问题（决策次数无界），奖励和可能变得无穷大。假设策略A每时间步获得奖励1，策略B每时间步获得奖励100。直观上，理性智能体应该偏好策略B，但两者的期望效用都是无穷大。

解决无限视野问题的两种方法：

折扣因子法：引入折扣系数$\gamma \in [0, 1)$，效用定义为：

\[ U = \sum_{t=0}^{\infty} \gamma^t r_t \tag{4.2} \]

注（注释）：折扣因子使得当前奖励比未来奖励更有价值，这一概念在经济学的现值计算中也很常见。当$0 \leq \gamma < 1$且奖励有限时，效用必定有限。$\gamma$接近1意味着智能体更有耐心，$\gamma$接近0意味着智能体更关注即时奖励。

平均奖励法：

\[ \lim_{n \to \infty} \frac{1}{n} \sum_{t=0}^{n-1} r_t \tag{4.3} \]

注：平均奖励法避免了折扣带来的"短视"问题，但对于比较不同策略不够敏感。本书主要关注无限视野折扣奖励优化。

4.2 动态规划

动态规划（Dynamic Programming, DP）是一种计算最优策略的计算技术。虽然本节聚焦于MDP的动态规划算法，但动态规划是一种通用技术，可应用于多种其他问题，例如计算斐波那契数列、寻找两个字符串的最长公共子序列、寻找隐马尔可夫模型的最可能状态序列等。

注（重要）：动态规划的核心思想是最优子结构和重叠子问题。最优子结构意味着最优解包含子问题的最优解；重叠子问题意味着在递归过程中会反复遇到相同的子问题。

4.2.1 策略与效用

策略（Policy）$\pi$在MDP中决定给定历史时选择什么动作。时刻$t$给定历史$h_t = (s_{0:t}, a_{0:t-1})$时选择的动作记为$\pi_t(h_t)$。

由于未来状态序列和奖励仅依赖于当前状态和动作（由条件独立性假设），我们可以将注意力限制在仅依赖当前状态的策略上，这类策略称为马氏策略（Markov Policy）。

对于无限视野且转移和奖励平稳的MDP，我们可以进一步限制为平稳策略（Stationary Policy）。平稳策略$\pi$在状态$s$下选择的动作记为$\pi(s)$，没有时间下标。

注（注释）：在有限视野问题中，可能需要根据剩余时间步数选择不同动作。例如，打篮球时，除非比赛只剩下几秒，否则不应该尝试半场投篮。

执行策略$\pi$从状态$s$开始的期望效用记为$U^\pi(s)$，在MDP语境下常称为价值函数（Value Function）。最优策略$\pi^*$满足：

\[ \pi^*(s) = \arg\max_\pi U^\pi(s) \quad \forall s \tag{4.4} \]

注：根据问题的不同，可能存在多个最优策略。

4.2.2 策略评估

策略评估（Policy Evaluation）是计算执行给定策略获得的期望效用。对于策略$\pi$，我们可以用动态规划评估其$t$步后的效用： - $U_0^\pi(s) = 0$（不执行策略） - $U_1^\pi(s) = R(s, \pi(s))$（执行一步）

假设已知执行$\pi$执行$t-1$步的效用，$t$步效用可递归计算为：

\[ U_t^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s'} T(s'|s, \pi(s)) U_{t-1}^\pi(s') \tag{4.5} \]

其中$\gamma$是折扣因子，若不需要折扣可设为1。

算法4.1 迭代策略评估展示了如何迭代计算策略的期望效用直到任意视野$n$。

对于无限视野折扣奖励：

\[ U^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s'} T(s'|s, \pi(s)) U^\pi(s') \tag{4.6} \]

注（注释）：我们可以用足够多次迭代使$U^\pi$任意精确，或者解$n$个线性方程组（$n$为状态数）。用矩阵形式表示：

\[ \mathbf{U}^\pi = \mathbf{R}^\pi + \gamma \mathbf{T}^\pi \mathbf{U}^\pi \tag{4.7} \]

其中$\mathbf{U}^\pi$和$\mathbf{R}^\pi$是效用和奖励向量，$\mathbf{T}^\pi$是状态转移概率矩阵。

解得：

\[ \mathbf{U}^\pi = (\mathbf{I} - \gamma \mathbf{T}^\pi)^{-1} \mathbf{R}^\pi \tag{4.10} \]

求解需要$O(n^3)$时间。

4.2.3 策略迭代

策略迭代（Policy Iteration）利用策略评估计算最优策略（算法4.2）： 1. 策略评估：给定当前策略$\pi_k$，计算$U^{\pi_k}$ 2. 策略改进：使用$U^{\pi_k}$计算新策略

算法在无法进一步改进时终止。由于每步都改进步骤且策略数量有限，算法必收敛到最优解。

注（注释）：策略迭代的一个变体是改进策略迭代（Modified Policy Iteration），它只用少量迭代近似$U^{\pi_k}$而不是精确计算。

4.2.4 价值迭代

价值迭代（Value Iteration，算法4.3）是策略迭代的替代方法因其简单易实现。

首先计算与视野$n$和无折扣相关的最优价值函数$U_n$。若$n=0$，则$U_0(s) = 0$对所有$s$成立。从这个基例递归计算：

\[ U_n(s) = \max_a \left[ R(s, a) + \sum_{s'} T(s'|s, a) U_{n-1}(s') \right] \tag{4.11} \]

对于折扣$\gamma$的无限视野问题，贝尔曼方程（Bellman Equation）给出最优策略的价值函数：

\[ U^*(s) = \max_a \left[ R(s, a) + \gamma \sum_{s'} T(s'|s, a) U^*(s') \right] \tag{4.12} \]

注（重要）：贝尔曼方程是动态规划的核心！它表达了最优价值函数必须满足的自洽关系。价值迭代通过迭代更新来近似$U^*$。

一旦知道$U^*$，可以通过以下公式提取最优策略：

\[ \pi(s) \leftarrow \arg\max_a \left[ R(s, a) + \gamma \sum_{s'} T(s'|s, a) U^*(s') \right] \tag{4.13} \]

价值迭代的实现细节： - $U_0$可以初始化为任意有界值（$|U_0(s)| < \infty$），常用对最优价值函数的猜测来加速收敛 - 常用终止条件是$\|U_k - U_{k-1}\| < \delta$，其中$\|\cdot\|$是最大范数$\|U\| = \max_s |U(s)|$，这个量称为贝尔曼残差（Bellman Residual） - 要保证$U^*$的估计在所有状态下都在$\varepsilon$范围内，应选择$\delta = \varepsilon(1-\gamma)/\gamma$ - 已知$\|U_k - U^*\| < \varepsilon$时，提取策略$\pi$的策略损失满足$\|U^\pi - U^*\| < 2\varepsilon\gamma/(1-\gamma)$

注（注释）：当$\gamma \to 1$时，终止阈值变小，收敛变慢。这是因为未来奖励的折扣越少，我们需要迭代更长时间才能看到可接受的视野。

4.2.5 网格世界示例

10×10网格世界问题用于说明价值迭代： - 每个单元格代表MDP的一个状态 - 动作：上、下、左、右（各方向概率0.7成功，0.1偏移到其他方向） - 撞墙成本为1 - 四个特殊单元格有奖励：$(8,9) = +10$、$(3,8) = +3$、$(5,4) = -5$、$(8,4) = -10$ - $(8,9)$和$(3,8)$是吸收状态

注（注释）：图4.2-4.4展示了价值迭代的收敛过程。随着迭代次数增加，奖励值向周围扩散。当$\gamma = 0.9$时，即使网格左侧单元格也有正值；当$\gamma = 0.5$时，+3和+10奖励的传播范围更小。不同折扣因子下$(4,8)$单元格的策略也不同。

4.2.6 异步价值迭代

异步价值迭代（Asynchronous Value Iteration）每轮迭代只更新部分状态。只要每个状态的价值函数被无限次更新，就能保证收敛到最优价值函数。

高斯-赛德尔价值迭代是一种异步价值迭代方法，按状态顺序扫描并就地更新价值函数：

\[ U(s) \leftarrow \max_a \left[ R(s, a) + \gamma \sum_{s'} T(s'|s, a) U(s') \right] \tag{4.14} \]

注（注释）：异步方法只需在内存中保存一份价值函数副本（而非两份），且根据状态排序可能比标准价值迭代收敛更快。

4.2.7 闭环规划与开环规划

闭环规划（Closed-loop Planning）考虑未来状态信息。动态规划算法属于此类，它们生成可随时间反应动作结果的反应式计划（或策略）。

开环规划（Open-loop Planning）不考虑未来状态信息。许多路径规划算法属于此类，只生成静态动作序列。

示例（图4.5）：9个状态，从$s_0$开始，两步决策（上或下）。从$s_0$向上的效果是随机的（$s_1$或$s_2$各0.5概率）。

开环计划只有4种：(上,上)、(上,下)、(下,上)、(下,下)。开环最优期望效用是20（选择下）。

闭环规划考虑可以根据第一次动作的结果选择第二次动作。如果从$s_0$向上，可以根据到达$s_1$或$s_2$选择下或上，保证获得30的奖励。

注（重要）：在动作效果不确定的序列问题中，闭环规划比开环规划有显著优势。然而，当状态空间很大时，闭环规划方法（如价值迭代）可能不可行。

4.3 结构化表示

前面动态规划算法假设状态空间是离散的。如果状态空间由$n$个二元变量决定，则离散状态数为$2^n$。这种指数增长限制了价值迭代和策略迭代只能应用于状态变量数量有限的问题。本节讨论利用问题结构解决高维问题的方法。

4.3.1 分解马尔可夫决策过程

分解MDP（Factored MDP）使用动态决策网络紧凑表示转移和奖励函数。动作、奖励和状态可以分解为多个节点。

决策树可用于紧凑表示条件概率分布和奖励函数。例如，图4.7展示了条件分布$P(G_{t+1}|D_t, F_t, G_t)$的表格形式和决策树形式。

决策图（Decision Diagram）比决策树更高效。在树中，除根节点外所有节点只有一个父节点，但决策图中的节点可以有多个父节点。图4.8展示了一个决策树及其等效决策图，决策图只需2个叶节点而非5个。

注（注释）：决策图通过共享子节点来节省空间，这是人工智能中常见的结构共享（Structure Sharing）技术。

4.3.2 结构化动态规划

存在多种寻找分解MDP策略的动态规划算法。结构化价值迭代和结构化策略迭代算法在决策树的叶节点上执行更新，而非所有状态上。这些算法通过聚合状态和利用奖励与价值函数的加性分解来提高效率。结果策略表示为决策树，内部节点对应状态变量测试，叶节点对应动作。

4.4 线性表示

前面方法假设问题是离散的。我们可以离散化连续问题，但当状态或动作空间很大时可能不可行。本节介绍为满足特定条件的连续状态和动作空间问题寻找精确最优策略的方法：

条件1：线性高斯动力学

状态转移函数形式为：

\[ T(z|s, a) = \mathcal{N}(z| T_s s + T_a a, \Sigma) \tag{4.15} \]

其中$T_s$和$T_a$是决定下一状态均值的矩阵，$\Sigma$是控制动力学噪声量的协方差矩阵。

条件2：二次奖励

奖励函数形式为：

\[ R(s, a) = s^\top R_s s + a^\top R_a a \tag{4.16} \]

其中$R_s = R_s^\top \leq 0$（负半定）且$R_a = R_a^\top < 0$（负定）。

注（注释）：线性高斯动力学和二次奖励的组合是控制理论中研究最充分的设置之一，称为线性二次调节器（Linear Quadratic Regulator, LQR）。当噪声为零时，就是标准的LQR问题。

连续空间贝尔曼方程：将求和替换为积分，$T(s'|s,a)$作为概率密度：

\[ U_n(s) = \max_a \left[ R(s, a) + \int T(z|s, a) U_{n-1}(z) dz \right] \tag{4.17} \]

可以证明$U_n(s)$可以写成$s^\top V_n s + q_n$形式。最终可推导出最优$n$步策略：

\[ \pi_n(s) = -(T_a^\top V_{n-1} T_a + R_a)^{-1} T_a^\top V_{n-1} T_s s \tag{4.27} \]

注（重要）：有趣的是，最优策略不依赖于噪声协方差$\Sigma$，尽管最优成本依赖于噪声。这是一个优雅的理论结果。

4.5 近似动态规划

近似动态规划（Approximate Dynamic Programming）关注为大型或连续空间问题寻找近似最优策略。该领域与强化学习有共同思想。在强化学习中，我们尝试在不知道模型的情况下快速获得尽可能多的奖励。

4.5.1 局部近似

局部近似（Local Approximation）基于相近状态有相近价值这一假设。如果我们知道有限状态集$s_{1:n}$的价值，可以用以下公式近似任意状态的价值：

\[ U(s) = \sum_{i=1}^n \lambda_i \beta_i(s) = \lambda^\top \beta(s) \tag{4.28} \]

其中$\beta_{1:n}$是权重函数（如核函数），满足$\sum_{i=1}^n \beta_i(s) = 1$。$\beta_i(s)$应对接近$s_i$的状态给予更大权重。

最近邻方法：将所有权重分配给最近的离散状态，产生分段常数价值函数。

k近邻：对$s$的$k$个最近离散状态各分配权重$1/k$。

线性插值：对于一维状态空间，$N(s) = \{s_1, s_2\}$时：

\[ U(s) = \lambda_1 \frac{s_2 - s}{s_2 - s_1} + \lambda_2 \frac{s - s_1}{s_2 - s_1} \tag{4.30} \]

注（注释）：这可以推广到$d$维状态空间，在$d$维中称为多线性插值（Multilinear Interpolation）。当维度高时，矩形单元格的$2^d$个顶点可能太多。单纯形插值（Simplex Interpolation）将矩形单元格分解为$d!$个单纯形（多维三角形），只需$d+1$个顶点，插值复杂度随维度线性而非指数增长。

4.5.2 全局近似

全局近似（Global Approximation）使用固定参数集$\lambda_{1:m}$在整个状态空间上近似价值函数。常用方法是基于线性回归：

\[ U(s) = \sum_{i=1}^m \lambda_i \beta_i(s) = \lambda^\top \beta(s) \tag{4.34} \]

注（注释）：与局部近似的区别是：$\lambda$不对应特定离散状态的价值，$\beta$函数不一定与距离度量相关，也不要求和为1。

算法4.5 线性回归价值迭代使用回归代替简单赋值：$\lambda \leftarrow \text{Regress}(\beta, s_{1:n}, u_{1:n})$。

回归目标是最小化平方误差和：

\[ \sum_{i=1}^n (\lambda^\top \beta(s_i) - u_i)^2 \tag{4.35} \]

注（图4.11说明）： - 线性插值在$s_{1:10}$处精确匹配目标值，但需要10个参数 - 线性回归（$\beta_1 = 1, \beta_2 = s$）用2个参数近似，效果较差 - 添加二次基函数$\beta_3 = s^2$和三次基函数$\beta_4 = s^3$可以逐步改善近似

注（注释）：基函数的选择很重要。过多基函数可能导致过拟合，在其他状态上表现不佳。基函数选择需要结合领域知识。

4.6 在线方法

前面方法都涉及在执行前离线计算整个状态空间的策略。虽然分解表示和价值函数近似可以帮助扩展到更高维状态空间，但计算和表示全状态空间策略可能仍然不可行。

在线方法（Online Methods）将计算限制在从当前状态可达的状态集。由于可达状态空间可能比全状态空间小几个数量级，在线方法可以显著减少选择最优（或近似最优）动作所需的存储和计算量。

4.6.1 前向搜索

前向搜索（Forward Search，算法4.6）是一种简单的在线动作选择方法，从初始状态$s_0$向前看直到某个视野（或深度）$d$。

注（注释）：算法对所有可能的动作和下一状态配对进行迭代，递归调用直到达到指定深度。计算复杂度为$O((|S| \times |A|)^d)$，是指数级的。

4.6.2 分支限界搜索

分支限界搜索（Branch and Bound Search，算法4.7）扩展了前向搜索，利用价值函数上下界知识剪枝搜索树的部分分支。

注（注释）：动作必须按上界降序迭代，这样才能有效剪枝。上下界越紧，剪枝效果越好，但最坏情况下复杂度不变。

4.6.3 稀疏采样

稀疏采样（Sparse Sampling，算法4.8）使用采样方法避免前向搜索和分支限界搜索的最坏情况指数复杂度。

稀疏采样使用生成模型$G$产生下一状态$s'$和奖励$r$的样本。优势在于通常更容易实现从复杂多维分布抽取随机样本的代码，而非显式表示概率。

注（注释）：运行时间复杂度$O((n \times |A|)^d)$仍然随视野指数增长，但不再依赖状态空间大小。$n$次采样代替遍历所有状态。

4.6.4 蒙特卡洛树搜索

蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）是近年来最成功的基于采样的在线方法之一。算法4.9是UCT（Upper Confidence Bounds for Trees）实现。

注（重要）：与稀疏采样不同，蒙特卡洛树搜索的复杂度不随视野指数增长。

算法三个阶段： 1. 搜索：如果当前状态在集合$T$中，进入搜索阶段。选择最大化以下值的动作： $$ Q(s, a) + c \sqrt{\frac{\log N(s)}{N(s, a)}} \tag{4.36} $$ 第二项是探索红利，鼓励选择尝试较少的动作。

扩展：到达不在$T$中的状态后，初始化所有动作的$N(s,a)$和$Q(s,a)$，将状态加入$T$。
** rollout**：根据 rollout 策略$\pi_0$选择动作直到达到指定深度（算法4.10）。

注（注释）：rollout 策略不必接近最优，但是专家偏置搜索到有前景区域的一种方式。可以携带之前步骤计算的$N(s,a)$和$Q(s,a)$值。

4.7 直接策略搜索

前面方法涉及计算或近似价值函数。替代方法是直接搜索策略空间。虽然状态空间可能高维使价值函数近似困难，但可能策略空间维度相对较低，更容易直接搜索。

4.7.1 目标函数

设策略由参数$\lambda$参数化。策略选择动作$a$给定状态$s$的概率为$\pi_\lambda(a|s)$。给定初始状态$s$，我们可以估计：

\[ U^{\pi_\lambda}(s) \approx \frac{1}{n} \sum_{i=1}^n u_i \tag{4.37} \]

其中$u_i$是策略$\pi_\lambda$到某深度的一次 rollout 的效用。

直接策略搜索的目标是找到最大化以下函数的参数$\lambda$：

\[ V(\lambda) = \sum_s b(s) U^{\pi_\lambda}(s) \tag{4.38} \]

其中$b(s)$是初始状态分布。我们可以使用蒙特卡洛模拟和生成模型$G$估计$V(\lambda)$（算法4.11）。

注（注释）：$V(\lambda)$是随机函数，相同输入可能产生不同输出。样本数$n$越大，输出变异性越小。

4.7.2 局部搜索方法

局部搜索（Local Search），又称爬山法或梯度上升，从搜索空间单点开始，逐步移动到邻近点直到收敛。假设价值函数在一点的值是到全局最优距离的指示，因此局部搜索通常选择价值最大的邻居。

注（注释）：局部搜索容易陷入局部最优和平坦区域。模拟退火或其他方法可以帮助找到全局最优。

4.7.3 交叉熵方法

交叉熵方法（Cross Entropy Method）维护策略分布并根据表现好的策略更新分布。交叉熵是信息论概念，衡量两个分布的差异。对于离散分布：

\[ H(p, q) = -\sum_x p(x) \log q(x) \tag{4.39} \]

对于连续分布，求和替换为积分。

算法4.12 交叉熵策略搜索过程： 1. 从$P(\lambda|\theta)$抽取$n$个样本，评估表现 2. 按表现降序排列，选前$m$个精英样本 3. 用精英样本更新$\theta$

注（图4.12说明）：初始分布$\theta = (0, 10)$（均值0，标准差10），$n=20$，$m=5$。第一轮随机采样，然后逐步向更有前景的区域移动，最终找到全局最优。

4.7.4 进化方法

进化搜索方法（Evolutionary Methods）从生物进化获得灵感。常用方法是遗传算法（Genetic Algorithm），进化表示策略的（通常是二进制）字符串种群。

过程： 1. 从随机初始种群开始 2. 根据测量的适应度进行交叉和变异 3. 产生新一代 4. 重复直到找到满意解

遗传编程（Genetic Programming）进化表示策略的树结构，允许比固定长度位串更灵活的策略表示。

注（注释）：遗传算法可以与局部搜索结合使用，例如先用遗传算法找到atisfactory策略再用局部搜索改进。这种方法称为遗传局部搜索或文化算法（Memetic Algorithms）。

4.8 本章小结

马尔可夫决策过程使用转移函数和奖励函数表示序列决策问题
动态规划算法可以找到最优策略
具有线性高斯动力学和二次成本的连续问题可以解析求解
结构化动态规划可以高效求解分解MDP
大型或连续状态空间问题可以使用函数近似近似求解
在线方法在当前状态而非全状态空间上搜索最优动作
在某些问题中，使用随机优化方法直接搜索策略空间可能更容易

4.9 扩展阅读

Richard Bellman (1954) 开创了序列决策问题的研究
MDP标准框架相关书籍：Puterman (1994), Bertsekas (2007), Sutton & Barto (1998), Baier & Katoen (2008)
分解MDP的结构化价值迭代和策略迭代算法：Boutilier, Dearden, Goldszmidt (2000)
线性二次高斯（LQG）控制问题：Anderson & Moore (2007), Aström & Murray (2008), Bertsekas (2005)
近似动态规划：Powell (2007)
稀疏采样：Kearns, Mansour, Ng (1999)
蒙特卡洛树搜索：Kocsis & Szepesvári (2006)，成功应用于围棋
策略搜索的梯度方法：Williams (1992), Baxter & Bartlett (2000)
交叉熵方法：de Boer et al. (2005)
遗传算法：Holland (1975)，遗传编程：Koza (1992)