Metraipolis › archive › dc_34aede9fdf84
A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits — arXiv:2611.02431
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02431
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:22:46.795Z
- SHA-256 of the archived text
7a1c12e652931762d11538455ffde0333a69ba3e9b8611bf9bf147b4ca835b45- Stable URL of this page
https://metraipolis.com/documento/dc_34aede9fdf84
How to cite
A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits — arXiv:2611.02431 — arXiv (en), https://arxiv.org/abs/2611.02431 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_34aede9fdf84 (Metraipolis archive dc_34aede9fdf84, sha256 7a1c12e652931762d11538455ffde0333a69ba3e9b8611bf9bf147b4ca835b45)
BibTeX
@misc{dc34aede9fdf84,
title = {A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits — arXiv:2611.02431},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02431},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_34aede9fdf84; sha256 7a1c12e652931762d11538455ffde0333a69ba3e9b8611bf9bf147b4ca835b45},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02431. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study online channel scheduling for a single queue served by $K$ channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves $\tilde{\mathcal{O}}(\sqrt{K L_T})$ worst-case queue length regret with high probability, where $L_T$ is the longest busy-period length. This result improves the previous $T^{3/4}$ dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.
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/2611.02431 — 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-11-03T11:02:37.616Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).