The Power of Online Learning in Stochastic Network Optimization

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, OLAC and 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: OLAC and OLAC2 achieve the near-optimal [O(), O([log(1/)]2)] utility-delay tradeoff and OLAC2 possesses an O(−2/3) con-vergence time. OLAC and OLAC2 are probably the first al-gorithms that simultaneously possess explicit near-optimal delay guarantee and sub-linear convergence time. Simula-tion results also confirm the superior performance of the proposed algorithms in practice. To the best of our knowl-edge, our attempt is the first to explicitly incorporate online learning into stochastic network optimization and to demon-strate its power in both theory and practice. 1