Rebounding Bandits for Modeling Satiation Effects
Year: 2022

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 ExploreEstimate-Plan, an algorithm that pulls arms methodically, estimates the system dynamics, and then plans accordingly.

heading: 1 Introduction
text: Recommender systems suggest such diverse items as music, news, restaurants, and even job candidates. 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 observed, these systems are typically trained on the available observational data (e.g., purchases, ratings, or clicks) with the objective of predicting customer behavior [4, 27]. Problematically, such observations tend to be confounded (reflecting exposure bias due to the current recommender system) and subject to censoring (e.g., users with strong opinions are more likely to write reviews) [41, 16].
Even if we could directly observe the utility experienced by each user, we might expect it to depend, in part, on the history of past items consumed. For example, consider the task of automated (music) playlisting. As a 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 eating pizza again for dinner.
35th Conference on Neural Information Processing Systems (NeurIPS 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 [3, 6]. Research on satiation dates to the 1960s (if not earlier) with early studies addressing brand loyalty [42, 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, 17]. For a comprehensive review on hedonic decline caused by repeated exposure to a stimulus, we refer the readers to [11].
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 rewards to evolve as a function of both the per-arm characteristics (susceptibility to satiation and speed of rebounding) and the historical pulls (e.g., past recommendations). In rebounding bandits, even if the dynamics are known and deterministic, selecting the optimal sequence of T arms to play requires planning in a 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 a stochastic dynamical system.
We propose Explore-Estimate-Plan (EEP) an 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.2 and bound EEP’s regret in § 6.3.
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-seeking behavior (§4.1); (iii) an estimator (for learning the satiation dynamics) along with a sample complexity bound for identifying an affine dynamical system using a single trajectory of data (§6.2); (iv) EEP, an algorithm for learning with unknown stochastic dynamics that achieves sublinear w-step lookahead regret [34] (§6); and (v) experiments demonstrating EEP’s efficacy (§7).

heading: 2 Related Work
text: 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-seeking consumer behavior [11, 25, 26]. In operations research, addressing continuous consumption decisions, [3] propose a deterministic linear dynamical system to model satiation effects. In the recommendation systems community, researchers have used semi-Markov models to explicitly model two states: (i) sensitization—where the user is highly interested in the product; and (ii) boredom—where the user is not engaged [18].
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’s expected reward grows (or shrinks) monotonically in the number of pulls. By contrast, [19, 2, 7] propose models where rewards increase as a function of the time elapsed since the last pull. [34] model the expected reward as a function of the time since the last pull drawn from a Gaussian Process 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 expected rewards change only when it is played, and in restless bandits [44] rewards evolve independently from the play of each arm.
Key Differences This may be the first bandits paper to model evolving rewards through continuousstate 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 a 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-normalized processes [33, 1] and block martingale conditions [40].

heading: 3 Rebounding Bandits Problem Setup
text: Consider the set of K arms [K] := {1, . . . ,K} with bounded base rewards b1, . . . , bK . Given a horizon T , a policy π1:T := (π1, . . . , πT ) is a sequence of actions, where πt ∈ [K] depends on past actions and observed rewards. For any arm k ∈ [K], we denote its pull history from time 0 to T as the binary sequence uk,0:T := (uk,0, . . . , uk,T ), where uk,0 = 0 and for t ∈ [T ], uk,t = 1 if πt = k and uk,t = 0 otherwise. The subsequence of uk,0:T from t1 to t2 (including both endpoints) is denoted by uk,t1:t2 .
At time t, each arm k has a satiation level sk,t that depends on a satiation retention factor γk ∈ [0, 1), as follows
sk,t := γk(sk,t−1 + uk,t−1) + zk,t−1, ∀t > tk0 , (1)
where tk0 := mint{t : uk,t = 1} is the first time arm k is pulled and zk,t−1 is independent and identically distributed noise drawn from N (0, σ2z), 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., sk,0 = . . . = sk,tk0 = 0.
At time t ∈ [T ], if arm k is played with a current satiation level sk,t, the agent receives reward µk,t := bk − λksk,t, where bk is the base reward for arm k and λk ≥ 0 is a bounded exposure influence factor. We use satiation influence to denote the product of the exposure influence factor λk and the satiation level sk,t. In Figure 1, we show how rewards evolve in response to 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 of bk, γk, λk for which the expected reward of arm k can be negative. In the traditional bandits setup, one must pull an arm at every time step. Thus, what matters are the relative rewards and the problem is mathematically identical, regardless of whether the expected rewards range from −10 to 0 or 0 to 10. In addition, one might construct settings where negative expected rewards are reasonable. For example, when one of the arms corresponds to no recommendation with 0 being its expected reward (e.g., bk = 0, λk = 0), then the interpretation of negative expected reward would be that pulling (recommending) the corresponding arm (item) is less preferred relative to not pulling (no recommendation).
Given horizon T ≥ 1, we seek a pull sequence π1:T , where πt depends on past rewards and actions (π1, µπ1,1, . . . , πt−1, µπt−1,t−1), that maximizes the expected cumulative reward:
GT (π1:T ) := E [∑T t=1 µπt,t ] . (2)
Additional Notation Let γ := maxk∈[K] γk and λ := maxk∈[K] λk. We use a . b when a ≤ Cb for some positive constant C.

heading: 4 Planning with Known Dynamics
text: Before we can hope to learn an optimal policy with unknown stochastic dynamics, we need to establish a 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 satiation level, i.e., sk,t = γk(sk,t−1 + uk,t−1), ∀t > tk0 . With some abuse of notation, at time t ≥ 2, given a pull sequence uk,0:t−1, we can express the satiation and the expected1 reward of each arm as
sk,t(uk,0:t−1) = γk (sk,t−1 + uk,t−1) = γk (γk (sk,t−2 + uk,t−2)) + γkuk,t−1 = ∑t−1 i=1 γ t−i k uk,i,
µk,t(uk,0:t−1) = bk − λk (∑t−1 i=1 γ t−i k uk,i ) . (3)
At time t = 1, we have that sk,1(uk,0:0) = 0 and µk,1(uk,0:0) = bk for all k ∈ [K]. Since the arm parameters {λk, γk, bk}Kk=1 are known, our goal (2) simplifies to finding a pull sequence that solves the following bilinear integer program:
max uk,t  K∑ k=1 T∑ t=1 uk,t ( bk − λk t−1∑ i=0 γt−ik uk,i ) : K∑ k=1 uk,t = 1, ∀t ∈ [T ],
uk,t ∈ {0, 1}, uk,0 = 0, ∀k ∈ [K],∀t ∈ [T ]  (4) 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 uk,t leading to bilinear terms in the objective. In Appendix A, we provide an equivalent integer linear program.

heading: 4.1 The Greedy Policy
text: At each step, the greedy policy πg picks the arm with the highest instantaneous expected reward. Formally, at time t, given the pull history {uk,0:t−1}Kk=1, the greedy policy picks
πgt ∈ arg max k∈[K] µk,t(uk,0:t−1).
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, in 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 b1, satiation retention factor γ1 ∈ (0, 1), and exposure influence factor λ1 = 1. For any fixed time horizon T > 2, suppose that arm 2 has b2 = b1 + γ2−γT2 1−γ2 where γ2 ∈ (0, 1) and λ2 = 1. The greedy policy π g 1:T will keep pulling arm 2 until time T − 1 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 µ2,T (u2,0:T−1) = b1 = µ1,T (u1,0:T−1). However, the policy πn1:T , where π n t = 2 if t ≤ T − 2, πnT−1 = 1, and πnT = 2, obtains a higher expected cumulative reward. In particular, the difference GT (πn1:T )−GT (π g 1:T ) will be γ2 − γ T−1 2 .

heading: 4.2 When is Greedy Optimal?
text: When the satiation effect is always 0, e.g., when the satiation retention factors γk = 0 for all k ∈ [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 to 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 (γk, λk, bk are identical for k ∈ [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
1We 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., µk,t = bk − λksk,t + ek,t for independent mean-zero noises ek,t.
has motivated studies on satiation [42, 28]: when controlling for marketing variables (e.g., the arm parameters γk, λk, bk), researchers still observe variety-seeking behaviors of consumers (e.g., playing arms in a cyclic order).
Assumption 1. γ1 = . . . = γK = γ, λ1 = . . . = λK = λ, and b1 = . . . = bK = b.
We start with characterizing the greedy policy when Assumption 1 holds.
Lemma 1 (Greedy Policy Characterization). Under Assumption 1 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: π1 = 1, π2 = 2, · · · , πK = K, and πt+K = πt, ∀t ∈ N+. In this case, the greedy policy is equivalent to playing the arms in a cyclic order. All proofs for the paper are deferred to the Appendices.
Theorem 1. Under Assumption 1, given any horizon T , the greedy policy πg1:T is optimal.
Remark 2. Theorem 1 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 1 and Theorem 1 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 1 also gives an exact Max K-Cut of a complete graph KT on T vertices, where the edge weight connecting vertices i and j is given by e(i, j) = λγ|j−i| for i 6= j. The Max K-Cut problem partitions the vertices of a graph into K subsets P1, . . . PK , such that the sum of the edge weights connecting the subsets are maximized [10]. Mapping the Max K-Cut problem back to our original setup, each vertex represents a time step. If vertex i is assigned to subset Pk, it suggests that arm k should be played at time i. The edge weights e(i, j) = λγ|j−i| for i 6= j can be seen as the reduction in satiation influence achieved by not playing the same arm at both time i and time j. The goal (4) is to maximize the total satiation influence reduction.
Proposition 2 (Connection to Max K-Cut). Under Assumption 1, an optimal solution to (4) is given by a Max K-Cut on KT , where KT is a complete graph on T vertices with edge weights e(i, j) = λγ|j−i| for all i 6= j. Using Lemma 1 and Theorem 1, we obtain an exact Max K-Cut of KT : ∀k ∈ [K], Pk = {t ∈ [T ] : t ≡ k (mod 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 on consecutive days but require time to recover from a trip to the steakhouse) we 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 is a special case). Given a window of size w and the current satiation levels, the w-lookahead policy picks actions to maximize the total reward over the next w time steps. Let l denote dT/we. Define ti = min{iw, T} for i ∈ [l] and t0 = 0. More formally, the w-lookahead policy πw1:T is defined as follows: for any i ∈ [l], given the previously chosen arms’ corresponding pull histories {uwk,0:ti−1} K k=1 where u w k,0 = 0 and u w k,t = 1 if (and only if) πwt = k, the next w (or T mod w) actions π w ti−1+1:ti are given by
max πwti−1+1:ti
 ti∑
t=ti−1+1
µπwt ,t(uπt,0:t−1) :
uk,0:ti−1 = u w k,0:ti−1 , ∀k ∈ [K],∑K k=1 uk,t = 1, ∀t ∈ [ti], uk,t ∈ {0, 1}, ∀k ∈ [K], t ∈ [ti]  (5) In the case of a tie, one can pick any of the sequences that maximize (5). 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 (4).
Remark 3. Another reasonable lookahead policy, which requires planning ahead at every time step, would be the following: at every time t, plan for the next w actions and follow them for a single time step. To lighten the computational load, we adopt the current w-lookahead policy which only requires planning every w time steps.
For the rest of the paper, we use Lookahead({λk, γk, bk}Kk=1, {uwk,0:ti−1} K k=1, ti−1, ti) to refer to the solution of (5), when the arm parameters are {λk, γk, bk}Kk=1, the historical pull sequences of all arms till time ti−1 are given by {uwk,0:ti−1} K k=1. The solution corresponds to the actions that should be taken by the w-lookahead policy for the next ti − ti−1 time steps. Theorem 2. Given any horizon T , let π∗1:T be a solution to (4). For a fixed window size w ≤ T , we have that
GT (π ∗ 1:T )−GT (πw1:T ) ≤ λγ(1− γT−w) (1− γ)2 dT/we.
Remark 4. Note that when w = T , the w-lookahead policy by definition is the optimal policy and in such a 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 T is large since it requires solving for a much smaller program (5). In general, the w-lookahead policy is expected to perform much better than the greedy policy (which corresponds to the case of w = 1) at the expense of a higher computational cost. Finally, we note that for the window size of w = √ T , we obtain GT (π∗1:T )−GT (πw1:T ) ≤ O( √ T ).

heading: 5 Learning with Unknown Dynamics: Preliminaries
text: When the satiation dynamics are unknown and stochastic (σz > 0), the learner faces a continuousstate partially observable MDP because the satiation levels are not observable. To set the stage, we first introduce our state representation (§ 5.1) and a regret-based performance measure (§ 5.2). In the next section, we will introduce EEP, our algorithm for rebounding bandits.

heading: 5.1 State Representation
text: Following [32], at any time t ∈ [T ], we define a state vector xt in the state space X to be xt = (x1,t, n1,t, x2,t, n2,t, . . . , xK,t, nK,t), where nk,t ∈ N is the number of steps at time t since arm k was last selected and xk,t is the satiation influence (product of λk and the satiation level) as of the most recent pull of arm k. Since the most recent pull happens at t − nk,t, we have xk,t = bk − µk,t−nk,t = λksk,t−nk,t . Recall that µk,t−nk,t is the reward collected by pulling arm k at time t − nk,t. Note that bk is directly observed when arm k is pulled for the first time because there is no satiation effect. The state at the first time step is x1 = (0, . . . , 0). At time t, if arm k is chosen at state xt, and reward µk,t is obtained, then the next state xt+1 will satisfy (i) for the pulled arm k, nk,t+1 = 1 and xk,t+1 = bk − µk,t; (ii) for other arms k′ 6= k, nk′,t+1 = nk′,t + 1 if nk′,t 6= 0, nk′,t+1 = 0 if nk′,t = 0, and the satiation influence remains the same xk′,t+1 = xk′,t.
Given {γk, λk, bk}Kk=1, the reward function r : X × [K] → R represents the expected reward of pulling arm k under state xt:
If nk,t = 0, then r(xt, k) = bk. If nk,t ≥ 1, r(xt, k) = E[µk,t|xt] = bk − γ nk,t k xk,t − λkγ nk,t k , where the expectation is taken over the noises in between the current pull and the last pull of arm k. See Appendix C.1 for the full description of the MDP setup (including the transition kernel and value function definition) 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 [31, 15], regrets are defined in terms of episodes. In such cases, the initial state is reset (e.g., to a fixed 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 dT/we episodes where each episode (besides the last) consists of w 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 t = iw + 1), given that the learner has played π1:iw with corresponding pull sequence uk,0:iw for k ∈ [K], we reset the initial state to be xi = (µ1,iw+1(u1,0:iw), n1,iw+1, . . . , µK,iw+1(uK,0:iw), nK,iw+1) where µk,t(·) is defined in (3) and nk,iw+1 is the number of steps since arm k is last pulled by the learner as of time iw + 1.
Then, given the learner’s policy π1:T , where πt : X → [K], the w-step lookahead regret, against a competitor class Cw (which we define later), is defined as follows:
Regw(T ) = ∑dT/we−1 i=0 maxπ̃1:w∈Cw E [∑min{w,T−iw} j=1 r(xiw+j , π̃j(xiw+j)) ∣∣∣xiw+1 = xi] − E [∑min{w,T−iw} j=1 r(xiw+j , πiw+j(xiw+j))
∣∣∣xiw+1 = xi] , (6) where the expectation is taken over xiw+2, . . . , xmin{(i+1)w,T}.
The competitor class Cw that we have chosen consists of policies that depend on time steps, i.e., Cw = {π̃1:w : π̃t = π̃t(xt) = π̃t(x′t), π̃t ∈ [K],∀t ∈ [w], xt, x′t ∈ X} . We note that Cw 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 a time-dependent policy that belongs to Cw, since at time t, it will play a fixed action by solving (5) using the true reward parameters {λk, γk, bk}Kk=1. The time-dependent competitor class Cw differs from a state-dependent competitor class which includes all measurable functions π̃t that map from X to [K]. The state-dependent competitor class contains the optimal policy π∗ where π∗t (xt) depends on not just the time step but also the exact state xt. Finding the optimal state-dependent policy requires optimal planning for a continuous-state MDP, which relies on state space discretizion [31] 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 Cw defined above. When w = 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.e., 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 w steps ahead but any given policy. For a more comprehensive discussion on these notions of regret, see [34, Section 4].

heading: 6 Explore-Estimate-Plan
text: We now present Explore-Estimate-Plan (EEP), an algorithm for learning in rebounding bandits with 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, we analyze EEP’s regret.
Because each arm’s base reward is known from the first pull, whenever arm k is pulled at time t and nk,t 6= 0, we measure the satiation influence λksk,t, which becomes the next state xk,t+1:
xk,t+1 = λksk,t = λkγ nk,t k sk,t−nk,t + λkγ nk,t k + λk ∑nk,t−1 i=0 γ i kzk,t−1−i
= γ nk,t k xk,t+1−nk,t + λkγ nk,t k + λk ∑nk,t−1 i=0 γ i kzk,t−1−i. (7)
We note that the current state xk,t equals xk,t+1−nk,t , since xk,t+1−nk,t is the last observed satiation influence for arm k and nk,t is the number of steps since arm k was last pulled.

heading: 6.1 The Exploration Phase: Repeated Pulls
text: We collect a dataset Pnk by consecutively pulling each arm n+1 times, in turn, where n ≥ bT 2/3/Kc (Line 4-7 of Algorithm 1). Specifically, for each arm k ∈ [K], the dataset Pnk contains a single trajectory of n+1 observed satiation influences x̃k,1, . . . , x̃k,n+1, where x̃k,1 = 0 and x̃k,j (j > 1) is the difference between the first reward and the j-th reward from arm k. Thus, for x̃k,j , x̃k,j+1 ∈ Pnk , using (7) with nk,t = 1 (because pulls are consecutive), it follows that
x̃k,j+1 = γkx̃k,j + dk + z̃k,j , (8)
where dk = λkγk and z̃k,j are independent samples from N (0, σ2z,k) with σ2z,k = λ2kσ2z . In Appendix E.2, we discuss other exploration strategies (e.g., playing the arms in a cyclic order) for EEP and their regret guarantees.
Algorithm 1: w-lookahead Explore-Estimate-Plan Input: Lookahead window size w, Number of arms K, Horizon T
1 Initialize t = 1, π1:T to be an empty array of length T and T̃ = T 2/3 + w − (T 2/3 mod w). 2 for k = 1, . . . ,K do 3 Set t′ = t and initialize an empty array Pnk . 4 for c = 0, . . . , bT̃ /Kc do 5 Play arm k to obtain reward µk,t′+c and add µk,t′ − µk,t′+c to Pnk . 6 Set πt = k and increase t by 1. 7 end 8 Obtain γ̂k, d̂k using the estimator (9),set λ̂k = |d̂k/γ̂k| and b̂k = µk,t′ . 9 end
10 Let t0 = T̃ , set πt:t0 = (1, . . . , T̃ − t+ 1), and play πt:t0 . 11 for i = 1, . . . , dT−t0w e do 12 Set ti = min{ti−1 + w, T}. 13 Obtain πti−1+1:ti = Lookahead({λ̂k, γ̂k, b̂k}Kk=1, {uk,0:ti−1}Kk=1, ti−1, ti) where {uk,0:ti−1}Kk=1 are the arm pull histories correspond to π1:ti−1 . 14 Play πti−1+1,ti . 15 end

heading: 6.2 Estimating the Reward Model and Satiation Dynamics
text: For all k ∈ [K], given the dataset Pnk , we estimate Ak = (γk, dk)> using the ordinary least squares estimator:
Âk ∈ arg min A∈R2 ‖Yk −XkA‖22, (9)
where Yk ∈ Rn is an n-dimensional vector whose j-th entry is x̃k,j+1 and Xk ∈ Rn×2 takes as its j-th row the vector xk,j = (x̃k,j , 1)>, i.e., x̃k,j+1 is treated to be the response to the covariates xk,j . For n ≥ 2, we have that
Âk = ( γ̂k d̂k ) = ( Xk > Xk )−1 Xk > Yk, (10)
and we take λ̂k = |d̂k/γ̂k|. 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 in the control theory and time series communities [13, 22]. Recent work on system identifications for linear dynamical systems focuses on the sample complexity [40, 38]. Adapting the proof of [40, Theorem 2.4], we derive the following theorem for identifying our affine dynamical system (8).
Theorem 3. Fix δ ∈ (0, 1). For all k ∈ [K], there exists a constant n0(δ, k) such that if the dataset Pnk satisfies n ≥ n0(δ, k), then
P ( ‖Âk −Ak‖2 & √ 1/(ψn) ) ≤ δ,
where ψ = √ min {
σ2z,k(1−γk)2
16d2k(1−γ 2 k)+(1−γk)2σ 2 z,k , σ2z,k 4(1−γ2k)
} .
As shown in Theorem 3, when dk = λkγk gets larger, the convergence rate for Âk gets slower. Given a single trajectory of sufficient length, we obtain |γ̂k − γk| ≤ O(1/ √ n) and |d̂k − dk| ≤ O(1/ √ n).
In Corollary 4, we show that the estimator of λk also achieves O(1/ √ n) estimation error. Corollary 4. Fix δ ∈ (0, 1). Suppose that for all k ∈ [K], we have P(‖Âk − Ak‖2 & 1/ √ n) ≤ δ and γ̂k > 0. Then, with probability 1− δ, we have that for all k ∈ [K],
|γ̂k − γk| ≤ O (
1√ n
) , |λ̂k − λk| ≤ O ( 1√ n ) .

heading: 6.3 Planning and Regret Bound
text: In the planning stage of Algorithm 1 (Line 11-15), at time ti−1 + 1, the next w arms to play are 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, we obtain the following sublinear regret bound for w-lookahead EEP.
Theorem 5. There exists a constant T0 such that for all T > T0 andw ≤ T 2/3, thew-step lookahead regret of w-lookahead Explore-Estimate-Plan satisfies
Regw(T ) ≤ O(K1/2T 2/3 log T ).
Remark 5. The fact that EEP incurs a regret of order O(T 2/3) is expected for two reasons: First, EEP can be viewed as an explore-then-commit (ETC) algorithm that first explores then exploits. The regret of EEP resembles the O(T 2/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 to 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 instantaneous regret has a lower bound Ω(T 2/3). On the other hand, in the traditionalK-armed bandits setup, the regret (following the classical definition [20]) is lower bounded by Ω(T 1/2), and can be attained by methods like the upper confidence bound algorithm [20]. Precisely characterizing the regret lower bound for rebounding bandits is of future interest.

heading: 7 Experiments
text: We now evaluate the performance of EEP experimentally, separately investigating the sample efficiency of our proposed estimators (10) for learning the satiation and reward models (Figure 2) and the computational performance of the w-lookahead policies (5) (Figure 3a). For the experimental setup, we have 5 arms with satiation retention factors γ1 = γ2 = .5, γ3 = .6, γ4 = .7, γ5 = .8, exposure influence factors λ1 = 1, λ2 = λ3 = 3, λ4 = λ5 = 2, base rewards b1 = 2, b2 = 3, b3 = 4, b4 = 2, b5 = 10, and noise with variance σz = 0.1.
Parameter Estimation We first evaluate our proposed estimator for using a single trajectory per arm to estimate the arm parameters γk, λk. In Figure 2, 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/2).
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 3a). Recall that the greedy policy is precisely the 1-lookahead policy. In order to solve the resulting integer programs, we use Gurobi 9.1 [23] 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 3a) solved through (4) is obtained in 1610s. On the other hand, all w-lookahead 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 w = 2, 5, 8, 10. All results are averaged over 20 random runs. As T 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’s legend) are close to 2/3, which aligns with our theoretical guarantees (Theorem 5), i.e., the regrets are on the order of O(T 2/3). In Appendix G, we present the T -step lookahead regret of w-lookahead EEP under the same settings, and additional experimental setups and results.

heading: 8 Conclusions
text: While our work has taken strides towards modeling the exposure-dependent evolution of preferences through dynamical systems, there are many avenues for future work. First, while our satiation dynamics are independent across arms, a natural extension might allow interactions among the arms. For example, a diner sick of pizza after too many trips to Di Fara’s, likely would also avoid Grimaldi’s until the satiation effect wore off. On the system identification side, we might overcome our reliance on evenly spaced pulls, producing more adaptive algorithms (e.g., optimism-based algorithms) that can 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 to 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.

heading: Acknowledgement
text: LL is generously supported by an 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 to 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.

Review summaries:
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).  The 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.   

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. 

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.

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.