Research map / Bandits and online learning / Online convex optimization and games
Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising in Online Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RCPacing, a risk-constrained percentile-space budget pacing method for guaranteed display ads that combines Lagrangian dual updates, probabilistic throttling, and modified Itakura-Saito mirror descent, with O(√T) dynamic regret and validation on offline data and Taobao A/B tests.
Problem
Smooth and robust budget pacing for guaranteed display (GD) advertising under budget disparities, user arrival distribution drift, and supply-demand changes, while maintaining near-optimal revenue for publishers.
Approach
Perform Lagrangian dual updates in a percentile space of the impression performance (CTR after Box-Cox and normal CDF transform), with probabilistic throttling (PTR) decoupled into base, performance-based, and emergency factors, plus adaptive gradient clipping and a modified Itakura-Saito Bregman divergence that shrinks step sizes near high percentiles.
Key results
- Offline: RCPacing unsmoothness 6.37 vs PDOA 15.70 and AUAF 12.95 (59.4% and 50.8% reductions), with CTR 7.46% vs 6.06% (PDOA) and 5.14% (AUAF) at 99.8% delivery rate.
- Online A/B test on Taobao for two weeks: 35.3% UI improvement and 23.4% CTR improvement over PDOA.
- Theory: O(√T) dynamic regret when horizon and initial resources scale proportionally.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RCPacing instead of PDOA | GD ad pacing · Offline evaluation | Unsmoothness: 59.4% reduction | Helped |
| Use RCPacing instead of AUAF | GD ad pacing · Offline evaluation | Unsmoothness: 50.8% improvement | Helped |
| Use RCPacing instead of PDOA | GD ad pacing · Offline evaluation | CTR: 23.1% increase | Helped |
| Use RCPacing instead of AUAF | GD ad pacing · Offline evaluation | CTR: 45.1% increase | Helped |
| Use RCPacing instead of Smart Pacing | GD ad pacing · Offline evaluation | CTR | Hurt |
| Use RCPacing instead of Smart Pacing | GD ad pacing · Offline evaluation | Delivery rate | Helped |
| Use RCPacing instead of PDOA | GD ad pacing · Taobao online A/B test | UI: 35.3% improvement | Helped |
| Use RCPacing instead of PDOA | GD ad pacing · Taobao online A/B test | CTR: 23.4% improvement | Helped |
| Increase P_ub from 90% to 95% (ablation) | RCPacing with Itakura-Saito divergence · Offline evaluation | Unsmoothness: 4.14% increase | Hurt |
| Use modified Itakura-Saito divergence instead of Euclidean divergence (ablation) | RCPacing · Offline evaluation, P_ub=90% | Unsmoothness: 3.74% improvement in smoothness | Helped |
| Set performance-based pacing slope k to 0 (ablation) | RCPacing · Offline evaluation | CTR: 7.46 -> 7.17 | Hurt |
| Set performance-based pacing slope k to 1000 instead of k=10 (ablation) | RCPacing · Offline evaluation | Unsmoothness: 6.37 -> 7.07 | Hurt |
Surprising findings
- Smart Pacing attains the highest offline CTR (7.88%) but only 95.9% delivery rate, which is unsuitable for guaranteed delivery.
Limitations
- Offline evaluation uses a single industrial dataset with predicted CTR as the quality score.
- Performance trade-off: higher percentile upper bound increases CTR but raises unsmoothness.
- Many hyperparameters (P_ub, epsilon, eta, clipping, WR_glb) are hand-tuned.
Experimental setup
Datasets: Taobao brand advertising logs (600K impressions, 300 GD ads, 50 time periods)
Benchmarks: RCPacing industrial offline dataset Taobao online A/B test
Metrics: unsmoothness index delivery rate average CTR
Baselines: DMD Smart Pacing AUAF PDOA
Builds on: Dual Mirror Descent Smart Pacing Balseiro et al. dual-based pacing
Closest papers by meaning
- Dynamic Budget Throttling in Repeated Second-Price Auctions (AAAI 2024 · similarity 0.87)
- Robust Budget Pacing with a Single Sample (ICML 2023 · similarity 0.85)
- Reserve Price Optimization for First Price Auctions in Display Advertising (ICML 2021 · similarity 0.84)
- Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising (AAAI 2017 · similarity 0.84)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.84)
- Maximizing the Success Probability of Policy Allocations in Online Systems (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.