# Recovering Bandits

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

## Key facts

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

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

- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Testing Stationarity and Change Point Detection in Reinforcement Learning](https://mlsanity.com/paper/2203.01707/) (2022)
- [Modeling Attrition in Recommender Systems with Departing Bandits](https://mlsanity.com/paper/2203.13423/) (2022)
- [Accounting for AI and Users Shaping One Another: The Role of Mathematical Models](https://mlsanity.com/paper/2404.12366/) (2024)
- [A Last Switch Dependent Analysis of Satiation and Seasonality in Bandits](https://mlsanity.com/paper/2110.11819/) (2021)
- [Learning with Exposure Constraints in Recommendation Systems](https://mlsanity.com/paper/2302.01377/) (2023)
- [Reinforcement Learning in Modern Biostatistics: Constructing Optimal Adaptive Interventions](https://mlsanity.com/paper/2203.02605/) (2022)
- [DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs](https://mlsanity.com/paper/2209.08646/) (2022)
- [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)
- [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)
- [Congested Bandits: Optimal Routing via Short-term Resets](https://mlsanity.com/paper/2301.09251/) (2023)
- [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)
- [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)
- [Deep Index Policy for Multi-Resource Restless Matching Bandit and Its Application in Multi-Channel Scheduling](https://mlsanity.com/paper/2408.07205/) (2024)
- [A single algorithm for both restless and rested rotting bandits](https://mlsanity.com/paper/2604.21432/) (2026)
- [Offline Planning and Online Learning under Recovering Rewards](https://mlsanity.com/paper/2106.14813/) (2021)
- [Continuous Time Bandits With Sampling Costs](https://mlsanity.com/paper/2107.05289/) (2021)
- [Batched Bandits with Crowd Externalities](https://mlsanity.com/paper/2109.14733/) (2021)
- [Bandit problems with fidelity rewards](https://mlsanity.com/paper/2111.13026/) (2021)
- [State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewards](https://mlsanity.com/paper/2403.11520/) (2024)
- [Artificial Intelligence-based Decision Support Systems for Precision and Digital Health](https://mlsanity.com/paper/2407.16062/) (2024)
- [Learning to Construct Knowledge through Sparse Reference Selection with Reinforcement Learning](https://mlsanity.com/paper/2509.05874/) (2025)
- [CAROL: Context-Aware Online Learning for Fuzzer Scheduling](https://mlsanity.com/paper/2609.06772/) (2026)
- [Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems](https://mlsanity.com/paper/2610.19179/) (2026)

## Abstract (arXiv)

We study the recovering bandits problem, a variant of the stochastic multi-armed bandit problem where the expected reward of each arm varies according to some unknown function of the time since the arm was last played. While being a natural extension of the classical bandit problem that arises in many real-world settings, this variation is accompanied by significant difficulties. In particular, methods need to plan ahead and estimate many more quantities than in the classical bandit setting. In this work, we explore the use of Gaussian processes to tackle the estimation and planing problem. We also discuss different regret definitions that let us quantify the performance of the methods. To improve computational efficiency of the methods, we provide an optimistic planning approximation. We complement these discussions with regret bounds and empirical studies.