Source-linked AI summary
Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising
Kuang-Chih Lee, Ali Jalali, Ali Dasdan
TL;DR
Real-time bidding must balance campaign performance with smooth budget delivery despite rare conversions and delayed feedback. This paper adapts spending and bids using prior performance distributions, and reports consistent CPC and CPA improvements in campaign evaluations.
Problem
Rare conversions and delayed feedback make it challenging to optimize campaign performance while meeting smooth budget-delivery constraints.
Source: §1 · p. 1, §2.1 · p. 3Method
An online control loop estimates future spending, then uses the spending rate to select high-quality impressions and adapt bid prices from prior performance distributions.
Source: §1 · p. 2Results
The algorithm consistently improved CPC and CPA in simulated and real campaigns without underpacing or overpacing; 20 dynamic campaigns averaged 19.02% lift for CPC campaigns and 30.87% for CPA campaigns.
Source: §5.2 · p. 11, §6 · p. 12Takeaways & Limitations
The simple implementation handles up to a million ad requests per second, and the authors identify real-time analytics across more user, publisher, and advertiser attributes as future work.
Source: §6 · p. 12The spending model assumes impression prices remain approximately constant within a time slot, whose length should be chosen to keep price variance small.
Source: §3.1 · p. 5
Abstract
from arXiv · showhide
Today, billions of display ad impressions are purchased on a daily basis through a public auction hosted by real time bidding (RTB) exchanges. A decision has to be made for advertisers to submit a bid for each selected RTB ad request in milliseconds. Restricted by the budget, the goal is to buy a set of ad impressions to reach as many targeted users as possible. A desired action (conversion), advertiser specific, includes purchasing a product, filling out a form, signing up for emails, etc. In addition, advertisers typically prefer to spend their budget smoothly over the time in order to reach a wider range of audience accessible throughout a day and have a sustainable impact. However, since the conversions occur rarely and the occurrence feedback is normally delayed, it is very challenging to achieve both budget and performance goals at the same time. In this paper, we present an online approach to the smooth budget delivery while optimizing for the conversion performance. Our algorithm tries to select high quality impressions and adjust the bid price based on the prior performance distribution in an adaptive manner by distributing the budget optimally across time. Our experimental results from real advertising campaigns demonstrate the effectiveness of our proposed approach.
1 Introduction
Real-time bidding requires advertisers to assess individual ad requests quickly while pursuing performance goals under smooth budget-delivery constraints. The paper proposes an online approach that adapts spending and bids to balance those goals despite delayed, sparse feedback.
1 Introduction
- RTB exchanges let advertisers bid on individual impressions in public auctions, requiring DSPs to evaluate requests in milliseconds at high throughput.The passage describes processing close to a million ad requests per second.Source: §1 · p. 1
- Smooth delivery limits how much of the budget can be spent before a set time, helping avoid premature exhaustion and bursty spending.Advertisers also use it to reach a broader audience over the day.Source: §1 · p. 1
- Delayed feedback and rare click or conversion events make real-time performance estimates challenging.View-through actions may take up to seven days to be converted and attributed.Source: §1 · pp. 1–2
- The approach uses a control feedback loop to estimate future spending, then selects high-quality impressions and adjusts bids using prior performance distributions.The spending rate is used to optimize campaign performance while satisfying smooth delivery constraints.Source: §1 · p. 2
2 Background and Related Work
The section frames smooth-budget bid optimization as sequential decisions under time-slot spending limits, then surveys why traffic and performance variation complicate pacing and why several prior approaches do not fit RTB practice.
2.1 Problem Setup
- Uniform pacing can misallocate budget when relevant traffic varies over the day, while pacing to performance peaks may create fluctuations that threaten smooth delivery.Uniform pacing may leave budget undelivered or force purchases of lower-quality impressions later in the day.Source: §2.1 · p. 3
- The section identifies premature budget exhaustion and fluctuating spend as delivery concerns, and proposes addressing traffic and performance balance together.The proposed scheme is intended to resolve both issues under smooth delivery constraints.Source: §2.1 · pp. 2–3
- The online setup represents each request as a bid-or-not decision under a daily budget divided into time-slot limits, with future request values and costs unknown at decision time.In dynamic campaigns, the bid price must also be estimated; the amount bid differs from the cost paid in a second-price auction.Source: §2.1 · pp. 2–3
2.2 Related Work
- Zhou et al. use an exponential time-based selection strategy, but its unlimited-supply assumption is impractical for campaigns with strict audience targeting.Source: §2.2 · p. 4
- Babaioff et al. use an upper-confidence-bound bandit approach without prior-distribution information, but it needs rapid feedback unavailable in display RTB.Source: §2.2 · p. 4
- Agrawal et al. [3] recompute dual solutions as new instances arrive, but unknown request values and costs make frequent recomputation computationally costly in RTB.Source: §2.2 · p. 4
3 Online Bid Optimization
The section formulates online bidding for flat- and dynamic-CPM campaigns under smooth-delivery constraints, then uses pacing and performance estimates to guide impression selection and bids.
3 Online Bid Optimization
- Flat- and dynamic-CPM campaigns optimize campaign goals subject to daily-budget, smooth-delivery, and eCPM-cap constraints.For dynamic CPM, the eCPM cap makes the campaign appear CPM-like on average.Source: §3 · p. 4
3.1 Smooth Delivery of Budget
- A feedback controller sets next-slot pacing from prior spend and predicted requests and win rate, while historical event rates direct more budget to promising slots.The performance-based schedule can combine with uniform pacing so zero-probability slots still receive exploration budget.Source: §3.1 · pp. 5–6
- Uniform pacing allocates the remaining budget by the next slot’s share of the remaining day, with a simplified formula for equal-length slots.The schedule is based on the remaining budget and the ratio of next-slot duration to remaining time.Source: §3.1 · p. 5
3.2 Selection of High Quality Ad Requests - Flat CPM Campaigns
- For each campaign, an empirical historical CTR or AR histogram informs a threshold: requests above its upper bound are kept, below its lower bound dropped, and those between sampled at pacing rate.The bounds use incrementally updated online mean and variance, assuming τ(t) is Gaussian. γ = 1.96 gives a 95% confidence interval.Source: §3.2 · p. 7
3.3 Selection of High Quality Ad Requests - Dynamic CPM Campaigns
- For dynamic CPM, the base bid is predicted AR multiplied by the CPA goal, while pacing-rate regions determine whether the campaign uses that bid or adjusts it.The method distinguishes safe, critical, and danger regions according to pacing rate and delivery status.Source: §3.3 · p. 7
- In the safe region, auction-price history for action-producing impressions informs lower bids; in the danger region, bids rise when auction wins, rather than targeting, constrain delivery.The safe-region approach can improve performance while reducing spend; the danger-region boost addresses bids too low to win impressions.Source: §3.3 · p. 8
3.4 Estimation of CTR and AR
- AR estimates aggregate impressions and actions through advertiser, publisher, and user feature hierarchies, then smooth estimates and apply logistic regression along each leaf-to-root path.The method builds raw estimates at hierarchy nodes before smoothing and fitting the regression for leaf triplets.Source: §3.4 · p. 8
4 Practical Issues
The section describes practical measures for starting campaigns with sparse feedback, preventing overspend, and processing bids at RTB scale.
4 Practical Issues
- The practical-issues section introduces implementation challenges and the solutions used in the deployed system.These include cold start, overspending, and distributed processing.Source: §4 · p. 9, §4.1 · p. 9, §4.2 · p. 9
4.1 Cold Start Problem
- With delayed click or conversion feedback, cold-start campaigns use campaign similarities to recommend sites and audiences, then explore while data accrue.Contextual-epsilon-greedy bidding raises bids for recommended groups and randomly explores others at a default bid; exploration decreases as the campaign ages.Source: §4.1 · p. 9
4.2 Prevention of Overspending
- Monitoring stops a campaign if total spend exceeds daily budget B and pauses bidding when a time-slot spend exceeds bt + δ.Bidding resumes in the next time slot after an interval overspend.Source: §4.2 · p. 9
4.3 Distributed Architecture
- The bid workflow must finish in under 50 milliseconds while processing close to a million requests per second, so it runs across distributed clusters and data centers.Offline training uses R, Pig, and Hadoop; online requests stream to servers and bids are evaluated via a real-time message bus.Source: §4.3 · pp. 9–10
5 Experimental Results
The experiments compare pacing in simulation and evaluate the bid-optimization framework on flat- and dynamic-CPM campaigns. Reported results include CTR lift for flat-CPM campaigns and CPC and CPA performance lifts for dynamic-CPM campaigns.
5.1 Comparison of Pacing Strategies
- 0.56 dollars was the average difference between ideal and actual uniform spend, less than 1% of daily budget; performance-based pacing differed by 0.17 dollars, about 2.3%.The performance-based actual spend followed the ideal curve based on the relative performance across time slots.Source: §5.1 · p. 10, Figure 6 · p. 11, Figure 5 · p. 11
5 Experimental Results
- The evaluation used CTR for flat-CPM campaigns and CPC or CPA for dynamic-CPM campaigns; lower CPC and CPA indicate better performance.The framework was implemented and deployed in Turn, and the experiments included simulation and real campaigns.Source: §5 · p. 10, §5.2 · p. 11
5.2 Evaluation of Real Campaign Performance
- 123% average CTR performance lift was reported across seven active flat-CPM campaigns compared with the adaptive-feedback baseline.The campaigns were randomly selected across advertiser categories; each method ran for one week, with two weeks of data collected.Source: §5.2 · p. 11
- 19.02% average performance lift for CPC campaigns and 30.87% for CPA campaigns were reported across 20 selected dynamic-CPM campaigns.All 20 were reported to perform better on their respective cost metric than the pacing-only baseline.Source: §5.2 · p. 11, Table 2 · p. 12, Table 3 · p. 12
6 Conclusions
The conclusion presents a real-time approach for bid optimization under budget and smooth-delivery constraints. Simulated and real-campaign evaluations show consistent CPC and CPA improvements without underpacing or overpacing.
6 Conclusions
- The approach handles up to a million ad requests per second in its current implementation, and the authors think it can scale further.The algorithm is described as general and straightforward for real-time campaign bid optimization under budget and smooth-delivery constraints.Source: §6 · p. 12
- Simulated and real-campaign evaluations show consistent CPC and CPA improvements without underpacing or overpacing.Source: §6 · p. 12
- Future work would add real-time analytics for online optimization across more user, publisher, and advertiser attributes.Source: §6 · p. 12