# Rotting Infinitely Many-armed Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 31 Jan 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [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)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (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)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [Multi-armed Bandit Problem with Known Trend](https://mlsanity.com/paper/1508.07091/) (2015)
- [Reducing Exploration of Dying Arms in Mortal Bandits](https://mlsanity.com/paper/1907.02571/) (2019)

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

- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)
- [An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints](https://mlsanity.com/paper/2404.14202/) (2024)
- [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025)

## Abstract (arXiv)

We consider the infinitely many-armed bandit problem with rotting rewards, where the mean reward of an arm decreases at each pull of the arm according to an arbitrary trend with maximum rotting rate varrho=o(1). We show that this learning problem has an Omega(maxvarrho1/3T,√T) worst-case regret lower bound where T is the horizon time. We show that a matching upper bound tildeO(maxvarrho1/3T,√T), up to a poly-logarithmic factor, can be achieved by an algorithm that uses a UCB index for each arm and a threshold value to decide whether to continue pulling an arm or remove the arm from further consideration, when the algorithm knows the value of the maximum rotting rate varrho. We also show that an tildeO(maxvarrho1/3T,T3/4) regret upper bound can be achieved by an algorithm that does not know the value of varrho, by using an adaptive UCB index along with an adaptive threshold value.