Stop When You Know: AV-AIVAT and the Real Price of Certified Early Stopping

Paper: 2608.06362 Authors: Boning Li, Yu Chen, Longbo Huang Categories: cs.GT, cs.AI, cs.CL, cs.LG, cs.MA

The Gap

Two threads of prior work each solve half of this problem, and nobody had spliced them.

Thread one: variance reduction in imperfect-information games. Poker payoffs are brutally noisy — one cooler hand can swing a hundred hands’ worth of edge. AIVAT (Burch et al., 2018) attacks this by subtracting a conditionally mean-zero correction built from a value function plus “imaginary observations” over the actions and cards that *could have happened. It keeps the estimator unbiased and, in this paper’s runs, cuts variance by a median 54x across 15 LLM agent configurations on 71,439 paired Heads-Up No-Limit Hold’em hands. What AIVAT does not do is tell you when you have seen enough. It hands you a tighter estimate at whatever sample size you happened to choose.

Thread two: anytime-valid inference. Confidence sequences (Howard et al.; Waudby-Smith & Ramdas) give you an interval you may look at after every single observation, with one global coverage promise. They solve the stopping problem but do nothing about the noise itself.

So today’s practitioner is stuck choosing between two bad options. Fix a budget of N hands up front: either the verdict was settled at hand 3,000 and you burned inference credits through hand 100,000, or N was too small and the intervals still overlap. Or peek at an ordinary 95% confidence interval and stop when it looks good — which quietly destroys the 95%, because you cherry-picked the moment.

The subtle obstacle to just gluing the two together: a confidence sequence needs the summands to behave like martingale increments. If your value model is fit on all the data, hand t helps build its own correction, the mean-zero property breaks conditionally, and the anytime-valid guarantee evaporates. That measurability discipline is the paper’s real hinge.

[Problem] two agents, noisy payoffs, unknown number of games needed
    |
    +--> fixed budget N: overpay past the verdict .. or .. stop too early
    +--> peek at an ordinary 95% CI: the stated level is a lie
    |
    v
[Prior art] AIVAT: conditionally mean-zero corrections -> variance / 54
            ...but silent on WHEN to stop
    |
    v
[Assumption] build corrections ONLY from past games
             => corrected payoff x_t is a martingale increment
    |
    v
[Method] AV-AIVAT = AIVAT (variance) + Confidence Sequence (anytime-valid)
    |                                          |
    v                                          v
 AsympCS: asymptotic screening          EB-CS: exact, needs |x_t| <= B
    |                                          |
    v                                          v
[Evidence] median 74x fewer hands       Leduc: B proved structurally
 71,439 HUNL hands / 15 configs         HUNL: only 1.37x (width floor)
    |                                          |
    +---------------------+--------------------+
                          v
[Conclusion] stop the moment evidence suffices; the exact-certification
 lane pays a standing price for needing a boundedness constant

The Increment

One sentence: Before, you picked a hand count and hoped; after, the evaluation itself decides when to halt, with a guarantee that survives continuous peeking — and with an honest accounting of how much of a 54x variance win actually converts into earlier stopping (a lot under asymptotic screening, very little under exact certification).

Core Mechanism

The pipeline is a three-stage conveyor. Stage one plays hand t and records the raw payoff in big blinds. Stage two computes the AIVAT correction using a value model whose parameters were frozen before hand t began — trained online, but strictly on hands 1 through t−1. Subtracting that correction gives a corrected payoff with the same mean as the raw one and roughly 1/54 the variance. Stage three feeds the corrected sequence into a confidence sequence and checks a single stopping rule: is the interval now narrower than ±1 big blind? If yes, stop and report; if no, play another hand.

The “no game scores its own correction” constraint is what makes stage three legal rather than decorative. Because the correction at time t is measurable with respect to the past, its conditional expectation is exactly zero given everything seen so far, so the corrected payoffs form a martingale-increment sequence around the true skill difference. Confidence sequences are built on exactly that structure, which is why optional stopping doesn’t cost you anything here.

Then the paper splits the road, and this is the part worth reading carefully. The Asymptotic CS needs no bound on the data and delivers the headline: raw outcomes need a median 74x as many hands to reach ±1 BB as corrected outcomes. But it is asymptotic — good for screening, not for certifying. The Empirical-Bernstein CS gives exact finite-sample coverage, but its width carries a term proportional to a bound *B on the corrected payoffs, divided by the CS’s betting cap. That term shrinks with t but not with variance. So there is a width floor: once the variance term drops below the range term, further variance reduction buys you almost nothing. The authors prove such a *B structurally for Leduc hold’em; for HUNL no independently justified bound exists, so those EB-CS runs are labeled descriptive, and the stopping-time ratio there is a median 1.37x. The gap between 74x and 1.37x is the paper’s most informative number.

hand t:  hole cards, betting actions, showdown
   |
   v
+-------------------------------+
|  raw payoff  u_t  (big blinds)|   variance: enormous
+-------------------------------+
   |
   |     value model V_(t-1)  . fit ONLY on hands 1..t-1
   |             |
   v             v
+-------------------------------+
| AIVAT correction c_t          |   E[ c_t | past ] = 0  exactly
|  = value baseline             |   (this is why peeking stays legal)
|  + imaginary observations      |
+-------------------------------+
   |
   v
 x_t = u_t - c_t        same mean, ~ variance / 54
   |
   v
+---------------------------------------------+
| Confidence Sequence on x_1 .. x_t           |
|   L_t <= mu <= U_t   for ALL t simultaneously|
|                                             |
|   AsympCS : no bound needed, asymptotic     |
|   EB-CS   : exact, needs |x_t| <= B         |
|             width >= floor( B / bet cap )   |
+---------------------------------------------+
   |
   v
 (U_t - L_t) <= 2 BB ?  --- no ---> play hand t+1
   |
  yes
   v
 STOP . publish (t, x_1..x_t, model checkpoints) for third-party recheck

The metaphor: weighing two suitcases on a certified scale, aboard a rocking boat.

The suitcases are the two agents; the weight difference is the true skill gap. The bathroom scale is your payoff measurement, and the boat’s rocking is variance — one big wave and the display says either agent is 40 pounds heavier.

AIVAT is an accelerometer bolted to the deck: it measures the wave motion and subtracts it from the reading. Crucially, the accelerometer is calibrated only on waves that already passed — if you let it calibrate on this instant, it would happily “explain away” the actual weight difference as wave motion, and your reading would be biased. That is the past-only value model.

The confidence sequence is a different kind of display. A normal scale certifies its reading only if you take exactly one reading after settling for a fixed time; if you stare at the flickering number and grab the moment it looks tightest, the certification is void. The CS display instead carries a single guarantee that holds at every instant, so you may watch it and stop the second the error bar fits inside ±1 BB.

And the two CS flavors are two classes of scale. AsympCS is the kitchen scale: quick, unbounded, good enough to tell which suitcase is heavier. EB-CS is the legally sealed trade scale used in commerce — but a sealed scale requires a declared maximum load stamped on it, and its smallest readable division is tied to that declared maximum. That division is the width floor. On a glassy calm sea the kitchen scale keeps getting more precise; the sealed scale hits its tick marks and stops improving. Which is exactly why 54x variance reduction becomes 74x on one and 1.37x on the other. The paper’s Leduc proof is the act of legitimately stamping a maximum load on the scale; for HUNL, nobody has stamped it yet.

Key Concepts

• Why peeking breaks a confidence interval (and what fixes it): An ordinary 95% CI is a promise about *one pre-declared moment: “if you compute me at hand 10,000, I cover the truth 95% of the time.” It says nothing about a person who computes it at hands 100, 200, 300, … and stops at the first one that looks decisive. That person is cherry-picking from a hundred flickering intervals, and their real error rate can be several times the nominal. A confidence sequence changes the quantifier: it is an infinite family of intervals with one joint promise — with probability 95%, no interval in the whole sequence ever misses the truth. Once that holds, stopping whenever you like is free, because your stopping rule can only pick a time from a family that is already all-correct. Concretely: instead of “playing until 10,000 hands then testing,” you get a live-updating bracket you may cash out at hand 2,317 with the same 95% behind it.

• Conditionally mean-zero corrections (control variates, done carefully): Suppose you want to know if a new coffee blend raised daily sales. Sales swing wildly with weather. If you have a weather-based sales predictor, subtract its prediction from each day’s sales: the average is unchanged as long as the prediction errors average to zero, but the day-to-day swing collapses. AIVAT is this idea specialized to poker — its “weather” is the cards dealt and the actions taken, and it also averages over the hands and actions that *could have occurred (the imaginary observations), which is why it can strip out so much luck. The catch that most people get wrong: the predictor must not have seen today’s sales. Otherwise it absorbs the very signal you are measuring.

• The width floor: The empirical-Bernstein interval width is roughly (variance term) + (range term), where the range term depends on your assumed bound *B on the data and on how aggressively the underlying betting scheme is allowed to wager. Variance reduction only shrinks the first term. So there is a point past which making your estimator quieter does not make your certificate tighter — you are floor-limited by the boundedness assumption you needed in order to be exact at all. This is a genuinely useful piece of engineering intuition: an exact finite-sample guarantee is not free, and it is priced in units of B.

Framework Shift

Before (mainstream approach):            After (this paper):

  choose N = 100,000 up front              play hand t
        |                                      |
        v                                      v
  play all N hands  ($$$$$)             AIVAT-correct with a PAST-only model
        |                                      |
        v                                      v
  compute ONE CI at the end             read CS interval [L_t, U_t]
        |                                      |
        +--> too wide: wasted run             width <= 2 BB ?
        +--> settled at hand 3k:               |         |
             90% of spend was noise           no        yes
                                               |         |
   ( peeking early == level is void )      loop back    STOP + audit bundle

  guarantee: at time N only              guarantee: at ALL times at once
  cost: fixed, chosen by guesswork       cost: adaptive, set by the evidence

                                         two lanes, kept honest:
                                          AsympCS  -> screening (74x)
                                          EB-CS    -> certification (1.37x,
                                                      floor-limited by B)

From a pre-declared sample size to an evidence-triggered halt, the core shift is that the guarantee moves from a single moment to every moment, which turns variance reduction into a direct saving in games played — up to a floor that exact certification imposes.

Expert Assessment

Problem choice: Real gap, well chosen, and timely. Evaluating LLM agents by self-play is now a line item with actual dollars attached, and imperfect-information games are the worst case for signal-to-noise. Anytime-valid inference has been rediscovered by the ML community over the last five years but has barely touched game-playing agent evaluation, where the payoff variance is precisely the thing that makes fixed budgets wasteful. Sitting AIVAT — a 2018 poker-community tool — next to confidence sequences is an obvious-in-hindsight pairing that nobody had done properly. The honest framing is that this is a well-executed bridge, not a new continent.

Method maturity: Clever in one specific place and standard everywhere else. The one real technical insight is enforcing that the value model is fit only on the past, so the corrected payoffs stay martingale increments and optional stopping remains legal. That trick is well known in adjacent literatures (sequential sample splitting in doubly-robust off-policy evaluation, prediction-powered inference), so the contribution is recognizing that AIVAT’s guarantee is fragile in exactly this way and repairing it, rather than inventing new machinery. The width-floor characterization is the part I’d keep: it converts a vague worry into a quantitative statement about when variance reduction stops paying.

What I think is underexplored: EB-CS may simply be the wrong exact tool here. Betting-based confidence sequences with variance-adaptive wagering, or sub-exponential/sub-gamma mixture boundaries that need tail control rather than a hard bound, could plausibly recover much more than 1.37x without needing a structural B at all. Truncating or Winsorizing corrected payoffs at a data-driven level is another cheap route to a defensible bound. The paper’s own framing — “exact certification is floor-limited” — is really a statement about EB-CS specifically, and I’d want it tested against those alternatives before accepting it as a general law.

Experimental integrity: Better than average, mainly because the authors did not hide the deflating number. Reporting 74x under AsympCS and 1.37x under EB-CS in the same abstract, and explicitly labeling the HUNL EB-CS runs “descriptive” because the bound is not independently justified, is the behavior of people trying to be right rather than impressive. Paired hands and 15 configurations over 71,439 hands is a respectable scale for this kind of study, and medians rather than means is the correct summary for stopping times.

Two things to keep an eye on. First, the title. “74x cheaper” plus “certified anytime-valid stopping” in one line invites the reading that you get 74x and certification; you do not — the 74x comes from the asymptotic procedure, the certified procedure gives 1.37x. That is disclosed in the abstract, so it is spin rather than misrepresentation, but it is spin. Second, 54x variance reduction yielding a 74x stopping-time ratio is roughly what the arithmetic predicts once you account for the running variance estimate and log factors, so the 74x is not an extra win on top of AIVAT — it is AIVAT’s variance win, expressed in the currency of hands. And note that all of this inherits AIVAT’s dependence on value-model quality; a weak online model on unfamiliar agents will not deliver 54x, and I would want the spread across those 15 configurations, not just the median, before budgeting on it.

Writing quality: The abstract is doing too much — it tries to carry the motivation, both CS variants, the Leduc theory, the width floor, and two headline numbers, and the result is dense enough that a casual reader will take away “74x” and nothing else. The section I would most want rewritten is the value-model specification: everything downstream depends on what the online model is, how fast it warms up, and what happens during the early hands when it is nearly uninformative, and that deserves a foregrounded treatment rather than a mention. Second priority: a short worked example turning the width-floor formula into a practitioner’s rule of thumb — “given range bound *B and target precision, here is the smallest sample size any exact certificate can achieve” — would be the single highest-value paragraph in the paper.

Verdict: weak accept — a correct, honestly reported, immediately usable splice of two mature tools, whose main claim to certification only partly delivers and whose exact-inference pessimism may be an artifact of one specific confidence sequence.

Takeaways

Things worth stealing regardless of whether you care about poker:

• The past-only fitting discipline is the transferable core. Any time you use a learned model to reduce variance in an estimate you intend to monitor continuously — off-policy evaluation, A/B tests with ML-based covariate adjustment, LLM-judge-assisted benchmarks — fit the helper model strictly on data preceding each point. It costs you a little statistical efficiency and buys you the right to peek whenever you want. This is the single most reusable idea here.

• Price your guarantee in the right currency. The paper’s real lesson is that a 54x variance reduction is worth 74x under an asymptotic bound and 1.37x under an exact one. Before celebrating a variance win, check which term in your interval width it actually attacks. If a range or boundedness term dominates, your noise reduction is invisible.

• Two lanes, declared explicitly. Running a cheap asymptotic procedure for screening and a strict finite-sample procedure for the final verdict — and saying which is which — is a template worth copying for any expensive evaluation pipeline. Most papers pick one and quietly let readers assume it does both jobs.

• Ship the audit bundle. Stopping at a data-dependent time is exactly where reviewers get suspicious, so emitting the stopping time, the corrected sequence, and the model checkpoints so a third party can recheck the verdict *at that stopping time is a cheap practice that makes adaptive experiments defensible.

• A caution to steal too: getting a defensible bound on your corrected values is the hard part, not the algorithm. They could prove it for Leduc, a toy game; they could not for HUNL. If your plan involves exact finite-sample certification of a learned-correction estimator, budget real effort for that bound, or choose an inference tool that does not need one.