Victor Gabillon
email: victor.gabillon@inria.fr

Mohammad Ghavamzadeh
email: mohammad.ghavamzadeh@inria.fr

Alessandro Lazaric
email: alessandro.lazaric@inria.fr

Sébastien Bubeck
email: sbubeck@princeton.edu

Multi-Bandit Best Arm Identification

We study the problem of identifying the best arm in each of the bandits in a multibandit multi-armed setting. We first propose an algorithm called Gap-based Exploration (GapE) that focuses on the arms whose mean is close to the mean of the best arm in the same bandit (i.e., small gap). We then introduce an algorithm, called GapE-V, which takes into account the variance of the arms in addition to their gap. We prove an upper-bound on the probability of error for both algorithms. Since GapE and GapE-V need to tune an exploration parameter that depends on the complexity of the problem, which is often unknown in advance, we also introduce variations of these algorithms that estimate this complexity online. Finally, we evaluate the performance of these algorithms and compare them to other allocation strategies on a number of synthetic problems.

Introduction

Consider a clinical problem with M subpopulations, in which one should decide between K m options for treating subjects from each subpopulation m. A subpopulation may correspond to patients with a particular gene biomarker (or other risk categories) and the treatment options are the available treatments for a disease. The main objective here is to construct a rule, which recommends the best treatment for each of the subpopulations. These rules are usually constructed using data from clinical trials that are generally costly to run. Therefore, it is important to distribute the trial resources wisely so that the devised rule yields a good performance. Since it may take significantly more resources to find the best treatment for one subpopulation than for the others, the common strategy of enrolling patients as they arrive may not yield an overall good performance. Moreover, applying treatment options uniformly at random in a subpopulation could not only waste trial resources, but also it might run the risk of finding a bad treatment for that subpopulation. This problem can be formulated as the best arm identification over M multi-armed bandits [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF], which itself can be seen as the problem of pure exploration [START_REF] Bubeck | Pure exploration in multi-armed bandit problems[END_REF] over multiple bandits. In this formulation, each subpopulation is considered as a multi-armed bandit, each treatment as an arm, trying a medication on a patient as a pull, and we are asked to recommend an arm for each bandit after a given number of pulls (budget). The evaluation can be based on 1) the average over the bandits of the reward of the recommended arms, or 2) the average probability of error (not selecting the best arm), or 3) the maximum probability of error. Note that this setting is different from the standard multi-armed bandit problem in which the goal is to maximize the cumulative sum of rewards (see e.g., [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF][START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF]).

Another motivating example is the popular problem of online advertisement, where a company uses a testing phase before deploying its advertisement system. This problem can also be formulated as above, where each bandit is a subpopulation of Internet users (e.g., young, old, single, married), each arm is a category of advertisements, and each pull is to show an advertisement to a user. Here the goal is to actively learn a rule, which recommends the best (the one with the highest chance to be clicked on) category of advertisements for each of the subpopulations.

Another motivating example is a brain-computer interface problem. A computer has to guess a letter chosen by a user. The computer arranges the letters in a matrix displayed to the user. At each timestep, the computer chooses either a row or a column and asks the user if the chosen letter belongs to it. The answer is obtained by recording noisy brain activity signals. This problem can be formalized as a two-bandit best arm identification problem where the bandits are "rows" and "columns". In this problem, the right measure of performance is exactly the maximum probability of error, since doing a mistake in either row or column would lead to choose the wrong letter.

The pure exploration problem is about designing strategies that make the best use of the limited budget (e.g., the total number of patients that can be admitted to the clinical trial) in order to optimize the performance in a decision-making task. Audibert et al. [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] proposed two algorithms to address this problem: 1) a highly exploring strategy based on upper confidence bounds, called UCB-E, in which the optimal value of its parameter depends on some measure of the complexity of the problem, and 2) a parameter-free method based on progressively rejecting the arms which seem to be suboptimal, called Successive Rejects. They showed that both algorithms are nearly optimal since their probability of returning the wrong arm decreases exponentially at a rate. Racing algorithms (e.g., [START_REF] Maron | Hoeffding races: Accelerating model selection search for classification and function approximation[END_REF][START_REF] Mnih | Empirical Bernstein stopping[END_REF]) and action-elimination algorithms [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF] address this problem under a constraint on the accuracy in identifying the best arm and they minimize the budget needed to achieve that accuracy. However, UCB-E and Successive Rejects are designed for a single bandit problem, and as we will discuss later, cannot be easily extended to the multi-bandit case studied in this paper. Deng et al. have recently proposed an active learning algorithm for resource allocation over multiple bandits [START_REF] Deng | Active learning for personalizing treatment[END_REF]. However, they do not provide any theoretical analysis for their algorithm and only empirically evaluate its performance. Moreover, the target of their proposed algorithm is to minimize the maximum uncertainty in estimating the value of the arms for each bandit. Note that this is different than our target, which is to maximize the quality of the arms recommended for each bandit.

In this paper, we study the problem of best-arm identification in a multi-armed multi-bandit setting under a fixed budget constraint, and propose an algorithm, called Gap-based Exploration (GapE), to solve it. The allocation strategy implemented by GapE focuses on the gap of the arms, i.e., the difference between the mean of the arm and the mean of the best arm (in that bandit). The GapE-variance (GapE-V) algorithm extends this approach taking into account also the variance of the arms. For both algorithms, we prove an upper-bound on the probability of error that decreases exponentially with the budget. Since both GapE and GapE-V need to tune an exploration parameter that depends on the complexity of the problem, which is rarely known in advance, we also introduce their adaptive version. Finally, we evaluate the performance of these algorithms and compare them with Uniform and Uniform+UCB-E strategies on a number of synthetic problems. Our empirical results indicate that 1) GapE and GapE-V have a better performance than Uniform and Uniform+UCB-E, and 2) the adaptive version of these algorithms match the performance of their non-adaptive counterparts.

Problem Setup

In this section, we introduce the notation used throughout the paper and formalize the multi-bandit best arm identification problem. Let M be the number of bandits and K be the number of arms for each bandit (we use indices m, p, q for the bandits and k, i, j for the arms). Each arm k of a bandit m is characterized by a distribution ν mk bounded in [0, b] with mean µ mk and variance σ 2 mk . In the following, we assume that each bandit has a unique best arm. We denote by µ * m and k * m the mean and the index of the best arm of bandit m (i.e., µ * m = max 1≤k≤K µ mk , k * m = arg max 1≤k≤K µ mk ). In each bandit m, we define the gap for each arm as

∆ mk = | max j =k µ mj -µ mk |.
The clinical trial problem described in Sec. 1 can be formalized as a game between a stochastic multibandit environment and a forecaster, where the distributions {ν mk } are unknown to the forecaster. At each round t = 1, . . . , n, the forecaster pulls a bandit-arm pair I(t) = (m, k) and observes a sample drawn from the distribution ν I(t) independent from the past. The forecaster estimates the expected value of each arm by computing the average of the samples observed over time. Let T mk (t) be the number of times that arm k of bandit m has been pulled by the end of round t, then the mean of this arm is estimated as

µ mk (t) = 1 T mk (t)
T mk (t) s=1 X mk (s), where X mk (s) is the s-th sample observed from ν mk . Given the previous definitions, we define the estimated gaps as ∆ mk (t) = | max j =k µ mj (t) -µ mk (t)|. At the end of round n, the forecaster returns for each bandit m the arm with the highest estimated mean, i.e., J m (n) = arg max k µ mk (n), and incurs a regret Parameters: number of rounds n, exploration parameter a, maximum range b Initialize: T mk (0) = 0, ∆ mk (0) = 0 for all bandit-arm pairs (m, k) 1) for all bandit-arm pairs (m, k)

for t = 1, 2, . . . , n do Compute B mk (t) = -∆ mk (t -1) + b a T mk (t-
Draw I(t) ∈ arg max m,k B mk (t) Observe X I(t) T I(t) (t -1) + 1 ∼ ν I(t) Update T I(t) (t) = T I(t) (t -1)
r(n) = 1 M M m=1 rm(n) = 1 M M m=1 µ * m -µ mJm (n) .
As discussed in the introduction, other performance measures can be defined for this problem. In some applications, returning the wrong arm is considered as an error independently from its regret, and thus, the objective is to minimize the average probability of error

e(n) = 1 M M m=1 em(n) = 1 M M m=1 P Jm(n) = k * m .
Finally, in problems similar to the clinical trial, a reasonable objective is to return the right treatment for all the genetic profiles and not just to have a small average probability of error. In this case, the global performance of the forecaster can be measured as

ℓ(n) = max m ℓm(n) = max m P Jm(n) = k * m .
It is interesting to note the relationship between these three performance measures:

min m ∆ m × e(n) ≤ Er(n) ≤ b×e(n) ≤ b×ℓ(n)
, where the expectation in the regret is w.r.t. the random samples. As a result, any algorithm minimizing the worst case probability of error, ℓ(n), also controls the average probability of error, e(n), and the simple regret Er(n). Note that the algorithms introduced in this paper directly target the problem of minimizing ℓ(n).

The Gap-based Exploration Algorithm

Fig. 1 contains the pseudo-code of the gap-based exploration (GapE) algorithm. GapE flattens the bandit-arm structure and reduces it to a single-bandit problem with M K arms. At each time step t, the algorithm relies on the observations up to time t -1 to build an index B mk (t) for each banditarm pair, and then selects the pair I(t) with the highest index. The index B mk consists of two terms. The first term is the negative of the estimated gap for arm k in bandit m. Similar to other upper-confidence bound (UCB) methods [START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF], the second part is an exploration term which forces the algorithm to pull arms that have been less explored. As a result, the algorithm tends to pull arms with small estimated gap and small number of pulls. The exploration parameter a tunes the level of exploration of the algorithm. As it is shown by the theoretical analysis of Sec. , where H = m,k b 2 /∆ 2 mk is the complexity of the problem (see Sec. 3.1 for further discussion). Note that GapE differs from most standard bandit strategies in the sense that the B-index for an arm depends explicitly on the statistics of the other arms. This feature makes the analysis of this algorithm much more involved.

As we may notice from Fig. 1, GapE resembles the UCB-E algorithm [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] designed to solve the pure exploration problem in the single-bandit setting. Nonetheless, the use of the negative estimated gap (-∆ mk ) instead of the estimated mean ( µ mk ) (used by UCB-E) is crucial in the multi-bandit setting. In the single-bandit problem, since the best and second best arms have the same gap (∆ mk * m = min k =k * m ∆ mk ), GapE considers them equivalent and tends to pull them the same amount of time, while UCB-E tends to pull the best arm more often than the second best one. Despite this difference, the performance of both algorithms in predicting the best arm after n pulls would be the same. This is due to the fact that the probability of error depends on the capability of the algorithm to distinguish optimal and suboptimal arms, and this is not affected by a different allocation over the best and second best arms as long as the number of pulls allocated to that pair is large enough w.r.t. their gap. Despite this similarity, the two approaches become completely different in the multi-bandit case. In this case, if we run UCB-E on all the M K arms, it tends to pull more the arm with the highest mean over all the bandits, i.e., k * = arg max m,k µ mk . As a result, it would be accurate in predicting the best arm k * over bandits, but may have an arbitrarily bad performance in predicting the best arm for each bandit, and thus, may incur a large error ℓ(n). On the other hand, GapE focuses on the arms with the smallest gaps. This way, it assigns more pulls to bandits whose optimal arms are difficult to identify (i.e., bandits with arms with small gaps), and as shown in the next section, it achieves a high probability in identifying the best arm in each bandit.

Theoretical Analysis

In this section, we derive an upper-bound on the probability of error ℓ(n) for the GapE algorithm. , then its probability of error satisfies

ℓ(n) ≤ P ∃m : J m (n) = k * m ≤ 2M Kn exp(- a 64 ),
in particular for a =

H mk = b 2 /∆ 2
mk , the complexity of arm k in bandit m, it is clear from the definition of H that each arm has an additive impact on the overall complexity of the multi-bandit problem. Moreover, if we define the complexity of each bandit m as H m = k b 2 /∆ 2 mk (similar to the definition of complexity for UCB-E in [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF]), the GapE complexity may be rewritten as H = m H m . This means that the complexity of GapE is simply the sum of the complexities of all the bandits.

Remark 2 (Comparison with the static allocation strategy).

The main objective of GapE is to tradeoff between allocating pulls according to the gaps (more precisely, according to the complexities H mk ) and the exploration needed to improve the accuracy of their estimates. If the gaps were known in advance, a nearly-optimal static allocation strategy assigns to each bandit-arm pair a number of pulls proportional to its complexity. Let us consider a strategy that pulls each arm a fixed number of times over the horizon n. The probability of error for this strategy may be bounded as

ℓStatic(n) ≤ P ∃m : Jm(n) = k * m ≤ M m=1 P Jm(n) = k * m ≤ M m=1 k =k * m P μmk * m (n) ≤ μmk (n) ≤ M m=1 k =k * m exp -T mk (n) ∆ 2 mk b 2 = M m=1 k =k * m exp -T mk (n)H -1 mk . (1)
Given the constraint mk T mk (n) = n, the allocation minimizing the last term in Eq. 1 is T * mk (n) = nH mk /H. We refer to this fixed strategy as StaticGap. Although this is not necessarily the optimal static strategy (T * mk (n) minimizes an upper-bound), this allocation guarantees a probability of error smaller than M K exp(-n/H). Theorem 1 shows that, for n large enough, GapE achieves the same performance as the static allocation StaticGap.

Remark 3 (Comparison with other allocation strategies).

At the beginning of Sec. 3, we discussed the difference between GapE and UCB-E. Here we compare the bound reported in Theorem 1 with the performance of the Uniform and combined Uniform+UCB-E allocation strategies. In the uniform allocation strategy, the total budget n is uniformly split over all the bandits and arms. As a result, each bandit-arm pair is pulled T mk (n) = n/(M K) times. Using the same derivation as in Remark 2, the probability of error ℓ(n) for this strategy may be bounded as

ℓUnif(n) ≤ M m=1 k =k * m exp - n M K ∆ 2 mk b 2 ≤ M K exp - n M K max m,k H mk .
In the Uniform+UCB-E allocation strategy, i.e., a two-level algorithm that first selects a bandit uniformly and then pulls arms within each bandit using UCB-E, the total number of pulls for each bandit m is k T mk (n) = n/M , while the number of pulls T mk (n) over the arms in bandit m is determined by UCB-E. Thus, the probability of error of this strategy may be bounded as

ℓUnif+UCB-E(n) ≤ M m=1 2nK exp - n/M -K 18Hm ≤ 2nM K exp - n/M -K 18 maxm Hm ,
where the first inequality follows from Theorem 1 in [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF] (recall that H m = k b 2 /∆ 2 mk ). Let b = 1 (i.e., all the arms have distributions bounded in [0, 1]), up to constants and multiplicative factors in front of the exponentials, and if n is large enough compared to M and K (so as to approximate n/M -K and n -K by n), the probability of error for the three algorithms may be bounded as

ℓUnif(n) ≤ exp O -n/M K max m,k H mk , ℓU+UCBE(n) ≤ exp O -n/M max m Hm , ℓGapE(n) ≤ exp O -n m,k H mk .
By comparing the arguments of the exponential terms, we have the trivial sequence of inequalities

M K max m,k H mk ≥ M max m k H mk ≥ m,k
H mk , which implies that the upper bound on the probability of error of GapE is usually significantly smaller. This relationship, which is confirmed by the experiments reported in Sec. 4, shows that GapE is able to adapt to the complexity H of the overall multi-bandit problem better than the other two allocation strategies. In fact, while the performance of the Uniform strategy depends on the most complex arm over the bandits and the strategy Unif+UCB-E is affected by the most complex bandit, the performance of GapE depends on the sum of the complexities of all the arms involved in the pure exploration problem.

Proof of Theorem 1.

Step 1. Let us consider the following event:

E = ∀m ∈ {1, . . . , M }, ∀k ∈ {1, . . . , K}, ∀t ∈ {1, . . . , n}, µ mk (t) -µ mk < bc a T mk (t)
.

From Chernoff-Hoeffding's inequality and a union bound, we have P(ξ) ≥ 1-2M Kn exp(-2ac 2 ). Now we would like to prove that on the event E, we find the best arm for all the bandits, i.e., J m

(n) = k * m , ∀m ∈ {1 . . . M }. Since J m (n)
is the empirical best arm of bandit m, we should prove that for any k ∈ {1, . . . , K}, µ mk (n) ≤ µ mk * m (n). By upper-bounding the LHS and lower-bounding the RHS of this inequality, we note that it would be enough to prove bc a/T mk (n) ≤ ∆ mk /2 on the event E, or equivalently, to prove that for any bandit-arm pair m, k, we have

T mk (n) ≥ 4ab 2 c 2 ∆ 2 mk .
Step 2. In this step, we show that in GapE, for any bandits (m, q) and arms (k, j), and for any t ≥ M K, the following dependence between the number of pulls of the arms holds

-∆ mk + (1 + d)b a max T mk (t) -1, 1 ≥ -∆ qj + (1 -d)b a T qj (t) , (2)
where d ∈ [0, 1]. We prove this inequality by induction.

Base step. We know that after the first M K rounds of the GapE algorithm, all the arms have been pulled once, i.e., T mk (t) = 1, ∀m, k, thus if a ≥ 1/4d 2 , the inequality (2) holds for t = M K.

Inductive step. Let us assume that (2) holds at time t -1 and we pull arm i of bandit p at time t, i.e., I(t) = (p, i). So at time t, the inequality (2) trivially holds for every choice of m, q, k, and j, except when (m, k) = (p, i). As a result, in the inductive step, we only need to prove that the following holds for any q ∈ {1, . . . M } and j ∈ {1, . . . K}

-∆ pi + (1 + d)b a max T pi (t) -1, 1 ≥ -∆ qj + (1 -d)b a T qj (t) . (3)
Since arm i of bandit p has been pulled at time t, we have that for any bandit-arm pair (q, j)

-∆ pi (t -1) + b a T pi (t -1) ≥ -∆ qj (t -1) + b a T qj (t -1) . (4)
To prove (3), we first prove an upper-bound for -∆ pi (t -1) and a lower-bound for -∆ qj (t -1)

-∆ pi (t-1) ≤ -∆ pi + 2bc 1 -c a T pi (t) -1 and -∆ qj (t-1) ≥ -∆ qj - 2 √ 2bc 1 -d a T qj (t) . (5)
We report the proofs of the inequalities in [START_REF] Deng | Active learning for personalizing treatment[END_REF] in in Appendix B. The inequality (3), and as a result, the inductive step is proved by replacing -∆ pi (t -1) and -∆ qj (t -1) in ( 4) from ( 5) and under the conditions that d ≥ 2c 1-c and d ≥ 2

√ 2c 1-d . These conditions are satisfied by d = 1/2 and c = √ 2/16.

Step 3. In order to prove the condition of T mk (n) in step 1, we need to find a lower-bound on the number of pulls of all the arms at time t = n (at the end). Let us assume that arm k of bandit m has been pulled less than

ab 2 (1-d) 2 ∆ 2 mk , which indicates that -∆ mk + (1 -d)b a T mk (n) > 0.
From this result and (2), we have

-∆ qj + (1 + d)b a Tqj (n)-1 > 0, or equivalently T qj (n) < ab 2 (1+d) 2 ∆ 2 qj + 1
for any pair (q, j). We also know that q,j T qj (n) = n. From these, we deduce that n -

M K < ab 2 (1 + d) 2 q,j 1 ∆ 2 qj . So, if we select a such that n -M K ≥ ab 2 (1 + d) 2 q,j 1 ∆ 2 qj , we contradict the first assumption that T mk (n) < ab 2 (1-d) 2 ∆ 2 mk , which means that T mk (n) ≥ 4ab 2 c 2 ∆ 2 mk
for any pair (m, k), when 1 -d ≥ 2c. This concludes the proof. The condition for a in the statement of the theorem comes from our choice of a in this step and the values of c and d from the inductive step.

Extensions

In this section we propose two variants on the GapE algorithm with the objective of extending its applicability and improving its performance.

GapE with variance (GapE-V).

The allocation strategy implemented by GapE focuses only on the arms with small gap and does not take into consideration their variance. However, it is clear that the arms with small variance, even if their gap is small, just need a few pulls to be correctly estimated. In order to take into account both the gaps and variances of the arms, we introduce the GapE-variance (GapE-V) algorithm. Let

σ 2 mk (t) = 1 T mk (t)-1 T mk (t) s=1 X mk (s) -µ mk (t)
2 be the estimated variance for arm k of bandit m at the end of round t. GapE-V uses the following B-index for each arm:

B mk (t) = -∆ mk (t -1) + 2a σ 2 mk (t -1) T mk (t -1) + 7ab 3 T mk (t -1) -1 .
Note that the exploration term in the B-index has now two components: the first one depends on the empirical variance and the second one decreases as O(1/T mk ). As a result, arms with low variance will be explored much less than in the GapE algorithm. Similar to the difference between UCB [START_REF] Auer | Finite-time analysis of the multi-armed bandit problem[END_REF] and UCB-V [START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF], while the B-index in GapE is motivated by Hoeffding's inequalities, the one for GapE-V is obtained using an empirical Bernstein's inequality [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF][START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF]. The following performance bound can be proved for GapE-V algorithm. We report the proof of Theorem 2 in in Appendix C.

Theorem 2. If GapE-V is run with parameter 0 < a ≤ 8 9 n-2MK H σ , then it satisfies ℓ(n) ≤ P ∃m : J m (n) = k * m ≤ 6nM K exp - 9a 64 × 64 in particular for a = 8 9 n-2MK H σ , we have ℓ(n) ≤ 6nM K exp -1 64×8 n-2MK H σ .
In Theorem 2, H σ is the complexity of the GapE-V algorithm and is defined as

H σ = M m=1 K k=1 σ mk + σ 2 mk + (16/3)b∆ mk 2 ∆ 2 mk .
Although the variance-complexity H σ could be larger than the complexity H used in GapE, whenever the variances of the arms are small compared to the range b of the distribution, we expect H σ to be smaller than H. Furthermore, if the arms have very different variances, then GapE-V is expected to better capture the complexity of each arm and allocate the pulls accordingly. For instance, in the case where all the gaps are the same, GapE tends to allocate pulls proportionally to the complexity H mk and it would perform an almost uniform allocation over bandits and arms. On the other hand, the variances of the arms could be very heterogeneous and GapE-V would adapt the allocation strategy by pulling more often the arms whose values are more uncertain.

H(t) = m,k b 2 UCB∆ i (t) 2 , H σ (t) = m,k LCBσ i (t) + LCBσ i (t) 2 + (16/3)b × UCB∆ i (t) 2 UCB∆ i (t) 2
, where

UCB∆ i (t) = ∆i(t -1) + 1 2Ti(t -1) and LCBσ i (t) = max 0, σi(t -1) - 2 Ti(t -1) -1 .
Similar to the adaptive version of UCB-E in [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF], H and H σ are lower-confidence bounds on the true complexities H and H σ . Note that the GapE and GapE-V bounds written for the optimal value of a indicate an inverse relation between the complexity and the exploration. By using a lower-bound on the true H and H σ , the algorithms tend to explore arms more uniformly and this allows them to increase the accuracy of their estimated complexities. Although we do not analyze these algorithms, we empirically show in Sec. 4 that they are in fact able to match the performance of the GapE and GapE-V algorithms.

Numerical Simulations

In this section, we report numerical simulations of the gap-based algorithms presented in this paper, GapE and GapE-V, and their adaptive versions A-GapE and A-GapE-V, and compare them with Unif and Unif+UCB-E algorithms introduced in Sec. 3.1. The results of our experiments both those in the paper and those in Appendix A indicate that 1) GapE successfully adapts its allocation strategy to the complexity of each bandit and outperforms the uniform allocation strategies, 2) the use of the empirical variance in GapE-V can significantly improve the performance over GapE, and 3) the adaptive versions of GapE and GapE-V that estimate the complexities H and H σ online attain the same performance as the basic algorithms, which receive H and H σ as an input.

Experimental setting. We use the following three problems in our experiments. Note that b = 1 and that a Rademacher distribution with parameters (x, y) takes value x or y with probability 1/2. All the algorithms, except the uniform allocation, have an exploration parameter a. The theoretical analysis suggests that a should be proportional to n H . Although a could be optimized according to the bound, since the constants in the analysis are not accurate, we will run the algorithms with a = η n H , where η is a parameter which is empirically tuned (in the experiments we report four different values for η). If H correctly defines the complexity of the exploration problem (i.e., the number of samples to find the best arms with high probability), η should simply correct the inaccuracy of the constants in the analysis, and thus, the range of its nearly-optimal values should be constant across different problems. In Unif+UCB-E, UCB-E is run with the budget of n/M and the same parameter η for all the bandits. Finally, we set n ≃ H σ , since we expect H σ to roughly capture the number of pulls necessary to solve the pure exploration problem with high probability. In Figs. 2 and3, we report the performance l(n), i.e. the probability to identify the best arm in all the bandits after n rounds, of the gap-based algorithms as well as Unif and Unif+UCB-E strategies. The results are averaged over 10 5 runs and the error bars correspond to three times the estimated standard deviation. In all the figures the performance of Unif is reported as a horizontal dashed line.

Unif + A UCBE-V 1/4 1/2 1 2 GapE 4 8 16 32 A GapE 1/4 1/2 1 2 GapE-V 1/2 1 2 4 A GapE-V 1/4 1/2 1 2
The left panel of Fig. 2 displays the performance of Unif+UCB-E, GapE, and A-GapE in Problem 1.

As expected, Unif+UCB-E has a better performance (23.9% probability of error) than Unif (29.4% probability of error), since it adapts the allocation within each bandit so as to pull more often the nearly-optimal arms. However, the two bandit problems are not equally difficult. In fact, their complexities are very different (H 1 ≃ 925 and H 2 ≃ 67), and thus, much less samples are needed to identify the best arm in the second bandit than in the first one. Unlike Unif+UCB-E, GapE adapts its allocation strategy to the complexities of the bandits (on average only 19% of the pulls are allocated to the second bandit), and at the same time to the arm complexities within each bandit (in the first bandit the averaged allocation of GapE is (37%, 36%, 20%, 7%)). As a result, GapE has a probability of error of 15.7%, which represents a significant improvement over Unif+UCB-E.

The right panel of Fig. 2 compares the performance of GapE, GapE-V, and A-GapE-V in Problem 2.

In this problem, all the gaps are equals (∆ mk = 0.05), thus all the arms (and bandits) have the same complexity H mk = 400. As a result, GapE tends to implement a nearly uniform allocation, which results in a small difference between Unif and GapE (28% and 25% accuracy, respectively). The reason why GapE is still able to improve over Unif may be explained by the difference between static and dynamic allocation strategies and it is further investigated in Appendix A. Unlike the gaps, the variance of the arms is extremely heterogeneous. In fact, the variance of the arms of bandit 1 is bigger than in bandit 2, thus making it harder to solve. This difference is captured by the definition of H σ (H σ 1 ≃ 1400 > H σ 2 ≃ 600). Note also that H σ ≤ H. As discussed in Sec. 3.2, since GapE-V takes into account the empirical variance of the arms, it is able to adapt to the complexity H σ mk of each bandit-arm pair and to focus more on uncertain arms. GapE-V improves the final accuracy by almost 10% w.r.t. GapE. From both panels of Fig. 2, we also notice that the adaptive algorithms achieve similar performance to their non-adaptive counterparts. Finally, we notice that a good choice of parameter η for GapE-V is always close to 2 and 4 (see also [START_REF] Gabillon | Multi-bandit best arm identification[END_REF] for additional experiments), while GapE needs η to be tuned more carefully, particularly in Problem 2 where the large values of η try to compensate the fact that H does not successfully capture the real complexity of the problem. This further strengthens the intuition that H σ is a more accurate measure of the complexity for the multi-bandit pure exploration problem.

While Problems 1 and 2 are relatively simple, we report the results of the more complicated Problem 3 in Fig. 3. The experiment is designed so that the complexity w.r.t. the variance of each bandit and within each bandit is strongly heterogeneous. In this experiment, we also introduce UCBE-V that extends UCB-E by taking into account the empirical variance similarly to GapE-V. The re-sults confirm the previous findings and show the improvement achieved by introducing empirical estimates of the variance and allocating non-uniformly over bandits.

Conclusion

In this paper, we studied the problem of best arm identification in a multi-bandit multi-armed setting. We introduced a gap-based exploration algorithm, called GapE, and proved an upper-bound for its probability of error. We extended the basic algorithm to also consider the variance of the arms and proved an upper-bound for its probability of error. We also introduced adaptive versions of these algorithms that estimate the complexity of the problem online. The numerical simulations confirmed the theoretical findings that GapE and GapE-V outperform other allocation strategies, and that their adaptive counterparts are able to estimate the complexity without worsening the global performance.

Although GapE does not know the gaps, the experimental results reported in [START_REF] Gabillon | Multi-bandit best arm identification[END_REF] indicate that it might outperform a static allocation strategy, which knows the gaps in advance, thus suggesting that an adaptive strategy could perform better than a static one. This observation asks for further investigation. Moreover, we plan to apply the algorithms introduced in this paper to the problem of rollout allocation for classification-based policy iteration in reinforcement learning [START_REF] Lagoudakis | Reinforcement learning as classification: Leveraging modern classifiers[END_REF][START_REF] Dimitrakakis | Rollout sampling approximate policy iteration[END_REF], where the goal is to identify the greedy action (arm) in each of the states (bandit) in a training set.

A Additional Simulations

A.1 Twin Bandits

• Problem 4: n = 3000, M = 4, K = 4. The 4 bandits are identical. The arms have Bernoulli distributions with the following means: (0.5, 0.45, 0.4, 0.3).

In this problem the bandits are identical. Therefore it seems intuitive to allocate the same budget to all the bandits. So we would expect GapE and Unif+UCB-E to have the same performance. In This suggests that dynamic allocation strategies (GapE) might outperform static allocation strategies (Unif+UCB-E). A possible explanation for this result is that GapE is able to adapt to the actual observations. For example, in one bandit, it can happen that the observations from best arm lead to an empirical mean which is bigger than its true mean, while the suboptimal arms have an empirical average lower than their true mean. For this specific realization, the complexity of the task is much smaller than expected. The opposite can happen in the other bandit, thus making it harder than expected. In this case, more pulls should be allocated to the second bandit because its complexity in this particular realization of the problem is bigger than the one of the first bandit. As GapE adapts to the complexity of each realization of the problem, it seems to successfully adapt to the specific "empirical" complexity of the bandits and to obtain a better performance w.r.t. an allocation which statically chooses the number of pulls on the basis of the gaps.

This result shows a potential advantage of dynamic strategies w.r.t. static strategies and it asks for a more thorough investigation.

A.2 Comparing all the algorithms

In the three following problems, we randomly generated the parameters a and b of the Rademacher distributions. In order to test the robustness of the algorithms we design problems where the number of arms goes from 9 to 40.

The results mostly confirm the experiments reported in the main paper. In fact, in all this problems all the gap-based algorithms outperform the Unif+UCB-E algorithms. Furthermore, it can be noticed that taking into account the variance leads to an extra improvement of the performance.

Both in those experiments and those from the main paper, we notice that GapE-V has its best performance when the exploration parameter η is in the interval [2 -4]. This strengthens the claim that the complexity H σ is a good measure of the complexity for any given problem. Moreover this makes the algorithms easy to use as it gives a strong a priori on how to tune the exploration parameter η . Unif + A UCBE Bandit 3: (0.0, 0.45), (0.3, 0.9), (0.55, 0.6)

Unif + A UCBE 1/8 1/4 1/2 1 Unif + UCBE-V 1 2 4 8 Unif + A UCBE-V 1/8 1/4 1/2 1 GapE 1 2 4 8 A GapE 1/8 1/4 1/2 1 GapE-V 1 2 4 8 A GapE-V 1/8 1/4 1/2 1
1 2 4 8 Unif + UCBE-V 4 8 16 32 Unif + A UCBE-V 1/4 1/2 1 2 GapE 1 2 4 8 A GapE 1/32 1/16 1/8 1/4 GapE-V 1/2 1 2 4 A GapE-V 1/16 1/8 1/4 1/2
In Figure 6, we report the performance of all the algorithms in Problem 6. In this problem, we notice that Unif+UCB-E performs worse than Uniform. In bandit 3, the gap between arm 2 and arm 3 is very small (= 0.025). Therefore the complexity H of this bandit is high, H 3 ≃ 3000.

However the variance of arm 3 in bandit 3 is really small, thus making H not representative of the true hardness to solve this bandit. The budget n in this experiment is set to 700 and, as a result, the budget allocated to the bandit 3 in Unif+UCBE is 233. This budget is small with respect to the complexity H, therefore the exploration term of UCB-E will be small and almost no exploration will be done in this bandit. This leads Unif+UCB-E to performance worse than Unif. Notice that when Unif In Figure 7, we report the performance of all the algorithm in Problem 7.

+ UCBE-V 1/2 1 2 4 Unif + A UCBE-V 1/32 1/16 1/8 1/4 GapE 1 2 4 8 A GapE 1/32 1/16 1/8 1/4 GapE-V 1/2 1 2 4 A GapE-V 1/16 1/8 1/4 1/2

B Proof of Theorem 1 Part 1. Upper Bound

Here we prove that -∆ pi (t-1) ≤ -∆ pi + 2bc 1-c a Tpi(t)-1 , where arm i of bandit p is the arm pulled at time t. This means that T pi (t-1) = T pi (t)-1. We consider the following four cases for this proof.

Case 1. i = k * p (t -1) and i = k * p
The pulled arm i is both the best arm and the best empirical arm at time t of bandit p. Here we may write

-∆pi(t -1) = µ p k + p (t-1) (t -1) -µpi(t -1) ≤ µ p k + p (t-1) -µpi + bc a T p k + p (t-1) (t -1) + bc a Tpi(t -1) (a) ≤ µ p k + p (t-1) -µpi + 2bc a Tpi(t -1) ≤ µ pk + p -µpi + 2bc a Tpi(t -1) = -∆pi + 2bc a Tpi(t) -1 ≤ -∆pi + 2bc 1 -c a Tpi(t) -1 .
(a) Since arm i of bandit p is pulled at time t, from (4) we have

-∆pi(t -1) + b a Tpi(t -1) ≥ -∆ p k + p (t-1) (t -1) + b a T p k + p (t-1) (t -1)
.

We also know by definition that ∆ pi (t -1) = ∆ p k + p (t-1) (t -1), which gives us 1) .

a Tpi(t-1) ≥ a T p k + p (t-1) (t-
Case 2. i = k * p (t -1) and i = k * p
The pulled arm i is the best empirical arm at time t, but not the best arm, of bandit p. Here we may write

-∆pi(t -1) = µ p k + p (t-1) (t -1) -µpi(t -1) ≤ µ p k * p (t-1) (t -1) -µ pk * p ≤ µpi -µ pk * p + bc a Tpi(t -1) + bc a T pk * p (t -1) (b) ≤ µpi -µ pk * p + bc a Tpi(t -1) + bc 1 + c 1 -c a Tpi(t -1) = -∆pi + 2bc 1 -c a Tpi(t -1)
.

(b) Since arm i of bandit p is pulled at time t, from (4) we have

-∆pi(t -1) + b a Tpi(t -1) ≥ -∆ pk * p (t -1) + b a T pk * p (t -1) µ p k + p (t-1) (t -1) + b a Tpi(t -1) ≥ µ pk * p (t -1) + b a T pk * p (t -1) µpi(t -1) + b a Tpi(t -1) ≥ µ pk * p (t -1) + b a T pk * p (t -1) µpi + (1 + c)b a Tpi(t -1) ≥ µ pk * p + (1 -c)b a T pk * p (t -1)
.

We also know that by definition µ pk * p > µ pi , which gives us 1+c

1-c a Tpi(t-1) > a T pk * p (t-1) . Case 3. i = k * p (t -1) and i = k * p
The pulled arm i is the best arm, but not the best empirical arm at time t, of bandit p. Here we may write

-∆pi(t -1) = µpi(t -1) -µ p k * p (t-1) (t -1) ≤ µ p k * p (t-1) (t -1) -µ pk * p (t -1) ≤ µ p k * p (t-1) -µ pk * p + bc a T p k * p (t-1) (t -1) + bc a Tpi(t -1) (c) ≤ µ pk + p -µ pk * p + bc a Tpi(t -1) + bc a Tpi(t -1) = -∆pi + 2bc a Tpi(t -1) ≤ -∆pi + 2bc 1 -c a Tpi(t -1)
.

(c) Since arm i of bandit p is pulled at time t, from (4) we have

-∆pi(t -1) + b a Tpi(t -1) ≥ -∆ p k * p (t-1) (t -1) + b a T p k * p (t-1) (t -1)
We also know that by definition -

∆ p k * p (t-1) (t -1) ≥ -∆ pi (t -1), which gives us a Tpi(t-1) ≥ a T p k * p (t-1) (t-1) . Case 4. i = k * p (t -1) and i = k * p
The pulled arm i is neither the best arm nor the best empirical arm at time t of bandit p. Here we may write

-∆pi(t -1) = µpi(t -1) -µ p k * p (t-1) (t -1) ≤ µpi -µ pk * p (t -1) + bc a Tpi(t -1) ≤ µpi -µ pk * p + bc a Tpi(t -1) + bc a T pk * p (t -1) (d) ≤ µpi -µ pk * p + bc a Tpi(t -1) + bc 1 + c 1 -c a Tpi(t -1) = -∆pi + 2bc 1 -c a Tpi(t -1)
.

(d) Since arm i of bandit p is pulled at time t, from (4) we have

-∆pi(t -1) + b a Tpi(t -1) ≥ -∆ pk * p (t -1) + b a T pk * p (t -1) . (6)
If k * p = k * p (t -1), we may write [START_REF] Dimitrakakis | Rollout sampling approximate policy iteration[END_REF] as

µpi(t -1) + b a Tpi(t -1) ≥ µ p k + p (t-1) (t -1) + b a T pk * p (t -1)
.

We also know that by definition µ p k + p (t-1) (t -1) ≥ µ pi (t -1), which gives us

a Tpi(t-1) ≥ a T pk * p (t-1) . Now if k * p = k * p (t -1)
, we may write [START_REF] Dimitrakakis | Rollout sampling approximate policy iteration[END_REF] as

µpi(t -1) + b a Tpi(t -1) ≥ µ pk * p (t -1) + b a T pk * p (t -1) µpi + (1 + c)b a Tpi(t -1) ≥ µ pk * p + (1 -c)b a T pk * p (t -1)
.

We also know that by definition µ pk * p > µ pi , which gives us 1+c

1-c a Tpi(t-1) > a T pk * p (t-1) .

Part 2. Lower Bound

Here we prove that -∆ qj (t -1) ≥ -∆ qj -2 √ 2bc 1-d a Tqj (t) for all bandits q ∈ {1, . . . M } and all arms j ∈ {1, . . . K}, such that the arm j of bandit q is not the one pulled at time t, i.e., (q, j) = (p, i). This means that T qj (t -1) = T qj (t). Similar to the proof for the upper-bound in Part 1, we consider the following four cases here.

Case 1. j = k * q (t -1) and j = k * q
The arm j is both the best arm and the best empirical arm at time t of bandit q. Here we may write

-∆qj (t -1) = µ q k + q (t-1) (t -1) -µqj (t -1) ≥ µ qk + q -µqj -bc a Tqj (t -1) ≥ µ qk + q -µqj -bc a T qk + q (t -1) -bc a Tqj (t -1) (e) ≥ -∆qj - √ 2bc 1 + d 1 -d a Tqj (t) -bc a Tqj (t) ≥ -∆qj - 2 √ 2bc 1 -d a Tqj(t)
.

(e) From the inductive assumption, we have

-∆qj + (1 + d)b a max Tqj (t -1) -1, 1 ≥ -∆ qk + q + (1 -d)b a T qk + q (t -1)
.

We know that by definition -∆ qk

+ q = -∆ qj , which gives us 1+d 1-d a max Tqj (t-1)-1,1 ≥ a T qk + q (t-1)
. Finally, we have

a max Tqj (t -1) -1, 1 = Tqj (t -1) max Tqj(t -1) -1, 1 a Tqj (t -1) ≤ 2 a Tqj (t -1) , (7)
which gives us the result.

Case 2. j = k * q (t -1) and j = k * q The arm j is the best empirical arm at time t, but not the best arm, of bandit q. Here we may write

-∆qj (t -1) = µ q k + q (t-1) (t -1) -µqj (t -1) ≥ µ qk * q (t -1) -µqj (t -1) ≥ µ qk * q -µqj -bc a T qk * q (t -1) -bc a Tqj (t -1) (f) ≥ -∆qj - √ 2bc 1 + d 1 -d a Tqj (t) -bc a Tqj (t) ≥ -∆qj - 2 √ 2bc 1 -d a Tqj(t)
.

(f) From the inductive assumption, we have

-∆qj + (1 + d)b a max Tqj (t -1) -1, 1 ≥ -∆ qk * q + (1 -d)b a T qk * q (t -1)
.

We know that by definition -∆ qk * q ≥ -∆ qj , which gives us 1+d 1-d

a max Tqj (t-1)-1,1 ≥ a T qk * q (t-1)
. The claim follows using Eq. 7.

Case 3. j = k * q (t -1) and j = k * q
The arm j is the best arm, but not the best empirical arm at time t, of bandit q. Here we may write

-∆qj(t -1) = µqj (t -1) -µ q k * q (t-1) (t -1) ≥ µ qk * q -µ q k * q (t-1) -bc a Tqj (t -1) -bc a T q k * q (t-1) (t -1) (g) ≥ ∆ q k * q (t-1) + c 1 -d (∆qj -∆ q k * q (t-1) ) -bc a Tqj(t -1) - √ 2bc 1 + d 1 -d a Tqj (t -1) ≥ c 1 -d ∆qj + (1 - c 1 -d )∆ q k * q (t-1) -bc a Tqj (t) - √ 2bc 1 + d 1 -d a Tqj (t) (h) ≥ -∆qj -bc a Tqj(t) - √ 2bc 1 + d 1 -d a Tqj(t) ≥ -∆qj - 2 √ 2bc 1 -d a Tqj (t)
.

(g) From the inductive assumption, we have

-∆qj + (1 + d)b a max Tqj (t -1) -1, 1 ≥ -∆ q k * q (t-1) + (1 -d)b a T q k * q (t-1) (t -1)
, or equivalently

-bc a T q k * q (t-1) (t -1) ≥ c 1 -d ∆qj -∆ q k * q (t-1) -bc 1 + d 1 -d a max Tqj (t -1) -1, 1 . (8)
The claim follows using Eqs. 8 and 7.

(h) This passage is true when

0 ≤ c 1-d ≤ 1. Case 4. j = k * q (t -1) and j = k * q
The pulled arm j is neither the best arm nor the best empirical arm at time t of bandit q. Here we may write

-∆qj(t-1) = µqj (t-1)-µ q k * q (t-1) (t-1) ≥ µqj -µ q k * q (t-1) -bc a Tqj (t -1) -bc a T q k * q (t-1) (t -1) . (9)
If k * q (t -1) = k * q , we may write [START_REF] Lagoudakis | Reinforcement learning as classification: Leveraging modern classifiers[END_REF] as

-∆qj(t -1) = µqj (t -1) -µ q k * q (t-1) (t -1) ≥ µqj -µ q k * q (t-1) -bc a Tqj(t -1) -bc a T q k * q (t-1) (t -1) ≥ -∆qj -bc a Tqj(t -1)
-bc a T q k * q (t-1) (t -1)

(I) ≥ -∆qj -bc a Tqj(t) - √ 2bc 1 + d 1 -d a Tqj(t) ≥ -∆qj - 2 √ 2bc 1 -d a Tqj (t)
.

(I) From the inductive assumption, we have

-∆qj + (1 + d)b a max Tqj (t -1) -1, 1 ≥ -∆ q k * q (t-1) + (1 -d)b a T q k * q (t-1) (t -1)
.

We know that by definition -∆ q k * q (t-1) = -∆ qk * q > -∆ qj , and thus, 1+d 1) . The claim follows using Eq. 7.

1-d a max Tqj (t-1)-1,1 > a T q k * q (t-1) (t-

Now if k *

q (t -1) = k * q , we may write [START_REF] Lagoudakis | Reinforcement learning as classification: Leveraging modern classifiers[END_REF] as

-∆qj(t -1) = µqj (t -1) -µ q k * q (t-1) (t -1) ≥ µqj -µ q k * q (t-1) -bc a Tqj(t -1) -bc a T q k * q (t-1) (t -1) ≥ -∆qj + ∆ q k * q (t-1) -bc a Tqj(t -1)
-bc a T q k * q (t-1) (t -1)

(J) ≥ (1 - c 1 -d ) -∆qj + ∆ q k * q (t-1) -bc a Tqj (t -1) - √ 2bc 1 + d 1 -d a Tqj(t -1) (K) ≥ -∆qj -bc a Tqj (t) - √ 2bc 1 + d 1 -d a Tqj (t) ≥ -∆qj - 2 √ 2bc 1 -d a Tqj(t)
.

(J) From the inductive assumption, we have

-∆qj + (1 + d)b a max Tqj (t -1) -1, 1 ≥ -∆ q k * q (t-1) + (1 -d)b a T q k * q (t-1) (t -1)
, or equivalently

-bc a T q k * q (t-1) (t -1) ≥ -c 1 -d -∆qj + ∆ q k * q (t-1) -bc 1 + d 1 -d a max Tqj(t -1) -1, 1 . (10)
The claim follows using Eqs. 10 and 7.

(K) This passage is true when 0 ≤ c 1-d ≤ 1.

C The GapE-V Algorithm and Analysis

C.1 The GapE-V algorithm Fig. 8 contains the pseudo-code of the GapE-V algorithm.

Parameters: number of rounds n, exploration parameter a Initialize: T mk (0) = 0, ∆ mk (0) = 0 for any bandit-arm pair

for t =

C.2 Theorem

We first define the complexity of the GapE-V algorithm as

H σ = M m=1 K k=1 σ mk + σ 2 mk + 16 3 b∆ mk 2 ∆ 2 mk . Theorem 3. If GapE-V is run with parameter 0 < a ≤ 8 9 n-2MK H σ
, then it satisfies

ℓ(n) = P ∃m : J m (n) = k * m ≤ 6nM K exp - 9a 64 × 64 in particular for a = 8 9 n-2MK H σ , we have ℓ(n) ≤ 6nM K exp -1 64×8 n-2MK H σ . Proof.
Step 1. Let us consider the following events:

E = ∀m ∈ {1, . . . M }, ∀k ∈ {1, . . . K}, | µ mk T mk (t) -µ mk | < 2ac σ 2 mk T mk (t) + abc 3T mk (t) , E ′ = ∀m ∈ {1, . . . M }, ∀k ∈ {1, . . . K}, | σ mk -σ mk (s)| < b 2ac T mk (t) -1 , E ′′ = ∀m ∈ {1, . . . M }, ∀k ∈ {1, . . . K}, | µ mk (s) -µ mk | < 2ac σ 2 mk (t) T mk (t) + 7abc 3 T mk (t) -1 .
From Bennett inequality, Theorem 10 in [START_REF] Maurer | Empirical bernstein bounds and sample-variance penalization[END_REF], and a union bound, we have P(ξ ∩ ξ ′ ) ≥ 1 -6N K exp(-ac). Moreover, we know that ξ ∩ ξ ′ =⇒ ξ ′′ . Now we would like to prove that on the event ξ ′′ , we find the best arm for all the bandits, i.e., J m (n) = k * m , ∀m ∈ {1, . . . , M }. Since J m (n) is the empirical best arm of bandit m, we should prove that

µ mk T mk (n) ≤ µ mk * m T mk * m (n) , ∀k ∈ {1, . . . , K}. (11)
On the event E, by upper-bounding the LHS and lower-bounding the RHS of Eq. 11, we obtain

µ mk + 2ac σ 2 mk T mk (n) + abc 3T mk (n) ≤ µ mk * m - 2ac σ 2 mk * m T mk * m (n) - abc 3T mk * m (n) , (12)
and thus, it would be enough for us to prove that on the event

E 2ac σ 2 mk T mk (n) + abc 3T mk (n) ≤ ∆ mk 2 , ∀m ∈ {1, . . . , M }, ∀k ∈ {1, . . . , K},
or equivalently,

T mk (n) ≥ 2ac σ mk + σ 2 mk + b∆ mk
Step 2. In this step, we prove the following inequality that shows a dependence between the number of pulls of the arms in the GapE-V algorithm:

∀(m, q) ∈ {1, . . . , M } 2 , ∀(k, j) ∈ {1, . . . , K} 2 , and ∀t ≥ 2M K -∆ mk + (1 + d) 2a σ 2 mk T mk (t) -1 + 8ab 3 max T mk (t) -2, 1 ≥ -∆qj + (1 -d) 2a σ 2 qj Tqj (t) + 6ab 3 Tqj(t) -1 , (14)
where d ∈ [0, 1]. We prove this inequality by induction.

Base step. We know that after the first 2M K rounds of the GapE-V algorithm, all the arms have been pulled twice, i.e., T mk (t) = 2, ∀m ∈ {1, . . . , M }, ∀k ∈ {1, . . . , K}, thus if a ≥ max( 1 8d 2 , 1 2d ), the inequality (2) holds for t = 2M K.

Inductive step. Let us assume that (14) holds at time t -1 and we pull arm i of bandit p at time t, i.e., I(t) = (p, i). So at time t, the inequality (14) trivially holds for every choice of m, q, k, and j, except when (m, k) = (p, i). As a result, in the inductive step, we only need to prove that ∀q ∈ {1, . . . , M }, ∀j ∈ {1, . . . , K}

-∆pi + (1 + d) 2a σ 2 pi Tpi(t) -1 + 8ab 3 max Tpi(t) -2, 1 ≥ -∆qj + (1 -d) 2a σ 2 qj Tqj (t) + 6ab 3 Tqj (t) -1 . ( 15
)
Since arm i of bandit p has been pulled at time t, we have

-∆pi(t -1) + 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ 20 -∆qj(t -1) + 2a σ 2 qj (t -1) Tqj (t -1) + 7ab 3 Tqj(t -1) -1 . (16)
In order to prove (16), we first prove an upper-bound for -∆ pi (t -1) and a lower-bound for -∆ qj (t -1) as follows:

-∆pi(t -1)

≤ -∆pi + 2 √ c 1 - √ c 2a σ 2 pi Tpi(t -1) + 8ab 3 Tpi(t -1) -1 , (17)
-∆qj(t -1) ≥ -∆qj -

16 3 √ c 1 -d 2a σ 2 qj Tqj(t -1) + 6ab 3 Tqj (t -1) -1 .
The inequality (15), and as a result, the inductive step is proved by replacing -∆ pi (t -1) and -∆ qj (t -1) in ( 16) from ( 17) and under the conditions that d ≥ 2c 1-c and d ≥ 16 Step 3. In order to prove (13), we need to find a lower-bound on the number of pulls of the arms at time t = n. Let us assume that arm k of bandit m has been pulled less than

(1 -d) 2 a (σ mk + √ σ 2 mk +4b∆ mk ) 2 2∆ 2 mk , which indicates that -∆ mk + (1 -d) 2a σ 2 mk T mk (n) + 6ab 3T mk (n) ≥ 0.
From this result and ( 14), we have

-∆ qj + (1 + d) 2a σ 2 qj Tqj (n)-1 + 8ab 3Tqj (n)-2 ≥ 0, or equivalently T qj (n) ≤ (1 + d) 2 a (σqj + √ σ 2 qj + 16 3 b∆qj ) 2 2∆ 2 qj + 2, ∀q ∈ {1, . . . , M }
and ∀j ∈ {1, . . . , K}. We also know that q,j T qj (n) = n. From these, we deduce that n -2M K < q,j (1 + d) 2 a

(σqj + √ σ 2 qj + 16 3 b∆qj ) 2 2∆ 2 qj . So if we select a such that n -2M K ≥ q,j (1 + d) 2 a (σqj + √ σ 2 qj + 16 3 b∆qj ) 2 2∆ 2 qj , we contradict the first assump- tion that T mk (n) < (1 -d) 2 a (σ mk + √ σ 2 mk +4b∆ mk ) 2 2∆ 2 mk , which means that T mk (n) ≥ (1 -d) 2 a (σ mk + √ σ 2 mk +4b∆ mk ) 2 2∆ 2 mk
, ∀m ∈ {1, . . . M }, k ∈ {1, . . . K}, which concludes the proof.

Here we report the proof of the inequalities (17).

Part 1. Upper Bound

Here we prove that -

∆ pi (t -1) ≤ -∆ pi + 2 √ c 1- √ c 2a σ 2 pi Tpi(t)-1 + 8ab 3 Tpi(t)-2
, where arm i of bandit p is the arm pulled at time t. This means that T pi (t -1) = T pi (t) -1. We consider the following four cases for this proof.

Case 1. i = k * p (t -1) and i = k * p
The pulled arm i is both the best arm and the best empirical arm at time t of bandit p. Here we may write

-∆pi(t -1) = µ p k + p (t-1) (t -1) -µpi(t -1) ≤ µ p k + p (t-1) -µpi + 2ac σ 2 pi (t -1) Tpi(t -1) + 7abc 3 Tpi(t -1) -1 + 2ac σ 2 p k + p (t -1) T p k + p (t -1) + 7abc 3 T p k + p (t -1) -1 (a) ≤ µ p k + p (t-1) -µpi + 2 √ c 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≤ µ pk + p -µpi + 2 √ c 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 = -∆pi + 2 √ c 2a σ 2 pi (t -1) Tpi(t) -1 + 7ab 3 Tpi(t) -2 .
Replacing the empirical standard deviation with the true one and c < 1 36 , we obtain the upper-bound

-∆pi(t -1) ≤ -∆pi + 2 √ c 2a σ 2 pi Tpi(t) -1 + ab(7 + 6 √ c) 3 Tpi(t) -2 ≤ -∆pi + 2 √ c 1 - √ c 2a σ 2 pi Tpi(t) -1 + 8ab 3 Tpi(t) -2 .
(a) Since arm i of bandit p is pulled at time t, from (4) we have

-∆pi(t -1) + 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ -∆ p k + p (t-1) (t -1) + 2a σ 2 p k + p (t-1) (t -1) T p k + p (t-1) (t -1) + 7ab 3 T p k + p (t-1) (t -1) -1)
.

We also know by definition that -∆ pi (t -1) = -∆ p k + p (t-1) (t -1), which gives us

2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ 2a σ 2 p k + p (t-1) (t -1) T p k + p (t-1) (t -1) + 7ab 3 T p k + p (t-1) (t -1) -1) . Case 2. i = k * p (t -1) and i = k * p
The pulled arm i is the best empirical arm at time t, but not the best arm, of bandit p. Here we may write

-∆pi(t -1) = µ p k * p (t-1) (t -1) -µpi(t -1) ≤ µ p k * p (t-1) (t -1) -µ pk * p ≤ µpi -µ pk * p + 2ac σ 2 pi (t -1) Tpi(t -1) + 7abc 3 Tpi(t -1) -1 + 2ac σ 2 pk * p (t -1) T pk * p (t -1) + 7abc 3 T pk * p (t -1) -1 (b) ≤ µpi -µ pk * p + 2ac σ 2 pi (t -1) Tpi(t -1) + 7ab √ c 3 Tpi(t -1) -1 + 1 + √ c 1 - √ c √ c 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≤ -∆pi + 2 √ c 1 - √ c 2a σ 2 pi (t -1) Tpi(t) -1 + 7ab 3 Tpi(t) -2
Replacing the empirical standard deviation with the true one and c < 1 36 , we obtain the upper-bound

-∆pi(t -1) ≤ -∆pi + 2 √ c 1 - √ c 2a σ 2 pi Tpi(t) -1 + 8ab 3 Tpi(t) -2 .
(b) Since arm i of bandit p is pulled at time t, from (16) we have

-∆pi(t -1) + 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ -∆ pk * p (t -1) + 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 µ p k + p (t-1) (t -1) + 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ µ pk * p (t -1) + 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 µpi(t -1) + 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ µ pk * p (t -1) + 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 µpi + (1 + √ c) 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ µ pk * p + (1 - √ c) 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 .
We also know that by definition µ pk * p > µ pi , which gives us We also know that by definition µ pk * p ≥ µ pi , which gives us for all bandits q ∈ {1, . . . M } and all arms j ∈ {1, . . . K}, such that the arm j of bandit q is not the one pulled at time t, i.e., (q, j) = (p, i). This means that T qj (t -1) = T qj (t). Similar to the proof for the upper-bound in Part 1, we consider the following four cases here.

1 + √ c 1 - √ c 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 . Case 3. i = k * p (t -
Case 1. j = k * q (t 1) and j = k * q The arm j is both the best arm and the best empirical arm at time t of bandit q. Here we may write -∆qj(t -1) = µ q k + q (t-1) (t -1) -µqj (t -1) ≥ µ qk + q -µqj - We know that by definition -∆ qk + q = -∆ qj , which gives us

Figure 1 :

 1 Figure 1: The pseudo-code of the gap-based Exploration (GapE) algorithm.

Theorem 1 . 4 9

 14 If we run GapE with parameter 0 < a ≤

•

  Problem 1. n = 700, M = 2, K = 4. The arms have Bernoulli distribution with parameters: bandit 1 = (0.5, 0.45, 0.4, 0.3), bandit 2 = (0.5, 0.3, 0.2, 0.1). • Problem 2. n = 1000, M = 2, K = 4. The arms have Rademacher distribution with parameters (x, y): bandit 1 = {(0, 1.0), (0.45, 0.45), (0.25, 0.65), (0, 0.9)} and in bandit 2 = {(0.4, 0.6), (0.45, 0.45), (0.35, 0.55), (0.25, 0.65)}. • Problem 3. n = 1400, M = 4, K = 4. The arms have Rademacher distribution with parameters (x, y): bandit 1 = {(0.4, 0.85), (0.25, 0.9), (0.2, 0.95), (0.1, 1.0)}, bandit 2 = {(0.0, 1.0), (0.0, 0.8), (0.0, 0.5), (0.3, 0.4)}, bandit 3 = {(0.4, 1.0), (0.0, 0.5), (0.1, 0.5), (0.2, 0.5)}, and bandit 4 = {(0.0, 1.0), (0.0, 0.8), (0.45, 0.45), (0.45, 0.45)}.

Figure 3 :

 3 Figure 3: Performance of the algorithms in Problem 3.

Figure A. 1 ,Figure 4 :

 14 Figure 4: Problem 4: The benefit of adaptive allocation over the bandits in the twin bandits problem.

Figure 5 :

 5 Figure 5: Performances of all the algorithms in Problem 5.

Figure 6 :• 6 )

 66 Figure 6: Performances of all the algorithms in Problem 6.

Figure 7 : 9 ) 9 ) 4 ) 8 )

 79948 Figure 7: Performances of all the algorithms in Problem 7.

Figure 8 :

 8 Figure 8: The pseudo-code of the GapE-V algorithm.

  , . . . , M }, ∀k ∈ {1, . . . , K}.

3 √ c 1 -

 31 d and c ≤ 1 36 . These two conditions are satisfied for d = 1/2 and c = (3/64) 2 .

2ac σ 2 qj 1 ≥ 3 2 qj

 2132 Tqj(t -1) -abc 3 Tqj (t -1)µ qk + q -µqj -Tqj (t -1) -1(e) From the inductive assumption, we have-∆qj + (1 + d) 2a σ + p (t -1) -1.

Remark 1 (Analysis of the bound). If

  the time horizon n is known in advance, it would be possible to set the exploration parameter a as a linear function of n, and as a result, the probability of error of GapE decreases exponentially with the time horizon. The other interesting aspect of the bound is the complexity term H appearing in the optimal value of the exploration parameter a (i.e., a = 4

	4 9	n-MK H	, we have ℓ(n) ≤ 2M Kn exp(-1 144	n-MK H	).
					9	n-K H ).
	If we denote by

  Figure 2: (left) Problem 1: Comparison between GapE, adaptive GapE, and the uniform strategies. (right) Problem 2: Comparison between GapE, GapE-V, and adaptive GapE-V algorithms.Adaptive GapE and GapE-V. A drawback of GapE and GapE-V is that the exploration parameter a should be tuned according to the complexities H and H σ of the multi-bandit problem, which are rarely known in advance. A straightforward solution to this issue is to move to an adaptive version of these algorithms by substituting H and H σ with suitable estimates H and H σ . At each step t of the adaptive GapE and GapE-V algorithms, we estimate these complexities as

	Maximum probability of error	0.15 0.20 0.25 0.30	Uniform + UCBE		GapE	Adapt GapE	Maximum probability of error	0.15 0.20 0.25	GapE		GapE-V	Adapt GapE-V
			4	8 16 32	2	4	8 16	1/8 1/4 1/2 1			8 16 32 64	2	4	8 16	1/4 1/2 1	2
					Parameter η					Parameter η

  1, 2, . . . , n do Compute B mk (t) = -∆ mk (t -1) + Draw I(t) ∈ arg max m,k B mk (t) Observe X mk (T mk (t -1) + 1) ∼ ν mk Update ∆ mk (t) and T mk (t) = T mk (t -1) + 1 end for Return Jm(n) ∈ arg max k∈{1,...,K} µ mk (n), ∀m ∈ {1 . . . M }

	2a σ 2 mk (t-1) T mk (t-1) +	7ab 3 T mk (t-1)-1

  Replacing the empirical standard deviation with the true one and c < 1 36 , we obtain the upper-bound Since arm i of bandit p is pulled at time t, from (16) we haveThe pulled arm i is neither the best arm nor the best empirical arm at time t of bandit p. Here we may write-∆pi(t -1) = µpi(t -1) -µ p k * p (t-1) (t -1) ≤ µpi -µ pk * p (t -1) +Replacing the empirical standard deviation with the true one and c < 1 36 , we obtain the upper-boundWe also know that by definition µ p k + p (t-1) (t -1) ≥ µ pi (t -1), which gives us

	≤ µ p k * p (t-1) -µ pk * p + (c) ≤ µ pk + p -µ pk * p + 2ac σ 2 2ac σ 2 pi (t -1) Tpi(t -1) pi (t -1) Tpi(t -1) + 3 Tpi(t -1) -1 + 7abc 3 Tpi(t -1) -1 7ab √ c + = -∆pi + 2 √ c 2a σ 2 pi (t -1) Tpi(t) -1 + 7ab 3 Tpi(t) -2 -∆pi(t -1) ≤ -∆pi + 2 √ c 2a σ 2 pi Tpi(t) -1 + (7 + 6 √ c)ab 3 Tpi(t) -2 ≤ -∆pi + -∆pi(t -1) + 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ -∆ p k * p (t-1) (t -1) + 2a σ 2 p k * + 2ac σ 2 + √ c 2 √ c 2ac σ 2 p k * p (t-1) (t -1) T p k * p (t-1) (t -1) 2a σ 2 pi (t -1) Tpi(t -1) + 3 Tpi(t -1) -1 + 7abc 3 T p k * 7ab 1 -√ c 2a σ 2 pi Tpi(t) -1 + 8ab 3 Tpi(t) -2 . 7ab pi (t -1) Tpi(t -1) + 7abc 3 Tpi(t -1) -1 ≤ µpi -µ pk * p + 2ac σ 2 pi (t -1) Tpi(t -1) + 7abc 3 Tpi(t -1) -1 + 2ac σ 2 pk * p (t -1) T pk * p (t -1) + 7abc 3 T pk * p (t -1) -1 (d) ≤ µpi -µ pk * p + 2ac σ 2 pi (t -1) Tpi(t -1) + 7ab √ c 3(Tpi(t -1) -1) + 1 + √ c 1 -√ c √ c 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 = -∆pi + 2 √ c 1 -√ c 2a σ 2 pi (t -1) Tpi(t) -1 + 7ab 3 Tpi(t) -2 -∆pi(t -1) ≤ -∆pi + 2 √ c 1 -√ c 2a σ 2 pi Tpi(t) -1 + 8ab 3 Tpi(t) -2 . -∆pi(t-1)+ 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ -∆ pk * p (t-1)+ 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 . (18) If k * p = k * p (t -1), we may write (18) as µpi(t-1)+ 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ µ p k + p (t-1) (t-1)+ 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 . 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ 2a σ 2 pk * p (t -1) T pk * p (t -1) + 7ab 3 T pk * p (t -1) -1 3 T p k 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ 2a σ 2 p k * p (t-1) (t -1) T p k * p (t-1) (t -1) + 7ab 3 T p k * µpi + (1 + √ c) 2a σ 2 pi (t -1) Tpi(t -1) + 7ab 3 Tpi(t -1) -1 ≥ µ pk * p + (1 -√ c) 2a σ 2 pk * p (t -1) T pk * p (t -1) 7ab + 3 T pk *
	µpi(t -1) +	2a σ 2 pi (t -1) Tpi(t -1)	+	7ab 3 Tpi(t -1) -1	≥ µ pk * p (t -1) +	2a σ 2 pk * p T pk * p (t -1) (t -1)	+	7ab p (t -1) -1 3 T pk *

1) and i = k * p

The pulled arm i is the best arm, but not the best empirical arm at time t, of bandit p. Here we may write

-∆pi(t -1) = µpi(t -1) -µ p k * p (t-1) (t -1) ≤ µ p k * p (t-1) (t -1) -µ pk * p (t -1) p (t-1) (t -1) -1 (c) p (t-1) (t -1) T p k * p (t-1) (t -1) * p (t-1) (t -1)

-1)

.

We also know by definition that -

∆ p k * p (t-1) (t -1) ≥ -∆ pi (t -

1), which gives us p (t-1) (t -1) -1) . Case 4. i = k * p (t -1) and i = k * p (d) Since arm i of bandit p is pulled at time t, from (16) we have . Now if k * p = k * p (t -1), we may write (18) as p (t -1) -1 .

  Here we prove that -∆ qj (t -1) ≥ -∆ qj -16

	1 + 1 -	√ c √ c	2a σ 2 pi (t -1) Tpi(t -1)	+	7ab 3 Tpi(t -1) -1	≥	2a σ 2 pk * p T pk * p (t -1) (t -1)	+	7ab p (t -1) -1 3 T pk *	.
	Part 2. Lower Bound
					3	a 1-d √ c		2a σ 2 qj (t-1) Tqj (t-1) +	6ab 3 Tqj (t-1)-1

Acknowledgments Experiments presented in this paper were carried out using the Grid'5000 experimental testbed (https://www.grid5000.fr). This work was supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council and FEDER through the "contrat de projets état region 2007-2013", French National Research Agency (ANR) under project LAMPADA n • ANR-09-EMER-007, European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 231495, and PASCAL2 European Network of Excellence.

which gives us the result.

Case 2. j = k * q (t -1) and j = k * q The arm j is the best empirical arm at time t, but not the best arm, of bandit q. Here we may write -∆qj(t -1) = µ q k + q (t-1) (t -1) -µqj (t -1) ≥ µ qk * q (t -1) -µqj (t -1)

(f) From the inductive assumption, we have

We know that by definition -∆ qk * q ≥ -∆ qj , which gives us

The claim follows using Eq. 19.

Case 3. j = k * q (t -1) and j = k * q The arm j is the best arm, but not the best empirical arm at time t, of bandit q. Here we may write

(g) From the inductive assumption, we have

.

The claim follows from Eqs. 20 and 19.

(h) This passage is true when 0

Case 4. j = k * q (t -1) and j = k * q

The pulled arm j is neither the best arm nor the best empirical arm at time t of bandit q. Here we may write

≥ µqj -µ q k * q (t-1) -

If k * q (t -1) = k * q , we may write (21) as

(I) From the inductive assumption, we have

We know that by definition -∆ q k * q (t-1) = -∆ qk * q > -∆ qj , and thus

The claim follows using Eq. 19.

Now if k * q (t -1) = k * q , we may write (21) as

(J) From the inductive assumption, we have The claim follows from Eqs. 22 and 19.

(K) This passage is true when 0 ≤ √ c 1-d ≤ 1.


Nitishal Chungoora
email: n.chungoora@lboro.ac.uk

O J Canciglieri
email: osiris.canciglieri@pucpr.br

R I M Young
email: r.i.young@lboro.ac.uk

Robert Ian Marr

Towards Expressive Ontology-Based Approaches to Manufacturing Knowledge Representation and Sharing

Keywords: design and manufacture, lightweight ontology, heavyweight ontology, semantics, knowledge sharing, injection moulding

Introduction

Ontological approaches are nowadays increasingly being applied to support the formal capture and sharing of the meaning and intent (i.e. semantics) of design and manufacture concepts. For a particular domain, the representation of the required semantics is held in an ontology and the Knowledge Base (KB) deployed from the ontology is used to populate knowledge which should consistently derive from the semantic structures within the ontology. Represented knowledge in a KB provides useful support for key engineering decisions, for example, the ways in which a designer's intent in the design domain could affect the selection of manufacturing processes in the manufacturing domain. Thus, expressive manufacturing knowledge refers to populated knowledge in a KB, based on the unambiguous definition of semantics structures which carry enriched formal meaning.

Unfortunately at present, the seamless exchange of design and manufacture semantics for knowledge sharing is still not achievable as a result of domain models that do not carry sufficiently-expressive semantics. This is because there are currently several ontological formalisms, of varying expressiveness [START_REF] Ray | NIST's semantic approach to standards and interoperability[END_REF]) and system interaction capabilities, which do not all necessarily address the knowledge capture and sharing needs in product design and manufacture. Consequently, there exists an ongoing requirement to refine the understanding of the level of logical expressiveness capable of semantically structuring the meaning of product lifecycle concepts [START_REF] Canciglieri | Information mapping across injection moulding design and manufacture domains[END_REF][START_REF] Chungoora | A framework to support semantic interoperability in product design and manufacture[END_REF]. This paper investigates the capture and intra-system sharing of ontology-based knowledge using the basis of two broad categories of ontological formalisms, notably "lightweight" and "heavyweight" approaches [START_REF] Gómez-Pérez | Ontological engineering: with examples from the areas of knowledge management, ecommerce and the semantic web[END_REF], further explained in the next section. By understanding the implications of each approach applied to concepts in injection moulding design and manufacture, the paper contributes to a clarification of (1) the ways of expressively capturing domain semantics and (2) the mechanisms for sharing semantics across intra-system domains to support engineering decisions.

A case study has been devised in order to expose the relative strengths and weaknesses between a lightweight ontological model and a version of the model formalised using a heavyweight formalism. It has been shown that the existence of an axiom layer in the heavyweight model is paramount to capturing rigorous semantics and for prompting the potential for knowledge sharing. Moreover, certain characteristics of the lightweight model have proved to be pertinent to aiding intrasystem knowledge sharing. Following this case study, a suitable ontological direction is then identified, as a benchmark for design and manufacture domains that intend to exploit expressive semantics alongside knowledge inference support.

A categorisation based on expressiveness

The requirements and preferences adopted by different communities have led to the development and utilisation of various ontological formalisms. Ontological formalisms are essentially formal languages that support the construction of ontologybased models and the encoding of the subject matter within these models. Some commonly-occurring formalisms are illustrated in Figure 1, featuring the Unified Modelling Language (UML) (UML, 2009), Frame-based languages [START_REF] Wang | Frames and OWL side by side[END_REF] and Description Logic-based languages [START_REF] Baader | Description logics[END_REF] among others. To distinguish families of ontological formalisms, the ontology community has introduced a categorisation based on the expressiveness of the subject matter contained within ontologies, and enabled via the use of ontological formalisms.

[Figure 1 to be inserted about here] This categorisation involves the notions of "lightweight" and "heavyweight" ontological approaches, which primarily differ in the degree of formality and granularity with which they can represent the same knowledge [START_REF] Gómez-Pérez | Ontological engineering: with examples from the areas of knowledge management, ecommerce and the semantic web[END_REF][START_REF] Casely-Hayford | Environments, methodologies and languages for supporting users in building a chemical ontology[END_REF]. Lightweight models predominantly consist of a taxonomy of concepts, with simple relationships established among these concepts and very basic constraints over the meaning of the ontological terms. On the other hand, heavyweight models, in addition to having the lightweight structures, are accompanied by a rich set of formal axioms that constrain the interpretation of ontological terms. In Figure 1 In the field of manufacturing engineering research, both lightweight and heavyweight methods have been utilised for the formalisation of domain models (ISO 18629, 2005;[START_REF] Patil | Ontology-based exchange of product data semantics[END_REF][START_REF] Kim | Ontology-based assembly design and information sharing for collaborative product development[END_REF][START_REF] Lin | A manufacturing engineering ontology model on the semantic web for inter-enterprise collaboration[END_REF]. It is clear, from the extent of the exploited lightweight and heavyweight ontological approaches, that there is currently no discernable consensus on a preferred ontological direction. This is largely because of the ongoing need to establish the suitability of these approaches to meet the semantic and knowledge sharing requirements of design and manufacture. Hence, the aim of assessing the benefits and limitations of both approaches becomes a key step towards identifying the essential elements to progress towards expressive ontology-based approaches.

Multi-domain knowledge representation and sharing using lightweight and heavyweight approaches

The methodology to achieve the previously-mentioned aim is identified in Figure 2.

Emphasis is placed on multi-domain knowledge representation and intra-system knowledge sharing in the context of injection moulding. The methodology involves considering a simple consumer product concept, namely a rotational container (C), as shown in Figure 2. Using both lightweight UML and heavyweight Frames with a First Order Logic constraint language, the product representation is first to be captured in the mouldability domain (D), by using the semantic structures supported in both methods.

[Figure 2 to be inserted about here] Then, populated knowledge from the mouldability domain is to be shared with the mould design domain (E) for obtaining a representation of the mould product model knowledge. Following this stage, the mould product model knowledge from the mould design domain is to be shared with the mould manufacturing domain (F) to capture the manufacturing representation knowledge for the mould. The sharing process between domains is to be achieved by using the adequate translation / mapping mechanisms accommodated in both ontology-based approaches.

A number of reasons justify the selection of UML and Frames with a First Order Logic constraint language, as the preferred lightweight and heavyweight ontological formalisms respectively. In the first place, a range of lightweight information models has exploited UML for multi-viewpoint modelling applied to design realisation stages [START_REF] Tam | An object-based process planning and scheduling model in a product design environment[END_REF][START_REF] Kugathasan | Multiple viewpoint models for automotive body-in-white design[END_REF][START_REF] Canciglieri | Information mapping across injection moulding design and manufacture domains[END_REF]. Thus, by performing an assessment of UML against the exposed methodology, it becomes possible to provide an appreciation of one extensively-used lightweight formalism.

Frames with a First Order Logic constraint language as heavyweight formalism presents characteristics that overlap with a range of other heavyweight formalisms. This explains its suitability for this investigation. For example, the formalism bears several structural similarities to Description Logic-based languages, which have witnessed unprecedented relevance in product design ontologies [START_REF] Aim | Advanced and Innovative Models and Tools for the development of Semantic-based systems for Handling, Acquiring and Processing knowledge Embedded in multidimensional digital objects[END_REF][START_REF] Lukibanov | Use of ontologies to support design activities at DaimlerChrysler[END_REF]. Furthermore, the chosen heavyweight formalism holds key commonalities with the Common Logic Interchange Format (CLIF) (ISO/IEC 24707, 2007), which has been used to encode the Process Specification Language (PSL) ontology (ISO 18629, 2005).

Overview of case study

Figure 3 identifies the case study scenario for the analysis of the selected lightweight and heavyweight ontological approaches, to support multi-domain knowledge representation and sharing. This scenario provides a more detailed view on the use of the methodology portrayed in Figure 2. Based on Figure 3, the study concentrates on the analysis of a UML multi-domain injection moulding model against a similar model formalised in Frames with a First Order Logic constraint language. A detailed understanding behind the UML development of the multiple viewpoint domains can be found in an earlier manuscript [START_REF] Canciglieri | Information sharing in multi-viewpoint injection moulding design and manufacturing[END_REF].

For implementation purposes, the Knowledge Engineering Methodology, prescribed by Noy and McGuinness (2001), has been adopted during ontology development. An appropriate UML tool has been utilised to formalise the lightweight UML model. Furthermore, the formalism Frames with the Protégé Axiom Language (PAL), as First Order Logic constraint language, has been used in the Protégé Frames 3.4 ontology editor (Protégé, 2009) for representing the heavyweight model.

[Figure 3 to be inserted about here] An important facet of the case study is related to the formal representation of the semantics of multi-domain injection moulding and the corresponding populated knowledge. This involves:

•

The explicit representation of the mouldability, mould design and mould manufacturing domain semantics. • Representing knowledge that is either common across domains or needs to be translated / mapped to a different domain.

• Capturing logical pre-conditions that exist in one domain which can drive the translation / mapping of the appropriate knowledge.

The representation of the rotational product in the mouldability domain is partly comprised of internal and external profiles (G), that pertain to primary and transition features that form the wall of the product. The dimensional knowledge captured in these profiles is to be shared with the mould design domain (H). It is to be noted that emphasis is laid on the semantics of the internal profile of the rotational product, which are then used to drive the rotational core insert representation knowledge (I) in the mould design domain. In this case the mould design domain has been referred to as the "rotational core design domain" to clarify that the intended representation is for the rotational core component of the mould.

The knowledge shared from the mouldability domain to the rotational core design domain, is then used to disseminate additional knowledge to the rotational core manufacturing domain (J) (i.e. the mould manufacturing domain). The rotational core manufacturing domain represents the semantics of the rotational core insert from a machining viewpoint, for example, in terms of the types of machining features that the rotational core insert holds in the manufacturing domain (K).

Lightweight ontology-based model

The lightweight UML model has been previously documented [START_REF] Canciglieri | Information mapping across injection moulding design and manufacture domains[END_REF] and therefore, this section concentrates on the most relevant strengths and weaknesses carried by the lightweight UML approach. The identification, retrieval and sharing of populated knowledge from the mouldability domain to the rotational core design domain and from the design domain to the manufacturing domain is formalised through UML activity diagrams (N). These activity diagrams enable the user to create a set of instructions on how to translate the required attributes and knowledge from one domain to another.

[Figure 4 to be inserted about here]

Strengths and weaknesses

• UML class diagrams provide a convenient way to design ontologies, as they support a fairly rich set of graphical constructs. This can be a particularly useful means of reusing platform-independent ontologies prior to their implementation in the required ontology applications. • UML activity diagrams allow translation / mapping knowledge to be captured and aid, at a system development level, to automatically perform information sharing procedures from one domain to another. For example, it is possible to trigger the automatic assertion of attributes and dimensional knowledge from the mouldability domain to the rotational core design domain. However, in the experiment, because UML activity diagrams depend on UML class diagrams, this implies that translation procedures are dependent on the terms carried by domain concepts rather than the semantics of these concepts.

• Although a low level of computational interpretation can be captured in UML classes purely associated to variations in class names, it is not fully possible to embed pre-conditional knowledge and intent. For example, in Figure 4, the class name "Rot_Wall_Par_Part_Line" (O) in the mouldability domain is used to imply a rotational primary feature which is positioned parallel to a parting line configuration (P). However, the condition for parallelism to a parting line cannot be formally stated in UML.

Heavyweight ontology-based model

The heavyweight ontological exploration using Frames with the Protégé Axiom Language (PAL) differs both in the degree of formality and granularity when compared to the lightweight approach. Figure 5 depicts the heavyweight ontological structures used to model multi-domain semantics and to identify sharable knowledge between domains.

[Figure 5 to be inserted about here]

In the heavyweight model, ontological structures consist of taxonomies of classes, relations and functions, accompanied by a rigorous logic-based axiom layer as shown in Figure 5 (Q). This layer is responsible for supporting the meaning of concepts in computational form. The axiom layer is built on top of the basic ontological structures and consists of integrity constraints and mapping rules, which are both written in PAL. This constraint language accommodates first order semantics, thereby providing considerable flexibility in specifying the conditions for semantic conformance and knowledge sharing. Integrity constraints are logical restrictions that help ensure the semantic integrity within the injection moulding domains identified in Figure 3, while mapping rules are logical conditions that help identify potential knowledge that could be shared from one domain to the other. regroups reusable behaviours across domains, such as the notions of "Point", "Axis", "Length Measure" and "Dimensional Tolerance" among others.

An instance of the class "Rotational Mouldability Product" (V) is shown in the instance browser. Captured semantics for one specific instance of "Rotational Mouldability Product", named "Product 1 -Rotational Container" (W), can be identified in Figure 6. These semantic structures involve, for example, the list of point profiles aggregated under the relations "holds_internal_profile" (X) and "holds_external_profile" (Y) and the list of primary and transition features aggregated under the binary relation "holds_feature" (Z).

[Figure 6 to be inserted about here]

Integrity constraints

From an ontology formalisation viewpoint, PAL is used for model-checking. This implies that integrity constraints act as semantic prescriptions to ensure that populated knowledge in the KB conforms to the semantics expressed in the heavyweight model.

To verify whether asserted knowledge violates or conforms to semantics, integrity constraints can be processed and a number of results are retained in the event that these constraints have been infringed. In other words, integrity constraints contribute to the semantic integrity and enrichment of the KB.

In order to account for the semantic needs of the heavyweight model, integrity constraints have been written for the multiple domains under consideration. Over 30 integrity constraints including both simple and complex ones, have been modelled for all three domains. The expression listed next gives an example of a simple integrity constraint in the mouldability domain to ensure that instances of the class "Rotational (defrange ?product :FRAME 'Rotational Mouldability Product') (forall ?product (= (number-of-slot-values holds_axis ?product) 1))

If, for example, an instance of "Rotational Mouldability Product" is asserted as having more than one axis in the KB, then an execution of the PAL constraint would show that this instance is violating the fundamental semantics that a rotational mouldability product must always hold one axis. Figure 7 illustrates the result of querying an integrity constraint based on an incorrectly-populated knowledge element. The instance "Product 1 -Rotational Container" (W) is shown to be violating the integrity constraint at query time as a result of an additional "Probe Inconsistent Axis" (A1) having been assigned. The identification of inconsistent knowledge, like the one shown in Figure 7, provides a useful way of prompting the user to rectify the incorrect assertions.

[Figure 7 to be inserted about here] An example of a more complex integrity constraint in the mouldability domain is shown in Figure 8. The axiom captures the relevant logical pre-conditions to ensure the correct specification of parting line features (see Figure 4 (P)), by using the appropriate formalised statement (B1). In the expression, the accurate definition of a "Parting Line Feature" (C1) is captured based on the known existence of some defined "Primary Feature" (D1). A similar understanding has been followed for the Once the mouldability domain has been modelled with its required instances populated, integrity constraints for that specific domain are processed to ensure that the asserted knowledge concords with semantics. If a constraint is violated this implies that the query response, obtained from running the constraint, points to inconsistent knowledge. The consequence of a visible inconsistency prompts the user to modify and/or assert correct knowledge. The process of checking integrity constraints is iterated until there are no violated conditions, thereby ensuring the completeness of domain semantics.

[Figure 8 to be inserted about here]

Mapping rules

The next stage following model-checking of the mouldability domain involves the execution of mapping rules. A first set of mapping rules is run with the intention of identifying sharable knowledge that needs to be communicated from the mouldability domain to the rotational core design domain. Mapping rules are written in the same way as integrity constraints and are very similar in terms of complexity. The main difference between the two lies in the specification of existential quantifiers (i.e. the First Order Logic directive called "exist") in the consequent of the mapping rules. An example of a mapping rule is informally quoted next, together with an exemplified understanding of the implications of the mapping rule as shown in Figure 9.

"Rotational core perpendicular straight line(s) must be specified" informally says that: If a parallel parting line primary feature (e.g. (E1)) of a rotational mouldability product has two points ?p1 and ?p2 that describe the internal profile of the product, such that only the z coordinates of the two points are different while the x and y coordinates are the same, then there should exist a core perpendicular straight line (e.g. (F1)) that meets the two points in the rotational core design domain.

[Figure 9 to be inserted about here]

In simpler words, logical semantic conditions arising in the mouldability domain imply the existence of similar, modified or different knowledge elements in the rotational core design domain. After sharable knowledge is processed on running the first set of mapping rules, the user then manually creates the identified knowledge for the rotational core design domain. Once this stage is performed, integrity constraints for the rotational core design domain are executed to ensure the consistency of the new knowledge input.

The next stage of knowledge sharing involves discovering mappings from the rotational core design domain to the rotational core manufacturing domain. An informally-expressed example of a mapping rule in this case is listed next, together with its corresponding explanatory diagram in Figure 10. Results from similar mapping rules help identify new knowledge required for the rotational core manufacturing domain based on the knowledge elements found in the rotational core design domain. The user asserts the identified sharable knowledge in the rotational core manufacturing domain and ascertains that the knowledge input is consistent with domain semantics by executing the integrity constraints for the manufacturing domain.

Figure 11 illustrates the results of processing two mapping rules for each domain-to-domain sharable knowledge identification process. Overall, 18 complex mapping rules have been explored in the heavyweight experiment to obtain, from the product representation in the mouldability domain, the accurate representation of the rotational core insert in both the mould design and manufacturing domains.

In the sample results in Figure 11, it can be seen that sharable knowledge has been inferred and consists of (1) hole features from the mouldability domain that can be directly shared with the rotational core design domain (I1), (2) product geometryrelated semantics (J1) from the mouldability domain which are required in the rotational core design domain and (3) geometry-related semantics (K1) of the design rotational core insert that are sharable with the rotational core manufacturing domain, in order to obtain a machining feature definition for the rotational core insert.

[Figure 11 to be inserted about here]

Strengths and weaknesses

•

The fundamental, primarily lightweight, semantic structures of domain concepts can be readily modelled through the specification of classes and their taxonomies, accompanied by binary relations that hold between classes, and functions which act like attributes of classes.

•

The presence of an axiom layer provides the capability to support the definition of rigorous semantic structures, which complement the lightweight structures. The axiom layer accommodates a set of integrity constraints and mapping rules written in the expressive and relatively flexible Protégé Axiom Language (PAL), which is First Order Logic-based.

•

The axiom layer offers the ability to formally capture logical pre-conditions.

Although the integrity constraints that model these pre-conditions deserve to be carefully written and may result in an impedance in processing time as a result of complexity, yet it is seen that such constraints explicitly enable the subject matter of the heavyweight model to be represented.

•

In the heavyweight approach, the use of integrity constraints has remained rigid. In other words, integrity constraints can only be specified to dictate the compulsory conformance of populated knowledge in the KB. In certain situations, it could be necessary to also support optional conformance of knowledge which is left for the user to decide, as opposed to relying on the system. This would require the ability to specify integrity constraints of lesser "strength", while remaining traceable by the user.

• It is possible via the use of mapping rules to make inferences for aiding the identification of sharable knowledge, that needs to be mapped from one domain to another. However, in the chosen heavyweight approach, it has not been possible to automatically perform the assertion of new knowledge as this has relied on manual input, articulated through the processing of mapping rules. This drawback is due to the fact that PAL is essentially used for writing • Furthermore, the heavyweight ontology development process is absent of the use of suitable ontology design schematics, which would serve as platformindependent model. This is because the ontology has been directly constructed within the implementation environment. Hence, this suggests that the heavyweight model is platform-dependent and, therefore, makes the process of interoperability between different applications a potential issue.

Discussions

The case study has documented a set of strengths and weaknesses of lightweight and heavyweight ontological approaches, applied to multi-domain knowledge representation and sharing in injection moulding design and manufacture. One of the primary differences between the two approaches lies in the ability for the heavyweight model to accommodate an axiom layer supported by First Order Logic semantics. The axiom layer helps express the behaviours and conditions that prescribe the integrity of populated domain knowledge in KBs.

In UML 2, the Object Constraint Language (OCL) can be used to specify invariant conditions that must hold for the system being modelled (OCL, 2006). This implies that in a similar way to PAL, OCL would enable the representation of certain logic-based conditions for ensuring that accurate knowledge is populated. However, OCL does not possess the expressive power of First Order Logic. For this reason, heavyweight ontological approaches are favoured from the perspective of semantic expressiveness and interoperability. Nevertheless, lightweight UML models can still be effective in collaborative settings, provided the concepts defined in these models are agreed and understood.

From the perspective of automating knowledge assertion processes, UML activity diagrams hold a stronger prospect of making the translation / mapping of knowledge an easier task compared to mapping rules. Thus, it can be extrapolated that by interfacing UML activity diagram mechanisms with heavyweight models, it could be possible to achieve an improved method for automatically asserting new knowledge. In the Protégé ontology environment, the Jess rule engine reasoner (Protégé, 2009) is able to interact directly with populated knowledge and could, therefore, potentially be exploited to perform the automatic assertion of inferred knowledge from PAL mapping rules.

Additional opportunities exist for extending the scope of the heavyweight ontology of injection moulding design and manufacture. For instance, the mould manufacturing domain could be broadened to include manufacturing process sequencing knowledge. This is where, in particular, the Process Specification Language (PSL) ontology would help formalise the semantics of flow models [START_REF] Bock | PSL: a semantic domain for flow models[END_REF]. Such extensions would require a heavyweight ontological approach that fully supports more intricate relations and functions, as a result of the complexity in the semantics of manufacturing process sequences. For meeting this purpose, it would be required to identify an even more expressive heavyweight ontological formalism, since employing Frames with a First Order Logic constraint language in Protégé imposes certain restrictions to using binary relations and less powerful semantic structures.

On the other hand, UML class diagrams as a conceptual modelling method presents interesting possibilities as far as platform-independent ontology design is concerned. This is especially because currently, there is no de-facto ontology design schematic language. So, for example, a UML class can be used to represent a class in a heavyweight ontology and a UML binary association can directly map to a binary relation. Another example involves higher-arity relations, such as ternary relations, that can be represented in UML by using the construct of n-ary associations.

However, more complex heavyweight constructs like functions of multiple arities and the instantiation of meta-classes would demand an agreed mode of exploiting UML class diagrams in order to avoid ambiguity.

Conclusions

The study presented in this work has shown that there currently exists a number of benefits and drawbacks related to both lightweight and heavyweight ontological approaches. It is understood from this that the progress towards enabling expressive manufacturing knowledge representation and sharing is bound to enfold the integration of an array of ontology-based understandings and semantic technologies.

Hence, the underpinning towards expressive ontology-based approaches firstly requires enabling multiple domains to explicitly represent fundamental semantic structures. These fundamental structures should include the notion of classes and their taxonomies, together with relations and functions which can bind more than two classes together. At present, the formalism Frames with a First Order Logic constraint language is not able to capture the representation of these more complex relations and functions, while UML also falls somehow short of a direct way for so doing.

Secondly, integrity constraints need to be formalised to complement these fundamental structures, thereby semantically-enriching ontologies and ensuring the semantic consistency of populated knowledge. It is highly desirable that integrity constraints be written using an appropriate First Order Logic-based language in order to impart the required level of logical expressiveness.

Thirdly, the process of ontology development should be accompanied by the provision of appropriate ontology design schematics. This is an essential stage to support the platform-independent representation and design of fundamental structures, prior to their implementation. Currently, Frames with a First Order Logic constraint language in Protégé is less suited for the purpose of ontology design due to platformdependent modelling. Conversely, UML offers useful prospects for ontology design, specially as it may be possible to utilise UML in a customised way to represent more complex ontological notions.

Finally, the ability to formalise knowledge inference rules, using a suitable

  , UML and Frames used on its own are examples of (A), while DL and Frames with a First Order Logic constraint language are examples of heavyweight ontological approaches (B).

Figure

  implementation of the lightweight ontology-based model. In the model, UML class diagrams (L) have been exploited to represent the necessary concepts and, to some extent, the basic semantics of each domain. These UML class representations capture domain concepts in the form of classes and arrange these classes according to a taxonomy. Relations with cardinality information (M) are used to formulate the key associations that hold between different classes.

Figure 6

 6 Figure6provides a screen shot of the "Mouldability Domain" (R) class

  Mouldability Product" (see Figure6 (V)) are only allowed to hold one axis of rotation.

  simple and complex integrity constraints required for the mould design and mould manufacturing domains.

"

  Horizontal turning feature(s) must be specified" informally says that: If a straight line (e.g. (G1)) that defines the core insert for a rotational mouldability product has two points ?p1 and ?p2, such that only the x coordinates of the two points are different while the z and y coordinates are the same, then there should exist a horizontal turning feature profile (e.g. (H1)) that meets the two points in the rotational core manufacturing domain.

[

  Figure 10 to be inserted about here]

Figure 1 .

 1 Figure 1. Examples of lightweight and heavyweight ontological approaches

  Young, R.I.M, Gunendran, G.,Chungoora, N., Harding, J.A. and Case, K., 2009. Enabling interoperable manufacturing knowledge sharing in PLM.Proceedings of the 6 th International Product Lifecycle ManagementConference, University of Bath, Bath, UK.

	F o r F o r F o r
	P P P
	e e e
	First Order Logic-based language, should be provided as a means of deriving new and e r e r e r
	expressive knowledge to support engineering decisions. By providing a logic-based R R R
	e e e ground for inference rules, it becomes possible to verify derived knowledge via tractable reasoning procedures. These procedures need to be accompanied by the v i e v i e v i e relevant translation / mapping mechanisms so as to help perform the automatic assertion of derived multi-domain knowledge. w w w
	With the introduction of new ontological formalisms notably Common Logic (CL) (ISO/IEC 24707, 2007), it is clear that improved capabilities are emerging to O n l O n l O n l address higher levels of semantic expressiveness and interoperability. Work is y y y
	currently under way in our laboratory to take this aspect forward.

URL: http://mc.manuscriptcentral.com/tandf/tcim Email:ijcim@bath.ac.ukInternational Journal of Computer Integrated Manufacturing

Acknowledgements

The research developed in this paper has resulted from a number of strands of work which have been supported by different funding agencies. In particular we wish to thank (1) the EPSRC, who are funding a majority of our work on "Interoperable Manufacturing Knowledge Systems" (IMKS) under project 253 of the Loughborough University Innovative Manufacturing and Construction Research Centre, and (2) the Wolfson School of Mechanical and Manufacturing Engineering of Loughborough University for funding research studentships.