PaperlayerView exact revision on arXiv

Source-linked AI summary

Budget Constrained Bidding by Model-free Reinforcement Learning in Display Advertising

Di Wu, Xiujun Chen, Xun Yang, Hao Wang, Qing Tan, Xiaoxun Zhang, Jian Xu, Kun Gai

arXiv:1802.08365v6cs.AI

TL;DR

Budget-constrained RTB bidding must maximize impression value despite a volatile, non-stationary auction environment that makes the optimal scaling factor difficult to obtain. The paper uses model-free deep reinforcement learning with redesigned rewards and reports improved performance over RL-based baselines and widely used bidding methods.

  • Problem

    Budget-constrained bidding seeks to maximize winning-impression value, but the optimal scaling factor is difficult to obtain in real time because auction environments are highly non-stationary.

  • Method

    The paper formulates bidding as λ control and trains a model-free reinforcement-learning agent with RewardNet-based rewards and dynamically adjusted exploration.

  • Results

    DRLB outperforms FLB, BSLB, and RLB overall by 100.92%, 18.33%, and 16.80%, respectively, and remains stronger when λ-deviation is large.

  • Takeaways & Limitations

    The framework significantly outperforms widely used bidding methods on real-world data and avoids the expensive computational cost associated with model-based reinforcement learning.

  • Takeaways & Limitations

    The equivalence between the new-reward optimal policy and the original policy holds only when there is one initial state and the MDP is deterministic.

Abstract

from arXiv · show

Real-time bidding (RTB) is an important mechanism in online display advertising, where a proper bid for each page view plays an essential role for good marketing results. Budget constrained bidding is a typical scenario in RTB where the advertisers hope to maximize the total value of the winning impressions under a pre-set budget constraint. However, the optimal bidding strategy is hard to be derived due to the complexity and volatility of the auction environment. To address these challenges, in this paper, we formulate budget constrained bidding as a Markov Decision Process and propose a model-free reinforcement learning framework to resolve the optimization problem. Our analysis shows that the immediate reward from environment is misleading under a critical resource constraint. Therefore, we innovate a reward function design methodology for the reinforcement learning problems with constraints. Based on the new reward design, we employ a deep neural network to learn the appropriate reward so that the optimal policy can be learned effectively. Different from the prior model-based work, which suffers from the scalability problem, our framework is easy to be deployed in large-scale industrial applications. The experimental evaluations demonstrate the effectiveness of our framework on large-scale real datasets.

1 INTRODUCTION

Budget constrained bidding seeks to maximize winning-impression value under a budget, but dynamic auctions and changing campaign settings make the optimal bidding parameter difficult to obtain. The paper proposes model-free reinforcement learning with redesigned rewards for scalable industrial deployment.

  • 1 INTRODUCTION: Budget constrained bidding maximizes the total value of winning impressions while respecting an advertiser-set budget.Advertisers can specify goals such as maximizing clicks or conversions, and the strategy calculates bids for individual impression opportunities.
  • 1 INTRODUCTION: The optimal scaling parameter λ is difficult to obtain because RTB marketplaces are highly dynamic and campaign settings can change.Thousands of heterogeneous bidders compete for opportunities, while advertisers may alter budgets and target audiences.
  • 1 INTRODUCTION: The paper trains an agent to regulate λ sequentially, adapting bids to a non-stationary environment without directly producing bids.This model-free approach retains the theoretical bidding strategy while avoiding the expensive computation associated with model-based reinforcement learning.
  • 1 INTRODUCTION: Immediate reward can drive suboptimal behavior because it neglects the budget constraint and encourages reducing λ for larger short-term gains.The proposed reward design methodology addresses this issue, alongside an adaptive ϵ-greedy policy for exploration.
  • 1 INTRODUCTION: The framework combines model-free reinforcement learning, deep neural networks, and policy-optimization innovations, and has been deployed and validated in industry-scale advertising systems.The paper presents the approach as applicable to large-scale industrial advertising.

2 BACKGROUND

The paper models budget constrained bidding as sequential auctions that maximize impression value under a spending limit, and relates the problem to reinforcement learning and constrained decision processes. Under second-price auctions, the theoretical bid uses impression value divided by a scaling factor, but the optimal factor is difficult to obtain online.

  • 2.1 Budget Constrained Bidding: An advertiser bids on sequential impression opportunities, wins when its bid is highest, pays the auction cost, and stops when budget B is exhausted or opportunities end.The objective is to maximize the total value of won impressions under the budget.
  • 2.1 Budget Constrained Bidding: Budget constrained bidding is formalized as a knapsack problem, with prior work showing that the second-price optimal bid has the form v/λ.Here, v denotes impression value and λ is a scaling factor.
  • 2.1 Budget Constrained Bidding: The optimal λ is difficult to obtain because real-time bidding occurs without advance knowledge of candidate impressions in a highly non-stationary auction environment.When the impression sequence is known beforehand, λ can instead be derived through greedy approximation.
  • 2.2 Reinforcement Learning and Constrained Markov Decision Process: Reinforcement learning models an agent that interacts with an environment through states, actions, transitions, rewards, policies, and a discount factor.The agent seeks a policy maximizing expected cumulative discounted return.
  • 2.2 Reinforcement Learning and Constrained Markov Decision Process: A constrained Markov decision process extends an MDP by adding constraints on cumulative costs.These costs can include multiple types, each with its own constraint.

3 METHOD

The paper models budget-constrained bidding as a λ-control problem in a CMDP and solves it with model-free deep reinforcement learning. It identifies why immediate rewards can produce suboptimal bidding and proposes an episodic reward design that incorporates the constraint while supporting scalable learning.

  • 3.1 Modeling: Model-free RL avoids requiring transition dynamics, addressing the non-stationary and computationally costly environment that limits model-based CMDP methods in RTB.The paper uses DQN to represent the action-value function with a deep neural network.
  • 3.1 Modeling: Budget-constrained bidding is modeled as an episodic CMDP in which the agent sequentially adjusts λ, bids with v_i/λ_t, and maximizes total impression value under budget B.The state includes time, remaining budget, regulation opportunities, budget consumption rate, CPM, win rate, and prior reward; actions adjust λ by predefined rates.
  • 3.2 Reward Function Design Trap: Immediate reward can drive λ downward because aggressive bidding wins more impressions, causing the agent to neglect the budget constraint and converge to suboptimal policies.The resulting early budget consumption can prevent exploration of more valuable impressions later in the episode.
  • 3.2.2 A Reward Design Methodology: The proposed reward methodology assigns an episode-level return to state-action pairs and updates it during policy optimization, while avoiding the need to tune a punishment coefficient α.The methodology is intended to encode the constraint, remain easy to implement, and generalize to other resource-constrained RL problems.
  • 3.2.2 A Reward Design Methodology: Under a deterministic MDP with fixed T steps and one initial state, the optimal policy under the new reward is guaranteed to remain optimal under the original immediate reward.This equivalence depends on the stated determinism and single-initial-state assumptions.
  • 3.3–3.4 Policy and Framework: DRLB combines DQN with an adaptive ϵ-greedy policy that increases exploration when the action-value distribution is not unimodal.The framework regulates λ rather than directly producing bids and is presented as a deployable model-free approach.

4 EXPERIMENTAL RESULTS

The experiments compare DRLB with baseline bidding methods on two large-scale datasets, including analyses of reward design and adaptive exploration.

  • DRLB is evaluated against several baseline methods and the state-of-the-art RLB on two large-scale datasets.The study also examines the reward function design and adaptive ϵ-greedy policy.

4.1 Experimental Setup

The evaluation uses two advertising datasets, CTR- or click-based value metrics, and comparisons against industrial and reinforcement-learning baselines.

  • Experimental Setup: Dataset A contains 2 billion impressions from 10 continuous days, while Dataset B is an iPinYou dataset augmented with predicted CTR.For both datasets, seven days are used for training and three for evaluation.
  • Experimental Setup: The objective is to maximize the total value of winning impressions under a budget, measured by predicted CTR or real clicks.Dataset A uses predicted CTR because click events are unavailable for lost impressions; Dataset B can use real clicks.
  • Baseline Methods: DRLB is compared with Fixed Linear Bidding, Budget Smoothed Linear Bidding, and model-based Reinforcement Learning to Bid.FLB uses a fixed λ0, whereas BSLB adjusts bidding using budget and time consumption information.
  • Implementation: DRLB uses neural-network value and reward models with seven actions corresponding to λ adjustment rates from -8% to 8%.The networks each have three hidden layers with 100 nodes per layer, and λ is adjusted every time step.

4.2 Evaluation Results on Dataset A

On Dataset A, DRLB generally outperforms the baselines across λ-deviation groups and remains more effective when the initial bidding parameter is far from optimal.

  • Evaluation Results on Dataset A: 100.92%, 18.33%, and 16.80% are DRLB’s overall improvements over FLB, BSLB, and RLB, respectively.DRLB almost outperforms all three methods in each of the nine λ-deviation groups.
  • Evaluation Results on Dataset A: When λ-deviation is [-100%, -80%), DRLB achieves average R/R∗ of 0.878, versus 0.436 for FLB, 0.525 for BSLB, and 0.430 for RLB.The baselines degrade substantially as λ-deviation increases, while DRLB retains desirable performance.
  • Evaluation Results on Dataset A: Testing environments can differ substantially from training environments, making training-data statistics such as budget and market-price distributions unreliable.FLB is described as unaware of auction dynamics, while RLB assumes a stationary market-price distribution.
  • Evaluation Results on Dataset A: DRLB outperforms BSLB because it uses auction information for λ control and can react promptly through a state representing the environment comprehensively.BSLB considers only budget and time and is less sensitive to elapsed time early in the day.

4.3 Evaluation Results on Dataset B

On Dataset B, DRLB improves acquired clicks overall relative to RLB, but its performance is weaker on campaigns with poor CTR prediction accuracy.

  • Evaluation Results on Dataset B: 4.3% is DRLB’s overall improvement in acquired clicks over RLB, with improvements in 5 of 9 campaigns.DRLB usually performs worse than RLB on campaigns with low AUCs.
  • Evaluation Results on Dataset B: Low AUCs indicate poor CTR prediction accuracy, and DRLB’s linear bidding uses predicted CTR as the impression value.The passage identifies improving CTR prediction as a separate effort that can directly improve DRLB’s performance.

4.4 Convergence Comparison with Immediate Reward Function

RewardNet avoids the greedy behavior induced by immediate reward and reaches a substantially better policy in fewer training steps. Immediate reward favors early gains that exhaust the budget, whereas RewardNet produces a distribution closer to the ideal policy.

  • RewardNet reaches R/R∗=0.893 within a small number of steps, while immediate reward reaches only R/R∗=0.418.
  • Immediate reward encourages higher rewards in early steps, exhausting the budget and harming long-term performance.
  • RewardNet produces a reward distribution similar to that generated by the theoretically optimal λ∗.

4.5 Effectiveness of the Adaptive ϵ-greedy Policy

The adaptive ϵ-greedy policy improves exploration and performance under both tested annealing rates. Its advantage is especially pronounced when the annealing rate is higher, where it also enables faster convergence.

  • Adaptive ϵ-greedy achieves better performance than original ϵ-greedy at both rϵ=2e-5 and rϵ=1e-5.
  • Adaptive exploration enables fast convergence and significantly outperforms original ϵ-greedy at the higher annealing rate.

5 RELATED WORK

Related work includes truthful or model-based bidding methods, budget-smoothing approaches, and reinforcement-learning formulations for auction environments. The supplied evaluation materials compare methods across λ-deviation groups and report AUC and click outcomes on another dataset.

  • Impression-value estimation supports impression-level bidding, but truthful bidding can perform poorly in repeated auctions with budget constraints.
  • Table 1 compares R/R∗ improvements across nine λ-deviation groups, and Table 2 reports AUC and real clicks for DRLB and RLB on Dataset B.
  • Model-based reinforcement-learning methods formulate bidding as an MDP, while other approaches target sponsored-search bidding, impression guarantees, or smoother budget spending.

6 CONCLUSION

The paper presents model-free deep reinforcement learning for budget-constrained RTB bidding, using λ control, RewardNet, and adaptive exploration. Experiments on real-world data report fast convergence and significant improvements over widely used bidding methods, while RewardNet is proposed as a general idea for some deterministic MDPs.

  • The method formulates budget-constrained bidding as a λ-control problem and solves it with model-free deep reinforcement learning.
  • RewardNet replaces immediate reward to address the reward-design trap that impedes convergence to the optimum.
  • Dynamic adjustment of the random probability in ϵ-greedy alleviates insufficient exploration.
  • Experiments on real-world datasets show fast convergence and significant outperformance of widely used bidding methods.
  • RewardNet is presented as applicable to other deterministic MDP problems where long-term results matter and reward functions are difficult to design.
Loading 1802.08365v6…