on par with Unif. Our empirical results suggest that APGAI enjoys better empirical performance than suggested by the theoretical guarantees summarized in Table 1.

<figure><img src="image_21.png" /><figcaption>Figure 15: Empirical error on instances (a) NoA1 and (b) NoA2. “-WR” means that each SH instance keeps all its history instead of discarding it.</figcaption></figure>

**No Good Arms** Since APGAI has arguably the best theoretical guarantees when $A_\theta(\mu) = \emptyset$, we expect it to have superior empirical performance on the instances NoA1 and NoA2. Figure 15 validates empirically that APGAI significantly outperform all the other anytime algorithms by a large margin. While Unif has the “worse” theoretical guarantees in Table 1, the empirical study shows that it outperforms both DSR-G and DSH-G-WR. This phenomenon is mainly due to the doubling trick. Converting a fixed-budget algorithm to an anytime algorithm forces the algorithm to forget past observations, hence considerably impacting the empirical performance.

<figure><img src="image_22.png" /><figcaption>Figure 16: Empirical error for varying number of good arms $|A_\theta(\mu)| \in \{5, 15, 30\}$ (left to right) among $K = 100$ arms on instances (top) TwoG and (bottom) LING. “-WR” means that each SH instance keeps all its history instead of discarding it.</figcaption></figure>

**Varying Number of Good Arms** In Figure 16, we study the impact of an increased number of good arms on the empirical error. While Table 1 suggests that APGAI is not benefiting from increased $|A_\theta(\mu)|$, we see that the empirical error is decreasing significantly as $|A_\theta(\mu)|$ increases. This suggests that better theoretical guarantees could be obtained when $A_\theta(\mu) \neq \emptyset$. It is an interesting direction for future research to show an asymptotic rate
featuring a complexity inversely proportional to $|\mathcal{A}_\theta(\mu)|$. In addition, we observe that APGAI outperforms all the other anytime algorithms by a large margin. Intuitively, APGAI is greedy enough when $\mathcal{A}_\theta(\mu) \neq \emptyset$ to avoid sampling the arms which are not good.

<figure><img src="image_23.png" /><figcaption>Figure 17: Empirical error on instances (a) THR3 and (b) MED1. “-WR” means that each SH instance keeps all its history instead of discarding it.</figcaption></figure>

**Good Arms With Similar Gaps** In light of Table 1, one might expect that APGAI has worse empirical performance when $\mathcal{A}_\theta(\mu) \neq \emptyset$ compared to other anytime algorithms. To assess this fact empirically, we first consider instances where the good arms have similar gaps, e.g. THR3 and MED1. In Figure 17, we see that APGAI is better than Unif on THR3, but worse on MED1. In both cases, APGAI outperforms both DSR-G and DSH-G-WR. Therefore, we see that APGAI has better empirical performance compared to the ones suggested by the theoretical guarantees summarized in Table 1.

<figure><img src="image_24.png" /><figcaption>Figure 18: Empirical error on instances (a) ISA2, (b) MED2, (c) ISA1, (d) REALL, (e) THR1 and (f) THR2. “-WR” means that each SH instance keeps all its history instead of discarding it.</figcaption></figure>

**Good Arms With Dissimilar Gaps** In Figure 18, we consider instances where $\mathcal{A}_\theta(\mu) \neq \emptyset$ and good arms have dissimilar gaps. Overall, APGAI always performs better than DSR-G and DSH-G-WR. While Unif seems to outperform APGAI on some instances (e.g. THR2 and MED2), it has worse performance on other instances (e.g. REALL and THR1).
## 1.5 Supplementary Results on Empirical Stopping Time

While APGAI is designed to tackle anytime GAI, it also enjoys theoretical guarantees in the fixed-confidence setting when combined with the GLR stopping rule (5) with stopping threshold (6). According to Table 2, we expect that APGAI has good empirical performance when $A_θ(μ) = \emptyset$, and sub-optimal ones when $A_θ(μ) \neq \emptyset$. Since we are interested in the empirical performance for moderate regime of confidence, we take $δ = 0.01$ in the following. We repeat our experiments over 1000 runs. We either display the boxplots or the mean with standard deviation as shaded area.

In summary, our experiments show that APGAI performs on par with all the other fixed-confidence algorithms when $A_θ(μ) = \emptyset$. When $A_θ(μ) \neq \emptyset$, APGAI has good performance only when the good arms have similar gaps. Importantly, its performance does not scale linearly with $|A_θ(μ)|$ as suggested by Table 2. When good arms have dissimilar gaps, APGAI can suffer from large outliers due to the greedyness of its sampling rule. Finally, we show a simple way to circumvent this limitation by adding forced exploration on top of APGAI.

<figure><img src="image_25.png" /><figcaption>Figure 19: Empirical stopping time ($δ = 0.01$) on instances (a) NoA1 and (b) NoA2. “MS” is Murphy Sampling, “TaS” is Track-and-Stop and “Unif” is round-robin uniform sampling.</figcaption></figure>

### No Good Arms
Since APGAI is asymptotically optimal when $A_θ(μ) = \emptyset$, we expect it to perform well on the instances NoA1 and NoA2. Figure 19 shows that APGAI has comparable performance with existing fixed-confidence GAI algorithms on such instances, and that uniform sampling performs poorly.

<figure><img src="image_26.png" /><figcaption>Figure 20: Empirical stopping time ($δ = 0.01$) for varying number of good arms $|A_θ(μ)| \in \{5k\}_{k \in [19]}$ among $K = 100$ arms on instances (a) TwoG and (b) LING. “MS” is Murphy Sampling, “TaS” is Track-and-Stop and “Unif” is round-robin uniform sampling.</figcaption></figure>
**Varying Number of Good Arms** In Figure 20, we study the impact of an increased number of good arms on the empirical error. While Table 2 suggests that APGAI is suffering from increased $|A_\theta(\mu)|$ due to the dependency in $H_\theta(\mu)$, we see that the empirical stopping time remains the same when $|A_\theta(\mu)| \in \{5k\}_{k \in [19]}$. Therefore, Figure 20 empirically validate our theoretical intuition that APGAI can achieve an asymptotic upper bound of the order $2 \max_{a \in A_\theta(\mu)} \Delta_a^{-2} \log(1/\delta)$ as discussed in Appendix F.2.1. On the LING, we also observe that APGAI can have large outliers due to the good arms with small gaps (see below for more details).

<figure><img src="image_27.png" /><figcaption>Figure 21: Empirical stopping time ($\delta = 0.01$) on instances (a) THR3 and (b) MED1. “MS” is Murphy Sampling, “TaS” is Track-and-Stop and “Unif” is round-robin uniform sampling.</figcaption></figure>

**Good Arms With Similar Gaps** When $A_\theta(\mu) \neq \emptyset$ and good arms have similar means, Table 2 suggests that APGAI could be competitive with other algorithms. Figure 21 validates this observation empirically. On the THR3 instance, APGAI achieves better performance than the other fixed-confidence algorithms, except for Track-and-Stop which has similar performance.

<figure><img src="image_28.png" /><figcaption>Figure 22: Empirical stopping time ($\delta = 0.01$) on instances (a) ISA2, (b) MED2, (c) ISA1, (d) REALL, (e) THR1 and (f) THR2. “MS” is Murphy Sampling, “TaS” is Track-and-Stop and “Unif” is round-robin uniform sampling.</figcaption></figure>

**Good Arms With Dissimilar Gaps** In Figure 22, we consider instances where $A_\theta(\mu) \neq \emptyset$ and good arms have dissimilar gaps. Table 2 suggests that APGAI can have poor empirical performance on such instances. Empirically, we see that APGAI can suffer from very large outliers on such instances. Depending on the initial draws, the greedy sampling rule of APGAI can focus on a good arm with small gap $\Delta_a$ instead of verifying a good
arm with large gap $\Delta_a$. Since those arms are significantly harder to verify, APGAI will incur a large empirical stopping time in that case. This explains why the distribution of the empirical stopping time has a heavy tail with large outliers.

<figure><img src="image_29.png" /><figcaption>Figure 23: Empirical error for varying confidence level $\delta \in \{10^{-2}, 10^{-4}, 10^{-6}\}$ (left to right) on instances (top) THR2 and (bottom) ISAI.</figcaption></figure>

In Figure 23, we study the impact of a varying confidence level on instances where APGAI suffers from large outliers. For a fair comparison, we only consider fixed-confidence algorithm whose sampling rule is independent of $\delta$ (i.e. excluding LUCB-G and HDoC). As expected, the large outliers phenomenon also increases when $\delta$ decreases.

<table><caption>Table 11: Empirical stopping time ($\pm$ standard deviation) of APGAI with (“-FE”) or without forced exploration.</caption><thead><tr><th>Ordering</th><th>THR1</th><th>THR2</th><th>THR3</th><th>MED1</th><th>MED2</th><th>ISAI</th><th>ISA2</th><th>REALL</th><th>NOA1</th><th>NOA2</th></tr></thead><tbody><tr><td>APGAI</td><td>634<br>±2091</td><td>2448<br>±4269</td><td>12301<br>±4755</td><td>22588<br>±9204</td><td>184<br>±147</td><td>544<br>±1591</td><td>159<br>±557</td><td>3721<br>±12511</td><td>288<br>±56</td><td>3014<br>±1031</td></tr><tr><td>APGAI-FE</td><td>341<br>±505</td><td>1466<br>±2833</td><td>12584<br>±4818</td><td>22394<br>±8942</td><td>216<br>±106</td><td>341<br>±444</td><td>72<br>±49</td><td>921<br>±1389</td><td>287<br>±55</td><td>3022<br>±1025</td></tr></tbody></table>

**Fixing APGAI With Forced Exploration** In the fixed-confidence setting, APGAI can suffer from large outliers when good arms have dissimilar means since it can greedily focus on good arms with small gaps. To fix this limitation, we propose to add forced exploration on top of APGAI, which we refer to as APGAI-FE. Let $\mathcal{U}_t = \{a \in \mathcal{A} | N_a(t) \le \sqrt{t} - K/2\}$. When $\mathcal{U}_t \ne \emptyset$, we pull $a_{t+1} \in \arg\min_{a \in \mathcal{U}_t} N_a(t)$. When $\mathcal{U}_t \ne \emptyset$, we pull according to APGAI sampling rule.

Table 11 shows that adding forced exploration significantly reduce the mean and the variance of the stopping time on instances where APGAI was prone to large outliers. For instances where APGAI had no large outliers, APGAI-FE has the same empirical performance. Therefore, adding forced exploration allows to circumvent the empirical shortcomings of APGAI in the fixed-confidence setting.