Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915359814057984 |
|---|---|
| author | Ryabchenko, Alexander Attias, Idan Roy, Daniel M. |
| author_facet | Ryabchenko, Alexander Attias, Idan Roy, Daniel M. |
| contents | 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 = Ω(\log(T))$, we achieve regret $\widetildeΘ(\sqrt{TK + DK/C + D\log(K)})$ for bandits and $\widetildeΘ(\sqrt{(D+T)\log(K)})$ for full-information feedback. When replacing clairvoyance with preemptibility, we require a known maximum delay bound $d_{\max}$, adding ${\widetilde{O}(d_{\max})}$ to the regret. For fixed delays $d$ (i.e., $D=Td$), the minimax regret is $Θ(\sqrt{TK(1+d/C)+Td\log(K)})$ and the optimal capacity is $Θ(\min\{K/\log(K),d\})$ in the bandit setting, while in the full-information feedback setting, the minimax regret is $Θ(\sqrt{T(d+1)\log(K)})$ and the optimal capacity is $Θ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19856 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs Ryabchenko, Alexander Attias, Idan Roy, Daniel M. Machine Learning 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 = Ω(\log(T))$, we achieve regret $\widetildeΘ(\sqrt{TK + DK/C + D\log(K)})$ for bandits and $\widetildeΘ(\sqrt{(D+T)\log(K)})$ for full-information feedback. When replacing clairvoyance with preemptibility, we require a known maximum delay bound $d_{\max}$, adding ${\widetilde{O}(d_{\max})}$ to the regret. For fixed delays $d$ (i.e., $D=Td$), the minimax regret is $Θ(\sqrt{TK(1+d/C)+Td\log(K)})$ and the optimal capacity is $Θ(\min\{K/\log(K),d\})$ in the bandit setting, while in the full-information feedback setting, the minimax regret is $Θ(\sqrt{T(d+1)\log(K)})$ and the optimal capacity is $Θ(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. |
| title | Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2503.19856 |