Finite-Time Minimax Bounds in Queueing Control

We establish the first finite-time minimax lower bounds—and derive new policies that achieve them—for the total queue length in scheduling problems over stochastic processing networks with adversarial arrivals. Prior analyses of MaxWeight guarantee only stability and asymptotic optimality in heavy traffic; we prove that, at finite horizons, MaxWeight can incur strictly larger backlog by problem -dependent factors which we identify. Our main innovations are 1) a minimax framework that pinpoints the precise problem parameters governing any policy’s finite-time performance; 2) a minimax lower bound on total queue length; 3) fundamental limitation of MaxWeight that it is suboptimal in finite time; and 4) a new scheduling rule that minimizes the full Lyapunov drift—including its second-order term—thereby matching the lower bound under certain conditions, up to universal constants. These findings reveal a fundamental limitation on “drift-only” methods and points the way toward principled, non-asymptotic optimality in queueing control.