Receding learning-aided control in stochastic networks

In this paper, we develop the Receding Learning-aided Control algorithm (RLC) for solving optimization problems in general stochastic networks with potentially non-stationary system dynamics. RLC is a low-complexity online algorithm that requires zero a-priori statistical knowledge. It has three main functionalities. First, it detects changes of the underlying distribution of system dynamics via receding sampling. Then, it carefully selects the sampled information and estimates a Lagrange multiplier of an underlying optimization problem via dual-learning. Lastly, it incorporates the multiplier into an online system controller via drift-augmentation. We show that RLC achieves near-optimal utility-delay tradeoffs for stationary systems, while ensuring an efficient distribution-change detection and a fast convergence speed when applied to non-stationary networks. The results in this paper provide a general framework for designing joint detection-learning-control algorithms and provide new understanding about the role-of-information and the power-of-online-learning in network control.