summaries: This paper considers causal inference in the discrete case, where probability axioms can be represented with matrix equations. Specifically, the paper characterizes the relationships between certain graphically driven formulae and matrix multiplications. With such characterizations, the authors then broaden the spectrum of proxy variable-based identification conditions and further propose novel intermediary criteria based on the pseudoinverse of a matrix.

summaries: This paper presents a synthesis between literatures on using matrix equations to characterize causal effect identifiability, and using proxies/surrogates to obtain identifiability when the effect of interest is not identifiable using the canonical ID algorithm. The authors highlight examples of identifiability under the various identification paradigms. They then describe notation used for their synthesis and highlight how it applies to each of the known cases. The main results entail an algorithm for determining identification of a broad class of effects via the matrix equations paradigm. The authors show that some key existing results, which had been proven sound, are not complete and show that their approach, while not yet proven complete, generalizes the existing approaches for the literatures studied.

summaries: Two primary methods exist for graph based identification. The first relies only on the assumptions in the graph while the second exploits assumptions  between unobserved confounders and the observable variables via proxy variables. This paper develops a new approach by combining both these methods. The new approach thus developed is able to solve problems that are not solvable by any of the methods alone.

summaries: This paper considers the causal effect identification problem, and proposes an approach making use of both graphical criteria and matrix equations. More precisely, the authors connect the graphical and matrical approaches by characterizing matrix equations of probability distributions driven by graphical constraints in a causal graph. Building on this new characterization, the authors generalize proxy-based criteria and devise novel intermediary pseudoinverse criteria so as to identify a causal effect by utilizing the general inverse of a matrix and diverse collection of distributions.

summaries: This paper provides a graphical identification approach that combines both graphical and matrical approaches. In particular, they apply certain matrix chain-rule and inversion criteria, previously used in for example certain proxy-based approaches, to a matrix version of the C-factorization to arrive at a new causal effect identification algorithm. They show that their algorithm applies to cases that could not be identified with certain previous algorithms and thereby rendering them incomplete.

abstractText: Causal effect identification is concerned with determining whether a causal effect is computable from a combination of qualitative assumptions about the underlying system (e.g., a causal graph) and distributions collected from this system. Many identification algorithms exclusively rely on graphical criteria made of a non-trivial combination of probability axioms, do-calculus, and refined c-factorization (e.g., Lee & Bareinboim, 2020). In a sequence of increasingly sophisticated results, it has been shown how proxy variables can be used to identify certain effects that would not be otherwise recoverable in challenging scenarios through solving matrix equations (e.g., Kuroki & Pearl, 2014; Miao et al., 2018). In this paper, we develop a new causal identification algorithm which utilizes both graphical criteria and matrix equations. Specifically, we first characterize the relationships between certain graphically-driven formulae and matrix multiplications. With such characterizations, we broaden the spectrum of proxy variable based identification conditions and further propose novel intermediary criteria based on the pseudoinverse of a matrix. Finally, we devise a causal effect identification algorithm, which accepts as input a collection of marginal, conditional, and interventional distributions, integrating enriched matrix-based criteria into a graphical identification approach.

authors:
S. Banerjee
A. Roy

title: Linear Algebra and Matrix Analysis for Statistics

venue: Boca Raton: Taylor & Francis

authors:
E. Bareinboim
J. Pearl

title: Causal inference by surrogate experiments: z-identifiability

venue: N. de Freitas and K. Murphy, editors, Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 113–120, Corvallis, OR

title: Causal inference and the data-fusion problem

venue: Proceedings of the National Academy of Sciences, 113:7345–7352

authors:
E. Bareinboim
J. Tian

title: Recovering causal effects from selection bias

venue: S. Koenig and B. Bonet, editors, Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 3475–3481, Palo Alto, CA

authors:
R. Carroll
D. Ruppert
L. Stefanski
C. Crainiceanu

title: Measurement Error in Nonlinear Models: A Modern Perspective

venue: Boca Raton: Chapman & Hall/CRC, 2nd edition

authors:
O. Dukes
I. Shpitser

title: and E

venue: J. T. Tchetgen. Proximal mediation analysis

authors:
D. Geiger
T. Verma
J. Pearl

title: Identifying independence in Bayesian networks

venue: Networks, volume 20, pages 507–534. John Wiley, Sussex, England

authors:
S. Greenland
T. Lash

title: Bias analysis

venue: K. Rothman, S. Greenland, and T. Lash, editors, Modern Epidemiology, pages 345–380. Lippincott Williams & Wilkins, Philadelphia, PA, 3rd edition

authors:
Y. Huang
M. Valtorta

title: Pearl’s calculus of intervention is complete

venue: R. Dechter and T. Richardson, editors, Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence

authors:
M. Kuroki
J. Pearl

title: Measurement bias and effect restoration in causal inference

venue: Biometrika, 101:423–437

authors:
J.J.R. Lee
I. Shpitser

title: Identification methods with arbitrary interventional distributions as inputs, 2020

authors:
S. Lee
E. Bareinboim

title: Causal effect identifiability under partial-observability

venue: Proceedings of the 37th International Conference on Machine Learning, volume 119. PMLR

title: Causal identification with matrix equations

venue: Technical Report R-70, Columbia Causal Artificial Intelligence Lab, Department of Computer Science, Columbia University

authors:
S. Lee
J.D. Correa
E. Bareinboim

title: General identifiability with arbitrary surrogate experiments

venue: Proceedings of the Thirty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence, Corvallis, OR

authors:
W. Miao
Z. Geng
E.J. Tchetgen Tchetgen

title: Identifying causal effects with proxy variables of an unmeasured confounder

title: Generalized inverses

venue: normal solvability, and iteration for singular operator equations. In L. B. Rall, editor, Nonlinear Functional Analysis and Applications, pages 311 – 359. Academic Press

title: Probabilistic Reasoning in Intelligent Systems

venue: Morgan Kaufmann, San Mateo, CA

title: Causal diagrams for empirical research

title: Causality: Models

venue: Reasoning, and Inference. Cambridge University Press, New York

authors:
J. Pearl
D. Mackenzie

title: The Book of Why: The New Science of Cause and Effect

venue: Basic Books

title: Appendum to “on the validity of covariate adjustment for estimating causal effects

authors:
I. Shpitser
J. Pearl

title: Identification of joint interventional distributions in recursive semi- Markovian causal models

venue: Proceedings of The Twenty-First National Conference on Artificial Intelligence, pages 1219–1226. AAAI Press

venue: Proceedings of the Twenty-First National Conference on Artificial Intelligence

authors:
I. Shpitser
T. VanderWeele
J. Robins

title: On the validity of covariate adjustment for estimating causal effects

venue: Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pages 527–536. AUAI, Corvallis, OR

authors:
I. Shpitser
Z. Wood-Doughty

title: and E

venue: J. T. Tchetgen. The proximal id algorithm

authors:
P. Spirtes
C.N. Glymour
R. Scheines

title: Causation

venue: prediction, and search. MIT press

authors:
E.J.T. Tchetgen
A. Ying
Y. Cui
X. Shi

title: and W

venue: Miao. An introduction to proximal causal learning

title: Studies in Causal Reasoning and Learning

venue: PhD thesis, Computer Science Department,

authors:
J. Tian
J. Pearl

title: A general identification condition for causal effects

venue: Proceedings of the Eighteenth National Conference on Artificial Intelligence

authors:
T. Verma
J. Pearl

title: Causal networks: Semantics and expressiveness

venue: Proceedings of the Fourth Workshop on Uncertainty in Artificial Intelligence, pages 352–359, Mountain View, CA

title: Equivalence and synthesis of causal models

venue: Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence

authors:
Y. Wang
D.M. Blei

title: The blessings of multiple causes

venue: Journal of the American Statistical Association, 114(528):1574–1596

authors:
A. Ying
W. Miao
X. Shi

title: and E

venue: J. T. Tchetgen. Proximal causal inference for complex longitudinal studies

heading: 1 Introduction

text:
Cause and effect relations are one of the most common types of knowledge sought after throughout the empirical sciences. These relations are one of the main ingredients in the construction of stable explanations, and usually underpin robust and generalizable decision-making strategies [19, 26]. There is a growing literature that aims to systematically find causal relations by fusing observations, experiments, and substantive knowledge about the phenomenon under investigation [19, 3, 20]. Formally, the inferential target usually appears as the effect of a set of variables do(X = x) on another set of variables Y, which is written as P (y|do(x)) or Px(y). Assumptions about the underlying data-generating processes are commonly expressed as a causal graph G over endogenous variables V. There are different lines of investigation that aims to establish the quantity Px(y).
First, one line of investigation attempts to exploit the non-parametric constraints encoded in G to determine whether the quantity Px(y) (i.e., query) is uniquely computable from the different available distributions. For instance, Pearl’s celebrated method known as do-calculus provides a symbolic way of determining whether a query can be identified from G and observational data P (V) [18]. A number of necessary and sufficient conditions were developed for systematically determining the identifiability status of the query from observational data [18, 29, 23, 9]. For example, the causal effect Px(y) in Fig. 1a is identified by a back-door criterion as Px(y) = P u P (y|x,u)P (u). Further methods were developed to identify the query from a combination of observational and experimental distributions [2, 14, 12, 11]. The key ideas behind these methods are (i) to decompose the given causal query into standard factors (following Tian’s c-factorization, [29]), leveraging the graphical
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
constraints, and (ii) to identify these factors individually, matching one of the available distributions. We call this the factorization-based approach.
Another line of investigation attempts to exploit assumptions about the relationship between unobserved confounders and the observable variables through the idea of proxy variables [5, 8, 10, 15, 32]. These methods rely on the cardinality and complexity of these relationships, which will possibly lead to the invertibility of certain matrices. The focus is usually on local conditions involving the treatment X , the outcome Y , and the proxies W ,Z for the set of unobserved confounders U ; for example, see Fig. 1b. Note that since U is unobserved, the effect of X on Y , i.e., Px(y), is provably not identifiable by standard graphical methods discussed earlier. Still, if the distribution of the proxy given the unobserved confounder is available P (W |U), in addition to P (X,Y ,W ), the quantity Px(y) can be computed under the invertibility of P(W |U), a matrix representation of P (W |U) where P(W |U)i,j = P (wi|uj) (see Eq. (3) for detail). In case of Fig. 1c, the causal effect Px(y) is identified from P (X,Y ,W ,Z) through the following,1
Px(y) = P(y|Z,x)P(W |Z,x) 1P(W ), (1)
where P(W |Z,x) has rank matching the size of domain of the unmeasured confounder U . Although typically not framed in terms of identification with multiple datasets, this setting corresponds to identifying Px(y) with, e.g., marginal distributions {P (X,Y ,Z),P (W ,X,Z)} or conditional distributions {P (Y |Z,x),P (W |Z,x),P (W )}. We call this the proxy approach.2
Despite all the power and successes achieved by the factorization and proxy approaches, there exist still interesting cases not covered by any of them individually. To witness, consider the causal graph in Fig. 1d and first notice that the effect is not identified from each approach. On the other hand, if we combine both approaches, we are able to obtain the causal effect is identifiable and given by,
Px(y) = P t Px(t, y) = P t Pt,x1(y)Px2(t)
= P
t
⇥ P(y|Z1,x1, t)P(W1|Z1,x1, t) 1P(W1) ⇤⇥ P(t|Z2,x2)P(W2|Z2,x2) 1P(W2) ⇤ ,
where Pt,x1(y) and Px2(t), the two factors of the query, are individually identified with the help of the proxy approach, i.e., Eq. (1).
Our goal in this paper is to explicate how this can be accomplished from first principles. More broadly, we will develop a flexible and general graphical identification approach that combines both the factorization and matrix equations (the underpinning idea of proxy-based methods). More specifically, our contributions are as follows:
1. We connect the graphical and matrical approaches by characterizing matrix equations of probability distributions driven by graphical constraints in a causal graph. This leads to a better understanding of the identification through solving systems of equations.
2. Building on this new characterization, we generalize proxy-based criteria and devise novel intermediary pseudoinverse criteria so as to identify a causal effect by utilizing the general inverse of a matrix and diverse collection of distributions.
1We focus on discrete variables. Detailed discussion on a continuous case can be found in [15]. We refer this identification condition MGT criterion where the acronym MGT comes from the surnames of the authors in [15].
2Recent work in this line of research use the term proximal causal inference (PCI) [25, 27, 33, 6]. [27] generalizes the results in [15] to allow observed confounders as well. [25] considered combining graphical and proximal approaches, similar to the motivational example.
3. We develop a general identification algorithm that amalgamates graphical and matrical approaches, returning an identification formula for a causal query given a causal diagram and a set of marginal, experimental, and conditional distributions. We show that this method subsumes current state of the art in the literature.

heading: 2 Preliminaries

text:
We follow notational conventions from literature on causal inference. We denote a variable by an upper case letter Y , and its value is denoted by its corresponding lower case letter y in the domain XY . A set of variables will be denoted by a bold capital letter Y with its value y. We may use [̇, instead of [, to emphasize the union of two disjoint sets. Given Z ✓W, w\Z denotes the value of W\Z consistent with w. Let a/B = (A \B,a\B) which retains B as a set of variables and values of a excluding B. Without loss of generality, we refer PZ(V0|W) a distribution. We may employ conditional to emphasize W ◆ ;, experimental or interventional Z ◆ ; compared to observational Z = ;, and marginal if Z [W [V0 ( V. We employ structural causal models (SCMs) [19, Ch. 7] as the semantical framework to represent a domain of interest. An SCM M is a quadruple hU,V,P (U),Fi. A set of exogenous variables U, which follows P (U), is determined by factors outside the model. V is a set of endogenous variables whose values are determined by functions F = {fi}Vi2V such that Vi fi(pai,ui) where PAi ✓ V\{Vi} and Ui ✓ U. Further, do(x) represents the operation of holding a set X to a constant x regardless of their original mechanisms. Such intervention induces a submodel Mx, which is M with fX replaced to x for X 2 X. The distribution over V induced by the submodel is denoted by Px(V). We may employ letter Q to denote an interventional distribution, e.g., Q = Pr.
Each SCM (model, for short) induces a causal diagram (or causal graph) G = hV,Ei, where each type of edge represents a different causal relationship among the variables: (i) X!Y if X is used as an argument of fY ; and (ii) X$Y if UX and UY are correlated. Given a causal diagram G, familial relationships among its vertices are denoted by pa and an for parents and ancestors, respectively. Further, An is a set of ancestors including its argument as well. We denote by GXZ an edge subgraph of G which removes edges incoming to X and outgoing from Z. Causal relationships among other variables are captured in G\X, which is the subgraph of G over V\X. A vertex induced subgraph is denoted by G[V0] where V0 ✓ V. Causal effect identification relies heavily on standard graphical constraints imposed by a causal diagram such as d-separation (reading off conditional independence from the graph, [30, 7]) and do-calculus (equivalence among interventional probabilities) [18], which we present in the Appendix for completeness.
The latent projection (or projection, for short) of a causal diagram is a causal diagram retaining the causal relationships among a subset of variables. We denote by GhV0i the latent projection of G onto V0 ✓ V, the causal graph over V0 [31]. Conditional independence (CI) statements and do-calculus [18] on a projection are valid in G, vice versa. We formally define a latent projection in the supplementary material. The omitted proofs and derivations are also provided in [13].

heading: 3 Characterization of Matrix Equations of Graphical Constraints

text:
In this section, we present characterizations of graphical constraints in a given causal diagram G, leading to equations expressed as the multiplication of matrices. The characterizations will further advance our understanding on the constraints imposed over the distributions generated by the underlying system compared to simple equivalence relationships such as conditional independence and do-calculus. To begin with, we denote by P the matrix representation of a distribution P where free outcome variables are rows and free condition or intervention variables correspond to columns. For instance, Pa,B(C, d) is a |XC |⇥ |XB | matrix and Pr(A, b|C, d) is a |XA|⇥ |XC | matrix. Further, we may use 0 and 00 to represent two disjoint subsets such that B = B0 [̇ B00.
Chain Rule with Conditional Independence The definitions of conditional and marginal distributions naturally lead to a sum of a product of probabilities. Let Q = Pr be an arbitrary interventional distribution. Let A, B, C, and R be disjoint. A marginal probability over chain-rule-induced multi-
plication is expressed as
Q(a,b0|c) = X
b00
Q(a|b, c)Q(b|c) = Q(a|b0,B00, c)Q(B00,b0|c).
Considering conditional independence, we can further enrich such a characterization. Lemma 1. Given a causal diagram G, let Q = Pr for some r 2 XR where R ( V. Let A,B,C,D,E be disjoint subsets of V\R. If (D ? A | B,C,E) and (E ? B | C,D) in G\R, then, Q(A,b0|c,D, e) = Q(A|b0,B00, c, e)Q(B00,b0|c,D).
The lemma emphasizes the condition under which the result of multiplication is a matrix not just a row or column. A special case of the lemma is appeared in MGT criterion where the inverse of a matrix multiplication P(W |Z,x) = P(W |U ,x)P(U |Z,x) is utilized so as to cancel out an unknown distribution P(W |U) = P(W |U ,x).
Adjustment Criterion Given a graph G and a causal effect of interest Px(y), the adjustment criterion [24] seeks a set of covariates Z ✓ V\X\Y, called an adjustment set for a causal effect Px(y), which grants the following expression, Px(y) = P z P (y|x, z)P (z). Adjustment criterion generalizes back-door criterion [19]. Its matricized expression with employing Q = Pr is
Qx(y) = X
z
Q(y|x, z)Q(z) = Q(y|x,Z)Q(Z).
This simple expression plays a central role in the identification with proxy variables.
In many settings, the left hand side (LHS) is the query of interest and two terms in the RHS are usually available or to be inferred using other available quantities. However, substituting value y with Y, we can further yield (under invertibility assumption) Q(Z) = Q(Y|x,Z) 1Qx(Y), which restores the covariate distribution of interest given a causal effect and conditional distribution.
C-Factorization C-factorization [28] decomposes a causal effect Px(y) into the sum-product of c-factors (simply, factors) with respect to the given causal diagram G. Without loss of generality, let X be minimal such that no X0 ( X satisfies Px0(y) 6= Px(y) (i.e., overriding X by anGX(Y) \X). For any projection H of G that preserves X [Y, the following holds:
Px(y) = X
y+\y
Px(y +) =
X
y+\y
Y
Yi2C(H[Y+])
PpaH(yi)\yi(yi), (2)
where Y+ = AnHX(Y) and C(·) is the c-component decomposition (partitioning the variables in the graph based on their connectivity through bidirected edges). Given a query Px(y), we let c-factors FH = {hXi,Yii}i where {Yi}i form the c-component decomposition of H[Y+] and Xi = paH(Yi)\Yi. The general identification method under partial-observability [12] can be summarily described as finding H such that each factor is identified by one of the available distributions.
Let us denote Xij = Xi [ Xj . We focus here on the sum-product of a pair of factors at some latent projection H, which satisfies Pxi(yi)Pxj (yj) = Pxij\yij (yij) where the values are consistent [12]. Now consider the summation over Z ✓ Xi\Yj . Then, X
z
Pxi\z,z(yi)Pxj (yj\z, z) = Pxij\yij (yij\Z).
To properly represent this as a matrix multiplication, we should decide which variables will become rows and columns. Two matrices to be multiplied should share only Z, and other common variables, appearing in the
two terms, or non-matching variables, appearing as intervention in left term and outcome in right term, need to be set to constants. To help understand, we illustrate in Fig. 2a the set relationships among Xi, Yi, Xj , and Yj in the case of Z = Xi \Yj .
Therefore, Yi\Xj (the shared variables other than Z) and (Xi[Yj)\Z (the non-matching variables) are fixed. These fixed variables are not colored in Fig. 2a. As a result, we can obtain a submatrix of PXij\Yij (Yij\Z) as the multiplication of the submatrices of PXi(Yi) and PXj (Yj) obtained via fixing variables.
Lemma 2 (Matrix Equation of C-Factorization with Two Factors). Given a causal diagram G and an experimental distribution Q = Pr where a causal effect is c-factorized as Qx(y) =P
z Qxi(yi)Qxj (yj) in a projection H of G\R, the effect can be represented as a matrix multiplication, if Z ✓ Xi \Yj . Further, the corresponding matrix equation is
Q(xij\yij)/(Xj\Xi\Yi)((yij\Z)/(Yi\Xj)) = Qxi/Z(yi/(Yi\Xj))Qxj/(Xj\Xi\Yi)(yj/Z).
We illustrate a causal graph in Fig. 2b where each variable matches to each region in the Euler diagram (Fig. 2a). With Z = {6} and for an arbitrary instantiation of variables V2, V4, V5, and V7, PV3,v4,v5(V1, v2, v7) = Pv4,v5,V6(V1, v2)Pv2,V3,v4(V6, v7).
In this section, we connected different graphical constraints—from chain-rule with conditional independence to c-factorization—induced identification formulae to matrix equations. Results presented in this section are by no means complete yet cover, to the best of our knowledge, every sum-product expression appeared in both graphical and matrical identification approaches. Nevertheless, this suite of characterizations will provide a fundamental understanding of the mathematical structures involved in the identification methods with matrical expressions.
4 Generalized Proxy-based Criteria
Equipped with the characterization from the previous section, we revisit single- and double-proxy settings [5, 8, 10, 15] more formally, which identify a causal effect through the combination of chain rule, adjustment criterion (c-factorization), and inverses of matrices given an observational distribution and additional external study involving an unobserved confounder. We investigate its extension capable of utilizing other types of available distributions. Results presented in this section is crucial in adopting matrical approaches into a factorization-based identification algorithm.
Single-Proxy Setting We illustrate in Fig. 4 the available distributions and unknown distributions, considered in Fig. 1b, that can lead to Px(y). In the figure, a matrix multiplication A = B · C is represented as B L!A R C
with positions annotated. First, note that (X,Y ? W | U) in a causal graph G is central, which grants P (W |U ,x, y) = P (W |U ,x) = P (W |U). If P(W |U) is invertible,3 the three distributions P(y,U |x), P(U |x), and P(U) are obtained where P(y|U ,x) is computed by chain rule (Lemma 1). Then, Px(y) is, with ↵ denoting elementwise division,
P(y|U ,x)z }| { (P(W |U) 1P(y,W |x))| {z }
P(y,U |x)
↵ (P(W |U) 1P(W |x))| {z } P(U |x) > P(W |U) 1P(W )| {z } P(U) . (3)
However, this scheme would not work in more restrictive conditions such as Fig. 3a or 3b. This challenging scenario can be handled if a different external study is available altogether with a surrogate
3In case of W has more categorical values than U , one can coarsen W to W 0 ensuring that P(W 0|U) is full rank. In other words, P(W |U) has full column rank.
experiment. For example, when only Y is independent to W given U and X , the availability of an external study P (W |U ,x), instead of P (W |U), and a surrogate experiment Px(W ), in addition to the observational distribution P (Y ,W ,X), suffices to identify the causal effect (see [13]for the derivations for Fig. 3a, 3b). These examples suggest that we can generalize the single proxy-based criterion to take advantage of a diverse collection of external studies and surrogate experiments. Theorem 1. Given G, let X, Y, W, U, and R be disjoint subsets of V, Q = Pr for some r 2 XR, and H = G\R. A causal effect Pr,x(y) = Qx(y) is identifiable if (1) U is an adjustment admissible set for Qx(y) in H; (2a) (Y ? W | U,X)H and Q(W|U,x), Q(y,W|x) and Q(W|x) are available where Q(W|U,x) has full column rank; or (2b) (Y 6? W | U,X)H and Q(W|U,x,Y) and Q(Y,W|x) are available where every Q(W|U,x,y0) has full column rank for y0 2 XY; (3) Qz0(W) is available for Z ✓ X [Y and Z0 = (X [Y)\Z with z0 consistent with x [ y such that (Z ? W | U,Z0) in H; and U is an adjustment admissible set for Qz0(W) in H.
The theorem presents a sound condition to elicit the causal effect through combining various distributions especially when the given situation is more restrictive.
Double-Proxy Setting We now generalize MGT criterion to utilize distributions other than the originally considered observational study. MGT criterion for a double-proxy setting relies on the following conditions to identify Px(y) with P (X,Y ,Z,W ):
(C1) U is an adjustment set for Px(y) in G; (C2) Y ? Z | U ,X in G; (C3) Z,X ? W | U in G; and (C4) P(W |Z,x) has rank |XU |.
Under these conditions, algebraic relationships between a causal effect Px(y) and other distributions can be illustrated as in Fig. 5a where the distributions form a closed loop alternating between (i) distributions with an unmeasured confounder and (ii) given distributions and a query. Among the four multipli-
cations, Px(y) corresponds to an adjustment criterion (C1) so as to Px(y) = P(y|U ,x)P(U). Others are due to the chain-rule combined with CI, e.g., (C2) P(y|U ,x) = P(y|U ,x, z) and (C3) P(W |U) = P(W |U ,x, z). With (C4), which implies that both P(W |U) and P(U |Z,x) are invertible under coarsening of W and Z if necessary [15, 1], the causal effect Px(y) can be expressed as Eq. (1) by subsequently rewriting P(U |Z,x) and P(y|U ,x), and contracting P(W ) = P(W |U)P(U) (see [13] Appendix C for an illustration).
To examine the possible extension of the setting, we relax (C3), where the CI grants the use of matrix multiplication leading to a chain-rule P(W ) = P(W |U)P(U) and P(W |Z,x) = P(W |U)P(U |Z,x). One can consider three relaxed versions of (C3), namely, (Z ? W | U ,X), (X ? W | U ,Z), and, ultimately, dropping (C3) illustrated respectively in Fig. 3c, 3d and 3e. For concreteness, consider the first relaxation (Z ? W | U ,X). The assumption grants P(W |U ,Z,x)=P(W |U ,x). Given that a surrogate experiment Px(W ) is accessible, and it can be decomposed as Px(W ) = P(W |U ,x)P(U) where U is also an adjustment admissible set for Px(w), then, Px(y) is identified. Other two relaxations turned out to be much more challenging, yet the causal effect can be identified by exploiting different surrogate experiments or additional external study (see [13] Appendix C for detail). Motivated by these examples, we present a theorem that extends MGT criterion with varying degrees of the assumption and data collection. Theorem 2 (Generalized MGT Criterion). Given a causal graph G, let X,Y,Z,W,U,R ⇢ V be disjoint sets of variables where R can be empty. Let Q = Pr for some r 2 XR and H = G\R. Let S ✓ X[Z. A causal effect Qx(y) = Px,r(y) is identifiable in G if, for some z, (1) U is an adjustment set for Qx(y) in H; (2) (Y ? Z | U,X)H; (3) (W ? S0 | U,S)H where S0 = (X [ Z)\S; (4) U is an adjustment set for Qs0(W) in H; (5) Q(W|U, s0) is invertible; (6) Q(U|z/(S [ Z0),x) is invertible for some Z0 ✓ Z\S and Q(y|z/(S [ Z0),x), Q(W|z/(S [ Z0),x), and Qs0(W) are available. Additionally, Q(W|U, s0/Z0) is available if Z0 6= ;.
The theorem broadens the applicability of the MGT criterion as an identification template to a range of collection of distributions. Although the conditions involved in generalizing MGT criterion non-trivial, we can similarly draw a (simplified) big picture of the generalized criterion as in Fig. 5b. The key idea is relaxing the C3 condition for a set of variables while considering sets of variables (explicitly) and interventional distributions.
We have established generalized identification criteria exploiting proxy variables.4 The purpose of both criteria aligns well with the philosophy of general identification [14, 12] so that they can be smoothly integrated into graphical approaches.

heading: 5 Pseudoinverse and Intermediary Criteria

text:
Now, we present a novel identification condition for a challenging setting that neither previous matrical nor graphical approaches could handle. In the setting, the probability of interest is expressed as the multiplication of three matrices and is identifiable through employing the pseudoinverse of a matrix, without an invertibility assumption. Let P(·)† denote the pseudoinverse of P(·).5
Lemma 3 (Base Intermediary Criterion). Let {P1,P2,P3,P4} be distributions. Let {Pi}4i=1 be their matrix representations. If submatrices {P0i} 4 i=1 of {Pi} 4 i=1 satisfy P 0 1 = P 0 2P 0 3P 0 4 and P 0 2P 0 3, P 0 3P 0 4, and P03 are given, then, P 0 1 = (P 0 2P 0 3)P 0 3 †(P03P 0 4).
Proof. By the given condition, the associativity of matrix multiplications, and the property of pseudoinverse PP†P = P, P01 = P 0 2P 0 3P 0 4 = P 0 2(P 0 3P 0 3 †P03)P 0 4 = (P 0 2P 0 3)P 0 3 †(P03P 0 4).
Although the lemma itself is rather general, we concretely characterize distributions satisfying Lemma 3 with respect to chain-rule (Sec. 5.1) and c-factorization (Sec. 5.2).
5.1 Chain-Rule-based Intermediary Criterion
We start by characterizing an intermediary criterion with a chain-rule using a simple illustrative example. Let Q be an arbitrary interventional distribution. One way to decompose Q(a, b, c|d) into three probabilities is Q(a|b, c, d)Q(b|c, d)Q(c|d). Let a probability of interest be its marginal Q(a|d) = P b,c Q(a, b, c|d) where the following distributions are available: Q(B|C, d), Q(A|C, d), and Q(B|d). If the first term Q(a|b, c, d) is equal to Q(a|b, d), the term can be multiplied by Q(b|d) = P c Q(b|c, d)Q(c|d). Hence, the matricized expression becomes,
Q(A|d) = Q(A|C,d)z }| { Q(A|B, d)Q(B|C, d)Q(C|d)| {z }
Q(B|d)
= Q(A|C, d)Q(B|C, d)†Q(B|d).
for any d 2 XD. Two illustrative examples where this expression is applicable (i.e., (C ? A | B,D) in G) are shown in Fig. 6. Now, we propose a chain-rule intermediary criterion. Lemma 4 (Chain-Rule Intermediary Criterion). Given a causal diagram G, let A, B, C, D, and R be disjoint subsets of V with D and R can be empty. Let B = B0 [̇ B00 and C = C0 [̇ C00 where B0 and C0 are not empty. Given an interventional distribution Q = Pr, if (C0 ? A | B,C00D) in G\R and Q(a,b00, c00|d) = P b0,c0 Q(a|b, c,d)Q(b|c,d)Q(c|d), then,
Q(A,b00, c00|d) = Q(A,b00|C0, c00,d) ·Q(B0,b00|C0, c00,d)† ·Q(B0,b00, c00|d). 4As mentioned earlier, [27] extends the MGT criterion by allowing observed confounders C. Roughly, this can be understood as replacing U in Fig. 5a with U and C where C is not necessarily marginalized out so that the resulting distribution may contain C.
5In case of continuous variables, P(B|A) can be understood as a linear operator on Hilbert spaces. See [16] for more detailed discussion on the existence and uniqueness of pseudoinverse for a bounded linear operator.
Additional CI allows the criterion to return a matrix, which can then be nested into other equation. Corollary 1. Given Lemma 4, if (D ? A,B00 | C) and (D ? B | C) in G\R, then
Q(A,b00, c00|D) = Q(A,b00|C0, c00) ·Q(B0,b00|C0, c00)† ·Q(B0,b00, c00|D).
These results advance current knowledge of the causal or non-causal identification with fragments of information presented as conditional distributions, which is often under-studied.

heading: 5.2 C-Factorization-based Intermediary Criterion

text:
We proceed to characterize an intermediary criterion where a matrix equation corresponds to a c-factorization resulting in three factors, extending the case of a pair of factors (Lemma 2). Concretely speaking, we are interested in the matrix form of
Px`(y`) = X
z,w
Pxi(yi)Pxj (yj)Pxk(yk) = X
z
Pxi(yi) X
w
Pxj (yj)Pxk(yk), (4)
where Z ✓ Xi \Yj and W ✓ Xj \Yk are disjoint sets of variables to be marginalized (the order among the three factors is irrelevant since they are invariant up to renaming.) In addition, available distributions are of the form PXj (Yj), PXij\Yij (Yij\Z), and PXjk\Yjk(Yjk\W). Theorem 3 (C-Factorization Intermediary Criterion). Let G be a causal diagram and Q = Pr. Let Qx`(y`) be c-factorized as Eq. (4). Let X + k be a subset of Xk excluding the rest five sets, {Yi,Yj ,Yk,Xi,Xj}. Y + i is similarly defined. If Z ✓ (Xi \Yj)\Xk and W ✓ Xj \Yk, then Qx`/X+k (y`/Y + i ), a submatrix of QX`(Y`), becomes
Qx`/X+k (y`/Y
+ i ) = Q(xij\yij)/W((yij\Z)/Y + i ) ·Qxj/W(yj/Z) † ·Q(xjk\yjk)/X+k ((yjk\W)/Z).
The theorem imposes an additional constraint that Z should be disjoint to Xk compared to naively interpreting the three-matrix multiplication as two individual matrix multiplications as seen in Lemma 2 (we depict the sophisticated set relationships among W, Xs, Ys, and Z in Appendix D [13].) Briefly speaking, given that the summation over W is nested (Eq. (4)), (Xj [Yj)\W is fixed along with Yj \Xk. Thus, Xi \Yj \Xk can’t be part of Z. In other words, the constraints imposed in the original expression asymmetrically affect what Z can be but not what W can be.
The implication of this result is immediate. It was previously unknown whether the identification procedures by Lee and Bareinboim [12] (GID-PO) and Lee and Shpitser [11] (Lemma 3 and 6) taking marginal and interventional are complete. Now, we show a negative result. Proposition 1. GID-PO [12] and Lemma 3 and 6 [11] are not complete.
Proof. Consider a causal graph X ! A ! B ! Y and distributions P (X,B), P (A,B), and P (A,Y ). Px(y) is identified as P(y|A)P(B|A)†P(B|x), which is not solvable by [12, 11].
In this section, we developed novel intermediary criteria by characterizing both chain-rule and cfactorization with respect to matrix multiplications of three matrices exploiting the pseudoinverse, which has never been employed in the context of causal identification to the best of our knowledge.

heading: 6 A Unifying Causal Identification Algorithm

text:
We present a causal identification algorithm ID-ME (Alg. 1) taking a collection of marginal, conditional, and interventional distributions D and causal graph G.6 The algorithm integrates different approaches such as generalized proxy-variable based criteria (Sec. 4 and [8, 10, 15]), intermediary criteria (Sec. 5), and factorization approaches [23, 14, 12, 11].
Taking a causal query Px(y), causal graph G, and distributions D, it refines the given query by removing redundant interventions based on Rule 3 of do-calculus, i.e., Px(y) = Px0(y) for a
6We omit some details on whether some variables are fixed (e.g., Pa(B) versus PA(B)). Without loss of generality, every distribution contains no redundant conditions and interventions, which can be obtained through repeatedly applying rules of do-calculus.
Algorithm 1 ID-ME 1: function ID-ME(x, y, G, D)
Input: x, y value assignments for a query Px(y); G a causal diagram; D a collection of distributions Output: a formula for Px(y) made with D or FAIL.
2: X,G0 anGX(Y) \X,G[AnG(Y)] 3: D expand(G,D) unless D is unconditional 4: F+ FG0 if D is unconditional and nonmarginal else S {FG0hV0i | X [Y ✓ V0 ✓ V} 5: F0,F00 empty dictionary,F+ 6: for all PXi(Yi) 2 F00 and {PZ(V0|T) 2 D | Yi ✓ V0,Xi ✓ Z [V0 [T} do 7: update F0,F00 with ID-RC(PXi(Yi), G0, PZ(V0|T)) 8: for all PXi(Yi) 2 F00 do update F0,F00 with PROXY(PXi(Yi), G, D [ F0) 9: repeat update F0,F00 with CF-INT(G0,F0,F00) and CF-INV(G0,F0,F00) until F0 not changed
10: return exact-cover(G0,Px(y),F0)
minimal subset X0 ✓ X. Further, G0 a copy of causal graph is obtained through pruning G only to the ancestors of Y. However, note that the original G is kept intact to be used in the proxy criteria later where proxies can be non-ancestors of Y, e.g., Fig. 1b. Then, the algorithm proceeds the following three parts: 1) expanding the given distributions D; 2) c-factorizing the query Px(y) and identifying each factor; and 3) combining identified c-factors F0 to elicit the causal query. First, the algorithm expands the given distributions (expand in Line 3). A given conditional distribution PZ(V0|T) can be understood as a distribution PZ(V0) under a selection bias, which might hinder identification of a c-factor. By multiplying another distribution equal to, e.g., PZ(T00|T0), we can obtain a distribution with more outcome and less bias, PZ(V0,T00|T0). Chain rule closure [11] describes a state of a set of distributions where no new distribution with a smaller condition can be added to the collection. Function expand contains a procedure for chain rule closure along with chain-rule matrix inversion (Lemma 1) and chain-rule intermediary criterion (Lemma 4), enjoying the matrical approach especially relevant to conditional distributions.
The next part enumerates c-factors (Line 4) and attempts to identify every c-factor based on available distributions (Lines 5–8). An algorithm for identifying a c-factor given a single unconditional and non-marginal distribution has been thoroughly studied (e.g., Identify [29] and ID [23]), and is a building block for general identification [2, 14]. Dealing with a marginal or conditional distribution, one should consider (i) whether the condition in the conditional distribution in D can be negligible with respect to identifying the c-factor or (ii) whether matrix equations can be utilized (e.g., simple inverse or generalized proxy criteria). ID-RC (Line 7) is an identification module modified to handle a conditional distribution [4, 11], and PROXY (Line 8) refers to generalized proxy criteria.
The last part (Lines 9–10) attempts to map the identified c-factors to the causal effect Px(y). Once a subset of c-factors are identified from the previous step, the algorithm proceeds to examine whether some of the unidentified factors in F00 can be further inferred from the individually identified factors F0, i.e., whether a simple inverse (CF-INV implementing Lemma 2) or the intermediary criterion over c-factors (CF-INT implementing Thm. 3) can be invoked (Line 9). Then, we finally elicit a causal effect if a valid combination of identified c-factors exists (exact-cover in Line 10 checking Eq. (2)).
The algorithm coherently integrates existing methods and the newly developed machinery in the previous sections. Whenever ID-ME returns a formula, evaluation of the formula leads to the quantity Px(y). Further, ID-ME strictly subsumes the union of aforementioned methods in a way that not only returns it a formula whenever some of the methods returns one given the same problem instance but also it can output novel formulae for the problems that cannot be answered by any of them as demonstrated through examples and by Prop. 1. Theorem 4. ID-ME is sound.
Theorem 5. ID-ME strictly subsumes proxy criteria [8, 15], GID(-PO) [14, 12], mID, or eID [11].
Finally, we discuss the time complexity of ID-ME through examining the complexity of algorithms concerning a subset of problem instances ID-ME can handle. First, the state of the art identification conditions with distributions marginal, experimental, but unconditional [12, 11] involve finding a latent projection where the corresponding set of c-factors are all identified. It is conjectured that it requires time exponential in |V| [12]. Next, dealing with conditional distributions through expanding
them takes time exponential in |V| (e.g., chain rule closure [11]). As a result the algorithm generally runs in time exponential in |V|, which we speculate that this complexity reflects a fundamental trade off between expressive power and tractability within causal inference, as already observed in [12, 11].

heading: 7 Conclusion

text:
In this paper, we studied the use of matrix equations in causal identification given general distributions. In particular, we characterized matrix equations made of distributions driven by graphical constraints, deepening our understanding on algebraic constraints imposed by the graph (Lemmas 1 and 2 in Sec. 3). We generalized proxy-based identification methods to cover a broad spectrum of problem instances beyond the identification problems with an observation study and optional external study (Thms 1 and 2 in Sec. 4). We developed novel intermediary criteria that identify a query by utilizing the pseudoinverse of the center matrix within the multiplication of three matrices (Lemma 4 and Thm. 3 in Sec. 5). Finally, we provide a causal identification algorithm (Alg. 1 in Sec. 6) integrating several existing identification results to produce an identification formula for a causal query given a causal graph and distributions that can be marginal, experimental, and conditional harnessing the power of matrix equations and (pseudo)inverses. As a future research direction, it will be crucial to devise a statistically efficient estimator for identification formulae involving matrix inversion.
Acknowledgments and Disclosure of Funding
Sanghack Lee was supported by the New Faculty Startup Fund from Seoul National University. Elias Bareinboim was supported in part by funding from the NSF, Amazon, JP Morgan, and The Alfred P. Sloan Foundation.

title: Causal Identification with Matrix Equations


summaries: This paper proposes to theoretical analysis of the Prioritized Level Replay (PLR) from prior work and proposes an environment generation framework named Dual Curriculum Design (DCD). The proposed framework is composed of teacher agents that keep generating new environments and a student agent that learns to solve the generated environments. The teacher agents are co-adapted to generate new environments by maximizing the student's agent's regret. In a grid world domain and the CarRacing domain, the proposed method outperforms previous baselines such as PAIRD.

summaries: This paper studies the problem of automatically designing a distribution of environments that adjusts to the learning agent, called unsupervised environment design. Specifically, they propose Dual Curriculum Design in which two co-evolving teachers, i.e. one is a generator and another one is a replay teacher, introduce new levels/environments to the learning agent (a.k.a student) to learn a policy that can be effectively generalized to new and unseen environments. Besides, this paper proposes a new theory about PLR and REPAIRED robustness guarantees. The paper evaluates zero-shot generalization, emergent complexity, and scalability of their proposed method in multiple environments and scenarios.

summaries: This paper considers a recent proposed problem, unsupervised environment design, that provides an environment selection scheme to enable the policy being trained under a curriculum learning setting. The proposed method combines two new approaches in this direction, PAIRED and PLR, where the former one learns to generate an environment while the latter one does not include a generator but instead gives a sampling scheme to choose previously encountered environments. The combined method is explained as a two-teacher dual curriculum game and explained theoretically. Experiments demonstrate the effectiveness of the combined method compared to PAIRED and PLR, respectively.

summaries: This paper considers two forms of curriculum design, unsupervised environment design and prioritized experience replay, and highlight their complementary nature. It then considers the games induced by both these approaches and combines them into a dual curriculum game where the agent faces one teacher or the other with certain probability. Further, the paper analyzes the equilibria of this joint game and the equilibria of the two component games.  The paper then proposes two new algorithms, a robust version of PLR that does not learn on experienced trajectories but only on trajectories sampled by the PLR teacher, and a replay-enhanced PAIRED that improves the UED technique with PLR.  The various approaches are then compared on mazes and car racing domains.

summaries: In this paper, the authors propose a common framework,  Dual Curriculum Design, that augments PAIRED with a PLR-based replay mechanism, named as REPAIRED. The theory also suggests convergence to Nash Equilibrium should be assisted by training on fewer data when using PLR—namely by only taking policy-gradient updates from data that originates from the PLR buffer, and only using samples from the environment distribution to populate the buffer. The authors further conducted experiments on a maze environment and on car-racing tracks. Results showed that the proposed approaches outperformed the PLR and other baselines in general.

abstractText: Deep reinforcement learning (RL) agents may successfully generalize to new settings if trained on an appropriately diverse set of environment and task configurations. Unsupervised Environment Design (UED) is a promising selfsupervised RL paradigm, wherein the free parameters of an underspecified environment are automatically adapted during training to the agent’s capabilities, leading to the emergence of diverse training environments. Here, we cast Prioritized Level Replay (PLR), an empirically successful but theoretically unmotivated method that selectively samples randomly-generated training levels, as UED. We argue that by curating completely random levels, PLR, too, can generate novel and complex levels for effective training. This insight reveals a natural class of UED methods we call Dual Curriculum Design (DCD). Crucially, DCD includes both PLR and a popular UED algorithm, PAIRED, as special cases and inherits similar theoretical guarantees. This connection allows us to develop novel theory for PLR, providing a version with a robustness guarantee at Nash equilibria. Furthermore, our theory suggests a highly counterintuitive improvement to PLR: by stopping the agent from updating its policy on uncurated levels (training on less data), we can improve the convergence to Nash equilibria. Indeed, our experiments confirm that our new method, PLR⊥, obtains better results on a suite of out-of-distribution, zero-shot transfer tasks, in addition to demonstrating that PLR⊥ improves the performance of PAIRED, from which it inherited its theoretical framework.

authors:
O.M. Andrychowicz
B. Baker
M. Chociej
R. Józefowicz
B. McGrew
J. Pachocki
A. Petron
M. Plappert
G. Powell
A. Ray
J. Schneider
S. Sidor
J. Tobin
P. Welinder
L. Weng
W. Zaremba

title: Learning dexterous in-hand manipulation

venue: The International Journal of Robotics Research, 39(1):3–20

authors:
Y. Bengio
J. Louradour
R. Collobert
J. Weston

title: Curriculum learning

venue: Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 41–48, New York, NY, USA

authors:
J. Bergstra
Y. Bengio

title: Random search for hyper-parameter optimization

venue: Journal of Machine Learning Research, 13:281–305

authors:
C. Berner
G. Brockman
B. Chan
V. Cheung
P. Dębiak
C. Dennison
D. Farhi
Q. Fischer
S. Hashme
C. Hesse

title: et al

venue: Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06680

authors:
G. Brockman
V. Cheung
L. Pettersson
J. Schneider
J. Schulman
J. Tang
W. Zaremba

title: Openai gym

authors:
A. Campero
R. Raileanu
H. Kuttler
J.B. Tenenbaum
T. Rocktäschel
E. Grefenstette

title: Learning with AMIGo: Adversarially motivated intrinsic goals

venue: International Conference on Learning Representations

authors:
M. Chevalier-Boisvert
L. Willems
S. Pal

title: Minimalistic gridworld environment for openai gym

authors:
K. Cobbe
C. Hesse
J. Hilton
J. Schulman

title: Leveraging procedural generation to benchmark reinforcement learning

venue: Proceedings of the 37th International Conference on Machine Learning, pages 2048–2056

authors:
K. Cobbe
O. Klimov
C. Hesse
T. Kim
J. Schulman

title: Quantifying generalization in reinforcement learning

venue: K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research. PMLR

authors:
M. Dennis
N. Jaques
E. Vinitsky
A. Bayen
S. Russell
A. Critch
S. Levine

title: Emergent complexity and zero-shot transfer via unsupervised environment design

venue: Advances in Neural Information Processing Systems, volume 33

authors:
K. Fang
Y. Zhu
S. Savarese
F.-F. Li

title: Adaptive procedural task generation for hardexploration problems

authors:
C. Florensa
D. Held
X. Geng
P. Abbeel

title: Automatic goal generation for reinforcement learning agents

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
J. Heinrich
M. Lanctot
D. Silver

title: Fictitious self-play in extensive-form games

venue: Proceedings of the 32nd International Conference on Machine Learning, pages 805–813

authors:
A. Jabri
K. Hsu
A. Gupta
B. Eysenbach
S. Levine
C. Finn

title: Unsupervised curricula for visual meta-reinforcement learning

venue: Advances in Neural Information Processing Systems, volume 32

title: Evolutionary robotics and the radical envelope-of-noise hypothesis

venue: Adaptive Behavior, 6(2):325–368

authors:
S. James
A.J. Davison
E. Johns

title: Transferring end-to-end visuomotor control from simulation to real world for a multi-stage task

venue: 1st Conference on Robot Learning

authors:
M. Jiang
E. Grefenstette
T. Rocktäschel

title: Prioritized level replay

venue: Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 4940–4950. PMLR

title: Car racing with pytorch

authors:
T. Matiisen
A. Oliver
T. Cohen
J. Schulman

title: Teacher-student curriculum learning

venue: IEEE Transactions on Neural Networks and Learning Systems, PP,

authors:
B. Mehta
M. Diaz
F. Golemo
C.J. Pal
L. Paull

title: Active domain randomization

venue: L. P. Kaelbling, D. Kragic, and K. Sugiura, editors, 3rd Annual Conference on Robot Learning, CoRL 2019, Osaka, Japan, October 30 - November 1, 2019, Proceedings, volume 100 of Proceedings of Machine Learning Research, pages 1162–1176. PMLR

authors:
V. Mnih
K. Kavukcuoglu
D. Silver
A.A. Rusu
J. Veness
M.G. Bellemare
A. Graves
M. Riedmiller
A.K. Fidjeland
G. Ostrovski

title: et al

venue: Human-level control through deep reinforcement learning. Nature, 518(7540):529–533

title: Mathematics for Computer Graphics Applications

venue: Industrial Press Inc.

authors:
S. Narvekar
B. Peng
M. Leonetti
J. Sinapov
M.E. Taylor
P. Stone

title: Curriculum learning for reinforcement learning domains: A framework and survey

venue: Journal of Machine Learning Research, 21:181:1–181:50

title: Equilibrium points in n-person games

venue: Proceedings of the National Academy of Sciences,

authors:
OpenAI
I. Akkaya
M. Andrychowicz
M. Chociej
M. Litwin
B. McGrew
A. Petron
A. Paino
M. Plappert
G. Powell
R. Ribas
J. Schneider
N. Tezak
J. Tworek
P. Welinder
L. Weng
Q. Yuan
W. Zaremba
L. Zhang

title: Solving rubik’s cube with a robot

venue: hand. CoRR,

authors:
O. OpenAI
M. Plappert
R. Sampedro
T. Xu
I. Akkaya
V. Kosaraju
P. Welinder

title: R

venue: D’Sa, A. Petron, H. P. de Oliveira Pinto, A. Paino, H. Noh, L. Weng, Q. Yuan, C. Chu, and W. Zaremba. Asymmetric self-play for automatic goal discovery in robotic manipulation

authors:
E. Popovici
A. Bucci
R.P. Wiegand
E.D. De Jong

title: Coevolutionary Principles

venue: pages 987–1033. Springer Berlin Heidelberg

authors:
R. Portelas
C. Colas
L. Weng
K. Hofmann
P.-Y. Oudeyer

title: Automatic curriculum learning for deep rl: A short survey

venue: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence,

authors:
S. Racaniere
A. Lampinen
A. Santoro
D. Reichert
V. Firoiu
T. Lillicrap

title: Automated curriculum generation through setter-solver interactions

authors:
S. Risi
J. Togelius

title: Increasing generality in machine learning through procedural content generation

venue: Nature Machine Intelligence, 2(8):428–436,

title: The theory of statistical decision

venue: Journal of the American Statistical association, 46(253):55–67

title: Powerplay: Training an increasingly general problem solver by continually searching for the simplest still unsolvable problem

venue: Frontiers in Psychology, 4:313,

authors:
J. Schulman
P. Moritz
S. Levine
M.I. Jordan
P. Abbeel

title: High-dimensional continuous control using generalized advantage estimation

venue: Y. Bengio and Y. LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings

authors:
J. Schulman
F. Wolski
P. Dhariwal
A. Radford
O. Klimov

title: Proximal policy optimization algorithms

authors:
D. Silver
A. Huang
C.J. Maddison
A. Guez
L. Sifre

title: G

venue: Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489

authors:
D. Silver
T. Hubert
J. Schrittwieser
I. Antonoglou
M. Lai
A. Guez
M. Lanctot
L. Sifre
D. Kumaran
T. Graepel

title: et al

venue: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1144

authors:
S. Sukhbaatar
Z. Lin
I. Kostrikov
G. Synnaeve
A. Szlam
R. Fergus

title: Intrinsic motivation and automatic curricula via asymmetric self-play

venue: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net

authors:
Y. Tang
D. Nguyen
D. Ha

title: Neuroevolution of self-interpretable agents

venue: Proceedings of the Genetic and Evolutionary Computation Conference

authors:
J. Tobin
R. Fong
A. Ray
J. Schneider
W. Zaremba
P. Abbeel

title: Domain randomization for transferring deep neural networks from simulation to the real world

venue: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 23–30

authors:
O. Vinyals
I. Babuschkin
W.M. Czarnecki
M. Mathieu
A. Dudzik
J. Chung
D.H. Choi
R. Powell
T. Ewalds
P. Georgiev

title: et al

venue: Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782):350–354

authors:
R. Wang
J. Lehman
J. Clune
K.O. Stanley

title: Paired open-ended trailblazer (POET): endlessly generating increasingly complex and diverse learning environments and their solutions

authors:
R. Wang
J. Lehman
A. Rawal
J. Zhi
Y. Li
J. Clune
K. Stanley

title: Enhanced POET: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions

venue: Proceedings of the 37th International Conference on Machine Learning, pages 9940–9951

title: The generalization of ‘student’s’ problem when several different population variances are involved

authors:
A. Zhang
N. Ballas
J. Pineau

title: A dissection of overfitting and generalization in continuous reinforcement learning

venue: arXiv preprint arXiv:1806.07937

authors:
Y. Zhang
P. Abbeel
L. Pinto

title: Automatic curriculum learning through value disagreement

venue: Advances in Neural Information Processing Systems, volume 33, pages 7648–7659

heading: 1 Introduction

text:
While deep reinforcement learning (RL) approaches have led to many successful applications in challenging domains like Atari [21], Go [35], Chess [36], Dota [4], and StarCraft [40] in recent years, deep RL agents still prove to be brittle, often failing to transfer to environments only slightly different from those encountered during training [44, 9]. To ensure learning of robust and well-generalizing policies, agents must train on sufficiently diverse and informative variations of environments (e.g. see Section 3.1 of [8]). However, it is not always feasible to specify an appropriate training distribution or a generator thereof. Agents may therefore benefit greatly from methods that automatically adapt the distribution over environment variations throughout training [10, 17]. Throughout this paper we will call a particular environment instance or configuration (e.g. an arrangement of blocks, race tracks, or generally any of the environment’s constituent entities) a level.
Two recent works [10, 17] have sought to empirically demonstrate this need for a more targeted agentadaptive mechanism for selecting levels on which to train RL agents, so to ensure efficient learning and generalization to unseen levels—as well as to provide methods implementing such mechanisms. The first method, Protagonist Antagonist Induced Regret Environment Design (PAIRED) [10], ∗Equal contribution. Correspondence to msj@fb.com and michael_dennis@berkeley.edu .
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
introduces a self-supervised RL paradigm called Unsupervised Environment Design (UED). Here, an environment generator (a teacher) is co-evolved with a student policy that trains on levels actively proposed by the teacher, leading to a form of adaptive curriculum learning. The aim of this coevolution is for the teacher to gradually learn to generate environments that exemplify properties of those that might be encountered at deployment time, and for the student to simultaneously learn a good policy that enables zero-shot transfer to such environments. PAIRED’s specific adversarial approach to environment design ensures a useful robustness characterization of the final student policy in the form of a minimax regret guarantee [31]—assuming that its underlying teacher-student multi-agent system arrives at a Nash equilibrium [NE, 24]. In contrast, the second method, Prioritized Level Replay (PLR) [17], embodies an alternative form of dynamic curriculum learning that does not assume control of level generation, but instead, the ability to selectively replay existing levels. PLR tracks levels previously proposed by a black-box environment generator, and for each, estimates the agent’s learning potential in that level, in terms of how useful it would be to gather new experience from that level again in the future. The PLR algorithm exploits these scores to adapt a schedule for revisiting or replaying levels to maximize learning potential. PLR has been shown to produce scalable and robust results, improving both sample complexity of agent training and the generalization of the learned policy in diverse environments. However, unlike PAIRED, PLR is motivated with heuristic arguments and lacks a useful theoretical characterization of its learning behavior.
In this paper, we argue that PLR is, in and of itself, an effective form of UED: Through curating even randomly generated levels, PLR can generate novel and complex levels for learning robust policies. This insight leads to a natural class of UED methods which we call Dual Curriculum Design (DCD). In DCD, a student policy is challenged by a team of two co-evolving teachers. One teacher actively generates new, challenging levels, while the other passively curates existing levels for replaying, by prioritizing those estimated to be most suitably challenging for the student. We show that PAIRED and PLR are distinct members of the DCD class of algorithms and prove in Section 3 that all DCD algorithms enjoy similar minimax regret guarantees to that of PAIRED.
We make use of this result to provide the first theoretical characterization of PLR, which immediately suggests a simple yet highly counterintuitive adjustment to PLR: By only training on trajectories in replay levels, PLR becomes provably robust at NE. We call this resulting variant PLR⊥ (Section 4). From this perspective, PLR effectively performs level design in a diametrically opposite manner to PAIRED—through prioritized selection rather than active generation. A second corollary to the provable robustness of DCD algorithms shows that PLR⊥ can be extended to make use of the PAIRED teacher as a level generator while preserving the robustness guarantee of PAIRED, resulting in a method we call Replay-Enhanced PAIRED (REPAIRED) (Section 5). We hypothesize that in this arrangement, PLR⊥ plays a complementary role to PAIRED in robustifying student policies.
Our experiments in Section 6 investigate the learning dynamics of PLR⊥, REPAIRED, and their replay-free counterparts on a challenging maze domain and a novel continuous control UED setting based on the popular CarRacing environment [5]. In both of these highly distinct settings, our methods provide significant improvements over PLR and PAIRED, producing agents that can perform out-of-distribution (OOD) generalization to a variety of human designed mazes and Formula 1 tracks.
In summary, we present the following contributions: (i) We establish a common framework, Dual Curriculum Design, that encompasses PLR and PAIRED. This allows us to develop new theory, which provides the first robustness guarantees for PLR at NE as well as for REPAIRED, which
augments PAIRED with a PLR-based replay mechanism. (ii) Crucially, our theory suggests a highly counterintuitive improvement to PLR: the convergence to NE should be assisted by training on less data when using PLR—namely by only taking gradient updates from data that originates from the PLR buffer, using the samples from the environment distribution only for computing the prioritization of levels in the buffer. (iii) Our experiments in a maze domain and a novel car racing domain show that our methods significantly outperform their replay-free counterparts in zero-shot generalization. We open source our methods at https://github.com/facebookresearch/dcd.

heading: 2 Background

heading: 2.1 Unsupervised Environment Design

text:
Unsupervised Environment Design (UED), as introduced by [10], is the problem of automatically designing a distribution of environments that adapts to the learning agent. UED is defined in terms of an Underspecified POMDP (UPOMDP), given byM = 〈A,O,Θ, SM, TM, IM,RM, γ〉, where A is a set of actions, O is a set of observations, S is a set of states, T : S × A × Θ → ∆(S) is a transition function, I : S → O is an observation (or inspection) function, R : S → R is a reward function, and γ is a discount factor. This definition is identical to a POMDP with the addition of Θ to represent the free-parameters of the environment. These parameters can be distinct at every time step and incorporated into the transition function TM : S ×A×Θ→∆(S). For example, Θ could represent the possible positions of obstacles in a maze. We will refer to the environment resulting from a fixed θ ∈ Θ asMθ, or with a slight abuse of notation, simply θ when clear from context. We define the value of π inMθ to be V θ(π) = E[ ∑T i=0 rtγ
t] where rt are the rewards attained by π in Mθ. Aligning with terminology from [17], we refer to a fully-specified environment as a level.

heading: 2.2 Protagonist Antagonist Induced Regret Environment Design

text:
Protagonist Antagonist Induced Regret Environment Design [PAIRED, 10] presents a UED approach consisting of simultaneously training agents in a three player game: the protagonist πA and the antagonist πB are trained in environments generated by the teacher θ̃. The objective of this game is defined by U(πA, πB , θ̃) = Eθ∼θ̃[REGRET
θ(πA, πB)], where regret is defined by REGRETθ(πA, πB) = V θ(πB) − V θ(πA). The protagonist and antagonist are both trained to maximize their discounted environment returns while the teacher is trained to maximize U . Note that by maximizing regret, the teacher is disincentivized from generating unsolvable levels, which will have a maximum regret of 0. As shorthand, we will sometimes refer to the protagonist and antagonist jointly as the student agents. The counterclockwise loop beginning at the student agents in Figure 2 summarizes this approach, with the students being both the protagonist and antagonist.
As both student agents grow more adept at solving different levels, the teacher continues to adapt its level designs to exploit the weaknesses of the protagonist in relation to the antagonist. As this dynamic unfolds, PAIRED produces an emergent curriculum of progressively more complex levels along the boundary of the protagonist’s capabilities. PAIRED is a creative method in the sense that the teacher may potentially generate an endless sequence of novel levels. However, as the teacher only adapts through gradient updates, it is inherently slow to adapt to changes in the student policies.

heading: 2.3 Prioritized Level Replay

text:
Prioritized Level Replay [PLR, 17] is an active-learning strategy shown to improve a policy’s sample efficiency and generalization to unseen levels when training and evaluating on levels from a common UPOMDP, typically implemented as a seeded simulator. PLR maintains a level buffer Λ of the top K visited levels with highest learning potential as estimated by the time-averaged L1 value loss of the learning agent over the last episode on each level. At the start of each training episode, with some predefined replay probability p, PLR uses a bandit to sample the level from Λ to maximize the estimated learning potential; otherwise, with probability 1− p, PLR samples a new level from the simulator. In contrast to the generative but slow-adapting PAIRED, PLR does not create new levels, but instead, acts as a fast-adapting curation mechanism for selecting the next training level among previously encountered levels. Also unlike PAIRED, PLR does not provide a robustness guarantee. By extending the theoretical foundation of PAIRED to PLR, we will show how PLR can be modified
to provide a robustness guarantee at NE, as well as how PAIRED can exploit PLR’s complementary curation to quickly switch among generated levels to maximize the student’s regret.

heading: 3 The Robustness of Dual Curriculum Design

text:
The previous approaches of PAIRED and PLR reveal a natural duality: Approaches that gradually learn to generate levels like PAIRED, and methods which cannot generate levels, but instead, quickly curate existing ones, like PLR. This duality suggests combining slow level generators with fast level curators. We call this novel class of UED algorithms Dual Curriculum Design (DCD). For instance, PLR can be seen as curator with a prioritized sampling mechanism with a random generator, while PAIRED, as a regret-maximizing generator without a curator. DCD can further consider Domain Randomization (DR) as a degenerate case of a random level generator without a curator.
To theoretically analyze this space of methods, we model DCD as a three player game among a student agent and two teachers called the dual curriculum game. However, to formalize this game, we must first formalize the single-teacher setting: Suppose the UPOMDP is clear from context. Then, given a utility function for a single teacher, Ut(π, θ), we can naturally define the base game between the student s and teacher t as G = 〈S = Ss × St, U = Us × Ut〉, where Ss = Π is the strategy set of the student, St = Θ is the strategy set of the teacher, and Us(π, θ) = V θ(π) is the utility function of the student. In Sections 4 and 5, we will study settings corresponding to different choices of utility functions for the teacher agents, namely the maximum-regret objective URt (π, θ) and the uniform objective UUt (π, θ). These two objectives are defined as follows (for any constant C):
URt (π, θ) = argmax π∗∈Π {V θ(π∗)− V θ(π)} (1)
UUt (π, θ) = C (2)
In the dual curriculum game G, the first teacher plays the game with probability p, and the second, with probability (1− p)—or more formally, G = 〈S = Ss × St × St, U = Us × U 1 t × U 2
t 〉, where the utility functions for the student and two teachers respectively, Us, U 1 t , U 2 t , are defined as follows:
U 1
t (π, θ 1, θ2) = pU1t (π, θ 1) (3) U 2
t (π, θ 1, θ2) = (1− p)U2t (π, θ2) (4)
Us(π, θ 1, θ2) = pUs(π, θ 1) + (1− p)Us(π, θ2) (5)
Our main theorem is that NE in the dual curriculum game are approximate NE of both the base game for either of the original teachers and the base game with a teacher maximizing the joint-reward of pU1t + (1− p)U2t , where the quality of the approximations depends on the mixing probability p.
Theorem 1. Let B be the maximum difference between U1t and U2t , and let (π, θ1, θ2) be a NE for G. Then (π, pθ1 + (1− p)θ2) is an approximate NE for the base game with either teacher or for a teacher optimizing their joint objective. More precisely, it is a 2Bp(1− p)-approximate NE when Ut = pU 1 t + (1− p)U2t , a 2B(1− p)-approximate NE when Ut = U1t , and a 2Bp-approximate NE when Ut = U2t .
The intuition behind this theorem is that, since the two teachers do not affect each other’s behavior, their best response to a fixed πs is to choose a strategy θ that maximizes U1t and U 2 t respectively.
Moreover, the two teachers’ strategies can be viewed as a single combined strategy for the base game with the joint-objective, or with each teacher’s own objective. In fact, the teachers provide an approximate best-response to each case of the base game simply by playing their individual best responses. Thus, when we reach a NE of the dual curriculum game, the teachers arrive at approximate best responses for both the base game with the joint objective and with their own objectives, meaning they are also in an approximate NE of the base game with either teacher. The full details of this proof are outlined in Appendix A.

heading: 4 Robustifying PLR

text:
In this section, we provide theoretical justification for the empirically observed effectiveness of PLR, and in the process, motivate a counterintuitive adjustment to the algorithm.
Algorithm 1: Robust PLR (PLR⊥) Randomly initialize policy π(φ) and an empty level buffer, Λ of size K. while not converged do
Sample replay-decision Bernoulli, d ∼ PD(d) if d = 0 then
Sample level θ from level generator Collect π’s trajectory τ on θ, with a stop-gradient φ⊥ i.e. Suppress policy update
else Use PLR to sample a replay level from the level store, θ ∼ Λ Collect policy trajectory τ on θ and update π with rewards R(τ) end Compute PLR score, S = score(τ, π) Update Λ with θ using score S
end

heading: 4.1 Achieving Robustness Guarantees with PLR

text:
PLR provides strong empirical gains in generalization, but lacks any theoretical guarantees of robustness. One step towards achieving such a guarantee is to replace its L1 value-loss prioritizaton with a regret prioritization, using the methods we discuss in Section 4.2: While L1 value loss may be good for quickly training the value function, it can bias the long-term training behavior toward high-variance policies. However, even with this change, PLR holds weaker theoretical guarantees because the random generating teacher can bias the student away from minimax regret policies and instead, toward policies that sacrifice robustness in order to excel in unstructured levels. We formalize this intuitive argument in the following corollary of Theorem 1.
Corollary 1. Let G be the dual curriculum game in which the first teacher maximizes regret, so U1t = U R t , and the second teacher plays randomly, so U 2 t = U U t . Let V
θ(π) be bounded in [B−, B+] for all θ, π. Further, suppose that (π, θ1, θ2) is a Nash equilibrium of G. Let R∗ = minπA∈Π{maxθ,πB∈Θ,Π{REGRETθ(πA, πB)}} be the optimal worst-case regret. Then π is 2(B+ − B−)(1 − p) close to having optimal worst-case regret, or formally, maxθ,πB∈Θ,Π{REGRETθ(πA, π)} ≥ R∗−2(B+−B−)(1−p). Moreover, there exists environments for all values of p within a constant factor of achieving this bound.
The proof of Corollary 1 follows from a direct application of Theorem 1 to show that a NE of G is an approximate NE for the base game of the first teacher, and through constructing a simple example where the student’s best response in G fails to attain the minimax regret in G. These arguments are described in full in Appendix A. This corollary provides some justification for why PLR improves robustness of the equilibrium policy, as it biases the resulting policy toward a minimax regret policy. However, it also points a way towards further improving PLR: If the probability p of using a teachergenerated level directly was set to 0, then in equilibrium, the resulting policy converges to a minimax regret policy. Consequently, we arrive at the counterintuitive idea of avoiding gradient updates from trajectories collected from randomly sampled levels, to ensure that at NE, we find a minimax regret policy. From a robustness standpoint, it is therefore optimal to train on less data. The modified PLR algorithm PLR⊥ with this counterintuitive adjustment is summarized in Algorithm 1, in which this small change relative to the original algorithm is highlighted in blue.

heading: 4.2 Estimating Regret

text:
In general, levels may differ in maximum achievable returns, making it impossible to know the true regret of a level without access to an oracle. As the L1 value loss typically employed by PLR does not generally correspond to regret, we turn to alternative scoring functions that better approximate regret. Two approaches, both effective in practice, are discussed below.
Positive Value Loss Averaging over all transitions with positive value loss amounts to estimating regret as the difference between maximum achieved return and predicted return on an episodic basis. However, this estimate is highly biased, as the value targets are tied to the agent’s current, potentially suboptimal policy. As it only considers positive value losses, this scoring function leads to optimistic sampling of levels with respect to the current policy. When using GAE [33] to estimate bootstrapped value targets, this loss takes the following form, where λ and γ are the GAE and MDP discount factors respectively, and δt, the TD-error at timestep t:
1
T T∑ t=0 max ( T∑ k=t (γλ)k−tδk, 0 ) .
Maximum Monte Carlo (MaxMC) We can mitigate some of the bias of the positive value loss by replacing the value target with the highest return achieved on the given level so far during training. By using this maximal return, the regret estimates no longer depend on the agent’s current policy. This estimator takes the simple form of (1/T ) ∑T t=0Rmax − V (st). In our dense-reward experiments, we compute this score as the difference between the maximum achieved return and V (s0).

heading: 5 Replay-Enhanced PAIRED (REPAIRED)

text:
We can replace the random generator teacher used by PLR⊥ with the PAIRED teacher. This extension entails a second student agent, the antagonist, also equipped with its own PLR level buffer. In each episode, with probability p, the students evaluate their performances (but do not train) on a newly generated level and, with probability 1− p, train on a level sampled from each student’s own regret-prioritizing PLR buffer. Training only on the highest regret levels should mitigate inefficiencies in the PAIRED teacher’s optimization procedure. We refer to this extension as Replay-Enhanced PAIRED (REPAIRED). An overview of REPAIRED is provided by black arrows in Figure 2, with the students being the protagonist and antagonist, while the full pseudocode is outlined in Appendix B.
Since PLR⊥ and PAIRED both promote regret in equilibrium, it would be reasonable to believe that the combination of the two does the same. A straightforward corollary of Theorem 1, which we describe in Appendix 1, shows that, in a theoretically ideal setting, combining these two algorithms as is done in REPAIRED indeed finds minimax regret strategies in equilibrium.
Corollary 2. Let G be the dual curriculum game in which both teachers maximize regret, so U1t = U 2 t = U R t . Further, suppose that (π, θ
1, θ2) is a Nash equilibrium of G. Then, π ∈ argminπA∈Π{maxθ,πB∈Θ,Π{REGRET θ(πA, πB)}}.
This result gives us some amount of assurance that, if our method arrives at NE, then the protagonist has converged to a minimax regret strategy, which has the benefits outlined in [10]: Since a minimax regret policy solves all solvable environments, whenever this is possible and sufficiently well-defined, we should expect policies resulting from the equilibrium behavior of REPAIRED to be robust and versatile across all environments in the domain.

heading: 6 Experiments

text: Our experiments firstly aim to (1) assess the empirical performance of the theoretically motivated PLR⊥, and secondly, seek to better understand the effect of replay on unsupervised environment design, specifically (2) its impact on the zero-shot generalization performance of the induced student policies, and (3) the complexity of the levels designed by the teacher. To do so, we compare PLR and REPAIRED against their replay-free counterparts, DR and PAIRED, in the two highly distinct settings of discrete control with sparse rewards and continuous control with dense rewards. We provide environment descriptions alongside model and hyperparameter choices in Appendix D.

heading: 6.1 Partially-Observable Navigation

text:
Each navigation level is a partially-observable maze requiring student agents to take discrete actions to reach a goal and receive a sparse reward. Our agents use PPO [34] with an LSTM-based recurrent policy to handle partial observability. Before each episode, the teacher designs the level in this order: beginning with an empty maze, it places one obstructing block per time step up to a predefined block budget, and finally places the agent followed by the goal.
Zero-Shot Generalization We train policies with each method for 250M steps and evaluate zeroshot generalization on several challenging OOD environments, in addition to levels from the full distribution of two procedurally-generated environments, PerfectMaze and LargeCorridor. We also compare against DR and minimax baselines. Our results in Figure 3 and 4 show that PLR⊥ and REPAIRED both achieve greater sample-efficiency and zero-shot generalization than their replay-free counterparts. The improved test performance achieved by PLR⊥over both DR and PLR when trained for an equivalent number of gradient updates, aggregated over all test mazes, is statistically significant (p < 0.05), as is the improved test performance of REPAIRED over PAIRED. Well before 250 million steps, both PLR and PLR⊥ significantly outperform PAIRED after 3 billion training steps, as reported in [10]. Further, both PLR variants lead to policies exhibiting greater zero-shot transfer than the PAIRED variants. Notably, the PLR⊥ agent learns to solve mazes via an approximate right-hand rule. Table 2 in Appendix C.1 reports performance across all test mazes. The success of designing regret-maximizing levels via random search (curation) over learning a generator with RL suggests that for some UPOMDPs, the regret landscape, as a function of the free parameters θ, has a low effective dimensionality [3]. Foregoing gradient-based learning in favor of random search may then lead to faster adaptation to the changing regret landscape, as the policy evolves throughout training.
Emergent Complexity As the student agents improve, the teachers must generate more challenging levels to maintain regret. We measure the resultant emergent complexity by tracking the number of blocks in each level and the shortest path length to the goal (where unsolvable levels are assigned a length of 0). These results, summarized in Figure 4, show that PAIRED slowly adapts the complexity over training while REPAIRED initially quickly grows complexity, before being overtaken by PAIRED. This more rapid onset of complexity may be
due to REPAIRED’s fast replay mechanism, and the long-term slowdown relative to PAIRED may be explained by its less frequent gradient updates. Our results over an extended training period in Appendix C confirm that both PAIRED and REPAIRED slowly increase complexity over time, eventually matching that attained in just a fraction of the number of gradient steps by PLR and PLR⊥. This result shows that random search is surprisingly efficient at continually discovering levels of increasing complexity, given an appropriate curation mechanism such as PLR. Figure 5 shows that, similar to methods with a regret-maximizing teacher, PLR finds levels exhibiting complex structure.

heading: 6.2 Pixel-Based Car Racing with Continuous Control

text:
To test the versatility and scalability of our methods, we turn to an extended version of the CarRacing environment from OpenAI Gym [5]. This environment entails continuous control with dense rewards, a 3-dimensional action space, and partial, pixel observations, with the goal of driving a full lap around a track. To enable UED of any closed-loop track, we reparameterize CarRacing to generate tracks as Bézier curves [22] with arbitrary control points. The teacher generates levels by choosing a sequence of up to 12 control points, which uniquely defines a Bézier track within specific, predefined curvature constraints. After 5M steps of training, we test the zero-shot transfer performance of policies trained by each method on 20 levels replicating official human-designed Formula One (F1) tracks (see Figure 19 in the Appendix for a visualization of the tracks). Note that these tracks are significantly OOD, as they cannot be defined with just 12 control points. In Figure 6 we show the progression of zero-shot transfer performance for the original CarRacing environment, as well as three F1 tracks of varying difficulty, while also including the final performance on the full F1 benchmark. For the final performance, we also evaluated the state-of-the-art CarRacing agent from [38] on our new F1 benchmark.
Unlike in the sparse, discrete navigation setting, we find DR leads to moderately successful policies for zero-shot transfer in CarRacing. Dense rewards simplify the learning problem and random Bezier tracks occasionally contain the challenges seen in F1 tracks, such as hairpin turns and observations showing parallel tracks due to high local curvature. Still, we see that policies trained by selectively sampling tracks to maximize regret significantly outperform those trained by uniformly sampling
from randomly generated tracks, in terms of zero-shot transfer to the OOD F1 tracks. Remarkably, with a replay rate of 0.5, PLR⊥ sees statistically significant (p < 0.001) gains over PLR in zero-shot performance over the full F1 benchmark, despite directly training on only half the rollout data using half as many gradient updates. Once again, we see that random search with curation via PLR produces a rich selection of levels and an effective curriculum.
We also observe that PAIRED struggles to train a robust protagonist in CarRacing. Specifically, PAIRED overexploits the relative strengths of the antagonist over the protagonist, finding curricula that steer the protagonist towards policies that ultimately perform poorly even on simple tracks, leading to a gradual reduction in level complexity. We present training curves revealing this dynamic in Appendix C. As shown in Figure 6, REPAIRED mitigates this degeneracy substantially, though not completely, inducing a policy that significantly outperforms PAIRED (p < 0.001) in mean performance on the full F1 benchmark, but underperforms DR. Notably, PLR⊥ exceeds the performance of the state-of-the-art AttentionAgent [38], despite not using a self-attention policy and training on less than 0.25% of the number of environment steps in comparison. These gains come purely from the induced curriculum.
Figure 17 in Appendix C further reveals that PLR⊥ produces CarRacing policies that tend to achieve higher minimum returns on average compared to the baseline methods, providing further evidence of the benefits of the minimax regret property coupled with a fast replay-based mechanism for efficiently finding high-regret levels.

heading: 7 Related Work

text:
In inducing parallel curricula, DCD follows a rich lineage of curriculum learning methods [2, 32, 28, 23]. Many previous curriculum learning algorithms resemble the curator in DCD, sharing similar underlying selective-sampling mechanisms as PLR⊥. Most similar is TSCL [19], which prioritizes levels based on return rather than value loss, and has been shown to overfit to training levels in some settings [17]. In our setting, replayed levels can be viewed as past strategies from a level-generating teacher. This links our replay-based methods to fictitious self-play [FSP, 13], and more closely, Prioritized FSP [40], which selectively samples opponents based on historic win ratios.
Recent approaches that make use of a generating adversary include Asymmetric Self-Play [37, 26], wherein one agent proposes tasks for another in the form of environment trajectories, and AMIGo [6], wherein the teacher is rewarded for proposing reachable goals. While our methods do not presuppose a goal-based setting, others have made progress here using generative modeling [12, 29], latent skill learning [14], and exploiting model disagreement [45]. These methods are less generally applicable than PLR⊥, and unlike our DCD methods, they do not provide well-principled robustness guarantees.
Other recent algorithms can be understood as forms of UED and like DCD, framed in the lens of decision theory. POET [41, 42], a coevolutionary approach [27], uses a population of minimax (rather than minimax regret) adversaries to construct terrain for a BipedalWalker agent. In contrast to our methods, POET requires training a large population of both agents and environments and consequently, a sizable compute overhead. APT-Gen [11] also procedurally generates tasks, but requires access to target tasks, whereas our methods seek to improve zero-shot transfer.
The DCD framework also encompasses adaptive domain randomization methods [DR, 20, 15], which have seen success in assisting sim2real transfer for robotics [39, 16, 1, 25]. DR itself is subsumed by procedural content generation [30], for which UED and DCD may be seen as providing a formal, decision-theoretic framework, enabling development of provably optimal algorithms.

heading: 8 Discussion

text:
We established a novel connection between PLR and minimax regret UED approaches like PAIRED, by developing the theory of Dual Curriculum Design (DCD). In this setting, a student policy is challenged by a team of two co-adapting, regret-maximizing teachers: one, a generator that creates new levels, and the other, a curator that selectively samples previously generated levels for replay. This view unifies PLR and PAIRED, which are both instances of DCD. Our theoretical results on DCD then enabled us to prove that PLR attains a minimax regret policy at NE, thereby providing the first theoretical characterization of the robustness of PLR. Notably our theory leads to the counterintuitive result that PLR can be made provably robust by training on less data, specifically, by only using
the trajectories on levels sampled for replay. In addition, we developed Replay-Enhanced PAIRED (REPAIRED), which extends the selective replay-based updates of PLR⊥ to PAIRED, and proved it shares the same robustness guarantee at NE. Empirically, in two highly distinct environments, we found that PLR⊥ significantly improves zero-shot generalization over PLR, and REPAIRED, over PAIRED. As our methods solely modify the order of levels visited during training, they can, in principle, be combined with many other RL methods to yield potentially orthogonal improvements in sample-efficiency and generalization.
While these DCD-based improvements to PLR and PAIRED empirically lead to more robust policies, it is important to emphasize that our theoretical results only prove a minimax regret guarantee at NE for these methods; however, they provide no explicit guarantee of convergence to such NE. Further, it is worth highlighting that replay-based methods like PLR⊥ are completely dependent on the quality of levels proposed by the generator. Our results show that simply curating high regret levels discovered via random search is enough to outperform the RL-based PAIRED teacher in the domains studied. We expect that advancing methods for defining or adapting the generator’s proposal distribution holds great potential to improve the efficacy of our methods, especially in more complex, higher-dimensional domains, where random search may prove ineffective for finding useful training levels. Importantly, our methods assume an appropriate choice of what constitutes the UPOMDP’s free parameters. Our methods cannot be expected to produce robust policies for zero-shot transfer if the set of environments defined by the free parameters does not sufficiently align with the transfer domain of interest. Designing the environment parameterization for successful zero-shot transfer to a specific target domain can be highly non-trivial, posing an important problem for future research.
Looking beyond environment design, we notice that long-running UED processes in expansive UPDOMPs closely resemble continual learning in open-ended domains. The congruency of these settings suggests our contributions around DCD may extend to more general continual learning problems in which agents must learn to master a diverse sequence of tasks with predefined (or inferred) episode boundaries—if tasks are assumed to be designed by a regret-maximizing teacher. Thus, DCD-based methods like PLR⊥ may yield more general policies for continual learning. We anticipate many exciting crossovers between these areas of research in the years to come.
Given the rapid progress in applying RL to ever more complex domains, we can confidently expect a continued rise in real-world deployments of RL systems in the coming years. Unlike in simulation, in the real world, the environment tends to exhibit much more variability, which may not be explicitly coded into the associated simulator used for training. Deployed RL agents are thus liable to make many mistakes due to unexpected environment variations. Our methods for improving UED lead to more robust RL agents across a potentially wide range of changes to the environment. Thus, our work may prove to be a useful tool in attaining safer, more reliable RL agents, helping to enable the application of RL to more real-world problems.
By increasing the applicability of RL to real-world settings, our work may exacerbate the more general risks of deploying machine learning: increased unemployment; overreliance on biased models that potentially reinforce common misconceptions and societal inequalities; and the advancement of automated weapons. Particular to our methods, as discussed in Section 8, aligning the choice of free parameters for the UPOMDP to the target domain of interest is important for successful transfer. While this choice of free parameters then acts as a potential point of failure, the UPOMDP abstraction underlying UED reveals this problem generally impacts all RL methods aiming to train robust policies; a UPOMDP simply makes explicit the otherwise implicit space of environment configurations defined by a standard POMDP. By forcing us to consider where our training environment departs from reality, UED methods encourage designing RL systems in a way that is more aware of the underlying assumptions about the environment, thereby leading to more principled, robust systems.
Acknowledgments and Disclosure of Funding
We would like to thank Natasha Jaques, Patrick Labatut, and Heinrich Küttler for fruitful discussions that helped inform this work. Further, we are grateful to our anonymous reviewers for their valuable feedback. MJ is supported by the FAIR PhD program. This work was funded by Facebook.

title: Replay-Guided Adversarial Environment Design