Control Design for Pacing Advertising Budgets

Here at Quantcast we focus not just on building the best models to predict which users we should serve impressions to, but also on how to pace the rate at which we serve those impressions. Why is this important? Imagine you’re a client interested in creating an ad campaign to run for a 30-day period using Quantcast Advertise. One of the expectations you might have is that the budget for your campaign be spent uniformly over the contracted time period (as opposed to say, spending your entire budget in the first hour the campaign goes live). We have found that the most effective way to ensure smooth delivery of an ad campaign over its lifetime is by using feedback control, which is a system that uses measurements of past behavior to make decisions about future behavior.

Of course, the world of real-time advertising always adds unique complexities to problems such as these. On the one hand, we need a system agile enough to regulate the pace of delivery and stabilize our bid price on the real-time bidding (RTB) exchange. This requires a control system that can manage high frequency measurement and control updates (on a scale of minutes to seconds). On the other hand, we need a system capable of making sophisticated decisions about how to allocate spend and achieve the best performance at an efficient operating cost. This requires a control system designed for low frequency measurement and control updates (on a scale of hours to days).

In this blog post, I will share with you how we at Quantcast have tackled this issue by repurposing a technology most commonly used in complex industrial processes like chemical plant control and robotic manufacturing systems. This technology, known as cascade control, addresses a key challenge we face with pacing advertising budgets: how can we make sophisticated decisions on the best pacing strategy for a campaign and ensure that strategy is actualized on the RTB exchange? To motivate this approach we will explore how the problem of pacing advertising budgets naturally decomposes into a control structure with multiple layers, each operating on a different time scale. We will then discuss key advantages to this design and control laws that are appropriate at each layer of the system.

What are our operational objectives?

To begin, let’s look at an example of a typical client contract: Consider an ad campaign with a cost-per-impression (CPM) pricing model, where the goal is to deliver a specific number of impressions at a fixed cost over a contracted time period. The client will be measuring campaign performance in terms of cost-per-acquisition (CPA) and expects, among other things, that impressions will be delivered uniformly over the campaign’s lifetime.
Next, let’s look at the control objectives for this campaign:

• At the highest level, we are interested in achieving the best performance for our client, while also ensuring that we deliver the contracted impression budget in full. Delivering a contract in full is incredibly important, since it reflects on the effectiveness of the client’s marketing strategy. Note that this objective requires computing a delivery plan that spans the lifetime of the campaign.
• In addition, we’d like the impression budget to be uniformly allocated day over day, perhaps with some skew towards the beginning of the month, when market conditions are more favorable. Uniform delivery day-over-day is an important expectation of our clients, because it ensures their money is being spent in a calm and predictable manner. This smoothness is modeled at a daily rate because that is the resolution of reports from third-party ad-servers that our clients use to monitor delivery.  
• Once we establish our daily delivery schedule, we need to consider how we can deliver these targets at an efficient operating cost. Since we know there are more bidding opportunities in the middle of the day compared to the middle of night, we will want to set a pacing schedule that takes this time-of-day variation into account. This ensures we won’t pay too much for impressions in the middle of the night, and too little for impressions in the middle of the day.
• At the highest frequency of our system — minutes to seconds — our objective is to attenuate disturbances which arise from rapidly fluctuating market conditions on the RTB exchange. These fluctuations can come from many sources. Entire exchanges can appear or disappear suddenly, our competitors can influence demand in drastic ways, or our own systems might experience a failure mode. Events such as these will lead to unexpected changes in inventory and/or sporadic price jumps. We must have a system that is agile enough to adjust our bid price so that we are always buying impressions at a steady rate, even in the presence of uncertain market conditions. Based on practical observations we know these disturbances occur on the scale of seconds to minutes. Any higher frequency fluctuations are considered negligible.

See Table 1 for a summary of our operational objectives and their respective timescales.

Table 1: A summary of our operational objectives at various timescales

What does the control configuration look like?
Now that we’ve outlined the objectives for pacing an ad campaign, let’s look at how we should configure the control system. A naive approach might be to construct a single feedback loop that optimizes all the objectives simultaneously. But since we are using a single feedback loop, we must also use a single timescale. This means we have two options. The first is to model on a low-frequency timescale and compute pacing schedules efficiently. Of course this means the controller will not be responsive enough to compensate disturbances in the real-time marketplace. Option two is to model on a high-frequency timescale and maintain responsiveness, but we will have to track our error across an extremely long horizon (days to weeks). This approach will not be scalable.

As it turns out, we can accomplish all our objectives without having to make a tradeoff between scalability and accuracy. Instead of designing a single large controller, we can decompose the control system into specific layers that will allow for the tuning of a collection of sub-controllers without the need for a detailed model describing the dynamics and interactions between each layer. See Fig. 1 below for details. We will treat the outputs of the slower (outer) loops as a reference signal inputs to the faster (inner) loops. This configuration, known as cascade control, resolves our scalability vs. accuracy tradeoff. We can now design one sub-controller (or set thereof) responsible for planning across a long horizon at low frequencies and another sub-controller responsible for attenuating disturbances at high frequencies.

Mind you, it’s rather amazing that this design works. Feedback loops feeding into other feedback loops sounds like a recipe for unstable behavior, but there are two key reasons why this system is successful:

• The inner loop has influence over the outer loop(s). Our innermost loop ensures we are buying impressions at a steady rate on the RTB exchange, essentially isolating nonlinear behavior from the outer loops. This enables our primary (outer) process to behave in a predictable and repeatable way.
• The inner loop is faster than the outer loop(s). A general rule of thumb is that the inner loop must be three to four times faster than the outer loop, so that it has enough time to compensate for disturbances before they affect the primary process. Thus our timescale separation of month/week/day/hour/minute/second is appropriate for cascade control.

Regulatory control layer
Let’s take a closer look at these sub controllers and discuss their properties. We begin with the innermost loop, called the regulation layer. The purpose of this layer is to stabilize the process we are trying to control (namely, the amount of inventory we are buying) using low complexity controllers (PID control, for example) such that 1) this process does not drift too far from its nominal operating point and 2) the supervisory layer can handle the effect of disturbances of the primary outputs. This sub-controller responds to rapid market fluctuations on the RTB exchange and attenuates disturbances in delivery before the slower control loops notice any effect. So how does this signal actually affect the campaign?  In order to control how often ads are shown, we must design a control element that can adjust the bid price such that we win enough impressions to meet the desired targets. If we are under delivering, this signal encourages us to bid on a broader range of cookies and/or pay more per bid. If we are over delivering, this signal forces us to bid on only the highest scoring cookies and/or decrease the bid price.

Supervisory control layer

We’ve purposefully designed the regulatory control layer on a short planning horizon, so we will need a supervisory layer that will guide this controller along an optimal trajectory to meet the long term objectives. In this case, an optimal trajectory is one that accounts for the strong time-of-day variation we see over a 24 hour period. If we were to send a constant-valued reference signal from the supervisory to the regulation layer, the control signal in the regulation layer would have to continually adjust against varying market conditions. This makes sense because meeting this reference will likely be too difficult at 3am, and will be too easy at 3pm. Thus, the supervisory controller must calculate a reference signal that has an intraday demand pattern encoded in it. Note this demand pattern is unique to each campaign; for example a campaign for pizza likely sees much more traffic in the evening, whereas a campaign for pancakes may see more traffic in the morning.

Optimization control layer

At the highest level, we have the optimization layer, which is designed to assess a campaign’s performance limits and produce a delivery schedule which meets the contractual obligations at the most efficient cost. This involves determining if constraints are active and making parameter adjustments to ensure a campaign’s delivery goals are always feasible. The optimization layer also provides an opportunity to examine performance on a portfolio level (e.g., by looking at aggregate behavior of groups of campaigns) and allocating resources efficiently across that portfolio. As the name suggests, optimal control design works very well here, since we are modeling system dynamics at a slower timescale and have a lengthier SLA to provide updates.

Summary

In this post we’ve presented a discussion not just of the control algorithms we use to manage the delivery of campaigns, but of the actual structure of the control system. This system naturally decomposes into a set of sub-controllers, each operating at different timescales. This cascading control design enables us to build sophisticated pacing schedules and actualize them on the RTB exchange in a robust and scalable manner. By pacing advertising campaigns with this system we are able to achieve the best performance for our customers at an efficient operating cost. Further details about this control design, like how to scale this system across thousands of campaigns, will be discussed in a future blog post.