Abstract
In this paper, we investigate the power of online learning in stochastic network optimization with unknown system statistics a priori. We are interested in understanding how information and learning can be efficiently incorporated into system control techniques, and what are the fundamental benefits of doing so. We propose two Online Learning-Aided Control techniques, $\mathtt{OLAC}$ and $\mathtt{OLAC2}$, that explicitly utilize the past system information in current system control via a learning procedure called dual learning. We prove strong performance guarantees of the proposed algorithms: $\mathtt{OLAC}$ and $\mathtt{OLAC2}$ achieve the near-optimal $[O(\epsilon), O([\log(1/\epsilon)]^2)]$ utility-delay tradeoff and $\mathtt{OLAC2}$ possesses an $O(\epsilon^{-2/3})$ convergence time. $\mathtt{OLAC}$ and $\mathtt{OLAC2}$ are probably the first algorithms that simultaneously possess explicit near-optimal delay guarantee and sub-linear convergence time. Simulation results also confirm the superior performance of the proposed algorithms in practice. To the best of our knowledge, our attempt is the first to explicitly incorporate online learning into stochastic network optimization and to demonstrate its power in both theory and practice.
Introduction
In modern stochastic networks—ranging from cellular data systems to smart grids—operators face the dual challenge of minimizing operational costs while maintaining system stability. For decades, the Lyapunov/Backpressure technique has been the standard for addressing these problems without requiring a priori knowledge of system statistics. However, Backpressure suffers from two critical limitations: high delay and slow convergence. To achieve a cost within an $O(\epsilon)$ gap of the optimum, average queue sizes must grow as $\Theta(1/\epsilon)$, leading to massive delays in high-precision scenarios. Furthermore, the algorithm takes $\Theta(1/\epsilon)$ time to reach a steady state, as it essentially treats every time slot as a fresh start, discarding historical data.
This research asks a fundamental question: Can we use online learning to accelerate system control by leveraging historical data? By viewing the network controller not just as a reactive agent but as a statistical learner, we can significantly improve performance.
Online Learning-Aided Control (OLAC)
The core innovation of this work is Dual Learning. Instead of allowing physical queues to build up naturally to discover the optimal "pressure" (Lagrange multiplier) for decision-making, the controller maintains an empirical distribution of observed network states. It then solves an empirical dual problem to estimate the optimal multiplier, $\beta(t)$.
OLAC and OLAC2
- OLAC: This algorithm utilizes an "effective backlog" $Q(t) = q(t) + \beta(t) - \theta$. By incorporating the learned multiplier $\beta(t)$ into the control logic, the system "thinks" the queue is already at its optimal operating point. This allows for optimal decision-making immediately, keeping the physical queue $q(t)$ small.
- OLAC2: This variant combines dual learning with a Last-In-First-Out (LIFO) queuing discipline and periodic backlog adjustments. This ensures that even if a large backlog exists, the majority of packets experience very low latency.
To analyze these time-varying policies, the authors introduced an "augmented problem" framework, allowing for rigorous Lyapunov drift analysis even as the control policy evolves through learning.
Performance and Results
The proposed algorithms achieve a near-optimal $[O(\epsilon), O([\log(1/\epsilon)]^2)]$ utility-delay tradeoff. This is a significant theoretical leap from the standard linear tradeoff, allowing for high precision with only logarithmic delay. Furthermore, OLAC2 achieves a sub-linear convergence time of $O(\epsilon^{-2/3})$, outperforming existing "fast" algorithms that typically converge at $\Theta(1/\epsilon)$.
As shown in the simulation results above, the dual learning mechanism in OLAC allows the system to estimate the optimal multiplier rapidly (within approximately 80 time slots). While the "Virtual queue" (representing the learned multiplier) converges to the optimal level around $t=1500$, the "Actual queue under OLAC" remains remarkably low throughout the process. In contrast, the standard Backpressure algorithm takes until $t=4000$ to converge and requires a much larger physical queue to maintain the same utility. In practical terms, this translates to a 10-fold reduction in average delay (e.g., from 210 slots down to 20 slots at $V=100$).
Conclusion and Future Work
OLAC and OLAC2 demonstrate that explicitly incorporating online learning into stochastic network optimization provides substantial benefits in both delay reduction and convergence speed. While this work assumes i.i.d. network states, future research will explore non-stationary environments where system statistics change over time. Additionally, reducing the computational overhead of solving the empirical dual problem at each step remains an open area for optimization. Nonetheless, this framework establishes a new benchmark for combining statistical learning with real-time network control.
Summary updated