2014 Optimal Real-time Bidding for Display Advertising

This paper is the Bid-Aware Gradient Descent for Unbiased Learning with Censored Data in Display published by Weinan Zhang in 2016 There was a strong connection between the two from previous jobs at Advertising

1 background

The figure above illustrates the role of DSP in a real-time bidding system. In this system, when a user visits a page, an exposure is generated, and the SSP sends a bidding request to the DSP. DSP then calculates the bid for this exposure and returns it to Ad Exchange. The winner will be notified and their AD will be exposed. The Bidding Engine in the system gives real-time Bidding.

The point of real-time bidding is that

• Allows each display transaction to expand the large amount of available AD inventory including the remainder (allows for fine bidding and budget control)
• Focus on user data rather than context data when buying ads (audience targeting is more accurate)

The contributions of the article are

• A novel optimization framework is proposed to find the best bidding strategy in real-time bid display ads
• The auction winning function constructed from the data, the best bid function derived from the framework, and the bid function is convex for each exposure KPI(Key Performance Indicator)

2. Optimal real-time bidding

2.1 Problem Definition

The variable used in the article is defined as follows

symbol	describe
$\boldsymbol{x}$	AD request, represented by features (features extracted from the AD itself, features relevant to the display)
$p_x(\boldsymbol{x})$	The probability distribution of x, I should be referring to the distribution of x in the requested data
$\theta(\boldsymbol{x})$	To predict the KPI of advertising winning, commonly used are: CTR, CVR
$p_{\theta}(\theta)$	KPI $\theta$Probability density function of
B	The advertising budget
$N_T$	The estimated number of AD bid requests over the life of the budget
$b (\theta (\boldsymbol{x}), \boldsymbol{x})$	Bidding function B, to simplify: $b(\theta(\boldsymbol{x}), \boldsymbol{x}) \equiv b(\theta(\boldsymbol{x}))$
$w(b(\theta(\boldsymbol{x})), \boldsymbol{x})$	At a given bid $b(\theta(\boldsymbol{x}))$When, the winning probability is also simplified: $w(b(\theta(\boldsymbol{x})), \boldsymbol{x}) \equiv w(b(\theta(\boldsymbol{x})))$

The problem is to design an optimal bidding strategy that maximizes kpIs within budget constraints. The paper takes the number of clicks as the objective of optimization, and the optimization function is as follows

$\begin{aligned} b()_{\mathrm{ORTB}} & = \underset{\text { b() }}{\arg \max } N_{T} \int_{\boldsymbol{x}} \theta(\boldsymbol{x}) w(b(\theta(\boldsymbol{x}), \boldsymbol{x}), \boldsymbol{x}) p_{x}(\boldsymbol{x}) d \boldsymbol{x} \\ & \text { subject to } N_{T} \int_{\boldsymbol{x}} b(\theta(\boldsymbol{x}), \boldsymbol{x}) w(b(\theta(\boldsymbol{x}), \boldsymbol{x}), \boldsymbol{x}) p_{x}(\boldsymbol{x}) d \boldsymbol{x} \leq B \end{aligned}$

Since the optimization objective is expressed in integral form, pθ(θ)p_{\theta}(\theta) pθ(θ) is used, Theta (x) \ theta (\ boldsymbol {x}) theta (x) and w (b (theta (x)), x) w (b (\ theta (\ boldsymbol {x})), \ boldsymbol {x}), w (b (theta (x)), x) multiply expressed by clicking the probability for a bid, In optimization, the constraint is that the bid cannot exceed B after winning within the budget validity period.

In the b (theta (x), x) b (\ theta (\ boldsymbol {x}), \ boldsymbol {x}) b (theta (x), x) and w (b (theta (x)), x) w (b (\ theta (\ boldsymbol {x})), \ boldSymbol {x})w(b(θ(x)),x) after appropriate simplification, the optimization problem is as follows

$\begin{aligned} b()_{\mathrm{ORTB}}=\underset{b()}{\arg \max } & N_{T} \int_{\boldsymbol{x}} \theta(\boldsymbol{x}) w(b(\theta(\boldsymbol{x}))) p_{x}(\boldsymbol{x}) d \boldsymbol{x} \\ \text { subject to } & N_{T} \int_{\boldsymbol{x}} b(\theta(\boldsymbol{x})) w(b(\theta(\boldsymbol{x}))) p_{x}(\boldsymbol{x}) d \boldsymbol{x} \leq B \end{aligned}$

Using the equation p theta (theta) (x) = p (x) ∥ ∇ theta (x) ∥ p_ {\ theta} (\ theta (\ boldsymbol {x})) = \ frac {p_ {x} (\ boldsymbol {x})} {\ | \ nabla (\ \ theta boldsymbol {x}) p \ |} theta (theta) (x) = ∥ ∇ theta ∥ px (x) (x) to replace the above formula, the integral form of x is expressed as integral form of theta \ theta theta, optimization problem as follows

$\begin{aligned} b()_{\mathrm{ORTB}} &=\underset{b()}{\arg \max } N_{T} \int_{\theta} \theta w(b(\theta)) p_{\theta}(\theta) d \theta \\ & \text { subject to } N_{T} \int_{\theta} b(\theta) w(b(\theta)) p_{\theta}(\theta) d \theta \leq B \end{aligned}$

2.2 Problem Solving

The Lagrange form of the optimization problem in 2.1 is as follows

$\mathcal{L}(b(\theta), \lambda)= \int_{\theta} \theta w(b(\theta)) p_{\theta}(\theta) d \theta – \lambda \int_{\theta} b(\theta) w(b(\theta)) p_{\theta}(\theta) d \theta+\frac{\lambda B}{N_{T}}$

According to the variational method, the Euler-Lagrange condition for b(θ)b(\theta)b(θ) is

$\theta p_{\theta}(\theta) \frac{\partial w(b(\theta))}{\partial b(\theta)}-\lambda p_{\theta}(\theta)\left[w(b(\theta))+b(\theta) \frac{\partial w(b(\theta))}{\partial b(\theta)}\right]=0$

$\lambda w(b(\theta))=[\theta-\lambda b(\theta)] \frac{\partial w(b(\theta))}{\partial b(\theta)}$

B (theta) b (\ theta) b (theta) and the probability distribution p theta (theta) p_ {\ theta} (\ theta) p theta (theta) has nothing to do, only depend on w (theta) (b) w (\ theta) (b) w (theta) (b).

Different winning functions will produce different optimal bidding functions. Here we present two typical winning functions that fit real world data curves and derive the optimal bid function form for each bid function.

Winning & Bidding Function 1

When the bid is low, raising the bid will greatly improve the probability of winning, while when the bid is high, raising the bid will slightly improve the probability of winning, so the win function is defined

$w(b(\theta))=\frac{b(\theta)}{c+b(\theta)}$

Where C is a constant. For different c, the probability of winning is shown in Figure 2(a).

By substituting the winning function into the euler-Lagrange condition for b(θ)b(\theta)b(θ), we can obtain

$b_{\mathrm{ORTB} 1}(\theta)=\sqrt{\frac{c}{\lambda} \theta+c^{2}}-c$

That is, the optimal bid function is related to θ\thetaθ, λ\lambdaλ, CCC, and the solution of λ\lambdaλ will be mentioned later. The relationship between the optimal bid and θ\thetaθ is shown in Figure 2(b).

Winning & Bidding Function 2

For some campaigns with competitive objectives, the target publisher /SSP sets a high floor price, and the probability of winning does not increase rapidly when the bid price is about zero; The probability of winning increases sharply only after the bid price is greater than some non-zero value. This usually happens in high-profile advertising space. To get this functionality, change it slightly and come up with another winning function

$w(b(\theta))=\frac{b^{2}(\theta)}{c^{2}+b^{2}(\theta)}$

Where C is a constant. For different c, the probability of winning is shown in Figure 3(a).

The optimal bidding function can be deduced as

BORTB2 (theta) = b_ {\ mathrm 2} {ORTB} (\ theta) = bORTB2 (theta) = c ⋅ [(theta. Theta + c2 lambda 2 + 2 c lambda) 13 – (c lambda theta. Theta + c2 lambda 2 + 2) 13] \ quad c \cdot\left[\left(\frac{\theta+\sqrt{c^{2} \lambda^{2}+\theta^{2}}}{c \lambda}\right)^{\frac{1}{3}}-\left(\frac{c + \ \ lambda} {\ theta SQRT {c ^ {2} \ lambda ^ {2} + \ theta ^ {2}}} \ right) ^ {\ frac {1} {3}} \ c ⋅ right] [(c lambda theta. Theta + c2 lambda 2 + 2) 31 – (theta. Theta + c2 lambda 2 + 2 c lambda) 31]

The relationship between the fixed lambda lambda optimal bid and θ\thetaθ is shown in Figure 3(b).

Discussion on optimal bid function

As shown in the figure below, when θ\thetaθ is less than 0.0011, the optimal bid function proposed in this paper gives a higher bid than the linear bid function. When θ\thetaθ is greater than 0.0011, the optimal bid function proposed in this paper gives a lower bid

• Bid higher for lower value exposure and get more clicks
• When the probability of winning exceeds a certain value, raising the bid does not increase the probability of winning very much, so for θ\thetaθ above a certain value, do not overbid
• Due to the concavity of the winning relative to the bid price, the ORTB strategy (the strategy in this article) will have a greater probability of winning, while the CPM will increase only slightly

$\lambda$To solve the

Lambda \ lambda lambda cannot directly obtained analytical solution and numerical solution can be determined by clicking the log data, there are properties: When lambda \lambda lambda decreases, ∫ theta b (theta) w (p (theta) b) theta (theta) d theta \ int_ {\ theta} b (\ theta) w (p_ (\ theta) b) {\ theta} \ \ theta) d theta ∫ theta b (theta) w (p (theta) b) theta (theta) d theta monotonically (explain the original).

The specific solution is described in the paper: Bid-Aware Gradient Descent for Unbiased Learning with Censored Data in Display Advertising. Please refer to the notes: Paper Reading (010).

3 Preparation for experiment

The data set is briefly introduced and can be seen in the original text. The winning rate in the data set is shown as follows, that is, with the increase of bid price, the probability of winning increases. When the bid is too high, the winning probability tends to 1, which is formally consistent with the two winning functions proposed in this paper. It also discusses the relationship between features and winning prices, and concludes that winning prices have nothing to do with features. So the relationship between w (b (theta (x)), x) ≡ w w (theta (x)) (b) (b (\ theta (\ boldsymbol {x})), \ \ boldsymbol {x}) equiv w (b (\ theta (\ boldsymbol {x}))) w (b (theta (x)), x) ≡ w (theta (x)) (b), namely the winning probability and only offer high and low.

The training method is abbreviated, that is, the routine operation, and the test strategy is recorded here. The evaluation process is shown in the figure below. The evaluation index is only calculated for the request winning the bidding, but it cannot obtain whether the advertisement is clicked and converted after winning the bidding (the paper uses relevant work of others to solve the problem, but there is no detailed elaboration). To test performance under different budget constraints, for each campaign, 1/64, 1/32, 1/16, 1/8, 1/4, and 1/2 of the original total cost in the test log were used for evaluation tests.

There are ways to compare

• Constant bidding: If you bid at a Constant price, you need to adjust the bid price
• Random bidding: Bidding at Random in a range, the lower and upper bounds of the price range need to be adjusted
• Bidding below Max eCPC (Mcpc) : Bidding price is Max eCPC X pCTR. Calculate Max eCPC per Campagin using cost/clicks
• Linear Form Bidding of pCTR (Lin) : Bid for bLin ⁡ (theta) = b0 theta. Theta 0 b_ {\ operatorname {Lin}} (\ theta) = b_ {0} \ frac {\ theta} {\ theta_ {0}} bLin (theta) = b0 theta 0 theta, θ0\ theTA_ {0}θ0 is the average CTR, b0b_{0}b0 based bid under the target condition, the value of b0b_{0}b0 needs to be adjusted.
• Optimal real-time bidding (ORTB1 and ORTB2) : In this method, C is calculated by fitting the winning probability and λ is calculated using training data

The characteristics of the above methods are shown below

4 Offline experiment

Answer the following questions

• Whether non-linear bidding functions are better than the most advanced linear bidding functions, that is, whether ORTB1 and ORTB2 are better than Lin
• What are the characteristics of ORTB bidding? How do parameters affect the ORTB effect? What impact does the budget situation have on ORTB bidding

Comparison of Bidding strategies

The comparison results of the above algorithms are shown in the figure below

Conclusion there are

• Under different budgets, ORTB1 and ORTB2 bidding strategies have better results in the number of clicks, that is, nonlinear bidding function is effective
• Besides ORTB, Lin works best and is widely used in DSP
• Mcpc can’t adjust to different budgets, and when the budget is low, Mcpc still bids Max eCPC X pCTR
• Rand and Const fared poorly
• From eCPC, Rand and Const will overbid for clicks

Budget impact on bidding strategy

Under different budget constraints, the effects of different bidding strategies are compared, and the results are shown in Figure 10(a)

Conclusion there are

• When budgets are low (such as 1/64 in the figure), ORTB has a large increase (over 45%) on Click relative to Lin, indicating that ORTB’s bidding strategy performs well on low budgets and validates a relatively high bid for low-value traffic
• When the budget is large, the promotion effect of Lin is relatively small, that is, when the budget is sufficient, most of the budget will be moved from low-value traffic to high-value traffic

Click and expose contrast

A comparison between Figure 10(a) and Figure 10(b) is like drawing a conclusion

• Both clicks and eCPC increase as the budget increases, that is, when the budget is low, bids are made on point-worth traffic, and when the budget is high, bids are made on high-value traffic
• Mcpc is not sensitive to bids, i.e. eCPC changes relatively little
• When the budget is lower (less than or equal to 1/16), the eCPC of ORTB and Lin is smaller than that of Mcpc; when the budget is higher (greater than 1/16), the eCPC of ORTB and Lin is larger than that of Mcpc

It can be seen from Figure 10(c) and Figure 10(d) that while ORTB gets the highest click, it also gets a relatively high exposure. Because the optimization goal and optimize the click and exposure (that is, the corresponding theta {\ theta} theta and w (theta) (b) w (\ theta) (b) w (theta) (b)).

Parameter adjustment

For ORTB1 and ORTB2, it is necessary to adjust λ\lambdaλ. In the case of different budgets, the relationship between λ\lambdaλ and click is shown in the figure below. In the case of lower budgets, the optimal λ\lambdaλ is larger; in the case of higher budgets, the optimal λ\lambdaλ is smaller, that is, the lower budget, the lower bid.

Other KPI indicators

Considering both click and exposure, set the KPIs as follows

KPI = # \ mathrm {KPI} = \ # KPI = # click + k ⋅ \ cdot \ # # + k + k ⋅ # conversion.

In this paper, k= 5K = 5K =5 and pKPI = pCTR + K.PCVR were set during the experiment. The experimental results are shown in the figure below

The main conclusions are

• ORTB works better than other bidding strategies
• With a budget limit of 1/64, ORTB2 performed better than ORTB1 because Winning Function 2 was better suited to the KPI optimization objectives described above than Winning Function 1

5 Online experiment

In the online experiment, White strategy was added (paying a high price for advertisements conforming to features and rules), and the experimental results are shown in the figure below

The conclusion is as follows

• ORTB generated more bids and received more exposure, clicks and conversions than the other two strategies. At the same time, ORTB obtained a lower eCPC, indicating that the bidding strategy is effective
• ORTB gets a lower CPM because ORTB allocates more of its budget to low-value traffic
• Due to low CPM and pCTR, ORTB has the lowest auction winning rate and click through rate
• White’s bidding strategy is opposite to ORTB’s, resulting in a low number of winning bids and a high CPM

6 discuss

1. The optimization objective is: θw(b(θ))\theta w(b(\theta))θw(b(\theta))θw(b(\theta)), that is, considering the winning probability and click rate, if the winning probability is high but the click rate is low, will the final conversion number be low? Is such an optimization objective reasonable?

7 Reference Materials

1. 002 Optimal RealTime Bidding for Display Advertising

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign