RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems
Open Access
- 31 March 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Performance Evaluation of Computing Systems
- Vol. 7 (1) , 1-35
Abstract
With the rapid advance of information technology, network systems have become increasingly complex and hence the underlying system dynamics are often unknown or difficult to characterize. Finding a good network control policy is of significant importance to achieve desirable network performance (e.g., high throughput or low delay). In this work, we consider using model-based reinforcement learning (RL) to learn the optimal control policy for queueing networks so that the average job delay (or equivalently the average queue backlog) is minimized. Traditional approaches in RL, however, cannot handle the unbounded state spaces of the network control problem. To overcome this difficulty, we propose a new algorithm, called RL for Queueing Networks (RL-QN), which applies model-based RL methods over a finite subset of the state space while applying a known stabilizing policy for the rest of the states. We establish that the average queue backlog under RL-QN with an appropriately constructed subset can be arbitrarily close to the optimal result. We evaluate RL-QN in dynamic server allocation, routing, and switching problems. Simulation results show that RL-QN minimizes the average queue backlog effectively.Keywords
All Related Versions
Funding Information
- National Science Foundation (CNS-1524317 and CNS-1907905)
- Office of Naval Research (N00014-20-1-2119)
This publication has 41 references indexed in Scilit:
- Performance of Multiclass Markovian Queueing Networks Via Piecewise Linear Lyapunov FunctionsThe Annals of Applied Probability, 2001
- Hitting time in an M/G/1 queueJournal of Applied Probability, 1999
- Achieving 100% throughput in an input-queued switchIEEE Transactions on Communications, 1999
- Stability of queueing networks and scheduling policiesIEEE Transactions on Automatic Control, 1995
- Performance bounds for queueing networks and scheduling policiesIEEE Transactions on Automatic Control, 1994
- Dynamic server allocation to parallel queues with randomly varying connectivityIEEE Transactions on Information Theory, 1993
- Q-learningMachine Learning, 1992
- K competing queues with geometric service requirements and linear costs: The μc-rule is always optimalSystems & Control Letters, 1985
- The cμ rule revisitedAdvances in Applied Probability, 1985
- Necessary and sufficient conditions for recurrence and transience of Markov chains, in terms of inequalitiesJournal of Applied Probability, 1978