PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiagent Evaluation under Incomplete Information

Mark Rowland, Shayegan Omidshafiei, Karl Tuyls, Julien Perolat, Michal Valko, Georgios Piliouras, Remi Munos

arXiv:1909.09849v4cs.MAcs.AIcs.LGstat.ML

TL;DR

Evaluating learned agents from noisy and incomplete game outcomes is difficult: Elo cannot handle intransitivity, and other ranking approaches have scope or tractability limits. This paper develops guarantees and adaptive sampling for α-Rank, plus a method to bound ranking uncertainty from payoff uncertainty. It concludes that these approaches support principled evaluation in incomplete-information settings, subject to the stated no-ties condition for adaptive stopping.

  • Problem

    Evaluating agents from noisy, incomplete game outcomes remains challenging because Elo cannot handle intransitivity and existing alternatives have scope or tractability limits.

    Source: §1 · pp. 1–2

  • Method

    The paper derives ranking sample-complexity guarantees, adaptively samples comparisons for α-Rank, and bounds ranking-weight uncertainty from payoff bounds.

    Source: §1 · p. 2, §4.1 · p. 4, §5 · p. 6

  • Results

    The paper provides correctness and sample-complexity guarantees for adaptive ranking and an efficient approach to bounding rankings under payoff uncertainty.

    Source: §4.1 · p. 4, §5 · p. 6, §7 · p. 9

  • Takeaways & Limitations

    These methods provide a principled route to evaluating agents in incomplete-information settings, including general-sum, many-player games.

    Source: §1 · p. 2, §7 · p. 9

    The adaptive stopping guarantee excludes instances with tied payoffs in the comparisons, since such cases may prevent finite-time stopping.

    Source: §4 · p. 4

Abstract

from arXiv · show

This paper investigates the evaluation of learned multiagent strategies in the incomplete information setting, which plays a critical role in ranking and training of agents. Traditionally, researchers have relied on Elo ratings for this purpose, with recent works also using methods based on Nash equilibria. Unfortunately, Elo is unable to handle intransitive agent interactions, and other techniques are restricted to zero-sum, two-player settings or are limited by the fact that the Nash equilibrium is intractable to compute. Recently, a ranking method called {\alpha}-Rank, relying on a new graph-based game-theoretic solution concept, was shown to tractably apply to general games. However, evaluations based on Elo or {\alpha}-Rank typically assume noise-free game outcomes, despite the data often being collected from noisy simulations, making this assumption unrealistic in practice. This paper investigates multiagent evaluation in the incomplete information regime, involving general-sum many-player games with noisy outcomes. We derive sample complexity guarantees required to confidently rank agents in this setting. We propose adaptive algorithms for accurate ranking, provide correctness and sample complexity guarantees, then introduce a means of connecting uncertainties in noisy match outcomes to uncertainties in rankings. We evaluate the performance of these approaches in several domains, including Bernoulli games, a soccer meta-game, and Kuhn poker.

1 Introduction

The paper studies how to evaluate learned multiagent strategies when game outcomes are noisy and not all agent match-ups can be observed. It develops an approach for general games that estimates rankings while accounting for uncertainty in observed payoffs.

1 Introduction

  • Existing evaluation methods leave gaps: Elo cannot handle intransitive interactions, while Nash-based methods assume noise-free outcomes and may be restricted to two-player zero-sum games.In large systems, limited computational budgets can make both exhaustive match-ups and reliable payoff estimates impractical.Source: §1 · pp. 1–2
  • Empirical game analysis uses meta-games of high-level agent strategies to compare agents in the original game.These comparisons can inform training or final agent selection.Source: §1 · p. 2
  • The paper gives ranking sample-complexity guarantees, adaptive interaction-sampling algorithms, and a method for propagating payoff uncertainty into ranking uncertainty.The focus is α-Rank and evaluation beyond dyadic interactions.Source: §1 · p. 2

2 Preliminaries

The paper frames agent evaluation as ranking strategies in general games, particularly through α-Rank. Because empirical payoff tables are uncertain, it also motivates carrying payoff uncertainty through to ranking uncertainty.

2 Preliminaries

  • Uncertain empirical payoff tables can yield uncertain rankings, so propagating payoff uncertainty can inform training-resource allocation.Plausible payoff tables can be mapped to plausible rankings using frequentist confidence sets or Bayesian high-posterior-density regions.Source: §2 · p. 3
  • α-Rank applies to general many-player, general-sum games and ranks strategy profiles using the ordered stationary probabilities of a response-graph Markov chain.Its connection to Markov-Conley chains captures intransitive interactions; these are tractably computed in general games, unlike Nash equilibria.Source: §2 · p. 3
  • Elo targets two-player symmetric constant-sum games and has no predictive power in intransitive games such as Rock-Paper-Scissors.Nash Averaging is also limited to two-player zero-sum settings.Source: §2 · p. 3

3 Sample complexity guarantees

The section bounds the observations needed for accurate α-Rank rankings in finite- and infinite-α regimes. Infinite-α exact recovery is guaranteed under a positive payoff-separation condition.

3 Sample complexity guarantees

  • The section gives a finite-α ranking guarantee and an instance-dependent infinite-α guarantee for reconstructing the transition matrix.The bounds depend on payoff bounds and α-Rank parameters; the finite-α guarantee also has the expected dependence on confidence and error tolerance.Source: §3 · pp. 3–4
  • With payoff differences separated by at least Δ, the infinite-α transition matrix and all MCCs are recovered exactly with probability at least 1 − δ.The theorem assumes bounded payoffs and nonzero separation between each player's distinct strategies against fixed opponents.Source: §3 · p. 4
  • Under the infinite-α condition, exact rankings are recovered with probability at least 1 − δ.The paper also provides supplementary theoretical guarantees for Elo in Appendix C.Source: §3 · p. 4

4 Adaptive sampling-based ranking

The section develops ResponseGraphUCB, which adaptively samples strategy profiles to resolve the payoff comparisons needed for α-Rank. Its correctness and sample requirements are analyzed, with the method illustrated on a two-player game.

4.1 Algorithm: ResponseGraphUCB

  • ResponseGraphUCB targets unresolved payoff comparisons, sampling profiles through uniform, uniform-exhaustive, valence-weighted, or count-weighted schemes.Valence-weighted sampling favors nodes with high squared valence; count-weighted sampling favors profiles with fewer observations.Source: §4.1 · pp. 4–5
  • The algorithm stops resolving a pair when its payoff confidence intervals are disjoint, using Hoeffding or Clopper-Pearson bounds and relaxed variants.These stopping rules are intended to ensure confidence in all pairwise comparisons.Source: §4.1 · p. 5
  • In the illustrated two-player game, the reconstructed response graph matches ground truth, and profile (0, 0) is its sole sink and α-Rank's top-ranked profile.The run used 90% confidence with uniform-exhaustive sampling and UCB stopping; strategy profiles received different sample counts.Source: §4.1 · p. 5
  • ResponseGraphUCB outputs the correct response graph with probability at least 1 − δ for a suitable choice of confidence levels and any sampling scheme.The analysis is agnostic to the specific confidence bounds used for stopping.Source: §4.1 · pp. 5–6
  • O(Δ^-2 log(1/(δΔ))) samples suffice with probability at least 1 − 2δ for ResponseGraphUCB using Hoeffding bounds.Here Δ is the minimum payoff gap across the comparisons required by the evaluation instance.Source: §4.1 · p. 6

5 Ranking uncertainty propagation

The section bounds uncertainty in infinite-α α-Rank strategy weights by optimizing over payoff tables consistent with confidence bounds. A reduction to an unconstrained stochastic shortest path problem makes the bounds tractable.

5 Ranking uncertainty propagation

  • For a strategy profile, the goal is to bound its ranking weight across all payoff tables within the known element-wise confidence bounds.The requested interval is the infimum and supremum of π(s) over payoff tables between L and U.Source: §5 · p. 6
  • The section proposes an efficient method for computing uncertainty in infinite-α α-Rank ranking weights.The method optimizes mean return time for the target profile and uses its inverse relationship with stationary probability to obtain a bound.Source: §5 · p. 6
  • The method searches for plausible response graphs that minimize or maximize the target profile’s stationary probability.The payoff bounds determine which response graphs are compatible with the uncertain payoff matrix.Source: §5 · p. 6
  • Payoff confidence bounds are converted into response-graph constraints, then encoded as a constrained shortest path policy-optimization problem.The constraints can be removed to obtain a stochastic shortest path problem solvable by standard means.Source: §5 · p. 6
  • Removing the action-consistency constraints preserves the constrained stochastic shortest path problem’s optimal value.This equality underpins the tractable approach to bounding infinite-α α-Rank ranking weights.Source: §5 · p. 6

6 Experiments

Experiments examine static finite-α sample complexity and adaptive ResponseGraphUCB performance across Bernoulli games, soccer, and poker. They show that ranking errors decline with more samples, while game size and payoff-gap distributions shape adaptive sampling outcomes.

6 Experiments

  • The experiments use randomly generated two-player zero-sum Bernoulli games, a 10-agent soccer meta-game, and a three-player Kuhn poker meta-game with asymmetric payoffs.Noisy outcomes are simulated by independent Bernoulli draws from the payoff table; Elo is not used for the three-player poker domain.Source: §6 · p. 7
  • R-CP-UCB requires roughly an order of magnitude fewer samples than other sampling schemes in Bernoulli games while achieving reasonably low response-graph error.CP-UCB’s tighter confidence bound than Hoeffding bounds also requires fewer interactions for a comparable confidence level.Source: §6 · p. 7, Figure 6.2 · p. 8
  • In soccer, non-relaxed samplers use the full 1e5-interaction budget because 10 strategies per player yield 900 two-arm problems.With uniform-exhaustive sampling at low δ, three variants concentrate samples on very few profiles; increasing δ spreads the budget across more profiles and lowers total edge errors.Source: §6 · pp. 7–8
  • Ranking errors for Elo and infinite-α α-Rank in soccer, and α-Rank in poker, decrease as the payoff-table error falls with added samples.Figure 6.3 plots payoff-table Frobenius error and ranking errors against normalized sample count.Source: §6 · p. 8, Figure 6.3 · p. 8
  • Poker ranking errors are positively correlated with δ, unlike soccer, and show higher variance; the authors conjecture that more near-zero payoff gaps make poker edges harder to resolve.Figure 6.4 shows the ground-truth payoff-gap distributions for soccer and poker.Source: Figure 6.4 · p. 8, §6 · p. 9
  • The results indicate that payoff uncertainty warrants careful consideration when ranking agents and quantify the proposed algorithms’ effectiveness under incomplete information.The conclusion describes bandit algorithms paired with α-Rank as a natural approach when match outcomes must be sampled adaptively under a limited budget.Source: §6 · p. 9

7 Conclusions

The paper studies multiagent evaluation under incomplete information, focusing on α-Rank for general-sum, many-player games. It provides static and adaptive sampling guarantees, an algorithm for propagating payoff uncertainty to ranking uncertainty, and experiments suggesting noisy match outcomes materially affect rankings.

7 Conclusions

  • The paper combines static sample-complexity bounds, adaptive sampling algorithms, and an efficient method to bound rankings under payoff uncertainty, evaluated from Bernoulli games to many-player meta-games.The conclusion’s central insight is that noise in match outcomes plays a prevalent role in determining agent rankings.Source: §7 · p. 9

Appendices: Multiagent Evaluation under Incomplete Information

The appendices review prior evaluation methods and provide background on α-Rank and Elo. They describe how these methods represent and rank interactions, and introduce Elo’s sample-complexity analysis.

A Related Work

  • Earlier empirical-game methods mainly study uncertainty in payoff tables through Nash-based approaches; this paper instead considers Elo and response-graph dynamics.The cited prior work includes sample-complexity bounds, adaptive sampling, payoff-query complexity, and equilibria robust to noisy payoffs.Source: A Related Work · p. 14
  • Elo is limited to two-player interactions, cannot capture intransitive behavior, and can potentially have artificially inflated scores.TrueSkill models player-skill uncertainty, while another fuzzy pair-wise method is also limited to two-player interactions.Source: A Related Work · p. 14

B α-Rank: Additional Background

  • The α-Rank background outlines constructing player-specific meta-payoff tables from match outcomes and then computing a transition matrix.The appendix also illustrates fixation probabilities for different m and α values, and shows a response graph with its MCCs.Source: B α-Rank: Additional Background · p. 14, Figure B.1 · p. 15, Figure B.2 · p. 15
  • A response graph represents pure strategy profiles as nodes and better-response deviations as directed edges; its sink strongly connected components are Markov-Conley Chains.α-Rank’s stationary distribution ranks strategy profiles in those components by their average time in the underlying evolutionary model.Source: B α-Rank: Additional Background · p. 15

C.1 Elo Evaluation

  • BatchElo fits strategy ratings from two-player outcomes, with the ordering of the fitted ratings giving the strategy ranking.The section introduces theoretical guarantees on the samples needed to construct accurate payoff matrices using Elo.Source: §C.1 · pp. 15–16

C.2 Theoretical Results

This section gives an Elo ranking sample-complexity result for symmetric two-player win-loss games. Its proof applies Hoeffding’s inequality to empirical payoffs and uses a union bound.

C.2 Theoretical Results

  • The Elo sample-complexity result concerns a symmetric, two-player win-loss game and empirical payoff estimates from repeated interactions between strategy pairs.The theorem builds on Balduzzi et al..Source: §C.2 · p. 16
  • The proof applies Hoeffding’s inequality to the empirical payoffs for each strategy pair, then uses a union bound.The theorem’s setup specifies interaction counts for each pair of strategies.Source: §C.2 · p. 16

D.1 Proof of Theorem 3.1

The finite-α proof bounds how errors in empirical payoffs affect the invariant distribution. The infinite-α proof shows exact transition-matrix recovery under a payoff-gap condition and a sufficient sampling condition.

D.1 Proof of Theorem 3.1

  • The finite-α result bounds the empirical invariant distribution’s deviation from the true one under a sample condition and bounded payoffs.The proof controls transition-matrix changes using a payoff Lipschitz bound and a lower bound on nonzero transition probabilities.Source: §D.1 · pp. 16–17
  • The finite-α confidence result requires the empirical payoff table to meet a condition involving ε, δ, the number of profiles, and the defined bounds.The appendix states the resulting invariant-distribution guarantee for the empirical Markov chain.Source: §D.1 · p. 17

D.2 Proof of Theorem 3.2

  • With the stated sampling condition, the infinite-α empirical transition matrix is exact with probability at least 1 − δ, so all MCCs are exactly recovered.The theorem assumes bounded payoffs and the stated minimum payoff gap.Source: §D.2 · p. 19
  • In the infinite-α regime, a payoff gap of at least ∆ between distinct strategies ensures exact transition-matrix recovery when payoff-estimation errors stay below ∆/2.The proof uses preservation of payoff-difference signs to recover the transition probabilities and invariant distribution.Source: §D.2 · p. 19

E Proofs of results from Section 4

The appendix proves ResponseGraphUCB’s correctness and sample-complexity guarantees, details confidence-bound variants, and develops reductions for propagating payoff uncertainty into α-Rank rankings.

E Proofs of results from Section 4

  • ResponseGraphUCB returns the correct response graph with probability at least 1 − δ under a suitable choice of confidence levels.The correctness guarantee holds for any particular sampling scheme.Source: E Proofs of results from Section 4 · p. 20

F Additional material on ResponseGraphUCB

E Proofs of results from Section 4

  • With Hoeffding bounds, the algorithm needs at most O(Δ^-2 log(1/(δΔ))) samples with probability at least 1 − 2δ.Here Δ is the minimum payoff gap between compared unilateral deviations; this bound matches the instance-aware bounds up to a log(1/Δ) factor.Source: E Proofs of results from Section 4 · p. 21

F Additional material on ResponseGraphUCB

  • Requiring confidence intervals to be only ε-disjoint can reduce sampling, but forfeits high-probability guarantees of correct comparisons.The variant may help when the noise has lower variance than the worst case assumed by Hoeffding bounds.Source: F Additional material on… · p. 22

G Additional material on uncertainty propagation

  • For ranking-weight bounds, uncertain response-graph edge directions encode compatible payoff tables, but enumerating all resulting transition matrices is generally exponential.The appendix reduces this search to a problem solvable with standard dynamic programming techniques.Source: G Additional material on uncertainty… · p. 22
  • The reduction optimizes a mean hitting-time value in a stochastic shortest-path problem, using its inverse relationship with stationary ranking mass.The method uses mean return times to translate the optimized value into bounds on π(s).Source: G Additional material on uncertainty… · pp. 22–23
  • Removing action-consistency constraints from the CSSP preserves its optimal value, allowing the unconstrained SSP formulation to recover the same optimum.The approach can use linear programming, policy iteration, or value iteration; in multi-population games it can sweep perturbation levels.Source: G Additional material on uncertainty… · p. 23

G.1 MCC detection

  • The MCC detection procedure tests whether a profile’s forced descendants are contained among its forced ancestors, then checks whether a path can leave the ancestor set.It uses certain and uncertain response-graph edge directions to determine whether the profile can lie outside an MCC.Source: §G.1 · p. 23

G.2 Proof of Theorem 5.1

The proof establishes that dropping action-consistency constraints does not change the optimum of the CSSP used to bound α-Rank weights.

G.2 Proof of Theorem 5.1

  • The unconstrained SSP has the same optimal value as CSSP(S, L, U, s).The proof replaces inconsistent edge-direction choices with consistent ones that achieve at least as good an objective value.Source: §G.2 · pp. 23–24
  • When two profiles make inconsistent choices about their shared edge, changing one choice to match the other does not worsen the objective.The proof compares expected costs under the inconsistent and adjusted transition matrices.Source: §G.2 · pp. 23–24
  • For the adjusted transition matrix, nonnegative expected-cost propagation yields an element-wise cost inequality supporting the optimality result.The argument also covers cases where one of the profiles is s itself.Source: §G.2 · p. 24

H.1 Experimental procedures and reproducibility

The appendix reports experimental procedures and supplementary comparisons, including symmetry-based sample savings and preliminary matrix-completion results for Soccer.

H.1 Experimental procedures and reproducibility

  • The experiments report independent trials, plot sample means with 95% confidence intervals, and state that no data were excluded or otherwise preprocessed.Finite-α results use 20, 5, and 5 trials for Bernoulli, Soccer, and poker; Fig. 6.3 ranking results use 10 trials per game and δ.Source: §H.1 · p. 24

H.2 Full comparison plots

  • Figure H.1 plots ResponseGraphUCB interactions required and response-graph edge errors against error tolerance δ across games.The appendix identifies sample complexity and ranking error under adaptive sampling as evaluation interests.Source: Figure H.1 · p. 25, §H.2 · p. 25

H.3 Exploiting knowledge of symmetry in games

  • Symmetry exploitation reconstructed the response graph with 20 samples from one profile, compared with 244 interactions without it.The comparison applies to the game in Fig. 4.1a and requires the payoffs truly to be symmetric for the tighter bounds to be guaranteed.Source: Figure H.2 · p. 26, §H.3 · p. 26

H.4 Kendall’s distance for partial rankings

  • The partial-ranking Kendall distance assigns 0 to concordant or jointly tied pairs, 1 to reversed pairs, and p when only one ranking ties them.The experiments use p = 0.5, within the stated range [0.5, 1] for the distance to be a metric.Source: §H.4 · pp. 26–27

H.5 Preliminary experiments on collaborative filtering-based approaches

  • Logit-matrix completion generally produced lower α-Rank error than odds-matrix completion in preliminary Soccer experiments.The comparison varied observation rates and assumed matrix ranks; the paper notes bandit methods may suit settings where every profile can be played once, while matrix completion may suit otherwise.Source: Figure H.3 · p. 27, §H.5 · p. 27
Loading 1909.09849v4…