Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret
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 arm
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.