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

arXiv: https://arxiv.org/abs/2608.06362 · HTML: https://mlsanity.com/paper/2608.06362/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 6 Aug 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 26 of 26)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Game-theoretic statistics and safe anytime-valid inference](https://mlsanity.com/paper/2210.01948/) (2022)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning](https://mlsanity.com/paper/2106.06135/) (2021)
- [Safe and Nested Subgame Solving for Imperfect-Information Games](https://mlsanity.com/paper/1705.02955/) (2017)
- [Time-uniform central limit theory and asymptotic confidence sequences](https://mlsanity.com/paper/2103.06476/) (2021)
- [Depth-Limited Solving for Imperfect-Information Games](https://mlsanity.com/paper/1805.08195/) (2018)
- [Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselines](https://mlsanity.com/paper/1809.03057/) (2018)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [PokerBench: Training Large Language Models to become Professional Poker Players](https://mlsanity.com/paper/2501.08328/) (2025)
- [Measuring the Size of Large No-Limit Poker Games](https://mlsanity.com/paper/1302.7008/) (2013)
- [RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learning](https://mlsanity.com/paper/2403.04344/) (2024)
- [Low-Variance and Zero-Variance Baselines for Extensive-Form Games](https://mlsanity.com/paper/1907.09633/) (2019)
- [AIVAT: A New Variance Reduction Technique for Agent Evaluation in Imperfect Information Games](https://mlsanity.com/paper/1612.06915/) (2016)
- [Effective, Efficient, and General Information Abstraction for Imperfect-Information Extensive-Form Games](https://mlsanity.com/paper/2605.10900/) (2026)
- [Real-Time Parallel Counterfactual Regret Minimization](https://mlsanity.com/paper/2605.19928/) (2026)
- [Correlated Chance Sampling for Monte Carlo Counterfactual Regret Minimization](https://mlsanity.com/paper/2607.27035/) (2026)
- [PokerSkill: LLMs Can Play Expert-Level Poker without Training or Solvers](https://mlsanity.com/paper/2605.30094/) (2026)
- [Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation](https://mlsanity.com/paper/2607.28520/) (2026)
- [GTO Wizard Benchmark](https://mlsanity.com/paper/2603.23660/) (2026)
- [Heuristic Pathologies and Further Variance Reduction via Uncertainty Propagation in the AIVAT Family of Techniques](https://mlsanity.com/paper/2605.14261/) (2026)

## Built on by (most cited first, 1 of 1)

- [ICM Out! Better Tournament Strategy from Computed Continuations, vs. Solvers and LLMs](https://mlsanity.com/paper/2608.09586/) (2026)

## Abstract (arXiv)

Deciding which of two agents is stronger means playing games until skill outweighs luck, and every game costs money, model inference, or expert time. Since the number of games needed is unknown, fixed-budget evaluations either keep paying after the result is settled or stop before the agents can be told apart, while naive optional stopping with an ordinary confidence interval invalidates the stated level. We make such an evaluation stop as soon as its evidence suffices, with the guarantee intact. The Action-Informed Value Assessment Tool (AIVAT) reduces variance in imperfect-information games through conditional mean-zero corrections, by a median 54× across 15 LLM agent configurations spanning 71,439 paired Heads-Up No-Limit Hold'em (HUNL) hands, but does not say when to stop. We combine AIVAT with continuously monitored Confidence Sequences (CSs) into anytime-valid AIVAT (AV-AIVAT), whose online value model learns only from past games so that no game scores its own correction. At the nominal 95% level and a target precision of ±1 Big Blind, raw outcomes need a median 74× as many hands as AIVAT-corrected outcomes to stop under the Asymptotic CS (AsympCS). Exact finite-sample certification uses the Empirical-Bernstein CS (EB-CS), which needs an independently justified bound on corrected payoffs. We establish such a bound structurally for Leduc hold'em and characterize a width floor set by the CS's bet cap and that bound, which governs how much of a variance gain becomes earlier stopping; the descriptive HUNL EB-CS runs show a median 1.37× stopping-time ratio. AV-AIVAT turns variance reduction into efficient, auditable early stopping while separating asymptotic screening from exact certification, so an evaluation can stop the moment its evidence suffices and hand a third party everything needed to recheck the verdict at that very stopping time.