IGT-OMD：延迟反馈下决策聚焦学习中的隐式梯度传输

# IGT-OMD：延迟反馈下针对决策聚焦学习的隐式梯度传输 来源：https://arxiv.org/html/2605.12693 Benjamin Amoh Geoffrey Parker Wesley Marrero 塞耶工程学院，达特茅斯学院 benjamin\.k\.amoh\.th@dartmouth\.edu ###### 摘要 决策聚焦学习端到端地训练预测模型以最小化下游决策损失，但在在线设置中会遭遇延迟反馈：经过多次环境交互后，结果才可能到达。我们识别出*陈旧性放大*，这是延迟下双层优化特有的一种失败模式，其中梯度陈旧性与内部求解器敏感性耦合，导致遗憾超出单层延迟理论的范围。我们证明，任何黑盒延迟优化器都会因内部求解器近似误差而产生不可约的遗憾成本，并且如果没有双层感知修正，梯度陈旧性会贡献一个二次增长的传输误差。我们的算法IGT-OMD将隐式梯度传输应用于在线镜像下降中的超梯度，利用存储的内部解在当前参数处重新评估陈旧梯度。该方法将传输误差从对延迟的二次依赖降低为线性依赖，并首次实现了具有队列长度自适应步长的延迟双层优化的次线性遗憾界。受控实验提供了一个*机制特征*：传输收益在单位延迟时为0.0%（根据构造），并单调增长至五十轮时的9.5%（p<0.001），隔离了修正的效果。在《魔兽争霸》最短路径上，IGT-OMD相比D-FTRL/两阶段基线将决策损失最优性差距降低了15–36%；在线性二次型调节器基准测试中，它在所有延迟下保持恒定的最大稳定学习率，而双层无感知方法则退化高达9.3倍。

## 1 引言

在许多运营场景中（从库存管理到能源调度再到个性化医疗），预测模型将其预测结果输入下游优化求解器，该求解器的解决方案随后被部署。决策聚焦学习（DFL）端到端地训练此类模型，以*决策损失*为目标，而非替代预测误差[8,34,20]。由此产生的训练问题本质上是双层的：*外层*调整预测器参数θ（例如神经网络权重），而*内层*求解最优决策w*(θ)（例如控制策略或运输计划）。在在线部署中，反馈常常是延迟的。在环境交互（即轮次）t时做出的决策只有在轮次t+d_t后才产生可观察的结果反馈，其中延迟d_t可能变化。在任何给定轮次，可能仍有若干过去决策在等待反馈；我们称这个集合为*队列*，其大小（即*队列长度*）为σ_t，并用σ_max表示其最坏情况值。单层延迟优化器，如延迟跟随正则化领导者（D-FTRL；[15,29]）和鲁棒在线镜像下降（OMD；[27]），通过修正外部参数漂移‖θ_t - θ_{t-d_t}‖来处理这一挑战。

**陈旧性放大：为何双层延迟更难。** 在单层在线凸优化（OCO）中，陈旧梯度是一个与优化器状态无关的有界扰动。而双层设置在结构上有所不同：F(θ) = L_true(w*(θ); θ)的超梯度依赖于内部最小化器w*(θ)，而w*(θ)会随着θ的变化而漂移。由已经漂移的内部解产生的反馈引入了与外部参数累积变化成比例的梯度误差——*陈旧性放大*。这在定理2中被形式化为两个结构性效应：一个不可约的内部求解器遗憾下限，以及在没有双层感知修正的情况下每轮传输误差与队列长度成二次关系。

**IGT-OMD：我们如何修复它。** 我们算法的关键思想是*重新评估*陈旧超梯度在当前参数处的值，而不是直接使用它们。当来自过去轮s的反馈到达时，我们的算法已经存储了一个内部解w_s和伴随向量v_s^*，可以在当前θ_t处以低成本重新计算超梯度，而无需重新求解内部问题。通过隐式梯度传输（IGT）[1]累积这些修正，将平方总漂移‖θ_t - θ_{t-d_t}‖^2替换为每步变化平方和∑_s‖θ_{s+1} - θ_s‖^2，这比σ_max小一个因子。将此修正后的梯度嵌入在线镜像下降（OMD），并采用跟踪运行队列包络的自适应步长（受延迟微分方程（DDE）稳定性分析[35]启发），得到我们的算法IGT-OMD。

**贡献。** (1) *算法。* IGT-OMD以每未解决轮次O(pq)的成本修正陈旧超梯度，无需重新求解内部问题（算法1）。 (2) *分析。* 我们证明了第一个双层延迟遗憾界O(√(Tσ_max) + Tε_inner^2)（定理1），一个显示出Ω(Tε_inner^2)是紧界（定理2）的陈旧性放大下界，一个将陈旧性与内部求解器质量解耦的内循环冷漠分解（定理3），以及DDE稳定性分析（命题1-2）。 (3) *实验。* 在LQR上，IGT-OMD在所有延迟下保持恒定稳定性；在《魔兽争霸》上，它将最优性差距相比D-FTRL/两阶段基线降低了15–36%。一个受控优化器实验证实了预测的机制特征，在d=50时提升9.5%（p<0.001）。

### 1.1 相关工作

表1将IGT-OMD与相关先前工作进行对比。先前的DFL方法[8,33,34,31,6]解决了双层训练问题，但假设即时反馈。从概念上讲，DFL是任务驱动的双层优化的一个子类：内部问题是下游决策层，外部模型在实现的决策损失上训练。在这一视角下，我们将[23]视为更接近DFL风格的先前工作，而非通用双层优化。单层延迟优化器[15,27,9,12,28,26]修正外部参数漂移，但将目标视为黑盒函数，因此在应用于双层问题时容易受到陈旧性放大的影响（定理2）。双层优化方法[10,14,32,19,21]处理嵌套结构，但假设同步更新。梯度传输[1]最初是为单层强化学习开发的；DDE稳定性分析[35]应用于分布式随机梯度下降。没有先前方法同时处理双层结构和延迟反馈。虽然一些单层延迟方法采用*延迟自适应*步长（按轮次或累积延迟缩放），但其调度未考虑内部求解器敏感性——这是双层目标独有的因素。我们的算法通过将梯度传输从单层策略梯度扩展到双层超梯度，并将结果嵌入具有*队列长度自适应*步长（针对双层结构校准）的OMD中，填补了这一空白。

表1：与相关工作的比较。IGT-OMD是第一个双层延迟优化器。

| 类别 | 方法 | 延迟 | 双层 | 自适应 | 未解决问题 |
|------|------|------|------|--------|------------|
| 任务驱动双层 | SPO+ [8] | ✗ | ✓ | ✗ | 无延迟 |
| 在线DFL | [6] | ✗ | ✓ | ✓ | 无延迟 |
| 面向控制的MBRL | [23] | ✗ | ✓ | ✗ | 无延迟 |
| 单层延迟OCO | D-FTRL [15] | ✓ | ✗ | ✓ | 陈旧性放大 |
| 鲁棒OMD | [27] | ✓ | ✗ | ✓ | 无双层 |
| DORM+ | [9] | ✓ | ✗ | ✓ | 单层 |
| 通用双层（无延迟） | 在线双层 [14] | ✗ | ✓ | ✗ | 无延迟 |
| BSA [10] | ✗ | ✓ | ✗ | 离线 |
| 梯度传输 | IGT [1] | ✓ | ✗ | ✗ | 单层RL |
| DDE分析 | 差分延迟分析 [35] | ✓ | ✗ | ✗ | 分布式SGD |
| 我们的工作 | IGT-OMD | ✓ | ✓ | ✓ | — |

## 2 问题形式化

现在形式化延迟反馈下的在线双层优化问题。我们的符号总结在附录A的表LABEL:tab:notation中。

### 2.1 带延迟反馈的在线双层优化

考虑一个学习器每轮调整预测模型，但结果反馈在若干轮后才到达。每次更新的梯度信号因此基于过去的参数——我们下面形式化的延迟双层反馈循环。

在与环境的每次交互（即轮次）t=1,...,T中，学习器持有外层预测器参数θ_t ∈ Θ ⊆ ℝ^p，并近似求解内部问题w*(θ_t) = argmin_{w∈W⊆ℝ^q} L_model(w; θ_t)，其中L_model是基于模型的决策目标，p是预测器维度，q是决策维度。近似解w_t通过从先前解w_{t-1}出发执行K ∈ ℕ_{>0}步梯度下降获得，产生内部求解器误差‖w_t - w*(θ_t)‖ ≤ ε_inner。学习器执行w_t，在d_t ≥ 0轮后，环境揭示一个结果对象z_t，它决定了实现的损失。在轮t，新到达的反馈为A_t = {s : s+d_s = t}，已到达的观察集为O_t = {(s,z_s) : s+d_s ≤ t}，仍在等待反馈的轮次队列为Q_t = {s ≤ t : s+d_s > t}，队列长度σ_t = |Q_t|，包络σ̄_t = max_{r≤t} σ_r。仅使用已到达的反馈，学习器更新θ_{t+1}。性能度量是*决策遗憾*：Regret_T^{dec} = ∑_{t=1}^T L_true(w_t; θ_t) - min_{θ∈Θ} ∑_{t=1}^T L_true(w*(θ); θ)，它将学习器的累积决策损失与事后最佳固定预测器的累积损失进行比较。

### 2.2 通过隐式微分的超梯度计算

超梯度——决策损失对预测器参数的导数——通过隐函数定理[7]分解为显式（直接）和隐式（通过内部求解器）两部分。为避免完整雅可比矩阵逆O(q^3)成本，我们遵循[23]引入一个伴随向量v* ∈ ℝ^q，它满足线性系统 H_w v* = ∇_w L_true(w*; θ)，其中H_w := ∇²_ww L_model(w*; θ)是内部目标的Hessian矩阵。伴随向量通过共轭梯度法[11]近似计算。超梯度则为：

g_t(θ) = ∇_θ L_true|_{w固定} - [∇_θ ∇_w L_model(w*; θ)]^⊤ v*,    (1)

其中第一项捕捉θ对损失的直接影响，第二项捕捉内部求解器决策随θ变化而产生的间接影响。

**延迟下的重新评估。** 当来自过去轮s的反馈在轮t > s到达时，算法可利用存储的内部解w_s、观察到的反馈z_s和伴随向量v_s^*，以O(pq)成本在当前参数θ_t处重新评估超梯度，而无需重新求解内部问题：

g_s(θ_t) = ∇_θ L_true(w_s; θ_t)|_{w固定} - [∇_θ ∇_w L_model(w_s; θ_t)]^⊤ v_s^*.