Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret

Orestis Papadigenopoulos, Constantine Caramanis, Sanjay Shakkottai

Summary

This paper tackles the "recharging bandits" problem, where the reward of an action increases the longer you wait to play it—a common scenario in recommendation systems where users tire of repetitive content. The authors significantly improve the state-of-the-art for planning these schedules, boosting the approximation guarantee for single-item recommendations from 25% to approximately 63% ($1-1/e$). They also introduce a bandit algorithm that achieves sublinear regret when these payoff recovery rates are initially unknown.

The Recharging Bandits Problem

Standard multi-armed bandit models assume that the environment is stationary: pulling an arm yields a reward drawn from a fixed distribution. However, in real-world applications like social media newsfeeds, e-commerce recommendations, or music shuffling, user satisfaction is highly dependent on time. If a platform recommends the same creator or artist repeatedly, the user's engagement drops. The expected payoff of an item effectively drops to zero after it is shown and slowly "recharges" back to a baseline over time.

This scenario is formalized as the $k$-RB (Multi-armed bandits under recharging payoffs) problem, where an algorithm can select up to $k$ arms per round. Even if the platform perfectly knows how fast each item recharges (the planning setting), finding the optimal schedule is NP-hard. Prior to this work, the best-known approximation algorithm for the $k=1$ case (picking one item per round) only guaranteed 25% ($1/4$) of the optimal payoff. The authors aim to close this theoretical gap and extend their solution to the learning setting, where the recharge rates are initially unknown.

Methodology: Randomize-Then-Interleave

The authors introduce a novel algorithm called Randomize-Then-Interleave, which operates in two main steps:

  1. A Highly Structured LP Relaxation: They formulate a natural Linear Programming (LP) relaxation to maximize the average expected payoff. The key mathematical heavy lifting is proving that the extreme point solutions of this LP have a very specific sparsity pattern. They are "almost-delay-feasible," meaning the LP assigns exactly one optimal "critical delay" to almost every arm, with at most one "irregular" arm having fractional delays.
  2. Randomized Rounding and Interleaved Scheduling:
    • The algorithm assigns each arm its critical delay based on the LP. For the single irregular arm, it uses randomized rounding to pick a delay.
  3. Each arm is then assigned a random starting offset.
  4. During the online phase, the algorithm simply checks which arms are "due" to be played (based on their offset and critical delay) and plays the top $k$ available arms with the highest current payoffs.

To handle the learning setting (where payoffs are unknown), they wrap this planning algorithm in an Explore-Then-Commit (ETC) framework. The algorithm spends the first fraction of rounds purely sampling arms at different delays to estimate their recovery functions, and then commits to the Randomize-Then-Interleave schedule using those estimates.

Key Theoretical Insights

  • The "Almost-Delay-Feasible" Structure: The most crucial insight is the structural characterization of the LP relaxation. By proving that the continuous LP solution is incredibly sparse (at most one arm has an ambiguous delay), the authors can treat a complex continuous optimization problem as a much simpler discrete scheduling one.
  • Reduction to Step-Functions: By assigning fixed critical delays to arms, the algorithm effectively reduces the complex, gradual recharging curves into simple "Heaviside" step functions (i.e., an arm is worth 0 before its critical delay, and its full value afterward). This proxy problem is much easier to approximate.
  • Leveraging the Correlation Gap: When multiple arms are "due" at the same time, they compete for the $k$ available slots. The authors cleverly use the concept of the "correlation gap" from submodular optimization to mathematically bound the worst-case performance loss caused by these collisions.

Main Results and Guarantees

Comparison of approximation guarantees for the planning problem.
  • Massive Improvement in Planning ($k=1$): For the single-arm case, the algorithm achieves a long-run expected approximation guarantee of $1 - 1/e \approx 63\%$, completely shattering the previous state-of-the-art of $25\%$.
  • Strong Guarantees for General $k$: When playing $k$ arms per round, the algorithm achieves an approximation of $1 - \frac{k^k}{e^k k!}$. Asymptotically, this scales as $1 - \mathcal{O}(1/\sqrt{k})$, matching the asymptotic rate of prior work but with vastly improved and explicit constants (e.g., for $k=2$, it improves from 33% to 72%).
  • Sublinear Regret in Learning: For the bandit setting, the ETC adaptation achieves a sublinear regret bound of $\mathcal{O}(T^{2/3})$. This proves that a system can efficiently learn users' recharge rates on the fly without sacrificing too much long-term engagement.

Limitations and Future Directions

  • Hardness of Approximation: While $1 - 1/e$ is a famous theoretical ceiling for many submodular optimization problems, the authors note it is currently unknown if this is the absolute best achievable bound for the recharging bandit problem. Finding a matching hardness proof is an open question.
  • Regret Bound Improvements: The $\mathcal{O}(T^{2/3})$ regret bound achieved by the simple Explore-Then-Commit strategy is likely not tight. Designing a more sophisticated bandit adaptation could yield tighter regret guarantees.
  • Empirical Validation: Because the paper is strictly theoretical, evaluating the algorithm on real or synthetic datasets (like actual newsfeed engagement logs) remains a highly promising direction for future applied research.

Summary updated

Abstract

The stochastic multi-armed bandit setting has been recently studied in the non-stationary regime, where the mean payoff of each action is a non-decreasing function of the number of rounds passed since it was last played. This model captures natural behavioral aspects of the users which crucially determine the performance of recommendation platforms, ad placement systems, and more. Even assuming prior knowledge of the mean payoff functions, computing an optimal planning in the above model is NP-hard, while the state-of-the-art is a $1/4$-approximation algorithm for the case where at most one arm can be played per round. We first focus on the setting where the mean payoff functions are known. In this setting, we significantly improve the best-known guarantees for the planning problem by developing a polynomial-time $(1-{1}/{e})$-approximation algorithm (asymptotically and in expectation), based on a novel combination of randomized LP rounding and a time-correlated (interleaved) scheduling method. Furthermore, our algorithm achieves improved guarantees -- compared to prior work -- for the case where more than one arms can be played at each round. Moving to the bandit setting, when the mean payoff functions are initially unknown, we show how our algorithm can be transformed into a bandit algorithm with sublinear regret.
BibTeX
@inproceedings{papadigenopoulos2022non,
  author = {Orestis Papadigenopoulos and Constantine Caramanis and Sanjay Shakkottai},
  title = {{Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=Eq3QLg6aXv},
}
Figure