Automated bidders ("autobidders") spend an advertiser's budget across millions of auctions. They do this by adjusting a single number, a bid multiplier, after each batch of auctions: if spend runs ahead of target, the multiplier shrinks, and if it runs behind, the multiplier grows. How fast it moves is set by a step size, and that one parameter carries two opposing demands. When the market drifts, through competitor entry, a switch from second-price to first-price rules, or seasonal traffic, the step must be large enough for the multiplier to keep up. When the step is large relative to how sharply spend responds to the multiplier, the update overshoots and oscillates. Recent theory shows that standard updates can even turn chaotic. This note proposes to measure that tension directly and to test one specific claim. The usable range of step sizes is set less by how much the market drifts than by how much the market's responsiveness (spend change per unit of multiplier change) varies over time. Once that variation exceeds a threshold, the range closes and no fixed step size works, however carefully it was tuned.
If the claim holds, two practical consequences follow. First, tuning sensitivity in production pacing is a measurable property of the market, and it can be forecast. Second, the right remedy is to divide the step by an online estimate of market responsiveness. Generic adaptive learning rates or reset schedules would not address the cause. The proposal also asks where this remedy stops working. When many autobidders apply it at once, the cross-bidder feedback loops that produce oscillation in existing theory remain, and we propose to quantify how much instability they leave behind.
Core Claim
Consider a pacing update $\lambda_{t+1} = \lambda_t + \eta\,(\text{spend}_t(\lambda_t) - \text{target}_t)$, where $\lambda_t$ is the multiplier's dual variable, $\eta$ is the step size, and $g_t = \partial\,\text{spend}_t/\partial\lambda$ is the market's local responsiveness. Two standard results bound the step size. The first is the stability condition for a linearized one-dimensional fixed-point iteration, which is also the point where the logistic-map behavior below first period-doubles. The second is the steady-state lag of a first-order tracker following a target that moves by $\delta$ per round, when the tolerated tracking error is $\epsilon$. Together they give
$$\frac{\delta}{\epsilon} \;<\; \eta\, g_t \;<\; 2 .$$
A fixed $\eta$ satisfies this window for every round only if the ratio $\kappa = \max_t g_t / \min_t g_t$ is below $2\epsilon/\delta$. Our central hypothesis is that, in realistic non-stationary auction traffic, $\kappa$ is what actually binds. Auction format changes and competitor entry can shift $g_t$ several-fold without moving the optimal multiplier much. In those markets, tuned fixed-step pacers fail in two ways at once: they oscillate in high-responsiveness periods and lag in low-responsiveness periods. Scaling the step by an estimate $\hat g_t$, so that $\eta_t = c/\hat g_t$, turns the condition into $\delta/\epsilon < c < 2$, which no longer depends on $\kappa$. The leftover constant $c$ should then be insensitive, meaning performance changes little across its range, and nearly untunable, meaning searching its range yields little gain over a default.
This is a self-gain argument for one bidder. In a market with $N$ adaptive bidders, stability depends on the spectral radius of the joint update's Jacobian. Normalization only rescales its diagonal. Our second claim is that a measurable share of the remaining instability lives in the off-diagonal, cross-bidder terms, and that per-bidder normalization cannot remove that share.
Relation to Prior Work
Three papers motivate the window. Complex Dynamics in Autobidding Systems models autobidding as differential equations in a smooth limit with infinitesimal items. It proves that three or more bidders can cycle indefinitely ("bidding repressilators"), and it explicitly leaves open how Mirror Descent or FTRL updates behave across practical step sizes. Chaos in Autobidding Auctions shows that discrete Mirror Descent pacing reduces to the logistic map and the Ricker population model, with period-3 orbits and Li–Yorke chaos. Its aim is to prove that chaos exists in particular parameter regimes, not to map stability boundaries or to propose stabilizing step rules. Our upper bound $\eta g < 2$ is the first period-doubling point of exactly that map, so our contribution is to place their chaotic regime inside a two-sided window that drift narrows from below. A Field Guide for Pacing Budget and ROS Constraints proves that chaining a return-on-spend (ROS) pacer and a budget pacer in sequence causes conflicting feedback loops and linear regret. Taking the pointwise minimum of the two bids ("Min-Pacing") avoids this. That analysis uses fixed market responses and does not study step-size sensitivity under shocks, and we supply that missing analysis.
Three other lines constrain the design. Robust Budget Pacing with a Single Sample shows that Dual FTRL degrades gracefully under shifts bounded in Wasserstein distance. Our regime, where $g_t$ changes several-fold, is precisely the one that bound does not cover, so Dual FTRL serves as a competitor rather than a counterexample. Online Second Price Auction with Semi-Bandit Feedback under the Non-Stationary Setting handles switching environments by detecting changes and resetting memory. That is a different remedy, and we test it head to head. Autobidders with Budget and ROI Constraints guarantees half of optimal liquid welfare even without convergence. This warns us that oscillation need not destroy welfare, so our metrics must include constraint violation and pacing error, not welfare alone.
HyperSHAP supplies the measurement method. It separates sensitivity (how much performance varies across a parameter's range) from tunability (how much searching that range gains over a default). It uses surrogate-based Shapley interaction indices and finds that interactions up to third order dominate. It has only been applied to static benchmarks. We reuse its tunability and sensitivity games in a setting where the task drifts. Complex Dynamics notes that pacers resemble proportional-integral-derivative controllers. Gain scheduling, meaning step sizes that adapt to the system's current responsiveness, is an old idea from control. We do not claim gain normalization is new as a mechanism. The new parts are three: the market-level prediction of when fixed tuning must fail, the multi-agent residual, and the measurement.
Research Program
The work has three parts. The first is analysis. We extend the one-bidder window to the coupled $N$-bidder map. We derive conditions under which simultaneous self-normalization keeps the joint Jacobian's spectral radius below one. We expect those conditions to fail for odd-length cyclic competition structures like the repressilators. We also analyze how the window shrinks when $\hat g_t$ is noisy. A multiplicative estimation error of $\pm\rho$ effectively widens $\kappa$ by $(1+\rho)/(1-\rho)$, which bounds how good the estimator must be.
The second part is the estimator. We will estimate $g_t$ in two ways. The first is a recursive regression of batch spend on recent multiplier changes. The second is small randomized bid perturbations, which cost a little revenue but give an unbiased local slope. We will apply each to Min-Pacing's budget and ROS multipliers separately. We will add a first-price variant in which spend is the bid times the win probability, so $g_t$ includes the change in bid shading.
The third part is measurement. For each pacer and each drift regime, we run HyperSHAP's sensitivity and tunability games over the pacer's parameters: step size or $c$, the estimator's forgetting factor, and the reset threshold where one is used. We also record the largest Lyapunov exponent of the multiplier trajectory, which measures how fast nearby trajectories diverge. A positive value indicates chaos.
Baselines
The naive reference is a constant-bid strategy and an unpaced auction. These are the reference points used in Real-Time Bidding Benchmarking with iPinYou Dataset, which reports 1,594 clicks for a linear bidder versus 242 for constant bidding at 1/32 budget. They are also the baselines in Practical Budget Pacing Algorithms and Simulation Test Bed for eBay Marketplace Sponsored Search, where the time-aware throttle BudgetTime reduces weighted pacing error by 39.5% relative to the unpaced baseline. We run BudgetTime as the heuristic competitor on budget-only campaigns.
The strongest existing method is Min-Pacing with a fixed step size, tuned per regime by an oracle. That makes it a deliberately generous competitor. The Field Guide reports 80% of campaigns finishing within 20% relative ROS error while capturing 86% of benchmark optimal value. Dual-Optimal pacing captures 81% of value at a 15% ROS error threshold. Both results are on their stationary semi-synthetic data. We also run Dual FTRL (Robust Budget Pacing with a Single Sample) and a change-detect-and-reset wrapper modeled on Elim-NS.
Every method gets the same traffic, the same horizon, and the same tuning budget: an equal number of full-horizon evaluations under random search. Each is reported twice. The first report uses parameters tuned on a stationary segment and deployed on the drifting segment, which is the realistic case. The second uses parameters tuned on the drifting segment itself, which is the oracle case.
Gain-normalized Min-Pacing beats the strongest baseline only under specific conditions. In regimes with large $\kappa$, it must match or exceed oracle-tuned fixed-step Min-Pacing on both captured value and the fraction of campaigns within the ROS error threshold. It must do so while deployed with a default $c$ that was never tuned on the drift. Matching oracle-tuned Min-Pacing only in small-$\kappa$ regimes is the expected null, not a win.
Two ablations isolate the key ingredient. In the first, the step is normalized by a deliberately wrong gain estimate, a constant equal to the stationary-period average. In the second, the step is normalized by a generic gradient-magnitude statistic, as in AdaGrad or RMSprop.
Why not just…?
Why not just pick a conservative step size that satisfies the stability bound? A small step stays under $\eta g < 2$ everywhere, but it violates the lower bound $\delta/\epsilon$ whenever responsiveness is low, so the pacer lags. Prior work on stability conditions in adaptive networks makes the general point that stability boundaries mark the edge of failure, not the best operating point. Our fixed-step sweep traces both edges directly. The claim is falsified if a single conservative step reaches oracle-tuned performance across all of our drift regimes.
Why not just use an adaptive optimizer like AdaGrad, or a decaying schedule? This is a serious threat, and we test it as an ablation rather than arguing it away. AdaGrad and RMSprop scale the step by the size of recent errors, not by the market's slope. A competitor entering the market can raise $g_t$ while errors are still small, and at that point a gradient-magnitude rule offers no protection against overshoot. Decaying schedules give up tracking altogether. If the gradient-magnitude ablation matches gain normalization in large-$\kappa$ regimes, our mechanism claim fails, and we will report that.
Why not just detect changes and reset, as Elim-NS does? Resets handle abrupt shifts in the target multiplier. They do nothing about a mismatch between the step size and responsiveness that persists after the reset. We expect resets to help in switching regimes where $\kappa$ is small, and to fail where the format change itself alters $g_t$. The head-to-head comparison across regimes separates these two cases.
Why not just retune the step size per campaign on recent logs? Retuning works when responsiveness is stable between the tuning window and the deployment window. The deployed-versus-oracle comparison in our protocol measures exactly how much is lost when it is not. HyperSHAP tunability measured on stationary segments compared with drifting segments tells us whether retuning is chasing a moving target.
Proposed Experiments
The first test validates the dynamics. We reproduce the discrete Mirror Descent regime from Chaos in Autobidding Auctions and confirm a positive Lyapunov exponent. Their continuous Chua construction reports about 0.14214, which serves as a sanity check on our estimator. We then show that gain normalization moves that same system into the stable band of $c$.
The main test runs in AuctionGym, the synthetic simulator of mixed first- and second-price auctions used by MiROCL. We control the drift rate $\delta$ and the responsiveness ratio $\kappa$ independently. To vary $\kappa$ without moving the optimal multiplier, we switch auction formats and inject competitors whose spend roughly cancels. The decisive check has three parts. The fraction of fixed step sizes achieving within 5% of oracle value should shrink to zero as $\kappa$ rises at fixed $\delta$. It should shrink much more slowly as $\delta$ rises at fixed $\kappa$. Over the same sweep, HyperSHAP tunability of $c$ under normalization should stay near zero, while tunability of $\eta$ without normalization should grow. If the fixed-step success fraction instead tracks $\delta$ rather than $\kappa$, the core claim is wrong.
The multi-agent test places 3 to 9 autobidders in cyclic competition structures modeled on the repressilators, all using normalized steps. We measure the remaining oscillation amplitude and the joint Jacobian's spectral radius, and we test whether odd-length cycles retain instability that even-length cycles lose.
The realism tests replay iPinYou budget traces and the eBay one-minute test bed for budget-only pacing. Weighted pacing error and clicks are the metrics, with BudgetTime as the comparison. For combined budget and ROS constraints, we reconstruct the Field Guide's semi-synthetic generator from its description: log-normal costs, Poisson clicks, and campaign parameters drawn as in that paper. The underlying 100,000 campaigns are not available to us. We then add structural shocks to that generator. If access permits, we run on the Alibaba in-distribution and out-of-distribution split. There, MiROCL reports a 30% improvement in its tolerance-aware comparative ratio over prior methods out of distribution, with baselines collapsing to near-zero utility. We treat it as the reference for heavy-shift robustness, not as a method to beat on its own terms, since it is a trained RL policy rather than a pacer.
References
- Complex Dynamics in Autobidding Systems
- Chaos in Autobidding Auctions
- A Field Guide for Pacing Budget and ROS Constraints
- Robust Budget Pacing with a Single Sample
- Online Second Price Auction with Semi-Bandit Feedback under the Non-Stationary Setting
- Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
- HyperSHAP: Shapley Values and Interactions for Explaining Hyperparameter Optimization
- Real-Time Bidding Benchmarking with iPinYou Dataset
- Practical Budget Pacing Algorithms and Simulation Test Bed for eBay Marketplace Sponsored Search
- A Robust Diffusion Minimum Kernel Risk-Sensitive Loss Algorithm over Multitask Sensor Networks
- Adversarial Constrained Bidding via Minimax Regret Optimization with Causality-Aware Reinforcement Learning