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
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:479-488, 2014.

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 $\varepsilon$-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 $\varepsilon$-First is at most O(T 2 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 with a O( 1 $\sqrt{}$ t) rate, where t is the number of updates. Based on this result, we prove that both GPL and LuekerLearn achieve O( $\sqrt{}$ 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 $\varepsilon$-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).

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-tran-thanh14a, title = {Efficient Regret Bounds for Online Bid Optimisation in Budget-Limited Sponsored Search Auctions}, author = {Tran-Thanh, Long and Stavrogiannis, Lampros and Naroditskiy, Victor and Robu, Valentin and Jennings, Nicholas and Key, Peter}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {479--488}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/tran-thanh14a/tran-thanh14a.pdf}, url = {https://proceedings.mlr.press/r12/tran-thanh14a.html}, 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 $\varepsilon$-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 $\varepsilon$-First is at most O(T 2 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 with a O( 1 $\sqrt{}$ t) rate, where t is the number of updates. Based on this result, we prove that both GPL and LuekerLearn achieve O( $\sqrt{}$ 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 $\varepsilon$-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).}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Efficient Regret Bounds for Online Bid Optimisation in Budget-Limited Sponsored Search Auctions %A Long Tran-Thanh %A Lampros Stavrogiannis %A Victor Naroditskiy %A Valentin Robu %A Nicholas Jennings %A Peter Key %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-tran-thanh14a %I PMLR %P 479--488 %U https://proceedings.mlr.press/r12/tran-thanh14a.html %V R12 %X 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 $\varepsilon$-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 $\varepsilon$-First is at most O(T 2 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 with a O( 1 $\sqrt{}$ t) rate, where t is the number of updates. Based on this result, we prove that both GPL and LuekerLearn achieve O( $\sqrt{}$ 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 $\varepsilon$-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). %Z Reissued by PMLR on 04 October 2026.
APA
Tran-Thanh, L., Stavrogiannis, L., Naroditskiy, V., Robu, V., Jennings, N. & Key, P.. (2014). Efficient Regret Bounds for Online Bid Optimisation in Budget-Limited Sponsored Search Auctions. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:479-488 Available from https://proceedings.mlr.press/r12/tran-thanh14a.html. Reissued by PMLR on 04 October 2026.

Related Material