  Autoregressive processes naturally arise in a large variety of real-world
scenarios, including stock markets, sales forecasting, weather prediction,
advertising, and pricing. When facing a sequential decision-making problem in
such a context, the temporal dependence between consecutive observations should
be properly accounted for guaranteeing convergence to the optimal policy. In
this work, we propose a novel online learning setting, namely, Autoregressive
Bandits (ARBs), in which the observed reward is governed by an autoregressive
process of order $k$, whose parameters depend on the chosen action. We show
that, under mild assumptions on the reward process, the optimal policy can be
conveniently computed. Then, we devise a new optimistic regret minimization
algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers
sublinear regret of order $\widetilde{\mathcal{O}} \left(
\frac{(k+1)^{3/2}\sqrt{nT}}{(1-\Gamma)^2}\right)$, where $T$ is the
optimization horizon, $n$ is the number of actions, and $\Gamma < 1$ is a
stability index of the process. Finally, we empirically validate our algorithm,
illustrating its advantages w.r.t. bandit baselines and its robustness to
misspecification of key parameters.
