Abstract
The stochastic multi-armed bandit (MAB) setting has recently been extended to the non-stationary regime, specifically where the mean payoff of an action is a non-decreasing function of the time elapsed since it was last selected. This "recharging" model captures critical behavioral dynamics in recommendation platforms and digital advertising, where repeated exposure to the same content leads to diminishing returns. Even with full knowledge of payoff functions, finding an optimal schedule is NP-hard. This paper introduces a polynomial-time $(1-1/e)$-approximation algorithm for the planning problem, significantly improving upon the previous state-of-the-art $1/4$-approximation. Furthermore, we extend this to the bandit setting where payoff functions are initially unknown, providing the first algorithm for this problem with provably sublinear regret.
Introduction
Standard Multi-Armed Bandit models typically assume stationarity—the expected reward for an action remains constant over time. However, in real-world applications like newsfeed curation or music streaming, user engagement (the payoff) is often a function of novelty. If a platform serves the same content repeatedly, the payoff drops; if it waits, the content "recharges" its potential value.
This paper addresses the Non-Stationary Bandits under Recharging Payoffs (k-RB) problem. In this setting, playing an arm causes its payoff to reset to zero, after which it recovers according to a specific recharge function. The challenge is twofold:
- Planning: Determining the optimal sequence of plays to maximize long-term reward when functions are known.
- Learning: Maximizing rewards when the recharge functions are unknown and must be learned through exploration.
The Planning Challenge: Randomize-Then-Interleave
Computing an optimal schedule in the recharging model is NP-hard. Prior work achieved only a $0.25$ approximation ratio for the single-arm case ($k=1$). This paper introduces the Randomize-Then-Interleave algorithm, which leverages a novel combination of Linear Programming (LP) and scheduling theory to achieve a $(1-1/e) \approx 0.632$ approximation.
1. LP Relaxation and Sparsity
The authors first formulate the problem as an LP to determine the optimal average payoff. A crucial technical insight is the discovery of a sparsity pattern in the LP's extreme point solutions. They prove that in an optimal solution, almost every arm is associated with exactly one "critical delay" (the frequency at which it should be played). Only one "irregular" arm might require being played at two different frequencies.
2. Randomized Rounding
To resolve the ambiguity of the irregular arm, the algorithm employs a randomized rounding step. This selects a single critical delay for the arm, effectively reducing the complex recharging problem into a simpler "Heaviside" instance—where arms provide a constant payoff only after a specific recovery threshold is met.
3. Interleaved Scheduling
Finally, the algorithm uses a time-correlated scheduling method to transform these frequencies into a concrete sequence of actions. This ensures that arms are played at the appropriate intervals while minimizing collisions (instances where multiple arms compete for the same time slot). The analysis utilizes the "correlation gap" for submodular functions to prove that this interleaved schedule performs nearly as well as an idealized independent schedule.
Moving to the Bandit Setting
In the true bandit setting, the agent does not know the recharge functions. The authors adapt their planning algorithm into an Explore-then-Commit (ETC) framework.
In the exploration phase, the agent plays arms at various delays to estimate the underlying recharge functions. Once the estimates are sufficiently accurate, the agent "commits" to the schedule generated by the Randomize-Then-Interleave algorithm. This approach yields a regret bound of $\tilde{O}(T^{2/3})$, ensuring that the average loss per round relative to the optimal planning strategy vanishes as time $T$ increases.
Key Results and Impact
- Planning Breakthrough: The approximation ratio for the 1-RB case is increased from 0.25 to 0.632.
- Generalization to k-RB: For settings where $k$ arms can be played simultaneously, the algorithm achieves a guarantee of $1 - O(1/\sqrt{k})$. For $k=10$, this results in an 87% approximation, a significant jump from the 57% achieved by previous methods.
- Sublinear Regret: The paper provides the first formal proof of sublinear regret for the recharging bandit problem, establishing a theoretical foundation for learning in these non-stationary environments.
Conclusion and Future Directions
This work bridges the gap between theoretical bandit models and the practical realities of recommendation systems. By improving the approximation ratio to the $1-1/e$ barrier, the authors provide a robust framework for handling recharging payoffs.
Future research may focus on closing the regret gap, potentially moving from $T^{2/3}$ to the $T^{1/2}$ rate common in other bandit variants through Upper Confidence Bound (UCB) techniques. Additionally, determining whether a Polynomial-Time Approximation Scheme (PTAS) exists—allowing for a $(1-\epsilon)$ approximation—remains an open and compelling question for the community.
Summary updated