Non-stationary stochastic network optimization with imperfect estimations

We investigate the problem of stochastic network optimization in presence of non-stationarity and estimations of average states in the future. Specifically, we first prove that the widely-used Drift and Penalty Algorithm in the Lyapunov optimization framework works well for non-stationary systems with periodical states. However, when the system is not periodical, non-stationarity may lead to severe performance degradation, which motivates the design of a novel, online algorithm named DPNP that incorporates the estimations of average future states into the stochastic optimization framework for decision making. DPNP is an online algorithm that requires zero a-prior distributional information about estimation errors. DPNP not only has near-optimal theoretical performance guarantees, but also outperforms existing Drift and Penalty Algorithm in numerical simulations. The improvement of DPNP highlights the importance of combining historic and future state estimations in non-stationary stochastic network optimization.