Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a stochastic multi-armed bandit setting with delayed feedback, where additionally, the bandit policy must incentivize an external agent to pull the desired arm, and the arm preferences of this external agent are self-reinforcing. They design a policy, UCB-FDF, for this setting, and prove expected regret (and incentive payment) upper bounds under various delay distribution assumptions. Finally, they evaluate their policy on bandit environments constructed using Amazon review data.

main_review: While I find the problem setting to be intriguing, I have a number of concerns about the writing, proof techniques, and regret upper bounds. I will outline these concerns below:

**Discussion of related work**:

It seems to me that there are a number of typos in the related work discussing Bandits with Delayed Feedback. In particular, I was confused by the claim that Joulani et al. (2013) proves a regret bound of $O(\sqrt{K T \log T + K \mathbb{E}[\tau]})$, where $\tau$ is the delay. Indeed, this upper bound is false when $\tau = T$, since the regret necessarily is linear in this regime. However, Theorem 6 from that paper does indeed show a proper scaling in this regime. I would encourage the authors to clarify this subtlety somehow.

I was also confused by the regret lower bound citation in delayed feedback from Vernade et al. (2017). Indeed, a scaling of $\Omega(K\log(T))$ follows from the standard bandit setting. Perhaps you should clarify this?

Also, I was confused by the line “... where only an upper bound on the tail of the delay distribution is needed, without requiring the expectation to be finite.” Perhaps you should clarify that only a _polynomial_ upper bound on the tail of the delay distribution is needed here.

**Regret modeling and payments**:

It is not clear to me how the payments made by the bandit policy affect the performance of the algorithm in your model. Indeed, the regret is measured against a policy which makes an infinite payment to the best arm. Does this mean that the algorithm is also allowed to make unbounded payments and “no cost” to performance? If, instead, we measure regret with respect to a policy which can only make some bounded number of payments, how does the regret change? Perhaps there is some meaningful notion of “payment regret” that measures the excess number of payments over the genie policy?

**Algorithm naming**:

(Minor comment) Although your algorithm is called UCB-..., it seems to not actually be a UCB-style policy, as the exploration and exploitation phases are distinct (unless I am misreading something?). It seems this algorithm is more of an Elimination-style algorithm? Perhaps you could consider changing the name to reflect this.

**Technical concerns**:

I am confused by the claimed regret scaling in Lemma 1 and Theorem 3. Indeed, both bounds seem to have a scaling term on the order of $\Delta^* \cdot \mathbb{E}[D^*(T)]$. However, consider an environment where $\Delta^* = 1/\sqrt{T}$ (e.g., the standard minimax regret lower bound environment), and suppose that all delays are deterministically $T$, so that $D^*(T)=T$ a.s. Then, it seems that your Lemma and Theorem would give a regret upper bound of $O(\sqrt{T})$ in this case. However, it is clear that regret must be linear, since the policy never receives any rewards. Am I missing something? I do not see how the claimed scaling can be true.

In trying to understand where this scaling term comes from, I began reading the proof of Lemma 1. It seems that there is an issue in the inequality of (7) on page 13. Indeed, this inequality does not type-match, since the left-hand side is a deterministic quantity (just the probability of some event), but the right-hand side is random, as it depends on $T_a(t)$, $D_a(t)$, and $c_a(t)$. Note that there is a similar issue in equation (10). It seems that this analysis introduces the scaling term that does not make sense to me (discussed in the previous paragraph). Thus, I suspect that fixing this bug will change the reported regret scaling.

**Empirical results**:

I suggest that the authors consider adding at least some simple baseline to their experimental results. For example, you may consider adding a UCB baseline, to demonstrate that policies that ignore the incentive structure should achieve poor regret scaling. Additionally, it would be nice to include error bars in the plots.

----

_Post-author response_: Please refer to my response to the authors. I think that most of my main concerns have now been addressed.

summary_of_the_review: Although the problem setting is interesting, there are a number of concerns I have with the writing and technical results/proofs of the paper (see above for details). Since I do not think these concerns can be sufficiently addressed during the rebuttal, I do not think that this paper is ready for publication.

----

_Post-author response_: Please refer to my response to the authors. I have changed my opinion of the technical concerns, and the remaining ones seem minor. The authors have given a satisfactory response, and I have increased my score accordingly. I would still like to see the concerns mentioned in my responses addressed before publication, however.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper combines three aspects of MAB: delayed reward, incentivized exploration and self-reinforcing user preference. They motivate this problem from the perspective of online recommender systems. For this model, they propose a new UCB based algorithm that achieves the optimal upper bounds. They also setup an online experiment based on Amazon review data and show how the regret evolves for both arm-independent delays and arm-dependent delays.
main_review: Strengths of the paper are as follows.

+ The paper considers a practical scenario where recommender systems face. Prior works considers only one of the aspects: delayed rewards, incentivizing exploration. This paper combines them to study the joint effects.

+ The paper is well-written with a meaningful experimental section where they empirically compare the incentive costs with regret.

+ The algorithm is realistic in terms of practical implementation.

The main weakness of this paper is as follows

- My main complain on the paper is primarily around positioning. In particular, it is not entirely clear to me what the main challenge for the new model is that do not exist in either the delayed reward MAB or the incentivized exploration lines of work. A discussion around that and why adapting the algorithm for incentivized exploration to handle delayed reward would not work? In particular, delayed rewards for an UCB type algorithm should not pose a whole lot of difficulties; so I am wondering why a new algorithm design is needed. Compaing and contrasting the current algorithm to prior works will greatly help the reader.
summary_of_the_review: As above I am supportive of this paper and line of work. I would like to better understand the challenges which will help me appreciate the results better. Thus, I would like the authors to address that.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers a MAB framework with joint effect of incentivized sampling, delayed sampling feedback, and self-reinforcing user preferences. The framework considers delayed feedbacks to reflect a more practical setting where customer preferences among products are influenced and reinforced by historical feedbacks.
main_review: Major comments:

1.	This paper is largely motivated by Zhou et al. 2021, which incorporated self-reinforcing user preferences into the incentivized bandit learning framework. The key difference is that this work considers the delay effect. That is, the accumulative award information accounts for reward information that can only be observed up to time t, while Zhou et al. 2021 can observe the feedback immediately. Could you elaborate more on the technical difficulty when you consider the delay effect, compared to the work Zhou et al. 2021?

2.	In bandits with delayed feedback [Pike-Burke et al. 2018], their Theorem 2 illustrates that the regret bound has an additional term log(1/\Delta_j) E[\tau], which does not depend on T. However, in your Theorem 3, it has an additional term \sqrt{4 E[\tau_1] ln T}, which has the dependence on T. Why is that? Can it be improved? Could you derive the lower bound and close the gap on the dependence of the delay period?

3.	In Assumption 1, it assumes that the delays of arm a follows an independent delay sequence {\tau_{a,t}}, where each element is a random variable satisfying \tau_{a,t}~T_a. Can the result be generalized to the setting where \tau_a,t follow different distributions when t varies?

4.	Why only the term g(b,1) shows up in the regret bound but not g(b,t) for t>1?

5.	Regarding the numerical experiments, how do you choose the self-reinforcing preference function f(x) and the incentive impact function g(b,t)? In addition, can you compare the regret between the setting with delay effect and that without the delay effect, and different delay distributions, through which to illustrate the influence of the delayed feedback?

summary_of_the_review: The problem this paper studied is defined in a clear way, but authors may need to emphasize the technical contribution that is built upon the existing work and demonstrate the tightness of the regret bound.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a multi-armed bandit (MAB) framework with three realistic considerations: incentivized sampling, delayed feedback and self-reinforcing preferences. The paper proposes a ‘UCB-Filtering-with-Delayed-Feedback’ (UCB-FDF) policy for the new MAB framework. For general feedback delays with bounded expectations, the authors showed that the delayed sampling feedback has additive penalty on regret and incentive costs, then utilized this key fact to derive that the UCB-FDF policy achieves logarithmic regret and incentive cost in the new MAB framework. The theoretical bounds are verified by experiments on instances with 3 arms using Amazon Review Data.
main_review: Pros: 
1.	The motivation for introducing the three factors is explained very clearly. The description of Algorithm 1 and the intuition behind each step in the policy are also well-written.
2.	The comparisons with related works given in Section 2 are helpful.
3.	The theoretical results, to my understanding, are derived under fairly general assumptions. The distinctions between arm-independent versus arm-dependent delays are useful to see.

Cons: 
1.	The experiment evaluation is insufficient in my opinion. In terms of verifying the provided regret bounds, I find the presented experimental results somewhat narrow. Given that the derived bounds contain many problem-specific parameters, such as arm number $K$, delay expectation $E[D*(T)]$, I think additional experiments with different setups would strengthen the empirical results. For example, would it be possible to replace the normal delay distributions with other distributions? What the results would look like at different self-reinforcing preference function and incentive impact function?
Additionally, I would expect the experiments to provide some empirical evidence for the benefits of considering these additional factors. For example, have the authors considered experiment comparisons between UCB-FDF on the new MAB framework versus a policy on the standard stochastic MAB framework?
2.	I briefly checked Zhou et al. 2021, which already considered two out of the three new factors. To my understanding, the main contribution from this paper is the additional factor of delayed feedback in the MAB framework. While I agree with the argued usefulness of allowing feedback delays, I am not sure how much novelty, or what are the new ideas needed, in the design of the UCB-FDF policy and the theoretical analysis. Please correct me if I were wrong: it appears that Algorithm 1 differs with Policy 2 in Zhou et al. 2021 only in the ‘Exploitation phase’ to include delay $D_a(t)$ into the dominance criterion. Is it the obvious choice, or is there more sophisticated argument underneath? 
 
Some minor suggestions: 
1.	The mathematical formalization for self-reinforcing preference is a little difficult to find in the paper.
2.	I believe $\Theta()$ is never formally defined in the paper. This may be a standard expression, but I think giving its definition would still be helpful.
3.	Would it be possible to mark $t_1, t_2$ to indicate the lengths of each phase when plotting the experiment results over the selected time horizon $T$?

Questions during rebuttal period: 
Please address and clarify the cons above. In particular, could the authors highlight what are the theoretical novelty of the proposed framework, policy and theoretical bound derivations, in comparison to the cited works? 

summary_of_the_review: I vote for 6: marginally above the acceptance threshold. The paper undertakes the ambitious goal of incorporating the joint effects of three new factors into a more realistic MAB framework. The proposed UCB-FDF policy is shown to achieve desirable logarithmic regrets without excessive incentive spending, and the theoretical results can apply to quite general delay distributions. Although I think the paper is well-written and the results are useful, I find the current version lacking in two main aspects. First, the experiments are limited: in addition to verifying the theoretical bounds, the experiments could also provide more insights about the UCB-FDF policy and/or compare with alternative MAB frameworks to demonstrate the advantages of incorporating the new factors. Second, the technical novelty and significance should be highlighted in a more clear way.
review_title: null

Meta-review: This paper tackles a bandit problem that incorporates three challenges motivated by common issues encountered in online recommender systems: delayed reward, incentivized exploration, and self-reinforcing user preference. The authors propose an approach called UCB-Filtering-with-Delayed-Feedback (UCB-FDF) for this problem and provide a theoretical analysis showing that UCB-FDF achieves the optimal regret bounds. Their analysis also implies that logarithmic regret and incentive cost growth rates are achievable under this setting. These theoretical results are supported by empirical experiments, e.g. using Amazon review data. The main concern with this paper is that the considered challenges have all been tackled already in different bandit settings, so the novelty here is that they are being tackled altogether. It would be more convincing if experiments included baselines from these existing settings to motivate the need for a new strategy rather than simply relying on methods that have been proposed previously to address each of these problems independently; the experiments currently contain only a baseline for bandits with self-reinforcing user preference, which has been added during the rebuttal phase.
Decision: Accept (Poster)