Hedging the Drift: Learning to Optimize under Non-Stationarity

Abstract

We introduce data-driven decision-making algorithms that achieve state-of-the-art dynamic regret bounds for a collection of non-stationary stochastic bandit settings. These settings capture applications such as advertisement allocation, dynamic pricing, and traffic network routing in changing environments. We show how the difficulty posed by the (unknown a priori and possibly adversarial) non-stationarity can be overcome by an unconventional marriage between stochastic and adversarial bandit learning algorithms. Beginning with the linear bandit setting, we design and analyze a sliding window-upper confidence bound algorithm that achieves the optimal dynamic regret bound when the underlying variation budget is known. This budget quantifies the total amount of temporal variation of the latent environments. Boosted by the novel Bandit over-Bandit framework that adapts to the latent changes, our algorithm can further enjoy nearly optimal dynamic regret bounds in a (surprisingly) parameter-free manner. We extend our results to other related bandit problems, namely the multi-armed bandit, generalized linear bandit, and combinatorial semi-bandit settings, which model a variety of operations research applications. In addition to the classical exploration exploitation trade-off, our algorithms leverage the power of the “forgetting principle” in the learning pro cesses, which is vital in changing environments. Extensive numerical experiments with synthetic datasets and a dataset of an online auto-loan company during the severe acute respiratory syndrome (SARS) epi demic period demonstrate that our proposed algorithms achieve superior performance compared to existing algorithms.