Efficient Regret Bounds for Online Bid Optimisation in BudgetLimited Sponsored Search Auctions
Long TranThanh, 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 Hannanconsistency. 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: 809818
PS Link:
PDF Link: /papers/14/p809tranthanh.pdf
BibTex:
@INPROCEEDINGS{TranThanh14,
AUTHOR = "Long TranThanh
and Lampros Stavrogiannis and Victor Naroditskiy and Valentin Robu and Nicholas Jennings and Peter Key",
TITLE = "Efficient Regret Bounds for Online Bid Optimisation in BudgetLimited Sponsored Search Auctions",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "809818"
}

