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.
As shown in Figure 1, the system operates via two distinct streams:
- 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.
- 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