# Learning and Information in Stochastic Networks and Queues

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 120 references that are in the map.
- First posted on arXiv 18 May 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management](https://mlsanity.com/paper/1905.04337/) (2019)
- [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)
- [Scalable Deep Reinforcement Learning for Ride-Hailing](https://mlsanity.com/paper/2009.14679/) (2020)
- [Reinforcement Learning for Datacenter Congestion Control](https://mlsanity.com/paper/2102.09337/) (2021)
- [Augmenting Max-Weight with Explicit Learning for Wireless Scheduling with Switching Costs](https://mlsanity.com/paper/1808.01618/) (2018)
- [Stability and Learning in Strategic Queuing Systems](https://mlsanity.com/paper/2003.07009/) (2020)
- [Stable Reinforcement Learning with Unbounded State Space](https://mlsanity.com/paper/2006.04353/) (2020)
- [Decentralized Signal Control for Urban Road Networks](https://mlsanity.com/paper/1310.0491/) (2013)
- [POND: Pessimistic-Optimistic oNline Dispatching](https://mlsanity.com/paper/2010.09995/) (2020)
- [Adaptive Matching for Expert Systems with Uncertain Task Types](https://mlsanity.com/paper/1703.00674/) (2017)
- [Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure](https://mlsanity.com/paper/1903.02764/) (2019)
- [When Backpressure Meets Predictive Scheduling](https://mlsanity.com/paper/1309.1110/) (2013)
- [Reinforcement Learning for Traffic Signal Control: Comparison with Commercial Systems](https://mlsanity.com/paper/2104.10455/) (2021)
- [Virtues of Patience in Strategic Queuing Systems](https://mlsanity.com/paper/2011.10205/) (2020)
- [Reinforcement Learning algorithms for regret minimization in structured Markov Decision Processes](https://mlsanity.com/paper/1608.04929/) (2016)
- [Network Utility Maximization in Adversarial Environments](https://mlsanity.com/paper/1712.08672/) (2017)
- [Stability and Instability of the MaxWeight Policy](https://mlsanity.com/paper/1909.10825/) (2019)
- [Necessity of Future Information in Admission Control](https://mlsanity.com/paper/1506.04263/) (2015)
- [Fluctuation Bounds for the Max-Weight Policy, with Applications to State Space Collapse](https://mlsanity.com/paper/1810.09180/) (2018)
- [A High-fidelity, Machine-learning Enhanced Queueing Network Simulation Model for Hospital Ultrasound Operations](https://mlsanity.com/paper/2104.07451/) (2021)
- [Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling](https://mlsanity.com/paper/2105.00210/) (2021)

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

- [Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.17116/) (2022)
- [Efficient Reinforcement Learning for Routing Jobs in Heterogeneous Queueing Systems](https://mlsanity.com/paper/2402.01147/) (2024)
- [Minimax Optimal Estimation of Stability Under Distribution Shift](https://mlsanity.com/paper/2212.06338/) (2022)
- [Learning-based Optimal Admission Control in a Single Server Queuing System](https://mlsanity.com/paper/2212.11316/) (2022)
- [Online Learning and Optimization for Queues with Unknown Demand Curve and Service Distribution](https://mlsanity.com/paper/2303.03399/) (2023)
- [Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space](https://mlsanity.com/paper/2302.10667/) (2023)
- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)
- [Learning to Admit Optimally in an M/M/k/k+N Queueing System with Unknown Service Rate](https://mlsanity.com/paper/2202.02419/) (2022)

## Abstract (arXiv)

We review the role of information and learning in the stability and optimization of queueing systems. In recent years, techniques from supervised learning, bandit learning and reinforcement learning have been applied to queueing systems supported by increasing role of information in decision making. We present observations and new results that help rationalize the application of these areas to queueing systems. We prove that the MaxWeight and BackPressure policies are an application of Blackwell's Approachability Theorem. This connects queueing theoretic results with adversarial learning. We then discuss the requirements of statistical learning for service parameter estimation. As an example, we show how queue size regret can be bounded when applying a perceptron algorithm to classify service. Next, we discuss the role of state information in improved decision making. Here we contrast the roles of epistemic information (information on uncertain parameters) and aleatoric information (information on an uncertain state). Finally we review recent advances in the theory of reinforcement learning and queueing, as well as, provide discussion on current research challenges.