Adaptive bidding for display advertising

ABSTRACT

Motivated by the emergence of auction-based marketplaces for display ads such as the Right Media Exchange, we study the design of a bidding agent that implements a display advertising campaign by bidding in such a marketplace. The bidding agent must acquire a given number of impressions with a given target spend, when the highest external bid in the marketplace is drawn from an unknown distribution P. The quantity and spend constraints arise from the fact that display ads are usually sold on a CPM basis. We consider both the full information setting, where the winning price in each auction is announced publicly, and the partially observable setting where only the winner obtains information about the distribution; these differ in the penalty incurred by the agent while attempting to learn the distribution. We provide algorithms for both settings, and prove performance guarantees using bounds on uniform closeness from statistics, and techniques from online learning. We experimentally evaluate these algorithms: both algorithms perform very well with respect to both target quantity and spend; further, our algorithm for the partially observable case performs nearly as well as that for the fully observable setting despite the higher penalty incurred during learning.

REFERENCES

• 1: 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 [doi>10.1023/A:1013689704352]
• 2: Matthew Cary , Aparna Das , Ben Edelman , Ioannis Giotis , Kurtis Heimerl , Anna R. Karlin , Claire Mathieu , Michael Schwarz, Greedy bidding strategies for keyword auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250949]
• 3: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 4: A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Annals of Mathematical Statistics, 27(3):642--669, 1956.
• 5: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 6: M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, 2003.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
adaptive bidding, concentration bounds, display advertising, guaranteed delivery, guess-then-double algorithms