Zeroth-Order Stackelberg Control in Combinatorial Congestion Games¶
会议: NeurIPS 2026
arXiv: 2602.23277
代码: https://anonymous.4open.science/r/ZO-Stackelberg
领域: 强化学习
关键词: Stackelberg控制, 组合拥塞博弈, 零阶优化, Frank-Wolfe算法, Wardrop均衡
一句话总结¶
针对组合拥塞博弈中因离散策略激活集突变导致上层目标非光滑的问题，提出无须通过下层均衡反向传播求导的 ZO-Stackelberg 框架，通过免投影 Frank-Wolfe 与分层采样 LMO 求解下层 Wardrop 均衡，结合外层双点零阶更新实现收敛到广义 Goldstein 驻点并取得最高上千倍加速。
研究背景与动机¶
在现代智能交通调度、通信多播路由和物流干线配送等大规模网络系统中，中心决策者（领导者）通常需要通过设定路桥收费通行费、分配链路带宽容量或动态资源激励，来引导网络中的自私用户群体优化资源配置。这类交互通常被建模为 Stackelberg（主从博弈）控制问题：领导者率先确定网络控制参数，随后大量的非原子自私用户在离散组合策略空间（如点对点路径、哈密顿路径、斯坦纳树或环路）中进行分布式决策，最终自发演化并稳定在 Wardrop 用户均衡状态。
然而，在组合拥塞博弈（CCG）中，可行策略集的规模通常随网络资源数量呈组合爆炸式增长，且可行负荷集构成了多面体。由于用户仅对当前总费用最小的离散策略分配正流量，当领导者对控制参数施加微小扰动时，达到最低费用的活跃策略集经常会发生离散的跳变，使得下层均衡映射在策略切换点处产生不可导的尖折（kinks），甚至导致不可导点的数量随策略集合规模呈线性增长。既有方法多采用可微均衡计算范式，即在内层迭代求解器中引入光滑松弛（如 Softmin 替换 argmin）并沿计算图展开反向传播求导；但此类方法优化的是有偏的人工平滑代理目标，难以保证在真实非光滑超目标下的全局收敛性，且随着内层迭代步数加深和状态图扩展，反向传播会产生极高的显存开销与计算延迟。
面对这一核心困境，本文摒弃了“强制将均衡计算平滑化后求导”的传统思路，将下层均衡求解器视为黑盒并直接面向原始非光滑超目标。核心 idea：将免投影 Frank-Wolfe 均衡求解器与外层基于两点有限差分的投影零阶优化耦合，并引入基于零抑制二分决策图（ZDD）的分层采样线性最小化预言机（LMO），在完全避免跨均衡反向传播的同时实现对原问题广义 Goldstein 驻点的理论收敛与数个数量级的工程加速。
方法详解¶
整体框架¶
ZO-Stackelberg 算法由内层均衡求解器和外层零阶更新回路嵌套构成。领导者控制参数 \(\theta \in \Theta\)（如各链路的收费或通行容量调控因子），下层非原子用户在可行负载多面体 \(\mathcal{C}\) 上自发达到最小化 Beckmann 凸势函数 \(f(\theta, y)\) 的唯一 Wardrop 均衡负荷 \(y^\star(\theta)\)。领导者根据真实诱导负荷评估系统级社会成本或总通行延迟 \(F(\theta, y^\star(\theta))\)。
算法在内层固定 \(\theta\) 运行 Frank-Wolfe 迭代获取近似均衡解 \(y_T(\theta)\)，外层通过随机球面方向扰动评估两点近似超目标函数值构建无偏伪梯度，最终投影回可行域更新参数。对于 NP-hard 组合策略族，预先构建紧凑的零抑制决策图（ZDD），并结合长度分层采样解决策略空间样本失衡问题。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["领导者参数 θ 与扰动方向采样"] --> B["外层双点零阶参数扰动：θ ± ρu"]
B --> C["内层 Frank-Wolfe 均衡求解：求近似均衡解 y_T"]
C --> D["线性最小化预言机：精确最短路/ZDD分层采样"]
D --> E["精确线搜索更新负荷迭代点"]
E --> F["系统目标评估与双点梯度估计量构建"]
F --> G["投影梯度更新领导者参数 θ"]关键设计¶
1. 免投影 Frank-Wolfe 内层均衡求解：规避高维欧氏投影并保留组合结构 在组合拥塞博弈中，可行负荷集合是策略发生向量的凸包 \(\mathcal{C} = \mathrm{conv}\{\mathbf{1}_S : S \in \mathcal{S}\} \subseteq [0, 1]^n\)。标准梯度投影法在此类高维离散组合多面体上计算投影极度昂贵甚至不可行。Frank-Wolfe 算法仅通过线性最小化预言机（LMO）在多面体顶点上求解极值。在每步内层迭代中，算法计算势函数梯度 \(g_t = \nabla_y f(\theta, y_t) = (c_i(y_{t,i}; \theta))_{i=1}^n\)，然后调用预言机返回当前边权重下的最优组合结构 \(s_t = \mathrm{LMO}(g_t) \in \arg\min_{S \in \mathcal{S}} \sum_{i \in S} [g_t]_i\)。随后通过精确一维线搜索确定步长 \(\gamma_t = \arg\min_{\gamma \in [0,1]} f(\theta, y_t + \gamma(s_t - y_t))\)，更新负载向量 \(y_{t+1} = (1 - \gamma_t)y_t + \gamma_t s_t\)。该过程无需枚举指数级策略集合，输出的迭代点自然保持在可行多面体 \(\mathcal{C}\) 内部。
2. 外层双点零阶梯度估计：直面非光滑超目标并解除反向求导内存瓶颈 由于活跃策略集的离散突变，真实超目标函数 \(\Phi(\theta) := F(\theta, y^\star(\theta))\) 通常处处连续但局部非光滑（包含 \(\Omega(|\mathcal{S}|)\) 个不可导转折点）。传统的一阶双层反向传播不仅需要平滑化处理从而引入系统偏差，还需要在计算图中保存全部内层迭代状态，显存随迭代步数线性爆炸。外层循环在单位球面上独立均匀采样 \(B\) 个随机方向向量 \(u_{t,1}, \dots, u_{t,B} \sim \mathrm{Unif}(\mathbb{S}^{k-1})\)，并基于半径为 \(\rho > 0\) 的双点函数差分构建梯度估计量： $\(\widehat{g}_t = \frac{k}{2\rho B} \sum_{i=1}^B \left( F(\theta_t + \rho u_{t,i}, y_{t,i}^+) - F(\theta_t - \rho u_{t,i}, y_{t,i}^-) \right) u_{t,i}\)$ 其中 \(y_{t,i}^+\) 和 \(y_{t,i}^-\) 分别是参数在正负扰动下独立运行 \(T\) 步 Frank-Wolfe 返回的近似均衡。随后执行欧氏参数投影步 \(\theta_{t+1} = \Pi_\Theta(\theta_t - \eta \widehat{g}_t)\)。该估计器完全解耦了内外层计算图，使各扰动方向的均衡求解可天然多线程并行。
3. ZDD 紧凑图与长度分层采样 LMO：打破指数策略空间中的命中率坍塌 对于哈密顿路径或斯坦纳环路等 NP-hard 策略族，即便预先编译出包含所有可行解的零抑制二分决策图（ZDD），在图规模庞大时单次精确动态规划依旧耗时沉重；而简单的均匀采样（US）策略在此类非均衡组合族中会遭遇严重的维数灾难：由于长策略组合数呈指数级压倒短策略，均匀采样抽取的几乎全为冗长策略，导致命中当前最优策略的概率 \(\kappa_m \approx m / |\mathcal{S}|\) 趋于零，使得采样版 FW 收敛速度停滞。本文引入长度分层采样，利用 ZDD 预先自底向上计算各节点具有特定长度的剩余路径数 \(N_r(v)\)，先以去偏概率分布选择基数 \(r \in \mathcal{L}\)，再在对应长度层级内部均匀采样策略： - 均匀长度采样（UL）：在所有可行长度集合 \(\mathcal{L}\) 上赋予等概率分布 \(\pi(r) = 1/|\mathcal{L}|\)； - 调和长度采样（HL）：按长度倒数加权 \(\pi(r) \propto 1/r\)，倾向于探索更短的精简组合路径。 由于非负权重下单调累加的物理特性，最优策略高度富集在基数较小的子空间中，长度分层极大抬升了采样最优解命中概率 \(\kappa_m\)，使采样版 FW 的收敛率达到与样本量独立的 \(\mathcal{O}(1/(\kappa_m T))\)。
损失函数 / 训练策略¶
在外层参数可行集约束方面，采用标准边界投影算子确保控制参数落在封闭凸集 \(\Theta\)（如归一化收费约束 \(\sum_i \theta_i = n, \theta_i \geq 0\)）。外层超参数选取平滑扰动半径 \(\rho = 0.05\)、外层学习率 \(\eta = 0.05\) 以及方向批大小 \(B = 4\)；内层均衡计算统一迭代 \(T = 3000\) 步。理论上，当内层近似误差满足 \(\varepsilon_y = \sup_\theta \sqrt{\mathbb{E}[\|y_T(\theta) - y^\star(\theta)\|^2]} \leq \mathcal{O}(\rho \epsilon / (k L_{F,1}))\) 时，算法在 \(K = \mathcal{O}(\epsilon^{-2})\) 步内收敛到 \(\Phi(\theta)\) 的 \((\epsilon, \rho, \eta)\)-广义 Goldstein 驻点。
实验关键数据¶
主实验¶
在真实交通基准数据集 TNTP（涵盖 Winnipeg、Chicago-Sketch、Philadelphia 真实路网拓扑）上评估三种策略场景：多项式时间 \(s\)-\(t\) 路径（场景1）、中等规模 ZDD 下 NP-hard 哈密顿路径（场景2）以及大规模庞大 ZDD 下斯坦纳环路（场景3）。对比基线为基于自动微分与 Softmin 松弛的微调反向传播方法 Diff（Sakaue & Nakamura, 2021）。
| 评估网络与场景 | 核心评价指标 | 本文 ZO-Stackelberg | 之前基线 Diff | 性能提升/对比 |
|---|---|---|---|---|
| Scenario 1 (Winnipeg) \(s\)-\(t\) 路径 (多项式LMO) |
外层单步耗时 (s) 峰值内存 RSS (GiB) 最终 FW 对偶间隙 最终社会总成本 |
0.82 0.28 \(2.1 \times 10^{-2}\) \(1.84 \times 10^3\) |
18.9 10.2 \(1.9 \times 10^{-2}\) \(1.84 \times 10^3\) |
23.0× 速度提升 97.3% 内存节省 均衡质量一致 目标成本相当 |
| Scenario 2 (Chicago) 哈密顿路径 (紧凑ZDD) |
外层单步耗时 (s) 峰值内存 RSS (GiB) 最终 FW 对偶间隙 最终社会总成本 |
0.51 0.37 \(1.2 \times 10^{-2}\) \(3.42 \times 10^2\) |
31.2 15.9 \(1.1 \times 10^{-2}\) \(3.41 \times 10^2\) |
61.2× 速度提升 97.7% 内存节省 均衡质量一致 目标成本相当 |
| Scenario 3 (Philadelphia) 斯坦纳环路 (大规模ZDD) |
外层单步耗时 (s) 峰值内存 RSS (GiB) 500步完成状态 最终社会总成本 |
5.4 (HL, \(m\)=1000) 1.65 顺利完成 500 轮 \(1.12 \times 10^3\) |
>7200 (外层超10小时) 194.0 内存爆炸/仅跑完5步 无法收敛中断 |
>1000× 实际加速 99.1% 内存节省 Diff完全不可行 收敛至真实低成本 |
消融实验¶
在场景3（策略空间总数达 \(3.81 \times 10^{14}\)，ZDD 节点数达 \(1.08 \times 10^6\)）中对比精确 ZDD 求解与不同采样预言机在不同采样规模 \(m \in \{10, 100, 1000\}\) 下的收敛表现：
| 采样配置方案 | 采样预算 \(m\) | FW 对偶间隙 | 单步耗时 (s) | 方案有效性说明 |
|---|---|---|---|---|
| ZOS-Exact (精确DP) | - | \(9.8 \times 10^{-4}\) | 37.2 | 基准真值，计算精确但随图增长耗时较长 |
| ZOS-US (均匀策略采样) | 100 | \(1.42 \times 10^{0}\) | 2.1 | 陷入维数灾难，命中率极低，间隙停滞 |
| ZOS-US (均匀策略采样) | 1000 | \(1.15 \times 10^{0}\) | 5.2 | 即使样本增至1000，长策略仍主导，无法收敛 |
| ZOS-UL (均匀长度分层) | 100 | \(8.5 \times 10^{-2}\) | 2.3 | 显著优于均匀采样，拉平长度层级权重 |
| ZOS-UL (均匀长度分层) | 1000 | \(1.8 \times 10^{-3}\) | 5.5 | 逼近精确 LMO 精度，耗时仅精确版的 1/7 |
| ZOS-HL (调和长度分层) | 100 | \(4.2 \times 10^{-2}\) | 2.2 | 倾斜偏好短路径，小样本下收敛显著快于 UL |
| ZOS-HL (调和长度分层) | 1000 | \(1.1 \times 10^{-3}\) | 5.4 | 完美贴合精确 ZDD 表现，FW 间隙达到 \(10^{-3}\) |
关键发现¶
- 针对 NP-hard 策略空间，精确动态规划与分层采样存在明确的分界线：当 ZDD 节点数在 \(10^5\) 以内时，精确 ZOS-ZDD 兼具极快速度与确定性最优；而当 ZDD 规模达到 \(10^6\) 以上时，基于 HL 的分层采样在 \(m=1000\) 预算下能取得近 7 倍的速度优势，且精度完全不损失。
- 均匀随机采样在组合博弈中存在明显的“结构性失效”，这是因为非平衡组合策略结构中长路径数量呈组合爆炸，掩盖了真正承载拥塞均衡的低成本短路径；长度分层采样从数学上打破了这一偏差。
- 内存占用的锐减是免求导框架最显著的工程优势：Diff 基线随着内层展开需要维持庞大的反向图，在场景 3 吞噬了 194 GiB 内存，而 ZO-Stackelberg 峰值内存全程低于 1.7 GiB。
亮点与洞察¶
- 算法视角转变：将不可导的复杂双层组合优化问题转化为黑盒零阶更新回路，成功解开了内层反向传播与组合策略非平滑性之间的结构性死结。
- 即插即用的模块化预言机：内层 Frank-Wolfe 与外层更新解耦，任意底层的组合求解器（Dijkstra、ZDD-DP 或采样生成器）均可无缝嵌入，无需推导任何针对下层算法的伴随矩阵或雅可比矩阵。
- 可复用的长度分层重加权技术：在利用决策图对非负权重图结构进行带约束路径采样时，通过自底向上统计路径长度并实施调和分层抽样，可直接迁移到强化学习离散轨迹生成、组合式因果推断等大状态空间探索问题。
局限与展望¶
- 维度扩展瓶颈：外层依赖有限差分零阶梯度估计，其估计方差和理论样本复杂度随领导者控制参数维度 \(k\) 呈多项式增长（主定理复杂度包含 \(k^{3/2}\) 项），对于上千维度的超高维控制参数场景收敛步数可能会大幅上升。
- 强凸势函数依赖：收敛定理的连续稳定性与二次增长条件依赖于链路成本函数对负荷的局部严格递增性；在高度退化、存在大量零边际拥塞成本的极端网络下，二次增长假设可能失效。
- 未来方向：探索结合拟牛顿方向或坐标下降的低秩降维零阶优化器，并将框架推广至多代理领导者竞争的非合作多层博弈场景。
相关工作与启发¶
- vs Sakaue & Nakamura (2021) (Diff)：Sakaue 等人通过对 ZDD 内部状态转移引入 Softmin 光滑化近似，利用自动微分反向穿越内层 FW 迭代展开图；本文完全舍弃反向传播与平滑化代理，直接在真实非光滑原目标上通过零阶球面差分优化，速度提升 20 至 1000 倍，消除了近 99% 的显存占用并保证真实超目标的 Goldstein 驻点收敛。
- vs Kerdreux et al. (2018) (Subsampled FW)：Kerdreux 等人分析了基于均匀原子包含的随机采样 Frank-Wolfe，其收敛率依赖于全集合上的均匀命中率；本文将理论推广至非均匀任意分布，抽象出统一的最优解命中概率 \(\kappa_m\)，并结合 ZDD 提出了专为图组合问题定制的长度分层与调和加权采样策略。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 成功将零阶优化与组合决策图预言机结合，彻底避开了组合拥塞博弈中长久困扰学术界的可微均衡近似失真问题。
- 实验充分度: ⭐⭐⭐⭐⭐ 覆盖从多项式类到 NP-hard 各层级基准路网，严密验证了单步耗时、显存消耗、对偶间隙及社会成本等多维指标。
- 写作质量: ⭐⭐⭐⭐⭐ 概念阐述清晰，数学符号规范，附录中的反例设计与收敛证明逻辑闭环极其严谨。
- 价值: ⭐⭐⭐⭐⭐ 为运筹学网络设计、交通配流收费管控和大规模强化学习双层优化提供了极具实用价值的工程范式。