When an advertiser switches to a new bid shading policy (a rule for bidding below what an impression is worth, so that winning a first-price auction still leaves a profit), the usual way to test it offline is to replay historical auction logs. Replay assumes everyone else keeps bidding as they did before. In a real exchange, competitors run their own learning bidders and react, so the surplus a new policy earns after the market settles can differ from what replay predicts. Simulating that reaction is the honest alternative, but it is expensive: each estimate needs many long runs of a market full of learning agents, and the answer only becomes accurate as the simulated adaptation gets long and finely resolved.
This note proposes treating that simulation the way computational finance treats a stochastic differential equation. We would use multilevel Monte Carlo, an estimator that combines many cheap, coarse simulations with a few expensive, fine ones, and that simulates coarse and fine versions of the same random auction stream in lockstep so that their difference has small variance. In our setting the level of the hierarchy is the time resolution of the competitors' learning dynamics. The main obstacle is specific to auctions. The payoff jumps from $v-b$ to zero the moment a bid falls a cent below the clearing price, and that jump destroys the coupling between levels on which multilevel methods depend. We would remove it by integrating out a small exogenous price noise analytically, which turns the jump into a smooth win probability. The deliverable is an estimator of post-adaptation surplus whose cost grows like that of plain Monte Carlo on a cheap model, together with a test of whether that accuracy changes which shading policy one would deploy.
Core Claim
Fix a candidate shading policy $\pi$, a market of $K$ competitors who update their bids by a stochastic learning rule with step size $h$, and a window of "virtual time" over which the market adapts. Let $X_h(\pi)$ be the advertiser's average surplus over the last part of that window when the dynamics are simulated with step size $h$. The quantity we want is the small-step limit $\mathbb{E}[X_0(\pi)]$, meaning the surplus under the continuous-time adaptation that the learners approximate. With levels $h_l = h_0 2^{-l}$, the telescoping identity used throughout the multilevel literature (Multilevel Monte-Carlo for Solving POMDPs Online) gives
$$\mathbb{E}[X_{h_L}] = \mathbb{E}[X_{h_0}] + \sum_{l=1}^{L}\mathbb{E}\big[X_{h_l} - X_{h_{l-1}}\big],$$
where each difference is estimated from paired runs. Within a pair, the fine run takes two updates on two consecutive auctions and the coarse run takes one update with doubled step size on the averaged signal from the same two auctions. This is the step-halving coupling familiar from solvers for stochastic differential equations, applied to a stochastic-approximation process.
The auction-specific ingredient is smoothing. The win indicator $\mathbf{1}(b>m)$, where $m$ is the highest competing bid, is replaced by its conditional expectation given everything except a small independent perturbation $\xi$ of the clearing price, for example a reserve-price jitter. The per-auction payoff then becomes
$$\tilde u(b) = (v-b)\,F_\xi(b - \bar m),$$
where $\bar m$ is the unperturbed competing bid and $F_\xi$ is the distribution function of $\xi$. Without smoothing, a coarse and a fine path that disagree slightly about $\bar m$ produce an order-one gap whenever $b$ lands between them. That is exactly the failure the research file flags for applying Lipschitz-based rates such as those of Optimal randomized multilevel Monte Carlo for repeatedly nested expectations to auction payoffs. With smoothing, the level-difference variance should decay at least linearly in $h$, because the smoothed payoff is differentiable and the coupled paths differ by $O(h)$ for a stable stochastic approximation. Under the standard multilevel complexity theorem, that decay brings the cost to reach root-mean-square error $\varepsilon$ down to roughly $O(\varepsilon^{-2})$, up to logarithmic factors, from $O(\varepsilon^{-3})$ for single-level simulation. This mirrors the reduction reported for option pricing and nested estimation (An Introduction to Multilevel Monte Carlo for Option Valuation; Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need).
Relation to Prior Work
The bid shading literature supplies the policies we would evaluate, and it evaluates them in ways that hold competitors fixed. Factorization machines trained with an asymmetric loss (Bid Shading in The Brave New World of First-Price Auctions) and deep distribution networks that predict a log-normal winning-price distribution and then search over bids (An Efficient Deep Distribution Network for Bid Shading in First-Price Auctions) were validated by offline replay and online A/B tests. MINMAX (Simultaneous Optimization of Bid Shading and Internal Auction for Demand-Side Platforms) learns monotone bid functions end to end and is evaluated on iPinYou logs as a static landscape. Our proposal changes none of these policies. It changes the yardstick, asking how each performs once rivals respond.
Work on learning dynamics in first-price auctions both motivates and constrains the target. Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions studies when mean-based learners settle to equilibrium, which is what makes a post-adaptation surplus meaningful. Where convergence fails, we fall back on a fixed virtual-time window rather than a limit, so the estimand stays well defined. The no-regret autobidding papers (No-Regret Online Autobidding Algorithms in First-price Auctions; No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints) provide realistic learning rules for the simulated competitors. They are ingredients of the simulator, not competitors to the estimator.
On the multilevel side, we reuse the coupling-by-common-random-numbers idea used in stochastic network and Langevin simulation (Efficient Steady-state Simulation of High-dimensional Stochastic Networks; Uncertainty quantification for generalized Langevin dynamics). We borrow the integer sample allocation of A Multifidelity Monte Carlo Method for Realistic Computational Budgets for the small budgets a practitioner would actually spend per candidate policy. The closest bridge to sequential bidding is Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework, which forecasts constraint violations one step ahead and does no rollouts. We deliberately do not attempt the obvious combination of multilevel Monte Carlo with multi-step budget look-ahead. Reactive pacing already attains $O(\sqrt{T})$ regret under full feedback, so the payoff of that combination is doubtful. Our use of multilevel estimation targets an evaluation problem where the expense is real and no cheap exact method exists.
Research Program
We would first build a market simulator. Impression values come from click-through-rate predictions trained on iPinYou, following the valuation pipeline of Real-Time Bidding Benchmarking with iPinYou Dataset. Competitors are initialized so that their joint highest bid matches the logged paying-price distribution, and they then adapt with mean-based or primal-dual learning rules at step size $h$. The level-zero model has no adaptation, so its estimate collapses to log replay with a fitted log-normal landscape, which has a closed-form expected surplus. That makes it nearly free and a natural base for the hierarchy.
Second, we would derive and verify the variance decay of the smoothed level differences. Concretely, we would measure the decay exponents for the mean and variance of $X_{h_l}-X_{h_{l-1}}$ across levels, with and without smoothing, and over a range of noise scales for $\xi$. The noise scale trades bias against variance, so we would report it as an explicit parameter rather than tune it silently. Smaller noise makes the estimand closer to the hard-indicator market, but it also makes the smoothed payoff steeper, which slows variance decay.
Third, we would use the estimator for its purpose: ranking candidate policies, and choosing the asymmetry parameter $\gamma$ of a factorization-machine shader under adaptive competition, at a fixed compute budget per candidate.
Baselines
The naive reference point is static log replay, the evaluation used for the factorization-machine, distribution-network and MINMAX results. On iPinYou it is the level-zero estimate alone. It costs almost nothing and is biased by exactly the competitor response we want to capture. The comparison is over the same candidate policies and the same valuations. Beating it means its policy ranking or its selected $\gamma$ differs from ground truth, and ours does not, by a margin larger than our error bars.
The strongest competitor for the estimation task is single-level Monte Carlo at the finest step size, given the same wall-clock budget, the same random-number streams and the same seeds. We also run a two-level multifidelity control-variate estimator that uses the closed-form log-normal surplus as the control, with sample sizes chosen by the integer allocation of A Multifidelity Monte Carlo Method for Realistic Computational Budgets. Every estimator gets the same pilot budget for estimating variances and correlations. Ground truth is a very large single-level run at a step size one level finer than any estimator uses. Beating these baselines means lower mean squared error at equal cost on every tested budget, and a cost-versus-error slope near $-2$ in log-log terms against their roughly $-3$. For this estimation task, no reported result was found on Lacuna for multilevel or multifidelity estimation of auction surplus. The only reported numbers concern policy quality under static evaluation: MINMAX reports a 7.42% surplus lift and a 22.75% profit lift over baselines on iPinYou (Simultaneous Optimization of Bid Shading and Internal Auction for Demand-Side Platforms), and the distribution network reports a 9.65% offline surplus lift over point-estimation models (An Efficient Deep Distribution Network for Bid Shading in First-Price Auctions). We will check whether gaps of this size survive adaptation.
The key ablation is the same multilevel estimator with the hard indicator in place of the smoothed payoff. If smoothing is the essential ingredient, this ablation should show level-difference variance that plateaus instead of decaying, and a cost slope no better than single-level Monte Carlo.
Why not just…?
Why not just trust log replay, as production systems already do? Replay is the method behind the reported A/B-consistent lifts, and if competitors in realistic markets barely move, replay is good enough and this proposal loses its motivation. We treat this as a real threat. The first experiment measures, across competitor learning rules and adaptation speeds, how often the policy ranking from replay disagrees with the post-adaptation ranking. If disagreements are rare and small relative to the reported lifts, we will report that as a negative result.
Why not just use one cheap control variate instead of a full hierarchy? A two-level multifidelity estimator is simpler. If the static landscape is already highly correlated with post-adaptation surplus, it may capture most of the gain. Its weakness should appear when adaptation is substantial: the correlation between replay and the fully adapted surplus then drops, and the variance reduction of a single control is bounded by that correlation. The head-to-head comparison at matched cost settles this. We expect the hierarchy to win mainly in the strong-adaptation regime and will say so if it does not.
Why not just buy more compute and run plain Monte Carlo? Any estimator wins with enough compute. The question is whether evaluating dozens of candidate policies or $\gamma$ values fits a daily budget. The measured cost-versus-error slopes answer this directly. If the smoothed level differences fail to decay faster than the cost per level grows, plain Monte Carlo is the right choice, and the ablation will show it.
Why not just compute the equilibrium analytically? Closed-form first-price equilibria exist only under symmetric, independent value assumptions. Heterogeneous learning bidders with budgets, seeded from real logs, have no such formula, and they may not reach equilibrium within the horizon that matters commercially. That is why the estimand is defined over a virtual-time window.
Proposed Experiments
The decisive checks run in order. First, on the iPinYou-seeded simulator with mean-based and primal-dual competitors, we estimate the decay exponents for the mean and variance of the level differences, with and without smoothing, over three noise scales. The method is viable only if the smoothed variance decays at a rate at least equal to the growth in per-level cost. Second, we plot root-mean-square error against cost for single-level Monte Carlo, two-level control variates and the multilevel estimator, against brute-force ground truth. Third, for the factorization-machine shader, the distribution-network shader and a MINMAX-style monotone shader, we compare post-adaptation surplus with replay surplus and record ranking reversals and the regret in surplus of the $\gamma$ chosen under each evaluation. Finally, to check that the gains do not depend on one data source, we repeat the variance-decay measurement in a fully synthetic market with known log-normal competitors, where the level-zero model is exact before adaptation. The project succeeds only if the first two checks hold and the third shows that the accuracy changes a deployment decision.
References
- Multilevel Monte-Carlo for Solving POMDPs Online.
- Optimal randomized multilevel Monte Carlo for repeatedly nested expectations
- An Introduction to Multilevel Monte Carlo for Option Valuation
- Accelerating Look-ahead in Bayesian Optimization: Multilevel Monte Carlo is All you Need
- Bid Shading in The Brave New World of First-Price Auctions
- An Efficient Deep Distribution Network for Bid Shading in First-Price Auctions
- Simultaneous Optimization of Bid Shading and Internal Auction for Demand-Side Platforms
- Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions
- No-Regret Online Autobidding Algorithms in First-price Auctions
- No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints
- Efficient Steady-State Simulation of High-Dimensional Stochastic Networks
- Uncertainty quantification for generalized Langevin dynamics
- A Multifidelity Monte Carlo Method for Realistic Computational Budgets
- Towards Safe and Optimal Online Bidding: A Modular Look-ahead Lyapunov Framework
- Real-Time Bidding Benchmarking with iPinYou Dataset