# reevaluating_evaluation__27133a80.pdf

Re-evaluating Evaluation

David Balduzzi Karl Tuyls Julien Perolat Thore Graepel

What we observe is not nature itself, but nature exposed to our method of questioning. Werner Heisenberg

Progress in machine learning is measured by careful evaluation on problems of outstanding common interest. However, the proliferation of benchmark suites and environments, adversarial attacks, and other complications has diluted the basic evaluation model by overwhelming researchers with choices. Deliberate or accidental cherry picking is increasingly likely, and designing well-balanced evaluation suites requires increasing effort. In this paper we take a step back and propose Nash averaging. The approach builds on a detailed analysis of the algebraic structure of evaluation in two basic scenarios: agent-vs-agent and agentvs-task. The key strength of Nash averaging is that it automatically adapts to redundancies in evaluation data, so that results are not biased by the incorporation of easy tasks or weak agents. Nash averaging thus encourages maximally inclusive evaluation since there is no harm (computational cost aside) from including all available tasks and agents.

1 Introduction

Evaluation is a key driver of progress in machine learning, with e.g. Image Net [1] and the Arcade Learning Environment [2] enabling subsequent breakthroughs in supervised and reinforcement learning [3,4]. 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 [5], is reaching its limits. Three examples suffice. Adversarial attacks have complicated evaluation, raising questions about which attacks to test against [6 9]. Training agents far beyond human performance with self-play means they can only really be evaluated against each other [10,11]. The desire to build increasingly general-purpose agents has led to a proliferation of environments: Mujoco, DM Lab, Open AI Gym, Psychlab and others [12 15].

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 (Av T), where algorithms are evaluated on suites of datasets or environments; and agent vs agent (Av A), 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 Av A, where the task is (beating) another agent, is especially interesting. Performance in Av A is often quantified using Elo ratings [16] or the closely related True Skill [17]. 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

Deep Mind. Email: { dbalduzzi | karltuyls | perolat | thore }@google.com

32nd Conference on Neural Information Processing Systems (Neur IPS 2018), Montréal, Canada.

like rock-paper-scissors. Intransitivity has been linked to biodiversity in ecology, and may be useful when evolving populations of agents [18 21]. 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 [22]. 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.

1.1 Overview

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 [23]. 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 (m Elo) 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 m Elo on the domain of training an Alpha Go agent [24].

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 [25]. 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.

1.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 [26,27]. Formally, they consider all computable tasks weighted by algorithmic complexity [28 30]. 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 [31 35]. There is a long history of psychometric evaluation in humans, some of which has been applied in artificial intelligence [36 38]. Bradley-Terry models provide a general framework for pairwise comparison [39]. Researchers have recently taken a second look at the arcade learning environment [2] and introduced new performance metrics [40]. However, the approach is quite particular. Recent work using agents to evaluate games has somewhat overlapping motivation with this paper [41 45]. Item response theory is an alternative, and likely complementary, approach to using agents to evaluate tasks [46] that has recently been applied to study the performance of agents on the Arcade Learning Environment [47].

Our approach draws heavily on work applying combinatorial Hodge theory to statistical ranking [48] and game theory [49 51]. We also draw on empirical game theory [52,53], 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 [54 58]. von Neumann winners in the dueling bandit setting and NE-regret are related to Nash averaging [59 62].

2 Preliminaries

Notation. Vectors are column vectors. 0 and 1 denote the constant vectors of zeros and ones respectively. We sometimes use subscripts to indicate dimensions of vectors and matrices, e.g. rn 1 or Sm n and sometimes their entries, e.g. ri or Sij; no confusion should result. The unit vector with a 1 in coordinate i is ei. Proofs and code are in the appendix.

2.1 The Elo rating system

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

ˆpij := 10ri/400

10ri/400 + 10rj/400 = σ( ri rj), where σ(x) = 1 1 + e x and = log(10)

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

Elo(pij, ˆpij) = pij log ˆpij (1 pij) log(1 ˆpij), where ˆpij = σ(ri rj)

and pij is the true probability of i beating j. Suppose the tth match pits player i against j, with outcome St

ij = 1 if i wins and St

ij = 0 if i loses. Online gradient descent on Elo obtains

i rri Elo(St

Choosing learning rate = 16 or 32 recovers the updates introduced by Arpad Elo in [16].

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 ˆpij = 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: pij = P

ij Nij . As the number of matches approaches infinity, the empirical estimates approach the true probabilities pij. Proposition 1. 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 columnsums):

Elo( pij, ˆpij)

5 = 0 8i iff

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.2 Antisymmetric matrices

We recall some basic facts about antisymmetric matrices. Matrix A is antisymmetric if A + A| = 0. Antisymmetric matrices have even rank and imaginary eigenvalues { iλj}rank(A)/2

j=1 . Any antisymmetric matrix A admits a real Schur decomposition:

An n = Qn n n n Q|

n n, where Q is orthogonal and consists of zeros except for (2 2) diagonal-blocks of the form:

The entries of are real numbers, found by multiplying the eigenvalues of A by i = p 1. Proposition 2. Given matrix Sm n with rank r and singular value decomposition Um r Dr r V|

r n. Construct antisymmetric matrix

A(m+n) (m+n) =

0m m Sm n S|

Then the thin Schur decomposition of A is Q(m+n) 2r 2r 2r Q|

2r (m+n) where the nonzero pairs in 2r 2r are the singular values in Dr r and

Q(m+n) 2r =

u1 0m 1 ur 0m 1 0n 1 v1 0n 1 vr

Combinatorial Hodge theory is developed by analogy with differential geometry, see [48 51]. Consider a fully connected graph with vertex set [n] = {1, . . . , n}. Assign a flow Aij 2 R to each edge of the graph. The flow in the opposite direction ji is Aji = Aij, so flows are just (n n) antisymmetric matrices. The flow on a graph is analogous to a vector field on a manifold.

The combinatorial gradient of an n-vector r is the flow: grad(r) := r1| 1r|. Flow A is a gradient flow if A = grad(r) for some r, or equivalently if Aij = ri rj for all i, j. The divergence of a flow is the n-vector div(A) := 1

n A 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 curl(A)ijk = Aij + Ajk Aik. Finally, the rotation is rot(A)ij = 1

k=1 curl(A)ijk. Theorem (Hodge decomposition, [48]). (i) div grad(r) = r for any r satisfying r|1 = 0. (ii) div rot(A) = 0n 1 for any flow A. (iii) rot grad(r) = 0n n for any vector r. (iv) The vector space of antisymmetric matrices admits an orthogonal decomposition )

antisymmetric matrices

= im(grad) im(rot) with respect to the standard inner product h A, Bi = P

ij Aij Bij. Concretely, any antisymmetric matrix decomposes as

transitive component

cyclic component

= grad(r)+rot(A) where r = div(A).

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.

3 On the algebraic structure of evaluation

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

3.1 Agents vs agents (Av A)

In Av A, results are collated into a matrix of win-loss probabilities based on relative frequencies. Construct A = logit P with Aij := log pij 1 pij . Matrix A is antisymmetric since pij + pji = 1.

When can Elo correctly predict win-loss probabilities? The answer is simple in logit space: Proposition 3. (i) If probabilities P are generated by Elo ratings r then the divergence of its logit is r. That is,

if pij = σ(ri rj) 8i, j then div(logit P) =

(ii) There is an Elo rating that generates probabilities P iff curl(logit P) = 0. Equivalently, iff

pji + log pjk

pkj + log pki

pik = 0 for all i, j, k.

Elo is, essentially, a uniform average in logit space. Elo s predictive failures are due to the cyclic component A := rot(logit P) that uniform averaging ignores.

Multidimensional Elo (m Elo2k). 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) Star Craft. Rating systems that can handle intransitive abilities are therefore necessary. An obvious approach is to learn a feature vector w and a rating vector ri per player, and predict ˆpij = σ(r|

j w). Unfortunately, this reduces to the standard Elo rating since r|

i w is a scalar.

Handling intransitive abilities requires learning an approximation to the cyclic component A. Combining the Schur and Hodge decompositions allows to construct low-rank approximations that extend Elo. Note, antisymmetric matrices have even rank. Consider

An n = grad(r) + A grad(r) + C|

C A C =: grad(r) + C|

n 2k 2k 2k C2k n

where the rows of C are orthogonal to each other, to r, and to 1. The larger 2k, the better the approximation. Let m Elo2k assign each player Elo rating ri and 2k-dimensional vector ci. Vanilla Elo uses 2k = 0. The m Elo2k win-loss prediction is

m Elo2k: ˆpij = σ

where 2k 2k =

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

3.2 Application: predicting win-loss probabilities in Go

Elo ratings are widely used in Chess and Go. We compared the predictive capabilities of Elo and the simplest extension m Elo2 on eight Go algorithms taken from extended data table 9 in [24]: seven variants of Alpha Go, and Zen. The Frobenius norms and logistic losses are k P ˆPk F = 0.85 and log = 1.41 for Elo vs the empirical probabilities and k P ˆP2k F = 0.35 and log = 1.27 for m Elo2.

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

Elo v p Zen v - 0.41 0.58 p 0.59 - 0.67 Zen 0.42 0.33 -

empirical v p Zen v - 0.7 0.4 p 0.3 - 1.0 Zen 0.6 0.0 -

m Elo2 v p Zen v - 0.72 0.46 p 0.28 - 0.98 Zen 0.55 0.02 -

3.3 Agents vs tasks (Av T)

In Av T, results are represented as an (m n) matrix S: rows are agents, columns are tasks, entries are scores (e.g. accuracy or total reward). Subtract the total mean, so the sum of all entries of S is zero. We recast both agents and tasks as players and construct an antisymmetric (m+n) (m+n)-matrix. Let s = 1 m S 1m 1 and d = 1

n S| 1n 1 be the average skill of each agent and the average difficulty of each task. Define S = S (s 1| 1 d|). Let r be the concatenation of s and d. We construct the antisymmetric matrix

A(m+n) (m+n) = grad(r) +

0m m Sm n S|

grad(s) Sm n S|

n m grad(d)

The top-right block of 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 Sij = si dj, the agent s skill minus the task s difficulty, for all i, j. Paralleling proposition 3, averages explain the data, S = s1| 1d|, iff curl(A) = 0.

The failure of averages to explain performance is encapsulated in S and A. By proposition 2, the SVD of S and Schur decomposition of A are equivalent. If the SVD is Sm n = Um r Dr r V|

r n then the rows of U represent the latent abilities exhibited by agents and the rows of V represent the latent problems posed by tasks.

4 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.

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

evaluation data

antisymmetric matrices

Desired properties. An evaluation method should be:

P1. Invariant: adding redundant copies of an agent or task to the data should make no difference. P2. Continuous: the evaluation method should be robust to small changes in the data. P3. 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.

4.1 Nash averaging

This section presents an evaluation method satisfying properties P1, P2, P3. We discuss Av A here, see section D for Av T. Given antisymmetric logit matrix A, define a two-player meta-game with payoffs µ1(p, q) = p|Aq and µ2(p, q) = p|Bq for the row and column meta-players, where B = A|. The game is symmetric because B = A| and zero-sum because B = 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 [63,64]. Fortunately, for zero-sum games there is a natural choice of Nash: Proposition 4 (maxent NE). For antisymmetric A there is a unique symmetric Nash equilibrium (p , p ) solving maxp2 n minq2 n p|Aq with greater entropy than any other Nash equilibrium.

Maxent Nash is maximally indifferent between players with the same empirical performance. Definition 2. The maxent Nash evaluation method for Av A is

evaluation data

antisymmetric matrices

maxent NE !

Nash average ! R

A is the maxent Nash equilibrium and n A := A p

A is the Nash average.

Invariance to redundancy is best understood by looking at an example; for details see section C. Example 1 (invariance). Consider two logit matrices, where the second adds a redundant copy of agent C to the first:

A A B C A 0.0 4.6 -4.6 B -4.6 0.0 4.6 C 4.6 -4.6 0.0

A0 A B C1 C2 A 0.0 4.6 -4.6 -4.6 B -4.6 0.0 4.6 4.6 C1 4.6 -4.6 0.0 0.0 C2 4.6 -4.6 0.0 0.0

The maxent Nash for A is p

3). It is easy to check that ( 1

3 ) is Nash for A0 for any 2 [0, 1] and thus the maxent Nash for A0 is p

6). Maxent Nash automatically detects the redundant agents C1, C2 and distributes C s mass over them equally.

Uniform averaging is not invariant to adding redundant agents; concretely div(A) = 0 whereas div(A0) = ( 1.15, 1.15, 0, 0), falsely suggesting agent B is superior. In contrast, n A = 03 1 and n A0 = 04 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. Theorem 1 (main result for Av A2). The maxent NE has the following properties:

2The main result for Av T is analogous, see section D.

NASH PROBABILITY

NASH PROBABILITY

[ left to right ]

centipede asterix private_eye double_dunk montezuma

[ other envs have p = 0 ]

A B [ left to right ]

distrib DQN rainbow human prior popart

[ other agents have p = 0 ]

ENVIRONMENTS Figure 1: (A) The Nash p

a assigned to agents; (B) the Nash p

e assigned to environments.

P1. Invariant: Nash averaging, with respect to the maxent NE, is invariant to redundancies in A.

P2. Continuous: If p is a Nash for ˆA and = k A ˆAkmax then p is an -Nash for A.

P3. Interpretable: (i) The maxent NE on A is the uniform distribution, p = 1

n1, iff the meta-game is cyclic, i.e. div(A) = 0. (ii) If the meta-game is transitive, i.e. A = grad(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 A = grad(r) then the transitive rating is all that matters: Nash averaging measures performance against the best player(s). If div(A) = 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 ˆA is -beatable for nearby A. Unfortunately, Nash equilibria themselves can jump discontinuously when A is modified slightly. Perturbed best response converges to a more stable approximation to Nash [65,66] that unfortunately is not invariant. Example 2 (continuity). Consider the cyclic and transitive logit matrices

0 1 1 1 0 1 1 1 0

0 1 2 1 0 1 2 1 0

The maxent Nash equilibria and Nash averages of C + T are

2 (1, 0, 0) if 1

2 < and n C+ T =

(0, 0, 0) 0 1

2 (0, 1 , 1 2 ) 1 2 <

The maxent Nash is the uniform distribution over agents in the cyclic case ( = 0), and is concentrated on the first player when it dominates the others ( > 1

2). When 0 < < 1

2 the optimal team has most mass on the first and last players. Nash jumps discontinuously at = 1

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

To illustrate the method, we re-evaluate the performance of agents on Atari [2]. Data is taken from results published in [67 70]. 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 S20 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 [0, 1].

We introduce a meta-game where row meta-player picks aims to pick the best distribution p

a on agents and column meta-player aims to pick the hardest distribution 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 [71,72]. 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 1

n S 1 and Nash S p

e averaging over environments; panel B shows the difficulty of environments under uniform 1

m S| 1 and Nash S| 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.

UNIFORM AVERAGE NASH AVERAGE

ENVIRONMENTS

[ left to right ]

centipede asterix private_eye double_dunk montezuma

UNIFORM AVERAGE NASH AVERAGE

[ left to right ]

distrib DQN rainbow human prior popart

Figure 2: Comparison of uniform and Nash averages. (A) Skill of agents by uniform 1

n S 1 and Nash S p

e averaging over environments. (B) Difficulty of environments under uniform 1

m S| 1 and Nash S| p

a averaging over agents. Agents and environments are sorted by Nash-averages.

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.

5 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 1AG) = 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. [73 79]. 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 [10,11], adversarial attacks [6 9], and automated curricula [80]. 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 [81,82]. 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.

[1] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, Imagenet: A large-scale hierarchical image

database, in CVPR, 2009.

[2] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling, The arcade learning environment: An evaluation

platform for general agents, J. Artif. Intell. Res., vol. 47, pp. 253 279, 2013.

[3] A. Krizhevsky, I. Sutskever, and G. E. Hinton, Imagenet classification with deep convolutional neural

networks, in Advances in Neural Information Processing Systems (NIPS), 2012.

[4] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller,

A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, Human-level control through deep reinforcement learning, Nature, vol. 518, pp. 529 533, 02 2015.

[5] D. Donoho, 50 years of Data Science, in Based on a presentation at the Tukey Centennial workshop,

[6] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, Intriguing

properties of neural networks, in ar Xiv:1312.6199, 2013.

[7] F. Tramèr, A. Kurakin, N. Papernot, I. Goodfellow, D. Boneh, and P. Mc Daniel, Ensemble Adversarial

Training: Attacks and Defenses, in ICLR, 2018.

[8] A. Kurakin, I. Goodfellow, S. Bengio, Y. Dong, F. Liao, M. Liang, T. Pang, J. Zhu, X. Hu, C. Xie, J. Wang,

Z. Zhang, Z. Ren, A. Yuille, S. Huang, Y. Zhao, Y. Zhao, Z. Han, J. Long, Y. Berdibekov, T. Akiba, S. Tokui, and M. Abe, Adversarial Attacks and Defences Competition, in ar Xiv:1804.00097, 2018.

[9] J. Uesato, B. O Donoghue, A. van den Oord, and P. Kohli, Adversarial Risk and the Dangers of Evaluating

Against Weak Attacks, in ICML, 2018.

[10] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai,

A. Bolton, Y. Chen, T. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis, Mastering the game of Go without human knowledge, Nature, vol. 550, pp. 354 359, 2017.

[11] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran,

T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis, Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm, in ar Xiv:1712.01815, 2017.

[12] E. Todorov, T. Erez, and Y. Tassa, Mujoco: A physics engine for model-based control, in IROS, 2012.

[13] C. Beattie, J. Z. Leibo, D. Teplyashin, T. Ward, M. Wainwright, H. Küttler, A. Lefrancq, S. Green,

V. Valdés, A. Sadik, J. Schrittwieser, K. Anderson, S. York, M. Cant, A. Cain, A. Bolton, S. Gaffney, H. King, D. Hassabis, S. Legg, and S. Petersen, Deep Mind Lab, in ar Xiv:1612.03801, 2016.

[14] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, Open AI

[15] J. Z. Leibo, C. de Masson d Autume, D. Zoran, D. Amos, C. Beattie, K. Anderson, A. G. Castañeda,

M. Sanchez, S. Green, A. Gruslys, S. Legg, D. Hassabis, and M. M. Botvinick, Psychlab: A Psychology Laboratory for Deep Reinforcement Learning Agents, in ar Xiv:1801.08116, 2018.

[16] A. E. Elo, The Rating of Chess players, Past and Present. Ishi Press International, 1978.

[17] R. Herbrich, T. Minka, and T. Graepel, True Skill: a Bayesian skill rating system, in NIPS, 2007.

[18] M. Frean and E. R. Abraham, Rock-scissors-paper and the survival of the weakest, Proc. R. Soc. Lond. B,

no. 268, pp. 1323 1327, 2001.

[19] B. Kerr, M. A. Riley, M. W. Feldman, and B. J. M. Bohannan, Local dispersal promotes biodiversity in a

real-life game of rock paper scissors, Nature, no. 418, pp. 171 174, 2002.

[20] R. A. Laird and B. S. Schamp, Competitive Intransitivity Promotes Species Coexistence, The American

Naturalist, vol. 168, no. 2, 2006.

[21] A. Szolnoki, M. Mobilia, L.-L. Jiang, B. Szczesny, A. M. Rucklidge, and M. Perc, Cyclic dominance in

evolutionary games: a review, J R Soc Interface, vol. 11, no. 100, 2014.

[22] M. Jaderberg, V. Dalibard, S. Osindero, W. M. Czarnecki, J. Donahue, A. Razavi, O. Vinyals, T. Green,

I. Dunning, K. Simonyan, C. Fernando, and K. Kavukcuoglu, Population based training of neural networks, Co RR, vol. abs/1711.09846, 2017.

[23] D. Balduzzi, S. Racanière, J. Martens, J. Foerster, K. Tuyls, and T. Graepel, The mechanics of n-player

differentiable games, in ICML, 2018.

[24] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser,

I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. P. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, Mastering the game of Go with deep neural networks and tree search, Nature, vol. 529, no. 7587, pp. 484 489, 2016.

[25] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Perolat, D. Silver, and T. Graepel, A

Unified Game-Theoretic Approach to Multiagent Reinforcement Learning, in NIPS, 2017.

[26] S. Legg and M. Hutter, A universal measure of intelligence for artificial agents, in IJCAI, 2005.

[27] S. Legg and J. Veness, An Approximation of the Universal Intelligence Measure, in Algorithmic

Probability and Friends. Bayesian Prediction and Artificial Intelligence, 2013.

[28] R. J. Solomonoff, A formal theory of inductive inference I, II, Inform. Control, vol. 7, no. 1-22, 224-254,

[29] A. N. Kolmogorov, Three approaches to the quantitative definition of information, Problems Inform.

Transmission, vol. 1, no. 1, pp. 1 7, 1965.

[30] G. J. Chaitin, On the length of computer programs for computing finite binary sequences, J Assoc.

Comput. Mach., vol. 13, pp. 547 569, 1966.

[31] C. Ferri, J. Hernández-Orallo, and R. Modroiu, An experimental comparison of performance measures for

classification, Pattern Recognition Letters, no. 30, pp. 27 38, 2009.

[32] J. Hernández-Orallo, P. Flach, and C. Ferri, A Unified View of Performance Metrics: Translating

Threshold Choice into Expected Classification Loss, JMLR, no. 13, pp. 2813 2869, 2012.

[33] J. Hernández-Orallo, The Measure of All Minds: Evaluating Natural and Artificial Intelligence. Cambridge

University Press, 2017.

[34] J. Hernández-Orallo, Evaluation in artificial intelligence: from task-oriented to ability-oriented measure-

ment, Artificial Intelligence Review, vol. 48, no. 3, pp. 397 447, 2017.

[35] R. S. Olson, W. La Cava, P. Orzechowski, R. J. Urbanowicz, and J. H. Moore, PMLB: a large benchmark

suite for machine learning evaluation and comparison, Bio Data Mining, vol. 10, p. 36, Dec 2017.

[36] C. Spearman, General Intelligence, objectively determined and measured, Am. J. Psychol., vol. 15,

no. 201, 1904.

[37] A. Woolley, C. Fabris, A. Pentland, N. Hashmi, and T. Malone, Evidence for a Collective Intelligence

Factor in the Performance of Human Groups, Science, no. 330, pp. 686 688, 2010.

[38] S. Bringsjord, Psychometric artificial intelligence, Journal of Experimental & Theoretical Artificial

Intelligence, vol. 23, no. 3, pp. 271 277, 2011.

[39] D. R. Hunter, MM algorithms for generalized Bradley-Terry models, Annals of Statistics, vol. 32, no. 1,

pp. 384 406, 2004.

[40] M. C. Machado, M. G. Bellemare, E. Talvitie, J. Veness, M. Hausknecht, and M. Bowling, Revisiting the

Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents, Journal of Artificial Intelligence Research (JAIR), vol. 61, pp. 523 562, 2018.

[41] A. Liapis, G. N. Yannakakis, and J. Togelius, Towards a Generic Method of Evaluating Game Levels, in

Artificial Intelligence in Digital Interactive Entertainment (AIIDE), 2013.

[42] B. Horn, S. Dahlskog, N. Shaker, G. Smith, and J. Togelius, A Comparative Evaluation of Procedural

Level Generators in the Mario AI Framework, in Foundations of Digital Games, 2014.

[43] T. S. Nielsen, G. Barros, J. Togelius, and M. J. Nelson, General video game evaluation using relative

algorithm performance profiles, in Evo Applications, 2015.

[44] F. de Mesentier Silva, S. Lee, J. Togelius, and A. Nealen, AI-based Playtesting of Contemporary Board

Games, in Foundations of Digital Games (FDG), 2017.

[45] V. Volz, J. Schrum, J. Liu, S. M. Lucas, A. M. Smith, and S. Risi, Evolving Mario Levels in the Latent

Space of a Deep Convolutional Generative Adversarial Network, in GECCO, 2018.

[46] R. K. Hambleton, H. Swaminathan, and H. J. Rogers, Fundamentals of item response theory. Sage

Publications, 1991.

[47] F. Martínez-Plumed and J. Hernández-Orallo, AI results for the Atari 2600 games: difficulty and

discrimination using IRT, in Workshop on Evaluating General-Purpose AI (EGPAI at IJCAI), 2017.

[48] X. Jiang, L.-H. Lim, Y. Yao, and Y. Ye, Statistical ranking and combinatorial Hodge theory, Math.

Program., Ser. B, vol. 127, pp. 203 244, 2011.

[49] O. Candogan, I. Menache, A. Ozdaglar, and P. A. Parrilo, Flows and Decompositions of Games: Harmonic

and Potential Games, Mathematics of Operations Research, vol. 36, no. 3, pp. 474 503, 2011.

[50] O. Candogan, A. Ozdaglar, and P. A. Parrilo, Near-Potential Games: Geometry and Dynamics, ACM

Trans Econ Comp, vol. 1, no. 2, 2013.

[51] O. Candogan, A. Ozdaglar, and P. A. Parrilo, Dynamics in near-potential games, Games and Economic

Behavior, vol. 82, pp. 66 90, 2013.

[52] W. E. Walsh, D. C. Parkes, and R. Das, Choosing samples to compute heuristic-strategy nash equilibrium,

in Proceedings of the Fifth Workshop on Agent-Mediated Electronic Commerce, 2003.

[53] M. P. Wellman, Methods for empirical game-theoretic analysis, in Proceedings, The Twenty-First

National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, pp. 1552 1556, 2006.

[54] S. Phelps, S. Parsons, and P. Mc Burney, An Evolutionary Game-Theoretic Comparison of Two Double-

Auction Market Designs, in Agent-Mediated Electronic Commerce VI, Theories for and Engineering of Distributed Mechanisms and Systems, AAMAS Workshop, pp. 101 114, 2004.

[55] S. Phelps, K. Cai, P. Mc Burney, J. Niu, S. Parsons, and E. Sklar, Auctions, Evolution, and Multi-agent

Learning, in AAMAS and 7th European Symposium on Adaptive and Learning Agents and Multi-Agent Systems (ALAMAS), pp. 188 210, 2007.

[56] M. Ponsen, K. Tuyls, M. Kaisers, and J. Ramon, An evolutionary game-theoretic analysis of poker

strategies, Entertainment Computing, vol. 1, no. 1, pp. 39 45, 2009.

[57] D. Bloembergen, K. Tuyls, D. Hennes, and M. Kaisers, Evolutionary dynamics of multi-agent learning: A

survey, J. Artif. Intell. Res. (JAIR), vol. 53, pp. 659 697, 2015.

[58] K. Tuyls, J. Perolat, M. Lanctot, J. Z. Leibo, and T. Graepel, A Generalised Method for Empirical Game

Theoretic Analysis , in AAMAS, 2018.

[59] M. Dudik, K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi, Contextual Dueling Bandits, in

COLT, 2015.

[60] A. Balsubramani, Z. Karnin, R. E. Schapire, and M. Zoghi, Instance-dependent Regret Bounds for Dueling

Bandits, in COLT, 2016.

[61] P. R. Jordan, C. Kiekintveld, and M. P. Wellman, Empirical game-theoretic analysis of the TAC supply

chain game, in 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007), Honolulu, Hawaii, USA, May 14-18, 2007, p. 193, 2007.

[62] P. R. Jordan, Practical Strategic Reasoning with Applications in Market Games. Ph D thesis, 2010.

[63] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. Princeton University

Press, Princeton NJ, 1944.

[64] J. F. Nash, Equilibrium Points in n-Person Games, Proc Natl Acad Sci U S A, vol. 36, no. 1, pp. 48 49,

[65] J. Hofbauer and W. H. Sandholm, On the global convergence of stochastic fictitious play, Econometrica,

vol. 70, no. 6, pp. 2265 2294, 2002.

[66] W. H. Sandholm, Population Games and Evolutionary Dynamics. MIT Press, 2010.

[67] Z. Wang, T. Schaul, M. Hessel, H. van Hasselt, M. Lanctot, and N. de Freitas, Dueling Network

Architectures for Deep Reinforcement Learning, in ICML, 2016.

[68] H. van Hasselt, A. Guez, M. Hessel, V. Mnih, and D. Silver, Learning values across many orders of

magnitude, in NIPS, 2016.

[69] G. Ostrovski, M. G. Bellemare, A. van den Oord, and R. Munos, Count-Based Exploration with Neural

Density Models, in ICML, 2017.

[70] M. Hessel, J. Modayil, H. van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar,

and D. Silver, Rainbow: Combining Improvements in Deep Reinforcement Learning, in AAAI, 2018.

[71] L. E. Ortiz, R. E, Schapire, and S. M. Kakade, Maximum entropy correlated equilibrium, in Technical

Report TR-2006-21, CSAIL MIT, 2006.

[72] L. E. Ortiz, R. E. Schapire, and S. M. Kakade, Maximum entropy correlated equilibria, in AISTATS,

[73] P. Diaconis, Group Representations in Probability and Statistics. Institute of Mathematical Statistics, 1988.

[74] Y. Le Cun, , L. Bottou, Y. Bengio, and P. Haffner, Gradient-based learning applied to document recognition,

Proc. IEEE, vol. 86, no. 11, pp. 2278 2324, 1998.

[75] R. Kondor and T. Jebara, A kernel between sets of vectors, in ICML, 2003.

[76] R. Kondor, Group theoretical methods in machine learning, in Ph D dissertation, 2008.

[77] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola, Deep Sets, in

NIPS, 2017.

[78] J. Hartford, D. R. Graham, K. Leyton-Brown, and S. Ravanbakhsh, Deep Models of Interactions Across

Sets, in ICML, 2018.

[79] R. Kondor, Z. Lin, and S. Trivedi, Clebsch Gordan Nets: a Fully Fourier Space Spherical Convolutional

Neural Network, in NIPS, 2018.

[80] S. Sukhbaatar, Z. Lin, I. Kostrikov, G. Synnaeve, A. Szlam, and R. Fergus, Intrinsic Motivation and

Automatic Curricula via Asymmetric Self-Play, in ICLR, 2017.

[81] Y. Freund and R. E. Schapire, A Decision-Theoretic Generalization of On-Line Learning and an Applica-

tion to Boosting, Journal of Computer and System Sciences, 1996.

[82] R. Schapire and Y. Freund, Boosting: Foundations and Algorithms. MIT Press, 2012.

[83] R. J. Vandenberg and C. E. Lance, A Review and Synthesis of the Measurement Invariance Literature:

Suggestions, Practices, and Recommendations for Organizational Research, Organizational Research Methods, vol. 3, no. 1, pp. 4 70, 2000.