Source-linked AI summary
Bid Optimization by Multivariable Control in Display Advertising
Xun Yang, Yasong Li, Hao Wang, Di Wu, Qing Tan, Jian Xu, Kun Gai
TL;DR
Advertisers need bidding strategies that maximize conversions while satisfying budget and CPC constraints. The paper derives an optimal strategy with linear programming and primal-dual optimization, then adds feedback control for dynamic conditions. On real Taobao.com data, the systems showed constraint-control capability and superiority over industry practices.
Problem
Advertisers seek campaign value within budget limits, but also use KPI constraints such as CPC to regulate cost and performance amid volatile traffic and delayed conversions.
Source: §1 · p. 1Method
The paper formulates conversion maximization under budget and CPC constraints as linear programming, derives bids with the primal-dual method, and adds multivariable feedback control.
Source: §1 · pp. 1–2Results
On real Taobao.com datasets, the systems showed strong capability in achieving constraints and superiority over state-of-the-art industry practices.
Source: §1 · p. 2Takeaways & Limitations
CPC can serve as a real-time proxy for expected advertising value because conversions are sparse and delayed.
Source: §1 · p. 1The approach assumes click and conversion probabilities and winning-price prediction have already been solved.
Source: §2.1 · p. 2
Abstract
from arXiv · showhide
Real-Time Bidding (RTB) is an important paradigm in display advertising, where advertisers utilize extended information and algorithms served by Demand Side Platforms (DSPs) to improve advertising performance. A common problem for DSPs is to help advertisers gain as much value as possible with budget constraints. However, advertisers would routinely add certain key performance indicator (KPI) constraints that the advertising campaign must meet due to practical reasons. In this paper, we study the common case where advertisers aim to maximize the quantity of conversions, and set cost-per-click (CPC) as a KPI constraint. We convert such a problem into a linear programming problem and leverage the primal-dual method to derive the optimal bidding strategy. To address the applicability issue, we propose a feedback control-based solution and devise the multivariable control system. The empirical study based on real-word data from Taobao.com verifies the effectiveness and superiority of our approach compared with the state of the art in the industry practices.
1 INTRODUCTION
Advertisers seek conversion volume while meeting budget and CPC constraints, which can help regulate campaign cost and performance amid volatile traffic. The paper derives a constrained bidding strategy and adds multivariable feedback control for dynamic industrial conditions.
1 INTRODUCTION
- In RTB, DSPs submit impression-level bids using opportunity-specific information, and the highest bid wins the ad opportunity.This lets advertisers use DSP-provided information and algorithms to set different bids for individual opportunities.Source: §1 · p. 1
- KPI constraints can regulate campaign cost and serve as real-time proxies for expected advertising value when conversions are sparse and delayed.They also reduce the need for frequent manual budget adjustments when traffic conditions fluctuate.Source: §1 · p. 1
- The bidding strategy maximizes conversion quantity under budget and CPC constraints by formulating bid optimization as linear programming and applying the primal-dual method.The methodology could be generalized to other cost-related KPI constraints, including CPM.Source: §1 · pp. 1–2
- The multivariable control system uses independent PID and model predictive control to address dynamic conditions and coupling among variables.It is based on the optimal bidding strategy and is intended to address its applicability in industrial settings.Source: §1 · p. 2
- Real Taobao.com experiments show strong control capability in achieving constraints and superiority over state-of-the-art industry practices.The paper reports implementing and evaluating the proposed systems on real industrial datasets.Source: §1 · p. 2
2 BIDDING STRATEGY
The section describes the RTB setting, formulates conversion maximization under budget and CPC constraints, and derives an optimal bidding strategy with primal-dual analysis.
2.1 RTB Eco-system
- The ad exchange requests DSP bids, charges the winning DSP under GSP, and routes user feedback back for model training and campaign-long bid adjustment.CTR/CVR estimation and winning-price prediction are assumed solved.Source: §2.1 · p. 2
2.2 Problem Formulation
- The LP maximizes expected conversions, valued as CTR_i × CVR_i, subject to budget B and a CPC ceiling C.The CPC formulation substitutes CTR for observed clicks.Source: §2.2 · pp. 2–3
2.3 Optimal Bidding Strategy
- Primal-dual analysis derives the optimal bid from CTR, CVR, CPC target C, and dual parameters p and q.The parameters correspond to the optimal dual solution.Source: §2.3 · p. 3
- The strategy bids above the winning price for opportunities assigned x_i*=1 and below it for x_i*=0, implementing the LP allocation.The paper states that this yields the optimal solution to LP1.Source: §2.3 · p. 3
- The strategy first sets a click-price bid and multiplies it by CTR for the final bid; under GSP, click cost is no higher than that click bid.Source: §2.3 · pp. 3–4
- The click-price bid rises linearly with CVR and can remain positive at zero-value opportunities, helping lower overall CPC to win higher-CPC valuable opportunities.Source: §2.3 · p. 4
3 SYSTEM DESIGN
The system addresses the difficulty of applying an optimal bidding strategy in a dynamic RTB environment with feedback control. It analyzes how the strategy’s parameters affect budget spending and CPC, then uses PID control and a model predictive module to manage those outcomes and their coupling.
3.1 Applicability Issue
- Historical optimal bids may fail in future RTB environments because ad opportunities, winning prices, CTR, and CVR are non-stationary.The required impression-level information is unavailable until the day ends, although bids must be set before the campaign starts.Source: §3.1 · p. 4
3.2 Feedback Control-based Solution
- Real-time feedback adjusts bidding parameters p and q to pace budget spending and control CPC simultaneously.The bidding strategy and RTB environment form a dynamic system, with p and q as inputs.Source: §3.2 · p. 4
3.3 Analysis on Hyper Parameters
- Increasing p generally lowers positive bids and expected cost, while increasing q favors opportunities whose CPC is below target C.The analysis assigns p a direct control effect on budget spending and q a direct control effect on CPC.Source: §3.3 · pp. 5–6, Figure 4 · p. 5, Figure 5 · p. 5
3.4 Multivariable Control
- Independent PID controllers use p for budget spending and q for CPC, treating each parameter’s effect on the other outcome as outside noise.The paper says this decomposition permits PID controllers to be deployed separately.Source: §3.4 · p. 6
- A model predictive module after the PID controllers regulates their signals to address coupling, using a linear approximation based on cost and CPC changes.The approximation is determined by weight parameters α and β; the exact system matrices are not required.Source: §3.4 · p. 6, Figure 7 · p. 6
4 EMPIRICAL STUDY
The empirical study describes real-data experiments that assess the proposed multivariable control systems and compare them with industry practices.
Experimental setup
- Experiments use real datasets and describe the related metrics and implementation details.The passage does not specify dataset size or metric values.Source: §4 · p. 6
Control capability
- Example campaigns are used to test the claimed control capability of the hyper parameters.Source: §4 · p. 6
Industry comparison
- A large group of campaigns is used to compare the proposed systems with industry practices.The supplied passage describes the comparison but does not report its outcome.Source: §4 · p. 6
4.1 Experiment Setup
The experiments use Taobao campaign data and evaluate advertising value alongside CPC control. Controller parameters are tuned on training data and tested in hourly steps using campaign-specific references.
4.1.1 Dataset.
- The Taobao dataset covers 40 campaigns across continuous days and 20M bid logs, with winning prices, CTR, and CVR used as key information.Winning prices are observed after auctions, including opportunities the advertiser did not win; CTR and CVR come from deployed estimation models.Source: §4.1.1 · pp. 6–7, Table 1 · p. 7
4.1.2 Metrics.
- Advertising value is the sum of CTR · CVR; CPCratio measures campaigns meeting the CPC constraint, while Valueratio averages R/R∗ among campaigns that satisfy it.The CPC constraint allows overshoot within 10%; campaigns breaking it are excluded from Valueratio.Source: §4.1.2 · p. 7
4.1.3 Implementation Details.
- PID weights and α and β are grid-searched on training data, then evaluated on test data in 24 hourly time steps with campaign-specific CPC and cost references.The cost reference is the training-set hourly ideal cost distribution normalized by the day's total cost; test simulation ends when budget runs out or opportunities cease.Source: §4.1.3 · p. 7
4.2 Control Capability
The control experiment adjusts p and q together and assesses budget spending and CPC on an example campaign. The results indicate that each parameter can control its corresponding output despite some interference.
4.2 Control Capability
- Hourly CPC quickly enters the ±10% tolerable margin, and accumulated CPC remains controlled under the reference, although real-time CPC fluctuates.The CPC reference is 200; attention to real-time CPC decreases over time, producing more stable accumulated CPC.Source: §4.2 · p. 7, Figure 9 · p. 8
- Hourly spending fluctuates around the cost reference, while accumulated spending is well controlled against its reference.Figure 8 uses the cost distribution as the cost reference.Source: §4.2 · p. 7, Figure 8 · p. 8
- Although p and q interfere with each other, experiments show they can be adjusted independently to control their corresponding outputs.The experiment adjusts both parameters simultaneously without the model predictive module.Source: §4.2 · p. 7
4.3 Performance Evaluation
The evaluation compares the proposed I-PID and M-PID systems with industry baseline strategies on real-world campaigns. Both proposed systems retain CPC control, with M-PID delivering the strongest advertising value among the compared strategies.
4.3.1 Baseline Strategies.
- Cost-min truncates bid prices to guarantee CPC control, while its cost-reference PID adjustment can lose valuable ad opportunities.Its initial b0 is set using the given CPC divided by the campaign's average CVR.Source: §4.3.1 · p. 8
- Fb-Control adjusts b0 using CPC feedback; Fb-Control-M adds cost-reference control and a separate PID-controlled bid cap, and performs better than Fb-Control.Fb-Control-M's b0 is initialized as in Cost-min, while its bid cap starts at the given CPC.Source: §4.3.1 · p. 8
4.3.2 Experimental Results.
- M-PID performs better than I-PID, and I-PID outperforms all baseline strategies while all methods satisfy the CPC constraint.The authors attribute M-PID's advantage over I-PID to addressing controller coupling; Cost-min achieves the least advertising value.Source: Table 2 · p. 8, §4.3.2 · p. 8
5 RELATED WORK
Prior RTB work often optimizes advertising value under budget constraints or addresses KPI constraints separately. This paper focuses on value and KPI constraints together, deriving a bidding strategy and applying feedback control for dynamic conditions.
5 RELATED WORK
- Earlier display-advertising work maximized value within budget without KPI constraints, while other work addressed KPI constraints; little work treated both together.Kitts et al. proposed a generic framework for value and multiple KPI constraints, whereas this work focuses on a specific KPI constraint and a more tailored strategy.Source: §5 · p. 8
- The paper uses a primal-dual approach to derive a bidding strategy rather than an ad-allocation strategy, then applies feedback control to address dynamic conditions.The cited feedback-control work includes [34].Source: §5 · pp. 8–9
6 CONCLUSION
The paper formulates constrained bid optimization as a linear program and derives an optimal strategy using the primal-dual method. It then evaluates multivariable feedback control systems, reporting superior advertising performance with the KPI constraint holding.
6 CONCLUSION
- The approach delivers superior advertising performance while holding the KPI constraint on a real-world dataset.The paper compares its multivariable control systems with the state of the art in industry.Source: §6 · p. 9
- Primal-dual optimization derives a bidding strategy, and a model predictive PID system compensates for coupling among variables.The paper also investigates how bidding-strategy hyperparameters relate to their corresponding constraints.Source: §6 · p. 9
- Feedback control, including an independent PID system, is proposed to address dynamic-environment applicability.The model predictive module is added to compensate for coupling effects.Source: §6 · p. 9