Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).

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.  

main_review: Strengths/Positives:

1. 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. 

2. 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.  

3. 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. 

Weaknesses/Questions/Negatives:

1. 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. 
2. 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). 
3. 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? 
4. 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. 
5. Experiments section seems a little weak: 

a) 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. 

b) 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).

c) 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?  

d) Part of Fig 2 is hard to read because of the legends. Having legends outside of the chart would be great.   


Other comments:

1. Line 58: Point (iv) is hard to understand, without reading the rest of the paper. 
2. Typos: Line 143: “to to”

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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

main_review: In general, the paper is well written and I enjoy reading the paper. I have the following main comments:

1. 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?

2. 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.

3. 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.

4. 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.

5. It would help to show the empirical computational cost for different values of w in the numerical section.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.
limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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?
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_title: null

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)