Re-evaluating Evaluation

Introduction

Evaluation is a key driver of progress in machine learning, with e.g. ImageNet and the Arcade Learning Environment enabling subsequent breakthroughs in supervised and reinforcement learning . However, developing evaluations has received little systematic attention compared to developing algorithms. Immense amounts of compute is continually expended smashing algorithms and tasks together – but the results are almost never used to evaluate and optimize evaluations. In a striking asymmetry, results are almost exclusively applied to evaluate and optimize algorithms.

The classic train-and-test paradigm on common datasets, which has served the community well , is reaching its limits. Three examples suffice. Adversarial attacks have complicated evaluation, raising questions about which attacks to test against . Training agents far beyond human performance with self-play means they can only really be evaluated against each other . The desire to build increasingly general-purpose agents has led to a proliferation of environments: Mujoco, DM Lab, Open AI Gym, Psychlab and others .

In this paper we pause to ask, and partially answer, some basic questions about evaluation: Q1. Do tasks test what we think they test? Q2. When is a task redundant? Q3. Which tasks (and agents) matter the most? Q4. How should evaluations be evaluated?

We consider two scenarios: agent vs task (AvT), where algorithms are evaluated on suites of datasets or environments; and agent vs agent (AvA), where agents compete directly as in Go and Starcraft. Our goal is to treat tasks and agents symmetrically – with a view towards, ultimately, co-optimizing agents and evaluations. From this perspective AvA, where the task is (beating) another agent, is especially interesting. Performance in AvA is often quantified using Elo ratings or the closely related TrueSkill . There are two main problems with Elo. Firstly, Elo bakes-in the assumption that relative skill is transitive; but Elo is meaningless – it has no predictive power – in cyclic games like rock-paper-scissors. Intransitivity has been linked to biodiversity in ecology, and may be useful when evolving populations of agents . Secondly, an agent’s Elo rating can be inflated by instantiating many copies of an agent it beats (or conversely). This can cause problems when Elo guides hyper-optimization methods like population-based training . Similarly, the most important decision when constructing a task-suite is which tasks to include. It is easy, and all too common, to bias task-suites in favor of particular agents or algorithms.

Section 2 presents background information on Elo and tools for working with antisymmetric matrices, such as the Schur decomposition and combinatorial Hodge theory. A major theme underlying the paper is that the fundamental algebraic structure of tournaments and evaluation is antisymmetric . Techniques specific to antisymmetric matrices are less familiar to the machine learning community than approaches like PCA that apply to symmetric matrices and are typically correlation-based.

Section 3 presents a unified approach to representing evaluation data, where agents and tasks are treated symmetrically. A basic application of the approach results in our first contribution: a multidimensional Elo rating (mElo) that handles cyclic interactions. We also sketch how the Schur decomposition can uncover latent skills and tasks, providing a partial answer to Q1. We illustrate mElo on the domain of training an AlphaGo agent .

The second contribution of the paper is Nash averaging, an evaluation method that is invariant to redundant tasks and agents, see section 4. The basic idea is to play a meta-game on evaluation data . The meta-game has a unique maximum entropy Nash equilibrium. The key insight of the paper is that the maxent Nash adapts automatically to the presence of redundant tasks and agents. The maxent Nash distribution thus provides a principled answer to Q2 and Q3: which tasks and agents do and do not matter is determined by a meta-game. Finally, expected difficulty of tasks under the Nash distribution on agents yields a partial answer to Q4. The paper concludes by taking a second look at the performance of agents on Atari. We find that, under Nash averaging, human performance ties with the best agents, suggesting better-than-human performance has not yet been achieved.

2 Related work

Legg and Hutter developed a definition of intelligence which, informally, states “intelligence measures an agent’s ability to achieve goals in a wide range of environments” . Formally, they consider all computable tasks weighted by algorithmic complexity . Besides being incomputable, the distribution places (perhaps overly) heavy weight on the simplest tasks.

A comprehensive study of performance metrics for machine learning and AI can be found in . There is a long history of psychometric evaluation in humans, some of which has been applied in artificial intelligence . Bradley-Terry models provide a general framework for pairwise comparison . Researchers have recently taken a second look at the arcade learning environment and introduced new performance metrics . However, the approach is quite particular. Recent work using agents to evaluate games has somewhat overlapping motivation with this paper . Item response theory is an alternative, and likely complementary, approach to using agents to evaluate tasks that has recently been applied to study the performance of agents on the Arcade Learning Environment .

Our approach draws heavily on work applying combinatorial Hodge theory to statistical ranking and game theory . We also draw on empirical game theory , by using a meta-game to “evaluate evaluations”, see section 4. Empirical game theory has been applied to domains like poker and continuous double auctions, and has recently been extended to asymmetric games . von Neumann winners in the dueling bandit setting and NE-regret are related to Nash averaging .

Preliminaries

Suppose $n$ agents play a series of pairwise matches against each other. Elo assigns a rating $r_{i}$ to each player $i\in[n]$ based on their wins and losses, which we represent as an $n$-vector ${\mathbf{r}}$. The predicted probability of $i$ beating $j$ given their Elo ratings is

The constant $\alpha$ is not important in what follows, so we pretend $\alpha=1$. Observe that only the difference between Elo ratings affects win-loss predictions. We therefore impose that Elo ratings sum to zero, ${\mathbf{r}}^{\intercal}{\mathbf{1}}=0$, without loss of generality. Define the loss,

Choosing learning rate $\eta=16$ or $32$ recovers the updates introduced by Arpad Elo in .

The win-loss probabilities predicted by Elo ratings can fail in simple cases. For example, rock, paper and scissors will all receive the same Elo ratings. Elo’s predictions are $\hat{p}_{ij}=\frac{1}{2}$ for all $i,j$ – and so Elo has no predictive power for any given pair of players (e.g. paper beats rock with $p=1$).

What are the Elo update’s fixed points? Suppose we batch matches to obtain empirical estimates of the probability of player $i$ beating $j$: $\bar{p}_{ij}=\sum_{n}\frac{S_{ij}^{n}}{N_{ij}}$. As the number of matches approaches infinity, the empirical estimates approach the true probabilities $p_{ij}$.

Elo ratings are at a stationary point under batch updates iff the matrices of empirical probabilities and predicted probabilities have the same row-sums (or, equivalently the same column-sums):

Many different win-loss probability matrices result in identical Elo ratings. The situation is analogous to how many different joint probability distributions can have the same marginals. We return to this topic in section 3.1.

2 Antisymmetric matrices

We recall some basic facts about antisymmetric matrices. Matrix ${\mathbf{A}}$ is antisymmetric if ${\mathbf{A}}+{\mathbf{A}}^{\intercal}=0$. Antisymmetric matrices have even rank and imaginary eigenvalues $\{\pm i\lambda_{j}\}_{j=1}^{\text{rank}({\mathbf{A}})/2}$. Any antisymmetric matrix ${\mathbf{A}}$ admits a real Schur decomposition:

where ${\mathbf{Q}}$ is orthogonal and $\boldsymbol{\Lambda}$ consists of zeros except for $(2\times 2)$ diagonal-blocks of the form:

The entries of $\boldsymbol{\Lambda}$ are real numbers, found by multiplying the eigenvalues of ${\mathbf{A}}$ by $i=\sqrt{-1}$.

Given matrix ${\mathbf{S}}_{m\times n}$ with rank $r$ and singular value decomposition ${\mathbf{U}}_{m\times r}{\mathbf{D}}_{r\times r}{\mathbf{V}}_{r\times n}^{\intercal}$. Construct antisymmetric matrix

Then the thin Schur decomposition of ${\mathbf{A}}$ is ${\mathbf{Q}}_{(m+n)\times 2r}\boldsymbol{\Lambda}_{2r\times 2r}{\mathbf{Q}}_{2r\times(m+n)}^{\intercal}$ where the nonzero pairs in $\boldsymbol{\Lambda}_{2r\times 2r}$ are $\pm$ the singular values in ${\mathbf{D}}_{r\times r}$ and

The combinatorial gradient of an $n$-vector ${\mathbf{r}}$ is the flow: $\operatorname*{grad}({\mathbf{r}}):={\mathbf{r}}{\mathbf{1}}^{\intercal}-{\mathbf{1}}{\mathbf{r}}^{\intercal}$. Flow ${\mathbf{A}}$ is a gradient flow if ${\mathbf{A}}=\operatorname*{grad}({\mathbf{r}})$ for some ${\mathbf{r}}$, or equivalently if ${\mathbf{A}}_{ij}={\mathbf{r}}_{i}-{\mathbf{r}}_{j}$ for all $i,j$. The divergence of a flow is the $n$-vector $\operatorname*{{div}}({\mathbf{A}}):=\frac{1}{n}{\mathbf{A}}\cdot{\mathbf{1}}$. The divergence measures the contribution to the flow of each vertex, considered as a source. The curl of a flow is the three-tensor $\operatorname*{curl}({\mathbf{A}})_{ijk}={\mathbf{A}}_{ij}+{\mathbf{A}}_{jk}-{\mathbf{A}}_{ik}$. Finally, the rotation is $\operatorname*{rot}({\mathbf{A}})_{ij}=\frac{1}{n}\sum_{k=1}^{n}\operatorname*{curl}({\mathbf{A}})_{ijk}$.

(i) $\operatorname*{{div}}\circ\operatorname*{grad}({\mathbf{r}})={\mathbf{r}}$ for any ${\mathbf{r}}$ satisfying ${\mathbf{r}}^{\intercal}{\mathbf{1}}=0$. (ii) $\operatorname*{{div}}\circ\operatorname*{rot}({\mathbf{A}})={\mathbf{0}}_{n\times 1}$ for any flow ${\mathbf{A}}$. (iii) $\operatorname*{rot}\circ\operatorname*{grad}({\mathbf{r}})={\mathbf{0}}_{n\times n}$ for any vector ${\mathbf{r}}$. (iv) The vector space of antisymmetric matrices admits an orthogonal decomposition

with respect to the standard inner product $\langle{\mathbf{A}},{\mathbf{B}}\rangle=\sum_{ij}{\mathbf{A}}_{ij}{\mathbf{B}}_{ij}$. Concretely, any antisymmetric matrix decomposes as

Sneak peak. The divergence recovers Elo ratings or just plain average performance depending on the scenario. The Hodge decomposition separates transitive (captured by averages or Elo) from cyclic interactions (rock-paper-scissors), and explains when Elo ratings make sense. The Schur decomposition is a window into the latent skills and tasks not accounted for by Elo and averages.

On the algebraic structure of evaluation

The Schur decomposition and combinatorial Hodge theory provide a unified framework for analyzing evaluation data in the AvA and AvT scenarios. In this section we provide some basic tools and present a multidimensional extension of Elo that handles cyclic interactions.

In AvA, results are collated into a matrix of win-loss probabilities based on relative frequencies. Construct ${\mathbf{A}}=\operatorname*{logit}{\mathbf{P}}$ with ${\mathbf{A}}_{ij}:=\log\frac{p_{ij}}{1-p_{ij}}$. Matrix ${\mathbf{A}}$ is antisymmetric since $p_{ij}+p_{ji}=1$.

When can Elo correctly predict win-loss probabilities? The answer is simple in logit space:

(i) If probabilities ${\mathbf{P}}$ are generated by Elo ratings ${\mathbf{r}}$ then the divergence of its logit is ${\mathbf{r}}$. That is,

(ii) There is an Elo rating that generates probabilities ${\mathbf{P}}$ iff $\operatorname*{curl}(\operatorname*{logit}{\mathbf{P}})=0$. Equivalently, iff $\log\frac{p_{ij}}{p_{ji}}+\log\frac{p_{jk}}{p_{kj}}+\log\frac{p_{ki}}{p_{ik}}=0$ for all $i,j,k$.

Multidimensional Elo (mElo2k). Elo ratings bake-in the assumption that relative skill is transitive. However, there is no single dominant strategy in games like rock-paper-scissors or (arguably) StarCraft. Rating systems that can handle intransitive abilities are therefore necessary. An obvious approach is to learn a feature vector ${\mathbf{w}}$ and a rating vector ${\mathbf{r}}_{i}$ per player, and predict $\hat{p}_{ij}=\sigma({\mathbf{r}}_{i}^{\intercal}{\mathbf{w}}-{\mathbf{r}}_{j}^{\intercal}{\mathbf{w}})$. Unfortunately, this reduces to the standard Elo rating since ${\mathbf{r}}_{i}^{\intercal}{\mathbf{w}}$ is a scalar.

where the rows of ${\mathbf{C}}$ are orthogonal to each other, to ${\mathbf{r}}$, and to ${\mathbf{1}}$. The larger $2k$, the better the approximation. Let mElo2k assign each player Elo rating $r_{i}$ and $2k$-dimensional vector ${\mathbf{c}}_{i}$. Vanilla Elo uses $2k=0$. The mElo2k win-loss prediction is

Online updates can be computed by gradient descent, see section E, with orthogonality enforced.

2 Application: predicting win-loss probabilities in Go

To better understand the difference, we zoom in on three algorithms that were observed to interact non-transitively in : $\alpha_{v}$ with value net, $\alpha_{p}$ with policy net, and Zen. Elo’s win-loss predictions are poor (Table Elo: Elo incorrectly predicts both that $\alpha_{p}$ likely beats $\alpha_{v}$ and $\alpha_{v}$ likely beats Zen), whereas mElo2 (Table mElo2) correctly predicts likely winners in all cases (Table empirical), with more accurate probabilities:

3 Agents vs tasks (AvT)

The top-right block of ${\mathbf{A}}$ is agent performance on tasks; the bottom-left is task difficulty for agents. The top-left block compares agents by their average skill on tasks; the bottom-right compares tasks by their average difficulty for agents. Average skill and difficulty explain the data if the score of agent $i$ on task $j$ is ${\mathbf{S}}_{ij}={\mathbf{s}}_{i}-{\mathbf{d}}_{j}$, the agent’s skill minus the task’s difficulty, for all $i,j$. Paralleling proposition 3, averages explain the data, ${\mathbf{S}}={\mathbf{s}}{\mathbf{1}}^{\intercal}-{\mathbf{1}}{\mathbf{d}}^{\intercal}$, iff $\operatorname*{curl}({\mathbf{A}})={\mathbf{0}}$.

Invariant evaluation

Evaluation is often based on metrics like average performance or Elo ratings. Unfortunately, two (or two hundred) tasks or agents that look different may test/exhibit identical skills. Overrepresenting particular tasks or agents introduces biases into averages and Elo – biases that can only be detected post hoc. Humans must therefore decide which tasks or agents to retain, to prevent redundant agents or tasks from skewing results. At present, evaluation is not automatic and does not scale. To be scalable and automatic, an evaluation method should always benefit from including additional agents and tasks. Moreover, it should adjust automatically and gracefully to redundant data.

An evaluation method maps data to a real-valued function on players (that is, agents or agents and tasks):

Desired properties. An evaluation method should be:

Invariant: adding redundant copies of an agent or task to the data should make no difference.

Continuous: the evaluation method should be robust to small changes in the data.

Interpretable: hard to formalize, but the procedure should agree with intuition in basic cases.

Elo and uniform averaging over tasks are examples of evaluation methods that invariance excludes.

This section presents an evaluation method satisfying properties $P1,P2,P3$. We discuss AvA here, see section D for AvT. Given antisymmetric logit matrix ${\mathbf{A}}$, define a two-player meta-game with payoffs $\mu_{1}({\mathbf{p}},{\mathbf{q}})={\mathbf{p}}^{\intercal}{\mathbf{A}}{\mathbf{q}}$ and $\mu_{2}({\mathbf{p}},{\mathbf{q}})={\mathbf{p}}^{\intercal}{\mathbf{B}}{\mathbf{q}}$ for the row and column meta-players, where ${\mathbf{B}}={\mathbf{A}}^{\intercal}$. The game is symmetric because ${\mathbf{B}}={\mathbf{A}}^{\intercal}$ and zero-sum because ${\mathbf{B}}=-{\mathbf{A}}$.

The row and column meta-players pick ‘teams’ of agents. Their payoff is the expected log-odds of their respective team winning under the joint distribution. If there is a dominant agent that has better than even odds of beating the rest, both players will pick it. In rock-paper-scissors, the only unbeatable-on-average team is the uniform distribution. In general, the value of the game is zero and the Nash equilibria are teams that are unbeatable in expectation.

A problem with Nash equilibria (NE) is that they are not unique, which forces the user to make choices and undermines interpretability . Fortunately, for zero-sum games there is a natural choice of Nash:

For antisymmetric ${\mathbf{A}}$ there is a unique symmetric Nash equilibrium $({\mathbf{p}}^{*},{\mathbf{p}}^{*})$ solving $\max_{{\mathbf{p}}\in\Delta_{n}}\min_{{\mathbf{q}}\in\Delta_{n}}{\mathbf{p}}^{\intercal}{\mathbf{A}}{\mathbf{q}}$ with greater entropy than any other Nash equilibrium.

Maxent Nash is maximally indifferent between players with the same empirical performance.

The maxent Nash evaluation method for AvA is

where ${\mathbf{p}}_{\mathbf{A}}^{*}$ is the maxent Nash equilibrium and ${\mathbf{n}}_{\mathbf{A}}:={\mathbf{A}}\cdot{\mathbf{p}}^{*}_{\mathbf{A}}$ is the Nash average.

Invariance to redundancy is best understood by looking at an example; for details see section C.

Consider two logit matrices, where the second adds a redundant copy of agent $C$ to the first:

and ${\mathbf{A}}^{\prime}$ $A$ $B$ $C_{1}$ $C_{2}$ $A$ 0.0 4.6 -4.6 -4.6 $B$ -4.6 0.0 4.6 4.6 $C_{1}$ 4.6 -4.6 0.0 0.0 $C_{2}$ 4.6 -4.6 0.0 0.0

The maxent Nash for ${\mathbf{A}}$ is ${\mathbf{p}}_{\mathbf{A}}^{*}=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$. It is easy to check that $(\frac{1}{3},\frac{1}{3},\frac{\alpha}{3},\frac{1-\alpha}{3})$ is Nash for ${\mathbf{A}}^{\prime}$ for any $\alpha\in$ and thus the maxent Nash for ${\mathbf{A}}^{\prime}$ is ${\mathbf{p}}^{*}_{{\mathbf{A}}^{\prime}}=(\frac{1}{3},\frac{1}{3},\frac{1}{6},\frac{1}{6})$. Maxent Nash automatically detects the redundant agents $C_{1},C_{2}$ and distributes $C$’s mass over them equally.

Uniform averaging is not invariant to adding redundant agents; concretely $\operatorname*{{div}}({\mathbf{A}})={\mathbf{0}}$ whereas $\operatorname*{{div}}({\mathbf{A}}^{\prime})=(-1.15,1.15,0,0)$, falsely suggesting agent $B$ is superior. In contrast, ${\mathbf{n}}_{\mathbf{A}}={\mathbf{0}}_{3\times 1}$ and ${\mathbf{n}}_{{\mathbf{A}}^{\prime}}={\mathbf{0}}_{4\times 1}$ (the zero-vectors have different sizes because there are different numbers of agents). Nash averaging correctly reports no agent is better than the rest in both cases.

The maxent NE has the following properties:

Invariant: Nash averaging, with respect to the maxent NE, is invariant to redundancies in ${\mathbf{A}}$.

Continuous: If ${\mathbf{p}}^{*}$ is a Nash for $\hat{{\mathbf{A}}}$ and $\epsilon=\|{\mathbf{A}}-\hat{{\mathbf{A}}}\|_{\text{max}}$ then ${\mathbf{p}}^{*}$ is an $\epsilon$-Nash for ${\mathbf{A}}$.

Interpretable: (i) The maxent NE on ${\mathbf{A}}$ is the uniform distribution, ${\mathbf{p}}^{*}=\frac{1}{n}{\mathbf{1}}$, iff the meta-game is cyclic, i.e. $\operatorname*{{div}}({\mathbf{A}})={\mathbf{0}}$. (ii) If the meta-game is transitive, i.e. ${\mathbf{A}}=\operatorname*{grad}({\mathbf{r}})$, then the maxent NE is the uniform distribution on the player(s) with highest rating(s) – there could be a tie.

See section C for proof and formal definitions. For interpretability, if ${\mathbf{A}}=\operatorname*{grad}({\mathbf{r}})$ then the transitive rating is all that matters: Nash averaging measures performance against the best player(s). If $\operatorname*{{div}}({\mathbf{A}})={\mathbf{0}}$ then no player is better than any other. Mixed cases cannot be described in closed form.

The continuity property is quite weak: theorem 1.2 shows the payoff is continuous: a team that is unbeatable for $\hat{{\mathbf{A}}}$ is $\epsilon$-beatable for nearby ${\mathbf{A}}$. Unfortunately, Nash equilibria themselves can jump discontinuously when ${\mathbf{A}}$ is modified slightly. Perturbed best response converges to a more stable approximation to Nash that unfortunately is not invariant.

Consider the cyclic and transitive logit matrices

The maxent Nash equilibria and Nash averages of ${\mathbf{C}}+\epsilon{\mathbf{T}}$ are

The maxent Nash is the uniform distribution over agents in the cyclic case ($\epsilon=0$), and is concentrated on the first player when it dominates the others ($\epsilon>\frac{1}{2}$). When $0<\epsilon<\frac{1}{2}$ the optimal team has most mass on the first and last players. Nash jumps discontinuously at $\epsilon=\frac{1}{2}$.

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

To illustrate the method, we re-evaluate the performance of agents on Atari . Data is taken from results published in . Agents include rainbow, dueling networks, prioritized replay, pop-art, DQN, count-based exploration and baselines like human, random-action and no-action. The 20 agents evaluated on 54 environments are represented by matrix ${\mathbf{S}}_{20\times 54}$. It is necessary to standardize units across environments with quite different reward structures: for each column we subtract the $\min$ and divide by the $\max$ so scores lie in $$.

We introduce a meta-game where row meta-player picks aims to pick the best distribution ${\mathbf{p}}^{*}_{a}$ on agents and column meta-player aims to pick the hardest distribution ${\mathbf{p}}^{*}_{e}$ on environments, see section D for details. We find a Nash equilibrium using an LP-solver; it should be possible to find the maxent Nash using the algorithm in . The Nash distributions are shown in figure 1. The supports of the distributions are the ‘core agents’ and the ‘core environments’ that form unexploitable teams. See appendix for tables containing all skills and difficulties. panel B.

Figure 2A shows the skill of agents under uniform $\frac{1}{n}{\mathbf{S}}\cdot{\mathbf{1}}$ and Nash ${\mathbf{S}}\cdot{\mathbf{p}}_{e}^{*}$ averaging over environments; panel B shows the difficulty of environments under uniform $-\frac{1}{m}{\mathbf{S}}^{\intercal}\cdot{\mathbf{1}}$ and Nash $-{\mathbf{S}}^{\intercal}\cdot{\mathbf{p}}_{a}^{*}$ averaging over agents. There is a tie for top between the agents with non-zero mass – including human. This follows by the indifference principle for Nash equilibria: strategies with support have equal payoff.

Our results suggest that the better-than-human performance observed on the Arcade Learning Environment is because ALE is skewed towards environments that (current) agents do well on, and contains fewer environments testing skills specific to humans. Solving the meta-game automatically finds a distribution on environments that evens out the playing field and, simultaneously, identifies the most important agents and environments.

Conclusion

A powerful guiding principle when deciding what to measure is to find quantities that are invariant to naturally occurring transformations. The determinant is computed over a basis – however, the determinant is invariant to the choice of basis since $\det(G^{-1}AG)=\det(A)$ for any invertible matrix $G$. Noether’s theorem implies the dynamics of a physical system with symmetries obeys a conservation law. The speed of light is fundamental because it is invariant to the choice of inertial reference frame.

One must have symmetries in mind to talk about invariance. What are the naturally occurring symmetries in machine learning? The question admits many answers depending on the context, see e.g. . In the context of evaluating agents, that are typically built from neural networks, it is unclear a priori whether two seemingly different agents – based on their parameters or hyperparameters – are actually different. Further, it is increasingly common that environments and tasks are parameterized – or are learning agents in their own right, see self-play , adversarial attacks , and automated curricula . The overwhelming source of symmetry when evaluating learning algorithms is therefore redundancy: different agents, networks, algorithms, environments and tasks that do basically the same job.

Nash evaluation computes a distribution on players (agents, or agents and tasks) that automatically adjusts to redundant data. It thus provides an invariant approach to measuring agent-agent and agent-environment interactions. In particular, Nash averaging encourages a maximally inclusive approach to evaluation: computational cost aside, the method should only benefit from including as many tasks and agents as possible. Easy tasks or poorly performing agents will not bias the results. As such Nash averaging is a significant step towards more objective evaluation.

Nash averaging is not always the right tool. Firstly, it is only as good as the data: garbage in, garbage out. Nash decides which environments are important based on the agents provided to it, and conversely. As a result, the method is blind to differences between environments that do not make a difference to agents and vice versa. Nash-based evaluation is likely to be most effective when applied to a diverse array of agents and environments. Secondly, for good or ill, Nash averaging removes control from the user. One may have good reason to disagree with the distribution chosen by Nash. Finally, Nash is a harsh master. It takes an adversarial perspective and may not be the best approach to, say, constructing automated curricula – although boosting is a related approach that works well . It is an open question whether alternate invariant evaluations can be constructed, game-theoretically or otherwise.

Acknowledgements. We thank Georg Ostrovski, Pedro Ortega, José Hernández-Orallo and Hado van Hasselt for useful feedback.

References

A Invariance: Further motivation

Consider agents A, B, C evaluated on a benchmark suite comprising three tasks:

On average, agent A performs best and agent C performs worst. Consider a second benchmark suite containing an additional fourth task. On the second benchmark suite, agent A performs worst and agent C performs best on average. However, a closer look at the second suite reveals that the additional task is a minor variant of one of the original three tasks.

Measuring performance by uniformly averaging over tasks in a benchmark suite is sensitive to the set of tasks that are included in the suite. Including redundant tasks, whether consciously or not, can easily skew average performance in favor of or against particular agents.

The problem becomes more serious when agent performance is measured against other agents, as in games such as Go, Chess or StarCraft. It is easy to manipulate the measured performance of agents by tweaking the composition of the population used to evaluate them. Consider the following example:

The three agents exhibit rock-paper-scissors dynamics; their Elo ratings (normalized to sum to zero) are all zero. However, adding a second copy of agent C decreases the Elo rating of agent A and increases the Elo rating of agent B:

That is, the Elo ratings of agents A and B are easily manipulated by changing the structure of the population.

The examples above suggest it is important to find evaluation metrics that are invariant to redundant changes in the population of agents or suite of tasks.

A different notion of measurement invariance has been proposed in the psychometric and consumer research literatures . There, measurement invariance refers to the statistical property that a measurement measures the same construct across a predefined set of groups. For example, whether or not a question in an IQ test is measurement invariant has to do with whether or not the question is interpreted in the same way by individuals with different cultural backgrounds.

B Proofs of propositions

Batch Elo updates are stable if the matrices of empirical probabilities and predicted probabilities have the same row-sums (or, equivalently the same column-sums):

Player $i$’s weights are updated in one batch after observing win-loss probabilities $\bar{p}_{ij}$ for each player $j=1,\ldots,n$. Observe that

Given matrix ${\mathbf{S}}_{m\times n}$ with rank $r$ and singular value decomposition ${\mathbf{U}}{\mathbf{D}}{\mathbf{V}}^{\intercal}$. Construct antisymmetric matrix

Then the thin Schur decomposition of ${\mathbf{A}}$ is ${\mathbf{Q}}\boldsymbol{\Lambda}{\mathbf{Q}}^{\intercal}$ where the eigenpairs in the $\boldsymbol{\Lambda}_{2r\times 2r}$ are $\pm$ the singular values in ${\mathbf{D}}$ and

Direct computation; multiply out the matrices. ∎

(i) If probabilities ${\mathbf{P}}$ are generated by Elo ratings ${\mathbf{r}}$ then the divergence of its logit is ${\mathbf{r}}$. That is,

(ii) There is an Elo rating that generates probabilities ${\mathbf{P}}$ iff $\operatorname*{curl}(\operatorname*{logit}{\mathbf{P}})=0$. Alternatively, iff $\log\frac{p_{ij}}{p_{ji}}+\log\frac{p_{jk}}{p_{kj}}+\log\frac{p_{ki}}{p_{ik}}=0$ for all $i,j,k$.

For the first claim, apply definitions and recall ${\mathbf{r}}^{\intercal}{\mathbf{1}}=0$. For the second, apply the Hodge decomposition from section 2.2. ∎

The game $\max_{{\mathbf{p}}\in\Delta_{n}}\min_{{\mathbf{q}}\in\Delta_{n}}{\mathbf{p}}^{\intercal}{\mathbf{A}}{\mathbf{q}}$, where ${\mathbf{A}}$ is antisymmetric, has a unique symmetric Nash equilibrium $({\mathbf{p}}^{*},{\mathbf{p}}^{*})$, with greater entropy than any other Nash equilibrium.

The Nash equilibria in a two-player zero-sum are rectangular: if $({\mathbf{p}},{\mathbf{q}})$ and $({\mathbf{u}},{\mathbf{v}})$ are Nash equilibria then so are $({\mathbf{p}},{\mathbf{v}})$ and $({\mathbf{u}},{\mathbf{q}})$. Further, they form a convex polytope. Since ${\mathbf{A}}^{\intercal}=-{\mathbf{A}}$, the set of Nash equilibria is also symmetric: if $({\mathbf{p}},{\mathbf{q}})$ is a Nash equilibrium then so is $({\mathbf{q}},{\mathbf{p}})$. The entropy $H({\mathbf{p}}):=-\sum_{i=1}^{n}p_{i}\log p_{i}$ is strictly concave and therefore achieves a unique maximum on the compact, convex, symmetric set of Nash equilibria. ∎

C Proof of theorem 1

The maxent NE has the following properties:

Invariant: Nash averaging, with respect to the maxent NE, is invariant to redundancies in ${\mathbf{A}}$.

Continuous: If ${\mathbf{p}}^{*}$ is a Nash for $\hat{{\mathbf{A}}}$ and $\epsilon=\|{\mathbf{A}}-\hat{{\mathbf{A}}}\|_{\text{max}}$ then ${\mathbf{p}}^{*}$ is an $\epsilon$-Nash for ${\mathbf{A}}$.

Interpretable: (i) The maxent NE on ${\mathbf{A}}$ is the uniform distribution, ${\mathbf{p}}^{*}=\frac{1}{n}{\mathbf{1}}$, iff the meta-game is cyclic, i.e. $\operatorname*{{div}}({\mathbf{A}})={\mathbf{0}}$. (ii) If the meta-game is transitive, i.e. ${\mathbf{A}}=\operatorname*{grad}({\mathbf{r}})$, then the maxent NE is the uniform distribution on the player(s) with highest rating(s) – there could be a tie.

First, we more precisely formalize invariance to redundancy.

Given antisymmetric matrix ${\mathbf{A}}_{n\times n}$, denote the right-most column by ${\mathbf{a}}_{n}$. Assume the right-most column (and bottom row) of ${\mathbf{A}}$ differs from all other columns. Construct antisymmetric matrix

by adding an additional copy of the right-most column (and bottom row) to ${\mathbf{A}}$. A family of functions

is invariant to adding a row and column according to (24) if

If the copied row is not unique and receives positive mass under maxent Nash, then maxent Nash will already be spreading mass across the copies. In that case, adding yet another copy will result in the maxent Nash on the larger mass spreading mass evenly across all copies.

Suppose ${\mathbf{A}}_{n\times n}$ is antisymmetric with Nash equilibrium ${\mathbf{p}}$. Construct ${\mathbf{A}}^{\prime}$ from ${\mathbf{A}}$ by adding a redundant copy of the right-most column and bottom row according (24). Then

is a Nash equilibrium for ${\mathbf{A}}^{\prime}$ for all $\alpha\in$. Conversely, if ${\mathbf{p}}^{\prime}$ is a Nash equilibrium for ${\mathbf{A}}^{\prime}$ then

is a Nash equilibrium for ${\mathbf{A}}$.

Since the value of the game on ${\mathbf{A}}$ is zero, it follows that ${\mathbf{p}}$ is a Nash equilibrium iff all the coordinates of ${\mathbf{A}}{\mathbf{p}}$ are nonnegative, i.e. ${\mathbf{A}}{\mathbf{p}}\succeq{\mathbf{0}}_{n\times 1}$. Direct computation shows that ${\mathbf{A}}^{\prime}{\mathbf{p}}^{\prime}_{\alpha}\succeq{\mathbf{0}}_{(n+1)\times 1}$, which implies ${\mathbf{p}}^{\prime}_{\alpha}$ is a Nash equilibrium for ${\mathbf{A}}^{\prime}$. The converse follows similarly. ∎

The definition and lemma are stated in the particular case where the last column and row are copied. This is simply for notational convenience. They generalize trivially to copying arbitrary row/columns into arbitrary positions, and can be applied inductively to the cases where ${\mathbf{A}}^{\prime}$ is constructed from ${\mathbf{A}}$ by inserting multiple redundant copies. ∎

C.2 Proof of theorem 1.2

Recall the max-norm on matrices is $\|{\mathbf{S}}\|_{\text{max}}:=\max_{ij}|{\mathbf{S}}_{ij}|$.

A joint strategy $({\mathbf{p}}^{*},{\mathbf{q}}^{*})$ is an $\epsilon$-Nash equilibrium for ${\mathbf{A}}$ if the benefit from either player deviating, separately, is at most $\epsilon$:

Continuous: If ${\mathbf{p}}^{*}$ is a Nash for $\hat{{\mathbf{A}}}$ and $\epsilon=\|{\mathbf{A}}-\hat{{\mathbf{A}}}\|_{\text{max}}$ then ${\mathbf{p}}^{*}$ is an $\epsilon$-Nash for ${\mathbf{A}}$.

Suppose $({\mathbf{p}}^{*},{\mathbf{p}}^{*})$ is a Nash equilibrium for the antisymmetric matrix $\hat{{\mathbf{A}}}$. Observe that

for any distribution ${\mathbf{p}}^{\prime}$ because $({\mathbf{p}}^{*})^{\intercal}{\mathbf{A}}{\mathbf{p}}^{*}=0$ since ${\mathbf{A}}$ is antisymmetric. It follows that

The first term on the right-hand-side is $\leq 0$ since ${\mathbf{p}}^{*}$ is a Nash equilibrium for $\hat{{\mathbf{A}}}$ and the value of the game is zero. The second term on the right-hand-side is $\leq\epsilon$ because $\|{\mathbf{A}}-\hat{{\mathbf{A}}}\|_{\text{max}}\leq\epsilon$ and ${\mathbf{p}}^{\prime}$ and ${\mathbf{p}}^{*}$ are probability distributions. ∎

Note that since $\|{\mathbf{S}}\|_{\text{max}}\leq\|{\mathbf{S}}\|_{2}\leq\|{\mathbf{S}}\|_{F}$ for any ${\mathbf{S}}$, the divergence from Nash is also controlled by how well $\hat{{\mathbf{A}}}$ approximates ${\mathbf{A}}$ in the operator or Frobenius norms.

The proof is adapted from the proof of the following lemma in .

Suppose $({\mathbf{p}}^{*},{\mathbf{q}}^{*})$ is a Nash equilibrium for $\hat{{\mathbf{A}}}$ and that $\epsilon=\|{\mathbf{A}}-\hat{{\mathbf{A}}}\|_{\text{max}}$. Then $({\mathbf{p}}^{*},{\mathbf{q}}^{*})$ is a $2\epsilon$-Nash for ${\mathbf{A}}$.

Our result is slightly sharper because we specialize to antisymmetric matrices.

C.3 Proof of theorem 1.3

(i) If $\operatorname*{{div}}({\mathbf{A}})={\mathbf{0}}$ then $\frac{1}{n}{\mathbf{1}}^{\intercal}{\mathbf{A}}={\mathbf{0}}^{\intercal}$ and ${\mathbf{A}}\frac{1}{n}{\mathbf{1}}={\mathbf{0}}$ implying the uniform distribution is a Nash equilibrium because there is no incentive to deviate from $(\frac{1}{n}{\mathbf{1}},\frac{1}{n}{\mathbf{1}})$. The uniform distribution also has maximum entropy. Conversely, suppose $\operatorname*{{div}}({\mathbf{A}})\neq{\mathbf{0}}$. Then ${\mathbf{1}}^{\intercal}{\mathbf{A}}$ has at least one positive and one negative coordinate because we know ${\mathbf{1}}^{\intercal}{\mathbf{A}}{\mathbf{1}}=0$ by antisymmetry. It follows that if the row player chooses $\frac{1}{n}{\mathbf{1}}^{\intercal}$ then the column player is incentivized to choose a distribution with more mass on the positive coordinate and less on the negative. In other words, the column player will not play the uniform distribution, and the uniform distribution is therefore not a Nash equilibrium.

(ii) By assumption ${\mathbf{A}}=\operatorname*{grad}({\mathbf{r}})={\mathbf{r}}{\mathbf{1}}^{\intercal}-{\mathbf{1}}{\mathbf{r}}^{\intercal}$, so ${\mathbf{p}}^{\intercal}{\mathbf{A}}{\mathbf{q}}={\mathbf{p}}^{\intercal}{\mathbf{r}}-{\mathbf{r}}^{\intercal}{\mathbf{q}}$ decouples into an independent maximization problem with respect to ${\mathbf{p}}$ and minimization problem with respect to ${\mathbf{q}}$. It follows that the optimal distribution ${\mathbf{p}}^{*}$ concentrates mass on the maximal coordinate(s) of ${\mathbf{r}}$ and so does ${\mathbf{q}}^{*}$. That is, to be a Nash equilibrium, ${\mathbf{p}}^{*}$ and ${\mathbf{q}}^{*}$ must place their mass on the maximal coordinate if it is unique and can distribute it arbitrarily over the set of maximal coordinates if there is a tie. Adding the condition that the Nash equilibrium has maximum entropy entails placing the uniform distribution over the maximal coordinate(s). ∎

D Nash averaging for agent-vs-task

Given score matrix ${\mathbf{S}}_{m\times n}$, construct antisymmetric matrix

Note this differs from the antisymmetrization used in section 3.3, see next remark.

The graph structure underlying AvT is bipartite: agents interact with tasks and tasks with agents, but there are no direct agent-agent or task-task interactions. When done in full generality, the definitions of $\operatorname*{{div}}$, $\operatorname*{grad}$ and $\operatorname*{curl}$ take into account the graph structure, see . In particular, $\operatorname*{{div}}$, $\operatorname*{grad}$ and $\operatorname*{curl}$ are computed differently on bipartite graphs than fully connected graphs – note the definitions in section 2.2 are specific to fully connected graphs. Working in full generality is overkill for our purposes. It suffices to introduce slightly ad hoc notation to handle the specific case of AvT.

where $\operatorname*{{{div}_{a}}}({\mathbf{S}})$ measures uniform average skill of agents on tasks and $\operatorname*{{{div}_{e}}}({\mathbf{S}})$ measures uniform average difficulty of tasks for agents. Let

The setup is the same as for AvA in the main text except the row and column meta-players each play two distributions: one on agents and one on tasks/environments. The same argument as in proposition 4 shows there is a unique symmetric maxent Nash equilibrium \Big{(}({\mathbf{p}}_{a}^{*},{\mathbf{p}}_{e}^{*}),({\mathbf{p}}_{a}^{*},{\mathbf{p}}_{e}^{*})\Big{)}.

The maxent Nash evaluation method for AvT is

where ${\mathbf{p}}_{a}^{*}$ and ${\mathbf{p}}_{e}^{*}$ are the maxent Nash equilibria over agents and environments and ${\mathbf{n}}_{e}:=-{\mathbf{S}}^{\intercal}\cdot{\mathbf{p}}^{*}_{a}$ and ${\mathbf{n}}_{a}:={\mathbf{S}}\cdot{\mathbf{p}}^{*}_{e}$ are the Nash averages quantifying difficulty of environments (Nash averaged over agents) and skill of agents (Nash averaged over environments) respectively.

and so the row player maximizes its payoff by putting all its agent-mass on the most skillful agent(s) and all of its environment-mass on the most difficult task(s) – and similarly for the column player.

It is easy to check that the maxent Nash $({\mathbf{p}}_{a}^{*},{\mathbf{p}}_{e}^{*})$ has ${\mathbf{p}}_{a}$ a uniform distribution on all agents iff $\operatorname*{{{div}_{a}}}({\mathbf{S}})={\mathbf{0}}$, and has ${\mathbf{p}}_{e}$ a uniform distribution on tasks iff $\operatorname*{{{div}_{e}}}({\mathbf{S}})={\mathbf{0}}$. We thus obtain

The maxent NE has the following properties:

Invariant: Nash averaging is invariant to redundancies in ${\mathbf{A}}$.

Continuous: If $({\mathbf{p}}_{a}^{*},{\mathbf{p}}_{e}^{*})$ is a Nash for $\hat{{\mathbf{A}}}$ and $\frac{\epsilon}{2}=\|{\mathbf{A}}-\hat{{\mathbf{A}}}\|_{\text{max}}$ then $({\mathbf{p}}_{a}^{*},{\mathbf{p}}_{e}^{*})$ is an $\epsilon$-Nash for ${\mathbf{A}}$.

Interpretable: (i) The agent component of the maxent NE on ${\mathbf{A}}$ is the uniform distribution on agents, ${\mathbf{p}}_{a}^{*}=\frac{1}{n}{\mathbf{1}}$, iff $\operatorname*{{{div}_{a}}}({\mathbf{A}})={\mathbf{0}}$. (ii) The task component of the maxent NE on ${\mathbf{A}}$ is the uniform distribution on tasks, ${\mathbf{p}}_{e}^{*}=\frac{1}{m}{\mathbf{1}}$, iff $\operatorname*{{{div}_{e}}}({\mathbf{A}})={\mathbf{0}}$. (iii) If the meta-game is transitive, i.e. ${\mathbf{A}}=\operatorname*{grad}({\mathbf{s}},{\mathbf{d}})$, then the maxent NE is the uniform distribution on the most skillful agent(s) and the uniform distribution on the most difficult task(s) – there could be ties.

E Code for computing mElo2 updates

The routine $\mathtt{mElo2\_update}$ takes as input: a pair of players $i,j$, the probability $\mathtt{p\_ij}$ of player $\mathtt{i}$ beating player $\mathtt{j}$ (which could be 0 or 1 if only a single match is observed on the given round), the rating vector $\mathtt{r}$ and the $n\times 2$ matrix $\mathtt{c}$ quantifying non-transitive interactions. It returns updates to the $\mathtt{i^{th}}$ and $\mathtt{j^{th}}$ entries of $\mathtt{r}$ and $\mathtt{c}$.

$\mathtt{\texttt{def mElo2\_update}(i,\,j,\,p\_ij,\,r,\,c):}$ $\texttt{}\quad\mathtt{p\_hat\_ij=sigmoid(r[i]-r[j]+c[i,0]*c[j,1]-c[j,0]*c[i,1])}$ $\texttt{}\quad\mathtt{delta=p\_ij-p\_hat\_ij}$ $\texttt{}\quad\mathtt{r\_update=[\,16*delta,\,-16*delta\,]}$ # r has higher learning rate than c $\texttt{}\quad\mathtt{c\_update=[}$ $\texttt{}\quad\quad\mathtt{[\,+delta*c[j,1],\,-delta*c[i,1]\,],}$ $\texttt{}\quad\quad\mathtt{[\,-delta*c[j,0],\,+delta*c[i,0]\,]}$ $\texttt{}\quad\mathtt{]}$ $\texttt{}\quad\mathtt{return\,\,r\_update,\,c\_update}$

F On the geometry of antisymmetric matrices

This section provides some intuition for multidimensional Elo ratings by describing some of the underling geometry.

and ${\mathbf{C}}$ $A$ $B$ $C$ $D$ $A$ 0 1 0 -1 $B$ -1 0 1 0 $C$ 0 -1 0 1 $D$ 1 0 -1 0

Note that ${\mathbf{T}}$ is transitive since ${\mathbf{T}}=\operatorname*{grad}\circ\operatorname*{{div}}({\mathbf{T}})$ and ${\mathbf{C}}$ is cyclic since $\operatorname*{{div}}({\mathbf{C}})={\mathbf{0}}$. Both matrices have rank two, so the thin Schur decomposition can be written

in either case. The matrices ${\mathbf{Q}}^{\mathbf{T}}_{4\times 2}$ and ${\mathbf{Q}}^{\mathbf{C}}_{4\times 2}$ arising from the respective Schur decompositions

can separately be thought of (and plotted) as four two-vectors, see figure 3. The rows of ${\mathbf{Q}}^{\mathbf{T}}_{4\times 2}$ form a straight line, see panel A. More generally, if ${\mathbf{A}}=\operatorname*{grad}({\mathbf{r}})$ and ${\mathbf{r}}$ is not identically zero then ${\mathbf{A}}$ is rank two with thin Schur decomposition ${\mathbf{A}}={\mathbf{Q}}_{n\times 2}\boldsymbol{\Lambda}_{2\times 2}{\mathbf{Q}}^{\intercal}_{2\times n}$, where the rows of ${\mathbf{Q}}$ are points along a line. More precisely, the rows are of the form

The rows of ${\mathbf{Q}}^{\mathbf{C}}_{4\times 2}$ lie on a circle centered at the origin, see panel B. This does not generalize to arbitrary cyclic matrices. However, the geometry of antisymmetric matrices has interesting connections with areas of parallelograms and the complex plane, see next subsection.

F.2 Areas and phases

Alternatively, introduce complex numbers $w=u_{1}+iu_{2}$ and $z=v_{1}+iv_{2}$, where $w=|w|\cdot e^{i\cdot\phi_{w}}$ and $z=|z|\cdot e^{i\cdot\phi_{z}}$ in polar coordinates. Then, (43) can be rewritten

F.3 Comment on Schur and Hodge