Selecting the right web links for a website is important because appropriate links not only can provide high attractiveness but can also increase the website's revenue. In this work, we first show that web links have an intrinsic . For example, consider a @math -level feedback web link: the @math st level feedback provides the Click-Through Rate (CTR) and the @math nd level feedback provides the potential revenue, which collectively produce the compound @math -level revenue. We consider the context-free links selection problem of selecting links for a homepage so as to maximize the total compound @math -level revenue while keeping the total @math st level feedback above a preset threshold. We further generalize the problem to links with @math -level feedback structure. The key challenge is that the links' multi-level feedback structures are unobservable unless the links are selected on the homepage. To our best knowledge, we are the first to model the links selection problem as a constrained multi-armed bandit problem and design an effective links selection algorithm by learning the links' multi-level structure with provable regret and violation bounds. We uncover the multi-level feedback structures of web links in two real-world datasets. We also conduct extensive experiments on the datasets to compare our proposed algorithm with two state-of-the-art context-free bandit algorithms and show that algorithm is the most effective in links selection while satisfying the constraint.
@cite_3: A B tests (or randomized controlled experiments) play an integral role in the research and development cycles of technology companies. As in classic randomized experiments (e.g., clinical trials), the underlying statistical analysis of A B tests is based on assuming the randomization unit is independent and identically distributed ( ). However, the randomization mechanisms utilized in online A B tests can be quite complex and may render this assumption invalid. Analysis that unjustifiably relies on this assumption can yield untrustworthy results and lead to incorrect conclusions. Motivated by challenging problems arising from actual online experiments, we propose a new method of variance estimation that relies only on practically plausible assumptions, is directly applicable to a wide of range of randomization mechanisms, and can be implemented easily. We examine its performance and illustrate its advantages over two commonly used methods of variance estimation on both simulated and empirical datasets. Our results lead to a deeper understanding of the conditions under which the randomization unit can be treated as In particular, we show that for purposes of variance estimation, the randomization unit can be approximated as when the individual treatment effect variation is small; however, this approximation can lead to variance under-estimation when the individual treatment effect variation is large.
One common approach to the links selection problem is to perform A B testing @cite_3 , which splits the traffic for different sets of links on two different web pages, and then evaluate their rewards. However, A B testing does not have any loss regret guarantee as it splits equal amounts of traffic to the links regardless of the links' rewards. That said, A B testing is still widely used in commercial web systems. Our algorithm can be viewed as a complementary approach to A B testing, e.g., our algorithm can select the set of links with the @math st level reward above a given threshold and facilitate a more efficient A B testing for the links selection problem.