TL;DR
This paper introduces ROAM, a novel framework for optimizing ad allocation in sponsored search. ROAM simultaneously maximizes platform revenue and user experience while respecting advertiser ROI constraints, a critical but often overlooked aspect in prior work. Through a parameter-server based offline optimization and a clever online strategy, ROAM significantly boosts platform revenue and advertiser ROI, as validated by extensive offline and online A/B testing.
What Problem Does This Paper Address?
Sponsored search is a cornerstone of e-commerce revenue, where search engines display ads alongside organic results. The core challenge lies in "online allocation": deciding in real-time which ads to show for a given user query. Existing systems aim to maximize platform revenue, but this often comes at the expense of user experience, advertiser utility, or long-term platform health. A key gap is addressing advertiser Return on Investment (ROI) constraints, which are crucial for advertiser satisfaction and retention. Furthermore, the inherent conflict between offline allocation models (which might rank ads based on various factors) and the online auction mechanism (which typically uses eCPM) needs to be reconciled to ensure the allocation strategy effectively influences the final ad display. This paper tackles these issues by proposing a unified framework that balances platform revenue, user experience, and advertiser ROI, while also bridging the gap between offline optimization and online auction dynamics.
Methods
The proposed framework, ROAM (ROI constrained Optimal Allocation Model), has two main components:
- Offline Optimization:
- Constrained Optimization Formulation: The problem is framed as a constrained optimization problem on a bipartite graph, where supply nodes represent user search requests and demand nodes represent ad campaigns. The objective is to maximize platform revenue while minimizing impressions (to preserve user experience) and satisfying budget and ROI constraints for advertisers.
- Parameter-Server Architecture: To handle the large scale of sponsored search, a parallel optimization algorithm is developed using a parameter-server architecture. This allows for efficient computation of dual variables and allocation probabilities.
- Lagrangian Relaxation and KKT Conditions: The optimization problem is solved by deriving its dual problem using KKT conditions, leading to an iterative update of dual variables.
- Online Strategy:
- Conflict Resolution: A key innovation is the online strategy designed to bridge the gap between the offline allocation model's output and the online Generalized Second Price (GSP) auction. The allocation model determines an "optimal" ad, but this ad might not win the auction if it doesn't have the highest eCPM. To address this, ROAM reserves ads whose eCPM is lower than the predicted winning ad's eCPM to participate in the auction. This ensures that the allocation model's preference has a strong influence on the final ad selection, thereby maximizing platform revenue.
Datasets
The paper utilizes a real-world production dataset comprising:
- 1.2 million requests (supply nodes)
- 622 ad campaigns (demand nodes)
- Over 4.8 million edges in the allocation bipartite graph.
For offline evaluation, model-estimated CTR and CVR were used to represent true values, as actual click and conversion probabilities are unknown. The paper also mentions generating a synthetic dataset for hyper-parameter sensitivity analysis, based on a dataset from a previous study (Ref. [31]).
Key Insights and Ideas
- ROI as a First-Class Constraint: Explicitly incorporating advertiser ROI constraints into the allocation model is crucial for long-term platform health and advertiser satisfaction. Simply maximizing platform revenue can lead to advertiser churn if their ROI suffers.
- Balancing Revenue and User Experience: The model's objective function explicitly balances platform revenue with user experience (by minimizing impressions), acknowledging that a good user experience is vital for sustained engagement and future revenue.
- Bridging Offline Allocation and Online Auction: The proposed online strategy to reconcile the allocation model's output with the GSP auction mechanism is a significant practical contribution. It ensures that the offline optimization efforts translate into tangible improvements in the online serving environment.
- Parameter-Server for Scalability: The adoption of a parameter-server architecture is essential for tackling the massive scale of real-world sponsored search systems, enabling efficient distributed computation.
Key Results
- Offline Evaluation:
- ROAM achieved the highest ROI among all tested methods, significantly outperforming OAM (ROAM without ROI constraint).
- It maintained competitive performance in other metrics like Revenue, RPM, BCR, and GMV.
- The model converged within 1000 iterations for ROI and BCR metrics.
- Online A/B Testing:
- ROAM demonstrated stable and significant improvements in both platform RPM and advertiser ROI over a 7-day period.
- Crucially, ROAM was the only method that achieved a positive lift in RPM without sacrificing ROI.
- ODBC showed the highest RPM lift but at the cost of a significant drop in ROI.
- AUAF showed no significant lift in either RPM or ROI.
- Production Stability: The ROAM model has been running stably in production for over three months since its launch.
Limitations and Future Work
- Limitations:
- The paper notes that for offline evaluation, model-estimated CTR and CVR were used as proxies for true values, as these are inherently unknown.
- The paper doesn't explicitly detail limitations of the parameter-server architecture itself, but large-scale distributed systems inherently face challenges like network latency and synchronization.
- Future Work:
- The paper's conclusion suggests that the proposed model has made significant improvements, implying that further refinements and extensions are possible. However, specific future research directions are not explicitly detailed in the provided text. The focus is on the successful implementation and validation of the current ROAM framework.
Summary updated