The Library
Efficient regret bounds for online bid optimisation in budget-limited sponsored search auctions
Tools
Tran-Thanh, Long, Stavrogiannis, Lampros, Naroditskiy, Victor, Robu, Valentin, Jennings, Nicholas R. and Key, Peter (2014) Efficient regret bounds for online bid optimisation in budget-limited sponsored search auctions. In: UAI'14: Thirtieth Conference on Uncertainty in Artificial Intelligence, Quebec City, Quebec, Canada, 23-27 Jul 2014. Published in: UAI'14: Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence pp. 809-818. ISBN 9780974903910.
|
PDF
WRAP-efficient-regret-bounds-online-bid-optimisation-budget-limited-sponsored-search-auctions-Tran-Thanh-2014.pdf - Accepted Version - Requires a PDF viewer. Download (872Kb) | Preview |
Official URL: https://dl.acm.org/doi/10.5555/3020751.3020835
Abstract
We study the problem of an advertising agent who needs to intelligently distribute her budget across a sequence of online keyword bidding auctions. We assume the closing price of each auction is governed by the same unknown distribution, and study the problem of making provably optimal bidding decisions. Learning the distribution is done under censored observations, i.e. the closing price of an auction is revealed only if the bid we place is above it. We consider three algorithms, 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 at most O(T⅔) with high probability. For the other two algorithms, we first prove that, by using a censored data distribution estimator proposed by Zeng [19], the empirical distribution of the closing market price converges in probability to its true distribution with a O(1/√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 research question raised in [1]. We also evaluate 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 running time may limit its suitability in practice. By contrast, LuekerLearn and ε— First proposed 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).
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Stochastic analysis , Probabilities, Software engineering -- Management, Search engines -- Programming, Search engines, Intelligent agents (Computer software) | ||||||
Journal or Publication Title: | UAI'14: Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence | ||||||
Publisher: | IFAAMAS | ||||||
ISBN: | 9780974903910 | ||||||
Official Date: | July 2014 | ||||||
Dates: |
|
||||||
Page Range: | pp. 809-818 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | © ACM, 2014. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Tran-Thanh, Long, Stavrogiannis, Lampros, Naroditskiy, Victor, Robu, Valentin, Jennings, Nicholas R. and Key, Peter (2014) Efficient regret bounds for online bid optimisation in budget-limited sponsored search auctions. In: UAI'14: Thirtieth Conference on Uncertainty in Artificial Intelligence, Quebec City, Quebec, Canada, 23-27 Jul 2014. Published in: UAI'14: Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence pp. 809-818. ISBN 9780974903910. | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 22 July 2020 | ||||||
Date of first compliant Open Access: | 22 July 2020 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | UAI'14: Thirtieth Conference on Uncertainty in Artificial Intelligence | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Quebec City, Quebec, Canada | ||||||
Date(s) of Event: | 23-27 Jul 2014 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year