Beyond the Click-Through Rate: Web Link Selection with Multi-level Feedback

1 Introduction

With the rapid development of the Internet, web links are playing important roles in websites and mobile apps for attracting users and generating revenues. For example, ecommerce websites such as Amazon and Taobao show featured recommendation links on shopping pages to induce more purchase. Online social networks such as Facebook and Google+ constantly push links of trending topics and friends' updates to users, so as to increase user engagement. Online media such as HBO and iQIYI present links to popular TV shows and movies on their homepages to attract more subscribers.

Due to the limited space of interest on a web page, only a finite number of links can be shown to a user when the page is browsed. This raises the web link selection problem, i.e., how to properly select a small subset of web links from a large link pool for a web page. Specifically, the web page on which the selected links are shown is called the target page. If clicked, each link directs the user to a subsequent page. This implies that web links provide a multi-level feedback to the web operator. The first level feedback refers to the likelihood that a user clicks a link, also known as the Click-Through Rate (CTR) at the target page. By tracking user actions after clicking a link, e.g., purchase or subscription, we can determine the revenue collected on the associated subsequent page, which gives the second level feedback. Since purchase or subscription can only happen after the click, the compound feedback is the product of the first-level and the second-level feedbacks. Intuitively, the first-level feedback (CTR) indicates the attractiveness of the link at the target page, while the second-level feedback indicates the potential revenue that can be collected from the subsequent page. The compound feedback reveals the compound revenue a web link can bring.

There has been a lot of research concerning the CTR of web links, e.g., [Langheinrich et al., 1999; Lohtia et al., 2003]. On the other hand, what happens after clicks is also worth great attention, as it generates revenue. For instance, cost per acquisition (CPA) is regarded as the optimal way for an advertiser to buy online advertising [Spooner, 2014]. Both the attractiveness and the profitability of a website or an app are important measures [Kohavi et al., 2014], because they represent the long-term and short-term benefits, respectively. This motivates us to move beyond CTR and to pursue both attractiveness and profitability simultaneously in link selection.

In this work, we consider the problem of selecting a finite number of links from a large pool for the target page, so as to maximize the total compound revenue, while keeping the total attractiveness above a certain threshold. The constraint on attractiveness (CTR) was also adopted in the literate of online advertising [Kumar, 2015; Mookerjee et al., 2016]. In addition, we also take into consideration the fact that contextual information, e.g., user preferences, is not always available, e.g., incognito visits [Aggarwal et al., 2010], cold start [Elahi et al., 2016], or cookie blocking [Meng et al., 2016]. Thus, we do not assume any prior contextual information. We refer to our problem as the context-free web link selection problem.

Our link selection problem is challenging. First of all, the attractiveness and profitability of a link can be conflicting goals, as shown in [Cai et al., 2017]. As a result, while selecting links with high CTRs satisfies the attractiveness constraint, it does not necessarily guarantee that the target page will have a high total compound revenue, and vice versa. What further complicates the problem is that the multi-level feedbacks, i.e., the CTR (first-level feedback) and the potential revenue (second-level feedback) of each link, are stochastic and unobservable unless a link is selected and shown on the target page.

We formulate our problem as a constrained stochastic multiple-play multi-armed bandit problem with multi-level rewards. Specifically, there are multiple arms in the system. Each arm represents a link in the pool. Its first-level reward, second-level reward, and compound reward correspond to the first-level feedback (the CTR), the second-level feedback (the potential revenue) and the compound feedback (the compound revenue) of that link, respectively. The objective is to select a finite number of links at each time step to minimize the cumulative regret, as well as the cumulative violation of the constraint. We design a constrained bandit algorithm, Constrained Upper Confidence Bound algorithm (Con-UCB), to simultaneously achieve sub-linear regret and violation bounds.

Our main contributions are as follows. (i) We formulate the link selection problem as a constrained bandit problem with stochastic multi-level rewards (Section 3). (ii) We propose the Con-UCB algorithm (Section 4) and prove that Con-UCB ensures small regret and violation bounds with high probability, i.e., for any given failure probability δ ∈ (0, 1), the regret and violation at time T are bounded by O(√T ln Tδ ) with probability at least 1 - δ (Section 5). (iii) We conduct extensive experiments on three real-world datasets. Our results show that Con-UCB outperforms three state-of-the-art context-free bandit algorithms, CUCB [Chen et al., 2013], EXP3.M [Uchiya et al., 2010], and LEXP [Cai et al., 2017] for the constrained link selection problem (Section 6).

2 RelatedWork

Link selection, or website optimization, has long been an important problem. One common approach for the problem is A/B testing [Xu et al., 2015; Deng et al., 2017], which splits the traffic to two web pages with different designs, and evaluates their performances. However, the overhead of A/B testing can be high when the web link pool is large, as it needs to compare different link combinations. Moreover, A/B testing does not have any loss/regret guarantees. Another approach is to model the link selection problem as a contextual multi-armed bandit problem [Li et al., 2010], and to incorporate the collaborative filtering method [Bresler et al., 2016; Li et al., 2016]. However, these contextual bandit formulations neglect the multi-level feedback structures and do not consider any constraint.

The multiple-play multi-armed bandit problem, where multiple arms are selected in each round, has been studied from both theoretical and empirical perspectives, and many policies have been designed [Uchiya et al., 2010;

Chen et al., 2013; Komiyama et al., 2015; Lagr´ee et al., 2016]. Our constrained multiple-play bandit model differs from aforementioned models in that we consider meeting the constraint on the total first-level rewards in selecting multiple arms, which is important for web link selection.

Recently, bandit with budgets [Ding et al., 2013; Wu et al., 2015; Xia et al., 2016] and bandit with knapsacks [Badanidiyuru et al., 2013; Agrawal and Devanur, 2014] have attracted much research attention. In these problems, pulling an arm costs certain resources, and each resource has a budget. Thus, resource cost is implicitly taken into consideration during the analysis of regret in the above two formulations since the arm selection process stops when resources are depleted. In contrast, since the constraint in our model is a requirement on the average performance, our arm selection procedure can last for an arbitrary length of time, and we need to consider both the regret and the violation of the constraint during the process. Thus, while our work builds upon the results in [Badanidiyuru et al., 2013] and [Agrawal and Devanur, 2014], the problem is different, and we study the multiple-play case rather than the single-play case. In addition, we conduct experiments on real-world datasets, which are not included in their works. On the other hand, the thresholding bandit problem in [Locatelli et al., 2016] is to find the set of arms whose means are above a given threshold through pure exploration in a fixed time horizon, which is different from our model.

Our work is closest to recent work [Cai et al., 2017]. They assume the second-level reward is adversarial. However, it has been observed that this might not be the case in practice [Pivazyan, 2004], and user behavior is likely to follow certain statistical rules when the number of users is large. So we study the stochastic case. Most importantly, our algorithm guarantees performance with high probability rather than in expectation, and the regret and violation bounds are improved significantly from O(T 2 3 ) and O(T 56 ) in their algorithm (LEXP) to both O(√T lnT) in our algorithm (ConUCB).

3 Model

Consider the two-level feedback context-free web link selection problem, where one needs to select L links from a pool of K web links, {l1, . . . , lK}, L ≤ K, to display on the target page. Each link directs users to a subsequent page. If li is shown on the target page, we obtain the following feedbacks when users browse the page:

1. the click-through rate (CTR), i.e., the probability that a user clicks li to visit the corresponding subsequent page,
2. the after-click revenue, i.e., the revenue collected from each user who clicks li and then purchases products (or subscribes to programs) on the corresponding subsequent page.

In practice, the click-through rate and the after-click revenue are stochastic, and we do not assume any prior knowledge about their distributions or expectations. The product of the CTR and the after-click revenue is the compound revenue, i.e., the revenue that li can bring if it is shown on the target page. The objective of the link selection problem is to maximize the total compound revenue of the selected L links, subject to the constraint that the total CTR of these selected links is no less than a preset threshold h > 0, 1 where h is determined by the web operator based on service requirement. An example is that in online advertising, the constraint on CTR is usually specified in the contract between the publisher (web operator) and the advertising firm [Kumar, 2015; Mookerjee et al., 2016].

To address the link selection problem, we formulate it as a constrained stochastic multi-armed bandit problem with multiple plays, where each arm has a two-level reward structure. In this formulation, each time step is a short duration and each arm corresponds to a specific web link. Thus, the set of arms can be written as K = {1, . . . ,K}. Each arm i is associated with two sequences of random variables, {ati }Tt=1 and {bti }Tt=1 , where ati characterizes arm i's firstlevel reward (CTR) at time t, and bti characterizes arm i's second-level reward (after-click revenue). We assume that for any i ∈ K, both {ati }Tt=1 and {bti }Tt=1 are sequences of i.i.d. random variables. The expectations of ati and bti are denoted by ai = E[ati ] and bi = E[bti ], i ∈ K. We also assume that ati is independent of bti for i ∈ K, t ≥ 1. Thus, the compound reward of arm i at time t is gt i = ati bti with mean gi = E[gt i ] = aibi. Denote a = (a1, . . . , aK) and g = (g1, . . . , gK). Without loss of generality, we assume that ati ∈ [0, 1] and bti ∈ [0, 1].

As mentioned above, the distributions or expectations of the two-level reward for any arm are unknown beforehand. At each time step t, an algorithm π selects a set of L ≤ K arms It(π) ⊂ K, and observes the first level reward ati as well as the second level reward bti for each arm i ∈ It(π). The optimal policy is the one that maximizes the expected total compound reward of the selected L arms, while keeping the total first level reward above the preset threshold 0 < h < L. 2

The optimal policy is not limited to deterministic policies as in traditional multi-armed bandit problems [Auer et al., 2002; Bubeck et al., 2012], but can be randomized, i.e., a distribution on the possible selections It. In practice, the number of web links K can be very large, and the number of possible selections of links at each time step can be as large as (KL ), which makes it complicated to consider randomized policies. To simplify the problem, we represent a randomized policy with a probabilistic selection vector x = (x1, . . . , xi, . . . , xK), 1ᵀx = L, where xi ∈ [0, 1] is the probability of selecting arm i and 1 = (1, . . . , 1) is the one vector. 3 At each time t, the selection set It(x) under a randomized policy x is generated via a dependent rounding procedure [Gandhi et al., 2006], which guarantees the probability that i ∈ It(x) is xi (see Section 4).

1 CTR measures the attractiveness of a link to users and is an important metric for the link selection problem.

2 If h = 0, the problem is equivalent to the classic unconstrained multiple-play multi-armed bandit problem (MP-MAB) [Anantharam et al., 1987]. If h ≥ L, there is no policy that can satisfy the constraint.

3 If not specified otherwise, all vectors defined in this paper are column vectors.

The set of randomized policies can be denoted by X = {x ∈ RK |0 ≤ xi ≤ 1, 1ᵀx = L}. Thus, the optimal stationary randomized policy is

Our objective is to design an algorithm π to decide the selection set It(π) for t = 1, . . . , T, such that the regret, i.e., the accumulated difference Regπ (T) between the compound reward under π and that under the optimal policy, is minimized. Specifically,

Note that the total first-level reward of arms in It(π) may violate the constraint, especially when t is small and we have little information about the arms. To measure the overall violation of the constraint at time T , we define violation of algorithm π as,

where [x]+ = max(x, 0). Note that when designing link selection algorithms, we should take both the regret and violation into consideration, so as to achieve both sub-linear regret and sub-linear violation with respect to T. Also, note that our model can be generalized to link selection problems with n-level (n > 2) feedback structures, by taking a subsequent page as a new target page and select links for it with the above model, and so on.

4 Algorithm

In this section, we present our Constrained Upper Confidence Bound algorithm (Con-UCB), and describe its details in Algorithm 1. Let Ht = {Iτ , aτi , bτi : i ∈ Iτ , 1 ≤ τ ≤ t} denote the historical information of chosen actions and observations up to time t. Define the empirical average first-level reward and compound reward for each arm i as

where N t i is the number that arm i is played before time t. Define R(µ, n) = √ γµ n + γn as in [Kleinberg et al., 2008] where γ is a constant. In Con-UCB, we use the following Upper Confidence Bounds for the unknown rewards [Agrawal and Devanur, 2014]:

Denote ¯at = (¯at1 , . . . , ¯atK ), ¯ gt = (¯ gt1 , . . . , ¯ gtK ), and ˆat = (ˆat1 , . . . , ˆatK ), ˆ gt = (ˆ gt1 , . . . , ˆ gtK ). In the initialization step

Algorithm 1 Constrained Upper Confidence Bound

• 1: for t = 1, 2, . . . , T do
• 2: Solve the following linear optimization problem:

If (5) has no feasible solution, set xt ∈ X arbitrarily.

• 3: Set It = DEPENDENTROUNDING(L, xt).
• 4: Receive ati and bti for i ∈ It. Update

• 5: end for
• 6: function DEPENDENTROUNDING(L, x)
• 7: while exists i such that 0 < xi < 1 do
• 8: Find i, j, i ̸= j, such that xi, xj ∈ (0, 1).

• 10: Update xi and xj as

• 12: end while
• 13: return I = {i | xi = 1, 1 ≤ i ≤ K}.
• 14: end function

of Algorithm 1, γ is set to 72 ln 8KT δ , where δ ∈ (0, 1) is an input parameter, i.e., the allowed failure probability.

Specifically, in each round, Con-UCB solves the optimization problem (5) to get the probabilistic selection vector xt (line 2). Notice that (5) is similar to the original constrained optimization problem (1) but uses the Upper Confidence Bounds to replace the unknown rewards. Then, It is generated via a dependent rounding procedure. In line 4 we receive the two-level rewards ati and bti for arms in It and update the empirical average rewards to get the Upper Confidence Bounds for the next round.

5 Theoretical Analysis

In this section, we bound the regret and violation of Algorithm 1. We will make use of the concentration inequalities in the following lemmas.

Lemma 1 (Azuma-Hoeffding inequality [Azuma, 1967]). Suppose {Yn : n = 0, 1, 2, 3, . . . } is a martingale and |Yn - Yn-1| ≤ cn almost surely, then with probability at least 1-2e- d2 2 ∑nj=1 c2j , we have

Lemma 2 ([Kleinberg et al., 2008; Badanidiyuru et al., 2013; Agrawal and Devanur, 2014]). Consider n i.i.d random variables Z1, . . . ,Zn in [0, 1] with expectation z. Let µ denote their empirical average. Then, for any γ > 0, with probability at least 1-2e- 1 72 γ , we have

The following lemma is a corollary of Lemma 2.

Lemma 3. Define the empirical averages ¯ati and ¯ gt i as in (4). Then, for every i and t, with probability at least 1 - 2e- 1 72 γ , we have

where γ ≥ 1. The same result holds between ¯ gt i and gi.

Proof. For every i and t, applying Lemma 2, we have that, with probability at least 1 - 2e- 1 72 γ ,

This implies that

The last inequality holds because ai ≤ 1 ≤ γ.

Based on the above lemmas, we obtain the following properties about Con-UCB.

Lemma 4. By running Con-UCB for T rounds with γ = 72 ln 8KT δ , with probability at least 1-δ, the following results hold simultaneously:

Proof. Omitted due to space limitation. Please refer to our technical report [Chen et al., 2018] for details.

From Lemma 4, we can obtain the regret and violation bounds for Con-UCB.

Theorem 1. For all T > 0, let γ = 72 ln 8KT δ . By running Con-UCB, we have with probability at least 1 - δ that,

Proof. We bound the regret and violation using (6) to (9), which were shown to hold with probability at least 1 - δ in Lemma 4.

From (6) we know for all t, x∗ is a feasible solution of the optimization problem (5), i.e., x∗ᵀ ˆat ≥ x∗ᵀa ≥ h. Then, for all 1 ≤ t ≤ T , we have,

where the last inequality follows from (8). Combining (9) and (10), we have

On the other hand, since for all t, (5) has a feasible solution x∗ , we know xᵀt ˆat ≥ h, 1 ≤ t ≤ T . Then with (7), we can get

This completes the proof.

6 Experiments

We conduct experiments on three real-world datasets to evaluate the performance of Con-UCB. Two datasets, CouponPurchase [Kaggle, 2016] and Ad-Clicks [Kaggle, 2015], with 271 coupons and 225 ads respectively, are shown to have a two-level feedback structure in [Cai et al., 2017]. In particular, for each coupon in Coupon-Purchase, a user who clicks the link to the coupon can decide whether to purchase that coupon; for each ad in Ad-Clicks, a user who clicks the link to the ad can decide whether to request the corresponding seller's phone number. Thus, for Coupon-Purchase (AdClicks), the first-level feedback is the CTR of each coupon (the CTR of each ad) and the second-level feedback is the purchase rate of each coupon (the phone request rate of each ad). The third dataset, edX-Course, is extracted from the data on 290 Harvard and MIT edX online courses [Chuang and Ho, 2016]. In particular, for the 290 online courses, we obtain course participation rates by normalizing the numbers of participants using min-max scaling and treat the course participation rates as the first-level feedback; we calculate course certification rates by dividing the numbers of certified participants by the numbers of participants, and treat the course certification rates as the second-level feedback.

We treat the coupons, ads, and courses as different sets of arms. To simulate the real-time two-level feedback of the coupons, ads, and courses, we generate the first-level reward of each arm (coupon, ad, and course) using a Bernoulli variable with mean taken from the first-level feedback (coupon CTR, ad CTR, and course participation rate) in the three datasets, and generate the second-level reward of each arm using another independent Bernoulli variable with mean taken from the second-level feedback (coupon purchase rate, ad phone request rate, and course certification rate).

For comparison purposes, we implement three state-of-theart bandit algorithms that can select multiple arms (L ≥ 1) at each round as baselines, i.e., CUCB [Chen et al., 2013], EXP3.M [Uchiya et al., 2010] and LEXP [Cai et al., 2017]. Specifically, CUCB selects the top-L arms with the L highest UCB indices ¯ gt i +√3 ln t/(2N t i ). EXP3.M selects L arms using exponential weights on the compound rewards of K arms, and LEXP selects arms using exponential weights based on the Lagrangian function of reward and violation of K arms.

For the three datasets, we run the three algorithms together with Con-UCB for 50, 000 rounds with parameter settings as shown in Figure 1-3, respectively. In particular, the parameters of EXP3.M and LEXP are set in accordance with Corollary 1 of [Uchiya et al., 2010] and Theorem 1 of [Cai et al., 2017], respectively. We compare the cumulative regrets tx∗ᵀg - ∑tτ=1 ∑i∈Iτ gτ i of LEXP and Con-UCB at each round t, where the optimal policy x∗ is computed from the means of the two-level feedback taken from each datatset. (Note that the regrets of CUCB and EXP3.M are not considered since they both have an unconstrained optimal policy, and therefore have different regret definitions from LEXP and Con-UCB.) We also compare the cumulative violations ∑tτ=1 (h - ∑i∈Iτ aτi )+ and the cumulative compound rewards ∑tτ=1 ∑i∈Iτ gτ i of the four algorithms. To put things into perspective, we compare the ratios between the cumulative rewards and the cumulative violations of all the algorithms. Such ratios show how much reward an algorithm can gain for each unit violation it has made.

The experiment results are averaged over 200 runs of each algorithm and illustrated in Figure 1-3. Figure 1(a) shows that the cumulative regret of Con-UCB is much lower than that of LEXP on the Coupon-Purchase dataset. This shows that Con-UCB can reduce the regret significantly by selecting arms using UCB-based optimization instead of exponential weights as in LEXP. Figure 1(b) and Figure 1(c) show the cumulative violations and the cumulative rewards of the four algorithms. In particular, the Optimal-reward in Figure 1(c) shows the cumulative reward tx∗ᵀg of the optimal policy x∗ at each round t. As shown in Figure 1(c), CUCB and EXP3.M have larger cumulative rewards than Con-UCB and LEXP, as both CUCB and EXP3.M neglect the threshold constraint and thereby blindly selecting arms that maximize the cumulative rewards. Therefore, both CUCB and EXP3.M incur huge cumulative violations as shown in Figure 1(b). Moreover, Con-UCB has a larger cumulative reward and a lower cumulative violation than LEXP. This matches our theoretical results that Con-UCB has smaller regret as well as violation bounds than LEXP. Figure 1(d) shows that Con-UCB achieves the largest reward/violation ratios among the four algorithms. This means that Con-UCB achieves the best tradeoff between rewards and violations and accumulates most reward for each unit violation it incurs.

We have similar experiment results on Ad-Clicks and edXCourse to those on Coupon-Purchase. As shown in Figure 2 and Figure 3, Con-UCB achieves lower cumulative regret and higher cumulative rewards than LEXP, and has the lowest cumulative violations and largest reward/violation ratios among all algorithms. Due to space limit, we omit the details.

In summary, our experiment results are consistent with our theoretical analysis and demonstrate the effectiveness of our Con-UCB algorithm in selecting arms with high cumulative rewards as well as low cumulative violations, thus achieving a good tradeoff between the reward and the violation.

7 Conclusion

In this paper, we consider the web link selection problem with multi-level feedback. We formulate it as a constrained multiple-play stochastic multi-armed bandit problem with multi-level reward. We design an efficient algorithm ConUCB for solving the problem, and prove that for any given allowed failure probability δ ∈ (0, 1), with probability at least 1 - δ, Con-UCB guarantees O(√T ln Tδ ) regret and violation bounds. We conduct extensive experiments on three real-world datasets to compare our Con-UCB algorithm with state-of-the-art context-free bandit algorithms. Experiment results show that Con-UCB balances regret and violation better than the other algorithms and outperforms LEXP in both

regret and violation.

Acknowledgments

The work by Longbo Huang and Kun Chen is supported in part by the National Natural Science Foundation of China Grants 61672316, 61303195, the Tsinghua Initiative Research Grant, and the China Youth 1000-Talent Grant. The work by John C.S. Lui is supported in part by the GRF 14208816 and the Huawei Research Grant.