- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies online decision-focused learning (DFL) with delayed feedback. In this setting, model parameters and their associated decisions may have changed by the time feedback arrives, making historical gradients outdated. To address this issue, the authors propose Implicit Gradient Transport Online Mirror Descent (IGT-OMD). The method combines gradients from newly arrived feedback with correction terms that account for changes in historical gradients as model parameters evolve. This improves the use of delayed feedback. The authors develop two implementations. Frozen Transport reduces computational costs by caching historical decisions and gradient-related information. Full Re-evaluation recomputes decisions and their gradients using the current model. On the theoretical side, the authors establish a regret upper bound for Frozen Euclidean IGT-OMD under assumptions of stationarity, convexity, and boundedness. They analyze how delays, inner optimization accuracy, and historical gradient corrections affect gradient estimation errors. They also derive a sufficient iteration complexity for the inner solver and learning rate stability conditions for a specific quadratic model. In the experiments, the authors evaluate the algorithm on LQR, Warcraft shortest path, and Sinkhorn optimal transport tasks, focusing on stability, decision quality, and computational cost. In the Sinkhorn experiments with independent random seeds, Full Re-evaluation + Adam + IGT reduces cumulative decision loss by 10.81% compared with a matched baseline that uses only newly arrived feedback at a delay of 50. However, its training update time increases to approximately 40.28 times that of the baseline. The results show that the benefits of gradient transport depend on the optimizer, gradient computation method, and learning rate. They also reveal a clear trade-off between decision quality and computational cost.
Critical strengths
S1. The method offers some novelty. To address the issue of outdated gradients in bilevel optimization with delayed feedback, the authors propose IGT-OMD based on historical gradient differences. They also develop two implementations, Frozen Transport and Full Re-evaluation, offering different trade-offs between computational efficiency and gradient accuracy.
S2. The theoretical analysis is relatively comprehensive. Under clearly stated assumptions, the paper provides regret bounds, hypergradient error bounds, and learning rate stability conditions. It also analyzes inner optimization accuracy and iteration complexity, providing theoretical support for the proposed algorithm.
S3. The experimental evaluation is reasonably thorough. The authors evaluate the method on three tasks: LQR, Warcraft, and Sinkhorn. They use independent random seeds and paired experiments to validate the main performance improvements. They also report computational costs, which strengthens the credibility of the experimental findings.
Critical weaknesses
W1. There is a gap between the theoretical analysis and the main experimental results. The regret and stability analyses mainly focus on Frozen Euclidean IGT-OMD under strong assumptions, while the most significant experimental gains come from Full Re-evaluation + Adam. Therefore, the current theory does not fully explain or guarantee the performance improvements observed in practice.
W2. The fairness of baseline comparisons remains a concern. Comparisons with methods such as DOOMD involve different optimizers and learning rate settings. Moreover, the best baseline learning rate lies at the boundary of the search range, suggesting that the baseline may not have been fully tuned. This raises questions about the claimed performance advantages over existing methods.
W3. The high computational cost raises concerns about practical applicability. Although Full Re-evaluation reduces decision loss by 10.81% at a delay of 50, its training update time increases by a factor of 40.28. In addition, the effectiveness of gradient transport is sensitive to the optimizer and learning rate. The lack of comparisons under equal computational budgets further limits the assessment of its practical value.
Questions for authors
1. Regarding the consistency between theory and experiments. The theoretical guarantees mainly focus on Frozen Euclidean IGT-OMD, while the most significant experimental gains come from Full Re-evaluation + Adam. Could the authors further explain how the current theory supports these experimental results and whether a verifiable theoretical connection exists between the two methods?
2. DOOMD still achieves its best performance at the upper boundary of the learning rate search range, even after the range is expanded. Could the authors clarify whether the baseline has been sufficiently tuned and whether further learning rate tuning could significantly narrow the performance gap?
3. Full Re-evaluation requires approximately 40 times the training update cost at a delay of 50. Could the authors provide performance comparisons under equal computational budgets to demonstrate whether the advantages of IGT still hold?
5 comments
Weakness 3/ Question 3 answered
W3 / Q3. Computational cost, sensitivity to the optimizer and learning rate, and equal budgets.
The 40.28× factor. It came from our original implementation, which recomputed stored examples one at a time. Computing them in one batched call, IGT's training time is 3.2×, 3.5× and 5.4× that of arrival-only learning at delays 5, 10 and 50 (median paired ratios; at delay 50, 19.8 s versus 3.6 s for 1,000 decisions).
Sensitivity to the learning rate. Mean cumulative loss on the calibration seeds, for each method at each tested rate:
| Delay, method | Rate 0.0003 | Rate 0.001 | Rate 0.003 | Rate 0.01 |
|---|---|---|---|---|
| Delay 5, arrival-only | 676.1 | 576.9 | 671.7 | 913.7 |
| Delay 5, IGT | 665.8 | 546.4 | 531.5 | 657.0 |
| Delay 50, arrival-only | 708.2 | 616.7 | 702.7 | 921.7 |
| Delay 50, IGT | 689.6 | 554.6 | 510.7 | 503.9 |
IGT has lower loss than arrival-only at every tested rate and delay, and it tolerates large rates far better: at rate 0.01, IGT's loss is 657.0 versus 913.7 at delay 5 and 503.9 versus 921.7 at delay 50. Tuning each method's rate therefore preserves IGT's advantage, as the held-out comparison in W1 / Q1 confirms (6.44–17.99%).
Sensitivity to the optimizer. With plain gradient steps at the same rate as the arrival-only learner, transport can hurt, as in our Warcraft runs with plain SGD. Proposition 2 predicts this: with plain gradient steps, the buffered changes enlarge the step along high-curvature directions, so the largest stable rate shrinks from without transport to with it. Our plain-gradient comparisons used one shared rate for both arms, so they did not give transport the smaller rate this condition requires. With Adam and separately tuned rates, the gain holds at every delay (W1 / Q1).
Equal computational budgets.
On five untouched seeds, with 1,000 decisions on 10×10 transport problems, the same feedback and inputs for every method, and each seed's methods sharing the same two-CPU allocation (mean cumulative loss · median training time; DF-OGD tuned until all four of its settings were bracketed, see our response to Reviewer YPWM, Q3):
| Method | Delay 5 | Delay 10 | Delay 50 |
|---|---|---|---|
| Arrival-only Adam | 583.1 · 3.4 s | 588.8 · 4.0 s | 626.9 · 3.6 s |
| IGT (batched) | 544.0 · 10.7 s | 528.3 · 14.1 s | 513.9 · 19.8 s |
| DF-OGD (fully tuned) | 590.6 · 31.9 s | 597.9 · 36.1 s | 632.4 · 34.2 s |
| FTL, 2 steps | 454.5 · 54.2 s | 460.0 · 62.0 s | 493.3 · 57.2 s |
| IGT's share of FTL's improvement over arrival-only | 30% | 47% | 85% |
| IGT's training time relative to FTL's | 0.20 | 0.23 | 0.35 |
Follow-the-leader (FTL), the unperturbed form of DF-FTPL (Capitaine et al., 2026), re-optimizes the predictor over all revealed examples every round. Its cost per round grows with the number of revealed examples, while IGT's stays fixed at the buffer size. Between the arrival-only control and FTL, IGT's improvement grows with delay. At delay 50 it achieves 85% of FTL's improvement over arrival-only in about a third of FTL's training time. IGT is also better and faster than the fully tuned DF-OGD at every delay. The batched implementation computes the same per-example gradients as the original one (relative difference about ) and is 1.4×, 2.1× and 6.6× faster at delays 5, 10 and 50.
Thanks for the response and the additional experiments. They address some of my concerns, but there is still no theoretical guarantee for Full Re-evaluation + Adam, or proof that gradient transport performs better than arrival-only learning. So I'll keep my rating unchanged for now.
Weakness and Questions 1-2 answered here.
Thank you for the precise summary and questions. "IGT" below is full re-evaluation with Adam, the configuration of our main transport results. We answer each weakness together with its matching question, in order.
W1 / Q1. Connection between the theory and the experiments.
The analyzed and the empirical methods use the same gradient estimate: each stored example contributes its gradient at arrival and afterwards only the changes, so its total contribution always equals its most recently computed gradient. They differ in two respects, the decision computation (frozen versus full) and the optimizer that turns this estimate into a parameter step (plain gradient steps versus Adam). The theory connects to the experiments at three levels.
W2 / Q2. Baseline fairness: optimizers, learning rates and tuning.
We extended DOOMD's search to rates {0.003, 0.01, 0.03, 0.1, 0.3, 1} for both hint choices, on five calibration seeds per delay. The selected rates are 0.1, 0.03 and 0.03 at delays 5, 10 and 50, all without the hint, and each is now worse at both neighbouring rates, so the best tested rate lies inside the grid. We froze these choices and then evaluated on five new seeds with common inputs:
Each percentage is the average over seeds of the per-seed reduction; all three survive Holm correction.
Two comparisons separate the optimizer from the method. First, with Adam held fixed and each method's learning rate tuned separately, IGT still lowers loss by 6.44–17.99% (W1 / Q1, point 3). Second, on five untouched seeds our arrival-only Adam control is within 1.6% of DF-OGD, a plain-gradient method whose four settings were tuned until all were bracketed, while IGT is 7–19% better than both (response to Reviewer YPWM, Q3). The advantage therefore comes from refreshing stored examples, not from the choice of optimizer.