Technical Summary: Experimentation for Different Scheduling Policies on Queues

Problem Statement

In modern data centers, scheduling algorithms are critical for distributing workloads across server networks to balance response times and computational costs. When deploying a new scheduling policy, practitioners typically rely on A/B testing to evaluate its real-world impact. However, standard A/B tests in queueing systems are susceptible to Markovian interference (also known as intertemporal interference).

In a standard randomized A/B test where tasks are assigned to treatment and control groups, the state of the system (e.g., queue lengths) evolves dynamically. A scheduling policy applied to one group influences the server load, which subsequently affects the response times and queue states of tasks in the other group. This interference causes "naive" estimators—which simply compare average outcomes between groups—to produce systematic bias. Specifically, the naive estimator underestimates the treatment effect because the presence of a more efficient policy in the control group artificially shortens queues for the treatment group, and vice versa.

While Differences-in-Q (DQ) estimators, introduced by Farias et al. [2022], have been proposed to mitigate this bias by summing future rewards to estimate Q-values, these estimators often suffer from high variance due to the accumulation of noise over long horizons.

Methodology

1. System Model

The authors model the data center as a parallel-server queueing network (the "supermarket model") with $N$ servers. Tasks arrive as a Poisson stream and are routed to servers based on load-balancing policies (e.g., Power-of-$d$). The system state is defined by the vector of queue lengths. The authors define two primary performance metrics:

• Response Time ($C_w$): The time a task spends in the system (waiting + service).
• Queue Length ($C_q$): The average number of tasks in the system.

The objective is to estimate the Global Treatment Effect (GTE), defined as the difference in long-run average performance between a treatment policy (e.g., Power-of-$d_2$) and a control policy (e.g., Power-of-$d_1$).

2. Theoretical Foundation: Little's Law

A core theoretical contribution is the application of Little's Law to the estimation framework. Little's Law states that in a stable system, the long-term average queue length equals the arrival rate multiplied by the average response time.
The authors prove that the GTE defined via response time ($GTE_w$) is equivalent to the GTE defined via queue length ($GTE_q$) scaled by the arrival rate $\lambda$:
$$GTE_w = GTE_q = \frac{C_{1,q}(\lambda) - C_{0,q}(\lambda)}{\lambda}$$
This equivalence allows the authors to treat queue length and response time as interchangeable proxies for the treatment effect, provided the arrival rate is accounted for.

3. The Mixed Differences-in-Q Estimator

To address the high variance of standard DQ estimators, the authors propose a Mixed Differences-in-Q Estimator.

• Standard DQ: Estimates the GTE by summing the differences in costs (response time or queue length) over a truncated horizon $L$ for all future tasks following a treatment assignment.
• Mixed Approach: Recognizing that queue-length-based Q-functions and response-time-based Q-functions are strongly correlated, the authors employ a control variate technique. They construct a mixed Q-function:
  $$\hat{Q}^{\alpha, L}_{mix} = \alpha \hat{Q}^L_w + (1-\alpha) \frac{\hat{Q}^L_q}{\lambda}$$
  where $\alpha$ is an optimal weight chosen to minimize the variance of the mixed estimator. The optimal $\alpha^*$ is derived analytically based on the variances and covariance of the individual estimators.

This method leverages the structural properties of queueing systems (specifically Little's Law) to reduce variance without sacrificing the bias-reduction properties of the original DQ approach.

Key Contributions

1. A/B Testing Framework for Data Centers: The paper establishes a rigorous A/B testing framework within the supermarket model, explicitly capturing the performance impact of alternative scheduling strategies under randomized experiments.
2. Mixed Differences-in-Q Estimator: The authors propose a novel estimator that generalizes the DQ estimator of Farias et al. [2022]. By combining queue-length and response-time Q-functions via Little's Law, the method achieves significantly lower variance while maintaining low bias.
3. Extensive Simulation Validation: The study validates the proposed method across diverse and challenging scenarios, including:
   • Heterogeneous service rates.
   • Non-stationary arrival rates (cyclic patterns).
   • Communication delays between dispatcher and servers.
   • Non-exponential service times (both constant and heavy-tailed Pareto distributions).
   • Comparison against switchback experimental designs.

Results

The numerical experiments (conducted with $N=20$ servers and varying arrival rates) demonstrate the following:

• Bias Reduction: The naive estimator exhibits significant bias (underestimating the treatment effect) due to interference. Both standard DQ estimators (queue-length and response-time based) and the mixed DQ estimator successfully reduce this bias.
• Variance Reduction: While standard DQ estimators reduce bias, they often exhibit standard deviations 50–500 times larger than the naive estimator. The Mixed DQ estimator significantly mitigates this issue. In homogeneous settings, it reduces the standard deviation by a factor of 2 to 5 compared to standard DQ estimators.
• Mean Squared Error (MSE): Across all tested scenarios (homogeneous, heterogeneous, non-stationary, delayed, and non-exponential service times), the Mixed DQ estimator consistently achieves the lowest MSE among all compared estimators (Naive, Group, qDQ, wDQ, and Switchback).
• Robustness: The method remains effective even under heavy-tailed service times and communication delays. In non-stationary settings, the Mixed DQ estimator outperforms switchback designs, even when the arrival rate is periodic (a setting theoretically favorable to switchbacks).
• Truncation Sensitivity: An ablation study on the truncation length $L$ reveals a bias-variance trade-off. The authors find that $L = 30N\lambda$ provides a robust balance, and the Mixed DQ estimator converges faster than its counterparts even with smaller $L$.

Significance and Claims

The paper claims that the primary significance of this work lies in demonstrating that incorporating domain knowledge—specifically the structural properties of queueing systems like Little's Law—can substantially improve the reliability of performance evaluation in A/B testing.

The authors argue that relying solely on theoretical analysis under restrictive assumptions is insufficient for industrial practice. Instead, their proposed Mixed DQ estimator offers a practical, easy-to-implement solution that significantly reduces both bias and variance in the presence of Markovian interference. This allows data center operators to more accurately assess the real-world impact of new scheduling algorithms before full deployment.

The paper concludes modestly, noting that while the methodology is demonstrated on the supermarket model, it is broadly applicable to general queueing network settings. Future work is identified as rigorously developing inference procedures for the estimator and extending the framework to complex scenarios such as Large Language Model (LLM) inference.