# Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 13 Dec 2021.

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

- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [FiBiNET: Combining Feature Importance and Bilinear feature Interaction for Click-Through Rate Prediction](https://mlsanity.com/paper/1905.09433/) (2019)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Resource Scheduling in Edge Computing: A Survey](https://mlsanity.com/paper/2108.08059/) (2021)
- [On Learning the cμ Rule in Single and Parallel Server Networks](https://mlsanity.com/paper/1802.06723/) (2018)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Adaptive Matching for Expert Systems with Uncertain Task Types](https://mlsanity.com/paper/1703.00674/) (2017)
- [Virtues of Patience in Strategic Queuing Systems](https://mlsanity.com/paper/2011.10205/) (2020)
- [Stability and Instability of the MaxWeight Policy](https://mlsanity.com/paper/1909.10825/) (2019)
- [Concave Switching in Single and Multihop Networks](https://mlsanity.com/paper/1404.2725/) (2014)
- [Reward Maximization in General Dynamic Matching Systems](https://mlsanity.com/paper/1608.01646/) (2016)

## Abstract (arXiv)

We consider the problem of scheduling in multi-class, parallel-server queuing systems with uncertain rewards from job-server assignments. In this scenario, jobs incur holding costs while awaiting completion, and job-server assignments yield observable stochastic rewards with unknown mean values. The mean rewards for job-server assignments are assumed to follow a bilinear model with respect to features that characterize jobs and servers. Our objective is to minimize regret by maximizing the cumulative reward of job-server assignments over a time horizon, while keeping the total job holding cost bounded to ensure the stability of the queueing system. This problem is motivated by applications requiring resource allocation in network systems. A central challenge is to control the tradeoff between reward maximization and fair allocation for the stability of the underlying queuing system (i.e., maximizing network throughput). To address this challenge, we propose a scheduling algorithm based on a weighted proportional fair criteria augmented with marginal costs for reward maximization, incorporating a bandit algorithm tailored for bilinear rewards. Our algorithm admits a regret--queue length tradeoff. For any fixed control parameter V>0, it ensures a uniform expected queue length and time-average holding-cost bounds. For a target horizon T, choosing VT=Theta(√IT) at initialization yields widetilde O((√ I+d2)√ T+1/δ) regret. Under this regret-optimized tuning, the corresponding expected queue length and time-average holding-cost bounds remain uniform over the execution time and scales as O(√IT+1/δ) and O(√IT/δ), respectively.