# Online Stochastic Optimization with Wasserstein Based Non-stationarity

arXiv: https://arxiv.org/abs/2012.06961 · HTML: https://mlsanity.com/paper/2012.06961/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2020.

## Built on by (most cited first, 25 of 25)

- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics](https://mlsanity.com/paper/2503.07324/) (2025)
- [No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!](https://mlsanity.com/paper/2506.13244/) (2025)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Distributionally Time-Varying Online Stochastic Optimization under Polyak-Lojasiewicz Condition with Application in Conditional Value-at-Risk Statistical Learning](https://mlsanity.com/paper/2309.09411/) (2023)
- [High-dimensional Linear Bandits with Knapsacks](https://mlsanity.com/paper/2311.01327/) (2023)
- [Risk-averse Learning with Non-Stationary Distributions](https://mlsanity.com/paper/2404.02988/) (2024)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints](https://mlsanity.com/paper/2212.01689/) (2022)
- [An Online Algorithm for Chance Constrained Resource Allocation](https://mlsanity.com/paper/2303.03254/) (2023)
- [Online Resource Allocation in Episodic Markov Decision Processes](https://mlsanity.com/paper/2305.10744/) (2023)
- [Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions](https://mlsanity.com/paper/2401.01077/) (2024)
- [A Re-solving Heuristic for Dynamic Assortment Optimization with Knapsack Constraints](https://mlsanity.com/paper/2407.05564/) (2024)
- [Episodic Contextual Bandits with Knapsacks under Conversion Models](https://mlsanity.com/paper/2507.06859/) (2025)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets](https://mlsanity.com/paper/2609.00662/) (2026)
- [Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning](https://mlsanity.com/paper/2302.00997/) (2023)
- [Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationarity](https://mlsanity.com/paper/2505.02796/) (2025)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)
- [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026)
- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)
- [Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More](https://mlsanity.com/paper/2610.09577/) (2026)

## Abstract (arXiv)

We consider a general online stochastic optimization problem with multiple budget constraints over a horizon of finite time periods. In each time period, a reward function and multiple cost functions are revealed, and the decision maker needs to specify an action from a convex and compact action set to collect the reward and consume the budget. Each cost function corresponds to the consumption of one budget. In each period, the reward and cost functions are drawn from an unknown distribution, which is non-stationary across time. The objective of the decision maker is to maximize the cumulative reward subject to the budget constraints. This formulation captures a wide range of applications including online linear programming and network revenue management, among others. In this paper, we consider two settings: (i) a data-driven setting where the true distribution is unknown but a prior estimate (possibly inaccurate) is available; (ii) an uninformative setting where the true distribution is completely unknown. We propose a unified Wasserstein-distance based measure to quantify the inaccuracy of the prior estimate in setting (i) and the non-stationarity of the system in setting (ii). We show that the proposed measure leads to a necessary and sufficient condition for the attainability of a sublinear regret in both settings. For setting (i), we propose a new algorithm, which takes a primal-dual perspective and integrates the prior information of the underlying distributions into an online gradient descent procedure in the dual space. The algorithm also naturally extends to the uninformative setting (ii). Under both settings, we show the corresponding algorithm achieves a regret of optimal order. In numerical experiments, we demonstrate how the proposed algorithms can be naturally integrated with the re-solving technique to further boost the empirical performance.