Queueing Network Controls via Deep Reinforcement Learning

References

• Abadi M, Barham P, Chen J, Chen Z, Davis A, Dean J, Devin M, et al. (2016) Tensorflow: A system for large-scale machine learning. Proc. 12th USENIX Sympos. Operating Systems Design Implementation, 265–283.Google Scholar
• Abbasi-Yadkori Y, Bartlett P, Malek A (2014) Linear programming for large-scale markov decision problems. Proc. 31st Intern. Conf. Machine Learn., vol. 32, 496–504.Google Scholar
• Andradóttir S, Heyman DP, Ott TJ (1993) Variance reduction through smoothing and control variates for Markov chain simulations. ACM Trans. Modeling Comput. Simulations 3(3):167–189.Google Scholar
• Asmussen S (2003) Applied Probability and Queues (Springer, New York).Google Scholar
• Ata B, Kumar S (2005) Heavy traffic analysis of open processing networks with complete resource pooling: Asymptotic optimality of discrete review policies. Ann. Appl. Probability 15:331–391.Google Scholar
• Avram F, Bertsimas D, Ricard M (1995) Fluid models of sequencing problems in open queueing networks: An optimal control approach. Kelly F, Williams RJ, eds. Stochastic Networks, vol. 71 (Springer, New York), 237.Google Scholar
• Bäuerle N (2001) Asymptotic optimality of tracking policies in stochastic networks. Ann. Appl. Probability 10(4):1065–1083.Google Scholar
• Baxter J, Bartlett PL (2001) Infinite-horizon policy-gradient estimation. J. Artificial Intelligence Res. 15(1):319–350.Google Scholar
• Bell SL, Williams RJ (2001) Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: Asymptotic optimality of a threshold policy. Ann. Appl. Probability 11(3):608–649.Google Scholar
• Bellemare MG, Naddaf Y, Veness J, Bowling M (2013) The arcade learning environment: An evaluation platform for general agents. J. Artificial Intelligence Res. 47(1):253–279.Google Scholar
• Bertsimas D, Gamarnik D, Rikun A (2011) Performance analysis of queueing networks via robust optimization. Oper. Res. 59(2):455–466.Link, Google Scholar
• Bertsimas D, Nasrabadi E, Paschalidis IC (2015) Robust fluid processing networks. IEEE Trans. Automatic Control 60(3):715–728.Google Scholar
• Bertsimas D, Paschalidis IC, Tsitsiklis J (1994) Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance. Ann. Appl. Probability 4:43–75.Google Scholar
• Beutler FJ, Ross KW (1987) Uniformization for semi-Markov decision processes under stationary policies. J. Appl. Probability 24(3):644–656.Google Scholar
• Bhatnagar S, Lakshmanan K (2012) An online actor-critic algorithm with function approximation for constrained Markov decision processes. J. Optim. Theory Appl. 153(3):688–708.Google Scholar
• Bramson M (1996) Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks. Queueing Systems 23(1-4):1–26.Google Scholar
• Bramson M (1998) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30:89–140.Google Scholar
• Chen H, Yao D (1993) Dynamic scheduling of a multiclass fluid network. Oper. Res. 41:1104–1115.Link, Google Scholar
• Chen RR, Meyn S (1999) Value iteration and optimization of multiclass queueing networks. Queueing Systems 32:65–97.Google Scholar
• Chen W, Huang D, Kulkarni AA, Unnikrishnan J, Zhu Q, Mehta P, Meyn S, et al. (2009) Approximate dynamic programming using fluid and diffusion approximations with applications to power management. Proc. 48th IEEE Conf. Decision Control held jointly with 2009 28th Chinese Control Conf., 3575–3580.Google Scholar
• Cooper WL, Henderson SG, Lewis ME (2003) Convergence of simulation-based policy iteration. Probability Engrg. Inform. Sci. 17(2):213–234.Google Scholar
• Dai JG (1996) A fluid limit model criterion for instability of multiclass queueing networks. Ann. Appl. Probability 6(3):751–757.Google Scholar
• Dai JG, Harrison JM (2020) Processing Networks: Fluid Models and Stability (Cambridge University Press, Cambridge, UK).Google Scholar
• Dai JG, Shi P (2019) Inpatient overflow: An approximate dynamic programming approach. Manufacturing Service Oper. Management 21(4):894–911.Link, Google Scholar
• de Farias DP, Van Roy B (2003) The linear programming approach to approximate dynamic programming. Oper. Res. 51(6):850–865.Link, Google Scholar
• Glorot X, Bengio Y (2010) Understanding the difficulty of training deep feedforward neural networks. Proc. 13th Internat. Conf. Artificial Intelligence Statist., 249–256.Google Scholar
• Haarnoja T, Zhou A, Abbeel P, Levine S (2018) Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. ICML 2018(5):2976–2989.Google Scholar
• Harrison JM (1988) Brownian models of queueing networks with heterogeneous customer populations. Fleming W, Lions PL, eds. Stochastic Differential Systems, Stochastic Control Theory and Applications, vol. 10 of The IMA Volumes in Mathematics and Its Applications (Springer, New York), 147–186.Google Scholar
• Harrison JM (1996) The bigstep approach to flow management in stochastic processing networks. F P Kelly SZ, Ziedins I, eds. Stochastic Networks: Theory and Applications, vol. 4 of Lecture Note Series (Oxford University Press, Oxford, UK), 57–90.Google Scholar
• Harrison JM (1998) Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. Ann. Appl. Probability 8(3):822–848.Google Scholar
• Harrison JM (2000) Brownian models of open processing networks: Canonical representation of workload. Ann. Appl. Probability 10(1):75–103.Google Scholar
• Harrison JM (2002) Stochastic networks and activity analysis. Suhov YM, ed. Analytic Methods in Applied Probability: In Memory of Fridrikh Karpelevich, vol. 207 of American Mathematical Society Translations: Series 2 (American Mathematical Society, Providence, RI), 53–76.Google Scholar
• Harrison JM, Nguyen V (1993) Brownian models of multiclass queueing networks: Current status and open problems. Queueing Systems 13(1-3):5–40.Google Scholar
• Harrison JM, Wein LM (1990) Scheduling networks of queues: Heavy traffic analysis of a two-station closed network. Oper. Res. 38(6):1052–1064.Link, Google Scholar
• Henderson SG, Glynn PW (2002) Approximating martingales for variance reduction in Markov process simulation. Math. Oper. Res. 27(2):253–271.Link, Google Scholar
• Henderson SG, Meyn SP (1997) Efficient simulation of multiclass queueing networks. Proc. 29th Conf. Winter Simulation (ACM Press, New York), 216–223.Google Scholar
• Henderson SG, Meyn SP, Tadić VB (2003) Performance evaluation and policy selection in multiclass networks. Discrete Event Dynamic Systems 13(1-2):149–189.Google Scholar
• Hessel M, Modayil J, van Hasselt H, Schaul T, Ostrovski G, Dabney W, Horgan D, et al.. (2018) Rainbow: Combining improvements in deep reinforcement learning. Proc. 2nd AAAI Conf. Artificial Intelligence (AAAI, Palo Alto, CA), 3215–3222.Google Scholar
• Ilyas A, Engstrom L, Santurkar S, Tsipras D, Janoos F, Rudolph L, Adry AM (2020) A closer look at deep policy gradients. Proc. 8th Intern. Conf. Learning Representations, https://arxiv.org/abs/1811.02553.Google Scholar
• Jaakkola TP, Singh S, Jordan MI (1994) Reinforcement learning algorithm for partially observable Markov decision problems. Proc. 7th Internat. Conf. Neural Inform. Processing Systems, 345–352.Google Scholar
• Jiang S, Liu Y, Tang Y (2017) A unified perturbation analysis framework for countable Markov chains. Linear Algebra Appl. 529:413–440.Google Scholar
• Kakade S (2001) Optimizing average reward using discounted rewards. COLT ’01/EuroCOLT ’01, 605–615.Google Scholar
• Kakade S, Langford J (2002) Approximately optimal approximate reinforcement learning. Proc. 19th ICML, 267–274.Google Scholar
• Kemeny JG, Snell JL, Knapp AW (1976) Denumerable Markov Chains (Springer, New York).Google Scholar
• Kingma DP, Ba J (2015) Adam: A method for stochastic optimization. Proc. 3rd Intern. Conf. Learning Representations, https://arxiv.org/abs/1412.6980.Google Scholar
• Konda VR, Tsitsiklis JN (2003) On actor-critic algorithms. SIAM J. Control Optim. 42(4):1143–1166.Google Scholar
• Kumar PR (1993) Re-entrant lines. Queueing Systems 13(1-3):87–110.Google Scholar
• Kumar S, Kumar PR (1994) Performance bounds for queueing networks and scheduling policies. IEEE Trans. Automatic Control AC-39:1600–1611.Google Scholar
• Kumar S, Kumar PR (1996) Fluctuation smoothing policies are stable for stochastic reentrant lines. Discrete Event Dynamic Systems 6:361–370.Google Scholar
• Lehnert L, Laroche R, van Seijen H (2018) On value function representation of long horizon problems. Proc. 32nd AAAI Conf. Artificial Intelligence (AAAI, Palo Alto, CA).Google Scholar
• Lu SCH, Ramaswamy D, Kumar PR (1994) Efficient scheduling policies to reduce mean and variance of cycle-time in semiconductor manufacturing plants. IEEE Trans. Semiconductor Manufacturing 7(3):374–388.Google Scholar
• Luong NC, Hoang DT, Gong S, Niyato D, Wang P, Liang YC, Kim DI (2019) Applications of deep reinforcement learning in communications and networking: A survey. IEEE Comm. Survey and Tutorial 21(4):3133–3174.Google Scholar
• Maglaras C (2000) Discrete-review policies for scheduling stochastic networks: Trajectory tracking and fluid-scale asymptotic optimality. Ann. Appl. Probability 10(3):897–929.Google Scholar
• Maguluri S, Srikant R, Ying L (2012) Stochastic models of load balancing and scheduling in cloud computing clusters. Proc. 31st IEEE Intern. Conf. Comput. Comm., 702–710.Google Scholar
• Marbach P, Tsitsiklis JN (2001) Simulation-based optimization of Markov reward processes. IEEE Trans. Automatic Control 46(2):191–209.Google Scholar
• Martins LF, Shreve SE, Soner HM (1996) Heavy traffic convergence of a controlled, multiclass queueing system. SIAM J. Control Optim. 34(6):2133–2171.Google Scholar
• McKeown N, Mekkittikul A, Anantharam V, Walrand J (1999) Achieving 100% throughput in an input-queued switch. IEEE Trans. Comm. 47(8):1260–1267.Google Scholar
• Meyn S (1997) Stability and optimization of queueing networks and their fluid models. Mathematics of Stochastic Manufacturing Systems (Williamsburg, VA, 1996), vol. 33 of Lectures in Applied Mathematics (American Mathematical Society, Providence, RI), 175–199.Google Scholar
• Meyn S (2007) Control Techniques for Complex Networks (Cambridge University Press, Cambridge, UK).Google Scholar
• Meyn S, Tweedie RL (2009) Markov Chains and Stochastic Stability, 2nd ed. (Cambridge University Press, Cambridge, UK).Google Scholar
• Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, et al. (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529–533.Google Scholar
• Moallemi C, Kumar S, Van Roy B (2008) Approximate and data-driven dynamic programming for queueing networks, preprint.Google Scholar
• Moritz P, Nishihara R, Wang S, Tumanov A, Liaw R, Liang E, Elibol M, et al. (2018) Ray: A distributed framework for emerging AI applications. Proc.13th USENIX Sympos. Operating Systems Design Implementation (OSDI ’18), 561–577.Google Scholar
• Nelson BL (1989) Batch size effects on the efficiency of control variates in simulation. Eur. J. Oper. Res. 43(2):184–196.Google Scholar
• Open AI (2019) Dota 2 with large scale deep reinforcement learning. Preprint, submitted December 13, https://arxiv.org/abs/1912.06680.Google Scholar
• Open AI, Akkaya I, Andrychowicz M, Chociej M, Litwin M, McGrew B, Petron A, et al. (2019) Solving rubik’s cube with a robot hand. Preprint, submitted October 16, https://arxiv.org/abs/1910.07113.Google Scholar
• Paschalidis I, Su C, Caramanis M (2004) Target-pursuing scheduling and routing policies for multiclass queueing networks. IEEE Trans. Automatic Control 49(10):1709–1722.Google Scholar
• Perkins JR, Kumar PR (1989) Stable distributed real-time scheduling of flexible manufacturing/assembly/disassembly systems. IEEE Trans. Automatic Control AC-34:139–148.Google Scholar
• Peters J, Schaal S (2008) Reinforcement learning of motor skills with policy gradients. Neural Networks 21(4):682–697.Google Scholar
• Puterman ML (2005) Markov Decision Processes: Discrete Stochastic Dynamic Programming (Wiley-Interscience, Hoboken, NJ).Google Scholar
• Ramirez-Hernandez JA, Fernandez E (2007) An approximate dynamic programming approach for job releasing and sequencing in a reentrant manufacturing line. Proc. 2007 IEEE Internat. Sympos. Approximate Dynam. Programming Reinforcement Learn. (IEEE, New York), 201–208.Google Scholar
• Schulman J, Klimov O, Wolski F, Dhariwal P, Radford A (2017a) Proximal policy optimization. OpenAI Blog https://openai.com/blog/openai-baselines-ppo/.Google Scholar
• Schulman J, Levine S, Moritz P, Jordan MI, Abbeel P (2015) Trust region policy optimization. Proc. 32nd Intern. Conf. Machine Learn., 1889–1897.Google Scholar
• Schulman J, Moritz P, Levine S, Jordan MI, Abbeel P (2016) High-dimensional continuous control using generalized advantage estimation. 4th Intern. Conf. Learn. Representations.Google Scholar
• Schulman J, Wolski F, Dhariwal P, Radford A, Klimov O (2017b) Proximal policy optimization algorithms Preprint, submitted July 20, https://arxiv.org/abs/1707.06347.Google Scholar
• Serfozo RF (1979) Technical note: An equivalence between continuous and discrete time Markov decision processes. Oper. Res. 27(3):616–620.Link, Google Scholar
• Silver D, Schrittwieser J, Simonyan K, Antonoglou I, Huang A, Guez A, Hubert T, et al. (2017) Mastering the game of Go without human knowledge. Nature 550(7676):354–359.Google Scholar
• Simm G, Pinsler R, Hernandez-Lobato JM (2020) Reinforcement learning for molecular design guided by quantum mechanics. Proc. 37th Internat. Conf. Machine Learn., vol. 119, 8959–8969.Google Scholar
• Srikant R, Ying L (2014) Communication Networks: An Optimization, Control and Stochastic Networks Perspective (Cambridge University Press, Cambridge, UK).Google Scholar
• Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction, 2nd ed. (MIT Press, Cambridge, MA).Google Scholar
• Thomas PS (2014) Bias in natural actor-critic algorithms. Proc. of the 31st Internat. Conf. Machine Learn., 441–448.Google Scholar
• Veatch MH (2015) Approximate linear programming for networks: Average cost bounds. Comput. Oper. Res. 63:32–45.Google Scholar
• Vinyals O, Babuschkin I, Czarnecki W, et al. (2019) Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575(7782):350–354.Google Scholar
• Wagner HM (1975) Principles of Operations Research: With Applications to Managerial Decisions, 2nd ed. (Prentice-Hall, Englewood Cliffs, NJ).Google Scholar
• Wang Y, He H, Tan X, Gan Y (2019) Trust region-guided proximal policy optimization. Adv. Neural Inform. Processing Systems 32:626–636.Google Scholar
• Wang Z, Bapst V, Heess N, Mnih V, Munos R, Kavukcuoglu K, de Freitas N (2017) Sample efficient actor-critic with experience replay. Proc. 5th Internat. Conf. Learn. Representations.Google Scholar
• Willams RJ (1998) Some recent developments for queueing networks. Probability Toward. 2000:340–456 (Springer).Google Scholar
• Wu Y, Mansimov E, Liao S, Grosse R, Ba J (2017) Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation. Proc. 31st Internat. Conf. Neural Information Processing Systems, 5285–5294.Google Scholar
• Zoph B, Vasudevan V, Shlens J, Le QV (2018) Learning transferable architectures for scalable image recognition. Proc. IEEE Conf. on Comput. Vision Pattern Recognition.Google Scholar