Source-linked AI summary
Real-Time Bidding by Reinforcement Learning in Display Advertising
Han Cai, Kan Ren, Weinan Zhang, Kleanthis Malialis, Jun Wang, Yong Yu, Defeng Guo
TL;DR
Repeated RTB bidding must allocate a constrained campaign budget across impressions while accounting for immediate and future rewards. The paper formulates this process as an MDP-based reinforcement-learning problem with value approximation for scale, achieving reported gains in offline and online evaluations.
Problem
Static bid optimization does not capture strategic dependence across repeated auctions created by market competition, auction volume, campaign budget, and cumulative campaign rewards.
Method
The paper models impression-level bidding as an MDP whose states include campaign parameters and bid-request information, using auction transitions, dynamic programming, and neural-network value approximation.
Results
The proposed solution achieved 16.7% and 7.4% gains against state-of-the-art methods on two real-world datasets and a 44.7% online click-performance improvement against an industry method.
Takeaways & Limitations
RLB provides a sequential bidding policy for optimizing advertising performance while handling large-scale auction volume and campaign budgets.
Takeaways & Limitations
Future work remains to investigate model-free approaches and compare RLB with explicit budget-pacing techniques.
Abstract
from arXiv · showhide
The majority of online display ads are served through real-time bidding (RTB) --- each ad display impression is auctioned off in real-time when it is just being generated from a user visit. To place an ad automatically and optimally, it is critical for advertisers to devise a learning algorithm to cleverly bid an ad impression in real-time. Most previous works consider the bid decision as a static optimization problem of either treating the value of each impression independently or setting a bid price to each segment of ad volume. However, the bidding for a given ad campaign would repeatedly happen during its life span before the budget runs out. As such, each bid is strategically correlated by the constrained budget and the overall effectiveness of the campaign (e.g., the rewards from generated clicks), which is only observed after the campaign has completed. Thus, it is of great interest to devise an optimal bidding strategy sequentially so that the campaign budget can be dynamically allocated across all the available impressions on the basis of both the immediate and future rewards. In this paper, we formulate the bid decision process as a reinforcement learning problem, where the state space is represented by the auction information and the campaign's real-time parameters, while an action is the bid price to set. By modeling the state transition via auction competition, we build a Markov Decision Process framework for learning the optimal bidding policy to optimize the advertising performance in the dynamic real-time bidding environment. Furthermore, the scalability problem from the large real-world auction volume and campaign budget is well handled by state value approximation using neural networks.
1. INTRODUCTION
The paper treats display-advertising bidding as a sequential reinforcement-learning problem rather than static bid optimization. It models campaign state and auction information to learn policies that improve performance at scale.
- Static bidding can fail to account for market competition, auction volume, and campaign budget in repeated auctions.
- The paper formulates bidding as sequential decision-making, with the advertiser’s environment comprising the ad market and Internet users.
- Each bidding state includes campaign parameters such as remaining lifetime and budget plus the bid request’s user and contextual information.
- The framework uses an MDP, neural-network value approximation, coarse-to-fine episode segmentation, and state mapping to address large-scale bidding.
- 16.7% and 7.4% performance gains were achieved against state-of-the-art methods on two large-scale real-world datasets, while online testing showed a 44.7% click-performance improvement.
2. BACKGROUND AND RELATED WORK
RTB bidding combines utility estimation, market-price forecasting, and bid optimization under budget constraints. The paper situates its approach within MDP-based bidding and addresses impression-level decisions and scalability.
- Reinforcement Learning: An MDP models environment dynamics through states, actions, transition probabilities, and rewards, with dynamic programming applicable when these dynamics are known.
- RTB Strategy: RTB agents estimate user-response utility, forecast auction market prices, and choose final bids using market, bid-request, budget, and auction-volume information.
- Utility Estimation: Utility estimation commonly models clicks or conversions using methods including logistic regression, boosted trees, and factorization machines.
- Bid Landscape Forecasting: Bid landscape forecasting models market-price distributions and winning probabilities, while censored data complicates learning from losing bids.
- Bid Optimization: Truthful bidding is optimal for a single second-price auction but may perform poorly across multiple auctions with budget constraints.
- Bid Optimization: The paper studies impression-level RTB bidding and tackles scalability beyond prior model-based MDP work focused on keyword-level decisions.
3. PROBLEM AND FORMULATION
The paper defines RTB bidding as an episodic MDP in which bids allocate a finite budget across sequential auctions. States combine remaining auctions, unspent budget, and impression features, while transitions encode auction outcomes.
- 3. PROBLEM AND FORMULATION: The bidding agent seeks to maximize user responses, treating clicks as the target KPI while allowing other performance objectives similarly.
- 3.1 Problem Definition: Each episode contains T sequential auctions, and each auction is represented by a high-dimensional one-hot feature vector.
- 3.1 Problem Definition: The agent’s state tracks remaining auctions t, unspent budget b, and the current auction feature vector x.
- 3.1 Problem Definition: A bid a wins when a ≥ δ, costs the market price δ, updates the budget to b − δ, and yields predicted CTR θ(x) as expected reward.
- 3.2 MDP Formulation of RTB: The MDP defines states, available bid-price actions, auction-driven transition probabilities, and rewards received after actions cause state transitions.
- 3.2 MDP Formulation of RTB: Winning transitions reduce both the auction count and budget according to the market price, whereas losing transitions preserve the budget; other transitions are impossible.
- 3.2 MDP Formulation of RTB: The value function is the expected total reward under a policy, and the optimal policy is the bidding strategy that maximizes this value with discount factor γ = 1.
- 3.2 MDP Formulation of RTB: Model-free methods may struggle with enormous state spaces, sparse rewards, and stochastic dynamics, motivating the use of modeled utility and market-price distributions.
4. DYNAMIC PROGRAMMING SOLUTION
The paper derives an optimal bidding policy with dynamic programming and addresses large-scale campaigns by approximating value-related functions and mapping large states to smaller ones. The resulting policy adapts to remaining time and budget, while its exact computation is limited to small-scale settings.
- Dynamic programming formulation: The optimal value functions V(t, b, x) and V(t, b) describe expected total reward with and without observing impression features.The state is represented by remaining auctions t, budget b, and, when available, feature vector x.
- Dynamic programming formulation: The optimal bid action combines market-price probabilities, predicted click-through rate, and the change in future value caused by spending δ.The action depends on m(δ, x), θ(x), and V(t −1, ·), with integer bid prices in practice.
- Dynamic programming formulation: The value function is approximated by replacing feature-dependent market-price distributions with m(δ) and marginalizing feature effects through the average pCTR θavg.This approximation yields a value function V(t, b) that can be computed without explicitly retaining the full feature vector.
- Derived policy: The derived RLB policy changes with remaining time and budget: it is linear at large budgets, lowers its slope as budget decreases or time increases, and becomes concave below b < 300.This differs from linear strategies with a static parameter.
- Large-scale handling: Exact value-function updating requires O(TB) time and O(TB) space, so Algorithm 1 is restricted to small-scale situations.Large T and B can exceed available computational resources for storing and updating every state.
5. EXPERIMENTAL SETUP
The experiments evaluate bidding policies on two real-world RTB datasets using budgeted episodes, shared prediction components, and small- versus large-scale settings. The study compares proposed RLB variants with established bidding strategies and scalability mechanisms.
- Datasets: Experiments use the iPinYou and YOYI real-world RTB datasets, with iPinYou containing 19.5M impressions and YOYI 441.7M impressions.The paper mainly reports iPinYou results and uses YOYI as supplementary verification.
- Evaluation flow: Each test episode contains T bid-request records and receives budget B, with winning auctions producing market-price costs and click rewards.The bid cannot exceed the current budget, and campaign state is updated after each auction.
- Evaluation flow: The budget is constrained relative to historical test-data cost using B = CPM_train×10^-3×T×c_0.The parameter c_0 controls the budget constraint, preventing trivially high bids from winning all impressions.
- Compared methods: RLB is evaluated alongside SS-MDP, Mcpc, and Lin, while RLB-NN and its segmentation or state-mapping variants address large-scale bidding.The compared policies share logistic-regression CTR estimation and non-parametric bid-landscape forecasting components.
- Compared methods: RLB-NN approximates the value function with a neural network, while RLB-NN-Seg allocates remaining budget across smaller episodes.RLB-NN-MapD and RLB-NN-MapA instead use mappings for value-function or action inputs.
6. EXPERIMENTAL RESULTS
The proposed RLB policy performs strongly in small-scale offline evaluations, while neural-network approximations require additional segmentation or state mapping for reliable large-scale performance. Across tested settings, the paper reports gains over the industry baseline Lin.
- Small-Scale Evaluation: RLB achieves the best total-click performance under every tested budget condition on iPinYou with T = 1,000.Lin is second best, while Mcpc is weak under very limited budgets and SS-MDP performs worst overall.
- Small-Scale Evaluation: RLB produces more clicks than Lin with comparable CPM and eCPC by allocating budget according to market conditions.SS-MDP has the highest win rate because it treats bid requests equally and effectively optimizes impressions.
- Small-Scale Evaluation: RLB wins Lin in 46 of 50 settings, ties once, and loses three times across campaigns and budget conditions.This corresponds to 92% wins, 2% ties, and 6% losses.
- Small-Scale Evaluation: 16.7% and 7.4% click improvements over Lin occur at 1/8 budget on iPinYou and YOYI, respectively.Under the same budget condition, RLB also attains more clicks with similar eCPC as episode length varies.
- Small-Scale Evaluation: When CTR-estimator AUC is below 70%, SS-MDP can compare favorably with Mcpc and Lin; with better AUC, CTR-aware methods attain more clicks.The comparison links SS-MDP’s relative performance to the quality of the CTR estimator.
- Large-Scale Evaluation: The neural network has relatively low RMSE against θ_avg, indicating good approximation to the exact algorithm within the trained state range.The large-scale results nevertheless show that direct neural-network generalization is unreliable at relatively large scales.
- Large-Scale Evaluation: RLB-NN outperforms Lin at c_0 = 1/32, 1/16, and 1/8 but underperforms at c_0 = 1/2 in the large-scale setting.RLB-NN-Seg, RLB-NN-MapD, and RLB-NN-MapA outperform Lin under every tested budget condition and are more stable.
7. ONLINE DEPLOYMENT AND A/B TEST
The proposed RLB model was deployed on a live RTB platform and compared with Lin under equal budgets. The online evaluation reports better click efficiency and more even spending over time for RLB.
- Deployment: RLB was deployed on Vlion DSP using a five-node bidding-agent cluster running Lua with Nginx.The deployment used HP ProLiant DL360p Gen8 servers with six-core CPUs and 64GB RAM per node.
- A/B test: The online comparison used Lin as the baseline, optimized clicks, and assigned both methods the same budget across episodes.The online process stopped when the budget was exhausted, with a per-episode bid limit determined partly by budget, CPM, and win rate.
- A/B test: At the same cost, RLB achieved lower eCPC than Lin and therefore more total clicks.The reported comparison identifies lower eCPC as RLB’s online cost-efficiency advantage.
- A/B test: RLB’s acquired clicks and spending increased more evenly over time than Lin’s, indicating better budget planning in the live evaluation.RLB also obtained lower CPM, more bids, and more winning impressions, while maintaining close CTR to Lin.
8. CONCLUSIONS
The paper presents model-based reinforcement learning for RTB bidding, using an MDP and neural networks to address large-scale auction volume and campaign budgets. Experiments show superiority over strong baselines on large-scale datasets and in an online A/B test, while future work targets model-free approaches and explicit budget pacing comparisons.
- RLB learns RTB bidding as a model-based reinforcement learning problem.The bidding policy maps campaign parameters and bid-request information to bidding actions within an MDP formulation.
- Experimental results on two large-scale real-world datasets and an online A/B test showed superiority over strong baselines and state-of-the-art methods.
- Future work will investigate model-free approaches to unify utility estimation, bid landscape forecasting, and bid optimization in highly dynamic environments.
- The authors will compare RLB with explicit budget pacing techniques.