Queueing Network Controls via Deep Reinforcement Learning

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.

arXiv commentCorrected Figure 4

References in corpus (16)

• Adam: A Method for Stochastic Optimization
• TensorFlow: A system for large-scale machine learning
• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Trust Region Policy Optimization
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• The Arcade Learning Environment: An Evaluation Platform for General Agents
• Dota 2 with Large Scale Deep Reinforcement Learning
• Solving Rubik's Cube with a Robot Hand
• Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation
• Rainbow: Combining Improvements in Deep Reinforcement Learning
• Infinite-Horizon Policy-Gradient Estimation
• Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies
• Approximate dynamic programming using fluid and diffusion approximations with applications to power management
• Linear Programming for Large-Scale Markov Decision Problems
• Trust Region-Guided Proximal Policy Optimization
• A Closer Look at Deep Policy Gradients

Cited by in corpus (6)

• ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling
• Scalable Deep Reinforcement Learning for Ride-Hailing
• Stochastic approximation of symmetric Nash equilibria in queueing games
• Average-Reward Reinforcement Learning with Trust Region Methods
• Refined Policy Improvement Bounds for MDPs
• Minimax Optimal Estimation of Stability Under Distribution Shift