Bandit Learning with Joint Effect of Incentivized Sampling, Delayed Sampling Feedback, and Self-Reinforcing User Preferences
Authors: Tianchen Zhou
Jia Liu
Chaosheng Dong
Yi Sun
Venue: ICLR 2022 Poster (2022)

Abstract: In this paper, we consider a new multi-armed bandit (MAB) framework motivated by three common complications in online recommender systems in practice: (i) the platform (learning agent) cannot sample an intended product directly and has to incentivize customers to select this product (e.g., promotions and coupons); (ii) customer feedbacks are often received later than their selection times; and (iii) customer preferences among products are influenced and reinforced by historical feedbacks. From the platform's perspective, the goal of the MAB framework is to maximize total reward without incurring excessive incentive costs. A major challenge of this MAB framework is that the loss of information caused by feedback delay complicates both user preference evolution and arm incentivizing decisions, both of which are already highly non-trivial even by themselves. Toward this end, we first propose a policy called ``UCB-Filtering-with-Delayed-Feedback'' (UCB-FDF) policy for this new MAB framework. In our analysis, we consider delayed feedbacks that can have either arm-independent or arm-dependent distributions. In both cases, we allow unbounded support for the random delays, i.e., the random delay can be infinite. We show that the delay impacts in both cases can still be upper bounded by an additive penalty on both the regret and total incentive costs. This further implies that logarithmic regret and incentive cost growth rates are achievable under this new MAB framework. Experimental results corroborate our theoretical analysis on both regret and incentive costs.


Published as a conference paper at ICLR 2022
BANDIT LEARNING WITH JOINT EFFECT OF INCEN- TIVIZED SAMPLING, DELAYED SAMPLING FEEDBACK, AND SELF-REINFORCING USER PREFERENCES
Tianchen Zhou', Jia Liu', Chaosheng Dong", Yi Sun"
! "Department of Electrical and Computer Engineering, The Ohio State University
2 "Amazon, Seattle, Washington, USA zhou. 22200osu.edu, liuêece. osu. edu, {chaosd, yisun)@amazon.com
ABSTRACT
In this paper, we consider new multi-armed bandit (MAB) framework motivated
by three common complications in online recommender systems in practice: (i)
the platform (learning agent) cannot sample an intended product directly and has to incentivize customers to select this product (c.g.. promotions and coupons); (ii) customer feedbacks are often received later than their selection times; and (iii) customer preferences among products are influenced and reinforced by historical feedbacks. From the platform's 's perspective, the goal of the MAB framework maximize total reward without incurring excessive incentive costs. A major chal- lenge of this MAB framework is that the loss of information caused by feedback delay complicates both user preference evolution and arm incentivizing decisions, both of which are already highly non-trive non-trivial even by themselves. Toward this end, we first propose policy called JUCB-Filtering with Delayed-Feedbaee FDF) policy for this new MAB framework. In our analysis, we consider delayed feedbacks that can have either arm-independent In both cases, we allow unbounded support for the random delays, i.e., the ran- dom delay can be infinite. We show that the delay impacts in both cases can still be upper bounded by an additive penalty on both the regret and total incentive costs. This further implies that logarithmic regret and incentive cost growth rates are achievable under this new MAB framework. Experimental results corroborate our theoretical analysis on both regret and incentive costs.
(UCB-
arm-dependent distributions.
INTRODUCTION
In recent years, the multi-armed bandit (MAB) framework has received a significant amount of interest in the learning research community. This is partly due to the fact that, in many online commerce recommender systems (c.g., Amazon and Walmart), the problem of online learning of the optimal products while making profits at the same time be well formulated by MAB problem. However, although many MAB algorithms have been proposed in this area, it is worth noting that most of the existing MAB models in the literature have not considered the joint effect of three common phenomena in e-commerce recommender systems: (i) In many e-commerce recommender systems, the platform (the learning agent) cannot sample an intended product (an intended arm) directly and has to incentivize customers (e.g., through promotions and coupons) to sample the product and receive the sampling feedback from the customers indirectly (e.g., ratings and reviews); (ii) Customer feedbacks are often received much later than their purchasing times (e.g.. a review may or may not be submitted by a customer even months later after purchasing a product); and (iii) Customer preferences among products are influenced and reinforced by historical feedbacks, which may even lead to various viral effects over some products (the more good reviews one product has received, the more likely that the next arriving customer will prefer this product). The lack of fundamental understanding and joint studies of these three important factors in MAB policy designs motivates us fill this gap in this paper.
Toward this end, we propose a new MAB framework that jointly considers i) incentivized sampling, ii) delayed sampling feedback, and iii) self-reinforcing user preferences in online recommender sys-

---

Published as a conference paper at ICLR 2022
tems. However, we note that the MAB policy design for the proposed new MAB framework is highly non-trivial due to the complex couplings between the aforementioned three factors. First, similar to conventional MAB problems, there exists dilemma between sufficient exploration through sam- pling to learn an optimal arm (i.e., an optimal product), which may incur numerous pullings of sub-optimal arms, and the greedy exploitation to play the arm that has performed well thus far to earn profits. Second, there is another dilemma to the learning agent between offering sufficiently attractive incentives mitigate biases (due to lack of initial data and self-reinforeing user prefer- ences) and avoid spending unnecessarily high incentives that hurt the learning agent's ss profits. Last but not least, the delayed sampling feedbacks may render the estimation of arms' quality during the MAB process highly inaccurate, introducing yet another layer of uncertainty to the MAB on- line learning problem, which is already plagued by complications from incentivized sampling and self-reinforcing user preferences. As in most MAB problems, we adopt "regret" as our performance metric in this paper, which is defined as the cumulative reward gap between the proposed policy and an optimal policy design in hindsight. Under the regret setting. the complications due to these three key factors naturally prompt the following fundamental questions:
(1) How should the agent design an incentivizing strategy to strike a good balance between explo- ration and exploitation to achieve sublinear (hopefully logarithmic) regrets?
(2) To avoid offering exceedingly high incentives, how should the agent incentivize in order to attract a user crowd that prefer an optimal arm, so that the users' self-reinforcing preference could automatically gravitate toward this optimal arm without further incentives?
(3) Under various delayed feedback situations in the new MAB framework (e.g., unbounded ran- dom delays, heavy-tailed delay distributions, and arm-dependent delays), could we still achieve low regrets with low incentive costs?
In this paper, we answer the above fundamental questions affirmatively by proposing a new "Delayed-UCC FCBllleriiiilleei policy for the MAB framework that jointly considers incentivizing sam- pling, delayed sampling feedback, and self-reinforcing user preferences. We show that our proposed policy achieves (log T') regret with O(log 7') incentive payments. The success of our policy design hinges upon two key insights: (i) the self-reinforcing user preference effect is actually a "blessing in disguise" and can be leveraged to establish an important "dominance" condition (more on this later) that further implies Olog T') regret and incentive costs; and (ii) the impacts of delayed feedback on regret and incentive costs can be upper bounded under appropriate statistical settings to preserve the "dominance" condition. Our key contributions and main results are summarized follows:
We propose a new MAB model that jointly considers incentivized arm sampling, delayed sam- pling feedback, and self-reinforcing user preferences, all of which are important features of online recommender systems. To develop efficient and low-cost incentivized policy for this new MAB model, we propose a three-phase JJCB-Filtering with-Delayed Delayee--Feddaaack FFeddback" (UCB-FDF) policy, which contains incentivized exploration phase, incentivized exploitation phase, and a self- sustaining phase. In our UCB-FDF policy, the first two phases judiciously integrate delayed feedback information, while in third phase, the system solely relies on self-reinforcing user pref- erences to converge to the pulling of the optimal arm.
We first show fundamental fact that, under our UCB-FDF policy, delayed sampling feedback only has an additive penalty on the regret and incentive cost performances, and that this additive penalty grows logarithmically with respect to time. Specifically, we first investigate the delayed feedback impact under the assumption that the feedback delay is an i.i.d. random variable across samplings with finite expectation. We show that the UCB-FDF policy achieves logarithmic growth rates of regret and incentive costs under this setting. Then, we relax the i.i.d. feedback delay assumption to allow the feedback delay distribution be arm-dependent. Under this setting, also show that similar logarithmic growth rates of regret and incentive can still be achieved.
We conduct extensive experiments on Amazon Review Data to demonstrate and verify the per- formance of our UCB-FDF policy as well as the impacts of delayed feedback real-world sce- narios. We also verify our theoretical analysis through various product categories and demonstrate the efficacy of our proposed UCB-FDF MAB policy.
The rest of the paper is organized as follows. In Section 2 we review the literature to put our work in comparative perspectives. In Section 3 we formulate our new MAB model that captures the three common phenomena. In Section 4 we present our UCB-FDF policy and analyze its performance.
2

---

Published as a conference paper at ICLR 2022
Then, we present experiment settings and results in Section 5 proofs and part of experiemntal results are relegated to the appendix.
Due to space limitations, the
2 RELATED WORK
In this section, we provide quick overview on three lines of research related to our work: i) bandits with delayed feedback, ii) bandits with random preferences, and iii) incentivized bandits.
Motivated by practical issues in the clinical trials, [Eik (9888) was the first to introduce a two-armed bandit model with delayed responses, where the patients' survival time reports after the treatment are delayed. Recently, Joulani et al. (2013) provided sys- tematic study and showed that for delay T with a finite expectation, the worst case regret scales with O(vKT TogT T + [T](r)) where K is the number of arms. Meanwhile, Vernade et al. (017)) showed that stochastic MAB problems with delayed feedback have a regret lower bound OTK log')) How- ever, this work assumed that the distribution of the random delay is arm-independent. In contrast, Joulani et al. (2013) considered arm-dependent delay distributions that have an upper bound of the maximum random delay. More recently. Manegueu
1) Bandits with Delayed Feedback:
al. (2020) considered arm-dependent and heavy-tailed delay distributions, where only an upper bound on the tail of the delay distribution is needed, without requiring the expectation to be finite. Also, [ancewicki et al. (202T) studied the case where the delay distribution is reward reward-dependent, which implies that the random delay in each round may also depend on the reward received on the same round. However, most of these works on delayed bandits are based on the standard stochastic MAB framework. In contrast, we consider delayed feedback in incentivized bandit learning with self-reinforcing user preferences, which is a more appropriate model for real-world recommender systems than the standard stochastic MAB.
2) Bandits with Random Preferences: The impacts of random user preferences in e-commerce platforms have received increasing interest in several different areas in learning and economies. Ex- isting works in (Agrawal et al.) 2017 2019) formulated the user preference variation given different product bundles by the multi-nomia logit model on top of the bandit learning framework and pro- posed Thompson Sampling approach that achieves worst-case regret bound of O(VNT log TK). where N is the size of recommended arm bundle. With a different focus on preference modeling, Barabási & Albert (199)): CChakrabarti et al. Ratkiewict et al. (2010) investigated the net- work evolution with "preferential attachment" that formulates the social behavior known as self- reinforeing preferences, among which the works in (Shah et al. 2018 Zhou al. 202T) are the closet to our work. To our knowledge, [haah et al. (2018) was the first to consider self self-reinforcing user preferences in bandit learning problems. Later, Zhou et al. (202T) incorporated self-reinforcing user preferences into the incentivized bandit learning framework. The key difference between these two works that, in the model (Shah et al.) 2018)), only one arm revealed to users each round, while in the model in (Zhou et al.) 2021), all arms revealed to users and users' arm selections influenced by incentives. However, both of these works fall short in modeling online recommender systems in practice they assume that an arm-sampling feedback is observable in the same time- slot when an arm is pulled. However, for most e-commerce recommender systems in practice user feedbacks are often not immediately observable. As a result, the decision on which arm to pull next has to be made without some of the feedbacks from arm-pulling actions in the past.
To our knowledge, Frazier al. (2014) among the first adopt incentive schemes into a Bayesian MAB setting. In their model, the agent seeks to maximize time- discounted total reward by incentivizing arm selections. Later, Mansour et al. (2015) studied the non-discounted reward setting. For the non -on-BByesian setting. [Wang & Huang (2018); Zhou et al. (202)) proposed policies that maximize the total non-discounted reward with bounded incentive costs. Bandits with budget (Guha & Munagala [007]] Goel et al. (209) also share some similarities with our work, where the agent takes actions under resource constraints that are either fixed or with a given growth rate bound. However, none of the aforementioned works considered the impacts of delayed feedback on the regret and incentive costs performances. Note that, due to the loss of information caused by delayed feedback. larger variances in the mean-reward estimations of the arms are inevitable. This implies that, in order to achieve a more accurate arm quality estimation under delayed feedbacks, higher incentive cost is necessary.
3) Incentivized Bandits:
3

---

Published as a conference paper at ICLR 2022
3 SYSTEM MODEL
The system has a set of K 2 2 arms denoted by A = {l...., K} and each arm a follows a Bernoulli reward distribution Pa with an unknown mean ja O. The bandit time horizon has T rounds. In each time step = 1, ..2.....77 T, a user arrives and chooses an arm I to pull. Then, the user will receive random reward feedback X, ~ Pt. Both the arm selection I, and the feedback X₁ are observable to the agent. We use (t) _ Ei= [(,==a) to denote the number of times that arm a is pulled up to time step t. We let (0) 0, Va A. We assume that there is a unique best arm a E in the sense that a" arg m Ma and let μr" = Pe Also, we define D. _ " Pe as the gap between the mean of the optimal arm and the mean of arm a.
3.1 DELAYED FEEDBACK MODELING
In this paper, we consider delayed feedback, i.e., when an arm I, is pulled time step t. the corre- sponding Bernoulli reward X, is observed after a delay period Tr, i.e., the feedback X, is observed at time step L + TI..-- Without loss of generality, we model the random delay time as a random vari- able Ta, Ta where the delay distribution Ta of arm is unknown to the agent.
We consider two settings of delayed feedback. We first consider i..d, delays (TiES across time and arms, i.c., the delay distributions are identical for all arms. Thus, we omit the arm index in the notations of delay feedback in this setting. Next, we generalize the delay modeling by allowing arm-dependent delay distributions, where the delay distributions are allowed to differ across arms. In both settings, we do not make further assumptions on the delay distributions, except that we only require finite delay expectation. Note that we allow the support of the delays to be unbounded, i.e, an infinite delay time is possible in both settings. This models the practical scenarios in online recommender systems that some user feedbacks (e.g., ratings and reviews) may never be received.
Under delayed feedbacks, we denote the total number of missing feedbacks from arm up to a time step t as (t) A E'=1 (sstT...))) St). We let (t) maxiş.si (s),), Va E AA as the maximum total number of delayed feedback for arm up to time t. Note that (t) = 0, Va E AA corresponds to the non-delayed setting. In this case, (t) denotes the total number of pulling times of arm up to time f. At each time step t, the agent observes a set of time-stamped feedback denoted by S, C N x {0, 1}. In the set S,, each element a pair of time index and Bernoulli reward value, and the time index is the time step when the corresponding reward is observable. Note that in this model, by observing the set S,, the agent is aware of the information of both the time step when the feedback is received, and the arm that generated the feedback. We denote the total reward generated
by arm up to time & as (t) ES= X. L Stt and let (0) = 0, Va E A.
3.2 USER PREFERENCES AND INCENTIVE IMPACT MODELING
In this paper, we assume that the arrival at time f has a non non-zero probability (t( E (0, 1) to pull each arm A. We note that pa (t) can also be thought of as the user's preference rate of arm a, and EaEA Pa (t) = 1, Vt < T. We adopt the widely accepted multinomial logit model in the economics CerratureBawa Shoemaker 1987) to model arm a's preference rate at time step follows:
Pa(1) = f(Sa - 1) + 0.)
S( +.))
where f(-) IR- + (0.+oo) is a feedback function that is increasing, and 02 > 0 denotes fixed initial preference bias of arm a. We note that the preference rate modeling in (Zhou et al. (02T) is also based on the multinomial logit model, which appears to be in the same form as in (T) However, the key difference between our preference model in ①I) and that in (Zhou et al., 2021
that the accumulative award information St 1) in ① accounts for reward information that can only be observed up to time t. In other words, S, T) in (I) is affected by feedback delays. In fact, the preference model in (Zhou et al. 2021) can be viewed as a special case of our model with zero delay.
Since the arriving users select arms based on preferences, while the agent aims to maximize the total reward in the long run, there exists general difference between users' arm preferences and agent's 's intended arm selection. To induce users to pull arms following the agent's 's goal, the agent needs to intervene users' arm pulling by offering incentives on its desired arm, to increase the user'
4

---

Published as a conference paper at ICLR 2022
preference of pulling the arm. That is, the agent incentivizes arm I time step t that Pi (t) increases accordingly. Note that when (t; increases, the preference rates the other arms will decrease since E (t) = 1, < T. In this paper, we adopt the "coupon effect" model, which widely used in the economics and marketing literature (Bawa & Shoemaker 1987). Specifically, we consider fixed incentive b in each time step and denote the time-dependent incentive impact as g(b, t). Then, the posterior preference rates of the arms with incentive b are updated as follows:
p:(() + g(,,t)
i= a
1 g(b,1)
P((1)
(t(
i a.
We remark that the definition of the posterior preference update in (2) also follows from the multi- nomial logit model, which is widely used to model user preferences and their variations in bandit field (Chen & Wang 2017 Avadhanula 2019; Dong et al. 2020 Zhou et al.) (02I]. Based on the defined posterior preference, as incentive impact g 1) increases to infinity (either the incentive value b increases to infinity or the users are more sensitive to incentives as time goes by), the user preference will be induced to pulling the agent's desired arm a with probability one. For further detailed interpretations of the incentive impact function g(b, (), we refer readers to the literature (e.g.. (Zhou et al., 2021)). Note also that, due to the random user behaviors, it is possible that I * I,, i..., the arm that the agent incentivizes is not the one that a user pulls eventually. We define the accumulative incentive up to time step as B, Σ. bt, where b, E {0, b). Vt S T, denotes the agent's binary decision whether to offer incentive at time step t.
3.3 REGRET MODELING
As in most bandit learning problems, the goal of the agent maximize the total expected reward E [[Eee Sa ST)) in the long run. Toward this end, we need the notion of the oracle incentivized policy, where in hindsight, the agent is aware of the optimal arm a* and can always offer an infinite amount of payments to users with feedback being observable immediately, so that the posterior preference rate of arm a" is always infinitely close to one. As result, the expected accumulative reward generated under the oracle policy up to time T is E(Sa- (T) = 1u" T. However, since the optimal arm a" is unknown to the agent, the goal of the agent is to maximize the total expected incentivized policy with low accumulative incentive
reward B[[T]] in the long run by designing in the presence of self-reinforcing preferences and feedback delay. Similar to conventional MAB, we measure the performance gap between our accumulative reward against that of the oracle policy, which is denoted by regret Rr. The expected (pseudo) regret is defined as follows:
B[RT] 4²"
T E Σ (a(T))
In this paper, our goal is to minimize [[ with low expected accumulative payment B[Br], i.e., sub-linear growth rate regarding time horizon T. It is clear that any policy with bounded payment cannot outperform the oracle policy. Thus any expected regret defined by comparing with bounded- payment policy is upper bounded by regret.
4 BANDIT POLICY DESIGN AND PERFORMANCE ANALYSIS
In this section, we first present the general version of the UCB-FDF policy that works with any delay distributions, where we upper bound the delay impact on the regret and incentive costs. Based on this general result, we then study the regret and incentive costs performance of UCB-FDF un- der the assumptions of 1) i.i.d. feedback delay across arms/times and 2) arm-dependent delay distributions. In both cases, we denote the total number of missing feedbacks over all arms by ((L) & EaEA (t),), and denote the maximum number of missing feedbacks during the first time steps by (t) & max1ç.s1 D(s). For arm a at time step t, we denote the number of its pulling times whose feedback is observed by T (t) = (t) (t), and denote the maximum mean gap by A = max, A.. At time step f, we denote the sample mean estimation (due to delayed feedbacks) of arm by (a(()) (1) (t). Our UCB-FDF policy is illustrated in Algorithm
5

---

Published as a conference paper at ICLR 2022
Algorithm 1 The UCB- "CC-FFilerinn-wiid--Deleye---ee
Policy (UCB-FDE).
Require: Time horizon T and incentive payment b, the confidence interval of arm at time step t defined ca (1) v In T (2T)()))
1: Initialization: Incentivize pulling the arms satisfying (t) = 0 with incentive payment b until minge TV (t) > 1. Let set U = A. Mark current time as to-
2: Exploration Phase: While (2) > 1, remove all the arms from set U satisfying (a + ca (1) <
max. (fx(t) c)(t)) if there is any, then incentivize pulling arm a E arg min,eu TT
with payment If [M|] = 1, let arm å" {a : a E U1} and mark current time as 41
3: Exploitation Phase: Incentivize pulling arm a" with payment b until it dominates: Sa (t) >
Eaza- (ta(t) + (t)). Mark current time as t2.
4: Self-Sustaining Phase: Users pull arms based on their own preferences until time T.
UCB-FDF policy contains three phases: an incentivized exploration phase, an incentivized exploita- tion phase, and a self-sustaining phase. UCB-FDF policy tackles feedback delays in the following two key aspects: (i) correcting the sample mean estimate of arms by only considering the number of pulling times that have observed feedback, (ii) setting the length of the exploitation phase in such way that the outstanding rewards do not harm the emergence of "dominance" (i.e., one arm receiving at least half of the rewards) of the sampled optimal arm. Subsequently, these two aspects also influ- ence the regret and incentive. In order to have enough arm exploration with an unbiased sample mean estimate, the loss of counted number of pulling times necessitates carefully designed exploration phase that incentivizes the pulling of the least informed arm a E arg min Th under delayed feedbacks. Similarly, the delay-based dominance threshold (i.e., Sa- (t) 2 Eafa- (ta + Du in Step of Algorithm D guarantees the dominance of sampled optimal arm, while also accounts for longer exploitation phase to mitigate the delayed feedback effect. We now analyze the upper bounds of the pseudo regret and expected incentive of the UCB-FDF policy.
Lemma 1. (UCB- FerB-FFittringwwii wiith-Delayed-Feee Feedback) Given fixed time horizon T. if g(b,t) 1, E [Rr] is upper bounded by
and J [(x) (x² with
then the pseudo regret of Algorithm /
80. (g 1)
SA" In T g(b, 1)4
(E[* 44)
E
Σ
(g(b, 1) 1)
g(b, 1)
axta"
with the expected payment B[ upper bounded by
(b, 1) +
8hn
8 A + E(D + 4K
B[BT]
+
g(b 1) A min
aFa"
Remark 1. The UCB-FDF policy achieves a sub-linear total incentive cost by leveraging the prop- crty of self-reinforcing preference. We can show that as long as the self-reinforcing preference function fz) satisfies the condition f(z) ((2²) with probability one (i.e., the scenario where only one arm has positive probability to be pulled, thus this particular arm is the only preferred arm). A natural incentivizing policy is to incentivize sam- pled optimal arm until it achieves monopoly. However, the key challenge here is that the onset of monopoly could take infinite time steps, which implies linear total incentive. Moreover, self- reinforcing property is not merely disrupting the system from converging to the optimal arm. The key idea in our UCB-FDF policy design is that under the condition of the self-reinforcing preference function f()). after one arm establishes its dominance (i.e., the arm a generates at least half of the current total reward), it will have exponentially increasing probability to beat other arms and achieve monopoly. More importantly, we can show that the onset of arm dominance takes sub-linear times, thus allowing us to achieve sub-linear total incentive costs.
1. then "monopoly" happens with
Remark 2. The feedback delay affects the observation of arm dominance, since the missing re- ward information from suboptimal arms, if not compensated carefully, can potentially destroy the dominance status of the optimal arm. Thus, to guarantee dominance of the optimal arm, longer exploitation phase is necessary, and thus a large total incentive is required.
The notation O() in this paper is defined as that, if f(x) ((g(x)), then there exist and two constants C1, C2 O, such that Cig(z) < f(x & C29(x) for all x Jo.

---

Published as a conference paper at ICLR 2022
The existence of delays in our MAB model introduces additive term (TE(D*(T)) in both regret and incentive costs, which is dependent on the maximum accumulated delayed feedback up to time horizon T. Based on Lemma [ in what follows, we will analyze the upper bounds of the expected maximum accumulated delayed feedback under different assumptions on delay distributions.
4.1 ARM-INDEPENDENT DELAY WITH A FINITE EXPECTATION
We now analyze the delay impact under our first assumption. In the arm-independent case, we consider an i..dd sequence {Ti}e of random delay regarding time step t S T. We do not make any assumption on the shape of the delay distribution, except that we only assume a finite expectation B[T]]. Thus, an infinite random delay is possible under this assumption, implying some feedbacks may never be observed by the agent. Our results show that under this assumption, we can still achieve similar orders of the regret and incentive costs growth rates, since the key fact is that we can upper bound the expected number of such unexpectedly large random delays for every time step t.
Existing works (e.g.. (Joulani et al., 2013)) provided a systematic study the delay effect on the partial monitoring problem with side information, including the stochastic problems, Although these works only considered the classic stochastic MAB, they share some similarities with our work in that their analysis of delay effects also leveraged the maximum number of missing feedbacks during the first time steps D (t.). However, since our UCB-FDF policy has different structure compared to these works on delayed stochastic MAB, their delay analysis is not applicable to our policy. Next, restate a result in (Joulani et al., 2013), which will be useful in analysis.
Te) is a sequence of i..dd. random Lemma 2 (Lemma 2 in Joulani et al. (2013). Assume {TI....,
variables with finite expected value, and let (t,, s) + 2 log + v logt. Then, it holds that E(D((t) & B(,, B(r)) +
Theorem 3. tions of Lemma
Delay) Under i...d delays with a finite expectation and the condi-
7 the pseudo regret of Algorithm 7 (ETTT] is upper bounded by
[2g(b, 1)
84. 1)
8A
T g(b, 1)
4E
71
In T
E2
4K + 1)
g(b. 1) - agtan
(g(b, 1)
4
g(b, 1)
-1
with the expected payment EE [Br] upper bounded by
2g(b, 1) +1
8
b g(b, 1) -
2+
Σ
InT+ V 4B/r1 In + E[T]] + +4K +
A
AZ
aFa'
We note that the gap summation of arms Enpor Aa plays an important role in both regret and total incentive. As arm gaps getting smaller, is more difficult to distinguish the optimal arm from others. Thus, longer exploration phase is required to conduct enough sampling, which implies a larger regret and a larger total incentive costs. On the other hand, the feedback delay causes additive terms in both regret and incentive costs in terms of the expected delay E[[T]. and the delay impact can be upper bounded as long as the expected delay [E[T]] is no larger than time horizon T.
4.2 ARM-DEPENDENT DELAY WITH FINITE EXPECTATIONS
Now, we further relax the assumption the delay to allow arm-dependent delays. In this case, the delay has two key impacts on the system: (i) for each arm, there is different real-time information loss when estimating the sample mean, (ii) for the whole arm set, different scales of delay cause an uneven arm estimation, which results in a larger risk of the elimination of the optimal arm in the UCB-based exploration step. We formally state our arm-dependent delay assumption as follows:
Assumption 1. The delays of arm a E A form an independent delay sequence (Ta,th where each element is a random variable satisfying Ta,t Ta, with a finite expectation [E(Ta,1) < toc, Va E A.
Under Assumption D
we show a more general result on the upper bound of (E(D((() (f) as follows:
Lemma 4. Under Assumption 7 given a finite number of arms K O, it holds that
(()())) S Σ 2E(T.,1) +K log K
1
acA
7

---

Published as a conference paper at ICLR 2022
The result in Lemma 4 implies larger upper bounds of the regret and incentive, due the existence of the pre-log factor K. This is a consequence of the situation where, as we consider arm-dependent delay distributions, the worst case could be evenly distributed expected delays 1[T,,1] of arm a with respect to time horizon T. Formally, we state the upper bounds of regret and incentive as follows:
Theorem 5. (Arm- Arm--ependent Delay) Under Assumption 7 pseudo regret of Algorithm [Rr]] is upper bounded by
and the conditions of Lemma the
(g 1) -) + 8A*
(g(b, 1) 4) In g(b, 10,11) (3K +
2E Ta, 4K)
g(b 1)
with the expected payment B[Br] upper bounded by
2g(b, 1)
T K
b g 1) - A min
IT + 3K
+
Bl + 4K
A
azea"
Similar to the results under the i..dd. delay assumption, we can still upper bound the regret and incentive by an logarithmic growth rate O(log I') under arm-dependent delay. This implies that even under the weak delay assumption where only finite expectation is needed, UCB-FDF estimate arms without too much bias, and finally achieve logarithmic regret with logarithmic incentive costs.
5 EXPERIMENTAL RESULTS
In this section, we first introduce our experiment setting and the dataset, then illustrate our experi- mental results. Due the space limit, the full experimental results are provided in Appendix ??.
5.1 EXPERIMENTAL SETUP
We conduct experiments under two different delay settings. The system parameters are set as follows: a three-armed model with Arml being the optimal arm, and the initial preference bias f [1, 5, 5]. i.e., the optimal arm has the least initial bias. We choose three-armed model since large arm set requires a proportional large time horizon to distinguish optimal arm, while in the public Amazon Review Data, the amount of reviews for most products is limited (no more than 3,000 for each product). The self-reinforcing preference function chosen as f(x) = x with 1.5 with an incentive impact function
1) System Parameters:
2. The constant incentive for each time step is set g(b,t) t) = b. For the delay distribution, we use normal distributions in both assumption setting, as normal distributions have an infinite support & E TR. Under the -ndeindeennden delay setting, we choose the delay distribution as ~ N(0,, 2). Under the arm-dependent delay setting, we choose the delay distributions as TI, ~ [(80, 2). T2, N(10, 2). and T3, ~ N(10, 2) for Arms 2, and 3, respectively. We only generate non-negative samples of delay under both assumptions.
Product Category
Arml(optimal)
Arm2
Arm3
Pet Supplies
0.773
0.656
0.626
Electronics
0.757
0.605
0.617
Home and Kitchen
0.875
0.588
0.673
Books
0.915
0.551
0.706
Table 1: Means of products (arms) in different categories.
2) Dataset: We use Amazon Review Data (i et al. 2019) to provide a practical learning environ- ment. The Amazon Review Data includes 233 million customer reviews (ratings, posting times) for 29 product categories. the largest number of reviews in category Pet Supplies, Electronics, Home and Kitchen, and Books, respectively. For each product (arm), we leverage the ratine anting and un unixRevi weveeeeiime informa- tion in each review, and the total number of reviews is 3,000 for each product. The range of ratings in Amazon Review Data is the discrete set {1, 2, 3, 4, 5}. We convert the rating values to binary by setting the rating values 1 and 2 as O and the rating value and 1, and the reviews with rating
the experiment, we select three products to serve as the arms that have
8

---

Published as a conference paper at ICLR 2022
FARP
4003
T SESTE
000
Stotee
3000
(00)
400
100
200
Time horizon
Time horizon
Time horionn
Time holizon
Rupel
endire
2000
1000
1000
1250
2000
3000
1033
2000
3200
1032
2000
3050
1030
3032
Tirm horizus
Tira horuzn
Tire fusuun
Time hasion
(a)
(b)
(c)
(d)
Figure 1: The performance of policy UCB-FDF in the face of no delay in (a), the performance of policy UCB-FDI in the face of arm- arn-independent delay in (b), the performance of policy UCB-FDF in the face of arm-dependent delay in (c), and the performance of policy UCB-Lin in the face of arm-dependent delay (d).
value 3 are removed. For each product, the binary review ratings sorted by unixReeveww! ime, so the ratings come in real-world order in the experiment. We summarize the mean values of the products by their Bernoulli ratings in the four selected categories, as shown in Table 1
5.2 RESULTS AND DISCUSSIONS
The experiment results are illustrated in Figure (a) shows the average regret and incentive trends with policy UCB-FDF under setting with no delay. (b) and (c) show the average regret and incentive trends with policy UCB-FDF under settings with arm-independent delays and arm-dependent delays, respectively. In Figures (c) and (d), we compare the performances with policy UCB-FII FDF and baseline policy UCB-List (Zhou et al.) (02T]. Specifically, Figure (d) shows the performance under policy UCB-List in the face of arm-dependent delays that is the same as that in (c). Each curve is constructed by regret or incentive values with different time horizons from 150 to T 3000, incremented by 150. Each node value in curves are averaged by 100 trials.
1) Results:
observe the delay impact regret and total incentive, that both the regret and total incentive are increased due to the delayed feedback. Comparing (c) and (d) in Figure I observe that under the bandit instances in the face of same delayed feedback, our policy UCB-FDF reaches sub-linear growth rate both regret and total incentive, except the total incentive in category Pet Supplies, since may require more time steps to converge while our data is limited, while the policy UCB-List cannot guarantee sub-linear growth rate for both regret and total incentive.
2) Discussion: Comparing (a) with (b) and (c) in Figure [1,
CONCLUSION
In this work, proposed practical bandit model that considers the joint effect of the incentive impact, delayed feedback and reiffrriin user preferences in real-world recommender systems. We proposed UCB-FDF policy that achieves logarithmic growth rates of pseudo regret and to- tal incentive costs for fixed time horizon T. We also analyzed how different delay assumptions influence the regret and incentive costs. Specifically, we considered imm-independent delays and arm-dependent delays with weak assumption that only requires a finite expectation. The evaluations with real-wwrr world customer review data showed the effectiveness of our UCB-FDF policy in achieving sub-line linelinear regret while spending only sub-linear total incentive costs under delayed feedback.
ACKNOWLEDGMENTSS
This work has been supported in part by NSF grants CAREER CNS-2110259, CNS-21 12471, CNS- 21 2102233, CCF-21 10252, and Google Faculty Research Award.
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Conference on Learning Theory, pp. 76-78. PMLR, 2017.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi Mnl-bandit: A dynamic learning approach to assortment selection. Operations Research, 67(5):1453 2019.
Vashist Avadhanula. The MNL-Bandit Problem: Theory and Applications. Columbia University, 2019.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-517 1999.
Kapil Bawa and Robert Shoemaker. The effects of direct mail coupon on brand choice behavior. Journal of Marketing Research, 24(4):370-376, 1987.
Djallel Bouneffouf and Irina Rish. A survey on practical applications of multi-armed and contextual bandits. arXiv preprint arXiv:1904.10440, 2019.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint arXiv: 2012.
Soumen Chakrabarti, Alan Frieze, and Juan Vera. The influence of search engines on preferential attachment. Internet Mahematicx, 3(3):361-381, 2006.
Xi Chen and Yining Wang. A note tight lower bound for mnl-bandit assortment selection models. arXiv preprint arXiv: 2017.
Kefan Dong, Yingkai Li, Qin Zhang, and Yuan Zhou. Multinomial logit bandit with low switching cost. In International Conference on Machine Learning, pp. 2607-2615. PMLR, 2020.
Stephen G Eick. The two-armed bandit with delayed responses. The Annals of Statistics, pp. 254- 264, 1988.
Peter Frazier, David Kempe, Jon Kleinberg, and Robert Kleinberg. Incentivizing exploration. In Proceedings of the fifteenth ACM conference Economics and computation, pp. 5-22, 2014.
Ashish Goel, Sanjeev Khanna, and Brad Null. The ratio index for budgeted learning, with applica- tions. In Proceedings of the twentieth annual ACM-SIAM symposium Discrete algorithms, pp- 18-27. SIAM, 2009.
Sudipto Guha and Kamesh Munagala. Approximation algorithms for budgeted learning problems. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 104-113, 2007.
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International Conference on Machine Learning, pp. 1453-1461. PMLR, 2013.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4 22, 1985.
Tal Lancewicki, Shahar Segal, Tomer Koren, and Yishay Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. arXiv preprint arXiv:2106.024333 2021.
Anne Gael Manegueu, Claire Vernade, Alexandra Carpentier, and Michal Valko. Stochastic bandits with arm-dependent delays. In International Conference on Machine Learning, pp. 3348-3356. PMLR, 2020.
Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatie bandit exploration. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, pp. 565-5822 2015.
10

---

Published as a conference paper at ICLR 2022
Jianmo Ni. Jiacheng Li, and Julian McAuley. Justifying recommendations using distandly-lbelle reviews and fine- ane-grained aspects. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-IJCNIP), pp. 188-197, 2019.
Jacob Ratkiewicz, Santo Fortunato, Alessandro Flammini, Filippo Menczer, and Alessandro Vespig- nani. Characterizing and modeling the dynamics of online popularity. Physical review letters, 105 (15):158701, 2010.
Virag Shah, Jose Blanchet, and Ramesh Johari. Bandit learning with positive externalities. arXiv preprint arXiv:1802.0569) 2018.
Min Shao and Chrysostomos L Nikias. Signal processing with fractional lower order moments: stable processes and their applications. Proceedings of the IEEE, 81(7):86--0010, 1993.
Claire Vernade, Olivier Cappé, and Vianney Perchet. Stochastic bandit models for delayed conver-
sions. arXiv preprint arXiv: (...iv:1006.9900 09186, 2017.
Siwei Wang and Longbo Huang. Multi-armed bandits with compensation. arXiv preprint 18100111 2018.
Tianchen Zhou, Jia Liu, Chaosheng Dong, and Jingyuan Deng. Incentivized bandit learning with self-reinforcing user preferences. arXiv preprint arXi::2105.08866 2021.


Reviews:
[{"review_id": "zEBkNA2Eqeu", "reviewer": "Reviewer_8BXC", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros: \n1.\tThe 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.\n2.\tThe comparisons with related works given in Section 2 are helpful.\n3.\tThe theoretical results, to my understanding, are derived under fairly general assumptions. The distinctions between arm-independent versus arm-dependent delays are useful to see.\n\nCons: \n1.\tThe 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?\nAdditionally, 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?\n2.\tI 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? \n \nSome minor suggestions: \n1.\tThe mathematical formalization for self-reinforcing preference is a little difficult to find in the paper.\n2.\tI 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.\n3.\tWould 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$?\n\nQuestions during rebuttal period: \nPlease 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? \n", "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.", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "r6DaOPuRXX", "reviewer": "Reviewer_Rqug", "summary": "", "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 of the paper are as follows.\n\n+ 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.\n\n+ The paper is well-written with a meaningful experimental section where they empirically compare the incentive costs with regret.\n\n+ The algorithm is realistic in terms of practical implementation.\n\nThe main weakness of this paper is as follows\n\n- 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PlPwicT6c61", "reviewer": "Reviewer_wZfK", "summary": "", "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": "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:\n\n**Discussion of related work**:\n\nIt 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.\n\nI 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?\n\nAlso, 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.\n\n**Regret modeling and payments**:\n\nIt 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?\n\n**Algorithm naming**:\n\n(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.\n\n**Technical concerns**:\n\nI 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.\n\nIn 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.\n\n**Empirical results**:\n\nI 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.\n\n----\n\n_Post-author response_: Please refer to my response to the authors. I think that most of my main concerns have now been addressed.\n", "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.\n", "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.\n\n----\n\n_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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Ggi5tHj25mZ", "reviewer": "Reviewer_mJjk", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Major comments:\n\n1.\tThis 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?\n\n2.\tIn 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?\n\n3.\tIn 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?\n\n4.\tWhy only the term g(b,1) shows up in the regret bound but not g(b,t) for t>1?\n\n5.\tRegarding 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?\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)