Rebounding Bandits for Modeling Satiation Effects
Authors: Liu Leqi
Fatma Kilinc-Karzan
Zachary Chase Lipton
Alan L Montgomery
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bandits
Boredom
Satiation
Recommender Systems
Dynamical Systems

Abstract: Psychological research shows that enjoyment of many goods is subject to satiation, with short-term satisfaction declining after repeated exposures to the same item. Nevertheless, proposed algorithms for powering recommender systems seldom model these dynamics, instead proceeding as though user preferences were fixed in time. In this work, we introduce rebounding bandits, a multi-armed bandit setup, where satiation dynamics are modeled as time-invariant linear dynamical systems. Expected rewards for each arm decline monotonically with consecutive exposures and rebound towards the initial reward whenever that arm is not pulled. Unlike classical bandit algorithms, methods for tackling rebounding bandits must plan ahead and model-based methods rely on estimating the parameters of the satiation dynamics. We characterize the planning problem, showing that the greedy policy is optimal when the arms exhibit identical deterministic dynamics. To address stochastic satiation dynamics with unknown parameters, we propose Explore-Estimate-Plan, an algorithm that pulls arms methodically, estimates the system dynamics, and then plans accordingly.

Rebounding Bandits for Modeling Satiation Effects
Liu Leqi
Fatma Kılmg-Karzan
Machine Learning Department Carnegie Mellon University Pittsburgh, PA 15213 leqiêcs cmu. edu
Tepper School of Business Carnegie Mellon University
Pittsburgh, PA 15213 fkilinc@andrew cmu edu
Zachary C. Lipton
Alan L. Montgomery Tepper School of Business Carnegie Mellon University Pittsburgh, PA 15213
Machine Learning Department Carnegie Mellon University
Pittsburgh, PA 15213 zlipton@emu. edu
alanmonttgomery@cmu edu
Abstract
Psychological research shows that enjoyment of many goods is subject to satiation, with short-term satisfaction declining after repeated exposures to the same item. Nevertheless, proposed algorithms for powering recommender systems seldom model these dynamics, instead proceeding as though user preferences were fixed time. In this work, we introduce rebounding bandits, a multi-armes bandit setup, where satiation dynamics are modeled as time-invariant linear dynamical systems. Expected rewards for each arm decline monotonically with consecutive exposures and rebound towards the initial reward whenever that arm not pulled. Unlike classical bandit algorithms, methods for tackling rebounding bandits must plan ahead and model-based methods rely on estimating the parameters of the satiation dynamics. We characterize the planning problem, showing that the greedy policy is optimal when the arms exhibit identical deterministic dynamics. To address stochastic satiation dynamics with unknown parameters, propose Explore- Estimate-Plan, an algorithm that pulls arms methodically, estimates the system dynamics, and then plans accordingly.
Introduction
Recommender systems suggest such diverse items as music, news, restaurants, and even job candi- dates. Practitioners hope that by leveraging historical interactions, they might provide services better aligned with their users' preferences. However, despite their ubiquity in application, the dominant learning framework suffers several conceptual gaps that can result in misalignment between machine behavior and human preferences. For example, because human preferences are seldom directly ob- served, these systems are typically trained on the available observational data (e.g.. purchases, ratings, clicks) with the objective of predicting customer behavior 4 [7]. Problematically. such observa- tions tend to be confounded (reflecting exposure bias due to the current recommender system) and subject censoring (e.g., users with strong opinions are more likely to write reviews) [6]
Even if we could directly observe the utility experienced by each user, we might expect it to depend, part, on the history of past items consumed. For example, consider the task of automated (music) playlisting. As user is made to listen to the same song over and over again, we might expect that the utility derived from each consecutive listen would decline (35). However, after listening to other music for some time, we might expect the utility associated with that song to bounce back towards its baseline level. Similarly, a diner served pizza for lunch might feel diminished pleasure upon cating pizza again for dinner.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The psychology literature on satiation formalizes the idea that enjoyment depends not only on one's intrinsic preference for a given product but also on the sequence of previous exposures and the time between them R 6 Research on satiation dates to the 1960s (if not earlier) with early
28 Interestingly, even after controlling for marketing variables like price, product design, promotion, etc., researchers still observe brand-switching behavior in consumers. Such behavior, referred as variety seeking, has often been explained as a consequence of utility associated with the change itself [25] [7]. For a comprehensive review on hedonic decline caused by repeated exposure to a stimulus, we refer the readers to
studies addressing brand loyalty 42
In this paper, we introduce rebounding bandits, a multi-armed bandits (MABs) 37 framework that models satiation via linear dynamical systems. While traditional MABs draw rewards from fixed but unknown distributions, rebounding bandits allow each arm's 's rewards to evolve as a function of both the per-arm characteristics (susceptibility to satiation and speed of rebounding) and the historical pulls (c.g., past recommendations) In rebounding bandits, even if the dynamics are known and deterministic, selecting the optimal sequence of I arms to play requires planning in Markov decision process (MDP) whose state space scales exponentially in the horizon T. When the satiation dynamics are known and stochastic, the states are only partially observable, since the satiation of each arm evolves with (unobserved) stochastic noises between pulls. And when the satiation dynamics are unknown, learning requires that we identify stochastic dynamical system.
Catiorr--sttmttee-PPee (EEP) algorithm that (i) collects data by pulling each arm repeatedly, (ii) estimates the dynamics using this dataset; and (iii) plans using the estimated parameters. We provide guarantees for our estimators in $ 6.22 and bound EEP's regret in $ 6.3
We propose Explore-
Our main contributions are: (i) the rebounding bandits problem ($3) (ii) analysis showing that when arms share rewards and (deterministic) dynamics, the optimal policy pulls arms cyclically, exhibiting variety-secking behavior ($4.1); (iii) estimator (for learning the satiation dynamics) along with sample complexity bound for identifying an affine dynamical system using a single trajectory of data ($6.2); (iv) EEP, algorithm for learning with unknown stochastic dynamics that achieves sublinear w-step lookahead regret 34] ($6); and (v) experiments demonstrating EEP's efficacy ($7).
2 Related Work
Satiation effects have been addressed by such diverse disciplines as psychology, marketing, operations research, and recommendation systems. In the psychology and marketing literatures, satiation has been proposed as an explanation for variety- seeeing consumer behavior [1] 255 26). In operations research, addressing continuous consumption decisions, (3) propose deterministic linear dynamical system to model satiation effects. In the recommendation systems community, researchers have used semi-Markov models explicitly model two states: (i) sensitization where the user is highly interested in the product; and (ii) boredom-whedt where the user is not engaged [8]
The bandits literature has proposed a variety of extensions where rewards depend on past exposures,
both to address satiation and other phenomena. [14 21 39 tackle settings where each arm't 's expected
reward grows (or shrinks) monotonically in the number of pulls. By contrast, [19, 2 7 models where rewards increase
propose
function of the time elapsed since the last pull. the expected reward as function of the time since the last pull drawn from a Gaussian Process
1 model
with known kernel. [43] propose a model where rewards are linear functions of the recent history of actions and [29] model the reward as a function of a context that evolves according to known deterministic dynamics. In rested bandits [12). an arm's 's expected rewards change only when it is played, and in restless bandits [4 rewards evolve independently from the play of each arm.
Key Differences This may be the first bandits paper to model evolving rewards through continuous- state linear stochastic dynamical systems with unknown parameters. Our framework captures several important aspects of satiation: rewards decline by diminishing amounts with consecutive pulls and rebound towards the baseline with disuse. Unlike models that depend only on fixed windows or the time since the last pull, our model expresses satiation more organically as quantity that evolves according to stochastic dynamics. To estimate the reward dynamics, we leverage recent advances in the identification of linear dynamical systems 40 38 that rely on the theory of self normalzzdd
processes (33 | and block martingale conditions 40).

---

Salekon
Saraton
n+
7kk 5, Ap
(b) Au 155, by
Figure I: These plots illustrate the satiation level and reward of an arm from time 1 to 30. The two plots are generated with the same pull sequence, base rewards by and realized noises with variance 03 = .1. In Figure [a ?k .5 and X 3. In Figure Lb 7 = .8 and X = 1.5. In both cases, the arm has started with its base satiation level. Black dashed line: the satiation level. Red solid line: the reward. Blue dots: time steps where the arm is pulled.
3 Rebounding Bandits Problem Setup
Consider the set K arms [K] := {1...., K} with bounded base rewards .......bu bk. Given horizon T, policy गı. (..,....: TT) is sequence of actions, where actions and observed rewards. For any arm & E [K], we denote its pull history from time to T the binary sequence UR,0:T (ua.0:.... "K,T), where u2o0 = 0 and for / E [T]. ux, = if = k and Uk,t = otherwise. The subsequence of 4100TT from 1 to la (including both endpoints) is denoted by Uk,
[K] depends on past
At time i, each arm has a satiation level Sk,e that depends on satiation retention factor 7k E [0, 1), follows
Sket == The (56,t-1 ux,c-1) + Ek,t-1: Vt Eo.
where E5 = ming {t= U,tt 1} is the first time arm k is pulled and 2g,t-1 independent and identically distributed noise drawn from N(O,o?), accounting for incidental (uncorrelated) factors in the satiation dynamics. Because satiation requires exposure, arms only begin to have nonzero satiation levels after their first pull, i.e., 8k,0
$2.06 0.
At time / E [T], if arm is played with a current satiation level 8k,1. the agent receives reward jkkt by AASSR, where by the base reward for arm h and A 2 0 is bounded exposure influence factor. We use satiation influence to denote the product of the exposure influence factor A and the satiation level 8k,t- In Figure [ we show how rewards evolve in response both pulls and the stochastic dynamics under two sets of parameters, The expected reward of arm k (where the expectation is taken over all noises associated with the arm) monotonically decreases by diminishing amounts with consecutive pulls and increases with disuse by diminishing amounts.
Remark 1. We note that there exist choices by, Ye. Ag for which the expected reward arm k can be negative. In the traditional bandits setup, must pull matters are the relative rewards and the problem is mathematically identical, regardless of whether the expected rewards range from -10 0 or 0 to 10. In addition, negative expected rewards are reasonable. For example, when one of the arms corresponds to no recommendation with being its expected reward (e.g.. ... by 0, A =), then the interpretation of negative expected reward would be that pulling (recommending) the corresponding arm (item) is less preferred relative not pulling (no recommendation).
every time step. Thus, what
might construct settings where
Given horizon T 2 1, we seek pull sequence TIr where n, depends past rewards and actions (Ti, Pryds-... m1 /x (.1)) that maximizes the expected cumulative reward:
GT(TTT) = ET MxLe
Additional Notation Let maxxe[]] 7he and Ā maxse[K] de. We use a S b when S Cb for some positive constant C.
3

---

4 Planning with Known Dynamics
Before we can hope to learn an optimal policy with unknown stochastic dynamics, we need to establish procedure for planning when the satiation retention factors, exposure influence factors, and base rewards are known. We begin by presenting several planning strategies and analyzing them under deterministic dynamics, where the past pulls exactly determine each arm's 's satiation level, i.e. 8k,t = 7A ( 1 + - VI > ly. With some abuse of notation, at time 2 2, given pull sequence 1,,0:t-1, we can express the satiation and the expected reward of each arm as
Sk.0(Uk,00013 TNe (5k + uk,0-1) 7k (7k (sk,e-2 + 2x,(-2)) + Yk 1 E/=l 7k
(0,,(UKK000-1 by A EE Vk uR.5 f
(3)
At time t 1, we have that $x.1 (x.1(0x,0:0) = 0 and px.1 (x,1((k,00) = by for all E [K]. Since the arm parameters {Ax: yR. bi are known, our goal (2 simplifies to finding a pull sequence that solves the following bilinear integer program:
max M..e
ΣΣ 1=1
by
AB
Uki
Σ Uk = W [7], Wk,t E {0,1], Wk.0 = 0, vk E (
(4)
1=0
where the objective maximizes the expected cumulative reward associated with the pull sequence and the constraints ensure that at each time period we pull exactly one arm. Note that 4 includes products of decision variables Wk,r leading to bilinear terms in the objective. In Appendix A we provide an equivalent integer linear program.
4.1 The Greedy Policy
At each step, the greedy policy T picks the arm with the highest instantancous expected reward. Formally, at time t, given the pull history {uk,0c-1) -=- the greedy policy picks
Ti E arg max PR, (",,0..))
kE[K]
In order to break ties, when all arms have the same expected reward, the greedy policy chooses the arm with the lowest index.
Note that the greedy policy is not, general, optimal. Sometimes, we are better off allowing the current best arm to rebound even further, before pulling it again.
Example 1. Consider the case with two arms. Suppose that arm 1 has base reward by. satiation retention factor 7/2 E (0, 1), and exposure influence factor x1 = 1. For any fixed time horizon T > 2,
suppose that arm 2 has by = b, + 72-2 where 7/2 E (0, and X2 = 1. The greedy policy के. will I-72
keep pulling arm 2 until time T - and then play arm 1 (or arm 2) at time T. This is true because if we keep pulling arm 2 until T 1, at time T, we have p2,7 (u2,0:T-1)
bj = M1.T pMirru,,, (1). However, the policy Nh... where n.. = 2 if <T 2, 2, --- = 1, and Tテ = 2, obtains a higher expected cumulative reward. In particular, the difference GT(ZfTr) Gr ( will be 72 72 T-1
4.2 When is Greedy Optimal?
When the satiation effect is always 0, e.g., when the satiation retention factors ? 0 for all l [K], we know that the greedy policy (which always plays the arm with the highest instantaneous expected reward) is optimal. However, when satiation can be nonzero, it is less clear under what conditions the greedy policy performs optimally. This question is of special interest when we consider human decision-making since we cannot expect people solve large-scale bilinear integer programs every time they pick music to listen to.
In this section, we show that when all arms share the same properties (7k, At. by identical for k E [K], the greedy policy is optimal. In this case, the greedy policy exhibits variety-seeking behavior as it plays the arms cyclically. Interestingly, this condition aligns with early research that
We use "expected reward" to emphasize that all results in this section apply to settings where the satiation dynamics are deterministic but the rewards are stochastic, i.e. fik, bu ALSE, + Cx,t for independent mean-zero noises ck.t-

---

has motivated studies on satiation 28: when controlling for marketing variables (e.g., the arm parameters Tk. Åz. by), researchers still observe suriety-seeking behaviors of consumers (e.g., playing arms in cyclic order).
Assumption 1. ?11 -.... =...---.. 7K = 7 X -... Ax = X, and bj = =... bx b.
We start with characterizing the greedy policy when Assumption | holds.
Lemma 1 (Greedy Policy Characterization). Under Assumption 7 and the tie-breaking rule that when all arms have the same expected reward, the greedy policy chooses the one with the lowest arm index, the sequence of arms pulled by the greedy policy forms a periodic sequence: T T, Tt: Vt E N+.
2. , -TK- K, and T++K
In this case, the greedy policy is equivalent to playing the arms in a cyclic order. All proofs for the paper deferred to the Appendices.
Theorem 1. Under Assumption
given any horizon T, the greedy policy "i.r- is optimal.
Remark 2. Theorem D [suggests that when the (deterministic) satiation dynamics and base rewards are identical across arms, planning does not require knowledge of those parameters, since playing the arms in a cyclic order is optimal.
Lemma I and Theorem
I lead us to conclude the following result: when recommending items that share the same properties, the best strategy is to show the users a variety of recommendations by following the greedy policy.
On a related note, Theorem aalso gives an exact Max K-Cut of complete graph 1Tr on T vertices, where the edge weight connecting vertices and j is given by e(i, j) = X-b for + j. The Max K-Cut problem partitions the vertices of a graph into K subsets Pi,... Px. such that the sum of the edge weights connecting the subsets are maximized [0]. Mapping the Max K-Cut problem back to our original setup, each vertex represents time step. If vertex is assigned to subset Pk. it suggests that arm A should be played at time i. The edge weights e(i.j) = X- for * can be seen as the reduction satiation influence achieved by not playing the same arm both time and time j. The goal 4 is to maximize the total satiation influence reduction.
Proposition 2 (Connection to Max K-Cut). Under Assumption / an optimal solution to 4 is given by a Max K-Cut on Kr, where Kr is a complete graph on T vertices with edge weights e(i, Xy for all $j.
Using Lemma and Theorem we obtain an exact Max K-Cut of Kr: Ak E [K] Pa = e t = h (mod K) K]..
4.3 The w-lookahead Policy
To model settings where the arms correspond to items with different characteristics (e.g., we can enjoy tacos consecutive days but require time to recover from trip the steakhouse) must allow the satiation parameters to vary across arms. Here, the greedy policy may not be optimal. Thus, we consider more general lookahead policies (the greedy policy special case). Given window of size w and the current satiation levels, the w-llookahead policy picks actions to maximize the total reward over the next w time steps. Let denote [T/w]] Define 4, min (iw, T) for i [1] and to = O. More formally, the w-lookahead policy T..r is defined as follows: for any i E [1] given the previously chosen arms' corresponding pull histories {ug ]k_ where uN. = and uE, = 1 (and only if) ग.
k, the next w (or T mod w) actions T., 1+ are given by
Uk.0:t.-1 = 20 "k,00e-11> Wk E [K], ΣK Uk,t 1, Vt [t.], Uh 13, Vk E [K], [t.]
max
Map ( O
(5)
In the case of a tie, can pick any of the sequences that maximize ( We recover the greedy policy when the window size w = 1, and finding the w-lookahead policy for the window size w = T is equivalent to solving
Remark Another reasonable lookahead policy, which requires planning ahead at every time step, would be the following: at every time i, plan for the next actions and follow them for single time step. To lighten the computational load, we adopt the current wo-lookahead policy which only requires planning every time steps.
5

---

b (u (u,, ; (4,,,t)) to refer to the For the rest of the paper, we use Lookahead(12e de, Yk, by k=
solution of { when the arm parameters are {Tr 7k, bys k= the historical pull sequences of all arms till time 1 are given by {uk,0,, R==1 The solution corresponds to the actions that should be taken by the w-lookahead policy for the next t, - 4-1 time steps.
Theorem 2. Given any horizon T, let Vic be solution to 4.. For fixed window size w S T, we have that
GT(FLT) - Gr(TTT) 1- 71-
[T/w].
Remark 4. Note that when w = T, the w-lookahead policy by definition is the optimal policy and in such case, the upper bound for the optimality gap of w-lookahead established in Theorem 2 is also 0. In contrast to the optimal policy, the computational benefit of the w-lookahead policy becomes apparent when the horizon 7 is large since it requires solving for much smaller program (5). In general, the w-lookahhead policy is expected to perform much better than the greedy policy (which corresoonds to the case of w 1) at the expense of higher computational cost. Finally, we note that for the window size of VT, obtain Gr(rir)) Gr(TEr) & O(VT).
Learning with Unknown Dynamics: Preliminaries
When the satiation dynamics are unknown and stochastic (a= > 0), the learner faces a continuous- state partially observable MDP because the satiation levels are not observable. To set the stage, we first introduce our state representation ($5..T) and a regret-based performance measure ($ (..2.) In the next section, we will introduce EEP, our algorithm for rebounding bandits.
5.1 State Representation
Following [32. at any time t [T], we define state vector 2, in the state space X' to be 2, (1,,,1 01 22,1, N2,1: ... KKt, HK,)), where nt.t N is the number of steps at time since arm k was last selected and Th,t is the satiation influence (product of X and the satiation level) as of the most recent pull of arm k. Since the most recent pull happens at t - 1l,tt we have Th,t = by Mk,t-DE, Aς A5-5R,r-ne... Recall that pk,t-ng. is the reward collected by pulling arm & at time t Tk Note that by is directly observed when arm is pulled for the first time because there is no satiation effect. The state at the first time step is 2 (O....,0) .). At time t, if arm k is chosen at state 24, and reward PR.t is obtained, then the next state It+1 will satisfy (i) for the pulled arm k. nx,++1
and 23,441 by Mk.t; (ii) for other arms k' f k. nw, ,1+1 n 1 if ny. * O, 7,,441 = 0 if nw. = O, and the satiation influence remains the same 2k1,4+1 = IK.L-
Given (7k, b k= the reward function r X [K] - represents the expected reward of pulling arm k under state Z4:
If Tikt 0. then r(x,, k)) by- If mi 2 1, r( E| by 7 Tk.t A where the expectation is taken over the noises in between the current pull and the last pull of arm k. See Appendix C.I for the full description of the MDP setup (including the transition kernel and value function defimitoon of rebounding bandits.
5.2 Evaluation Criteria: w-step Lookahead Regret
In reinforcement learning (RL), the performance of a learner is often measured through a regret that compares the expected cumulative reward obtained by the learner against that of an optimal policy in a competitor class [20]. In most episodic (e.g.. finite horizon) RL literature [3 [5]. regrets are defined in terms of episodes. state) after each episode ends, independent of previous actions taken by the leaner. Unlike these episodic RL setups, in rebounding bandits, we cannot restart from the initial state because the satiation level cannot be reset and user's memory depends on past received recommendations. Instead, [34] proposed a version of w-step lookahead regret that divides the T time steps into [T/w) episodes where each episode (besides the last) consists of time steps. At the beginning of each episode, the initial state is reset but depends on how the learner has interacted with the user previously. In particular, at the beginning of episode i + 1 (at time f iw 1), given that the learner has played Tisw with corresponding pull sequence Ug,0zi for E [K], we reset the initial state to be r² = (111 (11,0 (u.,::i); ). 11, 11K,i 1 (K,000)))) ); n nx,0++1) where (.,((.) defined (3) and 1g. is the number of steps since arm k is last pulled by the learner of time iw +
such cases, the initial state is reset (e.g., to a fixed

---

Then, given the learner's ' policy TI.,, where Te : X' + [K]. the w-step lookahead regret, against competitor class C (which we define later), defined as follows:
Reg th (T) Σ
[T/w/-1 m EC
IE
Σك= - min//,T'-iw) r(riuttj (z(winnt)) Fiw+1
x²
==
E
iw)
r r(Ziw+j Tiw+y (Few+s))
Tho+1 = x²
(6)
where the expectation is taken over fiw+2,-.... (1in((++))
The competitor class C" that have chosen consists of policies that depend on time steps, i.e., C" = { w. म. = (x(2²) = H (at), Rg E [K] Vt E Ty x E X}. We note that C" subsumes many traditional competitor classes in bandits literature, including the class of fixed-action policies considered in adversarial bandits (20) and the class of periodic ranking policies 7 In our paper, the w-lookahead policy (including the T-lookahead policy given by (4) is time-dependent policy that
belongs to C", since at time t, it will play a fixed action by solving (5) using the true reward parameters
{Ag, The ] k=1- The time-dependent competitor class C" differs from state-dependent competitor class which includes all measurable functions Te that map from X' to [K]. The state-dependent competitor class contains the optimal policy л² where x (azz) depends on not just the time step but also the exact state zt. Finding the optimal state-dependent policy requires optimal planning for continuous-saad MDP, which relies on state space discretizion [3] or function approximation (e.g.. approximate dynamic programming algorithms (30) 9 (36). In Appendix[C] we provide discussion and analysis on an algorithm compared against the optimal state-dependent policy. We proceed the rest of the main paper with C" defined above.
When
1, the 1-step lookahead regret is also known as the instantaneous regret, which is commonly used in restless bandits literature and some nonstationary bandits papers including [29]. Note that low instantaneous regret does not imply high expected cumulative reward in the long-term, i.c., one may benefit more by waiting for certain arms to rebound. When w = T. we recover the full horizon regret. As we have noted earlier, finding the optimal competitor policy in this case is computationally intractable because the number of states, even when the satiation dynamics are deterministic, grows exponentially with the horizon T. Finally, we note that the w-step lookahead regret can be obtained for not just policies designed to look steps ahead but any given policy, For more comprehensive discussion on these notions of regret, see (34 Section 4].
Explore-Estimate-Plan
We now present stochastic dynamics and unknown parameters, that (i) collects data by pulling each arm a fixed number of times; (ii) estimates the model's parameters based on the logged data; and then (iii) plans according to the estimated model. Finally, analyze EEP's regret.
(EEP), an algorithm for learning in rebounding bandits with
Because each arm's 's base reward known from the first pull, whenever arm is pulled at time and Ak,t * 0, we measure the satiation influence AgSk,t, which becomes the next state Fh,++1
Fk.t+1 A = A 88,1 + > + >A E.u =
Bk.t T
ahe d -mu0- 1 - Tk
IR.1+I-nE.
We note that the current state Fh.t equals 24.441-me.- since 08,141-me. is the last observed satiation influence for arm l and n is the number of steps since arm k was last pulled.
6.1 The Exploration Phase: Repeated Pulls
We collect a dataset Ph by consecutively pulling each arm n- times, in turn, where 2 [T223/ (Line 4-7 of Algorithm 1.. Specifically, for each arm E [K]. the dataset Ph contains a single
trajectory of n observed satiation influences ēx. T.....,,R,..... TR. 1, where 2R, 0 and ãx.j (j > 1) the difference between the first reward and the j-th reward from arm Thus, for T &h.++ E Pg. using 7
with naa (because pulls are consecutive), it follows that
kk = Tukkk + d2 + Ek.ss
(8)
where d2 = A47i and ΣΦ, are independent samples from NN o2,w) with 02, = -oo In Appendix [..2] we discuss other exploration strategies (e.g., playing the arms in a cyclic order) for EEP and their regret guarantecs.
7

---

Algorithm 1: w--lookahead
Input: Lookahead window size w, Number of arms K, Horizon 7
Initialize & I, TTT to be an empty array of length T and T 7 + w (1 mod w).
for k = 1..... K do
Set t' and initialize an empty array Pk.
for c= O,..., | do
Play arm obtain reward Pk,e-c and add pk, P Ph. Set nं k and increase by 1.
7
end
Obtain nhe de using the estimator
9.set dạ /dk/ and by = pk.e"
end
Let lo = T, set Te:to = (1...., T + 1), and play Tuato
10
for i = 1,..., T- do
12
Set t, = min (ti-1 T..
Obtain +4,, Lookahead (Ax, 7hk b k== ou.,0.t.11 1 t--,,t) where {uk,0::,-1 fk=1 are the arm pull histories correspond to Mh::111 Play mi 1+1,2
14
15
end
6.2
Estimating the Reward Model and Satiation Dynamics
For all l E [K], given the dataset Pt we estimate A₁- ((Y,, dx) using the ordinary least squares estimator:
Åg arg min Y AERS
XxA12
where Yk I= is an n-dimensional vector whose j-th entry is ēkj+1 and Xx i takes as its j-th row the vector Tx.j (Tx.j, 1) i.e. jRj+i 1 is treated be the response the covariates Tk-j- For n 2 2, we have that
As =
7 dx
=
Xx T
Xx
X
Yk:
(10)
and we take A₂ = |d
The difficulty in analyzing the ordinary least squares estimator 10 for identifying an affine dynamical system (8) using a single trajectory of data comes from the fact that the samples are not independent. Asymptotic guarantees of the ordinary least squares estimators in this case have been studied previously the control theory and time series communities [33 (2)- Recent work on system identifications for linear dynamical systems focuses the sample complexity [40] 38). Adapting the
proof of [40] Theorem 2.4], we derive the following theorem for identifying our affine dynamical system
Theorem 3. Fix E (0.1) For all [K]. there exists constant no k) such that if the dataset Ph satisfies 2 no (6, k), then
P ||A
Aulla Z v1/(in) 8,
a2 (1 72
22
where 1/
min
164 (1-
M1 ~n 120
As shown in Theorem when da = > gets larger, the convergence rate for Åş gets slower. Given single trajectory sufficient length, we obtain Fix - Tul O(1 and Idx - dal S (L/v/n). In Corollary 4
we show that the estimator of d also achieves O(1/ nn) estimation error.
Corollary 4. Fix d E (0. 1). Suppose that for all k E [K], we have P( - A&ll 2 1/vD) < 8
and 7ik 0. Then, with probability 8. we have that for all k [K].
Fix - 7xl 000 (1)
A
Au S 0
v
8

---

-2
Vi 0.5
A1
V: 0.5
A2
log|
-
Y4
Ys 0.6
log
An 2
Ag
Vs
As 2
-6
2
3
5
2
(a) log
74
Yk v.s.
log n
(b) log de Au v.s. log
Figure 2: Figure 2a and 2b are the log-log plots of absolute errors of 7h and X with respect to the number of samples
single trajectory. The results are averaged over 30 random runs, where the shaded area represents one standard deviation.
neward
165
6.00
160
5.75
155
t15.50
Cumulal 1ive
145
140
T.lookahead
- 4.50
.44.5
5.25
5.00
W 8, Slope 0.67
Slope 0.61
0.57
135
y-llokaheaad
4.25
w Slope 0.71
130
4.50
6.00
log
30
(b) log Reg log
Figure 3: Figure 3a shows the expected cumulative reward collected by the T-lookahead policy (red line) and w-llokkahead policy (blue dots) when 30. Figure 3b shows the log-log plot of the w-step lookahead regret of w-llokahhad EEP under different T averaged over 20 random runs.
6.3 Planning and Regret Bound
In the planning stage of Algorithm (Line 11-15), at time 4--1 1, the next arms play obtained through the Lookahead function defined in (5) based on the estimated parameters from the estimation stage (Line 8). Using the results in Corollary 4 obtain the following sublinear regret bound for woloooaheaad EEP.
Theorem 5. There exists constant To such that for all > To and w S T233, the w-step lookahead regret of w-lookahead Eaplore-Estimater Paann satisfies
Reg" (T) < /2K2/222/3 T).
Remark 5. The fact that EEP incurs regret of order O(T2/3) is expected for two reasons: First, EEP can be viewed as an
(ETC) algorithm that first explores then exploits. The regret EEP resembles the O(T2/3) regret of the ETC algorithm in the classical K-armed bandits setting 20) In rebounding bandits, the fundamental obstacle to mixing the exploration and exploitation stages is the need to estimate the satiation dynamics. When the rewards of each arm are not observed periodically, the obtained satiation influences can no longer be viewed as samples from the same time-invariant affine dynamical system, since the parameters of the system depend on the duration between pulls. In practice, one may utilize the maximum likelihood estimator obtain estimates of the reward parameters but obtaining the sample complexity of such an estimator with dependent data is difficult. Second, it has been shown in [5] that when the rewards of the arms have temporal variation that depends on the horizon T, the worst case instantancous regret has a lower bound (2(2333) On the other hand, in the traditional K Kaamedd bandits setup, the regret (following the classical definition (20) is lower bounded by 12T)) and can be attained by methods like the upper confidence bound algorithm (00 Precisely characterizing the regret lower bound for rebounding bandits of future interest.
Experiments
We now evaluate the performance of EEP experimentally, separately investigating the sample effi- ciency of our proposed estimators I00 for learning the satiation and reward models (Figure and the computational performance of the w-lookahead policies (5) (Figure 3ap. For the experimental setup,
we have 5 arms with satiation retention factors 71 72 5, -6, 74 .7,75 = .8, exposure
influence factors À 1, A2 = A = 3, As = Às = base rewards b 2, dz 3, bb 4, b2 =
2, b5 10, and noise with variance o, = 0.1.

---

Parameter Estimation We first evaluate our proposed estimator for using a single trajectory per arm estimate the arm parameters Yk: Ag. F we show the absolute error (averaged over 30 random runs) between the estimated parameters and the true parameters for each arm. Aligning with our theoretical guarantees (Corollary 4 the log-log plots show that the convergence rate of the absolute error is on the scale of O(n 1/22..
w-lookahead Performance To evaluate w-lookahead policies, we solve (5) using the true reward parameters and report expected cumulative rewards of the obtained w-lookahead policies (Figure Bap. Recall that the greedy policy is precisely the 1-lookahead policy. In order to solve the resulting integer programs,
Gurobi 9.1 [33] and set the number of threads for solving the problem to 10. When T = 30, the T-lookahead policy (expected cumulative rewards given by the red line in Figure Baj solved through 44) is obtained in 1610s. On the other hand, all w--lokkahead policies (expected cumulative rewards given by the blue dots in Figure 3a for w in between 1 and 15 are solved within 2s. We provide the results when T 100 in Appendix G Despite using significantly lower computational time, w--lookahead policies achieve a similar expected cumulative reward to the T-lookahead policy.
EEP Performance We evaluate the performance of EEP when T ranges from 60 to 400. For each horizon T, we examine the w-step lookahead regret of w-lookahead EEP where = 2, 5, 8, 10. All results are averaged over 20 random runs. As increases, the exploration stage of EEP becomes longer, which results in collecting more data for estimating the reward parameters and lower variance of the parameter estimators. We fit a line for the regrets with the same lookahead size w to examine the order of the regret with respect to the horizon T. The slopes of the lines (see Figure(3b] legend) are close to 2/3, which aligns with our theoretical guarantees (Theorem 5 i.e., the regrets are on the order of (TT/3)). In Appendix G. we present the T -tep lookahead regret of w-lookahead EEP under the same settings, and additional experimental setups and results.
8 Conclusions
While our work has taken strides towards modeling the exposure-dependen evolution of preferences through dynamical systems, there are many avenues for future work. First, while our satiation dynamics are independent across arms, natural extension might allow interactions among the arms. For example, a diner sick of pizza after too many trips to Di Fara's ss likely would also avoid Grimaldi's until the satiation effect wore off. On the system identification side, we might overcome reliance on evenly spaced pulls, producing more adaptive algorithms (e.g., optimism -asedd algorithms) that refine their estimates, improving the agent's policy even past the pure exploration period. Finally, our satiation model captures just one plausible dynamic according to which preferences might evolve in response past recommendations. Characterizing other such dynamics (e.g.. the formation of brand loyalty where the rewards of an arm increase with more pulls) in bandits setups is of future interest.
Acknowledgement
LL is generously supported by Open Philanthropy AI Fellowship. This research has been partly funded by the Center for Marketing Information and Technology at the Tepper School of Business. The authors would like thank David Childers, Biswajit Paria, Eyan P. Noronha, Sai Sandeep and Max Simchowitz for very helpful discussions, and Stephen Tu for his insightful suggestions on system identification of affine dynamical systems.
References
[1] Yasin Abbasi- Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2320- 2011.
[2] Soumya Basu, Rajat Sen, Sujay Sanghavi, and Sanjay Shakkottai. Blocking bandits. In Advances in Neurul Information Processing Systems, pages 4785-4794 2019.
[3] Manel Baucells and Rakesh K Sarin. Satiation in discounted utility. Operations research, 150 2007.
10

---

[4] James Bennett, Stan Lanning, et al. The netflix prize. In Proceedings of KDD cup and workshop. volume 2007, page 35. New York, 2007.
[5] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Optimal exploration-exploittionn in a multi-armed bandit problem with non-stationary rewards. Stochastic Systemx, (4):319-337, 2019.
[6] Felipe Caro and Victor Martinez-de Albéniz. Product and price competition with satiation effects. Management Science, 58(7):3357-1373, 2012.
[7] Leonardo Cella and Nicolò Cesa-Bianchi. Stochastic bandits with delay-dependent payoff'. In International Conference on Artificial Intelligence and Statistics, pages 1168-1177, 2020.
[8] Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians. arXiv preprint arXiv: OrXivv/810.000 /11000893, 2018.
[9] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6(Apr):503-55) 2005.
[10] Alan Frieze and Mark Jerrum. Improved approximation algorithms for max k-cut and max bisection. Algorithmica, 18(1):67-81, 1997.
[11] Jeff Galak and Joseph P Redden. The properties and antecedents of hedonic decline. Annual review of psychology, 69:1-25, 2018.
[12] John C Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41 (1):::148-16 1979.
[13] James Hamilton. Time series analysis. Princeton University Press, Princeton, N.J, 1994.
[14] Hoda Heidari, Michael J Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In JJCAI, pages 1562-1570, 2016.
[15] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 1 11(4), 2010.
[16] Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. Unbiased learning-to-rante with biased feedback. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 781-789 2017.
[17] Barbara Kahn. Consumer pariety-seeking among goods and services: integrative review. Journal of retailing and consumer services, (3):1139144,, 1995.
[18] Komal Kapoor, Karthik Subbian, Jaideep Srivastava, and Paul Schrater. Just in time recommen- dations: Modeling the dynamics of boredom in activity streams. In Proceedings of the eighth ACM international conference on web search and data mining, pages 233-242, 2015.
[19] Robert Kleinberg and Nicole Immorlica. Recharging bandits. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages 309-319. IEEE, 2018.
[20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[21] Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. In Advances in neural information processing systems, pages 3074-3083.2017 2017.
[22] Lennart Ljung. System identification. Wiley encyclopedia of electrical and electronics engi- neering, pages 1-19, 1999.
[23] Gurobi Optimization LLC. Gurobi optimizer reference manual, 2021.
[24] Nikolai Matni and Stephen Tu. A tutorial on concentration bounds for system identification. In
2019 IEEE 58th Conference on Decision and Control (CDC), pages 3741-3749. IEBE, 2019.
[25] Leigh McAlister. A dynamic attribute satiation model of variety-seeking behavior. Journal of Consumer Research, 9(2):141-150, 1982.

---

[26] Leigh McAlister and Edgar Pessemier. Variety seeking behavior: An interdisciplinary review. Journal of Consumer research, 93)):11-332. 1982.
[27] Julian John McAuley and Jure Leskovec. From amateurs connoisseurs: modeling the evolution of user expertise through online reviews. In Proceedings of the 22nd international conference on World Wide Web, pages 897-908. ACM, 2013.
[28] J Douglas McConnell. The development of brand loyalty: an experimental study. Journal of Marketing Research, 5(1):13-19, 1968.
[29] Yonatan Mintz, Anil Aswani, Philip Kaminsky, Elena Flowers, and Yoshimi Fukuoka. Nonsta- tionary bandits with habituation and recovery dynamics. Operations Research, 1493)11493 2020.
[30] Rémi Munos. Performance bounds in no-n for approximate value iteration. SIAM journal on control and optimization, 46(2):541-56) 2007.
[31] Ronald Ortner and Daniil Ryabko. Online regret bounds for undiscounted continuous rein- forcement learning. In Advances in Neural Information Processing Systems, pages 1763-1771, 2012.
[32] Ronald Ortner, Daniil Ryabko, Peter Auer, and Rémi Munos. Regret bounds for restless markov bandits. In International Conference on Algorithmic Learning T'heory, pages 214-228. Springer, 2012.
[33] Victor Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer, 2009.
[34] Ciara Pike-Burke and Steffen Grunewalder. Recovering bandits. In Advances in Neural Information Processing Systems, pages 14122-14131, 2019.
[35] Rehecca K Ratner, Barbara E Kahn, and Daniel Kahneman. Choosing less sess-preeeree experiences for the sake of variety. Journal of consumer research, 26(1):1-15, 1999.
[36] Martin Riedmiller. Neural fitted q iteration-first experiences with data efficient neural reinforcement learning method. In European Conference on Machine Learning, pages 317-328. Springer, 2005.
[37] Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
[38] Tuhin Sarkar and Alexander Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In International Conference on Machine Learning, pages 5610-5618, 2019.
[39] Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2564-24 2572,,27, 2019.
[40] Max Simehowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. In Conference On Learning Theory, pages 433, 2018 8.
[41] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. International Conference on Machine Learning, pages 814-823, 2015.
[42] William Tucker. The development of brand loyalty. Journal of Marketing research, 1(3):32-35, 1964.
[43] Romain Warlop, Alessandro Lazaric, and Jérémie Mary. Fighting boredom in recommender systems with linear reinforcement learning. In Advances in Neural Information Processing Systems, pages 1757-1768, 2018.
[44] Peter Whittle. Restless bandits: Activity allocation in a changing world. Journal of applied probability, 25(A))287-298, 1988.
12


Reviews:
[{"review_id": "hJ6khh-ByuS", "reviewer": "Reviewer_rYye", "summary": "This paper introduces a problem of modeling satiation effects in multi-armed bandits. For example, if we assume the arms are restaurants that an agent is going to over time. Said agent may have a preference for pizza hut, but eating there every night would lead to a lower reward than it would if you haven't been to pizza hut in a while. The authors prove that the greedy algorithm is optimal when satiation retention, base rewards, and satiation influence is known and is equivalent over all arms. The authors then provide an upper bound on regret when using their EEP (Explore, Estimate, Plan) policy. The authors also provide empirical results on a toy version of the problem.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I have read through the paper in detail but did not read carefully through the proofs provided in the appendices. Based on that information, I believe the theoretical results to be sound. The problem of rebounding bandits for this kind of satiation effects is a novel contribution to this area. I also appreciate the literature review of the psychology behind satiation effects and how the authors formulation of the problem fits into the current understanding of satiation. One question I have is did the authors observe any cyclic-like behavior in the setting of unknown dynamics if given a sufficient enough T?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors thoroughly provided limitations throughout the paper and included remarks to address potential questions about limitations. As this is a highly theoretical paper the authors provided sufficiently discussed potential negative societal impacts by stating that only certain aspects of human behavior can be captured in this setting and that more work is needed before deploying this in practice. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "g5NQQNLBYNo", "reviewer": "Reviewer_kguD", "summary": "This paper introduced rebounding bandits where satiation dynamics are modeled as time-invariant linear dynamical systems. With consecutive exposures to the same item, the expected rewards for each arm decline monotonically, and whenever that arm is not pulled, the reward rebounds. It first studied the offline problem and then characterized the regret bound for the proposed online algorithm. The paper propose Explore-Estimate-Plan and proves that the greedy policy is optimal when the arms exhibit identical deterministic dynamics. It also claims that this is the first bandits paper to model evolving rewards through continuous-state linear stochastic dynamical systems with unknown parameters.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In general, the paper is well written and I enjoy reading the paper. I have the following main comments:\n\n1. Can you specify the key difference between your model and 1) recharging bandits 2) non-stationary bandits? I understand that you model evolving rewards through continuous-state linear stochastic dynamical systems, but 1) from the modeling perspective, what additional features does it capture? Is it a more general model?; 2) from the technical aspect, what is the technical contribution compared to the existing literature?\n\n2. Can you characterize the computational cost for solving the w-lookahead policy (formula (5))? The algorithm can be inefficient if it is the \\sqrt{T}-lookahead policy.\n\n3. In the definition of regret in Section 5.2, the regret is defined for the w-step lookahead. It seems doable that in each step, the algorithm solves the w-step lookahead policy, but it only plays the arm for the current state. When the response is received, it moves to the next time step and resolves the optimization problem. It may perform better if the policy is planned ahead of time and update at each time step.\n\n4. For the online learning part, can UCB-type algorithm be designed to improve the regret from O(T^{2/3}) to O(T^{1/2})? The algorithm is suboptimal since in the K-armed bandits case, the regret of Algorithm 1 is still O(T^{2/3}). UCB-type algorithm seems possible since larger value of gamma and smaller value of d is more optimistic.\n\n5. It would help to show the empirical computational cost for different values of w in the numerical section.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "dF34kg4F3hA", "reviewer": "Reviewer_q6Cg", "summary": "The paper proposes a Multi-armed Bandits model with non-stationary reward affected by users' satiation level. The authors consider two cases of satiation dynamic: known deterministic dynamics and unknown stochastic dynamics. Then the authors show that under specific conditions a greedy algorithm is optimal. In the general setting (unknown stochastic satiation dynamics), they propose a two-step algorithm EEP with error estimation and analysis.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposes an interesting framework modelling users non-stationary interests on the same item, which is practical in many real-world scenes, and novel in bandit learning. The proposed model is also general enough to cover both deterministic and stochastic cases of satiation level. The experiment results look promising. Also, the paper is well written and easy to follow.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}, {"review_id": "HxBeJhuvurK", "reviewer": "Reviewer_GJkC", "summary": "This paper considers a class of Multi-Armed Bandits in which the rewards on arms decline monotonically with consecutive arm pulls and rebound to the base value when arms are not pulled. The paper distinguishes itself from previous similar approaches, which assume the reward to collapse to some “zero” after an arm pull and recharge with time — in this paper, the degree of satiation effect depends on the number of recent pulls (not just the last pull).\n\nThe paper first provides analysis for this problem setting with all arms sharing the same deterministic and known satiation dynamics and shows that the optimal policy in this case pulls arms cyclically. Further, the paper analyses the stochastic setting with unknown satiation dynamics, providing an algorithm to explore and plan in this situation and provides regret bounds for the same. Finally, the paper concludes with numerical evaluation to (1) evaluate the proposed algorithm and (2) run validation checks for the theoretical regret bounds.  \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths/Positives:\n\n1. The problem is well motivated. Previous relevant work studying similar bandit classes seems to assume that the bandit reward only depends on the time since the last pull. However, the added complexity of this paper fits the motivation well. \n\n2. Paper is very engaging to read and is written well. The paper does a good job of introducing the problem setup (through illustrative examples, etc.), distinguishing it from previous related work and the overall narrative/flow of the paper is great.  \n\n3. Theoretical analysis in the paper seems to be solid -- there are regret bounds presented for the proposed algorithm and other theoretical guarantees for the estimation errors for the other satiation parameters. \n\nWeaknesses/Questions/Negatives:\n\n1. I’m not sure the linear satiation dynamics make perfect sense for the following reason: In the linear satiation dynamics defined in Equation 1, it seems with enough number of arms pulls, the (degree of satiation) > (base reward). In that case the reward accrued from an arm pull would be negative. In other words, inserting extra arm pulls (more resources) can be detrimental? This seems a little counterintuitive. \n2. One of the contributions of the paper is the observation that when all arms have the same rewards and satiation dynamics, the optimal policy is cyclic. However, this result seems a little trivial to me -- because intuitively, that seems like the natural thing to do (maximizing the gap between consecutive pulls of the same arm). \n3. Line 49: Why are states partially observable when the satiation dynamics are known but stochastic? If the decay factor \\gamma is known, can’t we observe the satiation effect of a previous arm pull, when the arm is pulled next? \n4. The w-lookahead policy doesn’t seem like a great solution to the problem (more in the following point on experiments): It seems to be still very expensive for large w and inaccurate for small w. The theoretical bound in Line 190, seems pretty lossy for w= sqrt(T). Similarly for the expression in Theorem2, the bound can blow up when T is large and w<T with \\gamma close to 1. So while the theoretical analysis and the guarantee is good to have, the bound doesn’t seem very promising. \n5. Experiments section seems a little weak: \n\na) Experiments are run with just 5 arms in the simulation. It would be good to see what happens to the performance and runtime (scalability of the algorithm) for larger problem sizes. \n\nb) In Fig.3, the results are averaged over just 5 runs. It would be good to have atleast 30 or 50 independent runs and/or have error bars in Fig 3(a).\n\nc) While the figures establish the validity of the theoretical regret bounds presented earlier, it’s hard to judge the actual performance of the algorithms because there are no baselines. For instance, in Fig 3(b), there seems to be a sharp drop in regret when w increased from just w=2 to w=10. That indicates this regret could be much higher in comparison to the w=T policy (not shown in the figure), meaning w=2 or 10 is probably a bad policy?  \n\nd) Part of Fig 2 is hard to read because of the legends. Having legends outside of the chart would be great.   \n\n\nOther comments:\n\n1. Line 58: Point (iv) is hard to understand, without reading the rest of the paper. \n2. Typos: Line 143: “to to”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors acknowledge some technical limitations of their work (but not negative societal impact in particular). I don't foresee any negative social impact of this work either. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The rebounding bandits model proposed and analyzed in the paper was appreciated by all the reviewers as an interesting and relevant problem, and by and large the algorithm and the analysis and the presentation was considered to be a decent contribution. The reviewers raised a number of questions in their reviews, and the authors did a reasonable job of addressing most of them. It will be critical that the authors revise the paper to ensure that the issues raised are addressed and to prevent some of the misunderstandings from persisting with the general reader. Two specific issues that lingered with the reviewers: (1) the issue of negative rewards generated some discussion. I do think the authors’ elaboration in the discussion with one of the reviewers is legitimate, but this point should be included/clarified in the paper. (2) The empirical results are quite weak (specifically, number of arms and number of runs in results, baseline (e.g., w=T)) . The author response to all questions about these matters is that they will be addressed “in future manuscripts of the paper.” I’m not sure what this means: in fact, I would almost consider it to be a condition of acceptance that these be included in the revised paper
Decision: Accept (Poster)