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

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.

Introduction

In online advertising, Guaranteed Display (GD) contracts require publishers to deliver a specific number of impressions to advertisers for a fixed price. A primary challenge in fulfilling these contracts is budget pacing: delivering ads too quickly risks missing high-quality traffic later in the day, while being too selective risks under-delivery. This balancing act is complicated by traffic volatility, diverse campaign scales, and distribution drift in user performance metrics like Click-Through Rate (CTR).

Existing methods often struggle to maintain delivery smoothness while optimizing for performance. Researchers from Alibaba have developed RCPacing, a framework that addresses these issues by shifting the optimization problem into a standardized percentile space. This approach manages the risk of overspending while achieving near-optimal ad performance, resulting in a 35% improvement in delivery smoothness on the Taobao platform.

Methodology: The RCPacing Framework

RCPacing builds upon the Dual Mirror Descent (DMD) algorithm, introducing several key innovations to enhance robustness and smoothness.

The RCPacing system architecture, showing the integration of percentile space mapping into the feedback control loop for budget pacing.

The core components of the framework include:

  • Parametric Percentile Transformation: To handle skewed and inconsistent CTR distributions across different campaigns, the system employs a Box-Cox transformation. This maps raw performance scores into a standard normal distribution and subsequently into a unified percentile space (0 to 1).
  • Risk-Constrained Control: The authors identify that campaigns operating in high-percentile ranges are highly sensitive to distribution drift. RCPacing constrains dual variables within a "low-risk" region to prevent runaway spending.
  • Decoupled Pacing Rate: The probability of showing an ad is determined by three factors: a baseline statistical rate, a fine-tuning factor for real-time performance, and a factor that prioritizes high-quality traffic.
  • Emergency Intervention (ePTR): A fail-safe module designed to prevent budget exhaustion during "cold starts" or unexpected traffic surges.
  • Modified Bregman Divergence: The system utilizes Itakura-Saito divergence for variable updates, reducing "jitter" in high-performance traffic segments.

Key Insights: The High-Percentile Trap

A central insight of this work is the "High-Percentile Trap." Mathematical analysis and empirical observation show that campaigns targeting the top tier of the performance distribution are disproportionately affected by minor shifts in traffic.

Illustration of the 'High-Percentile Trap': small shifts in the performance distribution lead to disproportionately large changes in the Participation Rate (PR), especially at higher percentiles.

As shown above, a small shift in the threshold (x) can lead to a massive relative change in the Participation Rate (PR). For instance, in a Beta(2,8) distribution, a shift of 0.1 can increase the PR from 1.0% to 4.2%. By mapping all campaigns into a unified 0-to-1 percentile space, RCPacing can apply a consistent risk management strategy regardless of campaign size or target audience. Furthermore, the authors prove that RCPacing achieves a dynamic regret of $O(\sqrt{T})$, ensuring its performance remains close to the theoretical offline optimum over time.

Experimental Results

The effectiveness of RCPacing was evaluated using an industrial dataset of 600,000 impressions from Alibaba and through online A/B testing on the Taobao brand advertising platform.

Offline Evaluation

In offline tests, RCPacing significantly improved delivery smoothness. It achieved an Unsmoothness Index (UI) of 6.37, compared to 15.71 for standard DMD, while maintaining a near-perfect delivery rate of 99.8%.

Online A/B Testing

During a two-week online test on Taobao, RCPacing outperformed the existing PDOA method across key metrics:

  • 35.3% improvement in smoothness (UI).
  • 23.4% improvement in average CTR, indicating higher quality ad placements.

Conclusion and Future Work

RCPacing provides a robust solution for budget pacing in GD advertising by leveraging percentile-based risk constraints. While highly effective, the system's performance depends on hyper-parameters that may require periodic tuning and historical data for accurate mapping. Future research will explore non-linear mapping functions to further refine the trade-off between delivery smoothness and performance optimality.

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