Linear Bandits with Memory
Authors: Giulia Clerici
Pierre Laforgue
Nicolò Cesa-Bianchi
Venue: Accepted by TMLR ()

Abstract: Nonstationary phenomena, such as satiation effects in recommendations, have mostly been modeled using bandits with finitely many arms. However, the richer action space provided by linear bandits is often preferred in practice. In this work, we introduce a novel nonstationary linear bandit model, where current rewards are influenced by the learner's past actions in a fixed-size window. Our model, which recovers stationary linear bandits as a special case, leverages two parameters: the window size $m \ge 0$, and an exponent $\gamma$ that captures the rotting ($\gamma < 0)$ or rising ($\gamma > 0$) nature of the phenomenon. When both $m$ and $\gamma$ are known, we propose and analyze a variant of OFUL which minimizes regret against cyclic policies. By choosing the cycle length so as to trade-off approximation and estimation errors, we then prove a bound of order $\sqrt{d}\,(m+1)^{\frac{1}{2}+\max\{\gamma,0\}}\,T^{3/4}$ (ignoring log factors) on the regret against the optimal sequence of actions, where $T$ is the horizon and $d$ is the dimension of the linear action space. Through a bandit model selection approach, our results are then extended to the case where both $m$ and $\gamma$ are unknown. Finally, we complement our theoretical results with experiments comparing our approach to natural baselines.

Published in Transactions on Machine Learning Research (05/2024)
Linear Bandits with Memory
Giulia Clerici
Funkka.clericci@umiimi..
Deportment of Computer Science, University of Milan, Italy
Pierre Laforgue
Department of Computer Science, University of Milan, Italy
Nicolò Cesa-Bianchi
nicolo. www.--biiacchh@uuiiiii...
Department of Computer Science, University of Milan, Italy DEIB, Politecnico di Milano, Italy
Reviewed OpenReview: https: openreview. net/ net/forun? id= CrpDuli
Abstract
Nonstationary phenomena, such as satiation effects in recommendations, have mostly been modeled using bandits with finitely many arms. However, the richer action space provided by linear bandits is often preferred in practice. In this work, we introduce novel nonstationary linear bandit model, where current rewards are influenced by the learner's 's past actions in a fixed-size window. Our model, which recovers stationary linear bandits as special case, leverages two parameters: the window size m 2 0, and an exponent 7 that captures the rotting (y < 0) or rising (y > 0) nature of the phenomenon. When both m and y are known, we propose and analyze a variant of OFUT which minimizes regret against cyclic policies. By choosing the cycle length so as to trade-off approximation and estimation errors, we then prove bound of order v (m+ 1) 1 73/1 (ignoring log factors) on the regret against the optimal sequence of actions, where T is the horizon and d is the dimension of the linear action space. Through a bandit model selection approach, our results are then extended to the case where both m and are unknown. Finally, we complement our theoretical results with experiments comparing our approach to natural baselines.
1 Introduction
Many real-world problems are naturally modeled by stochastic linear bandits, where actions belong to a linear space, and the learner obtains rewards whose expectations are linear functions of the chosen action (see e.g., Lattimore & Szepesvári (2020)). Formally, at each time step the expected reward is r (a,, 0*), where E I is the chosen action and 0" E Rd is a fixed and unknown parameter to be est Tn a song recommendation problem, for instance, the possible actions are the songs from the catalogue, usually represented by their feature vectors (Deshpande & Montanari, 2012; Korkut & Li, 2021; Ghoorchian & Maghsudi, 2022). The linear reward т, (i.e., the user satisfaction) measures how well the song a picked by the learner matches the (unknown) preferences of the user, represented by d". However, this model fails capture key aspect, i.e., the nonstationarity of the users' preferences. For example, user satiation with respect to the recommended items is a typical phenomenon in this context (Kapoor et al., 2015; Kunaver & Požrl, 2017), studied in rotting bandits (Bouneffouf & Féraud, 2016). Indeed, identifying the favorite song of a user (i.c., the vector in the action set that maximizes (a, 8*)) only partly solves the recommendation problem, as suggesting this song repeatedly is not meaningful in the long run (Kovacs et al., 2018; Schedl et al., 2018). But satiation is far from being the only nonstationary phenomenon observed in practice. In algorithmic selection for instance, one must choose among a pool of algorithms the one that is going to get the next chunk of resources (e.g., CPU time or samples). In this case, we expect the quality of the solution found by each algorithm to increase the algorithm gets selected. This model, known rising bandits,

---

Published in Transactions on Machine Learning Research (05/2024)
has been studied in deterministic (Heidari et al., 2016; Li et al., 2020) and stochastic (Metelii et al., 2022) settings.
Nonstationarity in bandits, which has been mostly studied in the case of finitely many arms, appears to be significantly more intricate to analyze in a linear bandit framework due to the structure of the action space. For instance, rotting bandits (Bouneffouf & Féraud, 2016) or rested rising bandits (Metelli et al., 2022) assumee that the expected reward of an arm is fully determined by the number of times this arm has been pulled in the past. In the linear case, on the contrary, one would expect nontrivial cross-arm effects. Listening to rock songs should affect the future interest in rock songs, but also to minor extent that in folk music, as the two genres are related. On the other side, it also seems reasonable that a folk rock song does not increase rock satiation as much as a pure rock song. Hence, & principled way to model nonstationarity in linear environments is needed.
In this work, we introduce a novel lincar bandit framework that allows to model complex nonstationary behaviors in an infinite and structured space of actions. More specifically, the nonstationarity is captured by matrix, determined by the past actions of the learner and affecting the expected reward of future actions. Formally, the expected reward at time step & becomes r; = (a, A,-10",, where A A(a:-1...., at-m)= (Ao + Σx= oe-aaT_a)" E Idxdd Here, Ag is some initial symmetric and positive semidefinite matrix. Typically, An is chosen to be the identity Ia, which we refer to as the isotropic initialization. The memory size m 20 0 controls the range of past actions having an influence, while the exponent y E IR quantifies their impact. A positive y corresponds to a rising behavior, and a negative 7 to a rotting one two established scenarios in the bandit literature. In the rotting setting, playing action a at time t decreases the expected reward of a at time t + 1. Hence, solving this problem requires long-term planning, and playing repeatedly 0' may not be optimal. Instead, in rising scenario with isotropic initialization, an optimal action played (and thus boosted) at time t remains optimal at time + 1. Although optimal policies are stationary in this case, note that such problems are intrinsically difficult as the learner is penalized twice: for not choosing a good action at the present time, but also at future time steps, for not having boosted the right action. We highlight that our approach is able to cope sinultaneously with these two different scenarios. Finally, note that our model recovers stationary linear bandits as a special case when 7 (or m and Ao = La).
We start by focusing on cyclic policics, and show that they provide reasonable approximation to the optimal policy (which may not be eyclic) while being easier to learn. When and y are known, estimating the best block of fixed length reduces to stationary problem, that we solve using a block variant of OFUL (Abbasi- Yadkori et al., 2011). When m = O, our variant recovers the regret bound (ddVT) of OFUL up to log factors. We then optimize the block length in order to balance the approximation and estimation errors, and obtain a bound on the regret against the optimal sequence of actions in hindsight, of order vd (m + +)22+mxx(700)7 (ignoring log factors) for all T 2 (md)². Finally, we extend our analysis to the case when m and Y are both unknown. For this case, prove regret bounds via extension of the bandit model selection approach of Cutkosky et al. (2020). Empirically, groedy strategy (playing the action with the best instantancous expected reward) and naive block lcarning approach. Our experimental results also include misspecified settings, where we learn 0 and simultaneously either m or 7.
approach is shown to outperform natural baselines, such as the oracle
Contributions.
We introduce new bandit. framework to model nonstationary eflects in linear action spaces. Our model generalizes stationary linear bandits, whose bound we recover special case.
We propose an ObUT-based algorithm achieving sublinear regret against the best sequence of actions by learning cyclic policies and balancing estimation and approximation errors.
We use a bandit model selection approach to learn the system's parameters m and 7.
Empirically, our algorithm outperforms natural baselines in both rotting and rising settings.
Related works. Stochastic linear bandits, which were introduced two decades ago (Abe & Long, 1999; Auer, 2002), are typically addressed using algorithms based ellipsoidal confidence sets (Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010; Abbasi- Yadkori et al., 2011). Nonstationary bandits have been mainly studied in the case of finitely many arms. Among the most studied models, there are rested (Gittins, 1979;
2

---

Published in Transactions on Machine Learning Research (05/2024)
Gittins al., 2011) and restless (Whittle, 1988; Ortner et al., 2012; Tekin & Liu, 2012) bandits, rotting bandits (Bounelfoul& & Féraud, 2016; Heidari et al., 2016; Cortes et al., 2017, 7; Levine et al., 2017; Seznec et al., 2019), bandits with rewards depending on arm delays (Kleinberg & Immorlica, 2018; Cella & Cesa-Bianchi 2020; Simchi-Levi et al., 2021; Laforgue et al., 2022), blocking and rebounding bandits (Basu et al., 2019; Leqi et al., 2021), and rising bandits (I.i et al., 2020; Metelli et al., 2022).
The d-step lookahead regret of Pike-Burke & Grunewalder (2019) is similar our regret against the best cyclic policy. However, while the lookahead oracle selects the best block based on the learner's current state, our oracle is defined independently of the learner's action. In this respect, our work investigates policy regret version of the lookahcad regret. Some works have also considered nonstationary bandit frameworks, where the unknown parameter 0* is then replaced by a sequence of vectors 0j that evolves over time. Standard assumptions then stipulate that 0r is piecewise stationary, with a fixed number change points (Bouneffouf et al., 2017; Wu et al., 2018; Auer et al., 2019; Chen et al., 2019; Di Benedetto al., 2020; Xu et al., 2020; Li et al., 2021), or that the variation budget Eisr ||0; 6--1 .ll is bounded (Besbes et al., 2014; Karnin & Anava, 2016; Luo et al., 2018; Cheung al., 2019; Russac et. al., 2019; 2020; Kim & Tewari, 2020; Zhao et al., 2020). See also Mueller et al. (2019) for an application of linear bandits to nonstationary dynamic pricing. In addition to these assumptions, we highlight that the above works are fundamentally different from ours, as the evolution of 0r is oblivious to the actions taken by the learner. This removes any need for long-term planning and puts the focus on the dynamic regret, where the algorithm's performance is compared to the rewards which one could obtain by picking at according to 0r. Finally, note that nonstationarity in linear bandit environments may also be tackled using Gaussian Processes (Faury et al., 2021; Deng et al., 2022).
We note that the idea of combining línear and rotting bandits was already discussed in Seznec (2020, Section 4.7), where the author provides some evidences on the intrinsic difficulty to do so. There, the author proposes an extension of rotting bandits to linear spaces of actions by summing along the different dimensions the projections of the past actions. It is however proved that such a model cannot be learned. Indeed, it is possible to exhibit an instance of this lincar rotting problem for which any policy suffers lincar regret. On the contrary, our analysis in Section shows that our model (based instead on the covariance matrix of the past actions) is learnable. The price we pay for ensuring learnability is that our model does not capture the K-armed rotting bandit sctting in its full generality, see Example 2 for more details.
Notation. Ba denotes the Euclidean unit ball, Oa and (ex)asd the zero and standard basis in Rd, La E Rdxd the identity matrix, ||M ||+ the operator norm of M, and y+ max(7, 0) for any y E IR Bold characters refer to block objects, and O is used when neglecting logarithmic factors.
2 Model
In this section, we introduce our model of linear bandits with memory (LBM in short). LBMs strictly generalize stationary linear bandits, and also recover some nonstationary bandit models with finitely many arms as special cases. The learning setup is as follows. At each time step t == 1,2,.. the learner picks an action ag from a (possibly infinite) set of actions A C Bd, and receives a stochastic reward yt- Similarly to linear models, we assune that the expected reward is a linear function of some unknown vector 0* E Ba- In contrast to stationary models, however, the expected reward at time t is also influenced by the choice of previous actions of the learner. Mathematically, this is captured by the correlation matrix Em Qt-sa, where measures how far in the past actions can influence the current reward. Finally, in order to model the type (rising or rotting) of behavior and its strength, use positive or negative exponent y. This results in the following formula for the reward at time t,
yt (ar, Ala: a.-1) + me
(1)
Using a different analysis, one could replace our fixed-size window with exponentially decaying discount factors. However, while these factors are typically treated as fixed model parameters, our analysis shows how learn the best m (see Section 3.3).
3

---

Published in Transactions on Machine Learning Research (05/2024)
where nn is 1-sub-Gaussin random variable independent of the actions of the learner, and
A(a am) = Ao + Σ aga
(2)
Equations (1) and (2) define model which strictly generalizes standard linear bandits, recovered for y 0. The choice of the covariance matrix for (2) is intuitive, as it stores the previously played actions and thus naturally encodes the directions where satiation or excitation occurs through its eigenvectors, see Figure 1. For simplicity, in the rest of the paper we use the abbreviation At-1 = A(at-m...... a1-1) and refer to it as the memory malria. Conventionally; we set d1-m = a2-m = ... = 0g = Og and choose Ag = la unless otherwise stated. Note that parameters m and y have the twofold advantage of making the model general enough to account for both rotting (7 < 0) and rising (7 > 0) scenarios while being simple enough to be learned simultaneously with 0", see Section 3.3. Note also that at any time step the expected reward Tt E[yr] satisfies Iral I || Given a horizon T E N, the learner aims at maximizing the expected sum of rewards obtained over the T interaction rounds. The performance is mcasured against the best sequence of actions over the T rounds, i.e., through the regret.
En
Σ
E
r7
E
1 yt
where ri <a A A
...... oz 0²) and (at) is the optimal sequence of actions, i.e., the sequence maximizing the expected sum of rewards obtained over the horizon T
Σ (ac. A(a
a 07 arg max
01.00.0 EAA.
Throughout the paper, we use OPT to denote Er whenever the horizon T is understood from the context. Note that a LBM is fully characterized by: the action set A, the parameter 0*, the memory size m, and the exponent y. As shown in the following examples, LBMs fully generalize (stationary) linear bandits, and allow to partially recover pottin/rrisig rested bandits in the limit m + 0c. 00.
Example 1 (Stationary linear bandits) Consider linear bandit model, defined by action set A C Ba and 8r E Ba. This is equivalent to a LBM with the same A and 8*, and memory matric A such that A(ai....,, am) = la for any a1...., O.m E A i.e., when m = or 7 ==
Example 2 (Rotting and rising rested bandits) In rotting (Levine et al., 2017; Seznec al., 2019) or rising (Metelli et al., 2022) rested bandits, the expected reward of an arm k at time step is fully determined by the number ml(() of limes arm k has been played before time L. Formally, each arm is equipped with function pa such that the expected reward at time t is given by (*)n)(()) In particular, requiring all the ps to be nonincreasing corresponds to the rotting bandits model, and requiring all the p* to be nondecreasing corresponds to the rested rising bandits model. Now, let d= K, A = (ex)1<k<k, 8-= (1/v/K...,,1) easy check that
and m > x By the definition of A, see (2), and the orthogonalily of the actions, the expected reward of playing action es at time step t is given by (1+ ne(t))² When Y 7S 0, this is nonincreasing function of (L),), and we recover rolling rested bundils. Conversely, when 7 2 O, we recover rising rested bondits. We note however that the class of decreasing (respectively increasing) functions consider is restricted to the set of monomials of the form n + (1 + n/)////// for 7 S O (respectiucly 2 0). Extending it to generic polynomials is clearly possible, although it requires more compulations in the model selection phase, see Remark 4 and Section 3.3.
can
Although rotting and rising bandits require infinite memory, we argue on both practical and theoretical grounds that in our setting a finite value of m is preferable. First, in many opplications is reasonable to assume that the effect of past actions will vanish at some point. For example, listening to song now does not affect how much we will enjoy the same song in distant enough future. Second, permanent effects may trivialize
2In the next paragraph, however, we explain why a bounded memory preferable within our model.
4

---

Published in Transactions on Machine Learning Research (05/2024)
y=-6
y=2
1.0
2
0.5
0.0
0.00
-0.25
-0.5
-0.50
-1.0
1.0
-1.0
0.0
1.0
-1.0
0,0
100
y
y=
y= 2
1.0
100
155
0.5
3
0.5
2
-1.0
-1.0
0.0 1.0 -1.0 0.0 1.0 -1.0 0.0 1.0
Figure 1: In the top pane, we plot the effect of the memory matrix (2) on the action space for - m 1, and y [-6,0,2), The red arrow is 8" and the black arrow is action dx-1- The color level indicates the value of the instantaneous expected reward of any action (point on the disk). When 7 -6, the rolting effect is so powerful that the optimal action ae is orthogonal to 0z-1. When = O, the optimal action remains 0*, independently of 4--1- For = 2, the optimal action shifted between l" and az-1- However, the top plot does not show that playing constantly 8" is not the optimal policy. In the bottom pane, we consider horizon T 2, with the same choices of parameters. For a given action 01, since T = 2, it possible determine the best possible next action 02 The color now indicates the sum of expected rewards as a function of the initial action d1 (point on the disk). For 7 -6, clearly that playing 0 is not optimal anymore. On the other side, it shows that not playing 0 is more harmful when y than when y 0.
the problem on the theoretical side: consider mn + oo and 7 S -1/2, then for any sequence of actions (a1)221 we have
Lta Ar-10") & EtE A4-100 S TE A 11-1 V 2dT log(1 + T/d) = Br
where we have used the elliptical potential lemma (Lattimore & Szepesvári, 2020, Lemma 19.4). Hence, as soom as 7 S -1/2, we have OPT Br, and the trivial stralegy consistenlly playing 0 enjoys a small regret Br. Conversely, consider 7 2 0. The strategy consistently playing 0" achieves, after rounds, on instantancous reward of (1 +1++0 t)?, which is diverging for 7 1. This is not realistic in most application and, incidentally, violates the concave payoffs assumption (Metelli et al., 2022, Assumption 3.2). Therefore, although considering m = +oo may look attractive at first sight, it actually fails to adequately model song satiation, and restricts the range of relevant from R. to (-1/2,1). Instead, focusing on finite memory m yields more interesting problems, although prevents a full generalization of rotting bandits with finitely mony arms. We note however that when m < oo, the spiril of rolling (resp., rising) bandits is still preserved, as playing an action does decrease (resp., increase) its efficiency for the next pulls (within the time window), see also Figure 1.
A naive approach to learning LBM is to neglect nonstationarity. Assuming that 0* is known, one may then play at time t the action greeddy arg max, (a, A(-10") Although this strategy, which we refer to oracle greedy, may be optimal in some cases (e.g., in rising isotropic settings, see Heidari et al. (2016, Section 3.1) and Metelli et al. (2022, Theorem 4.1) for discussions in the K-armed case), we highlight that it may also be arbitrarily bad, as stated in the next proposition.
Proposition The oracle greedy strategy, which plays af suffer linear vegret, both in rolting rising scenarios.
greedy arg max Ar-10") at time step t, can
5

---

Published in Transactions on Machine Learning Research (05/2024)
Hence, one must resort to more sophisticated strategies, which may include long-term planning. Before describing our approach in the next section, we conclude the model exposition by highlighting that LBMs may also be generalized to contextual bandits (Lattimore & Szepesvári, 2020).
Remark 1 (Contextual bandits) In contextual bundils, at each time step t the learner is provided a contert at (e.g., data about user). The learner then picks an oction at E A (based on et), and receives reward whose expectation depends linearly on the vector (f at) E RR, where to is a known feature map. Note that it is equivalent to have the learner playing actions de E Rd that belong to subset A, = {v(c,, a) E RR: a A}. The analysis developed in Section 3 still holds true when A, depends on t, and can thus be generalized to contertual bandits with memory.
3 Regret Analysis
In this section, we introduce and analyze QFUL-memory (Algorithm 1) for learning LBMs. We first observe that for every block length there exists cyclic policy providing a reasonable approximation to the optimal policy (Proposition 2) that cannot be improved in general, see Proposition 3. Learning the optimal block in the cyclic policy then reduces to stationary lincar bandit problem that can be solved by rumning the OFUL algorithm (Proposition 4). This approach is however wasteful, as it estimates concatenated model whose dimension scales with the block length. We thus propose refined algorithm leveraging the structure of the concatenated model, and show that it enjoys a better regret bound. We then tune the block length to trade-off estimation and approximation errors (Theorem 1). Since the optimal block length depends on the memory size m, which may be unknown in practice, we finally wrap our algorithm with bandit model selection algorithm that is shown to preserve regret guarantees (Corollary 1). Throughout the analysis, we assume for simplicity that the horizon T is always divisible by the block length considered. Finally, note that all technical proofs are relegated to the Appendix (Proposition and Theorem 1 being proved with high probability while stated in expectation in the main body for simplicity of exposition).
3.1 Approximation
In LBMs, finding a block of actions maximizing the sum of expected rewards is not a well-defined problem. Indeed, the rewards also depend on the initial conditions, determined by the m actions preceding the current. block. To bypass this issue, introduce the following proxy reward function. For any m, L > 1 and any block a 01 am+L of m + L actions, let
m+L Σ (=++1
m++
F(a)
(c. - Σ (Ar-ades 0*).
(4)
(==+1
In words, we only consider the expected rewards obtained from the index m + 1 onward. Note that actions 01 On still do play a role F, as they influence from the initial state, so that
The key that now independent.
a arg max F(a)
(5)
8EBTI2
is well-defined. The next proposition quantifics the approximation crror incurred when playing cyclically ä instead of the optimal sequence actions (at)ıer defined in (3). A critical quantity to establish this result is the maximal (and minimal) instantaneous reward one can obtain. To this end, we introduce the notation R- Supaa.....mmt1. E.4 (Am+1,A(a), am ). Note that in (8) we provide a bound on R in terms of and 7. We now state approximation result, and show that it is tight up constant.
Proposition 2 For any m, I. 2 1, let à be the block of m + L actions defined in (5) and (7.) be the expected rewards collected when playing cyclically â. We have
T
2m
OPT Σ
F
T
(6)
+ L
6

---

Published in Transactions on Machine Learning Research (05/2024)
The dependence on the cycle length L of the right-hand side of (6) is as expected: by increasing L, the expected reward of the cyclic policy gets closer to OPT. In addition, note that for = 0 we recover the stationary behaviour. In this case, there are no long- tong-term effects and the performance is oblivious to the block length, so that we recover Σ, Fe = OPT independently of L. Next, we show that Proposition is tight up to constants.
Proposition 3 (Tight approximation) For any m, L 2 and 7 S 0, let a be the block of m + L actions defined in (5) and (Ft) be the expected rewards collected when playing cyclically a. Then, there exists a choice of and 0r such that
mR T m + L
OPT
Upper bounds on R are easy to obtain. Let 01,...; 0m+1 E A, and Am = A(a am), we have
Iml (Am+1, Am Am0 |1m |la ||Am0"||2 < ||Am|l. 110^1/ (m + 1)=*
such that one can take R = (m + 1)" Note that any other choice of dual norms could have been used to upper bound K Amo%) as done in Proposition For simplicity, we restrict ourselves to the Euclidean norm from now on, and use R (m + 1)"*
Remark 2 (On the necessity of optimizing over the first actions.) We highlight that optimizzng over the first m actions in Equation (5) necessary, as there erists no such "pre-sequence" which is universally optimal. Indeed, let A, and A be the memory matrices generated by 01 01...0m+L and dj ......., .n... 0m+1 ... Om+ respectively. It is immediate to check that if the pre-sequence a1 11...am is better than af ....... o'n with respect to some model 0 Rd, i.e., if we have Ii=m-1 (ot, A1-10) 2 Ei=mti Al-, then the opposite holds true for -0, Hence, one cannot determine priori good pre-sequence and has to optimize for it.
3.2 Estimation
The next step now consists in building a sequence of blocks with small regret against ā. As detailed below, this reduces to stationary linear bandit problem, with specifie action set. After showing an initial naive solution, provide a refined approach which exploits the structure of the latent parameter and enjoys improved regret guarantees.
A naive approach. We introduce some notation first. Let 0 = (O....., 0,, .......")) E Rd(++t) be the vector concatenating m times Oa and L times 8* Inspired by the right-hand side in (4), we introduce the subset of [R)(m+)) composed of the blocks ... bm+z whose actions are of the form b, = A:-1a, for some block E A Formally, let
B b ())(++)); 3a E A such that b; = 1 1 m b; A--1a; m. + -
}
where the (A))t are the memory matrices generated from Equipped with this notation, it is easy to see that for any a E A and the corresponding b E B we have F(a) (b, 0*)) Therefore, estimating b (the block in B associated to a) reduces to a standard stationary linear bandit problem in Rd)(+)), with parameter and feasible set B. In other words, we have transformed the nonstationarity the rewards into constraint on the action set. Running OFUL (Abbasi- YAbkosi-Yadkori et al., 2011) then amounts playing time step = T(m + L), the block a, E ALLL, whose associated block b, in B satisfies
b arg max sup (b, 0),
(9)
dEB BEC.-1
where C, e RRd(m+ 1); 110, 0 0lv. < (6)), with (8) defined in Equation (17), V, =i b,
Al((m+L): yr Im+h VT,i using Vr,i to denote the reward obtained by the 5th action of block 7, and

---

Published in Transactions on Machine Learning Research (05/2024)
0, = V, Br.b) Noticing that ||0*112 I L, that for any block b B we have ||612 I m+ L(m+ (mm++))2 and (0'bb) & L(m + 1) and adapting the OFUL's analysis, we get the following regret bound.
Proposition 4 Let E [1, L2 m, and ar be the blocks of actions in Rd(m-L) associated to the b, defined in (9). Then we have
L))++)
E
Σ
F(a) - -(a,)
(m
(m 177 VT).
In the stationary case, i.e., when m 0 and L 1, the block approach coincide with OFUL and we do recover (up to log factors) the (dd'T) bound for standard lincar bandits. Note that in Proposition 5 in the Supplementary Material prove more general high-probability bound, which also specializes to known results for linear bandits in the stationary case.
A refined approach. Note however that the approach presented above is wasteful. Indeed, while the relevant model to estimate l e Rd, the 0, are estimators of the concatenated vector 0 E Rd(m+)) with degraded accuracy due the increasod dimension. Similarly, this method only uses the sum of rewards obtained by a block, while finer-grained information is available, namely the rewards obtained by each individual action in the block. Driven by these considerations, let a, a,,1 0r,11...7,,+L be the block of actions played at block time step T, Ar,i-1 A(ar,ims ................................ d7,i-1), and br, = 17,5-10, for 2 m. We propose to compute instead
m+L L Σ
0, -.=
Σ
Vr by
(10)
where V, = -t==1 Emtt by,, bb,, + Als. In words, 0, is the standard regularized least square estimator of H" when only the last L rewards of each block of size m + L are considered. Note however that the 0 are only computed every m + L rounds. Indeed, recall that regret is computed here at the block level, such that at each block time step T the learner chooses upfront an entire block to play, preventing from updating the estimates between the individual actions the block. Following the principle of optimism in the face of uncertainty, a natural stratogy then consists playing
0, = arg max sup a BEC,-1 1=1
Σ (0,,5 1,,
(11)
where C, = {0 E :e:: 100 llv, S { for some (r) defined in (18). Expressed in terms of b,, the estimate (11) corresponds to
b, arg max sup bEB OED+-1
(b,0),
(12)
where D, = (0 E Rdd(++);; 30 E C. such that 0 to (9); except that we use the improved confidence set D. that leverages the structure of 0- A dedicated analysis to deal with the fact that the estimates 0, are not "up to date" for actions inside the block then allows to bound the regret of the sequence a, against the optimal ā. Setting the block size in order to balance this bound with the approximation error of Proposition yiclds the final regret bound.
= (0.: Og 0................... 0)}
In words, this estimate similar
Theorem Let [1, d], and a, be the blocks of actions in Rd(m+L) defined in (11). Then we have
1/imt F(ā) - -0(a))a))))) = (( 1) VT)
T=1
Suppose that m 2 1, T Lm²
+ 1, and set L = / T2/1 - m. Let ue be the rewards collected when
playing a as defined in (11). Then we have
OPT
E
Σ 1=1
D1
= o (va (m + ( 73/1)
8

---

Published in Transactions on Machine Learning Research (05/2024)
When m 0 (i.e,, in the stationary case), setting L = 1 recovers the OFUL bound.
When comparing the first claim of Theorem to Proposition 4, we note that the dependence in L has been reduced from 1, to L, thanks to the improved confidence sets. Solving the approximation-cstimati tradeoff using Proposition 4 would have yielded an overall regret bound of order d3/s + 1) T4/S, worse than the bound provided by the second claim of Theorem 1. In the stationary case (i.e., for m 0) Theorem 1 recovers the OFUL regret bound and matches the lower bound for stationary linear bandits (Lattimore & Szepesvári, 2020, Theorems 24.1 and 24.2, c.g.), such that our analysis is tight in general (rocall that Proposition shows that the control of the approximation error provided by Proposition 2 is optimal up to constants). Finding a lower bound matching Theorem for arbitrary values of m and y remains however an open problem. We highlight that lower bounds for nonstationary bandits are particularly hard to obtain and that most papers on this topic do not prove any, see e.g., Levine et al. (2017); Kleinberg & Immorlica (2020); Metelli et al. (2022).
(2018); 8); Pike-Burke & Grunewalder (2019); Cella &
As we can see from the optimal choice of L in Theorem 1, OFUL-memory requires the knowledge of the horizon T, the memory size m, and the exponent y, which might all be unknown in practice. If adaptation to T can be achieved by using the doubling trick, adaptation to m and y is more involved. In the next section, we show that OFUL-memory can be wrapped by model selection algorithm to learn m and 7. Before turning to this problem, we state few remarks.
Remark 3 (An over-optimistic variant) Note that D. = {e E RRd(m+)); 30 E Cr such that })} is not the only improved confidence set that one can build from Cy. Indeed, it is im- Oa. (Os....,
mediate to check that our proof remains unchanged if one uses instead Dept = Rd(m+L); 3.,...., Or E C such that 0 (Od...., .0. (l.....01))} optèmistic block version of the UCB, composed of the sum of the UCBs of the single-actions in the block, although the latter might be attained at different models 0z, while we know that O* is the same model or repeated L times. Still, since each 0; is estimated in the confidence set CT-1 of reduced dimension, the guarantees are unchanged. In the rest of the poper, we refer to this variant as the over-optimistic version of OFUL-memory, denoted by 03M. Empirically, 03M outperforms the vanilla approach. We attribute these better performances to the fact that the confidence set it is buill upon is more optimistic.
Optimizing (12) over Dowt and not Dr-1 creates an over-
Remark 4 (Generic matrix mapping A) Note that our analysis naturally exlends to any malris mapping
A, as long it is known. The term (m+1)7* in Theorem 1 is then replaced with supe...am |A(ai...., um)ll.. We highlight however that having access to such knowledge is unlikely in practice. This is why we focus on the simpler parametric family (2), which encompasses many rotting and rising scenarios while allowing us to learn simaltancously m and 7, as shown in the next section. It is of course possible to extend the family of monomials (2) to a family of polynomialss but this requires tracking more paramelers (namely, the different coefficients of the polynomial), thus degrading the final regret bound.
Remark 5 (Solving LBM with a general Reinforcement Learning (RL) approach) Our setting may be seen as an MDP with a d-dimensional continuuus space of aclions, a (md)- -dimensional contiruuous stote space (for the past m actions), a deterministic transition function parameterized by an unknown scolar ", and a stochastic reward function with linear dependence on an additional d- d-dimensional latent parameter 0* The oplimal policy in Uhis MDP is generally nonslationary, and we are not aware of RL algorithms whose regret can be bownded without relying on more specific assumptions on the MDP. By exploiting the structure of the MDP, and restricting to cyclic policies, we show instead that the original problem can be solved using stationary bandit techniques.
3.3 Model Selection
In the absence of prior knowledge on the nature of the nonstationary mechanism at work, a natural idea consists in instantiating several LBMs with different values of y and running a model selection algorithm for bandits (Foster et al., 2019; Cutkosky et al., 2020; Pacchiano et al., 2020). In bandit model selection, where a master algorithm runs the different LBMs, the adaptation to the memory size m becomes more complex. Indeed, the different putative values for m induce different. block sizes (see Theorem 1) which perturb the
9

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 1 OFUL- (OM, 03M)
input- action space A C R memory size m, exponent 7, regularization parameter X, horizon T.
init set L = /mm/ T m. Go Od, Vo Ald, Bg = 0.
for -....., T/(m + L) do
// 0M
11 03M
a, arg sup a.EEA BEC
Ari-10
a, arg max sup ariiA 0
Σ i=1
(T,s Ar.--
// Play and update confidence set Play ar, collect yr,1i..... 7r
Compute Cr, i.c., 0,, Vr, and B, via (10) and (18).
time and reward scales the master algorithm. For instance, bandits with larger block lengths will collect more rewards per block, although they might not be more efficient. on average. Our solution consists feeding the master algorithm with averaged rewards. One may then control the true regret (i.e., not averaged) of the output sequence, against scaled version of the optimal sequence through Lemma 1, which links the normalized regret of a block meta-algorithm to the true regret of the corresponding sequence of blocks.
Lemma 1 Suppose that a block-based bandit algorithm (in our case the bondit combiner) produces sequence of The blocks a,, with possibly different cortinalities (ar,, such that
The r(ar) < F(The),
a-
for some sublinear function F. Then, we have
min, |arl max, ar
Σ- |arl
The
F(a)
Σ F(a,) S min |a-| F(The)
In particular, if all blocks have the same cordinality the last bound is just the block regret bound scaled by |arl-
Combining this result with Theorem 1 and (Cutkosky et al., 2020, Corollary 2) yields the following result.
Corollary 1 Consider an instance of LBM with unknown parameters (m., T.). Assume a bandil combiner is run on N < d instances of OFUL-memory (Algorithm 2), each using different pair of parameters (ma,ne) 1) from a set S = (im,,,))...... (mNx 7NN)] such that (m,, E S. Let M = (max, mz)/(min, m2).
Then, for all T 2 (m+ + 1)2rt /m,d', the expected rewords (r T (m) of the bandit combiner satisfy
OPT
E
Ö(Md(m, + 1)1-+88 73/4) r
bc
VM
4 Algorithms
In this section, we discuss the practical implementation of our approach. This includes OFUT-memory (OM) and its over-optimistic variant (03M, see Remark 3), both summarized in Algorithm 1. We also instantiate the Bandit Combiner from Cutkosky et al. (2020) to our specific setting with average rewards and 03M as base algorithm, see Algorithm
Maximizing the UCBs. We start by making explicit the UCBs used in OM and 03M, see (12), optimized over D. Dopt. Using the formula for C, one can check that they given by UCB((a) mm (a,, A A + B(a), where B(a) 8r- Enth AJ-20/lv=z for DM and
10

---

Published in Transactions on Machine Learning Research (05/2024)
for 03M. The two UCBs only differ in their exploration bonuses. Note =(a)=B--1D0) |
By-1
that by the triangle inequality, we have UCB I UCB (a) for any a. Thanks to this closed form in terms of a, it is possible to approximate arg max, (a) using gradient ascent. Note however that maximizing the UCBs is a hard problem when the action space infinite, which might be non-convex in general. In that respect, the theoretical guarantees we provide in Theorem 1 hold whenever the learner has access to some oracle that returns the exact UCB maximizer, as traditionally assumed in the literature, see e.g,, Kveton et al. (2015). Conversely, note that the practical implementation of 03M still satisfies Theorem 1, but for slightly weaker version of the regret where the "best block" " is understood the one returned by the approximated oracle used in 03M (i.e., our gradient ascent solver). See (Kveton et al., 2015, Section 9) for a similar discussion.
Computational complexity. As described in Algorithm 1, our approach consists of two steps: updating the confidence region Cr i.e,, 0, and 3, according to (10) and (18), and computing the block a, that maximizes the UCB index. The first step is performed by online Ridge regression, and has a computational cost of ((Ld)). We note here the advantage of our refined algorithm over the naive concatenated approach, whose Ridge regression update has cost O(L'd). The maximization of the UCB indices, performed through gradient ascent has time complexity per iteration of O( L)d?). Hence, the overall complexity of an epoch of Algorithm 1 is O(m + L)d na), where 74e is the number of iterations performed by gradient ascent. Recall that the epochs of Algorithm 1 correspond to blocks of m + L actions, such that the actual per-round complexity is Odd na).
Bandit combiner. Our bandit, combiner, see Algorithmi 2, builds upon the approach developed by Cutkosky et al. (2020) and works as follows. The meta-algorithm is fed with different bandit algorithms (in our case, instances of 03M with different choices of parameters my and 7/2) and at each round plays a block according to one of the algorithms. Each 03M instance comes with putative regret bound C,7º,, which is the regret bound satisfied by the algorithm should it be well-specifted, i.e., if the rewards are indeed generated through memory matrix with memory my and exponent 7/. Note that in order to be comparable across the different instances, the putative regrets apply to the average rewards. The values of C3 and aj can be computed using Theorem 1, see the proof of Corollary 1 for details. The putative regrets are then used to successively discard the instances that are not well specified, and eventually identify the instance using parameters (m. 74)- Knowing C₁ and Otj we can compute for any j the target regret
R₃ = C, T2/3
2/3
5v30
0g/2 02/2T222 + 1152(m, + 1)215 1/3 Tog(TT + (N 1)72/3,
(13)
18
where The is the number of blocks the Bandit Combiner is called on, see Appendix B for details. Here, note how the presence of (my + 1)215 is impacting differently the rising and rolting scenarios. Using (Cutkosky et al., 2020, Corollary 2), the regret of Algorithm 2 is finally given by 3R, where j. is the index such that (m... )3.) = (m.:
5 Experiments
We perform experiments to validate the theoretical performance of OM and 03M (Algorithm 1). Similarly to (Warlop et al., 2018), we work with synthetic data because of the counterfactual nature of the learning problem in bandits. Unless stated otherwise, we set d = 3 while 0* Rd generated uniformly at random with unit norm. The rewards are generated according to (1) and (2), and perturbed by Gaussian noise with standard deviation 1/10.
Rotting with Bandit Combincr. We start by analyzing the rotting scenario with m = 2 and y= -3 We measure the performance in terms of the cumulative reward averaged over 5 runs (this is enough because the variance is small). In Figure? 2 (left pane) we compare the performance of 03M against oracle greedy, vanilla OFUL, and two instances of Bandit Combiner (Algorithm 2. The first instance, Combiner 7, works in the setting where the misspecified parameter is y and the algorithm is run over the set (-4, -3. 22, -1, 0} of possible values for y with the true value being -3 The second instance, Combiner m, tests the setting where
11

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm Bandit Combiner 03M
input Instances ?1)).- .... 03M(mn, YN), horizon Tbc
numbers CI...., , Cy > 0, target regrets RI...., Rv-
Set (t) = U,S; = 0, A, = for i ,,..., N, and set to = [I,...,NN}
for t L.... The do
if there is some i E 4 with T(i) 0 then 4 =
elsc
For each E 4, compute the UCB index:
UCB(i) = min (im
(m, + 1)2x
C₁
+ 4(m; + +)221
2 log (NN/6)
R The
VT(i)
T(i)
Set i, arg ea T(a)
S. UCB(i)
Obtain from instance ; (t.) block of size mi, + Li, and play it
Return the total reward ri collected in the last Li, time steps of the block to 03M(m,, 7c.)
Compute the average reward Pic
Iv
T.q
Update A., + A + S.,T((i)) Fi, (where set 0/0 0) and S,, S., + f
Update the number of plays T(t)) t T(i)) +1
if , C. (1t) (m,, + 1)3%/4 (o then
4 4-11-1 {
elsc
1, 1--1
2500
2
m 2==
03M
0GM
Cumulative rewards
Combiner y
Combiner m
Cumulative rewards
OFUL
Policy fl;
OFUL
Oracle Greedy
Oracle Greedy
150
1000
100
500
50
0
200
400
800
830
1000
1200
200
600
800
1000
1200
Time
Time
Figure 2: Cumulative rewards in rotting (left) and rising with non-isotropic initialization (right) cases.
the misspecified parameter m. In this case the algorithm run over the set 2,33,3 of possible values for m with the true value being The results see Figure (left pane) show that 03M able to plan the actions in the block ensuring that good arm is not played right away if higher reward can be obtained later on in the block. This means that 03M is waiting to play certain actions until the corresponding entries of A have been offloaded, preventing A to negatively impact the reward of these actions. Although lcarning proves to be more difficult, which is consistent with the impact of M = (max, myj)/miin,m) in Corollary 1, Combiner m run on instances of 03M competitive with 03M run with the true parameters. Note that with isotropic initialization there no point in running Combiner y with values of y larger than zero. Indcod, the isotropic case oracle greedy optimal, stationary, and with the same optimal action for any y 0. The empirical performance of our algorithms in non-isotropic rising setting is investigated in the next example.
12

---

Published in Transactions on Machine Learning Research (05/2024)
Rising with non-isotropic initialization. When y > 0 (rising setting) and Ao # Ia (non-isotropic initialization), there are instances for which oracle greedy is suboptimal, as we show next. Let d = 2, m = 2, y=1, 1, Ao = =iee and 0 = vI=)). With these choices, oracle greedy starts to pull action e1 = (1, 0) and will always play it, obtaining a cumulative reward of T(1 + m)ye. Instead, a better stratogy would be to play 62 = (0,1) all the time, collecting a cumulative reward of TmyT ee. We call this stralegy #2 and in Figure 2 (right pane) we compare the performance of 03M with oracle greody, T2, and OFUL. Here OFUL performs well because the optimal action is stationary and, unlike oracle greedy, OFUL can use exploration to discover that ez is better than 61.
6 Conclusions and open problems
We introduced and analyzed a nonstationary generalization of linear bandits that uses fixed-size memory. Some interesting future rescarch directions may include the derivation of a matching lower bound or quantifying the UCB optimization error to better tradeoff the block length L.
Acknowledgments
The authors acknowledge the financial support from the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), the FAIR (Future Artificial Intelligence Research) project, funded by the Generatiio program within the PNRR-PE-AL scheme, and the EU Horizon 2022-HUMAN-02 research and innovation action under grant agreement 101 101120237, project ELIAS (European Lighthouse of AI for Sustainability).
References
Yasin Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for lincar stochastic bandits. Advances in neurol information processing systems, 24, 2011.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pp. 3 3-1,, 1999.
Peter Auer. Using confidence bounds for explotaation-ccollratiin tradc-offs. Journal of Machine Learning Research, 3(Nov) 3997-)22 422, 2002.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Conference on Learning Theory, pp. 138-158. PMLR, 2019.
Soumya Basu, Rajat Sen, Sujay Sanghavi, and Sanjay Shakkottai. Blocking bandits. Advances in Newral Information Processing Systems, 32, 2019.
Omar Besbes, Yonatan Gur, and Assal Zeevi. Stochastic multi-armed-bandii problem with non-stationary rewards. Advances in neural information processing systems, 27, 2014.
Djallel Bouneffouf and Raphael Féraud. Multi-armed bandit problem with known trend. Neurocomputing. 205:16 21, 2016.
Djallel Bouneffouf, Trina Rish, Guillermo A Cecchi, and Raphaël Féraud. Context attentive bandits: contextual bandit with restricted context. In Proceedings of the 26th International Joint Conference Artificial Intelligence, pp. 1468 1475, 2017.
Leonardo Cella and Nicolò Cesa-Bianchi. Stochastic bandits with delay-dependent payoffs. In International Conference on Artificial Intelligence and Statistics, pp. 1168-1177. PMLR, 2020.
Yifang Chen, Chung-Wer Wei Lee, Haipeng Luo, and Chen-Yo Yu Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. In Conference on Learning Theory, pp. 696 726. PMLR, 2019.
Wang Chi Cheung, David Simchi- Sevchi-Levi, and Ruihao Zhu. Learning optimize under non-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1079-1099 PMLR, 2019.
13

---

Published in Transactions on Machine Learning Research (05/2024)
Corinna Cortes, Giulia DeSalvo, Vitaly Kuznetsov, Mchryar Mohri, and Scott Yang. Discrepancy-baseed algorithms for non-stationary rested bandits. arXie preprint 171 2017.
Ashok Cutkosky, Abhimanyu Das, and Manish Purohit. Upper confidence bounds for combining stochastic bandits. arXiv preprint arXiv:2012.3311 2020.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Conference on Learning Theory. PMLR, 2008.
Yuntian Deng, Xingyu Zhou, Baekjin Kim, Ambuj Tewari, Abhishek Gupta, and Ness Shroff. Weighted gaussian process bandits for non-stationary environments. In International Conference on Artificial Intelligence and Statistics, pp. 6909 6932. PMLR, 2022.
Yash Deshpande and Andrea Montanari. Linear bandits in high dimension and recommendation systems. 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp- 1750-1754. IEEE, 2012.
Ginseppe Di Benedetto, Vito Bellini, and Giovanni Zappella. linear bandit for seasonal environments. arXiv preprint ar erXi:20044.188 19576, 2020.
Louis Faury, Yoan Russac, Mare Abeille, and Clément Calauzênes. A technical note on non-stationary parametric bandits: Existing mistakes and preliminary solutions. In Algorithmic Learning Theory, pp- 619 626. PMLR, 2021.
Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Saced Ghoorchian and Setarch Maghsudi. Bayesian linear bandits for large-scale recommender systems. arXiv preprint arXiv:2202.08107 2022.
John Gittins, Kevin Glazebrook, and Richard Weber. Multi-armed bandit allocation indices. John Wiley & Sons, 2011.
John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41(2):148-166 1979.
Hoda Heidari, Michael Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In IJCAI, pp. 1562-1570, 2016.
Komal Kapoor, Karthik Subbian, Jaideep Srivastava, and Paul Schrater. Just in time recommendations: Modeling the dynamics of boredom in activity streams. In Proceedings of the eighth ACM international conference on web search and data mining, pp. 233 242, 2015.
Zohar S Karnin and Oren Anava. Multi-armed bandits: Competing with optimal sequences. Advances in Neural Information Processing Systems, 29, 2016.
Baekjin Kim and Ambuj Tewari. Randomized exploration for non-stationary stochastic linear bandits. In Conference on Uncertainty in Artificial Intelligence, pp. 71-80. PMLR, 2020.
Robert Kleinberg and Nicole Immorlica. Recharging bandits. In 2018 IEEE 59th Anmual Symposium Foundations of Computer Science (FOCS), pp. 309-319. IEEE, 2018.
Melda Korkut and Andrew Li. Disposable linear bandits for online recommendations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4172 4180, 2021.
Geza. Kovacs, Zhengxuan Wu, and Michael S Bernstein. Rotating online behavior change interventions increases effectiveness but also increases attrition. Proceedings of the ACM CompntCr Interaction, 2(CSCW):1122 25, 2018.
Matevž Kunaver and Tomaž Poërl. Diversity in recommender systems-a survey. Knowledge- systems, 123:154-162. 2017.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence. and Statistics, pp. PMT.R, 2015.
Pierre Laforgue, Giulia Clerici, Nicolò Cesa-Biancias and Ran Bachr-Bach A last switch dependent analysis of satiation and seasonality in bandits. In International Conference Artificial Intelligence and Statistics, pp. 971 990. PMLR, 2022.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Liu Leqi, Fatma Kilinc Karzan, Zachary Lipton, and Alan Montgomery, Rebounding bandits for modeling satiation effects. Advances in Neural Information Processing Systems, 34:4003-4011 2021.
Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. Advances in neural information processing systems, 30, 2017.
Chuanhao Li, Qingyun Wu, and Hongning Wang. Unifying clustered and non-stationary bandits. In International Conference on Artificial Intelligence and Statistics, pp. 1063-1071. PMLR, 2021.
Yang Li, Jiawei Jiang, Jinyang Gao, Yingxia Shao, Ce Zhang, and Bin Cui. Efficient automatic CASH via rising bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4763-4771, 2020.
Haipeng Luo, Chen-Yu Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In Conference On Learning Theory, pp. 1739-1777 1776. PMLR, 2018
Alberto Maria Metelli, Francesco Trovo, Matteo Pirola, and Marcello Restelli. Stochastic rising bandits. In International Conference on Machine Learning, pp. 15421-15457. PMLR, 2022.
Jonas W Mueller, Vasilis Syrgkanis, and Matt Taddy. Low-rank bandit methods for high-dimensional dynamic pricing, Advances in Newral Information Processing Systems, 32, 2019.
Ronald Ortner, Daniil Ryabko, Peter Auer, and Rémi Munos. Regret bounds for restless markov bandits. In International conference on algorithmic learning theory, pp. 214 228. Springer, 2012.
Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Amup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. Advances in Neural Information Processing Systems, 33:10328-10337, 2020.
Ciara Pike-Burke and Steffen Grunewalder. Recovering bandits. Advances in Neural Information Processing Systems, 32:14122-14133 2019.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411 2010.
Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. Advances in Neural Information Processing Systems, 32, 2019.
Yoan Russac, Olivier Cappé, and Aurélien Garivier. Algorithms for non-stationary generalized linear bandits. arXiv preprint arxi::0003. 10119, 2020.
Markus Schedl, Hamed Zamani, Ching-Was Wei Chen, Yashar Deldjoo, and Mehdi Elahi, Current challenges and visions in music rocommonder systems rescarch. International Journal of Multimedia Information Retrieval, 7(2):95 116, 2018
Julien Seznee. Apprentissage automatique séquenticl pour les systèmes éducatifs intelligents, 2020.
Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rotting bandits no harder than stochastic oncs. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 2564 2572.. PMLR, 2019.
David Simchi-Levi, Zeyu Zheng, and Feng Zhu. Dynamic planning and learning under recovering rewards. International Conference on Machine Learning, pp. 9702 97119 PMLR, 2021.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Cem Tekin and Mingyan Liu. Online learning of rested and restless bandits. IEEE Transactions on Information Theory, 58(8):5588-500) 2611,,56111.11 2012.
Romain Warlop, Alessandro Lazaric, and Jérémie Mary. Fighting boredom in recommender systems with linear reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied probability, 25 (A):287 298, 1988.
Qingyun Wu, Naveen Tyer, and Hongning Wang. Learning contextual bandits in a non-stationary environment. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 495 504, 2018.
Xiao Xu, Fang Dong, Yanghua Li, Shaojian Hc, and Xin Li. Contextual-bandit based personalized recommen- dation with time-varying user interests. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 34, pp. 6518 6525, 2020.
Peng Zhao, Lijum Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In International Conference Artificial Intelligence and Statistics, pp. 746-755. PMLR, 2020.
16

---

Published in Transactions on Machine Learning Research (05/2024)
A Technical Proofs
We gather this section the proofs omitted the core text.
A.1 Proof of Proposition
Proposition The oracle greedy strategy, which plays at greedy = arg max Aa,aa,,AA--- Ar-10%) at time step t, can suffer linear regret, both in rotting or rising scenarios.
We build two instances of LBM, one rotting, rising, in which the oracle greedy strategy suffers linear regret. We highlight that the other strategy exhibited, which performs better than oracle greedy, may not be optimal.
Proof
Rotting instance. Let A= Ba, l" = =1, m = d - and such that
= la Σ a.a.
greedy for some 7 0 to be specified later. Oracle greedy, which plays at each time step ag arg max (a, A constantly plays 61. After the first m pulls, it collects reward of 1/d at ev- ery time slep. On the other side, the strategy that plays cyclically the block eg...ed collects a reward of every d= + time steps, ie., an average reward of 1/d per step. Hence, up to the transitive first m puuls, the cumulative reward of oracle greedy after T rounds is T/d', and that of the cyclic policy is T/d. The regret of oracle greedy thus at least
T (
1
d
d:
which is linear for y >> 1.
Rising instance. Let m 2 1, d= 2, = B2, 8" (e, 1) whore E > is be specified later, and A such that
1 0 0 + Σ a.a
A(a am) =
Oracle greedy constantly plays 61 collecting a reward of (m + 1)87 from round m + onward. On the other side, the strategy that plays constantly e2 collects reward of m0g from round m 1 onward. Hence, the regret of oracle greedy from round m onward is at least (T - mmmmm (m + 1)s], which is linear for m/(m + 1).
A.2 Proof of Proposition 2
Proposition 2 For any m. L 2 1, let à be the block of m + L actions defined in (5) and (Fr) be the erpecled rewards collected when playing cyclically a. We have
2nR T
OPT Σ
(6)
m + L
Proof Recall that the optimal sequence is denoted (at)²= and collects rewards (ri)zz) Let L> 0; by definition, there exists block of actions of length L in (a (0))=1 with average expected reward higher that OPT/T. Let t" be the first index of this block, we thus have (1/L) Et---1 r 2 OPT/T. However, this average expected reward realized only using the initial matrix A generated from oj 1..-1..... a Let aj.-m...... ae of length m L. Note that, by definition, we have that F(a) 2 F(a*)
E E(-l-1 ri L. OPT/T. Furthermore, by (8), when playing cyclically one obtains least. reward of - R in each one of the first m pulls of the block. Collecting all the pieces, obtain
T
T
Σ
F >
mR + mR+
+(a)
+ I
17

---

Published in Transactions on Machine Learning Research (05/2024)
T
ml -mR+f((a))
m +
T
(-mR+ + OPT
m + L
T
L
mR OPT
T
m +L
m + L
L
mR
m& 111 + L
OPP
-PT
T
(14)
m + L
m. + L
m. +
2m T,
OPT
m + L
where (14) derives from OPT < RT.
A.3 Proof of Proposition 4
We prove the (stronger) high probability version of Proposition 4.
Proposition 5 Let X X 1, E (0, 1), and a, the blocks of actions in Rd((++)) associated the b, defined in (9). Then, with probubility al least 8 we have
L)m-L)
F(a) F(a,) S 4Lmm 41m V VTd in (1+ T(m 1)27
d(m + L)A
VXL+ + V In (3) + d(m + L) In 1+
T(m + 1)27* d(m + LJA
Proof The proof essentially follows that of (Abbasi- Yadkori et al., 2011, Theorem 3). The main difference is that our version of OFUL operates at the block level. This implics a smaller time horizon, but also and increased dimension and an instantaneous regret (b, 0*) - (b,, 0*) upper bounded by 2L(m + 1)²* instead of 1. We detail the main steps of the proof for completeness. Recall that running OFUL in our case amounts to compule at every block time step
0, 0-=
Σ yr byo r'=1
where
V. Σ by Ml((+))) and y- Σ Vr.i. r'=1
since we associate with a block of actions the sum of rewards obtained after time step m. Note that by the determinant-trace inequality, see e.g., (Abbasi- Yadkori al., 2011, Lemma 10), with actions b, that satisfy 113 < m + L(m + 1)2T we have
d(n+
T(m + 1)2x* d(m++) I (1+
V
T(m + L(m + 1))2** (1+
<
(15)
Mla(m
d(m + L)A
dA
The action played at block time step the block a, BL+ associated with
b, arg max sup bEB
(b,0),
(16)
occ
where
C, = (0e L)) 10, 10-001 -0lv S (1,(0))
18

---

Published in Transactions on Machine Learning Research (05/2024)
with
Br( / 21n (7) + d(m + L) In 1+ 7(m + 1)27
dA ) + VAL.
(17)
Applying (Abbasi-Yadkori et al., 2011, Theorem 2) 0 E (dd(+t)) which satisfies 1|0 VL we have that 0" E C, for every T with probability at least 1 1 8. Denoting by 0, the model that maximizes (16), we thus have that with probability at least 1 - 8, the inequality (b) I (b, O-) holds for every 7, and consequently
7/im+ L.) (b,0)) (b)
T/(++L)
min {2L(m+ + 1)7", (b,, -00)
())++)
Σ min (2 |0 12--0"llv, | v-
Σ
min + 28) |6, 1I
+/(m+))
221(m 1 B1/(m+))(0
Σ min (1, ||b [1v=
T T/(++))
min { 1, b 112
< 2m 1y** (T/(m+2)(0)
m
T
(T/(m+
< <2/2L(m + 1)7* (1/(m+2)(0)
In
V
m++
(
T(m + 1)2yt
< <40mm+17)
Td In
d(m + T.JA
VXL+ In (c)
T(m + 1)27*
+ d(m L) In 1
d(m L)A
where we have used (Abbasi-Yadaae Yadkori et al., 2011, Lemma 11), as well as (15) and (17). Note that in the stationary case, i.c., when m = 0 and 1, we exactly recover (Abbasi- Yadkori et al., 2011, Theorem 3). Proposition 4 is obtained by setting E [1, d], , L 2 m, and 8 = 1/T.
A.4 Proof of Proposition 3
and 7 s 0. For simplicity, we note the basis modulo d, Le., Ex4d = e for any E N. Note that for any aj...., am+1 E A we have (om+1, Am!''| < |lomtalla || blx 1/vd, such that one can take R 1/vd.. Observe now that the strategy which plays cyclically eI....,ed ed collects reward of 1/vd at each time step, which is optimal, such that OPT - T/vd. Further, it is easy to check that block a, composed of m pulls of 022 followed by eI,..., er satisfies f(ā)= = L/Vd, which is optimal for similar reasons. Playing cyclically ā, one gets a reward L/Vd every m + pulls. In other terms, we have
Proof Let = m + 1, A = {0a) U (ex)asd; 0r =
T
T
L
T
m T mR
OPT Σ
rt
T
d
m +
Vd
m + Vd
m +
19

---

Published in Transactions on Machine Learning Research (05/2024)
A.5 Proof of Theorem 1
We prove the high probability version of Theorem 1, obtained by selting À E [1, dl, and 8 = 1/T.
Theorem Let X 2 1, 5 E (0,1), and a, be the blocks of actions in Rd((+() defined in (11). Then, with
probability at least 1 - 8 we have
T/(m+D) b)
f(ā) F(ar)= S 4L(m + 1)2* Td In ( [ T(m + 1)27
dd
(v++ (v+ Vin (3) { + In (1+ T(m 1927. d(m + L)A
Let m 1, T 2 m²d 1,, and set L Vm/dd T1/4| m. Let rt be the rewards collected when playing at as defined in (11). Then, with probubilily at least we have
T OPT
[(m + 1)2rt in 14
n ( + 1) 73/4
1 1+2
2
dd
t=1
In(1/o) d
T(m + 1)27 dA
V
In (1+
V
Proof The proof is along the lines of OFUL's analysis. The main difficulty is that we cannot use the elliptical potential lemma, e.g., (Lattimore & Szepesvári, 2020, Lemma 19.4) due to the delay accumulated by V,, which is computed every m + L round only. Let
B-(0) ((10)=12) /2 { - d In (1+ 7(m + 1)27*
+ VT.
(18)
dA
By (Abbasi-Yaduee et al., 2011, Theorem 2), we have with probability at least 1 8 that 0" E Cr for every It follows directly that 0- E Dr for any т, such that (b, 0*) < (b,, 0,), where 0, (Od..... O2, Br...,, 0,) 0,) with 0- E Idd that maximizes (11) over C7-1- It can be shown that the regret is upper bounded by Σx Emth 2i=m41 (0m,, 0*). Following the standard analysis, one could then use
(br 0, - -0)) S [bb.::ll= 10 -0-00 0'Ilv--1'
While the confidence set gives 1 I|v,_, < ( the quantity Emth+ |6r,sll,, is much more complex
to bound. Indeed, the elliptical potential lemma allows to bound E. |/uell when Vn = Eest anu! + Ala-
However, recall that in our case have V, =F Limm+ br + Ala, which is only computed every m + L rounds. As consequence, there exists "delay" between V,-1 and the action by,s for i 2 m + 2, preventing from using the lemma. Therefore, we propose to use instead
(br.,, - 8²)5+) S br, |00 80 llv.....' where -
Σ br.b f=m+1
(19)
By doing so, the elliptical potential lemma applies. On the other hand, has to control ||00 - 00
1011 llv, 1²
which is not anymore bounded by 2,3 since the subscript matrix is V7,-1 instead of V,-1. Still, one can show that for any < m + L we have
00, 11
Tr (Vra-1 (0,-0)) (O) -0-)²
20

---

Published in Transactions on Machine Learning Research (05/2024)
Σ brgbts) (o. - 03) (0. (0: 099T)
i-1
Tr
V +
jmm+1
{-1
Ir
(1++
Σ
07) - -0y) V/1/3 (V (V= (v= vi
j=m+1
br,) ( (V7 1---1//000- br,) 7 Tr (V (0, 8*) (0. 8*) T Tv,L1)
$
1a
Σ
(V=-1 1/2
br,))
j=m+1
1+ Σ
V 1/2 b., (2) 110. -0
j=m+1
$ (1 + (L - 1) + 1)27 110, 1
s Lmm + 1)2r* 1|0. - 001
(20)
Recalling also that (b,0") (br, 0-) S 2L( + 1)7*, we have with probability at least 8
+/m++) L)
(b,0)) - (br, 0*)
L)(++))
min 22 1)²* (b.,0, -0:)
T/(++))
m+L
min 2L(m + 1)x*
Σ
(br 0, -09)
i=++1
T/(++L)
m+
110- - 01 } [br.ally.
min
2L(m + 1)x*
Σ
i=++1
T/(m+L)
min
2L(m+ + 1)" 22I(m 1))** 3)-1(0)
i=m+1
L/ m-
< 2L + 1) Br/m+L)(0)
min {I, [bbrallle221
i=++1
T T/(+L) m+L
}
22L(m + 1)pt (1/m+1))0))
min
1, ||,,, 2 v
i=++1 m m+L
<2V2L(m + 1)x* B1/(mt2)(0) /r In
IT In (1+ T(m + 1)27
< 4L(m + 1)x"
dA
V y In (7) + d In (1+ T(m - 1)2
(21)
d(m L)A
where we have usod (18), (19), and (20). Similarly to Proposition 5, note that in the stationary case, i.c., when m 0 and L 1, we exactly recover (Abbasi- (Abbasi-Yadkorri al., 2011, Theorem 3). The first claim of Theorem 1 is obtained by setting X E [1,d] and ā 1/T.
21

---

Published in Transactions on Machine Learning Research (05/2024)
Let Ry denote the right-hand side of (21). Combining this bound with the arguments of Proposition 2, we have with probability 1 -
T
T/ L)
m(m + 1)= m + L
Σ
F(ar)
T
(22)
t=1
T=1
(1(++L)
(b,, m(m 1)7* m + L
Σ
T/(m+L)
m(m 1)7 m +
(b.0% 0-) Rr
T
(23)
T/(++1 L)
m(m + 1)²²t f(a) RT
T
+ L
T=1
2m(m 1)T T
Pt
RT
(24)
m + L
t=1
4m + =1)²* T
ОРT
RT
(25)
+ L
m&T m L
T(m + 1)221 dd
ОPT 4(m 1)x*
+ (m + L/ Id In (1+
V yin (7) dln (1 (1+
T(m 1)2x*
d(m + L)>
where (22) and (24) come from the fact that any instantaneous reward bounded by (m + 1)7", see (8), (23) from (21), and (25) from Proposition 2.
Now, assume that m 1, 2 d22 1, and let L [vm/d T2/4 m. By the condition T, have Vm/d T1/4 > m 2 1, such that 2 1 and
m
V m T1/4 = = S
m V
71/4
+ S 2
m
1/4
d
d
Substituting in the above bound, have with probability 1 1
T
T(m + 1)27 1
OPT Σ n S + 1)bttt 73/4
1 1+2 In
2
dd
(V
A
In(1/8)
T'm 1)27*
In (1+
d
dd
The second clain of Theorem is obtained by setting X E [1, and d = 1/T.
A.6 Proof of Corollary 1
Lemma 1 Suppose that block-based bandil algoritio (in our case the bondil combiner) produces sequence of The blocks a,, with possibly different cortinalities lay such that
The
The 7(a)) S F(Tbe),
arl
for some sublinear function F. Then we have
miny aa
Σ, a
The f(ar) < min |ar| F(Tbe)
F(a)
max, [rr
7=1
22

---

Published in Transactions on Machine Learning Research (05/2024)
In particular, if all blocks have the same cordinality the last bound is just the block regret bound scaled by lar).
Proof We have
The r(a,) 2 min |arl
The
i(a;
a-
7m
The F(a)
min [r]
F(bbe)
min, |a,|
((O)
max |a_| The
min |a-| F ((Tbc)
max, a,
[
mini,
|rr]
Σ, ar
F(a)
min |a, F(Tbe).
max, a.y
Corollary 1 Consider on instance of LBM with unknown parameters (m,, Assume a bandät combiner is run on N S d instances of OFUL-memory (Algorithm 2), each using a different pair of porameters (mi.7) 1) from a set ={ {m..?))..... (m): such that (m..?.) E S. Let M (max, my)/(ming m2).
Then, for all T 2 (m, + 1)2 /m.d', the expected rewards (rbt) T of the bandit combiner satisfy
OPT
Ö(M d
(m, (m, + 1) T3/1).
=
M
Proof Let m, be the true memory size, and L, L(m.) the corresponding (partial) block length. Throughout the proof, ä denotes the block defined in (5) with length m, + T.,- First observe that only one of the OFUL-memory instances we test is well-spccifidd, i.c., has the truc parameters (m+, We can thus rewrite the regret bound for the Bandit Combiner (Cutkosky et al., 2020, Corollary 2), generalized to rewards bounded in [-R, R] as follows
Regret = = @ +C.- Them. + RT +
1
ΣΣ 3 11j
(26)
where The = T/(m, + L.) is the bandit combiner horizon, C. and a, are the constants in the regret bound of the well-specified instance (see below how we determine them), and the TJ are free parameters to be tuned. We now derive C, and a., To that end, we must establish the regret bound of the well-specified instance, and identify C. and a, such that this bound is equal to C.T where C, may contain logarithmic factors. For the sell-specified instance, the first claim of Theorem 2 gives that, with probability at least 1 6, we have
T//m. +L.)
F(a) - -((a)) ) < 4(m. + L.),m. + 117 Td In (1t T(m, + 1122
1+
dA
T(m, + 1)27; d(m, + L.)
VĀ+
In
+ d In
1+
T/(m. +L.)
F(a)
a
T(m, + 1)2x*
< 1122 A(m, + 1)
dln 1
(27)
|a
dA
T(m. - 1)2xx
V +
In
+ d In
1
d(m. L.)A
23

---

Published in Transactions on Machine Learning Research (05/2024)
where have used that |a-| | + L. for every Note that the right-hand side of (27) is expressed in terms of T, which is not the correct horizon, (/ + L.). However, recall that we have
m4 + L S 2
my d
T
4m
(m+ + L.,)* I
T
4mz
T
T
m, + L.
4mm,
1/3
T
2/3
T/
m. + L.
such that by substituting in (27) and identifying we have a, = 2/3, and
[Am+]
1/3
Tbc(m, + [., 1)2x
C.
(m, + 1)
d'nn
dd
Thelm, + 1)21
VX+ +
In
d In
1+
dd
Setting fy TTe T/22/3 and substituting in (26) with R (m, + 1)7h, we have that with high probability
F(ab be o (C2/ + N) 72/3 + (m, + +) To/3)
T=1
Now, recall that The = O T8/4), and that C. = 5( + +1) d2/3). Hence, N s dy/m, implies
N = ( and (m, + 1)7 I d /m,T implies (m, + 1)7. T O T213). Setting À E [1,4], 1/T, we obtain
The
F(ab)) be)
o ①(d (m, + 1)2rt T2/3)
E
(28)
Let. my be the memory size associated to the bandit played at block time step t by Algorithm 2. Let Mmin = miny my and Mmax = max, my- Finally, let Lunin and Immax the (partial) block length associated with Mmin and mmax. We have
T
The F(abo) my (m, + 17m!) 2
The F(a
Σ
bbc
bc Mmax (m, + 1)r1 Toe.
such that by Lemma 1 and (28) we obtain
min, |a,1 max, |arl
Σ- |a
F(ā))
àl
Mmmax (my + 1)2² Toe + min |a- la:10(d (m (m. + 1)8rt T2/3
E
Maiin
Lmmn
L. OPT
mh + Iea - Σ
T
T
Mmaa
Imaxx
T
24

---

Published in Transactions on Machine Learning Research (05/2024)
Mmmax (m, + 1172 T
+ (Mmnn mmin) (/s 0(1. /m (m, + +) 72/3).
M'min
Lunin
T Σ
Momin OPT
bc
Mmmax
/dm. (m, + 1)72 T8/1 + 6(dm, (m, + +1)371 22/1)
mmax
Mamin
1=1
Mmmax
ō Ö(dm, (m, + 1)2rt T3/44)
Mmmi
where we have used the fact that Miin + Limin mmmi/ d T2/1, and mmax + Imax v /max/ T1/4
Corollary is obtained by setting M Manas/ Mmin-
B Bandit Combiner
In this section we show our adaptation of the numbers Cj and target regrets Rj for the Bandit Combiner algorithm Algorithm 2 which builds on Cutkosky et al. (2020). For 03M(m,, (y), = 1,..., N, the numbers C, and target regrets Rg are defined as
Cj 4 ( (Am)))
Amj
1/3
dln (1
Tho(my + Li) + 1)2r)
(my + 1)35
1
(29)
dd
Tho(m, + 1))213
1
vx +
In
+ d
In
1
dA
R₁ C + (1 a,) 1-a;
1 (1 a,) %
"
C, -,,TTool
Tooll
1-91
1152(mg 1) N
kfj 77
Note that the form of the target regret Ry slightly differs from the one presented in (Cutkosky et al., 2020, Corollary 2) due to the different range of the rewards. The algorithm, which is an adaptation of Bandit Combiner in Cutkosky et al. (2020), is summarized in Algorithm 2.
C Additional Experiments
We provide an additional experiment comparing the regrets of 03M and OM-Block. In order to be able to plot the regret, we must know OPT which hard to compute in general. Since in the rising scenario with an rising
isotropic initialization OPT is oracle greedy, which is easy to compute, we present this experiment setting with m 1 and 7 2. We plot the regret of 03M and OM-Block against the number of time steps, mcasuring the performance at different time horizons and for different sizes of L (where L depends T, see at the end of Section 3.2). Specifically, we instantiated 03M and OM-Block for increasing values of L, setting the horizon of each instance based on the equations in Theorem 1 and Proposition 4. Figure 3 shows how the dimension of 0, which is d for 03M and d x L for OM-Block, has an actual impact on the performance since 03M outperforms OM-Block. The code is written in Python and is publicly available at the following GitHub repository: Linear Bandits with Memory.
25

---

Published in Transactions on Machine Learning Research (05/2024)
m 1, y=
135
OM-Block
Regret
144
0.7
0.52
Time
165
Figure 3: The regret of 03M and OM-Block. Each dot is a separate run where the value of L is tuned to the corresponding horizon.
26


Reviews:
[{"review_id": "srhLx5Lyi9", "reviewer": "Reviewer_WoTz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Why is the model in eq (1) and (2) a reasonable or justified way of doing things? Why model memory via a covariance matrix? Why not simply use a linear model that depends on the latest $m$ actions? E.g., $y_t = \\sum_{i=0}^{m-1}\\theta_{i}^\\ast a_{t-i} + \\eta_t$, which can be recast as a standard linear model ($m=1$) in a higher dimensional space. One can then simply invoke the technical machinery already developed for linear bandits to essentially \"solve\" this richer setting. \n\nEven if there are computational/statistical benefits to modeling memory via a covariance matrix, I do not see how it is a natural or intuitive way to do it compared to the simple alternative described above? The paper currently does not provide any background/motivation on this, and I think the authors need to better explain why their model is reasonable/justified.\n\nIn addition to the above, the \"rotting/rising\" settings need better explanation and motivation. Currently, they are simply passed off as settings with a positive or negative $\\gamma$. Further, this model is, in fact, not linear as the outcome depends non-linearly on past and present actions unless $\\gamma=0$.\n\nThe current version of the paper lacks a coherent example/motivation to ground the model. The mathematics is fine, but the reader is likely to walk away with the impression that the paper analyzes and provides results for an esoteric model that is a strict generalization of linear bandits and a partial generalization of some other models. The current positioning and motivation leaves much to be desired.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a bandit problem where the observed (scalar) outcome of a given round depends on the latest $m+1$ actions. The authors propose an OFUL-based algorithm for this setting and provide an upper bound on the regret thereof against the optimal sequence of actions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the \"Strengths And Weaknesses\" section.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UsIS6YXfYc", "reviewer": "Reviewer_CVyS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The author proposes a novel bandits framework that can generalize several structured nonstationry bandits problem including bandits, rising and rotting rested bandits and cyclic bandits, and it can also generalize a special case of MDP problem.  \n2. I also like the way they explain this problem step by step. It is quite clear. For example, in Section 3.1. They discuss the influence of initial m conditions. In Section 3.1,3.2, they give a clear explaination on the trade-off on L between long tern plainning and infrequent updating. \n3. Their results, although may not be optimal, is quite compelete as the first paper proposing this.\n\nWeakness:\n1. It is unclear to me wether this solution is optimal, seems a very direct solutions. \n2. It might be interesting to talk about some instance-dependent bound under this setting\nBut overall I think the results are enough as the first paper under this framework.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The author propose a new linear bandits framwork LBM where the reward at time t is affected by all the actions within [t-m, t] blocks. This frameworks generalized the stationary linear bandits, rising and rotting rested bandits and cyclic bandits. Under this framework, the author first proposes a variant of OFUL algortihm with the known-parameter m. Then the author propose a parameter-free algortihm by using a meta-algorihtm to select the right model with an additional $M\\sqrt{d(m+1)^{1+\\gamma}}$ multiplicative term in the final bound.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think it is a little unclear for me on the over-optimistic part (O3M). I can understand it has the same proofs as the OM. Are you mentioned this because it is more easy to implement? or has better emprirical results ?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fAxBmit3Be", "reviewer": "Reviewer_uWLR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- Novelty: It is kind of a natural process to think of an extension from the analysis of the K-armed bandits to linear bandits. However, I believe this paper well-defined and interpreted the concept of rising/rotting in the linear bandit setting. I think this is a topic someone should deal with someday, and the authors made a proper analysis. \n\n- Quality: I want to value three main techniques.\n1) $\\langle a_t, A_{t-1} \\theta^* \\rangle = \\langle A_{t-1} a_t, \\theta^* \\rangle$, so actually the researchers don't need to worry about the 'changing hidden parameter' $A_{t-1} \\theta^*$, and one can take this rising/rotting environment as 'changing arm set' environment where the environment changes based on learner's choice and the learner fully understand its effect. I think it is a simple idea that researchers who have deeply studied this field may find it easily, but at least for me, it is a result that gives me a fresh intuition.\n2) Instead of directly dealing with the 'true optimal sequence', they proved in Propositions 2 and 3 that one can use 'cyclic best action' as the alternative to the true optimal sequence since 'true optimal' and 'cyclic best' are tight. This is an interesting way to detour something difficult to compute. Though I haven't fully read the details of the proof, it is an interesting result for me if it is true. \n3) It was surprising that even the learner knew $\\theta^*$ beforehand, the 'oracle greedy policy' could have linear regret. It was very counter-intuitive. I haven't read the proof in detail, but if it is true then it is definitely worth to add points on this paper. \n\n- Clarity: The authors tried to deliver the main ideas as straightforward as possible. Though it is not crystal clear to me yet, at least I could understand the mathematical structure they constructed for their analysis. Plus, I personally like Figure 1 they added to help readers understand better.\n\n\nWeakness and Quality\n\n- Novelty: (super minor) Using OFUL, the traditional approach for the linear bandit, is a kind of predictable approach. \n\n- Clarity: I believe they need to explain some parts more clearly.\n\n1) I hope they explain more about the ease of the 'infinite memory case.' I know they mentioned it on Page 5, but they also need to explain it on the rising bandit case too, I believe. It is not straightforward for me how rising will also be easy. \n\n2) It is not clear how easy to find the best batch of actions $a_\\tau$. Though they mentioned they found the UCB indices by Gradient Ascent (Page 10, computational complexity), I think it would be great if authors also provided more explanation that computing blocks $a_{\\tau}$ is easy (such as a convex problem or sth? I am not super clear whether it is that easy problem).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In short, this paper is a linear bandit version of the rotting/rising bandit. The author assumes that the reward is non-stationary and depends on the previous decisions, especially on the memory matrix. Authors proved that in this sliding-window setting, the optimal policy can be tightly approximated by optimal cyclic policy, and using this idea they proposed a variant of OFUL, which minimizes the regret against the cyclic policies. This result holds for both rotting and rising bandit which is determined by the sign of the exponent $\\gamma$. Not only that, using the model selection approach, they could extend their approach to all the positive and negative cases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I believe the authors should also justify the scale of the effect of the history. I mean, the authors assume $A_t = I + \\sum a_s a_s^\\top$, but it is also a natural question to ask the case $A_t = I + \\alpha \\sum a_s a_s^\\top$ for some constant $\\alpha$ and effect of this constant $\\alpha$. \n\n- I need more explanation to support why 'finite memory' is natural. I read their argument in Page 5 that using the well-known Eliptic potential lemma, it becomes a trivial problem. However, I believe the tendency of rotting ($\\gamma <0$) and rising ($\\gamma>0$) are quite different, as they demonstrated\n\n- I need some valid explanation 2) It is not clear how the authors 'optimized' the sequence of batch actions. Though they mentioned they found the UCB indices by Gradient Ascent (Page 10, computational complexity), I think it would be great if authors also provided more explanation that computing block $a_{\\tau}$ is easy (such as convex problem or sth? I am not super clear whether it is actually that easy problem).\n\n- (Minor) What happens when the memory is not a sliding window, but a diminishing one? There are two representative ways of expressing the limitation of memory. One is the sliding window which the authors used in this paper, and the other is using discount factors to express the exponential decay of the memory. I think it would be great if the authors could also explain what happens with discount factors instead of this sliding window structure.", "broader_impact_concerns": "There are no ethical concerns we need to worry about in this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new nonstationary linear bandit model, to capture situations where rewards depend on the learner’s past actions in a fixed-length sliding window. This model (approximately) recovers a few previously bandit problems. Weaknesses include a matching lower bound, and a somewhat limited class of polynomial nonstationary reward functions. Overall, reviewers found the work to be technically sound and contribute meaningfully to the bandit literature. Some of the technical results are also interesting, such as using the cyclic policy as a reference as part of the analysis.

Please use the reviews to revise the paper, including strengthening the motivation, among others. In addition, can you elaborate further why finite m avoid trivializing the theory? The current argument relies on gamma to be sufficiently small.If gamma is large, does an infinite m still trivialize the theory?
Decision: Accept (poster)