Research map / Bandits and online learning / Multi-armed bandits

On Multi-Armed Bandit with Impatient Arms

ICML 2024 · Bandits and online learning › Multi-armed bandits · approach: Non-stationary and structured-reward 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.

Studies multi-armed bandits where arms leave permanently if neglected for too many consecutive rounds, proves hardness bounds, shows UCB/SE limitations, and proposes FC-SE and FC-Entry using feasible cycle schedules, validated by simulations.

Problem

Standard bandit algorithms fail when arms have limited patience and exit the game if the algorithm continuously neglects them, since the optimal arm may leave early and force linear regret.

Approach

Model arm patience explicitly and schedule pulls along a feasible cycle (via AoI-style almost uniform schedules) so no arm exits before elimination; extend with virtual arm slots to handle arms that enter later.

Key results

• Proves a minimax regret lower bound of order Omega(W(K,m)T) whenever load factor l(K,m) > 1, so no algorithm achieves sublinear regret there.
• FC-SE achieves regret about O(n + sqrt(nT)) (log factors) when a feasible cycle includes all arms, and O(K^{4/3} T^{2/3} n^{1/3}) when only a subset fits initially.
• FC-Entry achieves dynamic regret O(K^2 T^{2/3} (n ln T)^{1/3}) for newly entering arms under sparse entry times; simulations with 50 trials and T=10^5 support the theory.

Surprising findings

• UCB can incur almost linear regret even when the load factor tends to 0, because the optimal arm may be impatient and exit early.
• Standard successive elimination with round-robin scheduling can have linear regret even when the load factor is below 1 if some arm has patience less than K.

Limitations

• Regret bounds for FC-SE depend on the feasible cycle length and degrade when only a subset of arms fits the initial cycle, dropping arms randomly.
• Assumes patience vector m is known in advance and, for entering arms, only a known lower bound on patience.
• Experiments are limited to small simulated instances with K up to 7 arms.

Experimental setup

Benchmarks: simulated bandit instances with Gaussian rewards

Metrics: cumulative expected regret

Baselines: UCB Successive Elimination

Builds on: Successive Elimination UCB Almost Uniform Schedule (Li et al. 2021) Even-Dar et al. 2006 successive elimination

Closest papers by meaning

• Rotting Bandits (NeurIPS 2017 · similarity 0.91)
• Blocking Bandits (NeurIPS 2019 · similarity 0.89)
• Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory (AAAI 2020 · similarity 0.89)
• Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.89)
• Pairwise Elimination with Instance-Dependent Guarantees for Bandits with Cost Subsidy (ICLR 2025 · similarity 0.88)
• An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints (NeurIPS 2024 · similarity 0.88)