# AdaStop: sequential testing for efficient and reliable comparisons of Deep RL Agents

Timothée Mathieu, Riccardo Della Vecchia, Alena Shilova, Matheus Centa de Medeiros, Hector Kohler, Odalric-Ambrym Maillard, Philippe Preux

► To cite this version:

Timothée Mathieu, Riccardo Della Vecchia, Alena Shilova, Matheus Centa de Medeiros, Hector Kohler, et al.. AdaStop: sequential testing for efficient and reliable comparisons of Deep RL Agents. RR-9513, Inria Lille Nord Europe - Laboratoire CRISTAL - Université de Lille. 2023. hal-04132861v1

HAL Id: hal-04132861

https://inria.hal.science/hal-04132861v1

Submitted on 20 Jun 2023 (v1), last revised 29 Jan 2024 (v2)

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# AdaStop: adaptive statistical testing for sound comparisons of Deep RL agents

Timothée Mathieu, Riccardo Della Vecchia, Alena Shilova, Matheus Medeiros

Centa, Hector Kohler, Odalric-Ambrym Maillard, Philippe Preux

► To cite this version:

Timothée Mathieu, Riccardo Della Vecchia, Alena Shilova, Matheus Medeiros Centa, Hector Kohler, et al.. AdaStop: adaptive statistical testing for sound comparisons of Deep RL agents. Transactions on Machine Learning Research Journal, 2024. hal-04132861v2

HAL Id: hal-04132861

https://inria.hal.science/hal-04132861v2

Submitted on 13 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Inria

# AdaStop: sequential testing for efficient and reliable comparisons of Deep RL Agents

Timothée Mathieu, Riccardo Della Vecchia, Alena Shilova, Matheus Centa de Medeiros, Hector Kohler, Odalric-Ambrym Maillard, Philippe Preux

## RESEARCH REPORT

Nº 9513

June 2023

Project-Team Scool
# AdaStop: adaptive statistical testing for sound comparisons of Deep RL agents

**Timothée Mathieu**

Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189 – CRISTAL

timothee.mathieu@inria.fr

**Riccardo Della Vecchia**

Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189 – CRISTAL

ric.della vecchia@gmail.com

**Alena Shilova**

Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189 – CRISTAL

alena.shilova@inria.fr

**Matheus Medeiros Centa**

Université de Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRISTAL

matheus.medeiros-centa@inria.fr

**Hector Kohler**

Université de Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRISTAL

hector.kohler@inria.fr

**Odalric-Ambrym Maillard**

Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189 – CRISTAL

odalric.maillard@inria.fr

**Philippe Preux**

Université de Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRISTAL

philippe.preux@inria.fr

Reviewed on OpenReview: https://openreview.net/forum?id=lXyZr9TLEU

## Abstract

Recently, the scientific community has questioned the statistical reproducibility of many empirical results, especially in the field of machine learning. To contribute to the resolution of this reproducibility crisis, we propose a theoretically sound methodology for comparing the performance of a set of algorithms. We exemplify our methodology in Deep Reinforcement Learning (Deep RL). The performance of one execution of a Deep RL algorithm is a random variable. Therefore, several independent executions are needed to evaluate its performance. When comparing algorithms with random performance, a major question concerns the number of executions to perform to ensure that the result of the comparison is theoretically sound. Researchers in Deep RL often use less than 5 independent executions to compare algorithms: we claim that this is not enough in general. Moreover, when comparing more than 2 algorithms at once, we have to use a multiple tests procedure to preserve low error guarantees. We introduce ADASTOP, a new statistical test based on multiple group sequential tests. When used to compare algorithms, ADASTOP adapts the number of executions to stop as early as possible while ensuring that enough information has been collected to distinguish algorithms that have different score distributions. We prove theoretically that ADASTOP has a low probability of making a (family-wise) error. We illustrate the effectiveness of ADASTOP in various use-cases, including toy examples and Deep RL algorithms on challenging Mujoco environments. ADASTOP is the first statistical test fitted to this sort of comparisons: it is both a significant contribution to statistics, and an important contribution to computational studies performed in reinforcement learning and in other domains.
<figure><img src="image_2.png" /></figure>
# 1 Introduction

In many fields of computer science, it is customary to perform an experimental investigation to compare the practical performance of two or more algorithms. When the behavior of an algorithm is non-deterministic (for instance because the algorithm is non-deterministic, or because the data it is fed upon is random), the performance of the algorithm is a random variable. Then, the way to do this comparison is not clear. Usually, one executes the algorithm (or rather an implementation of the algorithm: this point will soon be clarified) several times in order to obtain an average performance and its variability. How much “several” is depends on the authors, and some contingencies: thanks to the law of large numbers, one may think that the larger the better, the more accurate the estimates of the average and the variability. This may be a satisfactory answer, but when a single execution lasts days or even weeks or months (such as LLM training), performing such a “large enough” number of executions is impossible.

To illustrate this point, let us consider the field of deep reinforcement learning (Deep RL), that is reinforcement learning algorithms that use a neural network to represent what they learn. We surveyed all deep RL papers published in the proceedings of the International Conference on Machine Learning in 2022 (see Fig.1a). In the vast majority of these papers, only a few executions have been performed: among the 18 papers using the Mujoco tasks, only 3 papers performed more than 10 runs, and 11 papers used only 3 to 5 runs. This begs the question: if we can be confident that 3 executions are not enough, how many executions would be enough to draw statistically significant conclusions? Conversely, are 80 executions not too much? This is not only a matter of computation time and computational resources occupation. Each execution contributes to pollute our planet and to the climate change. There is no answer to these questions today. Moreover, if someone redoes the comparison of the same algorithms on the same task, the conclusions should be the same: this concept is known as statistical reproducibility (Agarwal et al., 2021; Colas et al., 2019; Goodman et al., 2016) and should be a feature of any good experimental design.

This paper provides a partial answer to the problem: we introduce ADASTOP, a new statistical test tailored to the problem of small sample sizes in which we cannot suppose that the data are Gaussian. On the application side, we demonstrate the use of ADASTOP in practice and show its efficiency in dealing with comparison of Deep RL algorithms. On the theory side, we show the usual non-asymptotic and asymptotic guarantees of such a nonparametric test: we show that for large sample sizes, ADASTOP controls the false positive rate appropriately, and we prove a non-asymptotic bound on false positive (i.e. family-wise error) when comparing the distributions. We keep as future work the question of the non-asymptotic comparison of the means of distributions.

This paper is accompanied by a software program that implements the test which is very easy to use. In short, in this paper, we provide a methodological approach and its actual implementation to compare the performance of algorithms having random performance in a statistically significant way, while trying to minimize the computational effort to reach such a conclusion. Such experimental investigations arise in various fields of computational AI such as machine learning, and computational optimization. We will use ADASTOP in the field of reinforcement learning to illustrate this paper, but its application to other fields of computational AI is straightforward, as well as in many other fields of science using computational studies to compare the performance of algorithms.

The organization of the paper is as follows: in an informal way, we detail the requirements that has to fulfil a statistical test to fit our expectations in Section 2. In this section, we also make clear the limitations of ADASTOP. Section 3 introduces the main ingredients of our test, ADASTOP. Section 4 in the formal analysis of the properties of ADASTOP. Proofs are established in appendices C to F. We illustrate the use of ADASTOP in Section 5 before concluding. Appendix A lists all the notations used in this paper. Appendix B provides a minimal exposition of the main concepts of hypothesis testing for readers who are not trained in statistics.

To reproduce the experiments of this paper, the python code is freely available on GitHub at https://github.com/TimotheeMathieu/Adaptive_stopping MC RL. In addition, we provide a library and command-line tool that can be used independently: the ADASTOP Python package is available at https://github.com/TimotheeMathieu/adastop.
Inria

# AdaStop: sequential testing for efficient and reliable comparisons of Deep RL Agents

Timothée Mathieu *, Riccardo Della Vecchia*, Alena Shilova*, Matheus Centa de Medeiros†, Hector Kohler†, Odalric-Ambrym Maillard*, Philippe Preux†

Project-Team Scool

Research Report n° 9513 — June 2023 — 38 pages

**Abstract:** The reproducibility of many experimental results in Deep Reinforcement Learning (RL) is under question. To solve this reproducibility crisis, we propose a theoretically sound methodology to compare multiple Deep RL algorithms. The performance of one execution of a Deep RL algorithm is random so that independent executions are needed to assess it precisely. When comparing several RL algorithms, a major question is how many executions must be made and how can we assure that the results of such a comparison are theoretically sound. Researchers in Deep RL often use less than 5 independent executions to compare algorithms: we claim that this is not enough in general. Moreover, when comparing several algorithms at once, the error of each comparison accumulates and must be taken into account with a multiple tests procedure to preserve low error guarantees. To address this problem in a statistically sound way, we introduce AdaStop, a new statistical test based on multiple group sequential tests. When comparing algorithms, AdaStop adapts the number of executions to stop as early as possible while ensuring that we have enough information to distinguish algorithms that perform better than the others in a statistical significant way. We prove both theoretically and empirically that AdaStop has a low probability of making an error (Family-Wise Error). Finally, we illustrate the effectiveness of AdaStop in multiple use-cases, including toy examples and difficult cases such as Mujoco environments.

**Key-words:** Reproducibility, Reinforcement Learning, Sequential Tests.

RESEARCH CENTRE
LILLE - NORD EUROPE

Parc scientifique de la Haute-Borne
40 avenue Halley - Bât A - Park Plaza
59650 Villeneuve d'Ascq

<footnote>* Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRISTAL, Lille, France</footnote>

<footnote>† Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 – CRISTAL, Lille, France</footnote>
# 2 Statistical reproducibility in RL through the lens of statistical tests

In this section we begin by identifying the key concepts necessary to discuss reproducibility in the case of Deep RL. Then we investigate the pros and cons of statistical tests to answer the statistical reproducibility problem in Deep RL, and we compare this methodology to current practices in experimental Deep RL.

## 2.1 Definitions

First, we define some key terms that we use in the rest of the paper.

As raised above, we do not compare algorithms but a certain implementation of an algorithm using a certain set of values for its hyperparameters. In D. Knuth's spirit (Knuth, 1968), we use the term **algorithm** in its usual meaning in computer science as the description of the basic operations required to transform a certain input into a certain output. By basic operations we mean the use of variables and simple operations (arithmetic, logical, etc), along with assignments to variables, sequences of instructions, tests and loops. Such an algorithm typically has some hyperparameters that control its behavior (a threshold, the dimension of the input domain, how a certain variable decays in time, the architecture of a neural network, etc). In this regard, we may say that as presented in (Schulman et al., 2017), PPO is an algorithm. However, one should be cautious that many aspects of PPO may be defined in various ways, and that the notion of “the PPO algorithm” is not as clearly defined as e.g. “the quicksort algorithm”. The same may be said for all Deep RL algorithms for which there exist many variations.

Let us make clear the distinction between parameters and hyperparameters: parameters are learned from data, while hyperparameters are set a priori. For instance, the weights of a neural network are parameters, while the architecture of the network is a hyperparameter (unless this architecture is also learned during the training of the agent, which is far from being a common practice in Deep RL).

We use the term **agent** to refer to a certain implementation of an algorithm along with the value of its hyperparameters. If an agent is run several times, the value of the hyperparameters is the same at the beginning of each run. A special case concerns the seed of the pseudo-random number generator. Deep RL algorithms typically use a different seed to initialize each run. So the seed is not part of the definition of an agent. In the context of reinforcement learning, we call **policy** a trained agent. A policy is a decision function that maps observations to actions.

The **score** of an agent is a numerical value that quantifies its performance. Its definition is really up to the experimenter and the objective of the experiments she designed. In the case of an RL agent, the score is usually a numerical value computed from policy evaluations. For instance, the score used in a given experiment may be the mean episodic return, or its variance, or many other quantities (running time, memory consumption, number of updates, etc). In most Deep RL research, agents are compared as follows: 1) an agent is trained on one random seed, 2) after training, the policy is evaluated for a given number of episodes to compute one score, 3) this evaluation is repeated *K* times eventually providing *K* scores, 4) then a statistic is computed over these *K* scores, 5) some conclusion about the performance of the various agents/algorithms is drawn. We suppose that enough policy evaluations have been performed to account for the possible stochasticity of both the policy and the environment. ADASTOP is concerned with having a significant comparison of the theoretical mean of the scores while using as few random seeds as possible.

## 2.2 Ingredients for an appropriate statistical test

Our goal is to provide a statistical test to decide whether one agent performs better than some others. However, strictly speaking, we really decide whether two agents perform equally or not by comparing the statistic of their scores measured on a set of (evaluation) runs, up to some confidence $\alpha$. Let us assume that the statistic is the mean. Then, when ADASTOP concludes that the means of the 2 agents differ, it is common practice to rank the agents based on their comparison. However, strictly speaking, this is an abuse and this conclusion is only valid up to some probability which is usually considered so large that its alternative can be rejected. To stress this point, we will write that an agent is “most likely performing better” than an other agent when the test of their mean performances is rejected. We will denote this with the acronym MLB.
# AdaStop: test séquentiel pour les comparaisons efficaces et fiables d'Agents Profonds APR

**Résumé** : La reproductibilité de nombreux résultats expérimentaux dans le domaine de l'apprentissage par renforcement profond (APR) est remise en question. Pour résoudre cette crise de reproductibilité, nous proposons une méthodologie théoriquement solide pour comparer plusieurs algorithmes d'apprentissage par renforcement profond. La performance d'une exécution d'un algorithme de APR Profond est aléatoire, de sorte que des exécutions indépendantes sont nécessaires pour l'évaluer avec précision. Lors de la comparaison de plusieurs algorithmes APR, une question majeure est de savoir combien d'exécutions doivent être effectuées et comment garantir que les résultats d'une telle comparaison sont théoriquement valides. Les chercheurs en APR profond utilisent souvent moins de 5 exécutions indépendantes pour comparer les algorithmes : nous affirmons que cela n'est pas suffisant en général. De plus, lorsque l'on compare plusieurs algorithmes à la fois, l'erreur de chaque comparaison s'accumule et doit être prise en compte par une procédure de tests multiples afin de préserver des garanties d'erreur faibles. Pour résoudre ce problème d'une manière statistiquement fiable, nous présentons AdaStop, un nouveau test statistique basé sur des tests séquentiels à groupes multiples. Lors de la comparaison d'algorithmes, AdaStop adapte le nombre d'exécutions pour s'arrêter le plus tôt possible tout en garantissant que nous disposons de suffisamment d'informations pour distinguer les algorithmes plus performants que les autres de manière statistiquement significative. Nous prouvons à la fois théoriquement et empiriquement qu'AdaStop a une faible probabilité de commettre une erreur. Enfin, nous illustrons l'efficacité d'AdaStop dans de multiples cas d'utilisation, y compris des exemples de jouets et des cas difficiles tels que les environnements Mujoco.

**Mots-clés** : Reproductibilité, Apprentissage par Renforcement, Tests Séquentiels.
The reader should note that this subtlety is not only true for ADASTOP but it is true for all statistical tests based on the equality of the means of two distributions. This point is rarely made clear in publications.

Now, let us list the requirements and difficulties we have to face in the design of such a statistical test.

First, many tests in statistics are defined for Gaussian random variables. However, one quickly figures out that the observed performance of an agent is usually not Gaussian. Fig.1b illustrates this point: we represent the distribution of the performance of 4 agents implementing 4 different RL algorithms (PPO, SAC, DDPG, TRPO): the performance is usually multi-modal, and it is not even a mixture of a few Gaussian distributions as it may seem. This leads us to a nonparametric test. Second, we would like to perform the minimal number of runs. This leads us to the use of a sequential adaptive test that tells us if we need to run the agents a few more times, or if we can take a decision in a statistically significant way with the already collected data. Third, we want to be able to compare more than 2 agents which leads us to multiple testing. Fourth, we want the conclusions of the test to be statistically reproducible, that is, if someone reproduces the execution of the agents and applies the test in the same way as someone else, the conclusion is the same. Fifth, we want to keep the number of runs within reasonable limits: for that purpose, we set a maximum number of scores to collect: if no decision can be made using this budget, the test can not decide whether an agent is MLB than the others. The first 3 requirements call for a nonparametric, sequential, multiple test. A candidate statistical test that may verify all these properties can be found in group sequential permutation test (see the textbook (Jennison & Turnbull, 1999) on general group sequential tests). We use these 5 ingredients to construct ADAStop.

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /><figcaption>Figure 1: Motivations for ADAStop. (a): a census of the number of scores ($N_{score}$) used in RL papers using Mujoco environments published in the proceedings of ICML 2022. (b): estimations of the score distributions of 4 well-known Deep RL agents on Hopper, a Mujoco environment, with $N_{score} = 30$. We see from the census that most experiments used 5 or less scores ($N_{score} \le 5$) to draw conclusions. Those conclusions are most likely statistically wrong as they are equivalent to drawing 5 samples from distributions similar to the right plot to draw conclusions about the empirical means.</figcaption></figure>

ADASTOP, our proposed statistical test, meets all these expectations. Before diving into the technical details, let us briefly explain how ADAStop is used in practice. Fig. 2 illustrates an execution of ADAStop on a small example. Let us suppose that we want to compare the performance of 2 agents, a green agent and a blue agent. Fig. 2 illustrates the sequential nature of the test from top to bottom. Initially, each agent is executed $N = 5$ times. This yields 5 scores for each agent: these 10 initial scores are shown on the top-leftmost part of Fig. 2 labelled Interim 1, $N = 5$, along with their barplots. After the test statistics are computed, ADAStop decides that this information is not enough to conclude, and more scores are needed. This set of actions (collection of 5 scores for each agent, computation of the statistics, and decision) is known as an **interim**. As no conclusion can be drawn, a second interim is performed: both agents are run 5 more times, yielding 10 more scores. In the middle of Fig. 2, these additional scores are combined with the first 5 ones of each agent: these 20 scores are represented, as well as the barplot for each agent. The test statistics are computed using these 20 scores. Again, the difference is not big enough to make a decision given the available information, so we make a third interim: each agent is executed 5 more times. At the bottom of Figure 2, these 30 scores are represented, as well as the barplot for each agent. The test statistics are
# 1 Introduction

We consider the problem of comparing a set of Reinforcement Learning (RL) agents, based on experimental runs only, in a theoretically sound way while using as few runs as possible.

A methodology crisis. In this paper, the end-goal is result reproducibility which consists in being able to get the “same” result when re-running an experiment even if the seed of randomness changes [1, 7, 13]. In RL, in particular, papers that contain an experimental study usually compare the performance of 2 or more agents facing a certain task. The common practice is to run each agent $N$ times, typically using different pseudo-random number seeds. From these runs, the performance of the agent is measured (e.g. using an estimate of the value of the agent policy). This $N$ is usually set a priori, hoping that it is enough to decide how agents rank, or at least the best one. When the training does not take too long, it is possible to take $N$ large and be confident about the conclusion. As it is customary today, one may also test the agents on computationally heavy tasks, where an experimental run of one agent may take several days to complete. In such cases, practitioners may execute only $N = 3$ runs, and still proceed with conclusions. We scanned all RL papers published in the proceedings of ICML 2022: there are 82 and only one paper uses a statistical test to compare agents [19]. Most papers use less than $N = 5$ runs (see Appendix H.1). For a statistician, it is clear that the $N$ being used is unlikely to be enough, except maybe the paper using $N = 80$. In any case, for all these 82 papers, we simply do not know if the conclusion is statistically significant. Indeed, from a probabilistic point of view, the performance of an agent is a random variable, and one run generates one sample from this random variable. The randomness may come from the agent itself (e.g. random initialization of some variables, or random decisions), from stochastic transitions or rewards of the environment, or both. For these reasons, comparing the performance of two agents in a reliable way usually requires more than a single run of each agent, to account for the statistical variability of the random variables and hence draw the correct conclusion. This creates a tension between collecting enough runs to ensure the correct conclusion and keeping the running time (also computational power, energy consumption) required by all experimental runs as low as possible. Moreover, the distribution of the performance of an agent rarely belongs to a classical parametric family and should rather be thought of as being non-parametric (see Appendix H.2), which creates an additional difficulty.

Motivation. Motivated by these critical methodological issues, we want to introduce a sound statistical test as a tool for practitioners to assess whether agent $A_1$ is statistically better than learning agents $A_2, \dots, A_L$. Furthermore, due to the stringent cost of performing one run of an agent, we want to achieve a statistically significant conclusion with as few runs as possible to rank the agents. In short, we want a sequential non-parametric multiple-hypothesis test with sound guarantees (for drawing the right conclusion), able to stop experiments as soon as enough evidence is acquired to rule out the wrong hypotheses. While designing such a test may be beneficial far beyond the field of reinforcement learning (e.g. computational optimization), in this paper we focus on RL due to its identified methodology issues and easily available benchmarks.

*Literature overview of evaluation methods.* The literature relevant to solving the evaluation methodology challenge is three-fold:

**Non-adaptive approaches.** In the literature, two approaches for RL agent comparison have been studied. In [6, 7], the authors show how to use hypothesis testing to test the equality between agents. Compared to our work, their approach is non-adaptive and only compares two agents. Another line of works can be found in [1] in which the authors compare many agents using confidence intervals. Their approach is non-adaptive and lacks theoretical guarantees, as they do not use multiple tests.

**Sequential tests.** A closely related method for adaptive hypothesis testing are sequential
<figure><img src="image_4.png" /><figcaption>Figure 2: Illustration of the sequential and adaptive aspects of ADASTOP.</figcaption></figure>

computed again on these 15 scores per agent. Now, ADASTOP decides to reject the null hypothesis, which means that the two set of scores of the two agents are indeed different, and terminates: the compared agents do not perform similarly. As explained in Section 2.5, this shows that the green agent performs most likely better than the blue one.

## 2.3 Current approaches for RL agents comparison

In the RL community, different approaches currently exist to compare agents. In (Colas et al., 2018; 2019), the authors show how to use hypothesis testing to test the equality between agents. Compared to our work, their approach is non-adaptive and only compares two agents. In (Patterson et al., 2023), the authors explore a similar workflow with added steps specialized to deep RL (hyperparameter optimization, choice of the testing environment...). Another line of works can be found in (Agarwal et al., 2021) in which the authors compare many agents using confidence intervals.

In this section, we summarize some of the problems we identify with the current approaches used to compare two or more RL agents in research articles.

**How many scores should we use?** The number of scores used in practice in RL is quite arbitrary and often quite small (see Figure 1a). An intuition comes from the law of large numbers. As the performance of an agent is represented by the true mean of its scores, the more scores, the more precise the estimation of its performance. However, this does not tell us anything about what is a sufficient number of scores to draw a statistically significant conclusion.

### Theoretically sound comparison of multiple agents.

According to statistical theory, in order to compare more than 2 agents, we need more samples from each agent than when we compare only two agents. The basic idea is that there is a higher chance to make an error when we perform multiple comparisons than when we compare only two agents, hence we need more data to have a lower probability of error at each comparison. This informal argument is formalized in the theory of multiple testing. However, the theory of multiple testing has almost never been used to compare
tests. Two particular classes of sequential tests that are commonly used are the Sequential Probability Ratio test [30] and the Generalized Likelihood Ratio test [18]. In the sequential testing, one deals with the performance of each single run, one after the other. This is not adapted to our situation because in RL practice, one often trains several agents in parallel, hence obtaining a batch of performances simultaneously. This motivates the use of group sequential tests [17]. In particular, the test we use is close to the one presented in [22] in which they use rank test with group-sequential testing. Contrary to our work, [22] do not provide theoretical guarantees.

**Bandits (Best arm identification or ranking).** Our objective is close to the one of bandit algorithms [20]. Similar to bandits, we *minimize the stopping time* (as in fixed-confidence setting) of the test and have a *fixed maximum budget* (as in fixed-budget setting). In our test, we allow a type I error with probability $\alpha \in (0, 1)$, which is similar to the fixed confidence setting while still having a fixed budget. Compared to the fixed budget setting, we allow a larger error rate, which results in a test that is more sample efficient than bandit algorithms.

*Contribution.* The main contribution of this paper is to define AdaStop, a statistical test able to decide whether the number of runs already made is enough to rank a set of agents with some confidence level $\alpha$. Moreover, AdaStop enables us to generate the number of runs adaptively until it can tell how the agents are ranked. AdaStop is a new sequential test; we provide the theoretical analysis that proves that AdaStop is actually performing this test. Aside from the theoretical contribution, we report on an experimental study that demonstrates its use. AdaStop also comes as an off-the-shelf open source program that is easy to use.

By providing a statistical test to compare the performance of different agents, AdaStop improves on experimental reproducibility (we define this term below) by making researchers run their experiments just enough times, but not more. In this regard, AdaStop may also help to optimize the energy consumption by avoiding unnecessary runs, while ensuring statistically valid conclusions.

**Overview of the paper:** In Section 2, we state the problem and make a survey of existing evaluation workflows in RL. In Section 3, we provide a background on the statistical tools used to design AdaStop, especially group-sequential, permutation and multiple hypotheses tests. Our main algorithm, AdaStop, is introduced in Section 4, Algorithm 1, and its theoretical guarantees are stated in Theorem 1. Finally, in Section 6, we give a detailed experimental study of potential benefits of AdaStop to draw statistically significant comparisons of agents.

The code (in python) to reproduce the article is on github, and, in addition, we provide a library and command-line tool that can be used independently<fnref n="1" />.

# 2 Problem setting

First, we fix some vocabulary that we will use throughout the article.

* Vocabulary in RL

**Agent:** a program implementing an RL algorithm with its set of parameters and hyper-parameters values, except the seed of the pseudo-random number generator.

<footnote n="1">¹Anonymous repository can be found here: AdaStop Library repo https://anonymous.4open.science/r/adastop-1CF3, paper reproducibility repo https://anonymous.4open.science/r/Adaptive_stopping MC_RL-5450/.</footnote>
RL agents (with the notable exception of Patterson et al. (2023, Section 4.5)). In this paper, we remedy this with ADASTOP giving a theoretically sound workflow to compare 2 or more agents.

**Theoretically sound study when comparing agents on a set of tasks.**

Atari environments (Bellemare et al., 2013) are famous benchmarks in Deep RL. Due to time constraints, when using these environments, it is customary to use very few scores for one given game (typically 3 scores) and compare the agents on many different games. The comparisons are then aggregated: agent $A_1$ perform better than agent $A_2$ on more than 20 games out of the 26 games consider in the experiments. In terms of rigorous statistics, this kind of aggregation is complex to analyse properly because reward distributions are not the same in all games. $A_2$ may be better than $A_1$ only on some easy games: does this mean that $A_1$ is better than $A_2$? Up to our knowledge, there is not any proper statistical guarantee for this kind of comparison.

Advances have been made in (Agarwal et al., 2021) to interpret and visualize the results of RL agents in Atari environments. In particular the authors advise plotting confidence intervals and using the interquartile mean instead of the mean as aggregation functions. Correctly aggregating the comparisons on several games in Atari is still an open problem, and it is beyond the scope of this article. In this article, we suppose that we compare the agents on a single task, and we leave the comparison on a set of different tasks for future work. A discussion on these methods and the challenges of aggregating the results from several Atari environments can be found in the Appendix G.

**2.4 Some methodologies for comparison of RL agents**

Figure 1 of (Patterson et al., 2023) defines a workflow for the meaningful comparison of two RL agents given an environment and a performance measure. In addition to the usual considerations regarding which statistics to compare (Colas et al., 2018; Agarwal et al., 2021), (Patterson et al., 2023) also include hyperparameter choice in the workflow. For that, they recommend to use 3 scores per algorithm per set of hyperparameters to identify a good choice of hyperparameters for a given algorithm. When this is done, a fixed number of scores (set using expert knowledge on the environment) are computed for each of these fully-specified agents. These scores are then used for statistical comparison. ADASTOP fits at the end of this workflow.

In Fig 3, we showcase the use of ADASTOP to compare SAC (Haarnoja et al., 2018) to other Deep RL algorithms on HalfCheetah and Hopper Mujoco tasks. One can imagine a scenario in which SAC inventors follow (Patterson et al., 2023) methodology. After finding the best hyperparameters for TRPO, PPO and DDPG (Schulman et al., 2015; 2017; Lillicrap et al., 2015) agents are compared with ADASTOP using a minimal number of scores to get significant statistics. (Patterson et al., 2023) recommends 15 scores per agent per environment for a maze environment but this number of scores should vary in other environments, and it is not clear how many scores should be used for HalfCheetah and Hopper. This is why we need to use ADASTOP.

Using ADASTOP, we collect scores in an adaptive manner. This allows us to state that we collected enough scores to conclude that the SAC agent is MLB than other agents on HalfCheetah, and MLB than DDPG and TRPO agents on Hopper. As in all statistical tests, the conclusion holds up to a certain confidence level. A more in-depth study of the agents performance on Mujoco environments is given in Section 5.3.

**2.5 Limitations of AdaStop and comparison to other statistical tests**

Before presenting the theory behind ADASTOP, we want to make it clear that doing a statistically sound comparison with very few samples is a hard problem, and ADASTOP is one way to partially answer this problem. In particular, (i) we do not claim that ADASTOP is optimal, and (ii) more work is still necessary to prove theoretical guarantees for ADASTOP to support the empirical performances exhibited in the experiments (see in particular Section 5.2 and discussions on the power of the test).

The main theoretical limitation of ADASTOP comes from the fact that ADASTOP is distribution-free: it does not make any assumption on the distribution of the scores except a finite variance to get the asymptotic guarantees. As a consequence, the only non-asymptotic guarantees that we have are based on the comparison
**Seed & run:** a run is one training of an agent and the subsequent evaluations of this trained agent. Because one run is initialized with a seed of the random number generator, it is common to refer to the number of runs as the number of seeds.

**Evaluation:** cumulative reward obtained after running the policy of a trained agent for one episode.

**Performance:** denoted $e_N(j)$ or $e_{N,k}(j)$: quantification of the performance of a trained agent on one run. Typically, we run the agent's policy on the environment for 100 epochs and recover the evaluation of each epoch. The performance returned is usually the mean of these 100 evaluations.

* **Vocabulary on tests**

**Interim:** interim $k$ is the $k^{th}$ iteration in a group sequential testing, when we take a decision whether to reject the hypotheses and stop early or continue with the group sequential test.

**Boundary:** denoted $B_N^{(j)}$ or $B_{N,k}^{(j)}$, the boundary is the set of all the thresholds used in the group sequential test.

## 2.1 Goal and requirements for AdaStop

Given two agents $A_1$ and $A_2$, the goal of this article is to propose a sound way to evaluate how large $N$ must be to be confident that either $E[e_1(A_1)] = E[e_2(A_2)]$ or $E[e_1(A_1)] \neq E[e_2(A_2)]$, i.e. if two agents perform similarly or if one is better than the other. This leads to manage a trade-off between the computational time and the correct assessment of the performances of $A_1$ and $A_2$. The main properties of AdaStop are as follows:

**Non-Parametric** The distribution of agents' performances is typically non-Gaussian, usually multi-modal, skewed, etc.

**Fixed Budget** AdaStop should use a fixed maximum number of runs so that the computational time stays reasonable.

**Sample efficient** AdaStop should stop as soon as possible in practice, that is, as soon as a statistically significant conclusion can be drawn.

**Handling batches of data** AdaStop should be able to manage batches of data to be run in parallel. Training one instance of an agent may take a long time, but training multiple instances of an agent is easy to parallelize, and thus should be done to speed-up computations.

Hence, AdaStop should be a distribution-free test.

A candidate statistical test that may verify all these properties can be found in group sequential permutation test (see the textbook [17] on the subject).

## 2.2 Survey of current evaluation workflows in RL

In the RL community, different approaches currently exist to compare agents and most of them are not based on any theoretically sound workflow. In what follows, we summarize some of the problems we see with the current approaches used to compare two or more RL agents in research articles.
<figure><img src="image_5.png" /><figcaption>Figure 3: Example of the use of ADASTOP to benchmark SAC in practice. We set the maximum number of runs B of each agent to 30. The upper row tables represent the conclusions when comparing SAC to the agents in the column using $N_{score}$ scores. For example, on HalfCheetah, ADASTOP concludes that SAC is MLB than PPO using 5 scores for SAC and 5 scores for PPO. On Hopper, 10 scores are enough to conclude that SAC is MLB than DDPG and TRPO, and ADASTOP concludes that SAC and PPO perform equally using the maximum budget of B scores for both SAC and PPO.</figcaption></figure>

of score distributions and not on the comparison of their means. Formally, this means that we have control over the error (in Theorem 1, the error is shown to be equal to the parameter of the test $\alpha$) when doing the tests:

$$H_j : P_{l_1} = P_{l_2}, \quad \text{against} \quad H'_j : P_{l_1} \neq P_{l_2}$$

where $P_{l_i}$ is the distribution of scores for agent $l_i$, and $(l_1, l_2)$ are the indices of the agents we want to compare. This comes in contrast with traditional Gaussian tests like the t-test, which have strong theoretical guarantees under strong Gaussian assumptions (see Table 1 for a comparison of the guarantees of some classical tests, in particular for nonparametric tests, a finite variance is not sufficient to get strong non-asymptotic results).

Comparing distributions is not what we really want to do, but it is how to proceed when performing distribution-free tests and if the distributions concentrate sufficiently well (i.e., have a finite variance) and the maximum sample size $N \times K$ is not too low. The Gaussian approximation of the sample mean justifies the way we use ADASTOP in this article. In particular, if we suppose a finite variance (a hypothesis that corresponds to a very weak concentration hypothesis necessary to get a central limit theorem), we give asymptotic guarantees on the comparison of the means (see Theorem 2):

$$H_j : \mathbb{E}_{P_{l_1}}[X] = \mathbb{E}_{P_{l_2}}[X], \quad \text{against} \quad H'_j : \mathbb{E}_{P_{l_1}}[X] \neq \mathbb{E}_{P_{l_2}}[X]. \qquad (1)$$

Asymptotic guarantees remain unsatisfactory because we are targeting small sample sizes. Non-asymptotic guarantees are harder to obtain and would typically require concentration assumptions such as sub-Gaussian or bounded distributions; we leave such theoretical concerns for future works. In practice, this means that ADASTOP approximately compares the means for a large enough sample size, and the practitioner should be aware that **if the size of an interim N is too small, AdaStop could give wrong results.** For this reason, we advise the practitioner to set $N$ and $K$ such that $N \times K \ge 30$. For a more precise study of the sample size effect, see Section 5.2. Please note that ADASTOP being an adaptive test, this does not mean that at least 30 scores have to be collected for each agent. This subtle point is illustrated in the experimental section of this paper.

Finally, note that the test expressed by Equation (1) is bidirectional, which means that in theory, concluding on this test does not tell us which of $P_{l_1}$ or $P_{l_2}$ has the largest mean score. Rather, it tells us that they are different. In practice, we use the sign of the difference in the empirical means to conclude which mean is larger. Using a bidirectional test and concluding on the direction afterward is often done by statisticians (see, in particular, the discussion in (Leventhal & Huynh, 1996) and the references therein), but this remains conceptually unsatisfactory. We keep the question of directional error for later work, which is why we do not
**Theoretically sound study of Atari environments?**

Atari environments are famous benchmarks in Deep RL [2]. Due to time constraints, when using these environments, it is customary to use very few seeds for one given game (typically 3 seeds) and compare the agents on many different games. The comparisons are then aggregated in: agent $A_1$ is better than agent $A_2$ on more than 20 games over the 26 games considered. In terms of rigorous statistics, this kind of aggregation is complicated to analyze properly because the reward distributions are not the same in all games. $A_2$ may be better than $A_1$ only on some easy games: does this mean that $A_1$ is a better than $A_2$? Up to our knowledge, there is not any proper statistical guarantee for this kind of comparison. Aggregating the comparisons on several games in Atari is still an open problem, and it is beyond the scope of this article. In this article, we suppose that we compare the agents only on one given task and leave the comparisons on a set of different tasks for future work.

**Theoretically sound comparison of multiple agents?**

Statistical theory tells that to compare more than 2 agents (this is called multiple testing in statistics), we need more samples from each agent than if we compare only two agents. The basic idea is that there are a lot more occasions to make an error than when we compare only two agents, hence we need more data to have a lower probability of error at each comparison. This informal argument is made precise when using multiple testing, but the theory of multiple testing has never been used to compare RL agents. In this paper, we remedy this with AdaStop giving a theoretically sound workflow to compare many RL agents.

**How many random seeds for Mujoco environments?**

The number of runs used in practice in RL is quite arbitrary and often quite small (see Appendix H.1). An arbitrary choice of seeds do not allow us to make a statistically significant comparison of the agents.

# 3 Background material on hypothesis testing

In this section we describe the basic building blocks used to construct AdaStop: group sequential testing, permutation tests, and step-down method for multiple tests. We explain these items separately, and then we combine them to create AdaStop in Section 4. We also provide a small recap on hypotheses testing in the Appendix (Section B) for readers that are not used to hypothesis testing and we provide an index of notations (Section A) defining the notations used in this article.

## 3.1 Group sequential testing

To choose the number of runs $N$ adaptively, we propose to use group sequential testing (GST, see [17, 14, 25, 23]). GST often makes strong assumptions on the data, in particular it is often assumed that the data is i.i.d. and drawn from a Gaussian distribution (see [17]). With AdaStop, we propose a non-parametric approach to GST similar to [22]. In GST, the data are obtained sequentially, but the tests are done only at interim time points, with a new block of $n$ data being obtained from one monitoring point to the next. At each interim, the boundary deciding which test to reject is derived from the permutation distribution of the statistics observed across all previously obtained data.

## 3.2 Permutation tests

Permutation tests (originally from [24, 11] and more recently [5, 27, 21]) are non-parametric tests that are exact for testing the equality of distributions. This means that the type I error of the
<table><caption>Table 1: Comparison of the properties of several statistical methods. The Wilcoxon, Permutation and Bootstrap tests are nonparametric tests used in (Colas et al., 2019) for comparison in Deep RL and the Gaussian Group-Sequential test (Jennison & Turnbull, 1999) is a (parametric) sequential test often used in the context of clinical trials.</caption><thead><tr><th rowspan="3">Test</th><th rowspan="3">Hypothesis</th><th rowspan="3">Sequential</th><th colspan="4">Theoretical Guarantees</th></tr><tr><th colspan="2">test P = Q vs P ≠ Q</th><th colspan="2">test μ<sub>P</sub> = μ<sub>Q</sub> vs μ<sub>P</sub> ≠ μ<sub>Q</sub></th></tr><tr><th>Asymptotic</th><th>Non-Asymptotic</th><th>Asymptotic</th><th>Non-Asymptotic</th></tr></thead><tbody><tr><td>t-test</td><td>Gaussian</td><td><b>X</b></td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Wilcoxon</td><td>None</td><td><b>X</b></td><td>✓</td><td>✓</td><td><b>X</b></td><td><b>X</b></td></tr><tr><td>Permutation</td><td>Finite variance</td><td><b>X</b></td><td>✓</td><td>✓</td><td>✓</td><td><b>X</b></td></tr><tr><td>Bootstrap</td><td>Finite variance</td><td><b>X</b></td><td>✓</td><td><b>X</b></td><td>✓</td><td><b>X</b></td></tr><tr><td>Gaussian GST</td><td>Gaussian</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>ADA STOP</td><td>Finite variance</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td><b>X</b></td></tr></tbody></table>

write that an agent performs “better” than another in this article but rather “most likely better (MLB)”. See Section B.2 for a discussion on directional error.

# 3 Hypothesis testing to compare agent performance

In this section, we provide the background material on the statistical tests that we use to construct ADA STOP. First we review the statistical evaluation methods found in the literature, and then we describe our methodology, and we express some results on ADA STOP.

## 3.1 Literature overview of evaluation methods

In this section, we present some relevant references connected to statistical evaluation methodology.

**Nonparametric (and non-sequential) hypothesis testing.** One of our main challenges is to deal with the nonparametric nature of the data at hand. In the literature there has been a lot of works on nonparametric testing (see (Lehmann et al., 2005) for a comprehensive overview). Traditionally, the focus has been on asymptotic results due to challenges in deriving optimality for a nonparametric model. For most nonparametric tests, only rather weak (exact) theoretical results can be given, mostly on type I error (Romano, 1989; Shapiro & Hubert, 1979). Recent work on sequential nonparametric tests (Shin et al., 2021; Howard et al., 2021) show strong non-asymptotic results using concentration inequalities. However, these results often involve non-optimal constants, failing to explain non-asymptotic efficiency. In contrast, we use permutation tests due to their empirical (Ludbrook & Dudley, 1998) and theoretical (Kim et al., 2022) efficiency for small sample sizes.

**Sequential tests.** A closely related method for adaptive hypothesis testing consists in sequential tests. Two commonly used sequential tests are the Sequential Probability Ratio test (Wald, 1945) and the Generalized Likelihood Ratio test (Kaufmann & Koolen, 2021). In sequential testing, the scores are compared one after the other in a completely online manner. This is not adapted to our situation because in RL practice, one often trains several agents in parallel, obtaining a batch of scores at once. This motivates the use of group sequential tests (Jennison & Turnbull, 1999).

**Parametric group sequential tests.** In traditional hypothesis testing, data is analysed as a whole once it has been collected. Conversely, in a Group Sequential Test (GST) data are collected sequentially, the tests being performed at interim time points. At each interim, a new set of N scores is collected (see (Jennison & Turnbull, 1999; Gordon Lan & DeMets, 1983; Pocock, 1977; Pampallona & Tsiatis, 1994) for references on GST). GST are often used in clinical trials to minimize the amount of data needed to conclude and this makes them well adapted for our purpose. The decision to continue sampling or conclude (with a controlled probability of error) depends on pre-defined stopping criteria used to define the tests. GST often makes strong assumptions on the data. In particular, it is often assumed that the data are i.i.d. and drawn from a Gaussian distribution (Jennison & Turnbull, 1999). This contrasts with our approach which is nonparametric.
test (e.g. the probability to make a mistake and reject the equality of two agents when their performances are statistically the same) is controlled by the parameter of the test $\alpha$.

Let us recall the basic formulation of a two-sample permutation test. Let $X_1, \dots, X_N$ be i.i.d. sampled from a law $P$ and $Y_1, \dots, Y_N$ i.i.d sampled from a law $Q$, we want to test $P = Q$ against $P \neq Q$. Let $Z_i = X_i$ if $i \le N$ and $Z_i = Y_i$ if $i > N$, $Z_1, \dots, Z_{2N}$ is the concatenation of $X_1, \dots, X_N$ and $Y_1, \dots, Y_N$. Then, the test proceeds as follows: we reject $P = Q$ if $T(id) = \left| \frac{1}{N} \sum_{i=1}^{N} (Z_i - Z_{N+i}) \right|$ is larger than a proportion $(1 - \alpha)$ of the values $T(\sigma) = \left| \frac{1}{N} \sum_{i=1}^{N} (Z_{\sigma(i)} - Z_{\sigma(N+i)}) \right|$ where $\sigma$ enumerates all possible permutations of $\{1, \dots, N\}$. The idea is that if $P \neq Q$, then $T(id)$ should be large, and due to compensations, most $T(\sigma)$ should be smaller than $T(id)$. Conversely, if $P = Q$, the difference of mean $T(\sigma)$ will be closer to zero.

## 3.3 Multiple hypothesis testing

Multiple comparisons arise when a statistical analysis involves multiple simultaneous statistical tests [21, Chapter 9]. One possible error measurement in such a test is the family-wise error. The idea is that the confidence level for rejection probability of a true hypothesis (type I error) generally applies only to each test considered individually, but often it is desirable to have a confidence level for the whole family of simultaneous tests. Instead of the type I error considered in two-sample testing, we consider the classical family-wise error rate [29] which is defined as the probability of making at least one type I error.

**definiton 1** (Family-Wise Error [29]). Given a set of hypothesis $H_j$ for $j \in \{1, \dots, J\}$, its alternative $H'_j$, and $I \subset \{1, \dots, J\}$ the set of the true hypotheses among them, then<fnref n="2" />

$$ \text{FWE} = \mathbb{P}_{H_j, j \in I}(\exists j \in I: \text{reject } H_j). $$

We say that an algorithm has a weak FWE control at a joint level $\alpha \in (0, 1)$ if the FWE is smaller than $\alpha$ when all the hypotheses are true, that is $I = \{1, \dots, J\}$ but not necessarily otherwise. We say it has strong FWE control if FWE is smaller than $\alpha$ for any non-empty set of true hypotheses $I \neq \emptyset$ (while $I^c$ refer to false hypotheses).

There are several procedures that can be used to control the FWE. The most famous one is Bonferroni's procedure [4] recalled in the Appendix (Section B). As it can be very conservative in general, we prefer a step-down method [27] that performs better in practice because it implicitly estimates the dependence structure of the test statistic. The step-down method that we use is described in details in the case of two agents in the Appendix in Section F.2. The basic idea is to use the quantiles of the permutation law of the maximum over all the comparisons of the test statistics of the tests for two agents. This step corresponds to line 10 to 15 in AdaStop algorithm (Algorithm 1).

# 4 Adaptive stopping for non-parametric group-sequential multiple hypothesis testing

We now go further and propose a new statistical test, AdaStop (see Algorithm 1), to compare the performance of multiple agents in an *adaptive* rather than fixed way. We consider $L \ge 2$ agents $A_1, \dots, A_L$. The $k^{th}$ step of the algorithm is called the $k^{th}$ *interim*, where $k \in \{1, \dots, K\}$.

<footnote n="2">²Regarding the precise meaning of the notation $\mathbb{P}_{H_j, j \in I}$, we refer to Appendix B.</footnote>
**Bandits (Best arm identification or ranking).** Our objective is close to the one of bandit algorithms (Lattimore & Szepesvári, 2020): we minimize the stopping time (as in the fixed-confidence setting) of the test, and we have a fixed maximum budget (as in a fixed-budget setting). In our test, we allow a type I error with probability $\alpha \in (0, 1)$, which is similar to the fixed confidence setting while still having a fixed budget. In practice, our approach is more sample efficient than fixed budget bandit algorithms because these algorithms will always exhaust their budget and thereby achieve lower error rates. In contrast, ADASTOP allows larger error rate in exchange to higher sample efficiency.

## 3.2 Background material on the building-blocks of AdaStop

This section describes the basic building blocks used to construct ADASTOP: group sequential testing, permutation tests, and step-down method for multiple hypothesis testing. We explain these items separately, and then we combine them to create ADASTOP in Section 4. We also provide a small recap on hypotheses testing in the Appendix B for readers unfamiliar with these notions.

In order to perform the minimal number of runs, we propose to use group sequential testing (GST) with a nonparametric approach using permutation tests. Our approach is similar to (Mehta et al., 1994) but for multiple hypothesis testing. Compared to GST, we keep the i.i.d. assumption, but we do not assume that the data are drawn from a specific family of parametric distribution. In (Mehta et al., 1994), the authors use rank tests with group-sequential testing. In contrast with our work, (Mehta et al., 1994) does not provide theoretical guarantees and considers only the case of 2 agents.

### 3.2.1 Permutation tests

Permutation tests are **nonparametric tests** that are exact for testing the equality of distributions. This means that the type I error of the test (i.e. the probability to make a mistake and reject the equality of two agents when their scores are statistically the same) is controlled by the parameter of the test $\alpha$, and that this is true for any fixed sample size $N$. Permutation tests are also well-known to work well in practice on **very small sample sizes** and are used extensively in biology. They were originally introduced by (Pitman, 1937) and (Fisher, 1936) (see (Lehmann et al., 2005, Chapter 17) for a textbook introduction). More recently (Chung & Romano, 2013) have studied asymptotic properties of this class of tests, while (Romano & Wolf, 2003) have focused on stepdown methods for multiple hypothesis testing.

Let us recall the basic formulation of a two-sample permutation test. Let $X_1, \dots, X_N$ be i.i.d. sampled from a law $P$ and $Y_1, \dots, Y_N$ i.i.d. sampled from a law $Q$. We want to test $P = Q$ against $P \neq Q$. Let $Z_i = X_i$ if $i \le N$ and $Z_i = Y_{i-N}$ if $i > N$, $Z_1, \dots, Z_{2N}$. The test proceeds as follows: we reject $P = Q$ if $T(\text{id}) = \left| \frac{1}{N} \sum_{i=1}^N (Z_i - Z_{N+i}) \right|$ is larger than a proportion $(1 - \alpha)$ of the values $T(\sigma) = \left| \frac{1}{N} \sum_{i=1}^N (Z_{\sigma(i)} - Z_{\sigma(N+i)}) \right|$ where $\sigma$ enumerates all possible permutations of $\{1, \dots, 2N\}$ and id is the identity permutation $(\text{id}(i) = i$ for all $i)$. Formally, we define the $(1 - \alpha)$-quantile as

$$B_N = \inf \left\{ b > 0 : \frac{1}{N!} \sum_{\sigma \in S_N} 1\{T(\sigma) \ge b\} \le \alpha \right\}$$

and we reject $P = Q$ when $T(\text{id}) \ge B_N$. The idea is that if $P \neq Q$, then $T(\text{id})$ should be large, and due to compensations, most $T(\sigma)$ should be smaller than $T(\text{id})$. Conversely, if $P = Q$, the difference of mean $T(\sigma)$ will be closer to zero. It is then sufficient to compute $T(\text{id})$ and $B_N$ in order to compute the decision of the test. Please note that this is a fairly usual simplification in the nonparametric tests literature to test the equality in distribution instead of the equality of the mean, because equality between distributions is easier to deal with<fnref n="1" />. It can be shown that permutation tests are nonetheless a good approximation of doing a comparison on the means (see Appendix E).

<footnote n="1">¹In a statistical test, we want to have control on the error when $H_0$ is true. $H_0$ can be seen as asserting that the distribution that generated the data is in a certain set of distributions $\mathcal{P}_0$. The larger $\mathcal{P}_0$, the more complicated it is to make a statistical test without using strong assumption on the data. When comparing distributions, $\mathcal{P}_0 = \{P, Q\}$ probability distributions $|P = Q|$, while when comparing the means, $\mathcal{P}_0$ is much larger because $\mathcal{P}_0 = \{P, Q\}$ probability distributions $|\mathbb{E}_P[X] = \mathbb{E}_Q[X]|$.</footnote>
We let $\mathbf{C}_0 = \{c_1, \dots, c_J\} \subseteq \{1, \dots, L\}^2$ be all the comparisons we want to make between agents. Therefore, $c_j = (c_{j,1}, c_{j,2}) \in \mathbf{C}_0$ denotes a comparison between a couple of agent's indices $c_{j,1}, c_{j,2} \in \{1, \dots, L\}$. To simplify the notation, we indicate a comparison between two agents directly with the index $j \in \{1, \dots, J\}$ instead of writing $c_j$, and we reserve the use of index $j$ just for this purpose. We adopt the same shorthand notation also to re-define equivalently the set of all comparisons $\mathbf{C}_0 = \{1, \dots, J\}$ using just the indices of the comparisons. I denotes the set of indices of the true hypotheses among $\{1, \dots, J\}$.

We denote $e_{1,i}(j), \dots, e_{2N,i}(j)$ the concatenation at interim $i$ of the $2N$ performance evaluations obtained for comparison $j$ of two agents. We also consider permutations of these evaluations to define our test statistics $T_{N,k}^{(j)}$ below. Let $\mathfrak{S}_{2N}$ be the set of all the permutations of $\{1, \dots, 2N\}$. For a comparison $j$, and a concatenation of the evaluations of the two agents in the comparison, we consider a permutation $\sigma_i \in \mathfrak{S}_{2N}$ at interim $i$ that reshuffles the order of the evaluations sending $n \in \{1, \dots, 2N\}$ to $\sigma_i(n) \in \{1, \dots, 2N\}$. Note that, if $n \in \{1, \dots, N\}$ and $\sigma_i(n) \in \{N+1, \dots, 2N\}$, we are permuting an evaluation of the first agent with an evaluation of the second agent in the comparison and vice versa. It can also happen that we instead permute evaluations of the same agents. The difference between the two cases is important for the definition of the following permutation statistic:

$$T_{N,k}^{(j)}(\sigma_{1:k}) = \left| \sum_{i=1}^{k} \left( \sum_{n=1}^{N} e_{\sigma_i(n),i}(j) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(j) \right) \right|. \quad (1)$$

In other words, $T_{N,k}^{(j)}(\sigma_{1:k})$ is the absolute value of the sum of differences of all evaluations until interim $k$ after consecutive permutations of the concatenation of the two agents' evaluations by $\sigma_1, \dots, \sigma_k \in \mathfrak{S}_{2N}$. Let $\mathbf{C} \subseteq \mathbf{C}_0$ be a subset of the set of considered hypothesis and denote

$$\bar{T}_{N,k}^{(\mathbf{C})}(\sigma_{1:k}) = \max_{j \in \mathbf{C}} T_{N,k}^{(j)}(\sigma_{1:k}).$$

**AdaStop: adaptive stopping algorithm using step-down method and group sequential permutation tests.** Algorithm 1 specifies the AdaStop test. It depends on the values of the boundary thresholds. Some implementation details are discussed below.

*Choice of permutations.* Instead of using all the permutations as it was done previously when comparing two agents, one may use a random subset of all permutations $S_k \subset \{\sigma_{1:k}, \forall i \le k, \sigma_i \in \mathfrak{S}_{2N}\}$ to speed-up computations. The theoretical guarantees persist as long as the choice of the permutations is made independent on the data. Using a small number of permutations will decrease the total power of the test, but with a sufficiently large number of random permutations (typically for the values of $N$ and $K$ considered, $10^4$ permutations are sufficient) the loss in power is acceptable.

$T_{N,k}$ is invariant by permutation of the first half and the second half of a group. In essence, choosing a permutation is equivalent to choosing the signs in $\sum_{n=1}^{N} e_{\sigma_i(n),i}(j) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(j)$. And because we take the absolute value, we obtain that there are $\frac{1}{2}(\binom{2N}{N})$ possible permutations in the first interim that give unique values to $T_{N,1}$. Then, by choosing permutation for the other interim, there are $\frac{1}{2}(\binom{2N}{N})^k$ possible permutations giving unique values to $T_{N,k}$.

Then, we use a parameter $m \in \mathbb{N}$ and the number of permutations used at interim $k$ will be $|S_k| = m_k = \min(m, \frac{1}{2}(\binom{2N}{N})^k)$, i.e. whenever possible, we use all the permutations and if this is too much, we use random permutations.
### 3.2.2 GST comparison of two agents

In this section, we compare two agents $A_1$ and $A_2$ through a group sequential test that can be seen as a particular case of ADA STOP for two agents (see Section 4). In this simplified case, the testing procedure is presented in Algorithm 1. We leave the case with more than 2 agents to compare and the full version of ADA STOP, including multiple hypothesis testing, for Section 4. Algorithm 1 uses a permutation test where, at each interim, the boundary deciding the rejection is derived from the permutation distribution of the difference of empirical means observed across all previously obtained data. In what follows, $N$ to denote the number of scores collected at interim $k$.

We denote by $S_{2N}$ the set of permutations of $\{1, \dots, 2N\}$, $\sigma \in S_{2N}$ one permutation and $\sigma(n)$ the $n$-th element of $\sigma$ for $n \in \{1, \dots, 2N\}$. In the GST setting, we perform a permutation test at each interim $k$, and $\sigma_k \in S_{2N}$ denotes the permutation at interim $k$. For $\sigma_1, \sigma_2, \dots, \sigma_k \in S_{2N}$, we denote $\sigma_{1:k} = \sigma_1 \cdot \sigma_2 \cdot \dots \cdot \sigma_k$ the concatenation$^2$ of the permutation $\sigma_1$ done in interim 1 with $\sigma_2$ done on interim 2, \dots, and $\sigma_k$ on interim $k$. Then, $e_{\sigma_i(n),i}$ denotes the score corresponding to the $n$-th element of the permuted sample at interim $i$, permuted by $\sigma_i$ (in the notations of Section 3.2.1 this corresponds to $Z_{\sigma_i(i)}$ but now, we specify the interim number in the notation). We denote:

$$T_{N,k}(\sigma_{1:k}) = \left| \sum_{i=1}^{k} \left( \sum_{n=1}^{N} e_{\sigma_i(n),i} - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i} \right) \right|, \quad (2)$$

and the decision boundary:

$$B_{N,k} \in \inf \left\{ b > 0 : \frac{1}{((2N)!)^k} \sum_{\sigma_{1:k} \in \hat{S}_{N,k}} 1\{T_{N,k}(\sigma_{1:k}) \ge b\} \le \frac{\alpha}{K} \right\}, \quad (3)$$

where $K$ is the total number of interims and $\hat{S}_{N,k}$ is the set of permutations $\sigma_{1:k} \in (S_{2N})^k$ such that the test was not rejected before interim $k$, e.g.

$$\hat{S}_{N,k} = \{\sigma_{1:k} \in (S_{2N})^k : \forall m < k, T_{N,m}(\sigma_{1:m}) \le B_{N,m}\}. \quad (4)$$

One can show that this is equivalent to choosing $B_{N,k}$ such that

$$\mathbb{P}_{\sigma_{1:k}} (T_{N,m}(\sigma_{1:m}) > B_{N,k}, \forall m < k, T_{N,m}(\sigma_{1:m}) \le B_{N,m}) \le \frac{\alpha}{K}.$$

We will see in Theorem 1 that this allows us to have control on the type I error of the test.

### 3.2.3 Multiple hypothesis testing

In order to compare more than two agents we need to perform multiple comparisons. This calls for a **multiple simultaneous statistical tests** (Lehmann et al., 2005, Chapter 9). The idea is that the probability to mistakenly reject a null hypothesis (type I error) generally applies only to each test considered individually. On the other hand, in order to conclude on all the tests at once, it is desirable to have an error controlled over the whole family of simultaneous tests. For this purpose, we use the family-wise error rate (Tukey, 1953) which is defined as the probability of making at least one type I error.

**Definition 1** (Family-Wise Error (Tukey, 1953)). Given a set of hypothesis $H_j$ for $j \in \{1, \dots, J\}$, its alternative $H'_j$, and $I \subset \{1, \dots, J\}$ the set of the true hypotheses among them, then the family-wise error (FWE) is defined by:

$$\text{FWE} = \mathbb{P}_{H_j, j \in I} (\exists j \in I: \text{reject } H_j),$$

where $\mathbb{P}_{H_j, j \in I}$ denotes the probability distribution for which all hypotheses $j \in I$ hold true$^3$. We say that an algorithm has a weak FWE control at a joint level $\alpha \in (0, 1)$ if the FWE is smaller than $\alpha$ when all the hypotheses are true, that is $I = \{1, \dots, J\}$ but not necessarily otherwise. We say it has strong FWE control if FWE is smaller than $\alpha$ for any non-empty set of true hypotheses $I \ne \emptyset$.

<footnote>$^2$Here, the word “concatenation” means that we apply $\sigma_1$ on $\{1, \dots, N\}$, then $\sigma_2$ on $\{N+1, \dots, 2N\}$ and so on, so that $\sigma_{1:k}(Nj + k) = \sigma_j(k)$.</footnote>

<footnote>$^3$See also Appendix B for further explanations on this concept.</footnote>
Definition of the boundaries. With these permutations, we define $B_{N,k}^{(C)}$ such that

$$B_{N,k}^{(C)} = \inf \left\{ b > 0 : \frac{1}{m_k} \sum_{\sigma \in \hat{S}_k} \mathbb{1}\{\bar{T}_{N,k}^{(C)}(\sigma_{1:k}) \ge b\} \le q_k \right\}. \quad (2)$$

where $\sum_{j=1}^k q_j \le \frac{k\alpha}{K}$ and where $\hat{S}_k$ is the subset of $S_k$ such that the statistic associated to the permutation would not have rejected before. Formally, $\hat{S}_k$ is the following set of permutations $\hat{S}_k = \{\sigma_{1:k} : \forall m < k, \bar{T}_{N,m}^{(C)}(\sigma_{1:m}) \le B_{N,m}^{(C)}\}$. Note that $q_1$ is not equal to $\alpha/K$. Due to discreteness (we use an empirical quantile over a finite number of values), $q_1$ is chosen equal to $\lfloor \frac{\alpha}{2K} \binom{2N}{N} \rfloor / (\frac{1}{2} \binom{2N}{N})$, and similarly $q_2$ is chosen to be as large as possible while having $q_1 + q_2$ smaller than $2\alpha/K$, and so on for $q_i$ for $3 \le i \le k$.

**Algorithm 1: AdaStop (main algorithm)**

**Parameters:** Agents $A_1, A_2, \dots, A_L$, environment $\mathcal{E}$, comparison pairs $(c_i)_{i \le L}$ where $c_i$ is a couple of two agents that we want to compare. Integers $K, N \in \mathbb{N}^*$, test parameter $\alpha$.

1. Define LNK different seeds $(s_{l,n,k})_{l \le L, n \le N, k \le K}$.

2. Set $\mathbf{C} = \{1, \dots, J\}$ the set of indices for the comparisons we want to do.

3. **for** $k = 1, \dots, K$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;**for** $l = 1 \dots L$ **do**

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Train agent $A_l$ on environment $\mathcal{E}$ with the seeds $s_{l,1,k}, \dots, s_{l,N,k}$.

6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Collect the $N$ evaluations of agent $A_l$.

7. &nbsp;&nbsp;&nbsp;&nbsp;end

8. &nbsp;&nbsp;&nbsp;&nbsp;**while** True **do**

9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Compute the boundaries $B_{N,k}^{(C)}$ from Equation (2).

10. &nbsp;&nbsp;&nbsp;&nbsp;**if** $T_{N,k}^{(C)}(id) > B_{N,k}^{(C)}$ **then**

11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Reject $H_{j_{\max}}$ where $j_{\max} = \arg\max (\bar{T}_{N,k}^{(j)}(id), j \in \mathbf{C})$.

12. &nbsp;&nbsp;&nbsp;&nbsp;**else**

13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Break the while loop.

14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

15. &nbsp;&nbsp;&nbsp;&nbsp;end

16. &nbsp;&nbsp;&nbsp;&nbsp;end

17. &nbsp;&nbsp;&nbsp;&nbsp;**if** $C = \emptyset$ **then** Break the loop and returns the answers.;

18. &nbsp;&nbsp;&nbsp;&nbsp;**if** $k = K$ **then** Then accept all hypotheses remaining in $\mathbf{C}$.

19. end

# 5 Theoretical guarantees

## 5.1 Control on the Family-wise Error

One of the basic properties of two-sample permutation tests is that when the null hypothesis is true, then all permutations are as likely to give a certain value and hence the law given the data is the uniform distribution over all permutations. Then, as a consequence of our choice of $\bar{B}_{N,k}$
**Algorithm 1:** Adaptive stopping to compare two RL agents. This algorithm is expressed in the context of the comparison of RL agents. It is easy to adapt to other types of computational agents.

**Parameters:** Agents $A_1, A_2$, environment $\mathcal{E}$, number of interims $K \in \mathbb{N}^*$, size of an interim $N$, error parameter $\alpha \in (0, 1)$.

1 **for** $k = 1, \dots, K$ **do**
2 &nbsp;&nbsp;&nbsp;&nbsp;**for** $l = 1, 2$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Train agent $A_l$ on environment $\mathcal{E}$ $N$ times, with the seeds $s_{l,(k-1)N+1}, \dots, s_{l,kN}$. This generates $N$ policies $\pi_{l,(k-1)N+1}, \dots, \pi_{l,kN}$
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Collect scores $e_{1,k}(A_l), \dots, e_{N,k}(A_l)$ by running each policy $\pi_{l,(k-1)N+1}, \dots, \pi_{l,kN}$.
5 &nbsp;&nbsp;&nbsp;&nbsp;**end**
6 &nbsp;&nbsp;&nbsp;&nbsp;Compute the boundary $B_{N,k}$ using Equation (3).
7 &nbsp;&nbsp;&nbsp;&nbsp;**if** $T_{N,k}(id) \ge B_{N,k}$ **then**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return reject
9 **end**
10 return accept

If we want to test the equality of $L$ distributions $P_1, P_2, \dots, P_L$, the straightforward way is to do a pairwise comparison. This creates $J = \frac{L(L-1)}{2}$ hypotheses. We let $\mathbf{C} = \{\mathbf{c}_1, \dots, \mathbf{c}_J\}$ be the set of all possible comparisons between the distributions, where $\mathbf{c}_j = (l_1, l_2) \in \mathbf{C}$ denotes a comparison between distributions $P_{l_1}$ and $P_{l_2}$ for $l_1, l_2 \in \{1, 2, \dots, L\}$. Therefore, for $\mathbf{c}_j = (l_1, l_2)$, $H_{\mathbf{c}_j}$ denotes a hypothesis stating that $P_{l_1}$ and $P_{l_2}$ are equal and its alternative $H'_{\mathbf{c}_j}$ is that $P_{l_1}$ and $P_{l_2}$ are different. On the other hand, if one wants to compare an agent to agents whose ranking does not interest us, it may be sufficient to only compare this agent to all the others yielding the $L-1$ comparisons $c_1 = (1, l_2)$ for $2 \le l_2 \le L$.

There are several procedures that can be used to control the FWE. The most famous one is Bonferroni's procedure (Bonferroni, 1936) recalled in the Appendix (Section B). As Bonferroni's procedure can be very conservative in general, we prefer a step-down method (Romano & Wolf, 2003) that performs better in practice because it implicitly estimates the dependence structure of the test statistics. The step-down method is detailed in the next section.

### 3.2.4 Step-down procedure

(Romano & Wolf, 2003) proposed the step-down procedure to solve a multiple hypothesis testing problem. It is defined as follows (for a non group-sequential test): for a permutation $\sigma \in \mathbf{S}_{2N}$ and for $(e_n(j))_{1 \le n \le 2N}$ the random variables being compared in hypothesis $j$, the permuted test statistic of hypothesis $j$ is defined by:

$$T_N^{(j)}(\sigma) = \left| \sum_{n=1}^{N} e_{\sigma(n)}(j) - \sum_{n=N+1}^{2N} e_{\sigma(n)}(j) \right|. \quad (5)$$

This test statistic is extended to any subset of hypothesis $\mathbf{C} \subset \{1, \dots, J\}$ with the following formula:

$$\bar{T}_N^{(\mathbf{C})}(\sigma) = \max_{j \in \mathbf{C}} T_N^{(j)}(\sigma). \quad (6)$$

To specify the test, one compares $\bar{T}_N^{(\mathbf{C})}(id)$ to some threshold value $B_N^{(\mathbf{C})}$, that is: we accept all hypotheses in $\mathbf{C}$ such that $\bar{T}_N^{(\mathbf{C})}(id) \le B_N^{(\mathbf{C})}$. The threshold of the test $B_N^{(\mathbf{C})}$ is defined as the quantile of order $1 - \alpha$ of the permutation law of $\bar{T}_N^{(\mathbf{C})}(\sigma)$:

$$B_N^{(\mathbf{C})} = \inf \left\{ b > 0 : \left( \frac{1}{(2N)!} \sum_{\sigma \in \mathbf{S}_{2N}} 1 \{ \bar{T}_N^{(\mathbf{C})}(\sigma) \ge b \} \right) \le \alpha \right\}. \quad (7)$$

In other words, $B_N^{(\mathbf{C})}$ is the real number such that an $\alpha$ proportion of the values of $\bar{T}_N^{(\mathbf{C})}(\sigma)$ exceeds it, when $\sigma$ enumerates all the permutations of $\{1, \dots, 2N\}$. The permutation test is summarized in Algorithm 2.
as a quantile of the law given the data, the algorithm has a probability to wrongly reject the hypothesis bounded by $\alpha$. This informal statement is made precise in the following theorem.

**Theorem 1 (Controlled family-wise error).** Suppose that $\alpha \in (0, 1)$, and consider the multiple testing problem $H_j: P_j = P_k$ against $H'_j: P_j \neq P_k$ for all the couples $(j, k) \in \{c_1, \dots, c_J\}$. Then, the test resulting from Algorithm 1 has a strong control on the Family-wise error for the multiple test, i.e. if we suppose that all the hypotheses $H_i, i \in \mathbf{I}$ are true and the remainder are false, then

$$ \mathbb{P}(\exists j \in \mathbf{I}: \text{reject } \mathbf{H}_j) \leq \alpha. $$

The proof of Theorem 1 is postponed to the Appendix (Section C).

*Hypotheses of the test:* in Theorem 1 we show that Algorithm 1 tests the equality of the distributions $P_j = P_k$ versus $P_j \neq P_k$, whereas in practice we would prefer to compare the means of the distribution $\mu_j = \mu_k$ versus $\mu_j \neq \mu_k$. Doing the test on distributions is something that is often seen in non-parametric tests (see [21]) and it is justified because without strong concentration assumptions on the distributions, we lack control on the mean of the distributions. On the other hand, we show in the Appendix (Section E) that for $N$ large the test of comparing the means $\mu_j = \mu_k$ versus $\mu_j \neq \mu_k$ has the right guarantees (FWE smaller than $\alpha$), this shows that even though we test the distributions, we also have an approximate test on the means.

*Power of the test:* in Theorem 1 there is no information on the power of the test. We show that, for any $N, K$, the test is of level $\alpha$. Having information on the power allows us to give a rule for the choice of $N$ and $K$ but power analysis in non-parametric setting is in general hard, and it is outside the scope of this article. Instead, we compute empirically the power of our test and show that we perform well empirically compared to non-adaptive approaches. See Section 6.2 for the empirical power study on a Mujoco environment.

## 5.2 Heuristic for early accept for even faster decisions

AdaStop only rejects hypotheses early, it is in addition also possible to accept some hypotheses early. When comparing four agents, we could have Agent $A_1$ performs similarly to $A_2$ and $A_3$ performs similarly to $A_4$. In such a case, AdaStop would use up all the maximum number of comparisons and would stop only when $k = K$ because it will never be able to reject the comparisons $A_1$ vs. $A_2$, and $A_3$ vs. $A_4$. To solve this problem, we *early accept* the equality of agents that are statistically very similar. We proceed by analogy with the early reject methodology and construct a boundary under which the minimum of the test statistics $T_{N,k}^{(j)}$ must be to accept. The details of the implementation and its effect on the Walker environment are given in the Appendix (see Section G).

# 6 Experimental study

In this section, we first illustrate the statistical properties of AdaStop on toy examples for which the performances of agents are simulated. Then, we compare empirically AdaStop to non-adaptive approach. Finally, we exemplify the use of AdaStop on a real case to compare several deep-RL agents, each from a different library. We believe this is a key section demonstrating the strength of our approach from a practitioner perspective.

## 6.1 Toy examples

To start with, let us demonstrate the execution of our algorithm on toy examples. In what follows, we use $\mathcal{N}(\mu, \sigma^2)$ for the normal distribution with the mean $\mu$ and the standard deviation $\sigma$, $t(\mu, \nu)$
**Algorithm 2:** Multiple testing by step-down permutation test.

**Parameters:** $\alpha \in (0, 1)$

**Input:** $e_n(j)$ for $1 \le n \le 2N$ and $j \in C_0 = \{c_1, \dots, c_J\}$.

1. Initialize $C \leftarrow C_0$.

2. while $C \neq \emptyset$ do

3. Compute $T_N^{(C)}(\sigma)$ for every $j$ and every $\sigma$ using Equation (6).

4. Compute $B_N^{(C)}$ using Equation (7).

5. if $\bar{T}_N^{(C)}(\text{id}) \le B_N^{(C)}$ then

6. Accept all the hypotheses $H_j, j \in C$ and exit the loop.

7. else

8. Reject $H_{c_{j_{\max}}}$ where $c_{j_{\max}} = \arg\max_{c_j \in C} T_N^{(j)}(\text{id})$.

9. Define $C = C \setminus \{c_{j_{\max}}\}$

10. end

11. end

Algorithm 2 is initialized with $C = C_0$ containing all the comparisons we want to test. Then, it enters a loop where the test decides to reject or not the most extreme hypothesis in $C$, i.e. $H_{j_{\max}}$ where $j_{\max} = \arg\max_{j \in C} T_N^{(j)}(\text{id})$. Here, $C$ is the current set of neither yet rejected nor accepted hypotheses. If the test statistic $T_N^{(j)}(\text{id})$ for the most extreme hypothesis in $C$ (i.e. $\bar{T}_N^{(C)}(\text{id})$) does not exceed the given threshold $B_N^{(C)}$, then all hypotheses in $C$ are accepted, and the loop is exited. Otherwise, the most extreme hypothesis is discarded from the set $C$ and another iteration is performed until either all remaining hypothesis are accepted, or the set of remaining hypotheses is empty.

The maximum of the statistic in Equation (6) for $\sigma = \text{id}$ allows us to test intersections of hypotheses, while the threshold $B_N^{(C)}$, under the null hypotheses of equality of distribution, allows for strong control on the FWE (i.e. FWE $\le \alpha$). This last result follows from (Romano & Wolf, 2003, Corollary 3) and is a particular case of Theorem 1 for ADAStop. In fact, this procedure is not specific to permutation tests, and it can be used for other tests provided some properties hold on the thresholds $B_N^{(C)}$.

## 4 AdaStop: adaptive stopping for nonparametric group-sequential multiple tests

In this section, we present the construction and the theoretical properties of ADAStop (see Algorithm 3). ADAStop compares the scores of multiple agents in an *adaptive* rather than a *fixed* way. We consider $L \ge 2$ agents $A_1, \dots, A_L$. As above, we let $C_0 = \{c_1, \dots, c_J\} \subseteq \{1, \dots, L\}^2$ be the set of all the comparisons to make between the agents. **I** denotes the set of indices of the true hypotheses among $\{1, \dots, J\}$.

Algorithm 3 specifies ADAStop. ADAStop relies on the test statistic $\bar{T}_{N,k}^{(C)}(\sigma_{1:k})$ defined in equation (9), and the boundary thresholds $B_{N,k}^C$ defined in Equation (10). We discuss a few implementation details in the rest of this section.

*Definition of the test statistic.* Let $e_{1,i}(j), \dots, e_{2N,i}(j)$ denote the $2N$ scores used at interim $i$. They are obtained through the execution of the policies resulting from the training of the two agents $A_{l_1}$ and $A_{l_2}$ for which $c_j = (l_1, l_2)$. We also consider permutations of these scores to define the test statistics $T_{N,k}^{(j)}$ below. For a comparison $j$, we consider a permutation $\sigma_i \in S_{2N}$ at interim $i$ that reshuffles the order of the scores mapping $n \in \{1, \dots, 2N\}$ on $\sigma_i(n) \in \{1, \dots, 2N\}$. Note that if $n \in \{1, \dots, N\}$ and $\sigma_i(n) \in \{N+1, \dots, 2N\}$, we are exchanging a score of the first agent with a score of the second agent in the comparison. It can also happen that instead, we permute two scores of the same agent. The difference between the two cases is
for the t-Student distribution with the mean $\mu$ and the degree of freedom $\nu$, $M_{\frac{1}{2}}^{N}(\mu_1, \sigma_1^2; \mu_2, \sigma_2^2)$ for the mixture of Gaussians $N(\mu_1, \sigma_1^2)$ and $N(\mu_2, \sigma_2^2)$ and $M_{\frac{1}{2}}^{t}(\mu_1, \nu_1; \mu_2, \nu_2)$ for the mixture of t-Student distributions $t(\mu_1, \nu_1)$ and $t(\mu_2, \nu_2)$. In the two examples, we suppose that we compare two agents $A_1$ and $A_2$ for which we know the distributions of their performances. Those two examples are summarized in Fig. 1 (top), where $\Delta$ denotes the distance between two modes of the mixtures ($\Delta = |\mu_1 - \mu_2|$). For both cases, we execute AdaStop with $K = 5$, $N = 5$ and $\alpha = 0.05$. We also limit the maximum number of permutations to $B = 10\,000$. These two cases are executed without early accept. In Fig. 1 (bottom), we plot the rate of rejection of the null hypothesis, stating that compared distributions are the same. By varying $\Delta$ from 0 to 1, we observe the evolution of the power of tests. The bottom line (Case 1) shows that the power of the test stays around 0.05 level for all $\Delta$. Indeed, even though the distributions in the comparison are different, their means remain the same. If the null hypothesis states that the means are the same, then AdaStop will return the correct answer with type I error not larger than 0.11 for $\alpha = 0.05$. This is an illustration of the fact that in addition to performing a test on the distributions, AdaStop approximates the test on the means as shown theoretically in the asymptotic result in Appendix Section E and as discussed at the end of Section 5. In contrast, the top line (Case 2) demonstrates the increasing trend, reaching the level close to 1 after $\Delta = 0.6$, which corresponds to the case when two modes are separated by 3 standard deviations from both sides. To obtain error bars, we have executed each comparison $M = 5\,000$ number of times, and we plot confidence intervals corresponding to $3\sigma/\sqrt{M}$ (more than 99% of confidence) where $\sigma$ is a standard deviation of the test decision. In addition to Cases 1 and 2, we also provide a third experiment with a comparison of 10 agents in Appendix Section H.3.

<figure><img src="image_3.png" /><figcaption>Figure 1: Toy examples 1 and 2 with an illustration of Gaussian mixtures (top) and rejection frequency of null hypothesis according to $\Delta$ (bottom).</figcaption></figure>

## 6.2 Comparison with non-adaptive approach

The article [7] shares the same objective as ours. However, it uses non-adaptive tests unlike AdaStop. We follow their experimental protocol and compare AdaStop and non-adaptive ap-
important for the definition of the following permutation statistic:

$$T_{N,k}^{(j)}(\sigma_{1:k}) = \left| \sum_{i=1}^{k} \left( \sum_{n=1}^{N} e_{\sigma_i(n),i}(j) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(j) \right) \right|. \quad (8)$$

In other words, $T_{N,k}^{(j)}(\sigma_{1:k})$ is the absolute value of the sum of differences of all scores until interim $k$ after consecutive permutations of the concatenation of the two agents scores by $\sigma_1, \dots, \sigma_k \in S_{2N}$. Let $C \subseteq C_0$ be a subset of the set of considered hypothesis and let us denote:

$$\bar{T}_{N,k}^{(C)}(\sigma_{1:k}) = \max_{j \in C} T_{N,k}^{(j)}(\sigma_{1:k}), \quad (9)$$

$\bar{T}_{N,k}^{(C)}(\sigma_{1:k})$ is the test statistic used in ADAStop. The construction of the test is inspired by the permutation tests of Equation (5) used to test intersection of hypotheses as in Equation (6) in the step-down method presented in Section 3.2. Still, it also incorporates group sequential tests from Section 3.2.2 and its test statistic introduced in Equation (2).

*Choice of permutations.* Instead of using all the permutations as we did for now, one may use a random subset among all permutations $S_{N,k} \subset \{\sigma_{1:k}, \forall i \le k, \sigma_i \in S_{2N}\}$ to speed-up computations. The theoretical guarantees persist as long as the choice of the permutations is made independent on the data. Using a small number of permutations will decrease the total power of the test, but with a sufficiently large number of random permutations (typically for the values of $N$ and $K$ we consider, $10^4$ permutations are sufficient) the loss in power is acceptable. We need to include the identity in addition to the random permutations to keep the type I error guarantee (Phipson & Smyth, 2010).

$T_{N,k}$ does not change when the permutation does not exchange any index from $\{1, \dots, N\}$ with an index of $\{N+1, \dots, 2N\}$. In essence, choosing a permutation is equivalent to choosing the signs in $\sum_{n=1}^N e_{\sigma_i(n),i}(j) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(j)$. And because we take the absolute value, there are $\frac{1}{2} \binom{2N}{N}$ possible unique values to $T_{N,1}$ (up to ties when the score distributions are discrete). Then, by enumerating all the permutations for the other interims, there are $\frac{1}{2} \binom{2N}{N}$ possible unique values to $T_{N,k}$.

In practice, we use a parameter $B \in \mathbb{N}$ and the number of permutations used at interim $k$ will be $|S_{N,k}| = m_k = \min\left(B, \frac{1}{2} \binom{2N}{N}\right)$, i.e. whenever possible, we use all the permutations and if this is too much, we use permutations drawn at random.

*Definition of the boundaries.* With these permutations, we define the boundary thresholds $B_{N,k}^{(C)}$ by:

$$B_{N,k}^{(C)} = \inf \left\{ b > 0 : \frac{1}{m_k} \sum_{\sigma \in \hat{S}_{N,k}} 1\{\bar{T}_{N,k}^{(C)}(\sigma_{1:k}) \ge b\} \le q_k \right\}. \quad (10)$$

where $\sum_{j=1}^k q_j \le \frac{k\alpha}{K}$ and where $\hat{S}_{N,k}$ is the subset of $S_{N,k}$ such that the statistic associated to the permutation would not have been rejected before. Formally, $\hat{S}_{N,k}$ is the following set of permutations:

$$\hat{S}_{N,k} = \left\{ \sigma_{1:k} : \forall m < k, \bar{T}_{N,m}^{(C)}(\sigma_{1:m}) \le B_{N,m}^{(C)} \right\}. \quad (11)$$

Note that $q_1$ is not equal to $\alpha/K$. Due to discreteness (we use an empirical quantile over a finite number of values), $q_1$ is chosen equal to $\lfloor \frac{\alpha}{2K} \binom{2N}{N} \rfloor / (\frac{1}{2} \binom{2N}{N})$. Similarly, $q_2$ is chosen to be as large as possible while having $q_1 + q_2 \le 2\alpha/K$. And so on and so forth: in practice this means taking the $q_i$'s as follows:

$$q_i = \lfloor \frac{\alpha i}{2K} \binom{2N}{N} \rfloor / (\frac{1}{2} \binom{2N}{N}) - q_{i-1} \text{ for } 2 \le i \le K, \text{ and } q_0 = 0. \quad (12)$$

One may notice that due to the discrete nature of the permutation distribution, the confidence of the test performed by ADAStop is not $\alpha$ but the sum of the $q_i$'s which may be smaller than the prescribed $\alpha$.
<table><caption>Table 1: Empirical statistical power and effective number of seeds used by AdaStop as a function of the total number of seeds ($N \times K$) when comparing SAC and TD3 on HalfCheetah. The number of permutations is 10 000 and $\alpha$ is 0.05. AdaStop is run 1000 times for every ($N, K$) pair. The shades of blue are proportional to a value in [0, 1] (we use the same color scheme as in [6])</caption><thead><tr><th>N \ K</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>1</td><td>0.0 (2.0)</td><td>0.0 (3.0)</td><td>0.277 (4.0)</td><td>0.465 (5.0)</td><td>0.56 (6.0)</td></tr><tr><td>2</td><td>0.005 (4.0)</td><td>0.33 (6.0)</td><td>0.531 (6.96)</td><td>0.602 (8.345)</td><td>0.704 (9.198)</td></tr><tr><td>3</td><td>0.213 (5.984)</td><td>0.506 (8.085)</td><td>0.627 (10.212)</td><td>0.689 (11.02)</td><td>0.785 (11.52)</td></tr><tr><td>4</td><td>0.371 (7.616)</td><td>0.611 (9.648)</td><td>0.744 (11.7)</td><td>0.82 (12.08)</td><td>0.845 (13.89)</td></tr><tr><td>5</td><td>0.465 (9.044)</td><td>0.691 (11.031)</td><td>0.78 (13.28)</td><td>0.853 (14.27)</td><td>0.884 (14.532)</td></tr><tr><td>6</td><td>0.534 (10.4)</td><td>0.73 (12.306)</td><td>0.837 (14.124)</td><td>0.89 (14.94)</td><td>0.911 (15.978)</td></tr><tr><td>7</td><td>0.599 (11.358)</td><td>0.779 (13.404)</td><td>0.879 (14.916)</td><td>0.92 (15.495)</td><td>0.939 (16.404)</td></tr><tr><td>8</td><td>0.635 (12.322)</td><td>0.818 (13.95)</td><td>0.885 (15.824)</td><td>0.942 (16.03)</td><td>0.961 (17.268)</td></tr></tbody></table>

proaches empirically in terms of statistical power as a function of the sample size (number of seeds). In particular, we use the data they provide for a SAC agent and for a TD3 agent evaluated on HalfCheetah (See Fig. 8 in Appendix). Similarly to [7, Table 15], we compute the empirical statistical power of AdaStop as a function of the number of seeds of the RL algorithms (Table 1). To compute the empirical statistical power for a given number of seeds, we make the hypothesis that the distributions of SAC and TD3 agents evaluations are different, and we count how many times AdaStop decides that one agent is better than the other (number of true positives). As the test is adaptive, we also report the effective number of seeds necessary to make a decision with 0.95 confidence level. For each number of seeds, we have launched AdaStop 1000 times. For example, when comparing SAC and TD3 agents performances on HalfCheetah using AdaStop with $N = 4$ and $K = 5$, the maximum number of seeds that could be used is $N \times K = 20$ without early stopping. However, we observe in Table 1 that when $N = 4$ and $K = 5$, AdaStop can make a decision with a power of 0.82 using only 12 seeds. In [7, Table 15], the minimum number of seeds required to obtain a statistical power of 0.8 when comparing SAC and TD3 agents is 15 when using a t-test, a Welch test, or a bootstrapping test.

## 6.3 AdaStop for Deep Reinforcement Learning

In this section, we use AdaStop to compare four commonly-used Deep RL algorithms on the MuJoCo<fnref n="3" /> ([28]) benchmark for high-dimensional continuous control, as implemented in Gymnasium<fnref n="4" />. More specifically, we train agents on the Ant-v3, HalfCheetah-v3, Hopper-v3, Humanoid-v3, and Walker-v3 environments using PPO from rlfberry [9], SAC from Stable-Baselines3 [26], DDPG from CleanRL [16], and TRPO from MushroomRL [8]. PPO, SAC, DDPG, and TRPO are all deep reinforcement learning algorithms used for high-dimensional continuous control tasks. We chose these algorithms because they are commonly used and represent a diverse set of approaches from different RL libraries. We employ different RL libraries in order to demonstrate the flexibility of AdaStop, as well as to provide examples on how to integrate these popular libraries with AdaStop. On-policy algorithms, such as PPO and TRPO, update their policies based on the current data they collect during training, while off-policy algorithms, such as SAC and DDPG, can learn from any data, regardless of how it was collected. This difference may make off-policy

<footnote n="3">³We use MuJoCo version 2.1, as required by https://github.com/openai/mujoco-py</footnote>

<footnote n="4">⁴https://github.com/Farama-Foundation/Gymnasium</footnote>
**Algorithm 3:** ADASTOP (main algorithm) in the context of the comparison of 2 RL agents. Its application to other types of computational agents is straightforward.

**Parameters:** Agents $A_1, A_2, \dots, A_L$, environment $\mathcal{E}$, comparison pairs $(c_j)_{j \le J}$ where $c_i$ is a couple of agents that we want to compare. Integers $K, N \in \mathbb{N}^*$, test parameter $\alpha$.

1. Set $\mathbf{C} = \{1, \dots, J\}$ the set of indices for the comparisons to perform.

2. for $k = 1, \dots, K$ do

3. for $l = 1 \dots L$ do

4. Train $N$ times agent $A_l$ on environment $\mathcal{E}$. This generates $N$ policies.

5. Collect the $N$ scores of the $N$ policies.

6. end

7. while True do

8. Compute the boundaries $B_{N,k}^{(\mathbf{C})}$ using Equation (10).

9. if $T_{N,k}^{(\mathbf{C})}(\mathrm{id}) > B_{N,k}^{(\mathbf{C})}$ then

10. Reject $H_{j_{\max}}$ where $j_{\max} = \arg\max(\bar{T}_{N,k}^{(j)}(\mathrm{id}), \quad j \in \mathbf{C})$.

11. $\mathbf{C} = \mathbf{C} \setminus \{j_{\max}\}$

12. else

13. Exit the while loop.

14. end

15. end

16. if $\mathbf{C} = \emptyset$ then Exit the loop and return the decision of the test.

17. if $k = K$ then Exit the loop and accept all hypotheses remaining in $\mathbf{C}$.

18. end

## 4.1 Theoretical guarantees of AdaStop

One of the basic properties of two-sample permutation tests is that when the null hypothesis is true, then all permutations are as likely to give a certain value and permuting the sample should not change the test statistic too much. Following our choice of $\bar{B}_{N,k}$ as a quantile of the law given the data, the algorithm has a probability to wrongly reject the hypothesis bounded by $\alpha$. This informal statement is made precise in the following theorem.

**Theorem 1 (Controlled family-wise error).** Let $\alpha \in (0, 1)$, and consider the multiple testing problem $H_j : P_{l_1} = P_{l_2}$ against $H'_j : P_{l_1} \neq P_{l_2}$ for all the couples $c_j = (l_1, l_2) \in \{c_1, \dots, c_J\}$. Then, the test resulting from Algorithm 3 has a strong control on the family-wise error for the multiple test, i.e. if we suppose that all the hypotheses $H_i, i \in \mathbf{I}$ are true and the others are false, then

$$ \mathbb{P}(\exists j \in \mathbf{I}: \text{reject } H_j) \le \alpha. $$

The proof of Theorem 1 is given in the Appendix (Section C).

*Hypotheses of the test:* in Theorem 1 we show that Algorithm 3 tests the equality of the distributions $P_{l_1} = P_{l_2}$ versus $P_{l_1} \neq P_{l_2}$, whereas in practice we would prefer to compare the means of the distribution $\mu_{l_1} = \mu_{l_2}$ versus $\mu_{l_1} \neq \mu_{l_2}$, see Section 2.5 for a discussion on the differences between the two. We show in the Appendix E that for large $N$, the test comparing the means $\mu_{l_1} = \mu_{l_2}$ versus $\mu_{l_1} \neq \mu_{l_2}$ has the right guarantees (FWE smaller than $\alpha$). This shows that even though we test the distributions, we also have an approximate test on the means. More precisely, we show the following in the Appendix E for the comparison of the means of two distributions.

**Theorem 2.** Suppose that $\alpha \in (0, 1)$, suppose that $P$ and $Q$ both have a finite variance, and consider the two-sample testing problem $H_0 : \mathbb{E}_P[X] = \mathbb{E}_Q[X]$ against $H'_0 : \mathbb{E}_P[X] \neq \mathbb{E}_Q[X]$. Then, the test resulting from Algorithm 3 has an asymptotic type I error of $\alpha$

$$ \lim_{N \to \infty} \mathbb{P}_{H_0} (\text{reject } H_0) = \alpha. $$
<figure><img src="image_4.png" /><figcaption>Figure 2: AdaStop decision tables for each MuJoCo environment, and the budget used to make these decisions (bottom right). See Appendix H.5 for further details.</figcaption></figure>

algorithms more sample-efficient but less stable than on-policy algorithms. Furthermore, SAC typically outperforms DDPG in continuous control robotics tasks due to its ability to handle stochastic policies, while DDPG restricts itself to deterministic policies [15]. Finally, PPO is generally accepted to perform better than TRPO in terms of cumulative reward [10]. For each algorithm, we fix the hyperparameters to those used by the library authors in their benchmarks for one of the MuJoCo environments. In Appendix H.5, we provide the values that were used and further discuss the experimental setup.

We compare the four agents in each environment using AdaStop with $N = 5$ and $K = 6$. Fig. 2 shows the AdaStop decision tables in each environment, as well as the number of evaluations per agent and environment. As expected, SAC ranks first in every environment. In contrast, DDPG is ranked last in four out of five environments. Such performance may be a product of the restriction to deterministic policies, which hurts exploration in high-dimensional continuous control environments such as the MuJoCo benchmarks. Furthermore, we observe that the expected ordering between PPO and TRPO is generally respected, with TRPO outperforming PPO in only one environment. Finally, we note that PPO performs particularly well in some environments with its performance comparable to SAC, while also being the worst-performing algorithm for HalfCheetah-v3. Overall, the AdaStop rankings in these experiments are not unexpected.

Moreover, our experiments demonstrate that AdaStop can make decisions with fewer evaluations, thus reducing the computational cost of comparing Deep RL agents. For instance, as expected, SAC outperformed other agents on the environment HalfCheetah-v3, and AdaStop required only five evaluations to make all decisions involving SAC. Additionally, we observed that the decisions requiring the entire budget of $NK = 30$ evaluations were the ones in which AdaStop determined that the agents were equivalent in terms of their performance. With the early-accept heuristic proposed in 5.2 and detailed in the Appendix (Section G), this process can be sped-up and for instance in the Walker2d-v3 environment, early accept allows us to take all the decisions after only 10 seeds.
The proof of Theorem 2 is given in the Appendix (Section E).

*Power of the test:* in Theorem 1, there is no information on the power of the test. For any $N, K$, we show that, the FWE is upper-bounded by $\alpha$. In the appendix E, we establish Theorem 3 that can be used to get a control on the asymptotic power. On the other hand, having non-asymptotic information on the power would allow us to give a rule for the choice of $N$ and $K$. However, non-asymptotic power analysis in a nonparametric setting is in general hard, and it is beyond the scope of this article. Instead, we compute empirically the power of our test and show that it performs well empirically compared to non-adaptive approaches. See Section 5.2 for the empirical power study on a Mujoco environment.

# 5 Experimental study

This section demonstrates ADASTOP from a practitioner perspective. First, we illustrate the statistical properties of ADASTOP on toy examples in which the scores of the agents are sampled from known distributions. Then, we compare empirically ADASTOP to non-adaptive approaches. Finally, we exemplify the use of ADASTOP on a real case to compare a set of Deep RL agents.

To reproduce the experiments of this paper, the python code is freely available on GitHub at https://github.com/TimotheeMathieu/Adaptive_stopping MC RL.

## 5.1 Toy examples

To start with, let us consider a toy example. In what follows, let us denote: (i) $\mathcal{N}(\mu, \sigma^2)$ the normal distribution with mean $\mu$ and standard deviation $\sigma$, (ii) $M_f^N(\mu_1, \sigma_1^2; \mu_2, \sigma_2^2)$ the mixture of 2 Gaussian distributions $\mathcal{N}(\mu_1, \sigma_1^2)$ and $\mathcal{N}(\mu_2, \sigma_2^2)$ with weights $f$ and $1-f$ respectively.

We compare two agents $A_1$ and $A_2$ for which we know the distributions of their scores. We consider three cases in Fig. 4. In the 3 cases, the scores of agent $A_1$ are drawn from $\mathcal{N}(0, 0.01)$ whereas the scores of the agent $A_2$ are drawn from a certain mixture detailed below. We use a hyperparameter $\Delta$ which is the distance between the two modes of the mixture ($\Delta = |\mu_1 - \mu_2|$). Our goal is to compare the performance of agent $A_1$ with the performance of agent $A_2$ and we study the outcome of ADASTOP when $\Delta$ is increasing from 0 to 1. In the first case (upper-left part), the scores of $A_2$ are drawn from $M_{\frac{N}{2}}(-\Delta/2, 0.01; \Delta/2, 0.01)$: in this situation, the means of both distributions are both equal to 0, but the distributions are different (except when $\Delta = 0$). In the second case (upper-right part), the scores of $A_2$ are drawn from $M_{\frac{N}{2}}(0, 0.01; \Delta, 0.01)$: in this situation, as $\Delta$ increases, the means of the two distributions get more and more apart making the rejection of the null hypothesis easier and easier. In the third case (lower part), the scores of $A_2$ are drawn from $M_{0.9}^N(-0.1\Delta, 0.01; 0.9\Delta, 0.01)$: in this situation, the distributions are different but their means are both 0. In all three cases, we run ADASTOP with $K = 5$, $N = 5$ and $\alpha = 0.05$. We also limit the maximum number of permutations to $B = 10^4$. At the bottom of each subfigure of Figure 4, a color bar indicates the rejection rate of the null hypothesis that the compared distributions are the same for $\Delta \in [0, 1]$. By varying $\Delta$ from 0 to 1, we observe the evolution of the power of the test, i.e. the probability of rejecting the null hypothesis when it is indeed false. Figure 4a shows that the error of the test remains around 0.05 for all $\Delta$ (it is at most 0.1 for the most extreme case). Indeed, even though the distributions are different, their means remain the same. If the null hypothesis states that the means are the same, then ADASTOP will return the correct answer with type I error not larger than 0.095 (see Figure 4a) for $\alpha = 0.05$, which is larger than $\alpha$ due to the fact that the test for comparison of the means is asymptotic. This is an illustration of the fact that in addition to performing a test on the distributions, ADASTOP approximates the test on the means as shown theoretically in the asymptotic result in Appendix E and as discussed at the end of Section 4.1. In contrast, Figure 4b demonstrates an increasing trend, reaching a confidence level close to 1 when $\Delta > 0.6$, which corresponds to the case where the two modes are separated by 3 standard deviations from both sides. Finally, in Figure 4c, we use a distribution made of an unbalanced mixture of 2 normal distributions. This is meant to model an agent that does not perform optimally except in some rare cases (e.g. the agent has a score around 0 for 90% of the evaluation runs). As in case 1, the mean of the scores for both agents is 0 and ADASTOP accepts the equality most of the time, with an error of 0.2 in the most extreme case which we think is acceptable given the difficulty of this setting.
# 7 Conclusion and future works

In this paper, we introduce AdaStop which is a sequential group test aiming at ranking the performance of agents. Our goal is to provide statistical grounding to define the number of times a set of agents should be run to be able to confidently rank them, up to some level $\alpha$. This is the first such test, and we think this is a major contribution to computational studies in reinforcement learning and other domains. Using AdaStop is simple, and we provide open source software to use it. From a statistical point of view, we have been able to demonstrate the soundness of AdaStop as a statistical test. Experiments demonstrate how AdaStop may be used in practice, even in a retrospective manner using logged data. The next step of our study is the case where we compare agents facing a collection of different tasks, such as the Atari games. Properly dealing with such experimental settings require a careful statistical analysis. Moreover, additional theoretical guarantees for the early accept and to control the power of AdaStop would also greatly improve its interpretability.

# 8 Ethical statement

We believe that there are no ethical concerns with our work. On the contrary, our work provides theory and tools for reproducible and open research. We hope AdaStop will be used for RL research so that, moving forward, one can be confident when saying a new agent is better than another. As a side-note, this paper is also a step towards “green AI” by trying to use only the necessary amount of computation to make a decision.

# References

[1] Agarwal, R., Schwarzer, M., Castro, P.S., Courville, A.C., Bellemare, M.: Deep reinforcement learning at the edge of the statistical precipice. Advances in neural information processing systems 34, 29304–29320 (2021)

[2] Bellemare, M.G., Naddaf, Y., Veness, J., Bowling, M.: The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research 47, 253–279 (2013)

[3] Benjamini, Y., Hochberg, Y.: Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal statistical society: series B (Methodological) 57(1), 289–300 (1995)

[4] Bonferroni, C.: Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commerziali di Firenze 8, 3–62 (1936)

[5] Chung, E., Romano, J.P.: Exact and asymptotically robust permutation tests. The Annals of Statistics 41(2), 484 – 507 (2013). https://doi.org/10.1214/13-AOS1090, https://doi.org/10.1214/13-AOS1090

[6] Colas, C., Sigaud, O., Oudeyer, P.Y.: How many random seeds? statistical power analysis in deep reinforcement learning experiments. arXiv preprint arXiv:1806.08295 (2018)

[7] Colas, C., Sigaud, O., Oudeyer, P.Y.: A hitchhiker’s guide to statistical comparisons of reinforcement learning algorithms. arXiv preprint arXiv:1904.06979 (2019)
To obtain an estimation of the error, we have executed each comparison $M = 5 \cdot 10^3$ times, and we plot confidence intervals corresponding to $3\sigma/\sqrt{M}$ (confidence larger than 99%) where $\sigma$ is the standard deviation of the test decision. In addition to cases 1, 2 and 3, we also provide a fourth experiment with a comparison of 10 agents in Appendix H.1.

<figure><img src="image_6.png" /><figcaption>Figure 4: Toy examples. For each of these 3 cases, we plot the distribution of scores of each of the 2 agents that are compared, as well as the frequency of rejection of the null hypothesis. Please, refer to the text for details.</figcaption></figure>

## 5.2 Comparison with non-adaptive approach

(Colas et al., 2019) share the same objective with us. However, they use non-adaptive tests unlike ADASTOP. We follow their experimental protocol and compare ADASTOP and non-adaptive approaches empirically in terms of statistical power as a function of the sample size (number of scores). In particular, we use the data<fnref n="4" /> they provide for a SAC agent and for a TD3 agent evaluated on HalfCheetah (see Fig. 12 in the Appendix). Similarly to (Colas et al., 2019, Table 15), we compute the empirical statistical power of ADASTOP as a function of the number of scores of the RL agents (Table 2). To compute the empirical statistical power for a given number of scores, we make the hypothesis that the distribution of SAC and TD3 agents scores are different, and we count how many times ADASTOP decides that one agent is MLB than the other (number of true positives). As the test is adaptive, we also report the effective number of scores that are necessary

<footnote n="4">⁴available at https://github.com/flowersteam rl_stats/tree/master/data.</footnote>
[8] D'Eramo, C., Tateo, D., Bonarini, A., Restelli, M., Peters, J.: Mushroomr: Simplifying reinforcement learning research. Journal of Machine Learning Research **22**(131), 1-5 (2021), http://jmlr.org/papers/v22/18-056.html

[9] Domingues, O.D., Flet-Berliac, Y., Leurent, E., Ménard, P., Shang, X., Valko, M.: rlberry - A Reinforcement Learning Library for Research and Education (10 2021). https://doi.org/10.5281/zenodo.5544540, https://github.com/rlberry-py/rlberry

[10] Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., Madry, A.: Implementation matters in deep policy gradients: A case study on ppo and trpo. arXiv preprint arXiv:2005.12729 (2020)

[11] Fisher, R.A.: Design of experiments. British Medical Journal 1 (3923), 554 (1936)

[12] Flet-Berliac, Y., Ouhamma, R., Maillard, O.A., Preux, P.: Learning value functions in deep policy gradients using residual variance. In: ICLR 2021-International Conference on Learning Representations (2021)

[13] Goodman, S.N., Fanelli, D., Ioannidis, J.P.: What does research reproducibility mean? Science translational medicine **8**(341), 341ps12-341ps12 (2016)

[14] Gordon Lan, K., DeMets, D.L.: Discrete sequential boundaries for clinical trials. Biometrika **70**(3), 659-663 (1983)

[15] Haarnoja, T., Zhou, A., Abbeel, P., Levine, S.: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In: International conference on machine learning. pp. 1861-1870. PMLR (2018)

[16] Huang, S., Dossa, R.F.J., Ye, C., Braga, J., Chakraborty, D., Mehta, K., Araújo, J.G.: Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms. Journal of Machine Learning Research **23**(274), 1-18 (2022), http://jmlr.org/papers/v23/21-1342.html

[17] Jennison, C., Turnbull, B.W.: Group sequential methods with applications to clinical trials. CRC Press (1999)

[18] Kaufmann, E., Koolen, W.M.: Mixture martingales revisited with applications to sequential tests and confidence intervals. The Journal of Machine Learning Research **22**(1), 11140-11183 (2021)

[19] Klink, P., Yang, H., D'Eramo, C., Peters, J., Pajarinen, J.: Curriculum reinforcement learning via constrained optimal transport. In: Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., Sabato, S. (eds.) Proceedings of the 39th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 162, pp. 11341-11358. PMLR (17-23 Jul 2022), https://proceedings.mlr.press/v162/klink22a.html

[20] Lattimore, T., Szepesvári, C.: Bandit algorithms. Cambridge University Press (2020)

[21] Lehmann, E.L., Romano, J.P., Casella, G.: Testing statistical hypotheses, vol. 3. Springer (2005)

[22] Mehta, C.R., Patel, N., Senchaudhuri, P., Tsiatis, A.: Exact permutational tests for group sequential clinical trials. Biometrics pp. 1042-1053 (1994)
<table><caption>Table 2: Average empirical statistical power and, in parentheses, effective number of scores used by ADASTOP as a function of the total number of scores ($N \times K$) when comparing SAC and TD3 agents on Mujoco HalfCheetah task. The number of permutations $B$ is set to $10^4$ and $\alpha$ is set to 0.05. ADASTOP is run $10^3$ times for each ($N, K$) pair. The shades of blue are proportional to the power, a value in [0, 1] (we use the same color scheme as in (Colas et al., 2018)). It can seem strange that the power is 0 in some cases. This situation is explained in the text.</caption><thead><tr><th>N \ K</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>1</td><td>0.0 (2.0)</td><td>0.0 (3.0)</td><td>0.277 (4.0)</td><td>0.465 (5.0)</td><td>0.56 (6.0)</td></tr><tr><td>2</td><td>0.005 (4.0)</td><td>0.33 (6.0)</td><td>0.531 (6.96)</td><td>0.602 (8.345)</td><td>0.704 (9.198)</td></tr><tr><td>3</td><td>0.213 (5.984)</td><td>0.506 (8.085)</td><td>0.627 (10.212)</td><td>0.689 (11.02)</td><td>0.785 (11.52)</td></tr><tr><td>4</td><td>0.371 (7.616)</td><td>0.611 (9.648)</td><td>0.744 (11.7)</td><td>0.82 (12.08)</td><td>0.845 (13.89)</td></tr><tr><td>5</td><td>0.465 (9.044)</td><td>0.691 (11.031)</td><td>0.78 (13.28)</td><td>0.853 (14.27)</td><td>0.884 (14.532)</td></tr><tr><td>6</td><td>0.534 (10.4)</td><td>0.73 (12.306)</td><td>0.837 (14.124)</td><td>0.89 (14.94)</td><td>0.911 (15.978)</td></tr><tr><td>7</td><td>0.599 (11.358)</td><td>0.779 (13.404)</td><td>0.879 (14.916)</td><td>0.92 (15.495)</td><td>0.939 (16.404)</td></tr><tr><td>8</td><td>0.635 (12.322)</td><td>0.818 (13.95)</td><td>0.885 (15.824)</td><td>0.942 (16.03)</td><td>0.961 (17.268)</td></tr></tbody></table>

to make a decision with 0.95 confidence level. For each number of scores, we have run ADASTOP $10^3$ times. For example, when comparing the scores of SAC and TD3 on HalfCheetah using ADASTOP with $N = 4$ and $K = 5$, the maximum number of scores that is used is $N \times K = 20$. However, we observe in Table 2 that when $N = 4$ and $K = 5$, ADASTOP can make a decision with a power of 0.82 using only 12 scores. In (Colas et al., 2019, Table 15), the minimum number of scores required to obtain a statistical power of 0.8 when comparing SAC and TD3 agents is 15 when using either a t-test, or a Welch test, or a bootstrapping test. With this example, we first show that being an adaptive test, ADASTOP may save computations. We also show that as long as the scores of agents are made available, ADASTOP can use them to provide a statistically sound conclusion, and as such, ADASTOP may be used to assess the initial conclusions, hopefully strengthening them with a statistically significant argument.

*Remark:* as already mentioned above, when $N$ and $K$ are both small, it can happen that ADASTOP does not allow an error up to $\alpha$ but it will restrict itself to a smaller error and this will lead to a much lower power. For instance, if $N = 2, K = 2, \alpha = 0.05$ for the first interim, we have $\lfloor \frac{1}{2} \binom{2N}{N} \alpha / 2 \rfloor = 0$ hence the first boundary is necessarily infinity and ADASTOP never rejects, e.g. with the notations of Equation (12), $q_1 = 0$. Then at the second interim $\lfloor \frac{1}{2} \binom{2N}{N} \alpha / 2 \rfloor = 3$ and we use $q_1 + q_2 = \lfloor \frac{1}{2} \binom{2N}{N} \alpha / 2 \rfloor / \lfloor \frac{1}{2} \binom{2N}{N} \alpha \rfloor \approx 0.041$ which is smaller than the 5% that we allow for the test, hence the test is more conservative than needed. This is an extreme case happening in the first few interim s when $N$ is small explaining some values in Table 2 that may seem strange at first glance (for instance the power is equal to 0 when $N = 1$ and $K \le 3$).

## 5.3 AdaStop for Deep Reinforcement Learning

In this section, we use ADASTOP to compare four commonly-used Deep RL agents on the MuJoCo$^5$ (Todorov et al., 2012) benchmark for high-dimensional continuous control. We use the Gymnasium$^6$ implementation. More specifically, we train agents on the Ant-v3, HalfCheetah-v3, Hopper-v3, Humanoid-v3, and Walker-v3 environments using PPO from rllberry (Domingues et al., 2021), SAC from Stable-Baselines3 (Raffin et al., 2021), DDPG from CleanRL (Huang et al., 2022), and TRPO from MushroomRL (D’Eramo et al., 2021). PPO, SAC, DDPG, and TRPO are Deep RL algorithms used for continuous control tasks. We choose these algorithms because they are commonly used and they represent a diverse set of approaches from different RL libraries. We use different RL libraries in order to demonstrate the flexibility of ADASTOP, as well as to provide examples on how to use these popular libraries with ADASTOP.

On-policy algorithms, such as PPO and TRPO, update their policies based on the current data they collect during training, while off-policy algorithms, such as SAC and DDPG, can learn from any data, regardless of how it was collected. This difference may make off-policy algorithms more sample-efficient but less stable

<footnote>$^5$We use MuJoCo version 2.1, as required by https://github.com/openai/mujoco-py.</footnote>

<footnote>$^6$https://github.com/Farama-Foundation/Gymnasium.</footnote>
[23] Pampallona, S., Tsiatis, A.A.: Group sequential designs for one-sided and two-sided hypothesis testing with provision for early stopping in favor of the null hypothesis. Journal of Statistical Planning and Inference **42**(1-2), 19-35 (1994)

[24] Pitman, E.J.: Significance tests which may be applied to samples from any populations. Supplement to the Journal of the Royal Statistical Society **4**(1), 119-130 (1937)

[25] Pocock, S.J.: Group sequential methods in the design and analysis of clinical trials. Biometrika **64**(2), 191-199 (1977)

[26] Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., Dormann, N.: Stable-baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research **22**(268), 1-8 (2021), http://jmlr.org/papers/v22/20-1364.html

[27] Romano, J.P., Wolf, M.: Exact and approximate stepdown methods for multiple hypothesis testing. SSRN Journal Electronic Journal (2003). https://doi.org/10.2139/ssrn.563267, https://doi.org/10.2139/2Fssrn.563267

[28] Todorov, E., Erez, T., Tassa, Y.: Mujoco: A physics engine for model-based control. In: 2012 IEEE/RSJ international conference on intelligent robots and systems. pp. 5026-5033. IEEE (2012)

[29] Tukey, J.W.: The problem of multiple comparisons. Multiple comparisons (1953)

[30] Wald, A.: Sequential Tests of Statistical Hypotheses. The Annals of Mathematical Statistics **16**(2), 117-186 (1945). https://doi.org/10.1214/aoms/1177731118, https://doi.org/10.1214/aoms/1177731118
<figure><img src="image_7.png" /><figcaption>Figure 5: ADASTOP decision tables for each MuJoCo environment, and the budget used to make these decisions (bottom right). The notation $→≥↓$ means that the agent which name is on the left of the row is MLB than the agent which name is at the bottom of the column. See Appendix H.2 for further details.</figcaption></figure>

than on-policy algorithms. Furthermore, SAC typically outperforms DDPG in continuous control robotics tasks due to its ability to handle stochastic policies, while DDPG restricts itself to deterministic policies (Haarnoja et al., 2018). Finally, PPO is generally considered performing better than TRPO in terms of cumulative reward (Engstrom et al., 2020).

For each algorithm, we fix the hyperparameters to those used by the library authors in their benchmarks for one of the MuJoCo environments. Appendix H.2 lists the values that were used and we further discuss the experimental setup. We compare the four agents in each environment using ADASTOP with $N = 5$ and $K = 6$. Fig. 5 shows the ADASTOP decision tables for each environment, as well as the number of scores per agent and environment. As expected, SAC is MLB than all the other agents in each environment. In contrast, all agents are MLB than DDPG; this may be due to the restriction to deterministic policies which hurts exploration in high-dimensional continuous control environments such as the MuJoCo benchmarks. Furthermore, we observe that the expected ordering between PPO and TRPO is generally respected, with TRPO MLB than PPO in only one environment. Finally, we note that PPO performs particularly well in some environments obtaining scores that are comparable to those of SAC, while also being the worst-performing algorithm on HalfCheetah-v3. Overall, the ADASTOP rankings in these experiments are not unexpected.

Moreover, our experiments demonstrate that ADASTOP can make decisions with fewer scores, thus reducing the computational cost of comparing Deep RL agents. For instance, as expected, SAC is MLB than all the other agents on the environment HalfCheetah-v3, and ADASTOP required only five scores to make all decisions involving SAC. Additionally, we observed that the decisions requiring the entire budget of $NK = 30$ scores were the ones in which ADASTOP determined that the agents were equivalent in terms of their scores. This decision process can be sped-up by using the early accept heuristic which is presented in the Appendix (Section F). For instance in the Walker2d-v3 environment, early accept allows us to take all the decisions after only 10 scores have been collected for each agent.

# 6 Conclusion and future works

In this paper, we introduce ADASTOP which is a sequential group test aiming at ranking agents based on their practical performance. ADASTOP may be applied in various fields where the performance of algorithms are random, such as machine learning, or optimization. Our goal is to provide statistical grounding to
# A Index of notations

• $\mathbb{E}[X]:$ expectation of the random variable $X$.

• $\mathfrak{S}_n$: set of all the permutations of $\{1, \dots, n\}$.

• $H_j$: denotes hypothesis $j$ in a multiple test, $H'_j$ denotes the alternative of hypothesis $H_j$.

• $\sigma$: generic notation for a permutation. Element of $\mathfrak{S}_n$ for some $n \in \mathbb{N}^*$.

• $e_i(j)$ or $e_{i,k}(j)$: performance measure that corresponds to run number $i$ when doing the test for comparison $j$. See the beginning of Section 2.

• $\sigma_{1:k}$: shorthand for the permutation that applies each $\sigma_i$ to the elements $(e_{n,i})_{n \le 2N}$, for interims from $i=1$ to $i=k$.

• $T_N(\sigma)$ and $T_{N,k}^{(j)}(\sigma)$: test statistics. See Equation (9) and Equation (1).

• $c_j$: denotes a comparison. This is a couple in $\{1, \dots, L\}^2$.

• $j$: shorthand for denoting comparison $c_j$.

• $C_0$: set of all the comparisons done in AdaStop.

• $C$: current set of undecided comparisons in AdaStop, a subset of $C_0$.

• $C_k$: state of $C$ at interim $k$ in AdaStop.

• $\mathbf{I}$: set of true hypotheses.

• FWE: family-wise error, see Definition 1.

• $\mathcal{N}(\mu, \sigma^2)$: law of a Gaussian with mean $\mu$ and variance $\sigma^2$.

• $t(\mu, \nu)$: law of a translated Student distribution with center of symmetry $\mu$ and $\nu$ degrees of freedom.

• $M_{\frac{1}{2}}^{\mathcal{N}}(\mu_1, \sigma_1^2; \mu_2, \sigma_2^2)$: mixture of two normal distributions.

• $M_{\frac{1}{2}}^{t}(\mu_1, \nu_1; \mu_2, \nu_2)$: mixture of two Student distributions.

• $\mathbb{P}_{H_j, j \in \mathbf{I}}$: probability distribution when $H_j, j \in \mathbf{I}$ are true and $H_j, j \notin \mathbf{I}$ are false.

# B Recap on hypothesis testing

To be fully understood, this paper requires the knowledge of some notions of statistics. In the hope of widening the potential audience of this paper, we provide a short recap of essential notions of statistics related to hypothesis testing.
define the number of times a set of agents should be run to be able to confidently rank them, up to some
confidence level α. This is the first such test, and we think this is an important contribution to computational
studies in reinforcement learning and other domains. From a statistical point of view, we have been able
to demonstrate the soundness of ADASTOP as a statistical test. Using ADASTOP is simple. We provide
open source software to use it. Experiments demonstrate how ADASTOP may be used in practice, even in a
retrospective manner using logged data: this allows one to diagnose prior studies in a statistically significant
way, hopefully confirming their conclusions, possibly showing that the same conclusions could have been
obtained with fewer computations.

Currently, ADASTOP considers a set of agents facing one single task. Our next step will be to extend the test to experimental settings where a set of agents are compared on a collection of tasks, such as the set of Atari games or the set of Mujoco tasks in reinforcement learning. Properly dealing with such experimental settings requires a careful statistical analysis. Moreover, additional theoretical guarantees for the early accept and the non-asymptotic control of the power, FWE, and directional error of ADASTOP for the comparison of means would also greatly improve the interpretability of the conclusions of ADASTOP. We are currently investigating these questions.

As this is illustrated in the experimental section, ADASTOP can be run on already collected scores: we do not need to run anew the agents as long as scores are available. This remark calls for an effort of the community to make their scores publicly available so that it is easy for anyone to compare one's new agent with others already proposed.

## Acknowledgments

The authors would like to thank the action editor and the reviewers for their many remarks that guided us to make this paper clearer, more legible, and to improve the rigor of the exposition. O-A.Maillard and Ph.Preux acknowledge the support of the Métropole Européenne de Lille (MEL), ANR, Inria, Université de Lille, through the AI chair Apprenf number R-PILOTE-19-004-APPRENF. R.Della Vecchia acknowledges the funding received by the CHIST-ERA Project Causal eXplainations in Reinforcement Learning – CausalXRL<fnref n="7" />. A.Shilova acknowledges the funding from the HPC-BigData Inria Project Lab<fnref n="8" />. T.Mathieu acknowledges the funding received by the SR4SG Inria exploratory action<fnref n="9" />. M.Centa Medeiros and H.Kohler acknowledge the funding of their Ph.D.by an ANR AI.PhD@Lille grant. This research is also partially supported by the CornellIA Hauts-de-France project. All the authors acknowledge the Scool research group for its outstanding working environment.

## References

Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Marc Bellemare. Deep reinforcement learning at the edge of the statistical precipice. *Advances in neural information processing systems*, 34:29304–29320, 2021.

Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. *Journal of Artificial Intelligence Research*, 47:253–279, 2013.

Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilità. *Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commerziali di Firenze*, 8:3–62, 1936.

EunYi Chung and Joseph P. Romano. Exact and asymptotically robust permutation tests. *The Annals of Statistics*, 41(2):484 – 507, 2013. doi: 10.1214/13-AOS1090. URL https://doi.org/10.1214/13-AOS1090.

Cédric Colas, Olivier Sigaud, and Pierre-Yves Oudeyer. How many random seeds? statistical power analysis in deep reinforcement learning experiments. *arXiv preprint arXiv:1806.08295*, 2018.

<footnote n="7">7. https://www.chistera.eu/projects/causalxrl</footnote>

<footnote n="8">8. https://project.inria.fr/hpcbigdata/</footnote>

<footnote n="9">9. https://project.inria.fr/sr4sg/home/</footnote>
## B.1 Type I and type II error

In its most simple form, a statistical test is aimed at deciding, whether a given collection of data $X_1, \dots, X_N$ adheres to some hypothesis $H_0$ (called the null hypothesis), or if it is a better fit for an alternative hypothesis $H_1$. Typically, $H_0: \mu = \mu_0$ and $H_1: \mu \neq \mu_0$ where $\mu$ is the mean of the distribution of $X_1, \dots, X_N$. Because $\mu$ is unknown, it has to be estimated using the data, and often that is done using the empirical mean $\hat{\mu} = \frac{1}{N} \sum_{i=1}^{N} X_i$. $\hat{\mu}$ is random and some deviation from $\mu$ is to be expected, the theory of hypothesis tests is concerned in finding a threshold $c$ such that if $|\hat{\mu} - \mu_0| > c$ then we say that $H_0$ is false because the deviation is more than what was expected by the theory.

A slightly more complex problem is to consider two samples $X_1, \dots, X_N$ and $Y_1, \dots, Y_N$ and do a two-sample test deciding whether the mean of the distribution of the $X_i$'s is equal to the mean of the distribution of the $Y_i$'s.

In both cases, the result of a test is either accept $H_0$ or reject $H_0$. This answer is not a ground truth: there is some probability that we make an error. However, this probability of error is often controlled and can be decomposed in type I error and type II errors (often denoted $\alpha$ and $\beta$ respectively, see Table 2). Please note that the problem is not symmetric: failing to

<table><caption>Table 2: Type I and type II error.</caption><thead><tr><th></th><th>$H_0$ is true</th><th>$H_0$ is false</th></tr></thead><tbody><tr><td>We accept $H_0$</td><td>No error</td><td>type II error $\beta$</td></tr><tr><td>We reject $H_0$</td><td>type I error $\alpha$</td><td>No error</td></tr></tbody></table>

reject the null hypothesis does not mean that the null hypothesis is true. It can be that there is not enough data to reject $H_0$.

## B.2 Multiple tests and FWE

When doing simultaneously several statistical tests, one must be careful that the error of each test accumulate and if one is not cautious, the overall error may become non-negligible. As a consequence, multiple strategies have been developed to deal with multiple testing problem.

To deal with the multiple testing problem, the first step is to define what is an error. There are several definitions of error in multiple testing, among which is the False discovery rate, which measures the expected proportion of false rejections. Another possible measure of error is the Family-wise error (this is the error we use in this article) and which is defined as the probability to make at least one false rejection:

$$ \text{FWE} = \mathbb{P}_{H_j, j \in \mathbf{I}} (\exists j \in \mathbf{I}: \text{reject } H_j), $$

where $\mathbb{P}_{H_j, j \in \mathbf{I}}$ is used to denote the probability when $\mathbf{I}$ is the set of indices of the hypotheses that are actually true (and $\mathbf{I}^c$ the set of hypotheses that are actually false). To construct a procedure with FWE smaller than $\alpha$, the simplest method is perhaps Bonferroni correction [4] in which one would use one statistical test for each of the $J$ couple of hypotheses to be tested. And then, one would tune each hypothesis test to have a type I error $\alpha/J$ where $J$ is the number of tests that have to be done. The union bound then implies that the FWE is bounded by $\alpha$:

$$ \text{FWE} = \mathbb{P}_{H_j, j \in \mathbf{I}} \left( \bigcup_{j \in \mathbf{I}} \{\text{reject } H_j\} \right) \leq \sum_{i \in \mathbf{I}} \mathbb{P}_{H_j, j \in \mathbf{I}} (\text{reject } H_j) \leq |\mathbf{I}| \frac{\alpha}{J} \leq \alpha. $$
Cédric Colas, Olivier Sigaud, and Pierre-Yves Oudeyer. A hitchhiker's guide to statistical comparisons of reinforcement learning algorithms. *arXiv preprint arXiv:1904.06979*, 2019.

Geoff Cumming and Sue Finch. Inference by eye: confidence intervals and how to read pictures of data. *American psychologist*, 60(2):170, 2005.

Carlo D'Eramo, Davide Tateo, Andrea Bonarini, Marcello Restelli, and Jan Peters. Mushroomrl: Simplifying reinforcement learning research. *Journal of Machine Learning Research*, 22(131):1–5, 2021. URL http://jmlr.org/papers/v22/18-056.html.

Omar Darwiche Domingues, Yannis Flet-Berliac, Edouard Leurent, Pierre Ménard, Xuedong Shang, and Michal Valko. rlberry - A Reinforcement Learning Library for Research and Education, 10 2021. URL https://github.com/rlberry-py/rlberry.

Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters in deep policy gradients: A case study on PPO and TRPO. *arXiv preprint arXiv:2005.12729*, 2020.

Ronald Aylmer Fisher. Design of experiments. *British Medical Journal*, 1(3923):554, 1936.

Yannis Flet-Berliac, Reda Ouhamma, Odalric-Ambrym Maillard, and Philippe Preux. Learning value functions in deep policy gradients using residual variance. In *ICLR 2021-International Conference on Learning Representations*, 2021.

Steven N Goodman, Daniele Fanelli, and John PA Ioannidis. What does research reproducibility mean? *Science translational medicine*, 8(341):341ps12–341ps12, 2016.

KK Gordon Lan and David L DeMets. Discrete sequential boundaries for clinical trials. *Biometrika*, 70(3): 659–663, 1983.

Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In *International conference on machine learning*, pp. 1861–1870. PMLR, 2018.

Steven R. Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. *The Annals of Statistics*, 49(2):1055–1080, 2021. doi: 10.1214/20-AOS1991. URL https://doi.org/10.1214/20-AOS1991.

Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga, Dipam Chakraborty, Kinal Mehta, and João G.M. Araújo. Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms. *Journal of Machine Learning Research*, 23(274):1–18, 2022. URL http://jmlr.org/papers/v23/21-1342.html.

Christopher Jennison and Bruce W Turnbull. *Group sequential methods with applications to clinical trials*. CRC Press, 1999.

Emilie Kaufmann and Wouter M Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. *The Journal of Machine Learning Research*, 22(1):11140–11183, 2021.

Ilmun Kim, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimality of permutation tests. *The Annals of Statistics*, 50(1):225–251, 2022. doi: 10.1214/21-AOS2103. URL https://doi.org/10.1214/21-AOS2103.

D. Knuth. *The art of programming, volume 1, Fundamental Algorithms*. Addison-Wesley, 1968.

Tor Lattimore and Csaba Szepesvári. *Bandit algorithms*. Cambridge University Press, 2020.

Erich Leo Lehmann, Joseph P Romano, and George Casella. *Testing statistical hypotheses*, volume 3. Springer, 2005.
which is the probability of rejecting the hypothesis given that it is actually true. Bonferroni correction has the advantage of being very simple to implement, but it is often very conservative and the final FWE would be most often a lot smaller than $\alpha$. An alternative method that performs well in practice is the step-down method that we use in this article and which is presented in Section F.2.

## C Proof of Theorem 1

The proof of Theorem 1 is based on an extension of the proof of the control of FWE in the non-sequential case and the proof of the step-down method (see [27]). The interested reader may refer to Lemma 1 in the Appendix where we reproduce the proof of the bound on FWE for simple permutation tests as it is a good introduction to permutation tests. The proof proceeds as follows: first, we prove weak control on the FWE by decomposing the error as the sum of the errors on each interim and using the properties of permutation tests to show that the error done at each interim is controlled by $\alpha/K$. Then, using the step-down method construction, we show that the strong control of the FWE is a consequence of the weak control because of monotony properties on the boundary values of a permutation test.

### C.1 Simplified proof for $L = 2$ agents, and $K = 1$

The proof of the theorem for this result is a bit technical. We begin by showing the result in a very simplified case with $L = 2$ agents, and $K = 1$.

**Lemma 1.** Let $X_1, \dots, X_N$ be i.i.d from a distribution $P$ and $Y_1, \dots, Y_N$ be i.i.d. from a distribution $Q$. Denote $Z_1^{2N} = X_1, \dots, X_N, Y_1, \dots, Y_N$ be the concatenation of $X_1^N$ and $Y_1^N$. Let $\alpha \in (0, 1)$ and define $B_N$ such that

$$B_N = \inf \left\{ b > 0 : \frac{1}{(2N)!} \sum_{\sigma \in \mathfrak{S}_{2N}} \mathbb{1} \left\{ \frac{1}{N} \sum_{i=1}^{N} (Z_{\sigma(i)} - Z_{\sigma(N+i)}) > b \right\} \le \alpha \right\}.$$

Then, if $P = Q$, we have

$$\mathbb{P} \left( \frac{1}{N} \sum_{i=1}^{N} (X_i - Y_i) > B_N \right) \le \alpha$$

*Proof.* Denote $T(\sigma) = \frac{1}{N} \sum_{i=1}^{N} (Z_{\sigma(i)} - Z_{\sigma(n+i)})$. Since $P = Q$, for any $\sigma, \sigma' \in \mathfrak{S}_{2N}$ we have $T(\sigma) \stackrel{d}{=} T(\sigma')$. Then, because $B_N$ does not depend on the permutation $\sigma$ (but it depends on the values of $Z_1^{2N}$, we have, for any $\sigma \in \mathfrak{S}_{2N}$

$$\mathbb{P}(T(\text{id}) > B_N) = \mathbb{P}(T(\sigma) > B_N)$$

Now, take the sum over all the permutations,

$$\mathbb{P}(T(\text{id}) > B_N) = \frac{1}{(2N)!} \sum_{\sigma \in \mathfrak{S}_{2N}} \mathbb{E}[1\{T(\sigma) > B_N\}] \\ = \mathbb{E} \left[ \frac{1}{(2N)!} \sum_{\sigma \in \mathfrak{S}_{2N}} 1\{T(\sigma) > B_N\} \right] \le \alpha$$

which proves the result. $\square$

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

Next, we prove weak control in the general case.
Les Leventhal and Cam-Loi Huynh. Directional decisions for two-tailed tests: Power, error rates, and sample size. *Psychological Methods*, 1(3):278, 1996.

Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. *arXiv preprint arXiv:1509.02971*, 2015.

John Ludbrook and Hugh Dudley. Why permutation tests are superior to t and f tests in biomedical research. *The American Statistician*, 52(2):127-132, 1998.

Cyrus R Mehta, Nitin Patel, Pralay Senchaudhuri, and Anastasios Tsiatis. Exact permutational tests for group sequential clinical trials. *Biometrics*, pp. 1042-1053, 1994.

Sandro Pampallona and Anastasios A Tsiatis. Group sequential designs for one-sided and two-sided hypothesis testing with provision for early stopping in favor of the null hypothesis. *Journal of Statistical Planning and Inference*, 42(1-2):19-35, 1994.

Andrew Patterson, Samuel Neumann, Martha White, and Adam White. Empirical design in reinforcement learning, 2023.

Belinda Phipson and Gordon K Smyth. Permutation p-values should never be zero: calculating exact p-values when permutations are randomly drawn. *Statistical applications in genetics and molecular biology*, 9(1), 2010.

Edwin JG Pitman. Significance tests which may be applied to samples from any populations. *Supplement to the Journal of the Royal Statistical Society*, 4(1):119-130, 1937.

Stuart J Pocock. Group sequential methods in the design and analysis of clinical trials. *Biometrika*, 64(2): 191-199, 1977.

Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. *Stable-baselines3: Reliable reinforcement learning implementations*. *Journal of Machine Learning Research*, 22(268):1-8, 2021. URL http://jmlr.org/papers/v22/20-1364.html.

Joseph P Romano. Bootstrap and randomization tests of some nonparametric hypotheses. *The Annals of Statistics*, 17(1):141-159, 1989.

Joseph P. Romano and Michael Wolf. Exact and approximate stepdown methods for multiple hypothesis testing. *SSRN Journal Electronic Journal*, 2003. doi: 10.2139/ssrn.563267. URL https://doi.org/10.2139/2Fssrn.563267.

John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In *International conference on machine learning*, pp. 1889-1897. PMLR, 2015.

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. *arXiv preprint arXiv:1707.06347*, 2017.

Connie P Shapiro and Lawrence Hubert. Asymptotic normality of permutation statistics derived from weighted sums of bivariate functions. *The Annals of Statistics*, 7(4):788-794, 1979.

Jaehyeok Shin, Aaditya Ramdas, and Alessandro Rinaldo. Nonparametric iterated-logarithm extensions of the sequential generalized likelihood ratio test. *IEEE Journal on Selected Areas in Information Theory*, 2 (2):691-704, 2021.

Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In *2012 IEEE/RSJ international conference on intelligent robots and systems*, pp. 5026-5033. IEEE, 2012.

John Wilder Tukey. The problem of multiple comparisons. *Multiple comparisons*, 1953.

A. Wald. Sequential Tests of Statistical Hypotheses. *The Annals of Mathematical Statistics*, 16(2):117-186, 1945. doi: 10.1214/aoms/1177731118. URL https://doi.org/10.1214/aoms/1177731118.
## C.2 Proof of Theorem 1

In this section, we use the shorthand $\mathbb{P}$ instead of $\mathbb{P}_{H_j, j \in \mathbf{I}}$ and omit $H_j, j \in \mathbf{I}$ because $\mathbf{I}$ will always be the set of true hypotheses and the meaning should be clear from the context.

**Weak control on FWE:** First, we prove weak control on the FWE. This means that we suppose that $\mathbf{I} = \{1, \dots, J\}$: all the hypotheses are true, and we control the probability to make at least one rejection. We have,

$$ \text{FWE} = \mathbb{P}(\exists j \in \mathbf{I}: H_j \text{ is rejected}). $$

We decompose the FWE on the diverse interims.

$$ \text{FWE} = \sum_{k=1}^{K} \mathbb{P} \left( \bar{T}_{N,k}^{(\mathbf{I})}(\text{id}) > B_{N,k}^{(\mathbf{I})}, \text{NR}_k(\text{id}) \right), \quad (3) $$

where $\text{NR}_k(\sigma_{1:k}) = \{\forall m < k, \bar{T}_{N,m}^{(\mathbf{I})}(\sigma_{1:k}) \le B_{N,m}^{(\mathbf{I})}\}$ is the event on which we did not reject before. We use $\sigma_{1:k}$ and not only id as this will be useful later on (See Equation (4)).

Then, similarly as in the proof of Lemma 1, we want to use the invariance by permutation to make the link with the definition of $B_{N,k}^{(\mathbf{I})}$. For this purpose, we introduce the following lemma, that we prove in Appendix D.

**Lemma 2.** We have that for $k \le K$, for any $\sigma_{1:k}$ concatenation of $k$ permutations,

$$ (\bar{T}_{N,l}^{(\mathbf{I})}(\text{id}), B_{N,l}^{(\mathbf{I})})_{l \le k} \stackrel{d}{=} (\bar{T}_{N,l}^{(\mathbf{I})}(\sigma_{1:l}), B_{N,l}^{(\mathbf{I})})_{l \le k}. $$

Using Lemma 2, we have for any $\sigma_{1:k}$

$$ \mathbb{P} \left( \bar{T}_{N,k}^{(\mathbf{I})}(\text{id}) > B_{N,k}^{(\mathbf{I})}, \text{NR}_k(\text{id}) \right) = \mathbb{P} \left( \bar{T}_{N,k}^{(\mathbf{I})}(\sigma_{1:k}) > B_{N,k}^{(\mathbf{I})}, \text{NR}_k(\sigma_{1:k}) \right) \quad (4) $$

Hence, injecting this in Equation (3),

$$ \begin{aligned} \text{FWE} &\le \sum_{k=1}^{K} \frac{1}{m_k} \sum_{\sigma_{1:k} \in S_k} \mathbb{P} \left( \bar{T}_{N,k}^{(\mathbf{I})}(\sigma_{1:k}) > B_{N,k}^{(\mathbf{I})}, \text{NR}_k(\sigma_{1:k}) \right) \\ &= \sum_{k=1}^{K} \mathbb{E} \left[ \frac{1}{m_k} \sum_{\sigma_{1:k} \in S_k} 1 \left\{ \bar{T}_{N,k}^{(\mathbf{I})}(\sigma_{1:k}) > B_{N,k}^{(\mathbf{I})}, \text{NR}_k(\sigma_{1:k}) \right\} \right] \end{aligned} $$

Then, use that $\sigma_{1:k} \in \hat{S}_k$ if and only if $\sigma_{1:k} \in S_k$ and $\text{NR}_k(\sigma_{1:k})$ is true. Hence,

$$ \text{FWE} \le \sum_{k=1}^{K} \mathbb{E} \left[ \frac{1}{m_k} \sum_{\sigma_{1:k} \in \hat{S}_k} 1 \left\{ \bar{T}_{N,k}^{(\mathbf{I})}(\sigma_{1:k}) > B_{N,k}^{(\mathbf{I})} \right\} \right] \le \sum_{k=1}^{K} q_k \le \alpha $$

where we used the definition of $B_{N,k}^{(\mathbf{I})}$ to make the link with $\alpha$
# A Index of notations

* $N_{score}$: the total number of scores used for one agent.

* $N$: the number of scores per interim.

* $K$: the total number of interims.

* $k$: the current interim number.

* $L$: the number of agents to compare.

* $A_1, A_2, \dots, A_L$: the agents to compare.

* $\mathbb{E}[X]$ : expectation of the random variable $X$.

* $\alpha$: type I error or Family-wise error of a test.

* $\beta$: type II error of a test.

* $S_n$: set of all the permutations of $\{1, \dots, n\}$.

* $\sigma$: generic notation for a permutation, $\sigma \in S_n$ for some $n \in \mathbb{N}^*$.

* id: the identity permutation, i.e. $id(k) = k$ for all $1 \le k \le n$ for $id \in S_n$.

* $B$: the number of random permutations used to approximate the test statistic.

* $\sigma_{1:k}$: shorthand for the concatenation of permutations $\sigma_1, \dots, \sigma_k$, i.e. $\sigma_{1:k}(e_{n,i}) = \sigma_i(e_{n,i})$ for all $1 \le i \le k$.

* $H_j$: denotes hypothesis $j$ in a multiple test, $H'_j$ denotes the alternative of hypothesis $H_j$.

* $c_j$: denotes a comparison. This is a couple $(l_1, l_2)$ in $\{1, \dots, L\}^2$.

* $j$: shorthand for denoting comparison $c_j$.

* $C_0$: set of all the comparisons done in ADASTOP.

* $C$: current set of undecided comparisons in ADASTOP, a subset of $C_0$.

* $C_k$: state of $C$ at interim $k$ in ADASTOP.

* $e_i(j)$ or $e_{i,k}(j)$: score corresponding to run number $i$ when doing the test for comparison $c_j$ for interim $k$.

* $T_N(\sigma)$ and $T_{N,k}^{(j)}(\sigma)$: test statistic. Defined in Equation (6) and Equation (8).

* $B_{N,k}^{(C)}$: boundary for test statistic $T_{N,k}^{(C)}$, such that if $T_{N,k}^{(C)}(id) > B_{N,k}^{(C)}$, then reject the set of hypotheses associated to $C$.

* $\mathbf{I}$: set of true hypotheses and $\mathbf{I}^c$ its complement.

* FWE: family-wise error, see Definition 1.

* $\mathcal{N}(\mu, \sigma^2)$: law of a Gaussian probability distribution with mean $\mu$ and variance $\sigma^2$.

* $t(\mu, \nu)$: law of a translated Student probability distribution with center of symmetry $\mu$ and $\nu$ degrees of freedom.

* $\mathcal{M}_f^N(\mu_1, \sigma_1^2; \mu_2, \sigma_2^2)$: mixture of the two normal probability distributions $\mathcal{N}(\mu_1, \sigma_1^2)$ and $\mathcal{N}(\mu_2, \sigma_2^2)$. Each component of the mixture in weigh by $f$ and $1-f$ respectively.

* $\mathcal{M}_f^t(\mu_1, \nu_1; \mu_2, \nu_2)$: mixture of two Student probability distributions $t(\mu_1, \nu_1)$ and $t(\mu_2, \nu_2)$. Each component of the mixture in weigh by $f$ and $1-f$ respectively.

* $\mathbb{P}_{H_j, j \in \mathbf{I}}$: probability distribution when $H_j, j \in \mathbf{I}$ are true and $H_j, j \notin \mathbf{I}$ are false.
**Strong control of FWE:** To prove strong control, it is sufficient to show the following Lemma (see Appendix D for a proof), which is an adaptation of the proof of step-down multiple-test strong control of FWE from [27].

**Lemma 3.** Suppose that $\mathbf{I} \subset \{1, \dots, J\}$ is the set of true hypotheses. We have

$$ \text{FWE} = \mathbb{P}(\exists j \in \mathbf{I}: H_j \text{ is rejected}) \le \mathbb{P}(\exists k \le K: \bar{T}_{N,k}^{(\mathbf{I})}(\text{id}) > B_{N,k}^{(\mathbf{I})}). $$

Lemma 3 shows that to control the FWE, it is sufficient to control the probability to reject on $\mathbf{I}$ given by $\mathbb{P}(\exists k \le K: \bar{T}_{N,k}^{(\mathbf{I})}(\sigma_{1:k}) > B_{N,k}^{(\mathbf{I})})$ and this quantity, in turns, is exactly the FWE of the restricted problem of testing $(H_j)_{j \in \mathbf{I}}$ against $(H'_j)_{j \in \mathbf{I}}$. In other words, Lemma 3 says that to prove strong FWE control for our algorithm, it is sufficient to prove weak FWE control, and we already did that in the first part of the proof.

# D Proof of Lemmas

## D.1 Proof of Lemma 2

In this section, for an easier comprehension, we change the notation for the performance measure $e_{n,k}^{(j)}(\sigma)$ and denote by $e_{n,k}(A_i)$ the $n^{th}$ performance value of agent $A_i$ at interim $k$. In effect, this means that for the comparison $j$ of agent $A_i$ versus agent $A_l$, we have the equality $e_{n,k}(A_i) = e_{n,k}^{(j)}(\text{id})$ for $n \le N$ and $e_{n,k}(A_l) = e_{N+n,k}^{(j)}(\text{id})$.

We denote the comparisons by $(c_i)_{i \in \mathbf{I}}$, they describe a graph with the nodes being the agents denoted $1, \dots, L$ and $(j_1, j_2)$ has an edge if $(j_1, j_2) \in (c_i)_{i \in \mathbf{I}}$ is one of the comparisons that corresponds to a true hypothesis. This graph is not necessarily connected, we denote $C(i)$ the connected component to which node $a$ (e.g. agent $a$) belongs, i.e. for any $a_1, a_2 \in C(a)$ there exists a path going from $a_1$ to $a_2$. Remark that $C(a)$ cannot be equal to the singleton $\{a\}$, because it would mean that all the comparisons with $a$ are in fact false hypotheses, and then $a$ would not belong to a couple in $\mathbf{I}$.

Then, it follows from the construction of permutation test that jointly on $k \le K$ and $a_1, a_2 \in C(i)$, we have $T_{N,k}^{(a_1, a_2)}(\text{id}) \stackrel{d}{=} T_{N,1}^{(a_1, a_2)}(\sigma_{1:k})$ for any $\sigma_1, \dots, \sigma_k \in \mathcal{S}_{2N}$.

Let us illustrate that on an example. Suppose that $N = 2$ and $J = 3$. Consider the permutation

$$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix} $$

Because all the evaluations are i.i.d., we have the joint equality in distribution

$$ \left( \begin{array}{c} |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_3) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_3) - e_{2,1}(A_3)| \end{array} \right) \stackrel{d}{=} \left( \begin{array}{c} |e_{1,1}(A_1) + e_{2,1}(A_2) - e_{1,1}(A_1) - e_{2,1}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_2) - e_{1,1}(A_3) - e_{2,1}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_3) - e_{1,1}(A_1) - e_{2,1}(A_3)| \end{array} \right) $$

and hence,

$$ (T_{N,1}^{(j)}(\text{id}))_{1 \le j \le 3} \stackrel{d}{=} (T_{N,1}^{(j)}(\sigma_1))_{1 \le j \le 3}. $$
# B Basics on hypothesis testing

To be fully understood, this paper requires the knowledge of some notions of statistics. In the hope of widening the audience of this paper, we recall notions of statistics related to hypothesis testing that are essential to understand the ADA STOP test.

## B.1 Type I and type II error

In its simplest form, a statistical test is aimed at deciding whether a given collection of data $X_1, \dots, X_N$ adheres to some hypothesis $H_0$ (called the null hypothesis), or if it is a better fit for the alternative hypothesis $H_1$. Typically, the null hypothesis states that the mean of the distribution from which the $X_i$'s are sampled is equal to some $\mu_0$: $H_0: \mu = \mu_0$ and $H_1: \mu \neq \mu_0$ where $\mu$ is the mean of the distribution of $X_1, \dots, X_N$. Because $\mu$ is unknown, it has to be estimated using the data. Often this is done using the empirical mean $\hat{\mu} = \frac{1}{N} \sum_{i=1}^N X_i$. $\hat{\mu}$ is a random variable and some deviation from $\mu$ is to be expected. The theory of hypothesis tests is concerned in finding a threshold $c$ such that if $|\hat{\mu} - \mu_0| > c$ then we say that $H_0$ is false because the deviation is greater than what was expected by the theory. A slightly more complex problem is to consider two samples $X_1, \dots, X_N$ and $Y_1, \dots, Y_N$ and do a two-sample test deciding whether the mean of the distribution of the $X_i$'s is equal to the mean of the distribution of the $Y_i$'s.

In both cases, the result of a test is either reject $H_0$ or to not reject $H_0$. This answer is not a ground truth: there is some probability that we make an error. However, this probability of error is often controlled and can be decomposed in type I error and type II error (often denoted $\alpha$ and $\beta$ respectively, see Table 3 and Figure 6). In words, a type I error is when we conclude that the null hypothesis is false ($H_0$ is rejected, means are different) whereas means are equal. $\alpha$ is the probability that this event occurs. A type II error is when we conclude that the null hypothesis is true ($H_0$ is accepted, means are equal) whereas means are not equal. $\beta$ is the probability that this event occurs.

<table><caption>Table 3: Type I and type II error.</caption><thead><tr><th></th><th>$H_0$ is true</th><th>$H_0$ is false</th></tr></thead><tbody><tr><td>We accept $H_0$</td><td>No error</td><td>Type II error $\beta$</td></tr><tr><td>We reject $H_0$</td><td>Type I error $\alpha$</td><td>No error</td></tr></tbody></table>

The problem is not symmetric: failing to reject the null hypothesis does not mean that the null hypothesis is true. It can be that there is not enough data to reject $H_0$. It has been shown that a test cannot simultaneously minimize $\alpha$ and $\beta$. It is customary to minimize $\beta$ for a given value of $\alpha$ (typically $\alpha$ is set to 0.05). The probability to reject $H_0$ when it is false is $1 - \beta$ and it is usually called the **power** of a test.

## B.2 Directional error

Statistical tests are often formulated as bilateral problems, which means that we test $\mu = \mu_0$ versus the bilateral interval $\mu \in (-\infty, \mu_0) \cup (\mu_0, +\infty)$. In practice (and in the case of this article), after rejecting the equality, we want to know if $\mu > \mu_0$ or if $\mu < \mu_0$. This can be done using the sign of the test statistic $\hat{\mu} - \mu_0$. However this is not a direct consequence of the test because the test did not suppose a direction. This means that in addition to the type I and type II, we can have a type III error which is the probability to say that $\mu > \mu_0$ when in fact $\mu < \mu_0$ or that $\mu < \mu_0$ when in fact $\mu > \mu_0$.

Intuitively, if the type II error is low, then type III error (Leventhal & Huynh, 1996) tends to be even lower provided that the data distribution is sufficiently concentrated around its mean. See Figure 6 (right sub-figure) for a visual representation of the errors, here the probability that $\hat{\mu} > \mu_0 + c$ when $\mu < \mu_0$. Type III error is often negligible, not considered in practice, and even unknown to many researchers.
For $k=2$, we have for $\sigma_2 = \sigma_1$,

$$ \left( \begin{array}{c} |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_3) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_3) - e_{2,1}(A_3)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_2) - e_{2,1}(A_2) + e_{1,2}(A_1) + e_{2,2}(A_1) - e_{1,2}(A_2) - e_{2,2}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_3) - e_{1,1}(A_2) - e_{2,1}(A_2) + e_{1,2}(A_3) + e_{2,2}(A_3) - e_{1,2}(A_2) - e_{2,2}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_3) - e_{2,1}(A_3) + e_{1,2}(A_1) + e_{2,2}(A_1) - e_{1,2}(A_3) - e_{2,2}(A_3)| \end{array} \right) \\ \stackrel{d}{=} \left( \begin{array}{c} |e_{1,1}(A_1) + e_{2,1}(A_2) - e_{1,1}(A_1) - e_{2,1}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_2) - e_{1,1}(A_3) - e_{2,1}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_3) - e_{1,1}(A_1) - e_{2,1}(A_3)| \\ |e_{1,1}(A_1) + e_{2,1}(A_2) - e_{1,1}(A_1) - e_{2,1}(A_2) + e_{1,2}(A_1) + e_{2,2}(A_2) - e_{1,2}(A_1) - e_{2,2}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_2) - e_{1,1}(A_3) - e_{2,1}(A_2) + e_{1,2}(A_3) + e_{2,2}(A_3) - e_{1,2}(A_3) - e_{2,2}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_3) - e_{1,1}(A_1) - e_{2,1}(A_3) + e_{1,2}(A_1) + e_{2,2}(A_3) - e_{1,2}(A_1) - e_{2,2}(A_3)| \end{array} \right) $$

and then, we get jointly

$$ (T_{N,k}^{(j)}(\mathrm{id}))_{1 \le j \le 3, k \le 2} \stackrel{d}{=} (T_{N,k}^{(j)}(\sigma_1 \cdot \sigma_2))_{1 \le j \le 3, k \le 2}. $$

This reasoning can be generalized to general N, J and K:

$$ (T_{N,k}^{(a_1,a_2)}(\mathrm{id}))_{k \le K, a_1 \in C(i), a_2 \in C(i)} \stackrel{d}{=} (T_{N,k}^{(a_1,a_2)}(\sigma_{1:k}))_{k \le K, a_1 \in C(i), a_2 \in C(i)}. $$

Then, use that by construction, the different connected component $C(i)$ are independent of one another and hence,

$$ (T_{N,k}^{(c_i)}(\mathrm{id}))_{k \le K, c_i \in \mathbf{I}} \stackrel{d}{=} (T_{N,k}^{(c_i)}(\sigma_{1:k}))_{k \le K, c_i \in \mathbf{I}}. $$

The result follows from taking the maximum on all the comparisons, and because the boundaries do not depend on the permutation.

## D.2 Proof of Lemma 3

Denote by $C_k$ the (random) value of $C$ at the beginning of interim $k$. We have,

$$ \begin{aligned} \mathrm{FWE} &= \mathbb{P}(\exists j \in \mathbf{I}: H_j \text{ is rejected}) \\ &= \mathbb{P}\left(\exists k \le K: \bar{T}_{N,k}^{(C_k)}(\mathrm{id}) > B_{N,k}^{(C_k)}, \arg \max_{j \in C_k} \bar{T}_{N,k}^{(j)}(\mathrm{id}) \in \mathbf{I}\right). \end{aligned} \quad (5) $$

Then, let $k_0$ correspond to the very first rejection (if any) in the algorithm. Having that the argmax is attained in $\mathbf{I}$,

$$ \bar{T}_{N,k_0}^{(C_{k_0})}(\mathrm{id}) = \max\{T_{N,k_0}^{(j)}(\mathrm{id}), j \in C_{k_0}\} = \max\{T_{N,k_0}^{(j)}(\mathrm{id}), j \in \mathbf{I}\} = \bar{T}_{N,k_0}^{(\mathbf{I})}(\mathrm{id}) $$

Moreover, having $C_{k_0} \supset \mathbf{I}$, we have $B_{N,k_0}^{(C_{k_0})} \ge B_{N,k_0}^{(\mathbf{I})}$. Injecting these two relations in Equation (5), we obtain

$$ \begin{aligned} \mathrm{FWE} &\le \mathbb{P} \left( \exists k \le K : \bar{T}_{N,k}^{(\mathbf{I})}(\mathrm{id}) > B_{N,k}^{(\mathbf{I})}, \arg \max_{j \in C_k} \bar{T}_{N,k}^{(j)}(\mathrm{id}) \in \mathbf{I} \right) \\ &\le \mathbb{P} \left( \exists k \le K : \bar{T}_{N,k}^{(\mathbf{I})}(\mathrm{id}) > B_{N,k}^{(\mathbf{I})} \right). \end{aligned} $$

This proves the desired result.
<figure><img src="image_8.png" /><figcaption>Figure 6: Illustration of type I, II and III errors: in these 3 plots, the shaded areas represent the probability of type I error (left), type II error (middle) and type III error (right) when testing $\mu = 0$ vs. $\mu \neq 0$. c denotes the threshold on test statistic $\hat{\mu}$ after which we take a decision.</figcaption></figure>

## B.3 Multiple tests and FWE

When performing simultaneously $L$ statistical tests for $L > 1$, one must be careful that the error of each test accumulates. If one is not cautious, the overall error may become non-negligible. As a consequence, multiple strategies have been developed to deal with multiple testing problem.

To deal with the multiple testing problem, the first step is to define what is an error. There are several definitions of error in multiple testing among which is the False Discovery Rate which measures the expected proportion of false rejections. Another possible measure of error is the Family-Wise Error (the error we use in this article) which is defined as the probability to make at least one false rejection:

$$ \text{FWE} = \mathbb{P}_{H_j, j \in \mathbf{I}} (\exists j \in \mathbf{I}: \text{reject } H_j), $$

where $\mathbb{P}_{H_j, j \in \mathbf{I}}$ is used to denote a probability. $\mathbf{I} \subset \{1, \dots, L\}$ is the set of indices of the hypotheses that are true (and $\mathbf{I}^c$ the set of hypotheses that are actually false). To construct a procedure with an FWE smaller than $\alpha$, the simplest method is perhaps Bonferroni's correction (Bonferroni, 1936) in which a statistical test is applied on each of the $J$ couples of hypotheses to be tested ($J = L(L-1)/2$). And then, one would tune each hypothesis test to have a type I error $\alpha/J$. The union bound then implies that the FWE is bounded by $\alpha$:

$$ \text{FWE} = \mathbb{P}_{H_j, j \in \mathbf{I}} \left( \bigcup_{j \in \mathbf{I}} \{\text{reject } H_j\} \right) \leq \sum_{i \in \mathbf{I}} \mathbb{P}_{H_j, j \in \mathbf{I}} (\text{reject } H_j) \leq |\mathbf{I}| \frac{\alpha}{J} \leq \alpha. $$

Bonferroni's correction has the advantage of being very simple to implement. However, it is often very conservative and the FWE is most often a lot smaller than $\alpha$. An alternative method that performs well in practice is the step-down method that we use in this article and is presented in Section 3.2.4.

## C Proof of Theorem 1

The proof of Theorem 1 is based on an extension of the proof of the control of FWE in the non-sequential case and the proof of the step-down method (Romano & Wolf, 2003). The interested reader may refer to Lemma 1, in the Appendix C.1, where we reproduce the proof of the bound on FWE for simple permutation tests as it is a good introduction to permutation tests. The proof proceeds as follows: first, we prove weak control<fnref n="10" /> on the FWE by decomposing the error as the sum of the errors on each interim and using the properties of permutation tests to show that the error done at each interim is controlled by $\alpha/K$. Then, using the step-down method construction, we show that the strong control of the FWE is a consequence of the weak control because of monotony properties on the boundary values of a permutation test.

### C.1 Simplified proof for $L = 2$ agents, and $K = 1$

The proof of this theorem is a bit technical. We begin by showing it in a very simplified case where $L = 2$ agents, and $K = 1$.

<footnote n="10">¹⁰A procedure controls has a weak control on the FWE if the FWE is smaller than $\alpha$ when all null hypotheses are true. On the other hand, strong control is when FWE is smaller than $\alpha$ whatever the set of true null hypotheses.</footnote>
# E Asymptotic results for two agents

## E.1 Convergence of boundaries and comparing the means

Because there are only two agents and no early stopping, we simplify the notations and denote

$$t_{N,i}(\sigma_i) = \sum_{n=1}^{N} e_{\sigma_i(n),i}(2) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(1)$$

and

$$T_{N,k}(\sigma_{1:k}) = \left| \sum_{i=1}^{k} \left( \sum_{n=1}^{N} e_{\sigma_i(n),i}(2) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(1) \right) \right| \\ = \left| \sum_{i=1}^{k} t_{N,i}(\sigma_i) \right|$$

and

$$B_{N,k} = \inf \left\{ b > 0 : \frac{1}{((2N)!)^k} \sum_{\sigma_1, \dots, \sigma_k \in \mathfrak{G}_{2N}^k} \mathbb{1}\{T_{N,k}(\sigma_{1:k}) \ge b\} \le q_k \right\}$$

When there is only one interim ($K = 1$), we have the following convergence of the random-ization law of $T_{N,1}(\sigma)$.

**Proposition 1.** Suppose $e_{1,1}(1), \dots, e_{N,1}(1)$ are i.i.d from $P$ and $e_{1,1}(2), \dots, e_{N,1}(2)$ are i.i.d from $Q$ and both $P$ and $Q$ has finite variance. Then, we have

$$\sup_t \left| \frac{1}{(2N)!} \sum_{\sigma \in \mathfrak{G}_{2N}} \mathbb{1} \left\{ \frac{1}{\sqrt{N}} T_{N,1}(\sigma) \le t \right\} - \Phi(t/\tau(P,Q)) \right| \xrightarrow[N \to \infty]{} 0$$

where $\Phi$ is the standard normal c.d.f. and $\tau(P,Q)^2 = \sigma_P^2 + \sigma_Q^2 + \frac{(\mu_P - \mu_Q)^2}{2}$.

**Theorem 2.** We have that for any $1 \le k \le K$, $\frac{1}{\sqrt{N}} B_{N,k} \xrightarrow[N \to \infty]{} b_k$ where the real numbers $b_k$ are defined as follows. Let $W_1, \dots, W_K$ be i.i.d random variable with law $N(0,1)$, then $b_1$ is the solution of the following equation:

$$\mathbb{P}\left(\left|W_1\right| \ge \frac{b_1}{\tau(P,Q)}\right) = \frac{\alpha}{K},$$

and for any $1 < k \le K$, $b_k$ is the solution of

$$\mathbb{P}\left(\left|\frac{1}{k}\sum_{j=1}^{k} W_j\right| > \frac{b_l}{\tau(P,Q)}, \quad \forall j < k, \quad \left|\frac{1}{j}\sum_{i=1}^{j} W_i\right| \le \frac{b_j}{\tau(P,Q)}\right) = \frac{\alpha}{K}.$$

Remark that the test we do corresponds to testing

$$\mathbb{1}\{\exists k \le K : \frac{1}{\sqrt{N}} T_{N,k}(\text{id}) > \frac{1}{\sqrt{N}} B_{N,k}\}$$
**Lemma 1.** Let $X_1, \dots, X_N$ be i.i.d. from a distribution $P$ and $Y_1, \dots, Y_N$ be i.i.d. from a distribution $Q$. Let $Z_1^{2N} = X_1, \dots, X_N, Y_1, \dots, Y_N$ be the concatenation of $X_1^N$ and $Y_1^N$. Let $\alpha \in (0, 1)$ and define $B_N$ as:

$$B_N = \inf \left\{ b > 0 : \frac{1}{(2N)!} \sum_{\sigma \in S_{2N}} \mathbb{1} \left\{ \frac{1}{N} \sum_{i=1}^{N} (Z_{\sigma(i)} - Z_{\sigma(N+i)}) > b \right\} \le \alpha \right\}.$$

Then, if $P = Q$, we have:

$$\mathbb{P}\left(\frac{1}{N} \sum_{i=1}^{N} (X_i - Y_i) > B_N\right) \le \alpha.$$

*Proof.* Let us denote $T(\sigma) = \frac{1}{N} \sum_{i=1}^{N} (Z_{\sigma(i)} - Z_{\sigma(n+i)})$. Since $P = Q$, for any $\sigma, \sigma' \in S_{2N}$ we have $T(\sigma) \stackrel{d}{=} T(\sigma')$. Then, because $B_N$ does not depend on the permutation $\sigma$ (but it depends on the values of $Z_1^{2N}$), we have, for any $\sigma \in S_{2N}$

$$\mathbb{P}(T(id) > B_N) = \mathbb{P}(T(\sigma) > B_N).$$

Now, we sum all the permutations:

$$\mathbb{P}(T(id) > B_N) = \frac{1}{(2N)!} \sum_{\sigma \in S_{2N}} \mathbb{E}[1\{T(\sigma) > B_N\}] \\ = \mathbb{E}\left[\frac{1}{(2N)!} \sum_{\sigma \in S_{2N}} 1\{T(\sigma) > B_N\}\right] \le \alpha,$$

which proves the result.

□

Next, we prove weak control in the general case.

## C.2 Proof of Theorem 1

In this section, we use the shorthand $\mathbb{P}$ instead of $\mathbb{P}_{H_{j,j} \in \mathbf{I}}$ and omit $H_{j,j} \in \mathbf{I}$ because $\mathbf{I}$ will always be the set of true hypotheses and the meaning should be clear from the context.

**Weak control on FWE:** First, we prove weak control on the FWE. This means that we suppose that all the hypotheses are true ($\mathbf{I} = \{1, \dots, J\}$), and we control the probability to make at least one rejection. We have:

$$\text{FWE} = \mathbb{P}(\exists j \in \mathbf{I} : H_j \text{ is rejected}).$$

We decompose the FWE on the set of interims, using the fact that a rejection happens if and only if we reject a true hypothesis for the first time at interim $k$ for some $k = 1, \dots, K$. These events are mutually exclusive therefore we have that their probabilities sum up and we can rewrite the FWE as:

$$\text{FWE} = \sum_{k=1}^{K} \mathbb{P} \left( \bar{T}_{N,k}^{(\mathbf{I})}(\text{id}) > B_{N,k}^{(\mathbf{I})}, \text{NR}_k(\text{id}) \right), \quad (13)$$

where $\text{NR}_k(\text{id})$ is the event on which we did *Not Reject* (NR) before interim $k$. $\text{NR}_k(\text{id})$ can be defined directly for a concatenation of permutations $\sigma_{1:k}$ as $\text{NR}_k(\sigma_{1:k}) = \{\forall m < k, \bar{T}_{N,m}^{(\mathbf{I})}(\sigma_{1:k}) \le B_{N,m}^{(\mathbf{I})}\}$. We introduced the definition for $\sigma_{1:k}$ and not only for id since this will be useful later on, for example in Equation (14).

Then, similarly as in the proof of Lemma 1, we want to use the invariance by permutation to make the link with the definition of $B_{N,k}^{(\mathbf{I})}$. For this purpose, we introduce the following lemma, that we prove in Appendix D.

**Lemma 2.** For $k \le K$, for any $\sigma_{1:k}$ concatenation of $k$ permutations:

$$(\bar{T}_{N,l}^{(\mathbf{I})}(\text{id}), B_{N,l}^{(\mathbf{I})})_{l \le k} \stackrel{d}{=} (\bar{T}_{N,l}^{(\mathbf{I})}(\sigma_{1:l}), B_{N,l}^{(\mathbf{I})})_{l \le k}.$$
and from Theorem 2 and central-limit theorem $\frac{1}{\sqrt{N}}T_{N,k}(\text{id})$ converges to $\sum_{j=1}^k W_j\sqrt{\sigma_P^2 + \sigma_Q^2}$ and $B_{N,k}/\sqrt{N}$ converges to $b_k$, hence the test is asymptotically equivalent to

$$1\left\{\exists k \le K : \sum_{j=1}^{k} W_j \sqrt{\sigma_P^2 + \sigma_Q^2} > b_k\right\}.$$

Then, in the case in which $\mu_P = \mu_Q$, we have $\tau(P, Q) = \sqrt{\sigma_P^2 + \sigma_Q^2}$ and

$$\begin{aligned}
\text{FWE} &= \mathbb{P}\left(\exists k \le K : \sum_{j=1}^{k} W_j \sqrt{\sigma_P^2 + \sigma_Q^2} > b_k\right) \\
&= \sum_{k=1}^{K} \mathbb{P}\left(\left|\frac{1}{k} \sum_{j=1}^{k} W_j\right| > \frac{b_l}{\tau(P, Q)}, \quad \forall j < k, \quad \left|\frac{1}{j} \sum_{i=1}^{j} W_i\right| \le \frac{b_j}{\tau(P, Q)}\right) \\
&= \sum_{k=1}^{K} \frac{\alpha}{K} = \alpha.
\end{aligned}$$

Hence, for the test $H_0: \mu_P = \mu_Q$ versus $H_1: \mu_P \ne \mu_Q$, our test is asymptotically of level $\alpha$.

## E.2 Proof of Theorem 2

We denote for $x \in \mathbb{R}$,

$$R_{N,k}(x) = \frac{1}{(2N)!} \sum_{\sigma_k \in \mathfrak{S}_{2N}} 1\{t_{N,k}(\sigma_k) \le x\}.$$

$R_{N,k}$ is the c.d.f of the randomization law of $t_{N,k}(\sigma_k)$, and by Proposition 1, it converges uniformly to a Gaussian c.d.f when $N$ goes to infinity.

### Convergence of $B_{N,1}$

$$\frac{1}{\sqrt{N}} B_{N,1} = \frac{1}{\sqrt{N}} \min \left\{ b > 0 : \frac{1}{(2N)!} \sum_{\sigma_1 \in \mathfrak{S}_{2N}} 1\{|T_{N,1}(\sigma_1)| > b\} \le \frac{\alpha}{K} \right\}$$

This implies

$$\begin{aligned}
\frac{1}{(2N)!} \sum_{\sigma_1 \in \mathfrak{S}_{2N}} 1\{|T_{N,1}(\sigma_1)| \le B_{N,1}\} &= \hat{R}_{N,1}\left(\frac{1}{\sqrt{N}} B_{N,1}\right) - \hat{R}_{N,1}\left(-\frac{1}{\sqrt{N}} B_{N,1}\right) \\
&\ge 1 - \frac{\alpha}{K}
\end{aligned}$$

and for any $b < B_{N,1}$, we have

$$\frac{1}{(2N)!} \sum_{\sigma_1 \in \mathfrak{S}_{2N}} 1\{|T_{N,1}(\sigma_1)| \le b\} = \hat{R}_{N,1}\left(\frac{b}{\sqrt{N}}\right) - \hat{R}_{N,1}\left(-\frac{b}{\sqrt{N}}\right) < 1 - \frac{\alpha}{K}$$
Using Lemma 2, we have for any interim $k$ and concatenation of permutations $\sigma_{1:k}$

$$ \mathbb{P}(\bar{T}_{N,k}^{(I)}(\text{id}) > B_{N,k}^{(I)}, \text{NR}_k(\text{id})) = \mathbb{P}(\bar{T}_{N,k}^{(I)}(\sigma_{1:k}) > B_{N,k}^{(I)}, \text{NR}_k(\sigma_{1:k})). \quad (14) $$

Combing this equation with equation (13), we have:

$$ \begin{aligned} \text{FWE} &\le \sum_{k=1}^{K} \frac{1}{m_k} \sum_{\sigma_{1:k} \in \mathcal{S}_{N,k}} \mathbb{P}(\bar{T}_{N,k}^{(I)}(\sigma_{1:k}) > B_{N,k}^{(I)}, \text{NR}_k(\sigma_{1:k})) \\ &= \sum_{k=1}^{K} \mathbb{E} \left[ \frac{1}{m_k} \sum_{\sigma_{1:k} \in \mathcal{S}_{N,k}} \mathbb{1}\left\{\bar{T}_{N,k}^{(I)}(\sigma_{1:k}) > B_{N,k}^{(I)}, \text{NR}_k(\sigma_{1:k})\right\} \right]. \end{aligned} $$

Then, use that $\sigma_{1:k} \in \hat{\mathcal{S}}_{N,k}$ if and only if $\sigma_{1:k} \in \mathcal{S}_{N,k}$ and $\text{NR}_k(\sigma_{1:k})$ is true. Hence,

$$ \text{FWE} \le \sum_{k=1}^{K} \mathbb{E} \left[ \frac{1}{m_k} \sum_{\sigma_{1:k} \in \hat{\mathcal{S}}_{N,k}} \mathbb{1}\left\{\bar{T}_{N,k}^{(I)}(\sigma_{1:k}) > B_{N,k}^{(I)}\right\} \right] \le \sum_{k=1}^{K} q_k \le \alpha, $$

where we use the definition of $B_{N,k}^{(I)}$ to make the link with $\alpha$

**Strong control of FWE:** To prove strong control, it is sufficient to show the following Lemma (see Appendix D for a proof), which is an adaptation of the proof of step-down multiple-test strong control of FWE from (Romano & Wolf, 2003).

**Lemma 3.** Suppose that $\mathbf{I} \subset \{1, \dots, J\}$ is the set of true hypotheses. We have:

$$ \text{FWE} = \mathbb{P}(\exists j \in \mathbf{I}: H_j \text{ is rejected}) \le \mathbb{P}(\exists k \le K: \bar{T}_{N,k}^{(I)}(\text{id}) > B_{N,k}^{(I)}). $$

Lemma 3 shows that to control the FWE, it is sufficient to control the probability to reject on $\mathbf{I}$ given by $\mathbb{P}(\exists k \le K: \bar{T}_{N,k}^{(I)}(\sigma_{1:k}) > B_{N,k}^{(I)})$ and this quantity, in turn, is exactly the FWE of the restricted problem of testing $(H_j)_{j \in \mathbf{I}}$ against $(H'_j)_{j \in \mathbf{I}}$. In other words, Lemma 3 says that to prove strong FWE control for ADA STOP, it is sufficient to prove weak FWE control, and we already did that in the first part of the proof.

# D Proof of Lemmas 2 and 3

## D.1 Proof of Lemma 2

In this section, for an easier understanding, we change the notation for the score $e_{n,k}^{(j)}(\sigma)$ to $e_{n,k}(A_l)$ the $n^{th}$ score of agent $A_l$ at interim $k$. In other words, we change the notation of the comparison of agent $A_{l_1}$ versus agent $A_{l_2}$: in the main text a comparison was denoted by $c_j \in \{1, \dots, J\}^2$ but here we make explicit the agent from which the score has been computed resulting in the following equalities: $e_{n,k}(A_{l_1}) = e_{n,k}^{(j)}(\text{id})$ and $e_{n,k}(A_{l_2}) = e_{N+n,k}^{(j)}(\text{id})$ for $n \le N$.

We denote the comparisons by $(c_i)_{i \in \mathbf{I}}$. The set of comparisons can be represented as a graph in which each node represents one of the agents to compare, and there exists an edge from $j_1$ to $j_2$ denoted $(j_1, j_2)$ if $(j_1, j_2) \in (c_i)_{i \in \mathbf{I}}$ is one of the comparisons that corresponds to a true hypothesis. This graph is not necessarily connected. We denote $C(i)$ the connected component to which node $l$ (e.g. agent $l$) belongs, i.e. for any $l_1, l_2 \in C(l)$ there exists a path going from $l_1$ to $l_2$. $C(l)$ cannot be equal to the singleton $\{l\}$, because this would mean that all the comparisons with $l$ are in fact false hypotheses, and then $l$ would not belong to a couple in $\mathbf{I}$.
Then,

$$
\begin{align*}
& \Phi\left(\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) - \Phi\left(-\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) \\
\ge & \hat{R}_{N,1}\left(\frac{B_{N,1}}{\sqrt{N}}\right) - \hat{R}_{N,1}\left(-\frac{B_{N,1}}{\sqrt{N}}\right) - \left|\Phi\left(\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) - \hat{R}_{N,1}\left(\frac{B_{N,1}}{\sqrt{N}}\right)\right| \\
& - \left|\Phi\left(-\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) - \hat{R}_{N,1}\left(-\frac{B_{N,1}}{\sqrt{N}}\right)\right| \\
\ge & 1 - \frac{\alpha}{K} - 2\sup_t \left|\Phi\left(\frac{t}{\tau(P,Q)}\right) - \hat{R}_{N,1}(t)\right|
\end{align*}
$$

Hence, by taking $N$ to infinity, we have from Proposition 1,

$$
\liminf_{N \to \infty} \Phi \left( \frac{B_{N,1}}{\tau(P, Q)\sqrt{N}} \right) - \Phi \left( -\frac{B_{N,1}}{\tau(P, Q)\sqrt{N}} \right) \geq 1 - \frac{\alpha}{K}.
$$

and for any $\varepsilon > 0$, because of the definition of $B_{N,1}$ as a supremum, we have

$$
\limsup_{N \to \infty} \Phi \left( \frac{B_{N,1} + \varepsilon}{\tau(P, Q)\sqrt{N}} \right) - \Phi \left( -\frac{B_{N,1} + \varepsilon}{\tau(P, Q)\sqrt{N}} \right) < 1 - \frac{\alpha}{K}.
$$

By continuity of $\Phi$, this implies that $\frac{1}{\sqrt{N}} B_{N,1}$ converges almost surely and its limit is such that

$$
\Phi \left( \frac{\lim_{N \to \infty} B_{N,1} / \sqrt{N}}{\tau(P, Q)} \right) - \Phi \left( - \frac{\lim_{N \to \infty} B_{N,1} / \sqrt{N}}{\tau(P, Q)} \right) = 1 - \frac{\alpha}{K}.
$$

Or said differently, let $W \sim \mathcal{N}(0, 1)$, then we have the almost sure convergence $\lim_{N \to \infty} \frac{1}{\sqrt{N}} B_{N,1} =$ $b_1$ where $b_1$ is the real number defined by

$$
\mathbb{P}\left(\left|W\right| \geq \frac{b_1}{\tau(P, Q)}\right) = \frac{\alpha}{K}.
$$

**Convergence of $B_{N,k}$ for $k > 1$.** We proceed by induction. Suppose that $\frac{1}{\sqrt{N}} B_{N,k-1}$ converges to some $b_{k-1} > 0$ and that for any $d_1, \dots, d_{k-1}$, the randomization probability

$$
\sup_{d_1, \dots, d_{k-1}} \left| \frac{1}{((2N)!)^{k-1}} \sum_{\sigma_1, \dots, \sigma_{k-1} \in \mathfrak{S}_{2N}} \mathbb{1} \left\{ \forall j \le k-1, \sum_{i=1}^j t_{N,i}(\sigma_i) \le d_j \sqrt{N} \right\} - \mathbb{P} \left( \forall j \le k-1, \sum_{i=1}^j W_i \le \frac{d_j}{\tau(P,Q)} \right) \right| \xrightarrow{N \to \infty} 0, \quad (6)
$$

where $W_1, \dots, W_{k-1}$ are i.i.d $\mathcal{N}(0, 1)$ random variables. In other words, the randomization law converges uniformly to the joint law described above with the sum of Gaussian random variables. Then, by uniform convergence and by convergence of the $B_{N,j}$, we have

$$
\frac{1}{((2N)!)^{k-1}} \sum_{\sigma_1, \dots, \sigma_{k-1} \in \mathfrak{S}_{2N}} \mathbb{1}\{T_{N,j}(\sigma_{1:j}) > B_{N,k-1}, \quad \forall j < k-1, T_{N,j}(\sigma_{1:j}) \le B_{N,j}\}
$$
Then, it follows from the construction of permutation test that jointly on $k \le K$ and $\mathbf{c}_j = (l_1, l_2) \in C(l)$, we have $T_{N,k}^{(j)}(\text{id}) \stackrel{d}{=} T_{N,1}^{(j)}(\sigma_{1:k})$ for any $\sigma_1, \dots, \sigma_k \in \mathbf{S}_{2N}$.

Let us illustrate that on an example. Suppose that $N = 2$ and $J = 3$ so that the comparison are $(A_1, A_2)$, $(A_1, A_3)$, $(A_2, A_3)$. Consider the permutation

$$ \sigma_1 = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix} $$

Because all the scores are i.i.d., we have the joint equality in distribution:

$$ \left( \begin{array}{c} |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_3) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_3) - e_{2,1}(A_3)| \end{array} \right) \stackrel{d}{=} \left( \begin{array}{c} |e_{2,1}(A_1) + e_{1,1}(A_2) - e_{1,1}(A_1) - e_{2,1}(A_2)| \\ |e_{2,1}(A_3) + e_{1,1}(A_2) - e_{1,1}(A_3) - e_{2,1}(A_2)| \\ |e_{2,1}(A_1) + e_{1,1}(A_3) - e_{1,1}(A_1) - e_{2,1}(A_3)| \end{array} \right) $$

and hence,

$$ (T_{N,1}^{(j)}(\text{id}))_{1 \le j \le 3} \stackrel{d}{=} (T_{N,1}^{(j)}(\sigma_1))_{1 \le j \le 3}. $$

For $k = 2$, we have for $\sigma_2 = \sigma_1$,

$$ \left( \begin{array}{c} |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_3) - e_{1,1}(A_2) - e_{2,1}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_3) - e_{2,1}(A_3)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_2) - e_{2,1}(A_2) + e_{1,2}(A_1) + e_{2,2}(A_1) - e_{1,2}(A_2) - e_{2,2}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_3) - e_{1,1}(A_2) - e_{2,1}(A_2) + e_{1,2}(A_3) + e_{2,2}(A_3) - e_{1,2}(A_2) - e_{2,2}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_1) - e_{1,1}(A_3) - e_{2,1}(A_3) + e_{1,2}(A_1) + e_{2,2}(A_1) - e_{1,2}(A_3) - e_{2,2}(A_3)| \end{array} \right) \stackrel{d}{=} \left( \begin{array}{c} |e_{1,1}(A_1) + e_{2,1}(A_2) - e_{1,1}(A_1) - e_{2,1}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_2) - e_{1,1}(A_3) - e_{2,1}(A_2)| \\ |e_{1,1}(A_1) + e_{2,1}(A_3) - e_{1,1}(A_1) - e_{2,1}(A_3)| \\ |e_{1,1}(A_1) + e_{2,1}(A_2) - e_{1,1}(A_1) - e_{2,1}(A_2) + e_{1,2}(A_1) + e_{2,2}(A_2) - e_{1,2}(A_1) - e_{2,2}(A_2)| \\ |e_{1,1}(A_3) + e_{2,1}(A_2) - e_{1,1}(A_3) - e_{2,1}(A_2) + e_{1,2}(A_3) + e_{2,2}(A_3) - e_{1,2}(A_3) - e_{2,2}(A_3)| \\ |e_{1,1}(A_1) + e_{2,1}(A_3) - e_{1,1}(A_1) - e_{2,1}(A_3) + e_{1,2}(A_1) + e_{2,2}(A_3) - e_{1,2}(A_1) - e_{2,2}(A_3)| \end{array} \right) $$

and then, we get jointly

$$ (T_{N,k}^{(j)}(\text{id}))_{1 \le j \le 3, k \le 2} \stackrel{d}{=} (T_{N,k}^{(j)}(\sigma_1 \cdot \sigma_2))_{1 \le j \le 3, k \le 2}. $$

This reasoning can be generalized to any $N$, $J$ and $K$:

$$ (T_{N,k}^{(j)}(\text{id}))_{k \le K, \mathbf{c}_j \in C(l)^2} \stackrel{d}{=} (T_{N,k}^{(j)}(\sigma_{1:k}))_{k \le K, \mathbf{c}_j \in C(l)^2}. $$

Then, by construction, the different connected component $C(l)$ are independent of one another and hence,

$$ (T_{N,k}^{(j)}(\text{id}))_{k \le K, j \in \mathbf{I}} \stackrel{d}{=} (T_{N,k}^{(j)}(\sigma_{1:k}))_{k \le K, j \in \mathbf{I}}. $$

Lemma 2 follows from taking the maximum on all the comparisons and because the boundaries do not depend on the permutation.

## D.2 Proof of Lemma 3

Denote by $\mathbf{C}_k$ the (random) value of $\mathbf{C}$ at the beginning of interim $k$. We have:

$$ \begin{aligned} \text{FWE} &= \mathbb{P}(\exists j \in \mathbf{I}: H_j \text{ is rejected}) \\ &= \mathbb{P}\left(\exists k \le K: \bar{T}_{N,k}^{(\mathbf{C}_k)}(\text{id}) > B_{N,k}^{(\mathbf{C}_k)}, \arg\max_{j, \mathbf{c}_j \in \mathbf{C}_k} \bar{T}_{N,k}^{(j)}(\text{id}) \in \mathbf{I}\right). \end{aligned} \quad (15) $$
converges to

$$ \mathbb{P}\left(\left|\sum_{i=1}^{l} W_i\right| > \frac{b_l}{\tau(P, Q)}, \quad \forall j < l, \quad \left|\sum_{i=1}^{j} W_i\right| \le \frac{b_j}{\tau(P, Q)}\right). \quad (7) $$

which is equal to $\frac{\alpha}{K}$ by construction of $B_{N,j}$ for $j < k$,

We have

$$ B_{N,k} = \min \left\{ b > 0 : \frac{1}{((2N)!)^k} \sum_{\sigma_1, \dots, \sigma_k \in \mathfrak{S}_{2N}} \mathbb{1} \left\{ \begin{array}{l} \left| \sum_{j=0}^{k} t_{N,j}(\sigma_j) \right| \ge b, \\ \forall j < k, \left| \sum_{i=0}^{j} t_{N,i}(\sigma_i) \right| \le B_{N,j} \end{array} \right\} + \sum_{i=1}^{k-1} q_i \le \frac{k\alpha}{K} \right\}. $$

By the induction hypothesis, we have $q_i \xrightarrow{n \to \infty} \alpha/K$ for any $i < k$.

Let $W_1, \dots, W_k$ be i.i.d $\mathcal{N}(0, 1)$ random variables. We show the following lemma that prove part of the step $k$ of the induction hypothesis, and proved in Section E.3.

**Lemma 4.** Suppose Equation (7) is true. Then,

$$ \sup_{d_1, \dots, d_k} \left| \frac{1}{((2N)!)^k} \sum_{\sigma_1, \dots, \sigma_k \in \mathfrak{S}_{2N}} \mathbb{1} \left\{ \forall j \le k, \sum_{i=1}^j t_{N,i}(\sigma_i) \le d_j \sqrt{N} \right\} - \mathbb{P} \left( \forall j \le k, \sum_{i=1}^j W_i \le \frac{d_j}{\tau(P, Q)} \right) \right| \xrightarrow{\substack{N \to \infty \\ a.s.}} 0, $$

Then, what remains is to prove the convergence of $B_{N,k}$. Denote

$$ \Psi_k(d_k) = \mathbb{P} \left( \left| \sum_{i=1}^{k} W_i \right| > \frac{d_k}{\tau(P, Q)}, \forall j \le k-1, \left| \sum_{i=1}^{j} W_i \right| \le \frac{b_j}{\tau(P, Q)} \right), $$

we have, from Lemma 4, that

$$ \left| \Psi_k \left( \frac{B_{N,k}}{\sqrt{N}} \right) - \frac{1}{((2N)!)^k} \sum_{\sigma_1, \dots, \sigma_k \in \mathfrak{S}_{2N}} \mathbb{1} \left\{ T_{N,k}(\sigma_{1:k}) > B_{N,k}, \quad \forall j < k, T_{N,j}(\sigma_{1:j}) \le B_{N,j} \right\} \right| $$

converges to 0 as $N$ goes to infinity. Hence,

$$ \limsup_{N \to \infty} \Psi_k \left( \frac{B_{N,k}}{\sqrt{N}} \right) \le \alpha/K. $$

Then, similarly to the case $k=1$, we also have for any $\varepsilon > 0$,

$$ \liminf_{N \to \infty} \Psi_k \left( \frac{B_{N,k} - \varepsilon}{\sqrt{N}} \right) \ge \alpha/K $$

and by continuity of $\Psi_k$ (which is a consequence of the continuity of the joint c.d.f. of Gaussian random variables) we conclude that $B_{N,k}/\sqrt{N}$ converges almost surely to $b_k$.
Then, let $k_0$ correspond to the very first rejection (if any) in the algorithm. Having that the argmax is attained in $\mathbf{I}$,

$$ \bar{T}_{N,k_0}^{(\mathbf{C}_{k_0})}(\mathrm{id}) = \max\{T_{N,k_0}^{(j)}(\mathrm{id}), \mathbf{c}_j \in \mathbf{C}_{k_0}\} = \max\{T_{N,k_0}^{(j)}(\mathrm{id}), j \in \mathbf{I}\} = \bar{T}_{N,k_0}^{(\mathbf{I})}(\mathrm{id}) $$

Moreover, having that the comparisons indexed by $\mathbf{I}$ are included into $\mathbf{C}_{k_0}$, we have $B_{N,k_0}^{(\mathbf{C}_{k_0})} \ge B_{N,k_0}^{(\mathbf{I})}$. Injecting these two relations in Equation (15), we obtain:

$$ \begin{aligned} \mathrm{FWE} &\le \mathbb{P} \left( \exists k \le K : \bar{T}_{N,k}^{(\mathbf{I})}(\mathrm{id}) > B_{N,k}^{(\mathbf{I})}, \arg \max_{j \in \mathbf{C}_k} \bar{T}_{N,k}^{(j)}(\mathrm{id}) \in \mathbf{I} \right) \\ &\le \mathbb{P} \left( \exists k \le K : \bar{T}_{N,k}^{(\mathbf{I})}(\mathrm{id}) > B_{N,k}^{(\mathbf{I})} \right). \end{aligned} $$

This proves the desired result.

# E Asymptotic results for two agents

## E.1 Convergence of boundaries and comparing the means

Because there are only two agents and no early stopping, we simplify the notations and denote

$$ t_{N,i}(\sigma_i) = \sum_{n=1}^{N} e_{\sigma_i(n),i}(2) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(1), $$

and

$$ \begin{aligned} T_{N,k}(\sigma_{1:k}) &= \left| \sum_{i=1}^{k} \left( \sum_{n=1}^{N} e_{\sigma_i(n),i}(2) - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i}(1) \right) \right| \\ &= \left| \sum_{i=1}^{k} t_{N,i}(\sigma_i) \right|, \end{aligned} $$

and

$$ B_{N,k} = \inf \left\{ b > 0 : \frac{1}{((2N)!)^k} \sum_{\sigma_1, \dots, \sigma_k \in \mathbf{S}_{2N}^k} \mathbb{1}\{T_{N,k}(\sigma_{1:k}) \ge b\} \le q_k \right\}. $$

When there is only one interim ($K = 1$), we have the following convergence of the randomization law of $T_{N,1}(\sigma)$.

**Proposition 1** (Theorem 17.3.1 in (Lehmann et al., 2005)). Suppose $e_{1,1}(1), \dots, e_{N,1}(1)$ are i.i.d.from $P$ and $e_{1,1}(2), \dots, e_{N,1}(2)$ are i.i.d.from $Q$ and both $P$ and $Q$ have finite variance. Then, we have:

$$ \sup_t \left| \frac{1}{(2N)!} \sum_{\sigma \in \mathbf{S}_{2N}} \mathbb{1} \left\{ \frac{1}{\sqrt{N}} T_{N,1}(\sigma) \le t \right\} - \Phi(t/\tau(P, Q)) \right| \xrightarrow[N \to \infty]{P} 0 $$

where $\Phi$ is the normal c.d.f. and $\tau(P, Q)^2 = \sigma_P^2 + \sigma_Q^2 + \frac{(\mu_P - \mu_Q)^2}{2}$.

Using the non-sequential result from proposition 1, we can show the following theorem that controls the asymptotic law of the sequential test.

**Theorem 3.** Suppose that $P$ and $Q$ both have a finite second moment. Then, for any $1 \le k \le K$, $\frac{1}{\sqrt{N}} B_{N,k} \xrightarrow[N \to \infty]{N} b_k$ where the real numbers $b_k$ are defined as follows. Let $W_1, \dots, W_K$ be i.i.d.random variables with law $N(0, 1)$. Then $b_1$ is the solution of the following equation:

$$ \mathbb{P} \left( |W_1| \ge \frac{b_1}{\tau(P, Q)} \right) = \frac{\alpha}{K}, $$
### E.3 Proof of Lemma 4

In this proof, we denote by $E_{\sigma_{1:k}}(x)$ the expectation of the randomization law defined for some function $f: \mathfrak{S}_{2N}^k \to \mathbb{R}$ by

$$E_{\sigma_{1:k}}[f(\sigma_{1:k})] = \frac{1}{((2N)!)^k} \sum_{\sigma_1, \dots, \sigma_k \in \mathfrak{S}_{2N}} f(\sigma_{1:k}).$$

Remark that this is still random and should be differentiated from the usual expectation $\mathbb{E}$.
First, let us first handle the convergence of step $k$. We have,

$$\begin{aligned}
& \frac{1}{(2N)!} \sum_{\sigma_k \in \mathfrak{S}_{2N}} \mathbb{1} \left\{ \sum_{j=1}^{k} t_{N,j}(\sigma_j) \le d_k \sqrt{N} \right\} \\
&= \frac{1}{(2N)!} \sum_{\sigma_k \in \mathfrak{S}_{2N}} \mathbb{1} \left\{ \frac{1}{\sqrt{N}} t_{N,k}(\sigma_k) \le d_k - \frac{1}{\sqrt{N}} \sum_{j=1}^{k-1} t_{N,j}(\sigma_j) \right\} \\
&= \hat{R}_{n,k} \left( d_k - \frac{1}{\sqrt{N}} \sum_{j=1}^{k-1} t_{N,j}(\sigma_j) \right)
\end{aligned}$$

We have, because the convergence in Proposition 1 is uniform,

$$\left| \hat{R}_{n,k} \left( d_k - \frac{1}{\sqrt{N}} \sum_{j=1}^{k-1} t_{N,j}(\sigma_j) \right) - \Phi \left( \frac{1}{\tau(P,Q)} \left( d_k - \frac{1}{\sqrt{N}} \sum_{j=1}^{k-1} t_{N,j}(\sigma_j) \right) \right) \right| \\ \le \sup_t \left| \hat{R}_n(t) - \Phi \left( \frac{t}{\tau(P,Q)} \right) \right| \underset{n \to \infty}{\longrightarrow} 0$$

Then, using this convergence we have that

$$E_{\sigma_{1:k}} \left[ \mathbb{1} \left\{ \forall j < k, \sum_{i=1}^{j} t_{N,i}(\sigma_i) \le d_j \sqrt{N} \right\} \right]$$

converges uniformly on $d_1, \dots, d_k$ when $N$ goes to infinity to

$$\begin{aligned}
& E_{\sigma_{1:k}} \left[ \mathbb{1} \left\{ \forall j < k-1, \sum_{i=1}^{j} t_{N,i}(\sigma_i) \le d_j \sqrt{N} \right\} \mathbb{P} \left( W_k \le \frac{1}{\tau(P,Q)} \left( d_k - \frac{1}{\sqrt{N}} \sum_{i=1}^{k-1} t_{N,i}(\sigma_i) \right) \right) \right] \\
&= \mathbb{E} \left[ E_{\sigma_{1:k-1}} \left[ \mathbb{1} \left\{ \frac{1}{\sqrt{N}} \sum_{i=1}^{k-1} t_{N,j}(\sigma_i) \le d_j \sqrt{N}, \min(d_k - \tau(P,Q)W_k, d_{k-1}) \right\} \right] \right]
\end{aligned}$$

Then, using the induction hypothesis, this converges to Equation (6),

$$\begin{aligned}
\mathbb{E} \left[ \mathbb{1} \left\{ \frac{1}{\sqrt{N}} \sum_{i=1}^{k-1} W_i \le \frac{d_j}{\tau(P,Q)} \min(d_k - W_k, d_{k-1}) \right\} \right] &= \mathbb{E} \left[ \mathbb{1} \left\{ \forall j < k, \sum_{i=1}^{j} W_i \le \frac{d_j}{\tau(P,Q)} \right\} \right] \\
&= \mathbb{P} \left( \forall j \le k, \sum_{i=1}^{j} W_i \le \frac{d_j}{\tau(P,Q)} \right).
\end{aligned}$$
and for any $1 < k \le K$, $b_k$ is the solution of

$$ \mathbb{P}\left(\left|\frac{1}{k}\sum_{j=1}^{k} W_j\right| > \frac{b_l}{\tau(P, Q)}, \quad \forall j < k, \quad \left|\frac{1}{j}\sum_{i=1}^{j} W_i\right| \le \frac{b_j}{\tau(P, Q)}\right) = \frac{\alpha}{K}. $$

The conditions on Theorem 3 are very weak: the existence of a finite second moment to be able to use the central limit theorem.

The test performed in ADASTOP when comparing two agents corresponds to testing

$$ 1\left\{\exists k \le K : \frac{1}{\sqrt{N}}T_{N,k}(\text{id}) > \frac{1}{\sqrt{N}}B_{N,k}\right\} $$

and from Theorem 3 and the central-limit theorem, $\frac{1}{\sqrt{N}}T_{N,k}(\text{id})$ converges to $\sum_{j=1}^{k} W_j\sqrt{\sigma_P^2 + \sigma_Q^2}$, and $B_{N,k}/\sqrt{N}$ converges to $b_k$. Hence the test is asymptotically equivalent to:

$$ 1\left\{\exists k \le K : \sum_{j=1}^{k} W_j\sqrt{\sigma_P^2 + \sigma_Q^2} > b_k\right\}. $$

Then, in the case in which $\mu_P = \mu_Q$, we have $\tau(P, Q) = \sqrt{\sigma_P^2 + \sigma_Q^2}$ and

$$ \begin{aligned} \text{FWE} &= \mathbb{P}\left(\exists k \le K : \sum_{j=1}^{k} W_j\sqrt{\sigma_P^2 + \sigma_Q^2} > b_k\right) \\ &= \sum_{k=1}^{K} \mathbb{P}\left(\left|\frac{1}{k}\sum_{j=1}^{k} W_j\right| > \frac{b_l}{\tau(P, Q)}, \quad \forall j < k, \quad \left|\frac{1}{j}\sum_{i=1}^{j} W_i\right| \le \frac{b_j}{\tau(P, Q)}\right) \\ &= \sum_{k=1}^{K} \frac{\alpha}{K} = \alpha. \end{aligned} $$

Hence, for the test $H_0: \mu_P = \mu_Q$ versus $H_1: \mu_P \ne \mu_Q$, our test has asymptotic type I error $\alpha$.

## E.2 Proof of Theorem 3

For $x \in \mathbb{R}$, we denote:

$$ R_{N,k}(x) = \frac{1}{(2N)!} \sum_{\sigma_k \in \mathbf{S}_{2N}} 1\{t_{N,k}(\sigma_k) \le x\}. $$

$R_{N,k}$ is the c.d.f. of the randomization law of $t_{N,k}(\sigma_k)$, and by Proposition 1, it converges uniformly to a Gaussian c.d.f when $N$ goes to infinity.

**Convergence of $B_{N,1}$** By definition of the boundary, we have

$$ \frac{1}{\sqrt{N}} B_{N,1} = \frac{1}{\sqrt{N}} \min \left\{ b > 0 : \frac{1}{(2N)!} \sum_{\sigma_1 \in \mathbf{S}_{2N}} 1\{|T_{N,1}(\sigma_1)| > b\} \le \frac{\alpha}{K} \right\}. $$

This implies

$$ \begin{aligned} \frac{1}{(2N)!} \sum_{\sigma_1 \in \mathbf{S}_{2N}} 1\{|T_{N,1}(\sigma_1)| \le B_{N,1}\} &= \hat{R}_{N,1}\left(\frac{1}{\sqrt{N}} B_{N,1}\right) - \hat{R}_{N,1}\left(-\frac{1}{\sqrt{N}} B_{N,1}\right) \\ &\ge 1 - \frac{\alpha}{K} \end{aligned} $$
# F Understanding AdaStop through simplified algorithms – 2 agents, non sequential

## F.1 Comparing two agents

In this section, we present the simpler case of two agents, we call them $A_1$ and $A_2$. We denote by $\mathfrak{S}_{2N}$ the set of permutations of $\{1, \dots, 2N\}$ and for $\sigma_1, \sigma_2, \dots, \sigma_k \in \mathfrak{S}_{2N}$, we denote $\sigma_{1:k} = \sigma_1 \cdot \sigma_2 \cdot \dots \cdot \sigma_k$ the concatenation of the permutation $\sigma_1$ done in interim 1 with $\sigma_2$ done on interim 2, \dots, and $\sigma_k$ on interim $k$. At interim $i$, we denote the concatenation of the $2N$ evaluations obtained from the two agents with $e_{1,k}, \dots, e_{2N,k}$. Then, we indicate with $e_{\sigma_i(n),i}$ the permutation of the $n$-th evaluation using permutation $\sigma_i$ for interim $i$.

In the case where only two agents are compared, we use the following algorithm (see Section 4 for the multi-agent and fully developed version of the algorithm). We denote

$$T_{N,k}(\sigma_{1:k}) = \left| \sum_{i=1}^{k} \left( \sum_{n=1}^{N} e_{\sigma_i(n),i} - \sum_{n=N+1}^{2N} e_{\sigma_i(n),i} \right) \right|,$$

and the boundary

$$B_{N,k} \in \inf \left\{ b > 0 : \frac{1}{((2N)!)^k} \sum_{\sigma_{1:k} \in S_k} 1\{T_{N,k}(\sigma_{1:m}) \ge b\} \le \frac{\alpha}{K} \right\}, \quad (8)$$

where $S_k$ is the set of permutations $\sigma_{1:k} \in (\mathfrak{S}_{2N})^k$ such that it would not have rejected before

$$\forall m < k, \quad T_{N,m}(\sigma_{1:k}) \le B_{N,m}.$$

The algorithm is summarized in Algorithm

**Algorithm 2:** Adaptive stopping to compare two agents.

**Parameters:** Agents $A_1, A_2$, environment $\mathcal{E}$, number of blocks $K \in \mathbb{N}^*$, size of a block $N$, level of the test $\alpha \in (0, 1)$.

1. Define $2NK$ different seeds $s_{1,1}, \dots, s_{1,N}, s_{2,1}, \dots, s_{2,N}$.

2. **for** $k = 1, \dots, K$ **do**

3. &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1, 2$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Train agent $A_i$ on environment $\mathcal{E}$ with the seeds $s_{i,kN}, \dots, s_{i,(k+1)N}$.

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Collect evaluations $e_{1,k}(A_i), \dots, e_{N,k}(A_i)$ using this trained agent.

6. **end**

7. Compute the boundary $B_{N,k}$ from Equation (8).

8. **if** $T_{N,k}(id) \ge B_{N,k}$ **then**

9. &nbsp;&nbsp;&nbsp;&nbsp;Reject the equality of the agents' evaluation, break the loop.

10. **end**

11. **else**

12. &nbsp;&nbsp;&nbsp;&nbsp;If $k = K$ then accept, otherwise continue.

13. **end**

14. **end**

15. If the test was never rejected, return accept. Else return reject.

An illustration of the group sequential test is given in Fig. 3. The boundary in blue is computed sequentially to have a final level $1 - \alpha$ for the test, the red points are the observed
and for any $b < B_{N,1}$, we have:

$$ \frac{1}{(2N)!} \sum_{\sigma_1 \in \mathbf{S}_{2N}} \mathbb{1}\{|T_{N,1}(\sigma_1)| \le b\} = \hat{R}_{N,1}\left(\frac{b}{\sqrt{N}}\right) - \hat{R}_{N,1}\left(-\frac{b}{\sqrt{N}}\right) < 1 - \frac{\alpha}{K} $$

Then,

$$ \begin{aligned} & \Phi\left(\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) - \Phi\left(-\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) \\ & \ge \hat{R}_{N,1}\left(\frac{B_{N,1}}{\sqrt{N}}\right) - \hat{R}_{N,1}\left(-\frac{B_{N,1}}{\sqrt{N}}\right) - \left|\Phi\left(\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) - \hat{R}_{N,1}\left(\frac{B_{N,1}}{\sqrt{N}}\right)\right| \\ & \quad - \left|\Phi\left(-\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) - \hat{R}_{N,1}\left(-\frac{B_{N,1}}{\sqrt{N}}\right)\right| \\ & \ge 1 - \frac{\alpha}{K} - 2\sup_t \left|\Phi\left(\frac{t}{\tau(P,Q)}\right) - \hat{R}_{N,1}(t)\right|. \end{aligned} $$

Hence, by taking $N$ to infinity, we have from Proposition 1:

$$ \liminf_{N \to \infty} \Phi\left(\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) - \Phi\left(-\frac{B_{N,1}}{\tau(P,Q)\sqrt{N}}\right) \ge 1 - \frac{\alpha}{K}. $$

And for any $\varepsilon > 0$, because of the definition of $B_{N,1}$ as a supremum, we have:

$$ \limsup_{N \to \infty} \Phi\left(\frac{B_{N,1} + \varepsilon}{\tau(P,Q)\sqrt{N}}\right) - \Phi\left(-\frac{B_{N,1} + \varepsilon}{\tau(P,Q)\sqrt{N}}\right) < 1 - \frac{\alpha}{K}. $$

By continuity of $\Phi$, this implies that $\frac{1}{\sqrt{N}}B_{N,1}$ converges almost surely and its limit is such that:

$$ \Phi\left(\frac{\lim_{N \to \infty} B_{N,1}/\sqrt{N}}{\tau(P,Q)}\right) - \Phi\left(-\frac{\lim_{N \to \infty} B_{N,1}/\sqrt{N}}{\tau(P,Q)}\right) = 1 - \frac{\alpha}{K}. $$

Or said differently, let $W \sim \mathcal{N}(0, 1)$, then we have the almost sure convergence $\lim_{N \to \infty} \frac{1}{\sqrt{N}}B_{N,1} = b_1$ where $b_1$ is the real number defined by

$$ \mathbb{P}\left(|W| \ge \frac{b_1}{\tau(P,Q)}\right) = \frac{\alpha}{K}. $$

**Convergence of $B_{N,k}$ for $k > 1$.** We proceed by induction. Suppose that $\frac{1}{\sqrt{N}}B_{N,k-1}$ converges to some $b_{k-1} > 0$ and that for any $d_1, \dots, d_{k-1}$, the randomization probability, it holds that:

$$ \sup_{d_1, \dots, d_{k-1}} \left| \frac{1}{((2N)!)^{k-1}} \sum_{\sigma_1, \dots, \sigma_{k-1} \in \mathbf{S}_{2N}} \mathbb{1}\left\{ \forall j \le k-1, \sum_{i=1}^j t_{N,i}(\sigma_i) \le d_j \sqrt{N} \right\} \right. \\ \left. - \mathbb{P}\left( \forall j \le k-1, \sum_{i=1}^j W_i \le \frac{d_j}{\tau(P,Q)} \right) \right| \xrightarrow{N \to \infty, a.s.} 0, \quad (16) $$

where $W_1, \dots, W_{k-1}$ are i.i.d.$\mathcal{N}(0, 1)$ random variables. In other words, the randomization law converges uniformly to the joint law described above with the sum of Gaussian random variables.

Then, by uniform convergence and by convergence of the $B_{N,j}$, we have that:

$$ \frac{1}{((2N)!)^{k-1}} \sum_{\sigma_1, \dots, \sigma_{k-1} \in \mathbf{S}_{2N}} \mathbb{1}\{T_{N,j}(\sigma_1:j) > B_{N,k-1}, \forall j < k-1, T_{N,j}(\sigma_1:j) \le B_{N,j}\} $$
<figure><img src="image_7.png" /><figcaption>Figure 3: Illustration of the boundary for two agents.</figcaption></figure>

values of the test statistic (denoted $w_i$). The algorithm stops at the third iteration $k = 10$ because the observed value of $w_i$ is outside the boundary, which was computed using Equation (8).

## F.2 Step-down procedure

Proposed by [27], the step-down procedure is defined as follows: let $\mathcal{S}_{2N}$ be the set of all the permutations of $\{1, \dots, 2N\}$, for a permutation $\sigma \in \mathcal{S}_{2N}$ we define the concatenation $(e_n(j))_{1 \le n \le 2N}$ of the random variables being compared in hypothesis $j$, and the permuted test statistics of hypothesis $j$ is

$$T_N^{(j)}(\sigma) = \left| \sum_{n=1}^{N} e_{\sigma(n)}(j) - \sum_{n=N+1}^{2N} e_{\sigma(n)}(j) \right|.$$

This test statistics is extended to any subset of hypothesis $C \subset \{1, \dots, J\}$, as follows

$$\bar{T}_N^{(C)}(\sigma) = \max_{j \in C} T_N^{(j)}(\sigma). \qquad (9)$$

To specify the test, one compares $\bar{T}_N^{(C)}(\text{id})$ to some threshold value $B_N^{(C)}$, that is: accept all hypotheses in $C$ if $\bar{T}_N^{(C)}(\text{id}) \le B_N^{(C)}$. The threshold of the test $B_N^{(C)}$ is defined as the quantile of order $1 - \alpha$ of the permutation law of $\bar{T}_N^{(C)}(\sigma)$:

$$B_N^{(C)} = \inf \left\{ b > 0 : \left( \frac{1}{(2N)!} \sum_{\sigma \in \mathcal{S}_{2N}} \mathbb{1}\{\bar{T}_N^{(C)}(\sigma) \ge b \} \right) \le \alpha \right\}. \qquad (10)$$

In other words, $B_N^{(C)}$ is the real number such that an $\alpha$ proportion of the values of $\bar{T}_N^{(C)}(\sigma)$ exceeds it, when $\sigma$ enumerates all the permutations of $\{1, \dots, 2N\}$.

The permutation test is summarized in Algorithm 3. It is initialized with all the hypotheses to test in $C = C_0$. Then, it enters a loop where it decides to reject or not the most extreme