Risk-Constrained Budget Pacing for Guaranteed Display Advertising

Abstract: This work proposes a percentile risk‑constrained budget pacing algorithm for guaranteed delivery (GD) advertising. By linking the pacing rate to the percentile position of the dual bidding factor, the method respects the guaranteed volume allocation while preventing overly rapid budget depletion and improving delivery performance. The approach is described in a paper published at AAAI’24.

Background

GD contracts require delivering a fixed number of impressions to a target audience at a fixed price, with strong volume guarantees. Allocation typically uses dual‑mirror descent and virtual bids (bid = CTR – dual). Similar constraints appear in other limited‑resource scenarios such as limited push notifications or coupon allocations.

Modeling

Optimizing for CTR, the ad’s estimated value leads to a primal‑dual formulation. The virtual bid is derived from the dual variable, which is adjusted based on consumption speed via feedback mechanisms (e.g., PID).

Smoothing Challenge

Pure virtual‑bid control can cause non‑smooth spend: an ill‑chosen dual factor may exhaust an hour’s budget in minutes, or cause sudden “burst” impressions. This harms both business (uneven traffic) and performance (missed high‑quality traffic).

Technical Challenges & Design

Existing Methods

Bid Modification – indirect pacing, slow feedback, risky for small orders.

Probabilistic Throttling – simple but interferes with dual adjustment.

Regularization – fixed hyper‑parameters, not adaptive.

These do not fully address our needs.

Proposed Approach

Key ideas:

Keep the guaranteed allocation untouched.

Control the percentile of the dual factor within a safe threshold to limit risk.

Avoid discarding high‑quality traffic by preventing the dual percentile from being too low.

Bid‑to‑Percentile Transform

Scores are transformed to a uniform [0,1] percentile space using a Box‑Cox followed by standardization and the normal CDF. The dual factor is adjusted in percentile space and then inverse‑transformed back to the original scale.

PTR Estimation and Adjustment

Offline coarse estimation of the pacing‑through‑rate (PTR) is refined online with two exponential functions that increase or decrease the dual factor based on observed consumption versus expectation.

Weighted Bidding

Linear weighting in percentile space boosts high‑quality traffic without the scale issues of raw scores.

Gradient Clipping & Variable Step‑Size

Static and dynamic gradient clipping limits abrupt updates; step size varies with the dual percentile to balance stability and responsiveness.

Bleeding‑Control

A proportional “stop‑loss” module caps release speed to twice the target, preventing budget exhaustion during bursts.

Overall Workflow

Set global and ad‑level hyper‑parameters.

Offline compute baseline PTR and initial dual percentiles.

Online: predict scores, transform to percentile, adjust dual, compute bids, filter zero‑price, calculate final pacing probability, select top‑1 ad.

Near‑line control every two minutes updates dual via PID, applies gradient clipping and stop‑loss.

Results

Extensive A/B tests on daily traffic and major promotions (e.g., Double‑11) show that the algorithm achieves a good balance between smooth spend and performance uplift, improving conversion‑related metrics while keeping release smoothness.

References

Key related works include budget pacing for targeted ads (KDD 2014), dual mirror descent (PMLR 2020), smart pacing (KDD 2015), and others.