# Rotting Bandits

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2017.

## Built on by (most cited first, 30 of 57)

- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [VolcanoML: Speeding up End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2107.08861/) (2021)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Accounting for AI and Users Shaping One Another: The Role of Mathematical Models](https://mlsanity.com/paper/2404.12366/) (2024)
- [Continual Auxiliary Task Learning](https://mlsanity.com/paper/2202.11133/) (2022)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits](https://mlsanity.com/paper/2110.11819/) (2021)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Client Selection for Generalization in Accelerated Federated Learning: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/2303.10373/) (2023)
- [Best Arm Identification for Stochastic Rising Bandits](https://mlsanity.com/paper/2302.07510/) (2023)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Falcon: Fair Active Learning using Multi-armed Bandits](https://mlsanity.com/paper/2401.12722/) (2024)
- [Addressing the Long-term Impact of ML Decisions via Policy Regret](https://mlsanity.com/paper/2106.01325/) (2021)
- [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)
- [Rotting Infinitely Many-armed Bandits](https://mlsanity.com/paper/2201.12975/) (2022)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning](https://mlsanity.com/paper/2505.05226/) (2025)
- [Complete Policy Regret Bounds for Tallying Bandits](https://mlsanity.com/paper/2204.11174/) (2022)
- [Congested Bandits: Optimal Routing via Short-term Resets](https://mlsanity.com/paper/2301.09251/) (2023)
- [Last Switch Dependent Bandits with Monotone Payoff Functions](https://mlsanity.com/paper/2306.00338/) (2023)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Off-Policy Evaluation for Action-Dependent Non-Stationary Environments](https://mlsanity.com/paper/2301.10330/) (2023)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints](https://mlsanity.com/paper/2404.14202/) (2024)
- [A single algorithm for both restless and rested rotting bandits](https://mlsanity.com/paper/2604.21432/) (2026)

## Abstract (arXiv)

The Multi-Armed Bandits (MAB) framework highlights the tension between acquiring new knowledge (Exploration) and leveraging available knowledge (Exploitation). In the classical MAB problem, a decision maker must choose an arm at each time step, upon which she receives a reward. The decision maker's objective is to maximize her cumulative expected reward over the time horizon. The MAB problem has been studied extensively, specifically under the assumption of the arms' rewards distributions being stationary, or quasi-stationary, over time. We consider a variant of the MAB framework, which we termed Rotting Bandits, where each arm's expected reward decays as a function of the number of times it has been pulled. We are motivated by many real-world scenarios such as online advertising, content recommendation, crowdsourcing, and more. We present algorithms, accompanied by simulations, and derive theoretical guarantees.