An adaptive algorithm for selecting profitable keywords for search-based advertising services

ABSTRACT

Increases in online search activities have spurred the growth of search-based advertising services offered by search engines. These services enable companies to promote their products to consumers based on their search queries. In most search-based advertising services, a company sets a daily budget, selects a set of keywords, determines a bid price for each keyword, and designates an ad associated with each selected keyword. When a consumer searches for one of the selected keywords, search engines then display the ads associated with the highest bids for that keyword on the search result page. A company whose ad is displayed pays the search engine only when the consumer clicks on the ad. If the company's spending has exceeded its daily budget, however, its ads will not be displayed. With millions of available keywords and a highly uncertain clickthru rate associated with the ad for each keyword, identifying the most profitable set of keywords given the daily budget constraint becomes challenging for companies wishing to promote their goods and services via search-based advertising. Motivated by these challenges, we formulate a model of keyword selection in search-based advertising services. We develop an algorithm that adaptively identifies the set of keywords to bid on based on historical performance. The algorithm prioritizes keywords based on a prefix ordering-- sorting of keywords in a descending order of profit-tocost ratio (or "bang-per-buck"). We show that the average expected profit generated by the algorithm converges to near-optimal profits. Furthermore, the convergence rate is independent of the number of keywords and scales gracefully with the problem's parameters. Extensive numerical simulations show that our algorithm outperforms existing methods, increasing profits by about 7%.

REFERENCES

• 1: G. Aggarwal and J. D. Hartline, "Knapsack Auctions," Workshop on Sponsored Search Auctions, EC 2005.
• 2: Rajeev Agrawal, The Continuum-Armed Bandit Problem, SIAM Journal on Control and Optimization, v.33 n.6, p.1926-1951, Nov. 1995 [doi>10.1137/S0363012992237273]
• 3: Peter Auer , Nicolò Cesa-Bianchi , Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, v.47 n.2-3, p.235-256, May-June 2002
• 4: P. Auer, N. Cesa-Bianchi, Y. Freund, R. E. Schapire, "Gambling in a rigged casino: The adversarial multi-armed bandit problem," SODA 1995.
• 5: M-F. Balcan, A. Blum, J. D. Hartline, Y. Mansour "Sponsored Search Auction Design via Machine Learning," Workshop on Sponsored Search Auctions, EC 2005.
• 6: J. Chen, D. Liu, A. B. Whinston, "Designing Share Structure in Auctions of Divisible Goods," Workshop on Sponsored Search Auctions, EC 2005.
• 7: Brian C. Dean , Michel X. Goemans , Jan Vondrak, Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.208-217, October 17-19, 2004 [doi>10.1109/FOCS.2004.15]
• 8: Eyal Even-Dar , Shie Mannor , Yishay Mansour, PAC Bounds for Multi-armed Bandit and Markov Decision Processes, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.255-270, July 08-10, 2002
• 9: J. Goodman, "Pay-Per-Percentage of Impressions: An Advertising Method that is Highly Robust to Fraud," Workshop on Sponsored Search Auctions, EC 2005.
• 10: R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, "Optimization and approximation in deterministic sequencing and scheduling: A survey," Annals of Discrete Mathematics, 5:287--326, 1979.
• 11: B. J. Jansen and M. Resnick, "Examining Searcher Perceptions of and Interactions with Sponsored Results," Workshop on Sponsored Search Auctions, EC 2005.
• 12: B. Kitts, P. Laxminarayan, B. LeBlanc, R. Meech, "A Formal Analysis of Search Auctions Including Predictions on Click Fraud and Bidding Tactics," Workshop on Sponsored Search Auctions, EC 2005.
• 13: R. Kleinberg, "Online Decision Problems with Large Strategy Sets," Ph.D. disseration, MIT 2005.
• 14: R. Kleinberg, "Nearly tight bounds for the continuum-armed bandit problem," in NIPS 2005.
• 15: S. R. Kulkarni and G. Lugosi, "Finite-time lower bounds for the two-armed bandit problem," IEEE Trans. Aut. Control, pp. 711--714, 2000.
• 16: T. L. Lai and H. Robbins, "Asymptotically efficient adaptive allocation rules," Advances in Applied Mathematics, vol. 6, pp. 4--22, 1985.
• 17: S. Mannor and J. N. Tsitsiklis, "Lower bounds on the sample complexity of exploration in the multiarmed bandit problem," Sixteenth Annual Conference on Computational Learning Theory, pp. 418-432. Springer, 2003.
• 18: C. Meek, D. M. Chickering, D. B. Wilson, "Stochastic and Contingent-Payment Auctions," Workshop on Sponsored Search Auctions, EC 2005.
• 19: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
• 20: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 21: D. C. Parkes and T. Sandholm,"Optimize-and-Dispatch Architecture for Expressive Ad Auctions," Workshop on Sponsored Search, EC 2005.
• 22: D. Pollard, Convergence of Stochastic Processes, Springer Verlang, 1994.
• 23: Sartaj Sahni, Approximate Algorithms for the 0/1 Knapsack Problem, Journal of the ACM (JACM), v.22 n.1, p.115-124, Jan. 1975 [doi>10.1145/321864.321873]
• 24: M. Zinkevich, "Online convex programming and generalized infinitisimal gradient ascent," in Proceeding of the 20th International Conference on Machine Learning, pp. 928--936, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Economics, Performance, Theory

Keywords:
adaptive algorithms, multi-armed bandits, online optimization, search-based advertising