Research map / Bandits and online learning / Multi-armed bandits
An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies infinitely many-armed rested rotting bandits under slow (total rotting budget V_T) and abrupt (rotting-instance budget S_T) constraints, proposing a UCB variant with an adaptive sliding window and a threshold, with matching-type regret bounds for beta>=1.
Problem
Minimizing regret in infinitely many-armed bandits where arm mean rewards decrease (rot) each time they are pulled, under generalized initial reward distributions P(mu>1-x)=Theta(x^beta) and generalized rotting constraints (total rotting V_T or number of rotting instances S_T).
Approach
UCB with an adaptive sliding window over doubling-length windows: an arm is withdrawn when the minimum window-UCB over candidate start times falls below a threshold 1-delta, balancing bias from rotting against variance; delta is tuned by beta and V_T or S_T.
Key results
- Proposed algorithm with delta tuned by V_T and beta achieves regret O~(max{V_T^{1/(beta+2)} T^{(beta+1)/(beta+2)}, T^{beta/(beta+1)}}) for beta>=1, matched by a lower bound Omega of the same order.
- For abrupt rotting with beta>=1 the upper bound O~(max{S_T^{1/(beta+1)} T^{beta/(beta+1)}, V_bar_T}) matches the stated lower bound.
- In numerical experiments with beta=1, the algorithm outperforms UCB-TP and SSUCB, with theoretical regret O~(T^{2/3}) and O~(T^{3/4}) for its variants versus O~(T/log(T)^{1/3}) for UCB-TP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an adaptive sliding window and tuned threshold instead of UCB-TP | Infinite-armed rotting bandits with ρ_t=1/(t\log(T)) · Synthetic datasets, uniform initial means (β=1) | regret | Helped |
| Use the V_T- and S_T-tuned proposed algorithm rather than the parameter-free proposed algorithm | Infinite-armed rotting bandits with ρ_t=1/(t\log(T)) · Synthetic datasets, uniform initial means (β=1) | regret | Helped |
| Use an adaptive sliding-window estimator instead of UCB-TP's maximum-rotting-rate estimator | Slow rotting with an oblivious adversary · Slow rotting (V_T), β=1 | regret upper bound: \tilde{O}(\max\{V_T^{\frac{1}{3}}T^{\frac{2}{3}},\sqrt{T}\}) ≤ \tilde{O}(\max\{\rho^{\frac{1}{3}}T,\sqrt{T}\}) | Helped |
| Include the cost of learning the threshold δ | UCB-Threshold with Adaptive Sliding Window without prior parameter knowledge · Slow and abrupt rotting | regret upper bound: +\max\{T^{(2\beta+1)/(2\beta+2)},T^{3/4}\} | Hurt |
Surprising findings
- For beta<1 the upper bounds do not improve as beta decreases, leaving a gap with the lower bounds.
Limitations
- Upper and lower bounds do not match for 0<beta<1.
- Parameter-free variant (BoB) incurs additional regret term and relies on stronger assumptions.
- Experiments limited to synthetic uniform-distribution instances (beta=1).
Experimental setup
Datasets: synthetic bandit instances with uniform initial mean rewards
Benchmarks: synthetic infinitely many-armed rotting bandit instances
Metrics: cumulative regret
Baselines: UCB-TP SSUCB
Builds on: UCB-TP SSUCB episodic regret analysis for infinitely many-armed bandits Bandit-over-Bandit
Closest papers by meaning
- Tracking Most Significant Shifts in Infinite-Armed Bandits (ICML 2025 · similarity 0.89)
- On Multi-Armed Bandit with Impatient Arms (ICML 2024 · similarity 0.88)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.88)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.88)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.87)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.