# A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits

arXiv: https://arxiv.org/abs/2110.11819 · HTML: https://mlsanity.com/paper/2110.11819/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 36 references that are in the map.
- First posted on arXiv 22 Oct 2021.

## Builds on (most cited first, 8 of 8)

- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Current Challenges and Visions in Music Recommender Systems Research](https://mlsanity.com/paper/1710.03208/) (2017)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Blocking Bandits](https://mlsanity.com/paper/1907.11975/) (2019)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Rebounding Bandits for Modeling Satiation Effects](https://mlsanity.com/paper/2011.06741/) (2020)
- [Multi-armed Bandit Problem with Known Trend](https://mlsanity.com/paper/1508.07091/) (2015)
- [Discrepancy-Based Algorithms for Non-Stationary Rested Bandits](https://mlsanity.com/paper/1710.10657/) (2017)

## Built on by (most cited first, 8 of 8)

- [Accounting for AI and Users Shaping One Another: The Role of Mathematical Models](https://mlsanity.com/paper/2404.12366/) (2024)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret](https://mlsanity.com/paper/2205.14790/) (2022)
- [Online Recommendations for Agents with Discounted Adaptive Preferences](https://mlsanity.com/paper/2302.06014/) (2023)
- [Last Switch Dependent Bandits with Monotone Payoff Functions](https://mlsanity.com/paper/2306.00338/) (2023)
- [State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewards](https://mlsanity.com/paper/2403.11520/) (2024)
- [Improving Engagement and Efficacy of mHealth Micro-Interventions for Stress Coping: an In-The-Wild Study](https://mlsanity.com/paper/2407.11612/) (2024)
- [Algorithmic Content Selection and the Impact of User Disengagement](https://mlsanity.com/paper/2410.13108/) (2024)

## Abstract (arXiv)

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.