AIVAT corrections plus time-uniform confidence sequences let evaluators stop agent-vs-agent poker comparisons far earlier without losing statistical validity; on 71k HUNL hands the method compresses variance by a median 54× and — under the asymptotic interval — cuts required hands by a median 74×, with an exact bounded-sample certificate available when a corrected-payoff bound is supplied.

Main Finding

AV-AIVAT (Anytime-Valid AIVAT) combines AIVAT variance reduction with time-uniform confidence sequences to let an evaluator stop an imperfect-information game (IIG) experiment the moment the evidence suffices while preserving a stated statistical guarantee. On a large HUNL corpus, AIVAT reduces payoff variance dramatically (median 54×), and using the asymptotic CS this converts into major sample savings (median 74× fewer hands to reach ±1 BB at 95%); an exact finite-sample certificate (EB‑CS) can be produced when an independent almost-sure bound on corrected payoffs is available, though that bound implies a deterministic width floor that limits stopping gains (median EB‑CS stopping-time ratio 1.37× in the HUNL runs).

Key Points

• Problem addressed: costly, noisy pairwise agent evaluation in IIGs (e.g., poker/LLM agents) where stopping early invalidates ordinary fixed-sample inference.
• Core idea: make AIVAT corrections predictable (value models only use past data; action kernels and enablement decisions are fixed before seeing the action) so corrected payoffs remain conditionally mean-zero; feed the corrected stream to confidence sequences that are valid under continuous monitoring.
• Two CSs:
  • EB‑CS (predictable empirical-Bernstein): exact, finite-sample, time-uniform validity if the corrected payoffs are almost-surely bounded by a declared BY. Bets are capped (≤1/2); this cap plus BY induces a deterministic width floor ∝ B/t.
  • AsympCS: asymptotically valid, variance-adaptive, much more sample-efficient in practice when its limiting regularity conditions hold.
• Practical protocol (AV-AIVAT): at each hand t, fix vt using only Ft−1, record conditional kernels and enablement flags, play hand, compute corrected payoff Yt = Xt + Ct, update both CSs; stop when desired half-width reached; publish Y1:τ and stopping metadata so third parties can recheck the claim.
• Theoretical guarantees:
  • Predictable AIVAT interface preserves mean-zero correction; online refitting of vt is valid so long as vt is Ft−1-measurable (no use of current-hand data).
  • Under variance-adaptive width and sublinear variance-regret, an online value learner matches oracle asymptotic stopping delay (Theorem 2); in experiments it recovers ~77–79% of frozen→oracle variance gap.
  • EB‑CS gives exact finite-sample validity conditional on declared BY (Proposition 1); AsympCS gives asymptotic validity under Lindeberg-type conditions (Proposition 2).
• Empirical results (HUNL corpus: 71,439 paired hands, 15 PokerSkill/LLM agent configurations):
  • AIVAT median variance reduction = 54× (across configurations).
  • At 95% level, ±1 BB target: median raw-to-AIVAT stopping-time ratio = 74 using AsympCS (i.e., AIVAT-corrected stream needs 1/74 the hands).
  • EB‑CS descriptive runs show median stopping-time ratio = 1.37×; difference explained by EB‑CS width floor from declared bound.
• Reproducibility: releasing corrected prefix Y1:τ, stopping rule/index, kernel and enablement provenance, declared bound and CS settings (and optional paired raw stream) suffices for a third party to recompute the intervals at the reported stopping time and recheck the verdict.
• Continuous monitoring danger illustrated: naive stopping on ordinary fixed-sample intervals produced 61% false positives under the null in a rolling-leaderboard simulation; recomputing the CS at the stopping time corrects such claims.

Data & Methods

• Data:
  • Corpus: 71,439 paired Heads-Up No-Limit Hold’em (HUNL) hands from 15 PokerSkill/LLM agent configurations in fixed-opponent multi-hand runs.
  • For each hand the evaluation platform supplied both raw payoff Xt and AIVAT-corrected payoff Yt (using frozen v in those runs).
• Variance reduction method:
  • AIVAT corrections: at a set Hc of eligible chance/evaluated-agent nodes, replace realized continuation value by its conditional average over known action kernels pt,h; an enablement indicator St,h must be chosen before the action and be G−t,h-measurable. Correction Ct = sum_h St,h It,h [Σ_a pt,h(a) v(h·a) − v(h·At,h)].
  • Predictable interface: vt may be refit online but only on Ft−1; action kernels and enablements must be recorded prior to the action so Ct has conditional mean zero.
• Confidence sequences:
  • EB‑CS: predictable plug-in empirical-Bernstein CS on bounded (declared) stream BY. Uses regularized plug-in mean emt−1 and predictable bets λt ∈ [0,1/2]; exact time-uniform coverage when BY holds.
  • AsympCS: time-uniform CLT-based asymptotic CS centered at running mean with sample variance input; tuning parameter ρ; asymptotic coverage under martingale-difference/Lindeberg conditions.
• Theory highlights:
  • Lemma: EB‑CS bet cap and declared BY create a deterministic half-width floor (~4B log(2/α)/t), producing a three-regime behavior for stopping-time gains.
  • Theorem: online value learners incur only variance-regret-dependent efficiency loss vs. oracle; empirical recovery ≈77–79% of possible improvement in experiments.
  • Propositions: formal validity of EB‑CS (finite-sample) and AsympCS (asymptotic).
• Experiments/benchmarks:
  • Paired replay and stopping-time comparisons using both CSs.
  • Leduc hold’em: exhaustive derivation and checking of an almost-sure bound BY so EB‑CS exact certificate can be used.
  • Rolling-leaderboard simulations illustrate false-positive risk with naive optional stopping vs. CS recomputation.

Implications for AI Economics

• Direct cost savings for expensive interactive evaluations:
  • For settings like LLM-based poker agents (inference cost ~$0.07–$0.30 per hand), median 74× reduction in required hands (AsympCS) implies dramatic reductions in inference/compute and human participation costs for pairwise comparisons and tournaments.
  • Even when exact finite-sample certification is required (EB‑CS), variance reduction still helps, but the declared-bound-induced width floor can sharply limit sample savings; practitioners must weigh tighter declared bounds (hard to justify) vs. stopping efficiency.
• Rigorous anytime evaluation enables new economic practices:
  • Live leaderboards and rolling comparisons can safely stop and promote agents when a CS reports sufficient precision, without inflating false-positive rates—this reduces wasted evaluation cost and speeds iteration cycles for model developers.
  • The release protocol supports auditable claims: vendors can stop early and publish minimal, provable evidence that others can recompute, improving market transparency and trust in competitive claims.
• Design and incentive considerations:
  • To realize large savings, evaluators must: (a) provide valid action-kernel provenance and ensure enablements are fixed pre-action; (b) justify any declared BY if finite-sample certificates are desired; (c) commit CS tuning (replication split) ahead of time to avoid post hoc tuning.
  • AsympCS is more sample-efficient in practice but relies on asymptotic regularity; EB‑CS gives exact guarantees but may require conservative BY declarations that limit gains—this trade-off affects contract design (e.g., benchmarking rules, prize conditions).
• Limitations and practical caveats:
  • EB‑CS’s width floor can mean variance reduction does not translate to earlier stopping unless the declared bound is tight relative to variance/target precision.
  • The exact finite-sample certificate requires an independently justified BY (provided in Leduc; harder in large real-world games like HUNL).
  • The asymptotic guarantee can fail in small samples or if conditional-Lindeberg-type conditions do not hold; practitioners should validate via replication splits and report both CSs when possible.
• Broader impact:
  • AV-AIVAT is applicable beyond poker to other costly IIG evaluations (card games, interactive human–AI comparisons, or online strategic testing), enabling more economical, robust, and auditable model comparisons—accelerating research and reducing the monetary and time costs of high-fidelity agent evaluation.