We consider the stochastic multi-armed bandit problem with non-stationary
rewards. We present a novel formulation of non-stationarity in the environment
where changes in the mean reward of the arms over time are due to some unknown,
latent, auto-regressive (AR) state of order $k$. We call this new environment
the latent AR bandit. Different forms of the latent AR bandit appear in many
real-world settings, especially in emerging scientific fields such as
behavioral health or education where there are few mechanistic models of the
environment. If the AR order $k$ is known, we propose an algorithm that
achieves $\tilde{O}(k\sqrt{T})$ regret in this setting. Empirically, our
algorithm outperforms standard UCB across multiple non-stationary environments,
even if $k$ is mis-specified.

我们考虑具有非平稳收益的随机多臂赌博问题，提出了一个称为潜在 AR 赌博的新环境，在这个环境中，臂的平均收益随时间变化是由未知的、潜在的、自回归（AR）阶数为 k 的状态引起的。针对已知的 AR 阶数 k，我们提出了一个算法，在这种情况下实现了 O (k√T) 的遗憾。在多个非平稳环境中，我们的算法在实证上优于标准 UCB，即使 k 被错误估计。