# Super graphs on groups, I

G. Arunkumar  Indian Institute of Technology, Dharwad, Karnataka, India.
<EMAIL_ADDRESS>,  Peter J. Cameron  School of Mathematics and
Statistics, University of St Andrews, Fife, UK<EMAIL_ADDRESS>,
Rajat Kanti Nath  Tezpur University, Tezpur, Assam, India.
<EMAIL_ADDRESS>and  Lavanya Selvaganesh  Indian Institute of
Technology, Varanasi, India<EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a finite group. A number of graphs with the vertex set $G$ have
been studied, including the power graph, enhanced power graph, and commuting
graph. These graphs form a hierarchy under the inclusion of edge sets, and it
is useful to study them together. In addition, several authors have considered
modifying the definition of these graphs by choosing a natural equivalence
relation on the group such as equality, conjugacy, or equal orders, and
joining two elements if there are elements in their equivalence class that are
adjacent in the original graph. In this way, we enlarge the hierarchy into a
second dimension. Using the three graph types and three equivalence relations
mentioned gives nine graphs, of which in general only two coincide; we find
conditions on the group for some other pairs to be equal. These often define
interesting classes of groups, such as EPPO groups, $2$-Engel groups, and
Dedekind groups.

We study some properties of graphs in this new hierarchy. In particular, we
characterize the groups for which the graphs are complete, and in most cases,
we characterize the dominant vertices (those joined to all others). Also, we
give some results about universality, perfectness, and clique number.

The paper ends with some open problems and suggestions for further work.

This work began in the Research Discussion on Groups and Graphs, organised by
Ambat Vijayakumar and Aparna Lakshmanan at CUSAT, Kochi, to whom we express
our gratitude.

##  1\. Introduction

In this section, we describe some graphs associated with groups and discuss a
convention for these graphs as well as notation and terminology. In the
following sections, we prove a number of properties of the collection of
graphs and show how treating them together can be helpful: we examine
conditions for some pair of these graphs to be equal; in most cases, we
characterize the dominant vertices; we show that some of the graphs are
perfect, and examine universality properties of the others; and we calculate
the clique number in some cases.

###  1.1. B superA graphs on groups

######  Definition 1.1.

Let $\mathop{\mbox{$\mathrm{A}$}}$ be a type of graph defined on a group $G$.
In this paper, we will consider three such types:

  1. (a)

the _power graph_ , in which $g$ is adjacent to $h$ if either $g$ or $h$ is a
power of the other;

  2. (b)

the _enhanced power graph_ , in which $g$ is adjacent to $h$ if $g$ and $h$
are both powers of an element $k$ (equivalently, if the group $\langle
g,h\rangle$ generated by $g$ and $h$ is cyclic);

  3. (c)

the _commuting graph_ , in which $g$ is adjacent to $h$ if $gh=hg$
(equivalently, if $\langle g,h\rangle$ is abelian).

Several other types of graphs can be defined, including the deep commuting
graph, nilpotency graph, solvability graph, and Engel graph; these are
described in the survey paper [4].

Also, let $\mathop{\mbox{$\mathrm{B}$}}$ be an equivalence relation defined on
$G$. In this paper, we will consider three equivalence relations;

  1. (a)

_equality_ , $g\sim h$ if $g=h$;

  2. (b)

_conjugacy_ , $g\sim h$ if $h=x^{-1}gx$ for some $x\in G$;

  3. (c)

_same order_ , $g\sim h$ if $o(g)=o(h)$, where $o(g)$ denotes the order of
$g$.

Other relations could be considered, such as _automorphism conjugacy_ , where
$g\sim h$ if some automorphism of $G$ maps $g$ to $h$.

#### Definition

The _$\mathop{\mbox{$\mathrm{B}$}}$ super$\mathop{\mbox{$\mathrm{A}$}}$ graph_
on $G$ is defined as follows: Let $[g]$ denote the B-equivalence class of the
element $g$. Now join $g$ and $h$ if and only if there exist
$g^{\prime}\in[g]$ and $h^{\prime}\in[h]$ such that $g^{\prime}$ and
$h^{\prime}$ are joined in the $\mathop{\mbox{$\mathrm{A}$}}$-graph on $G$.

In principle the graph and equivalence relation are arbitrary, but there are
reasons for choosing them to be preserved by the automorphism group of $G$, as
we will see. This is the case for the examples mentioned above.

######  Remark 1.1.

If we take $\mathop{\mbox{$\mathrm{A}$}}$ to be the power graph and
$\mathop{\mbox{$\mathrm{B}$}}$ the relation “same order”, we do obtain the
definition of the superpower graph of $G$ from [17]. For suppose that
$o(g)\mid o(h)$. Then some power of $h$, namely $h^{o(h)/o(g)}$, has order
$o(g)$; so in the definition we can take $g^{\prime}=h^{o(h)/o(g)}$ and
$h^{\prime}=h$. Our naming convention gives this graph the name “order
superpower graph” of $G$, which will distinguish this from the conjugacy
superpower graph. Also, Herzog _et al._ [8] have considered the conjugacy
supercommuting graph. Our aim here is to give a unified treatment of these
graphs.

Our convention would also give the power graph the name “equality superpower
graph”, but we will simply say “power graph”, with similar convention for the
other basic graph types.

We see that any result about the power graph is in principle one of a set of
nine results about related graphs.

Note that we have inclusions of the edge sets as follows: the edge set of the
power graph is contained in the edge set of the conjugacy superpower graph,
which is contained in the edge set of the order superpower graph; similarly
for other types of graphs.

Note also that graph parameters such as clique number, chromatic number, and
matching number are monotonic increasing with edge set; independence number
and clique cover number are monotonic decreasing; and increasing the edge set
cannot destroy properties such as being Hamiltonian.

######  Proposition 1.1.

  1. (a)

Let the equivalence relation $\mathop{\mbox{$\mathrm{B}$}}$ be “same order”.
If $g$ and $h$ are joined in the power graph, then for one of them, say $g$,
every element equivalent to $g$ is joined to some element equivalent to $h$.

  2. (b)

Let $\mathop{\mbox{$\mathrm{B}$}}$ be the conjugacy relation and consider any
graph of type $\mathop{\mbox{$\mathrm{A}$}}$ on the group $G$. If the graph
$\mathop{\mbox{$\mathrm{A}$}}$ is invariant under inner automorphisms of $G$,
and $g$ is joined to $h$ in $\mathop{\mbox{$\mathrm{A}$}}$, then every element
of the conjugacy class of $g$ is joined to some element of the conjugacy class
of $h$ in the conjugacy super$\mathop{\mbox{$\mathrm{A}$}}$ graph on $G$, and
_vice versa_.

  3. (c)

More generally, let $H$ be a subgroup of the automorphism group of $G$ which
acts on $\mathop{\mbox{$\mathrm{A}$}}$ for some graph type
$\mathop{\mbox{$\mathrm{A}$}}$. Let $\mathop{\mbox{$\mathrm{B}$}}$ be the
equivalence relation induced by the orbit partition of this action. Then $g$
is joined to $h$ in $\mathop{\mbox{$\mathrm{A}$}}$ implies that (in
$\mathop{\mbox{$\mathrm{B}$}}$ super$\mathop{\mbox{$\mathrm{A}$}}$ graph)
every element equivalent to $g$ is joined to some element equivalent to $h$
under the equivalence relation $\mathop{\mbox{$\mathrm{B}$}}$.

###### Proof.

The first statement was observed in the earlier remark. We prove the third
statement from which second the statement follows. Note that if $\\{g,h\\}$ is
an edge, then $\\{\phi(g),\phi(h)\\}$ is an edge for all $\phi\in H$ since $B$
is the equivalence relation induced by the orbit partition. In particular, for
the second statement, note that the conjugacy classes are orbits of the inner
automorphism group of $G$; so, if $\\{g,h\\}$ is an edge, then
$\\{x^{-1}gx,x^{-1}hx\\}$ is an edge for all $x\in G$. In this case, the
hypothesis holds for all the three graph types we are considering. ∎

######  Remark 1.2.

Let us observe another general property. For each of the power graph, enhanced
power graph and commuting graph, if $H$ is a subgroup of $G$, then
$\mathop{\mbox{$\mathrm{A}$}}(H)$ is an induced subgraph of
$\mathop{\mbox{$\mathrm{A}$}}(G)$. This holds also for the order
super$\mathop{\mbox{$\mathrm{A}$}}$ graphs, but not in general for the
conjugacy super$\mathop{\mbox{$\mathrm{A}$}}$ graphs since the conjugacy
relation can change when we pass from $G$ to $H$.

###  1.2. A convention about equivalence classes

Our adjacency rule is ambiguous about whether we join vertices in the same
equivalence class. We now explain how we resolve this and explain the
rationale.

In many of the graphs defined on a group, including all those treated here,
the definition would naturally give us a loop at each vertex; any group
element is a power of itself, so this holds for the power graph and enhanced
power graph; any element commutes with itself, so this holds for the commuting
graph; and so on. Of course, we prefer graphs not to have loops, so we
silently remove these, even though they make little difference to many graph-
theoretic properties (they make no change to connectivity and diameter, and
simply add the identity matrix to the adjacency matrix). Adopting the
convention that there is a (silent/virtual) loop at each vertex, we find that
any equivalence class of the equivalence relation B will induce a complete
subgraph in the $\mathop{\mbox{$\mathrm{B}$}}$
super$\mathop{\mbox{$\mathrm{A}$}}$ graph.

In fact, even without this convention, things would not be very different.
Consider the order super$\mathop{\mbox{$\mathrm{A}$}}$ graph. An element $g$
has the same order as its inverse, which is joined to it in the power graph,
enhanced power graph, or commuting graph; so as long as the order of $g$ is
greater than $2$, each order equivalence class will induce a complete graph.
This will fail only for involutions. For the conjugacy relation, things are a
bit more complicated and could be worth investigating. However, as stated, we
will adopt the convention here that every equivalence class of
$\mathop{\mbox{$\mathrm{B}$}}$ induces a complete subgraph in the
$\mathop{\mbox{$\mathrm{B}$}}$ super$\mathop{\mbox{$\mathrm{A}$}}$ graph.

###  1.3. Notation

We have defined a fairly large number of graphs: what notation should we use
to make it easy for the reader to recognize which graph is being discussed
without being altogether too cumbersome?

In [4], the second author proposed a systematic notation for various graphs on
groups: given a group $G$, that paper uses $\mathrm{Pow}(G)$,
$\mathrm{EPow}(G)$, and $\mathrm{Com}(G)$ for the power graph, enhanced power
graph, and commuting graph of $G$. One possibility is to modify these in an
obvious way, so that $\mathrm{CSPow}(G)$ is the conjugacy superpower graph and
$\mathrm{OSPow}(G)$ is the order superpower graph, with similar terminology
for the other graphs.

This notation is a bit cumbersome but is hopefully self-explanatory.

##  2\. Reducing nine graphs to eight

We have defined nine graphs, but two of them turn out to be the same.

######  Theorem 2.1.

For any finite group $G$, the order superenhanced power graph of $G$ is equal
to the order supercommuting graph of $G$.

###### Proof.

We use the basic fact that, if a finite abelian group $G$ has exponent $m$,
then it contains an element of order $m$. By definition, the graph
$\mathrm{OSEPow}(G)$ is a spanning subgraph of $\mathrm{OSCom}(G)$. We have to
prove the reverse implication. So suppose that $\\{x,y\\}$ is an edge of
$\mathrm{OSCom}(G)$. By definition, there exist elements $x^{\prime}$ and
$y^{\prime}$ such that $o(x)=o(x^{\prime})$, $o(y)=o(y^{\prime})$, and
$x^{\prime}y^{\prime}=y^{\prime}x^{\prime}$. Then $A=\langle
x^{\prime},y^{\prime}\rangle$ is abelian. Let $m$ be its exponent, and $z\in
A$ an element of order $m$. Then $o(x^{\prime})\mid o(z)$ and
$o(y^{\prime})\mid o(z)$, so there exist elements $x^{\prime\prime}$ and
$y^{\prime\prime}$ in $A$ with $o(x^{\prime\prime})=o(x^{\prime})$,
$o(y^{\prime\prime})=o(y^{\prime})$, and $x^{\prime\prime}$ and
$y^{\prime\prime}$ are both powers of $z$. Then
$\\{x^{\prime\prime},y^{\prime\prime}\\}$ is an edge of the enhanced power
graph of $G$, and $o(x^{\prime\prime})=o(x)$, $o(y^{\prime\prime})=o(y)$; so
$\\{x,y\\}$ is an edge of the order superenhanced power graph. ∎

Any two of the remaining eight graphs are unequal for some group $G$. By
Theorem 3.1, the only pairs that need to be considered are the
$\mathop{\mbox{$\mathrm{A}$}}$ graph and the conjugacy
super$\mathop{\mbox{$\mathrm{A}$}}$ graph for each of our three graph types
$\mathop{\mbox{$\mathrm{A}$}}$; all of these are settled by the example
$G=S_{3}$ (the dihedral/symmetric group of order $6$).

One could ask: Is there a group $G$ for which all eight graphs are different?
If so, what is the smallest order of such a group?

A more challenging question would be, for each pair of graph types, to
determine the groups for which the two types of graphs coincide. This has been
solved for the original three graphs, and is a non-trivial exercise. The power
graph and enhanced power graph are equal if and only if $G$ contains no
subgroup $C_{p}\times C_{q}$ for distinct primes $p$ and $q$; this condition
characterizes the so-called _EPPO groups_ (elements of prime power order
groups), which were determined by Brandl [2] using earlier work of Higman [9]
and Suzuki [19]; see also [5]. The enhanced power graph and the commuting
graph are equal if and only if $G$ contains no subgroup $C_{p}\times C_{p}$
for a prime $p$; this condition is equivalent to saying that all the Sylow
subgroups are cyclic or (for the prime $2$) generalized quaternion groups and
it is not too difficult to list such groups. Indeed, all groups with cyclic or
generalized quaternion Sylow $2$-subgroups have been determined; see [1].

We give two more results along these lines. For the first, recall the
definition of iterated commutators in a group: $[x,y]=x^{-1}y^{-1}xy$ and

$[x_{1},x_{2},\ldots,x_{n+1}]=[[x_{1},x_{2},\ldots,x_{n}],x_{n+1}]$

for $n\geq 2$. A group $G$ is _nilpotent of class at most $n$_ if
$[x_{1},\ldots,x_{n+1}]=1$ for all $x_{1},\ldots,x_{n+1}\in G$; and a group
satisfies the $n$th _Engel identity_ , or is _$n$ -Engel_, if
$[y,x,\ldots,x]=1$ (with $n$ occurrences of $x$) for all $x,y\in G$. Clearly a
group which is nilpotent of class at most $n$ is $n$-Engel; the converse is
false, but it was shown by Hopkins [10] and Levi [14] independently that a
$2$-Engel group is nilpotent of class at most $3$.

The following lemma is proved by Korhonen given in a post on StackExchange
[13].

######  Lemma 2.2.

The following statements are equivalent for a group $G$.

  1. (a)

Every centralizer in $G$ is a normal subgroup.

  2. (b)

Any two conjugate elements in $G$ commute, ie. $x^{g}x=xx^{g}$ for all $x,g\in
G$.

  3. (c)

$G$ is a $2$-Engel group, ie. $[[x,g],g]=1$ for all $x,g\in G$.

###### Proof.

$(a)\implies(b)$: Consider $x$ in $C_{G}(x)$, since a normal subgroup is a
union of conjugacy classes of its elements, we have $x^{g}\in C_{G}(x)$ for
all $g\in G$ .

$(b)\implies(c)$: Since $x^{g}=x[x,g]$, if $x^{g}$ commutes with $x$, $[x,g]$
also commutes with $x$.

$(c)\implies(a)$: If $[[x,g],g]=1$ for all $g\in G$, then according to [12,
Lemma 2.2] we have $[x,[g,h]]=[[x,g],h]^{2}$. Therefore $[C_{G}(x),G]\leq
C_{G}(x)$, which means that $C_{G}(x)$ is a normal subgroup. ∎

######  Theorem 2.3.

Let $G$ be a finite group. Then the following conditions are equivalent:

  1. (a)

the commuting graph of $G$ is equal to the conjugacy supercommuting graph;

  2. (b)

the centralizer of every element of $G$ is a normal subgroup of $G$;

  3. (c)

$G$ is a $2$-Engel group.

###### Proof.

First, we show the equivalence of (a) and (b). Suppose the commuting graph and
conjugacy supercommuting graph are equal. If $x$ and $y$ commute, they are
joined in the commuting graph, and so every conjugate of $y$ is joined to $x$
in the conjugacy supercommuting graph, and hence also in the commuting graph;
thus $x$ commutes with every conjugate of $y$. Hence the centralizer of $x$ is
a union of conjugacy classes, so it is a normal subgroup of $G$. The argument
reverses. The equivalence of (b) and (c) follows from the above lemma. ∎

For the second result, recall that a _Dedekind group_ is a group in which
every subgroup is normal. Dedekind [6] showed that such a group is either
abelian or of the form $Q_{8}\times E\times F$, where $Q_{8}$ is the
quaternion group of order $8$, $E$ an elementary abelian $2$-group, and $F$ an
abelian group of odd order.

######  Theorem 2.4.

For a finite group $G$, the following conditions are equivalent:

  1. (a)

the power graph of $G$ is equal to the conjugacy superpower graph;

  2. (b)

the enhanced power graph of $G$ is equal to the conjugacy superenhanced power
graph;

  3. (c)

$G$ is a Dedekind group.

###### Proof.

We use the fact that conjugate elements have the same order. Let $x^{G}$
denote the conjugacy class of $x$ in $G$.

In either the power graph or the enhanced power graph, elements of the same
order which are adjacent generate the same cyclic subgroup. So, if either (a)
or (b) holds, then all elements of $x^{G}$ generate $\langle x\rangle$. So
every cyclic subgroup of $G$, and hence every subgroup, is normal; that is,
$G$ is a Dedekind group.

For the converse, if $x$ and $y$ are joined in either the power graph or the
enhanced power graph, then there is a cyclic group $C$ containing $x$ and $y$.
If $G$ is a Dedekind group, then $C$ is normal; so $x^{G}\cup y^{G}\subseteq
C$. In the case of the enhanced power graph, $C$ is a clique, so all vertices
in $x^{G}$ are joined to all vertices in $y^{G}$, and (b) holds. In the case
of the power graph, (a) holds because either $o(x)$ divides $o(y)$ or _vice
versa_. ∎

######  Remark 2.1.

There are some other elementary observations. The group $G$ has the property
“two elements are conjugate if and only if they are equal” exactly when $G$ is
abelian. So we have that the conjugacy super$\mathop{\mbox{$\mathrm{A}$}}$
graph is equal to the $\mathop{\mbox{$\mathrm{A}$}}$ graph if $G$ is abelian,
for any graph type $\mathop{\mbox{$\mathrm{A}$}}$. In a similar way, the
conjugacy super$\mathop{\mbox{$\mathrm{A}$}}$ graph is equal to the order
super$\mathop{\mbox{$\mathrm{A}$}}$ graph if $G$ is a group in which any two
elements of the same order are conjugate. (There are only three finite groups
with this property, the symmetric groups of degrees $1$, $2$ and $3$: see
Fitzpatrick [7, Theorem 3.6].)

##  3\. Completeness and dominant vertices

In this section, we begin a study of how the properties of the graphs relate
to properties of the groups they are built on.

###  3.1. When is the $\mathop{\mbox{$\mathrm{B}$}}$
super$\mathop{\mbox{$\mathrm{A}$}}$ graph complete?

The theorem below summarises the answer to this question “When is the graph
complete?” for our three types of graph and three types of partition, and is
intended as an example of treating the hierarchy uniformly. In the table,
$(*)$ means that the group $G$ has an element whose order is the exponent $m$
of $G$; equivalently, the _spectrum_ of $G$ (the set $\pi^{*}(G)$ of orders of
elements of $G$, sometimes denoted by $\pi_{e}(G)$) is the set of all divisors
of $m$. Such groups are not so rare. Any nilpotent group has this property;
and, for any finite group $G$, there is a positive integer $r$ such that
$G^{r}$ has property $(*)$. For example, $(A_{5})^{3}$ contains elements of
order $30$, which is the exponent of the group.

######  Theorem 3.1.

The following table describes groups whose power graph, enhanced power graph,
commuting graph, or their conjugacy or order supergraph is complete.

| power graph | enhanced | commuting
---|---|---|---
|  | power graph | graph
equality | cyclic | cyclic | abelian
|  $p$-group |  |
conjugacy | cyclic | cyclic | abelian
|  $p$-group |  |
order |  $p$-group | $(*)$ | $(*)$

###### Proof.

The results for the power graph, enhanced power graph, and commuting graph are
well-known [4].

To prove that the conjugacy supercommuting graph is complete if and only if
$G$ is abelian, we use a result which goes back to Jordan [11]: if $G$ is a
finite group and $H$ a proper subgroup of $G$, then there is a conjugacy class
in $G$ which is disjoint from $H$. (For the reader’s convenience we sketch a
proof. Let $H$ have index $n$ in $G$, and consider the action of $G$ by right
multiplication on the set of right cosets of $H$. This action is transitive,
so by the Orbit-counting Lemma (sometimes called Burnside’s Lemma), the
average number of fixed points of the elements of $G$ is $1$. But the identity
fixes $n$ points, and $n>1$; so some element $g$ fixes no point. This means
that $g$ lies in no conjugate of $H$; equivalently, no conjugate of $g$ lies
in $H$. For a modern take on Jordan’s theorem, we strongly recommend a paper
of Serre [18].)

Now, if $G$ is abelian, then the conjugacy supercommuting graph coincides with
the commuting graph, and is complete. So suppose that $G$ is a finite group
whose conjugacy supercommuting graph is complete, and take any element $g\in
G$. If $C_{G}(g)\neq G$ then, by Jordan’s theorem, there is an element $h$
such that the conjugacy class of $h$ is disjoint from $C_{G}(g)$; thus no
conjugate of $h$ commutes with $g$, and so $g$ and $h$ are non-adjacent, a
contradiction. Thus $C_{G}(g)=G$, or $g\in Z(G)$. Since this holds for all
$g\in G$, we see that $G$ is abelian.

If $G$ is not a $p$-group, then it contains elements of distinct prime orders.
These elements are non-adjacent in the power graph and both of its
supergraphs. So if any of these graphs are complete, then $G$ must be a
$p$-group. Conversely, if $G$ is a $p$-group, its order superpower graph is
complete, as shown in [17].

If $G$ is a cyclic $p$-group, then its power graph, and hence its conjugacy
superpower graph, is complete. Suppose conversely that $G$ is a group whose
conjugacy superpower graph is complete. Then $G$ cannot have elements of
distinct prime order, so $G$ is a $p$-group. Let $g$ be an element of order
$p$ in $Z(G)$. Then $G$ is conjugate only to itself, so cannot be joined to
any element of order $p$ outside $\langle g\rangle$; so there can be no such
elements. Thus $G$ has a unique subgroup of order $p$, and by a result of
Burnside [3, Sections 104–105] it is cyclic or generalized quaternion. But
generalized quaternion groups contain non-conjugate subgroups of order $4$, so
cannot arise here.

If $G$ is cyclic, then its enhanced power graph, and hence its conjugacy
superenhanced power graph, is complete. Suppose conversely that $G$ is a group
whose conjugacy superenhanced power graph is complete. Then the conjugacy
supercommuting graph of $G$ is complete, so $G$ is abelian. Then the conjugacy
superenhanced power graph coincides with the enhanced power graph, so $G$ is
cyclic.

Finally, let $G$ be a group whose order supercommuting graph is complete. Take
two elements of $G$, with orders (say) $g$ and $h$. Since $g$ and $h$ are
adjacent, we can replace them with elements of the same orders which commute,
and so the order of their product is the least common multiple of $k$ and $l$.
Thus the set $\pi_{e}(G)$ is closed under taking least common multiples (as
well as under taking divisors), and so $(*)$ holds. Conversely, if $g\in G$
has order equal to the exponent of $G$, then every element in $\pi_{e}(G)$ is
the order of some power of $g$, and all these powers are joined in the
enhanced power graph and in the commuting graph. So the order supercommuting
graph is complete. ∎

###  3.2. Dominant vertices

A graph is complete if and only if every vertex is _dominant_ (or
_universal_), that is, joined to all other vertices. So, as a generalization
of Theorem 3.1, we could ask: for each of the nine graphs, which elements of a
group $G$ are dominant vertices? The answers are known for the basic graphs,
and can be found in [4, Section 9.1]; we summarise the results here.

  1. (a)

The set of dominant vertices of the power graph of $G$ is the whole of $G$, if
$G$ is a cyclic $p$-group; the identity and the generators of $G$, if $G$ is
cyclic but not a $p$-group; the centre, if $G$ is a generalized quaternion
group; and only the identity in all other cases.

  2. (b)

The set of dominant vertices in the enhanced power graph is a cyclic subgroup
of $Z(G)$ called the _cyclicizer_ of $G$; it is the product of the Sylow
$p$-subgroups of $Z(G)$ for those primes $p$ for which a Sylow $p$-subgroup of
$G$ is cyclic or generalized quaternion.

  3. (c)

The set of dominant vertices in the commuting graph is the centre $Z(G)$.

Now we solve the problem for the conjugacy supergraphs.

######  Theorem 3.2.

If $\mathop{\mbox{$\mathrm{A}$}}$ is the power graph, enhanced power graph, or
commuting graph, then the set of dominant vertices in the conjugacy
super$\mathop{\mbox{$\mathrm{A}$}}$ graph of $G$ is the same as the set of
dominant vertices in the $\mathop{\mbox{$\mathrm{A}$}}$ graph.

###### Proof.

We show this first for the commuting graph. Suppose that $g\in G$ and $g$ is
joined to all other vertices of $G$ in the conjugacy supercommuting graph. By
Proposition 1.1, $g$ is joined to an element of every conjugacy class of $G$;
in other words, its centralizer $C_{G}(g)$ meets every conjugacy class. Hence
$C_{G}(g)=G$, so $g\in Z(G)$. Thus $g$ is joined to all other vertices in the
commuting graph.

Now suppose that $\mathop{\mbox{$\mathrm{A}$}}(G)$ is the power graph or
enhanced power graph of $G$, and let $g$ be a dominant vertex in the conjugacy
super$\mathop{\mbox{$\mathrm{A}$}}$ graph of $G$. Since the conjugacy
super$\mathop{\mbox{$\mathrm{A}$}}$ graph is a spanning subgraph of the
conjugacy supercommuting graph, $g\in Z(G)$. So, for any $h\in G$, $h$ is
joined to a conjugate of $g$. But the only conjugate is $g$ itself; so $g$ is
joined to all other vertices in $\mathop{\mbox{$\mathrm{A}$}}(G)$.∎

We have also solved the problem for the order superpower graph. If $G$ has
prime power order then its order superpower graph is complete; so we can
suppose not.

######  Proposition 3.3.

Let $G$ be a group not of prime power order, having exponent $m$. Then the set
of dominant vertices in the order superpower graph of $G$ consists of the
identity and the elements of order $m$ (if any).

###### Proof.

Let $p_{1},\ldots,p_{r}$ be the prime divisors of $|G|$ with $r>1$, and let
$p_{i}^{a_{i}}$ be the largest power of $p^{i}$ dividing the order of an
element of $G$; then there are elements of order $p_{i}^{a_{i}}$ in $G$.
Suppose that $n$ has the property that elements of order $n$ are dominant, and
that $n>1$. Then, for each $i$, either $p_{i}^{a_{i}}$ divides $n$, or $n$
divides $p_{i}^{a_{i}}$. Since $r>1$, the second cannot hold. (If, say, $n$
divides $p_{1}^{a_{1}}$, then $n$ is a proper power of $p_{1}$; then neither
$p_{2}^{a_{2}}\mid n$ or $n\mid p_{2}^{a_{2}}$ can hold.) Thus $n$ is the
product of the prime powers $p_{i}^{a_{i}}$, which is equal to the exponent of
$G$.

Conversely, if $g$ has order $m$, the exponent of $G$, then $o(h)\mid o(g)$
for all $h\in G$, so $g$ is dominant.∎

We have not found a characterisation of the dominant vertices in the (one)
remaining case, the order supercommuting graph.

#### Remark

If a graph has a dominant vertex, then it is connected, with diameter at most
$2$. So it is customary to remove the dominant vertices in order to get non-
trivial questions about connectedness and diameter. This is one reason why it
is important to know such vertices. This remark suggests that a next step in
the investigation of these graphs would be to decide about the connectedness
of the “reduced” graphs.

##  4\. Some graph properties and parameters

In this section, we discuss several further graph properties (perfectness,
universality) and parameters (clique number) for our graphs.

###  4.1. Perfectness and universality

It is known that power graphs of finite groups are perfect, but enhanced power
graphs and commuting graphs are not necessarily perfect; indeed, any finite
graph can be embedded as an induced subgraph in the enhanced power graph (or
the commuting graph) of a finite group (see [4]). In this section we give some
similar results for supergraphs.

######  Theorem 4.1.

The conjugacy or order superpower graph of a finite group is the comparability
graph of a finite partial preorder and hence is perfect.

###### Proof.

For this, we define directed versions of these graphs and show that they are
comparability graphs. For conjugacy, we put an arc from $x$ to $y$ if some
conjugate of $y$ is a power of $x$ (or equivalently if $y$ is a power of some
conjugate of $x$); for order, we put an arc from $x$ to $y$ if $o(y)\mid
o(x)$. Both are reflexive (if we add loops), symmetric and transitive. ∎

######  Theorem 4.2.

Every finite graph $\Gamma$ is embeddable as an induced subgraph in the
conjugacy superenhanced power graph, and in the conjugacy supercommuting
graph, of some finite group.

###### Proof.

The proof in [4, Theorem 5.5] of the analogous result for the enhanced power
graph constructs an abelian group, where conjugacy coincides with equality,
proving the result for this case. Here, we give a different proof, which works
for both graph types. We use the fact that two elements of distinct prime
orders are joined in the enhanced power graph if and only if they are joined
in the commuting graph. (One way round is trivial since the enhanced power
graph is a subgraph of the commuting graph. In the other direction, if $g$ and
$h$ have distinct prime orders and commute, then both are powers of $gh$.)
Now, if $\Gamma$ is a complete graph on $n$ vertices, then we can take $G$ to
be the direct product of cyclic groups of distinct prime orders
$p_{1},\ldots,p_{n}$; if $X$ consists of one element of each prime order, then
the induced subgraph of the commuting graph of $G$ on $X$ is $\Gamma$. So we
may assume that $\Gamma$ is not complete.

First, we observe that it is possible to find a set of $n$ prime numbers
$p_{1},\ldots,p_{n}$ such that, if $i\neq j$ and $p_{i}<p_{j}$, then
$p_{i}\mid p_{j}-1$. This is proved by induction. Suppose that
$p_{1},\ldots,p_{n-1}$ have been chosen. Then we choose $p_{n}$ to be
congruent to $1$ mod $p_{i}$ for $i=1,\ldots,n-1$ (this is possible by the
Chinese remainder theorem) and to be prime (this is possible by Dirichlet’s
theorem on primes in arithmetic progression).

Now for $i,j\in\\{1,\ldots,n\\}$, let $G_{ij}$ be the direct product of the
non-abelian group of order $p_{i}p_{j}$ and the cyclic group of order $p_{k}$
for every $k\notin\\{i,j\\}$; let $x_{ijk}$ be an element of order $p_{k}$ in
$G_{ij}$ for $k=1,\ldots,n$. We note that the induced subgraph of the
commuting graph of $G_{ij}$ on $\\{x_{ij1},\ldots,x_{ijn}\\}$ is the complete
graph $K_{n}$ with the edge $\\{i,j\\}$ deleted.

Given a graph $\Gamma$ with vertex set $\\{1,\ldots,n\\}$, let $G$ be the
direct product of the groups $G_{ij}$ over all _nonedges_ $\\{i,j\\}$ of $G$;
let $x_{k}$ be the element of $G$ which projects onto $x_{ijk}$ in the factor
$G_{ij}$ for all such pairs $\\{i,j\\}$. Then the element $x_{k}$ has order
$p_{k}$, and $x_{k}$ and $x_{l}$ commute if and only if $x_{ijk}$ and
$x_{ijl}$ commute for all $\\{i,j\\}$, that is, $\\{k,l\\}$ is an edge of
$\Gamma$.

Finally, we note that, if two elements commute, they are joined in the
conjucacy supercommuting graph. Conversely, if $x_{j}$ and $x_{k}$ do not
commute, then they project onto non-commuting elements in $G_{jk}$; the
structure of the non-abelian group of order $p_{j}p_{k}$ shows that conjugates
of these elements also do not commute. ∎

###  4.2. Clique number

We describe the maximal cliques in the order superpower and superenhanced
power graphs.

We begin with some definitions. The _spectrum_ $\\\ pi^{*}(G)$ of a finite
group $G$ (cf. Section 3.1) is closed under divisibility (if $k\in\pi^{*}(G)$
and $l\mid k$ then $l\in\pi^{*}(G)$), so $\pi^{*}(G)$ is determined by the set
$\pi^{*}_{\max}(G)$ of its elements which are maximal in the divisibility
partial order.

A sequence $(m_{1},m_{2},\ldots,m_{r})$ of distinct positive integers is a
_chain_ in the divisibility partial order if $m_{i}\mid m_{i+1}$ for
$i=1,\ldots,r-1$. It is a _maximal chain_ if $m_{1}=1$ and $m_{i+1}/m_{i}$ is
prime for $i=1,\ldots,r-1$. The _top_ of the chain is $m_{r}$.

For a finite group $G$ and $m\in\pi^{*}(G)$, we let $G(m)$ denote the set of
all elements of order $m$ in $G$.

######  Theorem 4.3.

  1. (a)

A maximal clique in the order superpower graph has the form $G(m_{1})\cup
G(m_{2})\cup\cdots\cup G(m_{r})$ for some maximal chain whose top belongs to
$\pi^{*}_{\max}(G)$.

  2. (b)

A maximal clique in the order superenhanced power graph has the form
$\displaystyle{\bigcup_{r\mid m}G(r)}$, for some $m\in\pi^{*}_{\max}(G)$.

Given this theorem, the clique numbers of these graphs are obtained by
maximizing over all maximal chains with top in $\pi^{*}_{\max}(G)$ (in the
first case) or elements of $\pi^{*}_{\max}(G)$ (in the second).

###### Proof.

(a) Given a clique $C$ in the order superpower graph, let $m$ be the largest
element of $C$. Then the orders of all other elements of $C$ divide $m$, and
so they form a chain with top $m$. So $C$ is contained in the union given in
part (a) of the theorem, and maximality implies that the chain is maximal, its
top is in $\pi^{*}_{\max}(G)$, and that every element of $G(k)$ for $k$ in the
chain belongs to $C$.

(b) Given $k$ and $l$, elements of $G(k)$ and $G(l)$ are joined in the order
superenhanced power graph if and only if
$\mathop{\mathrm{lcm}}(k,l)\in\pi^{*}(G)$. So the set of orders of elements in
a clique has a unique maximal element $m$. As in the preceding argument, if
$C$ is maximal, then the orders include every divisor of $m$ and $C$ contains
$G(k)$ whenever $k\mid n$.∎

For the superpower and superenhanced power graphs, we do not give a formula,
but explain what maximal cliques look like.

######  Proposition 4.4.

Let $G$ be a finite group.

  1. (a)

Let $C$ be a maximal clique in the conjugacy superenhanced power graph of $G$.
Then there exists $m\in\pi^{*}(G)$ such that $C$ is the union of a conjugacy
class of cyclic subgroups of order $m$.

  2. (b)

Let $C^{\prime}$ be a maximal clique in the conjugacy superpower graph of $G$.
Then there exists $m\in\pi^{*}(G)$ and a maximal chain $(m_{1},\ldots,m_{r})$
of divisors of $m$ and a conjugacy class of cyclic subgroups of $G$ of order
$m$ (with union $C$) such that $C^{\prime}$ consists of all elements of $C$
which have order $m_{i}$ for some $i$ with $1\leq i\leq r$.

###### Proof.

In either case, let $m$ be the largest order of an element of the clique; then
the order of any element of the clique divides $m$. (This is clear for the
power graph. For the enhanced power graph, let $g$ be an element of order $m$.
If there are elements of order $q$ not dividing $m$, then there is one (say
$h$) joined to $g$ in the enhanced power graph; but then there is an element
of larger order to which both $g$ and $h$ are joined, and so it is joined to
all elements of the clique. Now the result follows as in the preceding
theorem. ∎

Note that we cannot conclude in this case that $m\in\pi^{*}_{\max}(G)$. For
example, in the dihedral group $D_{4}$ of order $8$, the cyclic group $C_{4}$
consisting of rotations is a maximal clique in either graph; the reflections
fall into two conjugacy classes, each of which (together with the identity)
forms a maximal clique. In general, it seems not an easy task to decide which
clique (as given in the Proposition) is largest, or to give a formula for its
size.

##  5\. Open problems and further directions

We mention here some questions which have arisen in this investigation which
we have not been able to answer, and some further directions for research.

######  Problem 5.1.

Extend these investigations to other graphs defined on groups (such as the
nilpotency and solvability graphs) and other equivalence relations (such as
automorphism conjugacy). This question for the conjugacy supergraphs has been
studied in several papers, for example, [15, 16].

######  Problem 5.2.

Complete the characterization of the classes of groups $G$ for which a given
pair of the super graphs on $G$ coincide, especially for classes that are
adjacent in a row or column of the $3\times 3$ table (as in Theorem 3.1): see
Theorems 2.3 and 2.4.

######  Problem 5.3.

Characterize the dominant vertices in the order supercommuting graph.

######  Problem 5.4.

What can be said about the connectedness of super graphs when dominant
vertices are deleted?

######  Problem 5.5.

Characterize the cliques of maximum size in the conjugacy supergraphs.

## References

  * [1] L. Babai and P. J. Cameron, Automorphisms and enumeration of switching classes of tournaments, Electron. J. Combin. 7(1) (2000), article #R38.
  * [2] R. Brandl, Finite groups all of whose elements are of prime power order, Boll. Unione Mat. Ital. (5) 18 A (1981), 491–493.
  * [3] W. Burnside, Theory of Groups of Finite Order (2nd edition), Dover Publ. (reprint), New York, 1955.
  * [4] P. J. Cameron, Graphs defined on groups, Int. J. Group Theory 11 (2022), 43–124.
  * [5] P. J. Cameron and N. Maslova, Criterion of unrecognizability of a finite group by its Gruenberg–Kegel graph, arXiv 2012.01482.
  * [6] R. Dedekind, Über Gruppen, deren sämmtliche Theiler Normaltheiler sind, Math. Ann. 48 (1897), 548–561.
  * [7] P. Fitzpatrick, Order conjugacy in finite groups, Math. Proc. R. Ir. Acad. 85A (1985), 53–58.
  * [8] M. Herzog, P. Longobardi and M. Maj, On a commuting graph on conjugacy classes of groups, Comm. Algebra 37 (2009), 3369–3387.
  * [9] G. Higman, Finite groups in which every element has prime power order, J. Lond. Math. Soc. (1) 32 (1957), 335–342.
  * [10] C. Hopkins, Finite groups in which conjugate operations are commutative, Amer. J. Math. 51 (1929), 35–41.
  * [11] C. Jordan, Recherches sur les substitutions, J. Math. Pures Appl. (Liouville) 17 (1872), 351–367.
  * [12] W. Kappe, Die $A$-Norm einer Gruppe, Illinois J. Math. 5 (1961), 187–197.
  * [13] M. Korkonen, post on StackExchange, https://math.stackexchange.com/questions/816442/finite-groups-of-which-the-centralizer-of-each-element-is-normal.
  * [14] F. W. Levi, Groups in which the commutator operation satisfies certain algebraic conditions, J. Indian Math. Soc. 6 (1942), 87–97.
  * [15] A. Mohammadian and A. Erfanian, On the nilpotent conjugacy class graph of groups, Note Mat. 37(2) (2017), 77–89.
  * [16] R. K. Nath, P. Bhowal and P. J. Cameron, Solvable conjugacy class graphs, in preparation.
  * [17] L. Selvaganesh, talk in the Research Discussion on Graphs and Groups, CUSAT, Kochi, 2021.
  * [18] Jean-Pierre Serre, On a theorem of Jordan, Bull. Amer. Math. Soc. 40 (2003), 429–440.
  * [19] M. Suzuki, On a class of doubly transitive groups, Ann. Math. 75 (1962), 105–145.


# Conditional Kernel Imitation Learning for Continuous State Environments

Rishabh Agrawal1, Nathan Dahlin2, Rahul Jain1, Ashutosh Nayyar1

###### Abstract

Imitation Learning (IL) is an important paradigm within the broader
reinforcement learning (RL) methodology. Unlike most of RL, it does not assume
availability of reward-feedback. Reward inference and shaping are known to be
difficult and error-prone methods particularly when the demonstration data
comes from human experts. Classical methods such as behavioral cloning and
inverse reinforcement learning are highly sensitive to estimation errors, a
problem that is particularly acute in continuous state space problems.
Meanwhile, state-of-the-art IL algorithms convert behavioral policy learning
problems into distribution-matching problems which often require additional
online interaction data to be effective. In this paper, we consider the
problem of imitation learning in continuous state space environments based
solely on observed behavior, without access to transition dynamics
information, reward structure, or, most importantly, any additional
interactions with the environment. Our approach is based on the Markov balance
equation and introduces a novel conditional kernel density estimation-based
imitation learning framework. It involves estimating the environment’s
transition dynamics using conditional kernel density estimators and seeks to
satisfy the probabilistic balance equations for the environment. We establish
that our estimators satisfy basic asymptotic consistency requirements. Through
a series of numerical experiments on continuous state benchmark environments,
we show consistently superior empirical performance over many state-of-the-art
IL algorithms.

##  1 Introduction

Reinforcement Learning (RL) has produced a series of breakthroughs over the
last decade from exceeding human proficiency at playing simple games such as
in the Atari suite (Mnih et al. 2015) to Go (Silver et al. 2016) and StarCraft
(Vinyals et al. 2019), and to protein structure prediction systems (Jumper et
al. 2021), etc. A fundamental premise that the ‘reward is enough’ (Silver et
al. 2021) underlies all of such RL methodology. And yet, in most problems, a
natural reward function is not available. Nor it may be possible to engineer
one from intuition. Thus, a lot of effort is spent on reward shaping (Ng,
Harada, and Russell 1999) to make RL algorithms work, often without success.

This problem is particularly acute when humans are in the loop, either as
demonstrators or as evaluators. Often, demonstration data comes from human
experts and it is impossible to infer precisely what reward function human
experts really have in mind while taking actions. To be fair, several inverse
RL (IRL) algorithms such as MaxEntropy-IRL (Ziebart et al. 2008) use a
methodology wherein a reward function is first inferred from the demonstration
data, and then used in conjunction with RL algorithms to design near-optimal
policies. This has two lacunae. First, the performance of the RL algorithms
can be very sensitive to errors in the reward function estimate. And second,
the expert may not be using a policy that is optimal with respect to any
reward objective at all! There is thus a need to develop imitation learning
algorithms that do not depend on reward inference as a first step (Arora and
Doshi 2021).

Behavioral Cloning (BC) is a simple and natural idea for imitation learning
(Pomerleau 1988). It is a supervised learning scheme that aims to learn the
expert policy as a map from states to actions. In fact, it largely ignores the
inherent sequential nature of reinforcement learning problems. Unfortunately,
it suffers from severe covariate shift issues as it fails to generalize to
less-visited parts of the state space and ignores the sequential decision-
making aspect. This results in propagation of errors in the agent’s
performance (Ross and Bagnell 2010) resulting in a limited practical ability
to generalize effectively.

To address the issue of compounding errors that can afflict methods like BC,
IRL algorithms (Abbeel and Ng 2004; Ng and Russell 2000; Syed and Schapire
2007; Ziebart et al. 2008; Levine, Popovic, and Koltun 2011) take a different
approach by learning a reward function that takes into account that
transitions come from trajectories. But this requires use of reinforcement
learning algorithms, making them extremely expensive to run, and at the same
time sensitive to reward function estimation errors.

In contrast, adversarial Imitation Learning (AIL) is a technique centered
around distribution matching through adversarial learning. It gained
significant traction in the recent past as an approach to imitation learning
(Ho and Ermon 2016; Fu, Luo, and Levine 2018; Ke et al. 2021). Within this
framework, the objective transforms into finding a behavioral policy that
minimizes the divergence between the target distribution and the distribution
of state-action pairs generated by the behavioral policy during its
interaction with the environment. The primary drawback of current distribution
matching methods via AIL is that estimating distribution density ratios, a
crucial step in each iteration, usually demands samples from the behavioral
policy distribution. Consequently, new interactions with the environment are
necessary for every behavioral policy update iteration. This limitation makes
these algorithms unsuitable for problems where only offline data is available.
This downside is even more apparent in continuous state and action space
problems wherein each visited state is visited at most once, with most states
not being visited at all in the demonstration data.

A related strand of literature on imitation learning (Ross, Gordon, and
Bagnell 2011) assumes access to a generative model so trajectory data can be
generated on the fly. We make no such assumption in our problem formulation.

In this paper, we aim to develop imitation learning algorithms that do not
need reward-feedback, do not rely on distribution matching between occupation
measures, are not doing behavioral-cloning but use the ‘meta’ knowledge that
the underlying dynamics are Markovian, do not need access to a generative
model, work for continuous state space problems, and allow for batch
processing of the offline dataset. This version of the imitation learning
problem is relevant in many real-world decision-making applications, such as
medical, healthcare, robotic manipulations, and autonomous vehicles (Le Mero
et al. 2022), where experimentation is either costly or unsafe.

We introduce a simple and natural framework based on a simple premise. Namely,
that the demonstration trajectory data satisfies the balance equation between
the demonstration policy, the Markov decision process (MDP) transition density
and that of the induced Markov chain. This allows us to incorporate the fact
that the demonstration data is coming from a system with Markovian dynamics.
The transition densities for the MDP and the Markov chain are then estimated
using conditional kernel density estimators which are universal density
estimators with proven asymptotic consistency properties. We start with the
discrete state and action space setting, but then show that the framework
extends to the continuous state space setting as well. We prove consistency
properties of the estimators, and validate the algorithm in a series of
continuous state space problems. Conceptual extension to continuous action
space is straightforward but requires more work for numerical robustness.

#### Related Work.

We now discuss prior work broadly related to our paper. As already mentioned
behavioral cloning faces a fundamental limitation due to discarding
distributional insights from the demonstrations (Ross and Bagnell 2010; Piot,
Geist, and Pietquin 2014). To address this, several remedies have been
suggested (Ross, Gordon, and Bagnell 2011; Piot, Geist, and Pietquin 2016)
which involve either further online interactions with the environment, or the
demonstrator, or using insights into model dynamics or the sparsity of
rewards, all of which are in general impractical. The recent work (Xu et al.
2022) aims to overcome these by using additional data from non-expert
policies, which circumvents the need for additional online interactions but
the additional offline data may not be available. The EDM approach (Jarrett,
Bica, and van der Schaar 2020b) captures the expert’s state occupancy measure
by training an explicit energy-based model but its limitations has been
scrutinized in (Swamy et al. 2021).

There also have been efforts to further develop IRL approaches to overcome the
limitations of earlier algorithms. (Klein, Geist, and Pietquin 2011; Klein et
al. 2012) introduce LSTD-$\mu$, a temporal difference technique for
calculating feature expectations. However, these approaches share the
weaknesses of least squares estimators, being highly sensitive to basis
features and training data distribution. (Lee, Srinivasan, and Doshi-Velez
2019a) propose DSFN, which estimates feature expectations in an off-policy
setting. They also propose a transition-regularized imitation network that
produces an initial policy close to expert behavior and an efficient feature
representation. Despite these advancements, the assumption of complete
knowledge about reward feature functions in these methods can often be
unrealistic, especially for complex problems (Arora and Doshi 2021). (Piot,
Geist, and Pietquin 2014) introduced RCAL, a non-parametric algorithm that
employs a boosting method to minimize the criterion directly without feature
selection steps and can help tackle some of the above issues. (Chan and van
der Schaar 2021a) propose AVRIL, adopting a variational approach to jointly
learn an approximate posterior distribution over reward and policy. However,
due to inherent covariate shift problems, these methods encounter significant
reward extrapolation errors, leading to misguided outcomes in novel
environments and reduced learning efficiency. To address this, the CLARE (Yue
et al. 2023) model-based offline Inverse Reinforcement Learning (IRL) approach
introduces conservatism to its estimated reward. It employs an IRL algorithm
within an estimated dynamics model to learn the reward. However, limitations
arise when dealing with a limited number of expert demonstrations or
predominantly low-quality transition samples from a behavior policy. In such
cases, forcing alignment of the empirical state-action visitation measure
across all data can lead to a recovered reward or policy that mimics the
suboptimal behavior policy, undermining the accuracy of the expert model (Zeng
et al. 2023).

Adversarial Imitation Learning (AIL) approaches (Ho and Ermon 2016) were a
breakthrough when they were introduced a few years ago (Blondé and Kalousis
2019; Kostrikov et al. 2019). However, these approaches require online
interactions with the environment, and thus are not applicable when we must
work only with offline data. Employing a distribution matching strategy,
(Kostrikov, Nachum, and Tompson 2020a) introduces ValueDICE, an offline
objective for assessing the distribution ratio between the imitator and expert
policies. Although theoretically allowing for comprehensive offline learning,
the approach undertakes a complex alternating maximization-minimization
optimization procedure. Additionally, it suffers from difficulty estimating
the expectation of an exponential that introduces bias when approximating
gradients using mini-batches (Jarrett, Bica, and van der Schaar 2020b).

Thus, the algorithm we present in this paper is quite distinct in its approach
from most of the prior literature. Additionally, it demonstrates promising
preliminary empirical results.

##  2 Preliminaries

###  2.1 The Imitation Learning Problem

An infinite horizon discounted Markov decision process (MDP) $M$ is defined by
the tuple ($S,A,T,r,\gamma$) with states $s\in S$, actions $a\in A$ and
successor states $s^{\prime}\in S$ drawn from the transition function
$T(s^{\prime}|s,a)$. The reward function $r:S\times A\rightarrow\mathbb{R}$
maps state-action pairs to scalar rewards, and $\gamma$ is the discount
factor. Policy $\pi$ is a probability distribution over actions conditioned on
state and is given by $\pi(a_{t}|s_{t})=P_{\pi}(A_{t}=a_{t}|S_{t}=s_{t})$,
where $a_{t}\in A$, $s_{t}\in S$, $\forall t=0,1,2,\cdots$. The induced
occupancy measure of a policy is given as
$\rho_{\pi}(s,a):=\operatorname{\mathbb{E}}_{\pi}[\sum_{t=0}^{\infty}\gamma^{t}\operatorname{\mathbf{1}}_{s_{t}=s,a_{t}=a}]$,
where the expectation is taken over $a_{t}\sim\pi(\cdot|s_{t})$, $s_{t+1}\sim
T(\cdot|s_{t},a_{t})$ for all $t$, and the initial state $s_{0}$. The
corresponding state-only occupancy measure is given as
$\rho_{\pi}(s)=\sum_{a}\rho_{\pi}(s,a)$.

In the imitation learning (IL) framework, the agent is provided with
trajectories generated by a demonstration policy $\pi_{D}$, collected as
$D=\\{(s_{0},a_{0}),(s_{1},a_{1}),(s_{2},a_{2}),...\\}$. The data $D$ does
_not_ include the corresponding reward information $r_{t}$ at each time step.
Indeed, rather than finding the optimal policy that maximizes the long-term
reward, the IL objective is to learn a policy $\pi^{\star}$ that is close to
$\pi_{D}$ in the following sense (Yue and Le 2018):

$\pi^{\star}\in\underset{\pi\in\Pi}{\arg\min}\,\mathbb{E}_{s\sim\rho_{\pi}}[\mathcal{L}(\pi(\cdot|s),\pi_{D}(\cdot|s))],$
(1)

where $\Pi$ is the set of all randomized (Markovian) stationary policies, and
$\mathcal{L}$ is a chosen loss function. In practice, (1) can only be solved
approximately in part due to the assumption that $\pi_{D}$ is unknown and only
observed via the finite dataset $D$.

###  2.2 Conditional Kernel Density Estimation (CKDE)

The imitation learning approach we will introduce will depend on transition
density estimation. Though, statistical theory exists for it, conditional
density estimation is a difficult problem due to lack of clarity on what
parametric families of density functions are good candidates. Thus, we adopt
the kernel density estimation framework (Wand and Jones 1994) that are
provably universal probability density estimators.

We next outline the method in the case of two continuous scalar random
variables, $X$ and $Y$ for the sake of simplicity. Let $f$ and $g$ denote the
joint density of $(X,Y)$ and the marginal density of $X$, respectively. The
conditional distribution of $Y$, given $X$, is denoted as
$h_{Y|X}(y|x)=f_{X,Y}(x,y)/g_{X}(x)$.

Selecting a pair of kernel functions $K\,:\,\mathbb{R}\to\mathbb{R}$ and
$K^{\prime}\,:\,\mathbb{R}\to\mathbb{R}$ with respective scalar bandwidth
parameters $h>0$ and $h^{\prime}>0$ and given a set of $n$ samples
$\\{(x_{i},y_{i})\\}_{i=1}^{n}$, the kernel density estimation (KDE)
approximations $\widehat{f}$ and $\widehat{g}$ for the joint and marginal
distributions, respectively, are obtained as follows:

$\begin{gathered}\widehat{f}_{X,Y}(x,y)=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{h}K\bigg{(}\frac{x-x_{i}}{h}\bigg{)}\frac{1}{h^{\prime}}K^{\prime}\bigg{(}\frac{y-y_{i}}{h^{\prime}}\bigg{)},\\\
\widehat{g}_{X}(x)=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{h}K\bigg{(}\frac{x-x_{i}}{h}\bigg{)}.\end{gathered}$
(2)

Using the approximations in (2), the approximate conditional density
$\widehat{h}_{Y|X}$ can be computed as

$\widehat{h}_{Y|X}(y|x)=\frac{\widehat{f}_{X,Y}(x,y)}{\widehat{g}_{X}(x)}.$
(3)

In more general cases involving random vectors, analogous estimates to those
in (2) and (3) may be obtained using kernel functions defined according to

$K_{H}(x)=|H|^{-\frac{1}{2}}K(H^{-\frac{1}{2}}x),$ (4)

where $H$ is a symmetric positive definite bandwidth matrix of appropriate
dimension, $m$, with determinant $|H|$, and $K$ is a real-valued function
satisfying $\int_{\mathbb{R}^{m}}K(x)dx=1$. For example, the KDE estimate for
the marginal distribution of random vector $X$ is defined as

$\widehat{g}_{X}(x;H)=\frac{1}{n}\sum_{i=1}^{n}K_{H}\big{(}x-x_{i}\big{)}.$
(5)

An example of such a multivariate kernel function is the standard $m$-variate
normal density function

$K(x):=(2\pi)^{-\frac{m}{2}}\exp\left(-\frac{x^{T}x}{2}\right).$

For more details on kernel density estimation, see (Chacón and Duong 2018).

##  3 Conditional Kernel Imitation Learning

We next describe our imitation learning algorithm. A key premise of our
algorithm is that the demonstration trajectories from an expert must satisfy
the Markov balance equation under the demonstrator’s policy $\pi_{D}$, and
thus we must use that to guide the agent’s learning. The use of the balance
equation then requires estimation of certain transition (conditional
probability) density functions which we do via conditional kernel density
estimation methods. Then, the problem reduces to identifying policies that
best fit the balance equation. We elucidate this procedure in Algorithm 1,
prove its theoretical properties and then present numerical evidence of its
efficacy on a number of benchmark environments.

###  3.1 The Markov Balance Equation

Consider a demonstration policy $\pi_{D}$ that is used to take actions
starting from an initial state $s_{0}$. Let $T(s^{\prime}|s,a)$ denote the
transition density function of the MDP. Note that $\pi_{D}(a|s)$ is a
randomized Markovian, stationary policy that denotes the probability of taking
action $a$ in state $s$. This will induce a Markov chain on the state space
$S$. Let its transition density be denoted $P(s^{\prime}|s)$. Then, the Markov
balance equation is given by

$P(s^{\prime}|s)=\sum_{a}\pi_{D}(a|s)T(s^{\prime}|s,a).$

Unfortunately, this involves a sum, and hence is difficult to use. We thus,
use the following alternate form which is a transition density of the induced
Markov chain on the state-action space,

$P_{\pi_{D}}(s^{\prime},a^{\prime}|s,a)=\pi_{D}(a^{\prime}|s^{\prime})T(s^{\prime}|s,a).$
(6)

The above balance equation is the basis of our imitation learning approach. If
we can estimate $P_{\pi_{D}}$ and $T$ in (6) (estimates denoted by
$\widehat{P}$ and $\widehat{T}$ respectively), we can then infer a policy
$\pi_{D}$ that satisfies it. Unfortunately, the problem is ill-conditioned,
and we will need to impose additional criterion such as a regularization term.

We consider a parametric class of policies for the agent parametrized by
$\theta$ and formulate the following optimization problem:

$\begin{gathered}\min_{\theta\in\Theta}\int_{(s^{\prime},a^{\prime})}\int_{(s,a)}\big{[}\widehat{P}(s^{\prime},a^{\prime}|s,a)-\pi_{\theta}(a^{\prime}|s^{\prime})\widehat{T}(s^{\prime}|s,a)\big{]}^{2}\\\
\,d\mu(s,a)\,d\mu(s^{\prime},a^{\prime})-\lambda\int_{s^{\prime}}H(\pi_{\theta}(\cdot|s^{\prime}))\,d\nu(s^{\prime}).\end{gathered}$
(7)

In (7), the first term ensures that the balance equation is satisfied
approximately. The second term involves $H(\pi_{\theta}(\cdot|s^{\prime}))$,
which is the entropy of the probability distribution
$\pi_{\theta}(\cdot|s^{\prime})$ on actions when the state is $s^{\prime}$. It
penalizes less randomized policies in favor of highly randomized policies.
$\lambda\geq 0$ is a regularization parameter that governs relative weight on
the first and second terms. Here, $\mu$ and $\nu$ denote reference measures on
state-action pairs and states respectively. For example, they can be the
counting measures obtained from the dataset. $\Theta$ is a given parameter
set. The parameters could be weights of a neural network, for example.

Algorithm 1 Conditional Kernel Imitation Learning (CKIL)

Input: Expert dataset of trajectories $D$ = $\\{(s_{i},a_{i})\\}_{i=1}^{n}$
Output: $\theta^{*}$

1: Initialize policy parameter $\theta$

2: Transform dataset $D$ into $(s,a,s^{\prime},a^{\prime})$ tuples, then store
them in buffer $B$.

3: Obtain $\widehat{P},\widehat{T}$ in (10) via CKDE on $B$

4: for $iter=0,1,\ldots$ do

5: Sample a batch $b_{iter}$ of $(s,a,s^{\prime},a^{\prime})$ tuples from $B$

6: Calculate empirical estimate of the objective function in (7) using all
$(s,a,s^{\prime},a^{\prime})$ $\in b_{iter}$ as:
$\sum_{(s^{\prime},a^{\prime})}\sum_{(s,a)}\big{[}\widehat{P}(s^{\prime},a^{\prime}|s,a)-\pi_{\theta}(a^{\prime}|s^{\prime})\widehat{T}(s^{\prime}|s,a)\big{]}^{2}+\lambda\sum_{s^{\prime}}\sum_{a^{\prime}}\pi_{\theta}(a^{\prime}|s^{\prime})log(\pi_{\theta}(a^{\prime}|s^{\prime}))$
(8)

7: Update the policy parameter $\theta$ using gradient update to minimize the
calculated empirical estimate of the objective function

8: end for

9: return $\theta^{*}$

###  3.2 Transition Density Estimation

We now discuss how to use kernel density estimation methods for estimating the
two conditional densities $P_{\pi_{D}}$ and $T$. We first discuss the discrete
state and action space setting where the form of estimates is simple and
intuitive. We then discuss the continuous setup.

#### Discrete Spaces.

For environments where both the state and action spaces are discrete, the
estimates $\widehat{P}$ and $\widehat{T}$ can be calculated as:

$\begin{gathered}\widehat{T}(s^{\prime}|s,a):=\frac{\eta(s,a,s^{\prime})}{\eta(s,a)},~{}~{}\text{and}~{}~{}\\\
\widehat{P}(s^{\prime},a^{\prime}|s,a):=\frac{\eta(s,a,s^{\prime},a^{\prime})}{\eta(s,a)}\end{gathered}$
(9)

where $\eta$ denotes the counting measure, i.e., the number of times a given
tuple or sequence appears in the dataset $D$. If the counting measures in the
denominator are zero when that state-action pair is not visited at all in the
given dataset, it implies that we have no information about transitions from
it. In such cases, we will take the conditional density to be uniform.

#### Continuous Spaces.

Estimation of transition densities in this setting is more challenging since
no visited state would appear twice, and most of the states would never be
visited in any given dataset. This, thus calls for conditional density
estimation using more sophisticated methods.

These include a range of techniques such as parametric approaches like mixture
density network (Bishop 1994), normalizing flows (Trippe and Turner 2018);
non-parametric methods like Gaussian process conditional density estimation
(Dutordoir et al. 2018), CKDE (Li and Racine 2006); and semi-parametric
methods like least squares conditional density estimation (Sugiyama et al.
2010). In this study, we opt for using CKDE since it is a closed-form, non-
parametric method that can be easily implemented and adapted to different data
types. Further, CKDE provides a consistent estimator under appropriate
conditions (Chacón and Duong 2018).

As described in Section 2.2, the kernel functions use a difference between two
samples/values (e.g., $x-x_{i}$) as their argument (5). This difference can be
alternatively replaced by a suitable distance metric, as indicated in prior
work (Haasdonk and Bahlmann 2004). We define three distinct distance metrics:
one to assess the dissimilarity between (next state, next action) pairs,
another for (state, action) pairs, and a final one for next states. These
metrics are denoted as $d_{1}:(S\times A)\times(S\times
A)\rightarrow\mathbb{R_{+}}$, $d_{2}:(S\times A)\times(S\times
A)\rightarrow\mathbb{R_{+}}$, and $d_{3}:S\times S\rightarrow\mathbb{R_{+}}$
respectively. Similarly, we define $H_{1}$, $H_{2}$, and $H_{3}$ as bandwidth
matrices for the kernels $K_{H_{1}}$, $K_{H_{2}}$, and $K_{H_{3}}$,
respectively. $H_{1}$, $H_{2}$, and $H_{3}$ are square matrices with
dimensions matching those of the $(s^{\prime},a^{\prime})$ pair, $(s,a)$ pair,
and $s^{\prime}$, respectively. The CKDE approximations $\widehat{P}$ and
$\widehat{T}$ are then computed as

$\begin{gathered}\widehat{P}(s^{\prime},a^{\prime}|s,a)=\\\
\frac{\sum_{l=1}^{n}K_{H_{1}}\big{(}d_{1}((s^{\prime},a^{\prime}),(s_{l}^{\prime},a_{l}^{\prime}))\big{)}K_{H_{2}}\big{(}d_{2}((s,a),(s_{l},a_{l}))\big{)}}{\sum_{l=1}^{n}K_{H_{2}}\big{(}d_{2}((s,a),(s_{l},a_{l}))\big{)}},\vspace{0.5cm}\\\
~{}\text{and}~{}~{}\widehat{T}(s^{\prime}|s,a)=\\\
\frac{\sum_{l=1}^{n}K_{H_{3}}\big{(}d_{3}(s^{\prime},s_{l}^{\prime})\big{)}K_{H_{2}}\big{(}d_{2}((s,a),(s_{l},a_{l}))\big{)}}{\sum_{l=1}^{n}K_{H_{2}}\big{(}d_{2}((s,a),(s_{l},a_{l}))\big{)}}.\end{gathered}$
(10)

We combine the transition estimation procedures of (9) and (10) with the
balance equation based optimization problem in (7) in our conditional kernel
imitation learning (CKIL) algorithm whose pseudo-code is presented in
Algorithm 1.

###  3.3 Theoretical Guarantees

In this section, we focus on the conditional kernel density estimation part of
our approach and show that, as the training dataset size $n$ approaches
infinity, the CKDE estimates in (10) converge towards the corresponding true
conditional distributions.

Here we introduce the kernel functions $K_{i}$, $i\in\\{1,2,3\\}$, so that
using (4), the kernels $K_{H_{i}}$ for $i\in\\{1,2,3\\}$ appearing in (10)

$K_{H_{i}}(x)=|H_{i}|^{-\frac{1}{2}}K_{i}(H^{-\frac{1}{2}}x),$ (11)

where $x$ is of appropriate dimension. Our theoretical guarantee holds under
the following assumptions (Chacón and Duong 2018):

(A1)

Suppose the buffer $B$ in Algorithm 1 consists of $n$ iid tuples
$(s,a,s^{\prime},a^{\prime})$ generated according to a probability
distribution
$P(s,a,s^{\prime},a^{\prime})=\mu(s,a)P_{\pi_{D}}(s^{\prime},a^{\prime}|s,a)$,
where $P_{\pi_{D}}$ is the transition probability density of the induced
Markov chain on the state-action space under the demonstration policy
$\pi_{D}$ (see (6)) and $\mu$ is a reference measure on $(s,a)$. Further, $P$
has a density function $g$ that is square-integrable and twice differentiable,
with all of its second-order partial derivatives bounded, continuous and
square integrable. Also assume that the marginals $P(s^{\prime},s,a)$ and
$P(s,a)$ satisfy these properties.

(A2)

The kernels $K_{i}$ for $i\in\\{1,2,3\\}$ in (11) are square integrable, zero-
mean, spherically symmetric, and with common finite second-order moment
$\int_{\mathbb{R}^{m_{i}}}zz^{T}K_{i}(z)dz=\sigma^{2}I_{m_{i}}$.

(A3)

For each kernel $K_{H_{i}}$ as defined in (4), the bandwidth matrices
$H_{i}(n)$ (where $n$ is the number of tuples in $B$) form a sequence of
positive definite, symmetric matrices such that $H_{i}(n)\rightarrow 0$ and
$n^{-1/2}|{H_{i}(n)}|^{-1/2}\rightarrow 0$ as $n\rightarrow\infty$.

######  Theorem 1.

Suppose assumptions (A1)-(A3) are true. Let $\widehat{P}_{n}$ and
$\widehat{T}_{n}$ be the CKDE estimates constructed using (10) and a buffer
$B$ with $n$ tuples. Then, for each $(s,a,s^{\prime},a^{\prime})$, as
$n\rightarrow\infty$,

$\displaystyle\widehat{P}_{n}(s^{\prime},a^{\prime}|s,a){\stackrel{{\scriptstyle
P}}{{\parbox{28.45274pt}{\rightarrowfill}}}}P_{\pi_{D}}(s^{\prime},a^{\prime}|s,a),$
$\displaystyle\widehat{T}_{n}(s^{\prime}|s,a){\stackrel{{\scriptstyle
P}}{{\parbox{28.45274pt}{\rightarrowfill}}}}T(s^{\prime}|s,a).$ (12)

###### Proof.

Let $\widehat{f}(\cdot)$ and $\widehat{g}(\cdot)$ represent the numerator and
denominator of $\widehat{T}(s^{\prime}|s,a)$ respectively from (10), i.e.,

$\begin{gathered}\widehat{f}(s^{\prime},s,a)=\sum_{l=1}^{n}K_{H_{3}}\big{(}d_{3}(s^{\prime},s_{l}^{\prime})\big{)}K_{H_{2}}\big{(}d_{2}((s,a),(s_{l},a_{l}))\big{)},\\\
\widehat{g}(s,a)=\sum_{l=1}^{n}K_{H_{2}}\big{(}d_{2}((s,a),(s_{l},a_{l}))\big{)}.\end{gathered}$
(13)

$\widehat{f}(\cdot)$ and $\widehat{g}(\cdot)$ are, in fact, the KDEs of
$P(s,a,s^{\prime})$ and $P(s,a)$, where $P(s,a,s^{\prime})$ and $P(s,a)$ are
marginals of $P(s,a,s^{\prime},a^{\prime})$ mentioned in Assumption (A1).

We now show why Lemma 2, given in Appendix, can be adopted to prove this
theorem under assumptions (A1)-(A3). We argue as follows:

  1. 1.

We assume (A1) that $P(s,a,s^{\prime},a^{\prime})$ has a density function $g$
that is square-integrable and twice differentiable, with all of its second-
order partial derivatives bounded, continuous and square integrable and so
does its marginals $P(s^{\prime},s,a)$ and $P(s,a)$. This leads to the
satisfaction of condition (C1).

  2. 2.

From assumption (A2), $\int_{\mathbb{R}^{m_{i}}}zK_{i}(z)dz=0$ for
$i=\\{2,3\\}$, where $z_{i}$ is a vector of size $m_{i}$. Partition the vector
$z$ as $z=[z_{3},z_{2}]$ and let $m=m_{2}+m_{3}$ and
$K(z)=K_{3}(z_{3})K_{2}(z_{2})$. Then for $t\leq m_{3}$,

$\begin{split}&\int_{\mathbb{R}^{m}}z_{t}K(z)dz=\int_{\mathbb{R}^{m}}z_{t}K_{3}(z_{3})K_{2}(z_{2})dz\\\
&\quad=\int_{\mathbb{R}^{m_{2}}}K_{2}(z_{2})dz_{2}\int_{\mathbb{R}^{m_{3}}}z_{t}K_{3}(z_{3})dz_{3}\\\
&\quad=\int_{\mathbb{R}^{m_{3}}}z_{t}K_{3}(z_{3})dz_{3}=0,\end{split}$ (14)

which follows from (A2). This can be shown for any $t\in\\{1,2,\ldots,m\\}$.
Hence, $\int_{\mathbb{R}^{m}}zK(z)dz=0$ is satisfied corresponding to
condition (C2).

Now,

$\begin{split}&\int_{\mathbb{R}^{m}}zz^{T}K(z)dz\\\
&\qquad=\int_{\mathbb{R}^{m}}\begin{bmatrix}z_{3}z_{3}^{T}&z_{3}z_{2}^{T}\\\
z_{2}z_{3}^{T}&z_{2}z_{2}^{T}\\\
\end{bmatrix}K_{3}(z_{3})K_{2}(z_{2})dz_{3}dz_{2}\\\
&\qquad=\sigma^{2}\begin{bmatrix}I_{m_{3}}&0\\\
0&I_{m_{2}}\end{bmatrix}=\sigma^{2}I_{m}.\end{split}$

Hence, $K(z)=K_{3}(z_{3})K_{2}(z_{2})$ satisfies condition (C2).

  3. 3.

Consider $H(n)$ to be a block diagonal matrix with $H_{3}(n)$ and $H_{2}(n)$
as the two block diagonal entries with $H_{3}(n)$ and $H_{2}(n)$ satisfying
assumption (A3). Then the matrices $H(n)$ form a sequence of positive
definite, symmetric matrices. Using (5) with this $H$, the kernel estimate for
$P(s^{\prime},s,a)$ takes the product kernel form as seen for
$\widehat{f}(\cdot)$ in (13). Now, $|H(n)|=|H_{3}(n)||H_{2}(n)|$, this implies
that as $n\rightarrow\infty$, $n^{-1}|H(n)|^{-1/2}\rightarrow 0$ because
$n^{-1/2}|H_{i}(n)|^{-1/2}\rightarrow 0$ for $i=\\{2,3\\}$. Also, vec
$H(n)\rightarrow 0$ as vec $H_{i}(n)\rightarrow 0$ for $i=\\{2,3\\}$.
Therefore, condition (C3) is satisfied.

Having satisfied conditions (C1)-(C3), we may apply the argument found in
Sections 2.6-2.9 of (Chacón and Duong 2018) and conclude that

$\begin{gathered}\widehat{f}(s^{\prime},s,a){\stackrel{{\scriptstyle
P}}{{\parbox{28.45274pt}{\rightarrowfill}}}}P(s^{\prime},s,a),\\\
\widehat{g}(s,a){\stackrel{{\scriptstyle
P}}{{\parbox{28.45274pt}{\rightarrowfill}}}}P(s,a).\end{gathered}$

It follows from the Continuous Mapping Theorem (Mann and Wald 1943) that
taking the ratio of $\widehat{f}$ and $\widehat{g}$ produces a consistent
estimator of $\frac{P(s^{\prime},s,a)}{P(s,a)}=T(s^{\prime}|s,a)$. That is,
$\widehat{T}_{n}(s^{\prime}|s,a)=\frac{\widehat{f}(s^{\prime},s,a)}{\widehat{g}(s,a)}{\stackrel{{\scriptstyle
P}}{{\parbox{28.45274pt}{\rightarrowfill}}}}T(s^{\prime}|s,a)$.

A similar approach can be used for establishing the asymptotic convergence in
probability for the CKDE of $P_{\pi_{D}}(s^{\prime},a^{\prime}|s,a)$.

∎

Figure 1: Average rewards attained by the CKIL agent in a discretized
MountainCar environment for a varying number of trajectories (higher values
indicate better performance).

##  4 Experimental Results

###  4.1 Experimental Setup

We now validate the empirical performance of the CKIL algorithm on a number of
benchmark environments from Open AI Gym (Brockman et al. 2016). These
encompass environments of varying complexities used in the RL literature.
These include the MountainCar environment, where the goal is to reach the top
of the mountain (Moore 1990); CartPole, which aims to balance a pendulum on a
frictionless track (Barto, Sutton, and Anderson 1983); Acrobot, which aims to
swing limbs around a system of joints to achieve a specified height (Sutton
1995); and LunarLander, which aims to optimize a rocket’s trajectory to
achieve a successful landing (Klimov 2019).

To create a demonstration dataset D, we generate data using pre-trained and
hyperparameter-optimized agents available in the RL Baselines Zoo (Raffin
2020). In particular, we used a PPO agent for LunarLander-v2, a DQN agent for
CartPole-v1 and an A2C agent for Acrobot-v1.

##### Benchmark Algorithms.

We compare the performance of our CKIL algorithm (Algorithm 1), with a range
of offline IRL/IL/AIL benchmarks. This comprehensive assessment covers a
spectrum of methodologies, including the inherently offline Behavioral Cloning
(BC); ValueDICE (VDICE), a sample-efficient AIL approach designed for offline
scenarios by removing replay regularization; reward-regularized classification
(RCAL), a large margin classification approach, which introduces a sparsity-
based penalty on inferred rewards to exploit dynamics information; Energy-
based Distribution Matching (EDM), an offline imitation learning algorithm
that captures the expert’s state occupancy patterns through explicit training
of an energy-based model; AVRIL, a recent model-free offline IRL technique
employing a variational approach to simultaneously learn an approximate
posterior distribution over rewards and policies; and Deep Successor Feature
Network (DSFN), an offline adaptation of the max-margin IRL algorithm that
transcends linear approaches by introducing a deep network architecture and
employing least-squares temporal-difference learning to produce both reward
and policy outputs.

BCVDICERCALEDMAVRILDSFNCKILExpertRandom

(a) Acrobot

(b) CartPole

(c) LunarLander

Figure 2: Average rewards achieved by benchmark IRL/IL/AIL and CKIL policies
during real-time deployment plotted against the number of trajectories
included in demonstration dataset $D$ (higher values indicate better
performance).

##### Implementation.

The policy $\pi_{\theta}$ in (8) is embodied by a neural network (NN)
architecture. This NN comprises two hidden layers featuring the Rectified
Linear Unit (ReLU) activation function. The final layer employs a softmax
function to produce a probability distribution over actions when given a state
as an input. To facilitate comparison, all benchmarks adopt a common neural
network architecture consisting of two hidden layers comprising 64 units each,
with Exponential Linear Unit (ELU) activation functions. Training is carried
out using the Adam optimizer (Kingma and Ba 2015) with individually tuned
learning rates.

In the case of VDICE, we used the publicly available source code provided at
(Kostrikov, Nachum, and Tompson 2020b). It is worth noting that, for VDICE,
offline learning is achieved by configuring the “replay regularization”
coefficient to zero. Our execution of EDM leveraged the source code accessible
at (Jarrett, Bica, and van der Schaar 2020a). It is essential to highlight
that the contrast between BC and EDM predominantly stems from the introduction
of $L_{\rho}$, an occupancy loss defined in the EDM work, while deriving the
RCAL loss is a straightforward process involving the inversion of the Bellman
equation. As for AVRIL and DSFN, the applicable source codes are accessible at
(Chan and van der Schaar 2021b), (Lee, Srinivasan, and Doshi-Velez 2019b)
respectively. Additional specifics regarding the experimental setup and
benchmarks implementations are available in the Appendix.

##### Choice of Kernel.

We utilize the Gaussian kernel due to its universal nature, i.e, its capacity
to uniformly approximate arbitrary continuous target functions on any compact
subset of the input space (Micchelli, Xu, and Zhang 2006). Moreover, its
properties such as square integrability, finite second-order moment, and
spherical symmetry are desirable properties for density estimation,
facilitating the asymptotic convergence of the conditional kernel density
estimator to the true conditional density.

We consider a Euclidean distance metric for $d_{1}$, $d_{2}$, and $d_{3}$ and
utilize a diagonal bandwidth matrix with the same values across its diagonal
elements. These matrices can then be denoted as $H_{i}=h_{i}I_{m_{i}}$, where
$m_{i}$ is the corresponding appropriate dimension for $i=1,2,3$. Here, each
$h_{i}$ is treated as a hyper-parameter and we tuned these in our experimental
work depending on what yielded better performance. We would like to emphasize
that in prior research (Mammen et al. 2011; Schölkopf and Smola 2002;
Silverman 1986; Ahmad and Ran 2004), approaches for systematic selection of
bandwidth parameters, which should decrease as the dataset size grows, have
been developed. These methods can be applied to more intricate problems where
manual tuning is impractical. Specific values of $h_{i}$ employed for various
experiments are detailed in the Appendix.

###  4.2 Results

#### Discrete States and Actions.

We first consider the discretized mountain car problem (Moore 1990) as an
example of a discrete state and action space environment. To that end, we
transformed the original continuous $2$-dimensional state space of the
MountainCar environment into a grid configuration measuring $15$ by $15$.
Subsequently, we estimate $\widehat{P}$ and $\widehat{T}$ using equation (9).
The dataset $D$ is generated using the policy outlined in (Xiao 2019). We
begin with one trajectory in $D$, and increase to $50$ trajectories, with
observations summarized in Figure 1. With more data, we see that the CKIL
agent’s performance improves and achieves expert-level proficiency with 50
trajectories.

#### Continuous States.

We next address our main goal, namely imitation learning for continuous state
environments. When provided ample demonstration data, all benchmarks exhibit
the capability to attain performance comparable to the demonstrator level.
Thus, we evaluate the algorithms’ capacity to manage sample complexity in
scenarios with limited data. To achieve this, we assess their performance
while granting access to a specific number of trajectories, which we vary.
This setup mirrors the configuration described in (Jarrett, Bica, and van der
Schaar 2020b). We vary the amount of demonstration data D, ranging from a
single trajectory to 15, to illustrate the sample complexity concept.

The algorithms used a batch of 1, 3, 7, 10, or 15 trajectories, each uniformly
drawn from a pool of 1000 expert trajectories. Subsequently, each algorithm
underwent a training phase until convergence. For testing, 300 live roll-outs
were conducted in the simulated environment, during which the average
accumulated reward for each episode was measured. This entire process was
repeated 10 times, utilizing diverse initialization and observed trajectories
in each iteration.

Figure 2 illustrates the average rewards for policies learned by different
algorithms with increasing numbers of demonstration trajectories. Across all
tasks, the results showcase CKIL’s capability to learn effective policies,
manifesting robust and consistently superior performance compared to other
well-known algorithms, especially when data is scarce.

Remarkably, even with a mere single expert trajectory, CKIL manages to attain
expert-level performance in the Acrobot environment, and it approaches expert-
level performance in the CartPole environment. Moreover, employing only three
trajectories enables it to achieve expert-level performance on the CartPole
environment. In the LunarLander environment, a substantial performance
enhancement becomes evident within $3$ trajectories. At this juncture, the
agent’s performance nearly matches that of an expert, surpassing all benchmark
algorithms by a considerable margin.

Additionally, it is worth highlighting that within the confines of this
exclusively batch-oriented context, the off-policy adaptations of online
algorithms (VDICE, DSFN) do not exhibit the same degree of consistent
performance as their inherently offline counterparts. This highlights the
inadequacy of solely adopting online algorithms in offline scenarios.
Furthermore, the challenges associated with estimating the expectation of an
exponential distribution may contribute to VDICE’s potential under-performance
when compared to the baseline behavioral cloning algorithm.

##  5 Conclusions

In this paper, we introduce Conditional Kernel Imitation Learning (CKIL), a
simple but novel approach to imitation learning for continuous state space
problems. The approach depends on finding policies that satisfy a Markov
balance equation, and hence incorporates the sequential nature of the problem
in a natural way. It uses conditional kernel density estimators for estimating
transition densities of the MDP and the induced Markov chain and allows for
behavioral policies to be represented as neural networks, thus both together
making the applicability of the approach to be almost universal. Furthermore,
it does not need access to a generative model or further online interaction
data, does not first need reward inference, does not do distribution matching,
and allows for batch processing of offline data for scalability. It also makes
no assumptions about the form of the transition densities, nor of course of
the reward function. The algorithm is supported by theoretical consistency
results about the estimators, and furthermore, shows remarkably good empirical
performance as compared to almost all state-of-the-art IL, IRL, and AIL
algorithms against which comparison is meaningful on a number of continuous
state OpenAI Gym benchmark environments.

There are a number of interesting directions for future work. Since the method
relies on kernel density estimation, scalability to high-dimensional problems
needs to be addressed. One potential remedy involves exploring a modified
version of CKDE designed to enhance computational efficiency (Holmes, Gray,
and Isbell 2007). Given that our framework is fundamentally rooted in the
estimation of conditional probability densities, it readily lends itself to
adaptations that can incorporate choices for substituting the CKDE, as
evidenced in various alternative approaches (Wang and Scott 2019), (Rothfuss
et al. 2019), (Dutordoir et al. 2018). In fact, conditional densities
themselves could have non-parametric representions. There is also scope for
deeper and more detailed theoretical analysis, including non-asymptotic sample
complexity bounds. Such bounds are rarely available in the current literature
for IL, IRL or AIL algorithms.

## References

  * Abbeel and Ng (2004) Abbeel, P.; and Ng, A. Y. 2004.  Apprenticeship Learning via Inverse Reinforcement Learning.  In _Proceedings of the Twenty-First International Conference on Machine Learning_.
  * Ahmad and Ran (2004) Ahmad, I. A.; and Ran, I. S. 2004.  Data based bandwidth selection in kernel density estimation with parametric start via kernel contrasts.  _Journal of Nonparametric Statistics_ , 16(6): 841–877.
  * Arora and Doshi (2021) Arora, S.; and Doshi, P. 2021.  A survey of inverse reinforcement learning: Challenges, methods and progress.  _Artificial Intelligence_ , 297: 103500.
  * Barto, Sutton, and Anderson (1983) Barto, A. G.; Sutton, R. S.; and Anderson, C. W. 1983.  Neuronlike adaptive elements that can solve difficult learning control problems.  _IEEE Transactions on Systems, Man, and Cybernetics_ , SMC-13(5): 834–846.
  * Bishop (1994) Bishop, C. 1994.  Mixture density networks.  Technical report, Aston University.
  * Blondé and Kalousis (2019) Blondé, L.; and Kalousis, A. 2019.  Sample-efficient imitation learning via generative adversarial nets.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , 3138–3148. PMLR.
  * Brockman et al. (2016) Brockman, G.; Cheung, V.; Pettersson, L.; Schneider, J.; Schulman, J.; Tang, J.; and Zaremba, W. 2016.  Openai gym.  _arXiv preprint arXiv:1606.01540_.
  * Chacón and Duong (2018) Chacón, J. E.; and Duong, T. 2018.  _Multivariate kernel smoothing and its applications_.  Chapman and Hall/CRC.
  * Chan and van der Schaar (2021a) Chan, A. J.; and van der Schaar, M. 2021a.  Scalable Bayesian Inverse Reinforcement Learning.  In _International Conference on Learning Representations_.
  * Chan and van der Schaar (2021b) Chan, A. J.; and van der Schaar, M. 2021b.  Scalable Bayesian Inverse Reinforcement Learning.  https://github.com/XanderJC/scalable-birl.
  * Dutordoir et al. (2018) Dutordoir, V.; Salimbeni, H.; Hensman, J.; and Deisenroth, M. 2018.  Gaussian process conditional density estimation.  _Advances in neural information processing systems_ , 31.
  * Fu, Luo, and Levine (2018) Fu, J.; Luo, K.; and Levine, S. 2018.  Learning Robust Rewards with Adverserial Inverse Reinforcement Learning.  In _International Conference on Learning Representations_.
  * Haasdonk and Bahlmann (2004) Haasdonk, B.; and Bahlmann, C. 2004.  Learning with distance substitution kernels.  In _Joint pattern recognition symposium_ , 220–227. Springer.
  * Ho and Ermon (2016) Ho, J.; and Ermon, S. 2016.  Generative adversarial imitation learning.  _Advances in neural information processing systems_ , 29.
  * Holmes, Gray, and Isbell (2007) Holmes, M. P.; Gray, A. G.; and Isbell, C. L. 2007.  Fast Nonparametric Conditional Density Estimation.  In _Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence_ , 175–182.
  * Jarrett, Bica, and van der Schaar (2020a) Jarrett, D.; Bica, I.; and van der Schaar, M. 2020a.  Strictly Batch imitation learning by Batch Imitation Learning by Energy-based Distribution Matching.  https://github.com/vanderschaarlab/mlforhealthlabpub/tree/main/alg/edm.
  * Jarrett, Bica, and van der Schaar (2020b) Jarrett, D.; Bica, I.; and van der Schaar, M. 2020b.  Strictly batch imitation learning by energy-based distribution matching.  _Advances in Neural Information Processing Systems_ , 33: 7354–7365.
  * Jumper et al. (2021) Jumper, J.; Evans, R.; Pritzel, A.; Green, T.; Figurnov, M.; Ronneberger, O.; Tunyasuvunakool, K.; Bates, R.; Žídek, A.; Potapenko, A.; et al. 2021\.  Highly accurate protein structure prediction with AlphaFold.  _Nature_ , 596(7873): 583–589.
  * Ke et al. (2021) Ke, L.; Choudhury, S.; Barnes, M.; Sun, W.; Lee, G.; and Srinivasa, S. 2021.  Imitation learning as f-divergence minimization.  In _Algorithmic Foundations of Robotics XIV: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics 14_ , 313–329. Springer.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A Method for Stochastic Optimization.  In _3rd International Conference on Learning Representations_.
  * Klein, Geist, and Pietquin (2011) Klein, E.; Geist, M.; and Pietquin, O. 2011.  Batch, off-policy and model-free apprenticeship learning.  In _European Workshop on Reinforcement Learning_ , 285–296. Springer.
  * Klein et al. (2012) Klein, E.; Geist, M.; Piot, B.; and Pietquin, O. 2012.  Inverse reinforcement learning through structured classification.  _Advances in neural information processing systems_ , 25.
  * Klimov (2019) Klimov, O. 2019.  Openai gym: Rocket trajectory optimization is a classic topic in optimal control.  https://github.com/openai/gym.
  * Kostrikov et al. (2019) Kostrikov, I.; Agrawal, K. K.; Dwibedi, D.; Levine, S.; and Tompson, J. 2019.  Discriminator-Actor-Critic: Addressing Sample Inefficiency and Reward Bias in Adversarial Imitation Learning.  In _International Conference on Learning Representations_.
  * Kostrikov, Nachum, and Tompson (2020a) Kostrikov, I.; Nachum, O.; and Tompson, J. 2020a.  Imitation Learning via Off-Policy Distribution Matching.  In _International Conference on Learning Representations_.
  * Kostrikov, Nachum, and Tompson (2020b) Kostrikov, I.; Nachum, O.; and Tompson, J. 2020b.  Imitation Learning via Off-Policy Distribution Matching.  https://github.com/google-research/google-research/tree/master/value˙dice.
  * Le Mero et al. (2022) Le Mero, L.; Yi, D.; Dianati, M.; and Mouzakitis, A. 2022.  A survey on imitation learning techniques for end-to-end autonomous vehicles.  _IEEE Transactions on Intelligent Transportation Systems_ , 23(9): 14128–14147.
  * Lee, Srinivasan, and Doshi-Velez (2019a) Lee, D.; Srinivasan, S.; and Doshi-Velez, F. 2019a.  Truly Batch Apprenticeship Learning with Deep Successor Features.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence_ , 5909–5915.
  * Lee, Srinivasan, and Doshi-Velez (2019b) Lee, D.; Srinivasan, S.; and Doshi-Velez, F. 2019b.  Truly Batch Apprenticeship Learning with Deep Successor Features.  https://github.com/dtak/batch-apprenticeship-learning.
  * Levine, Popovic, and Koltun (2011) Levine, S.; Popovic, Z.; and Koltun, V. 2011.  Nonlinear inverse reinforcement learning with gaussian processes.  _Advances in neural information processing systems_ , 24.
  * Li and Racine (2006) Li, Q.; and Racine, J. S. 2006.  _Nonparametric Econometrics: Theory and Practice_.  Number 8355 in Economics Books. Princeton University Press.
  * Mammen et al. (2011) Mammen, E.; Martinez Miranda, M. D.; Nielsen, J. P.; and Sperlich, S. 2011.  Do-validation for kernel density estimation.  _Journal of the American Statistical Association_ , 106(494): 651–660.
  * Mann and Wald (1943) Mann, H. B.; and Wald, A. 1943.  On stochastic limit and order relationships.  _The Annals of Mathematical Statistics_ , 14(3): 217–226.
  * Micchelli, Xu, and Zhang (2006) Micchelli, C. A.; Xu, Y.; and Zhang, H. 2006.  Universal Kernels.  _Journal of Machine Learning Research_ , 7(12): 2651–2667.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M.; Fidjeland, A. K.; Ostrovski, G.; et al. 2015\.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540): 529–533.
  * Moore (1990) Moore, A. W. 1990.  Efficient Memory-based Learning for Robot Control.  Technical report, University of Cambridge.
  * Ng, Harada, and Russell (1999) Ng, A. Y.; Harada, D.; and Russell, S. J. 1999.  Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping.  In _Proceedings of the Sixteenth International Conference on Machine Learning_ , volume 99, 278–287.
  * Ng and Russell (2000) Ng, A. Y.; and Russell, S. J. 2000.  Algorithms for Inverse Reinforcement Learning.  In _Proceedings of the Seventeenth International Conference on Machine Learning_ , 663–670.
  * Piot, Geist, and Pietquin (2014) Piot, B.; Geist, M.; and Pietquin, O. 2014.  Boosted and Reward-Regularized Classification for Apprenticeship Learning.  In _Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems_ , 1249–1256.
  * Piot, Geist, and Pietquin (2016) Piot, B.; Geist, M.; and Pietquin, O. 2016.  Bridging the gap between imitation learning and inverse reinforcement learning.  _IEEE transactions on neural networks and learning systems_ , 28(8): 1814–1826.
  * Pomerleau (1988) Pomerleau, D. A. 1988.  Alvinn: An autonomous land vehicle in a neural network.  _Advances in neural information processing systems_ , 1: 305–313.
  * Raffin (2020) Raffin, A. 2020.  RL Baselines3 Zoo.  https://github.com/DLR-RM/rl-baselines3-zoo.
  * Ross and Bagnell (2010) Ross, S.; and Bagnell, D. 2010.  Efficient reductions for imitation learning.  In _Proceedings of the thirteenth international conference on artificial intelligence and statistics_ , 661–668. JMLR Workshop and Conference Proceedings.
  * Ross, Gordon, and Bagnell (2011) Ross, S.; Gordon, G.; and Bagnell, D. 2011.  A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , volume 15, 627–635.
  * Rothfuss et al. (2019) Rothfuss, J.; Ferreira, F.; Walther, S.; and Ulrich, M. 2019.  Conditional density estimation with neural networks: Best practices and benchmarks.  _arXiv preprint arXiv:1903.00954_.
  * Schölkopf and Smola (2002) Schölkopf, B.; and Smola, A. J. 2002.  _Learning with kernels : support vector machines, regularization, optimization, and beyond_.  MIT Press.
  * Silver et al. (2016) Silver, D.; Huang, A.; Maddison, C. J.; Guez, A.; Sifre, L.; Van Den Driessche, G.; Schrittwieser, J.; Antonoglou, I.; Panneershelvam, V.; Lanctot, M.; et al. 2016.  Mastering the game of Go with deep neural networks and tree search.  _nature_ , 529(7587): 484–489.
  * Silver et al. (2021) Silver, D.; Singh, S.; Precup, D.; and Sutton, R. S. 2021.  Reward is enough.  _Artificial Intelligence_ , 299: 103535.
  * Silverman (1986) Silverman, B. W. 1986.  _Density Estimation for Statistics and Data Analysis_.  Chapman & Hall.
  * Sugiyama et al. (2010) Sugiyama, M.; Takeuchi, I.; Suzuki, T.; Kanamori, T.; Hachiya, H.; and Okanohara, D. 2010.  Least-squares conditional density estimation.  _IEICE Transactions on Information and Systems_ , 93(3): 583–594.
  * Sutton (1995) Sutton, R. S. 1995.  Generalization in reinforcement learning: Successful examples using sparse coarse coding.  _Advances in neural information processing systems_ , 8.
  * Swamy et al. (2021) Swamy, G.; Choudhury, S.; Bagnell, J. A.; and Wu, Z. S. 2021.  A Critique of Strictly Batch Imitation Learning.  _arXiv preprint arXiv:2110.02063_.
  * Syed and Schapire (2007) Syed, U.; and Schapire, R. E. 2007.  A game-theoretic approach to apprenticeship learning.  _Advances in neural information processing systems_ , 20.
  * Trippe and Turner (2018) Trippe, B. L.; and Turner, R. E. 2018.  Conditional density estimation with bayesian normalising flows.  _arXiv preprint arXiv:1802.04908_.
  * Vinyals et al. (2019) Vinyals, O.; Babuschkin, I.; Czarnecki, W. M.; Mathieu, M.; Dudzik, A.; Chung, J.; Choi, D. H.; Powell, R.; Ewalds, T.; Georgiev, P.; et al. 2019.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ , 575(7782): 350–354.
  * Wand and Jones (1994) Wand, M. P.; and Jones, M. C. 1994.  _Kernel smoothing_.  CRC press.
  * Wang and Scott (2019) Wang, Z.; and Scott, D. W. 2019.  Nonparametric density estimation for high-dimensional data—Algorithms and applications.  _Wiley Interdisciplinary Reviews: Computational Statistics_ , 11(4): e1461.
  * Xiao (2019) Xiao, Z. 2019.  _Reinforcement Learning: Theory and Python Implementation_.  China Machine Press.
  * Xu et al. (2022) Xu, H.; Zhan, X.; Yin, H.; and Qin, H. 2022.  Discriminator-weighted offline imitation learning from suboptimal demonstrations.  In _International Conference on Machine Learning_ , 24725–24742. PMLR.
  * Yue et al. (2023) Yue, S.; Wang, G.; Shao, W.; Zhang, Z.; Lin, S.; Ren, J.; and Zhang, J. 2023.  CLARE: Conservative Model-Based Reward Learning for Offline Inverse Reinforcement Learning.  In _The Eleventh International Conference on Learning Representations_.
  * Yue and Le (2018) Yue, Y.; and Le, H. M. 2018.  Imitation learning (Tutorial).  _International Conference on Machine Learning (ICML)_.
  * Zeng et al. (2023) Zeng, S.; Li, C.; Garcia, A.; and Hong, M. 2023.  Understanding Expertise through Demonstrations: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning.  _arXiv preprint arXiv:2302.07457_.
  * Ziebart et al. (2008) Ziebart, B. D.; Maas, A.; Bagnell, J. A.; and Dey, A. K. 2008.  Maximum Entropy Inverse Reinforcement Learning.  In _Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 3_ , 1433–1438. AAAI Press.

##  6 Appendix

###  6.1 Lemma used in Theoretical Guarantees subsection 3.3

We state the following technical lemma for convergence in probability of
kernel density estimators from i.i.d samples which we used for Theorem 1.

######  Lemma 2.

(Chacón and Duong 2018) Suppose $X_{1},X_{2},\ldots,X_{n}$ are i.i.d vectors
with probability density $g$. Let $\widehat{g}(\cdot;H)$, as given in Eq. (5),
be the kernel density estimator constructed from these samples using kernel
$K$ and bandwidth matrix $H=H(n)$. Suppose the following assumptions hold.

(C1)

Each entry of $\mathcal{H}_{g}(\cdot)$ be piecewise continuous and square
integrable, where $\mathcal{H}_{g}$ is the $m\times m$ Hessian-matrix of $g$.

(C2)

The kernel $K$, is square integrable, spherically symmetric and with a finite
second order moment; this means that $\int_{\mathbb{R}^{m}}zK(z)dz=0$ and
$\int_{\mathbb{R}^{m}}zz^{T}K(z)dz=m_{2}(K)$$I_{m}$ (where $m_{2}(K)$ is
independent of $i$, for $i\in\\{1,2,\ldots m\\}$). Furthermore,
$\int_{\mathbb{R}^{m}}K(z)=1$.

(C3)

The bandwidth matrices $H=H(n)$ form a sequence of positive definite,
symmetric matrices such that as $n\rightarrow\infty$, vec $H(n)\rightarrow 0$,
i.e. all entries of $H(n)$ approaches $0$ and $n^{-1}|H(n)|^{-1/2}\rightarrow
0$, where vec is the vectorization operator which acts on a matrix by stacking
its columns on top of one another.

Then, $\widehat{g}(\boldsymbol{x};H)$ converges in probability to
$g(\boldsymbol{x})$ for each $\boldsymbol{x}$.