Learning to Optimize under Non-Stationarity

We introduce algorithms that achieve state-of-the-art \emph{dynamic regret} bounds for non-stationary linear stochastic bandit setting. It captures natural applications such as dynamic pricing and ads allocation in a changing environment. We show how the difficulty posed by the non-stationarity can be overcome by a novel marriage between stochastic and adversarial bandits learning algorithms. Defining $d,B_T,$ and $T$ as the problem dimension, the \emph{variation budget}, and the total time horizon, respectively, our main contributions are the tuned Sliding Window UCB ($\mathtt{\text{SW-UCB}}$) algorithm with optimal $\tilde{O}(d^{2\mathrm{/}3}(B_T+1{)}^{1\mathrm{/}3}{T}^{2\mathrm{/}3})$ dynamic regret, and the tuning free bandit-over-bandit ($\mathtt{\text{BOB}}$) framework built on top of the $\mathtt{\text{SW-UCB}}$ algorithm with best $\tilde{O}(d^{2\mathrm{/}3}(B_T+1{)}^{1\mathrm{/}4}{T}^{3\mathrm{/}4})$ dynamic regret.