Finite-Time Minimax Bounds in Queueing Control
Abstract: We establish the first finite-time information‑theoretic lower bounds for the total queue length in scheduling problems over parallel queueing systems with adversarial arrivals. We also derive policies that achieve these lower bounds up to universal constants. Prior analyses of MaxWeight guarantee only stability and asymptotic optimality in heavy traffic. We prove that in the finite horizon (time) regime, MaxWeight incurs strictly larger backlogs by problem‑dependent factors which we identify. Our main innovations in this work include: 1) a minimax framework that pinpoints the precise problem parameters governing any policy’s finite‑time performance; 2) an information‑theoretic lower bound on the total queue length; 3) fundamental limitations 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 fundamental limits on “drift‑only” methods and point the way toward principled, non‑asymptotic optimality in queueing control. (Joint work with Yujie Liu and Vincent Tan from NUS.)
Biography: Yunbei Xu is an Assistant Professor (Presidential Young Professorship) at the National University of Singapore. With training in mathematics (BSc, Peking University), decision science (PhD, Columbia), and computing (postdoc, MIT), he works across machine learning theory, stochastic processes, optimization, and physical systems to integrate information and computation principles into next-generation fundamental science.