Journal Article

Non-Stationary Stochastic Optimization

Gur, Yonatan, Zeevi, Assaf, Besbes, Omar

2015

Overview

We consider a non-stationary variant of a sequential stochastic optimization problem, in which 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 long-run average optimality and more refined 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: (1) adversarial online convex optimization and (2) 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.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: Analysis / Budgets / Changing environments / Complexity / Convexity / Cost analysis / Cost function / Decision-making / Mathematical analysis / Mathematical optimization / METHODS / minimax regret / Minimax technique / non-stationary / online convex optimization / Operations research / Optimization / Policies / Stochastic approximation / Stochastic models