Datacratic Website  |  1-877-397-9484

Peeking Into The Black Box Series: Part 1 - RTB Pacing, Is Everyone Doing it Wrong?


Sep 8, 2011, By Datacratic
|0 comments

This is the first blog post in a series that examines key theories and concepts about Real-Time Bidding (RTB), and how Datacratic leverages these items as part of our RTB strategies. In this post, we take a look at how we apply control theory to pace our spending.

Here is a basic problem: if someone gives you a fixed amount of money to run a display advertising campaign over a specific time period, it's generally advisable to spend exactly that amount of money, spread out reasonably evenly over that time period. Overspending could mean you're on the hook for the difference, and under-spending doesn't look great if you want repeat business. And if you don't spend it evenly, you might get some angry customers, and end up in situations where you could potentially spend all your budget in minutes.

Sounds obvious, right? Apparently, it's harder than it looks!

 

Doing it wrong

When Datacratic first dipped its toe into RTB, the main tool at our disposal to control budget/pacing was a daily spending cap. It took about 48 hours for us to figure out that this wasn't going to work for us. Depending on the types of filters we used to decide when to bid at all, we'd either not manage to spend the daily budget (more on that at the bottom) or blow the budget very quickly, usually the latter. In practice, this meant that we would start buying impressions at midnight (all times in this post are in Montreal local time: EST or EDT), and generally hit our cap mid-morning.

dailycap.png No bidding occurs after daily cap is reached

Image source: nicolas.kruchten.com 

 

On a daily spend graph over a 30 to 60-day period resulting from such a policy, this would probably look just fine: you're spending the budget in the time given, and spending exactly the right amount per day. But having this sort of 'dead time' where we don't bid at all bothered us, so as soon as we spun up our own bidder, we added options like "bid on X% of the request stream". When we looked at the resulting data, we noticed something really interesting: the impressions we were buying before were actually among the most expensive of the day!

The average win-price graph below (i.e. what the next-highest bid was to our winning one) from a high-bidding campaign shows a clear pattern: if you start at noon, the dollar cost for one thousand impressions (the CPM) generally drops until precisely midnight, then jumps something like 40%. It fluctuates a bit, hits a high in the morning and then drops down again until noon to start the cycle again. This pattern repeats day after day:

prices.png Notice the discontinuous jumps every midnight

Image source: nicolas.kruchten.com 

 

So what's with that midnight jump? This is supposed to be an efficient marketplace, but are impressions one minute past midnight really worth 40% more than impressions 2 minutes earlier? Had we not had our initial experiences described above, it might have taken us a long time to puzzle out!

Our current working theory is in fact that there must be lots of bidders out there that behave just like our first one did: they have a fixed daily budget and they reset their counters at midnight. This would mean that starting at midnight, there's a whole lot more demand for impressions, and thanks to supply and demand, the price spikes way up. Alternately, odds are that at least one of the many bidders coming back online is set up to bid higher than the highest-bidder in the smaller pool of 11:59PM bidders. And as bidders run out of budget throughout the day, at different times, depending on their budget and how quickly they spend it, the price drops to reduced demand. It's not obvious from the above graph, but when you plot the averages over multiple days together there is a similar step at 3AM, when it's midnight on the West Coast, where a lot of other developers live and work and code:

prices2.png

Average Price Per Minute of the Day For the Month of August

Image source: nicolas.kruchten.com

 

Now, there might be some other explanations for this price jump. We're in the Northeast, and that impacts the composition of our bid-request stream. So, this may be just a regional pattern (do other people see this also?), although the 3AM jump suggests otherwise. Midnight also happens to be when our bid-request volume starts its nightly dip, but that dip is gradual and isn't enough to alone explain that huge spike. Maybe some major sites have some sort of reserve price that kicks in at midnight. Or maybe everyone else is way smarter than us and noticed that click-through rates are much higher a minute past midnight than they are a minute before. Whatever the reason, it looks like if you're going to only be bidding for a few hours a day, don't choose the time-period starting at midnight and ending at 10AM!

 

Closed-loop control to the rescue

So let's assume that this post gets a ton of coverage among the right circles and that this before/after-midnight arbitrage opportunity eventually disappears, or maybe you just want to actually spread your spending evenly throughout the day. How would you do it?

As I mentioned above, we have the ability to specify a percentage of the bid-volume to bid on. The obvious way to use this capability is to see how far into the day (percentage-wise) we get with our daily budget, and bid only on that percentage of the bid-request stream, thereby ensuring that we run out of budget just as midnight rolls around. In practice, though, bidding on a fixed percentage of all requests can and does result in a different amount spent each day, sometimes higher than the daily budget (if you remove the daily cap), and sometimes lower. Maybe some days you get a different volume of bid-requests, because your upstream provider is making changes. Maybe there's an outage. Maybe the composition of your bid-request stream is changing such that all of a sudden, the percentage of all bid-requests that's in the geo-area you're targeting goes way up (or down). Maybe your bidding logic doesn't result in a consistent spend.

All of these factors could amount to a very jagged spend profile:

openloop.png

 Spend rate can change despite constant bid probability

Image source: nicolas.kruchten.com

 

So what's the solution? For us, it's to look at this problem as a control problem and to move from open-loop control to closed-loop control. If you theorize about the appropriate bid probability, set it up and let things run for a week and look at the results later, that's basically open-loop control. If every morning you look at what the spend was the day before and adjust the coming day's bid probability accordingly, you're doing a form of closed-loop control: you're feeding back information from the output into the input. It's easy to automate (at least we thought so), and once that's done, there's basically no reason not to shorten the feedback loop from daily to every few minutes.

Our RTB client was designed from the ground up to facilitate this sort of thing, so we were able to control spend to within 1-2% of target with the following simple control loop:

  • Every 2 minutes, set the bid probability for the subsequent 2 minutes to that which would have resulted in the 'correct spend' over the preceding 2 minutes (maybe with a bit of damping).
  • If for whatever reason we get 20% fewer bid requests (at night, for example), the bid probability will rise so that the spend rate stays roughly constant.

There are more sophisticated ways to do closed-loop control, but this really basic system work well: 

beforeafter.png

Above is actual data from around the time we activated our simple controller. Notice how Open Loop Control gives output that looks like the mountains of Mordor, whereas Closed Loop Control makes it look like the fields of the Shire.

Image source: nicolas.kruchten.com

 

pace.png

Actual production data, smoothed a little bit to reveal underlying trend. Pace (blue, prob*1000) rises at night when volume drops; Spend Rate (green) stays close to target (red)

 Image source: nicolas.kruchten.com

 

Like any good optimizer, the scheme described above does exactly what you ask it to: it tries to keep the error between 'instantaneous' spend rate and the target as close to zero as possible. If there's a full-on outage where no bidding occurs for an hour, this system will not try to make up the spend, it will just try to get the spend rate back to where it should be according to the originally-specified target, once bidding resumes:

closedloop.png

Spend rate after outage is too low to catch up (slope remains parallel to initial target)

Image source: nicolas.kruchten.com 

 

To deal with outages, as well as over- or under-spending due to accumulated error or drift from the instantaneous control system's imperfect responses, we have to dynamically adjust this spend-rate target as well. The way we've come up with to deal with this is to define the error function in terms of the original problem: continuously work to keep the spend rate at a level that will spend the remaining budget in the remaining time. This means that if there is an outage for an hour or a day, the spend rate for the rest of the campaign will be marginally higher to make up for it, without human intervention. This system also has the nice property of automatically stopping right on the dot when the remaining budget is zero:

adaptive.png

Spend rate after outage increases to catch up (slope gets steeper as outage gets longer)

Image source: nicolas.kruchten.com 

 

Now, obviously you might not want to always have exactly the same spend rate all the time. In fact, I almost guarantee that you don't. A closed-loop control system can support pretty much whatever spending profile you like. You can also use one to manipulate other variables than the bid-probability (such as the actual bid price, the targeting criteria, or whatever other scheme your quant brain can conjure up). Finally, the astute reader will notice that the approach described above may only be useful in situations where there is more supply than your budget permits you to buy. As such, you need to allocate your budget over time. The approach above won't help at all if the optimal bid probability to meet your needs is up above 100%. That is to say, even when you bid on and win everything that matches your targeting criteria, you're not able to spend your budget.

That's probably a topic for a different blog post.

 

Make sure to check out our other blog posts as part of our Peeking Into The Black Box Series: 

 

Banner image source: Gratisography

Datacratic

Datacratic is a leader in audience data solutions that help brands create more effective and targeted digital marketing campaigns. With our team of experts specializing in machine learning, digital advertising and artificial intelligence, Datacratic helps you engage with the right person at the right time, with the right message to improve campaign and conversion results.

Peeking Into The Black Box Series: Part 1 - RTB Pacing, Is Everyone Doing it Wrong?


Sep 8, 2011, By Datacratic
|0 comments

This is the first blog post in a series that examines key theories and concepts about Real-Time Bidding (RTB), and how Datacratic leverages these items as part of our RTB strategies. In this post, we take a look at how we apply control theory to pace our spending.

Here is a basic problem: if someone gives you a fixed amount of money to run a display advertising campaign over a specific time period, it's generally advisable to spend exactly that amount of money, spread out reasonably evenly over that time period. Overspending could mean you're on the hook for the difference, and under-spending doesn't look great if you want repeat business. And if you don't spend it evenly, you might get some angry customers, and end up in situations where you could potentially spend all your budget in minutes.

Sounds obvious, right? Apparently, it's harder than it looks!

 

Doing it wrong

When Datacratic first dipped its toe into RTB, the main tool at our disposal to control budget/pacing was a daily spending cap. It took about 48 hours for us to figure out that this wasn't going to work for us. Depending on the types of filters we used to decide when to bid at all, we'd either not manage to spend the daily budget (more on that at the bottom) or blow the budget very quickly, usually the latter. In practice, this meant that we would start buying impressions at midnight (all times in this post are in Montreal local time: EST or EDT), and generally hit our cap mid-morning.

dailycap.png No bidding occurs after daily cap is reached

Image source: nicolas.kruchten.com 

 

On a daily spend graph over a 30 to 60-day period resulting from such a policy, this would probably look just fine: you're spending the budget in the time given, and spending exactly the right amount per day. But having this sort of 'dead time' where we don't bid at all bothered us, so as soon as we spun up our own bidder, we added options like "bid on X% of the request stream". When we looked at the resulting data, we noticed something really interesting: the impressions we were buying before were actually among the most expensive of the day!

The average win-price graph below (i.e. what the next-highest bid was to our winning one) from a high-bidding campaign shows a clear pattern: if you start at noon, the dollar cost for one thousand impressions (the CPM) generally drops until precisely midnight, then jumps something like 40%. It fluctuates a bit, hits a high in the morning and then drops down again until noon to start the cycle again. This pattern repeats day after day:

prices.png Notice the discontinuous jumps every midnight

Image source: nicolas.kruchten.com 

 

So what's with that midnight jump? This is supposed to be an efficient marketplace, but are impressions one minute past midnight really worth 40% more than impressions 2 minutes earlier? Had we not had our initial experiences described above, it might have taken us a long time to puzzle out!

Our current working theory is in fact that there must be lots of bidders out there that behave just like our first one did: they have a fixed daily budget and they reset their counters at midnight. This would mean that starting at midnight, there's a whole lot more demand for impressions, and thanks to supply and demand, the price spikes way up. Alternately, odds are that at least one of the many bidders coming back online is set up to bid higher than the highest-bidder in the smaller pool of 11:59PM bidders. And as bidders run out of budget throughout the day, at different times, depending on their budget and how quickly they spend it, the price drops to reduced demand. It's not obvious from the above graph, but when you plot the averages over multiple days together there is a similar step at 3AM, when it's midnight on the West Coast, where a lot of other developers live and work and code:

prices2.png

Average Price Per Minute of the Day For the Month of August

Image source: nicolas.kruchten.com

 

Now, there might be some other explanations for this price jump. We're in the Northeast, and that impacts the composition of our bid-request stream. So, this may be just a regional pattern (do other people see this also?), although the 3AM jump suggests otherwise. Midnight also happens to be when our bid-request volume starts its nightly dip, but that dip is gradual and isn't enough to alone explain that huge spike. Maybe some major sites have some sort of reserve price that kicks in at midnight. Or maybe everyone else is way smarter than us and noticed that click-through rates are much higher a minute past midnight than they are a minute before. Whatever the reason, it looks like if you're going to only be bidding for a few hours a day, don't choose the time-period starting at midnight and ending at 10AM!

 

Closed-loop control to the rescue

So let's assume that this post gets a ton of coverage among the right circles and that this before/after-midnight arbitrage opportunity eventually disappears, or maybe you just want to actually spread your spending evenly throughout the day. How would you do it?

As I mentioned above, we have the ability to specify a percentage of the bid-volume to bid on. The obvious way to use this capability is to see how far into the day (percentage-wise) we get with our daily budget, and bid only on that percentage of the bid-request stream, thereby ensuring that we run out of budget just as midnight rolls around. In practice, though, bidding on a fixed percentage of all requests can and does result in a different amount spent each day, sometimes higher than the daily budget (if you remove the daily cap), and sometimes lower. Maybe some days you get a different volume of bid-requests, because your upstream provider is making changes. Maybe there's an outage. Maybe the composition of your bid-request stream is changing such that all of a sudden, the percentage of all bid-requests that's in the geo-area you're targeting goes way up (or down). Maybe your bidding logic doesn't result in a consistent spend.

All of these factors could amount to a very jagged spend profile:

openloop.png

 Spend rate can change despite constant bid probability

Image source: nicolas.kruchten.com

 

So what's the solution? For us, it's to look at this problem as a control problem and to move from open-loop control to closed-loop control. If you theorize about the appropriate bid probability, set it up and let things run for a week and look at the results later, that's basically open-loop control. If every morning you look at what the spend was the day before and adjust the coming day's bid probability accordingly, you're doing a form of closed-loop control: you're feeding back information from the output into the input. It's easy to automate (at least we thought so), and once that's done, there's basically no reason not to shorten the feedback loop from daily to every few minutes.

Our RTB client was designed from the ground up to facilitate this sort of thing, so we were able to control spend to within 1-2% of target with the following simple control loop:

  • Every 2 minutes, set the bid probability for the subsequent 2 minutes to that which would have resulted in the 'correct spend' over the preceding 2 minutes (maybe with a bit of damping).
  • If for whatever reason we get 20% fewer bid requests (at night, for example), the bid probability will rise so that the spend rate stays roughly constant.

There are more sophisticated ways to do closed-loop control, but this really basic system work well: 

beforeafter.png

Above is actual data from around the time we activated our simple controller. Notice how Open Loop Control gives output that looks like the mountains of Mordor, whereas Closed Loop Control makes it look like the fields of the Shire.

Image source: nicolas.kruchten.com

 

pace.png

Actual production data, smoothed a little bit to reveal underlying trend. Pace (blue, prob*1000) rises at night when volume drops; Spend Rate (green) stays close to target (red)

 Image source: nicolas.kruchten.com

 

Like any good optimizer, the scheme described above does exactly what you ask it to: it tries to keep the error between 'instantaneous' spend rate and the target as close to zero as possible. If there's a full-on outage where no bidding occurs for an hour, this system will not try to make up the spend, it will just try to get the spend rate back to where it should be according to the originally-specified target, once bidding resumes:

closedloop.png

Spend rate after outage is too low to catch up (slope remains parallel to initial target)

Image source: nicolas.kruchten.com 

 

To deal with outages, as well as over- or under-spending due to accumulated error or drift from the instantaneous control system's imperfect responses, we have to dynamically adjust this spend-rate target as well. The way we've come up with to deal with this is to define the error function in terms of the original problem: continuously work to keep the spend rate at a level that will spend the remaining budget in the remaining time. This means that if there is an outage for an hour or a day, the spend rate for the rest of the campaign will be marginally higher to make up for it, without human intervention. This system also has the nice property of automatically stopping right on the dot when the remaining budget is zero:

adaptive.png

Spend rate after outage increases to catch up (slope gets steeper as outage gets longer)

Image source: nicolas.kruchten.com 

 

Now, obviously you might not want to always have exactly the same spend rate all the time. In fact, I almost guarantee that you don't. A closed-loop control system can support pretty much whatever spending profile you like. You can also use one to manipulate other variables than the bid-probability (such as the actual bid price, the targeting criteria, or whatever other scheme your quant brain can conjure up). Finally, the astute reader will notice that the approach described above may only be useful in situations where there is more supply than your budget permits you to buy. As such, you need to allocate your budget over time. The approach above won't help at all if the optimal bid probability to meet your needs is up above 100%. That is to say, even when you bid on and win everything that matches your targeting criteria, you're not able to spend your budget.

That's probably a topic for a different blog post.

 

Make sure to check out our other blog posts as part of our Peeking Into The Black Box Series: 

 

Banner image source: Gratisography

Datacratic

Datacratic is a leader in audience data solutions that help brands create more effective and targeted digital marketing campaigns. With our team of experts specializing in machine learning, digital advertising and artificial intelligence, Datacratic helps you engage with the right person at the right time, with the right message to improve campaign and conversion results.

Datacratic Info Kit

Double your retargeting conversion

Download our info kit to see how you can dramatically boost campaign effectiveness with audience segments powered by your visitors' feedback.

Download our Info Kit