Finite-Time Minimax Bounds and an Optimal Lyapunov Policy in Queueing Control

References

• Abate J, Whitt W (1987) Transient behavior of the M/M/1 queue: Starting at the origin. Queueing Systems 2(1):41–65.Crossref, Google Scholar
• Abbasi-Yadkori Y, Szepesvári C (2011) Regret bounds for the adaptive control of linear quadratic systems. Kakade SM, von Luxburg U, eds. Proc. 24th Annual Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 19 (JMLR.org, Budapest, Hungary), 1–26.Google Scholar
• Agarwal A, Bartlett PL, Ravikumar P, Wainwright MJ (2012) Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inform. Theory 58(5):3235–3249.Crossref, Google Scholar
• Andrews M, Kumaran K, Ramanan K, Stolyar AL, Vijayakumar R, Whiting P (2004) Scheduling in a queuing system with asynchronously varying service rates. Probab. Engrg. Inform. Sci. 18(2):191–217.Crossref, Google Scholar
• Ao R, Luo G, Simchi-Levi D, Wang X (2025) Optimizing LLM inference: Fluid-guided online scheduling with memory constraints. Preprint, submitted April 15, https://arxiv.org/abs/2504.11320.Google Scholar
• Asmussen S (2003) Applied Probability and Queues, Stochastic Modelling and Applied Probability, 2nd ed., vol. 51 (Springer, New York).Google Scholar
• Azar MG, Osband I, Munos R (2017) Minimax regret bounds for reinforcement learning. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 70 (JMLR.org, Sydney, Australia), 263–272.Google Scholar
• Bandi C, Bertsimas D, Youssef N (2015) Robust queueing theory. Oper. Res. 63(3):676–700.Link, Google Scholar
• Bramson M (1998) State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems 30(1):89–140.Crossref, Google Scholar
• Chen F, Foster DJ, Han Y, Qian J, Rakhlin A, Xu Y (2024) Assouad, Fano, and Le Cam with interaction: A unifying lower bound framework and characterization for bandit learnability. Globerson A, Mackey L, Belgrave D, Fan A, Paquet U, Tomczak J, Zhang C, eds. Advances in Neural Information Processing Systems, vol. 37 (Curran Associates, Red Hook, NY), 75585–75641.Crossref, Google Scholar
• Dai Y, Huang L (2024) Adversarial network optimization under bandit feedback: Maximizing utility in non-stationary multi-hop networks. Proc. ACM Measurement Anal. Comput. Systems 8(3):1–48.Crossref, Google Scholar
• Dai JG, Lin W (2005) Maximum pressure policies in stochastic processing networks. Oper. Res. 53(2):197–218.Link, Google Scholar
• Dai JG, Lin W (2008) Asymptotic optimality of maximum pressure policies in stochastic processing networks. Ann. Appl. Probab. 18(6):2239–2299.Crossref, Google Scholar
• D’Apice C, Dudin A, Dudin S, Manzo R (2023) Priority queueing system with many types of requests and restricted processor sharing. J. Ambient Intelligence Humanized Comput. 14(9):12651–12662.Crossref, Google Scholar
• Dar R, Karabulut E (2025) NVIDIA open sources run: AI scheduler to foster community collaboration. Accessed July, 27, 2026, https://developer.nvidia.com/blog/nvidia-open-sources-runai-scheduler-to-foster-community-collaboration/.Google Scholar
• Eryilmaz A, Srikant R (2007) Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control. IEEE/ACM Trans. Networking 15(6):1333–1344.Crossref, Google Scholar
• Eryilmaz A, Srikant R (2012) Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems 72(3):311–359.Crossref, Google Scholar
• Freund D, Lykouris T, Weng W (2023) Quantifying the cost of learning in queueing systems. Oh A, Naumann T, Globerson A, Saenko K, Hardt M, Levine S, eds. Advances in Neural Information Processing Systems, vol. 36 (Curran Associates, Red Hook, NY), 6532–6544.Crossref, Google Scholar
• Gamarnik D, Goldberg DA (2013) On the rate of convergence to stationarity of the M/M/N queue in the Halfin–Whitt regime. Ann. Appl. Probab. 23(5):1845–1882.Crossref, Google Scholar
• Gao Y, He Y, Li X, Zhao B, Lin H, Liang Y, Zhong J, et al. (2024) An empirical study on low GPU utilization of deep learning jobs. Proc. IEEE/ACM 46th Internat. Conf. Software Engrg. (Association for Computing Machinery, New York), 96.Google Scholar
• Gurvich I, Whitt W (2009) Queue-and-idleness-ratio controls in many-server service systems. Math. Oper. Res. 34(2):363–396.Link, Google Scholar
• Harrison JM, Van Mieghem JA (1997) Dynamic control of Brownian networks: State‐space collapse and equivalent workload formulations. Ann. Appl. Probab. 7(3):747–771.Crossref, Google Scholar
• Hirayama T, Kijima M, Nishimura S (1989) Further results for dynamic scheduling of multiclass G/G/1 queues. J. Appl. Probab. 26(3):595–603.Crossref, Google Scholar
• Hsu WK, Xu J, Lin X, Bell MR (2022) Integrated online learning and adaptive control in queueing systems with uncertain payoffs. Oper. Res. 70(2):1166–1181.Link, Google Scholar
• Jaksch T, Ortner R, Auer P (2010) Near-optimal regret bounds for reinforcement learning. J. Machine Learn. Res. 11(51):1563–1600.Google Scholar
• Krishnasamy S, Arapostathis A, Johari R, Shakkottai S (2018) On learning the cμ rule in single and parallel server networks. Proc. 2018 56th Annual Allerton Conf. Comm., Control, Comput. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 153–154.Google Scholar
• Krishnasamy S, Sen R, Johari R, Shakkottai S (2021) Learning unknown service rates in queues: A multiarmed bandit approach. Oper. Res. 69(1):315–330.Link, Google Scholar
• Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Lehmann EL, Casella G (1998) Theory of Point Estimation (Springer, New York).Google Scholar
• Li Y, Dai JG, Peng T (2025) Throughput-optimal scheduling algorithms for LLM inference and AI agents. Preprint, submitted April 10, https://arxiv.org/abs/2504.07347.Google Scholar
• Liang Q, Modiano E (2018) Minimizing queue length regret under adversarial network models. Proc. ACM Measurement Anal. Comput. Systems 2(1):1–32.Crossref, Google Scholar
• Lim S, Jung K, Andrews M (2014) Stability of the max-weight protocol in adversarial wireless networks. IEEE/ACM Trans. Networking 22(6):1859–1872.Crossref, Google Scholar
• Luczak MJ, McDiarmid C (2006) On the maximum queue length in the supermarket model. Ann. Probab. 34(2):493–527.Crossref, Google Scholar
• Ma Y, Maguluri ST (2025) Convergence rate analysis of the join-the-shortest-queue system. Preprint, submitted March 19, https://arxiv.org/abs/2503.15736.Google Scholar
• Maguluri ST, Srikant R (2016a) Heavy traffic queue length behavior in a switch under the Maxweight algorithm. Stochastic Systems 6(1):211–250.Link, Google Scholar
• Maguluri ST, Srikant R (2016b) Heavy-traffic queue length behavior in a switch under the MaxWeight algorithm. Stochastic Systems 6(1):1–34.Link, Google Scholar
• Maguluri ST, Burle SK, Srikant R (2018) Optimal heavy-traffic queue length scaling in an incompletely saturated switch. Queueing Systems 88(3–4):279–309.Crossref, Google Scholar
• Mandelbaum A, Stolyar AL (2004) Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule. Oper. Res. 52(6):836–855.Link, Google Scholar
• Massoulié L, Roberts J (1999) Bandwidth sharing: Objectives and algorithms. Proc. 18th Annual Joint Conf. IEEE Comp. Comm. Soc., vol. 3 (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1395–1403.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.Crossref, Google Scholar
• Milner JM, Olsen TL (2008) Service-level agreements in call centers: Perils and prescriptions. Management Sci. 54(2):238–252.Link, Google Scholar
• Neely MJ (2010) Stochastic Network Optimization with Application to Communication and Queueing Systems (Morgan & Claypool Publishers, San Rafael, CA).Crossref, Google Scholar
• Qiao Y, Anzai S, Yu S, Ma H, Wang Y, Kim M, Xu H (2024) ConServe: Harvesting GPUs for low-latency and high-throughput large language model serving. Preprint, submitted October 2, https://arxiv.org/html/2410.01228.Google Scholar
• Reiman MI (1984) Open queueing networks in heavy traffic. Math. Oper. Res. 9(3):441–458.Link, Google Scholar
• Robert P (2013) Stochastic Networks and Queues, vol. 52 (Springer, Berlin).Google Scholar
• Shah D, Tsitsiklis JN, Zhong Y (2016) On queue-size scaling for input-queued switches. Stochastic Systems 6(1):1–25.Link, Google Scholar
• Shah D, Walton NS, Zhong Y (2014) Optimal queue-size scaling in switched networks. Ann. Appl. Probab. 24(6):2207–2245.Crossref, Google Scholar
• Shortle JF, Thompson JM, Gross D, Harris CM (2018) Fundamentals of Queueing Theory, 5th ed. (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Simchowitz M, Foster D (2020) Naive exploration is optimal for online LQR. Daumé H, Singh A, eds. Proc 37th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 119 (JMLR.org), 8937–8948.Google Scholar
• Stahlbuhk T, Shrader B, Modiano E (2021) Learning algorithms for minimizing queue length regret. IEEE Trans. Inform. Theory 67(3):1759–1781.Crossref, Google Scholar
• Stolyar AL (2004) Maxweight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1):1–53.Crossref, Google Scholar
• Stolyar AL, Ramanan K (2001) Largest weighted delay first scheduling: Large deviations and optimality. Ann. Appl. Probab. 11(1):1–48.Crossref, Google Scholar
• Tarjan RE (1983) Data Structures and Network Algorithms (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Tassiulas L (1998) Linear complexity algorithms for maximum throughput in radio networks and input queued switches. Proc. 17th Annual Joint Conf. IEEE Comp. Comm. Soc., vol. 2 (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 533–539.Google Scholar
• Tassiulas L, Bhattacharya PP (2000) Allocation of interdependent resources for maximal throughput. Stochastic Models 16(1):27–48.Crossref, Google Scholar
• Tassiulas L, Ephremides A (1990) Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. Proc. 29th IEEE Conf. Decision Control (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 2130–2132. Google Scholar
• Van Leeuwaarden JS, Knessl C (2011) Transient behavior of the Halfin–Whitt diffusion. Stochastic Process. Appl. 121(7):1524–1545.Crossref, Google Scholar
• Verma A, Pedrosa L, Korupolu M, Oppenheimer D, Tune E, Wilkes J (2015) Large-scale cluster management at Google with Borg. Proc. 10th Eur. Conf. Comput. Systems (Association for Computing Machinery, New York), 1–17.Google Scholar
• Wainwright MJ (2019) High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Wald A (1945) Statistical decision functions which minimize the maximum risk. Ann. Math. 46(2):265–280.Crossref, Google Scholar
• Walton N, Xu K (2021) Learning and information in stochastic networks and queues. Carlsson JG, ed. Emerging Optimization Methods and Modeling Techniques with Applications, TutORials in Operations Research (INFORMS, Catonsville, MD), 161–198.Google Scholar
• Wang S, Shroff N (2017) Towards fast-convergence, low-delay and low-complexity network optimization. Proc. ACM Measurement Anal. Comput. Systems 1(2):1–32.Crossref, Google Scholar
• Xu J, Zhong Y (2020) Improved queue-size scaling for input-queued switches via graph factorization. Adv. Appl. Probab. 52(3):798–824.Crossref, Google Scholar
• Yang Z, Srikant R, Ying L (2023) Learning while scheduling in multi-server systems with unknown statistics: Maxweight with discounted UCB. Ruiz F, Dy J, van de Meent JW, eds. Proc. 26th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 206 (JMLR.org, Valencia, Spain), 4275–4312.Google Scholar
• Yu H, Neely MJ (2018) A new backpressure algorithm for joint rate control and routing with vanishing utility optimality gaps and finite queue lengths. IEEE/ACM Trans. Networking 26(4):1605–1618.Crossref, Google Scholar
• Ziemann I, Sandberg H (2021) On uninformative optimal policies in adaptive LQR with unknown B-matrix. Jadbabaie A, Lygeros J, Pappas GJ, Parrilo PA, Recht B, Tomlin CJ, Zeilinger MN, eds. Proc. Third Conf. Learn. Dynam. Control, Proceedings of Machine Learning Research, vol. 144 (JMLR.org), 213–226.Google Scholar