Emilie Kaufmann Kaufmann

Olivier Cappé

Aurélien Garivier
email: aurelien.garivier@math.

On the Complexity of A/B Testing

Keywords: Sequential testing, Best arm identification, Bandit models, Sample complexity

A/B testing refers to the task of determining the best option among two alternatives that yield random outcomes. We provide distribution-dependent lower bounds for the performance of A/B testing that improve over the results currently available both in the fixed-confidence (or δ-PAC) and fixed-budget settings. When the distribution of the outcomes are Gaussian, we prove that the complexity of the fixed-confidence and fixed-budget settings are equivalent, and that uniform sampling of both alternatives is optimal only in the case of equal variances. In the common variance case, we also provide a stopping rule that terminates faster than existing fixed-confidence algorithms. In the case of Bernoulli distributions, we show that the complexity of fixed-budget setting is smaller than that of fixed-confidence setting and that uniform sampling of both alternatives-though not optimal-is advisable in practice when combined with an appropriate stopping criterion.

Introduction

A/B Testing is a popular procedure used, for instance, for website optimization: two versions of a webpage, say A and B, are empirically compared by being presented to users. Each user only sees one of the two versions, and the goal is to determine which version is preferable. We assume that the users provide a real-valued index of the quality of the pages, which is modeled by probability distributions ν A and ν B , with respective means µ A and µ B . For example, a standard objective is to determine which webpage has the highest conversion rate (probability that a user actually becomes a customer) by receiving binary feedback from the users.

Methods for A/B Testing are often viewed as statistical tests of the hypothesis H 0 : (µ A ≤ µ B ) against H 1 : (µ A > µ B ). One may consider either classical tests, based on a number of samples n A and n B from each distribution fixed before the experiment, or sequential tests, based on paired samples (X s , Y s ) of ν A , ν B and in which a randomized stopping rule determines when the experiment is to be terminated. In both of these test settings, the sampling schedule is determined in advance, which is a possible source of sub-optimality as A/B Testing algorithms could take advantage of past observations to provide a smarter choice of the page to be displayed to the next user. In the sequel, we investigate whether A/B Testing could benefit from an adaptive sampling schedule. Ignoring the possible long-term effects on users of presenting one or the other option, we consider it as a particular instance of best arm identification in a two-armed bandit model.

A two-armed bandit model consists of two unknown probability distributions on R, ν 1 and ν 2 , sometimes referred to as arms or options (webpages in our motivating example). Arm a has expectation µ a . At each time t = 1, 2, . . . , an agent chooses an option A t ∈ {1, 2} and receives an independent draw Z t of the corresponding arm ν At . We denote by P ν (resp. E ν ) the probability law (resp. expectation) of the corresponding process (Z t ). We assume that the bandit model ν = (ν 1 , ν 2 ) belongs to a class M such that for all ν ∈ M, µ 1 = µ 2 . In order to identify the best arm, that is the arm a * with highest expectation, the agent must use a strategy defining which arms to sample from, when to stop sampling, and which arm â to choose. The sampling rule determines how, at time t, the arm A t is chosen based on the past observations; in other words, A t is F t-1measurable, with F t = σ(A 1 , Z 1 , . . . , A t , Z t ). The stopping rule τ is a stopping time with respect to (F t ) t∈N satisfying P ν (τ < +∞) = 1. The recommendation rule is a F τ -measurable random arm â ∈ {1, 2}. This triple ((A t ), τ, â) entirely determines the strategy, which we denote in the sequel by A. As discussed before, statistical tests correspond to strategies that sample the arms in a round-robin fashion, which we will refer to as uniform sampling.

In the bandit literature, two different settings have been considered. In the fixed-confidence setting, a risk parameter δ is fixed. A strategy A is called δ-PAC if, for every choice of ν ∈ M, P ν (â = a * ) ≥ 1 -δ. The goal is, among the δ-PAC strategies, to minimize the expected number of draws E ν [τ ]. In the fixed-budget setting, the number of draws τ is fixed in advance (τ = t almost surely) and the goal is to choose the recommendation rule so as to minimize p t (ν) := P ν (â = a * ). In the fixed-budget setting, a strategy A is called consistent if, for every choice of ν ∈ M, p t (ν) → t→∞ 0.

In order to unify and compare these approaches, we define the complexity κ C (ν) (resp. κ B (ν)) of best arm identification in the fixed-confidence (resp. fixed-budget) setting, as follows:

κ C (ν) = inf A δ-PAC lim sup δ→0 E ν [τ ] log(1/δ) , κ B (ν) = inf A consistent lim sup t→∞ - 1 t log p t (ν) -1
.

Heuristically, for a given bandit model ν and a given δ > 0, a fixed-confidence optimal strategy uses an average number of samples of order κ C (ν) log(1/δ), whereas a fixed-budget optimal strategy uses approximately t = κ B (ν) log(1/δ) draws in order to ensure a probability of error at most equal to δ. Most of the existing performance bounds for the fixed confidence and fixed budget settings can be expressed using these complexity measures.

The main goal of this paper is to determine κ C and κ B for important classes of parametric bandit models, allowing for a comparison between the fixed-confidence and fixed-budget settings. Classical sequential testing theory provides a first element in that direction in the simpler case of fully specified alternatives. Consider for instance the case where ν 1 and ν 2 are Gaussian laws with the same known variance σ 2 , the means µ 1 and µ 2 being known up to a permutation. Denoting by P the joint distribution of the paired samples (X s , Y s ), one must choose between the hypotheses [START_REF] Wald | Sequential tests of statistical hypotheses[END_REF] that among the sequential tests such that type I and type II probabilities of error are both smaller than δ, the Sequential Probability Ratio Test (SPRT) minimizes the expected number of required samples, and is such that E ν [τ ] = 2σ 2 /(µ 1 -µ 2 ) 2 log(1/δ). However, the batch test that minimizes both probabilities of error is the Likelihood Ratio test; it can be shown to require a sample size of order 8σ 2 /(µ 1 -µ 2 ) 2 log(1/δ) in order to ensure that both type I and type II error probabilities are smaller than δ. Thus, when the sampling strategy is uniform and the parameters are known, there is a clear gain in using randomized stopping strategies. We show in the following that this conclusion is not valid anymore when the values of µ 1 and µ 2 are not assumed to be known. Related works. Bandit models have received a considerable interest since their introduction by [START_REF] Thompson | On the likelihood that one unknown probability exceeds another in view of the evidence of two samples[END_REF]. An important focus was set on a different perspective, in which each observation is considered as a reward: the agent aims at maximizing the cumulative rewards obtained until some horizon t. Equivalently, his goal is to minimize the regret R t (ν) = tµ [1] -E ν t s=1 Z s . Regret minimization, which is paradigmatic of the so-called exploration versus exploitation dilemma, was introduced by [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] and its complexity is well understood for parametric bandits. In generic one-parameter models, [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF] prove that, with a proper notion of consistency adapted to regret minimization,

H 0 : P = N µ 1 , σ 2 ⊗ N µ 2 , σ 2 and H 1 : P = N µ 2 , σ 2 ⊗ N µ 1 , σ 2 . It is known since
inf A consistent lim inf t→∞ R t (ν) log t ≥ a:µa<µ [1] (µ [1] -µ a ) KL(ν a , ν [1] ) ,
where KL(ν i , ν j ) denotes the Kullback-Leibler divergence between distributions ν i and ν j . Since then, non-asymptotic analyses of efficient algorithms matching this bound have been proposed.

Optimal algorithms include the KL-UCB algorithm of [START_REF] Cappé | Kullback-Leibler upper confidence bounds for optimal sequential allocation[END_REF]-a variant of UCB1 [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]) using informational upper bounds, Thompson Sampling (Kaufmann et al. (2012b); [START_REF] Agrawal | Further Optimal Regret Bounds for Thompson Sampling[END_REF]), the DMED algorithm [START_REF] Honda | An asymptotically optimal policy for finite support models in the multiarmed bandit problem[END_REF] and Bayes-UCB Kaufmann et al. (2012a). This paper is a first step in the attempt to similarly characterize the complexity of pure exploration, where the goal is to determine the best arms without trying to maximize the cumulated observations. The problem of best arm identification has received an important interest in the 1950s as a particular case of 'ranking and identification problems'. The literature on the subject goes beyond two-armed bandit models to finding the m > 1 best arms among K > 2 arms, and sometimes introduces a relaxation parameter > 0, such that arms within of the best arm should be recommended. In the sequel, we always particularize the existing results to the two-armed bandit models presented above. The first advances on this topic are summarized in the monograph by [START_REF] Bechhofer | Sequential identification and ranking procedures[END_REF], who only consider the fixed-confidence setting. In the same setting, algorithms introduced more recently by [START_REF] Even-Dar | Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems[END_REF]; [START_REF] Kalyanakrishnan | PAC subset selection in stochastic multiarmed bandits[END_REF]; [START_REF] Gabillon | Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence[END_REF] can be used to find the best arm in a two-armed bounded bandit model, in which ν 1 and ν 2 are probability distributions on [0, 1]. Combining the upper bound on E ν [τ ] for the LUCB algorithm of [START_REF] Kalyanakrishnan | PAC subset selection in stochastic multiarmed bandits[END_REF] with the lower bound following from the work of [START_REF] Mannor | The Sample Complexity of Exploration in the Multi-Armed Bandit Problem[END_REF], it can be shown that for bounded bandit models such that µ a ∈ [0, 1 -α] for a ∈ {1, 2}, there exists a constant C α for which

C α /(µ 1 -µ 2 ) 2 ≤ κ C (ν) ≤ 584/(µ 1 -µ 2 ) 2 .
The fixed-budget setting has been studied recently by [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF]; [START_REF] Bubeck | Multiple Identifications in multi-armed bandits[END_REF]. In two-armed bandit problems, the algorithms introduced in these papers boil down to sampling each arm t/2 times-t denoting the total budget-and recommending the empirical best arm. A simple upper bound on the probability of error of this strategy can be derived, and this result paired with the lower bound of [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF] yields, for bounded bandit models such that µ a ∈ [α; 1 -α] for a ∈ {1, 2}: [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF] show that in the fixed-budget setting any sampling strategy designed to minimize regret performs poorly with respect to the simple regret r t := µ * -µ Ŝ1 , a quantity closely related to the probability p t (ν) of recommending the wrong arm. Therefore, good strategies for best arm identification have to be quite different from UCB-like strategies. We will show below that the complexities κ B (ν) and κ C (ν) of pure-exploration involve information terms that are different from the Kullback-Leibler divergence featured in Lai and Robbins' lower bound on regret.

(2/5)α(1 -α)/(µ 1 -µ 2 ) 2 ≤ κ B (ν) ≤ 2/(µ 1 -µ 2 ) 2 .
Contents of the paper. Compared to existing results, we provide general lower bounds on κ B (ν) and κ C (ν) that: (i) are tighter, leading in specific parametric cases to a precise evaluation of these complexities; (ii) do not require unnecessary support assumptions; and (iii) are stated in terms of information divergences between the distributions ν 1 and ν 2 rather than in terms of the gap µ 1 -µ 2 . As can be expected, we will indeed confirm that the inverse of the squared gap (µ 1 -µ 2 ) 2 is the relevant measure of complexity only in the Gaussian case, and an approximation (in the spirit of Pinsker's inequality) for sub-Gaussian distributions.

Lower bounds on the sample complexity (resp. probability of error) of algorithms using the uniform sampling strategy in the fixed-confidence (resp. fixed-budget) setting are also derived and we show that for Gaussian bandit models with different variances, there is a significant gain in using a non-uniform sampling strategy. For Bernoulli bandits however, we show that little can be gained by departing from uniform sampling, and we therefore propose close-to-optimal tests both for the batch and sequential settings. For Gaussian bandits with a known common variance the optimal algorithm uses uniform sampling. In this specific case, we propose an improved δ-PAC stopping rule, illustrating its performance through numerical experiments.

Our contributions follow from two main mathematical results: Lemma 8 provides a general relation between the expected number of draws and Kullback-Leibler divergences of the arms' distributions, which is the key element to derive the lower bounds. Lemma 9 is a tight deviation inequality for martingales with sub-Gaussian increments, in the spirit of the Law of Iterated Logarithm.

The paper is structured as follows. Section 2 presents a distribution-dependent lower bound on both κ B (ν) and κ C (ν) under the some identifiability assumption, as well as lower bounds for algorithms using uniform sampling. Gaussian bandit models are then studied in details in Section 3, and Bernoulli bandit models in Section 4. Section 5 includes a practical illustration of the performance of matching algorithms for Gaussian bandits, as well as a practical comparison of the fixed-confidence and fixed-budget settings. The most important elements of proof are gathered in Section 6, with the rest of the proofs in the Appendix.

Lower Bounding the Complexity

Introducing the Kullback-Leibler divergence of any two probability distributions p and q:

KL(p, q) = log dp dq (x) dp(x) if q p,
+∞ otherwise, we make the assumption that there exists a set N such that for all ν = (ν 1 , ν 2 ) ∈ M, for a ∈ {1, 2}, ν a ∈ N and that N satisfies ∀p, q ∈ N , p = q ⇒ 0 < KL(p, q) < +∞.

A class M of bandit models satisfying this property is called identifiable. For M an identifiable class of bandit models, Theorem 1 provides lower bounds on κ B (ν) and κ C (ν) for every ν ∈ M. The proof of this theorem is based on changes of distribution and detailed in Section 6.

Theorem 1 Let ν = (ν 1 , ν 2 ) be a two-armed bandit model such that µ 1 > µ 2 . In the fixed-budget setting, any consistent algorithm satisfies

lim sup t→∞ - 1 t log p t (ν) ≤ c * (ν), where c * (ν) := inf (ν 1 ,ν 2 )∈M:µ 1 <µ 2 max KL(ν 1 , ν 1 ), KL(ν 2 , ν 2 ) .
In the fixed-confidence setting any algorithm that is δ-PAC on M satisfies, when δ ≤ 0.15,

E ν [τ ] ≥ 1 c * (ν) log 1 2δ
, where c * (ν) := inf

(ν 1 ,ν 2 )∈M:µ 1 <µ 2 max KL(ν 1 , ν 1 ), KL(ν 2 , ν 2 ) .
In particular, Theorem 1 implies that κ B (ν) ≥ 1/c * (ν) and κ C (ν) ≥ 1/c * (ν). Proceeding similarly, one can obtain lower bounds for the algorithms that use uniform sampling of both arms. The proof of the following result is easily adapted from that of Theorem 1 (cf. Section 6), using that each arm is drawn τ /2 times.

Theorem 2 Let ν = (ν 1 , ν 2 ) be a two-armed bandit model such that µ 1 > µ 2 . In the fixed-budget setting, any consistent algorithm using a uniform sampling strategy satisfies

lim sup t→∞ - 1 t log p t (ν) ≤ I * (ν) where I * (ν) := inf (ν 1 ,ν 2 )∈M:µ 1 <µ 2 KL (ν 1 , ν 1 ) + KL (ν 2 , ν 2 ) 2 .
In the fixed-confidence setting, any algorithm that is δ-PAC on M and uses a uniform sampling strategy satisfies, for δ ≤ 0.15,

E ν [τ ] ≥ 1 I * (ν) log 1 2δ where I * (ν) := inf (ν 1 ,ν 2 )∈M:µ 1 <µ 2 KL (ν 1 , ν 1 ) + KL (ν 2 , ν 2 ) 2 .
Obviously, one always has I * (ν) ≤ c * (ν) and I * (ν) ≤ c * (ν) suggesting that uniform sampling can be sub-optimal. It is possible to give explicit expressions for the quantities c * (ν), c * (ν) and I * (ν), I * (ν) for specific classes of parametric bandit models that will be considered in the rest of the paper. In the case of Gaussian bandits with known variance (see Section 3):

M = {ν = N µ 1 , σ 2 1 , N µ 2 , σ 2 2 : (µ 1 , µ 2 ) ∈ R 2 , µ 1 = µ 2 }, (1)
one obtains

c * (ν) = c * (ν) = (µ 1 -µ 2 ) 2 2(σ 1 + σ 2 ) 2 and I * (ν) = I * (ν) = (µ 1 -µ 2 ) 2 4(σ 2 1 + σ 2 2 )
.

Hence, the lower bounds of Theorem 1 are equal in this case, and we provide in Section 3 matching upper bounds confirming that indeed κ B (ν) = κ C (ν). In addition, the observation that 2I * (ν) ≥ c * (ν) ≥ I * (ν) implies that, except when σ 1 = σ 2 , strategies based on uniform sampling are suboptimal.

The values of c * (ν) and c * (ν) can also be computed for canonical one-parameter exponential families with density with respect to some reference measure given by

f θ (x) = A(x) exp(θx -b(θ)), for θ ∈ Θ ⊂ R.
(2)

We consider the class of bandit models

M = {ν = (ν θ 1 , ν θ 2 ) : (θ 1 , θ 2 ) ∈ Θ 2 , θ 1 = θ 2 }
where ν θa has density f θa given by (2). Using the shorthand

K(θ, θ ) = KL(ν θ , ν θ ) for (θ, θ ) ∈ Θ 2 , one can show that, for ν such that µ 1 > µ 2 : c * (ν) = inf θ∈Θ max (K(θ, θ 1 ), K(θ, θ 2 )) = K(θ * , θ 1 ), where K(θ * , θ 1 ) = K(θ * , θ 2 ), c * (ν) = inf θ∈Θ max (K(θ 1 , θ), K(θ 2 , θ)) = K(θ 1 , θ * ), where K(θ 1 , θ * ) = K(θ 2 , θ * ).
The coefficient c * (ν) is known as the Chernoff information K * (θ 1 , θ 2 ) between the distributions ν θ 1 and ν θ 2 (see [START_REF] Cover | Elements of Information Theory[END_REF] and [START_REF] Kaufmann | Information complexity in bandit subset selection[END_REF] for earlier notice of the relevance of this quantity in the best arm selection problem). By analogy, we will also denote c * (ν) by

K * (θ 1 , θ 2 ) = K(θ 1 , θ * ).
For exponential family bandits the quantities c * (ν) and c * (ν) are not equal in general, although it can be shown that it is the case when the log-partition function b(θ) is (Fenchel) self-conjugate (e.g., for Gaussian and exponential variables). In Section 4, we will focus on the case of Bernoulli models for which c * (ν) > c * (ν). By exhibiting a matching strategy in the fixed-budget case, we will show that this implies that κ C (ν) > κ B (ν) in this case.

The Gaussian Case

We study in this Section the class of two-armed Gaussian bandit models with known variances defined by (1), where σ 1 and σ 2 are fixed. In this case, we observed above that the lower bounds of Theorem 1 are similar, because c * (ν) = c * (ν). We prove in this section that indeed

κ C (ν) = κ B (ν) = 2(σ 1 + σ 2 ) 2 (µ 1 -µ 2 ) 2
by exhibiting strategies that reach these performance bounds. These strategies are based on the simple recommendation of the empirical best arm but use non-uniform sampling in cases where σ 1 and σ 2 differ. When σ 1 = σ 2 we provide in Theorem 3 an improved stopping rule that is δ-PAC but results in a significant reduction of the running time of fixed-confidence tests.

Fixed-Budget Setting

We consider the simple family of static strategies that draw n 1 samples from arm 1 followed by n 2 = t -n 1 samples of arm 2, and then choose arm 1 if μ1,n 1 < μ2,n 2 , where μi,n i denotes the empirical mean of the n i samples from arm i. Assume for instance that

µ 1 > µ 2 . Since μ1,n 1 -μ2,n 2 -µ 1 + µ 2 ∼ N 0, σ 2 1 /n 1 + σ 2 2 /n 2 ,
the probability of error of such a strategy is easily upper bounded as:

P (μ 1,n 1 < μ2,n 2 ) ≤ exp - σ 2 1 n 1 + σ 2 2 n 2 -1 (µ 1 -µ 2 ) 2 2 .
The right hand side is minimized when n 1 /(n 1 + n 2 ) = σ 1 /(σ 1 + σ 2 ), and the static strategy drawing n 1 = σ 1 t/(σ 1 + σ 2 ) times arm 1 is such that

lim inf t→∞ - 1 t log p t (ν) ≥ (µ 1 -µ 2 ) 2 2(σ 1 + σ 2 ) 2 ,
which matches the bound of Theorem 1 for Gaussian bandit models.

Fixed-Confidence Setting

EQUAL VARIANCES

We start with the simpler case σ 1 = σ 2 = σ, where the quantity I * (ν) introduced in Theorem 2 coincides with c * (ν), which suggests that uniform sampling could be optimal. A uniform sampling strategy is equivalent to collecting paired samples (X s , Y s ) from both arms. The difference X s -Y s is Gaussian with mean µ = µ 1 -µ 2 and a δ-PAC algorithm is equivalent to a sequential test of H 0 : µ < 0 versus H 1 : µ > 0 such that the probability of error is uniformly bounded by δ. [START_REF] Robbins | Statistical Methods Related to the law of the iterated logarithm[END_REF] proposes such a test that stops after a number of samples

τ = inf    t ∈ 2N * : t/2 s=1 (X s -Y s ) > 2σ 2 tβ(t, δ)    with β(t, δ) = t + 1 t log t + 1 2δ (3)
and recommends the empirical best arm. This procedure belongs to the class of elimination strategies, introduced by [START_REF] Jennison | Asymptotically optimal procedures for sequential adaptive selection of the best of several normal means[END_REF] who derive a lower bound on the sample complexity of any δ-PAC elimination strategy-whereas our lower bound applies to any δ-PAC algorithm-matched by Robbins' algorithm, that is, lim δ→0 E ν [τ ]/log 1 δ = 8σ 2 /(µ 1 -µ 2 ) 2 . Therefore, Robbins' rule (3) yields an optimal strategy matching our general lower bound of Theorem 1 in the particular case of Gaussian distributions with common known variance.

Note that any elimination strategy that is δ-PAC and uses a threshold function smaller than Robbins' also matches our asymptotic lower bound, while being strictly more efficient than Robbins' rule. For practical purpose, it is therefore interesting to exhibit smaller exploration rates β(t, δ) leading to a δ-PAC algorithm. The probability of error of such an algorithm is upper bounded, for example for µ 1 < µ 2 by

P ν ∃k ∈ N : k s=1 X s -Y s -(µ 1 -µ 2 ) √ 2σ 2 > 2kβ(2k, δ) = P ∃k ∈ N : S k > 2kβ(2k, δ) (4
) where S k is a sum of k i.i.d. variables of distribution N (0, 1). [START_REF] Robbins | Statistical Methods Related to the law of the iterated logarithm[END_REF] obtains a nonexplicit confidence region of risk at most δ by choosing β(2k, δ) = log (log(k)/δ) + o(log log(k)). The dependency in k is in some sense optimal, because the Law of Iterated Logarithm (LIL) states that lim sup k→∞ S k / 2k log log(k) = 1 almost surely. Recently, [START_REF] Jamieson | lil'UCB: an optimal exploration algorithm for multi-armed bandits[END_REF] proposed an explicit confidence region inspired by the LIL. However, Lemma 1 of [START_REF] Jamieson | lil'UCB: an optimal exploration algorithm for multi-armed bandits[END_REF] cannot be used to upper bound (4) by δ and we provide in Section 6 a result derived independently (Lemma 9) that achieves this goal and yields the following result.

Theorem 3 For δ small enough, the elimination strategy (3) is δ-PAC with

β(t, δ) = log 1 δ + 3 4 log log 1 δ + 3 2 log(1 + log(t/2)). (5)
Algorithm 1 α-Elimination Require: Exploration function β(t, δ), parameter α.

1: Initialization: μ1 (0) = μ2 (0) = 0, σ 2 0 (α) = 1. t = 0. 2: while |μ 1 (t) -μ2 (t)| ≤ 2σ 2 t (α)β(t, δ) do 3: t = t + 1.

4:

If αt = α(t -1) , A t = 2, else A t = 1.

5:

Observe Z t ∼ ν At and compute the empirical means μ1 (t) and μ2 (t).

6:

Compute σ 2 t (α) = σ 2 1 / αt + σ 2 2 /(t -αt ). 7: end while 8: return a = argmax a=1,2 μa (t)

MISMATCHED VARIANCES

In the case where σ 1 = σ 2 , we rely on an α-elimination strategy, described in Algorithm 1. For a = 1, 2, μa (t) denotes the empirical mean of the samples gathered from arm a up to time t. The algorithm is based on a non-uniform sampling strategy governed by the parameter α ∈ (0, 1) which ensures that, at the end of every round t, N

1 (t) = αt , N 2 (t) = t -αt and μ1 (t) -μ2 (t) ∼ N µ 1 -µ 2 , σ 2 t (α)
. The sampling schedule used here is thus deterministic. Theorem 4 shows that the σ 1 /(σ 1 + σ 2 )-elimination algorithm, with a suitable exploration rate, is δ-PAC and matches the lower bound on E ν [τ ], at least asymptotically when δ → 0. Its proof can be found in Appendix C.

Theorem 4 If α = σ 1 /(σ 1 + σ 2 ), the α-elimination strategy using the exploration rate β(t, δ) = log t δ + 2 log log(6t) is δ-PAC on M and satisfies, for every ν ∈ M, for every > 0,

E ν [τ ] ≤ (1 + ) 2(σ 1 + σ 2 ) 2 (µ 1 -µ 2 ) 2 log 1 δ + o δ→0 log 1 δ .
Remark 5 When σ 1 = σ 2 , 1/2-elimination reduces, up to rounding effects, to the elimination procedure described in Section 3.2.1, for which Theorem 3 suggests an exploration rate of order log(log(t)/δ). As the feasibility of this exploration rate when σ 1 = σ 2 is yet to be established, we focus on Gaussian bandits with equal variances in the numerical experiments of Section 5.

The Bernoulli Case

We consider in this section the class of Bernoulli bandit models defined by

M = {ν = (B(µ 1 ), B(µ 2 )) : (µ 1 , µ 2 ) ∈]0; 1[ 2 , µ 1 = µ 2 },
where each arm can be equivalently parametrized by the natural parameter of the exponential family, θ a = log(µ a /(1 -µ a )). Following the notation of Section 2, the Kullback-Leibler divergence between two Bernoulli distributions can be either expressed as a function of the means, KL(B(µ 1 ), B(µ 2 )), or of the natural parameters, K(θ 1 , θ 2 ).

In this Section, we prove that κ C (ν) > κ B (ν) for Bernoulli bandit models (Proposition 7). To do so, we first introduce a static strategy matching the lower bound of Theorem 1 in the fixedbudget case (Proposition 6). This strategy is reminiscent of the algorithm exhibited for Gaussian bandits in Section 3 and uses parameter-dependent non uniform sampling. This strategy is not directly helpful in practice but we show that it can be closely approximated by an algorithm using the uniform sampling strategy. In the fixed-confidence setting we similarly conjecture that little can be gained from using a non-uniform sampling strategy and propose an algorithm based on a non-trivial stopping strategy that is believed to match the bound of Theorem 2.

Proposition 6 Let α(θ 1 , θ 2 ) be defined by

α(θ 1 , θ 2 ) = θ * -θ 1 θ 2 -θ 1 where K(θ * , θ 1 ) = K(θ * , θ 2 ).
For all t, the static strategy that allocates α(θ 1 , θ 2 )t samples to arm 1 , and recommends the empirical best arm, satisfies p t (ν) ≤ exp(-K * (θ 1 , θ 2 )t).

This result, proved in Appendix D, shows in particular that for every ν ∈ M there exists a consistent static strategy such that

lim inf t→∞ - 1 t log p t ≥ K * (θ 1 , θ 2 ), and hence that κ B (ν) = 1 K * (θ 1 , θ 2 )
.

However, as α(θ 1 , θ 2 ) depends in the Bernoulli case on the unknown means of the arms, this optimal static strategy is not useful in practice. So far, it is not known whether there exists a universal strategy such that p t (ν) ≤ exp(-K * (θ 1 , θ 2 )t) for all bandit instance ν ∈ M.

For Bernoulli bandit models it can be checked that for all ν ∈ M, K * (θ 1 , θ 2 ) < K * (θ 1 , θ 2 ). This fact together with Proposition 6 and Theorem 1 yields the following inequality.

Proposition 7 For all ν ∈ M, κ C (ν) > κ B (ν).

In the specific case of Bernoulli distributions, there is a strong incentive to use uniform sampling: the quantities I * (ν) and I * (ν) introduced in Theorem 2 appear to be very close to c * (ν) and c * (ν) respectively. This fact is illustrated in Figure 1, on which we represent these different quantities, that are functions of the means µ 1 , µ 2 of the arms, as a function of µ 1 , for two fixed values of µ 2 . Therefore, algorithms matching the bounds of Theorem 2 provide upper bounds on κ B (ν) (resp. κ C (ν)) very close to 1/c * (ν) (resp. 1/c * (ν)). In the fixed-budget setting, Lemma 15 shows that the strategy with uniform sampling that recommends the empirical best arm, satisfies p t (ν) ≤ e -tI * (ν) , and matches the bound of Theorem 2 (see Remark 16 in Appendix D). Hence, problem-dependent optimal strategy described above can be approximated by a very simple, universal algorithm. Similarly, finding an algorithm for the fixed-confidence setting sampling the arms uniformly and matching the bound of Theorem 2 is a crucial matter. This boils down to finding a good stopping rule. In all the algorithms studied so far, the stopping rule was based on the difference of the empirical means of the arms. For Bernoulli arms, such a strategy can be analyzed with the tools provided in this paper: the algorithm stopping for t such that μ1,t/2 -μ2,t/2 > 2β(t, δ)/t with β(t, δ) as in Theorem 3 is δ-PAC and its expected running time bounded by 2/(µ 1 -µ 2 ) 2 log 1 δ + o log 1 δ . Yet, Pinsker's inequality implies that I * (µ 1 , µ 2 ) > (µ 1 -µ 2 ) 2 /2 and this algorithm is thus not optimal with respect to Theorem 2. The approximation optimal error exponent is particularly significant when both means are close to 0 or 1. The stopping rule we propose to circumvent this drawback is the following:

I * (µ 1 , µ 2 ) = (µ 1 -µ 2 ) 2 /(8µ 1 (1 -µ 1 )) + o (µ 1 -µ 2 ) 2 suggests
τ = inf t ∈ 2N * : tI * (μ 1,t/2 , μ2,t/2 ) > log ((log(t) + 1)/δ) . ( 6
)
This algorithm is related to the KL-LUCB algorithm of [START_REF] Kaufmann | Information complexity in bandit subset selection[END_REF]. Indeed, I * (x, y) mostly coincides with K * (B(x), B(y)) (Figure 1) and a closer examination shows that the stopping criterion in KL-LUCB for two arms is exactly of the form tK * (B(μ 1,t/2 ), B(μ 2,t/2 )) > β(t, δ). The results of [START_REF] Kaufmann | Information complexity in bandit subset selection[END_REF] show in particular that the algorithm based on ( 6) is provably δ-PAC for appropriate choices of β(t, δ). However, by analogy with the result of Theorem 3 we believe that the analysis of [START_REF] Kaufmann | Information complexity in bandit subset selection[END_REF] is too conservative and that the proposed approach should be δ-PAC for exploration rates β(t, δ) that grow as a function of t only at rate log log t.

Numerical Experiments and Discussion

The goal of this Section is twofold: to compare results obtained in the fixed-budget and fixedconfidence settings and to illustrate the improvement resulting from the adoption of the reduced exploration rate of Theorem 3.

In Figure 2, we consider two bandit models: the 'easy' one is N (0.5, 0.25) ⊗ N (0, 0.25), κ = 8 (left) and the 'difficult' one is N (0.01, 0.25) ⊗ N (0, 0.25), κ = 20000 (right). In the fixed-budget setting, stars ('*') report the probability of error p n (ν) as a function of n. In the fixedconfidence setting, we plot both the empirical probability of error by circles ('O') and the specified maximal error probability δ by crosses ('X') as a function of the empirical average of the running times. Note the logarithmic scale used for the probabilities on the y-axis. All results are averaged on N = 10 6 independent Monte Carlo replications. For comparison purposes, a plain line represents the theoretical rate x → exp(-x/κ) which is a straight line on the log scale.

In the fixed-confidence setting, we report results for algorithms of the form (3) with g(t, δ) = 2σ 2 tβ(t, δ) for three different exploration rates β(t, δ). The exploration rate we consider are: the provably-PAC rate of Robbins' algorithm log(t/δ) (large blue symbols), the conjectured 'optimal' exploration rate log((log(t) + 1)/δ), almost provably δ-PAC according to Theorem 3 (bold green symbols), and the rate log(1/δ), which would be appropriate if we were to perform the stopping test only at a single pre-specified time (orange symbols). For each algorithm, the log probability of error is approximately a linear function of the number of samples, with a slope close to -1/κ, where κ is the complexity. We can visualize the gain in sample complexity achieved by smaller exploration rates, but while the rate log((log(t) + 1)/δ) appears to guarantee the desired probability of error across all problems, the use of log(1/δ) seems too risky, as one can see that the probability of error becomes larger than δ on difficult problems. To illustrate the gain in sample complexity when the means of the arms are known, we add in red the SPRT algorithm mentioned in the introduction along with the theoretical relation between the probability of error and the expected number of samples, materialized as a dashed line. The SPRT stops for t such that

|(µ 1 -µ 2 )(S 1,t/2 -S 2,t/2 )| > log(1/δ).
Robbins' algorithm is δ-PAC and matches the complexity (which is illustrated by the slope of the measures), though in practice the use of the exploration rate log((log(t) + 1)/δ) leads to huge gain in terms of number of samples used. It is important to keep in mind that running times play the same role as error exponents and hence the threefold increase of average running times observed on the rightmost plot of Figure 2 when using β(t, δ) = log(t/δ) is really prohibitive. This illustrates the asymptotic nature of our notion of complexity: the leading term in E ν [τ ] is indeed κ log(1/δ) but there is a second-order constant term which is not negligible for fixed value of δ. [START_REF] Jamieson | lil'UCB: an optimal exploration algorithm for multi-armed bandits[END_REF] implicitly consider an alternative complexity for Gaussian bandit models with common known variance: for a fixed value of δ, if ∆ = µ 1 -µ 2 , they show that when the gap ∆ goes to zeros, the sample complexity if of order some constant-that depends on δ-multiplied by ∆ -2 log log ∆ -2 .

If one compares on each problem the results for the fixed-budget setting to those for the best δ-PAC algorithm (in green), one can see that to obtain the same probability of error, the fixedconfidence algorithm needs an average number of samples of order at least twice larger than the deterministic number of samples required by the fixed-budget setting algorithm. This remark should be related to the fact that a δ-PAC algorithm is designed to be uniformly good across all problems, whereas consistency is a weak requirement in the fixed-budget setting: any strategy that draws both arm infinitely often and recommends the empirical best is consistent. Figure 2 shows that when the values of µ 1 and µ 2 are unknown, the sequential version of the test is no more preferable to its batch counterpart and can even become much worse if the exploration rate β(t, δ) is chosen too conservatively. This observation should be mitigated by the fact that the sequential (or fixed-confidence) approach is adaptive with respect to the difficulty of the problem whereas it is impossible to predict the efficiency of a batch (or fixed-budget) experiment without some prior knowledge regarding the problem under consideration.

Elements of Proof

Proof of Theorem 1

The cornerstone of the proof of all the lower bounds given in this paper is Lemma 8 which relates the probabilities of the same event under two different models to the expected number of draws of each arm. Its proof, which may be found in Appendix A, encapsulates the technical aspects of the change of distributions. N a (t) denotes the number of draws of arm a up to round t and N a = N a (τ ) is the total number of draws of arm a by some algorithm A.

Lemma 8 Let ν and ν be two bandit models. For any A ∈ F τ such that 0 < P ν (A) < 1

E ν [N 1 ]KL(ν 1 , ν 1 ) + E ν [N 2 ]KL(ν 2 , ν 2 ) ≥ d(P ν (A), P ν (A)), (7)
where d(x, y) := KL(B(x), B(y

)) = x log(x/y) + (1 -x) log (1 -x)/(1 -y) .
Without loss of generality, assume that the bandit model ν = (ν 1 , ν 2 ) is such that a * = 1. Consider any alternative bandit model ν = (ν 1 , ν 2 ) in which a * = 2 and the event A = (â = 1) where â is the arm chosen by algorithm A. Clearly A ∈ F τ .

Fixed-Confidence Setting. Let A be a δ-PAC algorithm. Then it is correct on both ν and ν and satisfies P ν (A) ≥ 1 -δ and P ν (A) ≤ δ. Using monotonicity properties of d (for example x → d(x, y) is increasing when x > y and decreasing when x < y) and inequality (7) in Lemma 8 yields

E ν [N 1 ]KL(ν 1 , ν 1 ) + E ν [N 2 ]KL(ν 2 , ν 2 ) ≥ d(δ, 1 -δ), and hence E ν [τ ] ≥ d(δ, 1 -δ) max a=1,2 KL(ν a , ν a )
,

using that τ = N 1 +N 2 .
Optimizing over the possible model ν satisfying µ 1 < µ 2 to make the right hand side of the inequality as large as possible gives the result, using moreover that for δ ≤ 0.15, it can be shown that d(1 -δ, δ) ≥ log(1/(2δ)).

Fixed-Budget Setting. Inequality (7) in Lemma 8 applied to A yields

E ν [N 1 (t)]KL(ν 1 , ν 1 ) + E ν [N 2 (t)]KL(ν 2 , ν 2 ) ≥ d(P ν (A), P ν (A)).
Note that p t (ν) = 1 -P ν (A) and p t (ν ) = P ν (A). As algorithm A is correct on both ν and ν , for every > 0 there exists t 0 ( ) such that for all t ≥ t 0 ( ), P ν (A) ≤ ≤ P ν (A). For t ≥ t 0 ( ),

E ν [N 1 (t)]KL(ν 1 , ν 1 ) + E ν [N 2 (t)]KL(ν 2 , ν 2 ) ≥ d( , 1 -p t (ν)) ≥ (1 -) log 1 - p t (ν) + log .
Taking the limsup (denoted by lim) and letting go to zero, one can show that lim -

1 t log p t (ν) ≤ lim E ν [N 1 (t)] t KL(ν 1 , ν 1 ) + E ν [N 2 (t)] t KL(ν 2 , ν 2 ) ≤ max a=1,2 KL(ν a , ν a ).
Optimizing over the possible model ν satisfying µ 1 < µ 2 to make the right hand side of the inequality as small as possible gives the result.

Proof of Theorem 3

According to (4), the proof of Theorem 3 boils down to finding an exploration rate such that P(∃t ∈ N * : S t > 2σ 2 tβ(t, δ)) ≤ δ, where S t = X 1 + • • • + X t is a sum of i.i.d. normal random variable.

Lemma 9 provides such a confidence region. Its proof can be found in Appendix B.

Lemma 9 Let ζ(u) = k≥1 k -u . Let X 1 , X 2 , . . . be independent random variables such that, for all λ ∈ R, φ(λ) := log E[exp(λX 1 )] ≤ λ 2 σ 2 /2. For every positive integer t let

S t = X 1 +• • •+X t .
Then, for all β > 1 and x ≥ 8 (e-1) 2 ,

P ∃t ∈ N * : S t > 2σ 2 t(x + β log log(et)) ≤ √ e ζ β 1 - 1 2x √ x 2 √ 2 + 1 β exp(-x).
Let β(t, δ) be of the form β(t, δ) = log 1 δ + c log log 1 δ + d log log(et), for some constants c > 0 and d > 1. Lemma 9 yields

P ∃t ∈ N : S t > 2σ 2 tβ(t, δ) ≤ ζ d 1 - 1 2(z + c log z) √ e (2 √ 2) d ( √ z + c log z + √ 8) d z c δ,
where z := log 1 δ > 0. To upper bound the above probability by δ, at least for large values of z (which corresponds to small values of δ), it suffices to choose the parameters c and d such that

√ e ζ d 1 - 1 2(z + c log z) 1 (2 √ 2) d ( √ z + c log z + 2 √ 2) d z c
≤ 1.

For c = d/2, the left hand side tends to √ eζ (d)/(2 √ 2) d when z goes to infinity, which is smaller than 1 for d ≥ 1.47. Thus, for δ small enough, the desired inequality holds for d = 3/2 and c = 3/4, which corresponds to the exploration rate of Theorem 3.

Conclusion

We provide distribution-dependent lower bounds for best-arm identification in the context of twoarmed bandit models. These bounds involve information-theoretic quantities that reflect the typical causes of failure, which are different from those appearing in regret analysis. For Gaussian and Bernoulli bandit models, we exhibit matching algorithms showing that these bounds are (mostly) tight, highlighting relationships between the complexities of the fixed-budget and fixed-confidence settings. Our numerical experiments illustrate the significance of using appropriate exploration rates in the context of best arm(s) identification and we believe that Lemma 8 can be adapted to deal with more general K-armed bandit scenarios.

These results suggest three practical implications for A/B testing. First, for Binary and Gaussianlike responses with matched variances it is reasonable to consider only tests-i.e., strategies using uniform sampling-rather than general sequential sampling strategies. Second, using a sequential stopping rule in this context is mostly of interest because it does not requires prior knowledge of the complexity of the problem. It should however not be expected to reduce the (average) running time of the experiment for a given probability of error. This leads to the third message regarding the utmost importance of using proper (i.e., provably δ-PAC but not too conservative) exploration rates when using a sequential stopping rule.

Lemma 12 For every η > 0,

A(η) := 4 (1 + η) 1/4 + (1 + η) -1/4 2 ≥ 1 - η 2 16 .
Lemma 13 Let t be such that (1+η

) k-1 ≤ t ≤ (1+η) k . Then, if λ = σ -1 2zA(η)/(1 + η) k-1/2 , σ √ 2z ≥ A(η)z λ √ t + λσ 2 √ t 2 .
Proof:

A(η)z λ √ t + λσ 2 √ t 2 = σ 2zA(η) 2 (1 + η) k-1/2 t + t (1 + η) k-1/2 ≤ σ √ 2z
according to Lemma 11.

An important fact is that for every λ ∈ R, because the X i are σ-subgaussian, W t = exp(λS tt λ 2 σ 2 2 )) is a super-martingale, and thus, for every positive u,

P   t≥1 λS t -t λ 2 σ 2 2 > u   ≤ exp(-u). (9)
Let η ∈]0, e -1] to be defined later, and let

T k = N ∩ (1 + η) k-1 , (1 + η) k . P   t≥1 S t σ √ 2t > x + β log log(et)   ≤ ∞ k=1 P   t∈T k S t σ √ 2t > x + β log log(et)   ≤ ∞ k=1 P   t∈T k S t σ √ 2t > x + β log (k log(1 + η))   .
We use that η ≤ e -1 to obtain the last inequality since this condition implies

log(log(e(1 + η) k-1 ) ≥ log(k log(1 + η)).
For a positive integer k, let

z k = x+β log (k log(1 + η)) and λ k = σ -1 2z k A(η)/(1 + η) k-1/2 .
Lemma 13 shows that for every t ∈ T k ,

S t σ √ 2t > √ z k ⊂ S t √ t > A(η)z k λ k √ t + σ 2 λ k √ t 2 .
Thus, by inequality (9),

P   t∈T k S t σ √ 2t > √ z k   ≤ P   t∈T k S t √ t > A(η)z k λ k √ t + σ 2 λ k √ t 2   = P   t∈T k λ k S t - σ 2 λ 2 k t 2 > A(η)z k   ≤ exp (-A(η)z k ) = exp(-A(η)x) (k log(1 + η)) βA(η) .
One chooses η 2 = 8/x for x such that x ≥ 8 (e-1) 2 (which ensures η ≤ e -1). Using Lemma 12, one obtains that exp(-A(η)x) ≤ √ e exp(-x). Moreover,

1 log(1 + η) ≤ 1 + η η = √ x 2 √ 2 + 1 . Thus, P   t∈T k S t σ √ 2t > √ z k   ≤ √ e k βA(η) √ x 2 √ 2 + 1 βA(η) exp(-x) ≤ √ e k βA(η) √ x 2 √ 2 + 1 β exp(-x)
and hence,

P   t≥1 S t σ √ 2t > x + β log log(et)   ≤ √ eζ (βA(η)) √ x 2 √ 2 + 1 βA(η) exp (-x) ≤ √ eζ β 1 - 1 2x √ x 2 √ 2 + 1 β exp (-x) ,
using the lower bound on A(η) given in Lemma 12 and the fact that A(η) is upper bounded by 1.

by an union bound and Chernoff bound applied to d t -(µ 1 -µ 2 ) ∼ N 0, σ 2 t (α) . The choice of β(t, δ) mentioned above ensures that the series in the right hand side is upper bounded by δ, which shows the algorithm is δ-PAC:

∞ t=1 e -β(t,δ) ≤ δ ∞ t=1 1 t(log(6t)) 2 ≤ δ 1 (log 6) 2 + ∞ 1 dt t(log(6t)) 2 = δ 1 (log 6) 2 + 1 log(6) ≤ δ.
To upper bound the expected sample complexity, we start by upper bounding the probability that τ exceeds some deterministic time T :

P ν (τ ≥ T ) ≤ P ν ∀t = 1 . . . T, d t ≤ 2σ 2 t (α)β(t, δ) ≤ P ν d T ≤ 2σ 2 T (α)β(T, δ) = P ν d T -(µ 1 -µ 2 ) ≤ -(µ 1 -µ 2 ) -2σ 2 T (α)β(T, δ) ≤ exp - 1 2σ 2 T (α) (µ 1 -µ 2 ) -2σ 2 T (α)β(T, δ) 2 .
The last inequality follows from Chernoff bound and holds for T such that

(µ 1 -µ 2 ) > 2σ 2 T (α)β(T, δ). (10)
Now, for γ ∈]0, 1[ we introduce

T * γ := inf t 0 ∈ N : ∀t ≥ t 0 , (µ 1 -µ 2 ) -2σ 2 t (α)β(t, δ) > γ(µ 1 -µ 2 ) .
This quantity is well defined as σ 2 t (α)β(t, δ) → t→∞ 0. We then upper bound the expectation of τ :

E ν [τ ] ≤ T * γ + T =T * γ +1 P (τ ≥ T ) ≤ T * γ + T =T * γ +1 exp - 1 2σ 2 T (α) (µ 1 -µ 2 ) -2σ 2 T (α)β(T, δ) 2 ≤ T * γ + ∞ T =T * γ +1 exp - 1 2σ 2 T (α) γ 2 (µ 1 -µ 2 ) 2 .
For all t ∈ N * , it is easy to show that the following upper bound on σ 2 t (α) holds:

∀t ∈ N, σ 2 t (α) ≤ (σ 1 + σ 2 ) 2 t × t -σ 1 σ 2 t -σ 1 σ 2 -1 . ( 11
)
Using the bound (11), one has

E ν [τ ] ≤ T * γ + ∞ 0 exp - t 2(σ 1 + σ 2 ) 2 t -σ 1 σ 2 -1 t -σ 1 σ 2 γ 2 (µ 1 -µ 2 ) 2 dt = T * γ + 2(σ 1 + σ 2 ) 2 γ 2 (µ 1 -µ 2 ) 2 exp γ 2 (µ 1 -µ 2 ) 2 2(σ 1 + σ 2 ) 2 .
We now give an upper bound on T * γ . Let r ∈ [0, e/2 -1]. There exists N 0 (r) such that for t ≥ N 0 (r), β(t, δ) ≤ log(t 1+r /δ). Using also (11), one gets T * γ = max(N 0 (t), Tγ ), where

Tγ = inf t 0 ∈ N : ∀t ≥ t 0 , (µ 1 -µ 2 ) 2 2(σ 1 + σ 2 ) 2 (1 -γ) 2 t > t -σ 1 σ 2 -1 t -σ 1 σ 2 log t 1+r δ .
If t > (1 + γ σ 1 σ 2 )/γ one has (t -σ 1 σ 2 -1)/(t -σ 1 σ 2 ) ≤ (1 -γ) -1 . Thus Tγ = max((1 + γ σ 1 σ 2 )/γ, T γ ), with

T γ = inf t 0 ∈ N : ∀t ≥ t 0 , exp (µ 1 -µ 2 ) 2 2(σ 1 + σ 2 ) 2 (1 -γ) 3 t ≥ t 1+r δ .
The following Lemma, whose proof can be found below, helps us bound this last quantity.

Lemma 14 For every β, η > 0 and s ∈ [0, e/2], the following implication is true:

x 0 = s β log e log (1/(β s η)) β s η ⇒ ∀x ≥ x 0 , e βx ≥ x s η .

Applying Lemma 14 with η = δ, s = 1 + r and

β = (1 -γ) 3 (µ 1 -µ 2 ) 2 2(σ 1 + σ 2 ) 2
leads to

T γ ≤ (1 + r) (1 -γ) 3 × 2(σ 1 + σ 2 ) 2 (µ 1 -µ 2 ) 2 log 1 δ + log log 1 δ + R(µ 1 , µ 2 , σ 1 , σ 2 , γ, r), with R(µ 1 , µ 2 , σ 1 , σ 2 , γ, r) = 1 + r (1 -γ) 3 2(σ 1 + σ 2 ) 2 (µ 1 -µ 2 ) 2 1 + (1 + r) log 2(σ 1 + σ 2 ) 2 (1 -γ) 3 (µ 1 -µ 2 ) 2 .
Now for > 0 fixed, choosing r and γ small enough leads to

E ν [τ ] ≤ (1 + ) 2(σ 1 + σ 2 ) 2 (µ 1 -µ 2 ) 2 log 1 δ + log log 1 δ + C(µ 1 , µ 2 , σ 1 , σ 2 , ),
where C is a constant independent of δ. This concludes the proof.

Proof of Lemma 14 Lemma 14 easily follows from the fact that for any s, η > 0,

x 0 = s log   e log 1 η η   ⇒ ∀x ≥ x 0 , e x ≥
x s η Indeed, it suffices to apply this statement to x = xβ and η = ηβ s . The mapping x → e x -x s /η is increasing when x ≥ s. As x 0 ≥ s, it suffices to prove that x 0 defined above satisfies e x 0 ≥ x s 0 /η.

Appendix D. An Optimal Static Strategy for Bernoulli Bandit Models

Bounding the probability of error of a static strategy using n 1 samples from arm 1 and n 2 samples from arm 2 relies on the following Lemma, that applies more generally to exponential families.

Lemma 15 Let (X 1,t ) t∈N and (X 2,t ) t∈N be two independent i.i.d sequences, such that X 1,1 ∼ ν θ 1 and X 2,1 ∼ ν θ 2 belong to an exponential family. Assume that µ(θ 1 ) > µ(θ 2 ). Then

P 1 n 1 n 1 t=1 X 1,t < 1 n 2 n 2 t=1 X 2,t ≤ exp(-(n 1 + n 2 )g α (θ 1 , θ 2 )), (12)
where α = n 1 n 1 +n 2 and g α (θ 1 , θ 2 ) := αK(αθ 1 + (1 -α)θ 2 , θ 1 ) + (1 -α)K(αθ 1 + (1 -α)θ 2 , θ 2 ).

The function α → g α (θ 1 , θ 2 ), can be maximized analytically, and the value α * that realizes the maximum is given by

K(α * θ 1 + (1 -α * )θ 2 , θ 1 ) = K(α * θ 1 + (1 -α * )θ 2 , θ 2 ) α * θ 1 + (1 -α * )θ 1 = θ * α * = θ * -θ 2 θ 1 -θ 2
where θ * is defined by K(θ * , θ 1 ) = K(θ * , θ 2 ) = K * (θ 1 , θ 2 ). More interestingly, the associated rate is such that g α * (θ 1 , θ 2 ) = α * K(θ * , θ 1 ) + (1 -α * )K(θ * , θ 2 ) = K * (θ 1 , θ 2 ), which leads to Proposition 6.

Figure 1 :

 1 Figure 1: Comparison of different information terms in Bernoulli bandit models.

Figure 2 :

 2 Figure 2: Experimental results (descriptions in text; plots best viewed in color).

c 2014 E. Kaufmann, O. Cappé & A. Garivier.

Acknowledgments

We thank Sébastien Bubeck for fruitful discussions during the visit of the first author at Princeton University. This work was supported by the ANR-2010-COSI-002 grant of the French National Research Agency.

Appendix A. Proof of Lemma 8: Changes of Distributions

Under the identifiability assumption, there exists a common measure λ such that for all ν = (ν 1 , ν 2 ), for all a ∈ {1, 2} ν a has a density f a with respect to λ.

Let ν ∈ M be a bandit model, and consider an alternative bandit model ν ∈ M. f a , f a are the densities of ν a , ν a respectively and one can introduce the log-likelihood ratio of the observations up to time t under an algorithm A:

The key element in a change of distribution is the following classical lemma (whose proof is omitted) that relates the probabilities of an event under P ν and P ν through the log-likelihood ratio of the observations. Such a result has often been used in the bandit literature for ν and ν that differ just from one arm (either ν 1 = ν 1 or ν 2 = ν 2 ), for which the expression of the log-likelihood ratio is simpler. As we will see, here we consider more general changes of distributions.

Lemma 10 Let σ be any stopping time with respect to F t . For every event

Let τ be the stopping rule of algorithm A. We start by showing that for all A ∈ F τ , P ν (A) = 0 if and only if P ν (A) = 0. Thus, if 0 < P ν (A) < 1 one also has 0 < P ν (A) < 1 and the quantity d(P ν (A), P ν (A)) in the statement of Lemma 8 is well defined. Let A ∈ F τ . Lemma 10 yields P

We now prove Lemma 8. Let A ∈ F τ be such that 0 < P ν (A) < 1. Then 0 < P ν (A) < 1. Lemma 10 and the conditional Jensen inequality leads to

Writing the same for the event

.

Therefore one can write

Introducing (Y a,t ), the sequence of i.i.d. samples successively observed from arm a, the loglikelihood ratio L t can be rewritten

Applying Wald's Lemma (see for example [START_REF] Siegmund | Sequential Analysis[END_REF]) to L τ = 2 a=1 Na t=1 log fa(Ya,t) f a (Ya,t) , where N a = N a (τ ) is the total number of draws of arm a, yields

which concludes the proof together with inequality (8).

Appendix B. Proof of Lemma 9: An Optimal Confidence Region

We start by stating three technical lemmas, whose proofs are partly omitted.

Lemma 11 For every η > 0, every positive integer k, and every integer t such that

Appendix C. Proof of Theorem 4

Let α = σ 1 /(σ 1 + σ 2 ). We first prove that with the exploration rate β(t, δ) = log(t/δ)+2 log log(6t) the algorithm is δ-PAC. Assume that µ 1 > µ 2 and recall τ = inf{t ∈ N :

The probability of error of the α-elimination strategy is upper bounded by

which shows that uniform sampling matches the lower bound of Theorem 2.

Proof of Lemma 15 The i.i.d. sequences (X 1,t ) t∈N and (X 2,t ) t∈N have respective densities

For every λ > 0, multiplying by λ, taking the exponential of the two sides and using Markov's inequality (this technique is often referred to as Chernoff's method), one gets

n with φ X (λ) = log E ν [e λX ] for any random variable X. If X ∼ f θ a direct computation gives φ X (λ) = b(λ + θ) -b(θ). Therefore the function G α (λ) introduced above rewrites

Using that b (x) = µ(x), we can compute the derivative of G and see that this function as a unique minimum in λ * given by

Using the expression of the KL-divergence between ν θ 1 and ν θ 2 as a function of the natural parameters: Summing these two equalities leads to G(λ * ) = -[αK(αθ 1 + (1 -α)θ 2 , θ 1 ) + (1 -α)K(αθ 1 + (1 -α)θ 2 , θ 2 )] = -g α (θ 1 , θ 2 ).

Hence the inequality P 1

t=1 X 2,t ≤ exp(G(λ * )n) is exactly (12).


Ph.D Loïc Harrault
email: loic.harrault@gmail.com

Emilie Jardé

Laurent Jeanneau

Patrice Petitjean

Are fecal stanols suitable to record and identify a pulse of human fecal contamination in short-term exposed shellfish? A microcosm study

Keywords: Oyster, Fecal contaminationSeawaterFecal stanolsPersistenceMicrocosms Oyster, fecal contamination, seawater, fecal stanols, persistence, microcosms

In this study, the capacity of oysters to bioaccumulate fecal stanols and to record a sourcespecific fingerprint was investigated by the short-term contamination of seawater microcosms containing oysters with a human effluent. Contaminated oysters bioaccumulated the typical fecal stanols coprostanol and 24-ethylcoprostanol and their bioaccumulation kinetics were similar to that of the Fecal Indicator Bacteria Escherichia coli used in European legislation. Although stanol fingerprints of contaminated water allowed the identification of the human specific fingerprint, this was not the case for oysters. This discrepancy is attributed to i) high concentrations of endogenous cholestanol and sitostanol, responsible for "unbalanced" stanol fingerprints, ii) different accumulation/depuration kinetics of fecal coprostanol and 24-ethylcoprostanol and iii) the limits of the analytical pathway used. These results show that fecal stanols bioaccumulated by oysters are useful to record fecal contamination but the usefulness of stanol fingerprints to identify specific sources of contamination in shellfish currently seems limited.

Highlights:

-Oysters were fecally-contaminated with human wastewater in seawater microcosms.

-Stanol concentrations and fingerprints were analyzed in both the water and oysters.

-Fecal stanols coprostanol and 24-ethylcoprostanol were bioaccumulated by the oysters.

-The human-specific stanol fingerprint of water was not transferred to the oysters.

Introduction

In coastal environments, shellfish can bioaccumulate pathogenic micro-organisms associated with human and animal fecal contamination originating from the watershed [START_REF] Fong | Enteric viruses of humans and animals in aquatic environments: health risks, detection, and potential water quality assessment tools[END_REF]Hundesa et al, 2005;[START_REF] Riou | Microbial impact of small tributaries on water and shellfish quality in shallow coastal areas[END_REF][START_REF] Soller | Risk-based evaluation of Escherichia coli monitoring data from undisinfected drinking water[END_REF]. This type of fecal contamination can result in sanitary risks due to the consumption of contaminated shellfish and has led European authorities to impose a shellfish classification based on the fecal indicator bacteria (FIB) Escherichia coli (E. coli, European Shellfish Directive 91/492/CEE).

In addition, the European Shellfish Directive on shellfish harvesting (854/2004/EC) requires the identification of potential sources of fecal contamination in these environments.

Since E. coli is not source-specific, microbial source tracking methods were developed combining microbial and chemical markers to identify the sources of fecal pollution [START_REF] Simpson | Microbial Source Tracking: State of the Science[END_REF][START_REF] Glassmeyer | Transport of Chemical and Microbial Compounds from Known Wastewater Discharges: Potential for Use as Indicators of Human Fecal Contamination[END_REF][START_REF] Blanch | Integrated analysis of established and novel microbial and chemical methods for microbial source tracking[END_REF]Vogel et al., 2007;[START_REF] Gourmelon | Application of library-independent microbial source tracking methods for identifying the sources of faecal contamination in coastal areas[END_REF]. These methods have been successfully used in several environmental matrices (e.g. water, soil, and sediment), but they remained poorly applied to shellfish and in these latter cases, they only involved microbial markers [START_REF] Vantarakis | Hybridisation of F+ RNA coliphages detected in shellfish samples with oligonucleotide probes to assess the origin of microbiological pollution of shellfish[END_REF]Wolf et al., 2010;[START_REF] Mieszkin | Identification of the origin of faecal contamination in estuarine oysters using Bacteroidales and F-specific RNA bacteriophage markers[END_REF]. Consequently, chemical markers have not yet been applied to directly identify the sources of fecal contamination in shellfish.

Fecal stanols are direct chemical markers from animal feces. Their distribution in feces depends on i) the animal's diet, ii) the ability of animals to biosynthesize endogenous sterols and iii) the composition of the intestinal flora responsible for sterol biohydrogenation into stanols [START_REF] Leeming | Using faecal sterols from humans and animals to distinguish faecal pollution in receiving waters[END_REF]. This species-specific distribution, called the "stanol fingerprint" has been successfully used, via the analysis of stanol ratios or by multivariate analyses, to distinguish between human and animal fecal contamination in water, soil, and sediment [START_REF] Bull | The origin of faeces by means of biomarker detection[END_REF]Jardé et al., 2007;[START_REF] Shah | Evaluating potential applications of faecal sterols in distinguishing sources of faecal contamination from mixed faecal samples[END_REF][START_REF] Jardé | Tracing and Quantifying Sources of Fatty Acids and Steroids in Amended Cultivated Soils[END_REF][START_REF] Tyagi | Distinguishing between human and animal sources of fecal pollution in waters: a review[END_REF][START_REF] Gourmelon | Application of library-independent microbial source tracking methods for identifying the sources of faecal contamination in coastal areas[END_REF][START_REF] Derrien | Extreme variability of steroid profiles in cow feces and pig slurries at the regional scale: implications for the use of steroids to specify fecal pollution sources in waters[END_REF], 2012;[START_REF] Biache | The use of sterol distributions combined with compound specific isotope analyses as a tool to identify the origin of fecal contamination in rivers[END_REF]. Moreover, stanols are sufficiently persistent in the environment to be transferred from the watershed to seawater where the shellfish are living [START_REF] Solecki | Persistence of microbial and chemical pig manure markers as compared to faecal indicator bacteria survival in freshwater and seawater microcosms[END_REF][START_REF] Jeanneau | Relative decay of fecal indicator bacteria and human-associated markers: a microcosm study simulating wastewater input into seawater and freshwater[END_REF].

In shellfish, studies that investigated the use of fecal stanols to track human contamination focused on the human-associated coprostanol [START_REF] Sherwin | Coprostanol (5β-cholestan-3β-ol) in lagoonal sediments and mussels of Venice, Italy[END_REF][START_REF] Cathum | Determination of steroids and coprostanol in surface water, effluent and mussel using gas chromatography-mass spectrometry[END_REF][START_REF] Gagné | Evidence of coprostanol estrogenicity to the freshwater mussel Elliptio complanata[END_REF][START_REF] Gagné | Biomarker study of a municipal effluent dispersion plume in two species of freshwater mussels[END_REF][START_REF] Hellou | Chemical contaminants and biological indicators of mussel health during gametogenesis[END_REF]Yeats et al., 2008), but the usefulness of the stanol fingerprint to identify human-specific contamination remains unknown. Recently, [START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF] applied the principal component analysis (PCA) model developed by [START_REF] Derrien | Extreme variability of steroid profiles in cow feces and pig slurries at the regional scale: implications for the use of steroids to specify fecal pollution sources in waters[END_REF] to oysters collected in Brittany, which can be used to distinguish between human, porcine and bovine fecal contamination in water in Brittany [START_REF] Derrien | Origin of fecal contamination in waters from contrasted areas: stanols as Microbial Source Tracking markers[END_REF]. [START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF] found that oysters fecally contaminated by the FIB E. coli presented a specific bovine fingerprint while non-contaminated oysters have no specific fingerprint. However, the transfer of a specific stanol fingerprint from the surrounding water to oyster tissue, in controlled conditions, has not been yet investigated and their persistence has not been compared to that of E. coli which are requirements for using them as reliable markers to identify sources of fecal contamination [START_REF] Blanch | Integrated analysis of established and novel microbial and chemical methods for microbial source tracking[END_REF].

The present study was conducted to evaluate these issues. In an experimental design conducted in microcosms, the persistence of selected stanols was compared to that of the FIB E. coli in seawater initially contaminated with wastewater treatment plant (WWTP) influent and in oysters. In addition, under these experimental conditions, the efficiency of the stanol ratios and Derrien et al.'s (2011) PCA model were investigated to track the human-specific contamination of water and oysters exposed to a short-term contamination.

Material and methods

Reagent and chemicals

Organic solvents were of high performance liquid chromatography (HPLC) grade. Dichloromethane (DCM) was purchased from Carlo-Erba SDS (Val de Reuil, France), methanol (MeOH), isopropanol, hydrochloric acid 37% and cyclohexane were purchased from VWR (West Chester, PA). N,O-bis-(trimethylsilyl)trifluoroacetamide and trimethylchlorosilane (99/1, v/v) (BSTFA + TMCS) and SPE disks (Supelco ENVI-18DISK, 47 mm in diameter) were purchased from Supelco (St. Quentin Fallavier, France).

Coprostanol (5β-cholestan-3β-ol), cholestanol (5α-cholestan-3β-ol), 5α-cholestane and anhydrous magnesium sulfate (MgSO 4 ) were purchased from Sigma (St. Quentin Fallavier, France). Sitostanol (24-ethyl-5α-cholestan-3β-ol) was purchased from Steraloids (Newport, United States). and 24-ethylepicoprostanol (24-ethyl-5β-cholestan-3α-ol) were purchased from BCP Instruments (Irigny, France). Silica gel (40-63 µm) was purchased from Merck (Darmstadt, Germany). Cholesterol d 6 ([2,2,3,4,4,6-2 H 6 ]-cholest-5-en-3β -ol) was purchased from CDN Isotopes (Pointe-Claire, Canada).

Incubations and sampling

Five-hundred and sixteen oysters (Crassostrea gigas) were purchased in Cancale (France), 200 L of seawater was sampled at Dinard (France) and 30 L of raw WWTP sewage was sampled at Acigné (France) in January 2013. In the laboratory, oysters were placed in 43 11-liter plastic boxes (39.5 × 26.5 × 15.6 cm, L × l × h) pre-washed with distilled water and ethanol to remove any plasticizers. Twelve oysters were submerged in each box filled with 4 L of unfiltered seawater. This volume corresponds to more than 300 mL of seawater per oyster, which is necessary for their survival in controlled conditions [START_REF] Mauffret | Recent innovation in microbial source tracking using bacterial real-time PCR markers in shellfish[END_REF].

Batches were continuously oxygenated using aquarium pumps and kept in the dark to avoid phytoplankton development and photodegradation of the organic compounds. At the beginning of the experiment, oysters were allowed to acclimate to laboratory conditions for 72 h [START_REF] Charles | Filtration of the enteric bacteria Escherichia coli by two filter-feeding bivalves, Venus verrucosa and Mytilus galloprovincialis[END_REF].

The experiment began by diluting the raw WWTP sewage to 10% ("10%" treatment thereafter) in 18 batches and 20% ("20%" treatment thereafter) in 18 other batches. The remaining batches without WWTP sewage addition were used as blanks. Except at the beginning of the experiment (0h), 1 "blank" batch and 3 batches (triplicates) for both the "10%" and "20%" treatments were sampled at each sampling time. At 0h, oysters sampled from the "blank" batch were considered as 0h samples for the "blank", "10%" and "20%" treatments. The water and oysters were sampled at 1h, 6h, 24h, 48h, 196h (8 days) and 332h (14 days) after the start of the experiment. At each sampling time, the 12 oysters from the sampled batches were collected for E. coli and stanol analyses and 2.5 L of the water was sampled for E. coli and chemical analyses including dissolved organic carbon analysis, suspended particulate matter concentrations, and dissolved stanol analyses. Results for the "10%" and "20%" treatments are the means of the three replicates.

Physico-chemical parameters

Suspended particulate matter concentrations were determined by filtrating the water samples through pre-weighted glass-fiber filters at 0.7 µm. Filters were freeze-dried and weighed to determine the particle concentrations. Dissolved organic carbon concentrations were determined on filtered (0.7 µm) water samples using a Shimadzu TOC 5050 total carbon analyzer (Noisiel, France). Dissolved oxygen, pH, salinity and temperature were measured throughout the experiment using a multisensor probe (WTW, Ales, France).

Escherichia coli analysis

The concentration of the FIB E. coli was determined by the CVPA laboratory (Saint-Malo, France) using culture methods (NF EN ISO 9308-3 for the water and NF V08 600 for the oysters). These methods required 500 mL of the water samples and six living oysters. Due to technical constraints, E. coli counts were limited to an upper limit of 4.5 log 10 colony forming units (log CFU) per 100 mL for the water and 4.2 log CFU per 100 g of flesh for the oysters.

Stanol extraction and analysis

Water

Solid phase extractions (SPE) were performed to extract fecal stanols from filtered (0.7 µm glass-fiber) water samples as described by [START_REF] Jeanneau | Influence of salinity and natural organic matter on the solid phase extraction of sterols and stanols: application to the determination of the human sterol fingerprint in aqueous matrices[END_REF]. Briefly, known amounts of the recovery standard cholesterol d 6 were added to 1 L of filtered water samples before adjusting its pH to 1 with a 1 M hydrochloric acid solution and the addition of 100 mL of isopropanol. Then, the mixture was passed through pre-washed (DCM) and activated (MeOH) SPE disks. Stanols bound to the disk were eluted with DCM and analyzed by gas chromatography-mass spectrometry (GC-MS).

Oysters

Stanols from oyster tissue were extracted and analyzed as described by [START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF]. Briefly, the oyster flesh (about 4 g dry weight, DW) was freeze-dried and ground and the total lipids were extracted using an Accelerated Solvent Extractor (ASE 200,Dionex,Courtaboeuf,France) with DCM. Then, the total lipids were fractionated on silica gel columns into an apolar fraction eluted with a mixture of cyclohexane/DCM (2/1, v/v) and a stanol-containing polar fraction eluted with a mixture of DCM/MeOH (1/1, v/v).

Stanol analysis using gas chromatography-mass spectrometry (GC-MS)

Stanols extracted from the water and oyster samples were derivatizated using a mixture of BSTFA + TMCS (99/1, v/v) at 60°C for 20 minutes to convert hydroxyl groups into trimethylsilyl (TMS) ether groups. Derivatizated stanols were then analyzed by GC-MS with a Shimadzu QP2010 + MS gas chromatograph/mass spectrometer (Shimadzu, Tokyo, Japan) with electron ionization at 70 eV. Separation was achieved using a fused silica column coated with SLB-5 MS (Supelco, 60 m, i.d. 0.25 mm, film thickness 0.25 µm) with helium as a carrier gas at a flow of 1 ml min -1 . The GC oven temperature was maintained at 70°C for 1 min, then increased to 130°C at 15 °C min -1 , then to 300°C at 3°C min -1 and held at this temperature for 15 min. Analyses were performed in SIM (selective ion monitoring) mode.

Quantification was based on the internal standard (5α-cholestane) method and a five-point calibration curve was used (standards: coprostanol, epicholestanol, epicoprostanol, cholestanol and sitostanol). The limits for the quantifications were 0.1 µg/L for the water and 5 µg/g DW for the oysters.

Stanol ratios

In order to investigate the usefulness of fecal stanols to record a specific human contamination in water and shellfish, three ratios for the fecal stanol concentrations were used:

-. With R1 considered as specific from human contamination when > 0.50 [START_REF] Shah | Evaluating potential applications of faecal sterols in distinguishing sources of faecal contamination from mixed faecal samples[END_REF]Furtula et al., 2012 and references therein).

-. With R2 considered as specific from human contamination when > 0.73 (Leeming et al., 1997, Furtula et al., 2012 andreferences therein).

-. With R3 considered as specific from human contamination when < 0.20 [START_REF] Gourmelon | Application of library-independent microbial source tracking methods for identifying the sources of faecal contamination in coastal areas[END_REF].

Statistical analyses

Statistical analyses were performed using the R software (2.15.3, http://www.rproject.org/). Two-way ANOVAs, with treatment and time as explanatory variables, were performed to compare the evolution of the stanol concentrations in water and oysters between treatments. When the "10%" and/or "20%" treatments had a significant effect on the concentrations compared to the blank, post-hoc Tukey's tests were performed to compare one treatment to another. Data were log-transformed when necessary to normalize distributions and homogenize variances. A significant threshold of p < 0.05 was chosen for all analyses.

Stanol fingerprints of the water and oysters were investigated using the PCA model set up by [START_REF] Derrien | Extreme variability of steroid profiles in cow feces and pig slurries at the regional scale: implications for the use of steroids to specify fecal pollution sources in waters[END_REF]) with XLSTAT 2013 (Addinsoft, Paris, France). Briefly, this model is based on the distribution of six main fecal stanols (i.e., coprostanol, epicoprostanol, 24ethylcoprostanol, 24 ethylepicoprostanol, campestanol, and sitostanol) from 88 various samples of bovine, porcine (feces, manures, slurries, etc.) and human origin (raw and diluted waste water treatment plant effluent, sewage sludge). With 78.3% of the total variance explained by the first two components, this model distinguishes stanol fingerprints from the three previous origins into three distinctive clusters, allowing the identification of the origin of fecal contamination in the environmental matrix between bovine, porcine and human contamination. Each source sample was used as an individual and the water and oyster samples were used as supplementary individuals.

Results

Physico-chemical parameters of water

The mean values of the physico-chemical parameters of water throughout the experiment are presented in Table 1. The dissolved oxygen, pH, temperature and suspended particulate matter concentration remained similar between all treatments over time. The different dilution factors between seawater and WWTP sewage in the "10%" and "20%" batches resulted in decreasing salinity and increasing dissolved organic carbon concentrations in water from the "blank" up to the "20%" batches.

Escherichia coli concentrations

Water

The concentration of E. coli in the seawater and raw WWTP effluent was respectively 1.7 and 7.3 log CFU/100 mL (Supplementary Table 1). Except at 1h after the start of the experiment (2.8 log CFU/100 mL), the concentration of E. coli in the non-contaminated water sample remained lower than the European threshold indicative of fecal contamination (2.7 log CFU/100 mL, Figure 1a). Until 48h after the start of the artificial contamination, the concentration of E. coli in the "10%" and "20%" water samples (4.5 ± 0.0 log CFU/100 mL) was higher than 2.7 log CFU/100 mL. Then their concentrations decreased below 2.7 log CFU/100 mL to reach low levels of contamination with 2.3 ± 0.2 log CFU/100 mL at 196h and 1.2 ± 0.0 log CFU/100 mL at 332h for the "10%" water samples and 1.8 ± 0.3 log CFU/100 mL at 196h and 1.3 ± 0.3 log CFU/100 mL at 332h for the "20%" water samples (Figure 1a).

Oysters

The "blank" oysters were not fecally contaminated since their concentrations of E. coli were below the limit of quantification for the method used, except at 48h with a concentration of 2.5 log CFU/100 g, which remained lower than the European threshold indicative of fecal contamination of shellfish (3.7 log CFU/100 g, Figure 1b). At the start of the experiment, the "10%" and "20%" oysters were not fecally contaminated (below the limit of quantification for both, Figure 1b) but from 1h to 48h, they were both highly contaminated since their concentration of E. coli was higher than 3.7 log CFU/100 g (4.2 ± 0.0 log CFU/100 g for both treatments, Figure 1b). Then, the concentration of E. coli in the "10%" oysters decreased below the contamination threshold at 196h (3.0 ± 0.4 log CFU/100 g) until 332h (2.8 ± 0.4 log CFU/100 g). The concentration of E. coli in the "20%" oysters decreased below the contamination threshold at 196h (3.3 ± 0.3 log CFU/100 g) and increased at the end of the experiment to reach 3.5 ± 0.1 log CFU/100 g at 332h.

Stanol concentrations

This section presents the temporal concentration variations in water and oysters of four particularly interesting stanols (Figure 2): coprostanol, 24-ethylcoprostanol, cholestanol and sitostanol. Coprostanol and 24-ethylcoprostanol were chosen because they are the two main fecal stanols of WWTP sewage (71% and 15% of the total stanols, respectively, Supplementary Table 1) and thus are used as qualitative biomarkers of human fecal contamination. Cholestanol and sitostanol were chosen because they are the main stanols in the oysters quantified in this study (Supplementary Table 3). Individual concentrations of all stanols quantified in the water and oysters are presented in Supplementary Tables 2 and3, respectively.

Water

On average throughout the experiment, the addition of WWTP sewage in seawater had a significant effect on the concentration of coprostanol, 24-ethylcoprostanol, cholestanol and sitostanol in water (treatment effect: p < 0.0001 for the four compounds, Figure 2a, b, c, d):

"blank" concentrations were lower than the "10%" ones (Tukey tests: p < 0.0001 for the four compounds), which were lower than the "20%" ones (Tukey tests: p < 0.0001, p < 0.001, p < 0.01 and p < 0.0005, respectively).

In non-contaminated water, the concentration of coprostanol, 24-ethylcoprostanol, cholestanol and sitostanol slightly varied over time and remained below 0.14, 0.45, 1.83 and 0.12 µg/L, respectively (Figure 2a,b,c,d).

On the contrary, the concentration of these four compounds in the "10%" and "20%"

water batches had high temporal variations which occurred at three different rates (time effect: p < 0.0001 for the four compounds, Figure 2a,b,c,d): on average, their concentrations first increased by 951% until 48h, then decreased by 95% until 196h and finally stabilized until 332h (Supplementary Table 2).

Oysters

Throughout the whole experiment, the concentration of both coprostanol and 24ethylcoprostanol in the "10%" and "20%" oysters were on average higher than those of the "blank" oysters (treatment effect: p = 0.002 and p = 0.025, respectively) but there was no significant dose effect between the "10%" and "20%" treatments (Tukey: p = 0.49 and p = 0.61, respectively; Table 2e, f; Supplementary Table 3). In addition, the kinetics of these two compounds were quite similar (time effect: p < 0.0001 for the four modalities): their mean concentration increased by 154% from 0h to 24h or 48h and then decreased by 38% until 332h.

Throughout the whole experiment, cholestanol was by and large the main stanol in the oyster tissue (ca. 450 µg/g DW and ca. 80% of the total stanols, Supplementary Table 3) and its concentrations exhibited high standard deviations (i.e. 17% of the mean relative standard deviation). Moreover, the concentration of cholestanol in oysters for the three treatments did not follow a specific trend (time effect: p = 0.84, Figure 2g) and was similar among the treatments (treatment effect: p = 0.42).

The sitostanol concentration in oysters tended to increase from the start until the end of the experiment (time effect: p < 0.0001, 36.05 µg/g DW at 0h to ca. 80 µg/g DW at 332h, Figure 2h) but did not differ between non-contaminated and contaminated microcosms (treatment effect: p = 0.26).

Stanol fingerprints

Water

The maximum values for the R1 and R2 ratios in "blank" water were respectively 0.16 and 0.28 at 6h, which remains below the thresholds indicative of a major human contamination (0.50 for R1, 0.73 for R2, respectively; Figures 3a,b). Similarly, the minimum value for the R3 ratio in "blank" water was 0.50 at 332h, which remains above the 0.20 threshold indicative of a major human contamination (Figure 3c).

The R1 ratio value for "10%" and "20%" water decreased from 0h to 6h (from 16.53 to 2.35 ± 0.83 and 9.53 to 4.96 ± 1.40, respectively), then respectively increased to 4.04 ± 0.29 until 48h and to 6.13 ± 0.38 until 24h, greatly decreased to 0.34 ± 0.07 and 0.37 ± 0.07 until 196h and finally decreased to 0.09 ± 0.04 and 0.04 ± 0.00 until 332h.

The R2 ratio value for "10%" water decreased from 0h (0.90) to 6h (0.76 ± 0.03), then increased to 0.83 ± 0.01 until 48h and finally decreased to 0.21 ± 0.08 until 332h. The R2 ratio value for "20%" water decreased from 0h (0.87) to 6h (0.82 ± 0.00), then remained constant until 48h and finally decreased to 0.10 ± 0.02 until 332h.

For "10%" and "20%" water, the R3 ratio values increased from 0h (0.02 and 0.01, respectively) to 1h (0.10 ± 0.03 and 0.05 ± 0.01, respectively), then both slightly decreased to 0.03 ± 0.00 until 48h, slightly increased to respectively 0.26 ± 0.02 and 0.22 ± 0.02 until 196h

and finally greatly increased to 1.71 ± 0.50 and 3.07 ± 0.54, respectively, until 332h.

The projections of the stanol fingerprints for the "10%" and "20%" water onto the 2D plane of the PCA developed by [START_REF] Derrien | Extreme variability of steroid profiles in cow feces and pig slurries at the regional scale: implications for the use of steroids to specify fecal pollution sources in waters[END_REF] were located in the human cluster during the whole course of the experiment (Figure 4).

Oysters

The values of the R1 ratio for the "blank", "10%" and "20%" oysters were lower than 0.03 ± 0.02 and therefore remained under the threshold of 0.50 indicative of human contamination (Figure 3d). Moreover, they did not greatly vary over time and, on average, did not differ (mean values for the three treatments: 0.02 ± 0.00).

The values of the R2 ratio for the "blank", "10%" and "20%" oysters were lower than 0.52 ± 0.03 and remained below the threshold of 0.73 indicative of human contamination (Figure 3e). In addition, they remained stable over time and were not different on average (mean values: 0.49 ± 0.03 for "blank" oysters, 0.51 ± 0.02 for "10%" oysters and 0.51 ± 0.02 for "20%" oysters).

Similarly, the values of the R3 ratio for the "blank", "10%" and "20%" oysters remained largely above the threshold of 0.20 (minimum value: 1.78) and were consequently not indicative of human contamination (Figure 3f). They did not differ between treatments and increased by 243% from the start to the end of the experiment.

In the PCA model developed by [START_REF] Derrien | Extreme variability of steroid profiles in cow feces and pig slurries at the regional scale: implications for the use of steroids to specify fecal pollution sources in waters[END_REF], stanol fingerprints of oysters from the "blank", "10%" and '20% treatments were not specifically located in the human cluster, but between the human and bovine clusters (Figure 4).

Discussion

4.1.

Comparison between E. coli and fecal stanol kinetics 4.1.1. Water

According to the European legislation on recreational water based on the E. coli concentration, the level of fecal contamination for "10%" and "20%" water decreased from highly contaminated levels until 48 hours to non-contaminated levels from 8 to 14 days. This pattern is in agreement with the patterns presented by [START_REF] Jeanneau | Relative decay of fecal indicator bacteria and human-associated markers: a microcosm study simulating wastewater input into seawater and freshwater[END_REF], who observed the highest E. coli decay rate between 2 and 6 days of incubation followed by a lower decay rate until 13 days in seawater microcosms contaminated with a WWTP effluent, but without oysters. This reduction could be due to the sedimentation of E. coli associated with particles and/or predation by bacteriophage protozoans (Marty et al., 1995;[START_REF] Solecki | Persistence of microbial and chemical pig manure markers as compared to faecal indicator bacteria survival in freshwater and seawater microcosms[END_REF].

The initial increase observed in the fecal stanol concentrations might be the result of i) the release of hydrophobic dissolved stanols from particles to water or ii) the exo-enzymatic hydrolysis of ester-bonded stanols by bacteria [START_REF] Thoumelin | laboratory investigation of the degradation of organic-matter in estuarine and coastal waters -sterols variations[END_REF]Marty et al., 1995).

Similarly to the E. coli concentrations, there was a high decrease for fecal stanols in water between 2 and 8 days, like in the study by [START_REF] Jeanneau | Relative decay of fecal indicator bacteria and human-associated markers: a microcosm study simulating wastewater input into seawater and freshwater[END_REF], who attributed this decrease to a combination of processes such as biodegradation and sedimentation.

These results shows that in these experimental conditions mimicking a short-term exposure to a human effluent, FIB E. coli and stanol markers in water are mainly degraded and/or removed during the course of the experiment (14 days).

Oysters

As previously observed in studies that investigated the kinetics of E. coli bioaccumulation by shellfish [START_REF] Selegean | Using zebra mussels to monitor Escherichia coli in environmental waters[END_REF][START_REF] Jozic | The accumulation of the indicator bacteria Escherichia coli in mussels (Mytilus galloprovincialis) and oysters (Ostrea edulis) under experimental conditions[END_REF], oysters contaminated with WWTP effluent bioaccumulated E. coli within 1 hour in the present study. Escherichia coli concentrations in oysters remained higher than the European regulatory value until 2 days and then decreased below this value until 8 days. Escherichia coli concentrations remained relatively high in the contaminated oysters compared to the blanks until the end of the experiment while the contaminated water finally decreased to the blank values. These results are in agreement with those of [START_REF] Selegean | Using zebra mussels to monitor Escherichia coli in environmental waters[END_REF] who conducted a similar experiment but on freshwater mussels contaminated by a WWTP effluent. Moreover, these results suggest that under these experimental conditions, the depuration process leading to the elimination of E. coli by defecation and lysozomal digestion of microorganisms [START_REF] Mchenery | The occurrence of lysozyme in marine bivalves[END_REF][START_REF] Power | Differential depuration of poliovirus, Escherichia coli, and a coliphage by the common mussel, Mytilus edulis[END_REF][START_REF] Love | Removal of Escherichia coli, Enterococcus fecalis, coliphage MS2, poliovirus, and hepatitis A virus from oysters (Crassostrea virginica) and hard shell clams (Mercinaria mercinaria) by depuration[END_REF]) from oyster tissues is not yet finished after 2 weeks. This depuration time is longer than those observed in depuration experiments in which fecally-contaminated oysters were allowed to depurate from E. coli in non-contaminated seawater [START_REF] Buisson | Bacterial depuration of the pacific oyster (Crassostrea gigas) in New-Zealand[END_REF]Doré and Lees, 1995;[START_REF] Selegean | Using zebra mussels to monitor Escherichia coli in environmental waters[END_REF][START_REF] Pommepuy | Evaluation of viral shellfish depuration in a semi-professional tank[END_REF][START_REF] Love | Removal of Escherichia coli, Enterococcus fecalis, coliphage MS2, poliovirus, and hepatitis A virus from oysters (Crassostrea virginica) and hard shell clams (Mercinaria mercinaria) by depuration[END_REF], while in our experiment, oysters remained in fecally-contaminated water until ca. 6 days (Figure 1a). However, a comparison of the depuration kinetics observed here and in the previous studies should be considered cautiously since the depuration kinetics of shellfish are highly dependent on the species studied and on the experimental parameters such as water temperature, salinity, dissolved oxygen and particle concentrations and phytoplankton uptake [START_REF] Richards | Microbial purification of shellfish -a review of depuration and relaying[END_REF][START_REF] Pommepuy | Evaluation of viral shellfish depuration in a semi-professional tank[END_REF].

Among the four stanols focused upon in this study, two groups can be identified. The first comprises cholestanol and sitostanol: their concentration, and especially that of cholestanol, was naturally higher than that of the other stanols and remained high until the end of the experiment. Their respective reduction did not follow the pattern of E. coli. The second group comprises coprostanol and 24-ethylcoprostanol: their concentrations in oysters were lower than those of cholestanol and sitostanol and exhibited larger temporal variations. Moreover, their concentration in contaminated oysters followed quite similar patterns to that of E. coli: a first increase step several hours after contamination until 2 days followed by a decay step until 2 weeks. Although different in amplitude, the similarities between the kinetics of these two stanols and E. coli in oysters suggest that these compounds are indicative of the fecal contamination of oysters. Moreover, contrary to the E. coli concentration that did not reach its initial value after 2 weeks, the coprostanol and 24-ethylcoprostanol concentrations reached their respective initial values at the same time. This could be the result of a higher depuration efficiency of these compounds compared to that of E. coli.

4.2.

Implications for the use of fecal stanols as markers of human fecal contamination

Water

As suggested by Furtula et al. (2012), the identification of human fecal contamination from wastewater by the use of fecal stanol ratios is more effective when several ratios are used. In the present study, the three ratios and the PCA model used on water contaminated by WWTP sewage confirmed their human fingerprint. This reinforces the usefulness of these ratios and/or the model to identify human fecal contamination in water [START_REF] Derrien | Origin of fecal contamination in waters from contrasted areas: stanols as Microbial Source Tracking markers[END_REF][START_REF] Jeanneau | Relative decay of fecal indicator bacteria and human-associated markers: a microcosm study simulating wastewater input into seawater and freshwater[END_REF]Furtula et al., 2012 and references therein). However, the sensibility of these ratios and the PCA model appears to differ. The three ratio values remained characteristic of human fecal contamination up to 2 to 8 days, while the projection of the stanol fingerprint onto the 2D plane of the PCA model remained in the human cluster up to the end of the experiment. These differences are probably due to the higher sensibility of the three stanol ratios to coprostanol variations than the PCA model. Indeed, the ratios are each based on the variations of two fecal stanols comprising the major stanol coprostanol, while the PCA model is based on the distribution of six stanols and is consequently less sensitive to coprostanol variations [START_REF] Derrien | Extreme variability of steroid profiles in cow feces and pig slurries at the regional scale: implications for the use of steroids to specify fecal pollution sources in waters[END_REF].

Oysters

In oysters, the concentrations of coprostanol and 24-ethylcoprostanol, which are typical of feces and dominated the distribution of the raw WWTP effluent (Supplementary Table 1), were higher in contaminated oysters compared to non-contaminated ones (Figures 2e,f). The R1, R2 and R3 ratios and the PCA model applied to oysters could not be used to record a specific human fingerprint. Several assumptions can be put forward to explain these discrepancies. Firstly, the natural occurrence of cholestanol in oysters at high concentrations compared to that of coprostanol strongly decreased the relative importance of the latter with regards to the R1 ratio. As a consequence, the R1 values were much lower than the "human threshold", which makes this ratio inappropriate to identify a specific human fingerprint in oysters. Secondly, in terms of the R1 ratio, the natural occurrence of sitostanol in oysters at high concentrations compared to that of coprostanol meant that the R3 ratio was not able to identify a human fingerprint in oysters. In addition, the naturally high concentration of sitostanol in oysters compared to those of the other stanols used to build the PCA model (i.e. coprostanol, epicoprostanol, 24-ethylcoprostanol, 24-ethylepicoprostanol and campestanol) could produce PCA score plots for oysters that are primarily calculated from the sitostanol proportions, which makes the PCA model inadequate to identify a specific human fingerprint in oysters. Thirdly, the similar concentrations of both coprostanol and 24-ethylcoprostanol in oysters led to low values for the R2 ratio, which makes this ratio inappropriate to identify a specific human fingerprint in oysters. The similarity between the concentrations of these two compounds in oysters raises issues because in the surrounding contaminated water the concentration of coprostanol was at least three times higher than that of 24-ethylcoprostanol.

A first hypothesis could be that the assimilation and/or depuration processes of these two compounds by oysters do not follow similar kinetics, resulting in large shifts in the R2 values from the surrounding water to oyster tissue. A second hypothesis could be that the concentrations of 24-ethylcoprostanol in oysters might have been overestimated because of its coelution with several compounds during GC-MS analysis (see the Experimental section in [START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF]; in which case, the analytical pathway developed by [START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF], and especially the fractionation step, has to be improved.

In contrast to the present study, [START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF] found that oysters (C. gigas) sampled in a French bay presented a bovine fingerprint according to the currently used PCA model, which was in agreement with the activities of the surrounding watershed. The fact that oysters sampled in the field [START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF] had a specific stanol fingerprint and that oysters artificially contaminated in the present batch experiment did not could be due to different exposure times to fecal contamination. Indeed, the present study was designed to represent a short-term exposure to a pulse of pollution by a WWTP effluent and the fecal coprostanol concentration decreased after 2 days in contaminated water. This decrease might not have occurred if the batches were continuously filled with WWTP sewage in order to represent constant pollution and the ratio values for the oysters used here might have reached a "human" value if the oysters were continuously supplied with the fecal stanol coprostanol from the surrounding water. This assumption could be investigated in a further study where oysters are exposed to constant concentrations of fecal stanols. On this basis, the theoretical kinetics of R1 for the "20%" oysters was calculated by considering that the highest coprostanol accumulation rates (between 6h and 24h) remained constant over time if the WWTP sewage discharge was continuous in our experiment (Figure 2e). As the cholestanol concentration did not vary over time in the "20%" oysters (Figure 2g), its concentration was considered as being constant for the calculation of the R1 equation (mean of the 6h and 24h samples = 430.8 µg/g DW). The result presented in Figure 5 can be used to determine, under the previous assumptions, the theoretical exposure time of oysters to a continuous WWTP sewage discharge needed to bioaccumulate enough coprostanol to reach a human fingerprint with regards to their R1 ratios. The theoretical exposure time of R1 was reached at 38 days with a coprostanol concentration of 217.3 µg/g DW, which is very high compared to the concentrations observed in field studies [START_REF] Sherwin | Coprostanol (5β-cholestan-3β-ol) in lagoonal sediments and mussels of Venice, Italy[END_REF][START_REF] Cathum | Determination of steroids and coprostanol in surface water, effluent and mussel using gas chromatography-mass spectrometry[END_REF][START_REF] Gagné | Evidence of coprostanol estrogenicity to the freshwater mussel Elliptio complanata[END_REF][START_REF] Gagné | Biomarker study of a municipal effluent dispersion plume in two species of freshwater mussels[END_REF][START_REF] Hellou | Chemical contaminants and biological indicators of mussel health during gametogenesis[END_REF]Yeats et al., 2008;[START_REF] Harrault | Development of the analysis of fecal stanols in the oyster Crassostrea gigas and identification of fecal contamination in shellfish harvesting areas[END_REF] and seems practically unreachable in the laboratory. As a consequence, the stanol fingerprint does not seem to be suitable for the determination of human fecal contamination.

Conclusion

In this study, the ability of oysters to record specific human contamination through the use of fecal stanols was investigated by means of punctual artificial contamination of the surrounding seawater with a human WWTP effluent. The typical fecal stanols coprostanol and 24-ethylcoprostanol exhibited higher bioaccumulation in the contaminated oysters than in the non-contaminated ones, and their bioaccumulation kinetics were quite similar to that of the FIB E. coli, suggesting that these two compounds could be used as markers for the human fecal contamination of oysters. On the contrary, the naturally high concentrations of cholestanol and sitostanol in oysters and their different kinetics compared to that of E. coli make them unreliable to record fecal contamination.

Stanol fingerprints, such as the stanol ratios and PCA model that were successfully used to identify the human fingerprint in water, could not be used for this identification in oysters.

This lack of specificity for the identification of a human fingerprint is the result of i) the high levels of cholestanol and sitostanol and ii) a large shift in the coprostanol concentration compared to that of 24-ethylcoprostanol in oysters compared to the surrounding water, probably due to either differences in the accumulation/depuration processes of these compounds or the limits of the analytical pathway used.

Thus this study shows that oysters are able to record a pulse of specific human contamination using specific fecal stanols. However, contrary to constant contamination, the stanol fingerprints of the oysters (ratios and PCA model) appear unreliable to identify a specific source of fecal contamination.

Last, the stanol fingerprint is a useful tool that can be used as a microbial source tracking toolbox to identify specific sources of fecally-contaminated water; however, the current analytical method of stanols in oysters might not allow the use of the stanol fingerprint as an applicable microbial source tracking tool in this type of matrix. This underlines the need to further investigate the analysis of stanols in a biological matrix. This limitation needs to be taken into account in further investigations of the application of stanol fingerprints to identify fecal contamination sources in shellfish harvesting areas.

Vogel

Figure 1 :

 1 Figure1: Temporal variations of the concentration of Escherichia coli in waters and oysters expressed as colony forming unit (CFU) log 10 units/100 mL and log 10 units/100 g of flesh, respectively. Open triangles are blanks, grey squares '10%' treatment and black circles '20%' treatment. Errors are standard deviations (n = 3). Horizontal dotted lines represent European fecal contamination thresholds for water and oyster of sufficient quality (2.7 log CFU/100 mL and 3.7 log CFU/100 g, respectively).

FigureFigure 2 :

 2 Figure(s)

Figure 3 :

 3 Figure 3 : Temporal variations of stanol ratios in water and oysters over time : (a, d) R1 = coprostanol/ cholestanol, (b, e) R2 = coprostanol/(coprostanol + 24-ethylcoprostanol) and (c, f) R3 = sitostanol/ coprostanol. Open triangles are blanks, grey squares '10%' treatment and black circles '20%' treatment. Horizontal dashed lines represent the upper limits above which each ratio is indicative of a major human contamination. Vertical dotted lines represent the theoretical time at which ratios become non-indicative of a human contamination. Errors are standard deviations (n = 3).

Figure 4 :

 4 Figure 4 : Plot of the principal component analysis comparing the 88 source samples and water and oyster samples using the 6 most discriminant stanol compounds proposed by Derrien et al. (2012). Sample fingerprints were not graphically distinguished between treatments and time. F1 axis: principal component 1; F2 axis: principal component 2.

Figure 5 :

 5 Figure 5 : Theoretical kinetics of stanol ratios R1 (coprostanol/ cholestanol) of oysters from '20%' treatment. Horizontal dashed lines represent the upper limits above which R1 is indicative of a major human contamination. Vertical dotted line represent the theoretical time at which R1 become indicative of a human contamination.

  J.R., Stoeckel D.M., Lamendella R., Zelt R.B., Santo Domingo J.W., Walker S.R., et al. (2007) Identifying fecal sources in a selected catchment reach using multiple sourcetracking tools. Journal of environmental quality 36, 718-29. Wolf S., Hewitt J. & Greening G.E. (2010) Viral multiplex quantitative PCR assays for tracking sources of fecal contamination. Applied and environmental microbiology 76, 1388-94. Yeats P., Gagné F. & Hellou J. (2008) Body burden of contaminants and biological effects in mussels: an integrated approach. Environment international 34, 254-64.Table1 : Mean values of physico-chemical parameters over the whole experiment. Uncertainties are standard deviations.

	Table(s)
	Treatment	Blank	10%	20%
	pH	7.98 ± 0.05	8.03 ± 0.03	8.10 ± 0.06
	O2 (%)	94.1 ± 7.4	92.2 ± 8.9	90.3 ± 10.1
	Salinity (g/kg)	34.5 ± 0.7	31.8 ± 1.2	29.0 ± 2.2
	T (°C)	13.1 ± 1.4	12.9 ± 1.4	12.6 ± 1.4
	DOC (mg/L)	2.51 ± 1.31	3.75 ± 2.05	4.12 ± 1.07
	SPM (mg/L)	20.1 ± 10.5	22.3 ± 11.1	27.2 ± 14.6

Acknowledgments:

As part of the Riskmanche project (http://www.brighton.ac.uk/riskmanche/), this study was fully funded by the Interreg IV A France (Channel)-England cross-border European cooperation program. Dr. S. Mullin post-edited the English style (www.trad8.eu/us/saramullin.html).

Supplementary Data

Click here to download Supplementary Data: Supplementary Tables Harrault MBP.docx