Aymen Al Marjani
email: aymen.al_marjani@ens-lyon.fr

Tomas Kocak
email: tomas.kocak@gmail.com

Aurélien Garivier
email: aurelien.garivier@ens-lyon.fr

On the complexity of All ε-Best Arms Identification

We consider the question introduced by [MJTN20] of identifying all the ε-optimal arms in a finite stochastic multi-armed bandit with Gaussian rewards. We give two lower bounds on the sample complexity of any algorithm solving the problem with a confidence at least 1 -δ. The first, unimprovable in the asymptotic regime, motivates the design of a Track-and-Stop strategy whose average sample complexity is asymptotically optimal when the risk δ goes to zero. Notably, we provide an efficient numerical method to solve the convex max-min program that appears in the lower bound. Our method is based on a complete characterization of the alternative bandit instances that the optimal sampling strategy needs to rule out, thus making our bound tighter than the one provided by [MJTN20]. The second lower bound deals with the regime of high and moderate values of the risk δ, and characterizes the behavior of any algorithm in the initial phase. It emphasizes the linear dependency of the sample complexity in the number of arms. Finally, we report on numerical simulations demonstrating our algorithm's advantage over state-of-the-art methods, even for moderate risks.

Introduction

The problem of finding all the ε-good arms was recently introduced by [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF]. For a finite family of distributions (ν a ) a∈[K] with vector of mean rewards µ = (µ a ) a∈[K] , the goal is to return G ε (µ) {a ∈ [K] : µ a ≥ max i µ i -ε} in the additive case and G ε (µ) {a ∈ [K] : µ a ≥ (1 -ε) max i µ i } in the multiplicative case. This problem is closely related to two other pure-exploration problems in the multi-armed bandit literature, namely the TOP-k arms selection and the THRESHOLD bandits. The former aims to find the k arms with the highest means, while the latter seeks to identify all arms with means larger than a given threshold s. As argued by [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF], finding all the ε-good arms is a more robust objective than the TOP-K and THRESHOLD problems, which require some prior knowledge of the distributions in order to return a relevant set of solutions. Take for example drug discovery applications, where the goal is to perform an initial selection of potential drugs through in vitro essays before conducting more expensive clinical trials: setting the number of arms k too high or the threshold s too low may result into poorly performing solutions. Conversely, if we set k to a small number or the threshold s too high we might miss promising drugs that will prove to be more efficient under careful examination. The All-ε objective circumvents this issues by requiring to return all drugs whose efficiency lies within a certain range from the best. In this paper, we want to identify G ε (µ) in a PAC learning framework with fixed confidence: for a risk level δ, the algorithm samples arms a ∈ [K] in a sequential manner to gather information about the distribution means (µ a ) a∈ [K] and returns an estimate G ε such that P µ ( G ε = G ε (µ)) ≤ δ. Such an algorithm is called δ-PAC and its performance is measured by the expected number of samples E[τ δ ], also called the sample complexity, needed to return a good answer with high probability. [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF] provided two lower bounds on the sample complexity: fhe first bound is based on a classical change-of-measure argument and exhibits the behavior of sample complexity in the low confidence regime (δ → 0). The second bound resorts to the Simulator technique [START_REF] Simchowitz | The simulator: Understanding adaptive sampling in the moderate-confidence regime[END_REF] combined with an algorithmic reduction to Best Arm Identification and shows the dependency of the sample complexity on the number of arms K for moderate values of δ. They also proposed FAREAST, an algorithm matching the first lower bound, up to some numerical constants and log factors, in the asymptotic regime δ → 0. Our contributions can be summarized as follows:

• Usual lower bounds on the sample complexity write as f (ν) log(1/δ) + g(ν) for an instance ν. We derive a tight bound in terms of the first-order term which writes as T * ε (µ) log(1/δ), where the characteristic time T * ε (µ) is the value of a concave max-min optimization program. Our bound is tight in the sense that any lower bound of the form f (ν) log(1/δ) that holds for all δ ∈ (0, 1) is such that f (ν) ≤ T * ε (µ). To do so, we investigate all the possible alternative instances λ that one can obtain from the original problem µ by a change-of-measure, including (but not only) the ones that were considered by [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF].

• We derive a second lower bound that writes as g(ν) in Theorem 3. g(ν) shows an additional linear dependency on the number of arms which is negligible when δ → 0 but can be dominant for moderate values of the risk. This result generalizes Theorem 4.1 in [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF], since it also includes cases where there can be several arms with means close to the top arm. The proof of this result relies on a personal rewriting of the Simulator method of [START_REF] Simchowitz | The simulator: Understanding adaptive sampling in the moderate-confidence regime[END_REF] which was proposed for the Best Arm Identification and TOP-k problems. As we explain in Section 2.3, our proof can be adapted to derive lower bounds for other pure exploration problems, without resorting to algorithmic reduction of these problems to Best Arm Identification. Therefore, we believe that the proof itself constitutes a significant contribution.

• We present two efficient methods to solve the minimization sub-problem (resp. the entire max-min program) that defines the characteristic time. These methods are used respectively in the stopping and sampling rule of our Track-and-Stop algorithm, whose sample complexity matches the lower bound when δ tends to 0.

• Finally, to corroborate our asymptotic results, we conduct numerical experiments for a wide range of the confidence parameters and number of arms. Empirical evaluation shows that Track-and-Stop is optimal either for a small number of arms K or when δ goes to 0, and excellent in practice for much larger values of K and δ. We believe these are significant improvements in performance to be of interest for ML practitioners seeking solutions for this kind of problem.

Similar to previous works, we restrict our attention to bandits with rewards coming from a Gaussian distribution with variance one. Even though this assumption is not mandatory, it considerably simplifies the presentation of the results1 . Section 2 is devoted to our lower bounds on the sample complexity of identifying the set of ε-good arms and the pseudo-code of our algorithm, along with the theoretical guarantees on its sample complexity. In Sections 3 and 4, we present our method for solving the optimization program that defines the characteristic time, which is at the heart of the sampling and stopping rules of our algorithm.

Lower bounds and asymptotically matching algorithm

We start by proving a lower bound on the sample complexity of any δ-correct algorithm. This lower bound will later motivate the design of our algorithm.

First lower bound

Let ∆ K denote the K-dimensional simplex and kl(p, q) be the KL-divergence between two Bernoulli distributions with parameters p and q. Finally, define the set of alternative bandit problems

Alt(µ) = {λ ∈ R K : G ε (µ) = G ε (λ)}.
Using change-of-measure arguments introduced by [LR85] , we derive the following lower bound on the sample complexity in our special setting. Proposition 1. For any δ-correct strategy and any bandit instance µ, the expected stopping time τ δ can be lower-bounded as

E[τ δ ] ≥ T * ε (µ) log(1/2.4δ) where T * ε (µ) -1 sup ω∈∆ K T ε (µ, ω) -1 and
(1)

T ε (µ, ω) -1 inf λ∈Alt(µ) a∈[K] ω a (µ a -λ a ) 2 2 . ( 2
)
The characteristic time T * ε (µ) above is an instance-specific quantity that determines the difficulty of our problem. The optimization problem in the definition of T * ε (µ) can be seen as a two-player game between an algorithm which samples each arm a proportionally to ω a and an adversary who chooses an alternative instance λ that is difficult to distinguish from µ under the algorithm's sampling scheme. This suggests that an optimal strategy should play the optimal allocation ω * that maximizes the optimization problem (1) and, as a consequence, rules out all alternative instances as fast as possible. This motivates our algorithm, presented in Section 2.2.

Algorithm

We propose a simple Track-and-Stop strategy similar to the one proposed by [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] for the problem of Best-Arm Identification. It starts by sampling once from every arm a ∈ [K] and constructs an initial estimate µ K of the vector of mean rewards µ. After this burn-in phase, the algorithm enters a loop where at every iteration it samples according to the estimated optimal sampling rule (3) and updates its estimate µ t of the arms' expectations. Finally, the algorithm checks if the stopping rule (4) is satisfied, in which case it stops and returns the set of empirically ε-good arms.

Sampling rule: our sampling rule performs so-called C-tracking: first, we compute ω( µ t ), an allocation vector which is 1 √ t -optimal in the lower-problem (1) for the instance µ t . Then we project ω( µ t ) on the set ∆ ηt K = ∆ K ∩ [η t , 1] K . Given the projected vector ω ηt ( µ t ), the next arm to sample from is defined by:

a t+1 = arg min a N a (t) - t s=1 ω ηt a ( µ s ) (3)
where N a (t) is the number of times arm a has been pulled up to time t. In other words, we sample the arm whose number of visits is farther behind its corresponding sum of empirical optimal allocations. In the long run, as our estimate µ t tends to the true value µ, the sampling frequency N a (t)/t of every arm a will converge to the oracle optimal allocation ω * a (µ). The projection on ∆ ηt K ensures exploration at minimal rate

η t = 1 2 √ (K 2 +t)
so that no arm is left-behind because of bad initial estimates.

Stopping rule: To be sample-efficient, the algorithm should should stop as soon as the collected samples are sufficiently informative to declare that G ε ( µ t ) = G ε (µ) with probability larger than 1 -δ. For this purpose we use the Generalized Likelihood Ratio (GLR) test [START_REF] Chernoff | Sequential design of Experiments[END_REF]. We define the Z-statistic: where

Z(t) = t × T ε µ t , N (t) t
N (t) = N a (t) a∈[K] .
As shown in [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF][START_REF] Garivier | Non-Asymptotic Sequential Tests for Overlapping Hypotheses and application to near optimal arm identification in bandit models[END_REF], the Z-statistic is equal to the ratio of the likelihood of observations under the most likely model where G ε ( µ t ) is the correct answer, i.e. µ t , to the likelihood of observations under the most likely model where G ε ( µ t ) is not the set of ε-good arms. The algorithm rejects the hypothesis G ε ( µ t ) = G ε (µ) and stops as soon as this ratio of likelihoods becomes larger than a certain threshold β(δ, t), properly tuned to ensure that the algorithm is δ-PAC. The stopping rule is defined as:

τ δ = inf t ∈ N : Z(t) > β(t, δ) (4)
One can find many suitable thresholds from the bandit literature [START_REF] Garivier | Informational confidence bounds for self-normalized averages and applications[END_REF], [START_REF] Magureanu | Lipschitz bandits: Regret lower bounds and optimal algorithms[END_REF], [START_REF] Kaufmann | Mixture martingales revisited with applications to sequential tests and confidence intervals[END_REF], all of which are of the order β(δ, t) ≈ log(1/δ) + K 2 log(log(t/δ)) is enough to ensure that

P G ε ( µ τ δ ) = G ε (µ) ≤ δ, i.e. that
G ε ( µ τ δ )
Now we state our sample complexity result which we adapted from Theorem 14 in [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. Notably, while their Track-and-Stop strategy relies on tracking the exact optimal weights to prove that the expected stopping time matches the lower bound when δ tends to zero, our proof shows that it is enough to track some slightly sub-optimal weights with a decreasing gap in the order of 1 √ t to enjoy the same sample complexity guarantees. Theorem 2. For all δ ∈ (0, 1), Track-and-Stop terminates almost-surely and its stopping time τ δ satisfies:

lim sup δ→0 E[τ δ ] log(1/δ) ≤ T * ε (µ).
Remark 1. Suppose that the arms are ordered decreasingly

µ 1 ≥ µ 2 ≥ • • • ≥ µ K . [MJTN20] define the upper margin α ε = min k∈Gε(µ) µ k -(µ 1 -ε) and provide a lower bound of the form f (ν) log(1/δ)
where:

f (ν) 2 K a=1 max 1 (µ 1 -ε -µ i ) 2 , 1 (µ 1 + α ε -µ a ) 2 .
It can be seen directly (or deduced from Theorem 2) that f (ν) ≤ T * ε (µ). In a second step, they proposed FAREAST, an algorithm whose sample complexity in the asymptotic regime δ → 0 matches their bound up to some universal constant c that does not depend on the instance ν. From Proposition 1, we deduce that T * ε (µ) ≤ cf (ν), which can be seen directly from the particular changes of measure considered in that paper. The sample complexity of our algorithm improves upon previous work by multiplicative constants that can possibly be large, as illustrated in Section 5.

Lower bound for moderate confidence regime

The lower bound in Proposition 1 and the upper bound in Theorem 2 show that in the asymptotic regime δ → 0 the optimal sample complexity scales as T * ε (µ) log(1/δ). However, one may wonder whether this bound catches all important aspects of the complexity, especially for large or moderate values of the risk δ. Towards answering this question, we present the following lower bound which shows that there is an additional cost, linear in the number of arms, that any δ-PAC algorithm must pay in order to learn the set of All-ε good arms. Before stating our result, let us introduce some notation.

We denote by S K the group of permutations over [K]. For a bandit instance ν = (ν 1 , . . . , ν K ) we define the permuted instance π(ν) = (ν π(1) , . . . , ν π(K) ). S K (ν) = {π(ν), π ∈ S K } refers to the set of all permuted instances of ν. Finally, we will write π ∼ S K to indicate that a permutation is drawn uniformly at random from S K . These results are much inspired from [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF], but come with quite different proofs that we hope can be useful to the community. Theorem 3. Fix δ ≤ 1/10 and ε > 0. Consider an instance ν such that there exists at least one bad arm: G ε (µ) = [K]. Without loss of generality, suppose the arms are ordered decreasingly

µ 1 ≥ µ 2 ≥ • • • ≥ µ K and define the lower margin β ε = min k / ∈Gε(µ) µ 1 -ε -µ k .
Then any δ-PAC algorithm has an average sample complexity over all permuted instances satisfying

E π∼S K E π(ν) [τ δ ] ≥ 1 12|G βε (µ)| 3 K b=1 1 (µ 1 -µ b + β ε ) 2 ,
The proof of the lower bound can be found in Appendix C. In the special case where

|G 2βε | = 1, then |G βε | = 1 also (since {1} ⊂ G βε ⊂ G 2βε
) and we recover the bound in Theorem 4.1 of [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF]. The lower bound above informs us that we must pay a linear cost in K, even when there are several arms close to the top one, provided that their cardinal does not scale with the total number of arms, i.e.

|G βε | = O(1).
The bound of Thm 3 can be arbitrarily large compared to T * ε (µ) log(1/δ). Fix δ = 0.1 and let ε, β > 0 with β ε and consider the instance such that

µ 1 = β, µ K = -ε and µ a = -β for a ∈ [|2, K -1|]. Then we show in Appendix C that T * ε (µ) log(1/δ) = O(1/β 2 + K/ε 2 ).
In contrast the lower bound above scales as Ω(K/β2 ). Since β ε, the second bound exhibits a better scaling w.r.t the number of arms.

The intuition behind this result comes from the following observations: first, note that arms in G βε (µ) must be sampled at least Ω(1/β 2 ε ) times, because otherwise we might underestimate their means and misclassify the arms in arg min k / ∈Gε(µ) µ 1 -ε -µ k as good arms. Second, in the initial phase the algorithm does not know which arms belong to G βε (µ) and we need at least Ω(1/(µ 1 -µ b ) 2 ) samples to distinguish any arm b from arms in G βε (µ). Together, these observations tell us that we must pay a cost of Ω(min(1/β 2 ε , 1/(µ 1 -µ b ) 2 )) samples to either declare that b is not in G βε (µ) or learn its mean up to O(β ε ) precision. More generally, consider a pure exploration problem with a unique answer, where some particular arm i 2 needs to be estimated up to some precision η > 0 in order to return the correct answer. In this case, one can adapt our proof, without using any algorithmic reduction to Best Arm Identification, to show that every arm a must be played at least Ω(1/(|µ i -µ a | + η) 2 ) times. For example, consider the problem of testing whether the minimum mean of a multi-armed bandit is above or below some threshold γ. Let ν be an instance such that {a ∈ [K] : µ a < γ} = ∅. Define η = min a:µa<γ γ -µ a > 0 and let i to be the arm that achieves this minimum. Then our proof can be adapted in a straightforward fashion to prove that any δ-PAC has a sample complexity of at least Ω K a=1 1 (µa-µ i +η) 2 .3 Note that Algorithm 1 requires to solve the best response problem, i.e. the minimization problem in (2), in order to be able to compute the Z-statistic of the stopping rule, and also to solve the entire lower bound problem in (1) to compute the optimal weights for the sampling rule. The rest of the paper is dedicated to presenting the tools necessary to solve these two problems.

Solving the min problem: Best response oracle

For a given vector ω, we want to compute the best response

λ * ε,µ (ω) arg min λ∈Alt(µ) a∈[K] ω a (µ a -λ a ) 2 2 . ( 5
)
For the simplicity of the presentation, we assume that the arms are ordered decreasingly

µ 1 ≥ µ 2 ≥ • • • ≥ µ K and start by presenting the additive case (i.e. G ε (µ) {a ∈ [K] : µ a ≥ max i µ i -ε}).
The multiplicative case can be treated in the same fashion and is deferred to appendix A. Finally, we denote by B ε (µ) [K] \ G ε (µ) the set of bad arms.

Since an alternative problem λ ∈ Alt(µ) must have a different set of ε-optimal arms than the original problem µ, we can obtain it from µ by changing the expected reward of some arms. We have two options to create an alternative problem λ:

• Making one of the ε-optimal arms bad. We can achieve it by decreasing the expectation of some ε-optimal arm k while increasing the expectation of some other arm to the point where k is no more ε-optimal. This is illustrated in Figure 1. • Making one of the ε-sub-optimal arms good. We can achieve it by increasing the expectation of some sub-optimal arm k while decreasing the expectations of the arms with the largest means -as many as it takes-to the point where k becomes ε-optimal. This is illustrated in Figure 1. In the following, we solve both cases separately.

1 k K . . . . . . . . . µ 1 µ k µ µ K t t + ε Arms Expectations 1 2 + 1 k K . . . . . . . . .
Case 1: Making one of the ε-optimal arms bad. Let k ∈ G ε (µ) be one of the ε-optimal arms. In order to make arm k sub-optimal, we need to set the expectation of arm k to some value λ k = t and the maximum expectation over all arms to max a λ a = t + ε. Note that the index of the arm with maximum expectation can be chosen in G ε (µ). Indeed, if we choose some arm from B ε (µ) to become the arm with maximum expectation in λ then we would make an ε-suboptimal arm good which is covered in the other case below. The expectations of all the other arms should stay the same as in the instance µ, since changing their values would only increase the value of the objective. Now given indices k and , computing the optimal value of t is rather straightforward since the objective function simplifies to

ω k (µ k -t) 2 2 + ω (µ -t -ε) 2
2 for which the optimal value of t is:

t = µ k, ε (ω)
ω k µ k + ω (µ -ε) ω k + ω .
and the corresponding alternative bandit is:

λ k, ε (ω) (µ 1 , . . . , µ k, ε (ω) index k , . . . , µ k, ε (ω) + ε index , . . . , µ K ) T .
The last step is taking the pair of indices (k, ) ∈ G ε (µ) × (G ε (µ) \ {k}) with the minimal value in the objective (2).

Case 2: Making one of the sub-optimal arms good. Let k ∈ B ε (µ) be a sub-optimal arm, if such arm exists, and denote by t the value of its expectation in λ. In order to make this arm ε-optimal, we need to decrease the expectations of all the arms that are above the threshold t + ε. We pay a cost of 1 2 ω k (t -µ k ) 2 for moving arm k and of 1 2 ω i (t + ε -µ i ) 2 for every arm i such that µ i > t + ε. Consider the functions:

f k (t) = 1 2 ω k (t -µ k ) 2 and for i ∈ [K] \ {k} f i (t) = 1 2 ω i (t + ε -µ i ) 2 for t < µ i -ε, 0 for t ≥ µ i -ε.
Each of these functions is convex. Therefore the function

f (t) = K i=1 f i (t)
is convex and has a unique minimizer t * . One can easily check that f (µ k ) ≤ 0 and f (µ

1 -ε) ≥ 0, implying that µ k -ε < µ k ≤ t * ≤ µ 1 -ε. Therefore: = min{i ≥ 1 : t * > µ i -ε} -1 is well defined and satisfies ∈ [|1, k -1|].
Note that by definition µ +1 -ε < t * and t * ≤ µ a -ε for all a ≤ , hence:

0 = f (t * ) = ω k (t * -µ k ) + a=1 ω a (t * + ε -µ a ).
Implying that4 :

t * = µ k, ε (ω)
ω k µ k + a=1 ω a (µ a -ε)
ω k + a=1 ω a and the alternative bandit in this case writes as:

λ k, ε (ω) (µ k, ε (ω) + ε indices 1to , µ +1 , . . . , µ k, ε (ω) index k , . . . , µ K ) T .
Observe that since depends on t * , we can't directly compute t * from the expression above. Instead, we use the fact that is unique by definition. Therefore, to determine t * one can compute µ k, ε (ω) for all values of ∈ [|1, k -1|] and search for the index satisfying µ +1 -ε < µ k, ε (ω) ≤ µ -ε and with minimum value in the objective (2).

As a summary, we have reduced the minimization problem over the infinite set Alt(µ) to a combinatorial search over a finite number of alternative bandit instances whose analytical expression is given in the next definition. Definition 1. Let λ k, ε (ω) be a vector created form µ by replacing elements on positions k and (resp. 1 to ), defined as:

λ k, ε (ω) (µ 1 , . . . , µ k, ε (ω) index k , . . . , µ k, ε (ω) + ε index , . . . , µ K ) T for k ∈ G ε (µ) and λ k, ε (ω) (µ k, ε (ω) + ε indices 1to , µ +1 , . . . , µ k, ε (ω) index k , . . . , µ K ) T for k ∈ B ε (µ) where µ k, ε (
ω) is a weighted average of elements on positions k and (resp. 1 to ) defined as:

µ k, ε (ω)
ω k µ k + ω (µ -ε) ω k + ω for k ∈ G ε (µ) and µ k, ε (ω)
ω k µ k + a=1 ω a (µ a -ε) ω k + a=1 ω a for k ∈ B ε (µ).
The next lemma then states that the best response oracle belongs to the finite set of (λ k, ε (ω)) k, . Lemma 4. Using the previous definition, λ * ε,µ (ω) can be computed as

λ * ε,µ (ω) = arg min λ∈Λ G ∪Λ B a∈[K] ω a (µ a -λ a ) 2 2 where Λ G = {λ k, ε (ω) : k ∈ G ε (µ), ∈ G ε (µ)/{k}} and Λ B = {λ k, ε (ω) : k ∈ B ε (µ), ∈ [|1, k -1|] s.t. µ ≥ µ k, ε (ω) + ε > µ +1 }.
4 Solving the max-min problem: Optimal weights

First observe that we can rewrite T ε (µ, .) -1 as a minimum of linear functions:

T ε (µ, ω) -1 = inf d∈Dε, µ ω T d (6)
where

D ε, µ (λ a -µ a ) 2 2 T a∈[K] λ ∈ Alt(µ) .
Note that by using D ε, µ instead of Alt(µ), the optimization function becomes simpler for the price of more complex domain (see Figure 2 for an example). As a result, T ε (µ, .) -1 is concave and we can compute its supergradients thanks to Danskin's Theorem [START_REF] Danskin | The theory of max-min, with applications[END_REF] which we recall in the lemma below.

(λ * (ω)a-µa) 2 2 T a∈[K] . Then d * (ω) is a supergradient of T ε (µ, .) -1 at ω.
Next we prove that T ε (µ, .) -1 is Liptschiz. Lemma 6. The function ω → T ε (µ, ω) -1 is L-Lipschitz with respect to • 1 for any

L ≥ max a,b∈[K] (µ a -µ b + ε) 2 2 .
Proof. As we showed in Lemma 4, the best response λ * ε,µ (ω) to ω is created from µ by replacing some of the elements by µ k, ε (ω) or µ k, ε (ω) + ε. We also know that µ k, ε (ω) is a weighted average of an element of µ with one or more elements of µ decreased by ε. This means that:

max a∈[K] µ a ≥ µ k, ε (ω) ≥ min a∈[K]
µ a -ε and, as a consequence, we have:

|µ i -λ * ε,µ (ω) i | ≤ max a,b∈[K] (µ a -µ b + ε) for any i ∈ [K]. Let f (ω) T ε (µ, ω) -1 .
Using the last inequality and the definition of d * (ω), we can obtain:

f (ω) -f (ω ) ≤ (ω -ω ) T d * (ω ) ≤ ω -ω 1 d * (ω ) ∞ ≤ ω -ω 1 max a,b∈[K] (µ a -µ b + ε) 2 2 for any ω, ω ∈ ∆ K .
As a summary T ε (µ, .) -1 is concave, Lipschitz and we have a simple expression to compute its supergradients through the best response oracle. Therefore we have all the necessary ingredients to apply a gradient-based algorithm in order to find the optimal weights and therefore, the value of T * ε (µ). The algorithm of our choice is the mirror ascent algorithm which provides the following guarantees:

Proposition 7. [Bub15] Let ω 1 = ( 1 K , . . . , 1 K ) T and learning rate α n = 1 L 2 log K n
. Then using mirror ascent algorithm to maximize a L-Lipschitz function f , with respect to • 1 , defined on ∆ K with generalized negative entropy Φ(ω) = a∈[K] ω a log(ω a ) as the mirror map enjoys the following guarantees:

f (ω * ) -f 1 N N n=1 ω n ≤ L 2 log K N .

Computational complexity of our algorithm.

To simplify the presentation and analysis, we chose to focus on the vanilla version of Track and Stop. However, in practice this requires solving the optimization program that appears in the lower bound at every time step, which can result in large run times. Nonetheless, we note that there are many possible adaptations of Track and Stop that reduce the computational complexity, while retaining the guarantees of asymptotic optimality in terms of the sample complexity (and with a demonstrated small performance loss experimentally). A first solution is to use Franke-Wolfe style algorithms [Mén19, WTP21], which only perform a gradient step of the optimization program at every step. Another adaptation is the Lazy Track-and-Stop [START_REF] Jedra | Optimal best-arm identification in linear bandits[END_REF], which updates the weights that are tracked by the algorithms every once in a while. We chose the latter solution in our implementation, where we updated the weights every 100K steps.

Experiments

We conducted three experiments to compare Track-and-Stop with state-of-the-art algorithms, mainly (ST) 2 and FAREAST from [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF]. In the first experiment, we simulate a multi-armed bandit with Gaussian rewards of means µ = [1, 1, 1, 1, 0.05], variance one and a parameter ε = 0.9. We chose this particular instance µ because its difficulty is two-fold: First, the last arm µ 5 is very close to the threshold max a µ a -ε. Second, the argmax is realized by more than one arm, which implies that any algorithm must estimate all the means to high precision to produce a confident guess of G ε (µ). Indeed, a small underestimation error of max a µ a would mean wrongly classifying µ 5 as a good arm. We run the three algorithms for several values of δ ranging from δ = 0.1 to δ = 10 -10 , with N = 100 Monte-Carlo simulations for each risk level. Figure 3 shows the expected stopping time along with the 10% and 90% quantiles (shaded area) for each algorithm. Track-and-Stop consistently outperforms (ST) 2 and FAREAST, even for moderate values of δ. Also note that, as we pointed out in Remark 1, the sample complexity of Track-and-Stop is within some multiplicative constant of (ST) 2 .

Next, we examine the performance of the algorithms w.r.t the number of arms. For any given K, we consider a bandit problem µ similar to the previous instance: ∀a ∈ [|1, K -1|], µ a = 1 and µ K = 0.05. We fix ε = 0.9 and δ = 0.1 and run N = 30 Monte-Carlo simulations for each K.

Figure 4 shows, in log-scale, the ratio of the sample complexities of (ST) 2 and FAREAST w.r.t to the sample complexity of Track-and-Stop. We see that Track-and-Stop performs better than (ST) 2 (resp. FAREAST) for small values of K. However when the number of arms grows larger than K = 40 (resp. K = 60), (ST) 2 (resp. FAREAST) have a smaller sample complexity. Finally, we rerun the Cancer Drug Discovery experiment from [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF]. Note that this experiment is more adapted to a fixed budget setting where we fix a sampling budget and the algorithm stops once it has reached this limit, which is different from the fixed confidence setting that our algorithm was designed for. The goal is to find, among a list of 189 chemical compounds, potential inhibitors to F1-score along with the 10% and 90% quantiles (shaded area). We see that (ST) 2 and Track-and-Stop have comparable performance and that both outperform UCB's sampling scheme.

Conclusion

We shed a new light on the sample complexity of finding all the ε-good arms in a multi-armed bandit with Gaussian rewards. We derived two lower bounds, identifying the characteristic time that reflects the true hardness of the problem in the asymptotic regime. Moreover, we proved a second bound highlighting an additional cost that is linear in the number of arms and can be arbitrarily larger than the first bound for moderate values of the risk. Then, capitalizing on an algorithm solving the optimization program that defines the characteristic time, we proposed an efficient Track-and-Stop strategy whose sample complexity matches the lower bound for small values of the risk level. Finally, we showed through numerical simulations that our algorithm outperforms state-of-the-art methods for bandits with small to moderate number of arms. Several directions are worth investigating in the future. Notably, we observe that while Track-and-Stop performs better in the fixed-K-small-δ regime, the elimination based algorithms (ST) 2 and FAREAST become more efficient in the large-K-fixed-δ regime. It would be interesting to understand the underlying tradeoff between the number of arms and confidence parameter. This will help design pure exploration strategies having best of both worlds guarantees.

A Multiplicative Case

Most of the previous analysis of the additive case can be directly applied to the multiplicative case where the set of the best arms is defined as

G ε (µ) {a ∈ [K] : µ a ≥ (1 -ε) max i µ i }.
The only missing pieces are the best response oracle and an upper bound on the Lipschitz constant for a mirror ascent algorithm. Solving these two problems gives us all the necessary tools to produce the multiplicative version of the algorithm presented in 1.

A.1 Best Response Oracle -Multiplicative Case

Similarly, as in the additive case, split the reasoning into two parts: making a good arm bad or making a bad arm good. This provides the following variation of Lemma 3 Lemma 7. Define λ k, ε (ω) as in Definition 1 for

µ k, ε (ω) (1 -ε) 2 ω k µ k + (1 -ε)ω µ (1 -ε) 2 ω k + ω in the case of k ∈ G ε (µ) and µ k, ε (ω) (1 -ε) 2 ω k µ k + a=1 (1 -ε)ω a µ a (1 -ε) 2 ω k + a=1 ω a in the case of k ∈ B ε (µ).
Then the best response λ * ε,µ (ω) to a given ω is defined as:

λ * ε,µ (ω) = arg min λ∈Λ G ∪Λ B a∈[K] ω a (µ a -λ a ) 2 2 .
where

Λ G = {λ k, ε (ω) : k ∈ G ε (µ), ∈ G ε (µ)/{k}} and Λ B = {λ k, ε (ω) : k ∈ B ε (µ), ∈ [|1, k -1|] s.t. µ ≥ µ k, ε (ω)/(1 -ε) > µ +1 }.
Proof.

Case 1: Making one of the ε-optimal arms bad. Selecting a good arm k ∈ G ε (µ) and any other arm ∈ G ε (µ) we can set the expectation of arm k to t and the expectation of arm to t/(1 -ε).

Using calculus, we can find the optimal value

t = (1 -ε) 2 ω k µ k + (1 -ε)ω µ (1 -ε) 2 ω k + ω .
Case 2: Making one of the sub-optimal arms good. Selecting a bad arm k ∈ B ε (µ) and the first arms we can set the expectation of arm k to t and the expectation of the first arms to t/(1 -ε). Note that is a unique integer such that µ ≥ t/(1 -ε) > µ +1 thanks to the same argument as in the additive case. Using calculus, we can find the optimal value

t = (1 -ε) 2 ω k µ k + a=1 (1 -ε)ω a µ a (1 -ε) 2 ω k + a=1 ω a .

A.2 Upper bound on the Lipschitz constant

The final ingredient is a constant L for a mirror ascent algorithm, characterized in the following lemma.

Lemma 8. The function ω → T ε (µ, ω) -1 is L-Lipschitz with respect to • 1 for any

L ≥ max a,b∈[K] (µ a -µ b (1 -ε)) 2 2(1 -ε) 2 .
Proof. Lemma 7 shows that the expectation of the selected arm k should be in equal to

t = (1 -ε) 2 ω k µ k + (1 -ε)ω a µ a (1 -ε) 2 ω k + ω a
where the sum is taken either over a single arm or over the first arms. In both cases we can show

(1 -ε)µ min ≤ (1 -ε) 2 ω k µ k + (1 -ε)ω a µ a (1 -ε) 2 ω k + ω a using (1 -ε) < 1, µ min ≤ µ a for any a ∈ [K]
and

(1 -ε) 2 ω k µ k + (1 -ε)ω a µ a (1 -ε) 2 ω k + ω a ≤ µ max using (1-ε) < 1 and µ max ≥ µ a for any a ∈ [K].
Using this inequality we can show that (µ a -λ a ) 2 can be upper-bounded by

µ max 1 -ε -µ min 2
for any best response λ. Applying this bound to the optimization problem concludes the proof of the lemma.

B Proof of Proposition 1

Let δ ∈ (0, 1) be a confidence parameter and µ be a bandit problem. Considering a δ-PAC strategy, we can apply transportation Lemma 1 of [START_REF] Kaufmann | On the Complexity of Best Arm Identification in Multi-Armed Bandit Models[END_REF] to obtain

a∈[K] (µ a -λ a ) 2 2 E[N a ] ≥ kl(δ, 1 -δ)
for N a N a (τ δ ). This holds for any alternative problem λ ∈ Alt(µ). Therefore, we have

kl(δ, 1 -δ) ≤ inf λ∈Alt(µ) a∈[K] E[τ δ ] (µ a -λ a ) 2 2 E[N a ] E[τ δ ] ≤ E[τ δ ] sup ω∈∆ K inf λ∈Alt(µ) a∈[K] ω a (µ a -λ a ) 2 2 . Fraction E[N a ]/E[τ δ ]
represents empirical proportion of arm draws which enables us to upper-bound it by a supremum over all possible arm allocations. We conclude by noting that kl(δ, 1 -δ) ≥ log(1/2.4δ).

C Proof of Theorem 3

We restrict our attention to symmetric algorithms. An algorithm A is said to be symmetric if it satisfies for any permutation π, any integer n ≥ 1 and any sequence of actions A 1 , . . . , A n ,

P A,ν (a 1 , . . . , a n ) = (A 1 , . . . , A n ) = P A,π(ν) (a 1 , . . . , a n ) = (π(A 1 ), . . . , π(A n )) .
In words, A is symmetric if it is indifferent to the order of the arms and acts only based on the underlying distributions. [START_REF] Simchowitz | The simulator: Understanding adaptive sampling in the moderate-confidence regime[END_REF] showed that for any algorithm A, one can easily build a symmetrized version A sym such that for any bandit instance ν,

E π∼S K E A,π(ν) [τ δ ] = E Asym,ν [τ δ ]
. Therefore, we only need to prove the lower bound for symmetric algorithms. Throughout the proof it will be useful to represent bandit instances using the random table model

[LS19]: ν can be defined as a collection of random variables (X a,t ) a∈[K],t≥1 where X a,t represents the reward received when playing arm a for the n-th time. Therefore it is enough to specify the law of each X a,t to define ν.

The lemma below shows that no arm can be played much less than the arms in G βε (µ) and enables us to avoid performing algorithmic reductions of the All-ε problem to Best Arm Identification or β-isolated tests as was done in [START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF]. Lemma 9. For all arms b ∈ [K] and all integers n ≥ 1,

1 |G βε (µ)| a∈G βε (µ) P ν (N a (τ ) > n) -(µ 1 -µ b ) n/2 ≤ 3P ν (N b (τ ) > n).
Proof. Fix a ∈ G βε (µ) \ {b} and n ≥ 1. Let π be the permutation that swaps arms a and b, i.e. π(a) = b, π(b) = a and π(k) = k for k ∈ [K] \ {a, b}. We define the non-stationary bandit instances ν and π such that ν :

Arm First n rewards Next rewards a ∼ N (µ a , 1) ∼ N (µ a , 1) b ∼ N (µ b , 1) ∼ N (µ a , 1) k ∈ [K] \ {a, b} ∼ N (µ k , 1) ∼ N (µ k , 1)
and π :

Arm First n rewards Next rewards a ∼ N (µ b , 1) ∼ N (µ a , 1) b ∼ N (µ a , 1) ∼ N (µ a , 1) k ∈ [K] \ {a, b} ∼ N (µ k , 1) ∼ N (µ k , 1)
ν and π will only serve as "bridges" in our change-of-measure argument. In particular, we do not require that the algorithm returns a good answer on any of them. Let P λ denote the law of all relevant random variables (rewards, actions played, stopping times..) when running algorithm A on instance λ and define the event E = (N b (τ ) ≤ n). Observe that P ν (E ∩ .) = P ν (E ∩ .), since under E algorithm A observes the same distribution of rewards. Thus using Bayes' Theorem one can write

≤ P ν (E c ) = P ν (N b (τ ) > n) , (7)
where (a) is because P ν (E) = P ν (E) hence P ν (E c ) = P ν (E c ) also, (b) is by the joint convexity of the TV distance and (c) is because P ν (E ∩ .) = P ν (E ∩ .) implies that P ν (.|E) = P ν (.|E).

Similarly, by considering event E = (N b (τ ) > n) we have

TV(P π(ν) , P π ) ≤ P π(ν) (N a (τ ) > n) . (8)
Using the above, one can write

P ν (N a (τ ) > n) -P π(ν) (N a (τ ) > n) ≤ TV(P ν , P π(ν) )
≤ TV(P π(ν) , P π ) + TV(P π , P ν ) + TV(P ν , P ν )

(a) ≤ P π(ν) (N a (τ ) > n) + P ν (N b (τ ) > n) + KL(P π , P ν ) 2 (b) ≤ 2P ν (N b (τ ) > n) + KL(P π , P ν ) 2 ,
where (a) comes from combining (7) and (8) and using Pinsker's inequality and (b) is because the symmetry of the algorithm implies that P

π(ν) (N a (τ ) > n) = P ν (N b (τ ) > n). Now observe
Now we are ready to prove Theorem 3. By combining the results of Lemmas 9 and 10, we get for all

b ∈ [K] 1 -2δ 3|G βε (µ)| -(µ 1 -µ b + β ε ) √ n/6 ≤ P ν (N b (τ ) > n) Thus by choosing n = (1-2δ) 2 |G βε (µ)| 2 (µ1-µ b +βε) 2 we get 1 -2δ 6|G βε (µ)| ≤ P ν (N b (τ ) > n) ≤ P ν N b (τ ) ≥ (1 -2δ) 2 |G βε (µ)| 2 (µ 1 -µ b + β ε ) 2 , which implies that for all b ∈ [K], (1 -2δ) 3 6|G βε (µ)| 3 (µ 1 -µ b + β ε ) 2 ≤ E ν [N b (τ )].
The final result is obtained by summing the inequality over all arms and noting that for δ ≤ 10, (1 -2δ) 3 ≥ 1/2.

C.1 Example showing the improved scaling of Theorem 3 w.r.t the number of arms.

We recall that µ

1 = β, µ K = -ε and µ a = -β for a ∈ [|2, K -1|]. Note that in this case β ε = β. By symmetry, ω a = ω 2 for all a ∈ [|2, K -1|].
In this case, using Lemma 4 we have

T * ε (µ) -1 (a) = sup ω∈Σ K min ω 1 ω K β 2 2(ω 1 + ω K ) , ω 1 ω 2 (ε -2β) 2 2(ω 1 + ω 2 ) , ω 2 ω 3 ε 2 2(ω 2 + ω 3 ) = sup ω∈Σ K min ω 1 ω K β 2 2(ω 1 + ω K ) , ω 1 ω 2 (ε -2β) 2 2(ω 1 + ω 2 ) , ω 2 ε 2 4 ≥ sup ω∈Σ K min ω 1 ω K β 2 2(ω 1 + ω K ) , ω 1 ω 2 (ε -2β) 2 2(ω 1 + ω 2 ) , ω 2 (ε -2β) 2 4 .
The first term of the min in (a) corresponds to the cost of making arm K a good arm by simultaneously increasing its mean reward and decreasing the mean reward of the first arm, the second term to that of making arm 2 a bad arm by simultaneously decreasing its mean reward and increasing the mean reward of the first arm. The third term, corresponds to the cost of making arm 2 a bad arm by simultaneously decreasing its mean reward and increasing the mean reward of the arm 3 (which is the same cost if we replace arms 2 and 3 by any other pair of arms in [|2, K -1|]). Now we look for ω such that ω 1 = ω K > ω 2 . This means that the third term of the min in the last line is always smaller than the second term. If we note S the set of such omegas then one can write

T * ε (µ) -1 ≥ sup ω∈Σ K ∩S min ω 1 β 2 4 , ω 2 (ε -2β) 2 4 (10)
Note that the right hand side is maximized when both terms of the min are equal. Let ω be the maximizer. Then

2 ω 1 + (K -2) ω 2 = 1, and ω 1 β 2 = ω 2 (ε -2β) 2 .
Solving for ω and injecting in (10) we get

T * ε (µ) -1 ≥ (ε -2β) 2 β 2 8(ε -2β) 2 + 4(K -2)β 2 or equivalently T * ε (µ) ≤ 8 β 2 + 4(K -2) (ε -2β) 2 .
When β ε and δ is fixed, this yields T * ε (µ) log(1/δ) = O(1/β 2 + K/ε 2 ). In contrast note that for this particular instance |G β (µ)| = 1 so that the lower bound of Theorem 3 is at least of order ω(K/β 2 ).

D Proof of Theorem 2

We start with a few technical lemmas. The first two are adapted from [GK16]: Lemma 11. LEMMA 7, [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] For all t ≥ 1, the C-Tracking with weights ( ω( µ

s )) s∈N * ensures that N a (t) ≥ √ t + K 2 -2K and that max 1≤1≤K N a (t) - t s=1 ω a ( µ s ) ≤ K(1 + √ t) Lemma 12. LEMMA 19, [GK16] For ξ > 0, define I ξ [µ 1 -ξ, µ 1 + ξ] × . . . [µ K -ξ, µ K + ξ].
And for T ≥ 1, consider the event:

E T = T t= T 1/4
µ t ∈ I ξ . Then there exists two constants B, C that only depend on µ and ξ such that

P E c T ≤ BT exp(-CT 1/8 ) where E c
T is the complementary event of E T . The last lemma states that µ → T ε (µ, ω) -1 is Lipschitz. Its proof is deferred to the end. Lemma 13. For all vectors ω in the simplex, for all instances µ, µ in [µ min , µ max ] K we have:

|T ε (µ , ω) -1 -T ε (µ, ω) -1 | ≤ 4(µ max -µ min + ε) µ -µ ∞ .
Now we are ready to prove the Theorem. We denote by L 1 ([µ min , µ max ] K ) 4(µ max -µ min + ε) the Lipschitz constant of the mapping µ → T ε (µ, ω) -1 in the domain [µ min , µ max ] K and by L 2 (µ) max a,b∈ [K] (µa-µ b +ε) 2 2 the Lipschitz constant of the mapping ω → T ε (µ, ω) -1 .

We will prove a lower bound on T ε µ t , N (t) . Now applying Lemma 7 and the Lipschitz property w.r.t the weights, we have for all T 1/4 ≤ t ≤ T :

T ε µ t , N (t) t -1 ≥ T ε µ t , t s=1 ω( µ s ) t -1 -L 2,max K(1 + √ t) t ≥ t s=1 T ε µ t , ω( µ s ) -1 t -L 2,max K(1 + √ t) t ≥ t s= T 1/4 T ε µ t , ω( µ s ) -1 t -L 2,max K(1 + √ t) t
Where we used the fact that the mapping ω → T ε (µ, ω) -1 is concave (resp. non-negative) in the second (resp. last) inequality. Now observe that for all s, t ≥ T 1/4 , µ t -µ s ∞ ≤ 2ξ. Therefore the Lipschitz property w.r.t µ implies that: Therefore for η > 0, there exists t η such that for all t ≥ t η :

T ε µ t , N (
t s= T 1/4 T * ε µ s -1 t - t s= T 1/4 1 √ s t -L 2,max K(1 + √ t) t ≥ T * ε µ -1 -η. ( 12
)
Summing up (11) and (12), we get for all t ≥ t η :

T ε µ t , N (t) t -1 ≥ T * ε µ -1 -2ξL 1,max -η.
Therefore for every T ≥ max t η , β(δ,t)

T * ε µ -1 -2ξL1,max-η
, we have E T ⊂ (τ δ ≤ T ) thus P(τ δ > T ) ≤ P E c T ≤ BT exp(-CT 1/8 ). Hence:

E[τ δ ] = ∞ T =1 P(τ δ > T ) ≤ max t η , β(δ, t) T * ε µ -1 -2ξL 1,max -η + ∞ T =1
BT exp(-CT 1/8 ) Since lim , we have:

|f (µ , λ k, ε (ω)) -f (µ, λ k, ε (ω))| ≤ a∈[K] ω a (µ a -µ a + λ k, ε (ω) a -λ k, ε (ω) a )(µ a + µ a -λ k, ε (ω) a -λ k, ε (ω) a ) 2 ≤ ω a × 2 µ -µ ∞ × 2(µ max -µ min + ε) 2 = 2(µ max -µ min + ε) µ -µ ∞ .
where in the second inequality we used the fact that λ k, ε (ω) (resp. λ k, ε (ω)) is a weighted average of some arm in µ(resp. µ ) with one or more arms of µ(resp. µ ) decreased by ε and therefore lies in [µ min -ε, µ max ] K . Let (k 0 , l 0 ) be such that λ * ε,µ (ω) = λ k0,l0 ε (ω) then:

T ε (µ , ω) -1 -T ε (µ, ω) -1 = T ε (µ , ω) -1 -f ω, λ k0,l0 ε (ω) (13)
≤ f ω, λ k0,l0 ε (ω) -f ω, λ k0,l0 ε (ω)

≤ 2(µ max -µ min + ε) µµ ∞ .

(15)

Figure 1 :

 1 Figure 1: Left: Making One of the ε-Optimal Arms Bad. Right: Making One of the ε-Sub-Optimal Arms Good.

Figure 2 :

 2 Figure 2: Comparison of Alt(µ) with Simple Linear Boundaries (First Figure) and D ε, µ with Non-Linear Boundaries (Second Figure) for µ = [0.9, 0.6] and ε = 0.05. Lemma 5. (Danskin's Theorem) Let λ * (ω) be a best response to ω and define d * (ω)

Figure 3 :

 3 Figure 3: Expected Stopping Time on µ = [1, 1, 1, 1, 0.05]. Left: All three Algorithms. Right: Track-and-Stop vs FAREAST.

Figure 4 :

 4 Figure 4: Left: log 10 E Alg [τ δ ]/E TaS [τ δ ] for Alg ∈ {(ST) 2 , FAREAST} and TaS = Track-and-Stop, K min = 5 arms. Right: F1 scores for Cancer Drug discovery.

  E T which will result into an upper bound on the stopping timeτ δ = inf t ∈ N : tT ε µ t , N (t) t -1 ≥ β(δ, t) . First observe that under E T , the L 1 constant is upper bounded: L 1 (I ξ ) ≤ L 1,max 4(max a µ a -min b µ b + ε + 2ξ). Similarly, we have for all T 1/4 ≤ t ≤ T, L 2 ( µ t ) ≤ L 2,max (maxa µa-min b µ b +2ξ+ε) 2 2

E

  δ) = 1 the last inequality implies that lim sup δ→0 η and ξ go to zero.D.1 Proof of Lemma 13First case: arms in µ and µ have the same order Without loss of generality, suppose that µ 1 ≥ µ 2 ≥ . . . ≥ µ K and µ 1 ≥ µ 2 ≥ . . . ≥ µ K . Then we see that for all k = l ∈ [K], µ k, ε (ω) and µ k, ε (ω) have the same formula and :|µ k, ε (ω)µ k, ε (ω)| ≤ µµ ∞ , which implies that |λ k, ε (ω) -λ k, ε (ω)| ≤ µµ ∞ . Therefore, letting f denote the function f (µ, λ) a∈[K] ω a (µa-λa) 2 2

  the algorithm is δ-correct. Confidence level δ, accuracy parameter ε. Pull each arm once and observe rewards (r a ) a∈[K] . Set initial estimate µ K = (r 1 , . . . , r K ) T . Set t ← K and N a (t) ← 1 for all arms a.

	Algorithm 1: Track and Stop
	Input: while Stopping condition (4) is not satisfied do
	Compute ω( µ t ), a 1 √ t -optimal vector for (1) using mirror-ascent.
	Pull next arm a t+1 given by (3) and observe reward r t .
	Update µ t according to r t .
	Set t ← t + 1 and update N a (t) a∈[K] .
	end
	Output: Empirical set of ε-good arms:

  TV(P ν , P ν ) = TV P ν (E) × P ν (.|E) + P ν (E c ) × P ν (.|E c ), P ν (E) × P ν (.|E) + P ν (E c ) × P ν (.|E c ) = TV P ν (E) × P ν (.|E) + P ν (E c ) × P ν (.|E c ), P ν (E) × P ν (.|E) + P ν (E c ) × P ν (.|E c ) ≤ P ν (E)TV P ν (.|E), P ν (.|E) + P ν (E c )TV P ν (.|E c ), P ν (.|E c )

	(a)
	(b)
	(c)

  where in the second inequality we used the fact that by definition ω( µ s ) is at most 1 ε µ -1 almost surely (since N a (t) ≥ t + K 2 -2K).

														√	s sub-optimal.
	Now observe that:
	T * ε µ s	-1 -→
	t s= T 1/4 t K(1 + t	1 √ s √ t)	∼ t→∞ -→ 0.	t 1	dx √ x t	-→ 0.
	t	t)	-1	≥	t s= T 1/4	T ε µ s , ω( µ s ) t	-1	-	2ξL 1,max (t -T 1/4 ) t	-L 2,max	K(1 + t	√	t)
				≥	t s= T 1/4	T * ε µ s t	-1	-	t s= T 1/4 t	1 √ s	-2ξL 1,max -L 2,max	K(1 + t	√	t)
														(11)

s→∞

T *

Preprint. Under review.

For σ

-subgaussian distributions, we only need to multiply our bounds by σ 2 . For bandits coming from another single-parameter exponential family, we lose the closed-form expression of the best response oracle that we have in the Gaussian case, but one can use binary search to solve the best response problem.

or a subset of arms, as in our case.

The phenomenon discussed above is essentially already discussed in[START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF], a very rich study of the problem. However, we do not fully understand the proof of Theorem

4.1. Define a sub-instance to be a bandit ν with fewer arms m ≤ K such that { ν1, . . . , νm} ⊂ {ν1, . . . , νK }. Lemma D.5 actually shows that there exists some sub-instance of ν on which the algorithm must pay Ω( m b=2 1/(µ1 -µ b ) 2 ) samples. But this does not imply that such cost must be paid for the instance of interest ν instead of some sub-instance with very few arms.

µ k, ε (ω) has a different definition depending on k being a good or a bad arm.

ACRVL1, a Kinaze that researchers [BSK + 19] have linked to several forms of cancer. We use the same dataset as[START_REF] Mason | Finding all \epsilongood arms in stochastic bandits[END_REF], where for each compound a percent control 5 is reported. We fix a budget of samples N = 10 5 and try to find all the ε-good compounds in the multiplicative case with ε = 0.8. For each algorithm, we compute the F1-score 6 of its current estimate G ε = {i : µ i ≥ (1 -ε) max a µ a } after every iteration. The F1-score in this fixed-budget setting reflects how good is the sampling scheme of an algorithm, independently of its stopping condition. In Figure4we plot the average 5 percent control is a metric expressing the efficiency of the compound as an inhibitor against the target Kinaze.6 F1 score is the harmonic mean of precision (the proportion of arms in G that are actually good) and recall (the proportion of arms in Gε(µ) that were correctly returned in G).

that KL(P π , P ν ) = n KL(N (µ a , 1), N (µ b , 1)) + KL(N (µ b , 1), N (µ a , 1)) = n(µ a -µ b ) 2 ≤ n(µ 1 -µ b ) 2 . So that the inequality above simplifies to

Note that the inequality above holds trivially when a = b. Now for a fixed b by summing the inequality over all arms a ∈ G βε (µ) we get

Hence the statement of the lemma. Now the next lemma will show that arms in G βε (µ) must be played Ω(1/β 2 ε ) times because underestimating their means by β ε may cause to declare a bad arm as ε-optimal. Lemma 10. For all integers n ≥ 1,

Proof. Let η > 0. We define the instances λ and ν such that λ :

and ν :

By considering the event E = (∀a ∈ G βε (µ), N a (τ ) ≤ n), one can show in a similar fashion to the proof of Lemma 9 that

µ 1 -ε -µ k be a bad arm with the highest mean. Note that B becomes an ε-optimal arm under λ. Thus we have

where (a) comes from (9) and Pinsker's inequality, (b) is because all arms in G βε (µ) satisfy µ 1 -β ε ≤ µ a ≤ µ 1 and (c) comes from the fact that |G βε (µ)| ≤ |G βε (µ)|. Note that the inequality above holds for all η > 0. We get the final result by taking the limit η → 0.

By symmetry we get for all instances µ and µ with the same arm ordering:

Second case: arms in µ and µ have a different order Then for n large enough we can find a sequence (µ i ) 0≤i≤2 n of instances in the segment [µ, µ ] such that µ 0 = µ, µ 2 n = µ and:

∀i ∈ [|0, 2 n -1|], µ i and µ i+1 have the same arm ordering and

We can construct such a sequence in the following way: Split [µ min , µ max ] K into K! regions such that any two instances in the same region share the same arm ordering. The boundaries between these regions correspond to instances where two or more arms are equal. Starting from µ 0 µ, span the segment [µ, µ ] and define µ i+1 to be the first instance where: either the

, or we cross a boundary between two regions. Since there can be at most K! -1 changes in the arm ordering, for n large enough such sequence always exists. Now we have:

where in the second inequality we use the first case and the fact that µ i and µ i+1 have the same arm ordering. As a summary, we always have:


Quang-Duy Nguyen
email: quang-duy.nguyen@cea.fr

Saadia Dhouib
email: saadia.dhouib@cea.fr

Kunal Suri
email: kunal.suri@cea.fr

Fadwa Rekik
email: fadwa.tmar@cea.fr

From Requirement Specification to OPC UA Information Model Design: A Product Assembly Line Monitoring Case Study

Keywords: OPC UA, Information model, Design, Product assembly line, Robotic cell, System engineering

Open Platform Communication Unified Architecture (OPC UA) has emerged as a highly-demanded standard in building industrial systems. One factor in this success is the concepts of OPC UA address space and OPC UA information model. OPC UA address space provides a mechanism to represent the resources of an OPC UA server and its field devices as OPC UA nodes. OPC UA information model structures OPC UA nodes as a schema. Once other devices and systems understand the schema, they can interact appropriately with the industrial system. Thus, designing the OPC UA information model is an undeniable and essential practice of OPC UA-based industrial system engineering. However, both academia and industry suffer from a lack of shared experiences on this subject. This gap motivated us to share our experiences on the development of an OPC UA information model. These experiences are based on an actual product assembly line monitoring case study developed at CEA LIST. Overall, in this paper, we aim to throw some light on the steps involved in the transformation of a requirement specification into an OPC UA information model.

I. INTRODUCTION

Open Platform Communication Unified Architecture (OPC UA) is a widely-used standard in the industry. It is developed and maintained by the OPC Foundation, a group of more than 850 industry members. OPC UA's newest version, v1.05, consists of more than twenty-three specifications for building an industrial system with reliability, security, and interoperability. Its specifications part 3 and part 5 are the keys to semantic interoperability. Part 3, Address Space, provides the definition of OPC UA nodes and implies a mechanism to represent the resources of an OPC UA server and its field devices as OPC UA nodes [START_REF] Opc Foundation | OPC Unified Architecture -Part 3: Address Space Model[END_REF]. Part 5, Information Model, defines a vocabulary containing the most basic OPC UA nodes and implies a mechanism to structure OPC UA nodes as an OPC UA information model [START_REF] Opc Foundation | OPC Unified Architecture -Part 5: Information Model[END_REF]. In other words, an OPC UA information model is a schema of OPC UA nodes. This paper considers the vocabulary presented in the first twenty-three specifications as the standard information model. All other OPC UA information models rely on the standard information model. An OPC UA-based industrial system always has a domain-specific OPC UA information model and an OPC UA address space to store OPC UA nodes. Often, an OPC UA server manages the OPC UA address space. Other devices and systems can understand the system by learning from its OPC UA information model. Then, they can access its resources through the OPC UA address space lying in the OPC UA server. Figure 1 OPC UA information model is an undeniable and essential part of an OPC UA-based information system. Therefore, designing the OPC UA information model must be part of OPC UA-based information system engineering. However, it still lacks sharing experiences on this subject. Instead of focusing on the design step, some available research works describe steps for generating, serializing, and implementing the OPC UA information model and address space [START_REF] Pauker | A Systematic Approach to OPC UA Information Model Design[END_REF], [START_REF] Rohjans | UML-based modeling of OPC UA address spaces for power systems[END_REF]. The partners of the OPC Foundation often propose companion specifications that include their domain-specific OPC UA information model and examples of how to use them. However, such examples are usually minimal. While in other domains, such as ontology-based system engineering, there exists research that focuses on the reason and steps to analyze data from requirements to produce ontological schema design [START_REF] Poveda Villalón | Ontological Requirement Specification for Smart Irrigation Systems: A SOSA/SSN and SAREF Comparison[END_REF]. Their sharing is useful to system developers in the domain.

In addressing the above issue, this paper aims to share experiences transforming a requirement specification into an OPC UA information model design. This sharing is meaningful and compelling for two reasons. First, the experiences are from the actual case study of developing the Product Assembly Line (PAL) monitoring system deployed in the LocalSEA robotic cell of CEA LIST [START_REF] Nguyen | Early lessons learned from the development of a local OPC UA-based robotic testbed for research[END_REF]. The PAL is also used as a testbed for the ongoing work in context of Eclipse Papyrus for Manufacturing development environment and related toolset 1 . Second, this case study's OPC UA information model is complex. Indeed, it models hardware, software, and abstract components. Also, it deals with different complexity of data: real-time data, historical data, and summary data. Each complexity of components and data requires a different strategy to model.

The development methodology applied in this case study is mini-waterfall. It contains five phases: specification, design, implementation, testing, and maintenance [START_REF] Muller | Modélisation objet avec UML[END_REF]. However, the scope of this paper is only the two first phases.

The organization of this paper is as follows. Section II introduces the case study, which includes the context and motivation of this research. Section III focuses on analyzing the requirement specification. Then, Section IV describes in detail the transformation from the analysis into an OPC UA information design. Finally, a brief conclusion sums up this paper and opens a discussion.

II. CASE STUDY: PRODUCT ASSEMBLY LINE

MONITORING SYSTEM PAL refers to "a manufacturing process where the bill-ofmaterial parts and components are attached one-by-one to a unit in a sequential way by a series of workers to create a finished product" [START_REF] Thomopoulos | Assembly Line Planning and Control[END_REF]. Note that a worker can be a robot or a human in the modern industry. A workstation is a point in the series where one or several workers stay and do the same job. The PAL system deployed in LocalSEA illustrates box manufacturing. In which, a product is composed of two parts: a box and its cover. While a cover's color can be red or green, all boxes are the same. The PAL system is composed of two workstations. The first workstation, called storage, stores all covers. The worker in the storage is a Niryo Ned 2 robotic arm that can pick up one cover and drops it into a carrier. This procedure is called a pick-n-drop cycle. Then the carrier can transport it to the second workstation. There are two carriers: a conveyor belt carries red covers, and a mobile robot carries green covers. The mobile robot is a TurtleBot3 Waffle Pi 3 . The second workstation is a workspace where a human assembles boxes with red covers, and another assembles boxes with green covers. They produce two different products. Figure 2 illustrates the PAL system. In this scenario, there are two further remarks. First, in practice, Niryo Ned controls and supplies energy directly to the conveyor belt. Thus, it is possible to consider the conveyor belt as a component of Niryo Ned. Second, the park is a new component, representing the position where the mobile robot waits to carry a new cover. It is neither hardware nor software but an abstract component.

PAL monitoring involves getting real-time and historical data from the PAL system and viewing such data in a humanunderstandable interface. Thus, the PAL monitoring system requires a server to connect to field devices, collect data from them, record data when necessary, and expose such data to external clients. The server in this case study is an OPC UA server. The field devices are the two robots (Niryo Ned and TurtleBot3 Waffle Pi) and the conveyor belt. There are three stakeholders with different interests in data outputs. The first stakeholder plans to visualize the position and movement of Niryo Ned on an external computer in realtime. The second one needs to record the periods when the two robots work. Finally, the third stakeholder demands the answer to the following questions:

• At any given time, how many covers have been handled

by Niryo Ned? How many red covers? How many green covers? • How many covers are on the storage before each pick-ndrop cycle? • At any given time, what is the total energy consumption of Niryo Ned and TurtleBot3 Waffle Pi? • At any given time, are the conveyer belt and TurtleBot3

Waffle Pi still running?

III. REQUIREMENT SPECIFICATION ANALYSIS

In system development, the specification is the output from the specification phase. It contains all the information related to the case study and the requirements needed to deploy the next phase. The specification of the PAL monitoring case study includes mainly the eight groups of information:

(1) Information for project management.

( 8) Description of the services that the system can provide. Among the above, only information groups (2), ( 3), [START_REF] Nguyen | Early lessons learned from the development of a local OPC UA-based robotic testbed for research[END_REF], and ( 7) are necessary for the OPC UA information model design. Note that the information group ( 7) is translated from the demands of the stakeholders as follows.

system designers propose to record the temperature of the two robots' control unit processors (CPU) instead. The unit of each value is degree Celsius (°C). They have the same meaning in this case: when a robot is on, the CPU temperature of the robot's controller is above 0°C.

• Concerning the third stakeholder's demand, the questions turn into the following information:

-The number of (red) covers transported via conveyor belt. The data type is an integer. -The number of (green) covers transported via TurleBot3 Waffle Pi. The data type is an integer. -The number of covers that Niryo Ned's camera has found in the storage. The data type is an integer. -The energy consumption of Niryo Ned. The unit of energy consumption is Joule (J). The data type of energy consumption is double. -The energy consumption of TurtleBot3 Waffle Pi.

-The status of Niryo Ned.

-The status of TurtleBot3 Waffle Pi.

-The status of the conveyor belt.

For technical reasons, the information about the status of the park is also required. Indeed, it enables Niryo Ned to recognize whether the mobile robot is ready for transportation.

There are some remarks from the above information. First, the expected data from the first and second stakeholders can be obtained directly from data sources of the PAL system's devices without further processing. Thus, they are raw data. While the first stakeholder demands real-time raw data, the second is interested in historical data. Unlike the above, the expected data from the third stakeholder requires summary data. Such complex data usually are aggregated and processed by one or several software components. For example, no module works as an energy calculator integrating inside Niryo Ned. Thus, system designers can design a software component representing this module, and system developers must develop a program that calculates energy consumption and links the result to the software component.

System designers study the above information and extract five groups of requirements corresponding to five elements of the PAL: Niryo Ned, TurtleBot3 Waffle Pi, the storage, the conveyor belt, and the park. There are two types of requirements: (1) object and (2) variable. They all should be described with at least a title and a description. Each variable requirement must be associated with a specific data type.

IV. OPC UA INFORMATION MODEL DESIGN

The strategy to design our domain-specific OPC UA information model for PAL monitoring is to reuse the existing vocabulary before defining new concepts. This approach enables our designers to profit from well-defined concepts of industrial organizations and also improves the interoperability between OPC UA-based industrial systems. The group of new-defined concepts is called the custom-specific information model.

A. Vocabulary Selection

The vocabulary to study is the standard information model and the list of 40 companion specifications approved by the OPC Foundation. Among them, the OPC UA information model part 100 Devices (CS-DI) is one of the most important. It provides generic fundamental concepts for the topology of an industrial system, including all devices, hardware and software components, networks, and features [START_REF] Opc Foundation | OPC Unified Architecture -Part 100: Devices[END_REF]. It is the skeleton for many other companion specifications to extend.

Next, OPC UA information for Robotics (CS-Robotics) is another companion specification information model necessary for this case study. It is presented by the working group of the Mechanical Engineering Industry Association (VDMA), and OPC Foundation [START_REF]OPC UA for Robotics -Part 1: Vertical Integration[END_REF]. CS-Robotics also relies on CS-DI. The working group of VDMA and OPC Foundation aim to propose a vocabulary for multiple industrial robot types; however, CS-Robotics is still developing, and its current version only supports robotic arms. It is possible to divide this vocabulary into four groups related to four main objects: motion device system, controller, motion device, and safety state. Logically, a motion device system contains the three others.

Other companion specifications can be used to model some requirements in this case study. The companion specification for Process Automation Devices is worth mentioning.

It includes an extension of analog measurement variables that can detail BaseAnalogItemType of CS-DI, such as the concept of TemperatureMeasurementVariableType can cover the CPU temperature requirements. However, their impact on this case study is too small compared to the cost of loading the whole vocabulary. Thus, our designers decide to reuse only the standard information model, CS-DI, and CS-Robotics and define new custom-specific concepts when necessary.

B. Requirement Coverage

Requirement coverage is the step to selecting the concepts that can model requirements. In OPC UA information model language, the concept is a type such as ObjectType and VariableType. Table I presents the relation between the requirements listed in Section III and the concepts to cover them. In this table, each row represents the coverage of a requirement. The first column identifies the requirement. The second column contains the exact concept covering the requirement. The representation format of a concept comprises two parts: domain and Concept. The part domain is the namespace of the vocabulary that holds the concept. In detail, ns0 is for the standard information model, ns2 is for CS-DI, ns3 is for CS-Robotics, and ns4 is for the custom-specific information model. The part Concept is the name of concept.

As dedicated to robotic arms, many concepts from CS-Robotics can cover the group of requirements R1 related to Niryo Ned. However, there are some exceptions. First, no concept in our selected information models is specifically for the CPU. Since the generic ns2:DeviceType is abstract, our designers cannot use it directly but need to define the subtype ns4:ComputerComponentType to cover the CPU requirements. Fortunately, the CPU temperature variable requirements can be covered by ns0:AnalogUnitType. Second, concerning the software components, including counters and energy calculators, our designers can just use ns2:SoftwareType to cover them. However, their associated variables are summary data. Thus, to explicitly represent such complexity, it is necessary to define the ns4:AggregatedItemType variable type, as the subtype of ns0:DataItemType, dedicated to summary and processed data.

Concerning the group of requirements R2, there is not yet any vocabulary for mobile robots. Thus, our designers copy the schema from CS-Robotics and produce another version for mobile robots with some replacements. In detail, the new concepts related to mobile robots replace the concepts related to motion devices. Also, the new concepts related to wheels replace the concepts related to axes. Since the two types of robots share many identical characteristics, it is practical and easy to reuse well-defined concepts from CS-Robotics, such as ns3:ControllerType, with mobile robots. The schema of mobile robots is a part of the custom-specific information model.

Group R3 contains three elements. First, the storage is a component of the system, but it should not be modeled as a ns2:DeviceType or ns2:SoftwareType. Our designers then defines ns4:PlaceType as a subtype of the ns2:ComponentType object type to cover storage. On the other hand, the storage counter can be covered by ns2:SoftwareType, and the count number can be covered by ns4:AggregatedType. The park of group R4 can be covered by ns4:PlaceType. To cover the conveyor belt of the group R5, our designers define ns4:ConveyorBeltType as the subtype of ns4:DeviceType. The variables of the park and conveyor belt are status representing two states. Thus, both can be covered by ns0:TwoStateDiscreteType. Back to the two robots Niryo Ned and TurtleBot3 Waffle Pi, their status represents three states, so they must be covered by ns0:MultiStateDiscreteType.

C. Schema Forming

Forming a schema is the step that brings the semantic to a model by making relations of all elements. The concepts in the OPC UA information model language are linked due to references. Three basic reference types in our schema are HasComponent, Organizes, and HasProperty. Moreover, the references HasTypeDefinition and HasSubType appear in Subsection IV-A to define a new object or variable type. By default, information models provide not only the vocabulary, but also a schema with relations between the concepts. Thus, when reusing a schema, system designers have only three jobs:

(1) define instances from the concepts, (2) put the defined instances in appropriate positions in the schema, and (3) add details to complete it. Since the skeleton of the OPC UA information model for the PAL monitoring system is CS-DI and CS-Robotics, our designers can adopt the above strategy.

Figure 3 is an excerpt of the blueprint of our final OPC information model design. The DeviceSet instance predefined by CS-DI is the root for all device instances. In this case, there are two instances: Niryo _ Ned representing Niryo Ned and TurtleBot3 _ Waffle _ Pi representing TurtleBot3 Waffle Pi. As every MotionDeviceType instance, Niryo _ Ned has three groups of components which are Controlers, MotionDevices, and SafetyStates. Our designer defines the instance Raspberry _ Pi _ 4 as the controller of Niryo Ned. It has a microprocessor represented by the CPU instance. Temperature is one of the variable of the CPU's ParameterSet. In the MotionDevices group, our designers define Robot to represent the mechanical and electronic parts of the Niryo Ned. The instance has many sub-elements, of which three are essential for this scenario. First, the ParameterSet has the component which is the Status variable. Second, the Axes contains all the joint instances of Niryo Ned. Third, the AdditionalComponents can contain all additional modules of Niryo Ned. In this sense, all software components and their corresponding variables are in this folder. The organization of the sub-elements of TurtleBot3 _ Waffle _ Pi shares the same design logic as the one of Niryo _ Ned, as explained in Section IV-B. Also in this design, our designers consider the conveyor belt and the storage as additional components of Niryo Ned, and the park as an additional component of TurtleBot3 Waffle Pi.

All variables in our schema are described with properties except CountNumber. Every ActualPosition associates with an EngineeringUnits and a EURange. The former property holds the value which is the unit identification corresponding to mrad. The latter one holds the minimum and maximum rotation angle values. Every Status initiated by ns0:TwoStateDiscreteType has two properties of two states FalseState and TrueState. However, the Status initiated by ns0:MultiStateDiscreteType links to a property EnumStrings which associates with three integer values corresponding to available, busy, and offline states. Temperature and EnergyConsumption variables have EngineeringUnits, with the units respectively are °C and J. One essential addition to Temperature variables are a new property, called RepeatIntervalMs, which implies the frequency that the variables is updated. Our designers define this property to distinguish historical data from other real-time data. This paper presents the experiences of designing an OPC UA information model from a requirement specification. The presented PAL monitoring system relies on a case study deployed in the robotic testbed LocalSEA. The vocabulary used to model the system relies mainly on the standard information model, CS-DI, and CS-Robotics. The sharing experiences are helpful to system developers who are dealing with a complex OPC UA-based industrial system engineering. Unfortunately, limited by the case study, this paper has no chance to share experiences in modeling OPC UA methods and views.

There are three further points to discuss. First, it is worth recalling that the blueprint in Subsection IV-C is only a part of the complete OPC UA information model. Since this paper focuses on highlighting the transformation from requirements into design, therefore, avoids presenting other unrelated parts.

Second, the conveyor belt is an additional component of Niryo Ned as in our design, or can be modeled as an independent device. The choice depends on the design style and the case study. For example, the second solution is better when multiple robotic arms share the same conveyor belt.

Third, the serialization from the OPC UA information model design into a system modeling format is out of the scope of this paper. In reality, our designers develop and use an extension for Eclipse Papyrus to encode the design into a SysML-based model and then generate code for OPC UA servers. We plan to share this extension with the public in the future.

Fig. 1 .

 1 Fig. 1. Example of an OPC UA-based industrial system

Fig. 2 .

 2 Fig. 2. Product Assembly Line for box manufacturing deployed in LocalSEA

)

  Description of Niryo Ned, TurtleBot3 Waffle Pi, and the conveyor belt. (3) Description of the available network infrastructure and communication method. (4) Description of the role of human workers. (5) Description of the final products. (6) Description of the working procedure of the PAL. (7) Description of the expected output data. (

Fig. 3 .

 3 Fig.3. Excerpt of the blueprint of the OPC UA information system for the PAL monitoring case study

  R1. Niryo Ned is an object requirement to represent the Niryo Ned robotic arm. R1 Status: is a variable requirement to represent the status of Niryo Ned. It should have at least three states: available, busy, and offline. R1.1. Controller: is an object requirement to represent the Raspberry Pi 4 that controls Niryo Ned. Since the data is periodically recorded in a historical database, it should associate with a valid interval representing the recording frequency. R1.2. Joint base: is an object requirement to represent the joint that connects the base and shoulder of Niryo Ned. R1.2 Actual position: is a variable requirement to represent the rotation angle of the joint base. All actual position variables should be described with the unit rad or mrad, and the range of motion associated with the minimum and maximum rotation angle values. R1.3. Joint shoulder: is an object requirement to represent the joint that connects the shoulder and arm. R1.3 Actual position: is a variable requirement to represent the rotation angle of the joint shoulder. R1.4. Joint elbow: is an object requirement to represent the joint that connects the arm and elbow. R1.4 Actual position: is a variable requirement to represent the rotation angle of the joint elbow. R1.5. Joint forearm: is an object requirement to represent the joint that connects the elbow and forearm. R1.5 Actual position: is a variable requirement to represent the rotation angle of the joint forearm. R1.6. Joint wrist: is an object requirement to represent the joint that connects the forearm and wrist. R1.6 Actual position: is a variable requirement to represent the rotation angle of the joint wrist. R1.7. Joint hand: is an object requirement to represent the joint that connects the wrist and hand. R1.7 Actual position: is a variable requirement to represent the rotation angle of the joint hand. R1.8. Red cover counter: is an object requirement to represent a software component that counts the number of covers transported via the conveyor belt. R1.8 Count number: is a variable requirement to represent the number counted by the red cover counter. R1.9. Green cover counter: is an object requirement to represent a software component that counts the number of covers transported via TurtleBot3 Waffle Pi. R1.9 Count number: is a variable requirement to represent the number counted by the green cover counter. R1.10. Energy calculator: is an object requirement to represent a software component that calculates the energy consumption of Niryo Ned during a period. R1.10 Energy consumption: is a variable requirement to represent the calculation result. All energy consumption variables should be described with the unit joule (J). R2. TurtleBot3 Waffle Pi: is an object requirement to represent TurtleBot3 Waffle Pi. R2 Status: is a variable requirement to represent the status of TurtleBot3 Waffle Pi. It should have at least three states: available, busy, and offline. R2.1. Controller: is an object requirement to represent the Raspberry Pi 4 that controls TurtleBot3 Waffle Pi. R2.1.1. CPU: is an object requirement to represent a microprocessor of the Raspberry Pi 4. R2.1.1 Temperature: is a variable requirement to represent the CPU temperature. R2.2. Energy calculator: is an object requirement to represent a software component that calculates the energy consumption of TurtleBot3 Waffle Pi during a period. R2.2 Energy consumption: is a variable requirement to represent the calculation result. R3.1. Storage: is an object requirement to represent the physical storage. It is optional. R3.1.1. Storage counter: is an object requirement to represent a software component that counts the total of covers at the storage. R3.1.1 Count number: is a variable requirement to represent the number of covers at the storage. R4. Conveyor belt: is an object requirement to represent the conveyor belt of this case study. R4 Status: is a variable requirement to represent the status of the conveyor belt. It has only two states: on and off. R5. Park: is an object requirement to represent the position where the TurtleBot3 Waffle Pi waits to carry a cover. It is an abstract component. R5 Status: is a variable requirement to represent the state if the TurtleBot3 Waffle Pi is available in the park.

R1.1.1. CPU: is an object requirement to represent a microprocessor of the Raspberry Pi 4. R1.1.1 Temperature: is a variable requirement to represent the CPU temperature. All temperature variables should be described with the unit °C.

TABLE I REQUIREMENTS

 I COVERAGE BY THE STANDARD INFORMATION MODEL (NS0), CS-DI (NS2), CS-ROBOTICS (NS3), AND CUSTOM-SPECIFIC (NS4)

	Requirement	domain:Concept
	R1. Niryo Ned	ns3:MotionDeviceSystemType
	R1 Status	ns0:MultiStateDiscreateType
	R1.1. Controller	ns3:ControllerType
	R1.1.1. CPU	ns4:ComputerComponentType
	R1.1.1 Temperature	ns0:AnalogUnitType
	R1.2. Joint base	ns3:AxisType
	R1.2 Actual position	ns0:AnalogUnitType
	R1.3. Joint shoulder	ns3:AxisType
	R1.3 Actual position	ns0:AnalogUnitType
	R1.4. Joint elbow	ns3:AxisType
	R1.4 Actual position	ns0:AnalogUnitType
	R1.5. Joint forearm	ns3:AxisType
	R1.5 Actual position	ns0:AnalogUnitType
	R1.6. Joint wrist	ns3:AxisType
	R1.6 Actual position	ns0:AnalogUnitType
	R1.7. Joint hand	ns3:AxisType
	R1.7 Actual position	ns0:AnalogUnitType
	R1.8. Red cover counter	ns2:SoftwareType
	R1.8 Count number	ns4:AggregatedItemType
	R1.9. Green cover counter	ns2:SoftwareType
	R1.9 Count number	ns4:AggregatedItemType
	R1.10. Energy calculator	ns2:SoftwareType
	R1.10 Energy consumption	ns4:AggregatedItemType
	R2. TurtleBot3 Waffle Pi	ns4:MobileRobotSystemType
	R2 Status	ns0:MultiStateDiscreateType
	R2.1. Controller	ns3:ControllerType
	R2.1.1. CPU	ns4:ComputerComponentType
	R2.1.1 Temperature	ns0:AnalogUnitType
	R2.2. Energy calculator	ns4:SoftwareType
	R2.2 Energy consumption	ns4:AggregatedItemType
	R3.1. Storage	ns4:PlaceType
	R3.1.1. Storage counter	ns2:SoftwareType
	R3.1.1 Count number	ns4:AggregatedItemType
	R4. Park	ns4:PlaceType
	R4 Status	ns0:TwoStateDiscreteType
	R5. Conveyor belt	ns4:ConveyorBeltType
	R5 Status	ns0:TwoStateDiscreteType

https://www.eclipse.org/papyrus/components/manufacturing/ This is not the final version. For more information, please check: https://ieeexplore.ieee.org/xpl/conhome/1001443/all-proceedings

• Concerning the first stakeholder's demand, the expected data is the rotation angles of the robot arm's six joints.The unit of each joint's value should be radian (rad) or milliradian (mrad). The manufacturer defines the limitation of each joint. For example, the angle that the first joint can rotate is between -2970 and 2970 mrad. • Concerning the second stakeholder's demand, the information about when the two robots are "on" or "off" is not informative to record in the historical database. Thus,