# On the asymptotic distribution of the symmetrized Chatterjee’s correlation
coefficient

Qingyang Zhang
Department of Mathematical Sciences, University of Arkansas, AR 72701
Email<EMAIL_ADDRESS>
###### Abstract

Chatterjee (2021) introduced an asymmetric correlation measure that has
attracted much attention over the past year. In this paper, we derive the
asymptotic distribution of the symmetric version of Chatterjee’s correlation,
and suggest a finite sample test for independence.

Keywords: Chatterjee’s correlation; asymptotic normality; asymptotic
independence; finite sample test

##  1 Introduction

Suppose $X$ and $Y$ are two continuous random scalars, and
$\\{(X_{1},Y_{1}),...,(X_{n},Y_{n})\\}$ are $n$ i.i.d. samples from $(X,Y)$.
In this paper, we are interested in the following classical independence test

$\displaystyle H_{0}$ $\displaystyle:X\perp Y,$ $\displaystyle H_{a}$
$\displaystyle:X\not\perp Y.$

The problem of testing independence has been examined from a number of
perspectives. For instance, Pfister et al. (2018) introduced a kernel-based
test for joint independence between multiple variables [1]. In their seminal
work, Székely et al. proposed a distance-based measure to test the association
between random vectors of arbitrary dimensions [2]. Bergsma & Dassios (2014)
defined a consistent test based on the sign covariance which is closely
related to Kendall’s $\tau$ [3]. Schweizer & Wolff (1981) used copulas to
obtain several nonparametric measures of dependence that satisfy Renyi’s
conditions [4]. There are many other proposals including a graph-theoretic
measure [5] and the maximal information coefficient [6].

Recently, Chatterjee (2021) introduced a novel correlation coefficient based
on simple rank statistics [7]. His test has quickly attracted much attention
as it is distribution-free, consistent against all fixed alternatives, and
asymptotically normal under independence. We begin with a brief review of this
test. Suppose $X_{i}$’s and $Y_{i}$’s have no ties, there is a unique way to
rearrange the data (with respect to $X$) as
$(X_{(1)},Y_{X(1)}),...,(X_{(n)},Y_{X(n)})$, where $X_{(1)}<\cdots<X_{(n)}$
and $\\{Y_{X(1)},...,Y_{X(n)}\\}$ denote the concomitants. Let $R(Y_{X(i)})$
be the rank of $Y_{X(i)}$, i.e.,
$R(Y_{X(i)})=\sum_{j=1}^{n}\mathbbm{1}\\{Y_{(j)}\leq Y_{X(i)}\\}$, Chatterjee
defined the following correlation coefficient

$\xi_{n}(X,Y)=1-\frac{3}{n^{2}-1}\sum_{i=1}^{n-1}|R(Y_{X(i+1)})-R(Y_{X(i)})|,$
(1)

and showed that $\xi_{n}(X,Y)$ consistently estimates Dette-Siburg-Stoimenov’s
correlation [8]

$\xi(X,Y)=\frac{\int V(E(\mathbbm{1}\\{Y\geq t|X\\}))dF_{Y}(t)}{\int
V(\mathbbm{1}\\{Y\geq t\\})dF_{Y}(t)}.$

It is not hard to see that the population quantity $\xi(X,Y)$ is between 0 and
1, since $V(\mathbbm{1}\\{Y\geq t\\})\geq V(E(\mathbbm{1}\\{Y\geq t|X\\}))$
for any $t$. To be specific, when $X$ and $Y$ are independent,
$E(\mathbbm{1}\\{Y\geq t|X\\})$ is a constant for any $t$, therefore
$\xi(X,Y)=0$. When $Y$ is a measurable function of $X$, we have
$E(\mathbbm{1}\\{Y\geq t|X\\})=\mathbbm{1}\\{Y\geq t|X\\}$ thus $\xi(X,Y)=1$.
The sample estimate in (1) is asymptotically normal under independence.
Precisely,

$\sqrt{n}\xi_{n}(X,Y)\xrightarrow[]{d}N(0,2/5)$

as $n\rightarrow\infty$. Moreover, as an empirical finding, Chatterjee’s test
is more sensitive to oscillatory patterns compared to other popular tests
including distance correlation test and Bergsma-Dassios test. These attractive
properties make Chatterjee’s test an appealing choice for large-scale
association studies.

It is also noteworthy that $\xi_{n}(X,Y)$ is generally asymmetric, i.e.,
$\xi_{n}(X,Y)\neq\xi_{n}(Y,X)$. A symmetrized measure can be easily obtained
by taking the maximum

$\xi^{sym}_{n}(X,Y)=\max\\{\xi_{n}(X,Y),\xi_{n}(Y,X)\\}.$

Unfortunately, the asymptotic distribution of $\xi^{sym}_{n}(X,Y)$ still
remains unknown, although Chatterjee conjectured that under independence,
$\xi^{sym}_{n}(X,Y)$ behaves like the maximum of two correlated normal random
variables [7]. To fill this gap, in this work we investigate the asymptotic
joint distribution of $\sqrt{n}\xi_{n}(X,Y)$ and $\sqrt{n}\xi_{n}(Y,X)$. We
show that under independence,
$[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)]^{T}$ converges to a bivariate
normal distribution with $\rho=0$, therefore the maximum converges to a skew
normal distribution with shape parameter $1$. As a byproduct, we derive the
finite sample variance and covariance of $\sqrt{n}\xi_{n}(X,Y)$ and
$\sqrt{n}\xi_{n}(Y,X)$, and construct a finite sample test to reduce the bias
of asymptotic p-value.

The remainder of the paper is structured as follows: Section 2 presents our
main results including the asymptotic joint distribution of
$\sqrt{n}\xi_{n}(X,Y)$ and $\sqrt{n}\xi_{n}(Y,X)$, as well as their finite
sample variance and covariance. Section 3 compares the asymptotic test and
finite sample test using simulated data. Section 4 discusses our method with
some future perspectives.

##  2 Main results

We first present the finite sample covariance between $\sqrt{n}\xi_{n}(X,Y)$
and $\sqrt{n}\xi_{n}(Y,X)$ in the following lemma. A detailed proof of Lemma 1
is provided in Appendix A.1.

######  Lemma 1.

If $X$ and $Y$ are independent, we have

$\mbox{Cov}\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]=-n+\frac{9}{(n+1)^{2}(n-1)^{3}}\left[2(n-1)^{2}+(n-2)(A+B)^{2}+(n-2)(n-3)C^{2}\right],$

for any $n\geq 4$, where $A$, $B$, $C$ represent

$\displaystyle A$
$\displaystyle=\frac{1}{2(n-2)}\sum_{i=1}^{n-1}\left[i(i-1)+(n-i+2)(n-i-1)\right],$
$\displaystyle B$
$\displaystyle=\frac{1}{2(n-2)}\sum_{i=1}^{n-1}\left[(i+2)(i-1)+(n-i-1)(n-i)\right],$
$\displaystyle C$
$\displaystyle=\frac{1}{3(n-2)(n-3)}\sum_{i=1}^{n-1}\left[n(n-1)(n+1)-6(n-i)^{2}-6(i+1)(i-1)\right].$

Figure 1 sketches
$\mbox{Cov}\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]$ for $4\leq
n\leq 100$. The covariance function is maximized at $n=6$ and decreases to $0$
afterwards. To verify Lemma 1, we also estimated the covariance between
$\sqrt{n}\xi_{n}(X,Y)$ and $\sqrt{n}\xi_{n}(Y,X)$ using $100,000$ Monte Carlo
samples. The analytical calculations and simulation results agree very well
(see the comparison in Figure 1). The following corollary can be obtained from
Lemma 1 (proof is given in Appendix A.2)

######  Corollary 1.

If $X$ and $Y$ are independent,
$\mbox{Cov}\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]=O(1/n)$.

Furthermore, we give the finite sample variance in Lemma 2 (derivation is
provided in Appendix A.3). The variance function is sketched in Figure 2 and
verified by $100,000$ Monte Carlo samples. As stated in Lemma 2,
$\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]$ monotonically increases from $0$
to $2/5$ for $n\geq 2$, therefore using the asymptotic variance of $2/5$ tends
to overestimate the p-value for independence testing.

######  Lemma 2.

If $X$ and $Y$ are independent, we have

$\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]=\frac{n(n-2)(4n-7)}{10(n+1)(n-1)^{2}},$

for any $n\geq 2$. Furthermore, $\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]$ is
monotonically increasing and
$\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]\rightarrow 2/5$ as
$n\rightarrow\infty$.

By Corollary 1 and Lemma 2, it is immediate that the correlation between
$\sqrt{n}\xi_{n}(X,Y)$ and $\sqrt{n}\xi_{n}(Y,X)$ converges to 0 as
$n\rightarrow\infty$. As of now, we have
$\sqrt{n}\xi_{n}(X,Y)\xrightarrow[]{d}N(0,2/5)$,
$\sqrt{n}\xi_{n}(Y,X)\xrightarrow[]{d}N(0,2/5)$ and
$\mbox{Cor}\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]\rightarrow
0$, however, these do not imply asymptotic joint normality. The following
lemma establishes the asymptotic joint normality using a coupling method by
[9], and Chatterjee’s central limit theorem [10, 11] (proof is given in
Appendix A.4)

######  Lemma 3.

If $X$ and $Y$ are independent,
$\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]$ converges in
distribution to a bivariate normal distribution.

Combining Corollary 1, Lemma 2 and Lemma 3, our main theorem follows
immediately

######  Theorem 1.

If $X$ and $Y$ are independent, $\begin{bmatrix}\sqrt{n}\xi_{n}(X,Y)\\\
\sqrt{n}\xi_{n}(Y,X)\end{bmatrix}\xrightarrow{d}N\left[\begin{pmatrix}0\\\
0\end{pmatrix},\begin{pmatrix}2/5&0\\\ 0&2/5\end{pmatrix}\right]$ as
$n\rightarrow\infty$.

It is well known that the maximum of two correlated standard normal random
variables has a skew normal distribution with mean 0, variance 1 and shape
$(1-\rho)/\sqrt{1-\rho^{2}}$, therefore we have the following asymptotic
result for the symmetric measure

$\sqrt{n}\xi^{sym}_{n}(X,Y)\rightarrow\mbox{SN}(\mu=0,\sigma^{2}=2/5,\alpha=1),$

where $\mu$, $\sigma^{2}$ and $\alpha$ represent the location, variance and
shape parameters in the skew normal distribution.

Going back to Lemma 1 and Lemma 2, we note that a finite sample test for
$\sqrt{n}\xi^{sym}_{n}(X,Y)$ may help reduce the bias of asymptotic p-value,
and this can be done by replacing the asymptotic variance and shape parameters
with the corresponding finite sample quantities, i.e.,

$\mbox{SN}\left\\{\mu=0,\sigma^{2}=\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right],\alpha=\frac{1-\rho_{n}}{\sqrt{1-\rho_{n}^{2}}}\right\\},$

where

$\rho_{n}=\frac{\mbox{Cov}\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]}{\sqrt{\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]}\sqrt{\mbox{V}\left[\sqrt{n}\xi_{n}(Y,X)\right]}}.$

For instance, when $n=10$, the finite sample method uses variance $0.296$ and
shape parameter $0.637$, compared to $0.4$ and $1$ in the asymptotic method.
In Section 3, we shall use simulations to evaluate the bias reduction under
relatively small sample sizes.

##  3 Simulation study

In this section, two simulation studies were conducted to investigate the bias
of p-values from the asymptotic and finite sample tests. The exact p-values
were approximated using $5,000$ permutations and the bias was computed as the
p-value by each test minus the exact p-value. Sample size was set to be
$\\{10,20,30,40,50\\}$.

In the first study, we examined the p-value bias under independence. In each
simulation run, we generated $X$ from $\mbox{Uniform}[-1,1]$ and $Y$ from
$N(0,1)$ independently, and then computed the p-value bias of the two tests.
Figure 3 summarizes the results over $1,000$ simulations runs. It can be seen
that the asymptotic p-value is heavily biased for smaller sample sizes, but
the use of finite sample test can significantly reduce the bias. For instance,
when $n=10$, the median bias of the two tests are $0.11$ (asymptotic) and
$0.03$ (finite sample).

In the second study, we investigated the p-value bias under various dependence
settings. Generating $X$ from $\mbox{Uniform}[-1,1]$, the following four
alternatives were considered

  * 1.

Linear: $Y=X+\epsilon$, where $\epsilon\perp X$ and $\epsilon\sim N(0,1)$.

  * 2.

Quadratic: $Y=X^{2}+\epsilon$.

  * 3.

Sinusoid: $Y=\cos(2\pi X)+2\epsilon$.

  * 4.

W-shaped:
$Y=|X+0.5|\mathbbm{1}\\{X<0\\}+|X-0.5|\mathbbm{1}\\{X>0\\}+\epsilon$.

Figure 4 shows the bias comparison under different scenarios, where it is
clear that the finite sample test again substantially reduces the bias. The
results also indicate that the asymptotic test can be conservative and
subsequently less powerful due to the positive bias. Therefore in practice,
the finite sample test is recommended especially for small sample sizes.

##  4 Discussion and conclusions

In a recent work, Chatterjee proposed an ingenious correlation measure that
has several unusual appeals. For instance, it consistently estimates a
population quantity that is 0 under independence and 1 under deterministic
relation. Moreover, it is distribution-free and asymptotic normal under
independence. Despite the success of this correlation measure, there are
several important problems remaining unexplored, one of which is about the
asymptotic distribution of the symmetrized measure
$\xi^{sym}_{n}(X,Y)=\max\\{\xi_{n}(X,Y),\xi_{n}(Y,X)\\}$. In this paper, we
showed that $\sqrt{n}\xi_{n}(X,Y)$ and $\sqrt{n}\xi_{n}(Y,X)$ are
asymptotically bivariate normal with $\rho=0$, thus
$\sqrt{n}\xi^{sym}_{n}(X,Y)$ converges to a skew normal distribution with
shape parameter 1. Motivated by the variance and covariance of
$\sqrt{n}\xi_{n}(X,Y)$ and $\sqrt{n}\xi_{n}(Y,X)$, we also suggest a finite
sample test for small sample sizes (e.g., $n<30$). Simulation studies show
that the asymptotic test tends to be heavily biased, and the use of our finite
sample test can reduce the bias.

Our results can be very useful for large-scale exploratory analyses in which
the dependence of interest are non-directional. For example, in gene co-
expression analysis, one may simply search for all the correlated gene pairs
without specifying the direction, thus a symmetric measure of dependence is
more appropriate. It is also noteworthy that, our finite sample test is
computationally efficient because the variance and covariance terms only
depend on the sample size $n$ (see Lemma 1 and Lemma 3).

More recently, several studies have pointed out that Chatterjee’s independence
test is unfortunately sub-optimal [12, 13]. As shown in Figure 5 of [7],
Chatterjee’s test has inferior performance for smoother alternatives, and its
statistical power quickly deteriorates as the noise level increases. To boost
the power of Chatterjee’s test, Lin & Han (2021) proposed the following
extension of Chatterjee’s original proposal by incorporating $M$ right nearest
neighbors

$\xi_{n,M}(X,Y)=-2+\frac{6\sum_{i=1}^{n}\sum_{m=1}^{M}\min[R(Y_{X(i)}),R(Y_{X(i+m)})]}{(n+1)[nM+M(M+1)/4]},$

where $R(Y_{X(i+m)})=R(Y_{X(i)})$ for $i+m>n$. Under the assumption that
$M=o(n^{1/4})$, Lin & Han showed
$\sqrt{nM}\xi_{n,M}(X,Y)\xrightarrow[]{d}N(0,2/5)$ as $n\rightarrow\infty$.
Empirical data analyses suggest that, under a reasonable choice of $M$,
$\xi_{n,M}(X,Y)$ achieves better statistical power than $\xi_{n}(X,Y)$ as the
latter does not use any information from neighboring points.

Similar to what we did in this work, it would be of interest to investigate
the joint distribution of $\sqrt{nM}\xi_{n,M}(X,Y)$ and
$\sqrt{nM}\xi_{n,M}(Y,X)$ and construct asymptotic and finite sample tests for
the symmetric measure. However, the derivations for $M\geq 2$ may take
significant effort and we leave this for future research.

## Competing Interests

The author has declared that no competing interests exist.

## References

  * [1] Pfister, N, Buhlmann, P., Scholkopf, B. & Peters, J. (2018). Kernel-based tests for joint independence. Journal of the Royal Statistical Society - Series B, 80(1): 5-31
  * [2] Székely, G.J., Rizzo, M.L. & Bakirov, N.K. (2007). Measuring and testing dependence by correlation of distances. Annals of Statistics, 35(6): 2769-2794
  * [3] Bergsma, W. & Dassios, A. (2014). A consistent test of independence based on a sign covariance related to Kendall’s tau. Bernoulli, 20(2): 1006-1028
  * [4] Schweizer, N. & Wolff, E.F. (1981). On nonparametric measures of dependence for random variables. Annals of Statistics, 9(4): 879-885
  * [5] Friedman, J.H. & Rafsky, L.C. (1983). Graph-theoretic measures of multivariate association and prediction. Annals of Statistics, 11(2): 377-391
  * [6] Reshef et al. (2011). Detecting novel associations in large datasets. Science, 334(6062): 1518-1524
  * [7] Chatterjee, S. (2021). A new coefficient of correlation. Journal of the American Statistical Association, 116(536): 2009-2022
  * [8] Dette, H., Siburg, K.F. & Stoimenov, P.A. (2013). A copula-based non-parametric measure of regression dependence. Scandinavian Journal of Statistics, 40(1): 21-41
  * [9] Angus, J.E.. (1995). A coupling proof of the asymptotic normality of the permutation oscillation. Probability in the Engineering and Informational Science, 9:615-621
  * [10] Chatterjee, S. (2008). A new method of normal approximation. Annals of Probability, 36(4):1584-1610.
  * [11] Auddy, A., Deb, N. & Nandy, S. (2021). Exact detection thresholds for Chatterjee’s correlation. Available at arXiv:2104.15140.
  * [12] Shi, H., Drton, M. & Han, F. (2021). On the power of Chatterjee’s rank correlation. Biometrika. (in press)
  * [13] Lin, Z. & Han, F. (2021). On boosting the power of Chatterjee’s rank correlation. Available at arXiv:2108.06828v1

## Figures

Figure 1: The covariance between $\sqrt{n}\xi_{n}(X,Y)$ and
$\sqrt{n}\xi_{n}(Y,X)$ based on theoretical calculation (Lemma 1) and 100,000
Monte Carlo samples.

Figure 2: The variance of $\sqrt{n}\xi_{n}(X,Y)$ based on theoretical
calculation (Lemma 2) and 100,000 Monte Carlo samples.

Figure 3: Bias comparison of the asymptotic and finite sample p-values under
independence. The bias is computed as the p-value by each test minus the exact
p-value based on $5,000$ permutations.

Figure 4: Bias comparison of the asymptotic and finite sample p-values under
four alternatives. The bias is computed as the p-value by each test minus the
exact p-value based on $5,000$ permutations.

## Appendix

### A.1. Proof of Lemma 1

We first derive
$E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||R(Y_{X(i+1)})-R(Y_{X(i)})|\right]$ using
the law of total expectation. The space of
$\left[R(Y_{X(i+1)}),R(Y_{X(i)})\right]$ can be partitioned into the following
parts

$\displaystyle Z_{1}$
$\displaystyle=\\{R(Y_{X(i)})=j,R(Y_{X(i)})=j+1\\}\cup\\{R(Y_{X(i)})=j+1,R(Y_{X(i+1)})=j\\},$
$\displaystyle Z_{2}$
$\displaystyle=\\{R(Y_{X(i)})=j,R(Y_{X(i+1)})\neq(j,j+1)\\},$ $\displaystyle
Z_{3}$ $\displaystyle=\\{R(Y_{X(i+1)})=j,R(Y_{X(i)})\neq(j,j+1)\\},$
$\displaystyle Z_{4}$
$\displaystyle=\\{R(Y_{X(i)})=j+1,R(Y_{X(i+1)})\neq(j,j+1)\\},$ $\displaystyle
Z_{5}$ $\displaystyle=\\{R(Y_{X(i+1)})=j+1,R(Y_{X(i)})\neq(j,j+1)\\},$
$\displaystyle Z_{6}$
$\displaystyle=\\{R(Y_{X(i)})\neq(j,j+1),R(Y_{X(i+1)})\neq(j,j+1)\\},$

It is straightforward that $|R(X_{Y(j+1)})-R(X_{Y(j)})|$ and
$|R(Y_{X(i+1)})-R(Y_{X(i)})|$ are independent given each $Z_{m},m=1,...,6$.
The probabilities of $Z_{m}$ are

$\displaystyle P(Z_{1})$ $\displaystyle=\frac{2}{n(n-1)},$ $\displaystyle
P(Z_{2})$ $\displaystyle=P(Z_{3})=P(Z_{4})=P(Z_{5})=\frac{n-2}{n(n-1)},$
$\displaystyle P(Z_{6})$ $\displaystyle=\frac{(n-2)(n-3)}{n(n-1)},$

and the following expectations can be derived using elementary probability

$\displaystyle E\left[[|R(X_{Y(j+1)})-R(X_{Y(j)})||Z_{1}\right]$
$\displaystyle=E\left|R(Y_{X(i+1)})-R(Y_{X(i)})||Z1\right]=1,$ $\displaystyle
E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||Z_{2}\right]$
$\displaystyle=\frac{(i-1)i+(n-i+2)(n-i-1)}{2(n-2)},$ $\displaystyle
E\left[|R(Y_{X(i+1)})-R(Y_{X(i)})||Z_{2}\right]$
$\displaystyle=\frac{(j-1)j+(n-j+2)(n-j-1)}{2(n-2)},$ $\displaystyle
E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||Z_{3}\right]$
$\displaystyle=\frac{(i+2)(i-1)+(n-i-1)(n-i)}{2(n-2)},$ $\displaystyle
E\left[|R(Y_{X(i+1)})-R(Y_{X(i)})||Z_{3}\right]$
$\displaystyle=\frac{(j-1)j+(n-j+2)(n-j-1)}{2(n-2)},$ $\displaystyle
E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||Z_{4}\right]$
$\displaystyle=\frac{(i-1)i+(n-i+2)(n-i-1)}{2(n-2)},$ $\displaystyle
E\left[|R(Y_{X(i+1)})-R(Y_{X(i)})||Z_{4}\right]$
$\displaystyle=\frac{(j+2)(j-1)+(n-j-1)(n-j)}{2(n-2)},$ $\displaystyle
E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||Z_{5}\right]$
$\displaystyle=\frac{(i+2)(i-1)+(n-i-1)(n-i)}{2(n-2)},$ $\displaystyle
E\left[|R(Y_{X(i+1)})-R(Y_{X(i)})||Z_{5}\right]$
$\displaystyle=\frac{(j+2)(j-1)+(n-j-1)(n-j)}{2(n-2)},$ $\displaystyle
E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||Z_{6}\right]$
$\displaystyle=\frac{n(n-1)(n+1)-6(n-i)^{2}-6(i+1)(i-1)}{3(n-2)(n-3)},$
$\displaystyle E\left[|R(Y_{X(i+1)})-R(Y_{X(i)})||Z_{6}\right]$
$\displaystyle=\frac{n(n-1)(n+1)-6(n-j)^{2}-6(j+1)(j-1)}{3(n-2)(n-3)}$

For the ease of notation, let

$\displaystyle A_{i}$ $\displaystyle=\frac{(i-1)i+(n-i+2)(n-i-1)}{2(n-2)},$
$\displaystyle B_{i}$ $\displaystyle=\frac{(i+2)(i-1)+(n-i-1)(n-i)}{2(n-2)},$
$\displaystyle C_{i}$
$\displaystyle=\frac{n(n-1)(n+1)-6(n-i)^{2}-6(i+1)(i-1)}{3(n-2)(n-3)},$

then by the law of total expectation and conditional independence between
$|R(X_{Y(j+1)})-R(X_{Y(j)})|$ and $|R(Y_{X(i+1)})-R(Y_{X(i)})|$, we have

$\displaystyle
E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||R(Y_{X(i+1)})-R(Y_{X(i)})|\right]$
$\displaystyle=$
$\displaystyle\sum_{m=1}^{6}E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})||Z_{m}\right]E\left[|R(Y_{X(i+1)})-R(Y_{X(i)})||Z_{m}\right]P(Z_{m})$
$\displaystyle=$
$\displaystyle\frac{2}{n(n-1)}+\frac{n-2}{n(n-1)}(A_{i}A_{j}+B_{i}B_{j}+A_{i}B_{j}+A_{j}B_{i})+\frac{(n-2)(n-3)}{n(n-1)}C_{i}C_{j}.$

Using the following fact

$E\left[|R(X_{Y(j+1)})-R(X_{Y(j)})|\right]E\left[|R(Y_{X(i+1)})-R(Y_{X(i)})|\right]=\frac{(n+1)^{2}}{9},$

the covariance can be obtained immediately

$\displaystyle\mbox{Cov}\left[|R(X_{Y(j+1)})-R(X_{Y(j)})|,|R(Y_{X(i+1)})-R(Y_{X(i)})|\right]$
$\displaystyle=$
$\displaystyle\frac{2}{n(n-1)}+\frac{n-2}{n(n-1)}(A_{i}+B_{i})(A_{j}+B_{j})+\frac{(n-2)(n-3)}{n(n-1)}C_{i}C_{j}-\frac{(n+1)^{2}}{9}.$

Taking the summation over $i$ and $j$, Lemma 1 is proved.

### A.2. Proof of Corollary 1

Using $\sum_{i=1}^{n-1}i^{2}=\sum_{i=1}^{n-1}(n-i)^{2}=n(n-1)(2n-1)/6$, we
have

$\displaystyle A$
$\displaystyle=\frac{1}{2(n-2)}\left[\frac{n(n-1)(2n-1)}{3}+O(n^{2})\right]$
$\displaystyle=\frac{n^{2}}{3}+O(n)$

Similarly, $B=n^{2}/3+O(n)$, therefore $(n-2)(A+B)^{2}=4n^{5}/9+O(n^{4})$.
Furthermore,

$\displaystyle(n-2)(n-3)C^{2}$
$\displaystyle=\frac{1}{9(n-2)(n-3)}\left[n(n-1)^{2}(n+1)-2n(n-1)(2n-1)+O(n)\right]^{2}$
$\displaystyle=\frac{n^{2}(n-1)^{2}}{9(n-2)(n-3)}\left[n^{2}-4n+1+O(1/n)\right]^{2}$
$\displaystyle=\frac{n^{4}(n-1)^{2}(n-4)^{2}}{9(n-2)(n-3)}+O(n^{4})$
$\displaystyle=\frac{n^{6}}{9}-\frac{5n^{5}}{9}+O(n^{4}).$

Summarizing the results above, we have

$\displaystyle\mbox{Cov}\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]$
$\displaystyle=-n+\frac{n^{5}}{(n+1)^{2}(n-1)^{2}}+O(1/n)$
$\displaystyle=\frac{2n^{3}-n}{(n+1)^{2}(n-1)^{2}}+O(1/n)$
$\displaystyle=O(1/n)$

### A.3. Proof of Lemma 2

If $X$ and $Y$ are independent, $\\{R(Y_{X(1)}),...,R(Y_{X(n)})\\}$ is a
random permutation of $\\{1,...,n\\}$. For the ease of notation, we let
$R_{i}=R(Y_{X(i)})$. The following facts from [13] (Lemma 6.1, page 13) are
needed for our derivation of $\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]$

$\displaystyle\mbox{V}\left[R_{1}\right]$
$\displaystyle=\frac{(n-1)(n+1)}{12}$
$\displaystyle\mbox{Cov}\left[R_{1},R_{2}\right]$
$\displaystyle=-\frac{n+1}{12}$
$\displaystyle\mbox{Cov}\left[R_{1},\min\\{R_{2},R_{3}\\}\right]$
$\displaystyle=-\frac{n+1}{12}$
$\displaystyle\mbox{Cov}\left[R_{1},\min\\{R_{1},R_{2}\\}\right]$
$\displaystyle=\frac{(n+1)(n-2)}{24}$
$\displaystyle\mbox{Cov}\left[\min\\{R_{1},R_{2}\\},\min\\{R_{3},R_{4}\\}\right]$
$\displaystyle=-\frac{4(n+1)}{45}$
$\displaystyle\mbox{Cov}\left[\min\\{R_{1},R_{2}\\},\min\\{R_{1},R_{3}\\}\right]$
$\displaystyle=\frac{(n+1)(4n-17)}{180}$
$\displaystyle\mbox{V}\left[\min\\{R_{1},R_{2}\\}\right]$
$\displaystyle=\frac{(n-2)(n+1)}{18}.$

We first decompose the total variance into three parts

$\displaystyle\mbox{V}\left[\sum_{i=1}^{n-1}|R_{i+1}-R_{i}|\right]=$
$\displaystyle(n-1)\mbox{V}\left[|R_{2}-R_{1}|\right]+2(n-2)\mbox{Cov}\left[|R_{2}-R_{1}|,|R_{3}-R_{2}|\right]$
$\displaystyle+(n-2)(n-3)\mbox{Cov}\left[|R_{4}-R_{3}|,|R_{2}-R_{1}|\right]$

where $\mbox{V}\left[|R_{2}-R_{1}|\right]$ in the first part can be derived as
follows

$\displaystyle\mbox{V}\left[|R_{2}-R_{1}|\right]$
$\displaystyle=\mbox{V}\left[R_{1}+R_{2}-2\min\\{R_{1},R_{2}\\}\right]$
$\displaystyle=2\mbox{V}\left[R_{1}\right]+2\mbox{Cov}\left[R_{1},R_{2}\right]+4\mbox{V}\left[\min\\{R_{1},R_{2}\\}\right]-8\mbox{Cov}\left[R_{1},\min\\{R_{1},R_{2}\\}\right]$
$\displaystyle=\frac{(n+1)(n-1)}{6}-\frac{n+1}{6}+\frac{2(n-2)(n+1)}{9}-\frac{(n-2)(n+1)}{3}$
$\displaystyle=\frac{(n+1)(n-2)}{18},$

and $\mbox{Cov}\left[|R_{2}-R_{1}|,|R_{3}-R_{2}|\right]$ in the second part is

$\displaystyle\mbox{Cov}\left[|R_{2}-R_{1}|,|R_{3}-R_{2}|\right]=\mbox{Cov}\left[R_{1}+R_{2}-2\min\\{R_{1},R_{2}\\},R_{2}+R_{3}-2\min\\{R_{2},R_{3}\\}\right]$
$\displaystyle=$ $\displaystyle
3\mbox{Cov}\left[R_{1},R_{2}\right]+\mbox{V}\left[R_{1}\right]-4\mbox{Cov}\left[R_{1},\min\\{R_{2},R_{3}\\}\right]-4\mbox{Cov}\left[R_{1},\min\\{R_{1},R_{2}\\}\right]+4\mbox{Cov}\left[\min\\{R_{1},R_{2}\\},\min\\{R_{1},R_{3}\\}\right]$
$\displaystyle=$
$\displaystyle-\frac{n+1}{4}+\frac{(n+1)(n-1)}{12}+\frac{n+1}{3}-\frac{(n-2)(n+1)}{6}+\frac{(n+1)(4n-17)}{45}$
$\displaystyle=$ $\displaystyle\frac{(n+1)(n-8)}{180},$

and $\mbox{Cov}\left[|R_{4}-R_{3}|,|R_{2}-R_{1}|\right]$ in the third part is

$\displaystyle\mbox{Cov}\left[|R_{4}-R_{3}|,|R_{2}-R_{1}|\right]=\mbox{Cov}\left[R_{1}+R_{2}-2\min\\{R_{1},R_{2}\\},R_{3}+R_{4}-2\min\\{R_{3},R_{4}\\}\right]$
$\displaystyle=$ $\displaystyle
4\mbox{Cov}\left[R_{1},R_{2}\right]-8\mbox{Cov}\left[R_{1},\min\\{R_{2},R_{3}\\}\right]+4\mbox{Cov}\left[\min\\{R_{1},R_{2}\\},\min\\{R_{3},R_{4}\\}\right]$
$\displaystyle=$
$\displaystyle-\frac{n+1}{3}+\frac{2(n+1)}{3}-\frac{16(n+1)}{45}$
$\displaystyle=$ $\displaystyle-\frac{n+1}{45}.$

Summarizing the results above, we have

$\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]=\frac{n(n-2)(4n-7)}{10(n+1)(n-1)^{2}},$

for any $n\geq 2$, and $\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]\rightarrow
2/5$ as $n\rightarrow\infty$. It is also noteworthy that

$\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]=\frac{2}{5}(1-\frac{1}{n+1})(1-\frac{1}{n-1})(1-\frac{3/4}{n-1}),$

thus $\mbox{V}\left[\sqrt{n}\xi_{n}(X,Y)\right]$ is monotonically increasing.

### A.4. Proof of Lemma 3

For the ease of notation, let

$\displaystyle Z_{n}^{X}$
$\displaystyle=\frac{\sum_{i=1}^{n-1}|R(X_{Y(i+1)})-R(X_{Y(i)})|-n(n-1)/3}{\sqrt{n}(n-1)},$
$\displaystyle Z_{n}^{Y}$
$\displaystyle=\frac{\sum_{i=1}^{n-1}|R(Y_{X(i+1)})-R(Y_{X(i)})|-n(n-1)/3}{\sqrt{n}(n-1)}.$

Let $F_{X}(x)$ and $F_{Y}(y)$ be the $c.d.f.$’s of $X$ and $Y$,
$\hat{F}_{X}(x)$ and $\hat{F}_{Y}(y)$ be the empirical $c.d.f.$’s, i.e.,

$\displaystyle\hat{F}_{X}(x)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{X_{i}\leq x\\},$
$\displaystyle\hat{F}_{Y}(y)$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{Y_{i}\leq y\\},$

therefore $\hat{F}_{X}(X_{Y(i)})=R(X_{Y(i)})/n$ and
$\hat{F}_{Y}(Y_{X(i)})=R(Y_{X(i)})/n$. We define $U_{i}:=F_{X}(X_{Y(i)})$ and
$V_{i}:=F_{Y}(Y_{X(i)})$. Under independence, $\\{U_{1},...,U_{n}\\}$ are
$i.i.d.$ samples from $\mbox{Uniform}(0,1)$, and same for
$\\{V_{1},...,V_{n}\\}$. But it is noteworthy that $\\{U_{1},...,U_{n}\\}$ and
$\\{V_{1},...,V_{n}\\}$ are not independent.

Using Equations (5)-(8) in Angus (1995), we have

$\displaystyle Z_{n}^{X}=$
$\displaystyle\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}\left[|U_{i+1}-U_{i}|+2U_{i}(1-U_{i})-\frac{2}{3}\right]+R_{n}^{X},$
$\displaystyle Z_{n}^{Y}=$
$\displaystyle\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}\left[|V_{i+1}-V_{i}|+2V_{i}(1-V_{i})-\frac{2}{3}\right]+R_{n}^{Y},$

where $R_{n}^{X}\xrightarrow{P}0$ and $R_{n}^{Y}\xrightarrow{P}0$. In
addition, it can be seen that

$\sqrt{n}\xi_{n}(X,Y)=Z_{n}^{X}-\frac{\sum_{i=1}^{n-1}|R(Y_{X(i+1)})-R(Y_{X(i)})|}{\sqrt{n}(n-1)(n+1)},$

where the second term is $O(1/\sqrt{n})$. For any two constants $a$ and $b$,
we have

$\displaystyle a\sqrt{n}\xi_{n}(X,Y)+b\sqrt{n}\xi_{n}(Y,X)$
$\displaystyle=~{}$ $\displaystyle aZ_{n}^{X}+bZ_{n}^{Y}+O(1/\sqrt{n})$
$\displaystyle=~{}$
$\displaystyle\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}\left[a|U_{i+1}-U_{i}|+b|V_{i+1}-V_{i}|+2aU_{i}(1-U_{i})+2bV_{i}(1-V_{i})-\frac{2(a+b)}{3}\right]$
$\displaystyle~{}+aR_{n}^{X}+bR_{n}^{Y}+O(1/\sqrt{n}).$

Recall that $U_{i}=F_{X}(X_{Y(i)})$ and $V_{i}=F_{Y}(Y_{X(i)})$, we will show
that

$\displaystyle\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[$ $\displaystyle
a|F_{X}(X_{Y(i+1)})-F_{X}(X_{Y(i)})|+2aF_{X}(X_{Y(i)})(1-F_{X}(X_{Y(i)}))$ (2)
$\displaystyle+b|F_{Y}(Y_{X(i+1)})-F_{Y}(Y_{X(i)})|+2bF_{Y}(Y_{X(i)})(1-F_{Y}(Y_{X(i)}))$
$\displaystyle-2(a+b)/3]$

converges to a normal distribution. It is equivalent to show

$\displaystyle W_{n}=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}[$ $\displaystyle
a|F_{X}(X_{i})-F_{X}(X_{N_{Y}(i)})|+2aF_{X}(X_{i})(1-F_{X}(X_{i}))$ (3)
$\displaystyle+b|F_{Y}(Y_{i})-F_{Y}(Y_{N_{X}(i)})|+2bF_{Y}(Y_{i})(1-F_{Y}(Y_{i}))$
$\displaystyle-2(a+b)/3],$

converges to a normal distribution, where $\\{X_{N_{X}(i)},Y_{N_{X}(i)}\\}$
and $\\{X_{N_{Y}(i)},Y_{N_{Y}(i)}\\}$ represent the right nearest neighbor of
$\\{X_{i},Y_{i}\\}$ in terms of $X$ and $Y$, respectively. If $N_{X}(i)$ does
not exist, one can define $Y_{N_{X}(i)}=Y_{(1)}$. Note that (3) is a summation
over $i=1,...,n$, which has one more term than (2), but the two differ by only
$O(1/\sqrt{n})$.

It is easy to see that (3) is based on $n$ dependent variables, therefore the
central limit theorem for $i.i.d.$ case does not apply. Here we use
Chatterjee’s central limit theorem based on interaction graphs [10, 11]. We
define a graphical rule $\mathcal{G}$ based on $W_{n}$ which we will show to
be an interaction rule (defined in Section 2.3 of [10], page 5). We borrow the
notations from [11]. Let

$\mathcal{M}:=\\{(X_{1},Y_{1}),...,(X_{n},Y_{n})\\}~{}\mbox{and}~{}\mathcal{M}^{\prime}:=\\{(X^{\prime}_{1},Y^{\prime}_{1}),...,(X^{\prime}_{n},Y^{\prime}_{n})\\}$

be two $i.i.d.$ samples of size $n$, and

$\displaystyle\mathcal{M}^{i}$
$\displaystyle:=\\{(X_{1},Y_{1}),...,(X^{\prime}_{i},Y^{\prime}_{i}),...,(X_{n},Y_{n})\\}$
$\displaystyle\mathcal{M}^{j}$
$\displaystyle:=\\{(X_{1},Y_{1}),...,(X^{\prime}_{j},Y^{\prime}_{j}),...,(X_{n},Y_{n})\\}$
$\displaystyle\mathcal{M}^{ij}$
$\displaystyle:=\\{(X_{1},Y_{1}),...,(X^{\prime}_{i},Y^{\prime}_{i}),...,(X^{\prime}_{j},Y^{\prime}_{j}),...,(X_{n},Y_{n})\\}$

Let $[n]:=\\{1,2,...,n\\}$, we define a graphical rule
$\mathcal{G}(\mathcal{M})$ on $[n]$ motivated by [11] (Equation 4.17, page 21)

$D^{X}_{\mathcal{M}}(i,j)=\begin{cases}\infty,~{}~{}\mbox{if}~{}X_{i}>X_{j}\\\
\\#\\{l:X_{i}<X_{l}<X_{j}\\},~{}~{}\mbox{if}~{}X_{i}<X_{j},\end{cases}$
$D^{Y}_{\mathcal{M}}(i,j)=\begin{cases}\infty,~{}~{}\mbox{if}~{}Y_{i}>Y_{j}\\\
\\#\\{l:Y_{i}<Y_{l}<Y_{j}\\},~{}~{}\mbox{if}~{}Y_{i}<Y_{j}.\end{cases}$

For any two indices $\\{i,j\\}$, there is an edge between $i$ and $j$ if there
exists an $l\in[n]$, such that

$\displaystyle D^{X}_{\mathcal{M}}(l,i)\leq 2~{}$
$\displaystyle\mbox{and}~{}D^{X}_{\mathcal{M}}(l,j)\leq 2$ or $\displaystyle
D^{Y}_{\mathcal{M}}(l,i)\leq 2~{}$
$\displaystyle\mbox{and}~{}D^{Y}_{\mathcal{M}}(l,j)\leq 2.$

It is straightforward that this rule is invariant under relabeling of indices,
therefore it is a symmetric rule (see the definition in [10], page 5). The
statistic $W_{n}(\mathcal{M})$ can be separated into the $X$ part and the $Y$
part, i.e.,

$W_{n}(\mathcal{M})=W_{n,X}(\mathcal{M})+W_{n,Y}(\mathcal{M}),$
$W_{n,X}(\mathcal{M})=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}[a|F_{X}(X_{i})-F_{X}(X_{N_{Y}(i)})|+2aF_{X}(X_{i})(1-F_{X}(X_{i}))-(a+b)/3],$
$W_{n,Y}(\mathcal{M})=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}[b|F_{Y}(Y_{i})-F_{Y}(Y_{N_{X}(i)})|+2bF_{Y}(Y_{i})(1-F_{Y}(Y_{(i)}))-(a+b)/3].$

We will show that $\mathcal{G}(\mathcal{M})$ is an interaction rule. For any
pair of indices $\\{i,j\\}$, if there is no edge between them, there does not
exist an $l\in[n]$, such that $D^{X}_{\mathcal{M}}(l,i)\leq 2$ and
$D^{X}_{\mathcal{M}}(l,j)\leq 2$. Using the proof of Lemma 4 in [11] (page 43,
section A.4), we have

$W_{n,X}(\mathcal{M})-W_{n,X}(\mathcal{M}^{i})-W_{n,X}(\mathcal{M}^{j})+W_{n,X}(\mathcal{M}^{ij})=0.$

Similarly for the $Y$ part, we have

$W_{n,Y}(\mathcal{M})-W_{n,Y}(\mathcal{M}^{i})-W_{n,Y}(\mathcal{M}^{j})+W_{n,Y}(\mathcal{M}^{ij})=0.$

Therefore

$W_{n}(\mathcal{M})-W_{n}(\mathcal{M}^{i})-W_{n}(\mathcal{M}^{j})+W_{n}(\mathcal{M}^{ij})=0,$

i.e., $\mathcal{G}$ is a symmetric graphical interaction rule. Define

$\Delta_{j}:=W_{n}(\mathcal{M})-W_{n}(\mathcal{M}^{j}),$

and

$M:=\max_{j}|\Delta_{j}|.$

Because all the $c.d.f.$’s are between 0 and 1, there exists a constant
$C_{1}>0$, such that

$M<\frac{C_{1}}{\sqrt{n}},$ $|\Delta_{j}|<\frac{C_{1}}{\sqrt{n}}.$

We now construct an extended graph $\mathcal{G}^{\prime}$ on $[n+4]$. There
exists an edge between $i$ and $j$ if there exists an $l\in[n]$, such that

$\displaystyle D^{X}_{\mathcal{M}}(l,i)\leq 6~{}$
$\displaystyle\mbox{and}~{}D^{X}_{\mathcal{M}}(l,j)\leq 6$ or $\displaystyle
D^{Y}_{\mathcal{M}}(l,i)\leq 6~{}$
$\displaystyle\mbox{and}~{}D^{Y}_{\mathcal{M}}(l,j)\leq 6.$

Clearly the extended rule $\mathcal{G}^{\prime}$ is also symmetric, and all
the edges of $\mathcal{G}$ are also in $\mathcal{G}^{\prime}$. The degree of
any vertex in $\mathcal{G}^{\prime}$ is bounded by a constant $C_{2}>0$,
therefore

$\delta:=1+\mbox{degree~{}of~{}the~{}vertex~{}1~{}in~{}}\mathcal{G}^{\prime}\leq
C_{2}+1.$

Using Theorem 2.5 of [10], there exists a universal constant $C>0$, such that

$\mathcal{D}(W_{n})\leq\frac{C}{\sqrt{n}\sigma^{2}}+\frac{C}{2\sqrt{n}\sigma^{3}},$

where $\mathcal{D}(W_{n})$ is the Wasserstein distance between
$(W_{n}-E(W_{n}))/\sigma$ and $N(0,1)$.

We now derive the variance term $\sigma^{2}$. Note that

$\displaystyle\mbox{V}(W_{n})=$
$\displaystyle\mbox{V}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[a|U_{i+1}-U_{i}|+b|V_{i+1}-V_{i}|+2aU_{i}(1-U_{i})+2bV_{i}(1-V_{i})])\right\\}$
$\displaystyle=$
$\displaystyle\mbox{V}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[a|U_{i+1}-U_{i}|+2aU_{i}(1-U_{i})]\right\\}+\mbox{V}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[b|V_{i+1}-V_{i}|+2bV_{i}(1-V_{i})]\right\\}$
$\displaystyle+\mbox{Cov}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[a|U_{i+1}-U_{i}|+2aU_{i}(1-U_{i})],\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[b|V_{i+1}-V_{i}|+2bV_{i}(1-V_{i})]\right\\}.$

From Equation (14) in [9], we have

$\displaystyle\mbox{V}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[a|U_{i+1}-U_{i}|+2aU_{i}(1-U_{i})]\right\\}$
$\displaystyle=2a^{2}/45+O(1/n)$
$\displaystyle\mbox{V}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[b|V_{i+1}-V_{i}|+2bV_{i}(1-V_{i})]\right\\}$
$\displaystyle=2b^{2}/45+O(1/n)$

For the covariance term, using the same technique in the proof of Lemma 1, we
have

$\displaystyle\mbox{Cov}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[a|U_{i+1}-U_{i}|],\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[b|V_{i+1}-V_{i}|]\right\\}$
$\displaystyle=O(1/n)$
$\displaystyle\mbox{Cov}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[2aU_{i}(1-U_{i})],\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[2bV_{i}(1-V_{i})]\right\\}$
$\displaystyle=0$
$\displaystyle\mbox{Cov}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[a|U_{i+1}-U_{i}|],\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[2bV_{i}(1-V_{i})]\right\\}$
$\displaystyle=0$
$\displaystyle\mbox{Cov}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[2aU_{i}(1-U_{i})],\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[b|V_{i+1}-V_{i}|]\right\\}$
$\displaystyle=0.$

Summarizing the results above, we have

$\mbox{Cov}\left\\{\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[a|U_{i+1}-U_{i}|+2aU_{i}(1-U_{i})],\frac{1}{\sqrt{n}}\sum_{i=1}^{n-1}[b|V_{i+1}-V_{i}|+2bV_{i}(1-V_{i})]\right\\}=O(1/n),$

therefore

$\sigma^{2}:=\mbox{Var}(W_{n})=2(a^{2}+b^{2})/45+O(1/n).$

By Slutsky’s theorem, $a\sqrt{n}\xi_{n}(X,Y)+b\sqrt{n}\xi_{n}(Y,X)$ converges
in distribution to a normal distribution. Finally, by Craḿer-Wold device,
$\left[\sqrt{n}\xi_{n}(X,Y),\sqrt{n}\xi_{n}(Y,X)\right]^{T}$ is asymptotically
bivariate normal.


# System III: Learning with Domain Knowledge for Safety Constraints

Fazl Barez1 Hosien Hasanbieg2 Alesandro Abbate2
1Edinburgh Centre for Robotics 2University of Oxford
<EMAIL_ADDRESS>
{hosein.hasanbeig<EMAIL_ADDRESS>
###### Abstract

Reinforcement learning agents naturally learn from extensive exploration.
Exploration is costly and can be unsafe in safety-critical domains. This paper
proposes a novel framework for incorporating domain knowledge to help guide
safe exploration and boost sample efficiency. Previous approaches impose
constraints, such as regularisation parameters in neural networks, that rely
on large sample sets and often are not suitable for safety-critical domains
where agents should almost always avoid unsafe actions. In our approach,
called System III, which is inspired by psychologists’ notions of the brain’s
System I and System II, we represent domain expert knowledge of safety in form
of first-order logic. We evaluate the satisfaction of these constraints via
p-norms in state vector space. In our formulation, constraints are analogous
to hazards, objects, and regions of state that have to be avoided during
exploration. We evaluated the effectiveness of the proposed method on OpenAI’s
Gym and Safety-Gym environments. In all tasks, including classic Control and
Safety Games, we show that our approach results in safer exploration and
sample efficiency.

##  1 Introduction

While existing Reinforcement Learning (RL) methods provide promising
guarantees given sufficient exploration guarantees, in safety-critical
applications most of the exploration methods are impractical due to the system
vulnerability. Consider the example of a self-driving car where the controller
agent should respect the speed limit, should not cross the stop sign, and
should not crash into objects and other agents in the environment [2]. Safety
in RL is not limited to self-driving cars, it can be used to make algorithms
systematically safe and aligned with human intent [17]. In safety-critical
domains such as autonomous driving, warehouse logistics or assistance in
health care, experts require deep RL controllers to operate within known
bounds and limits. Let us refer to these safety bounds and limits as
constraints. Recent advances in the development of deep RL provide means to
allow prior domain knowledge to be encoded in the training processes of neural
networks. However, previous efforts on encoding the constraints requires
direct modification of the optimization problem. Specifically, the constraints
are encoded in the loss function, which may require heavy domain-specific
engineering [8]. Consequently, these approaches are not suitable in safety-
critical domains where the constraints must be satisfied during learning and
thus sample efficiency is an important factor. Although combining expert
constraints with neural networks tends to help learning, generating expert
constraints remains challenging, understudied and domain-dependent. Further
related work is discussed in Appendix 2.

In this work we take inspiration from [7, 20, 27] and express our constrains
in first-order logic, which allows for efficient encoding of expert domain
knowledge. Deep reinforcement learning relies on extensive exploration to
generate data, which is highly undesirable when dealing with safety-critical
domains. On the other hand, exploration is needed in order to learn and
generalize better.

In this paper, we address both issues. Firstly, we provide a novel way of
incorporating constraints in the training processes of deep reinforcement
learning. We do not manipulate the current deep learning formulations, i.e. we
do not add any extra regularization parameter in the loss function, nor do we
rely on any domain-specific engineering. Our approach evaluates the likelihood
of constraints being satisfied at each point in time given a state prediction,
and this affects the agent’s reward function. Namely, actions that highly
satisfy the constraints are encouraged, and actions that do not fully satisfy
the constraints are discouraged. Secondly, we use model-based reinforcement
learning techniques, which are data-efficient comparing to model-free
counterparts. In general, the proposed approach can be seen as analogous to
combining system I and system II of the brain, as discussed in Kahneman’s
Thinking Fast and Slow [18]. Whilst system I is fast, automatic and intuitive,
system II is slower, analytical, and has reasoning capabilities. Hence, we
call this approach "System III" as we represent logical constraints and
combine them with the high-performing fast deep learning algorithms.

To show the effectiveness of System III, we conduct experiments on classic
control tasks such as the Cart-Pole setup from OpenAI’s Gym [3], which is a
common task in many reinforcement learning algorithms. We show that even a
simple constraint on the Cart-Pole system leads to safer exploration and
faster convergence. We further conduct experiments on the OpenAI Safety-Gym
environments [1]. We show the approach’s superiority in safe exploration for a
wide arrangement of constraints, hazards and environment configuration in a
dynamic setting where the constraints differ across experiments. Further
details are discussed in Section 8. The contribution of this paper is a novel
framework for integrating domain knowledge in the training process of deep RL.
Our framework is applicable to any off-the-shelf reinforcement learning
algorithm and can be used on top of them to encode domain knowledge and boost
sample efficiency significantly while satisfying the constraints.

##  2 Related work

In this section, we compare supervised, unsupervised and RL related works that
use human knowledge in the form of constraints. The integration of constraints
as an additional regularizer in the training process of neural networks has
achieved considerable attention in recent years, with most work still imposing
constraints on the network’s output [27, 7]. The main contribution of
"Semantics loss" [27] is the addition of a semantic loss function to the
standard neural network loss (e.g. another regularizer), and the design is
such that it is equivalent to evaluating some Boolean constraint formula using
Weighted Model Counting (WMC) which counts the weights of the solutions to a
propositional logic formula [6]. Similar to [27], [7] defines a non-negative
loss function using fuzzy logic to incorporate logical constraints. This loss
measures how far the output of the network is from the nearest satisfying
solution. Our approach differs from both of these. We compile constraints and
add them to the training process of an RL agent; our constraints are motivated
by real-world physics, which are crucial for safety-critical domains. Unlike
[27] we do not rely on WMC to evaluate the constraints as they rely on SAT
solvers, instead we designed a more suitable metric for constraint evaluation
in sequential decision-making tasks.

One of the closest works to ours is [28] comprised of a two-system, a fuzzy
rule controller that takes the represented human knowledge constraints and
returns a preferred action and a refined module that tunes the suboptimal
knowledge. The constraints are represented in fuzzy logic and allow for
imprecise policy selection. During the constraint generation, they assume to
have perfect knowledge of the state-space, and the constraints fully capture
all aspects of the state-space, which is a strong assumption to hold. Our work
differs from this: we do not assume to know the full-state space dynamics and
do not use constraints to warm-start the policy; further, our constraints are
much more general and expressive. To illustrate this generality, consider the
rule from [28] Rule: IF $S_{1}$ is $Ml_{1}$ and $S_{2}$ is $Ml_{2}$ and… and
$S_{k}$ is $Ml_{k}$ THEN Action is $a_{j}$: where $S_{i}$ are variables that
describe different parts of the state, $Ml_{i}$ is the fuzzy rules
corresponding to each $S_{i}$ and $a_{j}$ is the action taken. This rule would
only be applicable with in fully observable scenarios: an assumption which is
unrealistic in many real-world applications. Their approach is no different to
hard encoding actions. In our framework, constraints are high level, general,
and provide expressiveness. For example, consider when we want to specify that
the agent’s distance to an undesired object (e.g. traffic light) should be
greater than the lower bound or if the distance is less than, the lower bound,
the agent should decrease its speed
$\varphi(s)=(lb\leq||s-obj||)\lor(velocity\leq v_{limit}\land||s-obj||\leq
ub)$. Similarly, there exist other approaches [9, 11, 13, 10, 16, 12, 14, 5,
15] that define safety by the satisfaction of temporal logical formulae of the
learnt policy.

Other works in this space [19] propose constrained Q-learning to restrict the
action space directly in the Q-update to learn the optimal Q-function; they
claim this approach can lead to optimal safe policy in the induced MDP. Our
method also differs from this approach, and we do not change anything in the
existing deep RL toolbox. However, we believe that some actions become
prohibited in our constraint evaluation phase due to low log probability.

##  3 Preliminaries

In this section, we introduce RL formalism and model-based RL methods that we
will build upon in the development of System III. We model our problem as
Markov Decision Process (MDP), which is defined as a tuple $\langle
S,A,P,R,\gamma\rangle$. In the MDP model $S\subseteq\mathbb{R}^{n}$ is a
continuous state space, $A\subseteq\mathbb{R}^{m}$ is a continuous action
space, and $P:\mathfrak{B}(\mathbb{R}^{n})\times A\times S\rightarrow[0,1]$ is
a Borel-measurable conditional transition kernel such that $P(\cdot|s,a)$ is a
probability measure of $s\in S$ and $a\in A$ over the Borel space
$(\mathbb{R}^{n},\mathfrak{B}(\mathbb{R}^{n}))$, where
$\mathfrak{B}(\mathbb{R}^{n})$ is the set of all Borel sets on
$\mathbb{R}^{n}$. The transition probability $P$ captures the motion
uncertainties of the agent, and it is assumed that $P$ is not known a priori.
A reward function $R:S\times A\times S\rightarrow\mathbb{R}$ defines a scalar
feedback that the agent receives. At each time step $t$ in the environment,
the agent observes a state $s_{t}\in S$, executes an action $a_{t}\in A$ and
transitions to the next state $s_{t+1}\sim P(\cdot|s_{t},a_{t})$ and receives
the reward associated with that action $r_{t}=R(s_{t},a_{t},s_{t+1})$. The
discount factor $\gamma\in[0,1]$ is used to weigh the current value of future
returns. A policy $\pi$ is a mapping from the state space to a distribution in
$\mathcal{P}(\mathcal{A})$, where $\mathcal{P}(\mathcal{A})$ is the set of
probability distributions on subsets of $\mathcal{A}$. A policy is stationary
if $\pi(\cdot|s)\in\mathcal{P}(\mathcal{A})$ does not change over time and it
is called a deterministic policy if $\pi(\cdot|s)$ is a degenerate
distribution. The objective in RL is to find a policy $\pi^{*}$ that maximises
the expected discounted sum of rewards,

$\mathbb{E_{\pi^{*}}}[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t},s_{t+1})],$
(1)

where $a_{t}\sim\pi(\cdot|s_{t})$, and $s_{t+1}\sim P(\cdot|s,a)$ [25, 22].
The value of state $s$ under any policy $\pi$, denoted as $V^{\pi}(s)$, is
similarly defined as the expected return starting at state $s$ and following
$\pi$ afterwards:
$V^{\pi}(s)=\mathbb{E}_{\pi}\Big{[}\sum_{t=0}^{\infty}\gamma^{t}r_{t}\mid
s_{0}=s\Big{]}.$ We might drop $\pi$ to simplify notation. We focus on policy
gradient methods, which model and optimise the policy directly. Different
policy gradient-based algorithms have been proposed in the literature, e.g.,
TRPO [23] and ACKTR [26], that learn to update the policy subject to a
constraint in the policy space which discourages large differences between
successive policies.

In policy gradient techniques, the key idea is to increase the probability of
actions that are associated with higher returns and reduce the probability of
actions that lead to lower return until an optimal policy is found. In this
paper, we use Asynchronous Advantage Actor Critic policy gradient (A3C) for
policy learning [21] combined with Generalized Advantage Estimation (GAE)
[24]. For a policy $\pi_{\theta}$ where $\theta$ is the neural network
parameters. $J(\pi_{\theta})$ is the expected discounted return, and
$\nabla_{\theta}J(\pi_{\theta})$ is the gradient of the return with respect to
the $\theta$:
$\nabla_{\theta}J(\pi_{\theta})=\mathbb{E_{\pi_{\theta}}}\Big{[}\sum\nabla_{\theta}\log\pi_{\theta}(s,a)A^{\pi_{\theta}}(s,a)\Big{]},$
where $A^{\pi_{\theta}}(s,a)$ is the advantage function. The policy gradient
algorithm updates the policy network parameter by stochastic gradient ascent
$\theta\leftarrow\theta+\alpha\nabla_{\theta}J(\pi_{\theta})$, where $\alpha$
is the learning rate.

##  4 Constraints Evaluation Using SMT

To illustrate how human prior knowledge is mapped to first order logic (FL)
sentences, consider the example of driving a car, where a learner, i.e. agent,
sits in the driver’s seat and observes the constraints in the environment,
e.g. other cars, designated driving lane, speed limit, humans, traffic signs
etc. Prior to driving, they have prior knowledge about the constraints in the
environment, for example, not to crash into humans, traffic signs, and not to
get out of the designated lane. Let us consider the example of not getting out
of the designated driving lane and maintaining the speed limit, as shown in
Figure 1(a) in Appendix 5. The prior knowledge for keeping the car in its
appropriate lane and respecting the speed limit can be expressed in the form
of ($lb\leq$ SPEED LIMIT $\leq ub$) $\land$ ($lb^{\prime}\leq$ DESIGNATED LANE
$\leq ub^{\prime}$) defined by a desirable range in Conjunctive Normal Form
(CNF) or Disjunctive Normal Form (DNF). For instance, if the car speed and the
designated lane are in the allowed range, and the distance by which any action
moves the car is smaller then the allowed range, any meditate should satisfy
the constraint because the agent will still be in the desired range.

##  5 System III Architecture

(a) Self-driving agent with SPEED LIMIT and DESIGNATED LANE

(b) System III architecture

Figure 1: S3 short for System III: Figure 1(a) shows a self-driving agent that
has to respect the speed limit and designated driving lane. The left-hand side
of Figure 1(b) shows the data generation (model free) while the right-hand
side of Figure 1(b) shows that the Forward Model takes $s_{t}$ and $a_{t}$ as
input and returns $\hat{s}_{t+1}$ as output. The Forward Model loss calculates
the discrepancy between $s_{t+1}$ and $\hat{s}_{t+1}$ and the constraint
satisfaction $\Delta$ calculates the reward $r^{c}_{t}$. The black arrows
indicate forward pass while, the red arrow indicates backward pass.

##  6 Running Example

Slippery grid world example below:

(a)

(b)

(c)

Figure 2: (a) Slippery grid world example, where yellow is the
$\mathit{target}$, red is $\mathit{unsafe}$, blue is $\mathit{safe}$, and
green is the initial state $s_{0}$; Safety and performance tuning with FL: (b)
value function $V(s)$ with $lb=0$; and (c) value function with $lb>0$ where
the FL formula is $\varphi(s)=lb\leq||s-\mathit{unsafe}||$, and
$||s-\mathit{unsafe}||$ is the agent’s distance to unsafe (red) states.

##  7 Combining Logical Constraints and Reinforcement Learning

High-Level FL Constraint: We take motivation from real-world settings, where
expressive yet intuitive constraints are required to fully capture the desired
behavior while are easily understandable for humans. For example, consider the
task of parking between two objects. Formally, given the agent state $s$, the
FL constraint is:

$\varphi(s)=\forall~{}\mathit{object_{i}}:~{}lb^{\prime}\leq||s-\mathit{object_{i}}||,$

where $||s-\mathit{object_{i}}||$ is the agent’s distance to the objects while
$lb^{\prime}$ is the lower bound on the distance.

The Running Example is shown in Figure 2 in Appendix 6 and is a moving robot
in a grid. Let the grid be a $20\times 20$ square over which the robot moves.
In this setup, the robot location is the MDP state $s\in{S}$. At each state
$s\in{S}$ the robot has a set of actions
${A}=\\{\mathit{left},\mathit{right},\mathit{up},\mathit{down},\mathit{stay}\\}$
using which the robot is able to move to other states (e.g. $s^{\prime}$) with
the probability of $P(s,a,s^{\prime}),a\in\mathcal{A}$. At each state
$s\in{S}$, the actions available to the robot are either to move to a
neighbour state $s^{\prime}\in{S}$ or to stay at the state $s$. In this
example, we assume for each action the robot chooses, there is a probability
of $85\%$ that the action takes the robot to the correct state and $15\%$ that
the action takes the robot to a random state in its neighbourhood, including
its current state. The property of interest in this example is an FL formula:
$\varphi(s)=\forall~{}\mathit{unsafe}_{i}:~{}||s-\mathit{unsafe}_{i}||\leq
lb$, where $||s-\mathit{unsafe}_{i}||$ is the agent’s distance to any unsafe
(red) state $\mathit{unsafe}_{i}$.

System III architecture: System III comprises two reciprocating subsystems: a
system that learns to model the next state $s_{t+1}$ and a system that
evaluates the constraints on $s_{t+1}$. The ability of the latter subsystem to
evaluate the constraints depends on the former subsystem’s ability to
accurately model the next state. We further define the total reward $r_{t}$ to
be the sum of reward returned by the environment ($r^{e}_{t}$) and reward
returned by the degree of constraints satisfaction ($r^{c}_{t}$) resulting in:
$r_{t}={r^{e}_{t}}+{r^{c}_{t}}$.

We use a policy $\pi(\cdot|s_{t};\theta_{p})$ representing an actor neural
network, where $s_{t}$ is the current state, and $\theta_{p}$ refers to the
weights of the network. An agent at state $s_{t}$ takes the action
$a_{t}\sim\pi(\cdot|s_{t};\theta_{p})$ sampled from the policy. The parameters
of the policy network $\theta_{p}$ are optimised to maximize the sum of
discounted expected return in (1). In order to ensure that the agent explores
the state space sufficiently to learn and satisfy the necessary constraints,
we construct a model to take as input the state $s_{t}$ and action $a_{t}$ and
returns the distribution of next state at $t+1$. This is also known as forward
dynamics. Formally: ${\hat{s}_{t+1}}\sim f(\cdot|s_{t},a_{t};\theta_{F})$,
where $\hat{s}_{t+1}$ is the estimate of ${s}_{t+1}$ and $\theta_{F}$ is the
forward model (e.g. a neural network) parameters. From the forward dynamics we
optimize the parameter $\theta_{F}$ by minimizing the mean squared loss
function:

$L_{f}=\sum_{t}(f(s_{t},a_{t})-(s_{t+1}))^{2}.$ (2)

With the model $f$ trained via mean squared loss function , we can evaluate
the constraints satisfaction at each time step. Consider the running example
FL constraint $\varphi(s)=lb\leq||s-\mathit{unsafe}||$. Define $\Delta:S\times
A\times S\rightarrow\mathbb{R}$ as the constraint evaluation function. At each
time step $t$, the agent observes a state $s_{t}\in S$, chooses an action
$a_{t}\in A$ and the forward model $f$ outputs ${\hat{s}_{t+1}}\sim
f(\cdot|s_{t},a_{t};\theta_{F})$. The constraint reward is then defined as:

${r^{c}_{t}}=\Delta(s_{t},a_{t},\hat{s}_{t+1})=\begin{cases}1~{}~{}~{}~{}\text{if}~{}~{}\varphi(\hat{s}_{t+1})\\\
0~{}~{}~{}~{}\text{otherwise}\end{cases}$.

We can write the overall optimization problem as a combination of (1) and (2):

$\min_{\theta_{p}\theta_{F}}[-\lambda\mathop{\mathbb{E}_{\pi_{(s_{t};\theta_{p})}}}[\sum_{t}\gamma
r_{t}]+\beta L_{F}],$ (3)

where $0\leq\beta\leq 1$ is a scalar that weighs the forward model loss and
$\lambda>0$ is a scalar that weighs the importance of the policy gradient loss
against the importance of satisfying the constraint.

##  8 Experiments setup and Results

In the running example, in order to get to the target state the agent has to
cross a bridge (Fig. 2a) surrounded by unsafe states. The grid is slippery,
namely from the agent’s perspective, when it takes an action it usually moves
to the intended cell, but there is an unknown probability that the agent is
moved to a random neighbour cell. However, the trained model $\hat{P}$
initially advises the agent that it can always move to the correct state and
this is the dynamics known to the agent. The initial state of the agent is
bottom left. For the simulated physical environments we consider OpenAI Gym
[4] and Safety Gym [1]. OpenAI’s Gym environment comprises a set of toolkits
for developing and comparing reinforcement learning algorithms. It contains
tasks ranging from control to Attari. For this paper, we focus on the
continuous control task CartPole [25]. In Safety Gym, we run experiments using
the Point, Car and Doggo robot [1] while varying the number of constraints in
the environment with constant goal task. In both environments, the agent
interacts with the environment and is rewarded based on the degree to which it
satisfies the constraints. We leave the case for sparse reward setting for
future work. Consider Figure 4(a), where the agent task is to press the
highlighted button while avoiding hazards. We represent such scenario via a
general FL formula:
$\varphi(s)=\\{(\forall~{}{\mathit{hazard}_{i}}:lb_{h}\leq||s-\mathit{hazard}_{i}||\leq
max\\_distance\\_pair\\_button)\land\\\
(\forall~{}{\mathit{goal\\_button}_{i}}:||s-\mathit{goal\\_button}_{i}||\leq
max\\_distance\\_pair\\_button)\\}.$

Constraints are defined as an ’allowable’ subspace of the state space. In the
CartPole experiment we deliver $d$-step accumulated reward every $d$ time
steps. The constraints on the in CartPole is: $\varphi(s)=(lb\leq x\leq
ub)\land(lb\leq k\leq ub)$ where $x$ corresponds to the cart position, and $k$
corresponds to the pole angle at tip. We evaluate our algorithm under
different delayed steps. Figure 3 plots the results under a sparse reward
setting. Similarly, in Safety-Gym, we provide $r^{c}_{t}$ after each immediate
action and $r^{e}_{t}$ is fully ignored as $r^{c}_{t}$ captures the degree of
satisfaction in each state. Table 1 shows the average episodic mean return
along with constraint violation (i.e. 1 - constraint satisfaction), where $0$
corresponds to $0\%$ constraint satisfaction and $1$ corresponds to $100\%$
satisfaction at evaluation. We train our system’s combined objective in 3 with
$\lambda$ = 0.15, $\beta$ = 0.3 and learning rate of $1e^{-3}$. We observe
there to exist an inverse relationship between the reward and constraint
satisfaction. Unconstrained algorithms (e.g. PPO and TRPO) achieves higher
return at the cost of high degree of constraint violation. However, PPO and
TRPO’s Lagrangian counter part which follows the adaptive penalty to enforce
constraints achieves higher degree of constraint satisfaction. We observe a an
inverse relationship between achieving higher reward and acting safely. System
3 is able to act safely after a small amount of interaction with the
environment at a cost of slightly lower return compared to the other methods
which achieves slightly higher return but does significantly worse at
satisfying the constraints. We hypothesis this is due to the nature of the the
environment reward function not being able to capture the actual desire of the
designer and what it intends it to do. We show that our method achieves high
constraint satisfaction (95%) as shown in 1 in Appendix 8, compared to popular
baselines designed to deal with constrained MDPs.

(a)

(b)

(c)

(d)

Figure 3: cartpole-v1 trained for 1e6 time steps (max score is 500). Each training loop has a length of 100 time steps and batch size of 20, hidden layers each has 64 nodes. Every 400 time steps, the model is saved and evaluated for 1000 time steps in “test runs”, i.e., no training. The score for each of the episodes that are completed are added in the test runs. The constraints are added up across all of the time steps in the test runs. The score plots are averaged between 10 different instances of the model at each time step, and the graph is smoothed with a 20 step rolling mean. The error plots are the same but with a 10 step rolling mean. The constraint are placed on the state space, e.g., angle and position. Method | Mean return | Constraint Satisfaction
---|---|---
PPO | 1.0 | 0.16
PPO-Lagrangian | 0.15 | 0.83
TRPO | 1.0 | 0.42
TRPO-Lagrangian | 0.61 | 0.83
System 3 | 0.75 | 0.95
Table 1: Normalized metrics from training averaged all environments and three random seeds per environment. Constraint Type | Static | Static & Moving
---|---|---
Method | Agent | Return | Constraint Sat | Return | Constraint Sat
PPO | Point | 1.0 | 0.16 | 1.0 | 0.11
Car | 1.0 | 0.26 | 1.0 | 0.23
Doggo | 1.0 | 0.08 | 1.0 | 0.17
PPO-Lagrangian | Point | 0.36 | 0.67 | 0.21 | 0.62
Car | 0.45 | 0.73 | 0.55 | 0.64
Doggo | 0.71 | 0.59 | 0.88 | 0.62
TRPO | Point | 1.0 | 0.32 | 0.99 | 0.28
Car | 1.0 | 0.41 | 1.0 | 0.45
Doggo | 1.0 | 0.64 | 1.0 | 0.43
TRPO-Lagrangian | Point | 0.41 | 0.73 | 0.56 | 0.84
Car | 0.62 | 0.88 | 0.73 | 0.88
Doggo | 0.69 | 0.89 | 0.67 | 0.84
System3 | Point | 0.73 | 0.96 | 0.68 | 0.94
Car | 0.72 | 0.96 | 0.75 | 0.95
Doggo | 0.81 | 0.94 | 0.82 | 0.93
Table 2: Agents: Mean return (return) and constraint satisfaction. Normalized
metrics from training averaged all environments and three random seeds per
environment

##  9 Conclusions And Future Work

In this paper we propose a novel framework for incorporating constraints in
the training processes of deep reinforcement learning. Our approach evaluates
the likelihood of constraints being satisfied at each point in time given a
state prediction, and this affects the agent’s reward function. The future
work should consider changing the environments and keeping the constraints
constant and learn the constraints directly from the environment. From a novel
safety and alignment perspective this work provides a solution for outer
alignment, however future research would need to address issues that might
arise with inner alignment.

## References

  * [1] Joshua Achiam Alex Ray and Dario Amodei.  Benchmarking safe exploration in deep reinforcement learning, 2019.
  * [2] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba.  End to end learning for self-driving cars, 2016.
  * [3] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  arXiv preprint arXiv:1606.01540, 2016.
  * [4] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym, 2016.
  * [5] Mingyu Cai, Hosein Hasanbeig, Shaoping Xiao, Alessandro Abate, and Zhen Kan.  Modular deep reinforcement learning for continuous motion planning with temporal logic.  In International Conference on Intelligent Robots and Systems. IEEE/RSJ, 2021.
  * [6] Mark Chavira and Adnan Darwiche.  On probabilistic inference by weighted model counting.  Artif. Intell., 172(6-7):772–799, 2008.
  * [7] Marc Fischer, Mislav Balunovic, Dana Drachsler-Cohen, Timon Gehr, Ce Zhang, and Martin Vechev.  DL2: Training and querying neural networks with logic.  In 36th International Conference on Machine Learning, ICML 2019, volume 2019-June, pages 3411–3427, 2019.
  * [8] Javier Garcıa and Fernando Fernández.  A comprehensive survey on safe reinforcement learning.  Journal of Machine Learning Research, 16(1):1437–1480, 2015.
  * [9] Hosein Hasanbeig, Alessandro Abate, and Daniel Kroening.  Logically-constrained reinforcement learning.  arXiv preprint arXiv:1801.08099, 2018.
  * [10] Hosein Hasanbeig, Alessandro Abate, and Daniel Kroening.  Certified reinforcement learning with logic guidance.  arXiv preprint arXiv:1902.00778, 2019.
  * [11] Hosein Hasanbeig, Alessandro Abate, and Daniel Kroening.  Logically-constrained neural fitted q-iteration.  AAMAS, 2019.
  * [12] Hosein Hasanbeig, Alessandro Abate, and Daniel Kroening.  Cautious reinforcement learning with logical constraints.  AAMAS, 2020.
  * [13] Hosein Hasanbeig, Yiannis Kantaros, Alessandro Abate, Daniel Kroening, George J Pappas, and Insup Lee.  Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5338–5343. IEEE, 2019.
  * [14] Hosein Hasanbeig, Daniel Kroening, and Alessandro Abate.  Deep reinforcement learning with temporal logics.  In International Conference on Formal Modeling and Analysis of Timed Systems, pages 1–22. Springer, 2020.
  * [15] Hosein Hasanbeig, Daniel Kroening, and Alessandro Abate.  LCRL: Certified policy synthesis via logically-constrained reinforcement learning.  In International Conference on Quantitative Evaluation of Systems, pages 217–231. Springer, 2022.
  * [16] Hosein Hasanbeig, Natasha Yogananda Jeppu, Alessandro Abate, Tom Melham, and Daniel Kroening.  DeepSynth: Program synthesis for automatic task segmentation in deep reinforcement learning.  In AAAI Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence, 2021.
  * [17] Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt.  Unsolved problems in ML safety.  CoRR, abs/2109.13916, 2021.
  * [18] Daniel Kahneman.  Thinking, fast and slow.  Macmillan, 2011.
  * [19] Gabriel Kalweit, Maria Huegle, Moritz Werling, and Joschka Boedecker.  Deep constrained q-learning, 2020.
  * [20] Robin Manhaeve, Angelika Kimmig, Sebastijan Dumančić, Thomas Demeester, and Luc De Raedt.  Deepproblog: Neural probabilistic logic programming.  In Advances in Neural Information Processing Systems, volume 2018-Decem, pages 3749–3759, 2018.
  * [21] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1928–1937, New York, New York, USA, 20–22 Jun 2016. PMLR.
  * [22] Vitchyr Pong, Shixiang Gu, Murtaza Dalal, and Sergey Levine.  Temporal difference models: Model-free deep rl for model-based control, 2020.
  * [23] John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel.  Trust region policy optimization.  CoRR, abs/1502.05477, 2015.
  * [24] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel.  High-dimensional continuous control using generalized advantage estimation, 2018.
  * [25] Richard S. Sutton and Andrew G. Barto.  Reinforcement Learning: An Introduction.  The MIT Press, second edition, 2018.
  * [26] Yuhuai Wu, Elman Mansimov, Shun Liao, Roger B. Grosse, and Jimmy Ba.  Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation.  CoRR, abs/1708.05144, 2017.
  * [27] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck.  A semantic loss function for deep learning with symbolic knowledge.  In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5502–5511. PMLR, 10–15 Jul 2018\.
  * [28] Peng Zhang, Jianye Hao, Weixun Wang, Hongyao Tang, Yi Ma, Yihai Duan, and Yan Zheng.  Kogun: Accelerating deep reinforcement learning via integrating human suboptimal knowledge.  In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 2291–2297. ijcai.org, 2020.

## Appendix

##  Appendix A OpenAI SafetyGym

(a) Point Agent with press task

(b) Point Agent with position task

(c) Point Agent with push task

(d) Car Agent with press task

(e) Car Agent with position task

(f) Car Agent with push task

(g) Quadruped Agent with press task

(h) Quadruped Agent with position task

(i) Quadruped Agent with push task

Figure 4: Environment Agent and Constraint Configuration: All constraint
elements represent scenarios for the agent to avoid; they pose different
challenges for the agent by virtue of having different dynamics. To illustrate
the contrast: hazards (purple circle) provide no physical obstacle, vases
(blue box) are movable obstacles, pillars (tall purple box) are immovable
obstacles, buttons (orange button) can sometimes be perceived as goals, and
gremlins (purple box) are actively-moving obstacles.