Campaign Budget Optimization at Rokt

By Dr. Andrew Chalk

On Rokt’s platform, advertisers bid to have their offers shown to customers who’ve completed transactions on one of our ecommerce partner sites. In doing so, these advertisers typically have a budget that they wish to spend over a defined time period. We noticed that advertisers were often exhausting their budget before the end of the budget period because they received too much volume and spent too much too early in the period.

Enter: Smart Budget.

Smart Budget is a tool developed by Rokt to help manage spending efficiently throughout the budget period. It adjusts an advertiser’s bid by spreading it over a longer period. This ensures that the advertiser’s budget doesn’t exhaust itself too early and manages to still achieve impressions and referrals later in the period.

The Problem

All too often, advertisers were seeing their budget exhausted before the end of their budget period. An example of this phenomenon is shown in the chart below, where a campaign’s impressions drop to zero between 2 and 3PM, indicating their daily budget was exhausted. The chart also indicates a large number of eligible sessions later in the day, which the campaign would’ve been eligible to compete for. However, as it spent too aggressively early within this initial period, it now has to remain dormant until the next day when its daily budget is refreshed.

This situation indicates that:

  1. The campaign is overspending on each click. It could reduce its bid price in order to improve efficiency while still spending its budget.
  2. The campaign misses out on opportunities to be seen later in the day when a more engaged audience may be available.
  3. Network efficiency as a whole can be impacted, as many more campaigns will be competing in the early hours of the day than in the evening.

This predicament hurts overall campaign performance. There are two main strategies to address this problem; allocation and bid modification. Allocation modifies the campaign’s eligibility. As the name suggests, bid modification adjusts the bid price for the advertising campaign. We have chosen the latter, as a lower price is more likely to improve campaign efficiency.

Rokt’s approach

In order to spread the budget across a longer time period we created a budget factor (bf) that, when multiplied by the campaign’s bid price, reduces how much the campaign will bid for that specific auction. Currently, the budget factor has an upper limit of 1 so that we never bid higher than the advertisers’ fixed bid or target CPA. However, it would be possible to remove this constraint to allow underspending campaigns to also meet their budget.

In order to determine the appropriate budget factor value, we made two assumptions about the effect of multiplying a bid price by a value (m).

  1. The number of clicks is proportional to m. A campaign that spends more will win more auctions, and therefore get more clicks. When the campaign is bidding in the range where the auction is competitive, we have found that this is a good approximation to reality. It’s only at the extreme bid prices that it breaks down.
  2. The cost per click (CPC) is also proportional to m. In a single-price auction, this is always true, but since Rokt uses a second-price auction (see our blog article Auction Mechanisms for details), it is approximately true when the auction is competitive.

Below are charts showing the relationship between m, clicks, and CPC. It can be seen that they are fairly close to linear.

Based on these two assumptions, we can conclude that spend, which is equal to the number of clicks * cost per click, is proportional to the square of m. The right chart above shows that this assumption is also reasonable.

We now define that budget factor as follows:

Where spend forecast is an estimate of what the campaign will spend in the remainder of the budget period in the absence of the budget factor.

Simply put, this formula says that if the campaign is over-pacing on spend by a factor X, we want to reduce its spend by the same factor. As shown above, spend is proportional to the square of m, so we have to take the square root so that the budget factor causes linear changes in spend.

Forecasting Spend

A key requirement of our approach is to be able to forecast spend. This forecast should take into account upward or downward trends and consider the appropriate seasonal variations. In order to do this, we use the Prophet time series model that allows multiple seasonalities to be defined. An example model is shown below.

The observed spend data in this model has been aggregated by hours and shows two types of seasonalities that are typical in advertising campaigns: daily and weekly. In addition, there is an upward trend. Since we are interested in forecasting spend without the effect of the budget factor, we need to reverse its effect on the observed data. This can be done simply by using the following formula:

Where bf is the budget factor that was in effect when click i occurred, and the paid price was its cost.

To calculate the spend forecast, we simply sum the forecasted results from “now” until the end of the budget period. Budget factors are calculated hourly and are then used in the Rokt auction to adjust bid prices in real-time.

Results

Although the approach we described is fairly simple, we have seen large efficiency gains for campaigns that use Smart Budget. The chart below shows the impressions per hour for the first day that Smart Budget was activated on a campaign (beetroot) and the day prior (gray). It is clear that the advertiser spend was successfully paced and the ad was shown throughout the entire day.

Below we show key performance metrics for the first day of Smart Budget versus the day prior.

SpendImpressionsClicksCost Per ClickAcquisitionsCPA
↓ 6%↑ 54%↑ 42%↓ 34%↑ 41%↓ 34%

There was an improvement of between 30 - 50% in key advertising metrics—despite the fact that a similar amount was spent on the two days.

Implementation

Since each campaign requires its own forecast, our implementation must be highly scalable. At the time this work was done, Rokt had recently begun experimenting with Kubeflow. This was an excellent opportunity to test how effectively it could scale Smart Budget. The chart below shows a high-level view of the Smart Budget architecture.

In order to maximize scalability and minimize the overhead of creating new Kubernetes pods, we use a combination of vertical and horizontal scaling to calculate spend forecasts. The ‘Chunk campaigns IDs’ step takes the list of campaigns running Smart Budget that is obtained by making an API call to our campaign management system. It then creates groups of campaign IDs having no more than N campaigns each. Each group runs in its own pod, which may or may not be on the same physical hardware, while each pod has M training jobs run in parallel using the multiprocessing Python library. Each forecast job writes its output to an Amazon S3 bucket and are gathered together and used to calculate the budget factors, which are subsequently written to S3 where they are available to Rokt’s auction system.

Rokt