Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Efficient Regret Bounds for Online Bid Optimisation in Budget-Limited Sponsored Search Auctions
Long Tran-Thanh, Lampros Stavrogiannis, Victor Naroditskiy, Valentin Robu, Nicholas Jennings, Peter Key
Abstract:
We study the problem of an advertising agent who needs to intelligently distribute her bud- get across a sequence of online keyword bid- ding auctions. We assume the closing price of each auction is governed by the same un- known distribution, and study the problem of making provably optimal bidding deci- sions. Learning the distribution is done un- der censored observations, i.e. the closing price of an auction is revealed only if the bid we place is above it. We consider three al- gorithms, namely ε??First, Greedy Product- Limit (GPL) and LuekerLearn, respectively, and we show that these algorithms provably achieve Hannan-consistency. In particular, we show that the regret bound of ε??First is 2 at most O(T 3 ) with high probability. For the other two algorithms, we first prove that, by using a censored data distribution esti- mator proposed by Zeng [19], the empirical distribution of the closing market price con- verges in probability to its true distribution 1 with a O( ??t ) rate, where t is the number of updates. Based on this result, we prove ?? that both GPL and LuekerLearn achieve O( T ) regret bound with high probability. This in fact provides an affirmative answer to the re- search question raised in [1]. We also evalu- ate the abovementioned algorithms using real bidding data, and show that although GPL achieves the best performance on average (up to 90% of the optimal solution), its long run- ning time may limit its suitability in practice. By contrast, LuekerLearn and ε??First pro- posed in this paper achieve up to 85% of the optimal, but with an exponential reduction in computational complexity (a saving up to 95%, compared to GPL).
Keywords:
Pages: 809-818
PS Link:
PDF Link: /papers/14/p809-tran-thanh.pdf
BibTex:
@INPROCEEDINGS{Tran-Thanh14,
AUTHOR = "Long Tran-Thanh and Lampros Stavrogiannis and Victor Naroditskiy and Valentin Robu and Nicholas Jennings and Peter Key",
TITLE = "Efficient Regret Bounds for Online Bid Optimisation in Budget-Limited Sponsored Search Auctions",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "809--818"
}


hosted by DSL   •   site info   •   help