AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Games

The paper addresses the problem of deciding which of two agents is stronger in imperfect-information games (IIGs), where every game costs money, model inference, or expert time. The authors note that PokerSkill, a framework for deploying LLM agents in complete poker games, spends 0.07– 0.30 of inference per hand, and human matches such as Libratus's 120,000-hand, 20-day, 200,000 prize pool match were expensive. Since the number of games needed is rarely known in advance, the usual response is a fixed budget, which either overruns the evidence or ends before a useful conclusion is possible. They also identify the statistical hazard that Watching an ordinary fixed-sample interval instead and stopping at the first favorable look invalidates nominal coverage and inflates false positives. The problem is to stop when the evidence is sufficient while preserving a stated statistical guarantee.

The paper combines two existing tools into a new protocol:

1. AIVAT (Action-Informed Value Assessment Tool): AIVAT reduces variance in imperfect-information games through conditional mean-zero corrections — the classical version freezes its value function.

2. Confidence Sequences (CSs): Confidence sequences (CSs) solve a complementary problem: they retain their stated guarantee under continuous monitoring and optional stopping.

The combination is AV-AIVAT (anytime-valid AIVAT), described as a general statistical interface for evaluating agents in IIGs. Two CS constructions run side by side: the predictable plug-in empirical-Bernstein CS (EB-CS), which is exact at every look and pays for that exactness through the range it declares, and the Asymptotic CS (AsympCS), which adapts to the realized variance and is valid asymptotically. AV-AIVAT reports both.

1. Predictable value functions suffice (Proposition 1). "The classical AIVAT analysis freezes its value function before the evaluation sample is observed. In a sequential analysis, the weaker condition needed for the correction argument is that the value function used on the current hand is fixed before that hand is observed. The proposition establishes that if each value function vt is Ft−1-measurable, the conditional action kernel is known, and enablement is decided before the action there is seen, then E[Ct Ft−1] = 0 and E[Yt Ft−1] = µ, with Yt ≤ BX + 2KV =: BY, so the value model may keep learning while an evaluation runs instead of being frozen before it starts. Proposition 2 gives asymptotic validity of the AsympCS under martingale-difference regularity" conditions.

2. Width floor for the EB-CS (Lemma 1 and Theorem 1). For every data realization and every predictable bet sequence λs ∈ [0, 1/2], the payoff-scale EB-CS on a stream declared in [−B, B] satisfies wtEB ≥ 4B log(2/α)/t. This is a deterministic, variance-independent floor for this capped-bet construction. Theorem 1 gives a three-regime characterization: The deterministic floor, oracle-bet high-probability upper bound, and common-support expected lower-bound family motivate the design proxy max BX, σX2/ε /max BY, σY2/ε, which reads off three regimes: range-limited, neutral, and variance-limited. The bet cap λt ≤ 1/2 is part of this construction, and Section 5.2 shows it is what turns the declared range into a width floor.

3. Variance-regret bound (Theorem 2). Under Assumption 1 (variance-adaptive width), if the value learner has sublinear variance regret ∑(σs2 − σ⋆2) ≤ Rt with Rt = o(t), then with probability tending to one, τ(ε) ≤ τ⋆(ε)(1 + 2R2τ⋆/(σ⋆2τ⋆) + o(1)). Corollary 1 shows polynomial value learning with ∥vt − v⋆∥∞ ≤ ct−beta gives Rt = o(t) and τ(ε) ≤ τ⋆(ε)(1 + o(1)), so a value learner whose variance regret is sublinear reaches a target precision at the oracle's own asymptotic horizon.

The corpus contains 71,439 paired hands from 15 PokerSkill/LLM-agent configurations in fixed-opponent multi-hand runs, with both per-hand raw and AIVAT-corrected payoffs supplied by the evaluation platform.

• Variance reduction: AIVAT reduces variance by a median 54.4× (range 24.2–86.0×).

• AsympCS stopping-time ratio: At a ±1 BB target, the median ratio of raw to AIVAT AsympCS stopping times is 74.17× (range 54.53–97.62×) — hence the title's 74× cheaper.

• EB-CS stopping-time ratio: the corresponding EB-CS ratio is 1.365× (range 1.235–1.556×) over 14 evaluable runs, explaining that the declared payoff bound imposes a deterministic width floor 4B log(2/α)/t (Lemma 1), so once that floor binds, precision is set by the bound rather than by observed variance.

• Tighter target: At the tighter ±0.5 BB target, all 15 raw AsympCS streams are censored at their available run horizons... The AIVAT AsympCS median stopping time... is 56.5 hands, with range 42.5–71.

• Bound provenance caveat: P0 declares B = 200 BB, which is structural rather than data-chosen for the raw stream (200 BB stacks, no rebuys), but The corrected stream has no matching analytic ceiling here, so the EB-CS stopping ratio pairs an exact raw boundary with a descriptive corrected one.

• False-positive summaries: The AsympCS false-positive summary reported by P0 is 7.1067%, the unweighted mean of 30 condition-level rates... The AIVAT-only mean is 12.43%. The corresponding EB-CS summary is 0.01%.

• Setup: The hero is CFR+ after 2,000 iterations and the opponent is CFR+ after 20 iterations. Exact evaluation gives µ = −0.0047697 chips per hand.

• Variance ratio 8.08× (std 3.96 raw vs 1.39 AIVAT).

• Median AsympCS stopping ratios are 5.29× at ±0.5 chips and 7.91× at ±0.2; at ±0.1, every raw stream is censored while AIVAT stops at median 1,789 hands.

• Exact structural bound: "Standard Leduc has X ≤ 13 and v ≤ 13; corrected deal, chance, and hero transitions telescope, leaving at most four opponent transitions, so Y ≤ 117. The complete legal tree verifies the transition counts and the telescoping identity." EB-CS excludes the exact mean in 2 raw and 0 AIVAT streams out of 400 replications.

• Price of exactness: The certificate runs within about 1% of the deterministic floor its declared range induces (empirical-to-floor ratios 1.0019 and 1.0074 at t = 1000 and 4000).

E2 compares raw, frozen, predictable, and oracle arms on the same 100 sets of 8,192 simulated hands. The predictable arm refits a Laplace-smoothed opponent action-frequency model at doubling epochs using past hands only. Results: In two opponent-model mismatch profiles, predictable learning recovers 78.6% and 77.1% of the frozen-to-oracle variance gap. At ±0.1 chips, predictable stops 25.9% earlier than frozen, while oracle remains faster.

• False positives under optional stopping: Stopping at the first favorable look claims a nonzero effect in 1,227 of 2,000 entries (61.35%), with median stopping time 59 hands among claims, even though the true effect is zero by construction. This demonstrates monitoring an ordinary fixed-sample interval and stopping at the first favorable look yields 61% false positives under the null.

• Recheck screens claims: Checking a time-uniform interval on that same selected prefix screens those claims out: EB-CS contains zero at all 1,227 selected stops, and AsympCS at 1,226 of them (99.9185%).

• Genuine effects recovered: when AsympCS continues as its own monitor, it detects the 0.1 effect in 81.2% of entries with median stopping time 960.5 and the 0.2 effect in 100% with median 173.

The paper proposes "a release protocol that makes an early-stopping claim directly reconstructible. Publishing the corrected prefix together with the stopping rule and index, first-look and censoring metadata, declared bound, and locked CS settings lets a third party recompute the reported intervals at the exact stopping time without requiring the raw payoff stream. The required elements are: the corrected outcome stream (with raw payoffs optional), correction provenance (including For online values, record update epochs and enough state to verify that vt was fixed before observing hand t), inference specification (including A bounded exact-coverage claim must include an independently justified almost-sure bound for the corrected payoff), stopping metadata, and experimental provenance. A Minimal recheck procedure is given: (i) verifies ordering and row selection; (ii) reconstructs the stated correction and predictability assumptions where artifacts permit; (iii) recomputes the declared interval at every eligible look and at t̂; and (iv) checks an independently justified corrected-payoff bound if exact EB validity is claimed."

The paper's stated contributions are:

1. AV-AIVAT protocol: "a predictable AIVAT interface that exposes the conditional action kernel and fixes correction enablement before the action is observed. Past-only value updates preserve the correction's conditional mean-zero property, while separate validity statements distinguish the exact bounded EB-CS certificate from the efficient asymptotic CS."

2. Stopping-time characterization: "A deterministic width floor induced by the declared payoff bound yields a three-regime, order-level design guide, while the variance-regret result shows when a past-only online value learner approaches the stopping efficiency of an oracle value function."

3. Release protocol: Publishing the corrected prefix together with the stopping rule and index... lets a third party recompute the reported intervals at the exact stopping time without requiring the raw payoff stream.

The paper closes: "Past-only value functions preserve the mean-zero correction law... so the value model may keep learning while an evaluation runs instead of being frozen before it starts. The AsympCS turns the resulting variance reduction into much earlier stopping, and the EB-CS certifies a stopping claim exactly once a corrected-payoff bound is established independently of the evaluation sample, as the game structure permits in Leduc. A bet-capped exact interval pays a width floor set by that declared bound, which is what decides how much of a variance gain becomes earlier stopping. It also identifies the sharpest open problem: An analytic corrected-payoff bound for HUNL, or a confidence sequence whose range dependence adapts to the realized payoff scale, would extend exact certification to the setting where evaluation is most expensive."

The paper is careful to distinguish exact from descriptive results. Several EB-CS executions use bounds derived from observed maxima, making them descriptive replay[s] of the boundary rather than exact certificates: Separating these two modes is what lets one paper report an exact certificate and a practical screen without conflating them. The Leduc structural rerun with analytic BY = 117 is the one execution that instantiates the exact-validity theorem directly. The paper also notes E1's deviation from its registered bound (E1's change from the registered raw-payoff bound B = 13 to the observed-joint-maximum-based B = 22) and flags that post hoc AIVAT value-function tuning can induce spurious significance [29] as a complementary estimator-audit concern distinct from stopping-claim reconstruction.

Based on the paper, here are concrete improvements you can make to AI evaluation and learning systems:

1. Add anytime-valid stopping to agent comparisons.

Replace fixed-budget evaluation intervals with confidence sequences that remain valid under continuous monitoring and optional stopping. The improved system can check a hypothesis after every game/hand, stop as soon as the evidence is sufficient, and still control false positives. It avoids both wasted compute and invalid “peek at the first favorable look” decisions.

2. Use predictable value functions that keep learning during evaluation.

Instead of freezing a value network before the eval starts, the system can update the value function on past hands only and still preserve the mean-zero correction property. The improved evaluator can adapt its own value model over time while maintaining statistically valid payoff estimates, so it no longer needs a fully pre-trained oracle value function.

3. Combine variance reduction with confidence sequences to make evaluation dramatically cheaper.

Use action-informed control variates (AIVAT-style corrections) inside an anytime-valid test. The improved system can reduce variance by 54× in HUNL-style settings and reach a ±1 BB decision in about 74× fewer hands than raw payoffs, substantially lowering inference cost for LLM-agent poker evaluations.

4. Report two complementary stopping certificates.

Run an exact empirical-Bernstein confidence sequence alongside an asymptotic variance-adaptive confidence sequence. The improved system can give an exact, auditable guarantee when a valid payoff bound exists, and an efficient, tighter practical screen otherwise. This lets users choose between exactness and speed depending on what the game structure supports.

5. Implement a reconstructible release protocol.

After stopping, the improved system can publish the corrected payoff prefix, stopping rule, stopping index, declared bound, locked confidence-sequence settings, and correction update metadata. A third party can recompute the claimed intervals at the exact stopping time without needing the raw payoff stream. This makes AI evaluation claims reproducible and auditable.

6. Screen out false positives caused by optional stopping.

The AI system can apply time-uniform intervals to already-selected “promising” prefixes. In the paper’s null simulation, an ordinary fixed-sample monitor claimed nonzero effects in 61.35% of runs under continuous sampling, while the EB confidence sequence excluded zero at all selected stops and the asymptotic CS at 99.9185% of them. The improved system can filter invalid significance claims after the fact.

7. Detect small effects that raw evaluation cannot reach.

With variance reduction plus confidence sequences, the improved system can reliably detect small true effects (e.g., 0.1 chip/hand in Leduc) where raw streams never converge within a feasible horizon. This enables evaluating fine-grained differences between models that were previously impractical.

8. Guide evaluation-budget design with the three-regime width characterization.

The system can use the design proxy max B X, σ X2/ε / max B Y, σ Y2/ε to decide whether it is range-limited, neutral, or variance-limited. Based on that, it can automatically choose whether to spend effort on variance reduction, tight payoff bounds, or more samples.

9. Use value learners with sublinear variance regret to approach oracle stopping horizons.

The improved system can deploy online value learners whose cumulative variance regret is sublinear, guaranteeing that its stopping time approaches the oracle’s asymptotic horizon even while the value function is still improving. This makes early stopping efficient during ongoing learning, not only after convergence.

10. Know the price of exactness and avoid overpaying for it.

Because a bet-capped empirical-Bernstein confidence sequence has a deterministic width floor 4B log(2/α)/t, the improved system can recognize when further variance reduction will no longer shorten stopping time because the declared payoff bound dominates. It can then avoid spending extra compute on variance reduction that cannot translate into earlier stopping.