Real-Time Bidding by Reinforcement Learning in Display Advertising

In plain words

An advertiser buys ad slots one at a time, each in its own real-time auction, and has a fixed budget to spend over a fixed number of auctions. Each bid decides whether the slot is won, and paying for it reduces the budget that the later auctions can use. This paper treats the whole campaign as a sequence of decisions. The state is how many auctions and how much money are left, plus the details of the current ad request. The method works backward from the end of the campaign to find, for each state, the value of the clicks still to come. Each new bid is then set by asking whether the expected click value of this request is worth the value lost by paying its price.

Exact calculation needs a table with one entry per combination of auctions and budget, which is too large for real campaigns. The paper fits a small neural network to the table and also gives ways to reuse the table for larger campaigns. The results come from replaying logged auctions and from one live A/B test, all reported by the authors.

TL;DR

• An impression-level bid is modelled as an MDP over (auctions left, budget left, request features). The reward is the predicted click-through rate (pCTR) of a won impression §3.1, §3.2.
• Exact value iteration costs O(TB) time and memory, where T is the episode length and B the budget §4.1. The bid is a threshold on the change in value from spending each price §4.
• For large T and B, a network with two tanh hidden layers (30 and 15 units) approximates the value differences D(t, b). Segmentation and state-mapping variants reuse the small table §4.1, §6.2.
• Author-reported gains: 16.7% more clicks than the Lin baseline at a 1/8 budget on iPinYou and 7.4% on YOYI §6.1. An online A/B test reports a 44.7% click improvement over a widely used industry method §1.

Problem

A campaign has a budget and a lifetime measured in auctions, and the target is the number of clicks it wins §3.1, §5.2. Bidding is repeated in every auction, so a bid changes the budget the later auctions can use. The paper argues that truthful second-price bidding and static bidding functions ignore this coupling, and that budget pacing adds a separate control step §1, §2. Earlier MDP bidding work (SS-MDP) was built for keyword-level sponsored search and ignores the features of each request §2, §5.3. Exact dynamic programming over the (auctions, budget) grid needs O(TB) time and memory, so it fails at real auction volumes and budgets §4.1.

Method

1. Episode and state §3.1. An episode has T auctions and a budget B. At each step the agent sees the number of auctions left t, the unspent budget b, and the one-hot feature vector x of the request. It chooses an integer bid a in {0, ..., b}. If a is at least the market price δ, it wins, pays δ, and receives the request's pCTR θ(x) as reward. Otherwise it gets nothing. The market price has density m(δ, x) §3.1, §3.2. Integer bids are required §4.

2. Transitions and reward §3.2. Winning at price δ ≤ a moves the state to (t−1, b−δ) with reward θ(x_t). Losing moves it to (t−1, b) with reward 0. The discount factor is 1, because the target is the total click count regardless of when the clicks happen §3.2.

3. Value recursion §4. The value V(t, b, x) is the best expected clicks from the state. Maximising over bids gives a recursion in V(t−1, ·). Because x is unobserved in the value table, the paper marginalises it out using the approximation m(δ, x) ≈ m(δ) and the average CTR θ_avg, which follows the dependency chain x → θ → bid → winning rate from prior work §4. This gives the table recursion in the equation below.

4. Bid rule §4. For a request with pCTR θ(x), define g(δ) = θ(x) + V(t−1, b−δ) − V(t−1, b). Bid b if g(b) ≥ 0. Otherwise bid the largest A with g(A) ≥ 0 and g(A+1) < 0. The paper argues that g decreases in δ, so this threshold is the optimal bid §4.

5. Algorithm 1 alg. 1. Fill the table with t from 1 to T and b from 0 to B by the recursion. At serve time, scan δ from 0 to min(δ_max, b) and keep the largest δ with g(δ) ≥ 0 alg. 1.

# Small-scale RLB: value table, then the bid rule  [alg. 1] [§4]
# m[d]: probability that the market price equals d  [§4]
# V[t][b]: expected clicks with t auctions and budget b left  [§4]

def expected_clicks(V, m, theta_avg, t, b, a):
    # Expected clicks from state (t, b) when bidding a  [§4]
    total = 0
    for d in range(len(m)):
        if d <= a:
            # Win at price d: one click on average, budget falls by d  [§4]
            total += m[d] * (theta_avg + V[t - 1][b - d])
        else:
            # Lose: budget is kept and no click is earned  [§4]
            total += m[d] * V[t - 1][b]
    return total

def build_value_table(m, theta_avg, T, B, D_max):
    # With no auctions left the expected clicks are zero  [§4]
    V = zeros((T + 1, B + 1))
    for t in range(1, T + 1):
        for b in range(B + 1):
            # Keep the bid that maximises expected clicks  [alg. 1]
            V[t][b] = max(
                expected_clicks(V, m, theta_avg, t, b, a)
                for a in range(min(D_max, b) + 1)
            )
    return V

def bid(V, t, b, theta, D_max):
    # Keep the largest delta whose gain is not negative  [alg. 1]
    best = 0
    for delta in range(min(D_max, b) + 1):
        gain = theta + V[t - 1][b - delta] - V[t - 1][b]
        if gain >= 0:
            best = delta
    return best

The recursion for the table, with the approximation above, is

V(t, b) \approx \max_{0 \le a \le b} \Big\{ \sum_{\delta=0}^{a} m(\delta)\big(\theta_{\text{avg}} + V(t-1, b-\delta)\big) + V(t-1, b) \sum_{\delta=a+1}^{\infty} m(\delta) \Big\} §4

The bid differential that drives the rule is

g(\delta) = \theta(x) + V(t-1, b-\delta) - V(t-1, b) §4

6. Large-scale value differences §4.1. The network works on the difference D(t, b) = V(t, b+1) − V(t, b) rather than on V, because V is much larger than θ_avg while D is on the scale of the CTR. Since V(t−1, b−δ) − V(t−1, b) = −Σ_{δ'=1}^{δ} D(t−1, b−δ'), the bid rule can use D directly §4.1. The network has two inputs (t, b), two tanh hidden layers of 30 and 15 units, and a linear output for D §4.1, §6.2.

7. Scaling variants §4.1. Four ways are proposed to use the approximation at the full horizon T and budget B:

• RLB-NN: use the network everywhere §5.3.
• Coarse-to-fine segmentation (RLB-NN-Seg): split the episode into segments of length T0 and give each segment a share of the remaining budget [§4.1, §5.3].
• State mapping of D (RLB-NN-MapD): for t > T0, use D(T0, b/t × T0) [§4.1, §5.3].
• State mapping of the action (RLB-NN-MapA): for t > T0, use a(T0, b/t × T0, x) §4.1, §5.3.

Hyperparameters

Results

Author-reported. Offline setup: test records replayed episode by episode with budget B; a bid wins when it is at least the market price; the metric is clicks §5.2. Baselines: SS-MDP, Mcpc (bid = CPC × pCTR), and Lin (bid = b0 × pCTR / θ_avg), all with the same logistic-regression CTR model and the same non-parametric market-price model §5.3.

The paper's text gives the headline numbers. The large-scale and online results are shown only as figures, and the text does not give their values §6.2, §7.

Paper vs code

The repository is linked by the paper's footnote §5.1, and its owner (han-cai) matches author Han Cai. Checked at commit 1eeb9e4. The repository has no LICENSE file, so no code is quoted here and code_license is not stated. Equation numbers are cited by section because the LaTeX source was read but not compiled.

• θ_avg. The paper says it is the expected pCTR from historical data §4. The code uses training clicks divided by training impressions, which is the observed click rate, not the mean predicted CTR rlb_dp_i.py rlb_dp_fa.py.
• Market-price pmf. The paper says the market price is estimated by non-parametric counting §2. The code adds 1 to every count (Laplace smoothing) utility.py.
• Value-iteration shortcut. The code tracks a value V_max, accumulated as if the budget never binds. For each round it stops the update early at the first budget whose value reaches V_max, and fills the higher budgets with V_max. The paper has no such step rlb_dp_i.py rlb_dp_i.py.
• Clamping. The code clamps the network's D prediction at zero. The paper does not mention this rlb_dp_fa.py.
• Mapping beyond the trained budget. The paper's MapD maps only when t > T0 §4.1. The code also maps when b > B0, to (n × B0 / b, B0) [code: python/rlb_dp_fa.py#L133-L136].
• Training range. The paper trains on {0..T0} × {0..B0} with T0 = 10,000 §6.2. The code trains on N = 5000 episodes and uses only budgets from 800 up, with a stored table for smaller states func_approx.py func_approx.py rlb_dp_fa.py.
• Segmentation and action mapping. RLB-NN-Seg and RLB-NN-MapA are described in the paper §4.1, §5.3. The repository has no code for either. No segmentation or action-mapping code was found when searching the Python files.
• SS-MDP. The paper says SS-MDP ignores the features of each request §5.3. The code's SS-MDP bid compares the request's own pCTR with the value differences ss_mdp.py.
• Lin tuning. The paper says b0 is tuned on training data §5.3. The code searches b0 in steps of 6 and stops after 5 steps without improvement lin_bid.py.
• Data. The repository includes the iPinYou test scores and info files for the nine campaigns. It has no YOYI data and no training split [code: data/ipinyou-data]. The README says its demo table uses only the first 350,000 lines per campaign at c0 = 1/32 and T = 1,000, so its numbers do not match the paper's tables README.md.
• Episode length name. The paper calls it T. The code calls it N rlb_dp_i.py.

Pitfalls

• Expected reward, not observed clicks. The agent optimises the pCTR of each won impression §3.1. The evaluation counts actual clicks §5.2. The paper notes that methods built on the CTR model gain less when that model is weak (AUC below 70%) §6.1.
• Independence assumption. The value table assumes that the market price distribution does not depend on the features, m(δ, x) ≈ m(δ) §4. The paper relaxes this only by splitting the feature space into segments §4.
• Integer bids and ties. Bids are integers, and a bid equal to the market price wins §4 §5.2 rlb_dp_i.py.
• Budget depends on training CPM. B = CPM_train × 10^-3 × T × c0 §5.2, so B grows with T at a fixed c0. Changing T or c0 changes the budget, and the budget grid, with it.
• Memory. Exact value iteration needs O(TB) time and space §4.1. The network removes the table but needs a training run, and the paper does not give its cost §6.2.
• Approximation range. The paper reports RMSE only for states inside the trained box §6.2, tab. 4. Its own text says the network's generalisation is "satisfactory only in small scales" §6.2.
• Mapping choices. MapD and MapA rest on the paper's observation that D decreases in t and increases in b, and that a increases in b §4.1. The deviation figure for the linear mapping shows one campaign fig. 6.
• Figures. Large-scale and online results appear only as figures. Do not quote numbers for them from the text §6.2, §7.
• Online test. The A/B test uses a fixed number of campaigns and days, a logistic-regression model trained with FTRL, and a budget split across episodes §7. No significance test is reported.
• Licensing. The paper is CC BY 4.0 (recorded by wikillm fetch). The repository has no licence file, so no code is granted for reuse. This card cites the code and quotes none of it.

Lineage

• Builds on: the MDP framework and dynamic programming from standard RL texts §2 (Sutton & Barto, Introduction to Reinforcement Learning), and the budget-optimised MDP for sponsored search of Amin et al. (SS-MDP) [§2, §5.3].
• Builds on: the logistic-regression utility model of Lee et al., and the non-linear bidding-function studies of Zhang et al. §2. No card exists for these.
• Compared against: SS-MDP, Mcpc, and Lin (Perlich et al.) §5.3. The Lin baseline is the industry standard the paper names §5.3.
• Superseded by: not known from content on this wiki.