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
- DualOGD dominates on both datasets — 9× better than Linear on real Criteo data
- Adaptive algorithms significantly outperform static approaches in first-price auctions
- ORTB performs poorly in first-price auctions (designed for second-price)
- All algorithms achieve ~100% budget utilization as required
- DualOGD has the lowest CPC — most cost-efficient
Files
train.py — Full training and comparison scriptresults.json — Synthetic data resultsresults_real.json — Real Criteo data resultsRESEARCH_RESOURCES.md — Complete literature survey (32 papers)AUDIT_TRAIL.md — Every resource consulted (44 items)
Recommended Next Steps (from research)
- Upgrade CTR model: Replace LogisticRegression with FinalMLP (AAAI 2023, Criteo AUC 0.8149)
- Add clearing price model: Use TorchSurv for censored regression
- Add Balseiro dual mirror descent: Second-price baseline for comparison
- Two-sided budget constraint: Add spend floor (k% minimum) with second dual variable
- 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
