# Blocking Bandits

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2019.

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

- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits](https://mlsanity.com/paper/2110.11819/) (2021)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret](https://mlsanity.com/paper/2205.14790/) (2022)
- [How to Strategize Human Content Creation in the Era of GenAI?](https://mlsanity.com/paper/2406.05187/) (2024)
- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)
- [Complete Policy Regret Bounds for Tallying Bandits](https://mlsanity.com/paper/2204.11174/) (2022)
- [Last Switch Dependent Bandits with Monotone Payoff Functions](https://mlsanity.com/paper/2306.00338/) (2023)
- [Recurrent Submodular Welfare and Matroid Blocking Bandits](https://mlsanity.com/paper/2102.00321/) (2021)
- [Extending Open Bandit Pipeline to Simulate Industry Challenges](https://mlsanity.com/paper/2209.04147/) (2022)
- [Weighted Tallying Bandits: Overcoming Intractability via Repeated Exposure Optimality](https://mlsanity.com/paper/2305.02955/) (2023)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics](https://mlsanity.com/paper/2510.16208/) (2025)
- [A Field Test of Bandit Algorithms for Recommendations: Understanding the Validity of Assumptions on Human Preferences in Multi-armed Bandits](https://mlsanity.com/paper/2304.09088/) (2023)
- [Online Weighted Paging with Unknown Weights](https://mlsanity.com/paper/2410.21266/) (2024)
- [Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models](https://mlsanity.com/paper/2509.20304/) (2025)
- [Regret Analysis of Sleeping Competing Bandits](https://mlsanity.com/paper/2603.19700/) (2026)
- [Generalized Linear Bandits with Memory](https://mlsanity.com/paper/2608.15848/) (2026)
- [Offline Planning and Online Learning under Recovering Rewards](https://mlsanity.com/paper/2106.14813/) (2021)
- [Bandit problems with fidelity rewards](https://mlsanity.com/paper/2111.13026/) (2021)
- [Fully Dynamic Online Selection through Online Contention Resolution Schemes](https://mlsanity.com/paper/2301.03099/) (2023)
- [Influential Bandits: Pulling an Arm May Change the Environment](https://mlsanity.com/paper/2504.08200/) (2025)
- [Learning to Construct Knowledge through Sparse Reference Selection with Reinforcement Learning](https://mlsanity.com/paper/2509.05874/) (2025)
- [Learning in Markovian bandits with non-observable states and constrained decision epochs](https://mlsanity.com/paper/2606.27448/) (2026)
- [Block Optimism for Nonstationary Bandits with Latent Linear Dynamics](https://mlsanity.com/paper/2610.00911/) (2026)

## Abstract (arXiv)

We consider a novel stochastic multi-armed bandit setting, where playing an arm makes it unavailable for a fixed number of time slots thereafter. This models situations where reusing an arm too often is undesirable (e.g. making the same product recommendation repeatedly) or infeasible (e.g. compute job scheduling on machines). We show that with prior knowledge of the rewards and delays of all the arms, the problem of optimizing cumulative reward does not admit any pseudo-polynomial time algorithm (in the number of arms) unless randomized exponential time hypothesis is false, by mapping to the PINWHEEL scheduling problem. Subsequently, we show that a simple greedy algorithm that plays the available arm with the highest reward is asymptotically (1-1/e) optimal. When the rewards are unknown, we design a UCB based algorithm which is shown to have c log T + o(log T) cumulative regret against the greedy algorithm, leveraging the free exploration of arms due to the unavailability. Finally, when all the delays are equal the problem reduces to Combinatorial Semi-bandits providing us with a lower bound of c' log T+ ω(log T).