2021/10/22 by Pierre Laforgue, Giulia Clerici, Laforgue, Pierre +5
Decision Sciences · Neuroscience · #Advanced Bandit Algorithms Research #Decision-Making and Behavioral Economics #FOS: Computer and information sciences #Machine Learning (cs.LG) #Mind wandering and attention
paper · pdf · doi:10.48550/arxiv.2110.11819
openalex publication_date 2021/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by the fact that humans like some level of unpredictability or novelty, and might therefore get quickly bored when interacting with a stationary policy, we introduce a novel non-stationary bandit problem, where the expected reward of an arm is fully determined by the time elapsed since the arm last took part in a switch of actions. Our model generalizes previous notions of delay-dependent rewards, and also relaxes most assumptions on the reward function. This enables the modeling of phenomena such as progressive satiation and periodic behaviours. Building upon the Combinatorial Semi-Bandits (CSB) framework, we design an algorithm and prove a bound on its regret with respect to the optimal non-stationary policy (which is NP-hard to compute). Similarly to previous works, our regret analysis is based on defining and solving an appropriate trade-off between approximation and estimation. Preliminary experiments confirm the superiority of our algorithm over both the oracle greedy approach and a vanilla CSB solver.