converges to

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

the last equality follows by construction of $B_{N,j}$ for $j < k$.

We have:

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

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

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

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

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

Then, what remains is to prove the convergence of $B_{N,k}$. Let us denote:

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

From Lemma 4, we have that

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

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

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

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

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

and by continuity of $\Psi_k$ (which is a consequence of the continuity of the joint c.d.f.of Gaussian random variables) we conclude that $B_{N,k}/\sqrt{N}$ converges almost surely to $b_k$.

## E.3 Proof of Lemma 4

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

$$ E_{\sigma_{1:k}}[f(\sigma_{1:k})] = \frac{1}{((2N)!)^k} \sum_{\sigma_1, \dots, \sigma_k \in \mathbf{S}_{2N}} f(\sigma_{1:k}). $$
**Algorithm 3:** Multiple testing by step-down permutation test.

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

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

1. Initialize $C \leftarrow C_0$.

2. **while** $C \neq \emptyset$ **do**

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

4. Compute $B_n^{(C)}$ using Equation (10).

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

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

7. **else**

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

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

10. **end**

11. **end**

hypothesis in $C$, the set of not yet discarded, nor accepted hypotheses. If the test statistic $T_N^{(j)}(\text{id})$, for the most extreme hypothesis in $C$ (i.e. $\overline{T}_N^{(C)}(\text{id})$), does not exceed the given threshold $B_n^{(C)}$, then it accepts all the hypotheses in $C$ and breaks the loop. Otherwise, it just rejects the most extreme hypothesis and it discards that from the set $C$. Then, it enters the loop again until the set of remaining hypotheses is empty.

The maximum of the statistics in Equation (9) for $\sigma = \text{id}$ allows to test an intersection of hypotheses, while, the threshold $B_n^{(C)}$, because of the equality of distribution hypotheses, allows to have strong control on the FWE (i.e. $\text{FWE} \le \alpha$). In fact, this procedure is not specific to permutation tests, and it can be used for other tests provided some properties on the thresholds $B_n^{(C)}$.

**remark 1** (Non-independent hypothesis). The acute reader may have noticed that as the hypotheses are not assumed to be independent, we can not resort to Benjamini-Hochberg or similar procedure [3] here. We adapt this procedure to the case of group sequential testing later in Section 4.

# G On early accept in AdaStop

In this section, we present in details the early-accept heuristic proposed to speed up computation of AdaStop. Let $C \subset \{1, \dots, J\}$ be a subset of the set of comparisons that we want to do, denote

$$ \overline{T}_{N,k}^{(C)}(\sigma_1^k) = \max \left( T_{N,k}^{(j)}(\sigma_1^k), \quad j \in C \right) \quad \text{and} \quad \underline{T}_{N,k}^{(C)}(\sigma_1^k) = \min \left( T_{N,k}^{(j)}(\sigma_1^k), \quad j \in C \right) $$

$$ \overline{B}_{N,k}^{(C)} = \inf \left\{ b > 0 : \frac{1}{m_k} \sum_{\sigma \in \hat{S}_k} \mathbb{1}\{\overline{T}_{N,k}^{(C)}(\sigma_1^k) \ge b\} \le \underline{q}_k \right\} \quad (11) $$

and

$$ \underline{B}_{N,k}^{(C)} = \sup \left\{ b > 0 : \frac{1}{m_k} \sum_{\sigma \in \hat{S}_k} \mathbb{1}\{\underline{T}_{N,k}^{(C)}(\sigma_1^k) \le b\} \le \underline{q}_k \right\}. \quad (12) $$

Inria
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:

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

Because the convergence in proposition 1 is uniform, we have:

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

Then, using this convergence we have that, when N goes to infinity,

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

converges uniformly on $d_1, \dots, d_k$ to:

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

Then, using the induction hypothesis, Equation (18) converges to Equation (16), hence in the limit we have

$$
\begin{align*}
\mathbb{E} \left[ 1 \left\{ \frac{\forall j < k-2}{\frac{1}{\sqrt{N}} \sum_{i=1}^{k-1} W_i \le \frac{d_j}{\tau(P,Q)} \min(d_k - W_k, d_{k-1})} \right\} \right] &= \mathbb{E} \left[ 1 \left\{ \forall j < k, \sum_{i=1}^{j} W_i \le \frac{d_j}{\tau(P,Q)} \right\} \right] \\
&= \mathbb{P} \left( \forall j \le k, \sum_{i=1}^{j} W_i \le \frac{d_j}{\tau(P,Q)} \right).
\end{align*}
$$

F On early accept in AdaStop

Let $\mathbf{C} \subset \{\mathbf{c}_1, \dots, \mathbf{c}_J\}$ be a subset of the set of comparisons that we want to do. Let us denote:

$$
\bar{T}_{N,k}^{(C)}(\sigma_1^k) := \max \left( T_{N,k}^{(j)}(\sigma_1^k), \mathbf{c}_j \in \mathbf{C} \right) \quad \text{and} \quad \underline{T}_{N,k}^{(C)}(\sigma_1^k) := \min \left( T_{N,k}^{(j)}(\sigma_1^k), \mathbf{c}_j \in \mathbf{C} \right),
$$

and

$$
\bar{B}_{N,k}^{(\mathbf{C})} := \inf \left\{ b > 0 : \frac{1}{m_k} \sum_{\sigma \in \hat{\mathcal{S}}_{N,k}} 1\{\bar{T}_{N,k}^{(\mathbf{C})}(\sigma_1^k) \ge b\} \le \bar{q}_k \right\}, \quad (19)
$$
where $\sum_{j=1}^{k} q_j \le \frac{k\alpha}{K}$ and $\sum_{j=1}^{k} \bar{q}_j \le \frac{k\beta}{K}$ and where $\hat{S}_k$ is the subset of $S_k$ such that it would not have accepted or rejected before: for each $\sigma_1^k \in \hat{S}_k$, we have the following property

$$ \forall m < k, \quad \bar{T}_{N,m}^{(C)}(\sigma_1^k) \le \bar{B}_{N,m}^{(C)} \quad \text{and} \quad \underline{T}_{N,m}^{(C)}(\sigma_1^k) \ge \underline{B}_{N,m}^{(C)}. $$

In AdaStop, modify the decision step (line 10 to 15 in Algorithm 1) to The resulting algorithm

<table><thead><tr><th colspan="2">Algorithm 4: Early accept</th></tr></thead><tbody><tr><td>1</td><td><b>if</b> <span style="text-decoration: overline;">T</span><sub>N,k</sub><sup>(C)</sup>(id) &gt; <span style="text-decoration: overline;">B</span><sub>N,k</sub><sup>(C)</sup> <b>then</b></td></tr><tr><td>2</td><td>Reject <i>H</i><sub>jmax</sub> where <i>j</i><sub>max</sub> = arg max (<i>T</i><sub>N,k</sub><sup>(j)</sup>(id), <i>j</i> &isin; <b>C</b>).</td></tr><tr><td>3</td><td>Update <b>C</b> = <b>C</b> \ {<i>j</i><sub>max</sub>}</td></tr><tr><td>4</td><td><b>else if</b> <span style="text-decoration: overline;">T</span><sub>n,k</sub><sup>(C)</sup>(id) &lt; <span style="text-decoration: overline;">B</span><sub>N,k</sub><sup>(C)</sup> <b>then</b></td></tr><tr><td>5</td><td>Accept <i>H</i><sub>jmin</sub> where <i>j</i><sub>min</sub> = arg min (<i>T</i><sub>N,k</sub><sup>(j)</sup>(id), <i>j</i> &isin; <b>C</b>).</td></tr><tr><td>6</td><td>Update <b>C</b> = <b>C</b> \ {<i>j</i><sub>min</sub>}</td></tr></tbody></table>

have a small probability to accept a decision early, and as a consequence it may be unnecessary to compute some of the agent in the subsequent steps.

As illustration of the performance of early accept, if one was to execute AdaStop with early parameter $\beta = 0.01$ for the Walked2D-v3 experiment from Section 6.3, the experiment would stop at interim 2 and 10 seeds would have been used for each agent. By comparison, in Section 6.3 we showed that without early accept, Adastop uses 30 seeds for DDPG and TRPO. Early stopping give in this instance a consequent speed-up without affecting the final decisions.

# H Implementation details and additional plots

## H.1 Plot of the census on the number of seeds in ICML 2022 RL articles

In Fig 4, we present the results of the census we did on the number of seeds used in the RL articles from ICML 2022. We plot only the articles having experiment on environments using Mujoco as this represent the majority of the articles.

## H.2 The distribution of evaluation performances in Deep RL problems

In Fig. 5, we represent the densities of the evaluations (cumulative rewards) of some RL agents on the Hopper environment (see Section 6.3 for the details on the experiment). The p-values for the Shapiro normality test on these data are: 0.0032 for PPO$^5$, 0.0003 for SAC, 0.0393 for DDPG and 0.015 for TRPO. As all p-values are less than $\alpha = 0.05$, we reject the null hypothesis of normality for at least one of them. This confirms what our eyes already told us: the performance of Deep-RL agents is not normally distributed (at least on this example).

## H.3 Complementary experiment for Section 6.1

In this third example, we suppose we have 10 agents whose performance distributions are listed in Fig. 6, where the first column indicates the labels of the agents as they are shown in Fig. 7.

<footnote>$^5$Here, PPO, SAC, DDPG, and TRPO should be read as “an agent that implements xxx”.</footnote>
and

$$ \underline{B}_{N,k}^{(C)} := \sup \left\{ b > 0 : \frac{1}{m_k} \sum_{\sigma \in \hat{S}_{N,k}} 1\{\underline{T}_{N,k}^{(C)}(\sigma_1^k) \le b\} \le \underline{q}_k \right\} \quad (20) $$

where the $\underline{q}_i = \lfloor \frac{\alpha_i}{2K} \binom{2N}{N} \rfloor / (\frac{1}{2} \binom{2N}{N}) - \underline{q}_{i-1}$ and $\bar{q}_i = \lfloor \frac{\beta_i}{2K} \binom{2N}{N} \rfloor / (\frac{1}{2} \binom{2N}{N}) - \bar{q}_{i-1}$ and where $\hat{S}_{N,k}$ is defined in Equation (11). By construction of $\hat{S}_{N,k}$, for each $\sigma_1^k \in \hat{S}_{N,k}$, we have the following property

$$ \forall m < k, \quad \bar{T}_{N,m}^{(C)}(\sigma_1^k) \le \bar{B}_{N,m}^{(C)} \quad \text{and} \quad \underline{T}_{N,m}^{(C)}(\sigma_1^k) \ge \underline{B}_{N,m}^{(C)}. $$

In ADA STOP, modify the decision step (lines 9 to 13 in Algorithm 3) to Algorithm 4.

**Algorithm 4: Early accept.**

1. **if** $\bar{T}_{N,k}^{(C)}(\text{id}) > \underline{B}_{N,k}^{(C)}$ **then**
2. **Reject** $H_{j_{\text{max}}}$ where $c_{j_{\text{max}}} = \arg\max (T_{N,k}^{(j)}(\text{id}), c_j \in \mathbf{C})$.
3. **Update** $\mathbf{C} = \mathbf{C} \setminus \{c_{j_{\text{max}}}\}$
4. **else if** $\underline{T}_{N,k}^{(C)}(\text{id}) < \bar{B}_{N,k}^{(C)}$ **then**
5. **Accept** $H_{j_{\text{min}}}$ where $c_{j_{\text{min}}} = \arg\min (T_{N,k}^{(j)}(\text{id}), c_j \in \mathbf{C})$.
6. **Update** $\mathbf{C} = \mathbf{C} \setminus \{c_{j_{\text{min}}}\}$

The resulting algorithm has a small probability to accept a decision early, and as a consequence it 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 ADA STOP with early parameter $\beta = 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, ADA STOP uses 30 scores for DDPG and TRPO. In this example, early stopping saves a lot of computations and results in a significant 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, IQM) 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 a conclusion from such graphs (see (Cumming & Finch, 2005) for a discussion on 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 in (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 is 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 a 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 intermediate 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 to the naive approach, providing a middle-ground between the first plot and second plot.
<figure><img src="image_8.png" /><figcaption>Figure 4: Census of the number of seeds used in RL articles published in ICML 2022 proceedings to study environments using Mujoco.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 5: Empirical density of the performances of various agents on Hopper Mujoco environment using 15 seeds for each agent.</figcaption></figure>

Similarly to Cases 1 and 2 (see Section 6.1), we execute AdaStop with $K = 5$, $N = 5$, $\alpha = 0.05$ and the maximum number of permutations $B = 10\,000$. In contrast to Cases 1 and 2, in Case 3 we use early accept (with $\beta = 0.01$) to avoid situations when all agents are run with all *NK* seeds, which may occur when each agent has a similar distribution to at least one another agent in comparison.

We show the performance of AdaStop for multiple agents’ comparison in Fig. 7, which corresponds to the output of one execution of AdaStop (with labels summarized in Fig. 6). The table (left) summarizes the decisions of the algorithm for every pair of comparisons, and violin plots (right) reflect empirically measured distributions in the comparison. From this figure, we can see that almost all agents are grouped in clusters of distributions with equal means, except for *MG3 that is assigned to two different groups at the same time. Interestingly, these clusters except for *MG3 are correctly formed. Moreover, similarly to two previous cases, we have executed AdaStop $M = 5\,000$ times to measure FWE of the test. The empirical measurements are 0.0178 of rejection rate of at least one correct hypothesis when comparing distributions and 0.0472 of rejection rate when comparing means, both are below 0.05. Thus, AdaStop can be efficiently
<figure><img src="image_9.png" /><figcaption>Figure 7: 95% confidence intervals on the IQM of the "Human Normalized Score" of a set of algorithms with various methods using the results from (Agarwal et al., 2021).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 8: Toy example 3, with an illustration of the involved distributions.</figcaption></figure>

# 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. 8, where the first column indicates the labels of the agents as they are used in Fig. 9. We add some more notations: $t(\mu, \nu)$ is the t-Student distribution with mean $\mu$ and $\nu$ degrees of freedom, and $M_1^t(t(\mu_1, \nu_1), t(\mu_2, \nu_2))$ is a mixture of 2 t-Student distributions $t(\mu_1, \nu_1)$ and $t(\mu_2, \nu_2)$, each weights $f$ and $1-f$.

Similarly to the setup of cases 1 and 2 (see Section 5.1), we execute ADASTOP with $K = 5$, $N = 5$, $\alpha = 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 $10^4$ randomly selected permutations to compute our test statistics at each interim.

In contrast to the experiments reported in the main text, we use early accept (with $\beta = 0.01$) to avoid situations where all agents are compared with the maximum number of scores, i.e. NK scores. This may occur when each agent has a similar distribution to at least one other agent.
<figure><img src="image_10.png" /><figcaption>Figure 6: Toy example 3, with an illustration of the involved distributions.</figcaption></figure>

used to compare performances of several agents simultaneously.

## H.4 Additional plot for Section 6.2

## H.5 MuJoCo Experiments

In this section, we go into details about the experimental setup of the MuJoCo experiments, as well as present additional plots.

**Hyperparameters.** Table 3 details the hyperparameters used with each Deep RL on the MuJoCo benchmark. For all agents, we use a budget of one million time steps for HalfCheetah-v3, Hopper-v3, and Walker2d-v3, and a budget of two million time steps for Ant-v3 and Humanoid-v3. Finally, we use a maximum horizon of one thousand steps for all environments.

**Evaluation.** Agents are evaluated by stopping the training procedure on predetermined time steps and averaging the results of 50 evaluation episodes.

**Learning Curves.** Fig. 10 presents sample efficiency curves for all algorithms in each environment. The shaded areas represent 95% bootstrapped confidence intervals, computed using *rliable* [1]. Note that each curve may be an aggregation of a different number of runs, which can be found in the bottom right of Fig. 9.

**Additional Comparison Plots.** Fig. 9 expands upon the comparisons given in the main text (in Fig. 2) by also plotting the evaluation distributions of each agent using boxplots.
<figure><img src="image_11.png" /><figcaption>Figure 9: ADASTOP decision table (left) and measured empirical distributions (right).</figcaption></figure>

We show the performance of ADASTOP for multiple agents comparison in Fig. 9, 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 of Fig. 9) reflect empirically measured distributions in the comparison. From this figure, we can see that almost all agents are clustered according to the mean of this distribution, except for *MG3, Mt5 and MG3 that are assigned to two different groups at once. Interestingly, except for *MG3, these clusters are correctly formed. Moreover, similarly to the two previous cases, we 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 means: both are below 0.05. This example illustrates the fact that ADASTOP can be efficiently used to compare the score of several agents simultaneously.
<table><caption>Table 3: Hyperparameters used for the MuJoCo experiments.</caption><thead><tr><th></th><th>DDPG</th><th>TRPO</th><th>PPO</th><th>SAC</th></tr></thead><tbody><tr><td>γ</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td></tr><tr><td>Learning Rate</td><td>1 × 10<sup>-3</sup></td><td>1 × 10<sup>-3</sup></td><td>3 × 10<sup>-4</sup></td><td>3 × 10<sup>-4</sup></td></tr><tr><td>Batch Size</td><td>128</td><td>64</td><td>64</td><td>256</td></tr><tr><td>Buffer Size</td><td>10<sup>6</sup></td><td>1024</td><td>2048</td><td>10<sup>6</sup></td></tr><tr><td>Value Loss</td><td>MSE</td><td>MSE</td><td>AVEC [12]</td><td>MSE</td></tr><tr><td>Use gSDE</td><td>No</td><td>No</td><td>No</td><td>Yes</td></tr><tr><td>Entropy Coef.</td><td>-</td><td>0</td><td>0</td><td>auto</td></tr><tr><td>GAE λ</td><td>-</td><td>0.95</td><td>0.95</td><td>-</td></tr><tr><td>Advantage Norm.</td><td>-</td><td>Yes</td><td>Yes</td><td>-</td></tr><tr><td>Target Smoothing</td><td>0.005</td><td>-</td><td>-</td><td>0.005</td></tr><tr><td>Learning Starts</td><td>10<sup>4</sup></td><td>-</td><td>-</td><td>10<sup>4</sup></td></tr><tr><td>Policy Frequency</td><td>32</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Exploration Noise</td><td>0.1</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Noise Clip</td><td>0.5</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Max KL</td><td>-</td><td>10<sup>-2</sup></td><td>-</td><td>-</td></tr><tr><td>Line Search Steps</td><td>-</td><td>10</td><td>-</td><td>-</td></tr><tr><td>CG Steps</td><td>-</td><td>100</td><td>-</td><td>-</td></tr><tr><td>CG Damping</td><td>-</td><td>10<sup>-2</sup></td><td>-</td><td>-</td></tr><tr><td>CG Tolerance</td><td>-</td><td>10<sup>-10</sup></td><td>-</td><td>-</td></tr><tr><td>LR Schedule</td><td>-</td><td>-</td><td>Linear to 0</td><td>-</td></tr><tr><td>Clip ε</td><td>-</td><td>-</td><td>0.2</td><td>-</td></tr><tr><td>PPO Epochs</td><td>-</td><td>-</td><td>10</td><td>-</td></tr><tr><td>Value Coef.</td><td>-</td><td>-</td><td>0.5</td><td>-</td></tr><tr><td>Train Freq.</td><td>-</td><td>-</td><td>-</td><td>1 step</td></tr><tr><td>Gradient Steps</td><td>-</td><td>-</td><td>-</td><td>1</td></tr></tbody></table>
## H.2 MuJoCo Experiments

<table><caption>Table 4: Hyperparameters used for the MuJoCo experiments.</caption><thead><tr><th></th><th>DDPG</th><th>TRPO</th><th>PPO</th><th>SAC</th></tr></thead><tbody><tr><td>γ</td><td>0.99</td><td>0.99</td><td>0.99</td><td>0.99</td></tr><tr><td>Learning Rate</td><td>1 × 10<sup>-3</sup></td><td>1 × 10<sup>-3</sup></td><td>3 × 10<sup>-4</sup></td><td>3 × 10<sup>-4</sup></td></tr><tr><td>Batch Size</td><td>128</td><td>64</td><td>64</td><td>256</td></tr><tr><td>Buffer Size</td><td>10<sup>6</sup></td><td>1024</td><td>2048</td><td>10<sup>6</sup></td></tr><tr><td>Value Loss</td><td>MSE</td><td>MSE</td><td>AVEC (Flet-Berliac et al., 2021)</td><td>MSE</td></tr><tr><td>Use gSDE</td><td>No</td><td>No</td><td>No</td><td>Yes</td></tr><tr><td>Entropy Coef.</td><td>-</td><td>0</td><td>0</td><td>auto</td></tr><tr><td>GAE λ</td><td>-</td><td>0.95</td><td>0.95</td><td>-</td></tr><tr><td>Advantage Norm.</td><td>-</td><td>Yes</td><td>Yes</td><td>-</td></tr><tr><td>Target Smoothing</td><td>0.005</td><td>-</td><td>-</td><td>0.005</td></tr><tr><td>Learning Starts</td><td>10<sup>4</sup></td><td>-</td><td>-</td><td>10<sup>4</sup></td></tr><tr><td>Policy Frequency</td><td>32</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Exploration Noise</td><td>0.1</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Noise Clip</td><td>0.5</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Max KL</td><td>-</td><td>10<sup>-2</sup></td><td>-</td><td>-</td></tr><tr><td>Line Search Steps</td><td>-</td><td>10</td><td>-</td><td>-</td></tr><tr><td>CG Steps</td><td>-</td><td>100</td><td>-</td><td>-</td></tr><tr><td>CG Damping</td><td>-</td><td>10<sup>-2</sup></td><td>-</td><td>-</td></tr><tr><td>CG Tolerance</td><td>-</td><td>10<sup>-10</sup></td><td>-</td><td>-</td></tr><tr><td>LR Schedule</td><td>-</td><td>-</td><td>Linear to 0</td><td>-</td></tr><tr><td>Clip ε</td><td>-</td><td>-</td><td>0.2</td><td>-</td></tr><tr><td>PPO Epochs</td><td>-</td><td>-</td><td>10</td><td>-</td></tr><tr><td>Value Coef.</td><td>-</td><td>-</td><td>0.5</td><td>-</td></tr><tr><td>Train Freq.</td><td>-</td><td>-</td><td>-</td><td>1 step</td></tr><tr><td>Gradient Steps</td><td>-</td><td>-</td><td>-</td><td>1</td></tr></tbody></table>

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 on the MuJoCo benchmark. Each agent is trained during $10^6$ interactions with its environment in the cases of HalfCheetah-v3, Hopper-v3, and Walker2d-v3. It is trained during $2 \times 10^6$ interactions in the cases of Ant-v3 and Humanoid-v3. In all cases, a training episode is made of no more than $10^3$ interactions.

**Scores.** According to algorithm 3, after each agent is trained, the resulting policy performs 50 evaluations episodes. The score of the agent is the mean performance on these 50 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 a 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 in the main text (in Fig. 5) by also plotting the score distributions of each agent using boxplots.
<figure><img src="image_11.png" /><figcaption>Figure 7: Case 3. AdaStop decision table (left) and measured empirical distributions (right).</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 8: Evaluations distributions for a SAC and a TD3 agents on HalfCheetah obtained from 192 independent seeds of 2 million steps.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>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.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>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.</figcaption></figure>

## H.3 Additional plot for Section 5.2

To illustrate Section 5.2, Figure 12 represents the kernel density estimation of the distribution of scores from (Colas et al., 2019).
<figure><img src="image_13.png" /><figcaption>Figure 9: AdaStop decision tables (top) and evaluation distributions (bottom) for each MuJoCo environment, and the budget used to make these decisions (bottom right). The medians are represented as the green triangles and the means as the horizontal orange lines.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 10: Mean of Evaluation Returns with 95% stratified bootstrap CIs. Note that curves in the same figure may use a different number of random seeds, depending on when AdaStop made the decisions.</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>Figure 12: Distributions of scores for a SAC agent and a TD3 agent on HalfCheetah obtained with 192 independent scores. Each score is obtained on an agent that has been trained during $2.10^6$ interactions.</figcaption></figure>
# Contents

<table><tr><td>1</td><td>Introduction</td><td>3</td></tr><tr><td>2</td><td>Problem setting</td><td>4</td></tr><tr><td>2.1</td><td>Goal and requirements for AdaStop</td><td>5</td></tr><tr><td>2.2</td><td>Survey of current evaluation workflows in RL</td><td>5</td></tr><tr><td>3</td><td>Background material on hypothesis testing</td><td>6</td></tr><tr><td>3.1</td><td>Group sequential testing</td><td>6</td></tr><tr><td>3.2</td><td>Permutation tests</td><td>6</td></tr><tr><td>3.3</td><td>Multiple hypothesis testing</td><td>7</td></tr><tr><td>4</td><td>Adaptive stopping for non-parametric group-sequential multiple hypothesis testing</td><td>7</td></tr><tr><td>5</td><td>Theoretical guarantees</td><td>9</td></tr><tr><td>5.1</td><td>Control on the Family-wise Error</td><td>9</td></tr><tr><td>5.2</td><td>Heuristic for early accept for even faster decisions</td><td>10</td></tr><tr><td>6</td><td>Experimental study</td><td>10</td></tr><tr><td>6.1</td><td>Toy examples</td><td>10</td></tr><tr><td>6.2</td><td>Comparison with non-adaptive approach</td><td>11</td></tr><tr><td>6.3</td><td>AdaStop for Deep Reinforcement Learning</td><td>12</td></tr><tr><td>7</td><td>Conclusion and future works</td><td>14</td></tr><tr><td>8</td><td>Ethical statement</td><td>14</td></tr><tr><td>A</td><td>Index of notations</td><td>17</td></tr><tr><td>B</td><td>Recap on hypothesis testing</td><td>17</td></tr><tr><td>B.1</td><td>Type I and type II error</td><td>18</td></tr><tr><td>B.2</td><td>Multiple tests and FWE</td><td>18</td></tr><tr><td>C</td><td>Proof of Theorem 1</td><td>19</td></tr><tr><td>C.1</td><td>Simplified proof for L = 2 agents, and K = 1</td><td>19</td></tr><tr><td>C.2</td><td>Proof of Theorem 1</td><td>20</td></tr><tr><td>D</td><td>Proof of Lemmas</td><td>21</td></tr><tr><td>D.1</td><td>Proof of Lemma 2</td><td>21</td></tr><tr><td>D.2</td><td>Proof of Lemma 3</td><td>22</td></tr><tr><td>E</td><td>Asymptotic results for two agents</td><td>23</td></tr><tr><td>E.1</td><td>Convergence of boundaries and comparing the means</td><td>23</td></tr><tr><td>E.2</td><td>Proof of Theorem 2</td><td>24</td></tr><tr><td>E.3</td><td>Proof of Lemma 4</td><td>27</td></tr></table>
<table><tr><td>F</td><td>Understanding AdaStop through simplified algorithms – 2 agents, non sequential</td><td>28</td></tr><tr><td></td><td>F.1 Comparing two agents</td><td>28</td></tr><tr><td></td><td>F.2 Step-down procedure</td><td>29</td></tr><tr><td>G</td><td>On early accept in AdaStop</td><td>30</td></tr><tr><td>H</td><td>Implementation details and additional plots</td><td>31</td></tr><tr><td></td><td>H.1 Plot of the census on the number of seeds in ICML 2022 RL articles</td><td>31</td></tr><tr><td></td><td>H.2 The distribution of evaluation performances in Deep RL problems</td><td>31</td></tr><tr><td></td><td>H.3 Complementary experiment for Section 6.1</td><td>31</td></tr><tr><td></td><td>H.4 Additional plot for Section 6.2</td><td>33</td></tr><tr><td></td><td>H.5 MuJoCo Experiments</td><td>33</td></tr></table>
Inria

RESEARCH CENTRE
LILLE - NORD EUROPE

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

Publisher
Inria
Domaine de Voluceau - Rocquencourt
BP 105 - 78153 Le Chesnay Cedex
inria.fr

ISSN 0249-6399