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

Overview§

AV-AIVAT addresses a fundamental problem in agent evaluation: deciding when enough games have been played to distinguish two agents under uncertainty. Fixed-budget evaluations either overspend or stop too early without statistical guarantees. The paper pairs the variance-reduction technique AIVAT (Action-Informed Value Assessment Tool) with anytime-valid Confidence Sequences (CSs) to create an evaluation protocol that can stop as soon as evidence suffices, while preserving a strict type-I error bound at all stopping times.

Methodology§

AIVAT Correction§

In imperfect-information games like poker, the raw outcome $X_i$ of hand $i$ has high variance. AIVAT reduces this by subtracting conditionally mean-zero corrections. For each decision point in a hand, a value model $v(h, a)$ estimates the value of taking action $a$ at history $h$. The correction replaces the realized action's value with the expected value under the agent's policy $\pi$:

$$Y_i = X_i - \sum_{h} \left( v(h, a_{\text{real}}) - \mathbb{E}_{a \sim \pi(h)}[v(h,a)] \right).$$

Because the correction is mean-zero conditional on the history, $\mathbb{E}[Y_i] = \mathbb{E}[X_i]$, but $\text{Var}(Y_i) \ll \text{Var}(X_i)$. Crucially, AV-AIVAT requires that the value model is updated only on past hands, never on the current hand, so the conditional mean-zero property holds online.

Anytime-Valid Confidence Sequences§

A confidence sequence is an anytime-valid interval $(L_t, U_t)$ such that $\Pr(\theta \in (L_t, U_t) \enspace \forall t) \ge 1 - \alpha$. Unlike fixed-sample confidence intervals, a CS can be monitored continuously and stopped at any time without inflating the false-positive rate. AV-AIVAT uses two types:

• AsympCS: asymptotic normal approximation for screening.
• EB-CS: empirical-Bernstein bound for finite-sample exactness, requiring a known upper bound on $|Y_i|$.

The EB-CS interval for the mean $\mu$ at time $n$ takes the form:

$$\hat{\mu}_n \pm \sqrt{\frac{2 \hat{\sigma}_n^2 \ln(1/\alpha)}{n}} + \frac{3 b \ln(1/\alpha)}{n},$$

where $\hat{\sigma}_n^2$ is the sample variance and $b$ is an upper bound on the absolute payoff. The width floor is caused by the $\mathcal{O}(\log n / n)$ term, which limits how much variance reduction can translate into earlier stopping.

Implementation Details§

For Leduc hold'em, the authors derive a structural bound on corrected payoffs, enabling exact EB-CS certification. For HUNL, they rely on descriptive AsympCS runs over 71,439 hands across 15 LLM agent configurations. At the nominal 95% level and target precision $\pm 1$ big blind, AIVAT-corrected outcomes required a median $74\times$ fewer hands than raw outcomes under AsympCS. The EB-CS runs showed a median $1.37\times$ stopping-time ratio, illustrating the width floor.

A minimal Python illustration of the core loop:

import numpy as np
from scipy.stats import norm

class AV_AIVAT:
    def __init__(self, alpha=0.05, target_width=2.0, bound=None):
        self.alpha = alpha
        self.target_width = target_width
        self.bound = bound  # known upper bound on |Y|
        self.model = ValueModel()  # e.g., a neural network trained online
        self.corrected = []
        self.stopped = False

    def evaluate_hand(self, hand, outcome):
        correction = 0.0
        for h, action in hand.decisions:
            v_real = self.model.predict(h, action)
            v_exp = sum(
                self.model.predict(h, a) * hand.policy_prob(h, a)
                for a in hand.legal_actions(h))
            correction += v_real - v_exp
        y = outcome - correction
        self.corrected.append(y)

        # Update model strictly with past hands (exclude current)
        self.model.update(hand, outcome)

        n = len(self.corrected)
        mu = np.mean(self.corrected)
        var = np.var(self.corrected, ddof=1)

        # AsympCS bound
        z = norm.ppf(1 - self.alpha / 2)
        width = z * np.sqrt(var / n)
        lower, upper = mu - width, mu + width

        # Optional EB-CS exact bound (requires self.bound)
        if self.bound is not None:
            extra = 3 * self.bound * np.log(1 / self.alpha) / n
            width = np.sqrt(2 * var * np.log(1 / self.alpha) / n) + extra
            lower, upper = mu - width, mu + width

        if upper - lower <= self.target_width:
            self.stopped = True
        return y

Conclusion§

The key contribution is the principled fusion of variance reduction and anytime-valid inference. AV-AIVAT turns variance reduction directly into earlier, certified stopping, while separating asymptotic screening (AsympCS) from exact finite-sample certification (EB-CS). This makes agent evaluations cheaper, faster, and auditable at the exact stopping time.