cs.LGAug 17, 2026

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

Authors: Anling Xiang, Yuwen Yang, Yang Shen

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 CC pending feedback items and discarded feedback is permanently lost? Existing one-point bandit convex optimization guarantees in this model pay Tσmax⁡\sqrt{Tσ_{\max}}, where σmax⁡σ_{\max} is the peak backlog, although unlimited tracking admits the sharper dtot\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(ECdtot)O(\sqrt{E_C d_{\mathrm{tot}}}), with only an explicit restart factor ECE_C; a public constant-factor peak bound removes this factor while dtotd_{\mathrm{tot}} remains unknown. Under strong convexity, the same interface yields the temporal cost HA(d)=∑tσt/(A+t)H_A(d)=\sum_t σ_t/(A+t). Two delay vectors with identical delay multisets, dtotd_{\mathrm{tot}}, σmax⁡σ_{\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≥ln⁡T+1C\ge \ln T+1 and do not constitute a complete capacity minimax characterization.

Figures & tables

Explore similar work

CardsList
  1. Capacity-Constrained Online Convex Optimization with Delayed Feedback

    Jun 10, 2026Alexander Ryabchenko, Idan Attias, Daniel M. RoyOnline Convex OptimizationBandit Convex Optimization

  2. Near-Optimal Stochastic Linear Bandits with Delay

    Jun 15, 2026Ofir Schlisselberg, Mengxiao Zhang, Yishay MansourBandits with Delayed FeedbackContextual Bandits

  3. Optimally Pacing Budget Spending and Learning

    Oct 8, 2026Mark Braverman, Jingyi Liu, Jieming Mao +2Online LearningOnline Resource Allocation