Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing¶

会议: NeurIPS 2025
arXiv: 2505.21671
代码: 无
领域: 机器人
关键词: Gittins Index, Branching Bandit, 图前沿探索, 疾病检测, Markov Random Field

一句话总结¶

提出 Adaptive Frontier Exploration on Graphs (AFEG) 问题框架，设计基于 Gittins index 的策略，在图是森林时可证明最优，在实际性传播疾病检测网络上仅测试一半人口即可检出几乎全部 HIV 感染者，大幅超越贪心和 DQN 等基线。

研究背景与动机¶

领域现状：网络化疾病检测（如 HIV 接触追踪）需要在社交/性接触网络上顺序选择节点进行检测，已测节点的结果会更新邻居的感染概率。WHO 推荐网络化检测策略来触达未确诊人群。

现有痛点：直接建模为 MDP 面临指数级状态空间；自适应次模优化不适用（疾病检测的边际收益可能递增）；现有图主动搜索方法无前沿约束且缺乏理论保证。

核心矛盾：实际检测受"前沿约束"——只能测试已测节点的邻居（类似接触追踪），但这个约束下的最优策略设计困难。

本文目标 在前沿约束下，如何自适应地选择图节点以最大化折扣累积奖励？

切入角度：将 AFEG 建模为分支赌博机 (branching bandit) 问题，利用 Gittins index 的最优性理论。

核心 idea：AFEG 在森林图上可精确归约为分支赌博机问题，Gittins index 策略可证明最优且可高效计算。

方法详解¶

整体框架¶

输入为图 \(\mathcal{G}\)、节点标签联合分布 \(\mathcal{P}\)（Markov Random Field）和折扣因子 \(\beta\)。每步选择前沿节点，揭示标签获得奖励，贝叶斯更新邻居信念。目标是最大化折扣累积奖励 \(\sum_t \beta^{t-1} r(X_{\pi(\mathcal{S}_{t-1})}, v)\)。

关键设计¶

AFEG → 分支赌博机归约 (Theorem: 森林最优性):
- 功能：证明当 \(\mathcal{G}\) 是森林时，AFEG 精确等价于分支赌博机问题
- 核心思路：在森林中，选择一个节点后其子节点成为新的"手臂"，且由 Markov 性质，已选节点的信息只通过父子链传递。这满足分支赌博机的独立性条件，因此 Gittins index 策略最优
- 设计动机：分支赌博机的最优性理论 [KO03] 保证了 Gittins 策略的最优性，但之前没有高效计算方法
分段线性 Gittins Index 计算:
- 功能：证明 Gittins index 的递归函数是分段线性的，据此设计高效算法
- 核心思路：对离散标签空间，价值函数 \(\phi_{X,v}(k)\)（子树 \(X\) 在父标签 \(v\) 下的退休值函数）是分段线性的。Gittins index 等于该函数斜率的上确界，可通过保存断点高效计算
- 设计动机：传统 Gittins index 被认为"计算困难"，这是首个针对离散分支赌博机的高效实现
非森林图的启发式扩展:
- 功能：对一般图（非森林），用 BFS 树近似原图，仍然应用 Gittins 策略
- 核心思路：将每个连通分量构建 BFS 树，忽略回边，在结果树上计算 Gittins index。虽然不再有最优性保证，但实际效果持续优于其他基线
- 设计动机：现实中性接触网络虽非严格森林，但通常稀疏且树宽低（实验中约 2-5），因此 BFS 树近似有效

损失函数 / 训练策略¶

无训练环节（非学习方法）
运行时间 \(\mathcal{O}(n^2 \cdot |\Omega|^2)\)，oracle 调用 \(\mathcal{O}(n \cdot |\Omega|^2)\)，空间 \(\mathcal{O}(n^2 \cdot |\Omega|)\)
MRF 参数可从历史疾病数据学习（附录 B）

实验关键数据¶

主实验 (真实性传播疾病网络)¶

疾病	测试50%人口时 Gittins 检出率	Greedy	DQN	Random
HIV	≈100%	≈80%	≈80%	≈55%
淋病	≈98%	≈90%	≈85%	≈55%
衣原体	≈97%	≈88%	≈82%	≈55%
梅毒	≈95%	≈85%	≈80%	≈55%
肝炎	≈96%	≈87%	≈83%	≈55%

消融实验 (合成树)¶

配置	说明
森林图	Gittins = Optimal（验证最优性定理）
添加边→非树	Gittins 优势递减但仍优于其他基线
噪声分布 \(\mathcal{Q}_\varepsilon\)	随 \(\varepsilon\) 增大，所有策略退化向 Random，但 Gittins 退化最慢

关键发现¶

Gittins 不仅在折扣收益上最优，在任何固定预算下也持续最优：虽然理论只保证折扣累积收益，但实验中 Gittins 在每个时间步都优于其他方法
真实网络树宽低（2-5）：性接触网络天然近似树结构，这是 Gittins 策略在实践中有效的关键原因
DQN 表现不如 Greedy：深度 RL 方法在这种结构化问题上难以竞争，指数级状态空间阻碍了学习

亮点与洞察¶

将公共卫生问题形式化为分支赌博机问题是全新的视角：为网络化疾病检测提供了有理论保证的最优策略，而非纯启发式
分段线性 Gittins index 的刻画：解决了分支赌博机文献中长期悬而未决的计算问题，有独立的理论贡献
实际影响力大：WHO 推荐的接触追踪策略可以直接受益于此方法，在 HIV "95-95-95" 目标中具有直接应用价值

局限与展望¶

非森林图无理论保证：BFS 树近似在高树宽图上可能失效
假设完全已知 MRF：实际中 \(\mathcal{P}\) 需要从数据估计，误差会传播到策略质量
可扩展性受限：\(\mathcal{O}(n^2 |\Omega|^2)\) 对超大网络可能过慢
未处理动态网络：假设图结构固定，现实中接触网络随时间变化

评分¶

新颖性: ⭐⭐⭐⭐⭐ 将图前沿探索形式化为分支赌博机并给出高效算法，理论贡献扎实
实验充分度: ⭐⭐⭐⭐ 合成+真实数据，5种疾病，噪声鲁棒性分析，但缺少更大规模实验
写作质量: ⭐⭐⭐⭐⭐ 动机清晰（HIV检测），理论严谨，图示直观
价值: ⭐⭐⭐⭐⭐ 对公共卫生领域有直接影响，理论和实践价值兼具