# Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs

arXiv: https://arxiv.org/abs/2503.19856 · HTML: https://mlsanity.com/paper/2503.19856/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 50 references that are in the map.
- First posted on arXiv 25 Mar 2025.

## Builds on (most cited first, 18 of 18)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [No Weighted-Regret Learning in Adversarial Bandits with Delays](https://mlsanity.com/paper/2103.04550/) (2021)
- [Scale Free Adversarial Multi Armed Bandits](https://mlsanity.com/paper/2106.04700/) (2021)
- [Gradient-free Online Learning in Games with Delayed Rewards](https://mlsanity.com/paper/2006.10911/) (2020)
- [A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays](https://mlsanity.com/paper/2308.10675/) (2023)
- [Delayed Bandits: When Do Intermediate Observations Help?](https://mlsanity.com/paper/2305.19036/) (2023)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning](https://mlsanity.com/paper/2301.10500/) (2023)
- [Any-Order Online Interval Selection](https://mlsanity.com/paper/2303.06127/) (2023)

## Built on by (most cited first, 6 of 6)

- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Decentralized Online Convex Optimization with Unknown Feedback Delays](https://mlsanity.com/paper/2601.07901/) (2026)
- [Reinforcement Learning with Action-Triggered Observations](https://mlsanity.com/paper/2510.02149/) (2025)
- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization](https://mlsanity.com/paper/2608.16216/) (2026)

## Abstract (arXiv)

We study online learning with oblivious losses and delays under a novel ``capacity constraint'' that limits how many past rounds can be tracked simultaneously for delayed feedback. Under ``clairvoyance'' (i.e., delay durations are revealed upfront each round) and/or ``preemptibility'' (i.e., we can stop tracking previously chosen round feedback), we establish matching upper and lower bounds (up to logarithmic terms) on achievable regret, characterizing the ``optimal capacity'' needed to match the minimax rates of classical delayed online learning, which implicitly assume unlimited capacity. Our algorithms achieve minimax-optimal regret across all capacity levels, with performance gracefully degrading under suboptimal capacity. For K actions and total delay D over T rounds, under clairvoyance and assuming capacity C = Omega(log(T)), we achieve regret widetildeTheta(√TK + DK/C + Dlog(K)) for bandits and widetildeTheta(√(D+T)log(K)) for full-information feedback. When replacing clairvoyance with preemptibility, we require a known maximum delay bound dmax, adding widetildeO(dmax) to the regret. For fixed delays d (i.e., D=Td), the minimax regret is Theta(√TK(1+d/C)+Tdlog(K)) and the optimal capacity is Theta(minK/log(K),d) in the bandit setting, while in the full-information feedback setting, the minimax regret is Theta(√T(d+1)log(K)) and the optimal capacity is Theta(1). For round-dependent and fixed delays, our upper bounds are achieved using novel preemptive and non-preemptive scheduling policies, based on Pareto-distributed proxy delays, and batching techniques, respectively. Crucially, our work unifies delayed bandits, label-efficient learning, and online scheduling frameworks, demonstrating that robust online learning under delayed feedback is possible with surprisingly modest tracking capacity.