Bandits for Sponsored Search Auctions under Unknown Valuation Model: Case Study in E-Commerce Advertising

Danil Provodin, Jérémie Joudioux, Eduard Duryev

Abstract

This paper presents a bidding system for sponsored search auctions operating under an unknown valuation model. In this setting, the bidder's value is unknown, evolves arbitrarily, and is observed only upon winning an auction. Unlike previous studies, we do not impose restrictive assumptions on feedback nature, treating the bidding problem in its full generality. Our system utilizes a bandit framework resilient to black-box auction structures and delayed, batched feedback. We validate our solution through a case study at Zalando, a leading fashion e-commerce company, demonstrating promising outcomes in increasing profitability through strategic cost reduction.

Introduction

In the idealized world of auction theory, bidders possess perfect information regarding the value of an item. However, the reality of e-commerce advertising is significantly more complex. Advertisers face a "triple threat" of challenges: unknown valuations, where the true value of a click (e.g., a resulting sale) is only observed post-auction and evolves over time; black-box mechanics, where ad exchanges do not disclose exact auction rules (e.g., first-price vs. second-price); and feedback lag, where sales attribution can take days. This paper addresses the "learning-to-bid" problem without making restrictive assumptions about the auction environment or feedback mechanisms.

The BatchEXP3 Framework

The core of our approach is BatchEXP3, an adaptation of the classic Exponential weights for Exploration and Exploitation (EXP3) algorithm. Given the unpredictable and potentially non-truthful nature of ad auctions, we treat the environment as an adversarial bandit problem. This allows the system to remain robust without assuming specific reward distributions.

To bridge the gap between theoretical bandit algorithms and production-scale advertising systems, we implemented a desynchronized two-stream architecture.

System architecture of the proposed bidding system, illustrating the desynchronized two-stream process for bid placement and policy updates.

As shown in Figure 1, the system operates via two distinct streams:

  1. Stream 1 (High Frequency): Operates at a round frequency (e.g., every 3 hours), placing bids based on the current policy stored in the system.
  2. Stream 2 (Low Frequency): Operates at a batch frequency (e.g., daily), processing the performance measurement pipeline to attribute sales and update the policy module.

This architecture handles the inherent delays and batching of real-world data. Furthermore, the algorithm employs minimax normalization and traffic-ratio adjustments to ensure that rewards are comparable across different time periods and products.

Experimental Evaluation at Zalando

The system was evaluated through a three-month live test at Zalando, involving 180 clothing products selected based on a traffic threshold of at least 10 average daily clicks. The test utilized real-world production traffic, tracking clicks, costs, and attributed sales value from December 2022 to March 2023.

Results and Key Insights

The primary finding of the study was a consistent upward trend in partial profit following an initial exploration phase. Interestingly, this profitability was driven not by increased revenue, but by aggressive cost reduction. The bandit algorithm learned to identify and stop overbidding on products with poor cost-to-value ratios.

Key observations include:

  • Rational Bid Decrease: The system steered bids toward lower values 1.5 times faster than toward higher values. In environments with sparse feedback, this represents a rational survival strategy to avoid excessive costs.
  • Efficiency Gains: Products in the "profitable" group achieved revenue comparable to the "unprofitable" group while spending ten times less on bids.
  • Convergence: The effective bid space narrowed significantly as the system identified that bids exceeding 10 cents were rarely profitable for the items tested.

Challenges and Future Work

The study highlighted several technical challenges, particularly regarding sparse feedback. When conversions are rare, the cost term dominates the reward equation, potentially leading the algorithm to prematurely cease exploration for certain products. Additionally, hyperparameter sensitivity was a critical factor; a lower learning rate ($\eta = 0.1$) was necessary to prevent the learner from overreacting to noisy signals.

Future research will focus on adaptive computation of normalization bounds, exploring decreasing learning rate schedules (e.g., $\eta_t = 1/\sqrt{t}$), and improving performance for "cold start" or low-traffic products where the signal-to-noise ratio remains a significant hurdle.

Conclusion

By framing bidding as an adversarial bandit problem and implementing a robust two-stream architecture, we demonstrated that it is possible to navigate the complexities of real-world ad auctions effectively. The BatchEXP3 system provides a scalable solution for advertisers operating in environments with unknown valuations and black-box mechanics, prioritizing profitability through intelligent cost management.

Summary updated

Abstract

This paper presents a bidding system for sponsored search auctions under an unknown valuation model. This formulation assumes that the bidder's value is unknown, evolving arbitrarily, and observed only upon winning an auction. Unlike previous studies, we do not impose any assumptions on the nature of feedback and consider the problem of bidding in sponsored search auctions in its full generality. Our system is based on a bandit framework that is resilient to the black-box auction structure and delayed and batched feedback. To validate our proposed solution, we conducted a case study at Zalando, a leading fashion e-commerce company. We outline the development process and describe the promising outcomes of our bandits-based approach to increase profitability in sponsored search auctions. We discuss in detail the technical challenges that were overcome during the implementation, shedding light on the mechanisms that led to increased profitability.
BibTeX
@inproceedings{provodin2024bandits,
  author = {Danil Provodin and Jérémie Joudioux and Eduard Duryev},
  title = {{Bandits for Sponsored Search Auctions under Unknown Valuation Model: Case Study in E-Commerce Advertising}},
  booktitle = {Ecml/pkdd},
  year = {2024},
  doi = {10.1007/978-3-031-70381-2\_17},
}
Figure