# An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 22 Apr 2024.

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

- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [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)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [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)
- [Rotting Infinitely Many-armed Bandits](https://mlsanity.com/paper/2201.12975/) (2022)

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

- [Non-Stationary Lipschitz Bandits](https://mlsanity.com/paper/2505.18871/) (2025)
- [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025)

## Abstract (arXiv)

In this study, we consider the infinitely many-armed bandit problems in a rested rotting setting, where the mean reward of an arm may decrease with each pull, while otherwise, it remains unchanged. We explore two scenarios regarding the rotting of rewards: one in which the cumulative amount of rotting is bounded by VT, referred to as the slow-rotting case, and the other in which the cumulative number of rotting instances is bounded by ST, referred to as the abrupt-rotting case. To address the challenge posed by rotting rewards, we introduce an algorithm that utilizes UCB with an adaptive sliding window, designed to manage the bias and variance trade-off arising due to rotting rewards. Our proposed algorithm achieves tight regret bounds for both slow and abrupt rotting scenarios. Lastly, we demonstrate the performance of our algorithm using numerical experiments.