Learning-Aided Stochastic Network Optimization With State Prediction.

We investigate the problem of stochastic network optimization in the presence of state prediction and non-stationarity. Based on a novel state prediction model featured with a distribution-accuracy curve, we develop the predictive learning-aided control (<monospace>PLC</monospace>) algorithm, which jointly utilizes historic and predicted network state information for decision making. <monospace>PLC</monospace> is an online algorithm that consists of three key components, namely, sequential distribution estimation and change detection, dual learning, and online queue-based control. We show that for stationary networks, <monospace>PLC</monospace> achieves a near-optimal utility-delay tradeoff. For non-stationary networks, <monospace>PLC</monospace> obtains an utility-backlog tradeoff for distributions that last longer than a time proportional to the square of the prediction error, which is smaller than that needed by backpressure (BP) for achieving the same utility performance. Moreover, <monospace>PLC</monospace> detects distribution change $O(w)$ slots faster with high probability ($w$ is the prediction size) and achieves a convergence time faster than that under BP. Our results demonstrate that state prediction helps: 1) achieve faster detection and convergence and 2) obtain better utility-delay tradeoffs. They also quantify the benefits of prediction in four important performance metrics, i.e., utility (efficiency), delay (quality-of-service), detection (robustness), and convergence (adaptability) and provide new insight for joint prediction, learning, and optimization in stochastic networks [ABSTRACT FROM AUTHOR]