README.md

RTB Bidding Algorithm Comparison

This repository contains the results of comparing different bidding algorithms for Real-Time Bidding (RTB) in online advertising, optimizing for clicks under budget constraints.

📚 NEW: Complete research resources are now available:

• RESEARCH_RESOURCES.md — Full literature survey covering 32 papers across bidding algorithms, CTR prediction, and clearing price models
• AUDIT_TRAIL.md — Every paper, dataset, codebase, and external resource consulted (44 total)

Problem Setup

• Objective: Maximize number of clicks
• Constraint: Total spend ≤ Budget, with ~100% budget utilization target
• Auction Type: First-price auctions
• Models Used:
  • CTR Prediction: Logistic Regression (simplified from FinalMLP)
  • Clearing Price: Gradient Boosting Regressor (simplified from Deep Cox PH)

Algorithms Compared

Algorithm	Type	Description
Linear	Static	bid = base_bid × (pCTR / avg_pCTR)
ORTB	Static	bid = √(c·pCTR/λ + c²) − c
DualOGD	Adaptive	Online gradient descent on Lagrangian multiplier
Threshold	Static	Fixed bid if pCTR > threshold, else 0
MPC	Adaptive	Model Predictive Control maximizing expected value

Results on Synthetic Data

Algorithm	Clicks	CTR	Budget Used	CPC	Efficiency
DualOGD	1331	0.5133	99.99%	7.51	1331.12
MPC	440	0.4878	100.00%	22.73	440.00
Linear	167	0.5076	99.90%	59.82	167.16
Threshold	110	0.5500	100.00%	90.91	110.00
ORTB	85	0.5152	99.87%	117.50	85.11

Results on Real Criteo Data (100K rows, CTR=25.7%)

Algorithm	Clicks	CTR	Budget Used	CPC
DualOGD	584	0.2421	100.00%	8.56
Linear	63	0.2593	100.00%	79.36
ORTB	47	0.2597	99.94%	106.32
Threshold	41	0.2470	99.60%	121.46

Key Findings

1. DualOGD dominates on both datasets — 9× better than Linear on real Criteo data
2. Adaptive algorithms significantly outperform static approaches in first-price auctions
3. ORTB performs poorly in first-price auctions (designed for second-price)
4. All algorithms achieve ~100% budget utilization as required
5. DualOGD has the lowest CPC — most cost-efficient

Files

• train.py — Full training and comparison script
• results.json — Synthetic data results
• results_real.json — Real Criteo data results
• RESEARCH_RESOURCES.md — Complete literature survey (32 papers)
• AUDIT_TRAIL.md — Every resource consulted (44 items)

Recommended Next Steps (from research)

1. Upgrade CTR model: Replace LogisticRegression with FinalMLP (AAAI 2023, Criteo AUC 0.8149)
2. Add clearing price model: Use TorchSurv for censored regression
3. Add Balseiro dual mirror descent: Second-price baseline for comparison
4. Two-sided budget constraint: Add spend floor (k% minimum) with second dual variable
5. Hyperparameter sweep: Step size ε, budget fraction k%, value per click

References

Bidding Algorithms

• Wang et al. (2023): "Learning to Bid in Repeated First-Price Auctions with Budgets" arXiv:2304.13477
• Balseiro et al. (2020): "Dual Mirror Descent for Online Allocation" arXiv:2011.10124
• Feng et al. (2022): "Online Bidding for RoS Constrained Advertisers" arXiv:2208.13713
• Cai et al. (2017): "Real-Time Bidding by Reinforcement Learning" arXiv:1701.02490
• Zhang et al. (2014): "Optimal Real-Time Bidding for Display Advertising" (KDD)

CTR Prediction

• Mao et al. (2023): "FinalMLP: Two-Stream MLP for CTR" arXiv:2304.00902
• Wang et al. (2023): "GDCN: Gated Deep Cross Network" arXiv:2311.04635
• Wang et al. (2021): "DCN V2" arXiv:2008.13535
• Zhu et al. (2021): "BARS-CTR Benchmark" arXiv:2009.05794

Clearing Price Prediction

• Wu et al. (2015): "Predicting Winning Price with Censored Data" (KDD)
• TorchSurv: Deep Survival Analysis arXiv:2404.10761