Empirical Gittins for data-driven M/G/1 scheduling with arbitrary job size distributions

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 Gittins policy is optimal. Gittins is best described as a policy construction: it takes as input the queue's job size distribution, 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 samples 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? Our main result is that to achieve near-optimal mean response time, it suffices to simply apply the Gittins construction to the empirical distribution of the job size samples. We call this policy empirical Gittins, 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. 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 tail, even if the density is completely wrong. Underlying this finding are two new extensions of the WINE queueing identity.