# On the association of secondary hairpin growth and surface pressure gradient
for oscillating foils

Suyash Verma1  Muhammad Saif Ullah Khalid1,2 and Arman Hemmati1
<EMAIL_ADDRESS>1Department of Mechanical Engineering, University of
Alberta, Edmonton, AB T6G 2R3, Canada 2Department of Mechanical and
Mechatronics Engineering, Lakehead University, Thunder Bay, ON P7B 5E1, Canada

###### Abstract

The correspondence of secondary spanwise structures and pressure gradient is
numerically evaluated for a foil, performing heaving and pitching motion, at a
range of phase offsets (90∘ $\leq\phi\leq$ 270∘) and reduced frequency (0.32
$\leq St_{c}\leq$ 0.56). The Reynolds number is $Re=$ 8000\. The wake is shown
to be dominated by secondary hairpin-like structures that are formed due to an
elliptic instability prompted by the paired primary and secondary leading edge
vortex ($LEV$). The weaker secondary $LEV$ undergoes a core deformation,
resulting in streamwise vorticity outflux across the span of the foil, and
hence, the growth of hairpin-like structures. Evaluating pressure gradients on
the surface of the foil reveals a unique fundamental measure to quantitatively
characterize the growth of these coherent structures. Their dominant presence
can be directly linked to the growth of the secondary $LEV$ formed due to the
large-scale interactions under localized adverse pressure gradients. These
promote a streamwise flow compression in neighboring regions of the primary
$LEV$. This association also presents a vivid consistency across a range of
kinematics. Therefore, this correspondence provides a novel procedure to
investigate the mechanisms involved in the formation of secondary structures
in the wake of an oscillating foil.

###### keywords:

Oscillating foil, wakes, secondary structures, instability, vortex dynamics,
surface pressure

##  1 Introduction

Formation of vortices and evolution of complex wakes behind an oscillating
foil has been the focus of many researchers in the fluid dynamics community.
Their studies have enriched our understanding of efficient propulsive
locomotion and flow control mechanisms employed by biological swimmers and
flyers (Anderson et al., 1998; Triantafyllou et al., 2005; Smits, 2019). The
influence of complex kinematics, such as coupled heaving and pitching
oscillation, on the vortex enhancement and diffusion in the wake requires more
detailed investigation (Verma & Hemmati, 2021). These foils are largely
considered as propulsors, bio-mimicking the motion of underwater swimmers and
aerial flyers (Van Buren et al., 2018). The mechanisms of $LEV$ evolution in
the wake of marine swimmers (e.g. batoid fish) and micro flyers are critical
in developing propulsive techniques that relate to the reduction of noise
propagation (Ortega et al., 2003). The associated instabilities of $LEV$s are
further exploited to promote turbulence and early diffusion of large scale
coherent structures (Leweke et al., 2016). Such mechanisms play a critical
role in the advancement of technologies that particularly reduce wake hazards
behind aircraft (Moriche et al., 2016; Leweke et al., 2016).

Recent studies have also established an association between the growth of
secondary hairpin-like vortex structures and kinematics of foils, undergoing
combined heaving and pitching motion (Verma & Hemmati, 2021, 2023b). The
transition from heave to pitch dominated kinematics coincides with changes in
the flow mechanism that contributes towards the growth of hairpin-like
secondary structures, or their absence (Verma & Hemmati, 2023b). At increased
chord- and amplitude-based Strouhal numbers ($St_{c}$ and $St_{A}$), the
stronger deformation of primary $LEVs$ were also discussed previously
(Chiereghin et al., 2020; Verma & Hemmati, 2021; Son et al., 2022), although
an association with secondary structures is not entirely clear. In this study,
we advance the fundamental knowledge about the formation of secondary hairpin-
like structures at a range of kinematic parameters by evaluating the
distribution of streamwise surface pressure gradients on an oscillating foil.

Verma & Hemmati (2021) provided a comprehensive three-dimensional wake
evolution process for an infinitely span foil oscillating with a coupled
heaving and pitching motion. The distribution of the coefficient of pressure
($C_{p}$) at low and high $St_{c}$ reveal the onset of elliptic instability
mechanism for pairs of counter-rotating vortices of unequal strength (Leweke &
Williamson, 1998; Ortega & Savas, 2001). At high $St_{c}$, dominant secondary
hairpin-like structures are observed, whose origins are considered to be
associated with core vorticity outflux (Mittal & Balachandar, 1995) of dipole
rollers shed in the wake. Recently, Verma & Hemmati (2023b) reported novel
findings related to the growth mechanisms and presence of secondary hairpin-
like vortex arrangement at a constant $St_{c}=$ 0.32. The phase offset
($\phi$) between heaving and pitching motion varied in the range of 90∘ to
270∘. The profiles of $C_{p}$ reveal the presence of a paired primary and
secondary $LEV$ roller arrangement, leading to an elliptic instability
mechanism (Leweke et al., 2016), and thereby promote an outflux of core
vorticity from the weaker secondary $LEV$ (Verma & Hemmati, 2023b). This
subsequently leads to thin streamwise vorticity filaments, which ultimately
extend to form an arrangement of hairpin-like secondary structure in the wake
(Mittal & Balachandar, 1995). Similar assessments that employed pressure
measurements on wings with finite aspect ratios (Hammer et al., 2022) are
largely focused on the dominant spanwise instability characteristics, e.g.,
wavelength of undulating $LEV$s prior to their separation from wings. The
association of pressure distribution and the growth of secondary hairpin-like
structures, however, remains unknown in the current literature.

In this study, we explain a fundamental association and quantified links
between streamwise gradients of pressure, calculated on the boundary of the
foil, and the formation of secondary hairpin-like vortical structures, which
were recently discussed by Verma & Hemmati (2023b). The findings are extended
to a range of kinematics in order to ensure a wider applicability of the
association between evolution of secondary wake structures and pressure
gradients on an oscillating foil.

###  1.1 Problem Description

The flow around an infinitely span (2D) foil with a maximum thickness ($D$) to
chord length ($c$) ratio of $D/c=0.1$ is examined numerically for a range of
chord-based ($St_{c}=fc/U_{\infty}=0.32-0.56$) and amplitude-based Strouhal
numbers (0.05 $\leq St_{A}\leq$ 0.4). Andersen et al. (2017) indicated that
significant transitions in the wake of flapping foils were observable at 0.2
$<St_{A}<$ 0.4. It also coincides with the range corresponding to the optimal
propulsive efficiency in swimming mammals (Triantafyllou et al., 2005; Smits,
2019). The cross section of the foil shown in Figure 1 resembles a teardrop
hydrofoil shape, which was used in recent experimental investigations (Floryan
et al., 2017; Van Buren et al., 2018). The Reynolds number is
$Re=U_{\infty}c/\nu=$ 8000, which is consistent with previous studies in this
area (Verma & Hemmati, 2021, 2023b), and agrees closely with the biological
characteristics of swimming fish (Anderson et al., 1998; Smits, 2019). Here,
$U_{\infty}$ and $\nu$ represent the freestream velocity and kinematic
viscosity of the fluid, respectively.

Figure 1: Schematic of the foil geometry and motion.

The kinematics of the foil is prescribed by a coupled heaving and pitching
motion, where the pitch axis is located at approximately 0.05$c$ from the
leading edge. Figure 1 marks the heave and pitch amplitudes as $h_{o}$ and
$\theta_{o}$, respectively. The resultant trailing edge amplitude is also
shown as $A_{T}$. The motion profiles of heave ($h$) and pitch ($\theta$),
where pitching has a phase advancement (or offset) of $\phi$ relative to
heaving, are represented as $h(t)=h_{o}\sin(2\pi ft)$ and
$\theta(t)=\theta_{o}\sin(2\pi ft+\phi)$, respectively.

In order to present a broader association of secondary wake structures
(hairpin-like), surface pressure gradient, and kinematics of the foil, we also
vary the phase offset ($\phi$) between heaving and pitching motion in the
range of 90∘ and 270∘. This leads to changes in $A_{T}$ relative to a fixed
$h_{o}/c$ ( = 0.25) and $\theta$ = (10∘) (Verma & Hemmati, 2022). It is
important to note that the most propulsively efficient phase offset
corresponds to $\phi=$ 270∘ in our study, following the reference coordinate
system employed by Van Buren et al. (2018).

###  1.2 Computational Method

The continuity and Navier-Stokes equations are solved directly using OpenFOAM,
which is a numerical package based on the finite-volume method. This platform
is extensively used for simulating wake dynamics behind oscillating foils and
panels (Senturk & Smits, 2019; Verma & Hemmati, 2021). Kinematics of the
oscillatory foil is modeled using Overset Grid Assembly (OGA) method, based on
a stationary background grid and a moving overset grid that are merged for the
simulation (Petra, 2019). More details of the method can be found in Verma &
Hemmati (2020, 2021, 2022).

The computational domain is also presented in Figure 1, which highlights the
C-type overset boundary containing the foil. The boundary conditions at the
inlet are prescribed a uniform fixed velocity (Dirichlet) and a zero normal
gradient (Neumann) for pressure. At the outlet, a zero-gradient outflow
boundary condition is implied (Deng & Caulfield, 2015). The top and bottom
walls are further prescribed a slip boundary condition that effectively model
open-channel or free-surface flows, and closely resemble the experimental and
computational conditions of Van Buren et al. (2018) and Hemmati et al. (2019),
respectively. At the boundary of the foil, a no-slip condition for velocity
and a zero-gradient condition for pressure is ensured. The periodic boundary
condition is further implemented on the side boundaries, coinciding with the
spanwise extent of the foil. It provides an effective way to model flows over
bodies with infinite spans without the end or tip effects.

A spatial convergence analysis is completed at $Re=$8000, $h_{o}/c=$0.25,
$\theta_{o}=$15∘, $\phi=$270∘ and $St_{c}=$0.67. This enables comparative
evaluation of the numerical results with respect to experiments of Van Buren
et al. (2018). Table 1 summarizes the grid convergence results involving three
grids, Grid1, Grid2 and Grid3. The ratio ($\delta^{*}$) of minimum grid size
element ($\Delta x$) to Kolmogorov scale ($\eta$) is kept approximately below
10 within the critical region near the foil ($x<$ 2.5$c$), specifically for
Grid2 and Grid3 (see Table 1). This region corresponds to the origin of
spanwise instability and secondary structures that emerge and grow with the
wake evolution (Verma & Hemmati, 2021, 2023b). The relative error in
prediction of $\overline{C_{T}}$
($\epsilon_{T}=|\overline{C_{T}}_{,exp}-\overline{C_{T}}|/\overline{C_{T}}_{,exp}$),
calculated with respect to the experimental results of Van Buren et al.
(2018), is below 5$\%$ for Grid2. Similarly,
$\epsilon_{L}^{rms}(=|C_{L,Grid3}^{rms}-C_{L}^{rms}|/C_{L,Grid3}^{rms})$,
calculated with respect to the finest grid (Grid3), is below 0.1$\%$. The
corresponding experimental results for $C_{L}$ are not yet available. This
agreement in results provide sufficient confidence in Grid2 for our analysis.
For more details on grid convergence, readers are referred to Verma & Hemmati
(2023b). Details for verification and validation of the numerical solver, with
respect to the domain size, spatial and temporal grid, OGA solver, and
boundary conditions, can be found in Hemmati et al. (2019), Verma & Hemmati
(2020), Verma & Hemmati (2021) and Verma & Hemmati (2023b).

Table 1: Grid refinement details for the current study. $N_{total}$ represents the sum of hexahedral elements in background grid and overset grid. Study | $N_{total}$ | $\overline{C_{T}}$ | $C_{L}^{rms}$ | $\epsilon_{T}$ | $\epsilon_{L}^{rms}$ | $x=$ | $1c$ | $2.5c$ | $5c$
---|---|---|---|---|---|---|---|---|---
Grid1 | $8.4\times 10^{6}$ | 0.64 | 2.86 | 0.084 | 0.010 | $\delta^{*}=$ | 7.3 | 16.9 | 55.2
Grid2 | $1.7\times 10^{7}$ | 0.60 | 2.84 | 0.017 | 0.003 | $\delta^{*}=$ | 3.7 | 8.5 | 15.8
Grid3 | $3.1\times 10^{7}$ | 0.59 | 2.83 | 0.001 | - | $\delta^{*}=$ | 1.8 | 4.2 | 7.9
Exp. | - | 0.59 | - | - | - | $\delta^{*}=$ | - | - | -

The simulations are completed using Cedar and Narval high performance
clusters, operated by Digital Research Alliance of Canada. The parallel
decomposition and assignment of computational domain utilizes 96 CPUs with a
total of 190 GB memory and 1440 simulation hours per case.

##  2 Results $\&$ Discussion

We begin with a brief discussion of the growth of secondary hairpin-like
structures over the span of the foil for a range of kinematic conditions of
the oscillating foil. It is followed by a detailed discussion of streamwise
pressure gradients on the boundary of the foil and its association with the
primary and secondary $LEV$ structures. The implications of varying $St_{c}$
and $\phi$ on this novel finding is further highlighted, which provides
sufficient confidence in employing streamwise pressure gradient as a unique
quantitative measure to explain the evolution of secondary hairpin-like
formations in the wake of an oscillating foil.

###  2.1 Formation of secondary hairpin-like structures

Verma & Hemmati (2023b) recently discussed the mechanisms that contribute to
the growth of secondary hairpin-like structures. Here, we provide only a brief
description of the wake dynamics explored by Verma & Hemmati (2023b) to set
the stage for our main analysis. At a range of increasing $\phi$
(90∘$\leq\phi\leq$ 270∘), a paired primary and secondary $LEV$ with unequal
strengths are formed at $St_{c}=$ 0.32, which lead to an elliptic instability
of vortex cores (Leweke & Williamson, 1998; Leweke et al., 2016). This
subsequently promote the outflux of vorticity from the weaker secondary $LEV$.
The shear straining on account of the primary $LEV$ further leads to the
streamwise extension of thin hairpin-like filaments that subsequently form the
dominant hairpin-like arrangement in the wake. As $\phi$ increases to 180∘,
however, the dominant hairpin-like arrangement fails to originate from an
instability of the pair of primary and secondary $LEV$. Rather, the primary
$LEV$ paired with the $TEV$ promotes the elliptic instability of the vortex
cores. Hairpin-like structures are subsequently formed through a deformed
$TEV$ core, in contrast to the observations noted at $\phi=$ 90∘. The wake at
$\phi=$ 225∘ and 270∘ lacks any secondary structure formation, which is
associated with the decreased strength of corresponding primary $LEV$s (Verma
& Hemmati, 2023b).

We further evaluate the formation of secondary hairpin-like structures at a
similar range of $\phi$, while increasing $St_{c}$ from 0.32 to 0.56. The
results (refer to the supplementary online material) confirm that at $St_{c}>$
0.48, and the entire range of $\phi$ examined here, the wake is characterized
by the formation of secondary hairpin-like structures. These follow the
mechanism of elliptic core instability triggered by a pair of primary and
secondary $LEV$. However, for $St_{c}\leq$ 0.48 and at the onset of pitch-
dominated kinematics (i.e. $\phi=$ 180${}^{\circ}-$ 270∘), the wake either
depicts a dominant hairpin-like formation, through the deformed $TEV$ core, or
a complete absence of them.

We expand on these wake dynamics by evaluating a unique quantitative measure,
in terms of streamwise pressure gradient that enable us to understand and
relate the mechanism of secondary hairpin-like growth with transitioning
kinematics of an oscillating foil.

(a) (b)

(c)

Figure 2: Vortex formation (primary and secondary $LEV$) and secondary
hairpin-like evolution over the foil boundary at $\phi=$ 90∘ and $St_{c}=$
0.56. The time instants correspond to (a) $t^{+}=$ 0, (b) $t^{+}=$ 0.25 and
(c) $t^{+}=$ 0.5. The structures correspond to $\lambda_{2}^{+}=$ -0.32 and
are colored using spanwise vorticity ($|\omega_{z}^{+}|=$ 4).

###  2.2 Secondary structures and streamwise pressure gradients

We employ a span-averaged estimation of the coefficient of pressure
($C_{p}=p/(0.5\rho U_{\infty}^{2})$) over the boundary of the foil during a
half oscillation cycle. The selected kinematic setting corresponds to $\phi=$
90∘ and $St_{c}=$ 0.56, although the discussion and mechanisms remain
consistent for the entire parameter space presented in Section 1.1. In order
to provide a qualitative outlook on the formation of the vortices, Figure
2(a-c) provides an instantaneous snapshot of $LEV$s formed over the surface of
the foil at first three quarters of the oscillation cycle (i.e. $t^{+}=$ 0,
0.25 and 0.5). The dominant vortical structures are identified using
$\lambda_{2}$ criterion ($\lambda_{2}^{+}=-0.32$) following the study of Verma
& Hemmati (2023b). The arrangement of $LEV_{ac}$ and $LEV_{c}^{s}$ at $t^{+}=$
0 reflects a pair of unequal strength (Figure 2(a)), which subsequently
triggers an elliptic instability of the vortex core (Leweke et al., 2016). The
undulations on $LEV_{c}^{s}$ are enhanced at $t^{+}=$ 0.25 in Figure 2(b),
owing to the developed instability. At $t^{+}=$ 0.5 (Figure 2(c)), the growth
of secondary hairpin-like structures is evident as a result of core vorticity
outflux from the secondary $LEV$ (Mittal & Balachandar, 1995). The
instantaneous pressure signatures, corresponding to the $LEV$s identified in
Figure 2, are averaged across the span and subsequently employed for
calculating the streamwise pressure gradient ($dp_{w}/dx$).

(a) (b)

(c)

Figure 3: Span averaged $dp_{w}/dx$ profiles for $\phi=$ 90∘ and $St_{c}=$
0.56 ∘. The time instants correspond to (a) $t^{+}=$ 0, (b) $t^{+}=$ 0.25 and
(c) $t^{+}=$ 0.5.

In order to evaluate an association between $dp_{w}/dx$ and the evolution of
secondary hairpin-like structures through the secondary $LEV$ (Verma &
Hemmati, 2023b), we initially evaluate the observations relevant to the case
exhibited in Figure 2. Figures 3(a-c) depicts the profiles of $dp_{w}/dx$ at
first three quarter instants ($t^{+}=$ 0, 0.25 and 0.5) of the oscillation
cycle, where the paired primary and secondary $LEV$s are dominant. The
pressure minima that coincide with the presence of the primary $LEV$ is
highlighted in Figure 3(a). The onset of the secondary $LEV_{c}^{s}$ is also
marked, which is characterized by a sharp change in the profile of
$dp_{w}/dx$. Obabko & Cassel (2002) provided a quantitative interpretation
with regards to the formation of the secondary re-circulation zone in the
neighborhood of a thick vortex core. Particularly, the discussion highlights
the contribution of large-scale interactions in the formation of re-
circulation zones. These are associated with the streamwise compression of the
flow due to the existence of localized adverse pressure gradients (Obabko &
Cassel, 2002).

To follow along the discussion of Obabko & Cassel (2002), it is evident that a
sudden rise from the minima of $dp_{w}/dx$ (coincident with $LEV_{ac}$) occurs
towards a positive $dp_{w}/dx$. Hence, this region featuring a localized
adverse pressure gradient is associated with the formation of $LEV_{c}^{s}$,
similar to the observations highlighted by Obabko & Cassel (2002) with regards
to the secondary re-circulation zone. The presence of $LEV_{c}^{s}$ can also
be observed at $t^{+}=$ 0.25 in Figure 3(b). Further ahead in the oscillation
cycle at $t^{+}=$ 0.5, a faded signature with regards to $LEV_{c}^{s}$ becomes
evident, which also coincides with the formation of secondary hairpin-like
structures through the outflux of core vorticity from the secondary $LEV$ (see
Figure 2(c)). This is in contrast to the observations of Obabko & Cassel
(2002), which indicates an increase in the magnitude of drop in $dp_{w}/dx$,
corresponding to the secondary re-circulation zone. Hence, based on the above
observations, it is reasonable to discuss a plausible association between the
variations of $dp_{w}/dx$ and the coincident transformation of the secondary
$LEV$ to hairpin-like vortices.

Figure 4: Span averaged $dp_{w}/dx$ profiles for $\phi=$ 90∘ and increasing
$St_{c}$. The straight $-$ and dashed $--$ lines corresponds to $t^{+}=$ 0 and
$t^{+}=$ 0.25, respectively.

To address this association for a wider kinematic setting, evaluations are now
discussed for different values of $\phi$ and $St_{c}$, within the range
specified in Section 1.1. Figure 4 exhibits the profiles of span-averaged
$dp_{w}/dx$ along the chord of the foil for $\phi=$ 90∘ and increasing
$St_{c}$ from 0.32 to 0.56. The presented time instants correspond to $t^{+}=$
0 and 0.25, respectively. The cases that feature the growth of secondary
hairpin-like structures from the secondary $LEV$ demonstrate a sharp change in
$dp_{w}/dx$, as it increases from the local minima corresponding to the
primary $LEV$. Further ahead in the cycle ($t^{+}\geq$ 0.25), the changes
diminish as secondary hairpin-like structures grow out of the secondary $LEV$.
For kinematics characterized by heave-domination at $\phi=$ 90∘, this
characteristic association between secondary hairpin-like evolution and
$dp_{w}/dx$ is consistent in the range of increasing $St_{c}$.

(a) (b)

(c)

Figure 5: Span averaged $dp_{w}/dx$ profiles for (a) $\phi=$ 180∘, (b) $\phi=$
225∘ and (c) $\phi=$ 270∘. The straight $-$ and dashed $--$ lines corresponds
to $t^{+}=$ 0 and $t^{+}=$ 0.25, respectively.

(a) (b)

(c) (d)

Figure 6: Vortex formation (primary and secondary $LEV$) and secondary
hairpin-like evolution over the foil boundary at $\phi=$ 180∘ and $St_{c}=$
0.32. The time instants correspond to (a) $t^{+}=$ 0, (b) $t^{+}=$ 0.25, (c)
$t^{+}=$ 0.5 and (d) $t^{+}=$ 0.75. The structures correspond to
$\lambda_{2}^{+}=$ -0.32 and are colored using spanwise vorticity
($|\omega_{z}^{+}|=$ 4).

Figure 5(a-c) shows the variations of span-averaged $dp_{w}/dx$ for $\phi=$
180∘, 225∘ and 270∘, respectively. The observations for $\phi>$ 90∘
demonstrates sharp changes in $dp_{w}/dx$ only at $St_{c}\geq$ 0.48. This also
coincides with the qualitative results similar to those presented in Figure 2,
which highlight the evolution of secondary hairpin-like structures from the
secondary $LEV$ at similar kinematics. For $\phi=$ 180∘ and 225∘, observations
at $St_{c}<$ 0.48 suggest that the dominant secondary hairpin-like structures
are associated with the instability triggered by the pair of $LEV-TEV$, rather
than a pair of primary and secondary $LEV$. In order to further illustrate
this mechanism, we look at the wake visualization in Figure 6(a-c). These
plots qualitatively depicts the formation of dominant secondary hairpin-like
structures through a $LEV-TEV$ pair at $\phi=$ 180∘ and $St_{c}=$ 0.32 (Verma
& Hemmati, 2023b). The secondary $LEV$ (marked as $LEV1_{c}^{s}$) at $t^{+}=$
0.25 in Figure 6(b) appears much weaker and diffused, which only results in
the growth of thin hairpin-like flow structures at $t^{+}=$ 0.5 (see Figure
6(c)). These structures soon lose their coherence due to diffusion in the near
wake (Figure 6(d)). However, the dominant secondary hairpin-like arrangement
emerged from the core vorticity outflux of $TEV$, as seen in Figure 6(d). The
dominant hairpin-like arrangement in the wake in Figure 6(a), are formed on
account of the $LEV-TEV$ instability. We observe that the trends of increasing
$dp_{w}/dx$ for such cases also appear flatter and closer to zero, which
reflects a low streamwise flow compression, and thus the absence of a strong
secondary $LEV$.

Figure 7: Variation of slope ($a_{i}/\Delta X^{+}$) with $St_{c}$ and
90∘$\leq\phi\leq$270∘.

To further understand the role of $dp_{w}/dx$ in quantitative characterization
of the evolution of secondary hairpin-like structures, we calculate the slope
of $dp_{w}/dx$ with respect to the streamwise distance along the foil. These
estimates are further focused on a localized region that features the rise
from a pressure minima (marked by blue dotted square in Figures 4 and 5),
coinciding with the primary $LEV$ structures. It provides an indicative
measure for the increasing streamwise flow compression as $St_{c}$ increases,
and hence expands on the association of $dp_{w}/dx$ and the growth of
secondary hairpin-like structures. Figure 7 demonstrates the variation in the
slope of $dp_{w}/dx$ for every kinematic setting considered in this study.
Here, the slope is computed as the ratio of $a_{i}$ and $\Delta X^{+}$, where
$a_{i}$ represents the magnitude of increasing $dp_{w}/dx$ (marked in Figure
4), and $\Delta X^{+}$ denotes the relative streamwise distance between the
minima and local maxima following the rise of $dp_{w}/dx$. With increasing
$St_{c}$, the slope of $dp_{w}/dx$ increases in Figure 7. It suggests an
environment of larger adverse pressure gradient and a stronger streamwise flow
compression, which further coincides with a consistent secondary hairpin-like
evolution from the secondary $LEV$, as $St_{c}$ becomes greater than 0.48.

The novel association described above presents a very useful quantitative tool
in characterization of the changes in mechanisms that govern the growth of
secondary spanwise structures. These particularly coincide with changes in
kinematics of an oscillating foil from heave- to onset of pitch-domination.
For example, (Verma & Hemmati, 2023a) recently investigated and discussed such
transitions, namely, Series $A$ and Series $B$. The trends for $dp_{w}/dx$
explained in this study accurately quantifies the identification of these
transitions. Particularly, the increasing slope of $dp_{w}/dx$ with increasing
$St_{c}$ coincides with the growth of secondary hairpin-like structures
through a primary and secondary $LEV$ pair (i.e. Mechanism $``1"$ in (Verma &
Hemmati, 2023a)), which also coincides with the Series $A$ transition at
different $\phi$ (Verma & Hemmati, 2023a).

##  3 Conclusion

A fundamental association between the evolution of secondary structures, in
the form of a spanwise hairpin-like arrangement, and the pressure gradient
along the streamwise flow is computationally investigated for the case of
infinitely span oscillating foils. Under large adverse gradients, a stronger
streamwise flow compression promotes the formation of a dominant secondary
$LEV$ in the neighborhood of the paired primary $LEV$. The growth of the
secondary $LEV$ leads to an elliptic instability mechanism (Leweke et al.,
2016), resulting in a core vorticity outflux from the secondary $LEV$, and a
subsequent growth of secondary hairpin-like structures. The highlighted
association is consistent across the range of increasing $St_{c}$ and $\phi$,
and thus reflects a unique quantitative measure of the growth of secondary
wake structures behind oscillating foils.

[Funding]This research has received support from the Canada First Research
Excellence Grant. The computational analysis was completed using Compute
Canada clusters.

[Declaration of Interests] The authors report no conflict of interest.

## References

  * Andersen et al. (2017) Andersen, A., Bohr, T., Schnipper, T. & Walther, J. H. 2017 Wake structure and thrust generation of a flapping foil in two-dimensional flow. Journal of Fluid Mechanics 812, R4.
  * Anderson et al. (1998) Anderson, J. M., Streitlien, K., Barrett, D. S. & Triantafyllou, M. S. 1998 Oscillating foils of high propulsive efficiency. Journal of Fluid Mechanics 360, 41–72.
  * Chiereghin et al. (2020) Chiereghin, N., Bull, S., Cleaver, D. J. & Gursul, I. 2020 Three-dimensionality of leading-edge vortices on high aspect ratio plunging wings. Phys. Rev. Fluids 5, 064701\.
  * Deng & Caulfield (2015) Deng, Jian & Caulfield, C. P. 2015 Three-dimensional transition after wake deflection behind a flapping foil. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics .
  * Floryan et al. (2017) Floryan, Daniel, Van Buren, Tyler, Rowley, Clarence W. & Smits, Alexander J. 2017 Scaling the propulsive performance of heaving and pitching foils. Journal of Fluid Mechanics 822, 386–397, arXiv: 1704.07478.
  * Hammer et al. (2022) Hammer, Patrick R., Garmann, Daniel J. & Visbal, Miguel R. 2022 Effect of aspect ratio on finite-wing dynamic stall. AIAA Journal 0 (0), 1–13.
  * Hemmati et al. (2019) Hemmati, Arman, Van Buren, Tyler & Smits, Alexander J. 2019 Effects of trailing edge shape on vortex formation by pitching panels of small aspect ratio. Physical Review Fluids 4, 033101.
  * Leweke et al. (2016) Leweke, Thomas, Le Dizès, Stéphane & Williamson, Charles H.K. 2016 Dynamics and Instabilities of Vortex Pairs.
  * Leweke & Williamson (1998) Leweke, T. & Williamson, C. H.K. 1998 Cooperative elliptic instability of a vortex pair. Journal of Fluid Mechanics .
  * Mittal & Balachandar (1995) Mittal, R. & Balachandar, S. 1995 Generation of streamwise vortical structures in bluff body wakes. Physical Review Letters .
  * Moriche et al. (2016) Moriche, M., Flores, O. & García-Villalba, M. 2016 Three-dimensional instabilities in the wake of a flapping wing at low Reynolds number. International Journal of Heat and Fluid Flow .
  * Obabko & Cassel (2002) Obabko, A. V. & Cassel, K. W. 2002 Navier–Stokes solutions of unsteady separation induced by a vortex. Journal of Fluid Mechanics 465, 99–130.
  * Ortega et al. (2003) Ortega, J. M., Bristol, R. L. & Savas, Ö. 2003 Experimental study of the instability of unequal-strength counter-rotating vortex pairs. Journal of Fluid Mechanics 474 (474), 35–84.
  * Ortega & Savas (2001) Ortega, Jason M. & Savas, Omer 2001 Rapidly growing instability mode in trailing multiple-vortex wakes. AIAA Journal 39 (4), 750–754, arXiv: https://doi.org/10.2514/2.1375.
  * Petra (2019) Petra, T. 2019 In Description of the overset mesh approach in ESI version of OpenFOAM. Proceedings of the CFD with OpenSource Software, Nilsson, H., Ed.; Chalmers University of Technology: Gothenburg, Sweden.
  * Senturk & Smits (2019) Senturk, Utku & Smits, Alexander J. 2019 Reynolds number scaling of the propulsive performance of a pitching airfoil. AIAA Journal 57, 2663–2669.
  * Smits (2019) Smits, Alexander J. 2019 Undulatory and oscillatory swimming. J. of Fluid Mechanics 874, P1.
  * Son et al. (2022) Son, O., Gao, A.-K., Gursul, I., Cantwell, C.D., Wang, Z. & Sherwin, S.J. 2022 Leading-edge vortex dynamics on plunging airfoils and wings. Journal of Fluid Mechanics 940, A28.
  * Triantafyllou et al. (2005) Triantafyllou, M. S., Hover, F. S., Techet, A. H. & Yue, D. K.P. 2005 Review of hydrodynamic scaling laws in aquatic locomotion and fishlike swimming. In Applied Mechanics Reviews, , vol. 58, pp. 226–237.
  * Van Buren et al. (2018) Van Buren, Tyler, Floryan, Daniel & Smits, Alexander J. 2018 Scaling and Performance of Simultaneously Heaving and Pitching Foils. https://doi.org/10.2514/1.J056635 57 (9), 3666–3677, arXiv: 1801.07625.
  * Verma & Hemmati (2023a) Verma, Suyash, M.S.U Khalid & Hemmati, Arman 2023a On the association of kinematics, spanwise instability and growth of secondary vortex structures in the wake of oscillating foils. arxiv (submitted) .
  * Verma & Hemmati (2020) Verma, Suyash & Hemmati, Arman 2020 Performance of overset mesh in modeling the wake of sharp-edge bodies. Computations 8, 66.
  * Verma & Hemmati (2021) Verma, Suyash & Hemmati, Arman 2021 Evolution of wake structures behind oscillating hydrofoils with combined heaving and pitching motion. Journal of Fluid Mechanics 927, A23.
  * Verma & Hemmati (2022) Verma, Suyash & Hemmati, Arman 2022 Characterization of bifurcated dual vortex streets in the wake of an oscillating foil. Journal of Fluid Mechanics 945, A7.
  * Verma & Hemmati (2023b) Verma, Suyash & Hemmati, Arman 2023b Influence of kinematics on the growth of secondary wake structures behind oscillating foils. International Journal of Heat and Fluid Flow 102, 109146.


$\displaystyle\quad\geq\frac{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,i}}{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,j}}\sqrt{\frac{1+(1-\varepsilon_{0})^{2}w^{\star}_{i^{\star}}/w^{\star}_{j}}{1+(1-\varepsilon_{0})^{2}\left(w^{\star}_{i}/w^{\star}_{i^{\star}}+\gamma\right)^{-1}}}\>.$

Let $\tilde{\gamma}>0$. Using Lemmas 12 and 18, we have, for all $n\geq N_{1}$
and all $k\neq i^{\star}$,

$\displaystyle\left|\frac{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,k}}{\mu_{i^{\star}}-(1-\varepsilon_{0})\mu_{k}}-1\right|$
$\displaystyle\leq\frac{W_{\mu}\left((1-\varepsilon_{0})\sqrt{\frac{\log(e+N_{n,k})}{N_{n,k}}}+\sqrt{\frac{\log(e+N_{n,i^{\star}})}{N_{n,i^{\star}}}}\right)}{\mu_{i^{\star}}-(1-\varepsilon_{0})\mu_{k}}$
$\displaystyle\leq\frac{(2-\varepsilon_{0})W_{\mu}}{\min_{k\neq
i^{\star}}(\mu_{i^{\star}}-(1-\varepsilon_{0})\mu_{k})}\sqrt{\frac{\log(e+\sqrt{n/K})}{\sqrt{n/K}}}\leq\tilde{\gamma}$

for all $n\geq N_{6}=K(X_{0}-e)^{2}+1$ which is defined as

$\displaystyle X_{0}$ $\displaystyle=\sup\left\\{x\geq
1\mid\>x<\frac{(2-\varepsilon_{0})^{2}W_{\mu}^{2}}{\tilde{\gamma}^{2}\min_{k\neq
i^{\star}}(\mu_{i^{\star}}-(1-\varepsilon_{0})\mu_{k})^{2}}\log x+e\right\\}$
$\displaystyle<h_{1}\left(\frac{(2-\varepsilon_{0})^{2}W_{\mu}^{2}}{\tilde{\gamma}^{2}\min_{k\neq
i^{\star}}(\mu_{i^{\star}}-(1-\varepsilon_{0})\mu_{k})^{2}},e\right)\>.$

where the last inequality is obtained by using Lemma 51 with $h_{1}$ defined
therein. Since $h_{1}(x,y)\sim_{x\to+\infty}x\log x$, we have
$\mathbb{E}_{\nu}[N_{6}]<+\infty$ since it polynomial in $W_{\mu}$ (by using
Lemma 12). Let $\kappa>0$. We have shown that, for all
$n\geq\max\\{N_{1},N_{4},N_{6}\\}$,

$\displaystyle\frac{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,i}}{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,j}}\sqrt{\frac{1+(1-\varepsilon_{0})^{2}N_{n,i^{\star}}/N_{n,j}}{1+(1-\varepsilon_{0})^{2}N_{n,i^{\star}}/N_{n,i}}}$
$\displaystyle\geq\frac{\mu_{i^{\star}}-(1-\varepsilon_{0})\mu_{i}}{\mu_{i^{\star}}-(1-\varepsilon_{0})\mu_{j}}\sqrt{\frac{1+(1-\varepsilon_{0})^{2}w^{\star}_{i^{\star}}/w^{\star}_{j}}{1+(1-\varepsilon_{0})^{2}\left(w^{\star}_{i}/w^{\star}_{i^{\star}}+\gamma\right)^{-1}}}\frac{1-\tilde{\gamma}}{1+\tilde{\gamma}}$
$\displaystyle=\sqrt{\frac{1+(1-\varepsilon_{0})^{2}w^{\star}_{i^{\star}}/w^{\star}_{i}}{1+(1-\varepsilon_{0})^{2}\left(w^{\star}_{i}/w^{\star}_{i^{\star}}+\gamma\right)^{-1}}}\frac{1-\tilde{\gamma}}{1+\tilde{\gamma}}\>.$

where the equality uses that the transportation costs are equal at the
equilibrium, i.e. (31). Taking $\tilde{\gamma}$ small enough, we have that
shown that, for all $n\geq\max\\{N_{1},N_{4},N_{6}\\}$,

$\frac{N_{n,i}}{N_{n,i^{\star}}}\geq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\quad\implies\quad\frac{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,i}}{\mu_{n,i^{\star}}-(1-\varepsilon_{0})\mu_{n,j}}\sqrt{\frac{1+(1-\varepsilon_{0})^{2}N_{n,i^{\star}}/N_{n,j}}{1+(1-\varepsilon_{0})^{2}N_{n,i^{\star}}/N_{n,i}}}>1\>,$

hence $C_{n}^{\text{TC}^{\text{m}}_{\varepsilon_{0}}}\neq i$. This concludes
the proof. ∎

Lemma 63 is obtained with the same proof as Lemma 23.

######  Lemma 63.

Let $\gamma>0$. There exists $N_{6}$ with $\mathbb{E}_{\nu}[N_{6}]<+\infty$
such that for all $n\geq N_{6}$ and all $i\neq i^{\star}$,

$\frac{N_{n,i}}{N_{n,i^{\star}}}\leq\frac{w^{\star}_{i}}{w^{\star}_{i^{\star}}}+\gamma\>.$

Lemma 64 is obtained with the same proof as Lemma 24.

######  Lemma 64.

Let $\varepsilon_{0}\in(0,1)$, $\gamma>0$ and $T_{\varepsilon_{0},\gamma}$
introduced before (adaptation of(10)). Under the EB-
TC${}_{\varepsilon_{0}}^{\text{m}}$ sampling rule with IDS proportions, we
have $\mathbb{E}_{\nu}[T_{\varepsilon_{0},\gamma}]<+\infty$.

Combining Lemmas 54 and 64 yields the first of Theorem 8.

####  I.3.4 Convergence towards $\beta$-optimal allocation

Combining Lemmas 58 and 27 with the proof of Lemma F.9 in [20] yields Lemma
65.

######  Lemma 65.

Let $\gamma>0$. There exists $N_{5}$ with $\mathbb{E}_{\nu}[N_{5}]<+\infty$
such that for all $n\geq N_{5}$ and all $i\neq i^{\star}$,

$\frac{N_{n,i}}{n-1}\geq w^{\star}_{\beta,i}+\gamma\quad\implies\quad
C_{n}^{\text{TC}^{\text{m}}_{\varepsilon_{0}}}\neq i\>.$

Lemma 66 is obtained with the same proof as Lemmas 29 and 30.

######  Lemma 66.

Let $\varepsilon_{0}\in(0,1)$, $\beta\in(0,1)$, $\gamma>0$ and
$T_{\varepsilon_{0},\beta,\gamma}$ introduced before (adaptation of (14)).
Under the EB-TC${}_{\varepsilon_{0}}^{\text{m}}$ sampling rule with fixed
proportions $\beta$, we have
$\mathbb{E}_{\nu}[T_{\varepsilon_{0},\beta,\gamma}]<+\infty$.

Combining Lemmas 54 and 66 yields the second part of Theorem 8.

##  Appendix J Implementation details and additional experiments

After presenting the implementations details in Appendix J.1, we display
supplementary experiments in Appendix J.2.

###  J.1 Implementation details

##### Top Two sampling rules

Given a fixed $\beta$, most Top Two algorithms use randomization to select
$I_{n}\in\\{B_{n},C_{n}\\}$, namely they sample $B_{n}$ with probability
$\beta$, otherwise sample $C_{n}$. Instead of randomization, TTUCB [20] uses
$K$ tracking procedures to select $I_{n}\in\\{B_{n},C_{n}\\}$. Namely, they
choose $I_{n}=B_{n}$ if $N^{B_{n}}_{n,B_{n}}\leq\beta\sum_{i\neq
B_{n}}T_{n+1}(B_{n},i)$, and $I_{n}=C_{n}$ otherwise. In comparison, EB-
TC${}_{\varepsilon_{0}}$ relies on $K(K-1)$ tracking procedures both for fixed
proportion $\beta$ and IDS proportions [40]. In [40], they consider IDS
proportions to define $\beta_{n}$ adaptively. For Gaussian with known
homoscedastic variance, their update mechanism is

$\beta_{n}=\frac{N_{n,B_{n}}d_{\text{KL}}(\mu_{n,B_{n}},u_{n}(B_{n},C_{n}))}{N_{n,B_{n}}d_{\text{KL}}(\mu_{n,B_{n}},u_{n}(B_{n},C_{n}))+N_{n,C_{n}}d_{\text{KL}}(\mu_{n,C_{n}},u_{n}(B_{n},C_{n}))}=\frac{N_{n,C_{n}}}{N_{n,B_{n}}+N_{n,C_{n}}}\>,$

where the second equality is obtained by direct computations which uses that

$u_{n}(i,j)=\inf_{x\in\mathbb{R}}\left[N_{n,i}d_{\text{KL}}(\mu_{n,i},x)+N_{n,j}d_{\text{KL}}(\mu_{n,j},x)\right]=\frac{N_{n,i}\mu_{n,i}+N_{n,j}\mu_{n,j}}{N_{n,i}+N_{n,j}}\>.$

[8] proposed a new methodology called Balancing Optimal Large Deviations
(BOLD) to select $I_{n}\in\\{B_{n},C_{n}\\}$ adaptively. While their approach
aims at minimizing the probability of incorrect selection (i.e. fixed-budget
setting), it is possible to adapt their idea to minimize the expected sample
complexity (i.e. fixed-confidence setting) by “swapping” the arguments of the
KL divergence. Namely, the BOLD procedure can be rewritten in our setting as
selecting $I_{n}=B_{n}$ if

$\sum_{i\neq
B_{n}}\frac{d_{\text{KL}}(\mu_{n,B_{n}},u_{n}(B_{n},i))}{d_{\text{KL}}(\mu_{n,i},u_{n}(B_{n},i))}>1\>,$

and $I_{n}=C_{n}$ otherwise. For Gaussian with known homoscedastic variance,
their approach recovers the heuristic “adaptive Welch divergence” algorithm of
proposed in [37], i.e. $I_{n}=B_{n}$ if $N_{n,B_{n}}^{2}<\sum_{i\neq
B_{n}}N_{n,i}^{2}$, and $I_{n}=C_{n}$ otherwise. The analysis of [8] is
focused on asymptotic guarantees in probability. It is an interesting
direction for future research to show that the BOLD procedure also yields
asymptotically optimal algorithms.

TTTS [34] uses a TS (Thompson Sampling) leader and a RS (Re-Sampling)
challenger based on a sampler $\Pi_{n}$. For Gaussian bandits, the sampler
$\Pi_{n}$ is the posterior distribution
$\bigtimes_{i\in[K]}\mathcal{N}(\mu_{n,i},1/N_{n,i})$ given the improper prior
$\Pi_{1}=(\mathcal{N}(0,+\infty))^{K}$. The TS leader is
$B_{n}^{\text{TS}}\in\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$ where
$\theta\sim\Pi_{n}$. The RS challenger samples vector of realizations
$\theta\in\Pi_{n}$ until
$B_{n}\notin\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$, then it is defined
as $C_{n}^{\text{RS}}\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$ for this
specific vector of realization. When the posterior $\Pi_{n}$ and the leader
$B_{n}$ have almost converged towards the Dirac distribution on $\mu$ and the
best arm $i^{\star}(\mu)$ respectively, the event
$B_{n}\notin\operatorname*{arg\,max}_{i\in[K]}\theta_{i}$ becomes very rare.
The experiments in [21] reveals that computing the RS challenger can require
more than millions of re-sampling steps. Therefore, the RS challenger can
become computationally intractable even for Gaussian distribution where
sampling from $\Pi_{n}$ can be done more efficiently.

T3C [36] combines the TS leader and the TC challenger. EB-TCI [21] combines
the EB leader with the TCI challenger defined as

$C^{\text{TCI}}_{n}=\operatorname*{arg\,min}_{i\neq
B_{n}}\mathds{1}\left(\mu_{n,B_{n}}>\mu_{n,i}\right)\frac{(\mu_{n,B_{n}}-\mu_{n,i})^{2}}{2(1/N_{n,B_{n}}+1/N_{n,i})}+\log(N_{n,i})\>.$

TTUCB [20] combined the TC challenger with a UCB leader which is defined as

$B^{\text{UCB}}_{n}=\operatorname*{arg\,max}_{i\in[K]}\\{\mu_{n,i}+\sqrt{g(n)/N_{n,i}}\\}\>,$

where $\sqrt{g(n)/N_{n,i}}$ is a bonus coping for uncertainty. TS-KKT [40]
uses the TS leader and a challenger based on transportation costs with a
different penalization than the one used in [21], namely

$C_{n})\in\operatorname*{arg\,min}_{i\neq
B_{n}}\left\\{\frac{(\mu_{n,B_{n}}-\mu_{n,i})^{2}}{2(1/N_{n,B_{n}}+1/N_{n,i})}-\frac{\rho}{n}\log\left(1/N_{n,B_{n}}+1/N_{n,i}\right)\right\\}\>,$

where $\rho$ is a parameter that needs to be selected beforehand. The authors
highlight that the choice of $\rho$ has an important impact on the empirical
performance.

While the above Top Two algorithms are BAI algorithms, we can adapt them
straightforwardly to tackle the $\varepsilon$-BAI setting by (1) using the
stopping rule as in (3) and (2) using transportation costs for
$\varepsilon$-BAI, i.e. the ones in (2). The modification (1) is inspired by
[19] and the modification (2) by [22]. As an example, the modified TCI
challenger can be written as

$C^{\text{TCI}}_{n}=\operatorname*{arg\,min}_{i\neq
B_{n}}\mathds{1}\left(\mu_{n,B_{n}}>\mu_{n,i}\right)\frac{(\mu_{n,B_{n}}-\mu_{n,i}+\varepsilon)^{2}}{2(1/N_{n,B_{n}}+1/N_{n,i})}+\log(N_{n,i})\>.$

##### Fixed-confidence BAI algorithms

At each time $n$, Track-and-Stop (TaS) [15] computes the optimal allocation
for the current empirical mean, $w_{n}=w^{\star}(\mu_{n})$. Given
$w_{n}\in\triangle_{K}$, it uses a tracking procedure to obtain an arm $I_{n}$
to sample. On top of this tracking a forced exploration is used to enforce
convergence towards the optimal allocation for the true unknown parameters.
The optimization problem defining $w^{\star}(\mu)$ can be rewritten as solving
an equation $\psi_{\mu}(r)=0$, where

$\forall r\in(1/\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2},+\infty),\>\psi_{\mu}(r)=\sum_{i\neq
i^{\star}}\frac{1}{\left(r(\mu_{i^{\star}}-\mu_{i})^{2}-1\right)^{2}}-1$

The function $\psi_{\mu}$ is decreasing, and satisfies
$\lim_{r\to+\infty}\psi_{\mu}(r)=-1$ and $\lim_{y\to 1/\min_{i\neq
i^{\star}}(\mu_{i^{\star}}-\mu_{i})^{2}}F_{\mu}(y)=+\infty$. For the practical
implementation of the optimal allocation, we use the approach of [15] and
perform binary searches to compute the unique solution of $\psi_{\mu}(r)=0$. A
faster implementation based on Newton’s iterates was proposed by [3] after
proving that $\psi_{\mu}$ is convex. While this improvement holds only for
Gaussian distributions, the binary searches can be used for more general
distributions. Similarly, one can adapt TaS to tackle $\varepsilon$-BAI as
done in [16], i.e. by tracking $w_{n}=w_{\varepsilon}(\mu_{n})$. Using Lemma
9, it is direct to see that one can use the same implementation to compute it
efficiently.

DKM [11] view $T^{\star}(\mu)^{-1}$ as a min-max game between the learner and
the nature, and design saddle-point algorithms to solve it sequentially. At
each time $n$, a learner outputs an allocation $w_{n}$, which is used by the
nature to compute the worst alternative mean parameter $\lambda_{n}$. Then,
the learner is updated based on optimistic gains based on $\lambda_{n}$.
Similarly, one can adapt DKM to tackle $\varepsilon$-BAI by using a modified
alternative mean parameter. This coincides with the L$\varepsilon$BAI
algorithm [19] when used on unstructured multi-armed bandits.

FWS [39] alternates between forced exploration and Frank-Wolfe (FW) updates.
Similarly, FWS can be adapted to tackle $\varepsilon$-BAI

LUCB [24] samples and stops based on upper/lower confidence indices for a
bonus function $g$. For Gaussian distributions, it rewrites for all $i\in[K]$
as

$\displaystyle
U_{n,i}=\mu_{n,i}+\sqrt{\frac{2c(n-1,\delta)}{N_{n,i}}}\quad\text{and}\quad
L_{n,i}=\mu_{n,i}-\sqrt{\frac{2c(n-1,\delta)}{N_{n,i}}}\>.$

At each time $n$, it samples $\hat{\imath}_{n}$ and
$\operatorname*{arg\,max}_{i\neq\hat{\imath}_{n}}U_{n,i}$. For
$\varepsilon$-BAI, LUCB stops when
$L_{n,\hat{\imath}_{n}}+\varepsilon\geq\max_{i\neq\hat{\imath}_{n}}U_{n,i}$.

##### Fixed-budget BAI algorithms

We consider Successive Reject (SR) [1] and Sequential Halving (SH) [25]. SR
eliminates one arm with the worst empirical mean at the end of each phase, and
SH eliminated half of them but drops past observations between each phase.
Within each phase, both algorithms use a round-robin uniform sampling rule on
the remaining active arms. It is possible to convert the fixed-budget SH
algorithm into an anytime algorithm by using the doubling trick. It considers
a sequences of algorithms that are run with increasing budgets $(T_{k})_{k\geq
1}$, with $T_{k+1}=2T_{k}$ and $T_{1}=2K\lceil\log_{2}K\rceil$, and recommend
the answer outputted by the last instance that has finished to run. It is well
know that the “cost” of doubling is to have a multiplicative factor $4$ in
front of the hardness constant. The first two-factor is due to the fact that
we forget half the observations. The second two-factor is due to the fact that
we use the recommendation from the last instance of SH that has finished. The
doubling version of SR and SH are named Doubling SR (DSR) and Doubling SH
(DSH).

##### Reproducibility

Our code is implemented in Julia 1.9.0, and the plots are generated with the
StatsPlots.jl package. Other dependencies are listed in the Readme.md. The
Readme.md file also provides detailed julia instructions to reproduce our
experiments, as well as a script.sh to run them all at once. The general
structure of the code (and some functions) is taken from the tidnabbil
library. This library was created by [11], see
https://bitbucket.org/wmkoolen/tidnabbil. No license were available on the
repository, but we obtained the authorization from the authors. Our
experiments are conducted on an institutional cluster with $4$ Intel Xeon Gold
5218R CPU with $20$ cores per CPU and an x86_64 architecture.

###  J.2 Supplementary experiments

For the sake of space, we only presented a small subset of our experiments in
Section 5, hence we provide additional empirical evidence below. In Appendix
J.2.1, we assess the impact of the choice of the slack $\varepsilon_{0}$ on
the empirical performance of EB-TC${}_{\varepsilon_{0}}$ with IDS or with
fixed proportion $\beta=1/2$. Appendix J.2.2 complements Section 5 by
providing more comparison between EB-TC${}_{\varepsilon_{0}}$ and existing
algorithms. In Appendix J.2.3, we study the BAI problem and show the empirical
performance of the EB-TC${}_{(\varepsilon_{n})_{n>K}}$ with fixed proportion
$\beta=1/2$ and using varying slack parameters $(\varepsilon_{n})_{n>K}$ (as
described in Sections 3 and 4). As in Section 5, we consider $\delta=0.01$ and
use the heuristic threshold $c(n,\delta)=\log((1+\log n)/\delta)$, which
yields an empirical error which is several orders of magnitude lower than
$\delta$.

####  J.2.1 Numerical simulations on EB-TC${}_{\varepsilon_{0}}$

Appendix J.2.1 is meant to be a sensitivity analysis of the EB-
TC${}_{\varepsilon_{0}}$ algorithm. It will allow us to numerically
substantiate our recommendation to the practitioner on how to set the slack
$\varepsilon_{0}$, and why using IDS yields better empirical performance. For
slacks $\varepsilon_{0}\in\\{0.15,0.1,0.05\\}$, we will consider the EB-
TC${}_{\varepsilon_{0}}$ algorithms with IDS proportions and fixed proportions
$\beta=1/2$.

Figure 4: Empirical stopping time with stopping rule (3) using
$(\varepsilon,\delta)=(0.1,0.01)$ on (a)“sparse” instances“, (b) $\alpha=0.3$”
instances and (c) “$\alpha=0.6$” instances. “c-” denotes fixed $\beta=1/2$,
without refers to IDS.

##### Large sets of arms

First, we evaluate the impact of larger number of arms (up to $K=1000$). The
“$\alpha=0.6$” scenario of [18] sets $\mu_{i}=1-((i-1)/(K-1))^{\alpha}$ for
all $i\in[K]$. The “sparse” scenario of [18] sets $\mu_{1}=1/4$ and
$\mu_{i}=0$ otherwise. We average on $100$ runs, and the standard deviations
are displayed.

In Figure 4, we see that all instances of EB-TC${}_{\varepsilon_{0}}$ with IDs
or fixed $\beta=1/2$ have the same scaling with the dimension $K$. Figure 4
also reveals that using IDS instead of fixed $\beta=1/2$ consistently yields
smaller empirical stopping time. Therefore, IDS should be preferred to
choosing fixed $\beta=1/2$. Finally, Figure 4 shows that better empirical
performance are obtained when using a slack $\varepsilon_{0}$ which matches
the error $\varepsilon$, i.e. choosing $\varepsilon_{0}=\varepsilon$ to tackle
$\varepsilon$-BAI. While choosing $\varepsilon_{0}>\varepsilon$ only slightly
damage the empirical performance, taking $\varepsilon_{0}<\varepsilon$ is
clearly detrimental to the empirical performance.

Figure 5: Empirical stopping time on random instances with stopping rule (3)
using (left) $(\varepsilon,\delta)=(0.05,0.01)$ and (right)
$(\varepsilon,\delta)=(0.1,0.01)$ with (top) $K=5$, (middle) $K=10$ and
(bottom) $K=20$. “c-” denotes fixed $\beta=1/2$, without refers to IDS.

##### Random instances

We further investigate the phenomenon described above on random instances. For
$\varepsilon\in\\{0.05,0.1\\}$, we assess the performance on $1000$ random
Gaussian instances with $K=5$ (resp. $K=10$ and $K=10$) such that $\mu_{1}=1$,
$\mu_{i}\sim\mathcal{U}([1-\varepsilon,1])$ for $i\in\\{2\\}$ (resp.
$i\in\\{2,3\\}$ and $i\in\\{2,3,4\\}$) and
$\mu_{i}\sim\mathcal{U}([0,1-\varepsilon))$ for $i\geq 3$ (resp. $i\geq 4$ and
$i\geq 6$), hence $\mathcal{I}_{\varepsilon}(\mu)=[2]$ (resp.
$\mathcal{I}_{\varepsilon}(\mu)=[3]$ and
$\mathcal{I}_{\varepsilon}(\mu)=[5]$). We display the boxplots of the
empirical stopping time on $1000$ runs.

In Figure 5, the tendencies glimpsed by inspecting Figure 4 are more apparent.
Figure 5 shows that better empirical performance are obtained when using a
slack $\varepsilon_{0}$ which matches the error $\varepsilon$, i.e. choosing
$\varepsilon_{0}=\varepsilon$ to tackle $\varepsilon$-BAI. We also see that
the empirical gain of taking $\varepsilon_{0}=\varepsilon$ is increasing with
the dimension $K$. Figure 5 shows that $\varepsilon_{0}>\varepsilon$ slightly
damage the empirical performance: the larger the missmatch
$\varepsilon_{0}-\varepsilon$ is, the worse the performances are. Moreover,
Figure 5 highlights how choosing $\varepsilon_{0}<\varepsilon$ is highly
detrimental to the empirical performance. Finally, we see that there is a mild
advantage in using IDS over fixed $\beta=1/2$. Note that the mild empirical
gain of adaptive proportions is a known phenomenon which was studied
empirically in [20], and larger gains can be observed for “two-groups”
instances. Intuitively, the characteristic times $T_{\varepsilon}(\mu)$ and
$T_{\varepsilon,1/2}(\mu)$ are very close to each other on average, and the
difference is the largest when all the sub-optimal arms have the same mean.
Therefore, on average, using IDS has mild gain compared to using fixed
$\beta=1/2$. This worst-case scenario of the “two-groups” instances is studied
in Figure 7.

Table 3: Specific instances from [16] with corresponding $\varepsilon$. $\varepsilon$ | Instance | $|\mathcal{I}_{\varepsilon}(\mu)|$ |  |  | Arms |  |  |
---|---|---|---|---|---|---|---|---
|  |  | $1$ | $2$ | $3$ | $4$ | $5$ | $6$
$0.1$ | $\mu_{1}$ | $1$ | $0.7$ | $0.55$ | $0.5$ | $0.4$ | $0.2$ | -
$0.15$ | $\mu_{2}$ | $3$ | $0.8$ | $0.75$ | $0.7$ | $0.6$ | $0.5$ | $0.4$
$0.1$ | $\mu_{3}$ | $3$ | $0.6$ | $0.6$ | $0.55$ | $0.45$ | $0.3$ | $0.2$

##### Specific instances

We continue the experimental validation of our the phenomenon described above
by considering the three specific instances from the experimental section of
[16] which are described in Table 3. Instance $\mu_{3}$ corresponds to the
specific instances studied in Section 5. It is particularly interesting since
it has two best arms, a third $\varepsilon$-good arm which is equally distant
from $\varepsilon$ than the bad arm with largest mean, and has two additional
bad arms. Instance $\mu_{2}$ has also three $\varepsilon$-good arms, which are
equally spaced, and three bad arms. Instance $\mu_{1}$ has only one
$\varepsilon$-good arm, and four bad arms. We display the boxplots of the
empirical stopping time on $1000$ runs, and the empirical simple regret on
$10000$ runs (with associated standard deviation).

Figure 6: (Left) Empirical stopping time for the stopping rule (3) using
$\delta=0.01$ and (right) empirical simple regret on instances (top) $\mu_{1}$
with $\varepsilon=0.1$, (middle) $\mu_{2}$ with $\varepsilon=0.15$ and
(bottom) $\mu_{3}$ with $\varepsilon=0.1$. “c-” denotes fixed $\beta=1/2$,
without refers to IDS.

The left column of Figure 6 confirms our previous observations: taking
$\varepsilon=\varepsilon_{0}$ yields the best performance, taking
$\varepsilon_{0}>\varepsilon$ slightly damage performance and taking
$\varepsilon_{0}<\varepsilon$ highly damage performance. Figure 6(middle left)
shows that the the larger the missmatch $\varepsilon-\varepsilon_{0}$ is, the
worse the performances are.

The right column of Figure 6 reveals that the choice of $\varepsilon_{0}$ has
few impact on the empirical simple regret, at least for reasonably chosen
$\varepsilon_{0}$. Likewise, there is few differences between IDS proportions
and fixed $\beta=1/2$. The good empirical performance of IDS proportions as
regards the simple regret hints that EB-TC${}_{\varepsilon_{0}}$ with IDS has
(most likely) similar theoretical guarantees as the ones obtained in Section 4
for EB-TC${}_{\varepsilon_{0}}$ with fixed $\beta=1/2$ (Theorem 3 and
Corollary 1). This is an interesting open problem that we leave for future
work.

##### Two-groups instances

We conclude our sensitivity analysis on EB-TC${}_{\varepsilon_{0}}$ by
considering the “two-groups” instances $\mu\in\\{0.6,0.4\\}^{10}$ for varying
number of best arms, i.e. $|i^{\star}(\mu)|\in[8]$. Our aim is to assess the
impact of having multiple best arms on the empirical stopping time. We average
on $1000$ runs, and the standard deviations are displayed.

Figure 7: Empirical stopping time with stopping rule (3) using
$(\varepsilon,\delta)=(0.1,0.01)$ on instances $\mu\in\\{0.6,0.4\\}^{10}$ for
varying $|i^{\star}(\mu)|$. “c-” denotes fixed $\beta=1/2$, without refers to
IDS.

On this specific instances where the number of arms is fixed, it would be
intuitive to think that the problem is easier when there are more best arms.
However, this is actually the opposite since there less bad arms (which were
easy to detect) and more good arms which need to be estimated well enough.
While Figure 7 shows how poor the performances are when taking
$\varepsilon_{0}<\varepsilon$, it also shows that the impact of having
multiple best arms is rather mild for slacks $\varepsilon_{0}\geq\varepsilon$.
We will see in Figure 12 that EB-TC${}_{\varepsilon_{0}}$ is the most
resilient algorithm with respect to multiple arms, meaning that its slope is
the smallest.

“Two-groups“ instances are interesting since they are the instances for which
the ratio $T_{\varepsilon,1/2}(\mu)/T_{\varepsilon}(\mu)$ is the largest.
Using Lemma 9 and the theoretical results of [20] (see their Lemma C.6), we
conjecture that $T_{\varepsilon,1/2}(\mu)\leq r_{K}T_{\varepsilon}(\mu)$ with
$r_{K}=2K/(1+\sqrt{K-1})^{2}$ and that the equality occurs for “two-groups”
instances. Since $r_{10}=5/4$, using fixed $\beta=1/2$ should be roughly
$25\%$ slower than using IDS. While Figure 7 confirms that using IDS yields
better empirical performance than using fixed $\beta=1/2$, the empirical ratio
between their performance is lower than the one suggested by the theory.

Table 4: Comparison between the original sampling rule and the modified sampling rule for BAI algorithms when combined with the GLRε stopping rule (3) using $(\varepsilon,\delta)=(0.1,0.01)$. We display the empirical stopping time (and standard deviation) on random instances with $K\in\\{5,10,20\\}$. $K$ | T3C |  $\varepsilon$-T3C | EB-TCI |  $\varepsilon$-EB-TCI
---|---|---|---|---
$5$ |  $9138$ ($\pm 7988$) |  $2259$ ($\pm 1243$) |  $22505$ ($\pm 66624$) |  $2290$ ($\pm 1202$)
$10$ |  $17418$ ($\pm 9726$) |  $3793$ ($\pm 1524$) |  $58086$ ($\pm 135655$) |  $3975$ ($\pm 1509$)
$20$ |  $30771$ ($\pm 13038$) |  $6631$ ($\pm 1992$) |  $115861$ ($\pm 195797$) |  $6905$ ($\pm 1879$)

####  J.2.2 Comparison with modified BAI algorithms

Appendix J.2.2 is meant to provide further empirical evidence that EB-
TC${}_{\varepsilon_{0}}$ outperforms its competitors on different tasks and
for different types of instances. Overall, we will use the same instances as
used in Appendix J.2.1 since they provide a wide range of interesting
problems. Throughout this section, we will be using EB-
TC${}_{\varepsilon_{0}}$ with slack $\varepsilon_{0}=0.1$. While IDS
proportions are used for the experiments on the empirical stopping time, we
use fixed $\beta=1/2$ for the empirical simple regret.

Figure 8: Empirical stopping time on (a) “$\alpha=0.6$” instances and (b)
“sparse” instances for varying $K$ and stopping rule (3) using
$(\varepsilon,\delta)=(0.1,0.01)$. The BAI algorithms T3C, EB-TCI and TTUCB
are modified to be $\varepsilon$-BAI ones.

Figure 9: Empirical stopping time on random instances with stopping rule (3)
using (left) $(\varepsilon,\delta)=(0.05,0.01)$ and (right)
$(\varepsilon,\delta)=(0.1,0.01)$ with (top) $K=5$, (middle) $K=10$ and
(bottom) $K=20$. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM are
modified for $\varepsilon$-BAI.

As benchmarks we consider modified BAI which are tailored to tackle
$\varepsilon$-BAI, and we combine them with the GLRε stopping rule. One can
still wonder whether the unmodified sampling rule would perform well for
$\varepsilon$-BAI when combined with the GLRε stopping rule. While we could
hope that modifying the stopping rule is enough, our experiments reveal that
it is not the case. If we don’t adapt the sampling rule as well, Table 4 shows
that the empirical stopping time can be more than ten times larger than their
modified version.

##### Large sets of arms

To complement Figure 2(a), we consider the “$\alpha=0.6$” instances and
“sparse” instances for varying $K$. We average on $100$ runs, and the standard
deviations are displayed.

Figure 8 confirms the observations made in Figure 2(a). We see that EB-TCε
performs on par with the $\varepsilon$-T3C, and outperforms the other
algorithms. It also highlights that the regularization ensured by the
TC$\varepsilon$ challenger is sufficient to ensure enough exploration. As a
consequence, other exploration mechanism are superfluous when using Top Two
algorithms for $\varepsilon$-BAI (e.g. using TS/UCB leader or TCI challenger).

##### Random instances

For $\varepsilon\in\\{0.05,0.1\\}$, we assess the performance on $1000$ random
Gaussian instances with $K\in\\{5,10,20\\}$ as described above. We display the
boxplots of the empirical stopping time on $1000$ runs.

Figure 9 confirms that EB-TC${}_{\varepsilon_{0}}$ performs on par with the
state-of-the-art $\varepsilon$-BAI algorithms and greatly outperform
$\varepsilon$-DKM, LUCB and uniform sampling. Interestingly, for larger sets
of arms ($K=20$), EB-TC${}_{\varepsilon_{0}}$ appears to be more robust than
its competitors, closely followed by $\varepsilon$-T3C and $\varepsilon$-EB-
TCI. The performance $\varepsilon$-TTUCB, $\varepsilon$-TaS and
$\varepsilon$-FWS is slighlty worse, while the one of $\varepsilon$-DKM is
greatly impacted. LUCB seems relatively robust to larger sets of arms, but it
is still significantly worse than EB-TC${}_{\varepsilon_{0}}$. It is even the
best when considering slack $\varepsilon_{0}=\varepsilon$ in the bottom row of
Figure 9. The slightly worse (but still competitive) empirical performance of
EB-TC${}_{\varepsilon_{0}}$ in the top row of Figure 9 is explained by the
slack $\varepsilon_{0}=0.1$ which differs from the error $\varepsilon=0.05$
considered in the GLRε stopping rule.

##### Specific instances

To complement Figure 2(b), we consider the two other instances from Table 3.
We display the boxplots of the empirical stopping time on $1000$ runs, and the
empirical simple regret on $10000$ runs (with associated standard deviation).

The left column of Figure 10 validates the previous conclusions as regards the
good empirical performance of EB-TC${}_{\varepsilon_{0}}$ compare to existing
$\varepsilon$-BAI algorithms. We also see that it seems to perform even better
when there are multiple $\varepsilon$-good arms and multiple best arms, i.e.
$|i^{\star}(\mu)|>1$. The right column of Figure 10 corroborates the
observations made in Figure 2(b): EB-TC${}_{\varepsilon_{0}}$ outperforms
uniform sampling, as well as DSR and DSH.

##### Two groups

We consider the “two-groups” instances $\mu\in\\{0.6,0.4\\}^{10}$ for varying
number of best arms, i.e. $|i^{\star}(\mu)|\in[8]$. We average on $1000$ runs,
and the standard deviations are displayed.

Figure 11 reveals that EB-TC${}_{\varepsilon_{0}}$ is the most robust to
increased number of best arms, i.e. its slope is the smallest. The good
performance of EB-TC${}_{\varepsilon_{0}}$ is closely followed by other Top
Two algorithms. This confirms that additional regularization mechanisms (e.g.
TS/UCB leader or TCI challenger) are superfluous since the TC$\varepsilon$
challenger is enough to ensure sufficient exploration. $\varepsilon$-TaS and
$\varepsilon$-FWS have slightly worse slope, and the one of $\varepsilon$-DKM
seems to become less steep after a large initial increase. The highest slope
is achieved by LUCB. Quite surprisingly, uniform sampling seems to reach a
plateau after which it is scaling better than EB-TC${}_{\varepsilon_{0}}$ (in
terms of slope), while still having worse empirical performance. It would be
interesting to quantify theoretically the good scaling of EB-
TC${}_{\varepsilon_{0}}$ with respect to increased number of best arms.

Figure 10: (Left) Empirical stopping time for the stopping rule (3) using
$\delta=0.01$ and (right) empirical simple regret on instances (top) $\mu_{1}$
with $\varepsilon=0.1$, (middle) $\mu_{2}$ with $\varepsilon=0.15$ and
(bottom) $\mu_{3}$ with $\varepsilon=0.1$. The BAI algorithms T3C, EB-TCI,
TTUCB, TaS, FWS, DKM are modified to be $\varepsilon$-BAI ones. Figure 11:
Empirical stopping time with stopping rule (3) using
$(\varepsilon,\delta)=(0.1,0.01)$ on instances $\mu\in\\{0.6,0.4\\}^{10}$ for
varying $|i^{\star}(\mu)|$. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS,
DKM are modified to be $\varepsilon$-BAI ones.

Figure 12: Empirical simple regret on instances $\mu\in\\{0.6,0.4\\}^{10}$ for
$|i^{\star}(\mu)|\in[6]$, i.e. (top left) $|i^{\star}(\mu)|=1$ and (bottom
right) $|i^{\star}(\mu)|=6$.

Figure 12 provides additional empirical validation that EB-
TC${}_{\varepsilon_{0}}$ outperforms uniform sampling as well as DSR and DSH
in terms of empirical simple regret. While the empirical stopping time
increased with the number of best arms, Figure 12 confirms the intuition that
the problem gets easier with respect to the simple regret. First, the range of
empirical simple regret becomes smaller with increased number of best arms.
This was expected as we have more chances to recommend one of the best arms at
early stage even though this recommendation is close to random. Second, we
observe a steeper decrease of the empirical simple regret with increased
number of best arms. Likewise, this is a natural phenomenon since the
collected data will reveal that there multiple good options very fast.

Quite surprisingly, EB-TC${}_{\varepsilon_{0}}$ is still better than DSH when
the number of best arms increases. To understand why it is surprising, we
recall that the exponential decrease of DSH’s probability of error is linear
with a rate proportional to a hardness constant $H_{\text{DSH}}(\mu)$. By
definition, $H_{\text{DSH}}(\mu)$ gets small when there are multiple best
arms, hence we would expect to observe lower empirical simple regret (i.e. a
“speed-up”). In contrast, our hardness constant
$H_{1}(\mu,\varepsilon_{0})=K(2\Delta_{\min}^{-1}+3\varepsilon_{0}^{-1})^{2}$
does not enjoy such property. Therefore, we would expect that DSH will
outperform EB-TC${}_{\varepsilon_{0}}$ when the number of best arms increases.
Theoretically proving that EB-TC${}_{\varepsilon_{0}}$ has a better scaling
than the one given in Theorem 3 is still an open problem. Solving it would
allow to better understand its good empirical performance on this task.

##### Fixed-budget performance

In addition, we compare the performance of EB-TC${}_{\varepsilon_{0}}$ with
$\varepsilon_{0}$ and $\beta=1/2$ to the one of SR and SH. Since SR and SH are
fixed-budget algorithms, we ran a different instance for each budget $T$.
Therefore, this comparison gives an unfair advantage to the fixed-budget
algorithms which fully leverage the knowledge of $T$ but have no theoretical
guarantees at time $n\neq T$ (even at time $T\pm 1$). As a result, the
empirical performances of SR and SH are better than the ones of DSR and DSH.
We consider the instances from Table 3, as well as “two-groups” instances.

Figure 13: (Left) Empirical simple regret and (right) empirical error on
instances (top to bottom) $\mu_{3}=(0.6,0.6,0.55,0.45,0.3,0.2)$,
$\mu_{2}=(0.8,0.75,0.7,0.6,0.5,0.4)$, $\mu_{1}=(0.7,0.55,0.5,0.4,0.2)$ and
$\mu\in\\{0.6,0.4\\}^{10}$ with $|i^{\star}(\mu)|\in\\{1,3\\}$. Average over
$200$ runs. We ran a different instance of SR and SH for each budget $T$.

Overall, according to Figure 13, EB-TC${}_{\varepsilon_{0}}$ seems to perform
on par with SR and SH in all instances considered, and to outperform SH for
some instances. In our experiments, we consider SH in which the samples are
dropped between each phase, as analyzed theoretically in [1]. This loss of
information explains why SR has better empirical performance than SH. To the
best of our knowledge, there is no theoretical analysis for the heuristic SH
where all the samples are preserved, even though it has better empirical
performance.

####  J.2.3 Varying slack parameter

In Appendix J.2.3, we study the BAI problem. Those experiments have two goals:
(1) sensitivity analysis of EB-TC${}_{(\varepsilon_{n})_{n}}$ described in
Section 3 and (2) performance assessment of EB-TC${}_{\varepsilon_{0}}$ on BAI
problems. We consider fixed proportions $\beta=1/2$, and use
$\varepsilon_{0}=0.1$ for EB-TC${}_{\varepsilon_{0}}$. For the rate of
decrease of $(\varepsilon_{n})_{n}$, we will be considering two archetypal
choices: (a) polynomial by taking $\varepsilon_{n}=n^{-\alpha/2}$ and (b)
polylogarithmic by taking $\varepsilon_{n}=\log(n)^{-\alpha/2}$. We compare
empirically those two rates of decrease for different choices of $\alpha$,
namely $\alpha\in\\{0.05,0.1,0.5\\}$. To tackle BAI, we consider the GLR0
stopping rule (3) with $(\varepsilon,\delta)=(0,0.01)$ and the heuristic
threshold $c(n,\delta)=\log((1+\log n)/\delta)$. Even though this choice is
not sufficient to prove $(0,\delta)$-PAC, it yields an empirical error which
is several orders of magnitude lower than $\delta$. As benchmark, we use the
unmodified BAI algorithms.

##### Random instances

We assess the performance on $1000$ random Gaussian instances with
$K\in\\{5,10,20\\}$ such that $\mu_{1}=1$ and
$\mu_{i}\sim\mathcal{U}([0.5,08])$ for $i\neq 1$. We display the boxplots of
the empirical stopping time on $1000$ runs.

Figure 14: Empirical stopping time for the stopping rule (3) using
$(\varepsilon,\delta)=(0,0.01)$ on random instances with (a) $K=5$, (b) $K=10$
and (c) $K=20$. “l” denotes $\varepsilon_{n}=\log(n)^{-\alpha/2}$, “p” denotes
$\varepsilon_{n}=n^{-\alpha/2}$. “a$\cdot\cdot$” refers to
$\alpha\in\\{0.5,0.1,0.05\\}$.

The most stricking feature of Figure 14 is that it reveals how poor the
performance of EB-TC${}_{(\varepsilon_{n})_{n}}$ can be for many choices of
$(\varepsilon_{n})_{n}$. For the considered $\alpha$, we observe that
polynomial decrease is always bad since it yields roughly the same empirical
performance as uniform sampling. This can be explained by the fact that this
decrease is too fast, hence EB-TC${}_{(\varepsilon_{n})_{n}}$ will ressemble
EB-TC0 which is know to have poor empirical performance [21]. For the
considered $\alpha$, we see that polylogarithmic decrease is often bad, except
for $\alpha=0.5$. In that case, it performs on par with TaS, slightly worse
than standard Top Two algorithms for BAI and better than LUCB and uniform
sampling. This can be explained by the fact that EB-
TC${}_{(\varepsilon_{n})_{n}}$ is similar to uniform sampling when the
decrease is too slow. The above sensitivity analysis truly shows how difficult
it is to choose $(\varepsilon_{n})_{n}$ beforehand. The best “trade-off”
between a slow decrease (yet not too slow) highly depends on the complexity of
the unknown instance. While EB-TC${}_{(\varepsilon_{n})_{n}}$ reaches
asymptotic optimality for BAI, we recommend the practitioner to use other Top
Two algorithms which enjoy the same theoretical guarantees and better
empirical performance. When one needs to have a deterministic algorithms, EB-
TCI seems to be the best. Without the deterministic constraint, T3C has great
performance.

In Figure 14, we also see that, when combined with the GLR0 stopping rule, EB-
TC${}_{\varepsilon_{0}}$ has good empirical performance for BAI. It
outperforms EB-TC${}_{(\varepsilon_{n})_{n}}$, performs on par with TaS and is
only slightly worse than standard Top Two algorithms for BAI. Experiments
conducted in Appendix J.2.1 already provide experimentally confirmation that
EB-TC${}_{\varepsilon_{0}}$ has still good empirical performance on
$\varepsilon$-BAI problems when $\varepsilon_{0}\geq\varepsilon$.
Theoretically, Theorem 1 provide some intuition on why this is true. It shows
that the gap between the asymptotic lower bound $T_{0}(\mu)$ and the
asymptotic upper bound of EB-TC${}_{\varepsilon_{0}}$ is bounded by

$\displaystyle\frac{T_{\varepsilon_{0},1/2}(\mu)}{T_{0}(\mu)}\left(1+\frac{\varepsilon_{0}}{\Delta_{\min}}\right)^{2}\leq
4\frac{\sum_{i\neq i^{\star}}(\Delta_{i}+\varepsilon_{0})^{-2}}{\sum_{i\neq
i^{\star}}\Delta_{i}^{-2}}\left(1+\frac{\varepsilon_{0}}{\Delta_{\min}}\right)^{2}\approx\begin{cases}4&\text{if
}\varepsilon_{0}\gg\Delta_{\min}\\\ 4&\text{if
}\varepsilon_{0}\ll\Delta_{\min}\\\ \end{cases}\>,$

where we used Lemmas 6, 9 and 7.

##### Specific instances

We consider the two instances $\mu_{1}$ and $\mu_{2}$ from Table 3 with
$\varepsilon=0$. Since most theoretical guarantees on BAI algorithms assume
that there is a unique best arm, we don’t study $\mu_{3}$. We display the
boxplots of the empirical stopping time on $1000$ runs.

Figure 15: Empirical stopping time for the stopping rule (3) using
$(\varepsilon,\delta)=(0,0.01)$ on instances (a) $\mu_{1}$ and (b) $\mu_{2}$.
“l” denotes $\varepsilon_{n}=\log(n)^{-\alpha/2}$, “p” denotes
$\varepsilon_{n}=n^{-\alpha/2}$.

Figure 15 confirms the empirical observations from Figure 14. Overall, EB-
TC${}_{(\varepsilon_{n})_{n}}$ performs poorly and EB-TC${}_{\varepsilon_{0}}$
has good empirical performance for BAI.