Gergely Neu
email: gergely.neu@gmail.com

Explore no more: Improved high-probability regret bounds for non-stochastic bandits

This work addresses the problem of regret minimization in non-stochastic multiarmed bandit problems, focusing on performance guarantees that hold with high probability. Such results are rather scarce in the literature since proving them requires a large deal of technical effort and significant modifications to the standard, more intuitive algorithms that come only with guarantees that hold on expectation. One of these modifications is forcing the learner to sample arms from the uniform distribution at least Ω( √ T ) times over T rounds, which can adversely affect performance if many of the arms are suboptimal. While it is widely conjectured that this property is essential for proving high-probability regret bounds, we show in this paper that it is possible to achieve such strong results without this undesirable exploration component. Our result relies on a simple and intuitive loss-estimation strategy called Implicit eXploration (IX) that allows a remarkably clean analysis. To demonstrate the flexibility of our technique, we derive several improved high-probability bounds for various extensions of the standard multi-armed bandit framework. Finally, we conduct a simple experiment that illustrates the robustness of our implicit exploration technique.

Introduction

Consider the problem of regret minimization in non-stochastic multi-armed bandits, as defined in the classic paper of Auer, Cesa-Bianchi, Freund, and Schapire [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF]. This sequential decision-making problem can be formalized as a repeated game between a learner and an environment (sometimes called the adversary). In each round t = 1, 2, . . . , T , the two players interact as follows: The learner picks an arm (also called an action) I t ∈ [K] = {1, 2, . . . , K} and the environment selects a loss function t : [K] → [0, 1], where the loss associated with arm i ∈ [K] is denoted as t,i . Subsequently, the learner incurs and observes the loss t,It . Based solely on these observations, the goal of the learner is to choose its actions so as to accumulate as little loss as possible during the course of the game. As traditional in the online learning literature [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], we measure the performance of the learner in terms of the regret defined as

R T = T t=1 t,It -min i∈[K] T t=1 t,i .
We say that the environment is oblivious if it selects the sequence of loss vectors irrespective of the past actions taken by the learner, and adaptive (or non-oblivious) if it is allowed to choose t as a function of the past actions I t-1 , . . . , I 1 . An equivalent formulation of the multi-armed bandit game uses the concept of rewards (also called gains or payoffs) instead of losses: in this version, the adversary chooses the sequence of reward functions (r t ) with r t,i denoting the reward given to the learner for choosing action i in round t. In this game, the learner aims at maximizing its total rewards. We will refer to the above two formulations as the loss game and the reward game, respectively.

Our goal in this paper is to construct algorithms for the learner that guarantee that the regret grows sublinearly. Since it is well known that no deterministic learning algorithm can achieve this goal [START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], we are interested in randomized algorithms. Accordingly, the regret R T then becomes a random variable that we need to bound in some probabilistic sense. Most of the existing literature on non-stochastic bandits is concerned with bounding the pseudo-regret (or weak regret) defined as

R T = max i∈[K] E T t=1 t,It - T t=1 t,i ,
where the expectation integrates over the randomness injected by the learner. Proving bounds on the actual regret that hold with high probability is considered to be a significantly harder task that can be achieved by serious changes made to the learning algorithms and much more complicated analyses. One particular common belief is that in order to guarantee high-confidence performance guarantees, the learner cannot avoid repeatedly sampling arms from a uniform distribution, typically Ω √ KT times [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF][START_REF] Beygelzimer | Contextual bandit algorithms with supervised learning guarantees[END_REF][START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. It is easy to see that such explicit exploration can impact the empirical performance of learning algorithms in a very negative way if there are many arms with high losses: even if the base learning algorithm quickly learns to focus on good arms, explicit exploration still forces the regret to grow at a steady rate. As a result, algorithms with high-probability performance guarantees tend to perform poorly even in very simple problems [START_REF] Seldin | PAC-Bayes-Bernstein inequality for martingales and its application to multiarmed bandits[END_REF][START_REF] Beygelzimer | Contextual bandit algorithms with supervised learning guarantees[END_REF].

In the current paper, we propose an algorithm that guarantees strong regret bounds that hold with high probability without the explicit exploration component. One component that we preserve from the classical recipe for such algorithms is the biased estimation of losses, although our bias is of a much more delicate nature, and arguably more elegant than previous approaches. In particular, we adopt the implicit exploration (IX) strategy first proposed by Kocák, Neu, Valko, and Munos [START_REF] Kocák | Efficient learning by implicit exploration in bandit problems with side observations[END_REF] for the problem of online learning with side-observations. As we show in the current paper, this simple loss-estimation strategy allows proving high-probability bounds for a range of nonstochastic bandit problems including bandits with expert advice, tracking the best arm and bandits with side-observations. Our proofs are arguably cleaner and less involved than previous ones, and very elementary in the sense that they do not rely on advanced results from probability theory like Freedman's inequality [START_REF] Freedman | On tail probabilities for martingales[END_REF]. The resulting bounds are tighter than all previously known bounds and hold simultaneously for all confidence levels, unlike most previously known bounds [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Beygelzimer | Contextual bandit algorithms with supervised learning guarantees[END_REF]. For the first time in the literature, we also provide high-probability bounds for anytime algorithms that do not require prior knowledge of the time horizon T . A minor conceptual improvement in our analysis is a direct treatment of the loss game, as opposed to previous analyses that focused on the reward game, making our treatment more coherent with other state-of-the-art results in the online learning literature 1 .

The rest of the paper is organized as follows. In Section 2, we review the known techniques for proving high-probability regret bounds for non-stochastic bandits and describe our implicit exploration strategy in precise terms. Section 3 states our main result concerning the concentration of the IX loss estimates and shows applications of this result to several problem settings. Finally, we conduct a set of simple experiments to illustrate the benefits of implicit exploration over previous techniques in Section 4.

Explicit and implicit exploration

Most principled learning algorithms for the non-stochastic bandit problem are constructed by using a standard online learning algorithm such as the exponentially weighted forecaster ( [START_REF] Vovk | Aggregating strategies[END_REF][START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF]) or follow the perturbed leader ( [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF][START_REF] Kalai | Efficient algorithms for online decision problems[END_REF]) as a black box, with the true (unobserved) losses replaced by some appropriate estimates. One of the key challenges is constructing reliable estimates of the losses t,i for all i ∈ [K] based on the single observation t,It . Following Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], this is traditionally achieved by using importance-weighted loss/reward estimates of the form

t,i = t,i p t,i I {It=i} or r t,i = r t,i p t,i I {It=i} (1)
where p t,i = P [ I t = i| F t-1 ] is the probability that the learner picks action i in round t, conditioned on the observation history F t-1 of the learner up to the beginning of round t. It is easy to show that these estimates are unbiased for all i with p t,i > 0 in the sense that E t,i = t,i for all such i.

For concreteness, consider the EXP3 algorithm of Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] as described in Bubeck and Cesa-Bianchi [9, Section 3]. In every round t, this algorithm uses the loss estimates defined in Equation [START_REF] Alon | From Bandits to Experts: A Tale of Domination and Independence[END_REF] to compute the weights w t,i = exp -η t-1 s=1 s-1,i for all i and some positive parameter η that is often called the learning rate. Having computed these weights, EXP3 draws arm I t = i with probability proportional to w t,i . Relying on the unbiasedness of the estimates (1) and an optimized setting of η, one can prove that EXP3 enjoys a pseudo-regret bound of √ 2T K log K. However, the fluctuations of the loss estimates around the true losses are too large to permit bounding the true regret with high probability. To keep these fluctuations under control, Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] propose to use the biased reward-estimates

r t,i = r t,i + β p t,i (2)
with an appropriately chosen β > 0. Given these estimates, the EXP3.P algorithm of Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] computes the weights w t,i = exp η t-1 s=1 r s,i for all arms i and then samples I t according to the distribution

p t,i = (1 -γ) w t,i K j=1 w t,j + γ K ,
where γ ∈ [0, 1] is the exploration parameter. The argument for this explicit exploration is that it helps to keep the range (and thus the variance) of the above reward estimates bounded, thus enabling the use of (more or less) standard concentration results 2 . In particular, the key element in the analysis of EXP3.P [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF][START_REF] Beygelzimer | Contextual bandit algorithms with supervised learning guarantees[END_REF][START_REF] Bartlett | High-probability regret bounds for bandit online linear optimization[END_REF] is showing that the inequality T t=1 (r t,i -r t,i ) ≤ log(K/δ) β

holds simultaneously for all i with probability at least 1 -δ. In other words, this shows that the cumulative estimates T t=1 r t,i are upper confidence bounds for the true rewards T t=1 r t,i . In the current paper, we propose to use the loss estimates defined as

t,i = t,i p t,i + γ t I {It=i} , (3)
for all i and an appropriately chosen γ t > 0, and then use the resulting estimates in an exponentialweights algorithm scheme without any explicit exploration. Loss estimates of this form were first used by Kocák et al. [START_REF] Kocák | Efficient learning by implicit exploration in bandit problems with side observations[END_REF]-following them, we refer to this technique as Implicit eXploration, or, in short, IX. In what follows, we argue that that IX as defined above achieves a similar variancereducing effect as the one achieved by the combination of explicit exploration and the biased reward estimates of Equation ( 2). In particular, we show that the IX estimates (3) constitute a lower confidence bound for the true losses which allows proving high-probability bounds for a number of variants of the multi-armed bandit problem.

High-probability regret bounds via implicit exploration

In this section, we present a concentration result concerning the IX loss estimates of Equation ( 3), and apply this result to prove high-probability performance guarantees for a number of nonstochastic bandit problems. The following lemma states our concentration result in its most general form:

Lemma 1. Let (γ t ) be a fixed non-increasing sequence with γ t ≥ 0 and let α t,i be nonnegative F t-1 -measurable random variables satisfying α t,i ≤ 2γ t for all t and i. Then, with probability at least 1 -δ,

T t=1 K i=1 α t,i t,i -t,i ≤ log (1/δ) .
A particularly important special case of the above lemma is the following:

Corollary 1. Let γ t = γ ≥ 0 for all t. With probability at least 1 -δ, T t=1 t,i -t,i ≤ log (K/δ) 2γ .
simultaneously holds for all i ∈ [K].

This corollary follows from applying Lemma 1 to the functions α t,i = 2γI {i=j} for all j and applying the union bound. The full proof of Lemma 1 is presented in the Appendix. For didactic purposes, we now present a direct proof for Corollary 1, which is essentially a simpler version of Lemma 1.

Proof of Corollary 1. For convenience, we will use the notation β = 2γ. First, observe that

t,i = t,i p t,i + γ I {It=i} ≤ t,i p t,i + γ t,i I {It=i} = 1 2γ • 2γ t,i /p t,i 1 + γ t,i /p t,i I {It=i} ≤ 1 β • log 1 + β t,i ,
where the first step follows from t,i ∈ [0, 1] and last one from the elementary inequality z 1+z/2 ≤ log(1 + z) that holds for all z ≥ 0. Using the above inequality, we get that

E exp β t,i F t-1 ≤E 1 + β t,i F t-1 ≤ 1 + β t,i ≤ exp (β t,i ) ,
where the second and third steps are obtained by using E t,i F t-1 ≤ t,i that holds by definition of t,i , and the inequality 1 + z ≤ e z that holds for all z ∈ R. As a result, the process

Z t = exp β t s=1 s,i -s,i is a supermartingale with respect to (F t ): E [ Z t | F t-1 ] ≤ Z t-1 . Observe that, since Z 0 = 1, this implies E [Z T ] ≤ E [Z T -1 ] ≤ . . . ≤ 1,
and thus by Markov's inequality,

P T t=1 t,i -t,i > ε ≤ E exp β T t=1 t,i -t,i • exp(-βε) ≤ exp(-βε)
holds for any ε > 0. The statement of the lemma follows from solving exp(-βε) = δ/K for ε and using the union bound over all arms i.

In what follows, we put Lemma 1 to use and prove improved high-probability performance guarantees for several well-studied variants of the non-stochastic bandit problem, namely, the multi-armed bandit problem with expert advice, tracking the best arm for multi-armed bandits, and bandits with side-observations. The general form of Lemma 1 will allow us to prove high-probability bounds for anytime algorithms that can operate without prior knowledge of T . For clarity, we will only provide such bounds for the standard multi-armed bandit setting; extending the derivations to other settings is left as an easy exercise. For all algorithms, we prove bounds that scale linearly with log(1/δ) and hold simultaneously for all levels δ. Note that this dependence can be improved to log(1/δ) for a fixed confidence level δ, if the algorithm can use this δ to tune its parameters. This is the way that

p t,i ∝ w t,i = exp -η t t-1 s=1 s,i , (4)
without mixing any explicit exploration term into the distribution. A fixed-parameter version of EXP3-IX is presented as Algorithm 1.

Our theorem below states a high-probability bound on the regret of EXP3-IX. Notably, our bound exhibits the best known constant factor of 2 √ 2 in the leading term, improving on the factor of 5.15 due to Bubeck and Cesa-Bianchi [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. The best known leading constant for the pseudo-regret bound of EXP3 is √ 2, also proved in Bubeck and Cesa-Bianchi [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF].

Theorem 1. Fix an arbitrary δ > 0. With η t = 2γ t = 2 log K KT for all t, EXP3-IX guarantees

R T ≤ 2 2KT log K + 2KT log K + 1 log (2/δ)
with probability at least 1-δ. Furthermore, setting η t = 2γ t = log K Kt for all t, the bound becomes

R T ≤ 4 KT log K + 2 KT log K + 1 log (2/δ) .
Proof. Let us fix an arbitrary δ ∈ (0, 1). Following the standard analysis of EXP3 in the loss game and nonincreasing learning rates [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF], we can obtain the bound

T t=1 K i=1 p t,i t,i -t,j ≤ log K η T + T t=1 η t 2 K i=1 p t,i t,i 2
for any j. Now observe that

K i=1 p t,i t,i = K i=1 I {It=i} t,i (p t,i + γ t ) p t,i + γ t -γ t K i=1 I {It=i} t,i p t,i + γ t t,i = t,It -γ t K i=1 t,i . (5)
Similarly,

K i=1 p t,i 2
t,i ≤ K i=1 t,i
holds by the boundedness of the losses. Thus, we get that

T t=1 ( t,It -t,j ) ≤ T t=1 t,j -t,j + log K η T + T t=1 η t 2 + γ t K i=1 t,i ≤ log (K/δ ) 2γ + log K η + T t=1 η t 2 + γ t K i=1 t,i + log (1/δ )
holds with probability at least 1 -2δ , where the last line follows from an application of Lemma 1 with α t,i = η t /2 + γ for all t, i and taking the union bound. By taking j = arg min i L T,i and δ = δ/2, and using the boundedness of the losses, we obtain

R T ≤ log (2K/δ) 2γ T + log K η T + K T t=1 η t 2 + γ t + log (2/δ) .
The statements of the theorem then follow immediately, noting that

T t=1 1/ √ t ≤ 2 √ T .

Bandits with expert advice

We now turn to the setting of multi-armed bandits with expert advice, as defined in Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], and later revisited by McMahan and Streeter [START_REF] Mcmahan | Tighter bounds for multi-armed bandits with expert advice[END_REF] and Beygelzimer et al. [START_REF] Beygelzimer | Contextual bandit algorithms with supervised learning guarantees[END_REF]. In this setting, we assume that in every round t = 1, 2, . . . , T , the learner observes a set of N probability distributions ξ t (1), ξ t (2), . . . , ξ t (N ) ∈ [0, 1] K over the K arms, such that

K i=1 ξ t,i (n) = 1 for all n ∈ [N ].
We assume that the sequences (ξ t (n)) are measurable with respect to (F t ). The n th of these vectors represent the probabilistic advice of the corresponding n th expert. The goal of the learner in this setting is to pick a sequence of arms so as to minimize the regret against the best expert:

R ξ T = T t=1 t,It -min n∈[N ] T t=1 K i=1 ξ t,i (n) t,i → min .
To tackle this problem, we propose a modification of the EXP4 algorithm of Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] that uses the IX loss estimates (3), and also drops the explicit exploration component of the original algorithm. Specifically, EXP4-IX uses the loss estimates defined in Equation ( 3) to compute the weights

w t,n = exp -η t-1 s=1 K i=1 ξ s,i (n) s,i
for every expert n ∈ [N ], and then draw arm i with probability p t,i ∝ N n=1 w t,n ξ t,i (n). We now state the performance guarantee of EXP4-IX. Our bound improves the best known leading constant of 6 due to Beygelzimer et al. [START_REF] Beygelzimer | Contextual bandit algorithms with supervised learning guarantees[END_REF] to 2 √ 2 and is a factor of 2 worse than the best known constant in the pseudo-regret bound for EXP4 [START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]. The proof of the theorem is presented in the Appendix.

Theorem 2. Fix an arbitrary δ > 0 and set η = 2γ = 2 log N KT for all t. Then, with probability at least 1 -δ, the regret of EXP4-IX satisfies

R ξ T ≤ 2 2KT log N + 2KT log N + 1 log (2/δ) .

Tracking the best sequence of arms

In this section, we consider the problem of competing with sequences of actions. Similarly to Herbster and Warmuth [START_REF] Herbster | Tracking the best expert[END_REF], we consider the class of sequences that switch at most S times between actions. We measure the performance of the learner in this setting in terms of the regret against the best sequence from this class C(S) ⊆ [K] T , defined as

R S T = T t=1 t,It -min (Jt)∈C(S) T t=1 t,Jt .
Similarly to Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF], we now propose to adapt the Fixed Share algorithm of Herbster and Warmuth [START_REF] Herbster | Tracking the best expert[END_REF] to our setting. Our algorithm, called EXP3-SIX, updates a set of weights w t,• over the arms in a recursive fashion. In the first round, EXP3-SIX sets w 1,i = 1/K for all i. In the following rounds, the weights are updated for every arm i as

w t+1,i = (1 -α)w t,i • e -η t,i + α K K j=1 w t,j • e -η t,j .
In round t, the algorithm draws arm I t = i with probability p t,i ∝ w t,i . Below, we give the performance of EXP3-SIX. Note that our leading factor of 2 √ 2 again improves over the best previously known leading factor of 7, shown by Audibert and Bubeck [START_REF] Audibert | Minimax policies for adversarial and stochastic bandits[END_REF]. The proof of the theorem is given in the Appendix.

Bandits with side-observations

Let us now turn to the problem of online learning in bandit problems in the presence of side observations, as defined by Mannor and Shamir [START_REF] Mannor | From Bandits to Experts: On the Value of Side-Observations[END_REF] and later elaborated by Alon et al. [START_REF] Alon | From Bandits to Experts: A Tale of Domination and Independence[END_REF]. In this setting, the learner and the environment interact exactly as in the multi-armed bandit problem, the main difference being that in every round, the learner observes the losses of some arms other than its actually chosen arm I t . The structure of the side observations is described by the directed graph G: nodes of G correspond to individual arms, and the presence of arc i → j implies that the learner will observe t,j upon selecting I t = i.

Implicit exploration and EXP3-IX was first proposed by Kocák et al. [START_REF] Kocák | Efficient learning by implicit exploration in bandit problems with side observations[END_REF] for this precise setting.

To describe this variant, let us introduce the notations

O t,i = I {It=i} + I {(It→i)∈G} and o t,i = E [ O t,i | F t-1 ].
Then, the IX loss estimates in this setting are defined for all t, i as t,i = Ot,i t,i ot,i+γt . With these estimates at hand, EXP3-IX draws arm I t from the exponentially weighted distribution defined in Equation ( 4). The following theorem provides the regret bound concerning this algorithm. The proof of the theorem is given in the Appendix. While the proof of this statement is significantly more involved than the other proofs presented in this paper, it provides a fundamentally new result. In particular, our bound is in terms of the independence number α and thus matches the minimax regret bound proved by Alon et al. [START_REF] Alon | From Bandits to Experts: A Tale of Domination and Independence[END_REF] for this setting up to logarithmic factors. In contrast, the only high-probability regret bound for this setting due to Alon et al. [START_REF] Alon | Nonstochastic multi-armed bandits with graph-structured feedback[END_REF] scales with the size m of the maximal acyclic subgraph of G, which can be much larger than α in general (i.e., m may be o(α) for some graphs [START_REF] Alon | From Bandits to Experts: A Tale of Domination and Independence[END_REF]).

Empirical evaluation

We conduct a simple experiment to demonstrate the robustness of EXP3-IX as compared to EXP3 and its superior performance as compared to EXP3.P. Our setting is a 10-arm bandit problem where all losses are independent draws of Bernoulli random variables. The mean losses of arms 1 through 8 are 1/2 and the mean loss of arm 9 is 1/2 -∆ for all rounds t = 1, 2, . . . , T . The mean losses of arm 10 are changing over time: for rounds t ≤ T /2, the mean is 1/2 + ∆, and 1/2 -4∆ afterwards. This choice ensures that up to at least round T /2, arm 9 is clearly better than other arms. In the second half of the game, arm 10 starts to outperform arm 9 and eventually becomes the leader.

We have evaluated the performance of EXP3, EXP3.P and EXP3-IX in the above setting with T = 10 6 and ∆ = 0.1. For fairness of comparison, we evaluate all three algorithms for a wide range of parameters. In particular, for all three algorithms, we set a base learning rate η according to the best known theoretical results [9, Theorems 3.1 and 3.3] and varied the multiplier of the respective base parameters between 0.01 and 100. Other parameters are set as γ = η/2 for EXP3-IX and β = γ/K = η for EXP3.P. We studied the regret up to two interesting rounds in the game: up to T /2, where the losses are i.i.d., and up to T where the algorithms have to notice the shift in the loss distributions. Figure 1 shows the empirical means and standard deviations over 50 runs of the regrets of the three algorithms as a function of the multipliers. The results clearly show that EXP3-IX largely improves on the empirical performance of EXP3.P and is also much more robust in the non-stochastic regime than vanilla EXP3.

Discussion

In this paper, we have shown that, contrary to popular belief, explicit exploration is not necessary to achieve high-probability regret bounds for non-stochastic bandit problems. Interestingly, however, we have observed in several of our experiments that our IX-based algorithms still draw every arm roughly √ T times, even though this is not explicitly enforced by the algorithm. This suggests a need for a more complete study of the role of exploration, to find out whether pulling every single arm Ω( √ T ) times is necessary for achieving near-optimal guarantees.

One can argue that tuning the IX parameter that we introduce may actually be just as difficult in practice as tuning the parameters of EXP3.P. However, every aspect of our analysis suggests that γ t = η t /2 is the most natural choice for these parameters, and thus this is the choice that we recommend. One limitation of our current analysis is that it only permits deterministic learning-rate and IX parameters (see the conditions of Lemma 1). That is, proving adaptive regret bounds in the vein of [START_REF] Hazan | Better algorithms for benign bandits[END_REF][START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Neu | First-order regret bounds for combinatorial semi-bandits[END_REF] that hold with high probability is still an open challenge.

Another interesting question for future study is whether the implicit exploration approach can help in advancing the state of the art in the more general setting of linear bandits. All known algorithms for this setting rely on explicit exploration techniques, and the strength of the obtained results depend crucially on the choice of the exploration distribution (see [START_REF] Bubeck | Towards minimax policies for online linear optimization with bandit feedback[END_REF][START_REF] Hazan | Volumetric spanners: an efficient exploration basis for learning[END_REF] for recent advances). Interestingly, IX has a natural extension to the linear bandit problem. To see this, consider the vector V t = e It and the matrix

P t = E [V t V T t ].
Then, the IX loss estimates can be written as t = (P t + γI) -1 V t V T t t . Whether or not this estimate is the right choice for linear bandits remains to be seen.

Finally, we note that our estimates (3) are certainly not the only ones that allow avoiding explicit exploration. In fact, the careful reader might deduce from the proof of Lemma 1 that the same concentration bound can be shown to hold for the alternative loss estimates t,i I {It=i} / (p t,i + γ t,i ) and log 1 + 2γ t,i I {It=i} /p t,i /(2γ). Actually, a variant of the latter estimate was used previously for proving high-probability regret bounds in the reward game by Audibert and Bubeck [START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF]-however, their proof still relied on explicit exploration. It is not hard to verify that all the results we presented in this paper (except Theorem 4) can be shown to hold for the above two estimates, too.

A The proof of Lemma 1

Fix any t. For convenience, we will use the notation β t = 2γ t . First, observe that for any i, where the first step follows from t,i ∈ [0, 1] and last one from the elementary inequality z 1+z/2 ≤ log(1 + z) that holds for all z ≥ 0.

Define the notations λ t = K i=1 α t,i t,i and λ t = K i=1 α t,i t,i . Using the above inequality, we get that

E exp λ t F t-1 ≤E exp K i=1 α t,i β t • log 1 + β t t,i F t-1 ≤E K i=1 1 + α t,i t,i F t-1 = E 1 + K i=1 α t,i t,i F t-1 ≤1 + K i=1 α t,i t,i ≤ exp K i=1 α t,i t,i = exp (λ t ) , (6)
where the second line follows from noting that α t,i ≤ β t , using the inequality x log(1+y) ≤ log(1+ xy) that holds for all y > -1 and x ∈ [0, 1] and the identity K i=1 1 + α t,i t,i = 1+ K i=1 α t,i t,i that follows from the fact that t,i • t,j = 0 holds whenever i = j. The last line is obtained by using E t,i F t-1 ≤ t,i that holds by definition of t,i , and the inequality 1 + z ≤ e z that holds for all z ∈ R.

As a result, the process Z t = exp t s=1 λ s -λ s is a supermartingale with respect to (F t ):

E [ Z t | F t-1 ] ≤ Z t-1 . Observe that, since Z 0 = 1, this implies E [Z T ] ≤ E [Z T -1 ] ≤ . . . ≤ 1,
and thus by Markov's inequality,

P T t=1 λ t -λ t > ε ≤ E exp T t=1 λ t -λ t • exp(-ε) ≤ exp(-ε)
holds for any ε > 0. The statement of the lemma follows from solving exp(-ε) = δ for ε.

B Further proofs B.1 The proof of Theorem 2

Fix an arbitrary δ . For ease of notation, let us define π t (n) = w t,n / N m=1 w t,m . By standard arguments (along the lines of [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]), we can obtain

T t=1 K i=1 p t,i -ξ t,i (m) t,i ≤ log K η + η 2 T t=1 N n=1 π t (n) K i=1 ξ t,i (n) t,i 2
for any fixed m ∈ [N ]. The last term on the right-hand side can be bounded as

N n=1 π t (n) K i=1 ξ t,i (n) t,i 2 ≤ N n=1 π t (n) K i=1 ξ t,i (n) t,i 2 = K i=1 p t,i t,i 2 ≤ K i=1 t,i ,
where the first step uses Jensen's inequality and the last uses p t,i t,i ≤ 1. Now, we can apply Lemma 1 and the union bound to show that

T t=1 K i=1 ξ t,i (m) t,i -t,i ≤ log (N/δ ) 2γ
holds simultaneously for all experts with probability at least 1 -δ , and in particular for the best expert, too. Putting this observation together with the above bound and Equation ( 5), we get that

R ξ T ≤ log N η + log (N/δ ) 2γ + η 2 + γ T t=1 K i=1 t,i ≤ log K η + log (N/δ ) 2γ + η 2 + γ K i=1 L T,i + η 2 + γ log (1/δ ) 2γ
holds with probability at least 1 -2δ , where the last line follows from Lemma 1 and the union bound. The proof is concluded by taking δ = δ/2 and plugging in the choices of γ and η.

B.2 The proof of Theorem 3

The proof of the theorem builds on the techniques of Cesa-Bianchi et al. [START_REF] Cesa-Bianchi | Mirror descent meets fixed share (and feels no regret)[END_REF] and Auer et al. [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF].

Let us fix an arbitrary δ ∈ (0, 1) and denote the best sequence from C(S) by J * 1:T . Then, a straightforward modification of Theorem 2 of [START_REF] Cesa-Bianchi | Mirror descent meets fixed share (and feels no regret)[END_REF] yields the bound3

T t=1 K i=1 p t,i t,i -t,J * t ≤ 2 S log K η - 1 η log α S (1-α) T -S + η 2 T t=1 K i=1 p t,i t,i 2
.

To proceed, let us apply Lemma 1 to obtain that

≤ 2 S log K η - 1 η log α S (1 -α) T -S + log T /(Sδ ) + 1 2γ + η 2 + γ T t=1 K i=1 t,i ≤ 2 S log K η - 1 η log α S (1 -α) T -S + log T /(Sδ ) + 1 2γ + η 2 + γ K i=1 L t,i + η 2 + γ log (1/δ ) 2γ ,
holds with probability at least 1 -2δ . where the last line follows from Lemma 1 and the union bound. Then, after observing that the losses are bounded in [0, 1] and choosing δ = δ/2, we get that

R S T ≤ (S + 1) log K η - 1 η log α S (1 -α) T -S-1 + (S + 1) log K + S log 2eT Sδ 2γ + η 2 + γ KT + η 2 + γ log (2/δ) 2γ
holds with probability at least 1 -δ. The only remaining piece required for proving the theorem is showing that

-log α S (1 -α) T -S ≤ S log eT S ,
which follows from the proof of Corollary 1 in [START_REF] Cesa-Bianchi | Mirror descent meets fixed share (and feels no regret)[END_REF], and then substituting the choice of η and γ.

B.3 The proof of Theorem 4

Before we dive into the proof, we note that Lemma 1 does not hold for the loss estimates used by this variant of EXP3-IX due to a subtle technical issue. Precisely, in this case K i=1 1 + t,i = K i=1 1 + t,i prevents us from directly applying Lemma 1. However, Corollary 1 can still be proven exactly the same way as done in Section 3. The only effect of this change is that the term log(1/δ ) is replaced by K log(K/δ ).

Turning to the actual proof, let us fix an arbitrary δ ∈ (0, 1) and introduce the notation

Q t = K i=1 p t,i o t,i + γ .
By the standard EXP3-analysis, we have

T t=1 K i=1 p t,i t,i -t,j ≤ log K η + η 2 T t=1 K i=1 p t,i t,i 2
.

Now observe that

T t=1 K i=1 p t,i t,i 2 = T t=1 K i=1 p t,i o t,i + γ • t,i ≤ T t=1 K i=1 p t,i o t,i + γ • t,i + K log(K/δ ) 2γ ≤ T t=1 Q t + K log(K/δ ) 2γ ,
holds with probability at least 1 -δ by an application of Corollary 1 for all i and taking a union bound. Furthermore, we have The proof is concluded by observing that the last term is bounded by the third one if T ≥ K 2 /(8α).

Theorem 3 .

 3 Fix an arbitrary δ > 0 and set η = 2γ = 2 S log K KT and α = S T -1 , where S = S + 1. Then, with probability at least 1 -δ, the regret of EXP3-SIX satisfies

Theorem 4 .

 4 Fix an arbitrary δ > 0. Assume that T ≥ K 2 /(8α) and set η = 2γ = log K 2αT log(KT ) , where α is the independence number of G. With probability at least 1 -δ, EXP3-IX guarantees R T ≤ 4+2 log (4/δ) • 2αT log 2 K +log KT +2 αT log(KT ) log K log (4/δ)+ T log(4/δ) 2 .

Figure 1 :

 1 Figure 1: Regret of EXP3, EXP3.P, and EXP3-IX, respectively in the problem described in Section 4.

Table 1

 1 presents our new bounds side-by-side with the best previously known ones.

	Setting	Best known regret bound Our new regret bound
	Multi-armed bandits	5.15 T K log(K/δ)	2 2T K log(K/δ)
	Bandits with expert advice	6 T K log(N/δ)	2 2T K log(N/δ)
	Tracking the best arm Bandits with side-observations	7 KT S log(KT /δS) O √ mT	2 2KT S log(KT /δS) O √ αT

Table 1 :

 1 Our results compared to the best previously known results in the four settings considered in Sections 3.1-3.4. See the respective sections for references and notation. Draw I t ∼ p t = (p t,1 , . . . , p t,K ).

	3.1 Multi-armed bandits
	Algorithm 1 EXP3-IX Parameters: η > 0, γ > 0. Initialization: w 1,i = 1. for t = 1, 2, . . . , T , repeat 1. p t,i = wt,i K j=1 wt,j . 2. 3. Observe loss t,It . 4. In this section, we propose a variant of the EXP3 algorithm of Auer et al. [5] that uses the IX loss estimates (3): EXP3-IX. The algorithm in its most general form uses two nonincreasing sequences of nonnegative parameters: (η

t,i ← t,i pt,i+γ I {It=i} for all i ∈ [K]. 5. w t+1,i ← w t,i e -η t,i for all i ∈ [K]. t

) and (γ t ). In every round, EXP3-IX chooses action I t = i with probability proportional to

  with probability at least 1 -δ . After putting the above inequalities together and applying Lemma 1, we obtain the bound is a martingale-difference sequence for all i ∈ [K] with |X t | ≤ K and conditional variance Thus, an application of Freedman's inequality (see, e.g., Theorem 1 of Beygelzimer et al.[START_REF] Beygelzimer | Contextual bandit algorithms with supervised learning guarantees[END_REF]), we can thus obtain the bound Combining this result with the previous bounds and using the union bound, we arrive at the bound that holds with probability at least 1 -δ, where α = α log 1 + K 2 /γ +K

	σ 2 t (X t ) =E	 	K i=1	(o t,i -O t,i )	p t,i o t,i + γ	2	F t-1	 
	≤E	 	K i=1	O t,i	p t,i o t,i + γ	2	F t-1	 	(since E [ O t,i | F t-1 ] = o t,i )
	=E	 	K i=1	K j=1	O t,i O t,j	p t,i o t,i + γ	•	p t,j o t,j + γ	F t-1	 
	≤E	 	K i=1	K j=1	O t,i	p t,i o t,i + γ	•	p t,j o t,j + γ	F t-1	 	(since O t,j≤1 )
	=	K i=1	K j=1	p t,i o t,i o t,i + γ	•	p t,j o t,j + γ	≤	K i=1	p t,i	K j=1	p t,j o t,j + γ	= Q t .
	T t=1 Q R T ≤ X t ≤ T log(1/δ ) ω + (e -2)ω t=1 log K η + log(K/δ ) 2γ + log(1/δ ) ω + η 2 + γ + ω T t=1 Q t + η 2	•	K log(K/δ ) 2γ	+	T log(1/δ ) 2
	that holds with probability at least 1 -4δ .
	K i=1 Invoking Lemma 1 of Kocák et al. [19] that states that p t,i t,i = K i=1 p t,i t,i + K i=1 (O t,i -o t,i -γ) ≥ K p t,i t,i + K i=1 p t,i o t,i + γ ≤ 2α log 1 + K 2 /γ + K α	p t,i t,i o t,i + γ + 2
	i=1 holds almost surely and setting δ = δ/4, we obtain the bound
	By the Hoeffding-Azuma inequality, we have T t=1 t,It ≤ T t=1 K i=1 R T ≤ log K η + log(4K/δ) 2γ + log(4/δ) ω + (η + 2γ + 2ω) α T + T log(1/δ ) η 2 • K log(4K/δ) 2γ p t,i t,i + 2 α + 1.	+	T log(4/δ) 2
	Now notice that when setting η = 2γ =	log K 2αT log(KT ) and ω =	log(4/δ) 2αT log(KT ) , we have α ≤
	R T ≤ 2α log(KT ) and the above bound becomes log K η + log(K/δ ) 2γ + η 2 + γ + T t=1 K i=1 R T ≤ 4 + 2 log (4/δ) • 2αT log 2 K + log KT + T t=1 Q t + η 2 • K log(K/δ ) 2γ 2αT log(KT ) T log(1/δ ) + 2 log (4/δ) + log K p t,i t,i (o t,i -O t,i ) + T log(4/δ) 2 + K log (4K/δ) 2 .

K i=1 (O t,i -o t,i ) p t,i t,i o t,i + γ -γQ t . o t,i + γ

that holds with probability at least 1 -3δ by the union bound. To bound the last term on the right hand side, observe that

X t = K i=1 (o t,i -O t,i ) p t,i t,i o t,i + γ t

that holds with probability at least 1 -δ for all ω ≤ 1/K.

In fact, studying the loss game is colloquially known to allow better constant factors in the bounds in many settings (see, e.g., Bubeck and Cesa-Bianchi[START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF]). Our result further reinforces these observations.

Explicit exploration is believed to be inevitable for proving bounds in the reward game for various other reasons, too-see Bubeck and Cesa-Bianchi[START_REF] Bubeck | Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems[END_REF] for a discussion.

Proving this bound requires replacing Hoeffding's inequality in their Lemma 1 by the inequality e -z ≤ 1 -z + z 2 /2 that holds for all z ≥ 0.

Acknowledgments This work was supported by INRIA, the French Ministry of Higher Education and Research, and by FUI project Hermès. The author wishes to thank Haipeng Luo for catching a bug in an earlier version of the paper, and the anonymous reviewers for their helpful suggestions.


Paco Bustamante

Alice Carravieri

Aurélie Goutte

Christophe Barbraud

Karine Delord

Olivier Chastel

Henri Weimerskirch

Yves Cherel

High feather mercury concentrations in the wandering albatross are related to sex, breeding status and trophic ecology with no demographic consequences

Keywords: Bioaccumulation, Metal, Sex, Age, Immature, Stable isotopes, Southern Ocean Highlights

Hg can affect physiology of seabirds and ultimately their demography, particularly if they are top consumers. In the present study, body feathers of > 200 wandering albatrosses from Possession Island in the Crozet archipelago were used to explore the potential demographic effects of the long-term exposure to Hg on an apex predator. Variations of Hg with sex, age class, foraging habitat (inferred from δ 13 C values), and feeding habits (inferred from δ 15 N values) were examined as well as the influence of Hg on current breeding output, long-term fecundity and survival. Wandering albatrosses displayed among the highest Hg feather concentrations reported for seabirds, ranging from 5.9 to 95 µg g -1 , as a consequence of their high trophic position (δ 15 N values). These concentrations fall within the same range of those of other wandering albatross populations from subantarctic sites, suggesting that this species has similar exposure to Hg all around the Southern Ocean. In both immature and adult albatrosses, females had higher Hg concentrations than males (28 vs 20 µg g -1 dw on average, respectively), probably as a consequence of females foraging at lower latitudes than males (δ 13 C values). Hg concentrations were higher in immature than in adult birds, and they remained fairly constant across a wide range of ages in adults. Such high levels in immature individuals question (i) the frequency of moult in young birds, (ii) the efficiency of Hg detoxification processes in immatures compared to adults, and (iii) importantly the potential detrimental effects of Hg in early life. Despite very high Hg concentrations in their feathers, neither effects on adults' breeding probability, hatching failure and fledgling failure, nor on adults' survival rate were detected, suggesting that long-term bioaccumulated Hg was not under a chemical form leading to deleterious effects on reproductive parameters in adult individuals.

Introduction

Mercury (Hg) is a non-essential element that bioaccumulates in organisms and biomagnifies through food webs. Both processes are due to the conversion of inorganic Hg into organic forms (mainly methylmercury, MeHg) in aquatic ecosystems, MeHg being highly bioavailable and toxic. As such, MeHg is harmful to biota, being associated with adverse effects such as neurological, immunological, physiological and reproductive impacts in both humans and wildlife (e.g. [START_REF] Evans | Neurotoxicity of methylmercury in the pigeon[END_REF]Thompson and Furness, 1989a;[START_REF] Burger | Risk, mercury levels, and birds: relating adverse laboratory effects to field biomonitoring[END_REF][START_REF] Tan | The endocrine effects of mercury in humans and wildlife[END_REF]. Nonetheless, the natural occurrence of Hg [START_REF] Nriagu | A history of global metal pollution[END_REF] has involved adaptations of predators to the presence of this toxic metal in their environment. This is particularly obvious for many top predators whose high trophic position and long life span lead to important levels of exposure. Most marine top predators feed on fish and cephalopods, which concentrate Hg mainly under MeHg [START_REF] Bloom | On the chemical form of mercury in edible fish and marine invertebrate tissue[END_REF][START_REF] Bustamante | Total and organic Hg concentrations in cephalopods from the North East Atlantic waters: influence of geographical origin and feeding ecology[END_REF]. Marine apex predators have thus developed efficient detoxification capacities to support elevated exposure to MeHg (reviews in Cuvin-Aralar and Furness, 1991;[START_REF] Das | Metallothioneins in marine mammals[END_REF]. In marine mammals, demethylation of MeHg in the liver leads to the production of non-toxic granules of tiemannite [START_REF] Koeman | Mercury-selenium correlations in marine mammals[END_REF][START_REF] Martoja | Identification of tiemannite as a probable product of demethylation of mercury by selenium in cetaceans. A complement to the scheme of the biological cycle of mercury[END_REF]. The accumulation of tiemannite granules makes the liver the ultimate organ of retention of Hg [START_REF] Wagemann | Methylmercury and total mercury in tissues of arctic marine mammals[END_REF]2000). Since these granules are not excreted [START_REF] Nigro | Intracellular storage of mercury and selenium in different marine vertebrates[END_REF], inorganic Hg is basically stored through the whole life, thus inducing particularly elevated and increasing liver Hg concentrations throughout life, without any apparent toxic effect (Cuvin-Aralar and Furness, 1991).

In aquatic birds, efficiency of Hg detoxification processes is critical to prevent the toxic effects of Hg, which can affect their breeding, hatching and fledging successes [START_REF] Tan | The endocrine effects of mercury in humans and wildlife[END_REF][START_REF] Frederick | Altered pairing behaviour and reproductive success in white ibises exposed to environmentally relevant concentrations of methylmercury[END_REF][START_REF] Tartu | To breed or not to breed: endocrine response to mercury contamination by an arctic seabird[END_REF], Goutte et al. 2014a,b). As in mammals, demethylation of Hg in the liver appears to be a significant detoxification mechanism in seabirds (Thompson andFurness 1989b, Thompson et al. 1993). However, birds present another complementary and efficient way to detoxify and excrete Hg on a regular basis, namely moult.

Hg binds to keratin in the form of MeHg, hence, most feather Hg is MeHg (Thompson and Furness, 1989a), thus leading to a direct elimination of the toxic organic form during feather growth and subsequent loss. Feathers are considered as the main route for Hg excretion in seabirds [START_REF] Monteiro | Seabirds as monitors of mercury in the marine environment[END_REF], with feather growth contributing to the elimination of >90% of the Hg accumulated since the previous moult [START_REF] Braune | Mercury levels in Bonaparte's gulls (Larus philadelphia) during autumn moult in the Quoddy region, New Brunswick, Canada[END_REF]. In some cases, moult of all feathers is synchronous, as in penguins that renew their whole plumage in a few weeks [START_REF] Brasso | Unique pattern of molt leads to low intraindividual variation in feather mercury concentrations in penguins[END_REF], Carravieri et al. 2013, 2014a), but generally moult is sequential and takes many weeks to months to be completed. For example, the wandering albatross Diomedea exulans replaces its feathers slowly and infrequently over several consecutive interbreeding periods [START_REF] Weimerskirch | Sex-specific differences in molt strategy in relation to breeding in the Wandering albatross[END_REF]) and this extreme moulting pattern is believed to contribute significantly to high feather Hg concentrations in the species [START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF][START_REF] Becker | Feather mercury levels in seabirds at South Georgia: influence of trophic position, sex and age[END_REF].

The present study adds new information on Hg exposure, the factors explaining its variations, and its demographic consequences on the wandering albatross breeding at Possession Island in the Crozet archipelago (southern Indian Ocean). There, an exceptional long-term demographic capture-mark-recapture survey (1965-present) allows a robust knowledge of the life history of each individual [START_REF] Weimerskirch | Population dynamics of wandering albatross Diomedea exulans and Amsterdam albatross D. amsterdamensis in the Indian Ocean and their relationships with long-line fisheries: conservation implications[END_REF]. The wandering albatross was chosen as a model animal because (i) it is an apex predator that occupies the highest trophic position within the diverse community of subantarctic seabirds, being thus submitted to contaminant biomagnification processes [START_REF] Blévin | Wide range of mercury contamination in chicks of Southern Ocean seabirds[END_REF], (ii) it is a very longlived species (> 50 years) making it a species of particular interest to investigate Hg bioaccumulation patterns over the long term [START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF], Carravieri et al. 2014b), and (iii) consequently the species presents consistently high Hg levels in various tissues, including liver, blood and feathers [START_REF] Hindell | Mercury and cadmium concentrations in the tissues of three species of southern albatrosses[END_REF][START_REF] Stewart | Influence of phylogeny, diet, moult schedule and sex on heavy metal concentrations in New Zealand Procellariiformes[END_REF][START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF], Carravieri et al. 2014b,c). The study is a companion work to a broader investigation using the same birds and data set that focused on (i) the complex foraging pattern of wandering albatrosses according to age, sex and breeding status using stable isotopes (Jaeger et al. 2014), (ii) the effect of all these factors and foraging ecology as explanatory variables of blood contaminants (Hg and persistent organic pollutants) (Carravieri et al. 2014b), and (iii) the corresponding consequences of blood contamination levels on birds' demography (Goutte et al. 2014b).

We focused here on Hg in body feathers to complement the previous investigations on blood, because the two tissues represent short-and long-term exposure to Hg, respectively. Blood Hg is directly influenced by recent dietary intake, while feathers are representative of Hg bioaccumulation over the inter-moult period (at least two years for body feathers in the wandering albatross). Our goal was three fold, by increasing order of importance (i) to describe body feather Hg concentrations in a larger data set of sampled birds (n> 200) than in most previous investigations on marine predators, (ii) to quantify the main intrinsic (sex, age and breeding status) and extrinsic (foraging habitat and trophic position) factors contributing to Hg variation, and (iii) the demographic consequences of feather Hg levels in terms of current probabilities of breeding success, and of long-term apparent probabilities of adult survival, return to the breeding colony, and breeding, hatching and fledgling successes. We also further investigated the surprising recent finding on a few birds showing that feather Hg concentrations were higher in young immature wandering albatrosses than in older immatures and adults [START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF].

Materials and Methods

Study area, species and fieldwork

Wandering albatrosses nest on subantarctic islands throughout the Southern Ocean. The study was conducted at Possession Island in the Crozet Archipelago (46°S, 52°E), Southern Indian Ocean, where 300-400 pairs nest each year [START_REF] Delord | Population trends in a community of large Procellariiforms of Indian Ocean: Potential effects of environment and fisheries interactions[END_REF]. Although the minimal age at first reproduction is five years old, ten years is the mean age of first breeding in this population [START_REF] Weimerskirch | Population dynamics of wandering albatross Diomedea exulans and Amsterdam albatross D. amsterdamensis in the Indian Ocean and their relationships with long-line fisheries: conservation implications[END_REF]. Wandering albatrosses return to their breeding grounds each year in December and females lay a single egg in late December-early January. Both parents incubate alternatively until hatching in March. Chicks are reared for ≈280 days and most young are fledged in November. It was recently demonstrated that up to 6% of the birds that fledged a chick still breed 2 years in a row, and the species is now considered as a quasibiennial breeding species [START_REF] Barbraud | Estimating survival and reproduction in a quasi-biennially breeding seabird with uncertain and unobservable states[END_REF]. Approximately 80% of birds that failed the previous year engage in another breeding attempt the following year. All wandering albatrosses had been ringed and sexed as part of a long-term mark recapture program [START_REF] Weimerskirch | Population dynamics of wandering albatross Diomedea exulans and Amsterdam albatross D. amsterdamensis in the Indian Ocean and their relationships with long-line fisheries: conservation implications[END_REF], with nestlings being ringed since 1965. In December, pre-breeding adults are counted over the whole island. From mid-January to mid-February, nest contents were checked every ten days to determine the identity of the breeding pairs and breeding status (egg laid/egg hatched) of each individual. In mid-April, June and August, all nests are checked to monitor the survival of chicks.

In the present work, sampled wandering albatrosses were grouped per sex according to their breeding history and age: (i) immatures refer to young birds (3-11 years) that never bred, and (ii) adult albatrosses were those that bred at least once. From 21 December 2007 to 04 March 2008, body feathers were collected on 201 immature and adult wandering albatrosses.

Since Hg is mostly excreted in growing feathers, Hg level in feathers is considered to be a reliable measure of Hg bioaccumulation since the last moult [START_REF] Furness | Using bird feathers to measure mercury in the environment: relationship between mercury content and moult[END_REF]). In wandering albatrosses, feather replacement takes place exclusively during the non-breeding period [START_REF] Weimerskirch | Sex-specific differences in molt strategy in relation to breeding in the Wandering albatross[END_REF]. Once collected, body feathers were stored dry in individual plastic bags.

Hg and stable isotope analyses

Four body feathers per individual were pooled to obtain a mean isotopic value and an average of Hg level for body feathers [START_REF] Bond | High within-individual variation in total mercury concentration in seabird feathers[END_REF][START_REF] Jaeger | Age, sex, and breeding status shape a complex foraging pattern in an extremely long-lived seabird[END_REF], Carravieri et al., 2014a). Prior to chemical analysis, feathers were cleaned to remove surface contaminants using a 2:1 chloroform:methanol solution followed by two successive methanol rinses. After cleaning, body feathers were oven dried for 48 h at 50°C. Total Hg was measured at the laboratory Littoral Environnement et Sociétés (LIENSs) with an Advanced Mercury Analyzer spectrophotometer (Altec AMA 254). At least two aliquots ranging from 5 to 10 mg dry weight (dw) were analyzed for each individual and measurement quality was certified by reference material, as described by [START_REF] Bustamante | Total and organic Hg concentrations in cephalopods from the North East Atlantic waters: influence of geographical origin and feeding ecology[END_REF]. Accuracy was checked using a Certified Reference Material (CRM), Tort-2 Lobster Hepatopancreas, NRC, Canada; certified Hg concentration: 0.27 ± 0.06 μg g -1 dry mass. Mass of the CRM was adjusted to represent the same amount of Hg introduced in the AMA compared to the one in the feathers. Recovery was 98 ± 4 % proving good repeatability and reliability of the method. Blanks were analysed at the beginning of each set of samples and the detection limit of the method was 0.005 μg g -1 dry mass. Hg concentrations are presented in μg g -1 dry mass.

To test potential effect of foraging habitat and trophic position on feather Hg levels, the isotopic niche was used as a proxy of the trophic niche [START_REF] Newsome | A niche for isotopic ecology[END_REF]. The isotopic method was validated in the southern Indian Ocean, with δ 13 C values of seabirds indicating their foraging habitats [START_REF] Cherel | Geographical variation in carbon stable isotope signatures of marine predators: a tool to investigate their foraging areas in the Southern Ocean[END_REF][START_REF] Jaeger | Seabird satellite tracking validates the use of latitudinal isoscapes to depict predators' foraging areas in the Southern Ocean[END_REF] and their δ 15 N values increasing with trophic level [START_REF] Cherel | Isotopic niches and trophic levels of myctophid fishes and their predators in the Southern Ocean[END_REF]. Feather is a metabolically inactive tissue that reflects the diet at the time it was grown, because keratin is inert after synthesis [START_REF] Hobson | Assessing avian diets using stable isotopes I: turnover of 13 C in tissues[END_REF][START_REF] Bearhop | Factors that influence assimilation rates and fractionation of nitrogen and carbon stable isotopes in avian blood and feathers[END_REF]. Cleaned pooled feathers (see above) were finely grounded with steel scissors and 0.30 ± 0.05 mg subsamples of the resulting powder were weighed in tin cups. Isotopic analyses were performed at the laboratory LIENSs with a Thermo Scientific Delta V Advantage mass spectrometer coupled to a Thermo Scientific Flash EA1112 elemental analyser. Results are presented in the usual δ notation relative to the deviation from international standards (Vienna PeeDee Belemnite and atmospheric N2 for δ 13 C and δ 15 N, respectively).

Replicate measurements of internal laboratory standards (acetanilide) indicate measurements errors <0.10 ‰ for both δ 13 C and δ 15 N values.

Statistical tests were performed using R 2.15.1 [START_REF] Core | R: A language and environment for statistical computing[END_REF]. A significance level of α < 0.05 was used for all tests, both in unifactorial and multifactorial analyses. Values are means ± SD. The effects of intrinsic (age, sex, reproductive status the previous year, 2007) and extrinsic (feeding ecology) factors on Hg concentrations in feathers were tested using Generalized Linear Models (GLM). Data exploration was carried out following [START_REF] Zuur | Mixed Effects Models and Extensions in Ecology with R[END_REF]. Multifactorial analyses were used to test multiple alternative hypotheses on the influence of age, sex, reproductive status, foraging habitat (δ 13 C) and trophic level (δ 15 N) on feather Hg concentrations. Continuous variables that were significantly correlated were not included in multifactorial models. Notably, feather δ 13 C and δ 15 N values were strongly correlated (Pearson correlation, r = 0.80, p < 0.0001, N = 201) due to the slight baseline latitudinal enrichment in δ 15 N values from cold to warm waters of the southern Indian Ocean [START_REF] Jaeger | Seabird satellite tracking validates the use of latitudinal isoscapes to depict predators' foraging areas in the Southern Ocean[END_REF]. GLM with a gamma distribution and an inverse-link function were constructed as follows: Hg concentrations as the response variable, sex and reproductive status as a categorical explanatory variables and age and feather δ 13 C values as continuous explanatory variables. The models were restricted to primary effects and two-way interactions. Immature birds were considered separately from the adults as they showed a different age-related variation in feather Hg concentrations. In both cases (immatures and adults), model selection was based on Akaïke's Information Criteria adjusted for small sample sizes (AICc). The model with the lowest AICc value was considered to be the most accurate. Models with AICc values differing by less than two have a similar level of support in the data. Since our aim was to make inference on the variables affecting contaminant burdens, the effect of variables was inferred through Akaike's weights (wi), and without using model averaging [START_REF] Burnham | Model selection and multi-model inference: a practical information theoretic approach[END_REF]. Model fit was checked by residual analysis.

The effects of Hg (log-transformed) on breeding probability at the year of sampling (thereafter 2008) and during the last breeding attempt preceding the year of sampling (thereafter in 2005, 2006 or 2007) were tested on sexually-mature albatrosses, using GLM binomial error distribution and a logit link function. Breeding probability was coded as 1 if a bird was observed as a breeder (i.e. incubating an egg or raising a chick) and as 0 if a bird was observed as a nonbreeder at the colony. Finally, we tested whether breeding success during the year of sampling (2008) or during the last breeding attempt preceding the year of sampling (2005, 2006 or 2007) were linked to feather Hg levels in individuals sampled as breeders (incubating or chickrearing), by using GLMs with binomial error distribution and a logit link function. Breeding success was coded as 1 for birds that successfully fledged a chick, and as 0 for those that failed at the egg or chick stage. Models were then checked for assumptions that are constancy of variance and residual normality.

The effects of Hg on long-term demographic parameters were evaluated using the capture-recapture data of sampled sexually-mature albatrosses from 2008 to 2012. A multistage mark-recapture (MSMR) model as developed by Pardo et al. (2013a,b) was built. This model includes eight states: dead, failed breeder on egg (FBE, defined as an individual that was observed with one egg that failed to hatch), failed breeder on chick (FBC, defined as an individual that was observed with one chick but that failed to fledge the chick), successful breeder (SB, defined as an individual that fledged one chick), observable non-breeder (ONB, defined as an individual that was observed at the colony but that was not observed with an egg or a chick), and three unobservable states (UNB) consisting of non-breeders that were observed at the colony during the previous breeding attempt (PONB), non-breeders whose previous breeding attempt failed (PFB) and non-breeders whose previous breeding attempt was successful (PSB). The state dead ( †) was an absorbing state representing death or permanent emigration from the study area. The unobservable states account for temporary absence corresponding to birds that skip breeding after breeding unsuccessfully or successfully. States occupied are not directly observed; rather at each occasion t, an event happens and is recorded leading to an observed encounter history. In our case, we thus considered five events; 0 = ''not observed'', 1 = ''seen as a failed breeder on egg'', 2 = ''seen as a failed breeder on chick'', 3 = "seen as a successful breeder'', 4 = ''seen as a non-breeder'', which were used to build capture histories. Events and states are considered as random variables, and it is assumed that an event at occasion t depends only on an underlying state (which is not observed) of the individual at the moment, and that successive states follow a Markov chain. Models were parameterized in terms of the probability of survival (s), the probability to return at the colony given survival (r), the probability of breeding given return at the colony (β), the probability of successful hatching given breeding (ω), the probability of successful fledgling given hatching (γ), and the detection probability (p). Transition probabilities between states were thus modelled with a five-step procedure where s, r, β, ω and γ were considered as five successive steps in transition matrices.

Parameters of the model are defined in Table 1. We chose a MSMR approach since this allows taking into account the probability of detecting individuals given their return to the study site.

It also allows taking into account the previous breeding state of individuals which might be important to obtain unbiased estimates of demographic parameters [START_REF] Lebreton | Multistate recapture models: modelling incomplete individual histories[END_REF].

This MSMR model was parameterized by the survival-transition probabilities matrix:

[ srβ(1 -ω) srβω(1 -γ) srβωγ sr(1 -β) s(1 -r) - - * srβ(1 -ω) srβω(1 -γ) srβωγ sr(1 -β) s(1 -r) - - * srβ(1 -ω) srβω(1 -γ) srβωγ sr(1 -β) - s(1 -r) - * srβ(1 -ω) srβω(1 -γ) srβωγ sr(1 -β) - - s(1 -r) * srβ(1 -ω) srβω(1 -γ) srβωγ sr(1 -β) - - - * srβ(1 -ω) srβω(1 -γ) srβωγ sr(1 -β) - - - * srβ(1 -ω) srβω(1 -γ) srβωγ sr(1 -β) - - - * - - - - - - - * ]
Asterisks (*) in the column for dead birds ( †) represent the complementary parameter (complement of the sum of positive row entries). Models' construction and constraints on parameters were exactly the same than those previously detailed in a paper about the demographic consequences of blood Hg levels in the wandering albatross (Goutte et al. 2014b). We tested for an effect of Hg on demographic parameters to test the hypothesis that feather Hg levels in one breeding season may influence the long-term survival and breeding outputs of an individual over the following years. The 95% confidence interval of the slope parameters and AICc was used for inference. The goodness-offit (GOF) of the time-dependent MSMR model was tested using U-CARE (Choquet et al., 2009a). Model selection was based on AICc and all models were run under program E-SURGE 1.8.5 allowing splitting transition probabilities between states (Choquet et al., 2009b). To avoid estimating parameters at a local minimum of the likelihood function, each model was run five times with random initial values.

Results

Influence of biological and environmental factors on Hg bioaccumulation

Overall, feather Hg concentrations of wandering albatrosses averaged 24±12 µg g -1 and showed a wide range of values, from 6 to 95 µg g -1 (Table 2), with the latter value being considered an outlier. Univariate multifactorial analyses were performed to estimate the influence of sex, age, reproductive status, and feeding habitat (δ 13 C) on Hg concentrations in feathers of immature and adult birds separately, because feather Hg concentration was higher in immatures than in adults (32±15 versus 22±10 µg g -1 ; Table 2). For immature and adult albatrosses, multiple models had a similar support, and explained at best 17% and 23% of the total variation, respectively (Table 3). In immatures, age was clearly the most influential variable, with sex having also a relatively high explanatory power as shown by the sum of Akaike's weights across all models (Table 3). Feather Hg concentrations decreased with age in immature birds (Fig. 1a) and were overall lower in males than females (26±14 and 37±15 µg g -1 , respectively; Table 2).

The effect of sex on feather Hg concentrations was much stronger in adults than immature wandering albatrosses. In contrast to immature birds, age had no significant influence on feather Hg concentrations of adult albatrosses (Fig. 1b). Instead, the sum of Akaike's weights across all models showed that feather δ 13 C values and sex were the most influential variables on adult feather Hg concentrations (Table 3). Specifically, Hg concentrations were positively related to δ 13 C values (Fig. 2a) and were significantly lower in males than in females (19±10 vs. 26±9 µg g -1 , respectively; Table 2, Fig. 2). Hg concentrations were also positively related to δ 15 N values (Fig 2b), given the strong correlation between feather δ 13 C and δ 15 N values (see Materials and Methods).

Effects of Hg on current breeding output

The

Long-term fitness consequences of Hg exposure

The GOF of the MSMR model was overall not significant (males: χ² = 25.186, d.f. = 25, p = 0.452 and females: χ² = 7.094, d.f. = 25, p = 1.000). Model 5 and model 14 had lower AICc than the intercept model (Table 4) suggesting that Hg in feathers were negatively related to return rate of individuals previously in state SB and positively related to breeding probability of males previously in states FBE or FBC. However, AICc values with the intercept model were less than 2 (1.61 and 0.5) and the confidence intervals of estimated slope included 0 (Table 4). Therefore it must be considered that there was no effect of feather Hg levels on any demographic parameters.

Discussion

The present study benefits from the long-term demographic investigation (from 1965 onward) on wandering albatrosses from Possession Island, resulting in the unique sampling of >200 birds of known sex, age and breeding status during the same summer season. Together with previous investigations on blood Hg using the same individual birds (Carravieri et al., 2014b;Goutte et al., 2014b), this study is one of the most comprehensive evaluations of Hg levels, with its explanatory factors and demographic consequences, in free-living animals of known life-history traits. The previous studies considered blood Hg that represents the shortterm exposure of the birds, while the present work focused on feather Hg that represents the long-term exposure. Accumulated Hg since the last moult is excreted into the feathers, which represent more than one year exposure in the case of the wandering albatross.

Comparison to other populations and species

Average feather Hg concentration of wandering albatrosses from Possession Island (24 µg g -1 ) is within the range of values obtained in other localities from the southern Indian Ocean (Marion: 25 µg g -1 , Kerguelen: 17 µg g -1 ; [START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF]Carravieri et al. 2014c) and southern Atlantic Ocean (South Georgia: 20-27 µg g -1 ; [START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF][START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF][START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF]. This suggests that Hg has a fairly similar bioavailability within these different sectors of the Southern Ocean, which is in agreement with its circumpolar annular (latitudinal) oceanographic structure [START_REF] Sokolov | On the relationship between fronts of the Antarctic circumpolar current and surface chlorophyll concentrations in the Southern Ocean[END_REF]. The observed feather Hg levels in the wandering albatross confirm that large albatrosses (Family Diomedeidae; [START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF], together with some other Procellariiformes (Procellariidae and Hydrobatidae; [START_REF] Monteiro | Contemporary patterns of mercury contamination in the Portuguese Atlantic inferred from mercury concentrations in seabird tissues[END_REF]Carravieri et al. 2014c) are amongst the most Hgcontaminated seabird species overall (mean values >10 µg g -1 ) (authors' unpublished review).

Body feather Hg concentrations of wandering albatrosses from Possession Island varied with a 16 magnification factor among individuals, with one 23 years-old male showing the remarkably high feather concentration of 95 µg g -1 (Table 2). To the best of our knowledge, this value is the highest ever recorded in body feathers for any bird in the current open scientific literature, followed by the levels of one common loon Gavia immer (76 µg g -1 ; [START_REF] Evers | Adverse effects from environmental mercury loads on breeding common loons[END_REF], two other wandering albatrosses (75 and 73 µg g -1 ; this study and Thompson et al., 1993, respectively) and one common tern chick Sterna hirundo from a highly-polluted area (70 µg g - 1 ; [START_REF] Furness | Spatial and temporal variation in mercury contamination of seabirds in the North Sea[END_REF]. Noticeably, these values are well above the commonest used toxicity threshold (5 µg g -1 ; [START_REF] Burger | Risk, mercury levels, and birds: relating adverse laboratory effects to field biomonitoring[END_REF] and above the adverse effect threshold for adult loons (40 µg g -1 ), the best studied species in the wild up to date [START_REF] Evers | Adverse effects from environmental mercury loads on breeding common loons[END_REF]. Together with the highest Hg concentration reported in the liver of any bird species (1800 µg g -1 dw; [START_REF] Hindell | Mercury and cadmium concentrations in the tissues of three species of southern albatrosses[END_REF], the wandering albatross and probably related species of the Genus Diomedea, appear to be thus good model animals to investigate the detoxification mechanisms allowing to cope with such high Hg body burdens.

Explanatory factors

Interestingly, feather Hg concentrations of wandering albatrosses were only influenced by age in immature birds (pre-breeders) and no effect of this factor was detected in individuals over 12 years-old. The lack of age-dependent variation in Hg concentrations has already been reported for known-age seabirds both in blood of e.g. wandering albatrosses [START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF]Carravieri et al. 2014b), and in feathers of e.g. red-billed gulls Larus novaehollandiae and great skuas Catharacta skua [START_REF] Furness | Mercury levels in the plumage of red-billed gulls Larus novaehollandiae scopulinus of known sex and age[END_REF][START_REF] Thompson | Mercury accumulation in great skuas Catharacta skua of known age and sex, and its effects upon breeding and survival[END_REF], with also some possible decreasing trends being observed as in adult snow petrels [START_REF] Tartu | Age-related mercury contamination and relationship with luteinizing hormone in a long-lived Antarctic bird[END_REF]. Our finding for immature wandering albatrosses is consistent with the results of [START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF] who reported an increase of Hg concentrations between chicks and immature albatrosses returning for the first time to the colony (age ranging from 4 to 6 years) and then a decline to a lower constant average value in breeding adults. Although no chicks were sampled in the present study, it is noteworthy that wandering albatross chicks from South Georgia and Kerguelen

Islands had similar Hg levels, ranging between 2 to 10 µg g -1 [START_REF] Becker | Feather mercury levels in seabirds at South Georgia: influence of trophic position, sex and age[END_REF][START_REF] Blévin | Wide range of mercury contamination in chicks of Southern Ocean seabirds[END_REF][START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF]). These Hg levels represent the assimilated metal accumulated during chick growth over months that was ultimately excreted in newly grown feathers at the end of the period [START_REF] Lewis | Mercury accumulation and excretion in laboratory reared black-headed gull Larus ridibundus chicks[END_REF].The subsequent Hg bioaccumulation in fledged young albatrosses up to their first reproduction would therefore reflect elevated exposure to the metal.

The higher feather Hg concentrations in immatures than in adults would firstly be due to a difference in the foraging areas exploited by the two age classes. Indeed, taking into account latitudinal changes in δ 13 C in the southern Indian Ocean [START_REF] Jaeger | Seabird satellite tracking validates the use of latitudinal isoscapes to depict predators' foraging areas in the Southern Ocean[END_REF], lower δ 13 C values in the feathers of adult individuals show that they forage in more southern waters compared to immatures during the inter-breeding period (Table 2). Because of the temporal uncoupling of Hg (representing exposure during the whole inter-moult period) and stable isotopes (representing food assimilated during feather synthesis) in feathers, the use of stable isotopes to interpret Hg concentrations in this tissue has to be done cautiously [START_REF] Bond | Relationships between stable isotopes and metal contaminants in feathers are spurious and biologically uninformative[END_REF].

Nevertheless, adult individuals foraging at higher latitudes (subantarctic waters) had lower Hg concentrations compared to those foraging in the northern subtropics (Fig. 2). As immatures feed all year round in subtropical waters [START_REF] Jaeger | Age, sex, and breeding status shape a complex foraging pattern in an extremely long-lived seabird[END_REF][START_REF] Weimerskirch | Lifetime foraging patterns of the wandering albatross: life on the move[END_REF], they should be exposed to higher quantity of Hg compared to adults that forage at higher latitudes at least during the reproduction period.

Higher Hg concentrations in the feathers of immature rather than adult wandering albatrosses were attributed to differences in moulting patterns [START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF]. Indeed, immatures show greater difficulties in replacing their feathers because they are less experienced to find and catch their prey compared to breeders [START_REF] Weimerskirch | Sex-specific differences in molt strategy in relation to breeding in the Wandering albatross[END_REF]. If a nutritional deficit occurs, it might reduce the capacity of immature albatrosses to synthetize new feathers. The decreasing Hg levels with increasing age in immature birds corroborate this hypothesis, likely reflecting (i) the change in foraging behaviour (shift to more southern habitats) and (ii) the progressive establishment of a regular moult. Feather Hg concentrations reflect blood Hg concentrations at the time of moult [START_REF] Bearhop | Dynamics of mercury in blood and feathers of great skuas[END_REF][START_REF] Evers | Adverse effects from environmental mercury loads on breeding common loons[END_REF]. Feather Hg concentrations are therefore dependent of both (i) the exposure at the time of their synthesis (dietary Hg), and (ii) the release of Hg accumulated since the last moulting event [START_REF] Furness | Using bird feathers to measure mercury in the environment: relationship between mercury content and moult[END_REF][START_REF] Thompson | Seabirds as biomonitors of mercury inputs to epipelagic and mesopelagic marine food chains[END_REF]. Therefore, moult appears as a crucial mechanism of Hg detoxification in birds. If moult occurs at a lower frequency in immatures compared to adults, feather Hg concentrations should be higher in immatures. On the other hand, demethylation of Hg and its subsequent co-precipitation with Se in the liver of Procellariiforms appears to constitute a significant detoxification strategy [START_REF] Nigro | Intracellular storage of mercury and selenium in different marine vertebrates[END_REF]Thompson and Furness, 1989b;[START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF], which leads to extremely high concentrations of accumulated Hg in this organ (e.g. [START_REF] Muirhead | Heavy metal concentrations in the tissues of seabirds from Gough Island, South Atlantic Ocean[END_REF][START_REF] Stewart | Influence of phylogeny, diet, moult schedule and sex on heavy metal concentrations in New Zealand Procellariiformes[END_REF][START_REF] Hindell | Mercury and cadmium concentrations in the tissues of three species of southern albatrosses[END_REF]. It is possible that such a detoxification process is not yet fully efficient in young albatrosses, making feathers the major pathway of detoxification for this age class, whereas it may allow at maintaining almost constant the quantity of Hg subsequently excreted in feathers of adults.

In adult albatrosses, Hg concentrations were higher in females than in males showing that maternal transfer of Hg to the egg seems limited in the wandering albatross. Data for stable isotopes in both feathers (present study) and blood (Carravieri et al. 2014b) rather suggest that such a gender difference is related to sexual segregation in foraging areas and hence diets. Male wandering albatrosses mainly forage in subantarctic waters during the breeding period, whereas they moult in subtropical waters outside the breeding period [START_REF] Weimerskirch | Lifetime foraging patterns of the wandering albatross: life on the move[END_REF][START_REF] Jaeger | Age, sex, and breeding status shape a complex foraging pattern in an extremely long-lived seabird[END_REF]. On the other hand, females rely essentially on subtropical waters throughout their life, visiting also subantarctic waters during incubation [START_REF] Weimerskirch | Lifetime foraging patterns of the wandering albatross: life on the move[END_REF]. On average, females thus forage at more northern latitudes than males [START_REF] Jaeger | Age, sex, and breeding status shape a complex foraging pattern in an extremely long-lived seabird[END_REF]. Wandering albatrosses prey predominantly upon large squids, both at northern and southern latitudes [START_REF] Cherel | Spawning cycle of onychoteuthid squids in the southern Indian Ocean: new information from seabird predators[END_REF]. Cephalopods mainly bioaccumulate Hg under its methylated form (MeHg), which is thus highly bioavailable for their consumers [START_REF] Bustamante | Total and organic Hg concentrations in cephalopods from the North East Atlantic waters: influence of geographical origin and feeding ecology[END_REF].

Even if information on Hg concentrations in the prey of the wandering albatross is missing over its wide-range foraging area, it is likely that cephalopods from subtropical waters had higher Hg concentrations than those from the subantarctic area as it is the case in Kerguelen Island waters [START_REF] Bustamante | Distribution of trace elements in the tissues of benthic and pelagic fish from the Kerguelen Islands[END_REF]unpublished data). This would reduce the Hg bioaccumulation of adult males when compared to females, at least during the breeding period, as shown by blood Hg analyses (Carravieri et al., 2014b). This pattern has already been reported for other seabird species from the Kerguelen Islands, with species foraging predominantly within the limits of the Southern Ocean year-round (e.g. the light-mantled albatross Phoebetria palpebrata) having lower Hg concentrations than those foraging in northern subtropical and neritic waters (Carravieri et al. 2014c). In this context, the wandering albatross appears as a valuable species to document latitudinal variations in Hg transfer in their food web.

Demographic consequences of long-term Hg exposure

Few studies have explored the demographic consequences of Hg on wild aquatic birds, with a main focus on short-term exposure using blood Hg (e.g. [START_REF] Evers | Adverse effects from environmental mercury loads on breeding common loons[END_REF]Burgess and Meyers 2008;Goutte et al. 2014a[START_REF] Goutte | Survival rate and breeding outputs in a high Arctic seabird exposed to legacy persistent organic pollutants and mercury[END_REF]. Using a long-term data set and MSMR models, the present study is among the first to explore the effects of feather Hg on current breeding output, long-term fecundity and survival in seabirds. Even if Hg concentrations in body feathers were extremely high, no effect on neither breeding probability, hatching and fledgling successes, nor adult survival was detected. This finding contrasts strongly with results obtained with blood that highlighted a negative impact of Hg on long-term breeding, hatching and fledging probabilities in the wandering albatross (Goutte et al. 2014b). Contrary to previous studies on blood Hg (e.g. [START_REF] Brasso | Effects of mercury exposure on reproductive success of tree swallows (Tachycineta bicolor)[END_REF][START_REF] Frederick | Altered pairing behaviour and reproductive success in white ibises exposed to environmentally relevant concentrations of methylmercury[END_REF][START_REF] Tartu | To breed or not to breed: endocrine response to mercury contamination by an arctic seabird[END_REF][START_REF] Tartu | Age-related mercury contamination and relationship with luteinizing hormone in a long-lived Antarctic bird[END_REF]Tartu et al., , 2015)), no negative effect of feathers Hg was detected on the breeding probability and the breeding success at the year of sampling. These results deserve further investigations as one can expect that the integrated Hg would have stronger effect on reproduction than blood Hg concentrations during the reproductive period.

Although Hg in feathers is considered to be an integrative measure of total Hg body burden [START_REF] Furness | Using bird feathers to measure mercury in the environment: relationship between mercury content and moult[END_REF], our analyses did not detect any strong correlation between Hg in feathers and long-term reproductive outputs. As commented previously, feathers replacement in wandering albatross takes more than a year [START_REF] Weimerskirch | Sex-specific differences in molt strategy in relation to breeding in the Wandering albatross[END_REF], leading to Hg bioaccumulation in the liver (see above). Hence, Hg in feathers would reflect different exposure periods of wandering albatrosses according to the analysed feathers. In contrast, blood reflects dietary contaminants exposure during the energetically challenging breeding period, and Hg in blood appears to be more critical for long-term reproductive responses (Goutte et al. 2014ab).

Estimated demographic parameters were similar to those previously estimated in the same population of wandering albatrosses, using all ringed individuals (Pardo et al. 2013a;[START_REF] Barbraud | Estimating survival and reproduction in a quasi-biennially breeding seabird with uncertain and unobservable states[END_REF]. Despite high Hg concentrations in the feathers which revealed an elevated exposure to Hg since the previous moult (Carravieri et al. 2014a), the survival rate of wandering albatrosses was not jeopardized by Hg. This is consistent with previous studies that did not detect an effect of Hg on adult mortality in free-living birds [START_REF] Mitro | Common loon survival rates and mercury in New England and Wisconsin[END_REF][START_REF] Wayland | Survival rates and blood metal concentrations in two species of free-ranging North American sea ducks[END_REF][START_REF] Hallinger | Mercury exposure and survival in free-living tree swallows (Tachycineta bicolor)[END_REF]Goutte et al., 2014a[START_REF] Goutte | Survival rate and breeding outputs in a high Arctic seabird exposed to legacy persistent organic pollutants and mercury[END_REF].

However, our study did not exclude that Hg could jeopardize the survival rate of immature wandering albatrosses, since they had higher Hg concentrations [START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF], and lower survival rate [START_REF] Weimerskirch | Population dynamics of wandering albatross Diomedea exulans and Amsterdam albatross D. amsterdamensis in the Indian Ocean and their relationships with long-line fisheries: conservation implications[END_REF]) than sexually-mature adults.

Conclusion

The wandering albatrosses from Crozet Islands displayed remarkably elevated Hg concentrations in their feathers as a consequence of their high trophic position. Hg concentrations are the highest in immatures and, after birds start reproduction, they remained stable in adults. Both a different moulting frequency and detoxification processes could be responsible for such differences between maturity stages. In both immatures and adults, females had higher Hg concentrations as they forage at lower latitude on prey that are likely enriched in Hg compared to higher latitude prey. Despite elevated Hg concentrations in their feathers reflecting long-term exposure to the metal, no effect on the demographic parameters were evidenced suggesting that long-term bioaccumulated Hg was not under a form leading to deleterious effects.

  probability of breeding during the last breeding attempt (between 2005 and 2007) and during the 2008 season was not linked to Hg concentrations in feathers (last breeding attempt: df = 1,159, χ² = 1.742, p = 0.189; 2008: df = 1,165, χ² = 0.288, p = 0.592). When considering only breeders, current breeding success was not related to Hg levels in feathers (last breeding attempt: df = 1,118, χ² = 2.105, p = 0.147; 2008: df = 1,129, χ² = 1.849, p = 0.174).

Fig. 1 .

 1 Fig. 1. Hg concentrations (µg g -1 dw) in body feathers of immature and adult wandering albatrosses from Possession Island as a function of age. F: females; M: males; continuous line: GLM (gamma distribution, inverse link function: immature feather Hg = age).

Fig. 2 .

 2 Fig. 2. Hg concentrations (µg g -1 dw) in body feathers of adult wandering albatrosses from Possession Island as a function of a) feather δ 13 C and b) feather δ 15 N. F: females; M: males; continuous and dotted lines for females and males, respectively: GLM (gamma distribution, inverse link function: feather Hg = δ 13 C + sex and feather Hg = δ 15 N + sex ).

Table 1 .

 1 Definition of parameters used in the multistate mark-recapture modelProbability that an individual in state s at time t survives to time t + 1 and does not permanently emigrate from the study area r t

	Parameter	Definition
	s t s

s

  Probability that an individual in state s at time t returns at the colony to time t + 1 given that it survives to t + 1 β t

s

  Probability that an individual in state s at time t breeds at time t + 1 given that it survives to and returns at the colony at time t + 1 γ t

s

  Probability that an individual in state s at time t incubates successfully at time t + 1 given that it survives to, returns at the colony and breeds at time t + 1 δ t

s

  Probability that an individual in state s at time t raises successfully one chick at time t + 1 given that it survives to, returns at the colony and incubates successfully at time t Probability that an individual in state s at time t is encountered at time t + 1

	+ 1
	p t s

Table 2 .

 2 Hg concentrations (µg g -1 dw) and stable isotope values in body feathers of the wandering albatross from Possession Island (F: females; M: males).

	N	Hg		δ 13 C	δ 15 N
	Mean±SD	Min-Max	Mean±SD	Min-Max	Mean±SD Min-Max

Acknowledgements

The authors warmly thank: A. Jaeger and V. Lecomte for collecting samples; H. Maheo, M. Berlincourt and all the wintering fieldworkers involved in the long-term monitoring programs for their help in the field; C. Churlaud and M. Brault-Favrou from the Plateforme Analyses Elémentaires (LIENSs) and G. Guillou from the Plateforme Analyses Isotopiques (LIENSs) for their help in the analyses; D. Besson for managing the long-term data base. This study was supported financially and logistically by the Poitou-Charentes Region through a PhD grant to A. Carravieri, by the Agence Nationale de la Recherche (ANR PolarTop, O. Chastel), by the French Polar Institute (IPEV, program 109, H. Weimerskirch), by the Terres Australes et Antarctiques Françaises, the Zone Atelier de Recherches sur l'Environnement Antarctique et Subantarctique (CNRS-INEE) and by the CPER 13 (Contrat de Projet Etat-Région). Field procedures were authorized by the Ethics Committee of IPEV and by the Comité de l'Environnement Polaire.