Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret
Authors: Orestis Papadigenopoulos
Constantine Caramanis
Sanjay Shakkottai
Venue: NeurIPS 2022 Accept (2022)

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.

Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret
Orestis Papadigenopoulos Department of Computer Science The University of Texas Austin papadig utexas. edu
Constantine Caramanis Department of Electrical and Computer Engineering
The University of Texas at Austin
constantine@utekaa edu
Sanjay Shakkottai
Department of Electrical and Computer Engineering The University of Texas at Austin sanjay- shakkot tatttttttttttttataee edu
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 was last played. This model captures natural behavioral aspects of the users which crucially determine the placement systems, and more.
performance of recommendation platforms, 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 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. this setting, significantly improve the best-known guarantees for the planning problem by developing a polynomial-time (1 1/e)-ape -approximation algorithm (asymptotically and in expectation), based 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 initially unknown, show how algorithm can be transformed into a bandit algorithm with sublinear regret.
Introduction
In the last two decades, the predominant rise of the social media industry has made notion of newsfeed integral part of our lives. In newsfeed, items (posts, photos etc.) particularly selected by the platform according to her/his preferences. Apart from social media, analogous idea potentially relabeled also appears in different domains as, for example, "frequently bought together" in e-commerce, "shuffling similar songs" in music recommendation, "recommended articles" in scholarly literature indexing databases. Whether it measured in terms of click-rate or time devoted, the high-level objective newsfeeds is fairly well-known: to maximize the user's engagement with the platform. In many applications, however, achieving this objective is not as simple as identifying the user's "favorite" content, given that her/his satisfaction can depend the time passed since the same (or similar) content has been observed. As an example, user's 's engagement can worsen if social media feed (resp., a music recommendation platform) constantly presents content from the same source (resp., same artist).
observes structured sequence of content
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Motivated by such scenarios, researchers have recently studied online decision making problems capturing the notion of "recovering" payofts, namely, scenarios where the payoff of an action drops (to zero) after each play and then slowly increases back to baseline. In the context of online learning, these non-stationary models interpolate between multi-armed bandits, where the environment is assumed to be intact, and reinforcement learning, since the actions may now alter the future environment in a structured manner. These models are wide enough to capture many real-life applications, yet special enough to accept efficiently computable (near-)optimal solutions. In this direction, the following general model was first introduced (under slightly different assumptions) by Immorlica and Kleinberg [IK [8] and has been recently studied by Simchi-Levi et al. [SLZZ21]]
Problem (Multi-armed bandits under recharging payoffs). We consider a set of actions for arms), where each arm i is associated with mean payoff function p;. For each T, pi(T) is the expected payoff collected for playing action i, when i has been played before exactly rounds (we refer to as the delay of an arm at a specific round). For each arm, we assume that its function:: (a) is monotone non-decrease non-decrg in T, and (b) has a known finite recovery time, namely, a specific delay after which the function remains constant. At each round, the player pulls a subset of at most actions, observes the realized payoff's of the arms played (each computed with respect to the delay of the corresponding action), and collects their sum. The objective is to maximize the expected cumulative payoff collected within an unknown time horizon.
We denote by k-RB an instance of the problem where at most h arms can be played at each round. Further, we distinguish between the planning setting, where the payoff functions are known to the player a priori (thus, payoff' can be considered deterministic), and the learning setting, where these are initially unknown and the user assumes semi-bandit feedback on the payoff's of the played actions. In the former case, the goal is to design an efficient algorithm which closely-aprroximates the optimal planning (since this is generally an NP-hard problem), while in the latter, the objective is to construct a bandit algorithm of sublinear regret, defined as the difference in expected payoff between a planning algorithm and its bandit variant due to the initial absence of information of the latter.
1.1 Background and Related Work
Immorlica and Kleinberg [K first study the 1-RB problem and provide a (1 - c) -aapproximation (asymptotically) for the planning setting, under the additional assumption that the payoff functions are weakly concave over the whole time horizon. On the other extreme, Basu et al. [BSSST9) provide long-run (1 - -/e-apprrxiinttinn for the case where, after each play, an arm cannot be played again for a fixed number of rounds problem which can be cast as a special instance of 1-RB using Heaviside step payoff functions | Shortly after the introduction of the problem, number
of special cases and variations have been studied [CC20 PC21 PBG19 BPCS2I BCMTT20
CCB20 LCCBGB22 APB (we address the reader to Appendix for overview).
In their recent work, Simchi-Levi et al. [SLZZ21] study the k-RB problem and prove the first ((1)=approxinationn guarantee under no additional assumptions. For large k. this result is the state- of-the-art. However, for small k. understanding the magnitude of the constant becomes the primary theoretical question. Specifically, the motivating case of newsfeeds (when, for instance, the content items are presented to a user sequentially) can be modeled as an instance of 1-RB. In this case, the approximation guarantee of [SL.7Z21] becomes 1/4, which is significantly weaker compared to both the (1 <) apapproxximation of [IKI for concave functions and the (1 a/e)-aaproxinatioon of [BSSS19 for the most "extreme" example of monotone convex functions, i.e., that of Hcaviside step functions. The above observation indicates that either the approximability status of the problem is not well-understood, or that the problem does not gradually become "easier" by increasing the concavity of the payoff functions.
1.2 Technical Contributions
In our work, we resolve this discrepancy by designing a long-run (1 - apa--approximation algorithm (in expectation) for 1-RB, which improves the state-of-the-art due to (SLZ721] Simultaneously, our algorithm enjoys the same asymptotic guarantee of (1 (())E)) for the general case of k-RB as in Simchi-Levi et al. [SLZZ2 with improved and explicit constants, as opposed to the guarantees of [SLZ211 which do not come in a closed-form (see Table || for summary of the best-known
Recall that the Heaviside step function is defined such that (T) 1 for and H(T) 0, otherwise.

---

Payoff functions
State-of-the-an
Reference
This work
Non-decreasing, concave, Lipschitz Scaled/translated Heaviside step
(1 (1-e) ---PTAS for
[K
1 for
BSSSI9
//
max a+I kita
i for any k
SLZZ21
k
aE24
Non-decreasing (finite recovery)
for k =1
SL7721
//
at2, a+1 K+a for any k
max k
SLZZ21
k
Table I: Summary of existing results (approximation guarantees) and our improvements.
approximation guarantees). Our algorithm is based on novel combination of linear programming (LP) rounding and a time-correlated (interleaved) scheduling method, and significantly simpler to implement compared to prior work. For the case where the mean payoff functions are initially unknown, we show how our algorithm can be transformed into bandit algorithm with sublinear regret guarantees.
1.3 Key Ideas and Intuition
Henceforth, we refer to any instance where the payoff function of each action has the form (T) = P: (T d.), where pa [o, 1]. d, E N. and (-) the Heaviside step function, as the Heaviside k-RB problem. The fact that our (1 approxxxxtnttoo for 1-RB matches the state-of-the- art bound obtained for Heaviside 1-RB BSSST PC21] is no coincidence. Our solution technique
shows that each k-RB problem is in fact (approximately) hiding a Heaviside k-RB problem.
Structural characterization of a natural LP relaxation. A key idea in both [K and SLZZ21
construct a concave relaxation of the optimal solution. Instead, we take more direct approach and construct a natural LP relaxation (see Section 3 of the optimal average payoff (our construction uses uniform upper bound on the recovery time of any arm). By carefully analyzing the structure of our LP, we prove that its extreme point solutions follow a particularly interesting sparsity pattern: there exist unique delays [T; associated with the arms (which we refer as "critical" delays), such that playing each arm i exactly once every т; rounds matches the average payoff of the relaxation. As we show, an exception the above rule can be at most a single arm, which we refer to as irregular. The above observation already hints that our problem could potentially be reduced to an instance of Heaviside k-RB for which better approximation guarantees (compared [SI7Z22] are known to exist (at least for small k) BSSS19 PC21
Improved approximation guarantees for the planning k-RB. Constructing planning where each arm is played at a rate indicated by its critical delay (as described above) is generally infeasible, since these rates stem from a relaxation of the problem. However, targeting these rates becomes the starting point our approximation. In Section 4 we design novel algorithm for the k-RB problem, called "Randomize-Theni Inte-lnter,,avee, which starts from computing an optimal solution to our LP relaxation. By combining the sparse structure of this solution with a randomized rounding step for determining critical delay for the (possible) irregular arm, our algorithm produces "proxy" instance of the Heaviside k-RB problem. Finally. the algorithm applies the interleaved scheduling method of [PC21] on the resulting Heaviside k-RB instance. As we prove, the above algorithm (ap)))-appoximattooo guarantee (in expectation), but with improved and explicit constants compared to [SL7721]. Importantly, for the particular case of k-RB, our guarantee is stronger than the one provided in the original work of [P22T]
achieves a long-run (1
As a first step, in Section we study the performance of our algorithm under the simplifying assumption that the solution returned by our LP relaxation does not contain an irregular arm, that is, every arm is associated with unique critical delay. For this case, the approximation guarantee of our algorithm follows by critically leveraging existing results on the correlation gap of the weighted rank function of uniform matroids due to [Yan I (see Section 2 In Section 2 we relax this simplifying assumption by carefully studying the contribution of the irregular arm to the produced solution. Our strategy relies on the novel idea of considering parallel (fictitious) copies of the irregular arm, one for each possible critical delay. While the marginal probabilities of each copy being played under the corresponding delay at any round are consistent with the initial LP solution, these events mutually
3

---

exclusive. Nevertheless, we show that expected payoff collected can only decrease by assuming that the parallel copies were instead independent. Having established that, the analysis reduces back to the "easier" case where an irregular arm does not exist.
bandit adaptation with sublinear regret. Finally, we turn our focus to the learning setting, where the mean payoff functions are initially unknown, and the player has semi-bandit feedback on the realized payoffs of the played arms of each round. In this setting, we begin by analyzing the robustness of our planning algorithm under small perturbations of the payoff functions. Then, provide sample complexity results to bound the number of samples required to get accurate estimates of the mean payoff functions. By combining the above elements, we transform into a bandit one, based on an Sxxplorethee-Commeee (ETC) scheme, and prove that the latter achieves sublinear regret relative to its planning counterpart. We present these results in Section
planning algorithm
All the omitted proofs of our results have been moved to the Appendix.
Preliminaries
Problem definition and notation. We consider set A (1,2....,m) of actions (or arms), where each arm i E A is associated with a (mean) payoff function p; - [0, 1]. For each T E N, (T(T) is the expected payoff for playing action E A, when i has been played before exactly rounds (i.e., T == 1 if the action has been played in the previous round). We refer to the number of rounds since the last play of an arm as the delay. For each arm E A,, we assume that the function P:(T): (a) is monotone non non-decreasing in T, and (b) has a polynomial recovery time T: such that PT(T) = P: (T,"ixxx for every T 2 maxx We assume knowledge of universal upper bound max on the recovery time of all arms, i.e., max maxic n_max At each round, the player plays a subset of at most & < n actions and collects the sum of their associated payoffs (each computed with respect to the delay of the corresponding action the time it is played). The objective is maximize the cumulative payoff collected within an (unknown) horizon of T rounds. We refer to the above instance as R-RB.
As a convention, we assume that the delay of each arm is initially equal to (i.c., all arms are played at time f 0). Note that, even if we assume that all arms start with delay max (i.e., the arms have never been played before), our results do not change qualitatively.
For any non-negative integer E N, we define [n] {1, 2....... ... set 5 C [n]. we denote w(S) Lies WT. Finally, throughout this work we assume that, when comparing between different payoffs, ties are broken arbitrarily.
m). m... For any vector E R" and
Continuous extensions and the correlation gap. Let f: 21r) - [0, oo) be set function defind
over a finite set of n elements. For any vector y E [0, 1|", we denote by D(y) a distribution over
2|n] with marginal probabilities y = (ji)ve(n)- We denote by S ~ >D()) random subset S C [x]]
sampled from the distribution D(y). Further, we denote by S I(y) random subset S S [n]
which is constructed by adding each element E [n] to S, independently, with probability yi.
We recall two canonical continuous extensions of set function (see [CCPV0Z Schos) ):
Definition 2.1 (Multi-linear extension). For any vector y [0, 1]", the multi-linear extension of sei function f is defined as
F(y)
E SwIly)
[[()]]=
Σ f(S)
9/ II vy).
SC(R]
igS
Definition 2.2 (Concave closure). For any vector y E [0, 1]", the concave closure of set function is defined as
ft(y) = sup Ply) SwD(y)
[f(S)] = sup
Σ asf(S)
Σ
agls = Σ ag - aa=
SCIml
SCIml mm]
SCIm
where 1s E {0, 13th is an indicator vector such that (1s); = 1, if E S, and (1s): = 0, otherwise.
DDue to the polynomial recovery time assumption, oracle access to the payoff functions not required.

---

For any non non-negative weight vector w E [0, oo)", of particular importance in the analysis of our algorithm is the function fw,k 2(x) + [0, 2o), defined as
(S) max m I and [1] S k).
(I)
We remark that J corresponds the weighted rank function of the (rank-k) uniform matroid under weight vector and, hence, non-decreasing submodular [Sch033
We denote by Fw,k and fw.
the multi-linear extension and the concave closure of fw.k, respectively.
fl The following result
The correlation gap ADSY TO of a set function is defined as supye[0,11 Fly)
due to I provides upper bound the correlation gap of fw.+(-):
Lemma 2.3 (Correlation gap [I) Let fw.k 2 - 00) be the weighted rank function of the rank-k uniform matroid. Then. for any vector y [0, 11"h we have
(1 (1-
s (1
F (y) Fw)
(y)
V2
3 Structural Properties of a Natural LP Relaxation
We consider the following LP relaxation which applies to any planning instance of k-RB:
maximize:
ΣΣ
(T(T)
Fi.T
(LPx)
x²
HETTEN
s.t.: ΣΣ Di,7 S k.
(C.1)
BEATEN
Σ r Fi, & 1, Vi A. TEN
(C.2)
In the above formulation, each variable Fi.r denotes the fraction of time where arm i is played under delay r -- namely, exactly time steps after was played for the last time. In (LPg) constraint (C.T) follows by the fact that the total fraction of time where any action can be played (under any delay) cannot be more than Further, constraints C.2 are valid constraints for the fractional plays of any individual arm under different delays.
We start by proving that the optimal solution of optimal average expected payoff:
asymptotically an upper bound on the
Lemma 3.1. For any instance of the k-RB problem, let V be the optimal value of LL and OPT(T) be the maximum payoff that can be collected in time horizon of rounds. Then
OPT(T)-
Assuming knowledge of an upper bound max 2 maxie max) on the maximum recovery time of any action, optimal extreme point solution (L
be computed in polynomial time:
Fact 3.2. There exists optimal solution to (. which is supported in (Iirr Ei Further, given an upper bound max on the maximum recovery time of any action, an optimal extreme point solution to LL can be computed in polynomial time.
Let us introduce the notion of supported actions:
Definition 3.3 (Supported actions). For any (potentially infeasible) solution LL we say that an action i E A is supported in x. denoted by E A(x), if there exists T E N such that Di, > 0.
We introduce the following class of solutions:
Definition 3.4 (Delay- solutions). We say that vector x (xi,r)ie is delay- feasible,, if for each supported action E A(x) there exists at most one non-zero variable Ti,50 and for this variable it holds 3i.r, = 1//,, Further, say that is almost-delay-feasibbe possibly with the exception of single arm 1. E A(x), for which there exist at most two non-zero variables Ze.r... I F1,5.,
it is feasible
such that ILTT.. 1/T,, and Te,T. 2/r,,, v. In the case of almost-delay- feasible solutions, we refer to as the irregular arm.
A function f: 2() R. is submodular, for any S,1 E [n], holds f(SUT)+ {())+
5

---

We remark that delay-feasible solutions subsume by definition ceassstdella--fssssii solutions and that a (almost- jdelay-feasiee solution is not necessarily a feasible solution (LP
As we prove the next key-lemma, any extreme point solution of (LP&) is almost-delayffesiilee
Lemma 3.5 (Sparsity pattern of extreme point solutions). Let x be any extreme point solution of
Then, x is almost-delay aimost-delay-eeasbble
Improved Approximation Guarantees for Planning
For any instance of k-RB, our algorithm (see Algorithm [ below). called "Randomize- Then- Interleave", constructs feasible planning schedule without requiring knowledge of the time horizon. We remark that for the planning setting of the problem, we treat the payoff of any arm under any possible delay as deterministic.
The algorithm starts from computing optimal extreme point solution x" this solution to determine a critical delay T. for each supported arm i E A((x) By Lemma 3.5 we know that x* -eaasssl which means that possibly with the exception of a single irregular arm ( --foo for every arm E A(x*) \ {4), there exists a unique
LP and then uses
such that _ 1/T, > 0. \ {c}. In the
Thus, Algorithm D sets this unique tj to be the critical delay of each arm i A(x") case where an irregular arm 1 A(x*) exists, then, by Definition 3.4 there exist most two distinct Te.o: Tub with " and Fi,,,, 2 0, in which case the critical delay T." of is set to Ti, or Tu,b. with marginal probability T,,.. and Tr,6",,,.... respectively. Notice that by constraints
of LL& the above sampling process is well-defined, since Te,a + Te,bRi, I 1. In the case where no T. is sampled, the irregular arm is removed from A(x*). After computing the critical delays, for each arm E A(x*) the algorithm draws random offset r; independently and uniformly from {0, 1, 7
Algorithm 1: Randomize- Ceeieniiz--hee--eeeeee Interllneeee
/+ Initialization phase
Compute an optimal extreme point solution x* to LP.
Let i A be the irregular arm (if such arm exists).
for each arm E A(x')) \\ {(} do
N which satisfies 27,r 1/r. an irregular arm A(x*) exists then
Let 7e be the unique
Let Ti,a: Ti,b E N be such that TT,T,a > O, x GTih 2 O, and Ti,a # Ti,b
Set Pa <- T,, and Pb <- T,,b"",
Sample r." from (Ti,as Teb, 20} with marginals Pa. Ph. and Pa Pb, respectively.
- Do then
Remove from A(x*).
for each arm E AAxx*) do
Sample an offset r; uniformly at random from {0, 1, 1,..,...,7 77 1}.
** Online phase
for f 1, 1,,2... 2.... do
Let C. C be the subset of candidate arms, defined C. (i E A(x*) mod =
Play the maximum-payoff subset of k arms in Cr, namely, A, = argmax DiesPi(or..)
scC(,1S)sk
where oie (actual delay) is the time passed since arm was last played before t.
After initialization, Algorithm proceeds to its online phase where, at each round f, it first computes subset of candidate arms C., namely, all arms E A(x") which satisfy & mod π. rt. Then, the algorithm computes the maximum-payoff subset A, of at most candidate arms, computed using their actual delays (the number of rounds passed since last play), and plays these arms.
4.1 Approximation Analysis: Assuming Delay-Feasible LP Solutions
We now present an analysis of the approximation guarantee of Algorithm foor general In order to facilitate the presentation, first focus special class of "casy" instances, where the optimal

---

extreme point solution x" of LL is delay-feasible (i.e., there is no irregular arm). Consequently, we show how this assumption can relaxed at the expense of additional technical effort.
Recall that we denote by A(x*) the set of arms that are supported in the solution x". Notice that, since x" is delay-feasible by assumption, the only source of randomness in Algorithm is due the random offsets. Since each offset r; is sampled independently and uniformly from {0, 1,..., T 1}
and E C if and only if mod 7 = ri, the following fact is immediate:
Fact 4.1. Let {T, )(A(())) be the critical delays of the supported arms. At any round t, each arm i A(x*) belongs to C₁ independently with probability l/r,.
Let us focus on the expected payoff collected by Algorithm I at any round t 12 - By our simplifying assumption that x" is delay-feasible, for each supported arm i E A(xx), there is a unique critical delay T,', such that ";;;; 1/+2 is the only non-zero variable of x" corresponding
We construct a vector y = [0, 1]", such that yi = 1/r, for each E A(x*), and yi = 0, otherwise. Further, let us define a vector E [0, oo)" such that w, p.(T,) for each E A(x"), and = 0, otherwise. Recall that for any fixed round & 2 - by definition C, and the construction of the offsets, the events {i E Ciji are independent. Hence, we can think of C, as a random set, where each arm E A belongs to Ce independently with probability y/ namely, C₁ ~ I(y).
Let A, = argmax ExEs (T(),) be a set of at most k arms in C which maximizes the total payoff SCC,,18KSk
measured with respect to the critical delays. By construction of C. the actual delay di, of each i E A(x*) is (deterministically) lower bounded by 7;" since any arm must be candidate in order to be played (which happens exactly every 7/ rounds). Thus, for the expected collected payoff of any round 2- 7 max we have
E Ce-I(y)
max SCC,,ISIsk IES
Eplord E CrII(y)
max sgC,,Is iES
Ep((T.))
E CrIIly)
(w4)]. (2)
Sk
Using Equation in combination with Definitions
2.1 and 2.2 we get
kb
[w(A)]
TE (Sw (. F (y)) 2
S (t)
(3)
Ci~I(y)
Ci~I(y)
chiR!!
where the last inequality follows by Lemma
The following technical lemma relates f (y) with optimal value of LP
Lemma 4.2. For any vectors w E [0,, (o) and y E 1jm, let I (y) be the concave closure of the weighted rank function of the rank-k uniform matroid with weights w, evaluated at y. Then, i satisfies y || S k, it the case that xt)) 2 Eie(n) wah.
Let 4 be the optimal value of (Px)) Since y 11 S k. then by applying Lemma 4.2 with vectors and y constructed above, have that
(t)
Σ XE ml]
wi . y1
Σ tEA(x*)
pe(TT)
xi:; V
By combining Equations expected payoff collected by Algorithm is at least R*/ /+///)))-iii -times the average optimal payoff. By using linearity of expectations together with the fact that all payoff's are bounded in [0. 1J. we can prove a long-run (1 - /e*we) approximation guarantee (in expectation) for instances where x" is delay-feasible.
with Lemma 3.I it follows that, for any round 2 max the
In the rest of this section, we show how the above analysis can be extended for the general case where x" is almost-delay-feasiie feasible (i.e., an irregular arm exists).
4.2 Approximation Analysis: Handling the Irregular Arm
We now extend the analysis of Section 4.T and relax the assumption that the optimal extreme point solution of (LPx) is delay-fcasible.
7

---

Let x" be an optimal solution to L.P and let e E A(x') be the irregular amm with Ti and T.b being the two potential critical delays such that Z2, L T. 2 0 (with at least one of zi, and Fi,,,, being strictly positive, by Definition 3.4). Instead of conditioning on the sampled critical delay of the irregular arm we construct two (fictitious) parallel copies ba and l6 - one for each possible realization (and associated payoff). Let define A'' A(xx) \ (1) U (fa; 4b) to be the set of supported arms of x", where we replace the irregular arm e with the two parallel copies to and 46-
In the next lemma, we characterize the marginal probability that any arm in A' is added to the set of candidate arms at any round. Notice that, as opposed to Fact 4.I the randomness in this case is taken over both the sampling of a critical delay for the irregular arm well as the random offsets.
Lemma 4.3. For any arm E A' and at any round I, we have that P li E C. and T = 7] o
Notice that, for the parallel copies of the irregular arm, the events {4a Cc} and {4s C.} are now dependent and, in particular, mutually exclusive (since, eventually, at most one of them is realized). However,
able to show that the expected payoff collected at any round 2 m can only decrease if the two events were instead independent with the same marginal probabilities.
For convenience, we relabel the arms in A' in non-increasing order of p. (T7") (breaking ties arbitrarily). Note that by exchanging with the two copies la and is the cardinality of A'' can be at most n + 1.
Let us construct a (n + 1)-dimensional vector y E [0, 1 such that yi = -,,; for any E A', and y: otherwise. Further, we construct a weight vector w [0, 0o)*+1, such that w; pb((T) for any E A', and w; = O, otherwise. Let D(y) be distribution over subsets of A', where every arm i A' Mta 4 (except for La and (6) added a S D(y). independently, with probability ",.. The arms and are also added to S ~ D(y) with marginal probabilities Fi..T;, and x ii,,7 respectively, yet not independently (since they are mutually exclusive). Therefore, by the above definitions and Lemma 4.3 the set of candidate arms at any fixed round 2 m is distributed as C. ~ D(y).
Let us fix any round / 2 m_ Similarly to Section by using the fact that the actual delay di,r of each arm E A' is deterministically lower bounded by its critical delay T;", we can lower bound the expected payoff collected by algorithm at time t
E CuvD(y)
max SCC.. Epsoow)
2
E CoNDly)
max SCC,, Si
Σ PP((ss) iES
[fm,)( CwNDyy)
E
(5)
where D(y) is defined as described above.
As we show in the following lemma, the RHS of the above inequality can only decrease, if we replace G. ~ D(y) with C, I(y), namely, if we assume that the copies la and 4 are added to Ca independently, but with the same marginals (y., and ye,, respectively). As we show in the following lemma, the above property in fact holds for any submodular function (including fw.k):
Lemma 4.4. Let f 2(m) + R be a submodular function over ground set of elements, where n 2 2. Let I(y) be a distribution over 2|m], where each element i is added in set 5 ~ I(y), independently, with probability y:- Further, let D(y) be a distribution over 2 where each element set S D(y), independently, with probability yi. except for two distinct elements las 4, whose addition to is mutually exclusive but with the same marginals ye.. and you respectively. In this case, we have
i E [n] {Lay"e} is added
E SwyDy)
[f(S)]
E [F()].
S~I(y)
By combining inequality 5 with Lemma 4. for n + 1 elements (recall, the function fw.A. is submodular), the expected reward collected any round max can be lower bounded
EE Ci~Dly)
max SCCt,18|Sk iES
Epiloua)
2
[f [.w.(CC)] CrwDly)
E
E C,~Ily)
[sw.(CC)]] (y).
8

---

In addition, by combining Lemma 2.3 with Lemma for the above choice of vectors and (again, it holds || y 1l S k). for any max follows that
Ep.(os))
2 Fw,x(y) 2 (1
f., 2 (1
1t V'
CrnD(y)
max SSCr.18iSK YES
ekiR!)
ct
where V* is the optimal value of (LP
Finally, using the fact that V* 2 (PT by Lemma 3.1 and applying linearity of expectations over all rounds t, the following result follows directly:
Theorem 4.5. For any instance of k-RB, where OPT(T) is the optimal expected payoff that can be collected in T rounds, the total expected payoff collected by Algorithm 7 at least
1* (1- etk!!
OPT(T) ) - O(k m
(1-V2A)) OPT(T) - O max))
1 (2-2
We remark that, although the asymptotic approximation guarantee of Algorithm I is the same as the one in [SLZZ2T, the constants of our algorithm are significantly better. In particular, for k E {1, 2,3, 5, 10). the guarantees of [SLZZ2]] and Algorithm are {0.25, 0.33, 0.40, 0.44, 0.46, 0.57] and (0.63, 0.72, 0.77, 0.80, 0.82, 0.87,, respectively.
Online Learning with Sublinear Regret
In this section, we consider the learning setting of k-RB where the payoff functions are initially unknown. At each round, the player plays subset of at most & arms and observes the realized payoff of each individual arm played (semi-bandit feedback). Every time an arm i A played under delay the realized payoff' is drawn independently from distribution of mean Pi(T), bounded in [0, 1]. For this setting, our goal is to show that there exists a bandit variant of Algorithm with sublinear in-approximate regret guarantee for k-RB, defined as
Reg (T) Yk OPT(T) R(T),
where "i = 1 fe'x! k! is the (multiplicatiie) approximation guarantee of Algorithm D and R(T") is the total expected payoff collected by the bandit algorithm T rounds.
As first step, we study the robustness of Algorithm under small perturbations of the payoff functions; in particular, we analyze its approximation guarantee when it runs using estimates {Px Je instead of the actual payoffs (pr He.A. We remark that the monotonicity of the (estimated) payoff functions is not required for the correctness of Algorithm I but only for proving its approximation guarantee.
Robustness Algorithm[1 |
Lemma 5.1. Let p. be an estimate of the payoff function ps for each i A, such that (()) =
VT E N for some E (0, 1). The expected payoff collected in T rounds by Algorithm when it uses the estimates instead of the actual payoff functions, lower bounded by
Tke OPT(T) - O(k: E - max
Estimation of the payoff functions. the number of samples required for each arm-delay pair in order to get an e-estimate p; for the mean payoff function Pt of every arm E A.
By using standard concentration results (oeb3), we bound
Lemma 5.2. For any e (0, let pc(T) be the empirical average of samples drawn from Ps(T) (2T (2Tmarr n2) samples, where n is the number of arms. Then, with probability 1 it holds (T( px(T) < for every i A and max)
for every arm i E A and delay T, using m 22 In
The following observation provides an upper bound on the number of rounds required in order to get m samples for each arm- arm-delay pair in any k-RB instance:
Fact 5.3. any k-RB instance, the number of rounds required collect m independent samples from (T()), for each arm i E A and delay [axx,, is upper-bounded by ( /

---

Bandit algorithm with sublinear regret. By combining the above elements, it is easy to design an Baglore-then-oommee (ETC) variant of Algorithm | achieving sublinear regret in the bandit setting. For simplicity. we assume here that the time horizon T is known to the player an assumption that can be relaxed using the doubling trick method [LS20].
Let m = 1/2.² In n/5) for some e, E (0, 1). In the first O(m(("ma))) rounds, the bandit algorithm collects independent samples from pT()), for each AA and E [-=ax]_ Then, by taking the empirical average of these samples, it constructs estimates (T( for each i and т. For the rest of the time horizon, the algorithm simulates Algorithm using the empirical estimates (T( in
place of the (initially unknown) payoff functions.
By setting the parameters e, 8 accordingly and combining Lemmas 5.1 and 5.2 with Fact 5.3 prove the following result:
Theorem 5.4. There exists a learning adaptation of Algorithm 7 in the semi-bandit setting, for which the "pppproxiette regret for T rounds can be upper-bounded as
O (n2/3. (k 7110002222233 In ( (m .72/3 k. mm)
Conclusion and Further Directions
Following the recent line of work non-stationary bandits with recharging payoffs, revisited one of the most general formulations studied in the area and significantly improved the state-of-the-ar for the planning setting. In particular, when at one arm is played per round, we designed an algorithm that collects at least 63% (asymptotically and in expectation) of the optimal payoff, improving the best-known 25%, due prior work. By providing results the robustness and sample complexity of our algorithm, we transformed the latter into a bandit algorithm with sublinear regret. Our work leaves a number of interesting open questions. An approximation guarantee of (1 - (1))/e) has been proved to be the best achievable under standard complexity assumptions - for number combinatorial problems. Therefore, an immediate future direction would be either provide matching hardness result for the planning setting of the problem, or to further improve on the best-known approximation. Another interesting question would be explore whether one can design bandit adaptation of our algorithm with improved regret guarantees. Finally, the empirical evaluation of our algorithm on real (or artificial) data another interesting direction.
Acknowledgements
This work partially funded by the NSF IFML Institute (NSF 2019844), the NSF AL-EDGE Institute (NSF 21 12471), and NSF 1704778.
10

---

References
[ACBF02] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(22:235-2566 2002.
[ADSY10] Shipra Agrawal, Yichuan Ding, Amin Saberi, and Yinyu Ye. Correlation robust stochastic optimization. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, page 1087-1096, USA, 2010. Society for Industrial and Applied Mathematics.
[AGO19] Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with unknown number of distribution changes. In Conference on Learning Theory, pages 138-158. PMLR, 2019.
[APB*21] Alexia Atsidakou, Orestis Papadigenopoulos, Soumya Basu, Constantine Caramanis, and Sanjay Shakkottai. Combinatorial blocking bandits with stochastic delays. In International Conference on Machine Learning, pages 404-413, PMLR, 2021.
[BCB12] Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and non- stochastic multi-armed bandit problems. Machine Learning, 5(1):1-122, 2012.
[BCMTT20] Nicholas Bishop, Hau Chan, Debmalya Mandal, and Long Than-Thanh Adversarial blocking bandits. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors. Advances in Neural Information Processing Systems, volume 33, pages 8139-8144 8149. Curran Associates, Inc., 2020.
[Ber00] Dimitri Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2nd edition, 2000.
[BGZ14] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed--andde problem with non-stationary rewards. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 1, NIPS' 14, page 199-207, Cambridge, MA, USA, 2014. MIT Press.
[BPCS21] Soumya Basu, Orestis Papadigenopoulos, Constantine Caramanis, and Sanjay Shakkottai. Contextual blocking bandits. In International Conference on Artifi- cial Intelligence and Statistics, pages 271-279 PMLR, 2021.
[BSSS19] Soumya Basu, Rajat Sen, Sujay Sanghavi, and Sanjay Shakkottai. Blocking bandits. Advances in Neural Information Processing Systems, 32, 2019.
[CCB20] Leonardo Cella and Nicolò Cesa-Bianchi. Stochastic bandits with delay-dependent payoffs. In International Conference on Artificial Intelligence and Statistics, pages 1168-1177. PMLR, 2020.
[CCPV07] Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to matroid constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 182-196. Springer, 2007.
[Git79] John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), (1): -164 1979.
[GMS10] Sudipto Guha, Kamesh Munagala, and Peng Shi. Approximation algorithms for restless bandit problems. Journal of the ACM (JACM), 58(1):1-50, 2010.
[Hoe63] Wassily Hoeffding, Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 1963.
[KK8]] Nicole Immorlica and Robert Kleinberg. Recharging bandits. 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 309-319, 2018
[KMMS10] Robert Kleinberg, Alexandru Niculescu-Mizil, and Yogeshwer Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2):245-272, 2010.

---

[KZ17] N Bora Keskin and Assaf Zeevi. Chasing demand: Learning and earning in changing environment. Mathematics of Operations Research, 42(2):277-377, 2017.
[LCCBGB22] Pierre Laforgue, Giulia Clerici, Nicolò Cesa-Bianchi, and Ran Gilad- Bachrach. A last switch dependent analysis of satiation and seasonality in bandits. In International Conference on Artificial Intelligence and Statistics, pages 97 17909 PMLR, 2022.
[LCM17] Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. In Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[LKKLM21] Liu Leqi, Fatma Kiline Karzan, Zachary Lipton, and Alan Montgomery. Rebounding bandits for modeling satiation effects. Advances in Neural Information Processing Systems, 34, 2021.
[LR+85] Tze Leung Lai, Herbert Robbins, al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
[LS20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[PBG19] Ciara Pike-Burke and Steffen Grunewalder. Recovering bandits. volume 32. 2019.
[PC21] Orestis Papadigenopoulos and Constantine Caramanis. Recurrent submodular welfare and matroid blocking enni-bandits. Advances in Neural Information Processing Systems, 34, 2021.
[PT99] Christos H Papadimitriou and John N Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293, 1999.
[Sch03] Alexander Schrijver. Combinatorial Optimization Polyhedra and Efficiency.
Springer, 2003.
[SGV20] Aadirupa Saha, Pierre Gaillard, and Michal Valko. Improved sleeping bandits with stochastic action sets and adversarial rewards. In International Conference on Machine Learning, pages 8357-8366, July 2020.
[SLZZ21] David Sanchi-Levis Zeyu Zheng, and Feng Zhu. Dynamic planning and learning under recovering rewards. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 9702-9711, PMLR, 18-24 Jul 2021.
[Tho33] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-22 222-2, 1933.
[TL12] Cem Tekin and Mingyan Liu. Online learning of rested and restless bandits. JEEE Transactions on Information Theory, 58(8):5588-500 5611, 2012.
[Whi88] Peter Whittle. Restless bandits: Activity allocation in changing world. Journal of applied probability, 25(A)2287-298, 1988.
[Yan Qiqi Yan. Mechanism design via correlation gap. In Dana Randall, editor, Proceedings of the Twenty-ecoond Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 201 I, San Francisco, California, USA, January 23-25, 2011, I, pages 710-719. SIAM, 2011.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See "Supplementary material".
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See "Supplementary material".
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section -
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs are included the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "N7CRw8Gq0K8", "reviewer": "Reviewer_uVwc", "summary": "The author studies a problem in which the reward of arms is increasing as the arms are not selected in the last rounds. At first, the author studied the problem of solving such an issue when the parameters of the problem are known. The first issue is to design an algorithm that effectively approximates the optimal solution to this problem. The author provide such an algorithm and studied its approximation properties. Finally, it provides an ETC scheme to deal with the case in which the learner is acquiring only bandit feedback. Finally, guarantees in terms of regret for this algorithm are provided.", "questions": "\nWhy are the proof so important? Are they providing novel techniques which are of general interest?", "limitations": "I do not foresee limitations and potential negative societal impact of the current work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think that the paper is well written. However, I think that the choice of the authors to include proofs and sketches of the prooofs is not effective to communicate the message of the paper. I think that such aspects, as well as the statement of some lemmas which are not central to the paper itself might have moved to the appendix to make room for some more comments and, possibly, to some final experiments.\n\nI think that adding a table to summarize the different results present in the literature and the ones provided in this paper would help to appreciate the value of this work.\n\nI think that adding a more formal definition of the bandit setting is necessary.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JliyvVbSxN0", "reviewer": "Reviewer_3yso", "summary": "Authors analyze and improved the existing results for the recharging bandits problem. They put a lot of efforts in the optimization/planning part and obtained strong improvements on that side.", "questions": "I have only few questions.\n\nThe first question I have is which technical difficulties authors have met in improving the planning stage. Specifically, I would like to understand how much the results of [PC21] and [Yan11] contribute in the obtained improvements.\n\nSecondly, I am wondering why developing an ETC approach rather than an UCB one as done by [Kleinberg and Immorlica].", "limitations": "See above.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and the contributions are clearly stated in particular thanks to paragraph 1.3. I found the literature review to be very complete.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7h6bCDNYkst", "reviewer": "Reviewer_Y2yC", "summary": "The paper studies a non-stationary bandit problem with $n$ arms, where the mean reward of an arm is a non-decreasing function of its \"idle time\" since last pull. It is assumed that each arm fully \"recovers\" after being idle for a certain number of periods, i.e., its mean reward does not change any further. An upper bound on the recovery time of all $n$ arms is also assumed known. At any time, the decision maker can play a subset of at most $k < n$ arms upon which she collects the sum of their associated payoffs. As is the norm, the goal is to maximize the cumulative expected payoffs over $T$ rounds, with $T$ possibly being unknown a priori. ", "questions": "Just out of curiosity: If T is also known, can the approximation ratio be improved? Alternatively, if T is known but not the max recovery time, can something be claimed at least for \"large\" T perhaps by using some appropriate sub-linear function thereof as a proxy for the latter?", "limitations": "This appears to have been well-addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It is well-known that computing an optimal policy even for the \"planning\" problem (assuming perfect knowledge of the mean reward functions) is NP-hard. Notably, the authors improve upon the current best known $1/4$-approximation guarantee for $k=1$ to $1-1/e$ achievable in polynomial time. For $k>1$ also, their algorithm achieves improved numerical guarantees vis-\\`a-vis extant work. Lastly, a learning version is also considered where the mean reward functions are initially unknown and decision maker only observes noisy semi-bandit feedback for the collection of arms played. For this setting, the authors propose an algorithm based on the Explore-then-Commit principle that is shown to incur sub-linear regret relative to its \"full information\" planning counterpart.\n\nOverall, the analysis appears sound (though I did not delve into details contained in the supplementary sections) and I reckon this paper makes solid theoretical contributions. I would therefore vote for an accept.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept