Estimation Bias in Multi-Armed Bandit Algorithms for Search Advertising
In search advertising, the search engine needs to select the most profitable advertisements to display, which can be formulated as an instance of online learning with partial feedback, also known as the stochastic multi-armed bandit (MAB) problem. In this paper, we show that the naive application of MAB algorithms to search advertising for advertisement selection will produce sample selection bias that harms the search engine by decreasing expected revenue and "estimation of the largest mean" (ELM) bias that harms the advertisers by increasing game-theoretic player-regret. We then propose simple bias-correction methods with benefits to both the search engine and the advertisers.
This paper explores the task of search advertising 
      auctions. In a second-price auction, the auctioneer must consider both the 
      per-click price offered by the advertisers (which is known) and the 
      probability that users will click the ad (which must be estimated from 
      data). Multi-armed bandit algorithms can be used to choose which ads to 
      run when estimating the click probability for each ad, since it is 
      critical to have accurate estimates of both the highest and second-highest 
      value advertisers in order to run the auction. The authors 
      identify and address two sources of bias that affect this task, impacting 
      both the auctioneer and advertisers' profits. First, they find that 
      multi-armed bandit algorithms tend to underestimate the value being 
      estimated due to sample selection bias, as overestimated values are 
      resampled (and corrected) while underestimated values receive fewer 
      samples (and remain underestimates). In a second-price auction, the 
      auctioneer then charges a lower price than they could on expectation if 
      the true click probabilities were known. Bounds on this loss are proven, 
      and the auctioneer's loss does not converge to zero due to the sample 
      selection bias. They give an example of a simple method for correcting 
      this bias. Second, they find that advertisers in this auction are not 
      acting optimally by bidding their true value, as is sought with a 
      second-price auction; instead, they can increase their expected value by 
      under-bidding while still bidding enough that their ads are bought. The 
      auctioneer will tend to overestimate the second price used for the 
      auction, even if its estimates for each individual advertiser are 
      unbiased. By underbidding an agent can cause the auctioneer to obtain 
      better estimates of the other advertisers' rates, thus lowering the price 
      that the winner will be charged. While this bias cannot be provably 
      corrected for, the authors show a technique for reducing it. Empirical 
      results are presented that demonstrate both sources of bias, and how their 
      correction measures decrease auctioneer loss and incentivize advertisers 
      to bid closer to their true value. QUALITY: The paper makes a 
      good contribution. It demonstrates sources of bias in the search 
      advertising task, proves bounds on them, presents corrections or 
      reductions, and demonstrates the effects empirically. CLARITY: 
      The paper is well written and easy to follow. ORIGINALITY: 
      I'm far enough from this domain that it's difficult to judge 
      originality. The sources of bias highlighted in the paper appear novel, as 
      do the bounds and solutions. SIGNIFICANCE: The paper 
      demonstrates two sources of bias in the search advertising task, corrects 
      them, and demonstrates the resulting improvement in utility for the 
      auctioneer. This should be a useful result to consider in future work in 
      this domain.