We consider a non-stationary variant of a sequential stochastic optimization problem, where the underlying cost functions may change along the horizon. We propose a measure, termed variation budget, that controls the extent of said change, and study how restrictions on this budget impact achievable performance. We identify sharp conditions under which it is possible to achieve lon-grun-average optimality and more refi?ned performance measures such as rate optimality that fully characterize the complexity of such problems. In doing so, we also establish a strong connection between two rather disparate strands of literature: adversarial online convex optimization; and the more traditional stochastic approximation paradigm (couched in a non-stationary setting). This connection is the key to deriving well performing policies in the latter, by leveraging structure of optimal policies in the former. Finally, tight bounds on the minimax regret allow us to quantify the "price of non-stationarity," which mathematically captures the added complexity embedded in a temporally changing environment versus a stationary one.

控制变化预算的非静态顺序随机优化问题，可以实现长期平均最优性和速率最优性。对于这些问题的复杂性，我们建立了在线对抗凸优化和随机逼近范式之间的联系，并给出了最小化后悔的紧密界限，以量化非静态性的代价。

非定态随机优化