Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization

arXiv:2608.16216v1 Announce Type: new 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{Tsigma_{max}}, where sigma_{max} is the peak backlog, although unlimited tracking admits the sharper sqrt{d_{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_{tot}}), with only an explicit restart factor E_C; a public constant-factor peak bound removes this factor while d_{tot} remains unknown. Under strong convexity, the same interface yields the temporal cost H_A(d)=sum_t sigma_t/(A+t). Two delay vectors with identical delay multisets, d_{tot}, sigma_{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 Cge ln T+1 and do not constitute a complete capacity minimax characterization.

Source: arXiv cs.LG | 2026-08-18