Autoregressive Bandits
This addresses decision-making in time-dependent scenarios like stock markets and advertising, offering a novel setting with theoretical guarantees, though it is incremental in extending bandit methods to autoregressive contexts.
The paper tackles the problem of sequential decision-making in autoregressive processes by proposing Autoregressive Bandits (ARBs), where rewards follow an autoregressive model dependent on actions, and devises the AR-UCB algorithm that achieves sublinear regret of order ̃O((k+1)^{3/2}√(nT)/(1-Γ)^2).
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-Γ)^2}\right)$, where $T$ is the optimization horizon, $n$ is the number of actions, and $Γ< 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.