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

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.