Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
2026-08-17 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a learning problem where feedback is delayed and only a limited number can be tracked before older feedback is permanently lost. They improve previous methods by introducing a new way to manage the timing and importance of delayed feedback, achieving better performance guarantees related to total delay and tracking capacity. They show that the timing of delays matters more than just their total amount when the learning problem has strong curvature, and they provide lower bounds on what is achievable given the tracking constraints. Their results require a minimum tracking capacity and do not fully characterize the best possible trade-offs.
bandit convex optimizationdelayed feedbackcapacity constraintsregret boundsstrong convexityrandomized admissionminimax regretperturbation filtrationquery budgetdelay complexity
Authors
Anling Xiang, Yuwen Yang, Yang Shen
Abstract
What is the right delay complexity when a learner can track only $C$ pending feedback items and discarded feedback is permanently lost? Existing one-point bandit convex optimization guarantees in this model pay $\sqrt{Tσ_{\max}}$, where $σ_{\max}$ is the peak backlog, although unlimited tracking admits the sharper $\sqrt{d_{\mathrm{tot}}}$ dependence on total delay. We introduce a scheduler-side conditional-energy interface that separates rate adaptation from the one-point perturbation filtration and handles the dependent importance weights created by randomized admission. Under the same semi-clairvoyant oracle and pathwise hard-capacity contract, this yields an untuned learner whose delay term scales as $O(\sqrt{E_C d_{\mathrm{tot}}})$, with only an explicit restart factor $E_C$; a public constant-factor peak bound removes this factor while $d_{\mathrm{tot}}$ remains unknown. Under strong convexity, the same interface yields the temporal cost $H_A(d)=\sum_t σ_t/(A+t)$. Two delay vectors with identical delay multisets, $d_{\mathrm{tot}}$, $σ_{\max}$, and capacity can nevertheless have polynomially different minimax regret, showing that timing matters under curvature even when aggregate delay summaries agree. Finally, a continuous hard family converts tracking capacity into a zeroth-order query budget and gives a complementary capacity-starvation lower endpoint. The upper bounds require $C\ge \ln T+1$ and do not constitute a complete capacity minimax characterization.