A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming

We study nonstationary online linear programming (OLP), where orders arrive sequentially and follow independent but not-identical reward-resource distributions. The decision- maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to a resource endowment available at the beginning of the planning horizon. Such problems arise in resource-constrained ML and AI systems, including inference admission control, online advertising and recommendation, and data-acquisition pipelines, where the mix and value of requests may change over time. We focus on a minimal-information regime in which the decision-maker observes only one independent sample from each future distribution before the horizon begins. We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of order, we prove that our algorithm achieves $O((\log n)^2)$ regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.