Search papers, labs, and topics across Lattice.
This paper investigates the delay complexity in capacity-constrained delayed bandit optimization, focusing on the limitations of existing one-point bandit convex optimization guarantees. By introducing a scheduler-side conditional-energy interface, the authors achieve a delay term that scales as \(O(\sqrt{E_C d_{\mathrm{tot}}})\) while addressing the challenges posed by dependent importance weights from randomized admission. The findings reveal that even with identical aggregate delay summaries, different timing can lead to polynomially distinct minimax regret, emphasizing the critical role of timing in optimization under curvature.
Identical delay summaries can yield vastly different regret outcomes, highlighting the crucial impact of timing in bandit optimization.
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.
