  We introduce data-driven decision-making algorithms that achieve
state-of-the-art \emph{dynamic regret} bounds for non-stationary 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 \emph{a priori} and possibly
adversarial) non-stationarity can be overcome by an unconventional marriage
between stochastic and adversarial bandit learning algorithms. Our main
contribution is a general algorithmic recipe for a wide variety of
non-stationary bandit problems. Specifically, we design and analyze the sliding
window-upper confidence bound algorithm that achieves the optimal dynamic
regret bound for each of the settings when we know the respective underlying
\emph{variation budget}, which 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, we can further enjoy the (nearly)
optimal dynamic regret bounds in a (surprisingly) parameter-free manner. In
addition to the classical exploration-exploitation trade-off, our algorithms
leverage the power of the "forgetting principle" in the learning processes,
which is vital in changing environments. Our extensive numerical experiments on
both synthetic and real world online auto-loan datasets show that our proposed
algorithms achieve superior empirical performance compared to existing
algorithms.
