Yannis Flet-Berliac
email: yannis.flet-berliac@inria.fr

Johan Ferret

Olivier Pietquin

Philippe Preux

Matthieu Geist

ADVERSARIALLY GUIDED ACTOR-CRITIC

Despite definite success in deep reinforcement learning problems, actor-critic algorithms are still confronted with sample inefficiency in complex environments, particularly in tasks where efficient exploration is a bottleneck. These methods consider a policy (the actor) and a value function (the critic) whose respective losses are built using different motivations and approaches. This paper introduces a third protagonist: the adversary. While the adversary mimics the actor by minimizing the KL-divergence between their respective action distributions, the actor, in addition to learning to solve the task, tries to differentiate itself from the adversary predictions. This novel objective stimulates the actor to follow strategies that could not have been correctly predicted from previous trajectories, making its behavior innovative in tasks where the reward is extremely rare. Our experimental analysis shows that the resulting Adversarially Guided Actor-Critic (AGAC) algorithm leads to more exhaustive exploration. Notably, AGAC outperforms current state-of-the-art methods on a set of various hard-exploration and procedurally-generated tasks.

INTRODUCTION

Research in deep reinforcement learning (RL) has proven to be successful across a wide range of problems [START_REF] Silver | Deterministic policy gradient algorithms[END_REF][START_REF] Schulman | High-dimensional continuous control using generalized advantage estimation[END_REF][START_REF] Lillicrap | Continuous control with deep reinforcement learning[END_REF][START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF]. Nevertheless, generalization and exploration in RL still represent key challenges that leave most current methods ineffective. First, a battery of recent studies [START_REF] Farebrother | Generalization and regularization in dqn[END_REF]Zhang et al., 2018a;[START_REF] Song | Observational overfitting in reinforcement learning[END_REF][START_REF] Cobbe | Leveraging procedural generation to benchmark reinforcement learning[END_REF] indicates that current RL methods fail to generalize correctly even when agents have been trained in a diverse set of environments. Second, exploration has been extensively studied in RL; however, most hard-exploration problems use the same environment for training and evaluation. Hence, since a well-designed exploration strategy should maximize the information received from a trajectory about an environment, the exploration capabilities may not be appropriately assessed if that information is memorized. In this line of research, we choose to study the exploration capabilities of our method and its ability to generalize to new scenarios. Our evaluation domains will, therefore, be tasks with sparse reward in procedurally-generated environments.

In this work, we propose Adversarially Guided Actor-Critic (AGAC), which reconsiders the actor-critic framework by introducing a third protagonist: the adversary. Its role is to predict the actor's actions correctly. Meanwhile, the actor must not only find the optimal actions to maximize the sum of expected returns, but also counteract the predictions of the adversary. This formulation is lightly inspired by adversarial methods, specifically generative adversarial networks (GANs) [START_REF] Goodfellow | Generative adversarial nets[END_REF]. Such a link between GANs and actor-critic methods has been formalized by [START_REF] Pfau | Connecting generative adversarial networks and actor-critic methods[END_REF]; however, in the context of a third protagonist, we draw a different analogy. The adversary can be interpreted as playing the role of a discriminator that must predict the actions of the actor, and the actor can be considered as playing the role of a generator that behaves to deceive the predictions of the adversary. This approach has the advantage, as with GANs, that the optimization procedure generates a diversity of meaningful data, corresponding to sequences of actions in AGAC.

This paper analyses and explores how AGAC explicitly drives diversity in the behaviors of the agent while remaining reward-focused, and to which extent this approach allows to adapt to the evolving state space of procedurally-generated environments where the map is constructed differently with each new episode. Moreover, because stability is a legitimate concern since specific instances of adversarial networks were shown to be prone to hyperparameter sensitivity issues [START_REF] Arjovsky | Towards principled methods for training generative adversarial networks[END_REF], we also examine this aspect in our experiments.

The contributions of this work are as follow: (i) we propose a novel actor-critic formulation inspired from adversarial learning (AGAC), (ii) we analyse empirically AGAC on key reinforcement learning aspects such as diversity, exploration and stability, (iii) we demonstrate significant gains in performance on several sparse-reward hard-exploration tasks including procedurally-generated tasks.

RELATED WORK

Actor-critic methods [START_REF] Barto | Neuronlike adaptive elements that can solve difficult learning control problems[END_REF][START_REF] Stuart | Temporal Credit Assignment in Reinforcement Learning[END_REF] have been extended to the deep learning setting by [START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF], who combined deep neural networks and multiple distributed actors with an actor-critic setting, with strong results on Atari. Since then, many additions have been proposed, be it architectural improvements (Vinyals et al., 2019), better advantage or value estimation [START_REF] Schulman | High-dimensional continuous control using generalized advantage estimation[END_REF][START_REF] Flet-Berliac | Learning value functions in deep policy gradients using residual variance[END_REF], or the incorporation of off-policy elements [START_REF] Wang | Sample efficient actor-critic with experience replay[END_REF][START_REF] Oh | Self-imitation learning[END_REF][START_REF] Flet | Only relevant information matters: Filtering out noisy samples to boost rl[END_REF]. Regularization was shown to improve actor-critic methods, either by enforcing trust regions [START_REF] Schulman | Trust region policy optimization[END_REF]2017;[START_REF] Wu | Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation[END_REF], or by correcting for off-policiness [START_REF] Munos | Safe and efficient off-policy reinforcement learning[END_REF][START_REF] Gruslys | The reactor: A fast and sample-efficient actor-critic agent for reinforcement learning[END_REF]; and recent works analyzed its impact from a theoretical standpoint [START_REF] Geist | A theory of regularized markov decision processes[END_REF][START_REF] Ahmed | Understanding the impact of entropy on policy optimization[END_REF]Vieillard et al., 2020a;b). Related to our work, [START_REF] Han | Diversity actor-critic: Sample-aware entropy regularization for sample-efficient exploration[END_REF] use the entropy of the mixture between the policy induced from a replay buffer and the current policy as a regularizer. To the best of our knowledge, none of these methods explored the use of an adversarial objective to drive exploration.

While introduced in supervised learning, adversarial learning [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF][START_REF] Miyato | Distributional smoothing with virtual adversarial training[END_REF][START_REF] Kurakin | Adversarial machine learning at scale[END_REF] was leveraged in several RL works. [START_REF] Ho | Generative adversarial imitation learning[END_REF] propose an imitation learning method that uses a discriminator whose task is to distinguish between expert trajectories and those of the agent while the agent tries to match expert behavior to fool the discriminator. [START_REF] Bahdanau | Learning to understand goal specifications by modelling reward[END_REF] use a discriminator to distinguish goal states from non-goal states based on a textual instruction, and use the resulting model as a reward function. [START_REF] Florensa | Automatic goal generation for reinforcement learning agents[END_REF] use a GAN to produce sub-goals at the right level of difficulty for the current agent, inducing a form of curriculum. Additionally, [START_REF] Pfau | Connecting generative adversarial networks and actor-critic methods[END_REF] provide a parallel between GANs and the actor-critic framework.

While exploration is driven in part by the core RL algorithms [START_REF] Fortunato | Noisy networks for exploration[END_REF][START_REF] Han | Diversity actor-critic: Sample-aware entropy regularization for sample-efficient exploration[END_REF][START_REF] Ferret | Self-imitation advantage learning[END_REF], it is often necessary to resort to exploration-specific techniques. For instance, intrinsic motivation encourages exploratory behavior from the agent. Some works use state-visitation counts or pseudo-counts to promote exhaustive exploration (Bellemare et al., 2016a), while others use curiosity rewards, expressed in the magnitude of prediction error from the agent, to push it towards unfamiliar areas of the state space [START_REF] Burda | Exploration by random network distillation[END_REF]. [START_REF] Ecoffet | Go-explore: a new approach for hard-exploration problems[END_REF] propose a technique akin to tree traversal to explore while learning to come back to promising areas. [START_REF] Eysenbach | Diversity is all you need: Learning skills without a reward function[END_REF] show that encouraging diversity helps with exploration, even in the absence of reward.

Last but not least, generalization is a key challenge in RL. Zhang et al. (2018b) showed that, even when the environment is not deterministic, agents can overfit to their training distribution and that it is difficult to distinguish agents likely to generalize to new environments from those that will not. In the same vein, recent work has advocated using procedurally-generated environments, in which a new instance of the environment is sampled when a new episode starts, to assess generalization capabilities better [START_REF] Justesen | Illuminating generalization in deep reinforcement learning through procedural level generation[END_REF][START_REF] Cobbe | Leveraging procedural generation to benchmark reinforcement learning[END_REF]. Finally, methods based on network randomization [START_REF] Igl | Generalization in reinforcement learning with selective noise injection and information bottleneck[END_REF], noise injection [START_REF] Lee | Network randomization: A simple technique for generalization in deep reinforcement learning[END_REF], and credit assignment [START_REF] Ferret | Self-attentional credit assignment for transfer in reinforcement learning[END_REF] have been proposed to reduce the generalization gap for RL agents.

BACKGROUND AND NOTATIONS

We place ourselves in the Markov Decision Processes [START_REF] Puterman | Markov Decision Processes[END_REF] framework. A Markov Decision Process (MDP) is a tuple M = {S, A, P, R, γ}, where S is the state space, A is the action space, P is the transition kernel, R is the bounded reward function and γ ∈ [0, 1) is the discount factor. Let π denote a stochastic policy mapping states to distributions over actions. We place ourselves in the infinite-horizon setting, i.e., we seek a policy that optimizes

J(π) = E π [ ∞ t=0 γ t r (s t , a t )].
The value of a state is the quantity V π (s) = E π [ ∞ t=0 γ t r (s t , a t ) |s 0 = s] and the value of a state-action pair Q π (s, a) of performing action a in state s and then following policy π is defined as:

Q π (s, a) = E π [ ∞ t=0 γ t r (s t , a t ) |s 0 = s, a 0 = a].
The advantage function, which quantifies how an action a is better than the average action in state s, is A π (s, a) = Q π (s, a) -V π (s). Finally, the entropy H π of a policy is calculated as:

H π (s) = E π(•|s) [-log π(•|s)] .
Actor-Critic and Deep Policy Gradients. An actor-critic algorithm is composed of two main components: a policy and a value predictor. In deep RL, both the policy and the value function are obtained via parametric estimators; we denote θ and φ their respective parameters. The policy is updated via policy gradient, while the value is usually updated via temporal difference or Monte Carlo rollouts. In practice, for a sequence of transitions {s t , a t , r t , s t+1 } t∈[0,N ] , we use the following policy gradient loss (including the commonly used entropic penalty):

L P G = - 1 N t+N t =t (A t log π (a t |s t , θ) + αH π (s t , θ)),
where α is the entropy coefficient and A t is the generalized advantage estimator [START_REF] Schulman | High-dimensional continuous control using generalized advantage estimation[END_REF] defined as:

A t = t+N t =t (γλ) t -t (r t + γV φold (s t +1 ) -V φold (s t ))
, with λ a fixed hyperparameter and V φold the value function estimator at the previous optimization iteration. To estimate the value function, we solve the non-linear regression problem minimize φ t+N t =t (V φ (s t ) -Vt ) 2 where Vt = A t + V φold (s t ).

ADVERSARIALLY GUIDED ACTOR-CRITIC

To foster diversified behavior in its trajectories, AGAC introduces a third protagonist to the actor-critic framework: the adversary. The role of the adversary is to accurately predict the actor's actions, by minimizing the discrepancy between its action distribution π adv and the distribution induced by the policy π. Meanwhile, in addition to finding the optimal actions to maximize the sum of expected returns, the actor must also counteract the adversary's predictions by maximizing the discrepancy between π and π adv (see Appendix B for an illustration). This discrepancy, used as a form of exploration bonus, is defined as the difference of action log-probabilities (see Eq. ( 1)), whose expectation is the Kullback-Leibler divergence:

D KL (π(•|s) π adv (•|s)) = E π(•|s) [log π(•|s) -log π adv (•|s)] .
Formally, for each state-action pair (s t , a t ) in a trajectory, an action-dependent bonus log π(a t |s t )log π adv (a t |s t ) is added to the advantage. In addition, the value target of the critic is modified to include the action-independent equivalent, which is the KL-divergence D KL (π(•|s t ) π adv (•|s t )). We discuss the role of these mirrored terms below, and the implications of AGAC's modified objective from a more theoretical standpoint in the next section. In addition to the parameters θ (resp. θ old the parameter of the policy at the previous iteration) and φ defined above (resp. φ old that of the critic), we denote ψ (resp. ψ old ) that of the adversary.

AGAC minimizes the following loss:

L AGAC = L PG + β V L V + β adv L adv .
In the new objective

L P G = -1 N N t=0 (A AGAC t log π (a t |s t , θ) + αH π (s t , θ))
, AGAC modifies A t as:

A AGAC t = A t + c log π(a t |s t , θ old ) -log π adv (a t |s t , ψ old ) , (1)
with c a varying hyperparameter that controls the dependence on the action log-probability difference.

To encourage exploration without preventing asymptotic stability, c is linearly annealed during the course of training. L V is the objective function of the critic defined as:

L V = 1 N N t=0 V φ (s t ) -Vt + c D KL (π(•|s t , θ old ) π adv (•|s t , ψ old )) 2 . (2)
Finally, L adv is the objective function of the adversary:

L adv = 1 N N t=0 D KL (π(•|s t , θ old ) π adv (•|s t , ψ)). (3)
Eqs. ( 1), ( 2) and ( 3) are the three equations that our method modifies (we color in blue the specific parts) in the traditional actor-critic framework. The terms β V and β adv are fixed hyperparameters.

Under the proposed actor-critic formulation, the probability of sampling an action is increased if the modified advantage is positive, i.e. (i) the corresponding return is larger than the predicted value and/or (ii) the action log-probability difference is large. More precisely, our method favors transitions whose actions were less accurately predicted than the average action, i.e. log π(a|s) -

log π adv (a|s) ≥ D KL (π(•|s) π adv (•|s))
. This is particularly visible for λ → 1, in which case the generalized advantage is A t = G t -V φold (s t ), resulting in the appearance of both aforementioned mirrored terms in the modified advantage:

A AGAC t = G t -V φold t + c log π(a t |s t ) -log π adv (a t |s t ) -Dφold KL (π(•|s t ) π adv (•|s t )) ,
with G t the observed return, V φold t the estimated return and Dφold KL (π(•|s t ) π adv (•|s t )) the estimated KL-divergence (estimated components of V φold (s t ) from Eq. 2).

To avoid instability, in practice the adversary is a separate estimator, updated with a smaller learning rate than the actor. This way, it represents a delayed and more steady version of the actor's policy, which prevents the agent from having to constantly adapt or focus solely on fooling the adversary.

BUILDING MOTIVATION

In the following, we provide an interpretation of AGAC by studying the dynamics of attraction and repulsion between the actor and the adversary. To simplify, we study the equivalent of AGAC in a policy iteration (PI) scheme. PI being the dynamic programming scheme underlying the standard actor-critic, we have reasons to think that some of our findings translate to the original AGAC algorithm. In PI, the quantity of interest is the action-value, which AGAC would modify as:

Q AGAC π k = Q π k + c (log π k -log π adv )
, with π k the policy at iteration k. Incorporating the entropic penalty, the new policy π k+1 verifies:

π k+1 = arg max π J PI (π) = arg max π E s E a∼π(•|s) [Q AGAC π k (s, a) -α log π(a|s)].
We can rewrite this objective:

J PI (π) = E s E a∼π(•|s) [Q AGAC π k (s, a) -α log π(a|s)] = E s E a∼π(•|s) [Q π k (s, a) + c (log π k (a|s) -log π adv (a|s)) -α log π(a|s)] = E s E a∼π(•|s) [Q π k (s, a) + c (log π k (a|s) -log π(a|s) + log π(a|s) -log π adv (a|s)) -α log π(a|s)] = E s E a∼π(•|s) [Q π k (s, a)] -c D KL (π(•|s)||π k (•|s)) π k is attractive + c D KL (π(•|s)||π adv (•|s)) πadv is repulsive + α H(π(•|s)) enforces stochastic policies .
Thus, in the PI scheme, AGAC finds a policy that maximizes Q-values, while at the same time remaining close to the current policy and far from a mixture of the previous policies (i.e., π k-1 , π k-2 , π k-3 , . . . ). Note that we experimentally observe (see Section 5.3) that our method performs better with a smaller learning rate for the adversarial network than that of the other networks, which could imply that a stable repulsive term is beneficial. This optimization problem is strongly concave in π (thanks to the entropy term), and is state-wise a Legendre-Fenchel transform. Its solution is given by (see Appendix E for the full derivation):

π k+1 ∝ π k π adv c α exp Q π k α .
This result gives us some insight into the behavior of the objective function. Notably, in our example, if π adv is fixed and c = α, we recover a KL-regularized PI scheme [START_REF] Geist | A theory of regularized markov decision processes[END_REF] with the modified reward r -c log π adv .

IMPLEMENTATION

In all of the experiments, we use PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] as the base algorithm and build on it to incorporate our method. Hence,

L P G = - 1 N t+N t =t min π(a t |s t , θ) π(a t |s t , θ old ) A AGAC t , clip π(a t |s t , θ) π(a t |s t , θ old ) , 1 -, 1 + A AGAC t ,
with A AGAC t given in Eq. ( 1), N the temporal length considered for one update of parameters and the clipping parameter. Similar to RIDE [START_REF] Raileanu | Ride: Rewarding impact-driven exploration for procedurallygenerated environments[END_REF], we also discount PPO by episodic state visitation counts, except for VizDoom (cf. Section 5.1). The actor, critic and adversary use the convolutional architecture of the Nature paper of DQN [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] with different hidden sizes (see Appendix D for architecture details). The three neural networks are optimized using Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF]. Our method does not use RNNs in its architecture; instead, in all our experiments, we use frame stacking. Indeed, [START_REF] Hausknecht | Deep recurrent q-learning for partially observable mdps[END_REF] interestingly demonstrate that although recurrence is a reliable method for processing state observation, it does not confer any systematic advantage over stacking observations in the input layer of a CNN. Note that the parameters are not shared between the policy, the critic and the adversary and that we did not observe any noticeable difference in computational complexity when using AGAC compared to PPO. We direct the reader to Appendix C for a list of hyperparameters. In particular, the c coefficient of the adversarial bonus is linearly annealed.

At each training step, we perform a stochastic optimization step to minimize L AGAC using stop-gradient:

θ ← Adam (θ, ∇ θ L P G , η 1 ) , φ ← Adam (φ, ∇ φ L V , η 1 ) , ψ ← Adam (ψ, ∇ ψ L adv , η 2 ) .

EXPERIMENTS

In this section, we describe our experimental study in which we investigate: (i) whether the adversarial bonus alone (e.g. without episodic state visitation count) is sufficient to outperform other methods in VizDoom, a sparse-reward task with high-dimensional observations, (ii) whether AGAC succeeds in partially-observable and procedurally-generated environments with high sparsity in the rewards, compared to other methods, (iii) how well AGAC is capable of exploring in environments without extrinsic reward, (iv) the training stability of our method. In all of the experiments, lines are average performances and shaded areas represent one standard deviation. The code for our method is released at github.com/yfletberliac/adversarially-guided-actor-critic. Environments. To carefully evaluate the performance of our method, its ability to develop robust exploration strategies and its generalization to unseen states, we choose tasks that have been used in prior work, which are tasks with high-dimensional observations, sparse reward and procedurallygenerated environments. In VizDoom [START_REF] Kempka | Vizdoom: A doom-based ai research platform for visual reinforcement learning[END_REF], the agent must learn to move along corridors and through rooms without any reward feedback from the 3-D environment. The MiniGrid environments (Chevalier-Boisvert et al., 2018) are a set of challenging partially-observable and sparse-reward gridworlds. In this type of procedurally-generated environments, memorization is impossible due to the huge size of the state space, so the agent must learn to generalize across the different layouts of the environment. Each gridworld has different characteristics: in the MultiRoom tasks, the agent is placed in the first room and should reach a goal placed in the most distant room. In the KeyCorridor tasks, the agent must navigate to pick up an object placed in a room locked by a door whose key is in another room. Finally, in the ObstructedMaze tasks, the agent must pick up a box that is placed in a corner of a 3x3 maze in which the doors are also locked, the keys are hidden in boxes and balls obstruct the doors. All considered environments (see Fig. 1 for some examples) are available as part of OpenAI Gym [START_REF] Brockman | Openai gym[END_REF].

Baselines. For a fair assessment of our method, we compare to some of the most prominent methods specialized in hard-exploration tasks: RIDE [START_REF] Raileanu | Ride: Rewarding impact-driven exploration for procedurallygenerated environments[END_REF], based on an intrinsic reward associated with the magnitude of change between two consecutive state representations and state visitation, Count as Count-Based Exploration (Bellemare et al., 2016b), which we couple with IMPALA [START_REF] Espeholt | Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures[END_REF], RND [START_REF] Burda | Exploration by random network distillation[END_REF] in which an exploration bonus is positively correlated to the error of predicting features from the observations and ICM [START_REF] Pathak | Curiosity-driven exploration by self-supervised prediction[END_REF], where a module only predicts the changes in the environment that are produced by the actions of the agent. Finally, we compare to most the recent and best performing method at the time of writing in procedurally-generated environments: AMIGo [START_REF] Campero | Learning with amigo: Adversarially motivated intrinsic goals[END_REF] in which a goal-generating teacher provides count-based intrinsic goals. In this section, we assess the benefits of using an adversarially-based exploration bonus and examine how AGAC performs without the help of count-based exploration. In order to provide a comparison to state-of-the-art methods, we choose VizDoom, a hard-exploration problem used in prior work. In this game, the map consists of 9 rooms connected by corridors where 270 steps separate the initial position of the agent and the goal under an optimal policy. Episodes are terminated either when the agent finds the goal or if the episode exceeds 2100 timesteps. Importantly, while other algorithms [START_REF] Raileanu | Ride: Rewarding impact-driven exploration for procedurallygenerated environments[END_REF][START_REF] Campero | Learning with amigo: Adversarially motivated intrinsic goals[END_REF] benefit from count-based exploration, this study has been conducted with our method not benefiting from episodic count whatsoever. Results in Table 1 indicate that AGAC clearly outperforms other methods in sample-efficiency. Only the methods ICM and RIDE succeed in matching the score of AGAC, and with about twice as much transitions (∼ 3M vs. 6M). Interestingly, AMIGo performs similarly to Count and RND. We find this result surprising because AMIGo has proven to perform well in the MiniGrid environments. Nevertheless, it appears that concurrent works to ours experienced similar issues with the accompanying implementation1 . The results of AGAC support the capabilities of the adversarial bonus and show that it can, on its own, achieve significant gains in performance. However, the VizDoom task is not procedurally-generated; hence we have not evaluated the generalization to new states yet. In the following section, we use MiniGrid to investigate this.

ADVERSARIALLY-BASED EXPLORATION (NO EPISODIC COUNT)

HARD-EXPLORATION TASKS WITH PARTIALLY-OBSERVABLE ENVIRONMENTS

We now evaluate our method on multiple hard-exploration procedurally-generated tasks from Mini-Grid. Details about MiniGrid can be found in Appendix C.1. Fig. 2 indicates that AGAC significantly outperforms other methods on these tasks in sample-efficiency and performance. AGAC also outperforms the current state-of-the-art method, AMIGo, despite the fact that it uses the fully-observable version of MiniGrid. Note that we find the same poor performance results when training AMIGo in MiniGrid, similar to Vizdoom results. For completeness, we also report in (2019) and [START_REF] Campero | Learning with amigo: Adversarially motivated intrinsic goals[END_REF]. We draw similar conclusions: AGAC clearly outperforms the state-of-the-art RIDE, AMIGo, Count, RND and ICM.

In all the considered tasks, the agent must learn to generalize across a very large state space because the layouts are generated procedurally. We consider three main arguments to explain why our method is successful: (i) our method makes use of partial observations: in this context, the adversary has a harder time predicting the actor's actions; nevertheless, the mistakes of the former benefit the latter in the form of an exploration bonus, which pushes the agent to explore further in order to deceive the adversary, (ii) the exploration bonus (i.e. intrinsic reward) does not dissipate compared to most other methods, as observed in Fig. 9 in Appendix A.4, (iii) our method does not make assumptions about the environment dynamics (e.g., changes in the environment produced by an action as in [START_REF] Raileanu | Ride: Rewarding impact-driven exploration for procedurallygenerated environments[END_REF]) since this can hinder learning when the space of state changes induced by an action is too large (such as the action of moving a block in ObstructedMaze).

In Appendix A.3, we also include experiments in two environments with extremely sparse reward signals: KeyCorridorS8R3 and ObstructedMazeFull. Despite the challenge, AGAC still manages to find rewards and can perform well by taking advantage of the diversified behaviour induced by our method. To the best of our knowledge, no other method ever succeeded to perform well (> 0 average return) in those tasks. We think that given more computing time, AGAC's score could go higher. Here we want to analyse the stability of the method when changing hyperparameters. The most important parameters in AGAC are c, the coefficient for the adversarial bonus, and the learning rates ratio ν = η2 η1 . We choose KeyCorridorS4R3 as the evaluation task because among all the tasks considered, its difficulty is at a medium level. Fig. 3 shows the learning curves. For readability, we plot the average return only; the standard deviation is sensibly the same for all curves. We observe that deviating from the hyperparameter values found using grid search results in a slower training. Moreover, although reasonable, c appears to have more sensitivity than ν. To better understand the effectiveness of our method and inspect how the agent collects rewards that would not otherwise be achievable by simple exploration heuristics or other methods, we analyze the performance of AGAC in another (procedurally-generated) challenging environment, MultiRoomN10S6, when there is no reward signal, i.e. no extrinsic reward.

TRAINING STABILITY

Beyond the good performance of our method when extrinsic rewards are given to the agent, Fig. 4 indicates that the exploration induced by our method makes the agent succeed in a significant proportion of the episodes: in the configuration "NoExtrinsi-cReward" the reward signal is not given (the goal is invisible to the agent) and the performance of AGAC stabilizes around an average return of ∼ 0.15.

Since the return of an episode is either 0 or 1 (depending on whether the agent reached the goal state or not), and because this value is aggregated across several episodes, the results indicate that reward-free AGAC succeeds in ∼ 15% of the tasks. Comparatively, random agents have a zero average return. This poor performance is in accordance with the results in [START_REF] Raileanu | Ride: Rewarding impact-driven exploration for procedurallygenerated environments[END_REF] and reflects the complexity of the task: in order to go from one room to another, an agent must perform a specific action to open a door and cross it within the time limit of 200 timesteps. In the following, we visually investigate how different methods explore the environments.

VISUALIZING COVERAGE AND DIVERSITY

In this section, we first investigate how different methods explore environments without being guided by extrinsic rewards (the green goal is invisible to the agent) on both procedurally-generated and singleton environments. In singleton environments, an agent has to solve the same task in the same environment/maze in every episode. Fig. 5 shows the state visitation heatmaps (darker areas correspond to more visits) after a training of 10M timesteps. We observe that most of the methods explore inefficiently in a singleton environment and that only RIDE succeeds in reaching the fifth room while AGAC reaches the last (tenth) room. After training the agents in procedurally-generated environments, the methods explore even less efficiently while AGAC succeeds in exploring all rooms. We now qualitatively study the diversity of an agent's behavior when trained with AGAC. Fig. 6 presents the state visitation heatmaps of the last ten episodes for an agent trained in procedurallygenerated environments in the MultiRoomN10S6 task without extrinsic reward. The heatmaps correspond to the behavior of the resulting policy, which is still learning from the AGAC objective.

Looking at the figure, we can see that the strategies vary at each update with, for example, backand-forth and back-to-start behaviors. Although there are no extrinsic reward, the strategies seem to diversify from one update to the next. Finally, Fig. 7 in Appendix A.2 shows the state visitation heatmaps in a different configuration: when the agent has been trained on a singleton environment in the MultiRoomN10S6 task without extrinsic reward. Same as previously, the agent is updated between each episode. Looking at the figure, we can make essentially the same observations as previously, with a noteworthy behavior in the fourth heatmap of the bottom row where it appears the agent went to the fourth room to remain inside it. Those episodes indicate that, although the agent sees the same environment repeatedly, the successive adversarial updates force it to continuously adapt its behavior and try new strategies.

DISCUSSION

This paper introduced AGAC, a modification to the traditional actor-critic framework: an adversary network is added as a third protagonist. The mechanics of AGAC have been discussed from a policy iteration point of view, and we provided theoretical insight into the inner workings of the proposed algorithm: the adversary forces the agent to remain close to the current policy while moving away from the previous ones. In a nutshell, the influence of the adversary makes the actor conservatively diversified.

In the experimental study, we have evaluated the adversarially-based bonus in VizDoom and empirically demonstrated its effectiveness and superiority compared to other relevant methods (some benefiting from count-based exploration). Then, we have conducted several performance experiments using AGAC and have shown a significant performance improvement over some of the most popular exploration methods (RIDE, AMIGo, Count, RND and ICM) on a set of various challenging tasks from MiniGrid. These procedurally-generated environments have served another purpose which is to validate the capacity of our method to generalize to unseen scenarios. In addition, the training stability of our method has been studied, showing a greater but acceptable sensitivity for c, the adversarial bonus coefficient. Finally, we have investigated the exploration capabilities of AGAC in a reward-free setting where the agent demonstrated exhaustive exploration through various strategic choices, confirming that the adversary successfully drives diversity in the behavior of the actor.

A ADDITIONAL EXPERIMENTS

A.1 MINIGRID PERFORMANCE

In this section, we report the final performance of all methods considered in the MiniGrid experiments of Fig. 2 with the scores reported in [START_REF] Raileanu | Ride: Rewarding impact-driven exploration for procedurallygenerated environments[END_REF] and [START_REF] Campero | Learning with amigo: Adversarially motivated intrinsic goals[END_REF]. All methods have a budget of 200M frames.

A.2 STATE VISITATION HEATMAPS IN SINGLETON ENVIRONMENT WITH NO EXTRINSIC REWARD

In this section, we provide additional state visitation heatmaps. The agent has been trained on a singleton environment from the MultiRoomN10S6 task without extrinsic reward. The last ten episodes of the training suggest that although the agent experiences the same maze over and over again, the updates force it to change behavior and try new strategies.

A.3 (EXTREMELY) HARD-EXPLORATION TASKS WITH PARTIALLY-OBSERVABLE ENVIRONMENTS

In this section, we include additional experiments on one of the hardest tasks available in MiniGrid.

The first is KeyCorridorS8R3, where the size of the rooms has been increased. In it, the agent has to pick up an object which is behind a locked door: the key is hidden in another room and the agent has to explore the environment to find it. The second, ObstructedMazeFull, is similar to ObstructedMaze4Q, where the agent has to pick up a box which is placed in one of the four corners of a 3x3 maze: the doors are locked, the keys are hidden in boxes and the doors are obstructed by balls. In those difficult tasks, only our method succeeds in exploring well enough to find rewards.

A.4 MEAN INTRINSIC REWARD

In this section, we report the mean intrinsic reward computed for an agent trained in Multi-RoomN12S10 to conveniently compare our results with that of [START_REF] Raileanu | Ride: Rewarding impact-driven exploration for procedurallygenerated environments[END_REF]. We observe in Fig. 9 that the intrinsic reward is consistently larger for our method and that, contrary to other methods, does not converge to low values. Please note that, in all considered experiments, the adversarial bonus coefficient c in Eq. 2 and 3 is linearly annealed throughout the training since it is mainly useful at the beginning of learning when the rewards have not yet been met. In the long run, this coefficient may prevent the agent from solving the task by forcing it to always favour exploration over exploitation.

Figure 1 :

 1 Figure 1: (a,b) Frames from the 3-D navigation task VizdoomMyWayHome. (c) MiniGrid-KeyCorridorS6R3. (d) MiniGrid-ObstructedMazeFull.

Figure 2 :

 2 Figure 2: Performance evaluation of AGAC.

Figure 3 :

 3 Figure 3: Sensitivity analysis of AGAC in KeyCorridorS4R3.

Figure 5 :Figure 4 :

 54 Figure 5: State visitation heatmaps for RND, Count, a random uniform policy, RIDE, and AGAC trained in a singleton environment (top row) and procedurally-generated environments (bottom row) without extrinsic reward for 10M timesteps in the MultiRoomN10S6 task.

Figure 6 :

 6 Figure 6: State visitation heatmaps of the last ten episodes of an agent trained in procedurallygenerated environments without extrinsic reward for 10M timesteps in the MultiRoomN10S6 task. The agent is continuously engaging in new strategies.

Figure 7 :

 7 Figure 7: State visitation heatmaps of the last ten episodes of an agent trained in a singleton environment with no extrinsic reward 10M timesteps in the MultiRoomN10S6 task. The agent is continuously engaging into new strategies.

Figure 8 :

 8 Figure 8: Performance evaluation of AGAC compared to RIDE, AMIGo, Count, RND and ICM on extremely hard-exploration problems.

Figure 9 :

 9 Figure 9: Average intrinsic reward for different methods trained in MultiRoomN12S10.

Table 1 :

 1 Average return in VizDoom at different timesteps.

	Nb. of Timesteps	2M	4M	6M	8M	10M
	AGAC	0.74 ± 0.05 0.96 ± 0.001 0.96 ± 0.001 0.97 ± 0.001 0.97 ± 0.001
	RIDE	0.	0.	0.95 ± 0.001 0.97 ± 0.001 0.97 ± 0.001
	ICM	0.	0.	0.95 ± 0.001 0.97 ± 0.001 0.97 ± 0.001
	AMIGo	0.	0.	0.	0.	0.
	RND	0.	0.	0.	0.	0.
	Count	0.	0.	0.	0.	0.

Table 2 :

 2 Final average performance of all methods on several MiniGrid environments.

	Task	KC-S4R3 KC-S5R3 MR-N10S10 OM-2Dlhb OM-1Q OM-2Q
	AGAC	0.95	0.93	0.52	0.64	0.78	0.63
	RIDE	0.19	0.	0.40	0.	0.	0.
	AMIGo	0.54	0.	0.	0.20	0.	0.
	RND	0.	0.	0.	0.03	0.	0.
	Count	0.	0.	0.	0.	0.	0.
	ICM	0.	0.	0.	0.	0.	0.

AMIGo implementation GitHub Issue.

C EXPERIMENTAL DETAILS AND HYPERPARAMETERS

C.1 MINIGRID SETUP Here, we describe in more details the experimental setup we used in our MiniGrid experiments.

There are several different MiniGrid scenarios that we consider in this paper. MultiRoom corresponds to a set of navigation tasks, where the goal is to go from a starting state to a goal state. The notation MultiRoom-N2S4 means that there are 2 rooms in total, and that each room has a maximal side of 4. In order to go from one room to another, the agent must perform a specific action to open a door. Episodes are terminated with zero reward after a maximum of 20 × N steps with N the number of rooms. In KeyCorridor, the agent also has to pick up a key, since the goal state is behind a door that only lets it in with the key. The notation KeyCorridor-S3R4 means that there are 4 side corridors, leading to rooms that have a maximal side of 3. The maximum number of steps is 270. In ObstructedMaze, keys are hidden in boxes, and doors are obstructed by balls the agent has to get out of its way. The notation ObstructedMaze-1Dl means that there are two connected rooms of maximal side 6 and 1 door (versus a 3x3 matrix and 2 doors if the leading characters are 2D), adding h as a suffix places keys in boxes, and adding b as a suffix adds balls in front of doors. Using Q as a suffix is equivalent to using lhb (that is, both hiding keys and placing balls to be moved). The maximum number of steps is 576. ObstructedMazeFull is the hardest configuration for this scenario, since it has the maximal number of keys, balls to move, and doors possible.

In each scenario, the agent has access to a partial view of the environment, a 7x7 square that includes itself and points in the direction of its previous movement.

C.2 HYPERPARAMETERS

In all experiments, we train six different instances of our algorithm with different random seeds. In Table 3, we report the list of hyperparameters.

In Fig. 11 is depicted the architecture of our method.

Figure 11: Artificial neural architecture of the critic, the actor and the adversary.

E PROOF OF SECTION 4.1 RESULTS

In this section, we provide a short proof for the result of the optimization problem in Section 4.1. We recall the result here:

with the objective function:

Proof. We first consider a simpler optimization problem: arg max π π, Q π k + αH(π), whose solution is known (Vieillard et al., 2020a, Appendix A). The expression for the maximizer is the α-scaled softmax:

.

We now turn towards the optimization problem of interest, which we can rewrite as:

By the simple change of variable Qπ k = Q π k + c (log π k -log π adv ), we can reuse the previous solution (replacing Q π k by Qπ k ). With the simplification:

we obtain the result and conclude the proof.


Aurore Rimlinger

Nathalie Raharimalala

Véronique Letort

Jean-Jacques Rakotomalala

Dominique Crouzillat

Romain Guyot

Perla Hamon

Sylvie Sabatier
email: sylvie-annabel.sabatier@cirad.fr

Phenotypic diversity assessment wihin a major ex situ collection of coffees in Madagascar

Keywords: phenology, LMA, LDMC, functional traits, Coffea, Rubiaceae

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Tropical rainforests of Africa and Madagascar harbor huge biodiversity characterized by great species richness and endemicity [START_REF] Myers | Biodiversity hotspots for conservation priorities[END_REF][START_REF] Yoder | Has Vicariance or Dispersal Been the Predominant Biogeographic Force in Madagascar? Only Time Will Tell[END_REF]Novak 2006, Vences et al. 2009).

In such context, for the genera that experienced radiative speciation, phenotypic divergence can be important while the associated genetic differentiation could remain low resulting in low congruency between genetic and phenotypic diversity, and in the recognition of morphological units as species [START_REF] Shaffer | Delimiting Species in Recent Radiations[END_REF]. For instance, 58 and 47 Coffea species (excluding ex-Psilanthus genus and Baracoffea grouping) respectively from Madagascar and Africa were described [START_REF] Davis | An annotated taxonomic conspectus of the genus Coffea (Rubiaceae)[END_REF][START_REF] Couturon | Caféiers sauvages -Un trésor en péril au coeur des forêts tropicales ! Wild coffee-trees -A threatened treasure in the heart of tropical forests ! Edition Association Biodiversité -Ecovalorisation et Caféiers[END_REF], although three and seven species from Madagascar and Africa respectively are not yet formally recognized.

For Coffee, clear relationships between species was not permitted by analysis conducted with two ITS plus four plastid sequences [START_REF] Maurin | Towards a phylogeny for Coffea (Rubiaceae) : identifying wellsupported lineages based on nuclear and plastid DNA sequences[END_REF], nor with a limited number of nuclear microsatellite markers [START_REF] Andrianasolo | High genetic diversity of in situ and ex situ populations of Madagascan coffee species: further implications for the management of coffee genetic resources[END_REF]. A completely resolved molecular phylogenetic tree was obtained using 28,800 concatenated SNPs obtained from Genotyping-By-Sequencing (GBS) methodology [START_REF] Hamon | Genotyping-by-sequencing provides the first well-resolved phylogeny for coffee (Coffea) and insights into the evolution of caffeine content in its species[END_REF]. The necessity to use GBS for assessment of between-species genetic divergence could be explained by two non-exclusive mechanisms: 1) the absence of strong genetic barrier and therefore the maintenance of gene flow between species even at a low rate [START_REF] Hey | Recent advances in assassing gene flow between diverging populations and species[END_REF][START_REF] Nosil | Speciation with gene flow could be common[END_REF][START_REF] Niemiller | Recent divergence-with-gene-flow in Tennessee cave salamanders (Plethodontidae: Gyrinophilus) inferred from gene genealogies[END_REF] and 2) recent speciation coupled with rapid morphological divergence [START_REF] Janssen | Neoendemism Madagascan scaly tree ferns results from recent, coincident diversification[END_REF].

Regarding Madagascar speciation, the general agreement states that "the importance of dispersal to the assembly of the Malagasy flora cannot be denied" [START_REF] Yoder | Has Vicariance or Dispersal Been the Predominant Biogeographic Force in Madagascar? Only Time Will Tell[END_REF].

The high level of speciation seems to be associated with the existence of different small niches side-by-side. Therefore, the resulting species should be highly differentiated at the phenotypic level but not, or less, at the genetic one [START_REF] Yoder | Has Vicariance or Dispersal Been the Predominant Biogeographic Force in Madagascar? Only Time Will Tell[END_REF].

In addition to environmental selective pressures, traits (i.e. individual heritable features, as defined by [START_REF] Garnier | A trait-based approach to comparative functional plant ecology: concepts, methods and application for agroecology. A review[END_REF] are also shaped by developmental (i.e. structural limitation on phenotypic variability, as defined by [START_REF] Smith | Developmental constraints and evolution[END_REF], functional and genetic constraints.

Common evolutionary origin or, at the opposite, evolutionary convergence could be the result of similar trait values for two species, or of correlations between traits. Hence, functionally similar species may belong to the same clade or may be phylogenetically distant. Regarding leaf functional traits such LMA, leaf mass per area, and LDMC (ratio dry leaf mass/fresh leaf mass); high LMA values characterize plants with low growth producing large leaves but whose longevity is low [START_REF] Westoby | Plant ecological strategies : some leading dimension of variation between species[END_REF]; high LDMC values characterize plants whose foliar organs accumulate nutrients and constitute important storage pools with low tissue turnover. Therefore, the study of their relationship permits to test whether there is compensatory effect between these two traits and whether this correlation still exists in case of evolutionary trade off.

The most recent Coffea molecular phylogeny highlighted independent and parallel diversification in the two landmasses Africa and Madagascar [START_REF] Hamon | Genotyping-by-sequencing provides the first well-resolved phylogeny for coffee (Coffea) and insights into the evolution of caffeine content in its species[END_REF] resulting in total endemism in these main regions. More widely, none of the species occurring in West and Central Africa is found in East Africa, in the Western Indian Ocean Islands, nor in Asia (broad sense) and conversely. Another important characteristic concerns the great vulnerability of Coffea species, as their distribution is generally restricted to one or a few forests [START_REF] Davis | An annotated taxonomic conspectus of the genus Coffea (Rubiaceae)[END_REF]; http://publish.plantnet-project.org/project/wildcofdb). In such context, forest cutovers and burns, human activities, and natural hazard (cyclones, fires) could dramatically decrease Coffea richness both at the population and species levels. As a consequence, more than 80% of Coffea species are present on the red list of endangered species of the IUCN (from nearly threatened to critically endangered, [START_REF] Davis | An annotated taxonomic conspectus of the genus Coffea (Rubiaceae)[END_REF]). Yet, wild Madagascan species constitute highly valuable genetic resources [START_REF] Andrianasolo | High genetic diversity of in situ and ex situ populations of Madagascan coffee species: further implications for the management of coffee genetic resources[END_REF]. A large part of the Malagasy species are grouped together in an ex situ collection. Such collection is especially important for coffees since some of them have already disappeared from their natural habitat [START_REF] Krishnan | The study of genetic diversity patterns of Coffea commersoniana,an endangered coffee species from Madagascar: a model for conservation of other littoral forest species[END_REF]. As part of the study, we were able to carry out in situ and ex situ comparisons of genetic diversity for four species and two populations per species. This study showed a strong genetic diversity in the ex situ collection [START_REF] Andrianasolo | High genetic diversity of in situ and ex situ populations of Madagascan coffee species: further implications for the management of coffee genetic resources[END_REF]. The plants in collection are very valuable for studies on interspecific variability.

Madagascan Coffea show different growth habits, growing as ligneous shrubs, treelets or trees. They are mainly plants, with only monopodial growth, axillary inflorescences and evergreen leaves (66 species at all; [START_REF] Davis | An annotated taxonomic conspectus of the genus Coffea (Rubiaceae)[END_REF][START_REF] Couturon | Caféiers sauvages -Un trésor en péril au coeur des forêts tropicales ! Wild coffee-trees -A threatened treasure in the heart of tropical forests ! Edition Association Biodiversité -Ecovalorisation et Caféiers[END_REF] http://publish.plantnet-project.org/project/wildcofdb). But some species have a sympodial growth [START_REF] Davis | A taxonomic revision of the baracoffea alliance: nine remarkable Coffea species from western Madagascar[END_REF]. Most Coffea species conform to the Roux's architectural model with rhythmic growth and continuous branching, and lateral flowering on the plagiotropic branches [START_REF] Hallé | Tropical trees and forests: an architectural analysis[END_REF]. In Coffea species, stem growth occurs phytomer by phytomer, with a phyllochron that varies depending on seasonality [START_REF] Varossieau | On the development of the stem and the formation of leaves in Coffea species[END_REF].

Another striking example of adaptation lies in their phenological traits. For all species, inflorescence and flower development require the dry season to be followed by a an adequate rainfall [START_REF] Portères | Action de l'eau, après une période sèche, sur le déclenchement de la floraison chez Coffea arabica[END_REF].The number of days from this triggering rain to the opening of the flower bud (anthesis) is genetically determined and depends on the species considered (Le Pierrès, 1995;[START_REF] Noirot | Reproductive isolation, gene flow and speciation in the former Coffea subgenus: a review[END_REF]. A better knowledge of the reproductive strategies is an important first step for the development of appropriate conservation strategies. The length of the maturation phase which correspond to the time between the seed emission and the seed germination is very variable between species according to the plant habitat.

Within the past few years, as more phylogenetic data got available, a number of studies have connected phylogenetic analyses with phenotypic, physiological, or phenological traits (Reginato and Michelangi, 2016;[START_REF] Bacon | Phylogenetics of Iriarteeae (Arecaceae), cross-Andean disjunctions and convergence of clustered infructescence morphology in Wettinia[END_REF]. Several descriptive statistics have been introduced to gauge phylogenetic signal as a quantity that could thus help compare different traits across phylogenies [START_REF] Pagel | Inferring the historical patterns of biological evolution[END_REF][START_REF] Blomberg | Testing for phylogenetic signal in comparative data: behavioral traits are more labile[END_REF]. Not all traits behave similarly for closely-related species: while some traits stay stable throughout the phylogeny [START_REF] Davies | Phylogenetic conservatism in plant phenology[END_REF], others are highly labile [START_REF] Cavender-Bares | The merging of community ecology and phylogenetic biology[END_REF]. Owing to shared ancestry, non-independence caused by evolutionary history is expected from species traits. Phylogenetic signal measures this tendency for related species [START_REF] Blomberg | Tempo and mode in evolution: phylogenetic inertia, adaptation and comparative methods[END_REF]: the stronger the signal, the larger the influence of the phylogenetic structure on the species traits.

In this study, the availability of Coffea molecular phylogeny and phenotypic data for a large set of Madagascan wild coffees allows us to address the following questions: How is the phenotypic variation distributed among Madagascan wild coffee species and which are their phenotypic relationships? Are there different reproductive strategies? Are there phenotypic traits associated with species evolution, and thus expressing phylogenetic signal?

MATERIALS AND METHODS

Plant Material

Plant material comes from the ex situ Coffea collection at the Kianjavato Coffee Research Station (KCRS) in Madagascar, (coordinates S 21°22'28", E 47°52'02"). The collection is situated 550 km away from Antananarivo, at altitudes ranging from 50 to 400 m above sea level. The collection is mainly constituted by Madagascan wild Coffea species [START_REF] Chevalier | Les caféiers du globe. Caféiers sauvages et cultivés[END_REF] excluding the Baracoffea group from the Western coast described by [START_REF] Davis | A taxonomic revision of the baracoffea alliance: nine remarkable Coffea species from western Madagascar[END_REF]. They are representatives of the five botanical series from the Great Island, which were classified by [START_REF] Charrier | La structure génétique des caféiers spontanés de la région malgache (Mascarocoffea). Leurs relations avec les caféiers d'origine africaine (Eucoffea)[END_REF] according to floral and leaf traits. These series are named Garcinioides, Millotii complex, Multiflorae, Subterminales and Verae.

The coffee trees sampled are adult trees mainly collected between 1960s and 1980s, growing under natural forest cover. Details on plant material (such as species name, botanical series, geographic origin, and coordinates) are provided in Table 1.

Phenotypic records

Records were done during years 2010-2011, 2013-2014 on a total of 364 plants from 63 populations corresponding to 36 species. Descriptive (such as, leaf shape and color, domatia position, aperture shape and pubescence) and quantitative traits on the numbers, leaves, fruits, seeds size and phenology (number of days between the triggering rain and blossoming, between flowering and ripening, number of flowers per inflorescence) were recorded.

Excepting for leaves, fruits and seeds measurements, the trait records were done on a maximum of ten trees (depending on the availability) per population.

Mature leaves measurements were performed on five leaves (picked on the fifth branching from the top) and five trees per population.

Measurements for fruits (including 100-seed weight and fruit disc diameter) were done on 20 and 40 seeds and fruits respectively per population. Four additional variables were calculated: i) the shape index of leaves as the ratio of length to width; ii) the surface index as length x width; volume indices of iii) fruits and iv) seeds as length x width x thickness. The 28 variables and range of variation are listed in Table S1.

The number of days for maximum seed germination was obtained after sowing between 68 and 120 seeds per harvest in nurseries at Kianjavato. This trait was recorded for 47 populations corresponding to 28 species.

Two functional attributes, leaf mass per area (LMA, recorded for 39 populations either 33 species) and leaf dry matter content (LDMC, i.e. the ratio of leaf dry mass to leaf fresh mass) which was recorded for 30 populations either 29 species, were added, as well as two physiological attributes: stomata density and stomata length, as measured in [START_REF] Razafinarivo | Geographical gradients in the genome size variation of coffee trees (Coffea) native to Africa and Indian Ocean islands[END_REF] were recorded for 56 populations either 35 species. The Leaver module was used to extract leaf area with the plugin Toaster (Tree and plant organs and structures analyzer, [START_REF] Borianne | Automated valuation of leaves area for large-scale analysis needing data coupling or petioles deletion[END_REF] run in the ImageJ software. The leaf dry mass was obtained after being dried four days in the oven (60°C). For all species, in order to compare even-aged organs, the measurements of size leaf and internode have been made on the more recent metamer at the branch extremity and in full light. These metamer were green and without secondary growth.

Environmental parameters

Climatic data were extracted from GPS coordinates of each species (Table 1) and from worldclim information (http://www.worldclim.org). The "habitat class", (Table 1) is obtained from a distribution of the number of dry months of each species original habitat. MadaClim (https://madaclim.cirad.fr/). An Index of Aridity was also calculated as annual precipitation minus annual potential evapotranspiration (Table 2).

Statistical analyses

Relationships among Madagascan wild coffees

Given that the recorded traits are quantitative and qualitative, quantitative traits (at all 14) were transformed into either similar size classes or well distinct range classes depending on the distribution of the trait. For the qualitative trait, each modality became a new trait.

Therefore, from the 28 initial variables, a total of 107 new variables were obtained and encoded 1-0 for presence-absence. With the aim to assess the relationships between individuals within populations, populations within species and between species, a Neighbour Joining (NJ) tree based on matrix of Dice's dissimilarities indices and 200 bootstraps was constructed using DARwin v.5 [START_REF] Perrier | DARwin software[END_REF].

For quantitative traits (reproductive, vegetative, phenological, physiological and functional leaf traits), we used standardized data to visualize for each trait and each species the deviation to the mean of the values obtained for all the species. The results for each species are ordered following the rooted molecular phylogenetic tree extracted from [START_REF] Hamon | Genotyping-by-sequencing provides the first well-resolved phylogeny for coffee (Coffea) and insights into the evolution of caffeine content in its species[END_REF].

Relationships between phenotypic and bioclimatic traits

Three habitat classes of species were defined according to the number of dry months from the original population location: 0-1 dry month for S1, 2-6 dry months for S2 and >6 months for S3. Comparisons were performed on seven traits recorded for all populations investigated (63 populations corresponding to 36 species). For 15 traits, data were obtained for 54 to 61 populations. Six traits were recorded for 30 to 39 populations corresponding to at least 29 species. Mean comparisons between subsets were performed with ANOVA using R (R Core Team, 2015).

Analysis of interspecific and intra specific (population) diversity

We summarized the interspecific and intraspecific (population) trait variation in the table S2 (Supplementary material), showing the mean trait values for a set of species. Differences between populations were analyzed by one-way ANOVA and the Tukey test. We also verified the contribution of the population level to the total trait variation by decomposing the variance of each trait using a linear mixed model that took into account the nested structure of the sampling design (package lme4, [START_REF] Bates | Fitting Linear Mixed -Effects Models Using Lme4[END_REF]..

The phylogenetic signal

The phylogenetic signal allows a better understanding of the evolutionary traits within a group. The phylogeneticPagel's λ [START_REF] Pagel | Inferring the historical patterns of biological evolution[END_REF]) and Blomberg's K indices [START_REF] Blomberg | Testing for phylogenetic signal in comparative data: behavioral traits are more labile[END_REF] were selected after assessment of their respective performance and shortcomings.

Pagel's λ estimated by a maximum-likelihood approach provides the most probable description of the observed trait distribution given Brownian model for trait evolution (BM).

A value of λ equal to 1 indicates that the trait evolves exactly as suggested from the original topology of phylogeny while a value of λ equal to 0 means an absence of phylogenetic signal.

Blomberg's statistic (K) quantifies phylogenetic signal. It is a descriptive statistical parameter to describe the degree of the difference between the F-statistic of simulated data and observed F-statistic distribution by the ratio of the observed mean squared error derived from a phylogenetically corrected mean and the expected mean square error obtained from the analysis by considering tree topology and branch length information. A K value inferior to one suggests that the trait evolution was independent of phylogeny (i.e. the phylogenetic signal is low). A K value equal to 1 suggests that the trait has evolved at a constant rate during species evolution, while K > 1 indicates a higher phylogenetic signal for the considered trait (i.e. the trait is more similar for related species than expected by the evolutionary model). The significance of K is obtained from 999 permutations. Phylogenetic signal was only considered significant for a trait when both Pagel's λ and Blomberg's K gave consistent results with the following thresholds for the p-values: p λ < 0.05 and p K < 0.1. Phylogenetic signals were estimated with the function phylosig in package 'phytools' [START_REF] Revell | phytools: An R package for phylogenetic comparative biology (and other things)[END_REF] from mean values data per species for 29 to 36 species depending on the trait.

Statistical tests (normality, independence and homoscedasticity of residuals) for validation of the linear model were performed using package lmtest [START_REF] Zeileis | Diagnostic Checking in Regression Relationships[END_REF].

Calculations were performed with the function pgls of the R package 'caper' [START_REF] Orme | caper: comparative analysis of phylogenetics and evolution in R[END_REF]. Figures drawings are performed within R 3.2.5.

RESULTS

Structuring of wild coffees based on traits

Individual phenotypic relationships showed that globally, intraspecific variation was lower than interspecific variation, which can be seen in the table S2 (Supplementary material) with ANOVA results on interspecific variation compared to intraspecific (population) variation.

The deviation to the mean was lower for intraspecific variation, and populations were generally pooled into fewer groups than did species. The contribution of intraspecific diversity to the variance of species traits (table S3, Supplementary material) varied between traits, being fairly high (leaf length , number of flowers per inflorescence), moderate (shape index, petiole length) or low (length of the maturation phase).

The estimation of dissimilarity indices within populations lower than between species (Figure 1). As an example, C. resinosa individuals were grouped close to each another, even if they are exhibiting an important phenotypic variability.

Only two Charrier's series (the Millotii complex and the Garcinioides) appeared very homogenous but no overall structuring according to the botanical series classification is obvious. Using standardized data for each trait permitted to discern some trends following phylogenetic species relationships (Figure 2). The ratio between internode mass and leaf mass was higher for three species: C. vohemarensis and C. vatovavyensis (Subterminale serie) and C. bertrandii (Multiflorae serie) that are highly branched and bear small leaves.

Another grouping of sister species (Figure 2, in red) was characterized by long petiole and leaves, thick and long internodes, large leaf area, large fruits and seeds (Figure 3A). Similarly, a grouping of northern species (Figure 2, in yellow) was characterized by a long maturation phase and included two species easy to identify from their fruit shape (C. tsirananae, Figure 3B) or their leaf shape (C. heimii, Figure 3C). The latter species also exhibited the highest value for LMA.

Reproductive traits and strategies

Madagascan wild coffee trees exhibited a wide range of number of days between the triggering rain and the flowering (from 4 to 13 days). Two series, Garcinioides and Millotii complex, were characterized by a long duration from rainfall to flowering (10-13 days) while the Verae exhibited a short to medium duration (4-7 days). Regarding the three bioclimatic subsets of species S1, S2 and S3, the range of the number of days between the trigger rain and blossoming was large for the three subsets going from four to 10 ( S2) or 13 (S1) days and, from seven to 12 for S3 (Figure 4A). The Multiflorae appeared as the most diverse series with from short (4 days) to long (10 days) durations (Figure 4B). Maturation phase lengths were also diverse and ranged from 59 to more than 350 days. In very humid habitats (0 to 1 dry month) as well as in intermediate habitats (2 to 6 dry months), species ripen in 2 to 6 months. In very dry habitats (>6 dry months), species ripened in contrasted time, either 2-3 months (for the majority), either around one year (Figure 5A).

Dates for harvest went around the year from January to December (Figure 5B). Early species (all Verae, and majority of Subterminales and Multiflorae) were harvested from January to February. Medium species (mainly Millotii) were harvested from March to May and very late species (all Garcinioides) from mid-November to December. The sequence of harvest was nearly invariable whatever the year. Considering seed germination; generally there was either no dormancy or germination after a couple of months.

In humid (S1) and intermediate (S2) habitats, maturation phase and seed germination took place during the hot rainy season with short time between the two physiological steps.

However, in dry habitats (S3), two behaviors were found. Either species (such as C. boiviniana) had a very short maturation phase followed by seed germination few weeks after, either species such as C. tsirananae had a long maturation phase (around one year) followed by immediate seed germination (occurring during the rainy season at year n+1 after the flowering). An overview of the timing of the different reproductive phases considered as reproductive strategies is given in Figure 6.

Environmental effect

Given the distribution of the number of dry months in their natural habitats, three habitat class of species were defined from the bioclimatic parameters of their natural habitat. The main features of these habitat class of species are given in Table 2.

Higher the number of dry months, higher the range of the average temperature of the coldest month and higher the annual potential evapotranspiration as a result of warm temperature.

Regarding biological trait, mean comparisons between habitat class for each trait showed significant differences between the three habitat class as described in Table 3 for vegetative traits (leaf length, leaf width and leaf area, two leaves mass and internode diameter perpendicular to leaves, ratio of internode mass/two leaves mass, ratio of internode length/diameter, Ratio Length of internode/internode diameter parallel to leaves), and reproductive traits (number of flowers per inflorescence,maturation phase length, and seed thickness).

Phylogenetic signal

The phylogenetic signal allows a better understanding of the evolutionary traits within a group. Phylogenetical signal was assessed using Pagels' λ and Blomberg's K parameters to describe the degree of the difference between the F-statistic of simulated data obtained from 999 permutations and observed F-statistic distributions.

We found that 9 traits (ratio of internode mass/leaf mass, petiole length, parallel internode diameter, ratio of internode length/diameter, leaf length, the length of the maturation phase, seed shape index, LDMC, stomata length and stomata density) evolved in relation with species evolution (Figure 7).

DISCUSSION

Reproductive strategies and limitation of gene flow

Our study showed that phenology parameters (the number of days for blossoming after the trigger rain and the maturation phase length, see Fig 4 and5) did not correlate with natural habitat type; similar range of variation was observed in the three types. For coffees, flowering requires two important steps. The first one is the buds inducing that is set up after a dry period. It is climate dependent as was reported in New-Caledonia by [START_REF] Gomez | Shift in precipitation regime promotes interspecific hybridization of introduced Coffea species[END_REF]. Indeed, flowering patterns for the three cultivated Coffea species (C. canephora, C. liberica and C. arabica) introduced during the beginning of 19 century followed the timing and sequence of precipitation in the study area. The second step corresponds to the development of the flower buds following a trigger rain (of at least 10 mm, [START_REF] Portères | Action de l'eau, après une période sèche, sur le déclenchement de la floraison chez Coffea arabica[END_REF]. It is genetically determined since the average number of days between the trigger rain and the blossoming is fixed for each species and ranged here between 5 and 13 days [START_REF] Noirot | Reproductive isolation, gene flow and speciation in the former Coffea subgenus: a review[END_REF]. These values remained invariable whatever the growing place as was observed in New-Caledonia for the three introduced species [START_REF] Gomez | Shift in precipitation regime promotes interspecific hybridization of introduced Coffea species[END_REF]). In such conditions, climate changes or new climate growing environment should affect only buds inducing and then, as a consequence, the quality of blossoming that depends on the intensity of the trigger rain. Under climatic changes, flowering could be disturbed. Erratic flowerings might open the way for flowering synchronization of usually non-synchronous flowering species and thus favoring unusual gene flow. However, the loss of species integrity involve also cross-species hybridization success and capability to produce fertile progenies. This phenomenon is probably at the origin of the natural cross between two wild species, producing the famous Arabica coffee [START_REF] Carvalho | Taxonomia de Coffea Arabica L. Cracteres morfologicos dos haploides[END_REF][START_REF] Lashermes | Molecular characterisation and origin of the Coffea arabica L. genome[END_REF].

Within tropical forests, a broad spectrum of flowering patterns has been found [START_REF] Sakai | Phenological diversity in tropical forests[END_REF], and observed variations in phenology may arise from phenotypic plasticity or from genetically based local adaptations or a combination thereof (e.g., [START_REF] Zalamea | Continental-scale patterns of Cecropia reproductive phenology : evidence from herbarium specimens[END_REF][START_REF] Panell | Rapid divergence in physiological and life-history traits between northern and southern populations of the British introduced neo-species,Senecio squalidus[END_REF]). Coffee flowering phenology has been characterized as highly dependent on climatic factors such as precipitation [START_REF] Crisosto | Effects of water deficit on flower opening in coffee (Coffea arabica L.)[END_REF], and temperature [START_REF] Lin | Microclimate effects on flowering success in coffee agroforestry systems[END_REF], and it is genetically controlled (Le Pierrès 1995). The time between this rain and the flowering date was well conserved, strictly species-dependent and followed a clear sequence in which C. liberica flowered first, followed by C. canephora and then C. arabica both in Africa and New-Caledonia [START_REF] Gomez | Shift in precipitation regime promotes interspecific hybridization of introduced Coffea species[END_REF].

For Madagascan wild coffees, the sequence of flowering is also well-conserved starting in September by C. sp. 'Sambava-Diego' (described in [START_REF] Couturon | Caféiers sauvages -Un trésor en péril au coeur des forêts tropicales ! Wild coffee-trees -A threatened treasure in the heart of tropical forests ! Edition Association Biodiversité -Ecovalorisation et Caféiers[END_REF] and in http://publish.plantnet-project.org/project/wildcofdb) and C. vatovavyensis. This is followed in October by a part of Subterminales, Millotii complex and Multiflorae species, followed in November by the late-flowering species belonging to Millotii complex and Multiflorae, all the Flowering patterns in Coffea thus appear to have a strong genetic component, causing the flowering times of each species to remain distinct [START_REF] Akaffou | Flowering phenology and yield-related traits in the interspecific cross between Coffea pseudozanguebariae Bridson and C. canephora Pierre[END_REF]. Partly asynchronous responses among species to key environmental factors would thus be expected to act as prezygotic barriers. The lack of a well-marked dry season is considered to influence flower bud formation by creating different levels of induction [START_REF] Crisosto | Effects of water deficit on flower opening in coffee (Coffea arabica L.)[END_REF]) and favoring multiple flowering events during a season (Allan, E., and J. R. Pannell. 2009). However, we do not know whether adaptive evolution will allow populations to reach new phenotypic optima rapidly enough to keep pace with climate change [START_REF] Panell | Rapid divergence in physiological and life-history traits between northern and southern populations of the British introduced neo-species,Senecio squalidus[END_REF].

Reproductive barriers due to no overlap of flowering is very important for sympatric species. This is all the more important given that hand-cross fertilizations in coffees were done in Ivory Coast and in Madagascar [START_REF] Louarn | La fertilité des hybrides interspecifiques et les relations genomiques entre caféiers diploïdes d'origine africaine (Genre Coffea L. sous-genre Coffea[END_REF][START_REF] Charrier | La structure génétique des caféiers spontanés de la région malgache (Mascarocoffea). Leurs relations avec les caféiers d'origine africaine (Eucoffea)[END_REF]). Despite differences in F1 hybrids and F1 fertility rates, the authors concluded that coffees share the same nuclear genome. Therefore, in natural conditions, species integrity in sympatry conditions should be mainly maintained by no flowering overlapping. So, the differences in days between the trigger rain and blossoming are an essential component. However, this physiologic barrier is not absolute. Buds inducing is highly dependent on climate parameters (alternating dry and rainy periods). Reproductive strategies involve mechanisms that favor species integrity (physiologic flow gene barrier), and species survival in climate changes and during new niche colonization.

For species survival, legitimate seed germination must benefit from rains to produce plantlets that can skip the dry season without damage. In Africa, short maturation phases are only observed in the lowlands of East Africa while long maturation phase are recorded in West and Central Africa plus high-altitudes of East Africa. In Madagascar, northern species among Subterminales have either very short maturation phase either very long maturation phase. This indicates two opposite strategies to avoid the dry season. Three behavior have been observed in Seasonally Dry Tropical Forest: (1) flowering and fruiting exclusively in in the rainy season or (2) flowering in the rainy season and fruiting in the dry season or (3) flowering and fruiting in the dry season [START_REF] Luna-Nieves | Reproductive phenology of usefull Seasonnally Dry Tropical Forest trees: Guiding patterns for seed collection and plant propagation in nurseries[END_REF]. The seasonal variation of irradiance influenced seed development times [START_REF] Zimmerman | Flowering and fruiting phenologies of seasonal and aseasonal neotropical forest: the role of annual changes in irradiance[END_REF]2007).

Climate effect on traits related to plant development.

Ours results shown that the climatic factors affect leaf size and mass, the diameter of green internodes which is a proxy of the size of meristem (see Table 3). These features decreased with increasing aridity. The size of leaves is an adaptive trait to drought [START_REF] Westoby | Plant ecological strategies : some leading dimension of variation between species[END_REF][START_REF] Wright | Global Climatic drivers of leaf size[END_REF]. In dry climate, the leaves are small and thick with a high LMA [START_REF] Niinemets | Globe-scale climatic controls of leaf dry mass per area, density, and thickness in trees and shrubs[END_REF].

The leaves of Coffea species of humid region have short internodes and large internode diameter and therefore a weak ratio of internode length to diameter. On the contrary, the species of arid region have long internode and small internode diameter and thus a high ratio of internode length-to-diameter. Our results are in line with Corner's rules on the leaf/stem size: the species with a large leaves have a thick stem and large fruits and weak branching while the species with small leaves have a thin stem and small fruits and high branching [START_REF] Corner | The Durian theory or the origin of the modern tree[END_REF]. In wild Coffea, our results show that the species with large leaves have large green internode diameter, proxy of the size of apical meristem.

A positive relationship was found between the leaf size and the internode diameter. Leaves intercept light and acquire carbon, while stems transport water with nutrients and mechanically support the leaves, thus leaf and stem traits are expected to be highly coordinated biomechanically and physiologically [START_REF] Westoby | Plant ecological strategies : some leading dimension of variation between species[END_REF].

The climatic factors influence the value of ratio between internode mass and leaf mass which are higher for species growing in intermediate and arid regions (see table 3). Thus, these species allocate more to the stem than to the leaves. In arid environment, the species with small leaves are favored because they have a high LMA and thus a better photosynthetic capacity [START_REF] Westoby | Plant ecological strategies : some leading dimension of variation between species[END_REF]. The mechanical cost is the lowest for the species with small leaves [START_REF] Givnish | Comparative studies of leaf form assessing the relative roles of selective pressures and phylogenetic constraints[END_REF]. The small leaves are dense and thick [START_REF] Niinemets | Globe-scale climatic controls of leaf dry mass per area, density, and thickness in trees and shrubs[END_REF]) with a low transpiration [START_REF] Westoby | Plant ecological strategies : some leading dimension of variation between species[END_REF].

Phylogenetic signal

The phylogenetical signal of ratio of internode mass to leaf mass was highly significant (see fig. 7). This ratio illustrates the variability in stem vs leaves biomass allocation between species. The phylogenetic signal of the leaf dry matter content (LDMC) is significant. The LMDC is an indicator of the use of plant resources, a trade-off between a rapid assimilation and growth and an efficient conservation of resources within well-protected tissues [START_REF] Vaieretti | Two measurement methods of leaf dry matter content produce similar results in a broad range of species[END_REF]. The strong conservatism of LDMC is known [START_REF] Purschke | Contrasting changes in taxonomic, phylogenetic and functional diversity during a long-term succession: insights into assembly processes[END_REF][START_REF] Kazakou | Are trait-based species rankings consistent across data set and spatial scales?[END_REF][START_REF] Fort | Hierarchical traits distances explain grassland Fabaceae species' ecological niches distances[END_REF][START_REF] Poorter | Can traits predict individual growth performance? A test in a hyperdiverse tropical forest[END_REF]. The stomatal length and stomata density have a significant phylogenetic signal. In the Coffea genus, generally, the smaller genome species have smaller leaves with larger stomata and grows on the dry environment while the larger genome species from humid habitats have longer leaves with a higher stomata density [START_REF] Andrianasolo | High genetic diversity of in situ and ex situ populations of Madagascan coffee species: further implications for the management of coffee genetic resources[END_REF].

LMA reflects the cost of leaf construction, the light interception and the plant fitness with a low phylogenetic signal [START_REF] Flores | An evolutionary perspective on leaf economics: phylogenetics of leaf mass per area in vascular plants[END_REF]. LMA is linked to leaf lifespan and to photosynthetic capacity per mass unit (Am). The species with low LMA have generally fast growth rate [START_REF] Flores | An evolutionary perspective on leaf economics: phylogenetics of leaf mass per area in vascular plants[END_REF].

The phylogenetical signal of leaf petiole length, leaf length, leaf area and leaf width was weakly significant. The size of the leaves is mainly controlled by global climatic factors [START_REF] Wright | Global Climatic drivers of leaf size[END_REF]. The phylogenetical signals of the ratio internode length-to-diameter are weakly significant too. The stem size is species dependent within Coffea.

The length of the maturation phase shows a high significant phylogenetic signal. It is well known that the phenology is an adaptive trait [START_REF] Chuine | Why does phenology drive species distribution? Philosophical[END_REF]. These results highlight the assumption that the phenological sensitivity was a significant predictor of species adaptation to climate change [START_REF] Cleland | Phenological tracking enables positive species responses to climate change[END_REF].

.

CONCLUSIONS

For Madagascan wild coffees as for African species, the flowering is influenced by both the climatic conditions (dry period followed by a trigger rain) and genetic parameters at the species level. Phenology parameters (number of days for blossoming after the trigger rain and maturation phase length) did not correlate with natural habitat type. However, a high variability of length of the maturation phase (from 59 to 360 days) with a strong phylogenetic signal is noted. In drier environment, two opposite strategies to avoid the dry season are observed either very short as C. boiviniana (59 days) or very long as C. tsirananae (360 days) that raise questions on the adaptive meaning of this trait. Reproductive strategies involve mechanisms that favor species integrity (reduced gene flow and reduced hybrids growth or fertility) and species survival in climate changes. The climatic factors affect leaf size and mass, the diameter of green internodes, which is a proxy of the size of meristem. The ratio between the stem dry mass and leaf dry mass shows a high phylogenetic signal. To our knowledge, there are few studies on such phylogenetic signal. [START_REF] Perrier | DARwin software[END_REF]. Only bootstraps superior to 80% are shown. The botanical series to which each species belongs to is given in yellow for Garcinioides, red for Millotii complex, blue for Multiflorae, pink for Subterminales and green for Verae. of strong phylogenetic effect can be seen for a trait when K is close to 1 (black dashed line) and higher than the lowest threshold value of 0,52 (grey dashed line). Its significance is attested when traits are followed by an asterisk (p-value < 0.05 and consistent with Pagel's λ significant p-value <0.05) or two asterisk when When K value close to 1.The leaf-related and vegetative traits are in red, phenological traits in yellow, fruit and seed traits in blue, functional leaf trait in green and stomata traits in purple.

  Among the 19 available bioclimatic variables, five (Annual Mean Temperature, Max Temperature of Warmest Month, Min Temperature of Coldest Month and Annual Precipitation) were retained for this study. Additional climate data such as Annual Potential evapotranspiration, Climatic Water Deficit and, Number of Dry Months were extracted from

  Garcinioides and C. boiviniana, C. alleizettii, C. augagneuri, C. ratsimamangae and C. sakarahae (Subterminales) and finishing in December with the very late-flowering C. tsirananae (Subterminales).

ACKNOWLEDGEMENT

  This work is a part of a collaborative project with the National Center of Applied Research and Rural Development (FOhibem-pirenena momba ny FIkarohana ampiharina amin'ny Fampandrosoana ny eny

Figure 2 :

 2 Figure 2: Phenotypic tendencies. Standardized trait values in columns for each species following their phylogenetic relationships based on Hamon et al. (2017), with large black squares indicating the highest values. The serie Millotii complex is colored in red and the species with higher length maturation phase are in yellow color. The leaf-related and vegetative traits are in red, phenological traits and inflorescence trait are in yellow, fruit and seed traits are in blue, functional leaf trait are in green and stomata traits are in purple.

Figure 3 :

 3 Figure 3: Internodes, fruits and seeds of C. richardii (A); Fruit of C. tsirananae (B); leaf of C. heimii (C).

Figure 4 :

 4 Figure 4: A:Variation of the time between the triggering rain and blossoming according to the number of dry months, 0-1 for S1 or "Habitat class 1", 2-6 for S2 or "Habitat class 2" and >6 for S3 or "habitat class 3" for each population and B: Dates of blossoming according to the botanical series of each population.

Figure 5 :

 5 Figure 5: A: Variation of the length of the maturation phase (in days) according to the length of the dry season (in number of dry months); B: Dates for ripen fruits according to the botanical series of the populations. GAR for Garcinioides, MIL for Millotii complex, MUL for Multiflorae, SUB for Subterminales and VER for Veare.

Figure 6 :

 6 Figure 6: Reproductive strategies of Madagascan wild coffee trees. Diagram showing the flowering (blue colors) and fructification period (red colors) and germination period (green color) according to the length of the rainy/dry seasons along the year. The length of the rainy season is indicated by clouds. The number of dry months of dry season is indicated by sunshine.

Figure 7 :

 7 Figure 7: Phylogenetic signal in coffee trees traits using Blomberg's K parameter. Indication

Table 1 .

 1 TABLES Coffee species examined, with population code, species name, botanical series (from

	Charrier 1978), origin, province, GPS coordinates, habitat class. Habitat class: 1: < 2 dry
	months; 2 : from 2 to 6 dry months; 3 : > 6 dry months.
	ID	species name botanical	Origin/Locality			Province latitude	longitude	habitat
	populat			series						coordina	coordinat	class
	ion									tes	es
	A964	C.dubardii		Garcinioid	Anivorano Nord		Antsiran	S12°44'	E49°09'	3
		Jum.		es					ana
									(North)
	A969	C.dubardii		Garcinioid	North	of	Vohemar	Antsiran	S13°20'	E49°57'	3
		Jum.		es	(Diégo-Suarez)			ana
									(North)
	A516	C.heimii J.-	Garcinioid	Diégo-Suarez (Sahafary)	Antsiran	S12°35'	E49°26'3	3
		F.Leroy		es					ana		0''
									(North)
	A40	C. mogenetii	Garcinioid	Montagne d'Ambre		Antsiran	S49°12'	E12°26'	3
		Dubard		es					ana
									(North)
	A252	C. tetragona	Garcinioid	Behangony	(Est	de	Mahajan	S14°13'3	E48°09'	3
		Jum.	&	es	Maromandia)			ga	0''
		H.Perrier							(Northwe
									st)
	A601	C. abbayesii	Millotii	Fort-Dauphin	(Isaka-	Toliara	S24°45'1	E46°51'4	2
		J.-F.Leroy		complex	Ivondro)				(Southea	5''	5''
									st)
	A572	C.		Millotii	reserve Ambodiriana		Toamasi	S18°27'0	E48°56'3	1
		ambodiriane	complex					na (East)	8"	6"
		nsis Portères
	A206	C.		Millotii	Nosy		Varika	Fianarant	S20°29'	E48°10'3	1
		dolichophyll	complex	Vohimanoro),			soa		0''
		a J.-F.Leroy		Ambodilafa			(Southea
									st)
	A208	C.		Millotii	Farafangana			Fianarant	S22°53'	E47°48'	1
		farafanganen	complex	(Amboangibe)			soa
		sis	J.-						(Southea
		F.Leroy							st)
	A212	C. millotii J.-	Millotii	Vatovavy				Fianarant	S21°24'3	E47°56'3	1
		F.Leroy		complex					soa	''	2''
									(Southea
									st)
	A219	C. millotii J.-	Millotii	Ambatovaky			Fianarant	S21°22'4	E47°53'0	1
		F.Leroy		complex					soa	8"	6"
									(Southea
									st)

Table 2 :

 2 Physical parameters of habitats corresponding to habitat class of species 1 to 3 as defined by the number of dry months.

	Habitat	Number	Annual	Temperature	Temperature	Annual potential	Aridity
	class	of	dry	precipitation	of	the	of	the	evapotranspiration	index in
		months	in mm	coldest		warmest		in mm	mm
					month in °C	month in °C
	1	0 -1		2051 to 3360 11.6 to 19.9 26.3 to 30.9 945 to 1289	1081 to 2142
	2	2 -6		1260 to 2265 10.6 to 20.7 23.1 to 30.9 814 to 1370	175 to 1111
	3	>6		552 to 1829 10.2 to 22.8 28 to 33.1	950 to 1627	-691 to 379

Table 3 .

 3 Mean comparison between the three bioclimatic subsets of species defined on the number of dry months in the natural habitat of studied populations/species. Mean for each trait according to the number of dry month in the natural habitat of Coffee populations. Phenotypic relationships among Madagascan Coffea species. NJ tree based on Dice's dissimilarity indices calculated from 107 variables encoded presence-absence for 364 individuals, 200 bootstraps using DARwin v5

	Difference in means between subsets was tested with ANOVA. P-values (***<0.001,
	**<0.01, *<0.05) inferior to 0.05 are considered as evidence of trait divergence. LDMC: leaf
	dry mass content; LMA: leaf mass per area.
	Habitat class	1	2	3	p	value
					ANOVA
	Leaf length (mm)***	113.05185 76.3	68.15909 0.000185
	Leaf width (mm)***	48.34444 35.02857	28.92727 2.16E-05
	Leaf area (mm 2 )***	6150.185 3156.571	2299.262 0.00012
	Two leaves mass (g)**	1.465	0.453	0.5341176 0.00925
	Internode diameter perpendicular to leaves,	3.720833 2.293	2.195625 0.00454
	mm)**
	Maturation phase length (days)**	104.6296 105.0714	178.3182 0.00308
	Ratio internode mass /2 leaves mass (g)*	0.1275	0.259	0.2175	0.0487
	Ratio Length of internode/internode diameter parallel to leaves*	12.78	24.117	21.7975	0.039
	Number of flowers per inflorescence*	4.403704 2.8	3.177273 0.0123
	Seed thickness (mm)*	3.885926 4.053077	4.673	0.0422
	Leaf shape	2.362	2.17	2.588	0.412
	Internode diameter (parallel to leaves, IDP, mm)	2.058333 1.587	1.636875 0.123
	Petiole length	8.12	6.45	6.34	0.151
	length internodes (LI, mm)	23.16667 32.1	33.35	0.056
	Internode mass (IM,g)	0.2143	0.0878	0.101	0.121
	Fruits length (mm)	15.86148 14.69077	15.5035	0.795
	Number of days from trigger rain to Flowering	7.648148 7.321429	8.475	0.13
	Fruits thickness (mm)	12.69296 11.46154	11.442	0.445
	Fruit shape index	1.225926 1.169231	1.2535	0.707
	Fruit volume index (mm 3 )	4836.13	3041.622	2910.932 0.212
	Pedicel length (mm)	3.498889 3.811538	4.293	0.108
	Disk diameter (mm)	3.391111 3.181667	2.784444 0.3
	Seed length (mm)	9.183704 8.683846	10.3285	0.237
	Seed width (mm)	5.692593 5.041538	6.57	0.228
	Seed volume (mm 3 )	295.5733 219.8423	352.434	0.549
	100 seed weight (g)	9.677778 8.8175	14.291333 0.138
	LMA mean (g/m 2 )	175.7083 137.78	202.3235 0.235
	LDMC (mg g-1)	357.1	344.4143	382.1583 0.388
	Mean stomata density	203.5238 152.2308	171.3182 0.0797
	Stomata length (µ)	8.12	8.378923	8.225682 0.845

Ambanivohitra: FOFIFA), in Madagascar and two French research institutes (Cirad and IRD, Montpellier France). We thank the FOFIFA staff at the Kianjavato Coffee Research Station (KCRS), Madagascar. We thank Yves Caraglio (UMR AMAP) for his critical and valuable comments on the manuscript.

FUNDING INFORMATION

This work was supported by the Agropolis Foundation (grant n° 0902-009) and by funds from the Botany and Computational Plant Architecture, joint research unit (UMR AMAP) and by funds from the Diversity, Adaption and Plant Development, joint research unit (UMR DIADE).