Queueing Network Controls via Deep Reinforcement Learning
Top Cited Papers
- 1 March 2022
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Stochastic Systems
- Vol. 12 (1) , 30-67
Abstract
Novel advanced policy gradient (APG) methods, such as trust region policy optimization and proximal policy optimization (PPO), have become the dominant reinforcement learning algorithms because of their ease of implementation and good practical performance. A conventional setup for notoriously difficult queueing network control problems is a Markov decision problem (MDP) that has three features: infinite state space, unbounded costs, and long-run average cost objective. We extend the theoretical framework of these APG methods for such MDP problems. The resulting PPO algorithm is tested on a parallel-server system and large-size multiclass queueing networks. The algorithm consistently generates control policies that outperform state-of-art heuristics in literature in a variety of load conditions from light to heavy traffic. These policies are demonstrated to be near optimal when the optimal policy can be computed. A key to the successes of our PPO algorithm is the use of three variance reduction techniques in estimating the relative value function via sampling. First, we use a discounted relative value function as an approximation of the relative value function. Second, we propose regenerative simulation to estimate the discounted relative value function. Finally, we incorporate the approximating martingale-process method into the regenerative estimator.Keywords
All Related Versions
This publication has 47 references indexed in Scilit:
- Reinforcement learning of motor skills with policy gradientsNeural Networks, 2008
- Target-Pursuing Scheduling and Routing Policies for Multiclass Queueing NetworksIEEE Transactions on Automatic Control, 2004
- CONVERGENCE OF SIMULATION-BASED POLICY ITERATIONProbability in the Engineering and Informational Sciences, 2003
- Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policiesThe Annals of Applied Probability, 1998
- Fluctuation smoothing policies are stable for stochastic re-entrant linesDiscrete Event Dynamic Systems, 1996
- Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networksQueueing Systems, 1996
- Efficient scheduling policies to reduce mean and variance of cycle-time in semiconductor manufacturing plantsIEEE Transactions on Semiconductor Manufacturing, 1994
- Variance reduction through smoothing and control variates for Markov chain simulationsACM Transactions on Modeling and Computer Simulation, 1993
- Re-entrant linesQueueing Systems, 1993
- Brownian models of multiclass queueing networks: Current status and open problemsQueueing Systems, 1993