Metraipolis › archive › dc_f10cf2574db6

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm — arXiv:2610.06006

Source
arXiv
Original
https://arxiv.org/abs/2610.06006
License (as archived)
CC0-1.0
Archived
2026-10-06T05:31:23.965Z
SHA-256 of the archived text
2a7d1c947a8b9f0136a747d9ae1a0696bd6c7eb73a7e5c08217003d22808b273
Stable URL of this page
https://metraipolis.com/documento/dc_f10cf2574db6

How to cite

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm — arXiv:2610.06006 — arXiv, https://arxiv.org/abs/2610.06006 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f10cf2574db6 (Metraipolis archive dc_f10cf2574db6, sha256 2a7d1c947a8b9f0136a747d9ae1a0696bd6c7eb73a7e5c08217003d22808b273)
BibTeX
@misc{dcf10cf2574db6,
  title = {Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm — arXiv:2610.06006},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.06006},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f10cf2574db6; sha256 2a7d1c947a8b9f0136a747d9ae1a0696bd6c7eb73a7e5c08217003d22808b273},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.06006. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study contextual queueing bandits, where a learner schedules jobs while learning unknown service rates modeled by logistic functions of job-server features. Performance is measured by queue length regret, the expected excess queue length at round $t$ relative to an oracle that knows the service rates. Existing decaying-regret guarantees either have a suboptimal decay rate or require a known fixed horizon. They also assume context-wise slack and a strictly positive minimum eigenvalue of the feature covariance. In this paper, we propose WISE (Widest Interval Selection with Elimination), achieving rate-optimal $\widetilde{\mathcal O}(t^{-1/2})$ queue length regret at every sufficiently large time without knowing the horizon. We assume capacity slack, meaning that expected incoming workload under best-server service is below service capacity, and impose no covariance lower bound. Our analysis uses a workload potential measuring the expected service attempts needed by waiting jobs on their best servers. Its drift on nonempty rounds combines a negative term ensured by capacity slack with errors from suboptimal service choices. Then an elliptical potential count bounds how often WISE selects wide confidence intervals, thereby limiting the number of rounds with large service errors. We also sharpen the arrival-rate dependence of an existing lower bound and make its dependence on feature dimension and server count explicit. We prove another lower bound that quantifies the increase in regret as the normalized capacity slack decreases; to our knowledge, this is the first such lower bound for CQB. Simulations show small regret even when context-wise slack fails.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.06006 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:27:05.847Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).