2022/12/06 by Killian Wood, Wood, Killian, Emiliano Dall’Anese +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Advanced Bandit Algorithms Research #Stochastic processes and financial applications #Economic Policies and Impacts
paper · pdf · doi:10.48550/arxiv.2212.02693
In this work, we consider a time-varying stochastic saddle point problem in which the objective is revealed sequentially, and the data distribution depends on the decision variables. Problems of this type express the distributional dependence via a distributional map, and are known to have two distinct types of solutions--saddle points and equilibrium points. We demonstrate that, under suitable conditions, online primal-dual type algorithms are capable of tracking equilibrium points. In contrast, since computing closed-form gradient of the objective requires knowledge of the distributional map, we offer an online stochastic primal-dual algorithm for tracking equilibrium trajectories. We provide bounds in expectation and in high probability, with the latter leveraging a sub-Weibull model for the gradient error. We illustrate our results on an electric vehicle charging problem where responsiveness to prices follows a location-scale family based distributional map.