{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T19:49:22Z","timestamp":1774554562481,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"DOD U.S. Department of Defense","award":["National Defense Science &amp;Engineering Graduate &#x28;NDSEG&#x29; Fellowship Program"],"award-info":[{"award-number":["National Defense Science &amp;Engineering Graduate &#x28;NDSEG&#x29; Fellowship Program"]}]},{"name":"National Science Foundation","award":["CMMI-2307008"],"award-info":[{"award-number":["CMMI-2307008"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,3,26]]},"abstract":"<jats:p>\n                    When scheduling in the M\/G\/1 queue to minimize mean response time, a classic result is that if job sizes are unknown, then the\n                    <jats:italic toggle=\"yes\">Gittins<\/jats:italic>\n                    policy is optimal. Gittins is best described as a policy construction: it takes as input the queue's\n                    <jats:italic toggle=\"yes\">job size distribution,<\/jats:italic>\n                    and it outputs a job prioritization rule that optimizes mean response time for that particular distribution. But in practice, instead of knowing the exact job size distribution, one usually only has\n                    <jats:italic toggle=\"yes\">samples<\/jats:italic>\n                    from it. We therefore ask: given finitely many samples from the job size distribution, how can one construct a scheduling policy with near-optimal mean response time?\n                  <\/jats:p>\n                  <jats:p>\n                    Our main result is that to achieve near-optimal mean response time, it suffices to simply\n                    <jats:italic toggle=\"yes\">apply the Gittins construction to the empirical distribution<\/jats:italic>\n                    of the job size samples. We call this policy\n                    <jats:italic toggle=\"yes\">empirical Gittins,<\/jats:italic>\n                    and we prove an explicit high-probability bound on its mean response time. Our bound implies convergence to the optimal mean response time as one increases the number of samples. We also show that if one has even vague knowledge of the true distribution's tail asymptotics, one can make empirical Gittins more robust using truncation, resulting in better convergence rates.\n                  <\/jats:p>\n                  <jats:p>\n                    It is surprising that empirical Gittins works well even for continuous job size distributions. This is because the Gittins construction is sensitive to the distribution's density, yet the empirical distribution, being discrete, cannot possibly approximate a continuous density. Our main technical contribution is to show that despite its sensitivity to density, the Gittins construction yields a good policy as long as one gives it a distribution with an approximately correct\n                    <jats:italic toggle=\"yes\">tail,<\/jats:italic>\n                    even if the density is completely wrong. Underlying this finding are two new extensions of the WINE queueing identity.\n                  <\/jats:p>","DOI":"10.1145\/3788091","type":"journal-article","created":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:49:47Z","timestamp":1774550987000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Empirical Gittins for data-driven M\/G\/1 scheduling with arbitrary job size distributions"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9315-1929","authenticated-orcid":false,"given":"Shefali","family":"Ramakrishna","sequence":"first","affiliation":[{"name":"Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2627-0012","authenticated-orcid":false,"given":"Amit","family":"Harlev","sequence":"additional","affiliation":[{"name":"Center for Applied Mathematics, Cornell University, Ithaca, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8547-1068","authenticated-orcid":false,"given":"Ziv","family":"Scully","sequence":"additional","affiliation":[{"name":"Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2026,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-009-9141-x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964811000015"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1214\/21-AAP1741"},{"key":"e_1_2_1_4_1","volume-title":"Teugels","author":"Bingham Nicholas H.","year":"1987","unstructured":"Nicholas H. Bingham, Charles M. Goldie, and Jef L. Teugels. 1987. Regular Variation. Number 27 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_5_1","volume-title":"Lattice Theory (3 ed.). Number 25 in Colloquium Publications","author":"Birkhoff Garrett","unstructured":"Garrett Birkhoff. 1967. Lattice Theory (3 ed.). Number 25 in Colloquium Publications. American Mathematical Society, Providence, RI."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2010.05.007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"Jo\u00ebl Charles-Rebuff\u00e9 Nicolas Gast and Bruno Gaujal. 2025. Model-Based Learning of Whittle Indices. https:\/\/doi.org\/10.48550\/arXiv.2511.20397 arXiv:2511.20397 [cs]","DOI":"10.48550\/arXiv.2511.20397"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Harshit Dhankhar Kshitij Mishra and Tejas Bodas. 2025. Tabular and Deep Reinforcement Learning for Gittins Index. https:\/\/doi.org\/10.48550\/arXiv.2405.01157 arXiv:2405.01157 [cs]","DOI":"10.48550\/arXiv.2405.01157"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000129"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2308.07817"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.0291"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3587250"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1979.tb01068.x"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470980033"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860300278"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.4.609.11225"},{"key":"e_1_2_1_17_1","unstructured":"Isaac Grosof. 2023. Optimal Scheduling in Multiserver Queues. Ph.D. Dissertation. Carnegie Mellon University Pittsburgh PA. https:\/\/isaacg1.github.io\/assets\/isaac-thesis.pdf"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Isaac Grosof and Michael Mitzenmacher. 2022. Incentive Compatible Queues without Money. https:\/\/doi.org\/10.48550\/arXiv.2202.05747 arXiv:2202.05747 [cs]","DOI":"10.48550\/arXiv.2202.05747"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139226424"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695411.3695418"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1032298288"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/stsy.2019.0036"},{"key":"e_1_2_1_23_1","volume-title":"Queueing Systems, Volume 2: Computer Applications","author":"Kleinrock Leonard","unstructured":"Leonard Kleinrock. 1976. Queueing Systems, Volume 2: Computer Applications. Wiley, New York, NY."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1119060"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1123034"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.1995"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2011.06.001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.0940"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176990746"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2014.0653"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","unstructured":"Benjamin Moseley Heather Newman Kirk Pruhs and Rudy Zhou. 2025a. Robust Gittins for Stochastic Scheduling. https:\/\/doi.org\/10.48550\/arXiv.2504.10743 arXiv:2504.10743 [cs]","DOI":"10.48550\/arXiv.2504.10743"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3744970.3727315"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3764944.3764974"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176346152"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/3214660"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670686"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.3.687"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.670"},{"key":"e_1_2_1_39_1","unstructured":"Ziv Scully. 2022. A New Toolbox for Scheduling Theory. Ph.D. Dissertation. Carnegie Mellon University Pittsburgh PA. https:\/\/ziv.codes\/pdf\/scully-thesis.pdf"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428328"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2020.102150"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","unstructured":"Ziv Scully Isaac Grosof and Michael Mitzenmacher. 2022. Uniform Bounds for Scheduling with Job Size Estimates. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Berkeley CA (virtual)) (Leibniz International Proceedings in Informatics (LIPIcs)). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik Wadern Germany Article 41 30 pages. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2022.114","DOI":"10.4230\/LIPIcs.ITCS.2022.114"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2018.8635963"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.23919\/WiOpt52861.2021.9589051"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Ziv Scully and Mor Harchol-Balter. 2021b. How to Schedule Near-Optimally under Real-World Constraints. https:\/\/doi.org\/10.48550\/arXiv.2110.11579 arXiv:2110.11579 [cs]","DOI":"10.48550\/arXiv.2110.11579"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3179419"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3379477"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/educ.2025.0290"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.0038"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2106.04228"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321803"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719017"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-013-9382-6"},{"key":"e_1_2_1_54_1","volume-title":"Queueing Systems with Non-Standard Service Policies and Server Vacations. MSc","author":"van Vreumingen Rocco","year":"2020","unstructured":"Rocco van Vreumingen. 2019. Queueing Systems with Non-Standard Service Policies and Server Vacations. MSc. University of Amsterdam, Amsterdam, The Netherlands. http:\/\/www.mt-support.nl\/VanVreumingen\/Rocco\/wp-content\/uploads\/2020\/01\/Master-thesis-Queueing-systems-with-non-standard-service-policies-and-server-vacations.pdf"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1524\/itit.1972.14.16.262"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005588"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf00635964"},{"key":"e_1_2_1_58_1","unstructured":"Adam Wierman. 2007. Scheduling for Today's Computer Systems: Bridging Theory and Practice. Ph.D. Dissertation. Carnegie Mellon University Pittsburgh PA. https:\/\/adamwierman.com\/wp-content\/uploads\/2020\/09\/thesis.pdf"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)","volume":"4312","author":"Yang Zixian","year":"2023","unstructured":"Zixian Yang, R. Srikant, and Lei Ying. 2023. Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023) (Valencia, Spain) (Proceedings of Machine Learning Research, Vol. 206). PMLR, Cambridge, MA, 4275-4312. https:\/\/proceedings.mlr.press\/v206\/yang23d.html"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-79289-2"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.0197"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3788091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:52:40Z","timestamp":1774551160000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3788091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,26]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,26]]}},"alternative-id":["10.1145\/3788091"],"URL":"https:\/\/doi.org\/10.1145\/3788091","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,26]]},"assertion":[{"value":"2026-03-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}