Online Stochastic Optimization with Wasserstein-Based Nonstationarity
研究有限时间范围内多资源约束的在线随机优化问题，提出基于Wasserstein距离的非平稳性度量，并设计梯度下降算法实现次线性遗憾，适用于在线线性规划和网络收益管理等场景。
We consider a general online stochastic optimization problem with multiple resource 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 resources. Each cost function corresponds to the consumption of one resource. The reward function and the cost functions of each time period are drawn from an unknown distribution, which is nonstationary across time. The objective of the decision maker is to maximize the cumulative reward subject to the resource 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 and (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 nonstationarity of the environment 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 an informative gradient descent algorithm. The algorithm takes a primal-dual perspective, and it 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. We illustrate the algorithm’s performance through numerical experiments. This paper was accepted by Chung Piaw Teo, optimization. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2020.03850 .