| # 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](RESEARCH_RESOURCES.md)** — Full literature survey covering 32 papers across bidding algorithms, CTR prediction, and clearing price models |
| - **[AUDIT_TRAIL.md](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](https://arxiv.org/abs/2304.13477) |
| - Balseiro et al. (2020): "Dual Mirror Descent for Online Allocation" [arXiv:2011.10124](https://arxiv.org/abs/2011.10124) |
| - Feng et al. (2022): "Online Bidding for RoS Constrained Advertisers" [arXiv:2208.13713](https://arxiv.org/abs/2208.13713) |
| - Cai et al. (2017): "Real-Time Bidding by Reinforcement Learning" [arXiv:1701.02490](https://arxiv.org/abs/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](https://arxiv.org/abs/2304.00902) |
| - Wang et al. (2023): "GDCN: Gated Deep Cross Network" [arXiv:2311.04635](https://arxiv.org/abs/2311.04635) |
| - Wang et al. (2021): "DCN V2" [arXiv:2008.13535](https://arxiv.org/abs/2008.13535) |
| - Zhu et al. (2021): "BARS-CTR Benchmark" [arXiv:2009.05794](https://arxiv.org/abs/2009.05794) |
|
|
| ### Clearing Price Prediction |
| - Wu et al. (2015): "Predicting Winning Price with Censored Data" (KDD) |
| - TorchSurv: Deep Survival Analysis [arXiv:2404.10761](https://arxiv.org/abs/2404.10761) |
|
|
