Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertising

Introduction

• RTB requires strategic bidding because optimal bids depend on market conditions and competing advertisers, despite second-price auctions theoretically encouraging truthful bids under strong assumptions.In practice, bid prices, budget constraints, performance objectives, and opponent behavior affect bidding; changes by one bidder can influence others and may undermine system-wide optimality.Source: §1 · p. 1
• Prior statistical methods often assume stationary markets, while single-party optimization can overlook bidder interactions and harm other parties’ benefits [1] [28] [33].Earlier work includes two-stage bandit modeling [33] and reinforcement learning for sequential bid optimization [1] [28], but bidder strategies also affect one another.Source: §1 · p. 1
• The paper formulates RTB as a game-theoretic multi-agent reinforcement learning problem, with agents maximizing their own payoffs while responding strategically to other bidders.The authors argue this approach can lead agents toward an equilibrium, unlike prior methods [1] [28] [33].Source: §1 · p. 1
• The study evaluates MARL on real Taobao advertising data at industrial scale, presenting it as an early realistic application beyond the simulated games common in prior MARL research [17].Taobao serves over 400 million active users, and its RTB exchange reaches more than 100 million active audiences daily.Source: §1 · p. 1
• To make large-scale MARL feasible, the authors cluster consumers into super-consumers and merchants into groups represented by bidding agents, then propose DCMAB to stabilize learning.Because agents explore simultaneously in a non-stationary, noisy auction environment, DCMAB feeds all agents’ bidding actions into each agent’s Q function to estimate future value [17].Source: §1 · pp. 1–2
• The distributed solution is integrated with Taobao’s worker system, and real-world experiments show advantages over strong baselines, while coordinated bidding can improve merchants’ cooperative goal [14].The authors caution that self-interested agents’ equilibrium need not be socially optimal and therefore develop a model that learns from a shared objective.Source: §1 · p. 2

Bid Optimization in RTB

• Earlier RTB bid-optimization methods use linear or nonlinear impression valuation but treat bidding as static, limiting their ability to handle dynamic situations and rational bidders.Perlich et al. introduced linear bidding; Zhang et al. identified a nonlinear relationship between optimal bids and impression evaluation.Source: §2 · p. 2
• Reinforcement-learning approaches adapt to KPI constraints, but prior work optimizes one advertiser at a time, treating competitors as part of the environment [1] [28].Prior work includes MDP-based budget allocation [1], constrained MDPs, and DQN without a budget constraint [28].Source: §2 · p. 2
• Pacing smooths spending with traffic fluctuations, but as a single-agent method it neither models other bidders’ actions nor coordinates cooperation toward equilibrium [13, 29].Source: §2 · p. 2

Multi-agent Reinforcement Learning

• Multi-agent research improves collective rewards through information sharing, parameter sharing, communication, and centralized training, but MADDPG was demonstrated in a toy simulation [7] [17] [19].Taobao’s framework is motivated by balancing consumers’, advertisers’, and the platform’s interests while advertisers compete for impressions and cooperate for user experience.Source: §2 · p. 2
• The proposed approach extends deterministic policy gradient with advertiser clustering and distributed processing to handle Taobao’s scale and asynchronous parallel workers.Modeling each advertiser separately would exceed the processing capacity of current multi-agent methods and leave rewards sparse for most agents.Source: §2 · p. 2

Taobao Display Ad System

• Matching, real-time prediction, and ranking process requests sequentially; eligible ads are ranked by bid × pCTR (eCPM) before display.Matching recalls typically hundreds of candidates while reflecting merchants’ behavior-targeting settings; the prediction engine estimates pCTR and pCVR for each eligible ad.Source: §3 · p. 2, Figure 1 · p. 3
• Bids affect ad rankings and consumer–merchant connections, so authorized bid adjustments can align products with purchase-intent consumers and benefit consumers, merchants, and the platform.Merchants authorize the platform to adjust manually set bids within an acceptable range.Source: §3 · p. 2
• Merchants seek revenue and ROI under predefined budgets; clicked ads incur GSP/CPC costs, while losing auctions incurs no payment and exhausted budgets end participation.A winning ad can be clicked and converted into a purchase; higher revenue for the same budget means higher ROI.Source: §3 · p. 3
• Sequential auctions form a multi-agent bidding game [1], where intense early competition can exhaust budgets and leave late auctions less competitive and less efficient.Merchants must allocate budgets to appropriate consumers and times across competition environments to support socially optimal outcomes.Source: §3 · p. 3

4.1 RTB as a Stochastic Game

• Merchant clusters act as bidding agents, while consumer clusters provide state features and help control the computational and exploration costs of modeling every merchant individually.The clusters are formed using merchants’ total daily revenue and consumers’ contributed daily revenue; increasing the number of clusters approaches the individual-merchant formulation.Source: §4.1 · p. 3, Figure 2 · p. 4
• Agents observe cumulative cost and revenue by merchant-consumer cluster plus consumer features, adjust fixed bids using learned actions, and earn revenue rewards under fixed budgets.The paper treats revenue maximization as ROI maximization when merchants spend their predefined budgets; it does not consider leaving budget unspent to pursue higher ROI.Source: §4.1 · pp. 3–4

4.2 Bidding by Multi-Agent RL

• Because bid adjustments are continuous, the paper uses deterministic policy gradients, with actor policies and Q-function critics to learn agents’ bidding strategies.The update approach adjusts each agent’s critic and policy while holding the other agents’ parameters fixed.Source: §4.2 · p. 4

4.3 Implementation & Distributed Architecture

• DCMAB addresses asynchronous distributed RTB workers by merging states and saving transition tuples periodically, while generating actions for every auction in real time.The periodic interval is denoted Tp; separating these frequencies avoids merging every request’s state transition while retaining per-auction execution.Source: §4.3 · p. 5
• DCMAB combines cluster-level learned adjustments with impression-level pCVR ratios, and summarizes executed cluster-pair actions as a distribution for critic updates.The actor computes merchant- and consumer-cluster actions ahead of each interval; each auction’s action is multiplied by its merchant-level pCVR relative to a seven-day historical average and clipped to the allowed adjustment range.Source: §4.3 · p. 5

2 Initialize replay memory D

• Each agent computes an exploratory action by adding noise from the initialized random process.The algorithm initializes the exploration process N and computes each agent’s action with N_t.Source: §2 · p. 6
• Agents receive initial states before the algorithm runs auctions in parallel workers over T_p.Source: §2 · p. 6
• For each parallel auction, agents compute bid ratios and a combined adjusting ratio α, then execute.Source: §2 · p. 6
• Agents record rewards and costs, merge results from the last T_p auctions, update the state, and store the resulting transition in replay memory.Source: §2 · p. 6
• Training samples a random minibatch from replay memory to update the critic using Eqs. (9)–(10) and the actor using Eq. (11).Source: §2 · p. 6
• All experiments use an offline simulator with online-identical upstream and downstream data flows and a distributed-worker design intended to meet online service requirements.The paper reports that the offline system is being transferred online for DCMAB A/B testing.Source: §2 · p. 6

• Experiments use Taobao App Homepage’s Guess What You Like column, which has three display-ad slots and hundreds of recommendation slots.Source: §5 · p. 6
• Collected market bid prices, consumer feedback, and conversions enable offline replay to train and test DCMAB.Source: §5 · p. 6
• The experimental settings are similar to those in prior research [1] [28] [33].Source: §5 · p. 6

Data Sets and Evaluation Setup

• Experiments use production display-ad data from Taobao App’s “Guess What You Like” homepage, with the first three hours of 20180110 logs for training and 20180111 logs for testing.Both sets are uniformly sampled at 1/20; all reported results use test data because real consumer feedback is unavailable.Source: §5.1 · p. 6
• Budgets are set as a fraction of total cost CT under manually set unlimited bids; the training set has 203,195 impressions and the test set 212,910.The sets contain 150,134 registered consumers and 294,768 registered merchants in total; revenue is measured in CNY.Source: §5.1 · p. 6
• Evaluation measures agent and total-traffic revenue, ROI, and CPA under predefined budgets and auction counts, with CPA defined as cost/click.The stated merchant objective is to maximize revenue given its budget; reward changes are also analyzed for their effects on converged equilibrium.Source: §5.1 · p. 6
• The offline simulator ranks bids by maximum eCPM, awards each auction to the top three merchants, and estimates costs and revenue from pCTR, pCVR, and ppb.It approximates expected CPC using the GSP mechanism and expected revenue as pCTR × pCVR × ppb; the distributed platform uses 40 nodes and TensorFlow.Source: §5.1 · p. 6
• The simulator updates states hourly and evaluates three-hour episodes comprising three state transitions; each training task takes about 4 hours with 40 distributed workers.The three-hour training data contains 203,195 impressions, counted as actor executions.Source: §5.1 · p. 6

Manually Set Bids

• Manually Set Bids are real bids set by humans according to their experience.Source: §5.2 · p. 7

Contextual Bandit

• Contextual Bandit [15] adjusts each impression’s bid from its context, including other agents’ actions, but does not optimize budget allocation over time.It optimizes each time step independently.Source: §5.2 · p. 7

Advantageous Actor-critic (A2C)

• A2C is an on-policy actor-critic without memory replay, and its critic does not take other agents’ actions as input.Source: §5.2 · p. 7

DDPG

• DDPG [16] is an off-policy learning algorithm with memory replay, and its critic does not take other agents’ actions as input.Source: §5.2 · p. 7

DCMAB

• DCMAB upgrades MADDPG [17] with clustered-agent modeling and actor–critic structures redesigned for distributed workers; its critic takes all agents’ actions as input.All methods use the same settings; except manually set bids, they use neural networks as approximators.Source: §5.2 · p. 7

5.3 Hyperparameter Tuning

• For each request, the system filters n merchants to nc candidates (nc ≪ n), then revenue-clusters merchants into groups with roughly equal training-request presences.Consumers are also revenue-ranked and clustered so each cluster accounts for an equal share of requests; clustering uses recent logs and can incorporate other features for business needs.Source: §5.3.1 · p. 7

5.3.2 Number of Clusters.

• Three clusters performed best overall (four was also strong), so follow-up experiments fixed three; performance fell as cluster count rose from 4 to 30.The tests compared 1, 2, 3, 4, 5, 10, and 30 clusters using total traffic revenue. Coordinated rewards assigned each cluster total traffic revenue; self-interest rewards assigned each cluster its own revenue.Source: §5.3.2 · p. 7, Figure 5 · p. 7
• With three clusters, coordinated DCMAB maintained higher revenue than manually set bids even at low budgets; over 99% of each given budget was spent.The budget range extended from one-third to the full unlimited budget; the authors attribute DCMAB’s low-budget advantage to better budget allocation.Source: §5.3.3 · p. 7, Figure 5 · p. 7

5.4.1 Performance Comparisons.

• DCMAB reached total revenue of 18199 versus DDPG’s 16359 and had lower revenue standard deviations, while improving all clusters’ and total revenue over every algorithm except DDPG.Table 2 reports converged performance averaged over four experiments; DCMAB and DDPG reached different equilibria, with some clusters earning more under DDPG.Source: §5.4.1 · p. 8
• DCMAB achieved the highest ROI for AgentC1, AgentC3, and Total, and lower CPA for the same agents and Total than competing bids.The paper defines ROI as revenue/cost and CPA as cost/click; nearly all agents spent their budgets.Source: §5.4.1 · p. 8
• DCMAB converged more stably than DDPG, and DCMAB and DDPG learned faster than A2C and Bandit.The authors attribute stability to modeling all agents’ actions and faster learning to deterministic policy gradients with memory replay.Source: §5.4.1 · p. 8
• Coord achieved better total revenue than Self-Interest, although Agent1 and Agent2 earned less as Agent3’s larger gain raised the total.Self-Interest assigns each agent its own revenue as reward; Coord gives all agents total traffic revenue as their reward.Source: §5.4.2 · p. 8

5.4.2 Coordination vs. Self-interest.

• Total revenue rose from 5347 under Manual to 9004 with Coord1, 14569 with Coord2, and 19501 with Coord, as coordination expanded across agents.The gains came with traffic reallocations and lower revenue for some agents, while Coord allowed Agent3 to contribute more to the total.Source: §5.4.2 · p. 8

6 CONCLUSIONS

• DCMAB models interactions among merchants bidding together and uses other agents’ actions, auction history, user feedback, and budget constraints to optimize bidding strategies.Its bidding can range from fully self-interested to fully coordinated; full coordination aims to balance consumers’, merchants’, and the platform’s benefits.Source: §6 · pp. 8–9
• DCMAB outperforms state-of-the-art single-agent reinforcement-learning approaches, while fully cooperative rewards enable agents to pursue a globally socially better objective.The authors report promising offline evaluation results and say they are in the process of deploying DCMAB online.Source: §6 · p. 9, Figure 6 · p. 9, Figure 7 · p. 9
• The authors implemented DCMAB in a product-scale distributed-worker system integrated with parallel, asynchronous auctions, and plan a Taobao live A/B test focused on mobile display ads.They report that offline evaluation results are promising.Source: §6 · p. 9