Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions
This work addresses optimization under uncertainty for applications like resource allocation, but it is incremental as it builds on existing adversarial learning frameworks.
The paper tackles online two-stage stochastic optimization with long-term constraints by developing algorithms that adapt to non-stationary distributions, achieving a regret bound of O(W_T + √T) when predictions are available, where W_T measures prediction inaccuracy.
We consider an online two-stage stochastic optimization with long-term constraints over a finite horizon of $T$ periods. At each period, we take the first-stage action, observe a model parameter realization and then take the second-stage action from a feasible set that depends both on the first-stage decision and the model parameter. We aim to minimize the cumulative objective value while guaranteeing that the long-term average second-stage decision belongs to a set. We develop online algorithms for the online two-stage problem from adversarial learning algorithms. Also, the regret bound of our algorithm can be reduced to the regret bound of embedded adversarial learning algorithms. Based on this framework, we obtain new results under various settings. When the model parameters are drawn from unknown non-stationary distributions and we are given machine-learned predictions of the distributions, we develop a new algorithm from our framework with a regret $O(W_T+\sqrt{T})$, where $W_T$ measures the total inaccuracy of the machine-learned predictions. We then develop another algorithm that works when no machine-learned predictions are given and show the performances.