Learning to target with network interference¶
会议: NeurIPS 2026
arXiv: 2605.27794
论文: https://arxiv.org/abs/2605.27794
代码: https://github.com/Xiaomengwang99/Interference_bandit_public
领域: 学习理论
关键词: 网络溢出效应、自适应定向、多臂老虎机、下界分析、逐次消除
一句话总结¶
针对网络溢出干扰下的在线自适应定向决策问题，论文证明了忽略网络结构的全局回报聚合必然导致超线性遗憾下界，并针对全支撑已知、仅列支撑大小已知及完全无支撑三种场景提出近最优遗憾界的网络老虎机算法。
研究背景与动机¶
在精准营销、公共卫生干预和推荐系统等场景中，决策者需要根据个体特征与干预反馈自适应选择目标人群以最大化总体回报。传统的因果推断与老虎机算法普遍依赖个体间无干扰假设（SUTVA），即任意个体的干预仅影响其自身观测结果。然而在真实社会网络中，个体之间普遍存在广泛的溢出效应（spillover effects）与同伴效应。例如在定向广告投放中，被触达的用户可能会向好友推荐商品，从而间接提升未受干预用户的转化概率；反之，在数字订阅共享场景中，干预可能导致未被干预群体的付费意愿下降。
这种网络干扰给在线策略学习带来了双重核心矛盾。一方面，传统直接对比受试组与对照组回报的做法，会因忽略间接溢出而严重误估因果效应；若将总回报降维为标量，转化为标准随机线性老虎机（Linear Bandit），由于个体间关联交错，原本行稀疏的网络矩阵在累加为列和参数后失去了稀疏结构，迫使算法在高维非稀疏参数空间中探索，导致遗憾值关于总体规模呈超线性激增。另一方面，若直接估计完整的网络效应矩阵，参数量随群体规模呈平方级爆炸，在在线决策的遗憾最小化目标下极难兼顾样本效率与探索成本。
本文切入的角度是：在现实大规模网络中，尽管总体规模庞大，但个体往往仅受少数可数同伴的直接影响，呈现典型的行稀疏结构。核心 idea：利用网络行稀疏特性与可观测个体维度的回报反馈，依据先验结构信息的多寡（全支撑、列支撑度数、无支撑）设计针对性的多阶段逐次消除与套索探索算法，在理论上消除遗憾对群体维度的超线性放大并匹配极小化极大遗憾下界。
方法详解¶
整体框架¶
系统在时间跨度 \(T\) 内面向规模为 \(d\) 的人群执行在线决策。在每一轮 \(t \in [T]\)，决策者指派干预向量 \(a_t \in \{-1, 1\}^d\)，并观测到全群体个体的回报向量 \(Y_t \in \mathbb{R}^d\)。每个个体的期望回报由行稀疏网络处理效应矩阵 \(X^* \in \mathbb{R}^{d \times d}\) 线性决定： $\(Y_{t,i} = \sum_{j \in [d]} X^*_{ij} a_{t,j} + \epsilon_{t,i}\)$ 其中对角线元素 \(X^*_{ii}\) 表示直接干预效应，非对角线元素 \(X^*_{ij}\) 刻画个体 \(j\) 对个体 \(i\) 的溢出效应，且每行最多含有 \(s \ll \min(d, T)\) 个非零项。目标是学习动态策略 \(\pi\)，最小化关于事后最优固定策略 \(a^* = \arg\max_{a \in \mathcal{A}} \mathbf{1}^\top X^* a = \text{sign}((X^*)^\top \mathbf{1})\) 的累积遗憾 \(\mathbb{E}[\text{regret}_{X^*}(\pi)] = \mathbb{E}\left[\sum_{t=1}^T \mathbf{1}^\top X^*(a^* - a_t)\right]\)。
根据决策者掌握网络支撑结构的精细程度，论文构建了针对三类先验信息阶梯的高效在线学习机制：
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入: 群体规模 d, 周期 T, 行稀疏度 s, 网络先验信息"] --> B{"网络先验结构信息层级"}
B -->|"全支撑已知 S"| C["分批预热与受限最小二乘逐次消除<br/>NSE-FS: 预热均值初筛 + OLS精细估计"]
B -->|"仅列支撑大小 ρ_j 已知"| D["硬阈值单热相关度逐次消除<br/>NSE: 互相关过滤截断 + 列置信区间消除"]
B -->|"完全无支撑信息"| E["套索探索与锁定<br/>NETC: 纯随机探索 + 行独立LASSO + 贪心承诺"]
C --> F["输出: 符号决策 a_t 逼近最优符号 a*<br/>匹配最优理论下界 O~(√T Σ√ρ_j)"]
D --> F
E --> F关键设计¶
1. 网络结构感知消除机制（NSE-FS）：预热均值粗筛与受限最小二乘精细截断 在完全掌握网络邻接支撑 \(S_{ij} = \mathbb{I}\{X^*_{ij} \neq 0\}\) 的场景下，识别最优决策 \(a^*_j\) 的核心在于精准判定列和参数 \(\theta_j = \sum_{i=1}^d X^*_{ij}\) 的正负符号。若直接使用无约束回归，在样本量不足时经验协方差矩阵可能出现奇异。算法将总时间 \(T\) 划分为以几何级数递增的 \(M = \lceil \log_2(T/2 + 1) \rceil\) 个批次。在预热阶段（批次 \(m < m_0\)），对尚未确定符号的待定集合 \(U_{m-1}\) 中的坐标随机探索，对已确定的坐标直接执行最优符号动作，并采用样本互相关均值 \(\hat{X}_{ij}^{(m)} = \frac{1}{n_m} \sum_{t \in D_m} Y_{t,i} a_{t,j}\) 累加估算 \(\hat{\theta}_j^{(m)}\)。当批次样本量满足 \(n_m \ge 128 s \log(8 \log_2 T d s / \delta)\) 时进入普通最小二乘（OLS）阶段，此时样本协方差在稀疏子空间上受限特征值严格远离零，算法仅在真实支撑与未定集合交集 \(E_i^{(m)} = S_i \cap U_{m-1}\) 上求解受限去均值最小二乘： $\(\hat{X}_{i, \cdot}^{(m)} = \arg\min_{\gamma \in \mathbb{R}^d, \gamma[(E_i^{(m)})^c] = 0} \frac{1}{2n_m} \sum_{t \in D_m} \left\{ Y_{t,i} - \bar{Y}_i^{(m)} - \gamma^\top (a_t - \bar{a}^{(m)}) \right\}^2\)$ 结合更新后的估计值 \(\hat{\theta}_j^{(m)} = \sum_{i=1}^d \hat{X}_{ij}^{(m)} \mathbb{I}\{j \in S_i\}\)，将满足 \(|\hat{\theta}_j^{(m)}| > \sqrt{\rho_j} \tau_m\) 的坐标剔除出不确定集合 \(U_m\)。该设计彻底消除了无支撑方向的噪声扰动，达到了与理论下界精确匹配的 \(\tilde{\mathcal{O}}(\sqrt{T} \sum_{j=1}^d \sqrt{\rho_j})\) 极小化极大收敛速率。
2. 统计硬阈值逐次消除机制（NSE）：列度数已知下的鲁棒单热截断估计 当决策者仅知悉每个个体的受影响总数（即网络列度数 \(\rho_j = \sum_{i=1}^d S_{ij}\)）而无法掌握具体连接拓扑时，最小二乘受限投影因缺乏支撑坐标集而失效。若直接对全部 \(d\) 维参数做密集求和，非零信号会被大量零均值噪声掩盖。NSE 算法在每批次 \(D_m\) 收集随机干预下的观测数据，首先计算无偏样本互相关估计 \(\hat{X}_{ij}^{(m)} = \frac{1}{n_m} \sum_{t \in D_m} Y_{t,i} a_{t,j}\)。随后引入基于噪声集中不等式设计的硬阈值过滤： $\(\hat{\theta}_j^{(m)} = \sum_{i=1}^d \hat{X}_{ij}^{(m)} \cdot \mathbb{I}\left\{ |\hat{X}_{ij}^{(m)}| > \frac{\tau_m}{8} \right\}\)$ 通过设定阈值 \(\tau_m = 16 \sqrt{\frac{\log(4 d^2 \log_2(T) / \delta)}{2^{m-1}}}\)，高概率过滤掉所有真实为零条目的估计噪声（因无边连接时 \(|\hat{X}_{ij}^{(m)}| \le \tau_m/8\)），仅保留潜在的真实连接边。未确定集合判定准则采用列支撑上界加权更新 \(U_m = \{j \in U_{m-1} : |\hat{\theta}_j^{(m)}| \le \rho_j \tau_m\}\)。此举在未知连边拓扑的恶劣条件下，避免了维度 \(d\) 的噪声累积，使得遗憾界仅线性依赖于列总度数 \(\sum_{j=1}^d \rho_j \le ds\)。
3. 套索探索与承诺机制（NETC）：未知拓扑下的行独立稀疏正则化恢复 在完全缺乏网络结构先验、仅假定行稀疏度不超过 \(s\) 的极限情形下，逐次消除因无法设定自适应消除阈值而不再适用。NETC 采用基于时间分割的探索-承诺（Explore-Then-Commit）机制。算法精准平衡探索代价与利用偏差，设定前 \(T_1 = T^{2/3} s^{2/3}\) 轮次为均匀随机探索阶段。在探索期结束后，利用各行相互独立的观测结构，将庞大的全网参数估计解耦为 \(d\) 个并行的单行 LASSO 回归： $\(\hat{X}_{i \cdot} = \arg\min_{\gamma \in \mathbb{R}^d} \left\{ \frac{1}{2 T_1} \sum_{t=1}^{T_1} (Y_{t,i} - \gamma^\top a_t)^2 + \lambda \|\gamma\|_1 \right\}\)$ 其中惩罚因子设为 \(\lambda = 4 \sqrt{\frac{2 \log(2 d^2 / \delta)}{T^{2/3} s^{2/3}}}\)。利用亚高斯随机设计矩阵在稀疏向量上的受限特征值性质（Restricted Eigenvalue Condition），证明估计误差满足 \(\|\hat{X}_{i \cdot} - X^*_{i \cdot}\|_1 \le \mathcal{O}(s \lambda)\)。在剩余的 \(T - T_1\) 轮利用阶段，算法直接承诺执行经验最优决策 \(\hat{a} = \text{sign}(\sum_{i=1}^d \hat{X}_{i \cdot})\)。此机制保证了在完全没有拓扑先验的黑盒网络中，遗憾值关于群体规模 \(d\) 严格保持线性增长 \(\tilde{\mathcal{O}}(d (sT)^{2/3})\)。
损失函数 / 训练策略¶
算法的核心优化策略依据结构知识分治： 1. NSE-FS 优化：预热期采用样本一阶矩估计；进入 OLS 阶段后，每行独立针对限制在非零支持交集 \(E_i^{(m)}\) 内的子矩阵求解投影线性回归，经验协方差矩阵规模不超过 \(s \times s\)，利用标准正规方程或奇异值分解快速解析求解。 2. NSE 优化：纯闭式计算，各行动作与回报的内积统计复杂度为 \(\mathcal{O}(n_m d)\)，硬阈值过滤仅需一维线性标量截断，单批次整体计算开销极低。 3. NETC 优化：在探索期结束时调用凸优化求解器（如 Gurobi 或坐标下降法）并行解 \(d\) 个独立的高维 LASSO 问题，参数选择严格依据理论极值条件设置，无需在线交叉验证。
实验关键数据¶
主实验¶
实验在合成随机网络（\(d=100, T=20000\)）以及真实社会网络（印度村庄小额信贷干预网络数据集，74个村庄，平均 \(d=199.31\)，行稀疏比率 \(s/d\) 均值 0.20）上进行评测。对比方法涵盖忽略网络结构的基线线性老虎机（Baseline LinUCB）、完全无先验的 NETC、列度数先验的 NSE 以及全拓扑先验的 NSE-FS。
| 数据集 / 实验设置 | 评估指标 | NSE-FS (全支撑已知) | NSE (列度数已知) | NETC (无支撑信息) | Baseline (聚合LinUCB) | 性能优势/收敛特性 |
|---|---|---|---|---|---|---|
| 合成网络 (\(d=100, T=2万, s_0=20\)) | 终期累积遗憾 \(\mathbb{E}[\text{regret}]\) | ~1,200 | ~1,500 | ~3,800 | ~8,900 | 相比基线分别降低 86.5%、83.1%、57.3% |
| 印度村庄网络 (74个真实村落均值) | 人均累积遗憾 \(\text{regret}/d\) | ~14.2 | ~16.8 | ~28.5 | ~63.1 | 真实复杂网络中人均遗憾下降达 77.5% |
| 维度扩展性 (\(T=2万, d: 100 \to 900\)) | 人均遗憾随 \(d\) 变化斜率 | 稳步收敛微增后持平 | 缓慢微增后持平 | 保持严格水平平坦 | 随 \(d\) 呈显著超线性快速发散 |
消融实验¶
论文在附录 C 中系统检验了算法对信号强度 \(\beta \in [0.01, 0.5]\) 与网络稀疏度 \(s \in [5, 50]\) 的鲁棒性与边界表现。
| 实验配置变化 | 核心指标表现 | 机制分析与说明 |
|---|---|---|
| 极低信号强度 (\(\beta = 0.01\)) | 四类方法累积遗憾相近（~5,000） | 真实信号被标准高斯噪声淹没，策略差异间隙极小，无法有效区分正负符号 |
| 中等信号强度 (\(\beta = 0.1\)) | NSE-FS < NSE < NETC \(\ll\) Baseline | 结构感知逐次消除显著主导，自适应平衡探索成本与利用收益 |
| 极强信号强度 (\(\beta = 0.5\)) | NETC 性能显著跃升并逼近 NSE-FS | 探索期后贪心决策正确率迅速趋近 100%，纯随机探索成本占比大幅缩小 |
| 极稀疏网络 (\(s = 5, d = 100\)) | 结构方法优势微弱 | 溢出效应极微弱，网络干扰退化为近似独立决策，各方法表现接近 |
| 高密度网络 (\(s = 50, d = 100\)) | NSE-FS 优势扩大至数倍于其他算法 | 当溢出波及半数群体时，全拓扑结构信息对压制高维交叉干扰噪声具备决定性价值 |
关键发现¶
- 忽略网络结构的全局回报聚合方法（Baseline）在任何规模下均表现最差，其实际遗憾随群体规模呈超线性发散，印证了理论推导的 \(\Omega(d^{3/2} \sqrt{T} \wedge dT)\) 遗憾下界。
- 在网络规模扩展性实验中，NETC 的人均遗憾几乎完全不随 \(d\) 增长（斜率接近 0），完美契合了其人均上界 \(\tilde{\mathcal{O}}((sT)^{2/3})\) 与群体维度解耦的性质；NSE 和 NSE-FS 则在小规模时遗憾最低，并在达到一定维度后迅速趋向平台期。
- 只要掌握粗粒度的列支撑度数，NSE 算法通过简单的统计硬阈值截断便能取得接近全支撑已知算法的实操表现，为数据隐私受限场景（无法采集完整邻接图）提供了极高实用价值的替代方案。
亮点与洞察¶
- 从信息论下界揭示网络干扰的本质瓶颈：文章首次推导出依赖列支撑轮廓 \(\rho_j\) 的实例依赖型下界，严格证明了简单加和汇报导致稀疏性破损的数学机制，界定了网络干预学习中的理论界限。
- 解耦消除的巧妙两阶段设计：NSE-FS 算法将预热相关初筛与受限 OLS 精准剔除融合，巧妙绕过了在线决策早期协方差矩阵奇异导致受限特征值失效的理论死穴。
- 度数先验与硬阈值的代数协同：NSE 算法在完全不获知具体相连个体的情况下，仅凭列度数设定截断阈值滤除无连接噪声，以极轻量的一维统计量实现了原本需要全图先验才能压制的高维误差。
局限与展望¶
- 行稀疏度先验依赖：NETC 算法中的探索步长 \(T_1\) 明确依赖稀疏度参数 \(s\) 的先验知识；在完全黑盒场景中若 \(s\) 被严重误估，算法的探索-利用权衡将偏离理论最优比率。
- 线性效应假设的适用边界：模型严格建立在线性加性溢出效应基础之上，未考虑网络传播中常见的阈值非线性效应、级联饱和或动态随时间演化的网络拓扑结构。
- 推断与遗憾最小化的兼顾：算法设计专精于累积遗憾极小化，但在实际 A/B 测试或医疗公共政策中，研究者往往同时要求对特定处理效应进行置信区间估计与无偏因果假设检验。
相关工作与启发¶
- vs Agarwal et al. (2024)：Agarwal 等人采用布尔傅里叶展开刻画网络干预的任意非线性函数，导致遗憾界对稀疏度 \(s\) 呈指数级恶化 \(\mathcal{O}(|\mathcal{A}|^s)\)，计算内存代价巨大；本文在线性高维因果框架下实现多项式甚至亚多项式级依赖，且关于群体规模 \(d\) 严格线性可扩展。
- vs Hao et al. (2020)：Hao 等人提出了无网络干扰下的高维稀疏线性老虎机 ETC 算法；本文将其拓展至存在横向网络溢出的复杂图结构环境，证明了各行误差可解耦控制并给出了全新的网络干扰下界体系。
- vs 经典自适应播种（Adaptive Seeding）：传统自适应播种关注信息在社交网络中的最大化级联传播（全正向扩散）；本文针对存在异质性因果效应、甚至存在负向溢出阻碍的精细化净收益收益优化。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次建立网络干扰下在线自适应定向的完整理论框架与分级信息下界体系。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖理论严密证明、合成网络多维度控制变量以及真实印度村落复杂网络实证。
- 写作质量: ⭐⭐⭐⭐⭐ 逻辑链路严丝合缝，符号系统规整，问题定义、下界推导与算法推演层次清晰。
- 价值: ⭐⭐⭐⭐⭐ 为社交营销、微金融渗透和公共干预实验提供了坚实且具极高拓展性的方法论工具。