hamverbot/bidding_algorithms_benchmark

Bidding Algorithms Benchmark — First-Price Auctions

Complete comparison framework for real-time bidding (RTB) algorithms in online advertising. Optimizing for clicks under budget constraints using Lagrangian dual methods. Latest benchmark: 200K rows (Criteox4), 5 independent runs, a10g GPU — [results/benchmark200Ka10g2026-05-05.json](results/benchmark200Ka10g2026-05-05.json) **Hyperparameter sweep**: 81 configs × 3 algos — [results/sweepsummary.json](results/sweep_summary.json)

Research Resources

• —[RESEARCH_RESOURCES.md](RESEARCH_RESOURCES.md) — Full literature survey: 26 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 items)

Problem Setup

• —Objective: Maximize number of clicks
• —Constraints: Total spend ≤ Budget, with k% minimum spend guarantee
• —Auction Type: First-price (winner pays their own bid)
• —Core Approach: Lagrangian dual multiplier with online error gradient descent (Wang et al. 2023)
• —Key Formula: λ{t+1} = max(0, λt − ε·(ρ − actual_cost))

Where:
  ρ = B/T         = target spend per auction  
  λ               = dual multiplier (pacing variable)
  ε               = learning rate (~1/√T)
  c̃_t(b)         = empirical expected cost of bidding b
  r̃_t(v,b)       = empirical expected reward for value v with bid b
  G̃_t(b)         = empirical win probability P(competing_bid ≤ b)

Benchmark Results (200K Criteo_x4, 10K auctions × 5 runs, a10g GPU)

Algorithm              Clicks       CPC   Budget%  WinRate
--------------------------------------------------------------
🥇 TwoSidedDual         285±8    33.41    95.0%    7.6%
🥈 ValueShading         258±7    38.82   100.0%    8.2%
🥉 DualOGD              248±9    31.18    77.3%    6.6%
   RLB                  136±13   74.34   100.0%    4.2%
   Threshold             71±4    70.36   ~50.0%    1.7%
   Linear                64±6    79.20   ~50.0%    2.0%

Key Insight: TwoSidedDual achieves 15% more clicks than DualOGD by maintaining the k=80% spend floor constraint. DualOGD alone gets too conservative (only 77% budget spent). The floor multiplier ν counteracts the natural conservatism of the cap multiplier μ.

CTR Model: Logistic Regression, AUC=0.6947. Upgrading to FinalMLP (AUC=0.8149) would improve all algorithms by better distinguishing high-value from low-value impressions.

Hyperparameter Sweep Results (81 configs × 3 algos × 3 price conditions)

Sweep on synthetic data (CTR ~25%, AUC=0.785), T=1500 auctions per config, 15 bid candidates per auction. Full results: [sweep_summary.json](results/sweep_summary.json)

By Market Condition

Key Sweep Findings

1. 1.TwoSidedDual wins every single market condition — 2.3–4.7× more clicks than DualOGD
2. 2.Optimal ε differs by algorithm: ε=0.003 for TwoSidedDual (slow/stable pacing), ε=0.03 for DualOGD (needs faster adaptation since it only has one constraint)
3. 3.k=0.95 is optimal for TwoSidedDual — near-full budget utilization is the dominant factor
4. 4.Low-competition markets give 1.7× more clicks than high-competition (292 vs 170 for TwoSidedDual)
5. 5.ValueShading tops out at 38.8% budget use — its closed-form pacing isn't precise enough to compete with grid-search optimization

How to Read the Config Codes

B{total_budget}_eps{ε}_k{minimum_spend_fraction}_{market_condition}

Example: B20000_eps0.003_k0.95_low = 20,000 budget, ε=0.003 learning rate, k=0.95 (must spend ≥95%), low-competition market.

Recommended Configs

Algorithm Descriptions

1. DualOGD — Lagrangian Dual + Online Gradient Descent ⭐

Paper: Wang et al. "Learning to Bid in Repeated First-Price Auctions with Budgets" (2023) arXiv: 2304.13477

How it works: The budget-constrained bidding problem is cast as a Lagrangian optimization. A single dual multiplier λ tracks whether you are over/under-spending relative to the target rate ρ = B/T (budget per auction).

Bid rule: b_t = argmax_b [(v−b)·G̃(b) − λ·b·G̃(b)]

• —Maximizes (expected reward minus λ × expected cost)
• —The penalty weight λ adapts online — no separate pacing module needed
• —Grid search over bid candidates to find the optimal bid

Update: λ ← max(0, λ − ε·(ρ − actual_cost))

• —Overspent → λ grows → future bids are penalized more → spend decreases
• —Underspent → λ shrinks → future bids are cheaper → spend increases

Regret bound: Õ(√T) — provably near-optimal under standard assumptions.

Required models: CTR predictor + empirical win probability CDF of competing bids.

Sweep insight: Best with ε=0.03 (fast learning). Without a floor, needs quick adaptation. Leaves 83% of budget unspent without floor constraint.

2. TwoSidedDual — Budget Cap + Spend Floor ⭐ BETTER

Extension of DualOGD. Two dual variables instead of one:

Effective multiplier: (μ − ν)

• —When μ > ν: cap dominates → bid conservatively (ahead on spend)
• —When ν > μ: floor dominates → bid aggressively (behind on spend floor)

Why it wins: The floor multiplier ν counteracts the natural conservatism of λ. If you get behind on your k% target, ν grows, making the effective penalty negative → bids increase. Once the floor is met, ν shrinks and μ takes over to cap spending.

Sweep insight: Best with ε=0.003 (slow, stable), k=0.95 (near-full budget utilization). Achieves 93% budget utilization across all market conditions. 2.3× more clicks than the next-best algorithm.

Winner for: Any campaign with a contractual minimum spend (brand campaigns, guaranteed-delivery deals).

3. ValueShading — Adaptive Bid Shading

First-price adaptation of second-price shading. In first-price auctions, bidding your true value guarantees zero surplus (winner's curse). ValueShading scales bids: bid = v / (1 + λ).

λ adapts online based on whether recent bids won or lost. Unlike DualOGD which does a grid search over bid candidates, ValueShading uses a closed-form shading formula — faster per auction (pool grid search).

Sweep insight: Best with ε=0.03. Uses only 39% of budget because the shading formula is conservative. 42% fewer clicks than TwoSidedDual but with 33% lower CPC when it does win.

Best for: Low-latency environments where per-auction compute must be <1ms.

4. RLB — Reinforcement Learning for Bidding

Paper: Cai et al. "Real-Time Bidding by Reinforcement Learning in Display Advertising" (WSDM 2017) arXiv: 1701.02490

Treats bidding as a Markov Decision Process:

• —State: (remainingbudgetratio, pCTR_bucket)
• —Action: bid_multiplier ∈ {0.1×, 0.3×, ..., 2.0×} of value
• —Reward: pCTR × valueperclick if won, else 0

Uses tabular Q-learning with ε-greedy exploration. The Q-table maps (budgetstate, impressionquality) → optimal bid_multiplier.

Current limitation: Spends the entire budget but achieves fewer clicks than adaptive algorithms. Tabular Q-learning needs many more auctions to converge (10K rounds × 10 budget buckets × 5 pCTR buckets = only ~200 visits per state). With more data, performance would improve, but tabular methods lack the regret guarantees of dual methods.

Best use case: Non-stationary environments where the RL agent continuously adapts, or as a benchmark against optimization-based approaches.

5. Linear — Proportional Bidding Baseline

bid = base_bid × (pCTR / avg_pCTR)

No adaptation to competition or budget pacing. Serves as the lower bound — any adaptive algorithm should beat this.

6. Threshold — Binary Bidding Baseline

bid = fixed_bid if pCTR > threshold else 0

Common "rule of thumb" in practice. Treats all above-threshold impressions equally — leaves value on the table.

Algorithm Comparison Matrix

Models

Datasets

Note on data: Criteox4 is 5.6GB across 37 Parquet files — streaming takes ~7 minutes. For fast iteration, `syntheticctr_50k` loads instantly (7.6MB) with matched CTR distribution (~25%) and AUC (~0.78).

Running the Benchmark

Main Benchmark (Criteo_x4 data)

# HF Jobs — 200K rows, 6 algos, 5 runs (~40 min)
python benchmark_job.py --max_rows 200000 --budget 10000 --T 10000 --n_runs 5

Hyperparameter Sweep (fast synthetic data)

# CPU sandbox — 81 configs, 3 algos (~60s)
python sweep_vectorized.py --T 1500

Via HF Jobs

hf_jobs.run(
    script="benchmark_job.py",
    dependencies=["numpy", "pandas", "scikit-learn", "datasets"],
    hardware="a10g-small",
    timeout="2h"
)

Structure

bidding_algorithms_benchmark/
├── README.md                          # this file
├── RESEARCH_RESOURCES.md              # Literature survey (26 papers)
├── AUDIT_TRAIL.md                     # Full resource audit (44 items)
├── benchmark_job.py                   # Self-contained benchmark (Criteo)
├── sweep_vectorized.py                # Vectorized sweep (synthetic data)
├── sweep_job.py                       # HF Jobs sweep launcher
├── src/
│   ├── ctr/
│   │   └── finalmlp_model.py         # FinalMLP CTR model
│   ├── price/
│   │   ├── empirical_cdf.py          # Online win prob CDF
│   │   └── torchsurv_model.py        # Deep survival win prob model
│   ├── algorithms/
│   │   ├── dual_ogd.py               # DualOGD + TwoSidedDual
│   │   └── baselines.py              # Linear, Threshold, ValueShading, RLB
│   └── benchmark/
│       ├── auction_simulator.py      # First-price auction simulation
│       ├── run_comparison.py         # Multi-algorithm runner
│       └── sweep.py                  # Grid search
├── results/
│   ├── benchmark_200K_a10g_2026-05-05.json   # Primary benchmark
│   ├── sweep_summary.json                     # Sweep results
│   └── benchmark_results.json                 # Earlier run
└── requirements.txt

Key Papers

Next Steps

1. 1.✅ ~~Benchmark all 6 algorithms on 200K Criteo rows~~ → Done
2. 2.✅ ~~Run hyperparameter sweep across budgets, ε, k, and market conditions~~ → Done
3. 3.Upgrade CTR model to FinalMLP (AUC 0.695 → 0.815) — will significantly improve all algorithms
4. 4.Real market price data — integrate iPinYou dataset (bid logs with actual competing bids)
5. 5.TorchSurv integration — replace empirical CDF with contextual win probability model
6. 6.Non-stationary evaluation — add distribution shift scenarios from paper 2505.02796

<!-- ml-intern-provenance -->

Generated by ML Intern

This model repository was generated by ML Intern, an agent for machine learning research and development on the Hugging Face Hub.

• —Try ML Intern: https://smolagents-ml-intern.hf.space
• —Source code: https://github.com/huggingface/ml-intern

Usage

from transformers import AutoModelForCausalLM, AutoTokenizer

model_id = 'hamverbot/bidding_algorithms_benchmark'
tokenizer = AutoTokenizer.from_pretrained(model_id)
model = AutoModelForCausalLM.from_pretrained(model_id)

For non-causal architectures, replace AutoModelForCausalLM with the appropriate AutoModel class.