Efficient Regret Bounds for Online Bid Optimisation in Budget-Limited Sponsored Search Auctions

Content Provider	Microsoft Research
Author	Tran-Thanh, Long Stavrogiannis, Lampros Naroditskiy, Victor Robu, Valentin Jennings, Nicholas R Key, Peter
Copyright Year	2014
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 ProductLimit (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 2) with high probability. For
Language	English
Publisher	uai2014, 30th Conf
Publisher Date	2014-07-01
Access Restriction	Open
Rights Holder	Microsoft Corporation
Subject Keyword	Algorithms theory
Content Type	Text
Resource Type	Proceeding