# Last Switch Dependent Bandits with Monotone Payoff Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 1 Jun 2023.

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

- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (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)
- [Non-Stationary Bandits with Habituation and Recovery Dynamics](https://mlsanity.com/paper/1707.08423/) (2017)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Contextual Blocking Bandits](https://mlsanity.com/paper/2003.03426/) (2020)
- [A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits](https://mlsanity.com/paper/2110.11819/) (2021)
- [Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret](https://mlsanity.com/paper/2205.14790/) (2022)
- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)

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

- [Accounting for AI and Users Shaping One Another: The Role of Mathematical Models](https://mlsanity.com/paper/2404.12366/) (2024)
- [Online Weighted Paging with Unknown Weights](https://mlsanity.com/paper/2410.21266/) (2024)
- [Improving Engagement and Efficacy of mHealth Micro-Interventions for Stress Coping: an In-The-Wild Study](https://mlsanity.com/paper/2407.11612/) (2024)

## Abstract (arXiv)

In a recent work, Laforgue et al. introduce the model of last switch dependent (LSD) bandits, in an attempt to capture nonstationary phenomena induced by the interaction between the player and the environment. Examples include satiation, where consecutive plays of the same action lead to decreased performance, or deprivation, where the payoff of an action increases after an interval of inactivity. In this work, we take a step towards understanding the approximability of planning LSD bandits, namely, the (NP-hard) problem of computing an optimal arm-pulling strategy under complete knowledge of the model. In particular, we design the first efficient constant approximation algorithm for the problem and show that, under a natural monotonicity assumption on the payoffs, its approximation guarantee (almost) matches the state-of-the-art for the special and well-studied class of recharging bandits (also known as delay-dependent). In this attempt, we develop new tools and insights for this class of problems, including a novel higher-dimensional relaxation and the technique of mirroring the evolution of virtual states. We believe that these novel elements could potentially be used for approaching richer classes of action-induced nonstationary bandits (e.g., special instances of restless bandits). In the case where the model parameters are initially unknown, we develop an online learning adaptation of our algorithm for which we provide sublinear regret guarantees against its full-information counterpart.