Year: 2021

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” (UCBFDF) 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.

heading: 1 INTRODUCTION
text: 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 ecommerce recommender systems (e.g., Amazon and Walmart), the problem of online learning of the optimal products while making profits at the same time can be well formulated by an 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 a fundamental understanding and joint studies of these three important factors in MAB policy designs motivates us to 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 systems. 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 a dilemma between sufficient exploration through sampling 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 to mitigate biases (due to lack of initial data and self-reinforcing user preferences) and avoid spending unnecessarily high incentives that hurt the learning agent’s 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 online 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 random 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-UCB-Filtering” policy for the MAB framework that jointly considers incentivizing sampling, delayed sampling feedback, and self-reinforcing user preferences. We show that our proposed policy achievesO(log T ) regret withO(log T ) 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 O(log 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 as 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 “UCB-Filtering-with-Delayed-Feedback” (UCB-FDF) policy, which contains an incentivized exploration phase, an incentivized exploitation phase, and a selfsustaining 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 preferences to converge to the pulling of the optimal arm.
• We first show a 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 a 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 to be arm-dependent. Under this setting, we also show that similar logarithmic growth rates of regret and incentive can still be achieved.
• We conduct extensive experiments on Amazon Review Data 1 to demonstrate and verify the performance of our UCB-FDF policy as well as the impacts of delayed feedback on real-world scenarios. 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. Then in Section 3, we formulate our new MAB model that capture the three common phenomena. In Section 4, we present our UCB-FDF policy and analyze its performance. Then, we present our experiment settings and results in Section 5. Due to space limitations, the proofs are relegated to the appendix.
1https://nijianmo.github.io/amazon/

heading: 2 RELATED WORK
text: In this section, we provide a 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.
1) Bandits with Delayed Feedback: Motivated by practical issues in the clinical trials, Eick (1988) 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 a systematic study and showed that for delay τ with a finite expectation, the worst case regret scales with O( √ KT log T+KE[τ ]), whereK is the number of arms. Meanwhile, Vernade et al. (2017) showed that stochastic MAB problems with delayed feedback have a regret lower bound O(K log T ). However, 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 et 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, Lancewicki et al. (2021) studied the case where the delay distribution is 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 economics. Existing works in (Agrawal et al., 2017; 2019) formulated the user preference variation given different product bundles by the multi-nomial logit model on top of the bandit learning framework and proposed a Thompson Sampling approach that achieves a worst-case regret bound ofO( √ NT log TK), where N is the size of recommended arm bundle. With a different focus on preference modeling, Barabási & Albert (1999); Chakrabarti et al. (2006); Ratkiewicz et al. (2010) investigated the network evolution with “preferential attachment” that formulates the social behavior known as selfreinforcing preferences, among which the works in (Shah et al., 2018; Zhou et al., 2021) are the closet to our work. To our knowledge, Shah et al. (2018) was the first to consider self-reinforcing user preferences in bandit learning problems. Later, Zhou et al. (2021) incorporated self-reinforcing user preferences into the incentivized bandit learning framework. The key difference between these two works is that, in the model in (Shah et al., 2018), only one arm is revealed to users in each round, while in the model in (Zhou et al., 2021), all arms are revealed to users and users’ arm selections are influenced by incentives. However, both of these works fall short in modeling online recommender systems in practice as they assume that an arm-sampling feedback is observable in the same timeslot 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.
3) Incentivized Bandits: To our knowledge, Frazier et al. (2014) was among the first to adopt incentive schemes into a Bayesian MAB setting. In their model, the agent seeks to maximize timediscounted total reward by incentivizing arm selections. Later, Mansour et al. (2015) studied the non-discounted reward setting. For the non-Bayesian setting, Wang & Huang (2018); Zhou et al. (2021) proposed policies that maximize the total non-discounted reward with bounded incentive costs. Bandits with budget (Guha & Munagala, 2007; Goel et al., 2009) 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, a higher incentive cost is necessary.

heading: 3 SYSTEM MODEL
text: We first introduce the MAB framework with incentivized sampling, delayed feedback, and selfreinforcing user preferences. The system has a set of K ≥ 2 arms denoted byA = {1, . . . ,K}, and
each arm a follows a Bernoulli reward distribution Pa with an unknown mean µa > 0. The bandit time horizon has T rounds. In each time step t = 1, 2, . . . , T , a user arrives and chooses an arm It to pull. Then, the user will receive a random reward feedback Xt ∼ PIt . Both the arm selection It and the feedback Xt are observable to the agent. We use Ta(t) , ∑t i=1 1{Ii=a} to denote the number of times that arm a is pulled up to time step t. We let Ta(0) = 0, ∀a ∈ A. We assume that there is a unique best arm a∗ ∈ A in the sense that a∗ = arg maxa∈A µa and let µ∗ = µa∗ . Also, we define ∆a , µ∗ − µa as the gap between the mean of the optimal arm and the mean of arm a.

heading: 3.1 DELAYED FEEDBACK MODELING
text: In this paper, we consider delayed feedback, i.e., when an arm It is pulled at time step t, the corresponding Bernoulli rewardXt is observed after a delay period τIt,t, i.e., the feedbackXt is observed at time step t+ τIt,t. Without loss of generality, we model the random delay time as a random variable τa,t ∼ Ta, where the delay distribution Ta of arm a is unknown to the agent. We consider two settings of delayed feedback. We first consider i.i.d. delays {τt}t≤T across time and arms, i.e., 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 a 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 a up to a time step t as Da(t) , ∑t s=1 1{s+τa,s>t}. We let D ∗ a(t) = max1≤s≤tDa(s), ∀a ∈ A as the maximum total number of delayed feedback for arm a up to time t. Note that D∗a(t) = 0, ∀a ∈ A corresponds to the non-delayed setting. In this case, Ta(t) denotes the total number of pulling times of arm a up to time t. At each time step t, the agent observes a set of time-stamped feedback denoted by St ⊂ N × {0, 1}. In the set St, each element is a pair of time index and a 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 St, 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 a up to time t as Sa(t) , ∑t s=1Xs · 1{Is=a,s+τa,s≤t}, and let Sa(0) = 0, ∀a ∈ A.

heading: 3.2 USER PREFERENCES AND INCENTIVE IMPACT MODELING
text: In this paper, we assume that the arrival at time t has a non-zero probability pa(t) ∈ (0, 1) to pull each arm a ∈ A. We note that pa(t) can also be thought of as the user’s preference rate of arm a, and∑ a∈A pa(t) = 1, ∀t ≤ T . We adopt the widely accepted multinomial logit model in the economics literature(Bawa & Shoemaker, 1987) to model arm a’s preference rate at time step t as follows:
pa(t) = f ( Sa(t− 1) + θa )∑ i∈A f ( Si(t− 1) + θi
), (1) where f(·) : R → (0,+∞) is a feedback function that is increasing, and θa > 0 denotes a fixed initial preference bias of arm a. We note that the preference rate modeling in (Zhou et al., 2021) is also based on the multinomial logit model, which appears to be in the same form as in (1). However, the key difference between our preference model in (1) and that in (Zhou et al., 2021) is that the accumulative award information Si(t − 1) in (1) accounts for reward information that can only be observed up to time t. In other words, Si(t − 1) in (1) 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 a general difference between users’ arm preferences and agent’s intended arm selection. To induce users to pull arms following the agent’s goal, the agent needs to intervene users’ arm pulling by offering incentives on its desired arm, so as to increase the user preference of pulling the arm. That is, the agent incentivizes arm I ′t at time step t so that pI′t(t) increases accordingly. Note that when pI′t(t) increases, the preference rates on the other arms will decrease since ∑ a∈A pa(t) = 1, t ≤ T . In this paper, we adopt the “coupon effect” model, which
is widely used in the economics and marketing literature (Bawa & Shoemaker, 1987). Specifically, we consider a 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̂i(t) =  pi(t) + g(b, t) 1 + g(b, t) , i = a, pi(t)
1 + g(b, t) , i 6= a.
(2)
We remark that the definition of the posterior preference update in (2) also follows from the multinomial 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., 2021). Based on the defined posterior preference, as incentive impact g(b, t) 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, t), 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 ′t 6= It, i.e., the arm that the agent incentivizes is not the one that a user pulls eventually. We define the accumulative incentive up to time step t as Bt , ∑t s=1 bt, where bt ∈ {0, b}, ∀t ≤ T , denotes the agent’s binary decision whether to offer incentive b at time step t.

heading: 3.3 REGRET MODELING
text: As in most bandit learning problems, the goal of the agent is to maximize the total expected reward E [∑ a∈A Sa(T ) ]
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 a result, the expected accumulative reward generated under the oracle policy up to time T is E[Sa∗(T )] = µ∗ · T . However, since the optimal arm a∗ is unknown to the agent, the goal of the agent is to maximize the total expected reward E[ΓT ] in the long run by designing an incentivized policy with low accumulative incentive 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 RT . The expected (pseudo) regret is defined as follows:
E[RT ] = µ∗ · T − E [∑ a∈A Sa(T ) ] .
In this paper, our goal is to minimize E[RT ] with low expected accumulative payment E[BT ], 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 boundedpayment policy is upper bounded by our regret.

heading: 4 BANDIT POLICY DESIGN AND PERFORMANCE ANALYSIS
text: 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 under 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 D(t) , ∑ a∈ADa(t), and denote the maximum number of missing feedbacks during the first t time steps by D∗(t) , max1≤s≤tD(s). For arm a at time step t, we denote the number of its pulling times whose feedback is observed by T ′a(t) = Ta(t) −Da(t), and denote the maximum mean gap by ∆∗ = maxa∈A∆a. At time step t, we denote the sample mean estimation (due to delayed feedbacks) of arm a by µ̂a(t) = Sa(t)/T ′a(t). Our UCB-FDF policy is illustrated in Algorithm 1.
UCB-FDF policy contains three phases: an incentivized exploration phase, an incentivized exploitation 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
Algorithm 1 The UCB-Filtering-with-Delayed-Feedback Policy (UCB-FDF). Require: Time horizon T and incentive payment b, the confidence interval of arm a at time step t
defined as ca(t) = √ lnT/ ( 2T ′a(t) ) .
1: Initialization: Incentivize pulling the arms satisfying T ′a(t) = 0 with incentive payment b until mina∈A T ′ a(t) ≥ 1. Let set U = A. Mark current time as t0. 2: Exploration Phase: While |U|>1, remove all the arms from set U satisfying µ̂a(t) + ca(t) ≤ maxi 6=a,i∈U ( µ̂i(t) − ci(t) ) if there is any, then incentivize pulling arm a ∈ arg mini∈U T ′a(t)
with payment b. If |U| = 1, let arm â∗ = {a : a ∈ U} and mark current time as t1. 3: Exploitation Phase: Incentivize pulling arm â∗ with payment b until it dominates: Sâ∗(t) ≥∑ a6=â∗ ( Sa(t) +Da(t) ) . Mark current time as t2. 4: Self-Sustaining Phase: Users pull arms based on their own preferences until time T .
pulling times that have observed feedback, (ii) setting the length of the exploitation phase in such a 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 influence 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 a carefully designed exploration phase that incentivizes the pulling of the least informed arm a ∈ arg mini∈U T ′a(t) under delayed feedbacks. Similarly, the delay-based dominance threshold (i.e., Sâ∗(t) ≥ ∑ a6=â∗ ( Sa(t) +Da(t)
) in Step 3 of Algorithm 1) guarantees the dominance of sampled optimal arm, while also accounts for a 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-Filtering-with-Delayed-Feedback) Given a fixed time horizon T , if g(b, t) > 1, and f(x) = Θ(xα) with α > 12, then the pseudo regret of Algorithm 1 E[RT ] is upper bounded by
E[RT ] ≤ ∑ a6=a∗
8∆a ( g(b, 1)− 1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
lnT + g(b, 1)∆∗
( E[D∗(T )] + 4K ) g(b, 1)− 1 ,
with the expected payment E[BT ] upper bounded by
E[BT ] ≤ b · 2g(b, 1) + 1
g(b, 1)− 1
[ 8 lnT ∆2min + ∑ a6=a∗ 8 lnT ∆2a + E[D∗(T )] + 4K ] .
Remark 1. The UCB-FDF policy achieves a sub-linear total incentive cost by leveraging the property of self-reinforcing preference. We can show that as long as the self-reinforcing preference function f(x) satisfies the condition f(x) = Θ(xα) with α > 1, then “monopoly” happens 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 sampled 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, selfreinforcing 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. Remark 2. The feedback delay affects the observation of arm dominance, since the missing reward 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, a longer exploitation phase is necessary, and thus a large total incentive is required.
The existence of delays in our MAB model introduces an additive term Θ(E[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 1, in what follows, we will analyze the upper bounds of the expected maximum accumulated delayed feedback under different assumptions on delay distributions.
2The notation Θ() in this paper is defined as that, if f(x) = Θ(g(x)), then there exist x0 and two constants C1, C2 > 0, such that C1g(x) ≤ f(x) ≤ C2g(x) for all x ≥ x0.

heading: 4.1 ARM-INDEPENDENT DELAY WITH A FINITE EXPECTATION
text: We now analyze the delay impact under our first assumption. In the arm-independent case, we consider an i.i.d. sequence {τt}t of random delay regarding time step t ≤ T . We do not make any assumption on the shape of the delay distribution, except that we only assume a finite expectation E[τ1]. Thus, an infinite random delay is possible under this assumption, which 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 on 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 t time steps D∗(t). However, since our UCB-FDF policy has a different structure compared to these works on delayed stochastic MAB, their delay analysis is not applicable to our policy. Next, we restate a result in (Joulani et al., 2013), which will be useful in our analysis. Lemma 2 (Lemma 2 in Joulani et al. (2013)). Assume {τ1, . . . , τt} is a sequence of i.i.d. random variables with finite expected value, and let B(t, s) = s+ 2 log t+ √ 4s log t. Then, it holds that
E[D∗(t)] ≤ B(t,E[τ1]) + 1.
Theorem 3. (Arm-Independent Delay) Under i.i.d. delays with a finite expectation and the conditions of Lemma 1, the pseudo regret of Algorithm 1 E[RT ] is upper bounded by[
2g(b, 1)∆∗ g(b, 1)− 1 + ∑ a6=a∗
8∆a ( g(b, 1)− 1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
] lnT+ g(b, 1)∆∗ (√ 4E[τ1] lnT + E[τ1] + 4K + 1 )
g(b, 1)− 1 ,
with the expected payment E[BT ] upper bounded by
b · 2g(b, 1) + 1
g(b, 1)− 1
[( 2+ 8 ∆2min + ∑ a 6=a∗ 8 ∆2a ) lnT + √ 4E[τ1] lnT + E[τ1] + 4K + 1 ] .
We note that the gap summation of arms ∑ a 6=a∗ ∆a plays an important role in both regret and total incentive. As arm gaps getting smaller, it is more difficult to distinguish the optimal arm from others. Thus, a 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[τ1], and the delay impact can be upper bounded as long as the expected delay E[τ1] is no larger than time horizon T .

heading: 4.2 ARM-DEPENDENT DELAY WITH FINITE EXPECTATIONS
text: Now, we further relax the assumption on 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 a 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 ∈ A form an independent delay sequence {τa,t}, where each element is a random variable satisfying τa,t ∼ Ta, with a finite expectation E[τa,1] < +∞, ∀a ∈ A.
Under Assumption 1, we show a more general result on the upper bound of E[D∗(t)] as follows: Lemma 4. Under Assumption 1, given a finite number of arms K > 0, it holds that
E[D∗(t)] ≤ ∑ a∈A 2E[τa,1] + 3K log t K .
The result in Lemma 4 implies larger upper bounds of the regret and incentive, due to 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 E[τa,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-Dependent Delay) Under Assumption 1 and the conditions of Lemma 1, the pseudo regret of Algorithm 1 E[RT ] is upper bounded by∑
a6=a∗
8∆a ( g(b, 1)− 1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
lnT + g(b, 1)∆∗
( 3K ln TK + ∑ a∈A 2E[τa,1] + 4K ) g(b, 1)− 1 ,
with the expected payment E[BT ] upper bounded by
b · 2g(b, 1) + 1
g(b, 1)− 1
[( 8 ∆2min + ∑ a6=a∗ 8 ∆2a ) lnT + 3K lnT K + ∑ a∈A E[τa,1] + 4K ] .
Similar to the results under the i.i.d. delay assumption, we can still upper bound the regret and incentive by an logarithmic growth rateO(log T ) under arm-dependent delay. This implies that even under the weak delay assumption where only finite expectation is needed, UCB-FDF can estimate arms without too much bias, and finally achieve logarithmic regret with logarithmic incentive costs.

heading: 5 EXPERIMENTAL RESULTS
text: We evaluate the performance of our policy and the impact of delayed feedback on real-world scenarios. In this section, we first introduce our experiment setting and the dataset, and then illustrate our experimental results with discussions.

heading: 5.1 EXPERIMENTAL SETUP
text: 1) System Parameters: We conduct experiments under two different delay settings. The system parameters are set as follows: a three-armed model with Arm1 being the optimal arm, and the initial preference bias θ = [1, 5, 5], i.e., the optimal arm has the least initial bias. We choose a 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 is chosen as f(x) = xα with α = 2. The constant incentive for each time step is set as b = 1.5 with an incentive impact function g(b, t) = b. For the delay distribution, we use normal distributions in both assumption setting, as normal distributions have an infinite support x ∈ R. Under the arm-independent delay setting, we choose the delay distribution as τt ∼ N(10, 2). Under the arm-dependent delay setting, we choose the delay distributions as τ1,t ∼ N(10, 2), τ2,t ∼ N(15, 2), and τ3,t ∼ N(18, 2) for Arms 1, 2, and 3, respectively. We only generate non-negative samples of delay under both assumptions.
2) Dataset: We use Amazon Review Data (Ni et al., 2019) to provide a practical learning environment. The Amazon Review Data includes 233 million customer reviews (ratings, posting times) for 29 product categories. In the experiment, we select three products to serve as the arms that have the largest number of reviews in category Pet Supplies, Electronics, Home and Kitchen, and Books, respectively. For each product (arm), we leverage the rating and unixReviewTime information 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 0 and the rating value 4 and 5 as 1, and the reviews with rating value 3 are removed. For each product, the binary review ratings are sorted by unixReviewTime, 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.

heading: 5.2 RESULTS AND DISCUSSIONS
text: 1) Results: The experiment results are illustrated in Figure 1. (a) and (b) show the average regret and incentive trends under arm-independent delays and arm-dependent delays, respectively. Each curve is constructed by regret or incentive values with different time horizons from T = 150 to T = 3000, incremented by 150. Each node value in curves are averaged by 100 trials. Figure 1(c) illustrates the 100 values of regret or incentive costs with time horizon T = 3000 under arm-dependent delays.
2) Discussions; From the figures, we observe that our UCB-FDF policy achieves sub-linear growth rates for regret and incentive costs under our assumptions of feedback delays. Comparing results under arm-independent delays in Figure 1(a) and arm-dependent delays in Figure 1(b), we observe that arm-dependent delays require higher incentive costs and result in larger regret, due to the longer exploration and exploitation phases. Comparing regrets in different categories, we observe that the regret growth trends of categories “Books” and “Home and Kitchen” increase rapidly initially but quickly slow down, since the arms in these two categories have larger gap summations ∑ a 6=a∗ ∆a. Although a large gap summation may cause larger regret before the policy finds the optimal arm, it also allows the algorithm to distinguish the optimal arm faster. More straightforward results can be seen by the incentive curves in different categories. From a different angle, as we show in Figure 1(c), some of the total incentives in category Pet Supplies are exactly 4500, implying that in many random cases, the policy is still in the exploration or exploitation phase, while in most of the random cases in categories Books and Home and Kitchen, the incentive can stop early while also reach sub-linear regret. This difference is also caused by the variation in gap summations.

heading: 6 CONCLUSION
text: In this work, we proposed a practical bandit model that considers the joint effect of the incentive impact, delayed feedback and self-reinforcing user preferences in real-world recommender systems. We proposed a UCB-FDF policy that achieves logarithmic growth rates of pseudo regret and total incentive costs for a fixed time horizon T . We also analyzed how different delay assumptions influence the regret and incentive costs. Specifically, we considered arm-independent delays and arm-dependent delays with weak assumption that only requires a finite expectation. The evaluations with real-world customer review data showed the effectiveness of our UCB-FDF policy in achieving sub-linear regret while spending only sub-linear total incentive costs under delayed feedback.

heading: A APPENDIX I: PROOFS

heading: A.1 PROOF OF LEMMA 1
text: Lemma 1. (UCB-Filtering-with-Delayed-Feedback) Given a fixed time horizon T , if g(b, t) > 1, and f(x) = Θ(xα) with α > 13, then the pseudo regret of Algorithm 1 E[RT ] is upper bounded by
E[RT ] ≤ ∑ a6=a∗
8∆a ( g(b, 1)− 1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
lnT + g(b, 1)∆∗
( E[D∗(T )] + 4K ) g(b, 1)− 1 ,
with the expected payment E[BT ] upper bounded by
E[BT ] ≤ b · 2g(b, 1) + 1
g(b, 1)− 1
[ 8 lnT ∆2min + ∑ a6=a∗ 8 lnT ∆2a + E[D∗(T )] + 4K ] .
By the law of total expectation, the expected regret up to time T can be bounded as follows:
E[RT ] = E[Rt0 ] + E[RT | â∗ = a∗]P(â∗ = a∗) + E[RT | â∗ 6= a∗]P(â∗ 6= a∗) ≤ E[Rt0 ] + E[RT | â∗ = a∗] + T · P(â∗ 6= a∗) = E[Rt0 ] + E[Rt2 | â∗ = a∗] + E[RT −Rt2 | â∗ = a∗] + T · P(â∗ 6= a∗) = E[Rt0 ] + E[Rt1 ] + E[Rt2 −Rt1 | â∗ = a∗] + E[RT −Rt2 | â∗ = a∗] + T · P(â∗ 6= a∗). (3)
We start from bounding the term E[Rt0 ]. Note that the goal of the initialization step is to ensure that the confidence interval for each arm is initialized. Then we have
E[Rt0 ] ≤ E[t0] (i) ≤ m · ( 1 + g(b, 1)
g(b, 1) + E[τ1] ) (i) < m · (E[τ1] + 2), (4)
where (i) is because that by definition of initialization, for each arm a, it contributes to t0 in terms of its incentivizing attempts for being pulled by users once, and its delay period after which arm a will be regarded as initialized, then at time step t, when offered incentive b, arm a has probability no less than g(b, t)/ ( 1 + g(b, t) ) to be pulled by users, thus the number of attempts for arm a to be
pulled once is a geometric random variable with parameter no less than g(b, t)/ ( 1 + g(b, t) ) , with
expectation value ( 1 + g(b, t) ) /g(b, t), and (ii) is because that by condition g(b, t) > 1, we have(
1 + g(b, t) ) /g(b, t) < 2.
Then we bound the term E[Rt1 ]. During the exploration phase, since the regret is caused by pullings of sup-optimal arms, the expected regret after t ≤ t1 time steps can be written as∑
a 6=a∗,a∈A
∆aE[Ta(t)].
Thus we can bound the expected regret during the exploration phase E[Rt1 ] by bounding each E[Ta(t1)] for a 6= a∗. Let U(t) denote the set of arms that are activated, i.e., can get incentive, at time t. Consider the following two cases during the exploration phase:
(a) At time t ≤ t1, a∗ ∈ U(t) and there exists at least one suboptimal arm a ∈ A, a 6= a∗ such that a ∈ U(t). Recall that ca(t) = √ lnT/2 ( Ta(t)−Da(t) ) is the confidence interval of arm a at time
3The notation Θ() in this paper is defined as that, if f(x) = Θ(g(x)), then there exist x0 and two constants C1, C2 > 0, such that C1g(x) ≤ f(x) ≤ C2g(x) for all x ≥ x0.
step t. In this case, we have: P ( ∃a 6= a∗ : a ∈ U(t), a∗ ∈ U(t) ) (5)
(i) ≤ P ( µ̂a(t) + ca(t) > µ̂ ∗(t)− ca∗(t) ) · P ( µ̂∗(t) + ca∗(t) > µ̂a(t)− ca(t) ) ≤ P ( µ̂a(t) + ca(t) > µ̂ ∗(t)− ca∗(t) )
(ii) ≤ P ( µ̂a(t) + ca(t) > µa + ∆a
2
) + P ( µ̂∗(t)− ca∗(t) < µ∗ − ∆a
2
) , (6)
where (i) is obtained since arms a, a∗ ∈ U(t) implies that the upper confidence bound of either arm is larger than the other arms’s lower confidence bound, (ii) is because µa+∆a/2 = µ∗−∆a/2, and the event {µ̂a(t) + ca(t) > µ̂∗(t)− ca∗(t)} implies either the event {µ̂a(t) + ca(t) > µa + ∆a/2} or the event {µ̂∗(t)− ca∗(t) < µ∗−∆a/2}. We consider the first probability in Eq. (6), and similar bound will be obtained for the second probability. By Chernoff-Hoeffding bound we have
P ( µ̂a(t) + ca(t) > µa + ∆a
2
) = P ( µ̂a(t)− µa > ∆a
2 − ca(t) ) ≤ e−2(Ta(t)−Da(t)) ( ∆a 2 −ca(t)
)2 = e− ( lnT+ ∆2a 2 (Ta(t)−Da(t))−∆a √ 2(Ta(t)−Da(t)) lnT ) . (7)
Let ∆ 2 a 2 (Ta(t)−Da(t))−∆a √
2(Ta(t)−Da(t)) lnT = 0, we obtain Ta(t) = 8 lnT/∆2a +Da(t) and Eq. (7) equals 1/T . Note that as (Ta(t) − Da(t)) increases, Eq. (7) decreases monotonically. Thus, in this case, the expected regret contributed by a suboptimal arm a ∈ A during the exploration phase is bounded by
∆aE[Ta(t1)] ≤ 8 lnT
∆a + ∆a
( E[Da(t1)] + T · P ( t < t1 : a ∈ U(t), a∗ ∈ U(t) )) ≤ 8 lnT
∆a + ∆a
( E[Da(t1)] + 2 ) (8)
≤ 8 lnT
∆a + ∆a
( E[D∗a(t1)] + 2 ) . (9)
(b) At time t ≤ t1, a∗ is eliminated by some suboptimal arm a ∈ U(t), a 6= a∗. In this case, with similar technique as that in case (a) and Chernoff-Hoeffding bound, we have
P ( ∃a 6= a∗ : a ∈ U(t), a∗ /∈ U(t) ) ≤ P ( µ̂a(t)− ca(t) > µ̂∗(t) + ca∗(t)
) ≤ P ( µ̂a∗(t) + ca∗(t) ≤ µa∗ −
∆a 2
) + P ( µ̂a(t)− ca(t) ≥ µa +
∆a 2 ) ≤ e−2(Ta∗ (t)−Da∗ (t)) ( ∆a 2 +ca∗ (t) )2 + e−2(Ta(t)−Da(t)) ( ∆a 2 +ca(t)
)2 = e− ∆2a 2 (Ta∗ (t)−Da∗ (t))−lnT−∆a √ 2(Ta∗ (t)−Da∗ (t)) lnT
+ e− ∆2a 2 (Ta(t)−Da(t))−lnT−∆a
√ 2(Ta(t)−Da(t)) lnT
≤ 2T−1. (10) Note that P(â∗ 6= a∗) = P ( ∃a 6= a∗ : a ∈ U(t), a∗ /∈ U(t) ) . Thus, in this case the expected regret contributed by a suboptimal arm a ∈ A is upper bounded by
∆aE[Ta(t1)] ≤ ∆aT · P ( a ∈ U(t), a∗ /∈ U(t) ) = 2∆a. (11)
Summing Eq. (9) and Eq. (11) over all suboptimal arms, the expected regret during the exploration phase is bounded by:
E[Rt1 ] ≤ ∑ a6=a∗ 8 lnT ∆a + ∆a ( E[D∗a(t1)] + 4 ) . (12)
During the exploration phase at time step t < t1, since the agent offers incentive payment b to the user for pulling arm i, the probability that the arm i is pulled is ( pi(t) + g(b, t) ) / ( 1 + g(b, t) ) lower bounded by g(b, t)/ ( 1 + g(b, t) ) . Thus, the number of attempts for arm i to get pulled is a
geometric random variable with expectation no larger than ( 1 + g(b, t) ) /g(b, t). Since the above cases (a) and (b) imply that at most 8 lnT/∆2a + E[D∗a(t1)] + 4 expected number of pullings from each suboptimal arm ensures a good estimation of the optimal arm, thus, the expected number of incentivizing attempts on a suboptimal arm a to guarantee 8 lnT/∆2a + E[D∗a(t1)] + 4 number of pullings is upper bounded by:
E [ t1∑ s=1 1{I′s=a} ] ≤ g(b, 1) + 1 g(b, 1) ( 8 lnT ∆2a + E[D∗a(t1)] + 4 ) .
Thus, E[τ1] is upper bounded by:
E[t1] = ∑ a∈A E [ t1∑ s=1 1{I′s=a} ] (i) ≤ g(b, 1) + 1 g(b, 1) [ 8 lnT ∆2min + ∑ a 6=a∗ ( 8 lnT ∆2a + 4 ) + ∑ a∈A D∗a(t1) ] , (13)
where (i) is due to the requirement of Ta∗(t1) to be at most 8 lnT/∆2min + E[D∗a∗(t1)], since the exploration phase stops once the sampled strongest suboptimal arm is eliminated. By the definition of dominance, arm â∗ is expected to dominate at time t ≥ t1 if
µâ∗E[Tâ∗(t)−Dâ∗(t)] ≥ ∑ a6=â∗ µaE[Ta(t)].
We tighten the condition by narrowing the left-hand-side and amplifying the right-hand-side, and obtain the sufficient condition of dominance as follows:
µâ∗E[Tâ∗(t)−Dâ∗(t)] ≥ ∑ a 6=â∗ µaE[Ta(t)]
⇒ µâ∗E[Tâ∗(t)−D∗â∗(t)− Tâ∗(t1)] ≥ ∑ a6=â∗ µa ( E[Ta(t1)] + E[Ta(t)− Ta(t1)] )
⇒ µâ∗E[Tâ∗(t)−D∗â∗(t)−Tâ∗(t1)] (i) ≥ ∑ a 6=â∗ [ 8µa ∆2a lnT+µa ( E[D∗a(t)]+4 ) +µaE[Ta(t)−Ta(t1)] ]
⇒ µâ∗ [ g(b, 1)E[t− τ1] g(b, 1) + 1 − E[D∗â∗(t)] ] (ii) ≥ ∑ a 6=â∗ [ 8µa ∆2a lnT + µa ( E[D∗a(t)] + 4 )] + µâ∗E[t− τ1] g(b, 1) + 1
⇒ E[t− τ1] (iii) ≥ g(b, 1) + 1
g(b, 1)− 1 [ ∑ a 6=â∗ 8 lnT ∆2a + ∑ a∈A ( E[D∗a(t)] + 4 )] , (14)
where (i) is obtained since Tâ∗(t1) > 0 and D∗â∗(t) ≥ Dâ∗(t), (ii) is because by incentivizing arm â∗, we have p̂â∗(t) ≥ g(b, t)/ ( g(b, t) + 1 ) and p̂a(t) ≤ 1/ ( g(b, t) + 1 ) for a 6= â∗, and (iii) is the rearrangement. Since time t2 is defined as the earliest time to reach dominance, we can upper bound E[t2 − t1] by
E[t2 − t1] ≤ g(b, 1) + 1
g(b, 1)− 1 [ ∑ a6=â∗ 8 lnT ∆2a + ∑ a∈A ( E[D∗a(t2)] + 4 )] . (15)
Thus, we can bound the regret during the exploitation phase E[Rt2 −Rt1 | â∗ = a∗] in (3) by
E[Rt2 −Rt1 | â∗ = a∗] (i) ≤
∆∗
g(b, 1) + 1 · E[t2 − t1]
≤ ∑ a 6=a∗
8∆∗ lnT ∆2a(g(b, 1)− 1) + ∑ a∈A
∆∗ ( E[D∗a(t2)] + 4 ) g(b, 1)− 1 , (16)
where (i) follows because during the exploitation phase there is always a positive probability p̂a(t) which is at most 1/ ( g(b, t) + 1 ) to pull suboptimal arm a. After arm â∗ dominates, we want to
prove that arm â∗ has exponentially large probability to achieve monopoly, so as to upper bound the regret in the self-sustaining phase E[RT −Rt2 | â∗ = a∗]. Since the dominance proof only involves the accumulated reward Sa(t), our situation reduces to the non-delay case in expectation. Thus, we omit the proof in Zhou et al. (2021) and show the result by
E[RT −Rτs | â∗ = a∗] ≤ e−(log T ) γ + e−(log T+1) γ + · · · , (17)
with the summation on the right hand side bounded by O ( (log T )1−γe−(log T ) γ) and γ ∈ (0, 1/4). Now, summing up Eqs. (4),(10),(12),(16),(17), we obtain the regret upper bound stated in Lemma 1.
By using Eqs (13) and (15), the expected incentive E[BT ] can also be upper bounded by
E[BT ] = (E[t1] + E[ts − t1]) · b
≤ g(b, 1) + 1
g(b, 1)
[ 8b lnT ∆2min + ∑ a6=a∗ (8b lnT ∆2a + 4b ) + E[D∗(t1)] ]
+ g(b, 1) + 1
g(b, 1)− 1 [ ∑ a 6=â∗ 8b lnT ∆2a + bE[D∗(t2)] + 4bK ] (i) ≤ g(b, 1) + 1
g(b, 1)
[ 8b lnT ∆2min + ∑ a6=a∗ 8b lnT ∆2a + bE[D∗(t2)] + 4bK ]
+ g(b, 1) + 1
g(b, 1)− 1 [ ∑ a 6=â∗ 8b lnT ∆2a + bE[D∗(t2)] + 4bK ]
= g(b, 1) + 1
g(b, 1) ·
8b lnT
∆2min +
( g(b, 1) + 1
g(b, 1) + g(b, 1) + 1 g(b, 1)− 1 ) · ( ∑ a6=â∗ 8b lnT ∆2a + bE[D∗(t2)] + 4bK ) (ii) ≤ 2g(b, 1) + 1
g(b, 1)− 1
[ 8b lnT ∆2min + ∑ a 6=a∗ 8b lnT ∆2a + bE[D∗(t2)] + 4bK ] ,
where (i) follows from D∗(t2) ≥ D∗(t1) since t2 ≥ t1, and (ii) follows from rearranging of the coefficients containing g(b, 1).

heading: A.2 PROOF OF THEOREM 3
text: Theorem 3. (Arm-Independent Delay) Under i.i.d. delays with a finite expectation and the conditions of Lemma 1, the pseudo regret of Algorithm 1 E[RT ] is upper bounded by[
2g(b, 1)∆∗ g(b, 1)− 1 + ∑ a6=a∗
8∆a ( g(b, 1)− 1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
] lnT+ g(b, 1)∆∗ (√ 4E[τ1] lnT + E[τ1] + 4K + 1 )
g(b, 1)− 1 ,
with the expected payment E[BT ] upper bounded by
b · 2g(b, 1) + 1
g(b, 1)− 1
[( 2+ 8 ∆2min + ∑ a 6=a∗ 8 ∆2a ) lnT + √ 4E[τ1] lnT + E[τ1] + 4K + 1 ] .
Combining the results in Lemma 1 and Lemma 2, we obtain that the regret is upper bounded by
E[RT ] ≤ ∑ a 6=a∗
8∆a ( g(b, 1)−1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
lnT + g(b, 1)∆∗
( E[τ1]+2 lnT+ √ 4E[τ1] lnT+4K+1 ) g(b, 1)− 1 .
Then by some straightforward rearrangements we obtain the regret upper bound in Theorem 3. Similarly, by replacing E[D∗(T )] with its upper bound in the incentive upper bound, we obtain the rearranged incentive upper bound in Theorem 3.

heading: A.3 PROOF OF LEMMA 4
text: Lemma 4. Under Assumption 1, given a finite number of arms K > 0, it holds that
E[D∗(t)] ≤ ∑ a∈A 2E[τa,1] + 3K log t K .
We consider a two-armed model with arm a and b, with arm-dependent delay distribution Ta and Tb. Without loss of generality, we assume that E[τa,1] ≥ E[τb,1]. Then, the worst case where D∗(t) is maximized is that one first consecutively pull arm a for ta times, then consecutively pull arm b for the rest t− ta times. Now, consider another two cases where arm a and arm b are pulled for ta times and t − ta times independently, we denote their maximum outstanding feedback up to time step ta and t− ta by D∗a(ta) and D∗b (t− ta) respectively. We obtain the relationship below at time step t:
D∗(t) ≤ D∗a(ta) +D∗b (t− ta),
Now, by the result in Lemma 2, we obtain that
E[D∗(t)] ≤ E[D∗a(ta)] + E[D∗b (t− ta)] (i) ≤ ∑ i=a,b E[τi,1] + 2 ( log ta + log(t− ta) ) + 2 √ E[τa,1] log ta + 2 √ E[τb,1] log(t− ta)
(ii) ≤ ∑ i=a,b E[τi,1] + 2 ( log ta + log(t− ta) ) + E[τa,1] + log ta + E[τb,1] + log(t− ta)
= ∑ i=a,b 2E[τi,1] + 3 ( log ta + log(t− ta) )
(iii) ≤ ∑ i=a,b 2E[τi,1] + 3 · 2 log t 2 ,
where (i) is by the result in Lemma 2; (ii) comes from the inequality 2 √ ab ≤ a + b; and (iii) comes from the fact that t/2 is the maximizer of function h(x) = log x + log(t − x). This result can be straightforwardly extended to multi-armed model with K ≥ 2 by the relationship D∗(t) ≤∑ i∈AD ∗ i (ti) with ∑ i∈A ti = t.

heading: A.4 PROOF OF THEOREM 5
text: Theorem 5. (Arm-Dependent Delay) Under Assumption 1 and the conditions of Lemma 1, the pseudo regret of Algorithm 1 E[RT ] is upper bounded by∑
a6=a∗
8∆a ( g(b, 1)− 1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
lnT + g(b, 1)∆∗
( 3K ln TK + ∑ a∈A 2E[τa,1] + 4K ) g(b, 1)− 1 ,
with the expected payment E[BT ] upper bounded by
b · 2g(b, 1) + 1
g(b, 1)− 1
[( 8 ∆2min + ∑ a6=a∗ 8 ∆2a ) lnT + 3K lnT K + ∑ a∈A E[τa,1] + 4K ] .
Combining the results in Lemma 1 and Lemma 4, we obtain that the regret is upper bounded by
E[RT ] ≤ ∑ a6=a∗
8∆a ( g(b, 1)− 1 ) + 8∆∗(
g(b, 1)− 1 ) ∆2a
lnT + g(b, 1)∆∗
(∑ a∈A 2E[τa,1] + 3K log t
K + 4K ) g(b, 1)− 1 .
Thus we obtain the regret upper bound in Theorem 5. Similarly, by replacing E[D∗(T )] with its upper bound in the incentive upper bound, we obtain the rearranged incentive upper bound in Theorem 5.

heading: B APPENDIX II: EXPERIMENTS
text: We provide the full details of the experiments here.

heading: B.1 BASELINE COMPARISONS
text: In this section, we compare our policy UCB-FDF with UCB-List in Zhou et al. (2021). The system parameters are almost the same as that in Section 5.1. We use the three-armed model with the initial preference bias θ = [1, 5, 5]. The self-reinforcing preference function is chosen as f(x) = xα with α = 2. The constant incentive for each time step is set as b = 1.5 with an incentive impact function g(b, t) = b. The experiment results are illustrated in Figure 2. In Figures (a) and (b), we compare the performances under the no delay setting and the arm-dependent delay setting. Specifically, Figure (a) shows the performance under policy UCB-FDF in the face of no delay, and Figure (b) shows the performance under policy UCB-FDF in the face of arm-dependent delays, we choose the delay distribution as τ1,t ∼ N(80, 2), τ2,t ∼ N(10, 2), τ3,t ∼ N(10, 2) for arm1, arm2, arm3, respectively. We only generate non-negative samples of delay under both assumptions. In Figures (b) and (c), we compare the performances with policy UCB-FDF and UCB-List (Zhou et al., 2021). Specifically, Figure (c) shows the performance under policy UCB-List in the face of arm-dependent delays that is the same as that in (b). Each curve is constructed by regret or incentive values with different time horizons from T = 150 to T = 3000, incremented by 150. Each node value in curves are averaged by 100 trials.
Discussion: Comparing (a) and (b) in Figure 2, we can observe the arm-dependent delay impact on regret and total incentive, that both the regret and total incentive are increased due to the delayed feedback. Comparing (b) and (c) in Figure 2, we observe that under the bandit instances in the face of same delayed feedback, our policy UCB-FDF reaches sub-linear growth rate in both regret and total incentive, except the total incentive in category Pet Supplies, since it 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.

heading: B.2 DELAY DISTRIBUTION COMPARISONS
text: In this section, we compare performance of policy UCB-FDF under different delay distributions using the data in category Books. The experiment results are illustrated in Figure 3. (a) in Fig-
ure 3 shows the different regret under different delay distributions, and (b) shows the corresponding total incentive. For arm-independent delays, we show the policy performance under distribution N(20, 5), N(40, 5), and Exp(0.1), Exp(0.01). For arm-dependent delays, we choose the delay distribution as τ1,t ∼ N(40, 5), τ2,t ∼ Exp(0.01), τ3,t = 0 for arm1, arm2, arm3, respectively. We also show the average exploration phases (t̄1) and average exploitation phases (t̄2) under four different settings of delay distribution: i) no delay; ii) arm-independent delay with normal distribution N(40, 5); iii) arm-independent delay with exponential distribution Exp(0.01); iv) arm-dependent delay with τ1,t ∼ N(40, 5), τ2,t ∼ Exp(0.01), τ3,t = 0 for arm1, arm2, arm3, respectively. The results are shown in Table 2.
Discussion: From Figure 3, we observe that the policy performance is impacted by different delay distributions and different distribution parameters. It aligns with our theoretical analysis that the case with no delay has the smallest regret, and as delay expectation getting larger, we have larger expected regret and larger total incentive. From Table 2, we firstly have the general observation that as time horizon increases, both the exploration phase and the exploitation phase are increasing, due to a more accurate estimation over arms. On the other hand, we observe that the length of exploration phase is problem-dependent, while the length of exploitation phase is positive proportional with the value of expected delay, which is due to our exploitation mechanism where dominance threshold grows with expected delay.

heading: B.3 COMPARISON WITH DIFFERENT PARAMETERS
text: In this section, we compare the performance of policy UCB-FDF under different system parameters using the data in category Books, specifically, we compare the impact of different strengths of feedback function f(·) and incentive impact function g(·). We use the setting f(x) = xα with α = 2 and g(b, t) = b as the comparison group. For the other four groups of experiment, we use α = 3 and α = 4 for feedback function with g(b, t) = b, and g(b, t) = 2b and g(b, t) = 3b for incentive
impact function with α = 2, respectively. (a) in Figure 4 shows the different regret under different parameters, and (b) shows the corresponding total incentive.
Discussion: For the feedback function f(·), as α increases, the strength of self-reinforcing preferences is enhanced, which implies that the preferences are easier to be induces to one arm, so that we observe smaller regret. For the incentive impact function g(b, t) = c·b, as the coefficient c increases, the preference impact of a unit payment is enhances, implying that users are easier to be affected (controlled) by the incentive, thus we observe a slightly smaller regret, with obviously decreased total incentive.

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

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.

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.