Re-evaluating Evaluation

1 Introduction

• Evaluation drives machine-learning progress, but research effort overwhelmingly optimizes algorithms rather than the evaluations used to assess them.Examples include ImageNet and the Arcade Learning Environment, which enabled subsequent breakthroughs.Source: §1 · p. 1
• The train-and-test paradigm is strained by adversarial attacks, superhuman self-play, and a proliferation of environments for general-purpose agents.The paper cites adversarial-evaluation questions [6] [8], self-play evaluation [11], and environments including Mujoco, DM Lab, Open AI Gym, and Psychlab [13] [15].Source: §1 · p. 1
• The paper asks whether tasks test intended abilities, when tasks are redundant, which tasks and agents matter, and how evaluations should themselves be evaluated.These questions are summarized as Q1–Q4.Source: §1 · p. 1
• It treats agent-versus-task and agent-versus-agent evaluation symmetrically, while noting that Elo can fail on cyclic games and can be inflated by copied agents.The framework targets eventual co-optimization of agents and evaluations; task suites can likewise be biased toward particular agents or algorithms.Source: §1 · pp. 1–2

1.1 Overview

• The paper’s first contribution is a unified representation yielding multidimensional Elo for cyclic interactions and using Schur decomposition to expose latent skills and tasks.The mElo illustration concerns training an AlphaGo agent.Source: §1.1 · p. 2
• Nash averaging is invariant to redundant tasks and agents, uses a maximum-entropy Nash equilibrium, and finds which evaluation components matter through a meta-game.Under Nash averaging, human performance ties with the best agents on Atari, suggesting that better-than-human performance has not yet been achieved.Source: §1.1 · p. 2

1.2 Related work

• The paper situates its approach among performance metrics, psychometric evaluation, Bradley-Terry models, item response theory, and empirical game theory.It also draws on combinatorial Hodge theory for statistical ranking and game theory.Source: §1.2 · p. 2

2.1 The Elo rating system

• Elo predicts pairwise outcomes from rating differences, imposes ratings summing to zero, and uses logistic cross-entropy loss.The predicted probability is ˆpij = σ(ri − rj), with the scale constant treated as one.Source: §2.1 · p. 3
• In rock-paper-scissors, Elo assigns equal ratings and predicts ˆpij = 1/2 for every pair, giving it no predictive power for individual matchups.This illustrates Elo’s failure on cyclic interactions.Source: §2.1 · p. 3
• Elo reaches a stationary point under batch updates exactly when empirical and predicted win probabilities have matching row-sums or, equivalently, column-sums.Different win-loss probability matrices can therefore produce identical Elo ratings.Source: §2.1 · p. 3

2 Preliminaries

• The paper represents pairwise evaluation data with antisymmetric matrices, whose entries encode opposing directed flows between agents or tasks.For a flow A, the reverse direction satisfies Aji = −Aij.Source: §2.2 · p. 4

2.2 Antisymmetric matrices

• Combinatorial Hodge theory decomposes antisymmetric flows into gradient and rotational components, separating transitive rating structure from cyclic interactions.The divergence measures each vertex’s contribution as a source, while curl captures three-way cyclic structure.Source: §2.2 · p. 4

=\bantisymmetric matrices

• The divergence recovers Elo ratings or average performance, while Hodge decomposition separates transitive from cyclic effects and Schur decomposition reveals latent skills and tasks beyond those summaries.These tools provide the algebraic basis for analyzing evaluation structure.Source: =antisymmetric matrices · p. 4

3 On the algebraic structure of evaluation

• The framework treats agents and tasks symmetrically by representing agent performance, task difficulty, and their pairwise comparisons within one antisymmetric matrix.The top-right block contains agent performance on tasks, while diagonal blocks compare agents by average skill and tasks by average difficulty.Source: §3 · p. 4, §3.3 · p. 5

3.1 Agents vs agents (AvA)

• Elo is valid exactly when curl(logit P) = 0, so its predictive failures arise from cyclic structure ignored by uniform averaging.When probabilities are generated by Elo ratings, the divergence of their logit equals the rating vector.Source: §3.1 · p. 4
• Multidimensional Elo models cyclic interactions that standard Elo misses by approximating the cyclic component of logit win-loss data.The extension combines Schur and Hodge decompositions to construct low-rank approximations for intransitive abilities.Source: §3.1 · p. 4

3.2 Application: predicting win-loss probabilities in Go

• mElo2 reduces Go prediction error relative to Elo, lowering the Frobenius norm from 0.85 to 0.35 and logistic loss from 1.41 to 1.27.On three non-transitively interacting algorithms, Elo incorrectly predicts two likely winners, whereas mElo2 predicts all likely winners correctly.Source: §3.2 · p. 5

3.3 Agents vs tasks (AvT)

• In agent-vs-task evaluation, average agent skill and task difficulty explain scores when S_ij = s_i − d_j, with departures captured by the residual matrix ˜S.The corresponding average-only explanation holds exactly when curl(A) = 0.Source: §3.3 · p. 5
• The SVD of residual agent-task scores yields latent abilities for agents and latent problems for tasks, while corresponding Schur structure describes the same residual information.This provides a decomposition of evaluation performance beyond average skill and difficulty.Source: §3.3 · p. 5

4.1 Nash averaging

• The maximum-entropy Nash equilibrium provides a unique, symmetric choice among potentially multiple Nash equilibria.It selects the equilibrium with greater entropy than any other Nash equilibrium.Source: §4.1 · p. 6

=\bantisymmetric matrices

• Redundant agents receive split probability mass, whereas uniform averaging can falsely suggest superiority for an agent created by the duplication.For the redundancy example, Nash averaging reports no agent as better than the rest in either representation.Source: =antisymmetric matrices · pp. 6–7

4 Invariant evaluation

• Nash averaging is invariant to redundant agents or tasks, unlike uniform averaging, so duplicated evaluation data does not distort results.The method treats agents and tasks symmetrically through a meta-game.Source: §4 · p. 5, =antisymmetric matrices→ · p. 6, §4.1 · p. 6

=\bantisymmetric matrices

• In cyclic games the maxent Nash is uniform, while in transitive games it concentrates on the highest-rated players.Mixed games do not have a closed-form description, and Nash equilibria can change discontinuously under small matrix perturbations.Source: =antisymmetric matrices · p. 7

4.2 Application: re-evaluation of agents on the Arcade Learning Environment

• In the Atari application, 20 agents and 54 environments are standardized and evaluated using Nash distributions over agents and environments.The meta-game identifies core agents and core environments as unexploitable teams.Source: §4.2 · p. 7, Figure 1 · p. 7
• Nash re-evaluation suggests ALE’s better-than-human result reflects a skew toward environments where current agents perform well, while fewer environments test human-specific skills.The Nash distribution evens out the playing field and identifies important agents and environments.Source: §4.2 · pp. 7–8, Figure 2 · p. 8

5 Conclusion

• Redundancy is the dominant evaluation symmetry because different agents, algorithms, environments, and tasks can perform essentially the same job.This motivates invariant evaluation methods.Source: §5 · p. 8
• Nash averaging automatically adjusts for redundant agents and tasks, so including additional evaluation data should not bias results apart from computational cost.The method is presented as a step toward more objective evaluation.Source: §5 · p. 8
• Nash averaging depends on the agents and environments supplied, cannot detect differences irrelevant to those players, and may be unsuitable for constructing automated curricula.The paper recommends diverse agents and environments while noting that Nash removes user control over the resulting distribution.Source: §5 · p. 8

A Invariance: Further motivation

• Uniform task averaging can reverse which agent appears best when a benchmark adds a minor variant of an existing task.The example shows that the additional task can change the average ranking despite adding little new information.Source: A Invariance: Further motivation · p. 12
• In agent-versus-agent evaluation, duplicating one agent can decrease A’s Elo and increase B’s, making ratings manipulable through population composition.The three-agent example has rock-paper-scissors dynamics before the duplicate is added.Source: A Invariance: Further motivation · p. 12
• The paper distinguishes its invariance notion from psychometric measurement invariance, which concerns measuring the same construct across predefined groups.The related-work comparison uses examples from IQ-test questions and cultural groups.Source: A Invariance: Further motivation · p. 13

B Proofs of propositions

• Batch Elo updates are stable when empirical and predicted probability matrices have matching row-sums, equivalently matching column-sums.The proof invokes the constraint r^T1 = 0 and the Hodge decomposition.Source: B Proofs of propositions · p. 13
• The Schur decomposition of the constructed antisymmetric matrix exposes eigenpairs corresponding to the singular values of the original evaluation matrix.The construction links latent structure in evaluation data to the matrix spectrum.Source: B Proofs of propositions · p. 13
• An Elo rating generates the observed pairwise probabilities exactly when the probability logit has zero curl.The proposition also identifies the divergence of the logit with the Elo rating when such ratings exist.Source: B Proofs of propositions · p. 13
• A unique symmetric Nash equilibrium with maximum entropy exists for the antisymmetric zero-sum game used by Nash averaging.It has greater entropy than any other Nash equilibrium.Source: B Proofs of propositions · p. 13

C Proof of theorem 1

• Maximum-entropy Nash averaging is invariant to redundancies in the agent interaction matrix.Adding redundant copies does not change the evaluation in the sense formalized by the theorem.Source: C Proof of theorem 1 · p. 14
• If p* is a Nash equilibrium for an approximate matrix A-hat and epsilon is the maximum entrywise difference from A, then p* is an epsilon-Nash equilibrium for A.This gives continuity under bounded perturbations of the interaction matrix.Source: C Proof of theorem 1 · p. 14
• For cyclic meta-games, the maximum-entropy Nash equilibrium is uniform across players.The theorem states this occurs when div(A) = 0.Source: C Proof of theorem 1 · p. 14
• For transitive meta-games, maximum-entropy Nash averaging is uniform over the highest-rated players, allowing ties.The transitive case is represented as A = grad(r).Source: C Proof of theorem 1 · p. 14

C.1 Proof of theorem 1.1

• The invariance definition requires a function to remain unchanged when the last row and column of an antisymmetric matrix are copied.The copied row and column represent a redundant player in the interaction matrix.Source: §C.1 · p. 14
• When a copied row already receives positive maximum-entropy mass, adding another copy spreads that mass evenly across the redundant copies.This explains why duplication does not alter the aggregate evaluation.Source: §C.1 · p. 14
• Adding a redundant copy of an agent’s interaction row and column preserves Nash equilibria after aggregating the copied agents’ probability mass.The construction can be generalized to arbitrary copied rows or columns and applied repeatedly.Source: §C.1 · p. 14

• An equilibrium for ˆA is an ϵ-Nash equilibrium for A when ϵ = ∥A −ˆA∥max.The result specializes the general approximate-game argument to antisymmetric matrices.Source: §C.2 · p. 15
• The proof bounds deviation incentives using the Nash property for ˆA and the max-norm approximation error between A and ˆA.Antisymmetry makes the equilibrium value zero, while the perturbation term is at most ϵ for probability distributions.Source: §C.2 · p. 15
• The same divergence control extends to operator and Frobenius norms because the max norm is bounded by both.The inequalities ∥S∥max ≤ ∥S∥2 ≤ ∥S∥F transfer the approximation guarantee across norms.Source: §C.2 · p. 15
• The proof adapts an earlier lemma stating that an equilibrium of an approximate game is a 2ϵ-Nash equilibrium for the original game.The present antisymmetric specialization is described as slightly sharper.Source: §C.2 · p. 15

• When div(A) = 0, the uniform distribution is a Nash equilibrium and has maximum entropy.There is no incentive to deviate because the relevant average payoff is zero.Source: §C.3 · p. 15
• When div(A) ≠ 0, antisymmetry ensures positive and negative coordinates, so a player can profit by shifting mass away from the uniform distribution.The uniform distribution is therefore not a Nash equilibrium in this case.Source: §C.3 · p. 15
• For transitive A = grad(r), maximum-entropy Nash strategies distribute mass uniformly across the coordinates where r is maximal.If the maximum is unique, both strategies concentrate there; ties permit uniform mass over all maximal coordinates.Source: §C.3 · p. 15

D Nash averaging for agent-vs-task

• In the bipartite graph, agents interact with tasks but not directly with other agents or tasks, so divergence, gradient, and curl require specialized definitions.The paper uses ad hoc notation for agent-vs-task rather than the fully general graph formulation.Source: D Nash averaging for agent-vs-task · p. 16
• The agent-vs-task setup gives each meta-player distributions over agents and tasks, producing a unique symmetric maximum-entropy Nash equilibrium.The method extends the agent-vs-agent construction while respecting the bipartite interaction structure.Source: D Nash averaging for agent-vs-task · p. 16
• The evaluation reports task difficulty by Nash averaging over agents and agent skill by Nash averaging over environments.These quantities are derived from the equilibrium distributions over the two sides of the meta-game.Source: D Nash averaging for agent-vs-task · p. 16, =antisymmetric matrices · p. 16

=\bantisymmetric matrices

• The maximum-entropy equilibrium places mass on the most skillful agents and most difficult tasks, with uniform allocation among ties.The same best-response logic applies symmetrically to the two meta-players.Source: =antisymmetric matrices · p. 16
• Nash averaging is invariant to redundancies in the evaluation matrix A.This is the principal stated property of the agent-vs-task theorem.Source: =antisymmetric matrices · p. 16

P2. Continuous: If (p∗

• If an equilibrium for ˆA is computed within ϵ = ∥A −ˆA∥max, it is an ϵ-Nash equilibrium for A.This gives a direct robustness guarantee for approximate evaluation games.Source: P2. Continuous: If (p∗ · p. 16
• When average agent skill is uniform, the agent component of the maximum-entropy equilibrium is uniform; the analogous condition holds for task difficulty.The theorem links uniform equilibrium components to diva(A) = 0 and dive(A) = 0.Source: P2. Continuous: If (p∗ · p. 16
• For transitive meta-games, the equilibrium is uniform over the most skillful agents and most difficult tasks, allowing ties.This provides an interpretable best-performing and hardest-task characterization.Source: P2. Continuous: If (p∗ · p. 16

E Code for computing mElo2 updates

• The mElo2 update uses observed win probability, current ratings, and a two-dimensional interaction matrix to update player ratings and cyclic-interaction coordinates.The predicted probability combines rating differences with a bilinear interaction term.Source: E Code for computing mElo2 updates · p. 17

F.1 Visualizing the Schur decomposition

• For rank-two transitive matrices, Schur-decomposition rows lie along a line, while the illustrated cyclic matrix has rows on a circle centered at the origin.These geometric patterns visualize transitive versus cyclic structure.Source: §F.1 · pp. 17–18, Figure 3 · p. 17

F.2 Areas and phases

• Schur decomposition entries can be interpreted as sums of signed parallelogram areas across orthogonal two-dimensional subspaces.In the rank-two case, each logit corresponds to one signed area, as illustrated in Figure 4.Source: §F.2 · p. 18, Figure 4 · p. 18

F.3 Comment on Schur and Hodge

• Schur and Hodge decompositions need not align when the rotational component is not well approximated by the relevant low-rank remainder.The paper recommends extracting the transitive component before applying Schur decomposition, despite possible nonoptimality in ∥·∥2.Source: §F.3 · p. 18, Figure 5 · p. 19, Figure 6 · p. 20