第 7 章：合作决策（Cooperative Decision Making）

章节作者：Christopher Amato 章节定位：理论篇第七章。前 6 章都在"单智能体"框架下展开——第 4 章讨论序贯决策（MDP），第 5 章引入模型不确定性（POMDP）。本章放宽"单智能体"假设，讨论多智能体协作下的合作决策问题。本章围绕"分散部分可观测 Markov 决策过程"（Dec-POMDP）展开：7.1 节给出形式化定义与示例问题，7.2 节讨论它与 POMDP 的差异、复杂度与广义信念状态，7.3 节讨论几类重要的子类（Dec-MDP、ND-POMDP、MMDP），7.4 节给出精确求解方法（动态规划、启发搜索、策略迭代），7.5 节给出近似方法（MBDP、JESP），7.6 节讨论通信对复杂度与策略的影响。从结构上看，本章是第 4–6 章"单智能体序贯决策"主题在多智能体情境下的对偶——把"一个智能体的信念"扩展为"多个智能体各自的局部观测历史"，把"信念 MDP"扩展为"广义信念空间上的合作博弈"。

7.1 Formulation

多智能体系统可以用 MDP/POMDP 在集中方式下建模——要求所有智能体的信息和决策在每一步都被集中处理。但许多问题要求"分散执行"（decentralized execution）：每个智能体只能基于自己局部的观测做决策，而系统的动力学与目标函数则依赖于所有智能体的联合动作。Dec-POMDP 是 MDP/POMDP 的扩展，为每个智能体提供分散策略：系统动力学与奖励依赖于所有智能体的动作，但每个智能体必须基于局部信息做决策。本节先给出形式化定义，再讨论一个示例问题，最后给出两种策略表示方式。

7.1.1 Decentralized POMDPs

Dec-POMDP 由以下要素定义：\(\mathcal{I}\)——有限个智能体集合；\(\mathcal{S}\)——有限状态集，附指定初始状态分布 \(b_0\)；\(\mathcal{A}_i\)——智能体 \(i\) 的有限动作集；\(T\)——转移概率函数 \(T(s' \mid s, a)\)，给出在状态 \(s\) 下、智能体采取联合动作 \(a\) 后转移到状态 \(s'\) 的概率；\(R\)——奖励函数 \(R(s, a)\)，给出处于状态 \(s\) 并采取联合动作 \(a\) 时的立即奖励；\(\Omega_i\)——智能体 \(i\) 的有限观测集；\(O\)——观测模型 \(O(o \mid s', a)\)，给出在转移到状态 \(s'\) 且执行动作 \(a\) 后观察到 \(o\) 的概率。

如图 7.1 所示，Dec-POMDP 涉及多个智能体，它们在不确定性下基于不同的观测流运行。与 MDP 或 POMDP 一样，Dec-POMDP 在有限或无限的步骤序列上演进。在每一步，每个智能体仅基于其局部观测选择动作，由此为整个智能体集合产生一个立即奖励，并为每个智能体各自产生一个观测。由于状态不能被直接观测，对每个智能体而言，记住自己的观测历史是有益的。与 POMDP 不同的是，在 Dec-POMDP 中，通常不可能由单个智能体的观测历史计算出系统状态的估计（即信念状态）——这一点将在 7.2.1 节中详细讨论。

联合策略（joint policy）是问题中每个智能体各自策略的集合。智能体 \(i\) 的局部策略是从局部观测历史到动作的映射。Dec-POMDP 的目标是找到使期望效用最大化的联合策略。与 MDP 和 POMDP 一样，效用可以按不同方式定义，例如有限时域的奖励之和或无限时域的折扣奖励之和（4.1.2 节）。Dec-POMDP 形式化的一种推广是为不同智能体指定各自的奖励函数：如果智能体要最大化自己累积的奖励，问题就变成部分可观测随机博弈（POSG），需要博弈论的处理（类似于 3.3 节中介绍的单步决策），分析起来显著更难。

7.1.2 Example Problem

可以用 Dec-POMDP 建模的一类领域是机器人导航与探索问题。图 7.2 给出一个简单的网格化机器人导航问题。问题中的状态对应两个机器人各自的位置；动作为上、下、左、右、原地不动；移动动作以 0.6 的概率将智能体按期望方向移动一格，或以各 0.1 的概率向另外三个方向之一移动或留在原地。撞墙的动作使机器人保持原地。选择原地动作则总是使智能体停留在当前位置。假设智能体能完美观测紧邻自身的网格单元（如图中灰线所示），因此每个机器人可以观测到周围方格的墙配置，但观测不到自己的实际位置。目标是让智能体尽快相遇：当两个智能体占据同一格时获得奖励 1，否则奖励为 0，初始状态如图所示。

这个问题中存在三类不确定性：动作结果的不确定性（如同 MDP）、传感器信息的不确定性（如同 POMDP）、以及关于其他智能体信息的不确定性。尽管智能体能观测到周围网格单元并缩小自身可能位置的集合，观测通常不提供关于其他智能体的选择或位置的信息。因此，最优算法在生成解时通常会考虑其他智能体的所有可能选择和位置。如后文所述，POMDP 中使用的集中信念状态在 Dec-POMDP 中已不可能，因此求解变得困难得多。该问题的一种解法是让每个智能体向中心位置移动；若看不到另一智能体，则继续向该智能体可能所在的某些位置移动；若仍然看不到，则智能体可移动到求解过程中约定的位置并等待另一智能体到达。求解方法将产生"在看到不同观测历史后智能体应执行何种移动"的策略，并在不确定性下对这些选择进行优化。

7.1.3 Solution Representations

对于有限时域问题，局部策略可以用策略树（policy tree）表示。图 7.3 给出一个示例。这种树类似于 POMDP 的策略树，但每个智能体拥有自己独立的、与其他智能体无关的树。为使其更具体，考虑上述示例问题在 \(2 \times 2\) 无障碍网格上的简化版本：智能体 1 从右上角出发，智能体 2 从左下角出发；动作用箭头或停止符号 \(\cdot\) 表示（每个智能体可按给定方向移动或原地不动）；观测标记为"wl"（左侧有墙）和"wr"（右侧有墙）。在这种表示中，智能体在根节点处执行所定义的动作，然后根据观测选择由相应分支定义的下一动作，这一过程持续到叶节点处的动作为止。例如智能体 1 首先向左移动，若看到右侧有墙，则再次向左移动；若现在看到左侧有墙，则在最后一步不移动。策略树记录了智能体在某个固定时域内的整个局部历史。由于每棵树都独立于其他树，策略可以以分散方式执行，所得策略允许智能体以高概率快速在左上角相遇。

树的求值方法是把每一步的奖励按转移到给定状态、观察到给定观测集合的似然加权求和。对于一组智能体，从状态 \(s\) 出发时树 \(q\) 的值由下式递推给出：

\[ U(q, s) = R(a_q, s) + \sum_{s', o} P(s' \mid a_q, s) \, P(o \mid a_q, s') \, U(q_o, s') \]

其中 \(a_q\) 是树 \(q\) 的根节点所定义的动作，\(q_o\) 是在看到观测 \(o\) 后访问的 \(q\) 的子树。

尽管这种表示对有限时域问题很有用，无限时域问题却要求无限高度的树。另一种做法是把动作选择条件化在某个内部记忆状态上。这些解可以表示为一组局部有限状态控制器（finite-state controllers），如图 7.4 所示。这些控制器类似于 POMDP 所用的控制器，只是每个智能体拥有自己独立的控制器。控制器的运行方式与策略树类似：有一个指定的初始节点，在该节点选择动作后，控制器根据观测转移到下一节点，这一过程在问题的无限步内循环。也可以考虑随机控制器，它以随机方式选择动作与转移，因为它们能在节点数相同的条件下产生比确定性控制器更高质量的解。在本章中，控制器状态（controller state）称为节点（node），以与系统状态（system state）相区分。

图 7.4 给出了该 \(2 \times 2\) 示例问题的两节点随机控制器示例。智能体 2 从节点 1 出发，以 0.89 的概率向上移动，以 0.11 的概率原地不动。若智能体原地不动且下一步观测到左侧有墙（"wl"），则控制器将转移回节点 1，智能体再次使用相同的动作分布；若观测到右侧有墙（"wr"），则控制器以 0.85 的概率转移回节点 1、以 0.15 的概率转移到节点 2 执行下一步动作。所得策略同样使智能体在左上角以高概率快速相遇。有限状态控制器允许用紧凑方式表示无限时域策略——只记忆智能体历史的某些方面，而非完整局部历史。

联合策略的求值可以从初始节点出发，根据所执行的动作和所看到的观测在控制器中转移。智能体 \(i\) 在节点 \(q_i\) 执行动作 \(a_i\) 的概率记为 \(P(a_i \mid q_i)\)；控制器在当前节点 \(q_i\)、执行动作 \(a_i\)、观察到 \(o_i\) 时转移到节点 \(q_i'\) 的概率记为 \(P(q_i' \mid q_i, a_i, o_i)\)。在每个智能体 \(i\) 各自的动作选择与节点转移概率下，从节点 \(q\) 和状态 \(s\) 出发时的值由下列 Bellman 方程给出：

\[ U(q, s) = \sum_a \prod_i P(a_i \mid q_i) \left[ R(s, a) + \gamma \sum_{s', o, q'} P(s' \mid a, s) \, O(o \mid s', a) \prod_j P(q_j' \mid q_j, a_j, o_j) \, U(q', s') \right] \]

注意，这些值（无论是树还是控制器的）都可以离线计算，以确定每个智能体的策略，然后在线以分散方式执行。事实上，如下文所述，许多算法考虑的正是这种"离线规划"情景：解（树或控制器）以集中方式离线生成，策略以分散方式在线执行。

7.2 Properties

Dec-POMDP 的分散性质使其与 POMDP 在根本上不同。本节解释这些差异中的一部分，讨论一般 Dec-POMDP 模型的复杂度，并描述信念状态概念向多智能体问题的推广。

7.2.1 Differences with POMDPs

在 Dec-POMDP 中，每个智能体的决策影响域中的所有智能体，但由于模型的分散性质，每个智能体只能基于局部信息选择动作。由于每个智能体收到的观测通常并不足以高效地推理其他智能体，最优求解变得困难。每个智能体可能收到不同的信息片段，无法得到一个公共的状态估计，也无法计算其他智能体决策的估计。例如在图 7.2 的机器人导航示例中，尽管每个智能体知道另一智能体的初始位置，但智能体 1 的观测（直到与智能体 2 相邻之前）并不提供关于智能体 2 的动作选择或位置的信息。因此，虽然可能限制另一智能体可能位于的位置（例如不在相邻网格内的那些位置），但通常不可能生成系统状态的估计。例外情况是观测提供了这些信息（例如看到了另一智能体）或其他智能体的策略已知（后文将讨论）。

在单智能体问题中，状态估计至关重要，因为它允许把智能体的历史简洁地总结为信念状态，但在 Dec-POMDP 中通常不可用。状态估计的缺失（从而缺乏简洁充分统计量）要求智能体记住整个动作与观测历史才能最优地行动；因此 Dec-POMDP 无法被转化为信念状态 MDP，我们必须使用一套不同的工具来求解。

7.2.2 Dec-POMDP Complexity

Dec-POMDP 与 POMDP 的差异在有限时域问题的复杂度上明显体现出来：至少有两个智能体的 Dec-POMDP 是 NEXP-完全问题，属于在实践中可能需要双指数时间的复杂度类别。这与 MDP（P-完全）和 POMDP（PSPACE-完全）形成对比。与无限时域 POMDP 一样，最优求解无限时域 Dec-POMDP 是不可判定的（因为可能需要无限资源——无限大小的控制器），但可以在有限时间与有限内存下找到 \(\varepsilon\)-最优解。这些复杂度差异表明，引入多个分散智能体使 Dec-POMDP 显著难于 POMDP。这种复杂度的直观解释是：智能体除了要考虑状态和动作的不确定性外，还必须考虑所有其他智能体的可能选择，才能产生最优策略。

7.2.3 Generalized Belief States

如上所述，从智能体的视角看，不仅存在关于状态的不确定性，还可能存在关于其他智能体策略的不确定性。如果把其他智能体的可能策略视为系统状态的一部分，则可以形成"广义信念状态"（generalized belief state，有时称为多智能体信念状态）。智能体还可以考虑广义信念空间（generalized belief space），它包括系统状态与其他智能体策略之上的所有可能分布。在两智能体情形下，智能体的策略 \(p\) 在给定广义信念状态 \(b_G\) 处的值为：

\[ U(p, b_G) = \sum_{q, s} b_G(s, q) \, U(p, q, s) \]

其中 \(q\) 代表另一智能体的策略。如果所有其他智能体的策略已知，则广义信念状态与 POMDP 信念状态相同，可以把 Dec-POMDP 中剩余智能体的问题当作 POMDP 求解（其他智能体可视为环境的一部分）。不幸的是，求解 Dec-POMDP 时，其他智能体策略的概率分布通常未知。因此，广义信念状态通常不能计算。尽管如此，"其他智能体的可能策略"以及"广义信念空间"的思想仍可用于决策过程。

7.3 Notable Subclasses

由于 Dec-POMDP 的最坏情况复杂度很高，研究者探索了许多 Dec-POMDP 子类，它们在理论上或实践中可能更易处理。本节讨论其中几种，包括 Dec-MDP、网络分布式 POMDP（ND-POMDP）以及多智能体 MDP（MMDP）。Dec-POMDP、POSG、POMDP、MDP 与 Dec-MDP 之间的关系如图 7.5 所示。

7.3.1 Dec-MDPs

分散 Markov 决策过程（Dec-MDP）是具有"联合完全可观测性"的 Dec-POMDP：即把所有智能体的观测合在一起，环境状态可被精确获知。Dec-MDP 的一个常见例子是：状态由若干机器人的位置组成，每个智能体能完美观测自己的位置；因此把所有这些观测合起来，所有机器人的位置就已知。注意（或许有违直觉），Dec-MDP 中每个智能体的观测通常仍是有噪声的状态指示器。Dec-MDP 的复杂度与 Dec-POMDP 相同——虽然真实状态在观测共享时已知，但这种共享并不会发生。

现在讨论 Dec-MDP 情境下的"因子化"（factorization），但类似的因子化在完整的 Dec-POMDP 中也可以做。因子化 \(n\) 智能体 Dec-MDP 是一种 Dec-MDP，其世界状态可被分解为 \(n+1\) 个分量，\(\mathcal{S} = \mathcal{S}_0 \times \mathcal{S}_1 \times \cdots \times \mathcal{S}_n\)。\(\mathcal{S}_i\) 中的状态是与智能体 \(i\) 相关联的局部状态。\(\mathcal{S}_0\) 分量是环境的属性，不受任何智能体动作的影响（有时可省略）。例如 \(\mathcal{S}_0\) 可以是目标跟踪场景中目标的位置；类似地，智能体的局部状态 \(\mathcal{S}_i\) 可以是它在网格中的位置。若每个智能体能完整观测自己的状态分量，则该因子化 \(n\) 智能体 Dec-MDP 称为"局部完全可观测"（locally fully observable）。

若状态转移概率按如下方式因子化，则因子化 \(n\) 智能体 Dec-MDP 称为"转移独立"（transition independent）：

\[ T(s' \mid s, a) = T_0(s_0' \mid s_0) \prod_i T_i(s_i' \mid s_i, a_i) \]

其中 \(T_i(s_i' \mid s_i, a_i)\) 是智能体 \(i\) 在执行动作 \(a_i\) 后从局部状态 \(s_i\) 转移到 \(s_i'\) 的概率。不受影响的转移概率记为 \(T_0(s_0' \mid s_0)\)。如果机器人从不相互影响（即它们移动时不会相撞且可以共享同一网格），则机器人导航问题是转移独立的。

若观测概率按如下方式因子化，则因子化 \(n\) 智能体 Dec-MDP 称为"观测独立"（observation independent）：

\[ O(o \mid s, a) = \prod_i O_i(o_i \mid s_i, a_i) \]

其中 \(O_i(o_i \mid s_i, a_i)\) 是智能体 \(i\) 在执行动作 \(a_i\) 后于状态 \(s_i\) 收到观测 \(o_i\) 的概率。如果导航问题中的机器人不能相互观测（由于在不同位置工作或缺乏传感器），则该问题变为观测独立。

若全局奖励可写为：

\[ R(s, a) = f(R_1(s_i, a_i), \ldots, R_n(s_i, a_i)) \]

其中 \(f\) 是某种单调非递减函数（在 \(x_i \leq x_i'\) 时 \(f(x_1, \ldots, x_i, \ldots, x_n) \leq f(x_1, \ldots, x_i', \ldots, x_n)\)），则该因子化 \(n\) 智能体 Dec-MDP 称为"奖励独立"（reward independent）。在此假设下，全局奖励的最大化等价于局部奖励的最大化。奖励独立模型中常使用可加性局部奖励：

\[ R(s, a) = R_0(s_0) + \sum_i R_i(s_i, a_i) \]

表 7.1 给出不同 Dec-MDP 子类的复杂度。最简单的情况是转移、观测与奖励均独立：此时问题可以分解为 \(n\) 个独立的 MDP，它们的解可以合并。当只有转移与观测独立时，问题变为 NP-完全。直观地看，NP-完全是因为其他智能体的策略不影响某智能体的状态（只影响在局部状态集合处取得的奖励）。因为独立转移和观测蕴含局部完全可观测性，智能体的观测历史不会提供关于自身状态的额外信息——它已经已知；类似地，智能体的观测历史也不会提供关于其他智能体状态的额外信息，因为它们独立。结果，最优策略变为从局部状态到动作的映射，而非从观测历史（或局部状态历史——因为局部状态在这种情况下是局部完全可观测的）到动作的映射。其他任何独立转移、独立观测与独立奖励的组合都不能降低问题复杂度，最坏情况下仍为 NEXP-完全。

7.3.2 ND-POMDPs

网络分布式 POMDP（ND-POMDP）是具有转移与观测独立以及特殊奖励结构的 Dec-POMDP。奖励结构由协调图（coordination graph）或超图（hypergraph）表示。超图是图的推广，其中边可以连接任意数量的节点。ND-POMDP 超图中的节点对应各个智能体，边对应奖励函数中智能体之间的交互。ND-POMDP 为超图中的每条边 \(j\) 关联一个奖励分量 \(R_j\)，它依赖于该边所连接的状态与动作分量。ND-POMDP 中的奖励函数只是与各边关联的奖励分量之和。这使得价值函数可以按相同方式因子化，求解方法可以利用这一额外结构。

图 7.6 给出具有五个智能体的 ND-POMDP 结构示例：存在三条超边——一条涉及智能体 1、2 和 3，一条涉及智能体 3 和 4，一条仅涉及智能体 5。奖励函数分解为 \(R_{123}(s_1, s_2, s_3, a_1, a_2, a_3) + R_{34}(s_3, s_4, a_3, a_4) + R_5(s_5, a_5)\)。ND-POMDP 的典型应用领域是传感器网络与目标跟踪问题。

ND-POMDP 模型与转移和观测独立的 Dec-MDP 模型类似，但 ND-POMDP 不作联合完全可观测假设：即使所有观测共享，世界的真实状态也可能未知。此外，即使有因子化的转移与观测，ND-POMDP 中的策略仍是观测历史到动作的映射，而不像转移与观测独立的 Dec-MDP 中是从局部状态到动作的映射。最坏情况复杂度与完整 Dec-POMDP 相同（NEXP-完全），但 ND-POMDP 的算法通常在智能体数量上更具可扩展性；可扩展性随着超图连接性降低而提升。

7.3.3 MMDPs

另一个值得注意的子类是多智能体 Markov 决策过程（MMDP）。在 MMDP 中，每个智能体能观测到真实状态，使问题完全可观测。因为每个智能体能观测到真实状态，MMDP 可以用多项式时间当作 MDP 求解（需要某种协调机制以保证策略彼此一致）。基于上述机器人导航问题的 MMDP 情形例子假设每个机器人在每一步都知道其他机器人的位置。MMDP、Dec-POMDP 与单智能体模型之间的关系如图 7.7 所示。

7.4 Exact Solution Methods

本节讨论有限时域问题的最优算法与无限时域问题的 \(\varepsilon\)-最优算法。有限时域方法可以通过使用足够大的时域来求解无限时域问题，使后续动作选择对整体值的贡献很小以达到任意 \(\varepsilon\)。POMDP 方法通常足够可扩展以产生这样的解，但 Dec-POMDP 方法不能。因此，针对 Dec-POMDP 的特定无限时域方法使用有限状态控制器作为策略表示。大多数求解方法假设问题以集中方式离线求解，以产生可以以分散方式在线执行的策略。这些方法在给定算法的适当协调机制下也可以以分散方式产生解。

7.4.1 Dynamic Programming

算法 7.1 是最优求解有限时域 Dec-POMDP 的动态规划算法。该方法自底向上、从最后一步到第一步为每个智能体构造一组树（记为 \(\pi\)）。在每一步，算法穷举地生成所有下一步策略，对它们求值，然后对每个智能体 \(i\) 依次剪除可证明次优的策略，直到没有更多树可移除为止。这种生成、求值与剪除的过程一直持续到期望时域 \(T\)。Dec-POMDP 中的动态规划与 POMDP 的值迭代方法类似，只是使用了广义信念状态，导致更复杂的剪除步骤。

所得树的集合将包含时域 \(T\) 与系统任意初始状态下的最优解。这是因为我们在每一步考虑了所有可能的树，并仅移除了那些无论其他智能体在该步选择什么策略都无用的树。这种保守的剪除确保我们可以安全地移除在给定时点次优的树。

用于判断树是否可被剪除的线性规划可表示如下：对智能体 \(i\) 给定的树 \(q_i\) 与变量 \(\varepsilon\) 和 \(x(q_{-i}, s)\)，在以下约束下最大化 \(\varepsilon\)：

\[ \sum_{q_{-i}, s} x(q_{-i}, s) \, U(\hat{q}_i, q_{-i}, s) + \varepsilon \leq \sum_{q_{-i}, s} x(q_{-i}, s) \, U(q_i, q_{-i}, s) \quad \forall \hat{q}_i \]

\[ \sum_{q_{-i}, s} x(q_{-i}, s) = 1, \quad x(q_{-i}, s) \geq 0 \quad \forall q_{-i}, s \]

该线性规划通过将智能体 \(i\) 的树 \(q_i\) 的价值与其他树 \(\hat{q}_i\) 的价值比较，判断其是否被支配。变量 \(x(q_{-i}, s)\) 是其他智能体的树与系统状态之上的一个分布（广义信念状态）。我们在确保代表广义信念状态的变量 \(x\) 仍为合法的概率分布的前提下最大化 \(\varepsilon\)，并测试是否存在某种其他智能体树与系统状态的分布使所有状态下价值都至少相等。无论系统状态与其他智能体策略如何，总存在至少同等价值的替代策略，因此若 \(\varepsilon\) 非正，树 \(q_i\) 可被剪除。

支配测试用于给定步长的树，确保我们考虑给定步长的所有可能策略，并移除那些无论其他智能体选择何种策略都无用的策略。若有策略被移除，由于（可能的策略空间缩小）广义信念空间缩小，可能有更多策略可被剪除。因此，我们可以持续对每个智能体测试被支配的策略，直到没有智能体能进一步剪除任何策略为止。算法 7.1 的第 7–11 行表明，只要任何智能体能够移除任何树，就对所有智能体继续进行剪除。

与 POMDP 的值迭代不同，必须保留策略树，因为已不可能从值函数恢复策略。即使在 POMDP 情形中采用单步前瞻，我们也必须计算选择动作后的信念状态。由于在 Dec-POMDP 情形中无法计算信念状态，且动作必须基于局部信息选择，最优值函数不足以生成 Dec-POMDP 策略。

7.4.2 Heuristic Search

我们可以从已知初始状态出发、自顶向下地构造策略树，而不是像动态规划方法那样自底向上构造。这就是多智能体 A（MAA）的做法，它是一种建立在启发搜索技术上的最优算法。搜索通过使用部分定义策略的上界（基于 POMDP 或 MDP 解）进行，并以最佳优先顺序选择要扩展的部分联合策略。然后添加动作，并找到该新部分联合策略的上界。再次选择最高价值的部分联合策略，并固定另一动作选择。这一过程持续到找到价值高于任何部分联合策略的完整定义联合策略为止。算法 7.2 概述了该方法。

我们可以自顶向下地增长联合策略，首先考虑每个智能体可以采取的可能动作以启动其策略。MAA* 考虑在每一步可以采取的所有可能动作组合，并构造一个搜索树，这些组合作为单独的搜索节点。最坏情况下，可以构造一棵包含每个智能体所有可能策略的搜索树，方法是考虑第一步的所有可能动作组合，然后考虑第二步针对每个观测的所有可能动作组合，依此类推。因为其中许多策略可能是次优的，所以更智能的做法是引入启发值来协助选择更优动作。

为协助选择更优动作，MAA 整合了"在部分策略执行后再执行给定步数"的启发值。也就是说，基于 A 启发搜索方法，可以从一组步长为 \(t\) 的树估计一组步长为 \(T\) 策略的价值：用公式 (7.1) 计算这些树到步长 \(t\) 的价值，再加上对继续到步长 \(T\) 的价值的某个启发估计。

更形式化地，把一组步长 \(t < T\) 的策略树 \(q\) 称为"部分策略"（partial policy），把一组策略 \(\Delta_{T-t}\) 称为"完成策略"（completion policy）。完成策略由在部分策略的每个叶（最后动作）上追加 \(T - t\) 个策略构成。给定部分策略与完成策略，可以在状态 \(s\) 处如下求值：

\[ U(\{q^t, \Delta_{T-t}\}, s) = U(q^t, s) + U(\Delta_{T-t} \mid q^t, s) \]

我们不必显式考虑要追加的完成策略，而可以估计一个完成策略将产生的价值。因此，可以给出部分策略在完整时域 \(T\) 下的估计价值 \(\hat{U}\) 为：

\[ \hat{U}(q^t, s) = U(q^t, s) + \hat{V}_{q^t, s}^{T-t} \]

其中 \(\hat{V}_{q^t, s}^{T-t}\) 是从状态 \(s\) 出发执行 \(q^t\) 后继续到时域 \(T\) 的价值的估计。

有许多方法可计算 \(\hat{V}_{q^t, s}^{T-t}\)，但为确保产生最优策略，要求估计价值至少与继续的最优价值一样高（\(\hat{V} \geq V^*\)）。MAA 通过放松问题假设来产生启发值，使用 MDP 或 POMDP 策略。\(V^*_{\text{POMDP}}(b)\) 可定义为从信念 \(b\) 出发的 POMDP 策略的最优价值（即所有智能体的所有观测都已知、且可以基于这些集中信息选择动作的集中式解）。类似地，\(V^*_{\text{MDP}}(s)\) 可定义为从状态 \(s\) 出发的 MDP 策略的最优价值（即假设问题状态可被所有智能体在剩余过程中看到的集中式策略）。可以证明 \(V^*_{\text{Dec-POMDP}} \leq V^*_{\text{POMDP}} \leq V^*_{\text{MDP}}\)，直观上成立，因为随着智能体可获得的信息增多，策略受到的约束减少。MAA 通过计算策略到其给定步长 \(t\) 的价值，然后假设从 \(q^t\) 的叶节点开始，信念状态（在 \(V^*_{\text{POMDP}}\) 情形）或状态（在 \(V^*_{\text{MDP}}\) 情形）此后对智能体已知，由此对部分策略求值。

MAA* 中的搜索然后选择增长具有最高启发值的部分策略。增长策略会在当前策略的叶之后为每个可能的观测追加动作。该搜索节点的扩展在每一步向搜索树添加指数级的节点。每个新策略接着被求值以产生更新的启发值。

最优联合策略的下界也被维护。若增长策略产生了一个时域 \(T\) 的策略，则该策略的价值与下界比较，若更高则更新下界。进而任何估计价值低于下界的部分策略都可被剪除——这种剪除之所以可行，是因为部分策略的估计价值是其真实价值的上界，表明它永远不会比产生下界的策略价值更高。搜索在不再有可扩展的部分策略时完成：此时一组 \(q^T\) 策略已经生成，其价值高于任何部分策略的启发价值。

现在更详细地描述算法 7.2。代表已知最佳联合策略价值的下界值 \(V\) 初始化为负无穷。代表可扩展部分策略的开放列表 \(L\) 初始化为智能体的所有联合动作。每一步选择具有最高估计价值 \(\hat{V}\) 的部分联合策略（搜索树中的一个节点）。然后扩展该部分策略，为该联合策略生成所有下一步策略（搜索树中所有子节点）。该集合称为 \(\Delta_0\)。时域 \(T\) 的完整联合策略集合现被汇总到 \(\Delta_T\)，每个都被求值，并选其中价值最高者 \(v\)。若该价值高于已知最佳完整策略的价值，则更新下界值与指向最佳策略的指针。开放列表中任何估计上界价值（使用 QMDP 或 QPOMDP 启发）低于 \(V\) 的部分策略也将被剪除。从扩展节点集合中移除完整树，并从开放列表中移除所选节点。然后将剩余扩展节点添加到开放列表。该算法持续到开放列表为空，返回最优联合策略 \(\pi^*\)。

图 7.8 给出该搜索的示例。每个搜索节点代表一个给定步长的联合策略。下标代表搜索节点的索引及其在搜索树中每个祖先节点的索引，上标代表联合策略的步长。带索引的祖先表示部分策略在适当时域被共享。注意 \(m\) 代表可能的下一步联合策略数，在 \(n\) 个智能体中为 \(|A_{\max}|^{n |\Omega_{\max}|}\)，其中 \(A_{\max}\)、\(\Omega_{\max}\) 为最大的动作与观测集合。可用的部分策略（开放列表）由树的叶表示，已经被扩展的节点显示为内部节点。

7.4.3 Policy Iteration

由于无限时域问题不可判定，可能无法产生具有精确最优价值的解。因此，方法侧重于产生在最优解 \(\varepsilon\) 范围内的解。

Dec-POMDP 的策略迭代方法与有限时域的动态规划算法类似，只是使用有限状态控制器作为策略表示（类似 POMDP 的策略迭代）。从每个智能体的初始控制器开始，每一步通过穷举备份产生每个智能体的任何可能下一步策略来添加节点。然后进行剪除，若智能体控制器中的节点对系统所有状态以及所有其他智能体的可能控制器，其价值都低于从另一节点开始的价值，则可移除该节点。这些穷举备份与剪除步骤持续到解可证明在最优解 \(\varepsilon\) 范围内为止。该算法可以在有限步数内产生 \(\varepsilon\)-最优策略。策略迭代的细节如下。

算法 7.3 给出策略迭代算法。输入为初始联合控制器 \(\pi_0\) 与参数 \(\varepsilon\)。在每一步，进行求值、备份与剪除。控制器使用公式 (7.2) 求值。然后执行穷举备份以添加节点到局部控制器。穷举备份一次为所有智能体添加节点到其局部控制器。与有限时域情形类似，对每个智能体 \(i\)，添加 \(|A_i| |Q_i| |\Omega_i|\) 个节点到局部控制器，对应每种单步策略。注意穷举备份的重复应用相当于在确定性策略空间中的暴力搜索。继续这些穷举备份将收敛到最优，但显然效率很低。

为提高算法效率，进行剪除。回想规划是离线进行的，所以每一步每个智能体的控制器已知，但智能体在执行时不会知道它们将处于各自控制器的哪个节点。因此，剪除必须在广义信念空间上完成（使用与有限时域动态规划类似的线性规划）。即，只有当存在某种节点组合在系统所有状态以及其他智能体控制器的所有节点下都具有更高价值时，才能剪除智能体控制器中的一个节点。若该条件成立，则到被移除节点的边被重定向到支配节点。由于一个节点可能由其他节点的分布所支配，所产生的转移可能是随机的而非确定性的。控制器被更新求值，剪除继续，直到没有智能体能移除任何节点。

与单智能体情形不同，不存在用于测试 \(\varepsilon\)-最优性收敛的 Bellman 残差。我们采用基于折扣率与至今迭代次数的更简单测试。设 \(|R_{\max}|\) 为 Dec-POMDP 中可能的最大立即奖励绝对值。若迭代 \(t\) 后满足 \(\gamma^{t+1} |R_{\max}| / (1 - \gamma) \leq \varepsilon\)，则算法终止。此时，由于折扣，步 \(t\) 之后任何策略的价值都小于 \(\varepsilon\)。

7.5 Approximate Solution Methods

本节讨论有限时域问题的近似动态规划方法与无限时域问题的固定大小控制器方法。本节中的算法不具有误差界。

7.5.1 Memory-Bounded Dynamic Programming

动态规划方法的主要局限是当时域增长时内存与时间需求的爆炸。这一爆炸发生在每一步需要生成与求值所有联合策略树（每个智能体的策略树集合）再执行剪除步骤时。近似动态规划技术可以通过在每一步为每个智能体保留固定数量的策略树（由称为 MaxTrees 的参数控制）来缓解此问题。这种方法称为有界内存动态规划（MBDP），在算法 7.4 中概述。

MBDP 通过使用启发式（在算法中记为 \(H\)）来为每个智能体自顶向下地选择策略到给定时域，从而把自顶向下（启发搜索）和自底向上（动态规划）方法融合。也就是说，动态规划照常进行，但在每次备份后，使用启发式生成 MaxTrees 个信念状态并自顶向下采样，直到达到当前动态规划步（在动态规划处于步 \(t\) 时为 \(T - t\)）。然后假设这些生成的信念状态对智能体已知，且只保留在这些信念状态下价值最高的树。在执行时，信念状态实际上不会对智能体已知，但希望使用此策略仍能产生高价值的分散策略。MBDP 以类似于传统动态规划的迭代方式进行。例如，在时域 \(T\) 的问题中，启发策略可用于前 \(T - 1\) 步，动态规划可对得到的信念找到最佳单步树（动作）。然后启发策略可用于前 \(T - 2\) 步，MaxTrees 单步树可通过动态规划构建到两步。这一过程持续到 MaxTrees 个时域 \(T\) 的树构造完毕为止。已使用的启发包括 MDP 策略与随机策略。

由于每一步只保留固定数量的树，结果是次优但更具可扩展性的算法。事实上，由于每一步保留的策略数受 MaxTrees 限制，MBDP 在时域上具有线性时间与空间复杂度。

7.5.2 Joint Equilibrium Search

作为 MBDP 类方法的替代，称为策略联合均衡搜索（JESP）的方法使用交替最优响应。JESP 如算法 7.5 所示：为所有智能体生成初始策略，然后固定除一个外的所有策略。剩下的智能体可以计算对固定策略的最优响应（局部最优）。该智能体的策略随即固定，下一个智能体计算最优响应。这一过程持续到没有任何智能体改变其策略为止。结果是仅局部最优的策略，但其价值可能很高。通过在策略生成中整合动态规划，JESP 可以变得更高效。注意，JESP 可被视为在表示为 Dec-POMDP 的合作博弈中寻找 Nash 均衡（如 3.3 节所讨论）。

7.6 Communication

通信可以用观测隐式表示，但更显式的通信表示也已发展出来。自由且瞬时的通信等价于集中化，因为所有智能体在每一步都能访问所有观测。当通信存在延迟或代价时，智能体必须推理通信的内容与时机。Dec-POMDP 模型在不同类型可观测性与通信下的复杂度类别如表 7.2 所示。

将一般 Dec-POMDP 模型显式扩展以包含通信的一种模型是"带通信的分散部分可观测 Markov 决策过程"（Dec-POMDP-Com）。Dec-POMDP-Com 是 Dec-POMDP，其中每个智能体可以在每一步发送一条消息。每一步的奖励是联合状态、联合动作与智能体所发消息集合的函数。

求解 Dec-POMDP-Com 的最优解与求解一般 Dec-POMDP 模型（NEXP-完全）的复杂度相同，可以采用类似的算法。可以证明，假设固定的通信代价，通信智能体自上次通信以来的历史所得的最优价值至少与其他可能消息集合一样高。因此，许多通信方法假设在通信中使用观测历史。许多方法假设通信决策由每个智能体独立做出，但也有一些模型假设智能体可以强制所有其他智能体发送其观测历史（从而可以计算 POMDP 信念状态）。

求解带通信的 Dec-POMDP 的一种自然方法是生成集中式（POMDP）计划，并在智能体收到的观测会导致其选择与集中式计划所规定动作不同的动作时进行通信。这种方法可视为智能体在执行前同意一个策略，并在智能体的局部观测发现该策略可被改进时进行通信。该方法不显式考虑通信代价或延迟，但可以限制通信发生的次数。

7.7 Summary

Dec-POMDP 可以表示带有动作结果不确定性、观测不确定性以及代价高昂、有损或无通信的合作多智能体问题。
与 MDP 和 POMDP 一样，Dec-POMDP 使用决策理论方法建模序贯问题——以概率表示不确定性、以价值表示结果。
与单智能体模型不同，每个智能体必须仅基于自己的观测历史做选择。
求解有限时域 Dec-POMDP 是 NEXP-完全的。
许多 Dec-POMDP 子类在理论上或实践中更高效。
已开发出能为有限与无限时域 Dec-POMDP 产生最优或 \(\varepsilon\)-最优解的算法。
也已开发出更具可扩展性的近似算法。
通信也可以被显式建模，以协助决定何时通信以及通信什么来提升性能。

7.8 Further Reading

Dec-POMDP 的一般综述以及更多算法与模型由 Seuken 与 Zilberstein [1]、Oliehoek [2]、Goldman 与 Zilberstein [3] 给出。一般 Dec-POMDP 的复杂度由 Bernstein 等 [4] 证明。与 Dec-POMDP 类似的模型是多智能体团队决策问题（MTDP）[5]。有限时域动态规划由 Hansen、Bernstein 与 Zilberstein [6] 给出，无限时域策略迭代由 Bernstein 等 [7] 描述。多智能体 A* 由 Szer、Charpillet 与 Zilberstein [8] 给出。

具有独立转移与观测的 Dec-MDP 最早由 Becker 等 [9] 讨论并求解。考虑有限转移依赖的、事件驱动交互的 Dec-MDP 也被讨论过 [10]。Allen 与 Zilberstein 讨论了多种不同建模假设及其导致的复杂度 [11]。ND-POMDP 由 Nair 等 [12] 首次提出，MMDP 由 Boutilier [13] 给出。近似有限时域算法 MBDP 与 JESP 分别由 Seuken 与 Zilberstein [14] 和 Nair 等 [15] 描述。无限时域近似算法可在文献 [16]–[18] 中找到。

Dec-POMDP-Com 模型由 Goldman 与 Zilberstein [3] 给出。把集中式策略用作通信基础的思想由 Roth、Simmons 与 Veloso [19] 描述。强制同步通信由 Nair 与 Tambe [20] 讨论。

最优有限时域算法已在若干方向上得到改进。剪除可在执行备份时使用以限制需考虑的子树 [21]。其他工作也压缩策略而非智能体历史，从而提高用于剪除的线性规划效率 [22]。MAA* 在多个方向上得到改进，包括纳入新启发与改进搜索 [23]–[25]。最近，两种用于生成更简洁充分统计量以进行离线规划的方法发展起来：证明状态与联合历史分布的充分性 [26]，以及使用可分散化策略把 Dec-POMDP 转化为 POMDP [27]。

近似算法也获得了进一步改进。许多方法改进了 MBDP，包括压缩观测 [28]、在联合策略树空间中使用分支定界搜索代替穷举备份 [29]，以及使用约束优化 [30] 和线性规划 [31] 来扩大每一步的树选择规模。已经发展出其他固定大小控制器方法，包括使用 Mealy 机作为控制器的替代表示以提高性能 [32]、使用期望最大化进行参数优化 [33]，以及使用更具结构的周期控制器与改进的搜索技术 [34]。

也已经开发出用于子类的算法。求解转移与观测独立 Dec-MDP 的算法是覆盖集方法 [9]。更多方法也被开发以更高效地求解独立转移与观测的 Dec-MDP，包括双线性规划算法 [35]、启发搜索与约束优化的混合 [36]，以及把问题改述为连续 MDP [37]。已经提出了求解 ND-POMDP 的最优与近似方法 [12]。其他 ND-POMDP 方法也已被开发，例如产生有界质量解的方法 [38] 以及使用有限状态控制器作为智能体策略的方法 [39]。

其他通信模型在文献 [3]、[5] 中被讨论。通信已在局部完全可观测且具有独立转移与观测的 Dec-MDP 情境下被研究。此类问题可建模为"以通信为代价接收其他智能体的局部状态"，并用一组启发式方法求解 [40]。短视通信（即智能体基于"通信可在当前步发生或永不发生"的假设决定是否通信）也已在许多情形下表现良好 [41]。其他已探索的通信类型包括随机延迟通信 [42] 以及 Dec-POMDP 在线规划中的通信 [43]。

因子化模型已在 Dec-POMDP 情境下被研究。一般因子化模型已被描述并求解 [44]。Witwicki 与 Durfee 总结了不同类型的因子化模型及其复杂度 [45]，并发展出改进算法 [46]、[47]。

总体而言，研究界已聚焦于与 Dec-POMDP 相似模型的规划方法，但也探索了一些学习方法。这些方法包括使用基于梯度的方法以改进策略的无模型强化学习方法 [48]、[49]，以及在 ND-POMDP 中使用通信学习解的方法 [50]。

也已经提出了用于一般 Dec-POMDP 的其他求解方法，包括用于 Dec-POMDP 的混合整数线性规划方法 [51] 和采样方法 [52]、[53]。

已研究了若干应用，包括太空探测车形式的多机器人协调 [54]、直升机飞行 [5] 与导航 [55]–[57]、分散队列的负载均衡 [58]、网络拥塞控制 [59]、多址广播信道 [60]、网络路由 [61]、传感器网络管理 [12]、目标跟踪 [12]、[62] 以及天气现象 [63]。

本章个人批注

第 7 章是这本书从"单智能体决策"过渡到"多智能体合作"的关键一章。在某种意义上，它是前 6 章在多智能体情境下的对偶：第 4 章的 MDP → 第 5 章的 POMDP（加入状态不确定性）→ 第 7 章的 Dec-POMDP（再加入分散性）；同时把"信念状态"扩展为"广义信念状态"，把"信念 MDP"扩展为"广义信念空间上的合作博弈"。

对我而言，最值得注意的几个点：

复杂度的阶跃。MDP 是 P-完全、POMDP 是 PSPACE-完全、Dec-POMDP 是 NEXP-完全。引入分散性后，复杂度从 PSPACE 直接跳到 NEXP，这比"加入状态不确定性"所造成的阶跃还要大。这说明"分散性 + 不确定性 + 合作"三者耦合之后，问题在结构上有了质的变化——智能体不仅要对世界的不确定性建模，还要对其他智能体的可能选择建模，这是"双重不确定性"的根源。
广义信念状态的概念性意义。在 POMDP 中，信念状态是状态上的一个分布，是观测历史的简洁充分统计量。在 Dec-POMDP 中，由于其他智能体的策略也未知，所以"状态"被扩展为"状态 + 其他智能体策略"的联合分布。这种扩展在概念上很优雅——但作者明确指出，这种分布"通常不可计算"。这恰恰是 Dec-POMDP 难解的核心：理论上存在的"最优统计量"在实践中往往无法获得。这一观点对方法论有指导意义——当我们遇到无法计算的"理想统计量"时，往往需要寻找某种"近似但可计算"的替代物（如 MBDP 中用启发采样得到的伪信念状态）。
离线规划 / 在线执行的模式。本章几乎所有算法都遵循"离线集中求解 + 在线分散执行"的模式。这与 POMDP 的范式一致，但有更深的含义：在 Dec-POMDP 中，"在线分散执行"是不可妥协的硬约束（因为每个智能体看不到全局），而"离线集中求解"则是为绕开这一硬约束而采取的妥协。这种"把计算集中化、把执行分散化"的两段式设计，是分布式 AI 系统的一种经典模式。
子类研究的工程意义。7.3 节的三类子类（Dec-MDP、ND-POMDP、MMDP）实际上代表了三种不同的"结构性放松"——联合完全可观测、转移与观测独立 + 超图奖励、完全可观测。每种放松都对应一种实际应用场景（机器人编队、传感器网络、共享态势感知）。这一思路给我一个启发：研究复杂问题时，与其尝试直接求解一般情形，不如识别出问题中的"结构性独立"或"局部可观测性"等可分离因素，把问题投影到某个更易处理的子类上。
通信作为"准集中化"机制。7.6 节关于通信的讨论让我想起分布式系统中的一个经典观点：通信不是免费的，但适当的通信可以让分散系统"接近"集中系统的性能。Dec-POMDP-Com 中通信消息集合作为奖励函数的自变量，使"通信决策"成为序贯决策的一部分——这是把通信建模为"一等公民"的方式，与把它建模为"自由副作用"形成对比。

与上下章的衔接（一段话）

本章在全书结构中处于"理论篇"向"应用篇"过渡的关键位置：前 6 章奠定了"单智能体序贯决策"的完整框架（MDP、POMDP、状态不确定性、模型不确定性），本章把这套框架扩展到多智能体合作情境；之后的第 8 章将进入"应用篇"，讨论这些模型在真实领域（航空、传感器网络等）中的部署。从作者的角度看，本章是"多智能体篇"的唯一一章——它必须同时承担"形式化扩展"（7.1–7.3）与"求解方法"（7.4–7.6）的双重任务；这种"一个章节、两个主题"的结构使得 7.4 节（精确方法）和 7.5 节（近似方法）的篇幅都比较大，但作者通过 7.2.2 节的复杂度对照表把"为什么需要这么多方法"的动机交代得比较清楚。作者把通信单独放在 7.6 节而非并入 7.1，是有意识的安排——通信既是模型扩展（Dec-POMDP-Com），又是求解策略（"集中规划 + 通信触发"），前者属于模型层，后者属于算法层；放在 7.6 既可在算法部分之后讨论通信对求解的影响，又为读者保留"通信本身是一种建模选择"的开放性。