# Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 26 references that are in the map.
- First posted on arXiv 21 Jul 2023.

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

- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [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)
- [Rebounding Bandits for Modeling Satiation Effects](https://mlsanity.com/paper/2011.06741/) (2020)
- [Online Regret Bounds for Undiscounted Continuous Reinforcement Learning](https://mlsanity.com/paper/1302.2550/) (2013)
- [Contextual Blocking Bandits](https://mlsanity.com/paper/2003.03426/) (2020)
- [Bandits with adversarial scaling](https://mlsanity.com/paper/2003.02287/) (2020)

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

- [The Bandit's Blind Spot: The Critical Role of User State Representation in Recommender Systems](https://mlsanity.com/paper/2604.26651/) (2026)
- [Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory](https://mlsanity.com/paper/2610.05659/) (2026)

## Abstract (arXiv)

We propose a model for learning with bandit feedback while accounting for deterministically evolving and unobservable states that we call Bandits with Deterministically Evolving States (B-DES). The workhorse applications of our model are learning for recommendation systems and learning for online ads. In both cases, the reward that the algorithm obtains at each round is a function of the short-term reward of the action chosen and how "healthy" the system is (i.e., as measured by its state). For example, in recommendation systems, the reward that the platform obtains from a user's engagement with a particular type of content depends not only on the inherent features of the specific content, but also on how the user's preferences have evolved as a result of interacting with other types of content on the platform. Our general model accounts for the different rate λ ∈ [0,1] at which the state evolves (e.g., how fast a user's preferences shift as a result of previous content consumption) and encompasses standard multi-armed bandits as a special case. The goal of the algorithm is to minimize a notion of regret against the best-fixed sequence of arms pulled, which is significantly harder to attain compared to standard benchmark of the best-fixed action in hindsight. We present online learning algorithms for any possible value of the evolution rate λ and we show the robustness of our results to various model misspecifications.