AdaStop: adaptive statistical testing for sound comparisons of Deep RL agents
Authors: Timothée Mathieu
Matheus Medeiros Centa
Riccardo Della Vecchia
Hector Kohler
Alena Shilova
Odalric-Ambrym Maillard
Philippe Preux
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (08/2024)
AdaStop: adaptive statistical testing for sound comparisons of Deep RL agents
Timothée Mathieu
mamothee.mathieeuiiniiii
Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL
Riccardo Della Vecchia
Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189
CRISIAL
Alena Shilova
alena.shilovoCinnrii.
Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189 CRIStAL
Matheus Medeiros Centa
matheus. medeemn-ec-ccctttrrriii..
Université de Lille, Inria, CNRS, Centrule Lille, UMR 9189
CRISIAL
Hector Kohler Université de Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL
hector, hoittrrrkollrriiii..ffh
AclariceAAmbym Maillard
odabric.miilantt@arr..
Inria, Université de Lille, CNRS, Centrale Lille, UMR 9189
CRISIAL
Philippe Preux
philippe-preunniiniio.
Université de Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRISIAL
Reviewed OpenReview: /ttps://openreviiee net/ forum? id= 1Xy2+9TLEU
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, propose theoretically sound methodology for comparing the performance of a set of algorithms. We exemplify our methodology in Deep Reinforce- ment Learning (Deep RL). The performance of one execution of a Deep RL algorithm is a random variable. Therefore, several indopendent executions are nceded 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 theoretically sound. Researchers in Deep RL often use less than 5 independent execu- tions to compare algorithms: claim that this is not enough in general. Morcover, when comparing more than 2 algorithms at once, we have to use multiple tests procedure to preserve low error guarantees. We introduce ADASTOP, new statistical test based on multiple group saquential 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 illus- trate the effectiveness of ADASTOP in various use-cases, including toy examples and Deep RL algorithms challenging Mujoco environments. ADASTOP is the first statistical test fitted to this sort of comparisons: it is both significant contribution to statistics, and an important contribution to computational studies performed in reinforcement learning and in other domains.

---

Published in Transactions on Machine Learning Research (08/2024)
1 Introduction
In many fields of computer science, it is customary to perform an experimental investigation to compare the practical performance of two more algorithms. When the behavior of 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 oblain 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 single execution lasts days or even weeks or months (such LLM training). performing such "large enough" number of executions is impossible.
To illustrate this point, let us consider the field of deep reinforcement learning (Deep RL), that is reinforce- ment 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 2022 (see Fig Lap. 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 exccutions 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, Morcover, if someone redocs 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 feature of any good experimental design.
This paper provides 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 raudom 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 Al 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 AT is straightforwwrd, 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 Section 2 In this section, we also make clear the limitations of ADASTOP. Section B introduces the main ingredients of our test, ADASTOP. Scction 4 in the formal analysis of the properties of ADASTOP. Proofs are established in appendices C to F We illustrate the use of 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.
ADASTOP in Section
To reproduce the experiments of this paper, the python code is freely available on GitHub at https: //gi hataubbocoo/iittttteeaaaaaalll hatu//daatiieee_eeee httprdvve_ttppin_____e MC_RL In addition, we provide library and command-line tool that can be used independently: the ADASTOP Python package is available at https: //g htg.hhhh.cc///iichhhhhhaaaaaaaaa
2

---

Published in Transactions on Machine Learning Research (08/2024)
2
Statistical reproducibility in RL through the lens of statistical tests
In this section we begin by identifying the key concepts necessary 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 RT.
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 (arithmetical, logical, etc), along with assignments variables, sequences of instructions, tosts and loops. Such an algorithm lypically has some lyperparameeers that control its behavior (a threshold, the dimension of the input domain, how a certain variable decays in time, the architecture of 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 cautions that many aspects of PPO may be defined in various ways, and that the notion of "the PPO algorithm" 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 make clear the distinction between parameters and hyperparameters: parameters are learned from data, while hyperparameters are set 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 the same at the beginning of each run. A special case concerns the seed of the pseudo-random number generalor. Deep RL algorithms typically use 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 usually a numerical value computed from policy evaluations. For instance, the score used in a given experiment may be the mean episodic return, 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 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 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 few random seeds possible.
2.2 Ingredients for an appropriate statistical test
Our goal is to provide statistical test to decide whether agent performs better than some others. However, strictly speaking, really decide whether two agents perform equally not by comparing the statistic of their scores measured on a sct of (evaluation) runs, up to some confidence a. 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 only valid up to some probability which 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.
3

---

Published in Transactions on Machine Learning Research (08/2024)
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 stalistics are defined for Gaussian random variables. However, one quickly figures out that the observed performance of an agent usually not Gaussian. Fig illustrates this point: we represent the distribution of the performance of 4 agents implementing 4 different RL algorithuss (PPO, SAC, DDPG, TRPO): the performance is usually multi-modal and it is not even mixture of a few Gaussian distributions as it may seem. This leads us to 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 lake a decision in a statistically significant way with the already collected data. Third, we want to be able to compare more than agents which leads us to multiple testing. Fourth, we want the conclusions of the test to be statistically reproducible, that is, somcone reproduces the exccution of the agents and applies the test in the same way as someone else, the conelusion is the same. Fifth, want to keep the number of runs within reasonable limits: for that purpose, to collect: if no decision can be made using this budget, the test can not decide whether 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.
set maximum number of scores
0.0008
SAC
0.0006
DDPG
Density
TRPO
0.0004
2-
0.0002
0.0000
30
40 50
-1000
0 1000 2000 3000
4000 5000
6000
(a)
(b)
Figure 1: Motivations for ADASTOP. (a): a census of the number of scores (Nscore) 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 Hopper, a Mujoco environment, with Nacore 30. We see from the census that most experiments used 5 or less scores (Necore S 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.
ADASTOP, our proposed statistical lest, 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 the test from top to bottom. Initially, each agent is executed N 5 times. This yields scores for each agent: these 10 initial scores are shown on the top- leftmost part of Fig, 2 labelled Interim 1, 5, along with their barplots. After the test statistics are computed, ADASTOP decides that this information is not enough to conclude, and more scores needed. This set of actions (collection of 5 scores for each agent, computation of the statisties, 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 make 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 represented, well the barplot for each agent. The test statistics are
4

---

Published in Transactions on Machine Learning Research (08/2024)
Decision
Interim N
continue
Interim N 10
continue
Interim
460
465
reject
Figure Illustration of the sequential and adaptive aspects of ADASTOP.
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 onc.
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-adaplive and only compares two agents. In (Patterson el al. 2023), the authors explore a similar workflow with added steps specialized 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 Ia). An intuition comes from the law large numbers. As the performance of an agent represented by the true mean of its scores, the more scores, the more precise the estimation of its performance. However, this does not tell anything about what sufficient number of scores draw statistically significant conclusion.
Theoretically sound comparison of multiple agents.
According lo 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 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 have a lower probability of error at each comparison. This informal argument formalized in the theory of multiple testing. However, the theory of multiple testing has almost never been used to compare

---

Published in Transactions on Machine Learning Research (08/2024)
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 RI. 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 perform better than agent A2 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, A2 may be better than A only on some easy games: does this mean that A is better than A₂? 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 interpret and visualize the results of RL agents in Atari environments. In particular the authors advise plotting confidence intervals and using the int interquartile mean instead of the mean as aggregation functions. Correctly aggregating the comparisons 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 of (Patterson et al. 2023 defines a workflow for the meaningful comparison of two RI. 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 good choice of hyperparameterss for given algorithm. When this is done, fixed number of scores (set using expert knowledge on the e are computed for each of these fully-specifeed 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 algorithrss on HalfCheetah and Hopper Mujoco tasks. One can imagine a scenario in which SAC inventors follow (Patterson al., 2023) methodology. After finding the best hyperparameters for TRPO, PPO and DDPG (Schulman 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 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 lests, the conclusion holds up to 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 way to partially answer this problem. In particular, (i) we do not claim that ADASTOP is optimal, and (ii) more work is still neces- sary 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 finite variance to get the asymptotic guarantees. As consequence, the only non-asymptotic guarantees that we have are based on the comparison
6

---

Published in Transactions on Machine Learning Research (08/2024)
N Sccore
5
5
5
5
N Scoor
10
10
30
30
2
2
2
2
2
PPO
TRPO
DDPG
SAC
DDPG
TRPO
PPO
SAC
4000
10000
2000
5000
(a) Comparisons HalfCheetah.
(b) Comparisons Hopper.
Figure 3: Example of the use ADASTOP to benchmark SAC in practice. We set the maximum number of runs B of each agent 30. The upper row lables represent the conclusions when comparing SAC to the agents in the column using N Nscore scores. For example, on HalfCheetah, ADASTOP concludes that SAC is MLB than PPO using scores for SAC and 5 scores for PPO. On Hopper, 10 scores are enough 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.
of score distributions and not on the comparison of their means. Formally, this means that we have control over the error (in Theorem the error shown to be equal to the parameter of the test a) when doing the tests:
H₃ : Pt, = Plas against Pr
where Pt, is the distribution of scores for agent 4, and (4, (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 thcoretical guarantees under strong Gaussian assumptions (see Table 1 for a comparison of the guarantees of some classical tests, in particular for nonparametric tests, finite variance is not sufficient to get strong non-asymptotic results).
Comparing distributions not what we really want to do, but it is how to proceed when performing dist ribuuutt lests and if the distributions concentrate sulficiently well (í.e., have finite variance) and the maximum sample size N K is not too low. The Gaussian approximation of the sample mean justifies the way we use ADASTOP in this article. In particular, if suppose finite variance (a hypothesis that corresponds to very weak concentration hypothesis necessary to get central limit theorem), we give asymptotic guarantees on the comparison of the means (see Theorem 2
Hy EA, [X] = Eag [X), against EA, [X] * EP, [X].
(1)
Asymptotic guarantees remain unsatisfactory because guarantecs are harder to obtain and would typically require concentration assumptions such as sub- Gaussan or bounded distributions; we leave such theoretical concerns for future works. In practice, this means that ADASTOP approximately compares the means for 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 K 2 30. For a more precise study of the sample size effect, see Scction 5.2 Please note that ADASTOP being an adaptive test, this does not mcan that at least 30 scores have be collected for each agent. This subtle point is illustrated in the experimental section of this paper.
targeting small sample sizes. Non-asymptotic
Finally, note that the test expressed by Equation 1 is bidircctional, which mcans that in thcory, concluding on this test does not tell us which of Pt, or P12 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 bidirectional test and concluding on the dircction afterward is often done by statisticians (see, in particular, the discussion in (Leventhal & Huynh] 1996) and the references therein), but this remains colceptually unsatisfactory. We keep the question of directional error for later work, which is why do not

---

Published in Transactions on Machine Learning Research (08/2024)
Theoretical Guarantees
Test
Hypothesis
Sequential
test Q vs P
test up = NQ vs up + uQ
Asymptotic
Non-Asymptotic
Asymptotic
Non-Asymptotic
t-test
Gaussian
Wilcoxon
None
X
x
x
Permutation
Finite variance
X
4
x
Bootstrap
Finite variance
X
Gaussian GST
Gaussian
ADASTOP
Finite variance
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.
write that an agent performs "better" than another in this article but rather "most likely better (MLB)".
See Section B.2 for 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 ADASTOP, First we review the statistical evaluation methods found in the literature, and then we describe our method- ology, and we express some results on ADASTOP.
3.1 Literature overview of evaluation methods
In this section, 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 challenges in deriving optimality for nonparametric model. For most nonparametric tests, only rather weak (exact) theoretical results be given, mostly on type error [Romano| 1989 Shapiro & Hubert, 1979). Recent work sequential nonparamctric tests (Shin et al. 2021 Howard et al.] 2021) show strong non-asymplotic results using concentration inequalities. However, these results often involve non-optimal constants, failing to explain uon-asymptotic efficiency. In contrast, we use permutation tests due to their empirical (Ludbrook & Dudley 1998) and thcoretical (Kim et al. 2022) efficiency for small sample sizes.
Sequential tests. closely related method for adaptive hypothesis testing consists in sequential tests. Two commonly used sequential tests the Sequential Probability Ratio test (alld 1945) and the Generalized Likelihood Ratio test (Kaufnann & Koolen 2021b. In sequential testing, the scores compared one after the other in 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 analysod as a whole once it has been collected. Conversely, in Group Sequential Test (GST) data are collected sequentially, the tests being performed at interim time points. At each interim, 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.
8

---

Published in Transactions on Machine Learning Research (08/2024)
Bandits (Best arm identification ranking). Our objective is close to the one of bandit algo- rithms (Lattimore & Szepesvári 2020): : we ménimize the stopping lime (as in the fixed-confidence setting) of the test, and we have a fized marimam budget (as in a fixed-budget setting). In our test, we allow a type error with probability a E (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 algorithus 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 the galding--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 combine them to create ADASTOP in Section | 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 nonparamelric 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 specific family of parametric distribution. In (Mehta al.) 1994), the authors use rank tests with group-sequential testing. In contrast with our work, (Mehta et al. theoretical guarantees and considers only the case of 2 agents.
1994] does not provide
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 mistake and reject the equality of two agents when their scores are statistically the same) is controlled by the parameter of the lest a, 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 el al., 2005, Chapter 17) for a textbook introduction). MMore 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. XI...., .N....,NN be i.i.d. sampled from law P and Yi....,
..... YN i.i.d. sampled from a law Q. We want to test P = Q against P # Q. Let Z = X, if i < N and Z; = Y if > N, Zi...., ZzN. The test proceeds as follows: we reject P == Q if T(i)) =
EN (Z, - ZN++) is larger than a proportion (1 - a) of the values T(a) = A (Z)r)) Zo(N+s)) where a enumerates all possible permutations of (1...., 2N} and id is the identity permutation (id(1) for all i). Formally, we define the (1 qu-untile as
1 Σ (IT() 0: N!
BN = inf b b>0:
JESM
and we reject P = Q when T(id)= 2 By. The idea is that if P Q, then T(id) should be large, and due to compensations, most T(a) should be smaller than T(id). Conversely, if P Q, the difference of mean T(r) will be closer to zero. It is then sufficient to compute T(id) and By 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 [ It can be shown that permutation tests are nonetheless good approximation of doing comparison on the means (see Appendix
IIn statistical test, we want have control on the error when Ho is truc. Hu can be seen asserting that the distribution that generated the data in certain sct of distributions Pa. The larger Po, the more complicated it is to make statistical test without using strong assumption the data. When comparing distributions, Po = (P. Q probability distributions P = Q). while when comparing the means, Po much larger because Po (P.Q Q probability distributions [E|X]] = =x((]]]
9

---

Published in Transactions on Machine Learning Research (08/2024)
3.2.2 GST comparison of two agents
In this section, we compare two agents A and A2 through a group sequential test that can be seen as a particular case of ADASTOP for two agents (see Section F In this simplified case, the testing procedure is presented in Algorithm [ We leave the case with more than 2 agents compare and the full version of ADASTOP, including multiple hypothesis testing, for Section Algorithm | uses permutation test where, al each interim, the boundary deciding the rejection is derived from the permulation 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 S2N the set of permutations of (1....,20 .N], a S2N one permulation and (n) the n-th element of for n E f1.....2y In the GST setting, we perform a permutation test at each interim k and O% S2N denotes the permutation at interim k. For 02,02 , 0 S2N, we denote di:k = 01 02 ..... 0% the co the permutation σ1 done in interim with d2 done on interim 2,..., and 0% interim k. Then, (n).s). denotes the score corresponding to the n-th element of the permuted sample at interim i, permuted by o, (in the notations of Section 3.2.1 this corresponds to Zo(s) but now, we specify the interim nunber in the notation). We denole:
h
N
2N Σ
TNA(OIA)) =
Σ
(n,(n),
Cag(n),
(2)
N=N+1
and the decision boundary:
BNK inf b>0: ((2N)))
Σ 1(Txx(01s)22) S K
(3)
OLNESN.
where K is the lotal number of interims and SN. is the set of permutations o E (S2N)* such that the test was not rejected before interim k e.g.
SN = (aru E (S2N)*: Vm < k (T S BN }.
(4)
One can show that this is equivalent to choosing By. such that
P Paw. (T Bu Vm < k, (o S B,, S a
K
We will see in Thcorem that this allows us to have control on the type crror 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 simultancous statistical tests (Lehmann et al.) 2005 Chapter 9). The idea is that the probability mistakenly reject null hypothesis (type error) generally applies only to each test considered individually. On the other hand, in order to conclude on all the tests al once, it is desirable to have an error controlled over the whole family of simultaneous tests. For this purpose, 1953) which is defined as the probability of making at least one type I crror.
use the family-wise error rate Tukeyy
Definition (Family- Wise Error (Tukey 1953)). Given set of hypothesis Hy for j E {l...., J}, its alternative H', and I C JI,....J} the set of the brue hypotheses among them, then the family wise error (FWE) is defined by:
FWE = PFn
reject H₃),
where PH, denotes the probability distribution for which all hypotheses algorithm has weak FWE control at joint level (0,1) if the FWE is smaller than when all the hypotheses are true, that is I= [I,...,J] but not necessorily olherwise. We say il has strong FWE control if FWE is smaller than a for any non-empty set of true hypotheses I + V.
hold trud") We say that an
Herr, the word "concatenation" means that apply σi on (I...,N); then dg on (N 1,..., 2N) and on, that (N = ok(). SSee also Appendix for further explanations on this concept.
10

---

Published in Transactions on Machine Learning Research (08/2024)
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 A1, A2, environment E, number of interims K N", size of an interim N, error
parameter E (0,
for k = K do
for = 1,2 do
3
Train agent A on environment N times, with the seeds
SLAN. This generates
N policies (T(kk-))+++--1 FN CN. (Ar) by running each policy =1,(k-1)N+1:-> FLANN-
Collect scores 61,6 (At),...,
end
Compute the boundary BNd using Equation 3 if (id) 2 BN then
return reject
end
10 return accept
If we want to test the equality of distributions Pt, P2,..., , Pt, the straight way to do a pairwise comparison. This creates J = L(4-1) hypotheses. We let C = (cI,.... be the set of all possible comparisons between the distributions, where C₁ = (2, C denotes a comparison between distributions Pt, and Pt, for 1, 21.2..... L}. Therefore, for Cj (21, He, denotes a hypothesis stating that Pt, and Pt₃ are equal and its alternative Hi is that Pt₃ and Pt, different. On the other hand, if one wants to compare agent to agents whose ranking docs not interest us, it may be sufficient to only compare this agent to all the others yielding the L - comparisons C₁ (1, for 2 2 l2 < 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 Bl. As Bonferroni's procedure can be very conservative in general, we prefer a slep-down method (Romano & Wolf, 2003) that performs belter 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 multiple hypothesis testing problem. It defined as follows (for non group-sequential test): for a permutation S2N and for (ex()))snns2) the random variables being compared in hypothesis j, the permuted test statistic of hypothesis j is defined by:
N
2N
()) =
Σ
Ca(n) (i)
Σ == -==++
ea(n)(o)
(5)
This test statistic is extended to any subset of hypothesis
C C (1,....,J) J} with the following formula:
T (o) max (o)
(6)
JEC
To specify the test, one compares (C)) (id) to some threshold value B that is: we accept all hypotheses
in C such that ((C) (id)= & ((O). The threshold of the test ((O) defined as the quantile of order a of the permutation law of (C) N (a):
1 (2N)
( Σ E1TH (a) 20) (0)) sa
B inf b> 0:
dESaN
In other words, (C) is the real number such that an a proportion of the values of T (a) exceeds it, when enumerates all the permutations of 2N...,,NN. The permutation test is summarized in Algorithm
11

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm 2: Multúple testing by step-down permutation test.
Parameters: a E (0,1) Input: ()) for 1 2N and j E Co (c1,...,c.))
Initialize C Co.
while C * 0 do
Compute T (C) (a) for every j and every a using Equation 6
3
Compute B using Equation 7
if ( (id) < B then
6
Accept all the hypotheses Hy.J E C and exit the loop.
else
Reject H jmaxx
where Janax
arg max TV (id). eEEC
Define C C {Cmmar
end
11 end
Algorithm 2 initialized with C Co containing all the comparisons want to test. Then, enters loop where the test decides to reject or not the most extreme hypothesis in C, i.e. H where Jmax arg max (id). Here, C the current set of neither yet rejected nor accepted hypotheses. If the test statistic ( (id) for the most extreme hypothesis in C (i.e. (id)) does not exceed the given threshold B(( 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.
(id).
The maximum of the statistic in Equation 6 for a id allows us to test intersections of hypotheses, while the threshold Bi() under the null hypotheses of equality of distribution, allows for strong control the FWE (i.e. FWE < <a). This last result follows from (Romano & Wolf 2003 Corollary 3) and is particular case of Thcorem for ADASTOP. In fact, this procedure is not specific to permutation tests, and it can be used for other tests provided some properties hold the thresholds ((
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 2 agents AL. As above, we let Co = (ci...., c,} C {I....,L} L} be the set of all the comparisons to make between the agents. I denotes the set indices of the true hypothescs among [1....,.J}.
Algorithm specifics ADASTOP. ADASTOP relics on the test statistic ((C) (.((0))) defined in equation and the boundary thresholds BC defined in Equation 10 We discuss a few implementation details in the rest this section.
Definition of the test statistic. Let e1,(1),... (2) 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 and A for which = (2) We also consider permutations of these scores lo define the test. statistics T(0) below. For a comparison j. we consider a permutation a, E SaN at interim i that reshuffles the order of the scores mapping n E f1...., 2N) on (n) E (1...., 2N). Note that if n E (1,.... ,..,, N) and (n) E (N 1,........ 2N). we are exchanging score of the first agent with a score of the second agent in the comparison. can also happen that instead, we permute two scores of the same agent. The difference between the two cases is
12

---

Published in Transactions on Machine Learning Research (08/2024)
important for the definition of the following permutation statistic:
k
N
2N Σ N+1
T (11A)
=
(()
(8)
In other words, (11s)) 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 ol...,, 0k E S2N. Let C C Co be a subset of the set considered hypothesis and let us denote:
T N.
max T T JEC N.K (.LL))
(9)
(()) N. (o1s)) 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 ils 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 SN C (misk, Vi S k; ag E S2N} 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 sufficiently large number of random permut atins (lypically for the values of N and K we consider, 10 permulations are sulficient) 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).
Ty. does not change when the permutation does not exchange any index from {I....,N} NN with an index of {N + 2N). In essence, choosing a permutation is equivalent to choosing the signs in Σ (i) >2N _ (z). And because we take the absolute value, there are (2x) possible unique values to TN.1 (up to ties when the score distributions are discrete). Then, by enumerating all the permutations for the other interims, there are 1 (2N) possible unique values to TN.K-
In practice, we use parameter B N and the number of permutations used at interim k will be |SN my min (B, 1 +)) tee. whenever possible, use all the permutations and if this is too much, use permutations drawn al random.
Definition of the boundaries. With these permutations, we define the boundary thresholds (C) N,k by:
1 Σ ((Th 2 qs
C inf b>
(10)
mi
GESN.
where Σj=1 93 S ka and where SN.4 is the subset of SN,6 such that the statistic associated to the permutation would not have been rejected before. Formally, SN.E is the following set of permutations:
K
SN. fOL Vm < k. T (a1m) S (C)
(11)
Note that 91 is not equal to K. Due to discreetness (we empirical quantile over finite number of values), qı is chosen equal to 12x J// (2N) Similarly, 42 is chosen to be as large as possible while having + 02 < 2a/K. And so on and so forth: in practice this means taking the qi 'ss as follows:
= ai (33) (3)1/(()) 4-11 for 2 sii K, and go- = 0.
(12)
One may notice that due to the discrete nature of the permutation distribution, the confidence of the test performed by ADASTOP is not a but the sum of the qi 'ss which may be smaller than the prescribed a.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Algorithm 3: ADASTOP (main algorithm) in the context of the comparison of RL agents. Its appli- cation to other types of computational agents is straightforward.
Parameters: Agents A2, .2...., AL, environment ε, comparison pairs (ci)isı where & a couple of agents that we want to compare. Integers K, N N", lest parameter a.
Set C= {1, .......J} J the set of indices for the comparisons perform.
for k ..... K do
for / = 1...L do
4
Train N times agent A on environment & This generates N policies.
5
Collect the N scores of the N policies.
end
while True do
Compute the boundaries B using Equation (1
if T > ( then
Reject Hamax where Jmax = arg max (T)) (id),, jE c).
10
11
C= C/ (jmax)
12
clsc
13
Exit the while loop.
14
end
15
end
16
if C= 0 then Exit the loop and return the decision of the test.
17
if K then Exit the loop and accept all hypotheses remaining in C.
18
end
4.1 Theoretical guarantees of AdaStop
One of the basic properties of two-sample permutation tests that when the null hypothesis true, then all permutations as likely to give certain value and permuting the sample should not change the test statistic too much. Following our choice of B as quantile of the law given the data, the algorithm has a probability to wrongly reject the hypothesis bounded by a. This informal statement is made precise in the following theorem.
Theorem (Controlled family-wise error). Let E (0, 1), and consider the multiple testing problem Hy
Pt = Pt, against H3 Pt, * Pt₃ for all the couples Cj (h,12) E {ci,...,c.) 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 E are true and the others are false, then
E
reject H2) S a.
The proof of Theorem is given in the Appendix (Section C
Hypotheses of the lest: in Theorem [ we show that Algorithm 3 tests the equality of the distributions Pt Pt, versus Pt * Pta; whereas in practice would prefer compare the means of the distribution ii, 1M, versus μi, * M421 Section 2.5 for discussion the differences between the two. We show in the Appendix E that for large N, the test comparing the means μl, Hi, versus μ4, * Pt, has the right guarantees (FWE smaller than a). This shows that even though we test the distributions, we also have an approximate test on the means. More precisely, we show the following the Appendix E for the comparison of the means of two distributions.
Theorem 2. Suppose that a E (0, 1), suppose that P and Q both have a finâte variance, and consider the lam-la testing problem Ho p [X] Ex[X]] against Hy Ep[X] + [x] Then, the test resulling from Algorithmm 3 has an asymptotic type 1 error of a
lim PHo (reject Ho) a.
N 00
14

---

Published in Transactions on Machine Learning Research (08/2024)
The proof of Theorem 2 is given in the Appendix (Section E
Power of the test: im Theorem ! there is no information on the power of the test. For any N, K, we show that, the FWE is upper-bounded by a. In the appendix D we establish Theorem G 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-asympiotic 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 Mujoco environment.
5 Experimental study
This section demonstrates ADASTOP from practitioner perspective. First, we illustrate the statistical properties of ADASTOP on toy examples in which the scores of the agents are sampled from known distribu- tions. Then, we compare empirically ADASTOP to non-adaplive approaches. Finally, we exemplify the use of ADASTOP on a real case to compare a set of Deep RT. agents.
To reproduce the experiments of this paper, the python code is froely available on GitHub at https: //github. httpaa/www..iiicceaaaaaaaaaaaaaa Sttprestttppppg____e MC____M__R_ MC__RL
5.1 Toy examples
To start with, let. us consider a toy example. In what follows, let us denote: (i) N), the normal distribution with mean μ and standard deviation o, (ii) My (p), u2, the mixture of 2 Gaussian distributions N (M of) and N(uu, with weights f and 1 - respectively.
We compare two agents A1 and A2 for which we know the distributions of their scores. We consider three cases in Fig. In the 3 cases, the scores of agent A, are drawn from (00 0.01) whereas the scores of the agent A2 are drawn from a certain mixture detailed below. We use a hyperparameter A which is the distance between the two modes of the mixture (A |u1 p2l)). Our goal is to compare the performance of agent A with the performance of agent A2 and we study the outcome of ADASTOP when A is increasing from 0 to 1. In the first case (upper-left part), the scores of A2 are drawn from (- A/2, 0.01): in this situation, the means of both distributions are both equal to O, but the distributions are different (except when A 0). In the second case (upper-right part), the scores of Ag are drawn from MY (0, 0.01; A, 0.01): in this situation, as A increases, the means of the two distributions gel. more and more apart making the rejection of the null hypothesis easier and easier. In the third case (lower part), the scores of A2 are drawn from ( 0.01; 0.94, 0.01): in this situation, the distributions are diffcrent but their mcans are both O. In all three cases, we run ADASTOP with K = 5, N = and a = 0.05. We also limit the maximum number of permutations to = 10 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 A E [0, By varying A from O to 1, we observe the evolution of the power of the test, í.e. the probability of rejecting the mull hypothesis when it is indeed false. Figure 4a shows that the error of the test remains around 0.05 for all A (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 a = 0.05, which is larger than a 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 discussed at the end of Section 4.1 In contrast, Figure 4b demonstrates which corresponds to the case where the two modes are scparated 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 (c.g. the agent has a score around for 90% of the evaluation runs). As in case 1, the mcan 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.
2
increasing trend, reaching confidence level close to 1 when A 0.6,
15

---

Published in Transactions on Machine Learning Research (08/2024)
To obtain estimation of the error, have executed each comparison M 5 10 times, and plot confidence intervals corresponding to 30 V (confidence larger than 99%) where 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.l
Laws:
M10,mm d My 0/2000 A/2.
Laws
A N.......
A M.....
03
0.000
Action eeuur vile
Pejectio Freguencee
630
039
9.%
346 (4000)
(42000)
[ (401.))
Case
(b) Case
N10.0.00
MM(--11 093, 0.13
--00
Rajest on Froqarda
LIOAE
(c) Case 3
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, well as the frequency of rejection of the null hypothesis. Please, refer to the lext for details.
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
function of the sample size (number of scores). In particular, we use the data i 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 given number of scores, we make the hypothesis that the distribution of SAC and TD3 agents scores are different, and count how many times ADASTOP decides that agent is MLB than the other (number of true positives). As the test is adaptive, we also report the effective number of scores that necessary
available http:://hhht..eoooroeoeeaaaaaaea
16

---

Published in Transactions on Machine Learning Research (08/2024)
K
2
3
5
6
0.0 (2.0)
0.0 (3.0)
0.277
(4.0)
0.465
(5.0)
0.56
(6.0)
2
0.005 (4.0)
0.33 (6.0)
0.531
(6.96)
0.602 (8.345)
0.704
(9.198)
0.213 (5.984)
0.506 (8.085)
0.627
(10.212)
0.689 (11.02)
0.785
(11.52)
4
0.371 (7.616)
0.611 (9.648)
0.744
(11.7)
0.82 (12.08)
0.845
(13.89)
5
0.465
(9.044)
0.691 (11.031)
0.78
(13.28)
0.853 (14.27)
0.884
(14.532)
6
0.534
(10.4)
0.73 (12.306)
0.837
(14.124)
0.89 (14.94)
0.911
(15.978)
7
0.599
(11.358)
0.779 (13.404)
0.879
(14.916)
0.92 (15.495)
0.939
(16.404
8
0.635 (12.322)
0.818 (13.95)
0.885
(15.824)
0.942 (16.03)
0.961 (17.268)
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 x K) when comparing SAC and TD3 agents on Mujoco HalfCheetah task. The number of permutations B is set to 10* and a is set to 0.05. ADASTOP is run 10 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 scem strange that the power is 0 in some cases. This situation is explained in the lext.
to make a decision with 0.95 confidence level. For each number of scores, we have run ADASTOP 100 timees. 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 N x K 20. However, we observe in Table 2 that when N = 4 and K = 5, ADASTOP can make decision with power of 0.82 using only 12 scores. In (Colas ct 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: already mentioned above, when N and K are both small, it can happen that ADASTOP does not allow an error up to a but it will restrict itself to smaller error and this will lead to much lower power. For instance, if N = 2, K = 2, a = 0.05 for the first interim, we have 1 (2 N aa/2] = 0 hence the first boundary is necessarily infinity and ADASTOP never rejects, e.g. with the notations of Equation 12 qi = 0. Then at the second interim ()((2)))2/2 = 3 and we use q1 + 92 = 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 interims 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 < 3).
(2N
Pa/2)/((
0.041 which
5.3 AdaStop for Deep Reinforcement Learning
In this section, we use ADASTOP to compare four commonly-used Deep RL agents on the MuJoCe 5 Todorov et al. 2012) benchmark for high-dimensional continuous control. We use the Gymnasium implementation. More specifically, we train agents on the Ant-v3, HalfCheetah-v3' Hopper-v3, Humanoid-va and Walker-v3 environments using PPO from rlberry (Domingues et al. 2021). SAC from
(Raffin et al. 2021,, DDPG from CleanRL (Huang el al. 2022), and TRPO from MushroomRL. (D DD'Eramo el 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, well as to provide examples on how to use these popular libraries with ADASTOP.
On-policy algs 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
We use MuJoCo version 2.1, as required by https:/ https///gttubb.com/oo httph//h...om//eeeaa//////oooogo 6 httpps://@tthuub.om//aaaaa Paramaa-aaaaaaaaaaaaaaaaaaa Foundation Roundation/yymasiinnn
17

---

Published in Transactions on Machine Learning Research (08/2024)
Ant-v3
HalfCheetah-v3
Hopper-v3
TRPO
PPO
SAC
2
+2
+ 42
42
-2
+
DDPG
TRPO
PPO
SAC
DDPG
TRPO
PPO
SAC
DDPG
TRPO
PPO
SAC
Humanoid-v3
Walker2d-v3
Used Budget
DDPG
DDPG
25
PPO
PPO
15
15
10
SAC
-2
1
-2
SAC
15
30 Hopper
15
10
DDPG
TRPO
PPO
SAC
DDPG
TRPO
SAC
Ant
HalfCheetahh
Humanoid
Walker2d
Figure ADASTOP decision tables for each MuJoCo environment, and the budget used to make these decisions (bottom right). The notation +24 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.
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 enviromment using ADASTOP with N = and K 6. Fig. shows the ADASTOP decision tables for each enviromment, 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 duc to the restriction to deterministic policies which hurts exploration in high-dineensioall continuous control environments such as the MuJoCo benchmarks. Furthermore, we observe that the expected ordering between PPO and TRPO 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 HallCheetah--3. Overall, the ADASTOP rankings in these experiments are not unexpected.
well the number of scores
Moreover, our experiments demonstrate that ADASTOP can make decisions with fewer scores, thus reducing the computational cost of comparing Deep RI. 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 NK = 30 scores were the ones in which ADASTOP determined that the agents were equivalent terms of their scores. This decision process 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 a sequential group test aiming at ranking agents based on their practical performance. ADASTOP may be applied various fields where the performance of algorithms random, such as machine learning, optimization. Our goal is to provide statistical grounding to
18

---

Published in Transactions on Machine Learning Research (08/2024)
define the number of times set of agents should be run to be able to confidently rank them, up some confidence level a. This is the first such test, and we think this is 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 remonstrate 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 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 thcoretical 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 alrcady 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. M-illard 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 funding received by the CHIST-ERA Project Causal explainations in Reinforcement Learning CausalXRI A.Shilova acknowledges the funding from the HPC-BigData Inria Project Lat T.Mathieu acknowledges the funding received by the SR4SG Inria exploratory action M.Centa Medeiros and K.Koller acknowledge the funding of their Pb.D.by an ANR AI PhD@Lille grant. This research is also partially supported by the CornelLA Couuts-deFFaancee project. All the authors acknowledge the Scool research group for its outstanding working environment.
R.Della Vecchia acknowledges the
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.
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling, The arcade learning environment: An evaluation platform for general agents. Journal of Arlificial Intelligence Research, 47:253 279, 2013.
Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericialli di Firenze, 8:3 3:3-62, 1936.
EunYi Chung and Joseph P. Romano. Exact and asymptotically robust permutation tests. The An- nals of Statistics, 41(2):484 - 507, 2013. doi: 10.1214/13-A0510000 URL https:///oi. http:::////o..o//11.... 10tg//..111////// 13-A0S1090
Códric Colas, Olivier Sigaud, and Pierre- Yves Oudeyer. How many random seeds? statistical power analysis in deep reinforcement learning experiments. arXiv preprint arXiv: 806. 08295, 2018.
httpp::/pproject.mmo wnrii.iiiii......... hnt.:inniii..t///ciiiaa.//// htap:://pooject.inii..rrrrt
19

---

Published in Transactions on Machine Learning Research (08/2024)
Cédric Colas, Olivier Sigaud, and Pierre- Overs Oudeyer. A hitchhiker's guide to statistical comparisons of reinforcement learning algorithms. arXiv preprinl arXiv: 9904900979, 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 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 httg/pppers/v2/11--111 html
Omar Darwiche Domingues, Yannis Flet-Berliae Berliar Edouard Leurent, Pierre Ménard, Xuedong Shang, and
Michal Valko. rlberry A Reinforcement Learning Library for Rescarch and Education, 10 2021. URL
https://githiei http://itthubb.oooobbbeerrr///// wttp://///rleerryyyylrlleeee
Logan Engstrom, Andrew Ilaas 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 Xrx:20005. 1 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 fune- tions in deep policy gradients using residual variance. In ICLR 2021-International Conference on Learning Representations, 2021.
Steven N Goodman, Danicle Fanelli, and John PA Ioannidis. What does research reproducibility mean?
Science translational medicine, ((341):341ps12-3411 2411222-ppp) ps1, 2016.
KK Gordon Lan and David T. DeMets. Discrete sequential boundaries for clinical trials. Biometrika, 70(3): 659 663, 1983.
Tuomas Haarnoja, Aurick Zhou, Picter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with 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-A0S1991. URL htttps://ooi...... http://o...org///// org/10. 1214/22222-2 1214/20-A081991
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:://mmr. org papers/
v23/21- 1334.httm
Christopher Jennison and Bruce 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, 2211)31110-111183, 2021.
Imm Kim, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimality permutation tests. The Annals of Statistics, 50(1):225- -251, 2022. doi: 10. (0.1214/11AA02100 URL /tttps://ao..rrg// 1214/ 21 ADS20001
D. Knuth. The art of programminng, volume 1, Pundamental Algorithmss. Addison-Wesled 1968.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Erich Leo Lehmann, Joseph Romano, and George Casella. Testing statistical hypotheses, volume Springer, 2005.
20

---

Published in Transactions on Machine Learning Research (08/2024)
Les Leventhal and Cam-Loi Huynh. Directional decisions for two-tailed tests: Power, error rates, and sample size. Psychologienl Methods, 1(3)2778, 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.020 02971, 2015.
John Ludbrook and Hugh Dudley, Why permutation tests are superior to and f tests in biomedical research. The American Statistician, 52(2):127-132, 1998.
Cyrus Mehta, Nitin Patel, Pralay Senchaudhuri, and Anastasios Tsiatis. Exact permutational tests for group sequential clinical trials. Biometries, pp. 1042 1053, 1994.
Sandro Pampallona and Anastasios Tsiatis. Group sequential designs for one-sided and two-sided hypoth- esis testing with provision for early stopping favor of the null hypothesis. Journal of Statistical Planning and Inference, 42(1-2):19-36) 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 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-baselines:: Reliable reinforcement learning implemennaations. Journal of Machine Learning Re- search, 22(268):1-8, 2021. URL http://jmlr orgg/papors//v222001566 html
Joseph P Romano. Bootstrap and randomization tests of some nonparametric hypotheses. The Annals of Statistics, 17(1):141-15)) 1989.
Joseph P. Romano and Michael Wolf. Exact and approximate stepdown methods for multiple hypothesis testing. SSRN Journal Electronic Journal, 2003. doi: 221199/ssmn.6633 URL https://doi.org//
213972Fesrn 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 optimiza- tion algorithms. arXiv preprint arXiv: 1er.:777.000 (07770770))) 06347, 2017.
Connie P Shapiro and Lawrence Hubert. Asymptotic normality of permutation statistics derived from weighted sums of bivariate functions. The Arnals of Statistics, 7(4):788 794, 1979.
Jachycok Shin, Aaditya Ramdas, and Alessandro Rinaldo. Nonparametric itcrated- extensions of the sequential generalized likelihood ratio test. IEEE Journal on Selecled Arens in Information Theory, 2 (2):691-704, 704, 2021.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 JEFE//SJ international conference on intelligent robots and systems, pp. 5026 5033. IEFF, 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/aoma //////117773/1118. URL http::///aai..gg//..112/////////
21

---

Published in Transactions on Machine Learning Research (08/2024)
A Index of notations
Nscore 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.
A1, .,,..,,,A AL: the agents to compare.
B[X]: expectation of the random variable X.
a: type error or Family-wisc crror of a test.
8: type II error of a test.
S set of all the permutations of {1....,ml n.]
a: generic notation for a permutation, a E S,, for some n E N
id: the identity permutation, i.e. id(k) = k for all S k S n for id S.
B: the number of random permutations used to approximate the test statistic.
Tist shorthand for the concatenation of permutations oI...., Tbe ie (ia(en,) = o (en,s) for all Kisk k.
Hy: denotes hypothesis j in a multiple lest, HiJ denotes the alternative of hypothesis H,.
Cj: denotes a comparison. This is couple (4, in L}²
j: shorthand for denoting comparison Cj.
Co set of all the comparisons done in ADASTOP.
C: current set of undecided comparisons in ADASTOP, subset of Co-
C state of C at interim k: in ADASTOP.
e(()) or (f)x score corresponding to run number i when doing the test for comparison сj for interim k.
Tx(o) and (a): test statistic. Defined Equation 6 and Equation 8
A. boundary for test statistic (C)) N such that if ( associated to C.
N.A (id) B (C)
N,k: then reject the set of hypotheses
set true hypotheses and its complement.
FWE: family-wise error, see Definition
N(H of): law of a Gaussian probability distribution with mean μ and variance o².
t(4, v): law a translated Student probability distribution with center of symmetry μ and v degrees of freedom.
My (Mi, of: #2, oz): mixture of the two normal probability distributions. N(u and N(2,, oz). Each component of the mixture weigh by and f respectively.
M (M1, M15 μ2, p1,
mixture of two Student probability distributions t(u1, vi) and (2). Each component of the mixture in weigh by and respectively.
p2):
Pnyjer: probability distribution when H,, I are true and H,yj $ I are false.
22

---

Published in Transactions on Machine Learning Research (08/2024)
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 this paper, we recall notions of statistics related to hypothesis testing that are essential to understand the ADASTOP test.
B.1 Type and type II error
In its simplest form, a statistical test is aimed at deciding whether a given collection of data xI,..., XN adheres to some hypothesis Ho (called the null hypothesis), or it is better fit for the alternative hypothesis H1. Typically, the mull hypothesis states that the mean of the distribution from which the X;'s are sampled is equal to some Pu: Ho lt Ao and H1 : # Ho where μ is the mean of the distribution of XI,...,Xx, Xy. Because 1 unknown, has to be estimated using the data. Often this done using the empirical mean ă - + X1. is random variable and some deviation from p is be expected. The theory of hypothesis tests is concerned in finding threshold such that if l - Mol because the deviation is greater than what was expected by the theory. A slightly more complex problem is to consider two samples XI...., XN and Yi.... Yn and do two-sample test deciding whether the mean of the distribution of the X,'s is equal to the mean of the distribution of the Y,'..
then say that Ho is false
In both cases, the result of a test is either reject Hg or to not reject Ho. This answer not a ground truth: there is some probability that we make an crror. However, this probability of error often controlled and can be decomposed in lype error and type II error (often denoted and / respectively, see Table 3 and Figure 6). In words, type error is when means are different) whereas means are equal. a is the probability that this event occurs. A type 1l error is when we conclude that the mull hypothesis is true (Ho is accepted, means are equal) whereas means are not equal. 3 is the probability that this event occurs.
conclude that the null hypothesis is false (Ho is rejected,
Ho is true No error Type error a
Ho is false Type ll error 8 No error
We accept Ho We reject Hu
Table Type I and type error.
The problem not symmetric: failing to reject the null hypothesis does not mean that the null hypothosis is true. It can be that there is not enough data reject Hg- It has been shown that test cannot simultaneously minimize and B. It is customary to minimize for given value of (typically is set to 0.05). The probability to reject Ho when it is false is 1 1-8 3 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 μ = Ho versus the bilateral interval μ (o),, (Ho; +oo). In practice (and in the case of this article), after rejecting the equality, we want know if μ > po or if p < po- This can be done using the sign of the test statistic ğ 10-0- However this is not direct consequence of the test because the test did not suppose direction. This means that in addition to the type I and type II, we can have type III error which is the probability to say that p > Mo when in fact μ < No or that < when in fact > Po-
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 sufficiently concentrated around its mean. See Figure 0 (right sub-figure) for visual representation of the errors, here the probability that P > po + e when p < po. Type III error is often negligible, not considered in practice, and even unknown to many researchers.
23

---

Published in Transactions on Machine Learning Research (08/2024)
Typel error
Type II error
Type III error
b
-c
Figure 6: Illustration of type 1, Il and III errors: in these plots, the shaded areas represent the probability of type I error (left), type II error (middle) and type III error (right) when testing μ 0 vs. μl o 0. denotes the threshold on test statistic tú after which we take a decision.
B.3 Multiple tests and FWE
When performing simultaneously statistical tests for I, > 1, one must be careful that the error each test accumulates. one is not cautious, the overall error may become non-negligibl. As a consequence, multiple strategies have been developed deal with multiple testing problem.
To deal with the multiple testing problem, the first step is define what is 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-Was Wise Error (the error use in this article) which is defined as the probability to make at least one false rejection:
FWE = PHYJEI (3j E I: reject H
where PHyjet jeT is used to denote a probability. IC (I.....L is the set of indices of the hypotheses that are true (and If the set of hypotheses that are actually false). To construct procedure with an FWE smaller than o, the simplest method is perhaps Bonferroni's correction (Bonferroni 1936) in which a statistical test 1)/2). And then, one would tune each hepot lest to have a lype error a/J. The union bound then implies that the FWE bounded by a:
is applied on each of the J couples of hypotheses to be tested
FWE Puςjer (reject H₂} S Pnn (reject H2) H JEI
a S 1 Sa.
TEI
Bonferroni's correction has the advantage of being very simple to implement. However, is often very conservative and the FWE most often lot smaller than a. An alternative method that performs well in practice is the step-down method that use in this article and is presented in Section 3.2.4
C Proof of Theorem 1
The proof of Theorem is based on 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 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 a/K. Then, using the step-down method construction, we show that the strong control of the FWE is consequence of the weak control because of monotony properties the boundary values of permulation test.
C.1 Simplified proof for L agents, and K ==
The proof of this theorem is bit technical. We begin by showing it in very simplified case where L agents, and K 1.
10 A pracedure controls has weak control the FWE the FWE smaller than when all null hypotheses are On the other hand, strong control when FWE is smaller than whatever the of mill hypotheses.
24

---

Published in Transactions on Machine Learning Research (08/2024)
Lemma 1. Let XI...., .N be i.i. d.om distribution P and YI,..., Ba....,Y, YN be i.i.d. from distribution Q. Let 7.N .I...., XN, ,....., YN be the concalenation of XT and YP Let E (0,1) and define BN as:
N
)
By = inf b>0: (b20:
Σ
Σ i=1
(Za()) Zo(N+a)) >6 sag.
(2N)
N
0ES2N
Then, P P- we have:
N
P
Σ
(X:
Yi)
BN aa.
N
Proof. Let us denote T(o) = N E (Za(i) Zo(n+s))- Since P Q, for any a,o' E S2N we have T(a) _ T(o)). Then, because BN does not depend the permutation (but it depends on the values of 2 ), we have, for any E S2N
(T((d)) Bx) =x)=P(((()) Br).
Now, we sum all the permutations:
P (T(id) > Bx) (2N)
Σ B[1[T(o) > Bull
0ES2N
Σ 1(T(o) > BN) Sa,
E (2N)) dES2N
which proves the result.
Next, we prove weak control in the general case.
C.2 Proof of Theorem i
In this section, we use the shorthand P instead of PH,,eeI and omit Hj.jer because 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 (I (l.....,J)) and we control the probability make at least one rejection. We have:
T e I: H, is rejected).
We decompose the FWE on the set of interims, using the fact that a rejection happens and only if we reject true hypothesis for the first time interim for some k 1...., K. These events are mutually exclusive therefore we have that their probabilities sum up and we can rewrite the FWE
K
FWE Σ P (idd
> B N.A NRa(id))
(13)
A=1
where NR₃ is the event on which we did Not Reject (NR) before interim k. NR can be defined directly for concatenation of permutations disk NRg(01:)) ('mm < k, 7(1) ( s ( )m We introduced the
definition for disk 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 we want to use the invariance by permutation to make the link with the definition of ( N. For this purpose, introduce the following lemma, that we prove in Appendix D
Lemma 2. For k S K, for any drk concatenation of k permutations:
(T (id),, B.. d (T (a(raa), D
25

---

Published in Transactions on Machine Learning Research (08/2024)
Using Lemma 2 we have for any interim & and concatenation of permutations d1:k
P (T (id) B N, (Ra(id) IP (TNA(OIs) B bo NR (Ra(o
(14)
Combing this equation with equation 13
we have:
FWE <
Σ
IP
P N NR
m
OLNESN.
Σ
{ T (. > B NR (onst)
mi TLA.SNNK
Then, use that Ti:k E SN. if and only if 01k E SN.& and NRa(F1s)) is true. Hence,
FWE
E
Σ
1 ( > B
Qk S a2
mi
k=1
k=1
where we use the definition of ( to make the link with
Strong control of FWE: To prove strong control, sufficient show the following Lemma (see Appendix D for proof), which FWE from (Romano & Wolf 2003).
adaptation of the proof of step-down multiple-test strong control of
Lemma Suppose that I C [I....,J} the set of true hypotheses. We have:
FWE = P(jel: Hj is rejected) < IP ( K:
T (id > >B>>BBBA BX,))
Lemma 3 shows that to control the FWE, it is sufficient to control the probability to reject on I given by T (NAlo)) BBg and this quantity, in turn, is exactly the FWE the restricted problem of testing (Hy))e against (Hf))æI. In other words, Lemma says that prove strong FWE control for ADASTOP, it is sufficient to prove weak FWE control, and alrcady did that in the first part of the proof.
IP 3k
K K:
Proof of Lemmas 2 and
D.1 Proof of Lemma 2
In this section, for an easier understanding, we change the notation for the score (o) to (Ai) the nh score of agent A, at interim k. In other words, we change the notation of the comparison of agent Ad, versus agent At:: in the main text comparison was denoted by C, E JI, but here we make explicit the agent from which the score has been computed resulting in the following equalities: cn,)(Ar,) c (id) and en (A,,)Ar))) e ( (id) for N.
We denote the comparisons by (ci)ier. The set of comparisons can be represented each node represents one of the agents to compare, and there exists an edge from ji to jz denoted (J, if (f1,12) E (c)) 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 / (e.g. agent 1) belongs, i.e. for any 4, C(I) there exists a path going from 1 to lz. C(I) cannot be equal to the singleton (7). because this would mean that all the comparisons with are in fact false hypotheses, and then would not belong to couple in I.
graph in which
26

---

Published in Transactions on Machine Learning Research (08/2024)
Then, it follows from the construction of permutation test that jointly & S K and Cj (41,2) C(I),
have N,K (id) & T (oiss) for any 01.-..;0k S2N.
Let us illustrate that on an example. Suppose that N = 2 and J = 3 so that the comparison are (A1, A2):
(A1, A3), (A2, As). Consider the permutation
1 2 3
=
3
Because all the scores are i.idd., we have the joint equality in distribution:
(A1) 22,1 -14))-e11AA))) e2,1(A2))
le2.1 + t1,,(A2)
e1,1 (A,)
(As) (2,1(As) c1,1(A2) c2,1(A2)
_
[22) +c1((A2) c1,1(As) c2,1
(AI) (2,((A)) e1,1(Aa) 2,, (Aa))
(A1) (11,1(a)) -1,1(A1) -22 (A3)(
and hence,
(T (i)
(o (o)))os)ss
For 2, we have for 02 01
l + 22, e1,1
62, 62, (A2)
(1,1(Ag) +,2,1
(A2)
22, (A2)
(1,)(A1) (A1) (A3)
62.1
ler,1 (A1) + (A1)
- e1,1(A2) - -22,((A2) +e1,(A1) + +e2,2AA) - (1,2(A2)
(2,((A2)
+ (Ag)
e,, (Ag)
(Ag) - -1,1(A2) 62,1(A2) + (112(Ad) + -222(AA))
- (12 (2,((A2)
(e1.( + (Ai) - -E1,(AA3)
+ (2.)
(1)) + + - (1,2(Ag) (Aa))
(a,1(A)) +221(A2) - c1,((11) e2.1
(A)) + (2,1 - 61,1(A3) e2,1
d
(e.1(A)) + =2.1(As)) e1,1(A1) -2,1
(A,) + (Ag)
C1,(AA) c2,((A2) +e1,((A) + +22
-112(AA) c22((A2]
1,,1 + e2 (A2)
e1,((As) c2,1(Ag) +c12(AAs) + (A2)
-112(Ag) -222(A2)]
(A1) + 6 (Ag) (1,)(A1) (Ag) + te1,2 (e2)(A3))
(1,((A1) -222(A3))
and then, we get jointly
(T)) (i)) =
d (T ( 02))
This reasoning can be generalized to any N, and K:
(T (il)s (osk))))ss
Then, by construction, the different connected component C(I) are independent of one another and hence,
( (id)asske (T (owR))
Lemma follows from taking the maximum all the comparisons and because the boundaries do not depend on the permutation.
D.2 Proof of Lemma 3
Denote by C2 the (random) value of C at the beginning of interim k. We have:
FWE (Ej I:
H, is rejected)
= S K:
(Cw)
N,K (id) B (Cw)
arg max 7) E.,
N. (id) E
(15)
27

---

Published in Transactions on Machine Learning Research (08/2024)
Then, let ky correspond to the very first rejection (if any) in the algorithm. Having that the argmax is attained in I,
((C))) N.ko
(id) max (T N, (id), Cj Cko max (T (id). I T N.Ao (id)
Moreover, having that the comparisons indexed by I are included into Ckg we have B Injecting these two relations in Equation 15 we obtain:
CCod No
2
B
N.
(idd (T) N. arg max T JEC,
FWE <
P
3k S K
N. (id) e
< 3 K
Nx B
This proves the desired result.
E Asymptotic results for two agents
E.1
Convergence of boundaries and comparing the means
Because there only two agents and no early stopping, simplify the notations and denote
tN,(o:)) = Σ co,
Σ
(a)())a(1,,
n=
and
k
2N Σ
TNA(O11)) =
(os(m))(
N=
Σ tN.i(oi)
and
BNN inf b> b>0: 0: ((2N)1)
Σ
((TN 2 qk
EL 2N
When there is only one interim (K = 1), we have the following convergence of the randomization law of To)(
Proposition 1 (Theorem 17.3.1 in Lehmann et al. 2005 Suppose (1, (,.(()....,e..I... (1, are i.d from P and (2). (2) are i. di.d.from Q and both P and Q have finite variance. Then, we have:
1
Σ
i{ { Tx, s1 1b (1/T(P,Q1)
P 0
sup
(2N).
N-100
0ES2N
where t is the normal c.d.f.and T(P. o2. + 002 (up (mp-pa)²
Using the non-sequential result from proposition 1 we can show the following theorem that controls the asymptotic law the sequential test.
Theorem Suppose that P and Q both have a fonite second moment. Then, for any S k S K, 1 BNNK N- by where the real numbers by are defoned as follows. Let WI...., WK be randomm VN
variables with law (0, 1). Then by the sobution of the following equation:
b
W1 2
T(P.Q)
K
28

---

Published in Transactions on Machine Learning Research (08/2024)
and for any 1 < k S K, by is the solution of
b <j<k, k Σ W S
bj -(P.Q)
P
W j=1
T(P,Q)
The conditions on Theorem central limit theorem. The test performed ADASTOP when comparing two agents corresponds to testing
g are very weak: the existence of finite second moment to be able to use the
{{ kk S K; (id) 1
BNn
and from Theorem and the central-limit theorem, VR (eTN(((id) converges to Σj=1 Wsy -og and BN,e/V /VN converges to bg. Hence the test is asymptotically equivalent to:
1 3k <
K
2 +00 bk W
j=l
Then, in the case in which μa pQq, we have T(P,Q) V0 + t and
FWE = P
SkSK K: Σ
W
o + 0z > bn
j=l
K
b T(P.Q))
Σ W
bj -(P.Q)
P
W
Vj < k
km
j=1
K
a
a
K
k=1
Hence, for the test Hg
Pp = pi versus H1
PP + μQ, our test has asymptotic type I error a.
E.2 Proof of Theorem
For x E R we denote:
RN,( (2N)
Σ 1(tN.(lRk) s x)
aLESaN
RN is the c.d.f.of the randomization law of (okk( and by Proposition it converges uniformly to a Gaussian c.d.f when goes to infinity.
Convergence of BN.1 By definition the boundary, we have
1
BN min
b> 0: (2N) G1ES2N
Σ 1(TTN[0)))>
VN
K
This implies
1 (
RNN. (- BN.1
Σ (TTx & Bri)
RN,1
(2N)
O1ESIN
a
1
K
29

---

Published in Transactions on Machine Learning Research (08/2024)
and for any b BN,1, we have:
1
Σ
5
RN.1
RN,1 (-vN)
b VNN
< 1
(2N)
VN
01ESEN
Then,
BN.1
BN.1
$
((P, QV.
BN.1
BN,1
BN.1
BN,1 VN
RN.1
RNA1
-RN.1
VN
T(P.Q)VN)
+
BN
RNNI
BN
T(P.Q))
VN
(T(P.0)
RN.1 (t)
21
ssup
K
Hence, by laking N to infinity, we have from Proposition
( BN,1 ((P.QON
BN.1 T((.QQVN
lim inf
2 K
N
And for any E 0, because the definition of BN,1 as a supremum, we have:
BN.1 (BNN +E (((P)Q)V
(_Bx.I +E ) <1- a K
lim sup & N
(=((PQ)VV)
By continuity Φ this implies that
1 BN converges almost surely and its limit is such that: VN
lim 30 BN.I/VN
[-ima~ ( BN.IVN
T(P.Q)
T(P.Q)
K
Or said differently, let W ~ (O, 1), then we have the almost sure convergence lim VN BN = bj where by is the real number defined by
1
& P(W1 W T(P.Q) K
P
Convergence of BNN for to >>1 1. We proceed by induction. Suppose that 1 BN converges to some b 0 and that for any ,i....,de d the randomization probability, it holds that:
VN
sup 4- (2N)1)
Σ
Ryssk -1
Σ im1
LN (a:) S SdvV
01 ES2N
d Wjsk - 1, Σ W. T(P.Q)) P
) N- 0, (16)
a.s.
where WI,..,, Wk-1 are ii.d.W((O,)) random variables. 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 By we have that:
Σ
1 (TNg (01:) > BNA-I Vj < 1, TN.s (013)) S BuJ)
(2N)))
30

---

Published in Transactions on Machine Learning Research (08/2024)
converges
b T(P.))
bj
P
W
Vj ا
Σ
W,
(17)
T(P. Q)
K
i=1
the last equality follows by construction of BN for j < k.
We have:
Bu min b b>0: ((2N)I*)
Σ
1
(vick E sN,los) sBx,
E (ns( 2b.
+
Σ
k-1
-
ka
K
E82
1=1
By the induction hypothesis, we have qi
カ-200 a/K K for any i < k.
Let Wi...., We be (i. 1) random variables. We show the following lemma that proves part of the stop of the induction hypothesis, proved in Section E.3
Lemma 4. Suppose Equation
17 is true. Then,
Σ 01
Visk Σ IN (a:) S Ed,V
sup dy
((2N)))
P
Pj
I k
Σ
W
<
dj
N- O.
=(P.Q)
1=1
Then, what remains is to prove the convergence of BN Let us denote:
dk T(P,Q)
by -
L (d4) P
Σ W
Vjsk 1, Σ Wg
S
From Lemma we have that
T
BN
Σ
1 [TN, (01.k) > BNN
Vj < k, TN. (01z) S BNi}
((2N)I)
converges to 0 as N goes to infinity. Hence,
B VN
lim sup V N
- a/K.
Then, similarly to the case = 1, we also have for any > 0:
BN,kk - VN
lim inf Wy N
2a/K
and by continuity of Vr (which is consequence the continuity of the joint e.d.f.of Gaussian random variables) we conclude that BN.e/Vl //V converges almost surely to by-
E.3 Proof of Lemma
In this proof, let Eor. (x) denote the expectation of the randomization law defined for some function f S + R by:
E [f(1)))
Σ
f(ork)-
((2N)))
31

---

Published in Transactions on Machine Learning Research (08/2024)
Please note that this expectation is still random and should be differentiated from the usual expectation E. First, let us first handle the convergence of step k. We have:
Σ
LN (0,) S dvVN
(2N)
on ESa
k-1
Σ
N (ox) S dx
Σ ==1
n (o,)
(2N)
VN
ORESaN
Ra,k
dk
Σ /=1
INS (oj) (
VN
Because the convergence in proposition
is uniform, we have:
Rn,k dx Σ NN. (0₂)
1
dj Σ tNo (0,)
(
T(P.Q) 0.
I sup (1) + (
Then, using this convergence we have that, when N goes to infinity,
1 Vj <k
N, (o:) S dgv.
converges uniformly d1,..., de 10:
Fanus
1 Vj Vj < h: - 1, Σ IN (ai) S sdv
Wh s T(P,Q)
di
1
NN (as)
vN
Yjck-2 Σ (d)
= E Bork-1 1 Σ.= Smin(d (P..)
(18)
VR
Then, using the induction hypothesis, Equation
18
converges to Equation
16 hence in the limit we have
Vjck-2, Σ W न(ल.O..
}]
d2 W T(P.Q) }
E l
E
Vj
k
DE Wis 7 min(ds We
i=1
dj
P
Vj
ki
W 5 -(P,Q)) (00))
F On early accept in AdaStop
Let Cc (c (ci....... c.} be a subset of the set of comparisons that we want to do. Let us denote:
(ot) = max (I Cj GEC) and [ = min (Tt) 9j c
and
B = inf
b> 0: my
Σ
2 2) S
(19)
GESX.
32

---

Published in Transactions on Machine Learning Research (08/2024)
and
B sup b>0:
Σ
(20)
m
where the 9i =
(N) 7--1 and where SN. .. is defined in 11 By construction of SN.K. for each of E SN.k. we have the following property
11
ai (2
J/C (N)) 2 and 75 = 2K
1
Bi (2N
2K N
Equation
Vm k T (af)))) S Nom and ( N.m (of) 2 N.m
In ADASTOP, modify the decision step (lines
Algorithm 3
Algorithm
Algorithm 4: Early accept.
if (id( B then
Reject jmax where Junce arg max (IR
cj E c).
Update C = C. {Cimmn
else if I.. (id) <
BBN, N then
(T (TN,e (id),
Cj e
Accept imm where Jim arg min
Update C = =C (Cimia)
The resulting algorithm has a small probability to accept a decision early, and as a consequence may be unnecessary to compute the score of some of the agents in the subsequent steps.
As an illustration of the performance of early accept, if we run ADASTOP with early parameter 8 = 0.01 (used to define the boundary in Equation (20)) on the Walker2D-v3 experiment from Section 5.3 the experiment stops at interim 2 and 10 scores have been collected for each agent. This has to be compared with the fact that, in Section 5.3 we showed that without early accept, ADASTOP uses 30 scores for DDPG and TRPO. In this example, early stopping saves a lot of computations and results in siguificant speed-up without affecting the final decisions.
G Agent comparison on Atari environments
In this section, we discuss the approach of Agarwal et al. 2021 on the problem of comparing RL agents on Atari environments. The methodology from (Agarwal et al. 2021) prescribes to give confidence intervals around some measure of location (typically mean or interquartile mean, 1QM) of the agents score. We demonstrate this approach in the left and middle sub-figures of Figure 7 However, it is not clear how to draw conclusion from such graphs (see (Cumming & Finch 2005) for discussion doing inference with confidence intervals). Moreover, there is no definite criterion on how to construct the confidence interval. For example, this approach gives rise to three very different confidence interval plots in Figure 7 the plots on the left and in the middle are the ones presented (Agarwal et al., 2021) and the plot on the right is a modified version of the plot in the middle, where we added the error due to performing multiple comparisons.
In the leftmost plot of Figure 7 it easy to draw conclusions but on the other hand the theoretical interpretation is not clear because the fact that different games have different laws for their scores is not taken into account. The middle and rightmost plots in Figure 7 are naive approach to the problem that assumes that all the games are very different from one another, and as such the confidence intervals are too large to draw conclusions. We think that there should be an internediate approach that considers a cluster of similar games (e.g. all the easy games, all the maze-like games, all the difficult games, etc.) and treat these games as having all the same law. This approach would produce smaller (and more interpretable) confidence intervals compared the naive approach, providing a middle-groun between the first plot and second plot.
33

---

Published in Transactions on Machine Learning Research (08/2024)
IQM
IQM stratified
IQM stratified corrected
DreamerV2
M-IQN Rainbow
IQN
REM
C51
DQN (Adam)
DQN (Nature)
1.0
1.5
2.0
Figure 7: 95% confidence intervals on the IQM of the 'Human Normalized Score' of set of algorithms with various methods using the results from (Agaraal et al. 2021
N
0.00
*N
0.000.01
MG1
-1,10-1,,0011100000
*MG1
1111000,00111100001)
MG2
(-.20-00.20000,10222,000
S
t(0,3)
MG3
11,2(-1,0001
*MG3
0.00,,,,01,
MtS
ts2
t(8,3)
-2
0
2
4
6
8
10
Figure 8: Toy example 3, with an illustration of the involved distributions.
H
Implementation details and additional experiments
H.1 Complementary experiment for Section 5.1
We consider 10 agents which score distributions are listed in Fig, S where the first column indicates the labels of the agents as they are used Fig. 9 We add some more notations: t(4,2) v) is the t-Student distribution with mean μ and degrees of freedom, and (1) v2)) is a mixture of 2 t-Student distributions t(m1, v1) and ((22, each weights f and 1-
Similarly to the setup of cases and 2 (see Section 5.1 execute ADASTOP with K = 5, N 5, a 0.05. As indicated in Section 4 we do not enumerate all the permutations in the permutation test as this would be too expensive. Instead we use 10a randomly selected permutations to compute our test statistics at each interim.
In contrast the experiments reported in the main text, we use early accept (with 0.01) avoid situations where all agents are compared with the maximum number scores, i.e. NK scores. This may occur when each agent has similar distribution to at least one other agent.
34

---

Published in Transactions on Machine Learning Research (08/2024)
n_teer 20
15
20
15
10
151
M62
MMG1
4
4-
MG1
+MG3
MtS
2
1
-2
151
MG2
NN
'MG1
MG1
*MG3
Mt5
MG3
t52
tS1
Má2
+
"MG1
MG1
MMG3
Mis
MG3
t52
Figure 9: ADASTOP decision table (left) and mcasured empirical distributions (right).
We show the performance of ADASTOP for multiple agents comparison in Fig. g which corresponds to the output of one execution of ADASTOP. The table (left part of Fig. 9 summarizes the decisions of the algorithm for every pair of comparisons. The violin plots (right part Fig. reflect empirically measured distributions in the comparison. From this figure, we can see that almost all agents are clustered according the mean of this distribution, except for *MG3, Mt5 and MG3 that are assigned two different groups once. Interestingly, except for *MG3, these clusters previous cases, have executed ADASTOP M = 5 000 times to measure the FWE of the test. Empirically, we measured a FWE of 0.0178 for the test comparing the distributions and a FWE of 0.0472 for the test comparing the mcans: both are below 0.05. This example illustrates the fact that ADASTOP can be efficiently used to compare the score of several agents simultaneously.
correctly formed. Moreover, similarly to the two
35

---

Published in Transactions on Machine Learning Research (08/2024)
H.2 MuJoCo Experiments
DDPG
TRPO
PPO
SAC
0.99
0.99
0.99
0.99
Learning Rate
1 X 10-3
1 1 10-3
3 x 10-1
3 10
Batch Size
128
64
64
256
Buffer Size
106
1024
2048
10
Value Loss
MSE
MSE
AVEC
Flet-Berliac et al.
2021
MSE
Use gSDE
No
No
No
Yes
Entropy Coef.
0
0
auto
GAE A
0.95
0.95
Advantage Norm.
Yes
Yes
Target Smoothing
0.005
0.005
Learning Starts
10a
101
Policy Frequency
32
Exploration Noise
0.1
Noise Clip
0.5
Max KL
10-2
Line Search Steps
10
CG Steps
100
CG Damping
10-2
CG Tolerance
10-10 10
LR Schedule
Linear to 0
Clip
0.2
PPO Epochs
10
Value Coef.
0.5
Train Freq.
step
Gradient Steps
1
Table 4: Hyperparameters used for the MuJoCo experiments.
In this section, we detail the experimental setup of the MuJoCo experiments, as well as adding new plots.
Hyperparameters. Table 4 lists the hyperparameters used for each Deep RL. agent the MuJoCo benchmark. Each agent is trained during 106 interactions with its environment in the cases of HalfCheetah- v3, H0pper-v3, and Walker2d-v3. It is trained during 2.10 interactions in the cases of Ant-v3 and Humanoid- v3. In all cases, a training episode is made of no more than 103 interactions.
Scores. According to algorithm 3 after each agent is trained, the resulting policy performs 50 evaluations episodes. The score of the agent the mean performance on these episodes.
Learning curves. Fig. 11 presents sample efficiency curves for all algorithms in each environment. The shaded areas represent 95% bootstrapped confidence intervals, computed using rliable (Agarwal et al, 2021). Note that each curve may be an aggregation of different number of scores. The number of scores can be found in the bottom right table of Fig. 10
Additional comparison plots. Fig. 10 expands upon the comparisons given the main text (in Fig. 5
by also plotting the score distributions of each agent using boxplots.
36

---

Published in Transactions on Machine Learning Research (08/2024)
HailCheetah-v3
Hoppery3
PPO
+
SAC
22
TRPO
PPO
DDPG
TRPO
DDFG
6000
10000
4000
3000
7500
2000
5000
2000
1000
2500
Humanoid-v3
Walker2d-v3
Used Budget
DDPG
DDRG
15
25
30
TRPO
DDPG
TAPO
PPO
SAC
DDPG
TIPO
PPO
SAC
6000
PPO
4000
2000
2000
SAC
15
30
15
HoitCheetah
Herpeer
Hommnoid
Walkerdd
Figure 10: ADASTOP decision tables (top) and score distributions (bottom) for each MuJoCo environment, and the budget used to make these decisions (bottom right). The medians are represented by green triangles and the means by horizontal orange lines.
SAC
DDPG
PPO
TRPO
163
And-v3
HallCheetah--33
163
Hoppar-u3
Mean of Evallation Faturns
Maan of Evaluation Raturns
1.0
Mean of Evaluation Fisurnss
50
21
2.0
1.0
0.2
0.8
To
Time Steps
1e5
Time
Time
1e6
1w3
Humanoid-43
1w5
Walker2d-v3
Mean of Evakiatoon Reiurne
Mean coluuation Returns
6
0
0.5
1.0
1.5
2.0
0.2
0.4
0.8
0.8
1.0
Time Sleps
165
Time Sleps
165
Figure 11: Mean of scores with 95% stratified bootstrap confidence intervals. Note that the curves in one figure may use a different number of scores, depending on when ADASTOP made the decisions.
H.3
Additional plot for Section 5.2
To illustrate Section 5.2 Figure 1
represents the kernel density estimation of the distribution of scores from
Colas et al. 2019
37

---

Published in Transactions on Machine Learning Research (08/2024)
SAC
0.0005
Denety
0.0002
0.0000
2500
evaluations means
Figure 12: Distributions of scores for a SAC agent and TD3 agent on HalfChootah obtained with 192 independent scores. Each score is obtained on an agent that has been trained during 2.10 interactions.
38


Reviews:
[{"review_id": "NhJ67FOXI3", "reviewer": "Reviewer_qLrz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n   \n- The paper concerns an important topic, as we currently don't have a rigorous methodology as a field for identifying whether one algorithm is better than another\n    \n- The proposed test is non-parametric, and so doesn't depend on hard-to-satisfy assumptions on the properties of the score distribution. This is especially useful for a setting like RL where score distributions for an algorithm are often multimodal / very different from standard e.g. Gaussian distributions.\n    \n- The proofs appear to be correct and are easy to read.\n    \n- The paper is well-written, providing suitable background on the relevant hypothesis-testing literature to understand the proposed method, and a clear explanation of the AdaStop algorithm. \n \n- Although the number of permutations needed to evaluate the AdaStop algorithm is quite large even in the approximate setting, given the relative cost of evaluating a deep RL algorithm this does not seem like a particularly meaningful computational burden.\n\n- The paper provides theoretical guarantees on the method which bound the probability of rejecting a correct hypothesis, and which suggest that in the large-sample limit the test is also able to evaluate the equality of distribution means with the target level $\\alpha$. \n\n - The method is friendly to batching, which is useful for the deep RL settings where a single experiment iteration can take a great deal of time. \n\n- The empirical evaluations on the MuJoCo environment show that AdaStop is able to calibrate its sampling procedure to each environment. \n\n\n**Weaknesses:**\n  \n- The paper abstract claims that AdaStop can answer the question 'is my algorithm the new state of the art' but this isn't exactly true -- know that deep RL agents are often trained on multiple environments, and AdaStop doesn't answer the question of whether the aggregate performance is the new SOTA. E.g. in Atari it is very common for an algorithmic improvement to improve performance on most but not all games. \n     \n  - Also, in the low-sample regime this method will not answer the question of whether the algorithm has a higher mean than the state of the art, but rather whether the algorithm comes from a different distribution (see point 3 below for a more detailed elaboration on this concern).\n\n- The proposed family of statistical tests does not seem very amenable to power analysis -- this seems like a problem, since if I run this test on an algorithm and it returns saying that the data does not support rejecting the null hypothesis with the desired confidence level, then I don't know how to update my belief that the algorithms really do have the same mean. \n\n- The proposed statistical test gives an answer to the question of whether two distributions are the same or not. However, for some distribution pairs it is easy to tell that they are not the same while also difficult to tell which has a greater mean. It is possible, for example, that if my new algorithm has much larger variance than a baseline but a very similar mean performance, a permutation test will identify that the two algorithms produce different return distributions with fewer samples than would be necessary to disentangle the means. As a result, I might (over-)confidently conclude that because AdaStop says to reject the null hypothesis and the sample mean for my method is higher than for the baseline, my algorithm has been robustly demonstrated to outperform the baseline.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes AdaStop, an evaluation protocol which uses a nonparametric statistical test to efficiently compare RL algorithms' performances. AdaStop is based on a permutation test, and can be applied to compare multiple algorithms simultaneously.  The paper bounds the probability that the method will falsely state that the performance distributions induced by two algorithms are different, and shows that the test asymptotically will also identify the equality of distribution means to a specified significance level. The paper evaluates AdaStop on four RL algorithms on the MuJoCo benchmark, along with synthetic experiments comparing pre-specified distributions.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My biggest concern with the paper is that the proposed test does not actually answer the question of whether one algorithm is better than another, but instead answers the question of whether one algorithm induces a different final performance distribution than another. Given that the distributions over returns induced by deep RL algorithms are often highly variable, I worry that the proposed methodology might inadvertently lead to many researchers falsely claiming that they have 'statistically significant' results showing that their method outperforms a baseline when in fact their method simply produced a different distribution over performances that happened to have a slightly higher sample mean.  The following would help to address this concern:\n\n1) An empirical evaluation of the robustness of AdaStop to distributions which have similar means but very different `shapes' (e.g. mixture of Gaussians with different numbers of modes and mode locations).\n2) Principled guidance on how to interpret the results of AdaStop if the algorithm terminates quickly but the sample means are very close.\n3) Non-asymptotic guarantees on the 'false positive' rate of the algorithm (potentially under certain easy-to-verify conditions on the distributions being tested), or at least a broader evaluation on more deep RL algorithm/environment combinations which includes a comparison between the mean performance gap between two algorithms and the number of samples requested by AdaStop (in particular, it would be encouraging to see a strong negative correlation between these two quantities).  \n\n\nThe following points would be nice to have but are less critical to my evaluation.\n\n- It would be useful to elaborate on the choice of $\\hat{S}_k$ in equation 2 when it is introduced -- when I reached equation 2 I had to stop reading and prove the correctness of the formula to myself before continuing, which broke the flow of the paper. Even just describing the mutually exclusive events whose probabilities you are computing implicitly in the equation would help to give a reader unfamiliar with permutation tests such as myself a better intuition for Algorithm 1. \n- One point in AdaStop's favour is that when evaluating a deep RL algorithm against a set of baseline algorithms we typically only care about whether the new algorithm beats the baselines, i.e. we do not care about the relative ranking of the baselines. This means we go from having $O(N^2)$ hypotheses (is algorithm i better than algorithm j for all i,j pairs) to falsify to having $O(N)$ hypotheses (is algorithm $j$ better than algorithm 1 for all $2 \\le j \\le N$), which would consequently reduce the number of algorithm evaluations needed.\n- Would it be possible to adaptively select the 'batch size' used to generate new data? In a domain like the Arcade Learning Environment, running a single experiment can take several days, and so if it is likely that more than one batch of data will be needed to falsify a hypothesis to a target significance level, it would be useful to run many iterations in parallel.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SqMvua82g4", "reviewer": "Reviewer_cbp8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper is very well-written and remarkably easy to read. All of the building blocks are presented with clarity and details. Indeed, the paper may be even too verbose in the presentation of the background (Section 3) and looks like the text could have been streamlined into a \"short\" submission (less than 12 pages).\n- The paper tackles an old and extremely important problem in deep RL, i.e. how to compare empirical results with statistical confidence. Its contribution is mostly orthogonal to (Agrawal et al. \"Deep RL at the edge of the statistical precipice\"), which focuses on performance metric rather than number of independent runs.\n- Differently from most previous works, it aims to provide a running solution (coming with code) rather than serving as a warning for bad practices.\n\nWeaknesses\n- Novelty: This may not be an actual weakness, but I think the paper is not doing a great job in highlighting what is a novel contribution. From my understanding AdaStop combines permutation testing and multiple sequential tests, but it is unclear what is novel beyond the combination itself. Also, are the theoretical results novel or directly derived from previously known guarantees?\n- Is the guarantee of AdaStop tight in any sense? It would be extremely valuable to get a sense (e.g., a lower bound on the number of runs required to get statistical significance) of how far is from optimum, as sub-optimality entails the experimental analysis of paper implementing AdaStop will incur in severe and unnecessary costs of computation and time. The empirical evaluation shows between 15 and 30 runs for simple Mujoco tasks, from which it is fair to wonder whether statistical significance in deep RL is out-of-reach for academic institutions without almost unlimited computing power.\n- From my understanding, the paper provides only an asymptotic (in the number of runs N) theoretical guarantees on the family-wise error for mean comparisons with AdaStop. This would not be ideal, as most deep RL works are concerned with comparing the mean score rather than the distribution.\n- Another potential limitation of the procedure and analysis, is that while AdaStop is adaptive on the number of runs, it does not adapt to the number of training samples. However, this seems to be crucial in RL, where a difference between algorithms performance can arise at later stage of training.\n\nMinor\n- The summation in the definition of B_N includes a space of permutation (?) that has not been defined?\n- In Table 1 the shaded bars go out of the table.\n- Captions of the figures in Section 5 are not really detailed, which means the reader has to rely a lot on the text to understand what is shown there.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of comparing empirical results in deep RL (rather the procedure is more general but presented for the deep RL setting) to state, with some statistical confidence, whether an algorithm performs better than another. It proposes AdaStop, a sequential testing procedure that works for simultaneous comparisons of multiple algorithms and automatically stops the collection of new runs whenever a desired confidence on the test is reached. The paper provides both theoretical guarantees on the family-wise error of the tests and an empirical evaluation in toy domains and Mujoco tasks. Finally, the paper provides an implementation of AdaStop that aims to become a standard statistically-grounded procedure for empirical analysis of deep RL algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not have specific changes to request (perhaps aside from the minor reported above) but rather clarifications on my comments (especially in the Weaknesses section).", "broader_impact_concerns": "This paper categorises as fundamental research, for which a specific statement on potential societal impact does not seem necessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "q3XbJPmz3x", "reviewer": "Reviewer_9doG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The core idea of using random permutation testing combined with sequential group testing to compare algorithm implementations is logical and well motivated for the types of comparisons typically performed in the RL field. The example figures in the first part of the paper are effective illustrations for understanding aspects of AdaStop. The experimental results are convincing that AdaStop is more sample efficient than current approaches. These are straightforwardly strong aspects of the paper and they represent the majority of my overall opinion of this work.\n\nHowever, I do have various critiques and questions.\n\n1. Distinguishing between algorithms and implementations/agents in Section 2.1 is helpful, but a missing distinction is between agents and \"trained agents\". Perhaps a trained agent should be labeled a \"policy\"?\n3. Regarding the conclusion\n> 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\n\n    at the end of Section 3.1, the wording makes it unclear to me if it is claiming that AdaStop is more sample efficient than all bandit algorithms or only those with a fixed budget. I would guess the latter, so is the trade-off then that fixed budget bandit algorithms will always exhaust their budget and thereby achieve lower error rates?\n\n    How does AdaStop compare with fixed confidence bandit algorithms? Presumably, fixed confidence bandit algorithms could stop earlier than AdaStop since AdaStop must (actually, is this a strict requirement?) sample the same number of scores for each agent involved in active hypotheses, whereas bandit algorithms sample a score from one agent at a time. Does this restriction on AdaStop's early stopping ability have any statistical benefit?\n\n4. The discussion around how many unique values of $T_{N, k}$ there are across all the permutations is good, but one sentence is awkward and somewhat ambiguous. By \". . . there are $\\frac{1}{2} {2N \\choose N}$ possible permutations in the first interim that give unique values to $T_{N, 1}$, I think you mean that there are $\\frac{1}{2} {2N \\choose N}$ unique values for $T_{N, 1}$ and there are not $\\frac{1}{2} {2N \\choose N}$ permutations that are special in some way from the permutations that yield the same values.\n\n    Can you not use the fact that there are fewer unique values across the permutations than the number of permutations to get more accurate estimates of the test statistics for the same computation even when $\\frac{1}{2} {2N \\choose N}^k$ is large, *e.g.*, a stratified sampling approach where unique values are sampled and combined with appropriate weights instead of sampling permutations uniformly. Furthermore, have you looked into whether or not it is faster to sort the sampled permutations according to the number of alterations from the identity permutation and applying only necessary alterations to compute the value for each permutation rather than computing each from scratch?\n\n5. There are various awkward or confusing wordings. Examples:\n    1.  > The fact is that if we can be confident that 3 executions is not enough, how many executions would be enough in a statistical significant way?\n    2. >  On the other way around, are 80 executions not too much to draw a statistically significant conclusion considering that each execution consumes resources (energy, CPU time, memory usage, etc) and contributes to pollute our planet and to the climate change.\n    3. > Moreover, we want the conclusion of the comparison to be reproducible: 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 . . .\n    - line 4 of Algorithm 1, \"running $N$ times the trained agent $A_l$\" -> \"running trained agent $A_l$ $N$ times\"\n\n\n6. Other sources of confusion:\n    1. Line 8 of Algorithm 1, why is it not simply `return reject`? And then, if both the reject and accept conditions are within the main loop, are the conditions after Line 14 still required? It looks to me like they can be removed.\n    2. The definitions of $\\mathcal{S}_k$ and $\\hat{\\mathcal{S}}_k$ implicitly depend on $N$, which is a variable in the experiments. Why not annotate them with $N$?\n    3. In Table 1, why is the power much larger given a fixed number of scores when $N$ is small? Specifically, $(N=2, K=2)$ < $(N=1, K=4)$, $(N=2, K=3) < (N=3, K=2) < (N=1, K=6)$. Except for $(N=3, K=2)$, which occasionally computes fewer scores because of early stopping, each of these tests have the same amount of data to work with on their last $k=K$ iterations. I would expect them to be the same on average.\n\n        Related, if $(N=3, K=2)$, occasionally computes fewer scores because of early stopping, why does $(N=1, K=6)$ appear to never stop early? Should not $(N=1, K=6)$ be more likely to stop early?\n    4. The comparison pairs, $(c_i)_{i \\le L}$, defined as parameters to Algorithm 3 are unused. Related, $J$ in Line 1 of Algorithm 3 appears to be undefined.\n    5. Line 4 of Algorithm 3 generates $N$ trained agents/policies for a given agent and then Line 5 states \"Collect the $N$ scores of agent $A_l$\". What if the policies or the environment are stochastic?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of comparing the performance of algorithm implementations with small sets of noisy performance samples. They develop the AdaStop algorithm that uses random permutation testing to iteratively check if the implementations under comparison can be separated or if more samples need to be gathered. AdaStop can also be used to process previously gathered data to perform a permutation testing analysis. This procedure is shown empirically to produce informative statistical comparisons between deep reinforcement learning algorithms with fewer samples than previously investigated statistical tests.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would strengthen the paper if awkward or confusing portions of the paper were improved.\n\nHow does the stochasticity of the score metric impact the confidence of agent comparisons? The definition of score at the end of Section 2.1 acknowledges that scores are typically the mean return of a policy across a set of episodes in practice, but this is merely an estimate of a policy's expected return. How do these errors interact with the confidence and power of the AdaStop analysis, and how do these errors interact with the error induced by sampling permutations? Are they entirely independent? I think this is an important discussion for the paper to include.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers overall liked the paper, and appreciate the utility in focusing on more rigorous experimentation in RL. There is, however, a concern around the fact that many readers might miss the nuance that there is a comparison of distributions rather than means. There was a lengthy discussion, and we decided on Accept, but under the conditions that this potential issue is addressed. 
1. The authors more clearly state upfront that distributions are compared, rather than means, and the ramifications of this choice.
2. It is better to tone down claims stating that AdaStop can allow practitioners to determine if their algorithm is the new state-of-the-art with statistical guarantees

It is useful here to include snippets/paraphrasings of our discussion.
From a reviewer
"After the discussion with the authors and the other reviews, and after re-reading the paper, I have decided to recommend rejecting this paper. I am concerned that this paper will be misused by practitioners to make claims about statistical significance and confidence that are inaccurate or misleading. 
...
Strictly speaking, AdaStop can only verify a common assumption: that different algorithms produce different score distributions. Except under the strong assumptions of Theorem 2, all statistical claims when using AdaStop must be phrased in terms of score distributions. As reviewer qLrz correctly pointed out, there are common practical scenarios where knowing that score distributions differ tells you nothing about expected scores. Since the paper claims that AdaStop is a solution to identify algorithms that perform better in a statistically significant way without assumptions on the algorithm score distributions, it is a major problem that achieving statistical confidence on such decisions do actually require score distributions to be sufficiently concentrated around their means. In fact, this concentration assumption is not merely that most of the probability mass is near the mean (as it is in Case 3 of Figure 4), but that there is no substantial mass far from the mean.

The authors say on page 12 that "[doing a test on distributions and ranking based on sample means] is justified because without strong concentration assumptions on the distributions, we lack control on the mean of the distributions." I have two responses to this claim. First, lacking the means to make a statistically meaningful statement about the difference of means does not justify the claim that a small sample test on distributions tells us anything about the difference in means. Second, bootstrap sampling can actually construct confidence intervals and tests for differences in means without making any assumptions on the score distributions.

Why would we use AdaStop over bootstrap sampling? The paper's answer on page 15 is that AdaStop makes a decision using fewer scores. In the example, they say that AdaStop uses 12 instead of 15 scores to achieve an empirical power of 0.82. They compare their empirical power to the power of Welch and boostrapping tests, but it is unclear to me if they really have the same meaning. I do not believe we have any guarantee about the accuracy of AdaStop's empirical power. Perhaps a more direct comparison of the accuracy of AdaStop's empirical power with bootrapping's power could have been useful here.

Overall, I find that this paper over-claims that AdaStop can allow practitioners to determine if their algorithm is the new state-of-the-art with statistical guarantees by failing to adequately address the issue that the guarantees AdaStop provides are not directly related to expected performance. This issue is subtle enough that I did not notice it on my first read through, and important enough that I recommend rejection to avoid future similar misunderstandings.

To give the paper its due, there is definitely something interesting about using permutation testing to compare algorithms. Ultimately, AdaStop is using the number of scores to complete a permutation test as an early stopping heuristic. I feel like there is still potential in using this heuristic, particularly combined with bootstrap sampling to construct confidence intervals, and completing more runs only where strong confidence is required. I look forward to the theory article on AdaStop, perhaps it will resolve the issues I have brought up here and reduce the potential I see for AdaStop to be misused."

Another issue raised by an author is the it is potentially implied that AdaStop is tight, and if 30 runs are required for AdaStop, then one could not get away with less. But, of course, a different statistical test might be able to. If there are any such claims, then do consider modifying them. 

In summary, the key things to address are the two points I bulleted above. These are strictly writing changes, so an Accept with Minor Revisions is appropriate. I will check the changes. If you need to clarify the revisions before doing them, then feel free to post a question to me (the action editor).
Decision: Accept (poster)