Improved Online Learning Algorithms for CTR Prediction in Ad Auctions
Zhe Feng Christopher Liaw Zixin Zhou
In this work, we investigate the online learning problem of revenue
maximization in ad auctions, where the seller needs to learn the click-through
rates (CTRs) of each ad candidate and charge the price of the winner through a
pay-per-click manner. We focus on two models of the advertisers' strategic
behaviors. First, we assume that the advertiser is completely myopic; i.e.~in
each round, they aim to maximize their utility only for the current round. In
this setting, we develop an online mechanism based on upper-confidence bounds
that achieves a tight $O(\sqrt{T})$ regret in the worst-case and negative
regret when the values are static across all the auctions and there is a gap
between the highest expected value (i.e.~value multiplied by their CTR) and
second highest expected value ad. Next, we assume that the advertiser is
non-myopic and cares about their long term utility. This setting is much more
complex since an advertiser is incentivized to influence the mechanism by
bidding strategically in earlier rounds. In this setting, we provide an
algorithm to achieve negative regret for the static valuation setting (with a
positive gap), which is in sharp contrast with the prior work that shows
$O(T^{2/3})$ regret when the valuation is generated by adversary.