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 budget across a sequence of online keyword bidding 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 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 $\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 estimator proposed by Zeng [19], the empirical distribution of the closing market price converges 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 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 $\varepsilon$-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).

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 budget across a sequence of online keyword bidding 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 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 $\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 estimator proposed by Zeng [19], the empirical distribution of the closing market price converges 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 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 $\varepsilon$-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).}, 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 budget across a sequence of online keyword bidding 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 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 $\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 estimator proposed by Zeng [19], the empirical distribution of the closing market price converges 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 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 $\varepsilon$-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). %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