In traditional Multi-Armed Bandit (MAB) frameworks, rewards are typically assumed to be stationary or driven by an external stochastic process. However, in many real-world applications—such as e-commerce recommendations, ad placements, or notification scheduling—the act of selecting an option inherently degrades its immediate future value. The resource experiences "fatigue" and requires time to recover.
This ICML 2021 paper by David Simchi-Levi, Zeyu Zheng, and Feng Zhu introduces a rigorous framework for MABs with recovering rewards. By modeling how rewards drop after an arm is pulled and recover non-parametrically over time, the authors provide a mathematical foundation for balancing immediate gratification with strategic resting.
The Challenge of Recovering Rewards
Standard bandit models struggle to capture the nuances of recovering rewards, particularly under complex operational constraints. The authors identify three critical gaps in the existing literature:
- Combinatorial Constraints: Most recovering reward models assume the agent can only pull one arm at a time. In reality, decision-makers often select a batch of $K$ items from $N$ available options.
- Non-Parametric Recovery: Previous work frequently assumes a specific, mathematically convenient shape for recovery (such as strictly concave functions). This paper relaxes that constraint, assuming only monotonicity (the longer you wait, the better the reward) and boundedness.
- The Scheduling Nightmare: If an agent decides to pull Arm A every 3 days and Arm B every 2 days, their schedules will eventually collide. Managing these collisions while maximizing rewards across multiple arms is a complex combinatorial challenge.
Methodology
The authors divide the challenge into an offline planning problem (where recovery rates are known) and an online learning problem (where they must be discovered).
The Offline Strategy: Purely Periodic Policies (PPP)
Instead of relying on computationally heavy dynamic programming, the authors propose Purely Periodic Policies (PPP). Under this regime, an arm $i$ is pulled exactly every $d_i$ periods.
To prevent scheduling collisions and ensure no more than $K$ arms are pulled simultaneously, the authors employ a clever rounding technique based on powers of 2. By rounding desired frequencies to this specific structure, they guarantee a collision-free schedule. Furthermore, they utilize the upper concave envelope of the recovery function to create a linear programming relaxation, establishing a theoretical upper bound for the best possible reward.
The Online Strategy: Phase-Based UCB
When recovery functions are unknown, the algorithm uses a "learning-while-planning" approach. The time horizon is divided into phases. At the beginning of each phase, the agent constructs Upper Confidence Bounds (UCB) for the recovery functions based on historical data. It then solves a generalized knapsack problem to determine the optimal arms and their frequencies for the duration of that phase.
Key Insights and Theoretical Guarantees
As a theoretical paper, the focus is on rigorous mathematical guarantees and regret bounds rather than empirical benchmark datasets. The framework yields several powerful insights:
- The Power of Periodicity: Surprisingly, simple periodic policies perform almost as well as complex dynamic strategies. The offline PPP achieves an approximation ratio of at least $1/4$ for any $K$. As the capacity $K$ increases, the gap between the periodic policy and the theoretical optimum shrinks to zero at a rate of $1 - O(1/\sqrt{K})$.
- Strategic Idleness and Bypassing Concavity: The framework explicitly models "idle time" as a valuable resource. It proves that strong guarantees can be achieved without assuming reward concavity—only that rewards do not decrease over time.
- Online Regret: The phase-based UCB algorithm achieves a regret of $\tilde{O}(N\sqrt{T})$ against the offline benchmark. This aligns with the "gold standard" for bandit algorithms, demonstrating that the cost of learning does not grow faster than the square root of time.
- Computational Efficiency: By reducing the scheduling challenge to a series of knapsack-like optimizations, the authors provide a Fully Polynomial-Time Approximation Scheme (FPTAS), ensuring the solution is practically computable even for a large number of arms $N$.
Limitations and Future Directions
Because the model is non-parametric and does not assume a specific shape for the recovery curve, the initial "learning cost" can be high, particularly when the action space $N$ is large.
The authors note that their current regret bounds are worst-case and suggest exploring "instance-dependent" bounds that could perform even better when specific recovery functions are well-behaved. Finally, whether the $O(1/\sqrt{K})$ gap in the offline approximation is the absolute mathematical limit, or if a more sophisticated scheduling algorithm could close it further, remains an open question for future research.
Summary updated