Dynamic Planning and Learning under Recovering Rewards

David Simchi-Levi, Zeyu Zheng, Feng ZhuICML 2021 · OpenReview

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:

  1. 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.
  2. 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.
  3. 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

Abstract

Motivated by emerging applications such as live-streaming e-commerce, promotions and recommendations, we introduce a general class of multi-armed bandit problems that have the following two features: (i) the decision maker can pull and collect rewards from at most $K$ out of $N$ different arms in each time period; (ii) the expected reward of an arm immediately drops after it is pulled, and then non-parametrically recovers as the idle time increases. With the objective of maximizing expected cumulative rewards over $T$ time periods, we propose, construct and prove performance guarantees for a class of “Purely Periodic Policies”. For the offline problem when all model parameters are known, our proposed policy obtains an approximation ratio that is at the order of $1-\mathcal O(1/\sqrt{K})$, which is asymptotically optimal when $K$ grows to infinity. For the online problem when the model parameters are unknown and need to be learned, we design an Upper Confidence Bound (UCB) based policy that approximately has $\widetilde{\mathcal O}(N\sqrt{T})$ regret against the offline benchmark. Our framework and policy design may have the potential to be adapted into other offline planning and online learning applications with non-stationary and recovering rewards.
BibTeX
@inproceedings{simchilevi2021dynamic,
  author = {David Simchi-Levi and Zeyu Zheng and Feng Zhu},
  title = {{Dynamic Planning and Learning under Recovering Rewards}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=zc7etCuWFV},
}
Figure