# Linear Bandits with Memory: from Rotting to Rising

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 58 references that are in the map.
- First posted on arXiv 16 Feb 2023.

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

- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Current Challenges and Visions in Music Recommender Systems Research](https://mlsanity.com/paper/1710.03208/) (2017)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Learning Contextual Bandits in a Non-stationary Environment](https://mlsanity.com/paper/1805.09365/) (2018)
- [Blocking Bandits](https://mlsanity.com/paper/1907.11975/) (2019)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [Linear Bandits in High Dimension and Recommendation Systems](https://mlsanity.com/paper/1301.1722/) (2013)
- [Rebounding Bandits for Modeling Satiation Effects](https://mlsanity.com/paper/2011.06741/) (2020)
- [Randomized Exploration for Non-Stationary Stochastic Linear Bandits](https://mlsanity.com/paper/1912.05695/) (2019)
- [Contextual-Bandit Based Personalized Recommendation with Time-Varying User Interests](https://mlsanity.com/paper/2003.00359/) (2020)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Multi-armed Bandit Problem with Known Trend](https://mlsanity.com/paper/1508.07091/) (2015)
- [Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing](https://mlsanity.com/paper/1801.10242/) (2018)
- [Context Attentive Bandits: Contextual Bandit with Restricted Context](https://mlsanity.com/paper/1705.03821/) (2017)
- [Unifying Clustered and Non-stationary Bandits](https://mlsanity.com/paper/2009.02463/) (2020)
- [A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits](https://mlsanity.com/paper/2110.11819/) (2021)
- [Upper Confidence Bounds for Combining Stochastic Bandits](https://mlsanity.com/paper/2012.13115/) (2020)
- [Discrepancy-Based Algorithms for Non-Stationary Rested Bandits](https://mlsanity.com/paper/1710.10657/) (2017)
- [A Linear Bandit for Seasonal Environments](https://mlsanity.com/paper/2004.13576/) (2020)

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

- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs](https://mlsanity.com/paper/2601.01069/) (2026)
- [Variance-Dependent Regret Bounds for Non-stationary Linear Bandits](https://mlsanity.com/paper/2403.10732/) (2024)
- [Rising Rested Bandits: Lower Bounds and Efficient Algorithms](https://mlsanity.com/paper/2411.14446/) (2024)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits](https://mlsanity.com/paper/2303.02691/) (2023)
- [Future Information-Directed Sampling for Bayesian Nonstationary Bandits](https://mlsanity.com/paper/2609.33981/) (2026)
- [Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory](https://mlsanity.com/paper/2610.05659/) (2026)

## Abstract (arXiv)

Nonstationary phenomena, such as satiation effects in recommendations, have mostly been modeled using bandits with finitely many arms. However, the richer action space provided by linear bandits is often preferred in practice. In this work, we introduce a novel nonstationary linear bandit model, where current rewards are influenced by the learner's past actions in a fixed-size window. Our model, which recovers stationary linear bandits as a special case, leverages two parameters: the window size m ≥ 0, and an exponent γ that captures the rotting (γ < 0) or rising (γ > 0) nature of the phenomenon. When both m and γ are known, we propose and analyze a variant of OFUL which minimizes regret against cycling policies. By choosing the cycle length so as to trade-off approximation and estimation errors, we then prove a bound of order √d,(m+1)^frac12+maxγ,0,T3/4 (ignoring log factors) on the regret against the optimal sequence of actions, where T is the horizon and d is the dimension of the linear action space. Through a bandit model selection approach, our results are extended to the case where m and γ are unknown. Finally, we complement our theoretical results with experiments against natural baselines.