Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
Organizations: Department of Intelligent Communication, School of Journalism and Communication, Minzu University of China, Beijing, China · ZeeLin (Beijing) Technology Co., Ltd., Beijing, China · School of Journalism and Communication, Tsinghua University, Beijing, China · College of AI, Tsinghua University, Beijing, China
Abstract
What is the right delay complexity when a learner can track only pending feedback items and discarded feedback is permanently lost? Existing one-point bandit convex optimization guarantees in this model pay , where is the peak backlog, although unlimited tracking admits the sharper 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 , with only an explicit restart factor ; a public constant-factor peak bound removes this factor while remains unknown. Under strong convexity, the same interface yields the temporal cost . Two delay vectors with identical delay multisets, , , 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 and do not constitute a complete capacity minimax characterization.
Figures & tables
| Setting | Closest benchmark | This work | Role / limitation |
|---|---|---|---|
| Convex BCO | Upper; endpoint matched up to | ||
| Strongly convex BCO | Upper; public backlog bound | ||
| Temporal geometry | Aggregate summaries assign the same scale to the early/late pair | versus | Minimax separation; |
| Fixed-delay capacity | No continuous-domain capacity lower in the exact contract | Lower endpoint; not a full match |
| Line of work | one-point convex | hard pathwise cap | permanent loss | principal control quantity |
|---|---|---|---|---|
| Classical delayed OCO [ 14 , 15 , 16 ] | no | no | no | delay count or total delay |
| Delayed BCO [ 22 , 23 ] | yes | no | no | or |
| Temporal feedback graphs [ 25 ] | no | no | no | temporal graph complexity |
| Capacity-constrained finite actions [ 42 ] | no | yes | yes | capacity–delay throughput |
| Capacity-constrained OCO/BCO [ 1 ] | yes | yes | yes | , , weighted backlog |
| This paper, convex result | yes | yes | yes | conditional energy and |