[title=Index,columns=3] noclearpage

# Unifying Causal Inference and Reinforcement Learning using Higher-Order
Category Theory ††thanks: Draft under revision. Comments welcome.

Sridhar Mahadevan
Adobe Research and University of Massachusetts, Amherst
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We present a unified formalism for structure discovery of causal models and
predictive state representation (PSR) models in reinforcement learning (RL)
using higher-order category theory. Specifically, we model structure discovery
in both settings using simplicial objects, contravariant functors from the
category of ordinal numbers into any category. Fragments of causal models that
are equivalent under conditional independence – defined as causal horns – as
well as subsequences of potential tests in a predictive state representation –
defined as predictive horns – are both special cases of horns of a simplicial
object, subsets resulting from the removal of the interior and the face
opposite a particular vertex. Latent structure discovery in both settings
involve the same fundamental mathematical problem of finding extensions of
horns of simplicial objects through solving lifting problems in commutative
diagrams, and exploiting weak homotopies that define higher-order symmetries.
Solutions to the problem of filling “inner" vs “outer" horns leads to various
notions of higher-order categories, from Kan complexes to quasicategories and
$\infty$-category theory. We define the abstract problem of structure
discovery in both settings in terms of adjoint functors between the category
of universal causal models or universal decision models and its simplicial
object representation. In general, the left adjoint functor from a simplicial
object $X$ to a category ${\cal C}$ is lossy, preserving only relationships up
to a certain order defined by homotopical equivalences. In contrast, the right
adjoint defining the nerve of a category constructs a lossless encoding of a
category as a simplicial object.

_K_ eywords AI $\cdot$ Category Theory $\cdot$ Causal Inference $\cdot$
Simplicial Objects $\cdot$ Machine Learning $\cdot$ Statistics

##  1 Introduction

Figure 1: (A): In this paper, we unify structure prediction in causal
inference and RL in terms of a simplicial object $X_{n},n\geqslant 0$,
contravariant functors from ordinal numbers into a category that originated in
algebraic topology (May, 1992), but has since become the foundation for
higher-order category theory (Boardman and Vogt, 1973; Joyal, 2002; Lurie,
2022). The internal structure of $X_{n}$ involves composable morphisms of
dimension $n$. $0$th order objects in $X_{0}$ involve only identity morphisms
from an object to itself. $1$th order objects in $X_{1}$ define binary arrows
between pairs of objects. Higher-order objects in $X_{n},n\geqslant 2$, induce
higher-order relationships including symmetries. Structure discovery in causal
inference and RL is modeled as the extension problems of “filling horns",
where the horn $\Lambda^{n}_{k}$ is a subset of a contravariant functor of an
$n$-simplex that results from removing its interior and the face opposite the
$k$-vertex. (B): Predictive state horns are partial fragments of potential
tests, which can faithfully embed a category of dynamical systems into a
simplicial object, and can be seen as a special case of the nerve of a
category that defines a fully faithful embedding of arbitrary categories in
terms of simplicial objects. (C): Causal “inner" horns, fragments of causal
models, define a quasicategory (Joyal, 2002), a simplicial object where
composition of oriented $n$-simplices involves solving a lifting problem in a
commutative diagram under a weak homotopy. (D) “Outer" horns define more
general compositional structures that are analyzed in $\infty$-category theory
(Lurie, 2022).

Causal inference (Pearl, 2009a; Imbens and Rubin, 2015; Spirtes et al., 2000)
and predictive state representations (PSRs) (Singh et al., 2004) in
reinforcement learning (Sutton and Barto, 1998), whose roots go back to
earlier work on subspace identification in linear systems (Van Overschee and
De Moor, 1996) and even earlier work on algebraic theories of context-free
languages Chomsky and Schützenberger (1963) and algebraic automata theory
(Give’on and Arbib, 1968), both involve structure discovery of a latent
variable model through interventions. The use of superficially dissimilar
representations – directed acyclic graphs (DAGs) (Pearl, 1989), hybrid
undirected and directed graphs (Lauritzen and Richardson, 2002) and hyperedge
graphs (Forré and Mooij, 2017; Evans, 2018) in causal inference, versus Hankel
matrix and Hilbert space embeddings of dynamical systems – have long obscured
their deeper connections. Structure discovery in causal inference and PSRs
both involve the determination of a latent structure, which is directional at
lower orders, but homotopy equivalences at higher orders induce symmetries. In
particular, causal inference involves determining a structure, such as a DAG
that encodes direct causal effects between a pair of objects, but multiple DAG
models are equivalent because of symmetries induced by conditional
independences (Dawid, 2001; Studený et al., 2010a) and correlations induced by
latent unobservable confounders that are only revealed over higher-order
simplices (e.g., DAGs over $n\geqslant 3$ vertices). PSRs represent “hidden
state" in dynamical systems by constructing a series of tests, a free algebra
over paired actions and observation that under certain conditions is
guaranteed to faithfully embed a dynamical system without requiring the need
to explicitly construct “belief states", probability distributions over latent
states, as in a partially observable Markov decision process (POMDP). The core
tests define a minimal left k-module over an Abelian group defined as a free
algebra over all possible tests, and induce higher-order symmetries.

We formulate structure discovery of causal and PSR models in terms of
simplicial objects (see Figure 1 and Figure 2) which were originally
introduced as a combinatorial representation in algebraic topology (May,
1992), but have become the foundation for higher-order category theory
(Boardman and Vogt, 1973; Joyal, 2002; Lurie, 2022). Formally, simplicial
objects May (1992) are contravariant functors $X:\Delta^{o}\rightarrow{\cal
C}$ from the category of ordinal numbers, whose objects are
$[n]=(0,1,\ldots,n),n\geqslant 0$, and whose arrows are non-decreasing maps,
into an underlying category, such as a universal causal model (Mahadevan,
2022a), or a universal decision model (Mahadevan, 2021a). The $0$th order
simplices are objects in a universal causal model, or a universal decision
model. The $1$-simplices define arrows encoding directional relationships
between causal or decision objects. Simplicial objects of higher dimensions
$n\geqslant 2$ encode higher-order relationships between groups of objects.

The general problem of horn filling has been solved in different ways in
higher-order category theory, including weak Kan complexes Boardman and Vogt
(1973), quasi-categories (Joyal, 2002), and $\infty$-categories (Lurie, 2022).
We will review this literature, and then show the connections to structure
discovery in causal inference and RL. Structure prediction in causal inference
and RL both can be formulated as filling horns of simplicial objects, subsets
of functors that result from interventions that removes the interior and the
face opposite a given vertex. These interventions can be defined in terms of a
sequence of elementary order-preserving morphisms in the category of ordinal
numbers $\Delta$, whose objects are the ordinals $[n]=\\{0,1,\ldots,n\\}$ and
whose arrows are defined as compositions of elementary injections
$d_{i}:[n-1]\rightarrow[n]$ and elementary surjections
$s_{i}:[n]\rightarrow[n-1]$ (see Figure 2). In particular, the units in a
causal study or the states of an underlying dynamical system are
$x,y,\ldots\in X_{0}$, the $0$-simplices of $X$. If $x,y\in X_{0}$, and $f\in
X_{1}$, we denote a potential causal effect or action in a dynamical system by
the arrow $f:x\rightarrow y$ to denote that $x=d_{1}f$ and $y=d_{0}f$. Here,
$d_{i}$ is an elementary injection $d_{i}:[n-1]\rightarrow[n]$ that skips
element $i$. The set of potential causal influences or actions between $x$ and
$y$ is denoted as $X_{1}(x,y)$. The degenerate $s_{0}x$ denotes the unit
morphism (a cycle) mapping ${\bf 1}_{x}:x\rightarrow x$, where
$s_{i}:[n]\rightarrow[n=1]$ is the elementary surjection that repeats element
$i\in[n]$. Higher-order simplices $X_{i},i\geqslant 2$ are used to capture
higher-order causal effects or action transitions among groups of causal
objects or dynamical system states of size $n>2$. Note in Figure 1, there is
one arrow out of $X_{0}$, denoting the self-mapping from an object to itself.
The two arrows from $X_{1}$ to $X_{0}$ represent the head and tail of each
morphism in $X_{1}$. There are in general $n+1$ arrows in and out of $X_{n}$,
for $n>0$. For example, $X_{2}$ has three arrows going back into $X_{1}$,
because those are the three arrows that are contained in the $2$-simplex.

##  2 Simplicial Objects

Simplicial objects have long been a foundation for algebraic topology (May,
1999, 1992), and more recently higher-order category theory (Boardman and
Vogt, 1973; Joyal, 2002; Lurie, 2022). The category $\Delta$ has non-empty
ordinals $[n]=\\{0,1,\ldots,n]$ as objects, and order-preserving maps
$[m]\rightarrow[n]$ as arrows. An important property in $\Delta$ is that any
mapping is decomposable as a composition of an injective and a surjective
mapping, each of which is decomposable into a sequence of elementary
injections $d_{i}:[n]\rightarrow[n+1]$, which omits $i\in[n]$, and a sequence
of elementary surjections $s_{i}:[n]\rightarrow[n-1]$, which repeats
$i\in[n]$. The fundamental simplex $\Delta([n])$ is the presheaf of all
morphisms into $[n]$, that is, the representable functor $\Delta(-,[n])$. 111A
representable functor is one that can be faithfully embedded in the category
of Sets.

We will denote simplicial objects over the category of sets by $X[n]=X_{n}$ to
mean the functor $[n]\rightarrow X$, mapping both the objects
$[n]=\\{0,1,\ldots,n\\}$ as well as its morphisms to a set $X$. Thus, $X_{0}$
is a set of objects, which are mappings from $[0]=\\{0\\}$ to $X$, and as
$[0]$ contains only one element, each such mapping must pick out a single
element of $X$. Note that as the only morphism in $[0]$ is $0\rightarrow 0$,
its image gives the identity mapping on each element in the set $X$.
Similarly, $X_{1}$ is the functor mapping $[1]=\\{0,1\\}$ and its non-identity
morphism $0\rightarrow 1$ to $X$, which defines arrows between elements of
$X_{0}$. Proceeding, $X[2]$ is the functor mapping $[2]=\\{0,1,2\\}$, with its
non-identity morphisms $0\rightarrow 1,1\rightarrow 2,0\rightarrow 2$ into a
category, so it picks out “triangles", or oriented simplices of order $2$.

The Yoneda Lemma MacLane (1971) assures us that an $n$-simplex $x\in X_{n}$
can be identified with the corresponding map $\Delta[n]\rightarrow X$. Every
morphism $f:[n]\rightarrow[m]$ in $\Delta$ is functorially mapped to the map
$\Delta[m]\rightarrow\Delta[n]$ in ${\cal S}$. Figure 2) illustrates
simplicial objects, in particular showing that any order-preserving morphism
can be decomposed into a sequence of elementary degeneracy and face operators.
222The Latex source for this diagram in is from
http://homepages.math.uic.edu/$\sim$jlv/seminars/infinitycats/inftycats.tex.

Category $\Delta$: | Objects are the ordinal numbers $[n]=(0,1,\dots,n)$ |
---|---|---
| Arrows are non-decreasing maps $[n]\to[m]$
_Elementary coface maps_ : |  $s_{i}:[n]\to[n-1]$, repeat $i$ twice in the co-domain |
_Elementary codegeneracy maps_ : |  $d_{i}:[n]\to[n+1]$, skips $i$ in the co-domain |
| Any arrow $[m]\rightarrow[n]$ is composed of elementary face and degeneracy maps: |
|
$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$s_{1}$$d_{1}$$d_{2}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$d_{1}$$s_{2}$$d_{2}$isor
$[n]$: | Objects are numbers $0,1,\dots,n$ |
|  $|\textup{Hom}_{[n]}(a,b)|=1$ iff $a\leqslant b$, else $\emptyset$ |
Simplicial set: sSet: | ${\bf Hom}_{\Delta}(\Delta^{op},\textup{Set})$ |
| Objects are functors $S=\\{S_{n}=S([n])\\}_{n\geqslant 0}$ with
|  _face maps_ $S(s_{i}):S_{n}\to S_{n+1}$ |
|  _degeneracy maps_ $S(d_{i}):S_{n}\to S_{n-1}$ |
| Morphisms $f:S\to T$ are natural transformations
Simplicial object: sObj: |  ${\bf Hom}_{\Delta}(\Delta^{op},C)$ for $C$ any category |
Figure 2: Simplicial objects are contravariant functors from ordinal numbers
into any category.

Any morphism in the category $\Delta$ can be defined as a sequence of
degeneracy and face operators, where the degeneracy operator
$\delta_{i}:[n-1]\rightarrow[n],0\leqslant i\leqslant n$ is defined as:

$\delta_{i}(j)=\left\\{\begin{array}[]{ll}j,&\mbox{for }\ 0\leqslant
j\leqslant i-1\\\ j+1&\mbox{for }\ i\leqslant j\leqslant
n-1\end{array}\right.$

Analogously, the face operator $\sigma_{j}:[n+1]\rightarrow[n]$ is defined as

$\sigma_{j}(k)=\left\\{\begin{array}[]{ll}j,&\mbox{for }\ 0\leqslant
k\leqslant j\\\ k-1&\mbox{for }\ j<k\leqslant n+1\end{array}\right.$

The compositions of these arrows define certain well-known properties (May,
1992; Richter, 2020):

$\displaystyle\delta_{j}\circ\delta_{i}$ $\displaystyle=$
$\displaystyle\delta_{i}\circ\delta_{j-1},\ \ i<j$
$\displaystyle\sigma_{j}\circ\sigma_{i}$ $\displaystyle=$
$\displaystyle\sigma_{i}\circ\sigma_{j+1},\ \ i\leqslant j$
$\displaystyle\sigma_{j}\circ\delta_{i}(j)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\sigma_{i}\circ\sigma_{j+1},&\mbox{for
}\ i<j\\\ 1_{[n]}&\mbox{for }\ i=j,j+1\\\
\sigma_{i-1}\circ\sigma_{j},\mbox{for}\ i>j+1\end{array}\right.$

######  Definition 1.

The set of all functors $[n]\rightarrow{\cal C}$ for any category ${\cal C}$
is denoted as ${\cal N}_{n}({\cal C})$. The image of each abstract face
operator $\sigma_{j}:[n+1]\rightarrow[n]$ under the covariant functor
$N_{n}({\cal C})$ is denoted as $N_{n}(\sigma_{j})=d_{j}$, and the image of
each abstract degeneracy operator $\delta_{i}:[n-1]\rightarrow[n]$ under the
covariant functor $N_{n}({\cal C})$ is given as $N_{n}(\delta_{i})=s_{i}$.

###  2.1 Full and Faithful Embedding of Categories

######  Definition 2.

A covariant functor $F:{\cal C}\rightarrow{\cal D}$ from category ${\cal C}$
to category ${\cal D}$, and defined as the following:

  * •

An object $FX$ (sometimes written as $F(x)$) of the category ${\cal D}$ for
each object $X$ in category ${\cal C}$.

  * •

An arrow $F(f):FX\rightarrow FY$ in category ${\cal D}$ for every arrow
$f:X\rightarrow Y$ in category ${\cal C}$.

  * •

The preservation of identity and composition: $F\ id_{X}=id_{FX}$ and
$(Ff)(Fg)=F(g\circ f)$ for any composable arrows $f:X\rightarrow
Y,g:Y\rightarrow Z$.

######  Definition 3.

A contravariant functor $F:{\cal C}\rightarrow{\cal D}$ from category ${\cal
C}$ to category ${\cal D}$ is defined exactly like the covariant functor,
except all the arrows are reversed. In the contravariant
functor$F:C^{\mbox{op}}\rightarrow D$, every morphism $f:X\rightarrow Y$ is
assigned the reverse morphism $Ff:FY\rightarrow FX$ in category ${\cal D}$.

  * •

For every object $X$ in a category ${\cal C}$, there exists a covariant
functor ${\cal C}(X,-):{\cal C}\rightarrow{\bf Set}$ that assigns to each
object $Z$ in ${\cal C}$ the set of morphisms ${\cal C}(X,Z)$, and to each
morphism $f:Y\rightarrow Z$, the pushforward mapping $f_{*}:{\cal
C}(X,Y)\rightarrow{\cal C}(X,Z)$.

  * •

For every object $X$ in a category ${\cal C}$, there exists a contravariant
functor ${\cal C}(-,X):{\cal C}^{\mbox{op}}\rightarrow{\bf Set}$ that assigns
to each object $Z$ in ${\cal C}$ the set of morphisms Hom${}_{\cal C}(X,Z)$,
and to each morphism $f:Y\rightarrow Z$, the pullback mapping $f^{*}:$
Hom${}_{\cal C}(Z,X)\rightarrow{\cal C}(Y,X)$. Note how “contravariance"
implies the morphisms in the original category are reversed through the
functorial mapping, whereas in covariance, the morphisms are not flipped.

######  Definition 4.

Let ${\cal F}:{\cal C}\rightarrow{\cal D}$ be a functor from category ${\cal
C}$ to category ${\cal D}$. If for all arrows $f$ the mapping $f\rightarrow
Ff$

  * •

injective, then the functor ${\cal F}$ is defined to be faithful.

  * •

surjective, then the functor ${\cal F}$ is defined to be full.

  * •

bijective, then the functor ${\cal F}$ is defined to be fully faithful.

######  Definition 5.

A pair of adjoint functors is defined as $F:{\cal C}\rightarrow{\cal D}$ and
$G:{\cal D}\rightarrow{\cal C}$, where $F$ is considered the right adjoint,
and $G$ is considered the left adjoint.

${{\cal
D}}$${\mathbf{C}.}$$\scriptstyle{G}$$\scriptstyle{F}$${\scriptscriptstyle\boldsymbol{\top}}$

######  Definition 6.

The nerve of a category ${\cal C}$ is the set of composable morphisms of
length $n$, for $n\geqslant 1$. Let $N_{n}({\cal C})$ denote the set of
sequences of composable morphisms of length $n$.

$\\{C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}\
|\ C_{i}\ \mbox{is an object in}\ {\cal C},f_{i}\ \mbox{is a morphism in}\
{\cal C}\\}$

The set of $n$-tuples of composable arrows in C, denoted by $N_{n}({\cal C})$,
can be viewed as a functor from the simplicial object $[n]$ to ${\cal C}$.
Note that any nondecreasing map $\alpha:[m]\rightarrow[n]$ determines a map of
sets $N_{m}({\cal C})\rightarrow N_{n}({\cal C})$. The nerve of a category C
is the simplicial set $N_{\bullet}:\Delta\rightarrow N_{n}({\cal C})$, which
maps the ordinal number object $[n]$ to the set $N_{n}({\cal C})$.

The importance of the nerve of a category comes from a key result Lurie
(2022), showing it defines a full and faithful embedding of a category:

######  Theorem 1.

(Lurie, 2022, Tag 002Y): The nerve functor $N_{\bullet}:{\bf
Cat}\rightarrow{\bf Set}$ is fully faithful. More specifically, there is a
bijection $\theta$ defined as:

$\theta:{\bf Cat}({\cal C},{\cal C^{\prime}})\rightarrow{\bf
Set}_{\Delta}(N_{\bullet}({\cal C}),N_{\bullet}({\cal C^{\prime}})$

In general, the functor $G$ from a simplicial object $X$ to a category ${\cal
C}$ can be lossy. For example, we can define the objects of ${\cal C}$ to be
the elements of $X_{0}$, and the morphisms of ${\cal C}$ as the elements $f\in
X_{1}$, where $f:a\rightarrow b$, and $d_{0}f=a$, and $d_{1}f=b$, and
$s_{0}a,a\in X$ as defining the identity morphisms ${\bf 1}_{a}$. Composition
in this case can be defined as the free algebra defined over elements of
$X_{1}$, subject to the constraints given by elements of $X_{2}$. For example,
if $x\in X_{2}$, we can impose the requirement that $d_{1}x=d_{0}x\circ
d_{2}x$. Such a definition of the left adjoint would be quite lossy because it
only preserves the structure of the simplicial object $X$ up to the
$2$-simplices. The right adjoint from a category to its associated simplicial
object, in contrast, constructs a full and faithful embedding of a category
into a simplicial set. In particular, the nerve of a category is such a right
adjoint.

######  Example 1.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
$N_{n}({\cal C})$, which we can identify with the sequence:

$\sigma=C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}$

the face operator $d_{0}$ applied to $\sigma$ yields the sequence

$d_{0}\sigma=C_{1}\xrightarrow[]{f_{2}}C_{2}\xrightarrow[]{f_{3}}\ldots\xrightarrow[]{f_{n}}C_{n}$

where the object $C_{0}$ is “deleted" along with the morphism $f_{0}$ leaving
it.

######  Example 2.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
$N_{n}({\cal C})$, which we can identify with the sequence:

$\sigma=C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}$

the face operator $d_{n}$ applied to $\sigma$ yields the sequence

$d_{n}\sigma=C_{0}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n-1}}C_{n-1}$

where the object $C_{n}$ is “deleted" along with the morphism $f_{n}$ entering
it.

######  Example 3.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
$N_{n}({\cal C})$, which we can identify with the sequence:

$\sigma=C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}$

the face operator $d_{i},0<i<n$ applied to $\sigma$ yields the sequence

$d_{i}\sigma=C_{0}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots
C_{i-1}\xrightarrow[]{f_{i+1}\circ
f_{i}}C_{i+1}\ldots\xrightarrow[]{f_{n}}C_{n}$

where the object $C_{i}$ is “deleted" and the morphisms $f_{i}$ is composed
with morphism $f_{i+1}$.

######  Example 4.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
$N_{n}({\cal C})$, which we can identify with the sequence:

$\sigma=C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}$

the degeneracy operator $s_{i},0\leqslant i\leqslant n$ applied to $\sigma$
yields the sequence

$s_{i}\sigma=C_{0}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots
C_{i}\xrightarrow[]{{\bf
1}_{C_{i}}}C_{i}\xrightarrow[]{f_{i+1}}C_{i+1}\ldots\xrightarrow[]{f_{n}}C_{n}$

where the object $C_{i}$ is “repeated" by inserting its identity morphism
${\bf 1}_{C_{i}}$.

######  Definition 7.

Given a category ${\cal C}$, and an $n$-simplex $\sigma$ of the simplicial set
$N_{n}({\cal C})$, which we can identify with the sequence:

$\sigma=C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}$

we define $\sigma$ as a degenerate simplex if some $f_{i}$ in the above
sequence is an identity morphism, in which case $C_{i}$ and $C_{i+1}$ are
equal.

##  3 Horns of Simplicial Objects

One of the fundamental contributions of this paper is to show that structure
discovery in causal inference and RL both involve solving extensions problems
defined by commutative diagrams, which are defined as “horn filling" in
higher-order category theory (Boardman and Vogt, 1973; Joyal, 2002; Lurie,
2022).

###  3.1 Simplicial Subsets and Horns

We now describe ways of modeling subsets of simplicial objects, which are
simplicial objects in their own right. We introduce the crucial concept of the
boundary and horn of a simplicial set.

######  Definition 8.

The standard simplex $\Delta^{n}$ is the simplicial set defined by the
construction

$([m]\in\Delta)\mapsto{\bf Hom}_{\Delta}([m],[n])$

By convention, $\Delta^{-1}\coloneqq\emptyset$. The standard $0$-simplex
$\Delta^{0}$ maps each $[n]\in\Delta^{op}$ to the single element set
$\\{\bullet\\}$.

######  Definition 9.

Let $S_{\bullet}$ denote a simplicial set. If for every integer $n\geqslant
0$, we are given a subset $T_{n}\subseteq S_{n}$, such that the face and
degeneracy maps

$d_{i}:S_{n}\rightarrow S_{n-1}\ \ \ \ s_{i}:S_{n}\rightarrow S_{n+1}$

applied to $T_{n}$ result in

$d_{i}:T_{n}\rightarrow T_{n-1}\ \ \ \ s_{i}:T_{n}\rightarrow T_{n+1}$

then the collection $\\{T_{n}\\}_{n\geqslant 0}$ defines a simplicial subset
$T_{\bullet}\subseteq S_{\bullet}$

######  Definition 10.

The boundary is a simplicial set
$(\partial\Delta^{n}):\Delta^{op}\rightarrow{\bf Set}$ defined as

$(\partial\Delta^{n})([m])=\\{\alpha\in{\bf Hom}_{\Delta}([m],[n]):\alpha\
\mbox{is not surjective}\\}$

Note that the boundary $\partial\Delta^{n}$ is a simplicial subset of the
standard $n$-simplex $\Delta^{n}$.

######  Definition 11.

The Horn $\Lambda^{n}_{i}:\Delta^{op}\rightarrow{\bf Set}$ is defined as

$(\Lambda^{n}_{i})([m])=\\{\alpha\in{\bf
Hom}_{\Delta}([m],[n]):[n]\not\subseteq\alpha([m])\cup\\{i\\}\\}$

Intuitively, the Horn $\Lambda^{n}_{i}$ can be viewed as the simplicial subset
that results from removing the interior of the $n$-simplex $\Delta^{n}$
together with the face opposite its $i$th vertex. Lifting problems provide
elegant ways to define basic notions in a wide variety of areas in
mathematics. For example, the notion of injective and surjective functions,
the notion of separation in topology, and many other basic constructs can be
formulated as solutions to lifting problems.

Let us illustrate this abstract definition with the following diagrams.
Consider the problem of composing $1$-dimensional simplices to form a
$2$-dimensional simplicial object. Each simplicial subset of an $n$-simplex
induces a a horn $\Lambda^{n}_{k}$, where $0\leqslant k\leqslant n$.
Intuitively, a horn is a subset of a simplicial object that results from
removing the interior of the $n$-simplex and the face opposite the $i$th
vertex. Consider the three horns defined below. The dashed arrow
$\dashrightarrow$ indicates edges of the $2$-simplex $\Delta^{2}$ not
contained in the horns.

${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$

The inner horn $\Lambda^{2}_{1}$ is the middle diagram above, and admits an
easy solution to the “horn filling" problem of composing the simplicial
subsets. The two outer horns on either end pose a more difficult challenge. A
considerable elaboration of the theoretical machinery in category theory is
required to describe the various solutions proposed, which led to different
ways of defining higher-order category theory (Boardman and Vogt, 1973; Joyal,
2002; Lurie, 2022), which we summarize below.

######  Definition 12.

Let ${\cal C}$ be a category. A lifting problem in ${\cal C}$ is a commutative
diagram $\sigma$ in ${\cal C}$.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}p}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,1}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\nu}$

######  Definition 13.

Let ${\cal C}$ be a category. A solution to a lifting problem in ${\cal C}$ is
a morphism $h:B\rightarrow X$ in ${\cal C}$ satisfying $p\circ h=\nu$ and
$h\circ f=\mu$ as indicated in the diagram below.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}p}$$\scriptstyle{h}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,1}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\nu}$

######  Definition 14.

Let ${\cal C}$ be a category. If we are given two morphisms $f:A\rightarrow B$
and $p:X\rightarrow Y$ in ${\cal C}$, we say that $f$ has the left lifting
property with respect to $p$, or that p has the right lifting property with
respect to f if for every pair of morphisms $\mu:A\rightarrow X$ and
$\nu:B\rightarrow Y$ satisfying the equations $p\circ\mu=\nu\circ f$, the
associated lifting problem indicated in the diagram below.

${A}$${X}$${B}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}p}$$\scriptstyle{h}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,1}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\nu}$

admits a solution given by the map $h:B\rightarrow X$ satisfying $p\circ
h=\nu$ and $h\circ f=\mu$.

######  Example 5.

Given the paradigmatic non-surjective morphism
$f:\emptyset\rightarrow\\{\bullet\\}$, any morphism p that has the right
lifting property with respect to f is a surjective mapping.

${\emptyset}$${X}$${\\{\bullet\\}}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}p}$$\scriptstyle{h}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,1}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\nu}$

######  Example 6.

Given the paradigmatic non-injective morphism
$f:\\{\bullet,\bullet\\}\rightarrow\\{\bullet\\}$, any morphism p that has the
right lifting property with respect to f is an injective mapping.

${\\{\bullet,\bullet\\}}$${X}$${\\{\bullet\\}}$${Y}$$\scriptstyle{f}$$\scriptstyle{\mu}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}p}$$\scriptstyle{h}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,1}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\nu}$

######  Definition 15.

If $S$ is a collection of morphisms in category ${\cal C}$, a morphism
$f:A\rightarrow B$ has the left lifting property with respect to S if it has
the left lifting property with respect to every morphism in $S$. Analogously,
we say a morphism $p:X\rightarrow Y$ has the right lifting property with
respect to S if it has the right lifting property with respect to every
morphism in $S$.

######  Definition 16.

Let $C$ and $C^{\prime}$ be a pair of objects in a category ${\cal C}$. We say
$C$ is a retract of $C^{\prime}$ if there exists maps $i:C\rightarrow
C^{\prime}$ and $r:C^{\prime}\rightarrow C$ such that $r\circ
i=\mbox{id}_{\cal C}$.

######  Definition 17.

Let ${\cal C}$ be a category. We say a morphism $f:C\rightarrow D$ is a
retract of another morphism $f^{\prime}:C\rightarrow D$ if it is a retract of
$f^{\prime}$ when viewed as an object of the functor category ${\bf
Hom}([1],{\cal C})$. A collection of morphisms $T$ of ${\cal C}$ is closed
under retracts if for every pair of morphisms $f,f^{\prime}$ of ${\cal C}$, if
$f$ is a retract of $f^{\prime}$, and $f^{\prime}$ is in $T$, then $f$ is also
in $T$.

###  3.2 Fibrations and Kan Complexes

######  Definition 18.

Let $f:X\rightarrow S$ be a morphism of simplicial sets. We say $f$ is a Kan
fibration if, for each $n>0$, and each $0\leqslant i\leqslant n$, every
lifting problem

${\Lambda^{n}_{i}}$${X}$${\Delta^{n}}$${S}$$\scriptstyle{\sigma_{0}}$$\scriptstyle{\definecolor[named]{.}{rgb}{1,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}f}$$\scriptstyle{\sigma}$$\scriptstyle{\definecolor[named]{.}{rgb}{0,0,1}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\bar{\sigma}}$

admits a solution. More precisely, for every map of simplicial sets
$\sigma_{0}:\Lambda^{n}_{i}\rightarrow X$ and every $n$-simplex
$\bar{\sigma}:\Delta^{n}\rightarrow S$ extending $f\circ\sigma_{0}$, we can
extend $\sigma_{0}$ to an $n$-simplex $\sigma:\Delta^{n}\rightarrow X$
satisfying $f\circ\sigma=\bar{\sigma}$.

######  Example 7.

Given a simplicial set $X$, then a projection map $X\rightarrow\Delta^{0}$
that is a Kan fibration is called a Kan complex.

######  Example 8.

Any isomorphism between simplicial sets is a Kan fibration.

######  Example 9.

The collection of Kan fibrations is closed under retracts.

######  Definition 19.

Let X and Y be simplicial sets, and suppose we are given a pair of morphisms
$f_{0},f_{1}:X\rightarrow Y$. A homotopy from $f_{0}$ to $f_{1}$ is a morphism
$h:\Delta^{1}\times X\rightarrow Y$ satisfying $f_{0}=h|_{{0}\times X}$ and
$f_{1}=h_{1\times X}$.

###  3.3 Higher-order Categories

We now formally introduce higher-order categories, building on the framework
proposed in a number of formalisms (Boardman and Vogt, 1973; Joyal, 2002;
Lurie, 2022).

######  Definition 20.

(Lurie, 2022) An $\infty$-category is a simplicial object $S_{\bullet}$ which
satisfies the following condition:

  * •

For $0<i<n$, every map of simplicial sets
$\sigma_{0}:\Lambda^{n}_{i}\rightarrow S_{\bullet}$ can be extended to a map
$\sigma:\Delta^{n}\rightarrow S_{\bullet}$.

This definition emerges out of a common generalization of two other conditions
on a simplicial set $S_{i}$:

  1. 1.

Property K: For $n>0$ and $0\leqslant i\leqslant n$, every map of simplicial
sets $\sigma_{0}:\Lambda^{n}_{i}\rightarrow S_{\bullet}$ can be extended to a
map $\sigma:\Delta^{n}\rightarrow S_{\bullet}$.

  2. 2.

Property C: for $0<1<n$, every map of simplicial sets
$\sigma_{0}:\Lambda^{n}_{i}\rightarrow S_{i}$ can be extended uniquely to a
map $\sigma:\Delta^{n}\rightarrow S_{\bullet}$.

Simplicial objects that satisfy property K were defined above to be Kan
complexes. Simplicial objects that satisfy property C above can be identified
with the nerve of a category, which yields a full and faithful embedding of a
category in the category of sets. Definition 20 generalizes both of these
definitions, and was called a quasicategory in (Joyal, 2002) and weak Kan
complexes in (Boardman and Vogt, 1973) when ${\cal C}$ is a category.

##  4 Universal Reinforcement Learning

In this section, we briefly review the framework of universal decision models
(Mahadevan, 2021a), where a decision making object is defined as a particular
type of category. We will focus in particular on predictive state
representations (PSRs) Singh et al. (2004), but we will include a brief review
of Markov decision processes (MDPs), which are a stochastic dynamical system
widely used in the literature on reinforcement learning. We show that
predictive state representations define a simplicial object representation of
a category, and prove the Universal PSR theorem based on the fact that the
nerve of a PSR defines a full and faithful embedding of the category of PSRs
in the category of sets. We show that simplicial object representations of
PSRs define a quasicategory.

###  4.1  UDMs based on Markov Decision Processes

We now briefly describe the category of UDMs, where each object represents a
(finite) Markov decision process (MDP) (Puterman, 1994). Recall that an MDP is
defined by a tuple $\langle S,A,\Psi,P,R\rangle$, where $S$ is a discrete set
of states, $A$ is the discrete set of actions, $\Psi\subset S\times A$ is the
set of admissible state-action pairs, $P:\Psi\times S\rightarrow[0,1]$ is the
transition probability function specifying the one-step dynamics of the model,
where $P(s,a,s^{\prime})$ is the transition probability of moving from state
$s$ to state $s^{\prime}$ in one step under action $a$, and
$R:\Psi\rightarrow\mathbb{R}$ is the expected reward function, where $R(s,a)$
is the expected reward for executing action $a$ in state $s$. MDP
homomorphisms can be viewed as a principled way of abstracting the state
(action) set of an MDP into a “simpler" MDP that nonetheless preserves some
important properties, usually referred to as the stochastic substitution
property (SSP).

######  Definition 21.

A UDM MDP homomorphism (Ravindran and Barto, 2003) from object $M=\langle
S,A,\Psi,P,R\rangle$ to $M^{\prime}=\langle
S^{\prime},A^{\prime},\Psi^{\prime},P^{\prime},R^{\prime}\rangle$, denoted
$h:M\twoheadrightarrow M^{\prime}$, is defined by a tuple of surjections
$\langle f,\\{g_{s}|s\in S\\}\rangle$, where $f:S\twoheadrightarrow
S^{\prime},g_{s}:A_{s}\twoheadrightarrow A^{\prime}_{f(s)}$, where
$h((s,a))=\langle f(s),g_{s}(a)\rangle$, for $s\in S$, such that the
stochastic substitution property and reward respecting properties below are
respected:

$\displaystyle
P^{\prime}(f(s),g_{s}(a),f(s^{\prime}))=\sum_{s"\in[s^{\prime}]_{f}}P(s,a,s")$
(2) $\displaystyle R^{\prime}(f(s),g_{s}(a))=R(s,a)$ (3)

Given this definition, the following result is straightforward to prove.

######  Theorem 2.

The UDM category ${\cal C}_{\mbox{MDP}}$ is defined as one where each object
$c$ is defined by an MDP, and morphisms are given by MDP homomorphisms defined
by Equation 2.

Proof: Note that the composition of two MDP homomorphisms $h:M_{1}\rightarrow
M_{2}$ and $h^{\prime}:M_{2}\rightarrow M_{3}$ is once again an MDP
homomorphism $h^{\prime}\circ h:M_{1}\rightarrow M_{3}$. The identity
homomorphism is easy to define, and MDP homomorphisms, being surjective
mappings, obey associative properties. ∎

###  4.2 UDM Category of Predictive State Representations

Figure 3: Left: A predictive state representation (PSR) can be defined in
terms of its underlying systems dynamics matrix (Singh et al., 2004). The
columns of this (infinite) matrix are tests $t=a_{1}o_{1}\ldots a_{n}o_{n}$
and the rows are histories $h=a_{1}o_{1}\ldots a_{k}o_{k}$. Right: the
simplicial object encoded by a PSR. $T_{n}$ represents the $n$-simplicial
object of tests or histories, and $P_{n}$ represents a symmetric monoidal
category Fong and Spivak (2018) that can be used to encode conditional
probabilities $P(t|h)$ of each test $t$ given its history $h$. Note that as in
Figure 2, there are $n$ arrows leading from the $n$-simplex $T_{n}$ back to
the $n-1$ simplex $T_{n-1}$ as well as to the $n+1$-simplex $T_{n+1}$, which
are not shown for clarity. The conditional probability for each test $t$ as a
function of history $h$, $P(t|h)$ can be defined using an enriched symmetric
monoidal category, exactly as defined in (Bradley et al., 2022), which defines
sentence completions in English by deep NLP networks using conditional
probabilities as enriched categories.

We now define the UDM (sub)category ${\cal C}_{\mbox{PSR}}$ of predictive
state representations (Thon and Jaeger, 2015), based on the notion of
homomorphism defined for PSRs proposed in (Soni and Singh, 2007). Recall that
a PSR is (in the simplest case) a discrete controlled dynamical system,
characterized by a finite set of actions $A$, and observations $O$. At each
clock tick $t$, the agent takes an action $a_{t}$ and receives an observation
$o_{t}\in O$. A history is defined as a sequence of actions and observations
$h=a_{1}o_{1}\ldots a_{k}o_{k}$. A test is a possible sequence of future
actions and observations $t=a_{1}o_{1}\ldots a_{n}o_{n}$. A test is successful
if the observations $o_{1}\ldots o_{n}$ are observed in that order, upon
execution of actions $a_{1}\ldots a_{n}$. The probability $P(t|h)$ is a
prediction of that a test $t$ will succeed from history $h$.

A state $\psi$ in a PSR is a vector of predictions of a suite of core tests
$\\{q_{1},\ldots,q_{k}\\}$. The prediction vector $\psi_{h}=\langle
P(q_{1}|h)\ldots P(q_{k}|h)\rangle$ is a sufficient statistic, in that it can
be used to make predictions for any test. More precisely, for every test $t$,
there is a $1\times k$ projection vector $m_{t}$ such that
$P(t|h)=\psi_{h}.m_{t}$ for all histories $h$. The entire predictive state of
a PSR can be denoted $\Psi$.

######  Definition 22.

In the UDM category ${\cal C}_{\mbox{PSR}}$ defined by PSR objects, the
morphism from object $\Psi$ to another $\Psi^{\prime}$ is defined by a tuple
of surjections $\langle f,v_{\psi}(a)\rangle$, where
$f:\Psi\rightarrow\Psi^{\prime}$ and $v_{\psi}:A\rightarrow A^{\prime}$ for
all prediction vectors $\psi\in\Psi$ such that

$P(\psi^{\prime}|f(\psi),v_{\psi}(a))=P(f^{-1}(\psi^{\prime})|\psi,a)$ (4)

for all $\psi^{\prime}\in\Psi,\psi\in\Psi,a\in A$.

######  Theorem 3.

The UDM category ${\cal C}_{\mbox{PSR}}$ is defined by making each object $c$
represent a PSR, where the morphisms between two PSRs $h:c\rightarrow d$ is
defined by the PSR homomorphism defined in (Soni and Singh, 2007).

Proof: Once again, given the homomorphism definition in Definition 22, the UDM
category ${\cal P}_{\mbox{PSR}}$ is easy to define, given the surjectivity of
the associated mappings $f$ and $v_{\psi}$. ∎

###  4.3 PSR Test Discovery as Horn Filling of a Simplicial Object

The extensive literature on PSRs has explored ways of constructing the set of
core tests needed to serve as a sufficient statistic for a full and faithful
embedding of any dynamical system that can be represented as a PSR. Here, we
just want to illustrate that the process of elaborating a partial test
$t=a_{1}o_{1}\ldots a_{i}o_{i}$ by adding a new candidate action observation
pair $a_{i+1}o_{i+1}$ can be viewed as filling the horn of a simplicial
object.

######  Definition 23.

A predictive horn of a PSR $\Lambda^{n}_{i}:\Delta^{op}\rightarrow{\cal
C}_{PSR}$ is defined as as the simplicial subset of the functor mapping $[n]$
to the category ${\cal C}_{PSR}$ defining a PSR model. Recall the horn removes
the interior of an $n$-simplex $\Delta^{n}$ together with the face opposite
its $i$th vertex.

Let us illustrate this notion of horn filling using the same diagram as shown
earlier, but this time, interpreting the morphisms shown below as tests in a
PSR.

${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$

The inner horn $\Lambda^{2}_{1}$ is the middle diagram above, and admits an
easy solution to the “horn filling" problem of composing the simplicial
subsets. The two outer horns on either end pose a more difficult challenge.
Stated in the language of PSRs, the inner horn filling problem represents the
problem of composing two tests, defined as images of abstract tests
$t_{01}:0\rightarrow 1$ and $t_{12}:1\rightarrow 2$ into the category defined
by a PSR. Each image of an abstract test leads to an actual test in a PSR
model, for example $F(t_{01})=a_{i}o_{i}$ and $F(t_{12})=a_{j}o_{j}$. These
two tests can be composed to form a test $F(t_{01}\circ
t_{12})=F(t_{02})=a_{i}o_{i}a_{j}o_{j}$. The outer horn filling problem, in
contrast, involves inducing a missing test that “fills in" between a test of
length $2$ and a test of length $1$.

First, let us define more precisely how to construct the associated simplicial
object from a PSR. We can define this construction following the systems
dynamics matrix in Figure 3. Both tests and histories are viewed as
$n$-simplices, constructed from sequences of action-observation pairs. For
example, in Figure 3, the $1$-simplex encodes a unit test or history
$a_{i}o_{j}$ of a single action observation pair. The conditional
probabilities $P(t|h)$ of each test $t$ given its history $h$ is defined using
an enriched symmetric monoidal category $P$. Basically, we are treating the
process of combining a test $t$ with a history $h$ as a morphism from $h$ to
$t\circ h$. The set of all morphisms ${\bf Hom}_{\cal C}(h,th)$ is defined as
an enriched symmetric monoidal category that can encode conditional
probabilities. (Bradley et al., 2022) gives a detailed treatment of how to
model conditional probabilities for the problem of defining the compositional
structure of deep NLP models, where for each fragment of an English sentence,
like $h=$ “I went to the grocery store…", each possible completion, such as
$t=$ “to get some milk" is defined as a conditional probability $P(t|h)$. This
problem is exactly the same as defining the conditional probability of PSR
tests, and we refer the reader to (Bradley et al., 2022) for additional
details.

######  Definition 24.

The nerve of a PSR ${\cal C}$ is the set of sequences of composable tests of
length $n$, for $n\geqslant 1$. Let $N_{n}({\cal C})$ denote the set of
sequences of composable tests

$\\{C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}\
|\ C_{i}\ \mbox{is an object in}\ {\cal C},f_{i}\ \mbox{is a morphism in}\
{\cal C}\\}$

${{\cal N}_{PSR}({\cal
C})}$${\mathbf{C}_{PSR}.}$$\scriptstyle{G}$$\scriptstyle{F}$${\scriptscriptstyle\boldsymbol{\top}}$

We can use this result to abstractly define a universal PSR theorem, which
states that any PSR can be defined completely by its nerve.

######  Theorem 4.

Universal PSR Theorem: The nerve functor defined by a PSR $N_{\bullet}:{\bf
Cat}_{PSR}\rightarrow{\bf Set}$ is fully faithful. More specifically, there is
a bijection $\theta$ defined as:

$\theta:{\bf Cat}({\cal C}_{PSR},{\cal C^{\prime}}_{PSR})\rightarrow{\bf
Set}_{\Delta}(N_{\bullet}({\cal C}_{PSR}),N_{\bullet}({\cal
C^{\prime}}_{PSR})$

######  Theorem 5.

PSRs form a quasicategory: The nerve functor defined by a PSR
$N_{\bullet}:{\bf Cat}_{PSR}\rightarrow{\bf Set}$ forms a quasicategory Joyal
(2002).

Proof: The proof of both theorems follows directly from more basic results
establishing that the nerve of a category is a fully faithful embedding of it.
Since we showed above in Theorem 3 that PSRs form a category, the nerve
embedding is fully faithful. It also follows from (Joyal, 2002) that the nerve
functor defined by the category of PSRs defines a quasicategory. $\bullet$

In particular, the nerve of a PSR defines a quasicategory, and this result
shows that its nerve is a full and faithful embedding of a category as a
simplicial object. The significance of this theorem is it shows that a
considerable amount of theoretical machinery in higher-order category theory
can be brought to bear on the problem of structure discovery of a PSR. There
are many elaborations of this basic result, which we will postpone to a
subsequent paper. The definition of nerve leads to an important topological
characterization of any category.

######  Definition 25.

The classifying space of a PSR ${\cal C}$ is the topological space defined by
its nerve functor $|N_{\bullet}({\cal C})|$.

The classifying space of a category gives a way to define an algebraic
invariant of a PSR, which we define below as its singular homology.

###  4.4 Singular Homology of a PSR

We will now describe the singular homology of a PSR. First, we need to define
more concretely the topological $n$-simplex that provides a concrete way to
attach a topology to a simplicial object. Our definitions below build on those
given in (Lurie, 2022). For each integer $n$, define the topological space
$|\Delta_{n}|$ realized by the object $\Delta_{n}$ as

$|\Delta_{n}|=\\{t_{0},t_{1},\ldots,t_{n}\in\mathbb{R}^{n+1}:t_{0}+t_{1}+\ldots+t_{n}=1\\}$

This is the familiar $n$-dimensional simplex over $n$ variables. For any PSR
model, its classifying space $|{\cal N}_{\bullet}({\cal C})|$ defines a
topological space. We can now define the singular $n$-simplex is a continuous
mapping $\sigma:|\Delta_{N}|\rightarrow|{\cal N}_{\bullet}({\cal C})|$. Every
singular $n$-simplex $\sigma$ induces a collection of $n-1$-dimensional
simplices called faces, denoted as

$d_{i}\sigma(t_{0},\ldots,t_{n-1})=(t_{0},t_{1},\ldots,t_{i-1},0,t_{i},\ldots,t_{n-1})$

Define the set of all morphisms $\mbox{Sing}_{n}(X)={\bf Hom}_{\bf
Top}(\Delta_{n},|{\cal N}_{\bullet}({\cal C})|)$ as the set of singular
$n$-simplices of $|{\cal N}_{\bullet}({\cal C})|$.

######  Definition 26.

For any topological space defined by a PSR $|{\cal N}_{\bullet}({\cal C})|$,
the singular homology groups $H_{*}(|{\cal N}_{\bullet}({\cal C})|;{\bf Z})$
are defined as the homology groups of a chain complex

$\ldots\xrightarrow[]{\partial}{\bf Z}(\mbox{Sing}_{2}(|{\cal
N}_{\bullet}({\cal C})|))\xrightarrow[]{\partial}{\bf
Z}(\mbox{Sing}_{1}(|{\cal N}_{\bullet}({\cal
C})|))\xrightarrow[]{\partial}{\bf Z}(\mbox{Sing}_{0}(|{\cal
N}_{\bullet}({\cal C})|))$

where ${\bf Z}(\mbox{Sing}_{n}(|{\cal N}_{\bullet}({\cal C})|))$ denotes the
free Abelian group generated by the set $\mbox{Sing}_{n}(|{\cal
N}_{\bullet}({\cal C})|)$ and the differential $\partial$ is defined on the
generators by the formula

$\partial(\sigma)=\sum_{i=0}^{n}(-1)^{i}d_{i}\sigma$

Intuitively, a chain complex builds a sequence of vector spaces that can be
used to construct an algebraic invariant of a PSR from its classifying space
by choosing the left k module ${\bf Z}$ to be a vector space. Each
differential $\partial$ then becomes a linear transformation whose
representation is constructed by modeling its effect on the basis elements in
each ${\bf Z}(\mbox{Sing}_{n}(X))$.

##  5 Universal Causal Model

We now state more formally the Universal Causal Model (UCM) framework
(Mahadevan, 2022a), which provides some background to simplicial objects
formulation below.

######  Definition 27.

A universal causal model (UCM) is defined as a tuple $\langle{\cal C},{\cal
X},{\cal I},{\cal O},{\cal E}\rangle$ where each of the components is
specified as follows:

  1. 1.

${\cal C}$ is a category of causal objects that interact with each other, and
their patterns of interactions are captured by a set of morphisms Hom${}_{\cal
C}(X,Y)$ between object $X$ and $Y$. Categories where the Hom morphisms can be
defined as a set are referred to as locally small categories, which are the
ones of primary interest to us in this paper. In particular, a V-enriched
category ${\cal C}$ is one where the Hom morphisms are defined over the
category V, which allows capturing additional structure that might exist in
the set of morphisms.

  2. 2.

${\cal X}$ is a set of construction objects that allow constructing complex
causal models from elementary parts. Examples include monoidal tensor product
of two categories ${\cal M}\otimes{\cal M}$, Galois extensions and profunctors
between two partially ordered sets to represent resource models, co-limits and
decorated cospans to represent electric circuits, and so on. In this paper, we
use the construction tools from the theory of simplicial objects.

  3. 3.

${\cal I}$ is an intervention category of intervention objects, which map from
some category ${\cal E}$ of experimental designs into the causal category
${\cal C}$ to implement an experimental design. Interventions can be simple,
such as setting the value of a variable to a specific value (see Figure 4), in
which case ${\cal I}$ is a comma category, or they can be more complex, such
as setting the value of a variable to some arbitrary marginal distribution,
such as the edge-intervention model proposed by Janzing et al. (2013). There
is a large literature on treatment planning in causal inference, and many of
the state of the art applications of causal inference, such as bipartite
experiments Zigler and Papadogeorgou (2018) use sophisticated experimental
designs. Any of these experimental designs can be accommodated in our
functorial intervention framework. In this paper, we use the elementary face
and degeneracy operators defined earlier on simplicial objects.

  4. 4.

${\cal O}$ is a functor category of observation objects, which provide a
(partial, perhaps noisy) view of causal objects in ${\cal C}$. For example, an
object in the covariant functor category of presheafs Hom${}_{\cal C}(X,-)$ of
morphisms out of $X$ can be viewed as a measurement of the “state" of $X$.
More general examples include bisimulation morphisms used in the literature in
reinforcement learning and software systems Mahadevan (2021a). Adam and Dahleh
(2019) propose modeling observation as an order-preserving function $\Phi$
from a system ${\cal S}$ modeled by a lattice to an observation structure
${\cal O}$, which is also a lattice. They define the composition of subsystems
into a larger system as a join $S_{1}\vee S_{2}$, where a system exhibits a
generative effect if $\Phi(S_{1}\vee S_{2})\neq\Phi(S_{1})\vee\Phi(S_{2})$.

  5. 5.

${\cal E}$ is a functor category of evaluation objects, which map a given
causal model into an evaluation category for the purposes of evaluating the
effects of an intervention. For an example, for a network economy Nagurney
(1999), the evaluation functor E is defined as a mapping from the causal
network economy model to the category of real-valued vector spaces defined by
the vector field $F$ of a variational inequality (VI) $\langle
F(x^{*}),(x-x^{*})\rangle\geqslant 0,\forall x\in$. Here, the vector field
$F:{\cal C}\rightarrow\mathbb{R}^{n}$ is a functor from the causal category
${\cal C}$ of network economy models (see Mahadevan (2021a)) to the category
of $n$-dimensional Euclidean space. Solving a VI means finding equilibrium
flows $x^{*}$ on the network that represent stable patterns of trade. For
example, due to the recent war in Ukraine, global supply chains from grain to
natural gas and oil have been disrupted, and this intervention requires the
global economic system to find a new equilibrium. The problem of studying
causal interventions in network economies was recently studied by us in a
previous paper Mahadevan (2021b), and we refer the reader to that paper for
more details. In a causal DAG model, the evaluation functor maps the causal
category into the category of probability spaces (i.e., the rules of Pearl’s
do-calculus Pearl (2009b) give conditions under which $P(Y|do(X))=P(Y|X)$).

Figure 4: A simple category ${\cal C}$ for studying causal effects of exposure
to getting Covid-19 infections. The morphism Exposure  maps a finite set
object Activity to the (Boolean) object Covid Test, where the morphism could
represent any arbitrary measure-theoretic Witsenhausen (1975); Heymann et al.
(2021), probabilistic Pearl (2009b), or topological relationship Mahadevan
(2021c). In category theory, an “element" of a set (such as Walking) is
formally denoted by a morphism from the unit object 1 (which has one object
and one identity morphism) to the set that is defined by the label it maps to.
Causal interventions are viewed as morphisms into an object, such as
determining the causal effect of Activity on Covid Test by intervening on the
Activity variable by setting it to Walking. In this paper, we model
interventions as elementary face and degeneracy mappings on simplicial
objects.

###  5.1 Causal Inference over Simplicial Objects

We now turn to formulating causal discovery in terms of adjoint functors
between a category, defining a universal causal model (Mahadevan, 2022a), and
a simplicial object. We define causal interventions as images of the
elementary injective maps $d_{i}:[n]\rightarrow[n+1]$, which skips element $i$
in its image, and surjective maps, $s_{j}:[n]\rightarrow[n-1]$, which repeats
element $i$, in the category of ordinal numbers. Defining causal inference
over simplicial objects requires choosing a compositional structure over
higher-order simplicial objects $n\geqslant 2$, which involves requires a
significant amount of higher-order category theory, including weak Kan
complexes Boardman and Vogt (1973), quasicategories (Joyal, 2002) and
$\infty$-categories (Lurie, 2022), which were reviewed above. We pose the
problem of causal discovery in simplicial objects in terms of adjoints between
categories and simplicial objects. The nerve of a category is a fully faithful
right adjoint from a category ${\cal C}$ to an associated simplicial object
${\cal N}_{\cal C}$. Its left adjoint is a destructive functor that only
preserves information up to the $2$-simplices. We relate these ideas to
existing literature on causal discovery from conditional independence oracles
on datasets.

Many previous studies of causal discovery from interventions, including the
conservative family of intervention targets (Hauser and Bühlmann, 2012), path
queries (Bello and Honorio, 2018), and separating systems of finite sets or
graphs. (Eberhardt, 2008; Hauser and Bühlmann, 2012; Kocaoglu et al., 2017;
Katona, 1966; Mao-cheng, 1984) can all be viewed as imposing a topology on the
sets of variables being intervened.

###  5.2 Causal Horns and Conditional Independence

We now introduce the concept of causal horns, subsets of simplicial objects,
which like the case of PSRs above, represent fragments of the complete
simplicial object that is constructed during the process of structure
discovery. In the literature on causal discovery, it is common to use
conditional independence as a guide to causal discovery. Conditional
independence is a symmetric property, as we will see below from examining a
well-known axiom system for conditional independence in statistics.

######  Definition 28.

A Causal Horn $\Lambda^{n}_{i}:\Delta^{op}\rightarrow{\cal C}$ is defined as

$(\Lambda^{n}_{i})([m])=\\{\alpha\in{\bf
Hom}_{\Delta}([m],[n]):[n]\not\subseteq\alpha([m])\cup\\{i\\}\\}$

Intuitively, a causal horn $\Lambda^{n}_{i}$ is a fragment of a causal model
(see Figure 6) that can be viewed as the simplicial subset that results from
removing the interior of the $n$-simplex $\Delta^{n}$ together with the face
opposite its $i$th vertex. Note that ${\cal C}_{n}$ defines the $n$-simplex
associated with the horn of a causal model defined by the category ${\cal C}$
(recall that a simplicial object is a contravariant functor from the category
of ordinal numbers $\Delta$ to the category ${\cal C}$ defining causal
models.).

######  Definition 29.

A separoid Dawid (2001) defines a category over preordered set $({\cal
S},\leqslant)$, namely $\leqslant$ is reflexive and transitive, equipped with
a ternary relation $\mathrel{\perp\mspace{-10.0mu}\perp}$ on triples
$(x,y,z)$, where $x,y,z\in{\cal S}$ satisfy the following properties:

  * •

S1: $({\cal S},\leqslant)$ is a join semi-lattice.

  * •

P1: $x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ x$

  * •

P2: $x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ z\ \ \ \Rightarrow\ \ \
y\mathrel{\perp\mspace{-10.0mu}\perp}x\ |z$

  * •

P3: $x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ z\ \ \ \mbox{and}\ \ \
w\leqslant y\ \ \ \Rightarrow\ \ \ x\mathrel{\perp\mspace{-10.0mu}\perp}w\ |z$

  * •

P4: $x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ z\ \ \ \mbox{and}\ \ \
w\leqslant y\ \ \ \Rightarrow\ \ \ x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\
(z\vee w)$

  * •

P5: $x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ z\ \ \ \mbox{and}\ \ \
x\mathrel{\perp\mspace{-10.0mu}\perp}w\ |\ (y\vee z)\ \ \ \Rightarrow\ \ \
x\mathrel{\perp\mspace{-10.0mu}\perp}(y\vee w)\ |\ z$

A strong separoid also defines a category. A strong separoid is defined over a
lattice ${\cal S}$ has in addition to a join $\vee$, a meet $\wedge$
operation, and satisfies an additional axiom:

  * •

P6: If $z\leqslant y$ and $w\leqslant y$, then
$x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ z\ \ \ \mbox{and}\ \ \
x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ w\ \ \ \Rightarrow\ \ \
x\mathrel{\perp\mspace{-10.0mu}\perp}y\ |\ z\ \wedge\ w$

It is well known that causal DAG structures can only be recovered up to an
equivalence class under observation. For example, the three DAG models
$A\rightarrow B\rightarrow C$, $A\leftarrow B\leftarrow C$, and the diverger
$A\leftarrow B\rightarrow C$ cannot be discriminated from observations alone,
because they define the same conditional independence property
$A\mathrel{\perp\mspace{-10.0mu}\perp}C|B$. Parameterizing these models as
probability distributions implies that Bayes rule allows inferring $P(B|A)$
from $P(A|B)$, thus these models are equivalent from purely observational
data. To discover the exact structure requires making interventions (e.g.,
intervening on a variable is usually done by clamping its value $X=x$, and
thereby deleting any arrows entering the variable from other objects). The
same problem applies as well to non-graphical representations of conditional
independence, such as integer-valued multisets (Studeny, 2010), defined as an
integer-valued multiset function $u:\mathbb{Z}^{{\cal
P(\mathbb{Z})}}\rightarrow\mathbb{Z}$ from the power set of integers, ${\cal
P(\mathbb{Z})}$ to integers $\mathbb{Z}$. An imset is defined over partialy
ordered set (poset), defined as a distributive lattice of disjoint (or non-
disjoint) subsets of variables. The bottom element is denoted $\emptyset$, and
top element represents the complete set of variables $N$. A full discussion of
the probabilistic representations induced by imsets is given (Studeny, 2010).
We will only focus on the aspects of imsets that relate to its conditional
independence structure, and its topological structure as defined by the poset.
A combinatorial imset is defined as:

$u=\sum_{A\subset N}c_{A}\delta_{A}$

where $c_{A}$ is an integer, $\delta_{A}$ is the characteristic function for
subset $A$, and $A$ potentially ranges over all subsets of $N$. An elementary
imset is defined over $(a,b\mathrel{\perp\mspace{-10.0mu}\perp}A)$, where
$a,b$ are singletons, and $A\subset N\setminus\\{a,b\\}$. A structural imset
is defined as one where the coefficients can be rational numbers. For a
general DAG model $G=(V,E)$, an imset in standard form (Studeny, 2010) is
defined as

$u_{G}=\delta_{V}-\delta_{\emptyset}+\sum_{i\in V}(\delta_{\mbox{{\bf
Pa}}_{i}}-\delta_{i\cup\mbox{{\bf Pa}}_{i}})$

Figure 5 shows an example imset for DAG models over three variables, defined
by an integer valued function over the lattice of subsets. Each of the three
DAG models shown defines exactly the same imset function. Studeny (2010) gives
a detailed analysis of imsets as a non-graphical representation of conditional
independence.

Figure 5: An illustration of an integer-valued multiset (imset) consisting of
a lattice of subsets over three elements for representing conditional
independences in DAG models. All three DAG models are represented by the same
imset. We can view an imset as a functor from a simplicial object (shown as
the dark blue filled triangle) to a left $k$ module. Note that a causal
intervention on a DAG generates a horn of the simplicial object shown in dark
blue.

Figure 6 illustrates the space of possible causal DAG models over $3$
variables, with their associated imset representations (see (Studený et al.,
2010b) for details). Each vertex in this figure shows a potential DAG model.
To explain this representation in more detail, the undirected edges represent
the essential graph, namely for each edge of the form $a-b$, there are two
possible structures that it represents $a\rightarrow b$ and $a\leftarrow b$.
These two structures are homotopically equivalent, that is, they define an
equivalence class on the space of all models.

Figure 6: Causal discovery through the space of all models over $3$ variables
shown with their associated imset representations (Studený et al., 2010b).
Each candidate DAG defines a causal horn, a simplicial subobject of the
complete simplex on $\Delta^{2}$, and the process of causal structure
discovery can be viewed in terms of the abstract horn filling problem defined
above for higher-order categories.

###  5.3 Causal Discovery as Adjoint Functors

Following the case for PSR structure discovery, we can also formulate causal
discovery in terms of a pair of adjoint functors between a category ${\bf C}$
and a simplicial object $X$.

${X_{n}}$${\mathbf{C}.}$$\scriptstyle{G}$$\scriptstyle{F}$${\scriptscriptstyle\boldsymbol{\top}}$

In general, the functor $G$ from a simplicial object $X$ to a category ${\cal
C}$ can be lossy. For example, we can define the objects of ${\cal C}$ to be
the elements of $X_{0}$, and the morphisms of ${\cal C}$ as the elements of
$f\in X_{1}$, where $f:a\rightarrow b$, and $d_{0}f=a$, and $d_{1}f=b$, and
$s_{0}a,a\in X$ as defining the identity morphisms ${\bf 1}_{a}$. Composition
in this case can be defined as the free algebra defined over elements of
$X_{1}$, subject to the constraints given by elements of $X_{2}$. For example,
if $x\in X_{2}$, we can impose the requirement that $d_{1}x=d_{0}x\circ
d_{2}x$. Such a definition of the left adjoint would be quite lossy because it
only preserves the structure of the simplicial object $X$ up to the
$2$-simplices. The right adjoint from a category to its associated simplicial
object, in contrast, constructs a full and faithful embedding of a category
into a simplicial set. In particular, the nerve of a category is such a right
adjoint.

Consider the three horns defined below, once again, and let us relate them to
the partial DAG structures shown in Figure 6. Notice all three horns are
illustrated by candidate DAG structures, for example, the rightmost horn below
corresponds to the partial DAG $A\rightarrow C\leftarrow B$, under the mapping
$0\rightarrow A,1\rightarrow B,2\rightarrow C$. The edge that represents
moving from this partial DAG to the complete DAG at the bottom of Figure 6
corresponds exactly to the problem of filling the outer horn shown below on
the right.

${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$${\\{0\\}}$${\\{1\\}}$${\\{2\\}}$

Let us consider a more complex case of horn filling over a $3$-simplex
$f:\Lambda^{3}_{2}\rightarrow{\cal C}$ for any category ${\cal C}$ that
represents a causal model. The “data" that is used to solve the “horn filling"
problem is as follows:

  * •

There are $4$ objects, represented as $0$-simplices $x_{0},x_{1},x_{2}$ and
$x_{3}$.

  * •

There are $6$ $1$-simplices, which we can define as potential causal arrows
$f_{0,1},f_{1,2},f_{2,3},f_{0,2},f_{0,3}$ and $f_{1,3}$. Each of these arrows
$f_{i,j}$ defines two $0$-faces $x_{i}$ and $x_{j}$, the basic units in a
causal study.

  * •

There are only $3$ $2$-simplices $f_{0,2,3},f_{0,1,2}$ and $f_{1,2,3}$. As we
are dealing with the horn $\Lambda^{3}_{2}$, the $2$-simplex $f_{0,1,3}$ is
missing. Each of the given $2$-simplices defines a homotopy equivalent
composition, for example $f_{0,2,3}:f_{2,3}\circ f_{0,2}\sim f_{0,3}$.

The problem of horn filling is to deduce the missing $2$-simplex $f_{0,1,3}$
and the missing $3$-simplex $f_{0,1,2,3}$ by defining a homotopy of
compositions of homotopies:

$f_{0,1,2,3}:f_{0,2,3}\circ f_{0,1,2}\equiv f_{0,1,3}\circ f_{1,2,3}$

######  Definition 30.

The nerve of a causal model ${\cal C}$ is the set of sequences of composable
arrows of length $n$, for $n\geqslant 1$. Let $N_{n}({\cal C})$ denote the set
of sequences of composable arrows

$\\{C_{o}\xrightarrow[]{f_{1}}C_{1}\xrightarrow[]{f_{2}}\ldots\xrightarrow[]{f_{n}}C_{n}\
|\ C_{i}\ \mbox{is an object in}\ {\cal C},f_{i}\ \mbox{is a morphism in}\
{\cal C}\\}$

We can define the causal discovery problem in terms of the right adjoint from
the nerve of a causal model to the category. In general, the functor mapping a
simplicial object to a category is lossy, because it only preserves properties
of the simplicial object up to a certain level. In the case of causal
discovery, we can exploit symmetry properties from conditional independence to
design this functorial mapping, as was discussed above.

${{\cal N}_{\bullet}({\cal
C})}$${\mathbf{C}.}$$\scriptstyle{G}$$\scriptstyle{F}$${\scriptscriptstyle\boldsymbol{\top}}$

The definition of nerve leads to an important topological characterization of
any causal category.

######  Definition 31.

The classifying space of a causal model ${\cal C}$ is the topological space
$|N_{\bullet}({\cal C})|$.

The classifying space of a causal model gives a way to define an algebraic
invariant.

###  5.4 The Singular Homology of a Causal Model

We will now describe the singular homology of a causal model, using the imset
representation as an example shown earlier in Figure 6.

######  Definition 32.

For any topological space $X$ defined by a causal model, the singular homology
groups $H_{*}(X;{\bf Z})$ are defined as the homology groups of a chain
complex

$\ldots\xrightarrow[]{\partial}{\bf
Z}(\mbox{Sing}_{2}(X))\xrightarrow[]{\partial}{\bf
Z}(\mbox{Sing}_{1}(X))\xrightarrow[]{\partial}{\bf Z}(\mbox{Sing}_{0}(X))$

where ${\bf Z}(\mbox{Sing}_{n}(X))$ denotes the free Abelian group generated
by the set $\mbox{Sing}_{n}(X)$ and the differential $\partial$ is defined on
the generators by the formula

$\partial(\sigma)=\sum_{i=0}^{n}(-1)^{i}d_{i}\sigma$

Intuitively, a chain complex builds a sequence of vector spaces that can be
used to construct an algebraic invariant of a topological space by choosing
the left k module ${\bf Z}$ to be a vector space. Each differential $\partial$
then becomes a linear transformation whose representation is constructed by
modeling its effect on the basis elements in each ${\bf
Z}(\mbox{Sing}_{n}(X))$.

######  Example 10.

Let us illustrate the singular homology groups defined by an integer-valued
multiset Studeny (2010) used to model conditional independence. Imsets over a
DAG of three variables $N=\\{a,b,c\\}$ shown previously as Figure 5 can be
viewed as a finite discrete topological space. For this topological space $X$,
the singular homology groups $H_{*}(X;{\bf Z})$ are defined as the homology
groups of a chain complex

${\bf Z}(\mbox{Sing}_{3}(X))\xrightarrow[]{\partial}{\bf
Z}(\mbox{Sing}_{2}(X))\xrightarrow[]{\partial}{\bf
Z}(\mbox{Sing}_{2}(X))\xrightarrow[]{\partial}{\bf
Z}(\mbox{Sing}_{1}(X))\xrightarrow[]{\partial}{\bf Z}(\mbox{Sing}_{0}(X))$

where ${\bf Z}(\mbox{Sing}_{i}(X))$ denotes the free Abelian group generated
by the set $\mbox{Sing}_{i}(X)$ and the differential $\partial$ is defined on
the generators by the formula

$\partial(\sigma)=\sum_{i=0}^{4}(-1)^{i}d_{i}\sigma$

The set $\mbox{Sing}_{n}(X)$ is the set of all morphisms ${\bf
Hom}_{Top}(|\Delta_{n}|,X)$. For an imset over the three variables
$N=\\{a,b,c\\}$, we can define the singular $n$-simplex $\sigma$ as:

$\sigma:|\Delta^{4}|\rightarrow X\ \ \mbox{where}\ \
|\Delta^{n}|=\\{t_{0},t_{1},t_{2},t_{3}\in[0,1]^{4}:t_{0}+t_{1}+t_{2}+t_{3}=1\\}$

The $n$-simplex $\sigma$ has a collection of faces denoted as
$d_{0}\sigma,d_{1}\sigma,d_{2}\sigma$ and $d_{3}\sigma$. If we pick the
$k$-left module ${\bf Z}$ as the vector space over real numbers $\mathbb{R}$,
then the above chain complex represents a sequence of vector spaces that can
be used to construct an algebraic invariant of a topological space defined by
the integer-valued multiset. Each differential $\partial$ then becomes a
linear transformation whose representation is constructed by modeling its
effect on the basis elements in each ${\bf Z}(\mbox{Sing}_{n}(X))$. An
alternate approach to constructing a chain homology for an integer-valued
multiset is to use Möbius inversion to define the chain complex in terms of
the nerve of a category (see our recent work on categoroids (Mahadevan, 2022b)
for details).

##  6 Summary

In this paper we presented a unified formalism for structure discovery in
causal inference and reinforcement learning using the framework of simplicial
objects, contravariant functors from the category of ordinal numbers into any
category, which form the basis for higher-order category theory. We showed
that structure discovery in both causal inference and RL can be defined as
filling the horns of simplicial objects, and showed that a number of
constructions in higher-order category theory, such as extensions and lifting
problems, weak Kan complexes, nerve of a category, and chain complexes could
be brought to bear on the design of new algorithms. Specifically, we show that
fragments of causal models that are equivalent under conditional independence
– defined as causal horns – as well as fragments of potential tests in a
predictive state representation – defined as predictive horns – are both
special cases of horns of a simplicial object of order $n$, resulting from the
removal of the interior and the face opposite a particular vertex in an
$n$-simplex. Causal and predictive-state horns both result from interventions
on simplicial objects, defined as images of a sequence of elementary order-
preserving morphisms from the category of ordinal numbers $\Delta$ into an
underlying category encoding a universal causal or decision model. Latent
structure discovery in both settings involve the same fundamental mathematical
problem of finding extensions of horns of simplicial objects through solving
lifting problems in commutative diagrams, and exploiting weak homotopies that
define higher-order symmetries. The problem of filling “inner horns" is solved
using quasicategories and weak Kan extensions, whereas filling “outer" horns
requires ideas from $\infty$-category theory. We define the common abstract
problem of structure discovery in terms of adjoint functors between a
universal causal or decision model category and its simplicial object
representation. In general, the left adjoint functor from a simplicial object
$X$ to a category ${\cal C}$ is lossy, preserving only relationships up to a
certain order defined by homotopical equivalences. In contrast, the right
adjoint defining the nerve of a category constructs a lossless encoding of a
category as a simplicial object.

## References

  * May (1992) J.P. May.  _Simplicial Objects in Algebraic Topology_.  Chicago Lectures in Mathematics. University of Chicago Press, 1992.  ISBN 9780226511818.  URL https://books.google.com/books?id=QGjwV0gyQnIC.
  * Boardman and Vogt (1973) M. Boardman and Rainer Vogt.  _Homotopy invariant algebraic structures on topological spaces_.  Springer, Berlin, 1973.
  * Joyal (2002) A. Joyal.  Quasi-categories and kan complexes.  _Journal of Pure and Applied Algebra_ , 175(1):207–222, 2002.  ISSN 0022-4049.  doi:https://doi.org/10.1016/S0022-4049(02)00135-4.  URL https://www.sciencedirect.com/science/article/pii/S0022404902001354.  Special Volume celebrating the 70th birthday of Professor Max Kelly.
  * Lurie (2022) Jacob Lurie.  Kerodon.  https://kerodon.net, 2022.
  * Pearl (2009a) Judea Pearl.  _Causality: Models, Reasoning and Inference_.  Cambridge University Press, USA, 2nd edition, 2009a.  ISBN 052189560X.
  * Imbens and Rubin (2015) Guido W. Imbens and Donald B. Rubin.  _Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction_.  Cambridge University Press, USA, 2015.  ISBN 0521885884.
  * Spirtes et al. (2000) Peter Spirtes, Clark Glymour, and Richard Scheines.  _Causation, Prediction, and Search, Second Edition_.  Adaptive computation and machine learning. MIT Press, 2000.  ISBN 978-0-262-19440-2.
  * Singh et al. (2004) Satinder P. Singh, Michael R. James, and Matthew R. Rudary.  Predictive state representations: A new theory for modeling dynamical systems.  In David Maxwell Chickering and Joseph Y. Halpern, editors, _UAI ’04, Proceedings of the 20th Conference in Uncertainty in Artificial Intelligence, Banff, Canada, July 7-11, 2004_ , pages 512–518. AUAI Press, 2004.
  * Sutton and Barto (1998) Richard S. Sutton and Andrew G. Barto.  _Reinforcement learning - an introduction_.  Adaptive computation and machine learning. MIT Press, 1998.  ISBN 978-0-262-19398-6.  URL https://www.worldcat.org/oclc/37293240.
  * Van Overschee and De Moor (1996) Peter Van Overschee and Bart De Moor.  _Subspace identification for linear systems. Theory, implementation, applications. Incl. 1 disk_ , volume xiv, pages xiv + 254.  Springer, 01 1996.  ISBN 0-7923-9717-7.  doi:10.1007/978-1-4613-0465-4.
  * Chomsky and Schützenberger (1963) N. Chomsky and M.P. Schützenberger.  The algebraic theory of context-free languages*.  In P. Braffort and D. Hirschberg, editors, _Computer Programming and Formal Systems_ , volume 35 of _Studies in Logic and the Foundations of Mathematics_ , pages 118–161. Elsevier, 1963.  doi:https://doi.org/10.1016/S0049-237X(08)72023-8.  URL https://www.sciencedirect.com/science/article/pii/S0049237X08720238.
  * Give’on and Arbib (1968) Y. Give’on and M.A. Arbib.  Algebra automata ii: The categorical framework for dynamic analysis.  _Information and Control_ , 12(4):346–370, 1968\.  ISSN 0019-9958.  doi:https://doi.org/10.1016/S0019-9958(68)90381-1.  URL https://www.sciencedirect.com/science/article/pii/S0019995868903811.
  * Pearl (1989) Judea Pearl.  _Probabilistic reasoning in intelligent systems - networks of plausible inference_.  Morgan Kaufmann series in representation and reasoning. Morgan Kaufmann, 1989.
  * Lauritzen and Richardson (2002) Steffen L. Lauritzen and Thomas S. Richardson.  Chain graph models and their causal interpretations.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 64(3):321–348, 2002.  doi:https://doi.org/10.1111/1467-9868.00340.  URL https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/1467-9868.00340.
  * Forré and Mooij (2017) Patrick Forré and Joris M. Mooij.  Markov properties for graphical models with cycles and latent variables, 2017.
  * Evans (2018) Robin J. Evans.  Margins of discrete Bayesian networks.  _The Annals of Statistics_ , 46(6A):2623 – 2656, 2018.  doi:10.1214/17-AOS1631.  URL https://doi.org/10.1214/17-AOS1631.
  * Dawid (2001) A. Philip Dawid.  Separoids: A mathematical framework for conditional independence and irrelevance.  _Ann. Math. Artif. Intell._ , 32(1-4):335–372, 2001.  doi:10.1023/A:1016734104787.  URL https://doi.org/10.1023/A:1016734104787.
  * Studený et al. (2010a) Milan Studený, Jiří Vomlel, and Raymond Hemmecke.  A geometric view on learning bayesian network structures.  _International Journal of Approximate Reasoning_ , 51(5):573–586, 2010a.  ISSN 0888-613X.  doi:https://doi.org/10.1016/j.ijar.2010.01.014.  URL https://www.sciencedirect.com/science/article/pii/S0888613X10000216.  PGM-2008.
  * Mahadevan (2022a) Sridhar Mahadevan.  On the universality of diagrams for causal inference and the causal reproducing property, 2022a.  URL https://arxiv.org/abs/2207.02917.
  * Mahadevan (2021a) Sridhar Mahadevan.  Universal decision models.  _CoRR_ , abs/2110.15431, 2021a.  URL https://arxiv.org/abs/2110.15431.
  * May (1999) J.P. May.  _A Concise Course in Algebraic Topology_.  Chicago Lectures in Mathematics. University of Chicago Press, 1999.  ISBN 9780226511832.  URL https://books.google.com/books?id=g8SG03R1bpgC.
  * MacLane (1971) Saunders MacLane.  _Categories for the Working Mathematician_.  Springer-Verlag, New York, 1971.  Graduate Texts in Mathematics, Vol. 5.
  * Richter (2020) B. Richter.  _From Categories to Homotopy Theory_.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2020.  ISBN 9781108479622.  URL https://books.google.com/books?id=pnzUDwAAQBAJ.
  * Puterman (1994) Martin L. Puterman.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  Wiley Series in Probability and Statistics. Wiley, 1994.  ISBN 978-0-47161977-2.  doi:10.1002/9780470316887.  URL https://doi.org/10.1002/9780470316887.
  * Ravindran and Barto (2003) Balaraman Ravindran and Andrew G. Barto.  SMDP homomorphisms: An algebraic approach to abstraction in semi-markov decision processes.  In Georg Gottlob and Toby Walsh, editors, _IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9-15, 2003_ , pages 1011–1018. Morgan Kaufmann, 2003\.  URL http://ijcai.org/Proceedings/03/Papers/145.pdf.
  * Fong and Spivak (2018) Brendan Fong and David I Spivak.  Seven sketches in compositionality: An invitation to applied category theory, 2018.  URL http://arxiv.org/abs/1803.05316.  cite arxiv:1803.05316Comment: 341+xii pages.
  * Bradley et al. (2022) Tai-Danae Bradley, John Terilla, and Yiannis Vlassopoulos.  An enriched category theory of language: From syntax to semantics.  _La Matematica_ , mar 2022.  doi:10.1007/s44007-022-00021-2.  URL https://doi.org/10.1007%2Fs44007-022-00021-2.
  * Thon and Jaeger (2015) Michael R. Thon and Herbert Jaeger.  Links between multiplicity automata, observable operator models and predictive state representations: a unified learning framework.  _J. Mach. Learn. Res._ , 16:103–147, 2015.  URL http://dl.acm.org/citation.cfm?id=2789276.
  * Soni and Singh (2007) Vishal Soni and Satinder P. Singh.  Abstraction in predictive state representations.  In _Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada_ , pages 639–644. AAAI Press, 2007.  URL http://www.aaai.org/Library/AAAI/2007/aaai07-101.php.
  * Janzing et al. (2013) Dominik Janzing, David Balduzzi, Moritz Grosse-Wentrup, and Bernhard Schölkopf.  Quantifying causal influences.  _The Annals of Statistics_ , 41(5):2324 – 2358, 2013.  doi:10.1214/13-AOS1145.  URL https://doi.org/10.1214/13-AOS1145.
  * Zigler and Papadogeorgou (2018) Corwin M. Zigler and Georgia Papadogeorgou.  Bipartite causal inference with interference, 2018.
  * Adam and Dahleh (2019) Elie M. Adam and Munther A. Dahleh.  Generativity and interactional effects: an overview, 2019.  URL https://arxiv.org/abs/1911.10406.
  * Nagurney (1999) A. Nagurney.  _Network Economics: A Variational Inequality Approach_.  Kluwer Academic Press, 1999.
  * Mahadevan (2021b) Sridhar Mahadevan.  Causal inference in network economics.  _CoRR_ , abs/2109.11344, 2021b.  URL https://arxiv.org/abs/2109.11344.
  * Pearl (2009b) Judea Pearl.  _Causality: Models, Reasoning and Inference_.  Cambridge University Press, USA, 2nd edition, 2009b.  ISBN 052189560X.
  * Witsenhausen (1975) H. S. Witsenhausen.  The intrinsic model for discrete stochastic control: Some open problems.  In A. Bensoussan and J. L. Lions, editors, _Control Theory, Numerical Methods and Computer Systems Modelling_ , pages 322–335, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg.  ISBN 978-3-642-46317-4.
  * Heymann et al. (2021) Benjamin Heymann, Michel de Lara, and Jean-Philippe Chancelier.  Causal inference theory with information dependency models, 2021.  URL https://arxiv.org/abs/2108.03099.
  * Mahadevan (2021c) Sridhar Mahadevan.  Causal homotopy, 2021c.  URL https://arxiv.org/abs/2112.01847.
  * Hauser and Bühlmann (2012) Alain Hauser and Peter Bühlmann.  Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs.  _J. Mach. Learn. Res._ , 13:2409–2464, 2012.  URL http://dl.acm.org/citation.cfm?id=2503320.
  * Bello and Honorio (2018) Kevin Bello and Jean Honorio.  Computationally and statistically efficient learning of causal bayes nets using path queries.  In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pages 10954–10964, 2018.  URL https://proceedings.neurips.cc/paper/2018/hash/a0b45d1bb84fe1bedbb8449764c4d5d5-Abstract.html.
  * Eberhardt (2008) Frederick Eberhardt.  Almost optimal intervention sets for causal discovery.  In David A. McAllester and Petri Myllymäki, editors, _UAI 2008, Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence, Helsinki, Finland, July 9-12, 2008_ , pages 161–168. AUAI Press, 2008.  URL https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1948&proceeding_id=24.
  * Kocaoglu et al. (2017) Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim.  Experimental design for learning causal graphs with latent variables.  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 7018–7028, 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/291d43c696d8c3704cdbe0a72ade5f6c-Abstract.html.
  * Katona (1966) Gyula Katona.  On separating systems of a finite set.  _Journal of Combinatorial Theory_ , 2(1):174–194, 1966.
  * Mao-cheng (1984) CAI Mao-cheng.  On separating systems of graphs.  _Discrete Mathematics_ , 49(1):15–20, 1984.  ISSN 0012-365X.  doi:https://doi.org/10.1016/0012-365X(84)90146-8.  URL https://www.sciencedirect.com/science/article/pii/0012365X84901468.
  * Studeny (2010) M. Studeny.  _Probabilistic Conditional Independence Structures_.  Information Science and Statistics. Springer London, 2010.  ISBN 9781849969482.  URL https://books.google.com.gi/books?id=bGFRcgAACAAJ.
  * Studený et al. (2010b) Milan Studený, Jiří Vomlel, and Raymond Hemmecke.  A geometric view on learning bayesian network structures.  _International Journal of Approximate Reasoning_ , 51:573–586, 06 2010b.  doi:10.1016/j.ijar.2010.01.014.
  * Mahadevan (2022b) Sridhar Mahadevan.  Categoroids: Universal conditional independence, 2022b.  URL https://arxiv.org/abs/2208.11077.