Windowed A-K-MDP

# 窗口化A-K-MDP
来源：https://arxiv.org/html/2609.13676
项文洋 Frankie Cho  
单位：莫纳什大学  
所在地：澳大利亚墨尔本  
邮箱：[[email protected]](mailto:)

艾迪纳·查德斯 (Iadine Chades)  
单位：莫纳什大学  
所在地：澳大利亚墨尔本  
邮箱：[[email protected]](mailto:)

###### 摘要
马尔可夫决策过程（MDP）用于支持生物多样性保护中的决策制定，但其策略，即使在较小的状态空间中，也可能难以被保护管理者理解。K-MDP方法通过构建最多具有K个抽象状态的简化MDP来解决此问题。我们表明，先前提出的A-K-MDP算法依赖于使用二分搜索选择离散化除数，可能会跳过更优的抽象状态。为解决此问题，我们提出了窗口化A-K-MDP算法，该算法在声明的除数窗口内生成每个不同的可行分区，并评估候选分区，直到达到理想值损失（J=0）或耗尽候选集合。在33个K-MDP实例上，窗口化方法改进了25个，并保持了8个的结果不变。

## 1 引言
MDP已用于为生物多样性保护问题中的不确定性下的序贯决策提供信息。然而，即使对于状态空间较小的MDP策略，也可能难以被人类解释，从而无法为现场管理者提供指导。K-MDP算法已被提出，通过将原始MDP状态空间缩减为K个抽象状态来解决此问题。例如，原始的海獭和北方鲍鱼模型，具有819个状态和四个动作，被转化为一个十状态的A-K-MDP，其性能损失很小（值损失=2.8%）。在A-K-MDP中，动作/值抽象$\phi_{a_d^*}$将共享最优动作和离散化最优值的状态分组。其已发布的除数选择循环使用中点二分更新。在每次迭代中，更新方向由生成的抽象是否包含最多K个状态，即$N(d) \le K$来决定。然而，此条件在除数$d$上并非单调，因此二分搜索可能会跳过具有较低值损失的可行分区。相反，我们提出的窗口化A-K-MDP推导了诱导分区发生变化的精确值。在其完整分支中，它在围绕修正的二分锚点的固定区间内生成每个不同的可行分区，并进行评估，直到达到无值损失（J=0）或耗尽候选集。其保证仅限于该声明的区间和抽象族。与已发布的二分搜索程序相比，我们做出了三项贡献。首先，我们提供了一个反例，表明抽象状态的数量在$d$上并非单调，因此二分搜索可能会错过具有较低决策损失的可行分区。其次，在指定的除数窗口内，我们推导了诱导分区可能发生变化的精确$d$值。第三，我们使用相同的构建和评估程序，将窗口化A-K-MDP与修复的二分基线进行比较。在考虑的保护问题中，当二分搜索错过更优的分区时，窗口化A-K-MDP能够找到具有更低决策损失的紧凑策略。

## 2 问题形式化
令 $M = (\mathcal{S}, \mathcal{A}, P, r, \gamma)$ 为一个有限MDP，其中 $\mathcal{S}$ 是状态空间，$\mathcal{A}$ 是动作集，$\varnothing \neq \mathcal{A}(s) \subseteq \mathcal{A}$ 是状态 $s$ 下可用的动作集，$P$ 是转移核，$r$ 是奖励，$\gamma \in [0, 1)$ 是折扣因子。假设 $V^*(s) \ge 0$ 且 $V_{\max} := \max_s V^*(s) > 0$。最低索引平局打破策略确定了一个最优确定性策略 $\pi^*$。
一个K-MDP $M_K = (\mathcal{S}_K, \mathcal{A}, P_K, r_K, \gamma, \phi)$ 是一个最多具有K个状态的MDP，解决K-MDP问题意味着找到最佳缩减状态空间（$\|\mathcal{S}_K\| \le K$），使得原始MDP与K-MDP之间的值损失最小。在此，我们研究Ferrer-Mestres等人报告的实证表现最佳的K-MDP变体，该变体使用动作/值抽象，形式化为：
$$
\phi_{a_d^*}(s) = \bigl( \pi^*(s), \lceil V^*(s)/d \rceil \bigr), \quad (1)
$$
并记 $\phi_d := \具有相同动作/值区间对的状态形成一个抽象状态，因此 $N(d) := \|\{ \phi_d(s) : s \in \mathcal{S} \}\|$ 是诱导的抽象状态数。当 $N(d) \le K$ 时，除数 $d$ 是可行的。更一般地，令 $N(\phi) := \| \{ \phi(s) : s \in \mathcal{S} \} \|$，因此 $N(\phi_d) = N(d)$。我们关注满足 $N(V_{\max}) \le K$ 的预算，这是该除数族在 $(0, V_{\max}]$ 上可达到的最小块数。
对于状态映射 $\phi$，我们定义其抽象状态集 $\mathcal{S}_\phi := \{ \phi(s) : s \in \mathcal{S} \}$ 和构成块 $B_k := \{ s \in \mathcal{S} : \phi(s) = k \}$。遵循Abel等人 (2016)和Ferrer-Mestres等人 (2020) 的做法，我们使用块内均匀权重 $\omega_\phi(s \mid k) := 1 / \| B_k \|$，其中 $s \in B_k$。抽象状态 $k$ 的动作集为 $\mathcal{A}_\phi(k) := \bigcap_{s \in B_k} \mathcal{A}(s)$。当 $\phi = \phi_d$ 时，对于每个 $k \in \mathcal{S}_\phi$，$\mathcal{A}_\phi(k) \neq \varnothing$，因为对于所有 $s \in B_k$，$\pi^*(s)$ 相同，并且这个共同动作属于每个 $s \in B_k$ 的 $\mathcal{A}(s)$。
对于 $k, k' \in \mathcal{S}_\phi$ 和 $a \in \mathcal{A}_\phi(k)$，抽象奖励和转移核定义为：
$$
r_\phi(k, a) := \sum_{s \in B_k} \omega_\phi(s \mid k) r(s, a), \quad
P_\phi(k' \mid k, a) := \sum_{s \in B_k} \omega_\phi(s \mid k) \sum_{s' \in B_{k'}} P(s' \mid s, a).
$$
连同 $\gamma$，这些量定义了抽象MDP。我们使用相同的最低索引平局打破策略求解它，并将其策略提升为 $\widetilde{\pi}_\phi(s) := \pi_\phi(\phi(s))$。遵循Ferrer-Mestres等人 (2020, 式(1))，我们通过其在原始MDP上的最大逐状态值损失来评估固定抽象 $\phi$：
$$
J(\phi) := \max_{s \in \mathcal{S}} \bigl[ V^*(s) - V^{\widetilde{\pi}_\phi}(s) \bigr]_+,
$$
其中 $[x]_+ := \max\{ x, 0 \}$。对于固定的 $\phi$，$J(\phi)$ 是其K-MDP间隙目标中的内部最大化。他们的目标是在所有允许的缩减状态空间上最小化，而窗口化仅比较在声明的除数窗口内诱导的候选分区。我们保留最坏状态标准，因为在选定的初始状态分布下的平均值可能会掩盖在不常加权但决策关键状态上的较大损失。

## 3 窗口化搜索
考虑一个具有两个状态的MDP，这两个状态共享相同的最优动作，且最优值 $V^* = (2, 3)$。对于 $K=1$ 个抽象状态的预算，在 $d = 3/2, 2, 3$ 处的值区间索引分别为 $(2, 2)$、$(1, 2)$、$(1, 1)$。因此，对于 $F_K(d) := \mathbb{1}\{ N(d) \le K \}$，两个状态在 $d=3/2$ 时分组在一起，在 $d=2$ 时分离，在 $d=3$ 时再次分组。因此，$N(d) = 1, 2, 1$，这表明条件 $N(d) \le K$ 在 $d$ 上并非单调。因此，二分轨迹可能会丢弃一个可行区间；附录A给出了一个三状态错过分区的例子。
我们的保守基线，端点修复二分法，在应用Ferrer-Mestres等人 (2020)的中点更新之前，保留了可行的端点 $d = V_{\max}$。我们通过利用抽象不等式(1)的结构来解决此问题。对于 $V^*(s) > 0$ 和 $d > 0$，整数分配 $\lceil V^*(s)/d \rceil$ 仅当 $d$ 穿过值 $V^*(s)/m$（其中 $m$ 为正整数）时发生变化。由于 $\pi^*(s)$ 固定，诱导的分区仅可能在这些除数值之一处发生变化。
对于一个固定的闭窗口 $W = [L, R]$，其中 $L > 0$，我们定义 $\mathcal{B}(W)$ 为包含窗口端点和所有诱导分区可能发生变化的 $d$ 值的集合：
$$
\mathcal{B}(W) := \{ L, R \} \cup \left\{ \frac{V^*(s)}{m} : V^*(s) > 0, m \in \mathbb{N}_+, L < \frac{V^*(s)}{m} < R \right\}.
$$
我们对 $\mathcal{B}(W)$ 进行排序以获得 $d_{(1)} < d_{(2)} < \dots < d_{(B_W)}$，其中 $B_W := |\mathcal{B}(W)|$。在每个开区间 $(d_{(j)}, d_{(j+1)})$ 内，向量 $\phi_d$ 是常数；因此，对于区间内的任何除数，$N(d)$ 和分区都是相同的。该区间的代表性除数为 $d_{(j)} + \epsilon$，其中 $\epsilon$ 为一个小正数（实际上，我们使用 $d_{(j+1)} - 10^{-14}$）。
窗口化算法（算法1）接受一个声明的窗口 $[L, R]$，并评估该窗口内每个不同分区的代表性除数。对于每个候选除数 $d_c$，它构建抽象MDP $M_{K_c}$，其中 $K_c := N(d_c) \le K$，求解它，提升策略，并计算值损失 $J(\phi_{d_c})$。它跟踪当前最佳值损失 $J^*$ 及其对应的除数 $d^*$。如果它遇到一个分区使得 $J=0$，则会提前终止并返回它。否则，它将返回在窗口中找到的最佳值损失及其对应的除数 $d^*$。
端点修复二分基线（算法2）从可行的端点 $d_b = V_{\max}$ 开始，并应用二分搜索，直到找到使 $N(d) \le K$ 的除数或满足停止容差 $\delta_b$。它返回在搜索过程中找到的最佳值损失和除数。

**算法1：窗口化A-K-MDP**
```
输入：V*, π*, K, L, R  // L > 0, L ≤ R
输出：J*, d*, E
1: d_list ← B([L, R]) 排序后的值
2: J*, d*, E ← ∞, null, 0
3: for j = 1 to |d_list| - 1 do
4:     d_c ← d_list[j] + ε  // ε 为一个极小的正数
5:     构建 φ_{d_c} 并计算 N(d_c)
6:     if N(d_c) ≤ K then
7:         构建并求解抽象 MDP M_{K_c}，其中 K_c = N(d_c)
8:         提升策略 \tilde{π}_{φ_{d_c}} 并计算 J(φ_{d_c})
9:         E ← E + 1
10:        if J(φ_{d_c}) < J* then
11:            J* ← J(φ_{d_c}), d* ← d_c
12:        if J* = 0 then
13:            return J*, d*, E
14: return J*, d*, E
```

**算法2：端点修复二分搜索**
```
输入：V*, π*, K, δ_b > 0
输出：J*, d*, E
1: V_max ← max_{s∈S} V*(s)
2: assert V_max > 0 且 N(V_max) ≤ K
3: d_min ← max{10^{-10} V_max, 10^{-12}}
4: d_b ← V_max, J* ← ∞, d* ← null, E ← 0
5: while d_b ≥ d_min do
6:     构建 φ_{d_b} 并计算 N(d_b)
7:     if N(d_b) ≤ K then
8:         构建并求解抽象 MDP M_{K_b}，其中 K_b = N(d_b)
9:         提升策略 \tilde{π}_{φ_{d_b}} 并计算 J(φ_{d_b})
10:        E ← E + 1
11:        if J(φ_{d_b}) < J* then
12:            J* ← J(φ_{d_b}), d* ← d_b
13:            if J* = 0 then return J*, d*, E
14:        d_b ← (d_b + d_min) / 2  // 中点更新
15:     else
16:        break  // N(d_b) > K，停止
17: return J*, d*, E
```

## 4 结果
我们评估了来自10个已求解MDP的33个案例-K对，其中七个是生态模型，三个是控制模型。所有比较均使用完整动作集 $\mathcal{A}$，相同的抽象MDP构建器和评估器，仅在候选分区上有所不同。窗口化改进了25行，持平了8行，因为它保留了修复的二分基线候选；在17个已完成窗口的有信息案例中，它改进/持平了14/3个。三个有界*伊蚊*运行达到 $J=0$，而 $K=305$ 在 $E_{\max}=96$ 处停止，并报告为“找到的最小间隙”。表1和附录提供了其余的详细说明。

**表1：使用完整动作集 $\mathcal{A}$ 的代表性原始-本地比较。** $C_W$ 是完整候选族的大小，$E$ 是实际的抽象MDP求解次数。破折号表示有界*伊蚊*运行；$E_0 d > 0$ 的行表示达到 $J=0$。重复的预算具有描述性而非独立重复，且无论 $K$ 小或 $J$ 低，都不能确立人类可解释性、生态有效性或实施的容易性。

## 代码和证据可用性
随附的匿名化制品记录了协议、模型标识、候选策略和策略哈希、验证脚本以及每个报告表格和图表背后的原始数据。

## 附录 A
非单调可行性
###### 命题 1. 谓词 $\mathbb{1}\{ N(d) \le K \}$ 在 $d$ 上可以是非单调的，即使对于共享一个动作且具有非负值的两个状态，且 $K=1$。
###### 证明. 取 $V^* = (2, 3)$。值区间在 $d=3/2$ 时为 $(2,2)$，在 $d=2$ 时为 $(1,2)$，在 $d=3$ 时为 $(1,1)$，因此随着 $d$ 增长，可行性依次为真、假、真。单个状态使得 $N(d) \equiv 1$，而具有不同最优动作的两个状态使得 $N(d) \equiv 2$；两种情况都是单调的。因此，这个两状态、共享动作的例子是最小的。∎
失败也可能改变哪些状态被分组。取 $V^* = (3, 5, 8)$，一个共享动作，且 $K=2$，每个 $d \in [5/2, 3)$ 诱导分区 $\{\{1,2\},\{3\}\}$，而 $d=4$ 诱导分区 $\{\{1\},\{2,3\}\}$。对 $[0,8]$ 进行二分法探测 $4, 2, 3, 7/2, \dots$ 并收敛到上部可行区域，而未评估较早的可行区间（图1）。

**图1：错过可行区间的二分搜索轨迹。** 对于 $V^* = (3, 5, 8)$，阴影区域满足 $N(d) \le K=2$。在探测 $d=4, 2, 3, 7/2$ 后，搜索向 $4$ 收缩，而未评估 $[5/2, 3)$，其诱导的分区与返回的分区不同。

## 附录 B
定理1的证明
固定 $s$，令 $v = V^*(s) > 0$。对于 $m \ge 2$，$\lceil v/d \rceil = m$ 当且仅当 $v/m \le d < v/(m-1)$。由于 $d>0$ 且永不改变，且每个动作标签 $\pi^*(s)$ 是固定的。因此，整个映射向量，从而诱导的分区，在每个半开区间上是常数；在闭端点 $R$ 处的映射单独计算。规范化通过首次出现重命名块，这仅移除了相同等价关系的标签排列，而确定性的构建器、求解器和提升对此是不变的。因此，对结果有限集的穷举比较达到了所述的最小值。∎

## 附录 C
实现说明
### 有限候选边界。
对于 $v = V^*(s) > 0$，只有满足
$$
\left\lfloor \frac{v}{R} \right\rfloor + 1 \le m \le \left\lceil \frac{v}{L} \right\rceil - 1 \quad (3)
$$
的整数 $m$ 会贡献断点。定义 $I_W := \sum_{v \in \text{uniq}\{V^*(s): V^*(s) > 0\}} \| \{ m \in \mathbb{N}_+ : L < v/m < R \} \|$，这是窗口 $W$ 中所有唯一正值 $v$ 的断点数量之和。窗口中不同分区的数量最多为 $I_W + 1$（定理1），因此候选评估次数 $E \le I_W + 1$。实际上，对于小窗口，$E$ 远小于此界限。
### 可行性检查。
由于 $N(d)$ 在开区间 $(d_{(j)}, d_{(j+1)})$ 内是常数，我们只需检查每个区间的代表性除数 $d_c$ 的 $N(d_c) \le K$。如果 $d_c$ 满足，则整个区间都满足。
### 抽象MDP构建。
对于每个候选分区，我们根据等式(1)计算抽象状态、动作集、奖励和转移。我们使用标准的值迭代来求解抽象MDP。
### 策略提升。
将抽象策略 $\pi_\phi$ 提升为原始状态 $s$ 的策略 $\widetilde{\pi}_\phi(s) = \pi_\phi(\phi(s))$。
### 值损失计算。
使用策略 $\widetilde{\pi}_\phi$ 通过策略评估计算原始MDP上的状态值 $V^{\widetilde{\pi}_\phi}$，然后计算 $J(\phi) = \max_s [V^*(s) - V^{\widetilde{\pi}_\phi}(s)]_+$。
### 二分搜索基线。
端点修复二分基线（算法2）从 $d_b = V_{\max}$ 开始。如果 $N(d_b) \le K$，则评估它，并通过将当前 $d_b$ 与 $d_{\min}$ 取平均来更新 $d_b$，其中 $d_{\min} = \max\{10^{-10} V_{\max}, 10^{-12}\}$。如果 $N(d_b) > K$，则停止。搜索持续直到 $d_b < d_{\min}$ 或找到 $J=0$。它跟踪遇到的最佳值损失。
### 窗口选择。
对于窗口化搜索，我们选择围绕二分锚点 $d_b$ 的窗口。具体来说，我们设置 $L = d_b / 2$ 和 $R = 2 * d_b$，并受 $L > 0$ 和 $N(V_{\max}) \le K$ 的约束。如果 $N(L) > K$，则我们增加 $L$ 直到 $N(L) \le K$。我们还确保 $R \ge V_{\max}$ 以覆盖整个可行范围。实际上，我们使用多个窗口来确保覆盖。
### 报告最佳值。
在窗口内，我们返回找到的最佳值损失 $J^*$ 及其对应的除数 $d^*$。如果 $J^* > 0$，我们报告为“找到的最小间隙”；这是评估的候选中的最小间隙，但不一定是整个窗口上的最小间隙。

## 附录 D
模型范围与来源
表2列出了每个案例中使用的精确计算对象。特别是，“包实例”不等同于重现一个已发表的表格。值间隙仅在行内报告：不同的奖励尺度和折扣使其幅度在领域间不可比。

**表2：十个MDP语料库的制品范围和折扣因子。** 下载的保护区和灰狼实例与相应已发表案例的维度不同；戈氏草雀是完全可观察的隐状态投影，而非原始的MOMDP策略。12行扩展使用了来自Marmote的36状态串联队列控制器、来自QuantEcon的41状态库存控制模型，以及源自ruspy的90状态公交车发动机更换适配器。随附的制品记录了这些实验中使用的源URL、版本、许可证、生成的数组和模型哈希。

## 附录 E
评估细节与代表性结果
所有比较均保留完整动作集 $\mathcal{A}$，尊重状态依赖的可用性，并使用相同的抽象MDP构建器、求解器、提升规则和目标。12行扩展使用了串联队列、库存控制和公交车更换模型。在观察它们的间隙之前，我们设置 $K_0 := \| \mathcal{S} \|$ 作为基线（无缩减）。我们报告值损失 $J(\phi)$ 和抽象状态数 $K_c$。我们还报告实际执行的抽象MDP求解次数 $E$。窗口大小为 $[L, R]$，其中 $L = d_b / 2$，$R = 2 d_b$，并受可行性约束。对于有界*伊蚊*运行，我们设置 $K=305$ 并运行二分搜索直到 $E_{\max}=96$，然后报告“找到的最小间隙”。窗口化运行针对相同的 $K$。重复的预算具有描述性，而非独立重复。我们注意到，无论 $K$ 小或 $J$ 低，都不能确立人类可解释性、生态有效性或实施的容易性。生态模型包括海獭-北方鲍鱼、草原犬鼠、北方斑点猫头鹰、黑足雪貂、草原榛鸡、红领带啄木鸟和新英格兰珊瑚蛇。控制模型包括库存、串联队列和公交车更换。我们还包含了三个有界*伊蚊*运行，其中 $K=305$。表1和附录中的表格提供了详细的数值比较。