A Learning and Rectification Algorithm for Nonstationary Online Linear Programming

This paper investigates online linear programming (OLP) under resource capacity constraints, aiming to maximize total reward over a finite horizon. To address the limitations of stochastic models in nonstationary settings and the conservatism of adversarial models, we introduce a globally nonstationary and locally stationary arrival model to the OLP context. This framework partitions the horizon into known periods where requests are independent and identically distributed within each period, while the underlying distribution varies across periods, balancing environmental evolution with local stability. Assuming the true distribution is unknown, but an inaccurate prior is available, we propose the Gradient Descent with Learning and Rectification (GDLR) framework. This dual-based method optimizes budget consumption for each request through two complementary components: a learning component that leverages local stationarity to refine estimates by combining prior knowledge with real-time observations, and a rectification component that counters global nonstationarity by adaptively adjusting estimates based on cumulative resource imbalance. Theoretically, we demonstrate that rectification serves as robust optimization against estimation errors in dual and ensures primal feasibility. The regret bound of GDLR decomposes into intrinsic stochasticity, estimation error, and allocation suboptimality, with the latter two significantly reduced via learning and rectification. Empirically, our approach consistently outperforms baselines on synthetic and real-world datasets. To our knowledge, this work presents the first enterprise OLP deployment at Alipay, achieving a 2.2% average revenue gain in online A/B tests.