Automated bidding agents now buy most online ad impressions on behalf of advertisers. A typical agent tries to win as much value (clicks, conversions) as it can across thousands of auctions, without overspending a budget and while keeping total value divided by total spend, its return on investment (ROI), above a target. Every algorithm in this literature assumes the campaign runs to the end of a fixed horizon. When the market turns bad, the agent can only shade its bids downward and keep participating.
Work on autonomous agents in robotics and computer use shows that deciding when to stop is a separate, hard problem with two failure modes. Agents either keep going after the goal is out of reach, or they quit early on noisy evidence. We propose giving autobidders an explicit exit action and controlling its premature-termination error with a distribution-free guarantee. The agent stops a campaign only when a calibrated upper bound on its end-of-horizon ROI falls below target. Any unspent budget returns to the advertiser's other campaigns. The guarantee is that the agent rarely kills a campaign that would in fact have met its ROI target.
Core Claim
The obvious version of this idea, "add early stopping to autobidding," is not interesting by itself, and we want to say why up front. If leftover budget has no other use, then bidding zero for the rest of the horizon is the same as stopping. A pacing multiplier can already drive bids toward zero. The exit action earns its place only when stopping produces a terminal value that continued participation does not. This is the structure of action-based termination in indefinite-horizon partially observable decision problems, where ending the episode is a deliberate action that pays a reward based on the agent's belief (Hansen). In advertising, the terminal value is concrete. Released budget can be redeployed to sibling campaigns at their marginal return, which is the cross-campaign allocation view of Zhang et al.. Stopping also freezes the ROI already realized, so the agent pays no further for tail impressions that dilute it.
Our claim has two parts. First, in portfolios where released budget has positive marginal value, a stop rule added to a standard pacer captures more portfolio value at equal or lower ROI violation than the pacer alone. Second, the stop rule's premature-termination rate can be controlled at a user-chosen level $\delta$ without distributional assumptions. Learned value functions and heuristic cutoffs do not offer this control. The second part is what we think is new. It transfers the "stop only when the calibrated set has contracted" logic of conformal exploration (Explore until Confident) from embodied question answering to a constrained economic control problem.
The Stop Rule
We fix a base pacing policy and evaluate the campaign at $K$ checkpoints. The base policy is min-pacing, which bids $\min(\mu_t,\lambda_t)\,v_t$ using separate budget and ROI multipliers (A Field Guide for Pacing Budget and ROS Constraints). At checkpoint $k$, a learned predictor outputs $\hat R_k$, an estimate of the ROI the campaign would reach at the horizon if it continued. Its inputs are spend, value, and win rate so far, the multipliers, time of day, and remaining budget.
On held-out calibration campaigns run to completion, we record each trajectory's worst over-pessimism, $S=\max_k (R_T-\hat R_k)$, where $R_T$ is the realized final ROI. Let $q$ be the conformal $(1-\delta)$ quantile of these scores. The agent exits at the first checkpoint where
$$\hat R_k + q < \rho,$$
with $\rho$ the ROI target.
If the agent stops at $k$ while the campaign would have finished with $R_T\ge\rho$, then $R_T-\hat R_k>q$, so $S>q$. Under exchangeability of campaigns, this happens with probability at most $\delta$. We call the guarantee simultaneous because calibrating on the trajectory-level maximum covers all $K$ checkpoints at once, with no Bonferroni correction.
The rule slots into min-pacing as a third multiplier that is either 1 or 0. This keeps the zero-communication property that makes min-pacing attractive. The threshold also tends to tighten late in the day as the predictor's error shrinks. This echoes the collapsing decision boundaries that Rao derives from the cost of gathering more evidence, although we do not assume known transition models as that work does.
Research Program
We will build the stop module, its predictor, and a portfolio evaluation harness on top of two public simulators. The harness has to supply two things existing benchmarks lack. The first is a terminal value for released budget, obtained by grouping campaigns into portfolios where unspent budget is reallocated to the remaining members, with a dial for how much a released dollar is worth. The second is counterfactual continuation. Because the environments are simulators, every stopped campaign can be replayed to its horizon. That lets us measure exactly how often a stop was premature, which is the bidding analogue of the oracle-success gap in navigation. There, an external oracle stop signal raises completion by over 200% (Xiang et al.), which shows how much termination quality alone can matter.
The analysis has three questions. The first is when the exit option has value at all; we expect value to grow with the terminal-value dial and with market adversity. The second is whether the conformal guarantee survives the dependence that real markets create, since campaigns on the same day share competitors, which strains exchangeability. We will compare calibration grouped by day against pooled calibration. The third is whether stops cluster at the transition into the ROI-binding regime. In that regime, the work on pricing against a budget and ROI constrained buyer shows that purchase volume collapses.
Baselines
The naive reference is min-pacing with no exit, run on the same portfolios with released budget fixed at zero by construction. This is the strongest simple pacer with guarantees. It reaches $O(\sqrt T)$ regret and ROI violation, and on its own 100,000-campaign semi-synthetic data it captured 86% of benchmark optimal value with 80% of campaigns finishing at or below 20% relative ROI error. Dual-optimal pacing captured 81% at a 15% threshold (A Field Guide for Pacing Budget and ROS Constraints). That dataset is not in our benchmarks, so we reimplement min-pacing and tune its step sizes with the same budget we give our method. We report its numbers on our data rather than borrowing the published ones.
The strongest learned bidder is GAVE, a Decision Transformer bidder with constraint-penalizing return targets and an expectile value function (Generative Auto-Bidding with Value-Guided Explorations). It reports gains of 1.3% to 6.75% over the next-best baseline on AuctionNet and AuctionNet-Sparse. On AuctionNet itself, the benchmark authors found Online LP the strongest classical baseline, though no number appears in the file for it (AuctionNet). Online LP, GAVE, and min-pacing will each be run with and without our stop module. This tests whether the module adds value on top of any base policy, not only a weak one.
Three stopping competitors isolate the key ingredient. The first is a hard cutoff that halts when cumulative ROI drops below $\rho$. The second is a concentration-bound stop that halts when an upper confidence bound on ROI falls below $\rho$, in the style of the optimistic estimates in UCB-RoS (Online Bidding under RoS Constraints without Knowing the Value). The third is an uncalibrated learned-value stop that exits when the predictor's point estimate, or GAVE's expectile value, falls below target. The key ablation keeps everything about our method except the conformal quantile $q$, which is the uncalibrated learned-value baseline. All stop rules share the same predictor features, training split, and calibration split.
Beating the baselines means two things at matched or lower ROI violation. Portfolio value must be higher than no-exit min-pacing whenever terminal value is positive. The empirical premature-stop rate must be at or below $\delta$ while the uncalibrated and hard-cutoff rules exceed it.
Why not just…?
Why not just let min-pacing drive the multiplier to zero? When released budget is worthless, this is equivalent to stopping, and we expect no gain. We will run that case explicitly as a sanity check, and a gain there would signal a bug. The difference appears only when budget can be redeployed. Even then, a near-zero multiplier still wins cheap tail impressions that dilute ROI. Only exit frees the remaining budget. The terminal-value sweep settles where the break-even point lies.
Why not just tighten the ROI target inside min-pacing, pacing to $\rho(1+m)$ for some margin $m$? This is a real threat to the violation-reduction part of our claim. A margin cuts violations across all campaigns but costs value on healthy ones, whereas exit acts only on campaigns predicted to fail. We will tune $m$ on the same calibration data and compare full value-versus-violation curves. If the margin curve dominates ours, the violation story is dead and only budget redeployment remains.
Why not just stop when cumulative ROI dips below target? Costs arrive before value, and conversions are sparse. Early cumulative ROI is therefore biased downward, especially on AuctionNet-Sparse, so this rule should commit exactly the premature-termination error that plagues GUI agents with optimistic self-checks (Knowing When to STOP, RECOVER, and SEARCH), only in the pessimistic direction. Counterfactual replay measures its false-stop rate directly.
Why not just use a confidence bound like UCB-RoS? This is the most serious alternative. Sub-Gaussian bounds may be valid but loose under heavy-tailed costs, which would delay stops and lose value. If they turn out to be about as tight as conformal bounds on these benchmarks, our contribution narrows to the simultaneous-checkpoint guarantee. We will report value at matched false-stop rates for the two rules.
Proposed Experiments
We use AuctionNet and AuctionNet-Sparse, a multi-slot second-price simulator with 48 competitor agents (AuctionNet), and BAT, with first-price and VCG auctions, about 9,000 campaigns, and traffic that swings 30-fold over a day (BAT). The file reports no numerical results for BAT's pacers (Mystique, TA-PID, M-PID, BROI), so we will rerun them as base policies.
Metrics are portfolio value relative to the offline optimum, the distribution of relative ROI error, the premature-stop rate from counterfactual replay, and the late-stop waste. We define late-stop waste as spend after the first checkpoint at which the campaign was already infeasible.
Four checks decide the proposal. The first is a coverage plot of premature-stop rate against $\delta$, for calibration and test from the same distribution and for calibration on AuctionNet with testing on AuctionNet-Sparse. Under the shift, the guarantee may break, and we will report by how much. The second is the terminal-value sweep, which should show zero gain at zero value and growing gain after that. The third is the head-to-head against the tuned-margin and UCB stops at matched violation. The fourth is a BAT test of whether stops concentrate in off-peak troughs, where reactive pacers are known to overspend.
If calibrated exit gives no value gain over a tuned margin when budget is redeployable, or if coverage collapses under day-level dependence, we will report that this direction does not pay off.
References
- Indefinite-Horizon POMDPs with Action-Based Termination
- Joint optimization of bid and budget allocation in sponsored search
- Explore until Confident: Efficient Exploration for Embodied Question Answering
- A Field Guide for Pacing Budget and ROS Constraints
- Decision Making Under Uncertainty: A Neural Model Based on Partially Observable Markov Decision Processes
- Learning to Stop: A Simple yet Effective Approach to Urban Vision-Language Navigation
- Pricing against a Budget and ROI Constrained Buyer
- Generative Auto-Bidding with Value-Guided Explorations
- AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games
- Online Bidding under RoS Constraints without Knowing the Value
- Knowing When to \texttt{STOP}, \texttt{RECOVER}, and \texttt{SEARCH} \\ A Modular Framework for GUI Automation
- BAT: Benchmark for Auto-bidding Task