# Queue Scheduling with Adversarial Bandit Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 38 references that are in the map.
- First posted on arXiv 3 Mar 2023.

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

- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [Augmenting Max-Weight with Explicit Learning for Wireless Scheduling with Switching Costs](https://mlsanity.com/paper/1808.01618/) (2018)
- [Modeling and Analysis of Energy Harvesting and Smart Grid-Powered Wireless Communication Networks: A Contemporary Survey](https://mlsanity.com/paper/1912.13203/) (2019)
- [On the Power of Randomization for Scheduling Real-Time Traffic in Wireless Networks](https://mlsanity.com/paper/2001.05146/) (2020)
- [A Theory of Auto-Scaling for Resource Reservation in Cloud Services](https://mlsanity.com/paper/2005.13744/) (2020)

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

- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Bandits in Flux: Adversarial Constraints in Dynamic Environments](https://mlsanity.com/paper/2601.19867/) (2026)

## Abstract (arXiv)

In this paper, we study scheduling of a queueing system with zero knowledge of instantaneous network conditions. We consider a one-hop single-server queueing system consisting of K queues, each with time-varying and non-stationary arrival and service rates. Our scheduling approach builds on an innovative combination of adversarial bandit learning and Lyapunov drift minimization, without knowledge of the instantaneous network state (the arrival and service rates) of each queue. We then present two novel algorithms textttSoftMW (SoftMaxWeight) and textttSSMW (Sliding-window SoftMaxWeight), both capable of stabilizing systems that can be stablized by some (possibly unknown) sequence of randomized policies whose time-variation satisfies a mild condition. We further generalize our results to the setting where arrivals and departures only have bounded moments instead of being deterministically bounded and propose textttSoftMW+ and textttSSMW+ that are capable of stabilizing the system. As a building block of our new algorithms, we also extend the classical textttEXP3.S (Auer et al., 2002) algorithm for multi-armed bandits to handle unboundedly large feedback signals, which can be of independent interest.