Finite-Time Information-Theoretic Bounds in Queueing Control
This work addresses the limitation of asymptotic optimality in queueing control for networks with adversarial and stochastic arrivals, offering a non-asymptotic framework that could improve real-time scheduling performance.
The paper tackled the problem of finite-time queue length in scheduling for stochastic processing networks, proving that MaxWeight policies can be suboptimal and deriving new policies that achieve information-theoretic lower bounds under certain conditions, with performance gaps identified by problem-dependent factors.
We establish the first finite-time information-theoretic lower bounds-and derive new policies that achieve them-for the total queue length in scheduling problems over stochastic processing networks with both adversarial and stochastic 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) an information-theoretic 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.