Research map / Bandits and online learning / Multi-armed bandits
Tracking Most Significant Shifts in Infinite-Armed Bandits
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.
Gives the first parameter-free optimal regret bounds for non-stationary infinite-armed bandits with rotting/rested changes, via a subsampling blackbox and a randomized elimination variant that adapts to a new "significant shift" measure.
Problem
Infinite-armed bandits with adversarial, rested non-stationary (mainly rotting) mean rewards drawn from a reservoir distribution. Prior optimal rates required knowledge of non-stationarity parameters and extra regularity of the reservoir; the goal is parameter-free optimal regret tied to tighter mea
Approach
A blackbox that restarts a subsampling-based finite-armed MAB base upon detecting large empirical regret (changepoint test), plus a restarting randomized elimination variant using importance-weighted, variance-aware gap estimates. Regret is bounded in terms of realized changes, total variation, rotting variants, and a new "significant shift" count, with rising non-stationarity not contributing.
Key results
- For beta=1 with rotting rewards at rate 1/t, both proposed algorithms outperform SSUCB and AUCBT-ASW, with the elimination variant performing best.
- The proposed algorithms achieve regret tilde-O(T^{2/3}) in the experimental setting versus the AUCBT-ASW bound of tilde-O(T^{3/4}).
- The performance gap between elimination and blackbox algorithms grows as beta decreases, consistent with theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Blackbox algorithm instead of the benchmark algorithms | Synthetic rotting bandit, β=1 · Synthetic rotting bandit, β=1 | regret | Helped |
| Use Restarting Subsampling Elimination instead of the other tested algorithms | Synthetic rotting bandit, β=1 · Synthetic rotting bandit, β=1 | regret | Helped |
| Use the proposed algorithms instead of the benchmark algorithms | Synthetic rotting bandit across various β values · Synthetic rotting bandit, various β values | regret | Helped |
| Decrease β while comparing Restarting Subsampling Elimination with Blackbox | Proposed algorithms on synthetic rotting bandits · Synthetic rotting bandit, various β values | regret | Mixed |
Surprising findings
- Rising non-stationarity does not contribute to the difficulty of the problem; only rotting variation matters for the bounds.
- The elimination-based bound does not depend on the reservoir mass upper bound kappa_2, unlike prior stationary analyses.
Limitations
- Optimal rates for beta < 1 only match suboptimal state-of-the-art, requiring a modified subsampling rate with sqrt(T)-type bounds.
- Significant shift can be triggered in stationary environments by poor algorithms, so it measures agent-dependent suboptimality as well as non-stationarity.
- Experiments are limited to synthetic rotting environments with a single rate of decay.
Experimental setup
Datasets: synthetic reservoir-distributed bandit environments (uniform and beta-regular initial rewards, rotting 1/t)
Benchmarks: synthetic rotting infinite-armed bandit environments
Metrics: cumulative regret
Baselines: SSUCB AUCBT-ASW UCB (as base)
Builds on: UCB successive elimination subsampling for infinite-armed bandits AUCBT-ASW
Closest papers by meaning
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.90)
- Non-Stationary Lipschitz Bandits (NeurIPS 2025 · similarity 0.90)
- An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints (NeurIPS 2024 · similarity 0.89)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.89)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.89)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.89)
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.