Source-linked AI summary
Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertising
Junqi Jin, Chengru Song, Han Li, Kun Gai, Jun Wang, Weinan Zhang
TL;DR
RTB bidding requires strategic responses to other advertisers because bids depend on interacting market participants and constraints. The paper uses clustered multi-agent reinforcement learning and DCMAB, assigning cluster-level bidding agents and coordinating their actions in distributed workers. On industry-scale real-world data, cluster-based bidding outperforms single-agent and bandit approaches, while coordinated bidding achieves better overall objectives than purely self-interested bidding.
Problem
RTB bidding requires strategic responses to other advertisers because bids depend on interacting market participants and constraints.
Method
The paper uses clustered multi-agent reinforcement learning and DCMAB, assigning cluster-level bidding agents and coordinating their actions in distributed workers.
Results
Cluster-based bidding outperforms single-agent and bandit approaches, while coordinated bidding achieves better overall objectives than purely self-interested agents.
Takeaways & Limitations
DCMAB can balance self-interested and fully coordinated bidding, with cooperative rewards supporting a globally socially better objective.
Takeaways & Limitations
The evaluation is offline, and the authors were still preparing online deployment and live A/B testing; budget settings also constrain the evaluation.
Abstract
from arXiv · showhide
Real-time advertising allows advertisers to bid for each impression for a visiting user. To optimize specific goals such as maximizing revenue and return on investment (ROI) led by ad placements, advertisers not only need to estimate the relevance between the ads and user's interests, but most importantly require a strategic response with respect to other advertisers bidding in the market. In this paper, we formulate bidding optimization with multi-agent reinforcement learning. To deal with a large number of advertisers, we propose a clustering method and assign each cluster with a strategic bidding agent. A practical Distributed Coordinated Multi-Agent Bidding (DCMAB) has been proposed and implemented to balance the tradeoff between the competition and cooperation among advertisers. The empirical study on our industry-scaled real-world data has demonstrated the effectiveness of our methods. Our results show cluster-based bidding would largely outperform single-agent and bandit approaches, and the coordinated bidding achieves better overall objectives than purely self-interested bidding agents.
1 INTRODUCTION
The paper frames RTB bidding as a strategic multi-agent problem because bidders affect one another in a nonstationary market. It proposes clustered, distributed MARL to model these interactions at industry scale and coordinate bidding objectives.
- Optimal RTB bids depend on market prices, budgets, performance objectives, and opponents’ rationality, leaving strategic optimization unresolved.
- Existing methods often assume stationary market data or optimize one advertiser’s benefit, despite bidders’ strategies affecting one another.
- MARL models bidding-agent interactions, with each agent maximizing its payoff while responding strategically to other bidders’ changes.
- Clustering represents consumers and merchants as super-consumers and cluster-level bidding agents, making large-scale modeling computationally feasible.
- DCMAB stabilizes learning by feeding all agents’ bidding actions into each agent’s Q function, which evaluates future value jointly.
- Experiments use real industrial data and show coordinated bidding can achieve a higher cooperative goal than purely self-interested agents.
2 RELATED WORK
Prior RTB work mainly uses statistical, bandit, pacing, or single-agent reinforcement-learning methods. The paper instead extends multi-agent reinforcement learning with clustering and distributed processing to handle many interacting advertisers.
- Prior bidding methods optimize KPIs such as clicks or profit using linear, nonlinear, MDP, constrained-MDP, or deep-RL formulations.
- Pacing smooths spending over time but does not explicitly model other agents’ actions or coordinate advertisers toward a cooperative equilibrium.
- Multi-agent research studies cooperation through information sharing, parameter sharing, communication, and centralized critics such as MADDPG.
- The paper addresses advertiser scale and sparse rewards by clustering merchants into multiple agents and processing requests through distributed workers in parallel and asynchronously.
3 TAOBAO DISPLAY AD SYSTEM
Taobao’s display-ad system sequentially matches candidate ads, predicts click and conversion rates, ranks bids using eCPM, and displays the selected ads. Limited budgets turn sequential auctions into a multi-agent allocation problem that can produce inefficient equilibria.
- Matching recalls typically hundreds of candidate ads using user preferences and advertiser targeting settings.
- The RTP engine predicts pCTR and pCVR for each eligible advertisement before ranking.
- Candidate ads are ranked by descending bid × pCTR, the system’s effective cost-per-mille sorting mechanism, before display.
- Higher merchant revenue under the same budget implies higher ROI, while aggregate revenue also aligns with consumer experience and platform GMV.
- With limited budgets, severe early competition can make merchants exit early and reduce late-auction matching efficiency.
4 MULTI-AGENT ADVERTISING BIDDING
The paper formulates RTB as a stochastic game in which clustered bidding agents choose bid adjustments while responding to one another. DCMAB combines multi-agent learning with distributed, periodic state aggregation and impression-level bid information.
- 4.1 RTB as a Stochastic Game: RTB is modeled as a stochastic game with agent-specific states, actions, transitions, rewards, and objectives based on each agent’s expected return.Each action is a bid adjustment ratio, and rewards depend on the state and all agents’ actions.
- 4.1 RTB as a Stochastic Game: Merchant and consumer clustering reduces the computational cost of modeling large-scale bidding while representing merchants as cluster-level agents and consumers as super-consumers.Merchants are clustered by daily total revenue and consumers by daily contributed revenue.
- 4.1 RTB as a Stochastic Game: Each merchant cluster produces consumer-cluster-specific bid adjustments, while the final adjustment scales manually set bids within a bounded range.The platform computes final bids as bidk × (1 + α), with α constrained to [−range, range] and range = 0.9 in the experiment.
- 4.2 Bidding by Multi-Agent RL: The MARL formulation uses deterministic policy gradients and Nash-equilibrium reasoning so each agent responds to the policies and actions of other agents.The critic evaluates joint actions, while actor updates optimize one agent while holding the others’ parameters fixed.
- 4.3 Implementation & Distributed Architecture: DCMAB periodically merges distributed workers’ states and transition information, then updates actors and critics using aggregated consumer-action distributions.The method supports asynchronous execution and uses real-time pCVR information alongside periodic consumer distributions and static features.
- 4.3 Implementation & Distributed Architecture: The final bid adjustment factorizes into a coarse cluster-level action and a merchant-specific real-time ratio based on pCVR relative to its seven-day average.The cluster action applies broadly within a merchant cluster, while the pCVR ratio differentiates merchants and reflects impression-level conversion value.
2 Initialize replay memory D
Algorithm 1 initializes exploration and agent states, executes actions asynchronously across parallel workers, periodically aggregates rewards and costs, and updates the critic and actor from replay memory.
- 2 Initialize replay memory D: The algorithm initializes replay memory and a random exploration process before receiving the initial state for all agents.Initial states are followed by per-agent action computation with exploration noise.
- 2 Initialize replay memory D: During each Tp interval, parallel workers compute impression-level bid adjustments, execute auctions, and record each agent’s rewards and costs.Actions and state-transition processing occur asynchronously at different frequencies.
- 2 Initialize replay memory D: At the end of each interval, the system merges rewards and costs, updates the state, and stores transition tuples in replay memory.The stored tuple includes the state, consumer-action distribution, joint actions, reward, and next state.
- 2 Initialize replay memory D: Training samples minibatches from replay memory, minimizes critic loss, and updates the actor using the corresponding gradient rule.These updates use the paper’s equations for critic and actor learning.
- 2 Initialize replay memory D: The offline simulator mirrors the online system’s upstream and downstream data flow and distributed-worker design for reinforcement-learning experiments.The paper reports that all experiments are based on this offline simulator.
5 EXPERIMENTS
The experiments use replayed Taobao display-ad data from the Guess What You Like homepage to train and test DCMAB offline.
- 5 EXPERIMENTS: Experiments use Taobao display-ad data collected from the Guess What You Like column of the App Homepage.The setting contains three display-ad slots and hundreds of recommendation slots.
5.1 Data Sets and Evaluation Setup
The evaluation uses replayed production logs, separate sampled training and test periods, and budget settings derived from total cost under unlimited bidding.
- 5.1 Data Sets and Evaluation Setup: The offline simulator replays consumer requests using pCTR, pCVR, and ppb to compute states and rewards.Training uses sampled data from 20180110, while testing uses sampled data from 20180111.
- 5.1 Data Sets and Evaluation Setup: Merchant budgets are set as fractions of the total cost accumulated under manually set bids with unlimited budgets.The setup avoids the trivial behavior in which unlimited-budget merchants always choose the highest bid.
- 5.1 Data Sets and Evaluation Setup: The training set contains 203,195 impressions, while the testing set contains 212,910 impressions.The passage also reports corresponding revenue statistics under CT and CT/3 budget settings.
5.2 Compared Methods
The comparison evaluates DCMAB against manual bids, contextual bandits, A2C, and DDPG. DCMAB differs by combining clustered-agent modeling with a critic that uses all agents’ actions.
- Manual bids are human-set bids based on experience.
- Contextual Bandit optimizes each impression independently from contextual features and does not allocate budgets across time.
- A2C is an on-policy actor-critic method without replay memory, and its critic excludes other agents’ actions.
- DDPG is an off-policy learning algorithm with replay memory, but its critic excludes other agents’ actions.
- DCMAB upgrades MADDPG with clustered agents and distributed-platform actor–critic structures, using all agents’ actions in its critic.
5.3 Hyperparameter Tuning
The experiments tune merchant clustering and examine revenue across cluster counts, coordination settings, and budget ratios. Three clusters perform best, while coordinated DCMAB maintains higher revenue than manually set bids across tested budgets.
- Clustering Method: Merchants are ranked by training-data revenue and grouped into clusters with approximately equal presence across consumer requests.
- Number of Clusters: The study tests cluster counts of 1, 2, 3, 4, 5, 10, and 30 using either coordinated or self-interest rewards, with total traffic revenue as the metric.
- Number of Clusters: Total traffic revenue peaks at 3 and 4 clusters, rises from 1 to 3, then drops as the cluster count increases from 4 to 30.
- Budget Ratio: With three clusters, coordinated DCMAB consistently earns higher revenue than manually set bids, including when budgets are low.
5.4 Experimental Results
The experiments compare learning algorithms, equilibria, and reward coordination on industrial data. DCMAB learns stably and quickly, improves total revenue over baselines, and achieves higher overall revenue as coordination expands.
- Performance Comparisons: The baseline comparison uses tuned settings with three merchant and consumer clusters, self-interest rewards, and four repeated experiments reported with averages and standard deviations.
- Performance Comparisons: DCMAB has Pareto improvement over every algorithm except DDPG, while DDPG also improves over manual bids and the contextual bandit.
- Performance Comparisons: DCMAB reaches a higher total revenue of 18199 than DDPG’s 16359 and a more stable equilibrium with lower standard deviations.
- Performance Comparisons: DCMAB converges more stably than DDPG and learns faster than A2C and the bandit.
- Coordination vs. Self-interest: Coordination improves total revenue over self-interest, although Agent1 and Agent2 receive less revenue while Agent3 improves substantially.
- Coordination vs. Self-interest: Coord1 raises total revenue from 5347 to 9004 versus Manual, primarily through Agent1’s increase from 231 to 4040.
- Coordination vs. Self-interest: Coord2 raises total revenue from 9004 to 14569 by reallocating traffic, while Agent1’s revenue falls from 4040 to 3370 and Agent2’s rises from 806 to 7088.
- Coordination vs. Self-interest: Full coordination produces the highest total revenue, increasing it from Coord2’s 14569 to 19501 by reallocating traffic toward Agent3.
6 CONCLUSIONS
The paper presents DCMAB, a distributed multi-agent reinforcement-learning solution for display-advertising RTB that models interactions among merchants. It incorporates auction and user information, supports self-interested or coordinated bidding, and reports stronger performance than single-agent approaches alongside promising offline coordination results.
- DCMAB models the interactions of all merchants bidding together through multi-agent reinforcement learning for RTB display advertising.
- The method uses historic auction features, user feedback, other agents’ actions, and budget constraints to inform bidding.
- DCMAB supports bidding that is fully self-interested or fully coordinated, allowing coordination toward a socially better objective.
- The distributed-worker implementation processes auctions in parallel and asynchronously at product scale.
- DCMAB outperforms state-of-the-art single-agent reinforcement-learning approaches, while offline evaluation reports promising coordinated results.