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](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)