Sliding-Window Thompson Sampling for Non-Stationary Settings

Restless Bandits describe sequential decision-making problems in which the rewards evolve with time independently from the actions taken by the policy-maker. It has been shown that classical Bandit algorithms fail when the underlying environment is changing, making clear that in order to tackle more challenging scenarios specifically crafted algorithms are needed. In this paper, extending and correcting the work by Trovò et al. [2020], we analyze two Thompson-Sampling inspired algorithms, namely BETA-SWTS and γ-SWGTS, introduced to face the additional complexity given by the non-stationary nature of the settings; in particular we derive a general formulation for the regret in any arbitrary restless environment for both Bernoulli and Subgaussian rewards, and, through the introduction of new quantities, we delve in what contribution lays the deeper foundations of the error made by the algorithms.