Buuren (2018)) by removing a fixed proportion of modalities
$q\in\\{5\%,10\%,20\%,50\%\\}$, embedded in a 5-fold cross validation for each
$q$. In each fold, we thus impute a complete dataset and compare the resulting
imputations to the observed values. In such a setting, classical per-
observation metrics like RMSE are not necessarily the best choices: if after
removing MCAR features two observations were then the same for the resulting
features, a perfect imputation of the missing values resulting in a
permutation of the observations in the dataset would incur non-zero RMSE, yet
would arguably be correct. Similarly to Muzellec et al. (2020), we have thus
opted for an optimal transport metric, Wasserstein’s $W_{2}^{2}$. We use mice
with method oracles in $\\{$cart, norm, random forests (RF) (100 trees)$\\}$.
norm is not tree-based but a good alternative on normal data van Buuren
(2018). Notice that we have not used the default number of trees for random
forests (10), which we considered too small for our purpose. Due to the
difficulty of aggregating different types of variables to compute the
Wasserstein distance without accidentally dimming the contribution of some to
the total, we consider here only domains for which all variables have the same
or closely-related types (e.g. categorical with a close number of modalities).
We compute our metric using the squared errors normalized to the variable
domain for continuous variables, and the error (0/1 loss, multiclass single
valued) of prediction for nominal variables (in all cases, the contribution to
the distance of each variable is in $[0,1]$).

Results A key part of our experiments was to compare approaches on simulated
data since we then know the ground truth, including data with non-trivial
structure. Table A6 provides all results on our simulated domains. Several
conclusions dan be drawn: first, our GTs appear to be winning on at least half
of the total domain $\times$ MCAR$\%$ combinations, regardless of the mice
contender, even when heavy disparities appear depending on the domain. On
gridGauss for example, we become competitive for large $\%$ MCAR (though not
statistically significantly) while on circGauss we statistically significantly
beat all mice contenders on all but one run. We can also notice the quality of
the imputations from the plots: norm in mice is clearly failing to impute
mostly on the heavy dense regions of the domain. Our results are viauslly much
closer to those of cart and rf. We suspect that our method has a different
imputation ’quality’ pattern vs cart and rf: such methods typically
successfully impute near the modes while we can get a more balanced allocation
of data among modes. On domains like circGauss, we suspect this is the source
of our better results. We then have tested what happens when the number of
variables increases: to assess this, we used different kind of data (boolean /
trinary valued) and domains with an oncreasing number of variables (from 8 to
181). Results are in Table A7, from which it comes that we are competitive on
problems on up to 25 variables and while we are significantly beaten by mice
on the largest problem, one has to keep in mind that on dna, we compete on
imputation with a single tree model per fold when random forests aggregate 90
500 of them to do the same task. On may expect that this has impact as well on
the time to complete the task. This turns out to be true: on dna, it takes
less than 5 minutes to impute a fold with GTs (taking into account the
training of the GT), while mice requires more than two hours for the same task
on random forests. The implementations of our algorithms (Java) and mice’s (R)
require caution in comparing times, but we can safely say that on such domains
with relatively large number of variables, our approach takes much less time
to complete the task. Finally, mice is specifically designed for imputation
while our GTs can be used for other purposes than just imputation itself.

us vs mice$|$ | norm | cart | rf |  |  |  |
---|---|---|---|---|---|---|---
$\\#$trees | N/A | 10 | 1 000
gridgauss | 5$\%$ | m | m | m
10$\%$ | m | m | m
20$\%$ | m | m | m
50$\%$ | u | u | u | us | mice$|$norm | mice$|$cart | mice$|$rf
us vs mice$|$ | norm | cart | rf |  |  |  |
$\\#$trees | N/A | 10 | 1 000
ringgauss | 5$\%$ | u |  u(0.07) | m
10$\%$ | u | u | m
20$\%$ | m | u | u
50$\%$ | m | m |  m(0.08) | us | mice$|$norm | mice$|$cart | mice$|$rf
us vs mice$|$ | norm | cart | rf |  |  |  |
$\\#$trees | N/A | 10 | 1 000
circgauss | 5$\%$ |  u(0.04) | u |  u(0.09)
10$\%$ |  u(0.05) |  u(0.0003) |  u(0.0007)
20$\%$ |  u(0.001) |  u(0.001) |  u(0.002)
50$\%$ |  u(0.04) |  u(0.05) |  u(0.05) | us | mice$|$norm | mice$|$cart | mice$|$rf
us vs mice$|$ | norm | cart | rf |  |  |  |
$\\#$trees | N/A | 10 | 1 000
randgauss | 5$\%$ | u | u | u
10$\%$ | m |  u(0.02) | u
20$\%$ | m | m | m
50$\%$ | u | m | m | us | mice$|$norm | mice$|$cart | mice$|$rf
Table A6: Experiments impute on simulated domains gridgauss, ringgauss,
circgauss and randgauss: comparison of copycat GT induction with maximal size
(us) vs mice (van Buuren & Groothuis-Oudshoorn, 2011) with three prediction
methods: norm, cart and random forests. Left table: for each $\%$ of missing
completely at random (MCAR) variables (in $\\{5,10,20,50\\}$), we indicate
which of us (u) or mice (m) achieves the lowest average Wasserstein metric
$W_{2}^{2}$. Bold faces indicate when a Student paired $t$-test returns a
$p$-val $<0.1$, in which case the $p$-values is indicated in parenthesis.
Right plots: examples imputation results (red dots) on top of the domain’s
data (green) for $50\%$ MCAR.

us vs mice$|$ | cart | rf
---|---|---
$\\#$trees | 40 | 4 000
led |  5$\%$ |  u(0.04) | u
10$\%$ |  u(0.04) | m
20$\%$ | u | u
50$\%$ | m | u

us vs mice$|$ | cart | rf
---|---|---
$\\#$trees | 45 | 4 500
tictactoe |  5$\%$ | u |  m(0.07)
10$\%$ | u | m
20$\%$ | m |  m(0.05)
50$\%$ | u | m

us vs mice$|$ | cart | rf
---|---|---
$\\#$trees | 125 | 12 500
led24 |  5$\%$ | m | u
10$\%$ | u | m
20$\%$ | u | m
50$\%$ |  m(0.01) |  m(0.07)

us vs mice$|$ | cart | rf
---|---|---
$\\#$trees | 905 | 90 500
dna |  5$\%$ |  m(0.03) |  m(0.02)
10$\%$ |  m(0.02) |  m(0.004)
20$\%$ |  m(0.001) |  m(0.002)
50$\%$ |  m(0.002) |  m(0.001)

Table A7: Experiments impute on binary/trinary valued domains led, tictactoe,
led24, dna, with increasing number of nominal description variables. Notations
follow Table A6 (norm not shown as it does not impute all NAs). While we are
competitive on domains with the smallest number of variables, we are clearly
beaten by mice when the number of variables substantially increases like for
dna. Those numbers have to be read keeping in mind the number of trees
involved in imputing a single fold: while we compete with 1 tree against 40
(cart) and 4 000 (rf) on led, we compete with 1 tree against 905 (cart) and 90
500 (rf) on dna.

###  II.6 ’Training on synthetic’ experiment (train-synth)

Domain |  $\\#$1 |  $\\#$2 |  $\\#$3 |  $\\#$4 |  $\\#$5 |  $\\#$6 |  $\\#$7 |  $\\#$8
---|---|---|---|---|---|---|---|---
abalone | copy |  u(max) |  u(300) |  c(1K) |  c(300) |  c(10) |  u(10) | unif
dna | copy |  u(300) |  u(max) | unif |  c(10) |  u(10) |  c(1K) |  c(300)
house votes | copy |  u(300) |  u(max) |  c(1K) |  u(10) |  c(10) |  c(300) | unif
iris | copy |  c(1K) |  u(300) |  u(max) |  c(10) |  c(300) |  u(10) | unif
led24 | copy |  u(300) |  u(max) |  c(10) |  u(10) |  c(1K) | unif |  c(300)
led | copy |  u(300) |  u(max) |  c(1K) |  u(10) |  c(10) |  c(300) | unif
winered | copy |  u(300) |  u(max) |  c(1K) | unif |  u(10) |  c(300) |  c(10)
winewhite | copy |  u(max) |  u(300) |  u(10) | unif |  c(300) |  c(10) |  c(1K)
sigma-cabs | copy |  c(1K) |  c(300) |  c(10) |  u(max) |  u(300) | unif |  u(10)
open-policing | copy |  u(max) |  c(1K) |  u(300) |  c(300) |  c(10) |  u(10) | unif
Table A8: Ranking results on experiment train-synth, showing for each domain the order (left to right: from best to worst) of the three sizes of runs of our GTs (u(.), number in parenthesis = number of splits; max = up to 10 000 splits), the three runs of ct-gan with different epoch numbers (c(.)), the copy approach (we use the original data) and the unif(orm) approach (we use a random sample). Those two last methods have their cells shaded to locate them. copy |  u(300) |  u(max) |  c(1K) |  c(10) |  u(10) |  c(300) | unif
---|---|---|---|---|---|---|---
1 | 2.9 | 3 | 4.5 | 5.7 | 6 | 6.2 | 6.8
Table A9: Average rank for each approach in the train-synth, as collected in Table A8, ordered in increasing average rank. u(.) c(.) | 10$\star$ | 300$\star$ | 1K$\star$$\star$
---|---|---|---
10 |  1 / 7 / 2 |  3 / 4 / 3 |  2 / 3 / 5
300 |  8 / 1 / 1 |  8 / 1 / 1 |  4 / 5 / 1
max |  8 / 1 / 1 |  8 / 1 / 1 |  7 / 2 / 1
Table A10: Experiment train-synth: statistical wins / ties / statistical losses for us (u()) vs CT-GAN (c()). Statistical = significant for $p\leq 0.01$. For example, $a$ / $b$ / $c$ means we statistically win $a$ times, lose $c$ times and there is no statistical difference $b$ times. Each red star ($\star$) indicates a domain for which the related technique performed statistically worse than uniform sampling (unif) for $p=0.05$ (See Table A8 to spot those domains). Domain |  u(10) |  u(300) |  u(max) |  c(10) |  c(300) |  c(1K)
---|---|---|---|---|---|---
abalone | 23 | 90 | 193 | 14 | 62 | 215
dna | 2 | 7 | 38 | 143 | 1 051 | 3 128
house-votes | $\varepsilon$ | $\varepsilon$ | $\varepsilon$ | 7 | 20 | 51
iris | $\varepsilon$ | $\varepsilon$ | $\varepsilon$ | 7 | 17 | 42
led24 | $\varepsilon$ | 1 | 2 | 6 | 22 | 62
led | $\varepsilon$ | 1 | 1 | 6 | 14 | 46
winered | 3 | 8 | 14 | 13 | 24 | 62
winewhite | 17 | 46 | 131 | 17 | 52 | 210
sigma-cabs | 19 | 60 | 286 | 13 | 86 | 419
open-policing | 168 | 311 | 933 | 24 | 338 | 1 316
Table A11: Average training times to get the generated training sample on experiment train-synth, in seconds, rounded to the nearest second. ’$\varepsilon$’ means average $<0.5$s. Domain |  $|\mbox{GT}|/|\mathcal{X}|\cdot 100$ ($\%$)
---|---
abalone | 3.99
dna | 0.26
house-votes | 21.57
iris | 200.13
led24 | 6.00
led | 18.76
winered | 7.82
winewhite | 2.55
sigma-cabs | 2.31
open-policing | 0.41
Table A12: Experiment train-synth: average sizes of the GT obtained using u(300) relative to the domain size (see text). ground truth |  u(10) |  u(300) |  u(max) |  c(10) |  c(300) |  c(1K)
---|---|---|---|---|---|---
|  |  |  |  |  |
Figure 17: Experiment train-synth: 2D distribution plots for domain abalone (warning: scales vary). ground truth |  u(10) |  u(300) |  u(max) |  c(10) |  c(300) |  c(1K)
---|---|---|---|---|---|---
|  |  |  |  |  |
Figure 18: Experiment train-synth: 2D distribution plots for domain winered
(warning: scales vary). Notice that GTs manage to capture complex distribution
shapes (such as the ’wavy’ 2nd row) that neural nets do not necessarily
capture, and neural networks can generate data clearly outside admissible
bounds (negative values for some variables)

Objective In the context of tabular data, there can be several reasons to
replace a training sample with a data generator: (i) the storing size of the
generated model, in particular for big databases and / or with substantial
redundancy (Rob & Coronel, 1995), (ii) privacy (disregarding the privacy
model), (iii) security (with respect to classical databases), etc. . The
objective of this experiment is the replacement of the training data by a data
generator to address the supervised learning problem related to the training
data. For example, for domain iris, the objective is the prediction of a
flower’s variety among three.

Experimental setting For each domain, we carry out a 5-fold CV, leaving 20$\%$
of the data for testing and the rest for training. We train a data generator
with the training data, then generate a training sample the size of the
generator’s training sample. This training sample is then used in lieu of the
original training sample to train a model following the original data’s task.
The model is then used to predict the class of the testing fold’s examples. To
alleviate the bias on the choice of this classifier and its training
algorithm, we pick two types of classifiers / training models: random forests
(RFs) and gradient boosted decision trees (GBDTs), that we thus run on each
dataset. We compute the accuracy for label prediction and root mean square
error for regression problems. For each domain and each generator type, we
thus obtain 10 statistics (5 for RFs, 5 for GBDTs), to which we add the 10
running times and use them for comparisons between methods. Speaking methods,
we consider for generative trees (GTs) copycat training against a
discriminator minimizing Matusita’s loss Kearns & Mansour (1996). We grow
generative trees with three different sizes: very small (10 splits, i.e. 21
total nodes), medium (300 splits, i.e. 601 total nodes) and ’maximal’. In this
last case, we provide a limit size of 10 000 splits (i.e. 20 001 total nodes).
Notice that this maximal size is usually not reached, in particular when a
training fold contains less than 10 000 training examples. We compare our
three GT training flavours to three training neural network based methods
relying on the state of the art CT-GANs Xu et al. (2019). We use CT-GANs
code666https://github.com/sdv-dev/CTGAN with default parameters and varying
number of epochs, choosing small (10), medium (300) and large (1K) training
epochs. We also use two more contenders: the first is the copy contender,
which uses the original training data as training data. The second is the
uniform contender, which just generates uniform data in the features domains.
While we expect copy to lead the pack of algorithms, contender unif is used to
point algorithms failing at learning anything ’substantial’ about the domain
when it significantly beats them.

Results Table A8 provides the ranking results among all eight contenders for
each domain, where the average of the metric (accuracy or RMSE) is used to
rank from best to worst. Table A9 provides a more synthetic view by computing
the average rank for each contender. There are several conclusions to draw:
(i) as perhaps expected, copy is always the best approach; what is perhaps
less expected is that (ii) unif is far from always being the worst, CT-GANs
being the most frequently beaten contenders (albeit not necessarily
statistically significantly, see below) on four out of ten domains. More
importantly, (iii) our approach largely performs the best in all non-copy
approaches unless small GTs are used (u(10)). In eight out of ten domains,
u(300) is in the top-three contenders, and top-two if we exclude copy. An
interesting observation is that u(max) is also in the top-three contenders in
eight out of ten domains, showing that there is reduced overfitting effect due
to the large tree size (which we attribute in part to the constraint that
$p\not\in\\{0,1\\}$ for GT splits). Obviously, in a context where
explainability would be key, the smaller size option (u(300)) would be a
preferred choice. To dig further in comparing our method to CT-GAN, we have
computed the number of domains one significantly ($p=0.01$) beats the other,
adding to those statistics the number of times unif does significantly
($p=0.05$) beat some contender(s). All results are summarized in Table A10.
The results display the superiority of our GT-based approach (unless, again
small trees are used), but they also display that CT-GANs are, in few cases,
significantly beaten by unif – and this can happen for all three epoch
numbers. This aligns with the observation that dealing with tabular data with
neural nets forces sophisticated choices for the design (Xu et al., 2019) and
probably has as consequence that not optimizing sufficiently hyperparameters
can result in worse performances than uniform generation. We clearly do not
have this problem and believe that this is due to the fact that the tree
(graphs) used in GTs bring the same convenience for data generation as the
tree (graphs) used in decision trees have for discrimination. Figures 17 and
18 provide two examples of sets of 2D plots showing the distribution of
generated examples according to different sets of couples of real-values
variables. The absence of overfitting as well as the capturing of
sophisticated features of the data’s distribution is quite apparent, also in
comparison with neural nets. Last, we have computed the average computation
time to get the generated datasets for us and CT-GAN – thus, inclusive of the
training time for the generator. Results are provided in Table A11. One must
be cautious in comparing numbers as our implementation of our algorithms is in
Java while CT-GAN’s is in Python, but at least one conclusion seems fair to
draw: we are in general – and especially for bigger models / longer training –
achieving much better results than CT-GAN. The dna domain, for which the
imputation experiments were already displaying our superiority in terms of
training time (Section 6), is a clear example of reduction in training time
that can be of order $10\times$ — $100\times$ with GTs compared to neural
networks.

To put our results in perspective, we have also computed the relative size of
the GT learned with respect to each domain size, for each experiment: we use
as GT size $|\mbox{GT}|$ the total number of vertices and arcs, which equals
($1+5\cdot$split number) and as domain size, $|\mathcal{X}|$, the total size
of the dataset used (number of examples times number of variables). Table A12
presents the results obtained for u(300), from which it appears that the GT
learned can represent a tiny proportion of a domain’s size — at most a few
percents in most cases.

###  II.7 ’Synthetic discrimination’ experiment (synth-discrim)

Figure 19: Experiment synth-discrim: General overview of the pipeline, designed to avoid rewarding generators that would just copy their training sample. Domain |  wins vs copy |  loses vs unif
---|---|---
circgauss |  u(300) (0.01), u(max) (0.02) | None
randgauss |  u(300) (0.00004), u(max) (0.00002) |  c(10) (0.01)
ringgauss |  u(300) (0.002), u(max) (0.001) | None
abalone | None |  c(10) (0.0006)
dna | None | None
house-votes | None |  c(10) (0.0002)
iris | None |  c(10) (0.007), c(300) (0.0002)
led24 | None | None
led | None |  c(1K) (0.03)
winered | None |  u(300) (0.003), u(max) (0.001)
winewhite | None |  u(300) (0.006), u(max) (0.001)
sigma cabs | None |  u(10) (0.001), u(300) (0.001), u(max) (0.001), c(10) (0.001), c(300) (0.003)
open-policing | None | None
Table A13: Experiment synth-discrim: for each domain, we compute the list of contenders in our method and CT-GAN statistically winning against copy and statistically losing against unif (for $p\leq 0.05$, indicated in parenthesis). u(.) c(.) | 10 | 300 | 1K
---|---|---|---
10 |  7 / 4 / 2 |  6 / 5 / 2 |  6 / 5 / 2
300 |  8 / 4 / 1 |  8 / 3 / 2 |  8 / 3 / 2
max |  8 / 4 / 1 |  8 / 3 / 2 |  8 / 3 / 2
Table A14: Experiment synth-discrim: statistical wins / ties / statistical
losses for us (u()) vs CT-GAN (c()). Statistical = significant for $p\leq
0.01$. For example, $a$ / $b$ / $c$ means we statistically win $a$ times, lose
$c$ times and there is no statistical difference $b$ times. (See Table A13 to
spot those domains).

Objective The objective fits in a simple question: can generated examples look
like real ones ?

Experimental setting The question is simple but its treatment non trivial: we
need in particular to avoid ’rewarding’ generators that would just copy their
training examples. Figure 19 provides the training pipeline we have designed,
that we ran for each domain considered. In short, we split each domain in
three equal sized parts, say ${\mathcal{S}}_{1}$, ${\mathcal{S}}_{2}$ and
${\mathcal{S}}_{3}$. One of these parts, say ${\mathcal{S}}_{1}$, is used to
trained the generator, which then generates a sample $\tilde{\mathcal{S}}_{1}$
having the same size as ${\mathcal{S}}_{1}$. We then train a discriminator for
the 2-classes supervised learning problem consisting in distinguishing real
from fake, using $\tilde{\mathcal{S}}_{1}$ and another original part, say
${\mathcal{S}}_{2}$ as training samples. The discriminator is then tested on
the problem consisting in distinguishing $\tilde{\mathcal{S}}_{1}$ from the
last original part (not yet used), ${\mathcal{S}}_{3}$ in this case. The
smaller the final accuracy, the more ’realistic’ is considered
$\tilde{\mathcal{S}}_{1}$. We then permut the roles of the three samples and
run the experiment again, ending up in $3!=6$ accuracies for each domain.
Considering that the discriminator is trained and tested on two different
subsets of the original data as real data, there is an incentive to not just
’copy’ the original data but capture features about the domain that generalise
well for data generation. We have considered the same generators as in
experiment ’textsctrain-synth’: CT-GANs with small (10), medium (300) and
large (1K) number of training epochs; our method with 10, 300 and max splits
for GTs (recall that max = training up to 10 000 splits); we also consider the
copy and uniform baselines, the former giving an idea of the accuracy for the
original data and the latter giving the most ’blunt’ baseline. We consider the
same discriminators as in experiment ’train-synth’ (random forests and
gradient boosted decision trees).

Results We first have a look at the extreme results, i.e. how our method and
CT-GANs compare to copy and unif. Table A13 presents the detailed results
obtained for each domain. In this table, we only look at statistically
significant results — for example, when the accuracies on testing were
statistically significantly larger than unif (which means that unif performed
better), or when the accuracies on testing were statistically significantly
smaller than copy (which means that copy performed worse). The picture with
respect to unif displays that some CT-GANs (disregarding the number of epochs)
get worse results on almost half of the domains (6) while some of our methods
gets worse results on 3 of them. When looking at copy, we see that on our
simulated domains, our method actually gets systematically significantly
better results than copy when the number of splits is at least 300. This, we
believe, signals the potential for GTs to be used as efficient data
generators, eventually as parts of more complex generators for more complex
domains than our generated domains. We have also drilled down in the
comparison between our approach and CT-GANs in the same way as we did for
experiment train-synth. Table A14 presents the aggregated results, whose
formatting follows the same rules as for Table A10. The conclusion from this
Table is that our approach does better at producing ’realistically looking’
datasets than CT-GAN does. When the GTs are big enough (at least 300 splits),
the picture displays that our approach wins against all CT-GANs alternatives
on a large majority of domains.

###  II.8 ’Synthetic augmentation’ experiment (synth-aug)

u(.) c(.) | 10 | 300 | 1K
---|---|---|---
10 |  6 / 1 / 3 |  6 / 2 / 2 |  4 / 1 / 5
300 |  9 / 0 / 1 |  9 / 0 / 1 |  6 / 2 / 2
max |  9 / 0 / 1 |  9 / 0 / 1 |  7 / 1 / 2
Table A15: Experiment synth-aug: statistical wins / ties / statistical losses
for us (u()) vs CT-GAN (c()). Statistical = significant for $p\leq 0.01$. For
example, $a$ / $b$ / $c$ means we statistically win $a$ times, lose $c$ times
and there is no statistical difference $b$ times.

---
abalone
winewhite
winered
Table A16: Experiment synth-aug: detailed results on three domains for which
the metric is the RMSE. In each plot, the $x$ value of a vertical bar
indicates a method’s accuracy and the height along the $y$ axis indicates the
$\%$ of real data that represents generated data used to train the final
classifier (up to $100\%$). Green filled circles are GTs results, the size of
the circle indicating the number of splits in the GTs (  = 10,  = 300,  =
10K). Red filled diamonds are CT-GANs results, the size of the diamond
indicating the number of epochs (  = 10,  = 300,  = 1K). Finally, empty pink
squares ( ) are unif’s results and filled blue squares ( ) are those of copy.
---
iris
led
open-policing
sigma-cabs
Table A17: Experiment synth-aug: detailed results on four domains for which
the metric is the accuracy. Conventions follow Table A16.

Objective Supplementing real data with additional ’faithful’ generated data
could be envisioned as a way to improve the performances of models trained
from the whole data, a problem of substantial practical impact. Our objective
was to test how generative models can perform in such a scenario.

Experimental setting The setting can be summarized as the equivalent of the
train-synth experiment (Section II.6), with the sole modification that we
train (supervised) models using generated data mixed with the training data of
the generators instead of just the generated data alone. Equivalently, we
train with copy \+ a generated sample. This generated sample could be
generated by CT-GANs or our GTs, but we also try the copy case (we add real
examples) and the uniform case (we add uniformly generated examples). We first
tried the simplest experimental setting in which the size of the generated
data was the same as the size of the training data, but the experiments were
largely inconclusive in terms of who wins or loses. Hence, we have dug in this
scenario, allowing a varying $\%$ of generated data to be added to the
training data, for a $\%$ of generated data that would represent
$5\%,10\%,15\%,...,100\%$ of the training (real) data. This represents a lot
more experiments but also allows us to understand, for each generative
technique, what is the effect of putting more generative examples in the
training sample. Regardless of the comparison with the copy approach, a good
generative approach should bring improved results as the number of generated
examples increases. All other parameters, generative models and supervised
classifiers considered are the same as in the train-synth experiment.

Results Table A15 summarises the results obtained, much in the same way as
Tables A10 and A14. The results display that GTs tend to be a better fit for
data augmentation than CT-GANs. Training more the neural nets does not yield
an advantage over GTs, as even when comparing with GTs having a few dozen
nodes, the picture is still quite balanced. Tables A16 and A17 complete Table
4 for the remains domains used. We observe that while dna is clearly the
domain where CT-GANs obtained the worst results, with all accuracies
(substantially) lower than any of unif, such bad performances also occur in
domains winewhite and winered, which could signal that the issue is not linked
to the domain being categorical (winewhite and winered are both real-valued).
On iris, CT-GANs have a slight edge over GTs, an edge which much more
significant on sigma-cabs where GT results basically cannot be distinguished
from unif. We observe that in this domain, CT-GANs manage to get an
improvement over $+5\%$ real data, in the same way as GTs manage to get an
improvement over $+5\%$ real data on abalone. open-policing, which is our
biggest domain, displays that training for a longer time is beneficial to both
CT-GANs and GTs, but ultimately GTs get the best results. Two conclusions can
be drawn: first, there is still work to do to beat adding real data, for both
neural nets and generative trees, even when those latter models seem to
overall get the best and most stable results. Second, we do not observe for
generative trees the apparent overfitting pattern that follows CT-GANs on dna,
winewhite and winered. Apart from the fact that we prevent discarding support
in the induction of the GTs, we do not see currently any other reason for this
observation to happen.


#  On the distribution of the last exit time over a slowly growing linear
boundary for a Gaussian process111The work of M.A. Lifshits was supported by
RFBR-DFG grant 20-51-12004.

N.A. Karagodin222St.Petersburg State University, Department of Mathematics and
Computer Sciences, 199034, St.Petersburg, Universitetskaya emb., 79. email:
<EMAIL_ADDRESS>, M.A.Lifshits333St.Petersburg State University,
Department of Mathematics and Computer Sciences, 199034, St.Petersburg,
Universitetskaya emb., 79. email<EMAIL_ADDRESS>
###### Abstract

For a class of Gaussian stationary processes, we prove a limit theorem on the
convergence of the distributions of the scaled last exit time over a slowly
growing linear boundary. The limit is a double exponential (Gumbel)
distribution.

Key words and phrases: last exit time, Gaussian process, limit theorem, double
exponential law.

##  1 Introduction

###  1.1 Problem setting

Consider a stationary Gaussian process with continuous trajectories and its
”last exit time over a linear boundary”, i.e. the last instant when the
process hits a line $at$, where $t$ denotes time and $a>0$ is a drift (or
trend) parameter. After this instant, the process stays forever under the
line. We are interested in the asymptotic distribution of the last exit time
when the trend $a$ goes to zero. In this work, we will prove a limit theorem
on the convergence of the distribution of the properly centered and scaled
last exit time to a double exponential (Gumbel) law.

A special case of this problem, for a particular process, emerged in recent
works [2, 3] providing a mathematical study of a physical model (Brownian
chain break). Quite naturally, a question is raised, whether it is possible to
extend that result to a sufficiently wide class of processes. This is what we
do here.

As far as we know, the problem setting handling the small trend is new,
although the last exit time is a sufficiently popular object in the problems
of economical applications such as studies of ruin probabilities. In those
settings, however, as a rule, one considers processes with stationary
increments and trend is fixed, see [4, 5, 7].

###  1.2 Main result

Let $Y(t),t\in\mathbb{R}$, be a real-valued centered stationary Gaussian
process with covariance function $\rho(t):=\mathbb{E}\,[Y(t)Y(0)]$. We make
two assumptions on the covariance function: at zero

$\displaystyle\rho(t)=v^{2}(1-Q|t|^{\alpha}+o(|t|^{\alpha})),\quad\textrm{as
}t\to 0,$ (1)

for some $v>0,Q>0$, $\alpha\in(0,2]$, and at infinity

$\displaystyle\rho(t)=o((\ln t)^{-1}),\quad\textrm{as }t\to+\infty.$ (2)

Recall that relation (1) appears in the following lemma that will serve as one
of the two basic tools in our calculations.

###### Lemma 1

(Pickands–Piterbarg lemma). Let $Y(t),t\in\mathbb{R}$, be a real-valued
centered stationary Gaussian process satisfying conditions (1) and

$\limsup_{t\to\infty}\rho(t)<1.$

Then

${\mathbb{P}}\left\\{\max_{s\in[0,t]}Y(s)\geq
x\right\\}\sim\frac{Q^{1/\alpha}{\mathcal{H}}_{\alpha}}{\sqrt{2\pi}}\cdot
t\cdot(x/v)^{2/\alpha-1}e^{-x^{2}/2v^{2}}$

for all $x$ and $t$ such that the right hand side tends to zero and
$tx^{2/\alpha}\to\infty$. Here ${\mathcal{H}}_{\alpha}$ are Pickands constants
(in particular, ${\mathcal{H}}_{1}=1$,${\mathcal{H}}_{2}=\pi^{-1/2}$).

Here and elsewhere throughout the paper $f\sim g$ stands for
$\lim\tfrac{f}{g}=1$. A first version of this lemma with fixed $t$ was
obtained by Pickands [8], while this version with variable $t$ (which is very
important for our goals) is due to Piterbarg, see [9, lecture 9].

Define the $Y$’s last exit time over a linear boundary as

$T=T(\varepsilon):=\max\\{t:Y(t)=\varepsilon\,t\\}.$

The main result of our work is as follows.

###### Theorem 2

Let $Y(t),t\in\mathbb{R}$, be a real-valued centered stationary Gaussian
process satisfying assumptions (1) and (2). Let
$c:=\frac{Q^{1/\alpha}{\mathcal{H}}_{\alpha}}{\sqrt{2\pi}}$,
$\varepsilon_{v}:=\frac{\varepsilon}{v}$. Then for each $r\in\mathbb{R}$ it is
true that

$\lim_{\varepsilon\to
0}{\mathbb{P}}\left\\{\frac{T(\varepsilon)-A_{\varepsilon}}{B_{\varepsilon}}\leq
r\right\\}=\exp(-c\exp(-r)),$

with the scaling constants

$\displaystyle A_{\varepsilon}$ $\displaystyle:=$
$\displaystyle\varepsilon_{v}^{-1}\left(\sqrt{-2\ln\varepsilon_{v}}+\left(\frac{1}{\alpha}-1\right)\,\frac{\ln(-2\ln\varepsilon_{v})}{\sqrt{-2\ln\varepsilon_{v}}}\right),$
$\displaystyle B_{\varepsilon}$ $\displaystyle:=$
$\displaystyle\left(\varepsilon_{v}\sqrt{-2\ln\varepsilon_{v}}\right)^{-1}.$

We stress that the research technique of the initial work [2] was based on the
exponential strong mixing property satisfied by the process studied there. In
our work, the assumption is only imposed on the covariance function (which is
by far easier to check than strong mixing) and the condition of the covariance
decay is logarithmic instead of the exponential one.

The double exponential law usually emerges in the studies of maxima of the
identically distributed random variables. Amazingly, in our problem it is
related to the maxima of non-identically distributed variables.

##  2 Proofs

###  2.1 Proof of Theorem 2

By the linear variable change $Y(t)=v{\widetilde{Y}}(Q^{1/\alpha}t)$ one may
reduce the problem to the case $v=Q=1$, $\varepsilon_{v}=\varepsilon$, which
is considered in the following.

Let us fix $r\in\mathbb{R}$ and let

$\tau=\tau(\varepsilon,r):=A_{\varepsilon}+B_{\varepsilon}r.$

The theorem’s statement is equivalent to

$\lim_{\varepsilon\to
0}{\mathbb{P}}\left\\{T(\varepsilon)\leq\tau\right\\}=\exp(-c\exp(-r)).$

In order to prove this, we cover the halfline $[\tau,\infty)$ by the following
system of sets:

  * •

the halfline $[\sigma,\infty)$, where
$\sigma:=A_{\varepsilon}+B_{\varepsilon}R$ and $R=R(\varepsilon)$ slowly tends
to infinity. The choice of $R$ will be further specified at the end of the
proof.

  * •

long intervals $L_{i}=[(\ell+s)i,(\ell+s)i+\ell]$, $i\in{\mathbb{Z}}$, of some
length $\ell$,

  * •

shorter intervals $S_{i}=[(\ell+s)i+\ell,(\ell+s)(i+1)]$,$i\in{\mathbb{Z}}$,
of length $s$.

In fact the main part of process exits over the linear boundary will occur on
the long intervals, while the shorter intervals placed between the long ones
play the role of separators providing weak dependence between the process
values on different long intervals.

The interval lengths $\ell=\ell(\varepsilon)$, $s=s(\varepsilon)$ must satisfy
the relations

$\displaystyle\ln s\sim|\ln(-\varepsilon)|,$ (3) $\displaystyle s/\ell\to 0,$
(4) $\displaystyle\varepsilon\,\sqrt{-\ln\varepsilon}\,\ell\to 0.$ (5)

The parameter $R$ should grow to infinity so slowly that

$\displaystyle\tau\sim\sigma.$ (6)

Let

$X_{i}^{\varepsilon}:=\max_{t\in L_{i}}Y(t);\quad
V_{i}^{\varepsilon}:=\max_{t\in S_{i}}Y(t).$

By using stationarity, we infer from Pickands–Piterbarg lemma the asymptotics
${\mathbb{P}}\\{X_{i}^{\varepsilon}\geq x\\}\sim
c\,\ell\,x^{2/\alpha-1}\exp(-x^{2}/2)$ and
${\mathbb{P}}\\{V_{i}^{\varepsilon}\geq x\\}\sim
c\,s\,x^{2/\alpha-1}\exp(-x^{2}/2)$, as soon as the corresponding right hand
sides tend to zero. Here $c=\tfrac{{\mathcal{H}}_{\alpha}}{\sqrt{2\pi}}$.

Define the index sets

$\displaystyle I_{1}$ $\displaystyle:=$ $\displaystyle\\{i:\
\begin{subarray}{c}(\ell+s)i+\ell\geq\tau\\\
(\ell+s)i<\sigma\end{subarray}\\},$ $\displaystyle I_{2}$ $\displaystyle:=$
$\displaystyle\\{i:\ \begin{subarray}{c}(\ell+s)i\geq\tau\\\
(\ell+s)i+\ell<\sigma\end{subarray}\\},$ $\displaystyle I_{3}$
$\displaystyle:=$
$\displaystyle\\{i:\begin{subarray}{c}(\ell+s)(i+1)\geq\tau\\\
(\ell+s)i+\ell<\sigma\end{subarray}\\},$

chosen so that the following inclusions hold:

$\bigcup_{i\in I_{2}}L_{i}\subset[\tau,\sigma]\subset\big{(}\bigcup_{i\in
I_{1}}L_{i}\big{)}\cup\big{(}\bigcup_{i\in I_{3}}S_{i}\big{)}.$ (7)

In the first inclusion one considers the long intervals belonging to
$[\tau,\sigma]$; in the second one, the long intervals and the short intervals
separating them cover $[\tau,\sigma]$.

Let us define the events related to the exits of our process over the linear
boundary:

$\displaystyle{\mathcal{E}}_{1}$ $\displaystyle:=$ $\displaystyle\bigcup_{i\in
I_{1}}\\{X_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon\\},$
$\displaystyle{\mathcal{E}}_{2}$ $\displaystyle:=$ $\displaystyle\bigcup_{i\in
I_{2}}\\{X_{i}^{\varepsilon}\geq(\ell+s)(i+1)\varepsilon\\},$
$\displaystyle{\mathcal{E}}_{3}$ $\displaystyle:=$ $\displaystyle\bigcup_{i\in
I_{3}}\\{V_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon\\},$
$\displaystyle{\mathcal{E}}_{4}$ $\displaystyle:=$
$\displaystyle\\{\exists\,t>\sigma:Y(t)\geq\varepsilon t\\}.$

By using inclusions (7) and monotonicity of the linear function, it is easy to
see that the following bounds are true:

$\displaystyle{\mathbb{P}}\\{T(\varepsilon)>\tau\\}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\\{\exists\,t>\tau:Y(t)\geq\varepsilon
t\\}\leq{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}+{\mathbb{P}}\\{{\mathcal{E}}_{3}\\}+{\mathbb{P}}\\{{\mathcal{E}}_{4}\\},$
$\displaystyle{\mathbb{P}}\\{T(\varepsilon)>\tau\\}$ $\displaystyle\geq$
$\displaystyle{\mathbb{P}}\\{{\mathcal{E}}_{2}\\}.$

Therefore, it is sufficient to prove that, as $\varepsilon\to 0$, we have

$\displaystyle{\mathbb{P}}\\{{\mathcal{E}}_{1}\\},{\mathbb{P}}\\{{\mathcal{E}}_{2}\\}$
$\displaystyle\rightarrow$ $\displaystyle 1-\exp(-c\exp(-r)),$
$\displaystyle{\mathbb{P}}\\{{\mathcal{E}}_{3}\\},{\mathbb{P}}\\{{\mathcal{E}}_{4}\\}$
$\displaystyle\rightarrow$ $\displaystyle 0.$

Let us first prove that the probabilities of the events ${\mathcal{E}}_{1}$
and ${\mathcal{E}}_{2}$ are almost equal, thus it will be enough to find the
limit of ${\mathbb{P}}\\{{\mathcal{E}}_{1}\\}$. Indeed, let the indices $m$
and $n$ be such that $I_{1}=[m,n]$. Then

$\displaystyle{\mathbb{P}}\\{{\mathcal{E}}_{2}\\}$ $\displaystyle\leq$
$\displaystyle{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}={\mathbb{P}}\left\\{\bigcup_{i=m}^{n}\\{X_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon\\}\right\\}$
$\displaystyle\leq$
$\displaystyle{\mathbb{P}}\left\\{X_{m}^{\varepsilon}\geq(\ell+s)m\varepsilon\right\\}+{\mathbb{P}}\left\\{X_{m+1}^{\varepsilon}\geq(\ell+s)(m+1)\varepsilon\right\\}$
$\displaystyle+{\mathbb{P}}\left\\{\bigcup_{i=m+2}^{n}\\{X_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon\\}\right\\}$
$\displaystyle\leq$ $\displaystyle
2\,{\mathbb{P}}\left\\{X_{m}^{\varepsilon}\geq(\ell+s)m\varepsilon\right\\}+{\mathbb{P}}\left\\{\bigcup_{j=m+1}^{n-1}\\{X_{j+1}^{\varepsilon}\geq(\ell+s)(j+1)\varepsilon\\}\right\\}$
$\displaystyle\leq$ $\displaystyle
2\,{\mathbb{P}}\left\\{X_{m}^{\varepsilon}\geq(\ell+s)m\varepsilon\right\\}+{\mathbb{P}}\\{{\mathcal{E}}_{2}\\},$

where in the penultimate inequality we used the stationarity of the sequence
$X_{i}^{\varepsilon}$ following from the stationarity of the process $Y$. For
the remaining term we use Pickands–Piterbarg bound and obtain

${\mathbb{P}}\left\\{X_{m}^{\varepsilon}\geq(\ell+s)m\varepsilon\right\\}\leq{\mathbb{P}}\left\\{X_{m}^{\varepsilon}\geq(\tau-\ell)\varepsilon\right\\}\sim
c\ell[(\tau-\ell)\varepsilon]^{2/\alpha-1}\exp\\{-[(\tau-\ell)\varepsilon]^{2}/2\\}.$

Let us take into account that the definitions of $\tau$ and $\sigma$ yield the
following three relations:

$\displaystyle\tau$ $\displaystyle\sim$
$\displaystyle\varepsilon^{-1}\sqrt{-2\ln\varepsilon},$ (8)
$\displaystyle\frac{1}{\varepsilon}(\tau\varepsilon)^{2/\alpha-2}\exp\\{-(\tau\varepsilon)^{2}/2\\}$
$\displaystyle\sim$ $\displaystyle e^{-r},$ (9)
$\displaystyle\frac{1}{\varepsilon}(\sigma\varepsilon)^{2/\alpha-2}\exp\\{-(\sigma\varepsilon)^{2}/2\\}$
$\displaystyle=$ $\displaystyle o(1).$ (10)

We stress that equation (9) is a key for the choice of the scaling constants
$A_{\varepsilon}$ and $B_{\varepsilon}$ in the theorem assertion.

We use the bound (5) and obtain $\ell/\tau\to 0$, $\ell\tau\varepsilon^{2}\to
0$. Therefore,

$\displaystyle\ell[(\tau-\ell)\varepsilon]^{2/\alpha-1}\exp\\{-[(\tau-\ell)\varepsilon]^{2}/2\\}$
$\displaystyle\sim$
$\displaystyle\ell(\tau\varepsilon)^{2/\alpha-1}\exp\\{-(\tau\varepsilon)^{2}/2\\}$
$\displaystyle\sim$ $\displaystyle\ell\tau\varepsilon^{2}e^{-r}\to 0.$

We conclude that
${\mathbb{P}}\left\\{X_{m}^{\varepsilon}\geq(\ell+s)m\varepsilon\right\\}\to
0$, so that the difference between ${\mathbb{P}}\\{{\mathcal{E}}_{1}\\}$ and
${\mathbb{P}}\\{{\mathcal{E}}_{2}\\}$ is indeed negligible.

In the sequel, we will many times use the following technical lemma. Its proof
is postponed to Section 2.2.

###### Lemma 3

For each $\alpha\neq 0$ and all
$\theta(\varepsilon),a(\varepsilon),b(\varepsilon)$ such that, as
$\varepsilon\to 0$, one has $\theta\varepsilon\to\infty$, $a=o(\theta)$,
$\theta a\varepsilon^{2}\to 0$, it is true that

$\sum_{i:ai+b\geq\theta}^{\infty}[(ai+b)\varepsilon]^{2/\alpha-1}\exp\\{-[(ai+b)\varepsilon]^{2}/2\\}\sim\frac{1}{a\varepsilon}(\theta\varepsilon)^{2/\alpha-2}\exp\\{-(\theta\varepsilon)^{2}/2\\}.$

Let us evaluate ${\mathbb{P}}\\{{\mathcal{E}}_{3}\\}$. By Pickands–Piterbarg
asymptotics, we have

$\displaystyle{\mathbb{P}}\\{{\mathcal{E}}_{3}\\}$ $\displaystyle\leq$
$\displaystyle\sum_{i\in
I_{3}}{\mathbb{P}}\\{V_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon\\}$
$\displaystyle\leq$ $\displaystyle
c\,s\,\sum_{i:(\ell+s)(i+1)\geq\tau}[(\ell+s)i\varepsilon]^{2/\alpha-1}\exp\\{-[(\ell+s)i\varepsilon]^{2}/2\\}(1+o(1)).$

In order to find the asymptotic behavior of this sum, we apply Lemma 3 with
parameters $a=\ell+s,b=0,\theta=\tau-\ell-s$. Then, by using (4), (5), and (8)
we have
$a\sim\ell,\theta\sim\tau,(\theta\varepsilon)^{2}=(\tau\varepsilon)^{2}+o(1)$.
Therefore, Lemma 3, relation (9), and assumption (4) yield

$\frac{cs}{a\varepsilon}(\theta\varepsilon)^{2/\alpha-2}\exp\\{-(\theta\varepsilon)^{2}/2\\}\sim\frac{cs}{\ell\varepsilon}(\tau\varepsilon)^{2/\alpha-2}\exp\\{-(\tau\varepsilon)^{2}/2\\}=o(1).$

Evaluation of ${\mathbb{P}}\\{{\mathcal{E}}_{4}\\}$ goes along the same lines.
By splitting the halfline $[\sigma,\infty)$ into the intervals of the unit
length, we obtain

$\displaystyle{\mathbb{P}}\\{{\mathcal{E}}_{4}\\}\leq\sum_{j=0}^{\infty}{\mathbb{P}}\\{\max_{t\in[\sigma+j,\sigma+j+1]}Y(t)>\varepsilon(\sigma+j)\\}$
$\displaystyle\leq$ $\displaystyle
c\,\sum_{j=0}^{\infty}[(\sigma+j)\varepsilon]^{2/\alpha-1}\exp\\{-[\sigma+j)\varepsilon]^{2}/2\\}(1+o(1)).$

We use Lemma 3 with parameters $a=1,b=\sigma,\theta=\sigma$. By applying (10),
we obtain the asymptotics

$\frac{c}{\varepsilon}(\sigma\varepsilon)^{2/\alpha-2}\exp\\{-(\sigma\varepsilon)^{2}/2\\}=o(1).$

The subsequent estimates use the effect of weak dependence of the values of
the process $Y$ at distant times. Our main tool here is the following
classical inequality due to Slepian (see e.g., [6, §14], [9, lecture 2]).

###### Lemma 4

Let $(U_{1},...,U_{n})$ and $(V_{1},...,V_{n})$ be two centered Gaussian
vectors such that $\mathbb{E}\,U_{j}^{2}=\mathbb{E}\,V_{j}^{2}$, $1\leq j\leq
n$, and $\mathbb{E}\,(U_{i}U_{j})\leq\mathbb{E}\,(V_{i}V_{j})$, $1\leq i,j\leq
n$. Then for each $r\in\mathbb{R}$ one has

${\mathbb{P}}\left\\{\max_{1\leq j\leq n}U_{j}\geq
r\right\\}\geq{\mathbb{P}}\left\\{\max_{1\leq j\leq n}V_{j}\geq r\right\\}.$

One may write this inequality in a slightly more general form (see [9, lecture
2]): under assumptions of Slepian lemma, for all non-negative
$r_{1},...,r_{n}$ one has

${\mathbb{P}}\left\\{\exists j:\ U_{j}\geq
r_{j}\right\\}\geq{\mathbb{P}}\left\\{\exists j:\ V_{j}\geq r_{j}\right\\}.$

This fact follows by application of Slepian inequality to the vectors
$(\tfrac{U_{1}}{r_{1}},...,\tfrac{U_{n}}{r_{n}})$,
$(\tfrac{V_{1}}{r_{1}},...,\tfrac{V_{n}}{r_{n}})$ and $r=1$.

The latter inequality obviously extends to the Gaussian processes with
continuous trajectories defined on a metric space (by the way, the processes
satisfying assumption (1) belong to this class). Namely, let $\\{U(t),t\in
T\\}$ and $\\{V(t),t\in T\\}$ be two Gaussian processes with continuous
trajectories defined on a common metric space $T$. Let
$\mathbb{E}\,U(t)^{2}=\mathbb{E}\,V(t)^{2}$, $t\in T$, and
$\mathbb{E}\,(U(t_{1})U(t_{2}))\leq\mathbb{E}\,(V(t_{1})V(t_{2}))$,
$t_{1},t_{2}\in T$. Then for all compact sets $T_{1},...,T_{n}$ in $T$ and for
all non-negative $r_{1},...,r_{n}$ it is true that

${\mathbb{P}}\left\\{\bigcup_{j=1}^{n}\left\\{\max_{t\in T_{j}}U(t)\geq
r_{j}\right\\}\right\\}\geq{\mathbb{P}}\left\\{\bigcup_{j=1}^{n}\left\\{\max_{t\in
T_{j}}V(t)\geq r_{j}\right\\}\right\\}.$ (11)

Now we may proceed to the proof of the remaining claim

$1-{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}\rightarrow\exp(-c\exp(-r)),\qquad\varepsilon\to
0.$ (12)

We provide the corresponding upper and lower bounds. In both cases we will use
Slepian inequality in the form (11).

Upper bound.

Let us compare our process $Y$ with an auxiliary process $Z$ which is defined
as follows. First, let us consider a process $\widetilde{Y}(t),t\in\cup L_{i}$
which consists of independent copies of $Y(t)$ on the intervals $L_{i}$.

Further, let

$\delta^{2}=\delta^{2}(\varepsilon):=\sup_{t\geq
s(\varepsilon)}\left|\mathbb{E}\,[Y(t)Y(0)]\right|.$

Taking into account the correlation decay assumption (2) and assumption (3)
concerning the choice of $s$, we have

$\delta^{2}=o((\ln s)^{-1})=o((-\ln\varepsilon)^{-1}).$ (13)

Let $\xi$ be an auxiliary standard normal random variable independent with the
process $\widetilde{Y}$. We define the centered Gaussian process $Z(t)$,
$t\in\cup L_{i}$, by the equality

$Z(t):=\sqrt{1-\delta^{2}}\widetilde{Y}(t)+\delta\xi.$

Then for all $t$ the variances are equal:
$\mathbb{E}\,Y(t)^{2}=\mathbb{E}\,Z(t)^{2}=1$. For covariances we have the
following inequalities:

  * •

for $t_{1}$ and $t_{2}$ that belong to the same interval $L_{i}$ we have

$\displaystyle\mathbb{E}\,[Z(t_{1})Z(t_{2})]$ $\displaystyle=$
$\displaystyle\mathbb{E}\,\left[\left(\sqrt{1-\delta^{2}}{\widetilde{Y}}(t_{1})+\delta\xi\right)\left(\sqrt{1-\delta^{2}}{\widetilde{Y}}(t_{2})+\delta\xi\right)\right]$
$\displaystyle=$
$\displaystyle(1-\delta^{2})\mathbb{E}\,[Y(t_{1})Y(t_{2})]+\delta^{2}\geq\mathbb{E}\,[Y(t_{1})Y(t_{2})],$

where the last inequality follows from
$\mathbb{E}\,[Y(t_{1})Y(t_{2})]\leq\sqrt{\mathbb{E}\,Y(t_{1})^{2}\mathbb{E}\,Y(t_{2})^{2}}$
$=1$,

  * •

for $t_{1}$ and $t_{2}$ that belong to different intervals $L_{i}$ and
$L_{j}$, by the definition of $\delta$ and by intervals’ construction we have

$\displaystyle\mathbb{E}\,[Z(t_{1})Z(t_{2})]$ $\displaystyle=$
$\displaystyle\mathbb{E}\,\left[\left(\sqrt{1-\delta^{2}}{\widetilde{Y}}(t_{1})+\delta\xi\right)\left(\sqrt{1-\delta^{2}}{\widetilde{Y}}(t_{2})+\delta\xi\right)\right]$
$\displaystyle=$ $\displaystyle\delta^{2}\geq\mathbb{E}\,[Y(t_{1})Y(t_{2})].$

Let ${\widetilde{X}}_{i}^{\varepsilon}:=\max_{t\in L_{i}}{\widetilde{Y}}(t)$.
By applying Slepian inequality (11) to the processes $Y$ and $Z$, we obtain

${\mathbb{P}}\\{{\mathcal{E}}_{1}\\}={\mathbb{P}}\left\\{\bigcup_{i\in
I_{1}}\\{X_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon\\}\right\\}\geq{\mathbb{P}}\left\\{\bigcup_{i\in
I_{1}}\\{\sqrt{1-\delta^{2}}{\widetilde{X}}_{i}^{\varepsilon}+\delta\xi\geq(\ell+s)i\varepsilon\\}\right\\}.$

Let us pass to the complementary events; for every $h=h(\varepsilon)>0$ the
following elementary bound holds,

$\displaystyle 1-{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\left\\{\bigcap_{i\in
I_{1}}\\{X_{i}^{\varepsilon}\leq(\ell+s)i\varepsilon\\}\right\\}$ (14)
$\displaystyle\leq$ $\displaystyle{\mathbb{P}}\left\\{\bigcap_{i\in
I_{1}}\\{\sqrt{1-\delta^{2}}{\widetilde{X}}_{i}^{\varepsilon}+\delta\xi\leq(\ell+s)i\varepsilon\\}\right\\}$
$\displaystyle\leq$ $\displaystyle{\mathbb{P}}\left\\{\bigcap_{i\in
I_{1}}\\{\sqrt{1-\delta^{2}}{\widetilde{X}}_{i}^{\varepsilon}\leq(\ell+s)i\varepsilon+h\varepsilon\\}\right\\}+{\mathbb{P}}\\{\delta\xi\leq-h\varepsilon\\}$
$\displaystyle=$ $\displaystyle\prod_{i\in
I_{1}}{\mathbb{P}}\left\\{X_{i}^{\varepsilon}\leq\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right\\}+{\mathbb{P}}\\{\xi\leq-h\varepsilon/\delta\\},$

where the last equality holds because ${\widetilde{X}}_{i}^{\varepsilon}$ are
independent copies of $X_{i}^{\varepsilon}$. We choose the level
$h=h(\delta,\varepsilon)$ so that

$\displaystyle h\varepsilon/\delta\to\infty,$ (15) $\displaystyle
h\varepsilon\cdot\sqrt{-2\ln\varepsilon}\to 0,$ (16)

which is possible under (13). It also follows from (16) that

$h/\tau=(h\varepsilon)/(\tau\varepsilon)\sim(h\varepsilon)/\sqrt{-2\ln\varepsilon}\to
0.$

Due to (15), the last term in our bound (14) is negligible. We check now that
the product converges to $\exp(-c\exp(-r))$. Taking the logarithm and passing
to the complementary events, we see that it is necessary to prove the
convergence

$\sum_{i\in
I_{1}}{\mathbb{P}}\left\\{X_{i}^{\varepsilon}\geq\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right\\}\to
c\exp(-r).$

By Pickands–Piterbarg lemma this is equivalent to

$c\,\ell\,\sum_{i\in
I_{1}}\left(\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right)^{2/\alpha-1}\exp\left(-\left(\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right)^{2}/2\right).$

We represent this expression as a difference of two sums

$c\,\ell\,\sum_{i:(\ell+s)i+\ell\geq\tau}\left(\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right)^{2/\alpha-1}\exp\left(-\left(\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right)^{2}/2\right)$
(17)

and

$c\,\ell\,\sum_{i:(\ell+s)i\geq\sigma}\left(\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right)^{2/\alpha-1}\exp\left(-\left(\frac{(\ell+s)i\varepsilon+h\varepsilon}{\sqrt{1-\delta^{2}}}\right)^{2}/2\right)$
(18)

The asymptotics of the first sum follows from Lemma 3 applied with parameters
$a=\frac{\ell+s}{\sqrt{1-\delta^{2}}}\sim\ell$ and
$\theta=\frac{\tau-\ell+h}{\sqrt{1-\delta^{2}}}\sim\tau$, where equations
(16), (8), (5) and (13) yield

$\displaystyle(\theta\varepsilon)^{2}$ $\displaystyle=$
$\displaystyle\frac{(\tau-\ell+h)^{2}\varepsilon^{2}}{1-\delta^{2}}=\frac{\tau^{2}\varepsilon^{2}}{1-\delta^{2}}+O(\tau(h+\ell)\varepsilon^{2})$
$\displaystyle=$
$\displaystyle\tau^{2}\varepsilon^{2}+\frac{\tau^{2}\varepsilon^{2}\delta^{2}}{1-\delta^{2}}+O(\tau(h+\ell)\varepsilon^{2})=\tau^{2}\varepsilon^{2}+o(1).$

By this relation and (9), Lemma 3 provides the following asymptotics for (17):

$c\,\ell\,\frac{1}{a\varepsilon}(\theta\varepsilon)^{2/\alpha-2}\exp\\{-(\theta\varepsilon)^{2}/2\\}\sim
c\,\ell\,\frac{1}{\ell\varepsilon}(\tau\varepsilon)^{2/\alpha-2}\exp\\{-(\tau\varepsilon)^{2}/2\\}\sim
ce^{-r}.$

Similarly, Lemma 3 applied with parameters
$a=\frac{\ell+s}{\sqrt{1-\delta^{2}}}\sim\ell$ and
$\theta=\frac{\sigma+h}{\sqrt{1-\delta^{2}}}\sim\sigma$ provides an
asymptotics for (18). Since
$(\theta\varepsilon)^{2}=(\sigma\varepsilon)^{2}+o(1)$, by using (10) we
obtain

$c\ell\frac{1}{a\varepsilon}(\theta\varepsilon)^{2/\alpha-2}\exp\\{-(\theta\varepsilon)^{2}/2\\}\sim
c\ell\frac{1}{\ell\varepsilon}(\sigma\varepsilon)^{2/\alpha-2}\exp\\{-(\sigma\varepsilon)^{2}/2\\}=o(1).$

Substraction of sums’ asymptotics implies the required upper bound for
$1-{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}$.

Lower bound.

In order to obtain an opposite bound for
$1-{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}$, we will introduce and compare two
more auxiliary processes $Y_{1}$, ${\widetilde{Y}}_{1}$. Let $\xi$ be an
auxiliary standard normal random variable independent with the process $Y$.
Let $Y_{1}(t):=Y(t)+\delta\xi$, $t\in\cup L_{i}$. Furthermore, let us consider
a sequence of independent standard Gaussian random variables $\xi_{i}$
independent of ${\widetilde{Y}}(t)$ and let

${\widetilde{Y}}_{1}(t):={\widetilde{Y}}(t)+\delta\xi_{i},\qquad t\in L_{i}.$

Then for all $t$ we have the equality of variances:
$\mathbb{E}\,Y_{1}(t)^{2}=\mathbb{E}\,{\widetilde{Y}}_{1}(t)=1+\delta^{2}$.
For covariances we have the following inequalities:

  * •

for $t_{1}$ and $t_{2}$ that belong to the same interval $L_{i}$ we have

$\mathbb{E}\,[Y_{1}(t_{1})Y_{1}(t_{2})]=\mathbb{E}\,[{\widetilde{Y}}_{1}(t_{1}){\widetilde{Y}}_{1}(t_{2})],$

  * •

for $t_{1}$ and $t_{2}$ that belong to different intervals $L_{i}$ and $L_{j}$
we have

$\displaystyle\mathbb{E}\,[Y_{1}(t_{1})Y_{1}(t_{2})]$ $\displaystyle=$
$\displaystyle\mathbb{E}\,[(Y(t_{1})+\delta\xi)(Y(t_{2})+\delta\xi)]=\mathbb{E}\,[Y(t_{1})Y(t_{2})]+\delta^{2}$
$\displaystyle\geq$ $\displaystyle
0=\mathbb{E}\,[{\widetilde{Y}}_{1}(t_{1}){\widetilde{Y}}_{1}(t_{2})].$

We choose $h=h(\delta,\varepsilon)$ as before, i.e. satisfying assumptions
(15) and (16).

Slepian inequality (11) yields

$\displaystyle{\mathbb{P}}\left\\{\bigcup_{i\in
I_{1}}\\{{\widetilde{X}}_{i}^{\varepsilon}+\delta\xi_{i}\geq(\ell+s)i\varepsilon-h\varepsilon\\}\right\\}={\mathbb{P}}\left\\{\bigcup_{i\in
I_{1}}\\{\max_{t\in
L_{i}}{\widetilde{Y}}_{1}(t)\geq(\ell+s)i\varepsilon-h\varepsilon\\}\right\\}$
$\displaystyle\geq$ $\displaystyle{\mathbb{P}}\left\\{\bigcup_{i\in
I_{1}}\\{\max_{t\in
L_{i}}Y_{1}(t)\geq(\ell+s)i\varepsilon-h\varepsilon\\}\right\\}={\mathbb{P}}\left\\{\bigcup_{i\in
I_{1}}\\{X_{i}^{\varepsilon}+\delta\xi\geq(\ell+s)i\varepsilon-h\varepsilon\\}\right\\}.$

By passing to the complementary events, we obtain

$\displaystyle{\mathbb{P}}\left\\{\bigcap_{i\in
I_{1}}\\{X_{i}^{\varepsilon}+\delta\xi\leq(\ell+s)i\varepsilon-h\varepsilon\\}\right\\}\geq{\mathbb{P}}\left\\{\bigcap_{i\in
I_{1}}\\{{\widetilde{X}}_{i}^{\varepsilon}+\delta\xi_{i}\leq(\ell+s)i\varepsilon-h\varepsilon\\}\right\\}$
$\displaystyle=$ $\displaystyle\prod_{i\in
I_{1}}{\mathbb{P}}\left\\{{\widetilde{X}}_{i}^{\varepsilon}+\delta\xi_{i}\leq(\ell+s)i\varepsilon-h\varepsilon\right\\}=\prod_{i\in
I_{1}}{\mathbb{P}}\left\\{X_{i}^{\varepsilon}+\delta\xi\leq(\ell+s)i\varepsilon-h\varepsilon\right\\}.$

Further, we apply an elementary bound

$\displaystyle 1-{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}$ $\displaystyle=$
$\displaystyle{\mathbb{P}}\left\\{\bigcap_{i\in
I_{1}}\\{X_{i}^{\varepsilon}\leq(\ell+s)i\varepsilon\\}\right\\}$
$\displaystyle\geq$ $\displaystyle{\mathbb{P}}\left\\{\bigcap_{i\in
I_{1}}\\{X_{i}^{\varepsilon}+\delta\xi\leq(\ell+s)i\varepsilon-h\varepsilon\\}\right\\}-{\mathbb{P}}\\{\delta\xi\leq-h\varepsilon\\}$
$\displaystyle\geq$ $\displaystyle\prod_{i\in
I_{1}}{\mathbb{P}}\left\\{X_{i}^{\varepsilon}+\delta\xi\leq(\ell+s)i\varepsilon-h\varepsilon\right\\}-{\mathbb{P}}\\{\delta\xi\leq-h\varepsilon\\}.$

Under assumption (15), we have
${\mathbb{P}}\\{\delta\xi\leq-h\varepsilon\\}\to 0$. It remains to prove that
the product is greater than $\exp(-c\exp(-r))(1+o(1))$. Taking the logarithm
and passing to the complementary events, we see that it is necessary to prove
the bound

$\sum_{i\in
I_{1}}{\mathbb{P}}\\{X_{i}^{\varepsilon}+\delta\xi\geq(\ell+s)i\varepsilon-h\varepsilon\\}\leq
c\exp(-r)(1+o(1)).$

We start with the estimate

$\displaystyle\sum_{i\in
I_{1}}{\mathbb{P}}\\{X_{i}^{\varepsilon}+\delta\xi\geq(\ell+s)i\varepsilon-h\varepsilon\\}$
(19) $\displaystyle\leq$ $\displaystyle\sum_{i\in
I_{1}}\big{[}{\mathbb{P}}\\{X_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon-2h\varepsilon\\}+{\mathbb{P}}\\{\delta\xi>h\varepsilon\\}\big{]}$
$\displaystyle\leq$
$\displaystyle\sum_{i:(\ell+s)i+\ell\geq\tau}{\mathbb{P}}\\{X_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon-2h\varepsilon\\}+N_{1}{\mathbb{P}}\\{\delta\xi>h\varepsilon\\},$

where $N_{1}$ denotes the number of elements in the set $I_{1}$; it has
asymptotics

$N_{1}\sim\frac{\sigma-\tau}{\ell+s}=\frac{(R-r)B_{\varepsilon}}{\ell+s}\sim\frac{R}{\varepsilon\sqrt{-2\ln\varepsilon}\,\ell}.$

For the sum in (19) Pickands–Piterbarg lemma provides an equivalent expression

$c\,\ell\,\sum_{i\in
I_{1}}\left((\ell+s)i\varepsilon-2h\varepsilon\right)^{2/\alpha-1}\exp\left(-\left((\ell+s)i\varepsilon-2h\varepsilon\right)^{2}/2\right).$
(20)

Next, Lemma 3 applied with parameters $a=\ell+s$, $b=-2h$,
$\theta=\tau-\ell-2h$ yields an asymptotics for the latter sum. Here, as in
the derivation of the upper bound we have $a\sim\ell$, $\theta\sim\tau$,
$(\theta\varepsilon)^{2}=(\tau\varepsilon)^{2}+o(1)$. By combining the result
of Lemma 3 with (9), we obtain

$\frac{c\,\ell}{a\varepsilon}(\theta\varepsilon)^{2/\alpha-2}\exp\\{-(\theta\varepsilon)^{2}/2\\}\sim\frac{c}{\varepsilon}(\tau\varepsilon)^{2/\alpha-2}\exp\\{-(\tau\varepsilon)^{2}/2\\}\sim
ce^{-r}.$

This means that

$\sum_{i:(\ell+s)i+\ell\geq\tau}{\mathbb{P}}\\{X_{i}^{\varepsilon}\geq(\ell+s)i\varepsilon-2h\varepsilon\\}=c\,e^{-r}(1+o(1)).$

It remains to estimate the last term in (19). To this aim, we have to specify
the choice of parameters $\ell$ and $R$.

Since ${\mathbb{P}}(\delta\xi>h\varepsilon)\to 0$, we may chose
$\ell=\ell(\varepsilon)$, although satisfying (5), but still such that

$\frac{{\mathbb{P}}(\delta\xi>h\varepsilon)}{\ell\varepsilon\sqrt{-\ln\varepsilon}}\to
0.$

Then we may choose $R=R(\varepsilon)$ tending to infinity so slowly that

$N_{1}\,{\mathbb{P}}\\{\delta\xi>h\varepsilon\\}\sim\frac{R\,{\mathbb{P}}(\delta\xi>h\varepsilon)}{\ell\varepsilon\sqrt{-2\ln\varepsilon}}\to
0.$

By summing up the estimates for the terms of (19), we arrive at the required
lower estimate for $1-{\mathbb{P}}\\{{\mathcal{E}}_{1}\\}$.

###  2.2 Proof of Lemma 3

The monotone decay of the function $x\mapsto x^{2/\alpha-1}\exp\\{-x^{2}/2\\}$
at large $x$ yields the following two bounds

$[(ai+b)\varepsilon]^{2/\alpha-1}\exp\\{-[(ai+b)\varepsilon]^{2}/2\\}\leq\frac{1}{a\varepsilon}\int_{(a(i-1)+b)\varepsilon}^{(ai+b)\varepsilon}x^{2/\alpha-1}\exp\\{-x^{2}/2\\}dx,$

$[(ai+b)\varepsilon]^{2/\alpha-1}\exp\\{-[(ai+b)\varepsilon]^{2}/2\\}\geq\frac{1}{a\varepsilon}\int_{(ai+b)\varepsilon}^{(a(i+1)+b)\varepsilon}x^{2/\alpha-1}\exp\\{-x^{2}/2\\}dx.$

By summing up over all considered $i$ we infer that the sum under
consideration is contained between two integrals

$\frac{1}{a\varepsilon}\int_{(\theta-a)\varepsilon}^{\infty}x^{2/\alpha-1}\exp\\{-x^{2}/2\\}dx\;\;\mbox{
and}\;\;\frac{1}{a\varepsilon}\int_{(\theta+a)\varepsilon}^{\infty}x^{2/\alpha-1}\exp\\{-x^{2}/2\\}dx.$

Furthermore, under our assumptions on $\theta$ and $a$ it is true that

$\displaystyle\frac{1}{a\varepsilon}\int_{(\theta-a)\varepsilon}^{\infty}x^{2/\alpha-1}\exp\\{-x^{2}/2\\}dx$
$\displaystyle\sim$
$\displaystyle\frac{1}{a\varepsilon}[(\theta-a)\varepsilon]^{2/\alpha-2}\exp\\{-[(\theta-a)\varepsilon]^{2}/2\\}$
$\displaystyle\sim$
$\displaystyle\frac{1}{a\varepsilon}(\theta\varepsilon)^{2/\alpha-2}\exp\\{-(\theta\varepsilon)^{2}/2\\}$

and

$\frac{1}{a\varepsilon}\int_{(\theta+a)\varepsilon}^{\infty}x^{2/\alpha-1}\exp\\{-x^{2}/2\\}dx\sim\frac{1}{a\varepsilon}(\theta\varepsilon)^{2/\alpha-2}\exp\\{-(\theta\varepsilon)^{2}/2\\},$

and the required estimate follows.

## References

  * [1]
  * [2] F.Aurzada, V.Betz, M.Lifshits, Breaking a chain of interacting Brownian particles. Preprint https://arxiv.org/abs/1912.05168.
  * [3] F.Aurzada, V.Betz, M.Lifshits, Universal break law for chains of Brownian particles with nearest neighbour interaction. Preprint www.arxiv.org/abs/2010.07706.
  * [4] K.Debicki, P.Liu, The time of ultimate recovery in Gaussian risk model. Extremes, 22(3), 499-521, 2019. https://arxiv.org/abs/1801.02469.
  * [5] J.Hüsler, Y.Zhang, On first and last ruin times of Gaussian processes. Statist. Probab. Lett., 78(10):1230–1235, 2008.
  * [6] M.Lifshits, Gaussian random functions, Kluwer, Dordrecht, 1995.
  * [7] Ch.Paroissin, L.Rabehasaina, First and last passage times of spectrally positive Lévy processes with application to reliability. Methodology and Computing in Applied Probability, 17, 351–372, 2015.
  * [8] J.Pickands III, Asymptotic properties of the maximum in a stationary Gaussian process, Trans. Amer. Math. Soc. 145 (1969), 75–86.
  * [9] V.I. Piterbarg, Twenty lectures on Gaussian processes. Atlantic Financial Press, 2015.
  * [10]


# When to Go, and When to Explore:
The Benefit of Post-Exploration in Intrinsic Motivation

Zhao Yang, Thomas M. Moerland, Mike Preuss and Aske Plaat
Leiden Institute of Advanced Computer Science
Leiden University, The Netherlands

###### Abstract

Go-Explore achieved breakthrough performance on challenging reinforcement
learning (RL) tasks with sparse rewards. The key insight of Go-Explore was
that successful exploration requires an agent to first return to an
interesting state (‘Go’), and only then explore into unknown terrain
(‘Explore’). We refer to such exploration after a goal is reached as ‘post-
exploration’. In this paper we present a systematic study of post-exploration,
answering open questions that the Go-Explore paper did not answer yet. First,
we study the isolated potential of post-exploration, by turning it on and off
within the same algorithm. Subsequently, we introduce new methodology to
adaptively decide when to post-explore and for how long to post-explore.
Experiments on a range of MiniGrid environments show that post-exploration
indeed boosts performance (with a bigger impact than tuning regular
exploration parameters), and this effect is further enhanced by adaptively
deciding when and for how long to post-explore. In short, our work identifies
adaptive post-exploration as a promising direction for RL exploration
research.

##  1 Introduction

Go-Explore (Ecoffet et al., 2021) achieved breakthrough performance on
challenging reinforcement learning (RL) tasks with sparse rewards, most
notably achieving state-of-the-art, ‘super-human’ performance on Montezuma’s
Revenge, a long-standing challenge in the field. The key insight behind Go-
Explore is that proper exploration should be structured in two phases: an
agent should first attempt to get back to a previously visited, interesting
state (‘Go’), and only then explore into new, unknown terrain (‘Explore’).
Thereby, the agent gradually expands its knowledge base, an approach that is
visualized in Fig.1. We propose to call such exploration after the agent
reached a goal post-exploration (to contrast it with standard exploration).

There are actually two variants of Go-Explore in the original paper: one in
which we directly reset the agent to an interesting goal (restore-based Go-
Explore), and one in which the agent has to act to get back to the proposed
goal (policy-based Go-Explore). In this work, we focus on the latter approach,
which is technically part of the literature on intrinsic motivation, in
particular intrinsically motivated goal exploration processes (IMGEP) (Colas
et al., 2020). Note that post-exploration does not require any changes to the
IMGEP framework itself, and can therefore be easily integrated into other
existing work in this direction.

While Go-Explore gave a strong indication of the potential of post-
exploration, it did not structurally investigate the benefit and possible
extensions of the approach. First of all, Go-Explore was compare to other
baseline algorithms, but post-exploration itself was never switched on and off
in the same algorithm. Thereby, the isolated performance gain of post-
exploration remains unclear. Second, it also remains unclear when we should
post-explore (Go-Explore does this at every trial) and for how long we should
post-explore (Go-Explore does this for a fixed number of steps).

Therefore, the present paper studies adaptive post-exploration. In particular,
we make the decision to post-explore a function of the novelty of the reached
goal, and the depth of post-exploration a function of the length of the goal-
reaching part of the episode. Experiments in a range of MiniGrid tasks show
that post-exploration provides a strong isolated benefit over standard IMGEP
algorithms, which can be further enhanced by adaptively deciding when and for
how long to post-explore. As a smaller contribution, we also cast Go-Explore
into the IMGEP framework, and show how it can be combined with hindsight
experience replay (HER) (Andrychowicz et al., 2017) to make more efficient use
of the observed data. In short, our work presents a systematic study of post-
exploration, and identifies adaptive post-exploration as a promising direction
for future RL exploration research.

Figure 1: Conceptual illustration of post-exploration. Each box displays the
entire state space, where green and red denote the (currently) explored and
unexplored regions, respectively. Left: Goal-based exploration without post-
exploration. The top graph shows the agent reaching a current goal, after
which the episode is terminated (or a next goal in the green area is chosen).
Therefore, at the next episode (bottom) the agent will again explore within
the known (green) region), often leaving the unknown (red) area untouched.
Right: Goal-based exploration with post-exploration. The top figure shows the
agent reaching a particular goal, from which the agent now post-explores for
several steps (dashed lines). Thereby, the known area (green) is pushed
outwards. On a next episode, the agent may now also select a goal in the
expanded region, gradually expanding its knowledge of the reachable state
space.

##  2 Related Work

Go-Explore is a variant of a intrinsically motivated goal exploration
processes (IMGEP) (surveyed by Colas et al. (2020)) which generally consists
of three phases: 1) defining/learning a goal space, 2) sampling an interesting
goal from this space, and 3) getting to the sampled goal based on information
from previous episodes. Regarding the first step, Go-Explore (Ecoffet et al.,
2021) uses a predefined goal space based on a downscaling of the state space.
Other IMGEP approaches, like Goal-GAN (Florensa et al., 2018) use a generative
adversarial network to learn a goal space of appropriate difficulty. As an
alternative, AMIGo (Campero et al., 2021) trains a teacher to propose goals
for a student to reach. In this work, we largely follow the ideas of Go-
Explore, and use a predefined goal space, since our research questions are
directed at the effects of post-exploration.

After a goal space is determined, we next need a sampling strategy to set the
next goal. Example strategies to select the next goal include novelty (Ecoffet
et al., 2021; Pitis et al., 2020), learning progress (Colas et al., 2019;
Portelas et al., 2020), diversity (Pong et al., 2019; Warde-Farley et al.,
2019), and uniform sampling (Eysenbach et al., 2018). In this work, we follow
the last approach, since it 1) gave good performance and 2) puts pressure on
the agent to adaptively decide when to post-explore.

In the third IMGEP phase, we need to get back to the proposed goal. One
variant of Go-Explore simply resets the agent to the desired goal, but this
requires an environment which can be set to an arbitrary state. Instead, we
follow the more generic ‘policy-based Go-Explore’ approach, which uses a goal-
conditioned policy network to get back to a goal. The concept of goal-
conditioning, which was introduced by Schaul et al. (2015), is also the common
approach in IMGEP approaches. A well-known addition to goal-based RL
approaches is hindsight experience replay (Andrychowicz et al., 2017), which
allows the agent to make more efficient use of the data through counterfactual
goal relabelling. Although Go-Explore did not use hindsight in their work, we
do include it as an extension in our approach.

After we manage to reach a goal, most IMGEP literature samples a new goal and
either resets the episode or continues from the reached state. The main
contribution of Go-Explore was the introduction of post-exploration, in which
case we temporarily postpone selection of a new goal (Tab. 1). While post-
exploration is a new phenomenon in reinforcement learning literature, it is a
common feature of most planning algorithms, where we for example select a
particular node on the frontier, go there first, and then unfold the search
tree into unknown terrain.

Table 1: Overview of moment of exploration in IMGEP papers. Most IMGEP approaches, like Goal-GAN (Florensa et al., 2018), CURIOUS (Colas et al., 2019), DIAYN (Pong et al., 2019), and AMIGo (Campero et al., 2021), only explore during goal reaching. Restore-based Go-Explore, which directly resets to a goal, only explore after the goal is reached. Our work, similar to policy-based Go-explore, explores both during goal-reaching and after goal reaching. Approach | Exploration during goal reaching | Post-exploration
---|---|---
IMGEP | ✓ | ✗
Restore-based Go-Explore | ✗ | ✓
Policy-based Go-Explore + this paper | ✓ | ✓

##  3 Background

We adopt a Markov Decision Processes (MDPs) formulation defined as the tuple
$M=(\mathcal{S},\mathcal{A},P,R,\gamma)$ (Sutton & Barto, 2018). Here,
$\mathcal{S}$ is a set of states, $\mathcal{A}$ is a set of actions the agent
can take, $P$ specifies the transition function of the environment, and $R$ is
the reward function. At timestep $t$, the agent observes state
$s_{t}\in\mathcal{S}$, selects an action $a_{t}\in\mathcal{A}$, after which
the environment returns a next state $s_{t+1}\sim P(\cdot|s_{t},a_{t})$ and
associated reward $r_{t}=R(s_{t},a_{t},s_{t+1})$. We act in the MDP according
to a policy $\pi(a|s)$, which maps a state to a distribution over actions.
When we unroll the policy and environment for $T$ steps, define the cumulative
reward (return) of the resulting trace as $\sum^{T}_{k=0}\gamma^{k}\cdot
r_{t+k+1}$, where $\gamma\in[0,1]$ denotes a discount factor. Define the
state-action value $Q^{\pi}(s,a)$ as the expected cumulative reward under some
policy $\pi$ when we start from state $s$ and action $a$, i.e.,

$Q^{\pi}(s,a)=\mathbb{E}_{\pi,P}\Big{[}\sum^{T}_{k=0}\gamma^{k}\cdot
r_{t+k}|s_{t}=s,a_{t}=a\Big{]}$ (1)

Our goal is to find the optimal state-action value function
$Q^{*}(s,a)=\max_{\pi}Q^{\pi}(s,a)$, from which we may at each state derive
the optimal policy $\pi^{*}(s)=\operatorname*{arg\,max}_{a}Q^{*}(s,a)$. A
well-known RL approach to solve this problem is Q-learning (Watkins & Dayan,
1992). Tabular Q-learning maintains a table of Q-value estimates
$\hat{Q}(s,a)$, collects transition tuples $(s_{t},a_{t},r_{t},s_{t+1})$, and
subsequently updates the tabular estimates according to

$\hat{Q}(s_{t},a_{t})\leftarrow\hat{Q}(s_{t},a_{t})+\alpha\cdot[r_{t}+\gamma\cdot\max_{a}\hat{Q}(s_{t+1},a)-\hat{Q}(s_{t},a_{t})]$
(2)

where $\alpha\in[0,1]$ denotes a learning rate. Under a policy that is greedy
in the limit with infinite exploration (GLIE) this algorithm converges on the
optimal value function (Watkins & Dayan, 1992).

##  4 Methods

We will first describe how we cast Go-Explore into the general IMGEP framework
(Sec. 4.1), and subsequently introduce our new methodology to adaptively
decide when and for how long to post-explore (Sec. 4.2).

###  4.1 IMGEP

Our work is based on the IMGEP framework shown in Appendix A.4, Alg 2. Since
this paper attempts to study the fundamental benefit of post-exploration, we
try to simplify the problem setting as much as possible, to avoid interference
with other issues. We therefore choose to study tabular RL problems, in which
we define the goal space as the set of states we have observed so far. The
goal space $G$ is initialized by executing a random policy for one episode,
while new states in future episodes augment the set.

For goal sampling we take uniform samples from the goal space, as for example
also used by Eysenbach et al. (2018). This approach empirically provided best
performance, and also increases the impact of the decision when to post-
explore. Note that we could also use other methods, both for defining the goal
space and for sampling new goals (for example based on novelty or learning
progress), but these choices allow us to focus on the benefit of post-
exploration.

To get (back) to a selected goal, we train a tabular goal-conditioned
Q-learning agent. The update rule of the value function is similar to the
standard Q-learning update shown in Eq. 2, except that $Q$ is conditioned on
the selected goal $g$, i.e., $Q(s,a,g)$. Agents are trained on the goal-
conditioned reward function $R_{g}$, which is a one-hot indicator that fires
when the agent manages to reach the specified goal

$R_{g}(s,a,s^{\prime})=\mathbbm{1}_{s^{\prime}=g},$ (3)

Note that different goal-conditioned rewards functions, different back-up
strategies and/or the use of function approximation are of course possible as
well.

###  4.2 Post-exploration

The general concept of post-exploration was already introduced in Figure 1.
The main benefit of this approach is that it increases our chance to step into
new, unknown terrain. Based on this intuition, we will now discuss new
methodology to adaptively decide when to post-explore and for how long to post
explore.

#### When to post-explore

As is directly visible from Figure 1, post-exploration is likely most
beneficial when performed from a state at the border of our currently explored
region. After all, when we perform post-exploration from a state in the middle
of the known region, it will likely only waste resources (and not discover
anything new), while post-exploration from the border does have much
potential. We propose to use the novelty of the particular state as a measure
of its location in the explored region: when a state is only visited a few
times, then it is more likely to reside at the border of our explored region
(although other measures, like a connectivity graph of the visited states, is
also possible).

We therefore propose to make the probability to post-explore in a particular
reached goal $g$ a function of the number of times we have visited that
particular goal. We therefore track the number of times we visited a
particular goal $n(g)$, and specify the probability to post-explore (when to
post-explore) as

$p_{pe}(g)=\left(\frac{1}{n(g)}\right)^{\beta},\beta\in[0,\infty).$ (4)

Here, $\beta$ is a temperature parameter that allow us to scale the amount of
post-exploration. When $\beta$ is 0, the agent will always post-explore after
reaching the goal, while $\beta\to\infty$ ensures the agent will never post-
explore.

#### How long to post-explore

We will denote the number of steps an agent post-explores after reaching a
goal as $n_{pe}$. While Go-Explore always explored for a fixed number of steps
($n_{pe}$ fixed), we hypothesize that the duration of post-exploration may
also influence performance. Intuitively, the longer the path the agent took to
reach the given goal, the more time it may want to spend in post-exploration
(since it is expensive to get back there). We therefore propose to let the
agent post-explore for a percentage $p_{pe}$ of the length of the whole
trajectory:

$n_{pe}=p_{pe}\cdot n_{ep},$ (5)

where $n_{ep}$ is the length of the goal-reaching part of the episode, and
$p_{pe}$ is a hyperparameter of our algorithm.

#### Hindsight relabelling

The agent in principle only observes a non-zero reward when it successfully
reaches the goal, which may not happen at every attempt. We may improve sample
efficiency (make more efficient use of each observed trajectory) through
hindsight relabelling (Andrychowicz et al., 2017). With hindsight, we imagine
states in our observed trajectory were the goals we actually attempted to
reach, which allows us to extract additional information from them (‘if my
goal had been to get to this state, then the previous action sequence would
have been a successful attempt’). Pseudocode for hinsight relabelling is
provided in Appendix A.4, Alg. 1. In particular, we choose to always relabel
50% of the entire trajectory (goal reaching plus post-exploration), i.e., half
of the states in each trajectory are imagined as if they were the goal of that
episode. We choose to always relabel the full post-exploration part, because
it likely contains the most interesting information, and randomly sample the
remaining relabelling budget from the part of the episode before the goal was
reached.

Figure 2: FourRooms, LavaCrossing and LavaGap. The latter two environments are
procedurally generated based on environment seeds.

##  5 Experimental Setup

We test our work on three MiniGrid environments (Chevalier-Boisvert et al.,
2018), visualized in Fig. 2. The MiniGrid-FourRooms-v0 only has a single lay-
out, while the MiniGrid-LavaCrossingS11N5-v0 and MiniGrid-LavaGapS7-v0
environments are procedurally generated. Results on these latter two
environments are averaged over 10 seeds, i.e., 10 independently drawn
instances of the task. For evaluation, we test the ability of the agent to
reach every possible state in the state space. This checks to what extent the
goal-conditioned value function is able to reach a given goal, when we execute
the greedy policy (turn exploration off). All our results report the total
number of environment steps on the x-axis. Therefore, since an episode with
post-exploration takes longer, it will also contribute more steps to the
x-axis (i.e., we report performance against the total number of unique
environment calls). Curves display mean performance over time, including the
standard error over 5 repetitions for each experiment. For all experiments, we
set $\epsilon=0.1$ (exploration during goal reaching), $\epsilon_{pe}=1.0$
(full exploration during post-exploration), $\beta=0$, and $p_{pe}=0.5$,
unless otherwise noted. Full details on hyperparameters can be found in
Appendix. A.3.

##  6 Results

We split our results up into five research questions: 1) does post-exploration
work in general, 2) to what extent should the agent also explore during goal
reaching, 3) when should we post-explore, 4) for how long should we post-
explore, and 5) is post-exploring also beneficial in continuing tasks, where
we sample a next goal without resetting the agent to an initial state. Each
research questions will be discussed below.

Figure 3: IMGEP agents with (blue) and without (orange) post-exploration.
Left: Performance on FourRooms, with results average over three different
values of $\epsilon$ ($0,0.1,0.3$). Middle: Performance on LavaCrossing,
averaged over 10 different environment seeds. Right: Performance in LavaGap,
averaged over 10 different environment seeds. Overall, agents with post-
exploration outperform agents without post-exploration.

###  6.1 Does post-exploration work?

Fig. 3 compares an IMGEP agent with post-exploration to an IMGEP agent without
exploration in the three test environments. On all three environments the
agent with post-exploration outperforms the baseline agent significantly (on
its average ability to reach an arbitrary goal in the state space).

A graphical illustration of the effect of post-exploration is provided in Fig.
4. Part a shows a characteristic trace for an agent attempting to reach the
green square without post-exploration, while b shows a trace for an agent with
post-exploration. In a, we see that the agent is able to reach the goal
square, but exploration subsequently stops, and the agent did not learn
anything new. In part b, the agent with post-exploration subsequently manages
to enter the next room. This graph therefore gives a practical illustration of
our intuition from Fig. 1.

To further illustrate this effect, Fig. 4 c and d show a visitation heat map
for the agent after 200k training steps, without post exploration (c) and with
post-exploration (d). The agent with post-exploration (c) has primarily
explored goals around the start region (in the bottom-right chamber). The two
rooms next to the starting room have also been visited, but the agent barely
managed to get into the top-left room. In contrast, the agent with post-
exploration (d) has extensively visited the first three rooms, while the
coverage boundary has also been pushed into the final room already. This
effect translates to the increased goal-reaching performance of post-
exploration visible in Fig. 3.

###  6.2 When should the agent explore?

Exploration and post-exploration play different roles in the IMGEP approach.
Standard exploration (during goal reaching) may help improve our ability to
reach a particular goal, while post-exploration especially helps to improve
our ability to reach novel terrain. We therefore investigate whether both
types of exploration should be jointly present, and to what extent they
contribute to overall performance in our test environments.

Fig. 5, left, shows experiments on the FourRooms environments with (blue) and
without (orange) post-exploration, where we also vary the amount of
exploration ($\epsilon$ of an $\epsilon$-greedy policy) during goal reaching.
$\epsilon=0$ implies there is no exploration at all during goal reaching,
while $\epsilon=1$ implies full exploration (and therefore no exploitation at
all during goal reaching).

Figure 4: Comparison of characteristic traces (a,b) and coverage (c,d) for
agents without post-exploration (a,c) and with post-exploration (b,d). Colour
bars indicate the number of visitations, green square indicates the selected
goal in a particular episode. (a): Standard exploration towards goal without
post-exploration. (b): With post-exploration the agent manages to reach the
next room. (c): Coverage after 200k training steps without post-exploration.
(d): Coverage after 200k training steps with post-exploration. The boundary of
the coverage with post-exploration clearly lies further ahead.

Figure 5: Left: Performance of agents with different exploration factors
$\epsilon$ with and without Post-Exploration (PE) in the FourRooms
environment. Adding slight exploration ($\epsilon=(0.1,0.3)$) can further
improve the performance. Adding fully random exploration will lead to similar
results with ones without Post-Exploration. Right: Performance of agents with
different $\beta$ in the FourRooms environment. $\beta=0$ is always Post-
Exploration. Selective Post-Exploration ($\beta=(0.01,0.05)$) works better
than full Post-Exploration. Too aggressive $\beta$ will hurt the performance.

In general, we see that post-exploration has a much stronger effect on
performance than the amount of exploration during goal reaching (the quantity
that is typically tuned in (goal-based) RL experiments). Only when we set
$\epsilon=1.0$ (full exploration during goal reaching) do we lose performance,
which of course makes sense, since the agent then hardly manages to get back
to the selected goal. Similar results on other environments are shown in
Appendix. A.

###  6.3 When should the agent post-explore?

We next investigate when to actually post-explore, i.e., whether it is
beneficial to make the probability of post-exploration dependent on the
novelty of a reached goal (Eq. 4). Results of these experiments on the
FourRooms environment are shown in Fig. 5, right. For clarity, $\beta=0$ means
that the agent will always post-explore, while a higher value of $\beta$ will
decay the probability of post-exploration with more visits, an effect that
becomes stronger the further $\beta$ increases.

We see that selective post-exploration ($\beta=0.01$ and $\beta=0.05$)
slightly outperforms full post-exploration ($\beta=0$). This selective post-
exploration decides to not post-explore when it is probably not beneficial,
and therefore saves it samples for a next episode. However, we should clearly
not overdo it, as a faster decrease in post-exploration probability
($\beta=1$) clearly hurts performance. Note that the curve of this agent
becomes almost flat near the end, probably because the agent does not post-
explore anymore at all. Additional results on other environments are available
in Appendix. A.

###  6.4 How long should the agent post-explore?

We next investigate whether the duration of post-exploration should be a fixed
number (like in Go-Explore), or should be a function of the duration of goal-
reaching (Eq. 5). In the former case we report a fixed $n_{pe}$ (regardless of
the length of the trajectory), while in the latter case we report the used
proportion $p_{pe}$.

Fig. 6, left and middle, show the results of these experiments on FourRooms
for different values of $n_{pe}$ and $p_{pe}$. The left part of the graph
shows the learning curves, in which we see that $n_{pe}=20$ and $p_{pe}=0.8$
achieve best performance, suggesting that both methods are on par. However,
the middle of Fig. 6, shows the total number of post-exploration steps (top)
and total number of relabelling steps (bottom) in each setting. This graph
shows that $p_{pe}=0.8$ uses roughly as many post-exploration steps as
$n_{pe}=15$, and way less than $n_{pe}=20$. Therefore, the proportional post-
exploration method ($p_{pe}$) does seem to be more effective at utilizing the
post-exploration data.

###  6.5 Does post-exploration work in continuing environments?

Similar to Go-Explore, we investigated post-exploration primarily in the
episodic setting (where we reset an agent after a goal is reached, or after
post-exploration has completed). However, many specifications of goal-based RL
assume a continuing task, in which there are no full resets, but the agent
simply attempts to reach the next sampled goal from the current state. This
does give the standard agent (without post-exploration) the ability to make
additional steps after reaching a goal, but it will do so in the direction of
an already set goal (which may direct it back into known territory, instead of
into new terrain). Fig. 6, right, shows results of these experiments. Again,
post-exploration outperforms the agent without post-exploration, although the
effect is less pronounced compared to the episodic setting. This confirms our
hypothesis that setting a next goal is indeed not the same as post-
exploration, since the agent will likely just move back into known territory.

Figure 6: Left: Two different ways for Post-Exploration in FourRooms
Environment. Left: performance of agents with different Post-Exploration
methods. Blues are post-explore with percentage of the whole trajectory
($p_{pe}$) while oranges are post-explore certain steps ($n_{pe}$). Middle:
the top sub figure is total steps that agent post-explores with different
Post-Exploration methods; the bottom sub figure is the total steps of
hindsight relabelling. Although we keep relabelling steps and Post-Exploration
steps similar for two methods, the percentage one performs better. For
example, $p_{pe}=0.5$ and $n_{pe}=10$. Right: Performance of agents with and
without post-exploration in the non-episodic continuing FourRooms environment.
Agents with post-exploration still outperform agents without post-exploration,
likely because the next goal directs agents back into known territory.

##  7 Conclusion and Future Work

An intrinsically motivated agent not only needs to set interesting goals and
be able to reach them, but should also decide whether to continue exploration
from the reached goal (‘post-exploration’). In this work, we systematically
investigated the benefit of post-exploration in the IMGEP framework.
Experiments in several MiniGrid environments show that post-exploration is
beneficial, and may even have a stronger effect on performance than tuning
exploration during goal reaching (which is usually tuned in RL experiments).
According to our intuition, agent with post-exploration gradually push the
boundaries of their known region outwards, which allows them to reach a
greater diversity of goals. Moreover, we find that adaptive post-exploration,
where we adjust when and for how long we post-explore based on previous data,
may further enhance this benefit. Finally, the benefit of post-exploration is
retained on continuing tasks, which shows that simply setting a next goal is
not the same as proper post-exploration.

The current paper studied post-exploration in the tabular setting, to better
understand its basic properties. In future work, post-exploration may be
scaled up to higher-dimensional IMGEP problems which require function
approximation, a learned goal space, and more complex goal sampling
strategies. Moreover, our current implementation uses random post-exploration,
which turned out to already work reasonably well. Another interesting
direction for future work is to post-explore in a smarter way, for example by
trying to set goals outside the known area, which was not possible in the
tabular setting, but would be possible when we use function approximation.
Altogether, post-exploration seems a promising direction for future RL
exploration research.

## References

  * Andrychowicz et al. (2017) Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba.  Hindsight experience replay.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Campero et al. (2021) Andres Campero, Roberta Raileanu, Heinrich Kuttler, Joshua B. Tenenbaum, Tim Rocktäschel, and Edward Grefenstette.  Learning with amigo: Adversarially motivated intrinsic goals.  In _International Conference on Learning Representations_ , 2021.
  * Chevalier-Boisvert et al. (2018) Maxime Chevalier-Boisvert, Lucas Willems, and Suman Pal.  Minimalistic gridworld environment for openai gym.  https://github.com/maximecb/gym-minigrid, 2018.
  * Colas et al. (2019) Cédric Colas, Pierre Fournier, Mohamed Chetouani, Olivier Sigaud, and Pierre-Yves Oudeyer.  Curious: intrinsically motivated modular multi-goal reinforcement learning.  In _International conference on machine learning_ , pp. 1331–1340. PMLR, 2019.
  * Colas et al. (2020) Cédric Colas, Tristan Karch, Olivier Sigaud, and Pierre-Yves Oudeyer.  Intrinsically motivated goal-conditioned reinforcement learning: a short survey.  _arXiv preprint arXiv:2012.09830_ , 2020.
  * Ecoffet et al. (2021) Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune.  First return, then explore.  _Nature_ , 590(7847):580–586, 2021.
  * Eysenbach et al. (2018) Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine.  Diversity is all you need: Learning diverse skills without a reward function.  2018\.
  * Florensa et al. (2018) Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel.  Automatic goal generation for reinforcement learning agents.  In Jennifer Dy and Andreas Krause (eds.), _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pp. 1515–1528. PMLR, 10–15 Jul 2018.
  * Pitis et al. (2020) Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba.  Maximum entropy gain exploration for long horizon multi-goal reinforcement learning.  In _International Conference on Machine Learning_ , pp. 7750–7761. PMLR, 2020.
  * Pong et al. (2019) Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine.  Skew-fit: State-covering self-supervised reinforcement learning.  _arXiv preprint arXiv:1903.03698_ , 2019.
  * Portelas et al. (2020) Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre-Yves Oudeyer.  Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments.  In _Conference on Robot Learning_ , pp. 835–853. PMLR, 2020.
  * Schaul et al. (2015) Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver.  Universal value function approximators.  In _International conference on machine learning_ , pp. 1312–1320. PMLR, 2015.
  * Sutton & Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Warde-Farley et al. (2019) David Warde-Farley, Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih.  Unsupervised control through non-parametric discriminative rewards.  In _International Conference on Learning Representations_ , 2019.
  * Watkins & Dayan (1992) Christopher JCH Watkins and Peter Dayan.  Q-learning.  _Machine learning_ , 8(3):279–292, 1992.

##  Appendix A Appendix

###  A.1 More results on LavaCrossing

Figure 7: Performance of agents with Post-Exploration with different
exploration factor $\epsilon$ in LavaCrossing. Adding exploration
($\epsilon=0.1$) during goal reaching can improve the performance. Each
experiment in LavaCrossing is averaged over 10 different environment seeds and
5 repetitions.

Figure 8: Left: Performance of agents with different $\beta$. The selective
Post-Exploration ($\beta=0.01$) slightly outperform full Post-Exploration
($\beta=0$). Right: Performance of agents with different $p_{pe}$. More Post-
Exploration steps lead to better performance.

###  A.2 More results on LavaGap

Figure 9: Performance of agents with different exploration factors $\epsilon$
in LavaGap. Adding exploration during goal reaching does not improve the
overall performance. We think that’s because the LavaGap environment is too
small so that the exploration can barely bring the agent to new states. Each
experiment in LavaCrossing is averaged over 10 different environment seeds and
5 repetitions.

Figure 10: Left: Performance of agents with different $\beta$. Selective Post-
Exploration ($\beta=0.01$) outperforms full Post-Exploration ($\beta=0$).
Right: Performance of agents with different $p_{pe}$.

###  A.3 Hyper-parameter Settings

All hyper-parameters we used in this work are shown in Tab. 2. Learning rate
$\alpha$ and discount factor $\gamma$ are for Q-learning update (Eq. 2).
$\beta$ is the temperature for selective Post-Exploration (Eq. 4). $\epsilon$
is the exploration factor in $\epsilon$-greedy policy. $p_{pe}$ is the
percentage of the whole trajectory that the agent will Post-Explore. $n_{pe}$
is the constant number of steps the agent will Post-Explore. Detailed
explanation of each parameters can be found in corresponding sections.

Parameters | Values
---|---
learning rate | 0.1
discount factor | 0.99
$\beta$ | 0, 0.01, 0.05, 1
$\epsilon$ | 0, 0.1, 0.3, 1
$p_{pe}$ | 0.1, 0.5, 0.8
$n_{pe}$ | 10, 15, 20
Table 2: All hyper-parameters we used in this work.

###  A.4 Algorithms

Alg. 2 is the IMGEP framework we use in this work, where the red part
indicates the extension with post-exploration (without the red part, the
algorithm simply reduces to standard IMGEP). Alg. 1 shows how we relabel the
trajectory and perform update on the relabelled data.

Algorithm 1 Single hindsight relabelling

Initialize: Episode $M=\\{g,s_{0},a_{0},r_{0},s_{1},a_{1}...\\}$, goal-
conditioned value function $Q(s,a,g)$, learning rate
$\alpha\in\mathbb{R}^{+}$, total number of relabelled goals $k$.

repeat $k$ times:

$i\leftarrow$ set-index-to-label-as-goal() {avoid duplicates over repetitions}

$g=s_{i}$ {set hindsight goal}

for $t$ in $0$ to $(i-1)$:

$r_{t}=\mathbbm{1}_{s_{t}=g}$

$\hat{Q}(s_{t},a_{t},g)\leftarrow\hat{Q}(s_{t},a_{t},g)+\alpha\cdot[r_{t}+\gamma\cdot\max_{a}\hat{Q}(s_{t+1},a,g)-\hat{Q}(s_{t},a_{t},g)]$

Algorithm 2 IMGEP Q-learning with post-exploration and hindsight (red part is
post-exploration)

Initialize: Goal-conditioned value function $\hat{Q}(s,a,g)$, environment Env,
episode memory $M$, goal space $G$, the number of post-exploration steps
$n_{pe}$, goal-conditioned reward function $R_{g}(s,a,s^{\prime})$, the
probability distribution of a goal $g$ being post-explored $p_{pe}(g)$,
learning rate $\alpha\in\mathbb{R}^{+}$, number of hindsight relabels $k$.

while training budget left do

$g\sim G$ {sample a goal $g$ from $G$}

$s\sim p_{0}(s)$ {reset environment}

$M\leftarrow\\{\\}$

while $s$ not terminal and $g\neq s$ do

$a\leftarrow$ e-greedy($\hat{Q}(s,a,g)$)

$s^{\prime}\leftarrow$ Env.step($a$) {simulate environment}

$r\leftarrow R_{g}(s,a,s^{\prime})$ {goal-conditioned reward}

$\hat{Q}(s,a,g)\leftarrow\hat{Q}(s,a,g)+\alpha\cdot[r+\gamma\cdot\max_{a^{\prime}}\hat{Q}(s^{\prime},a^{\prime},g)-\hat{Q}(s,a,g)]$

$M$.append($\langle s,a,r,s^{\prime},g\rangle$)

$G$.update($s^{\prime}$) {Possibly augment goal space with new observation}

$s\leftarrow s^{\prime}$ {$\Delta\sim$ Uniform[0,1]}

end while

if $g$ is reached and $\Delta\leq p_{pe}(g)$ then

for 1 to $n_{pe}$ do

$a$ = RandomAction() {Post-exploration has random action selection}

$s^{\prime}$ = Env.step($a$)

$r=0,g=\texttt{None}$

$M$.append($\langle s,a,r,s^{\prime},g\rangle$)

$s\leftarrow s^{\prime}$

end for

end if

Hindsight($M$,$\hat{Q}(s,a,g)$, $\alpha$, $k$) { Alg. 1 }

end while