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

• URL: http://arxiv.org/abs/2608.16216v1
• Date: Mon, 17 Aug 2026 07:49:51 GMT
• Title: Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
• Abstract summary: We introduce a scheduler-side conditional-energy interface that separates rate adaptation from the one-point perturbation filtration.<n>Two delay vectors with identical delay multisets, $d_mathrmtot$, $_max$, and capacity can nevertheless have banditly different minimax regret showing that aggregate timing matters under curvature.
• Score: 11.872017840435428
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits [13.075031222564535]
  Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs.<n>We study the trade-off between worst-case regret $mathcalR_K,T$ and instability $mathcal S_K,T$, defined as the largest standard deviation of a terminal pull count, for $K$ arms and $T$ rounds.
  arXiv  Detail & Related papers  (2026-08-18T14:38:47Z)
• From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting [0.1624454100511275]
  Gambling-based sequential tests and Blackwell approachability are linked by a rate-explicit reduction through support-functions.<n>We prove the exact pathwise identity $$ dist(bar r_T,S) =frac1Tsum_t=1Tq_t+fracReg_TT.
  arXiv  Detail & Related papers  (2026-08-10T11:23:30Z)
• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Capacity-Constrained Online Convex Optimization with Delayed Feedback [58.59385794080679]
  We study delayed online convex optimization (OCO) under a hard capacity constraint.<n>We find that for first-order feedback, capacity $C = (log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors.<n>For bandit feedback, the regret rates are modulated by powers of $(1 + _textmax/C)$, where $_textmax$ is the maximum number of pending observations at any time.
  arXiv  Detail & Related papers  (2026-06-10T06:37:06Z)
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  We introduce a continuous-time model under which regret decomposes into a delay-independent learning term and a delay-induced drift term.<n>For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching state-of-the-art first-order rates.
  arXiv  Detail & Related papers  (2026-02-02T18:17:34Z)
• Exploiting Curvature in Online Convex Optimization with Delayed Feedback [6.390468088226495]
  We study the online convex optimization problem with curved losses and delayed feedback.<n>We propose a variant of follow-the-regularized-leader that obtains regret of order $minsigma_maxln T, sqrtd_mathrmtot$.<n>We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning.
  arXiv  Detail & Related papers  (2025-06-09T09:49:54Z)
• Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
  We study online learning with oblivious delays under a novel clairvoyance'' that limits how many past rounds can be tracked simultaneously for delayed feedback.<n>Our algorithms achieve minimax regrets across all capacity levels, with performance degrading gracefully under suboptimal capacity.
  arXiv  Detail & Related papers  (2025-03-25T17:20:39Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  bandit convex optimization (BCO) with delayed feedback, where only the loss value of the action is revealed under a delay. We develop a novel algorithm, and prove that it enjoys a regret bound of $O(sqrtnT3/4+sqrtdT)$ in general. We show that the proposed algorithm can improve the regret bound to $O((nT)2/3log/3T+dlog T)$ for strongly convex functions.
  arXiv  Detail & Related papers  (2024-02-14T13:08:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.