Online learning in repeated auctions

Abstract

Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive bidding strategies for two models: stochastic and adversarial. In the stochastic model, the observed values of the goods are random variables centered around the true value of the good. In this case, logarithmic regret is achievable when competing against well behaved adversaries. In the adversarial model, the goods need not be identical and we simply compare our performance against that of the best fixed bid in hindsight. We show that sublinear regret is also achievable in this case and prove matching minimax lower bounds. To our knowledge, this is the first complete set of strategies for bidders participating in auctions of this type.

Cited by in corpus (11)

• Attribution Modeling Increases Efficiency of Bidding in Display Advertising
• Logarithmic regret bounds for Bandits with Knapsacks
• Explicit shading strategies for repeated truthful auctions
• The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation
• Dynamic Pricing with Finitely Many Unknown Valuations
• Efficient Algorithms for Stochastic Repeated Second-price Auctions
• Distribution-free Contextual Dynamic Pricing
• On consistency of optimal pricing algorithms in repeated posted-price auctions with strategic buyer
• Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization
• Learning to Bid Without Knowing your Value
• Repeated Bidding with Dynamic Value