mlsanityData to 7 Oct 2026

Rotting Bandits

arXiv 1702.07274 ↗First posted 23 Feb 2017stat.ML cs.LGcited by 57

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 11; 2023: 13; 2024: 10; 2025: 5; 2026: 9.

57 papers.

Sort:

By area:

  1. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  2. 2024Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Banditscited by 26
  3. 2021VolcanoML: Speeding up End-to-End AutoML via Scalable Search Space Decompositioncited by 25
  4. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  5. 2022Stochastic Rising Banditscited by 18
  6. 2024Accounting for AI and Users Shaping One Another: The Role of Mathematical Modelscited by 11
  7. 2022Continual Auxiliary Task Learningcited by 9
  8. 2021Generalized non-stationary banditscited by 8
  9. 2021A Last Switch Dependent Analysis of Satiation and Seasonality in Banditscited by 8
  10. 2022Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Banditscited by 8
  11. 2023Learning with Exposure Constraints in Recommendation Systemscited by 8
  12. 2023Client Selection for Generalization in Accelerated Federated Learning: A Multi-Armed Bandit Approachcited by 8
38 more
  1. 2023Best Arm Identification for Stochastic Rising Banditscited by 6
  2. 2024Falcon: Fair Active Learning using Multi-armed Banditscited by 6
  3. 2021Addressing the Long-term Impact of ML Decisions via Policy Regretcited by 5
  4. 2023Online Recommendations for Agents with Discounted Adaptive Preferencescited by 5
  5. 2023Linear Bandits with Memory: from Rotting to Risingcited by 5
  6. 2022Rotting Infinitely Many-armed Banditscited by 4
  7. 2022Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regretcited by 4
  8. 2024Adaptive Smooth Non-Stationary Banditscited by 4
  9. 2025Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learningcited by 4
  10. 2022Complete Policy Regret Bounds for Tallying Banditscited by 3
  11. 2023Congested Bandits: Optimal Routing via Short-term Resetscited by 3
  12. 2023Last Switch Dependent Bandits with Monotone Payoff Functionscited by 3
  13. 2024Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscited by 3
  14. 2023Off-Policy Evaluation for Action-Dependent Non-Stationary Environmentscited by 2
  15. 2023Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimalitycited by 2
  16. 2024An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraintscited by 2
  17. 2026A single algorithm for both restless and rested rotting banditscited by 2
  18. 2021Bandits with Dynamic Arm-acquisition Costscited by 1
  19. 2022Dynamic collaborative filtering Thompson Sampling for cross-domain advertisements recommendationcited by 1
  20. 2022Interactive Learning with Pricing for Optimal and Stable Allocations in Marketscited by 1
  21. 2023MNL-Bandit in non-stationary environmentscited by 1
  22. 2023Energy Regularized RNNs for Solving Non-Stationary Bandit Problemscited by 1
  23. 2023A Field Test of Bandit Algorithms for Recommendations: Understanding the Validity of Assumptions on Human Preferences in Multi-armed Banditscited by 1
  24. 2023Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platformscited by 1
  25. 2025The Hidden Cost of Waiting for Accurate Predictionscited by 1
  26. 2025Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Modelscited by 1
  27. 2026Generalized Linear Bandits with Memorycited by 1
  28. 2021Sleeping Combinatorial Banditscited by 0
  29. 2021Offline Planning and Online Learning under Recovering Rewardscited by 0
  30. 2021Bandit problems with fidelity rewardscited by 0
  31. 2022Contextual Bandits for Advertising Campaigns: A Diffusion-Model Independent Approach (Extended Version)cited by 0
  32. 2022Efficient End-to-End AutoML via Scalable Search Space Decompositioncited by 0
  33. 2024Influencing Bandits: Arm Selection for Preference Shapingcited by 0
  34. 2024State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewardscited by 0
  35. 2024Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rottingcited by 0
  36. 2024Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Banditscited by 0
  37. 2025On Mitigating Affinity Bias through Bandits with Evolving Biased Feedbackcited by 0
  38. 2025Influential Bandits: Pulling an Arm May Change the Environmentcited by 0

50 most cited of 57 All 57 (JSON)