  Nonstationary phenomena, such as satiation effects in recommendations, have
mostly been modeled using bandits with finitely many arms. However, the richer
action space provided by linear bandits is often preferred in practice. In this
work, we introduce a novel nonstationary linear bandit model, where current
rewards are influenced by the learner's past actions in a fixed-size window.
Our model, which recovers stationary linear bandits as a special case,
leverages two parameters: the window size $m \ge 0$, and an exponent $\gamma$
that captures the rotting ($\gamma < 0)$ or rising ($\gamma > 0$) nature of the
phenomenon. When both $m$ and $\gamma$ are known, we propose and analyze a
variant of OFUL which minimizes regret against cycling policies. By choosing
the cycle length so as to trade-off approximation and estimation errors, we
then prove a bound of order
$\sqrt{d}\,(m+1)^{\frac{1}{2}+\max\{\gamma,0\}}\,T^{3/4}$ (ignoring log
factors) on the regret against the optimal sequence of actions, where $T$ is
the horizon and $d$ is the dimension of the linear action space. Through a
bandit model selection approach, our results are extended to the case where $m$
and $\gamma$ are unknown. Finally, we complement our theoretical results with
experiments against natural baselines.
