Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising in Online Optimization

Liang Dai, Kejie Lyu, Chengcheng Zhang, Guangming Zhao, Zhonglin Zu, Liang Wang, Bo Zheng

Introduction

In online advertising, Guaranteed Display (GD) represents a contractual agreement where publishers guarantee a specific number of impressions to advertisers over a fixed period. Unlike the volatile environment of Real-Time Bidding (RTB), the primary challenge in GD is ensuring "smooth" ad delivery. Delivering a budget too quickly can lead to missed opportunities later in the day, while delivering too slowly risks failing to meet contractual obligations.

Current systems struggle with campaign diversity and traffic volatility. A campaign targeting a niche audience might have a very different predicted Click-Through Rate (CTR) distribution than a broad brand campaign. This paper introduces RCPacing, a robust framework designed to manage these challenges by shifting optimization from raw performance scores to a standardized percentile space.

The RCPacing Framework

The core innovation of RCPacing is the use of a Parametric Percentile Transformation. Raw predicted CTRs vary significantly across campaigns, making it difficult to apply uniform optimization parameters. RCPacing addresses this by applying a Box-Cox transformation to normalize performance data, which is then mapped into a percentile space ranging from 0 to 1.

Normalization of diverse performance distributions into a standardized percentile space.

This standardization allows the system to use consistent "dual variables"—internal price premiums—across all campaigns, regardless of their size or target audience. The framework integrates these components into a feedback control loop to maintain stable delivery.

The RCPacing framework architecture integrating percentile space and feedback control.

Key Methodological Components

  • Modified Itakura-Saito Divergence: Instead of standard Euclidean distance, RCPacing uses a modified Itakura-Saito divergence for mirror descent updates. This approach makes the algorithm more "cautious" in high-percentile regions where small changes in dual variables could cause non-smooth spikes in delivery.
  • Emergency PTR (ePTR) Module: This acts as a safety valve, using proportional control to quickly throttle campaigns that are spending too rapidly, preventing early budget depletion.
  • Adaptive Gradient Clipping: This restricts the magnitude of changes to a campaign's internal "price" in a single step, ensuring a stable competitive environment.

Key Insights: Risk and Smoothness

The authors identify a fundamental trade-off between smoothness and optimality. While picking only the highest-CTR users is optimal for performance, it often leads to erratic delivery. RCPacing provides a "knob"—the safety percentile upper bound ($P_{ub}$)—allowing publishers to tune this balance.

Furthermore, the research highlights the "risk" associated with high-percentile regions. Campaigns operating at the top end of their CTR distribution are more sensitive to environmental shifts; a minor change in traffic can cause their participation rate to fluctuate violently. By explicitly managing risk within the percentile space, RCPacing achieves much smoother delivery.

Experimental Evaluation

The researchers evaluated RCPacing using a large-scale industrial dataset from Alibaba (600,000 impressions, 300 GD ads) and through online A/B testing on the Taobao brand advertising platform.

Key Results

  • Offline Performance: Compared to the state-of-the-art PDOA method, RCPacing reduced the Unsmoothness Index (UI) by 59.4% while simultaneously increasing the average CTR by 23.1%.
  • Online Deployment: In live tests dealing with billions of daily requests, the system achieved a 35.3% improvement in smoothness and a 23.4% improvement in CTR.
  • Reliability: RCPacing maintained a delivery rate of nearly 100%, ensuring that all contractual obligations were met consistently.

Limitations and Future Work

While RCPacing offers significant improvements, its theoretical $O(\sqrt{T})$ regret bound relies on the assumption that user arrivals are Independent and Identically Distributed (IID). In highly adversarial or non-stationary environments, this theory may require further refinement. Additionally, the Box-Cox parameters currently rely on historical logs, which presents a "cold start" challenge for entirely new campaigns. Future research will explore extending this model to multi-slot scenarios where multiple ads compete for space on the same page.

Summary updated

Abstract

Guaranteed display (GD) advertising is a critical component of advertising since it provides publishers with stable revenue and enables advertisers to target specific audiences with guaranteed impressions. However, smooth pacing control for online ad delivery presents a challenge due to significant budget disparities, user arrival distribution drift, and dynamic change between supply and demand. This paper presents robust risk-constrained pacing (RCPacing) that utilizes Lagrangian dual multipliers to fine-tune probabilistic throttling through monotonic mapping functions within the percentile space of impression performance distribution. RCPacing combines distribution drift resilience and compatibility with guaranteed allocation mechanism, enabling us to provide near-optimal online services. We also show that RCPacing achieves O(sqrt(T)) dynamic regret where T is the length of the horizon. RCPacing's effectiveness is validated through offline evaluations and online A/B testing conducted on Taobao brand advertising platform.
BibTeX
@inproceedings{dai2024percentile,
  author = {Liang Dai and Kejie Lyu and Chengcheng Zhang and Guangming Zhao and Zhonglin Zu and Liang Wang and Bo Zheng},
  title = {{Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising in Online Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28636},
}
Figure