Budget Optimization for Sponsored Search: Censored Learning in MDPs

Kareem Amin, Michael Kearns, Peter Key, Anton Schwaighofer
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:51-60, 2012.

Abstract

We consider the budget optimization problem faced by an advertiser participating in repeated sponsored search auctions, seeking to maximize the number of clicks attained under that budget. We cast the budget optimization problem as a Markov Decision Process (MDP) with censored observations, and propose a learning algorithm based on the wellknown Kaplan-Meier or product-limit estimator. We validate the performance of this algorithm by comparing it to several others on a large set of search auction data from Microsoft adCenter, demonstrating fast convergence to optimal performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-amin12a, title = {Budget Optimization for Sponsored Search: Censored Learning in MDPs}, author = {Amin, Kareem and Kearns, Michael and Key, Peter and Schwaighofer, Anton}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {51--60}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/amin12a/amin12a.pdf}, url = {https://proceedings.mlr.press/r10/amin12a.html}, abstract = {We consider the budget optimization problem faced by an advertiser participating in repeated sponsored search auctions, seeking to maximize the number of clicks attained under that budget. We cast the budget optimization problem as a Markov Decision Process (MDP) with censored observations, and propose a learning algorithm based on the wellknown Kaplan-Meier or product-limit estimator. We validate the performance of this algorithm by comparing it to several others on a large set of search auction data from Microsoft adCenter, demonstrating fast convergence to optimal performance.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Budget Optimization for Sponsored Search: Censored Learning in MDPs %A Kareem Amin %A Michael Kearns %A Peter Key %A Anton Schwaighofer %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-amin12a %I PMLR %P 51--60 %U https://proceedings.mlr.press/r10/amin12a.html %V R10 %X We consider the budget optimization problem faced by an advertiser participating in repeated sponsored search auctions, seeking to maximize the number of clicks attained under that budget. We cast the budget optimization problem as a Markov Decision Process (MDP) with censored observations, and propose a learning algorithm based on the wellknown Kaplan-Meier or product-limit estimator. We validate the performance of this algorithm by comparing it to several others on a large set of search auction data from Microsoft adCenter, demonstrating fast convergence to optimal performance. %Z Reissued by PMLR on 04 October 2026.
APA
Amin, K., Kearns, M., Key, P. & Schwaighofer, A.. (2012). Budget Optimization for Sponsored Search: Censored Learning in MDPs. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:51-60 Available from https://proceedings.mlr.press/r10/amin12a.html. Reissued by PMLR on 04 October 2026.

Related Material