Weijia Wang
email: weijia.wang@lri.fr

Michèle Sebag
email: michele.sebag@lri.fr

Steven C H Hoi

Wray Buntine

Asian Conference on Machine Learning Multi-objective Monte-Carlo Tree Search

Keywords: Monte-Carlo tree search, multi-objective optimization, sequential decision, hypervolume indicator

Concerned with multi-objective reinforcement learning (MORL), this paper presents MO-MCTS, an extension of Monte-Carlo Tree Search to multi-objective sequential decision making. The known multi-objective indicator referred to as hyper-volume indicator is used to define an action selection criterion, replacing the UCB criterion in order to deal with multi-dimensional rewards. MO-MCTS is firstly compared with an existing MORL algorithm on the artificial Deep Sea Treasure problem. Then a scalability study of MO-MCTS is made on the NP-hard problem of grid scheduling, showing that the performance of MO-MCTS matches the non RL-based state of the art albeit with a higher computational cost.

Introduction

Reinforcement learning (RL) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF][START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF] addresses sequential decision problems in the Markov decision process framework. RL algorithms provide guarantees of finding the optimal policies in the sense of the expected cumulative reward, relying on the thorough exploration of the state and action spaces. The price to pay for these optimality guarantees is the limited scalability of mainstream RL algorithms w.r.t. the size of the state and action spaces.

Recently, Monte-Carlo Tree Search (MCTS), including the famed Upper Confidence Tree algorithm [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF] and its variants, has been intensively investigated to handle sequential decision problems. MCTS, notably illustrated in the domain of Computer-Go [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], has been shown to efficiently handle medium-size state and action search spaces through a careful balance between the exploration of the search space, and the exploitation of the best results found so far. While providing some consistency guarantees [START_REF] Berthier | Consistency modifications for automatically tuned Monte-Carlo Tree Search[END_REF], MCTS has demonstrated its merits and wide applicability in the domain of games [START_REF] Ciancarini | Monte-Carlo Tree Search techniques in the game of kriegspiel[END_REF] or planning [START_REF] Nakhost | Monte-Carlo exploration for deterministic planning[END_REF] among many others.

This paper is motivated by the fact that many real-world applications, including reinforcement learning problems, are most naturally formulated in terms of multi-objective optimization (MOO). In multi-objective reinforcement learning (MORL), the reward associated to a given state is d-dimensional (e.g. cost, risk, robustness) instead of a single scalar value (e.g. quality). To our best knowledge, MORL was first tackled by Gábor et al. (1998); introducing a lexicographic (hence total) order on the policy space, the authors show the convergence of standard RL algorithms under the total order assumption. In practice, multi-objective reinforcement learning is often tackled by applying standard RL algorithms on a scalar aggregation of the objective values (e.g. optimizing their weighted sum; see also [START_REF] Mannor | A geometric approach to multi-criterion reinforcement learning[END_REF][START_REF] Tesauro | Managing power consumption and performance of computing systems using reinforcement learning[END_REF]).

In the general case of antagonistic objectives however (e.g. simultaneously minimize the cost and the risk of a manufacturing process), two policies might be incomparable (e.g. the cheapest process for a fixed robustness; the most robust process for a fixed cost): solutions are partially ordered, and the set of optimal solutions according to this partial order is referred to as Pareto front (more in section 2). The goal of the so-called multiple-policy MORL algorithms [START_REF] Vamplew | Empirical evaluation methods for multiobjective reinforcement learning algorithms[END_REF] is to find several policies on the Pareto front [START_REF] Natarajan | Dynamic preferences in multi-criteria reinforcement learning[END_REF][START_REF] Chatterjee | Markov decision processes with multiple long-run average objectives[END_REF][START_REF] Barrett | Learning all optimal policies with multiple criteria[END_REF].

The goal of this paper is to extend MCTS to multi-objective sequential decision making. The proposed scheme called MO-MCTS basically aims at discovering several Pareto-optimal policies (decision sequences, or solutions) within a single tree. MO-MCTS only requires one to modify the exploration of the tree to account for the lack of total order among the nodes, and the fact that the desired result is a set of Pareto-optimal solutions (as opposed to, a single optimal one). The proposed approach relies on the hyper-volume indicator [START_REF] Zitzler | Multiobjective optimization using evolutionary algorithms -a comparative case study[END_REF] measuring the MOO quality of a set of solutions. Taking inspiration from [START_REF] Auger | Theory of the hypervolume indicator: optimal µ-distributions and the choice of the reference point[END_REF], we use this indicator to define a single optimization objective for the current path being visited in each MCTS tree-walk, conditioned on the other solutions previously discovered. MO-MCTS thus handles a single-objective optimization problem in each tree-walk, while eventually discovering several decision sequences pertaining to the Pareto-front.

The experimental validation of the MO-MCTS approach considers two problems. Firstly, the performance of MO-MCTS is tested on the artificial Deep Sea Treasure problem for the sake of comparative evaluation with MORL algorithms. Secondly, the performance and scalability of MO-MCTS are also experimentally assessed on a real world application, the NP-hard problem of grid scheduling [START_REF] Yu | Workflow Scheduling Algorithms for Grid Computing[END_REF].

The paper is organized as follows. Section 2 briefly introduces related formal background. Section 3 describes the MO-MCTS algorithm. Section 4 presents the experimental validation of MO-MCTS. Section 5 discusses MO-MCTS strengths and limitations w.r.t. the state of the art and the paper concludes with some research perspectives.

Formal background

Assuming the reader's familiarity with the reinforcement learning setting [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF], this section briefly introduces the main notations and definitions used in the rest of the paper.

A Markov decision process (MDP) is described by its state and action space respectively denoted S and A. Only deterministic environments will be considered in the following; the transition function (tr : S ×A → S) gives the next state tr(s, a) reached by executing action a in state s. The (scalar) reward function is defined from the state × action space onto IR (r : S × A → IR).

Multi-objective optimization

In multi-objective optimization (MOO), each point x in the search space X is associated with a d-dimensional reward vector r x in IR d , referred to as vectorial reward in the following.

With no loss of generality, it is assumed that each objective is to be maximized. Given two points x, x ∈ X with r x = (r 1 , . . . , r d ) and r x = (r 1 , . . . , r d ) their associated vectorial rewards, r x is said to dominate, or Pareto-dominate, r x (noted r x r x ) iff r i is greater than or equal to r i for i = 1 . . . d. The dominance is strict (noted r x r x ) if r x r x and r i > r i for some i. As mentioned, Pareto-dominance defines a partial order relation on IR d and thus on X . The Pareto front is defined as follows:

Definition 1 Given A ⊂ IR d a set of vectorial rewards, the set P A of non-dominated points in A is defined as:

P A = {r ∈ A : r ∈ A s.t.

r r}

The Pareto front is made of all non-dominated vectorial rewards. By abuse of language, P A is referred to as the set of Pareto-optima in A.

Notably, there is no natural total order on sets of points. Still, a total order on the sets of points relatively to a reference point has been proposed, based on the hyper-volume indicator [START_REF] Zitzler | Multiobjective optimization using evolutionary algorithms -a comparative case study[END_REF].

Definition 2 Given A ⊂ IR d a set of vectorial rewards, given reference point z ∈ IR d such that it is dominated by every r ∈ A, then the hyper-volume indicator (HV) of A is the measure of the set of points dominated by some point in A and dominating z:

HV (A; z) = µ({x ∈ IR d : ∃r ∈ A s.t. r x z})
where µ is the Lebesgue measure on IR d (Fig. 1( a)).

It is clear that all dominated points in A can be removed without modifying the hypervolume indicator (HV (A; z) = HV (P A ; z)). As shown by [START_REF] Fleischer | The measure of Pareto optima. applications to multi-objective metaheuristics[END_REF], the hypervolume indicator is maximized iff points in P A belong to the Pareto front of the MOO problem. [START_REF] Auger | Theory of the hypervolume indicator: optimal µ-distributions and the choice of the reference point[END_REF] show that, for d = 2, for a number K of points, the hypervolume indicator maps a multi-objective optimization problem defined on IR d , onto a singleobjective optimization problem on IR d×K , in the sense that there exists at least one set of K points in IR d that maximizes the hyper-volume indicator w.r.t z.

Monte-Carlo Tree Search

Let us describe the best known MCTS algorithm, referred to as Upper Confidence Tree (UCT) [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF] and extending the Upper Confidence Bound algorithm [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] to tree-structured spaces. UCT simultaneously explores and builds a search tree, initially restricted to its root node, along N tree-walks a.k.a. simulations. Each tree-walk involves three phases: The bandit phase starts from the root node and iteratively selects an action/a child node until arriving in a leaf node. Action selection is handled as a multi-armed bandit problem. The set A s of admissible actions a in node s defines the child nodes (s, a) of s; the selected action a * maximizes the Upper Confidence Bound: rs,a + c e ln(n s )/n s,a

(1) over a ranging in A s , where n s stands for the number of times node s has been visited, n s,a denotes the number of times a has been selected in node s, and rs,a is the average cumulative reward collected when selecting action a from node s. The first (respectively the second) term in Eq. ( 1) corresponds to the exploitation (resp. exploration) term, and the exploration vs exploitation trade-off is controlled by parameter c e . In a deterministic setting, the selection of the child node (s, a) yields a single next state tr(s, a), which replaces s as current node. The bandit phase stops upon arriving in a leaf node of the tree.

The tree building phase takes place upon arriving in a leaf node s; some action a is (uniformly or heuristically) selected and tr(s, a) is added as child node of s. Accordingly, the number of nodes in the tree is the number of tree-walks. The random phase starts from the new leaf node tr(s, a) and iteratively (uniformly or heuristically) selects an action until arriving in a terminal state u; at this point the reward r u of the whole tree-walk is computed and used to update the cumulative reward estimates in all nodes (s, a) visited during the tree-walk:

rs,a ← 1 n s,a +1 n s,a × rs,a + r u n s,a ← n s,a + 1; n s ← n s + 1
Additional heuristics have been considered, chiefly to prevent over-exploration when the number of admissible arms is large w.r.t the number of simulations (the so-called manyarmed bandit issue [START_REF] Wang | Algorithms for infinitely many-armed bandits[END_REF]). The Progressive Widening (PW) heuristics [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo Tree Search[END_REF] will be used in the following, where the allowed number of child nodes of s is initialized to 1 and increases with its number of visits n s like n s 1/b (with b usually set to 2 or 4). The Rapid Action Value Estimation (RAVE) heuristic is meant to guide the exploration of the search space [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]. In its simplest version, RAV E(a) is set to the average reward taken over all tree-walks involving action a. The RAVE vector can be used to guide the tree-building phase1 , that is, when selecting a first child node upon arriving in a leaf node s, or when the Progressive Widening heuristics is triggered and a new child node is added to the current node s. In both cases, the selected action is the one maximizing RAV E(a). The RAVE heuristic aims at exploring earlier the most promising regions of the search space; for the sake of convergence, it is clearly desirable to consider the best options as early as possible, despite the asymptotic consistency guarantees of MCTS [START_REF] Berthier | Consistency modifications for automatically tuned Monte-Carlo Tree Search[END_REF].

Overview of MO-MCTS

This section presents the MO-MCTS algorithm. The main difference between MCTS and MO-MCTS regards the node selection step. The challenge is to extend the single-objective node selection criterion (Eq. ( 1)) to the multi-objective setting.

From multi-to single-objective optimization

As mentioned, the most straightforward way of dealing with multi-objective optimization is to get back to single-objective optimization, through aggregating the objectives into a single one; the price to pay is that this approach yields a single solution on the Pareto front. The hyper-volume indicator however makes it feasible to model multi-objective optimization as a set of (interdependent) single-objective optimization problems, as follows. Conditioned on a set P ⊂ IR d , let us define the value of any r in IR d as the hyper-volume indicator of P ∪ {r}.

V (r) = HV (P ∪ {r}; z) By construction, any r maximizing V belongs to the Pareto front and offers some diversity w.r.t. P .

A scalar multi-objective value function

Let P denote the archive of non-dominated vectorial rewards measured for every terminal state u (section 2.2). It then comes naturally to define the value of any MCTS tree node as follows.

Let us associate to each node (s, a) in the tree the vector r s,a of the upper confidence bounds on its rewards:

r s,a = rs,a; i + c i ln(n s )/n s,a d i=1 (2)
with c i the exploration vs exploitation parameter for the i-th objective (Eq. ( 1)).

Finally, an upper-bound U (s, a) on the value of (s, a) is given by considering the hypervolume indicator of r s,a w.r.t. archive P .

U (s, a) = V (r s,a ) = HV (P ∪ {r s,a }; z) While U (s, a) does provide a scalar value of a node (s, a) conditioned on the solutions previously evaluated, it takes on a constant value if r s,a is dominated by some vectorial reward in P (section 2.1). A finer-grained value function must thus be defined. A straightforward option is to consider the so-called Pareto-rank of the vectorial rewards [START_REF] Deb | A fast elitist non-dominated sorting genetic algorithm for multiobjective optimization: NSGA-II[END_REF]. This option however hardly scales up as it requires one to maintain the archive of all vectorial rewards ever evaluated, and the rank of every point in it with quadratic complexity in the size of the archive, that is the number N of tree-walks. Instead, we consider the perspective projection r p s,a of r s,a onto P, the piecewise linear surface in IR d including all r u ∈ P (Fig. 1(b)). Let r p s,a denote the (unique) intersection of line (r s,a , z) with P (being reminded that z is dominated by all points in P and by r s,a )2 . The value function associated to (s, a) is then defined as the value of r s,a , minus the Euclidean distance between r s,a and r p s,a . Finally, the value of (s, a) is defined as:

W (s, a) = U (s, a) if r s,a is non-dominated in P U (s, a)-r p s,a -r s,a 2 otherwise (3)
The Euclidean distance term here sets a penalty for dominated points, increasing with their distance to the linear envelope P of P . Note that Eq. ( 3) sets a total order on all vectorial rewards in IR d , where non-dominated points are ranked higher than dominated ones.

It is straightforward to see that the total order based on W (s, a) is consistent with Pareto-domination: if r s,a is dominated by r s ,a then W (s, a) < W (s , a ). In the general case however, the order based on W (s, a) is not necessarily consistent with the Pareto rank: As the Pareto front is not bound to make regular progress in the objective space, a point with low Pareto rank can be closer to the Pareto front in the objective space, than a point with higher Pareto rank.

MO-MCTS algorithm

MO-MCTS differs from MCTS in only three respects (Alg. 1). Firstly, the selected action a * now is the one maximizing value function W (s, a) (Eq. (3) replacing Eq. ( 1)). Secondly, MO-MCTS maintains the archive P of all non-dominated vectorial rewards evaluated in previous tree-walks by MO-MCTS. Upon arriving in a terminal state u, MO-MCTS evaluates the cumulative reward r u of the tree-walk. It then updates r s,a as well as the (vectorial) RAV E(a) for all nodes (s, a) visited during the tree-walk, and it updates P if r u is non-dominated. Thirdly, the RAVE vector is used to select the new node in the tree-building phase. Letting s denote the current node and a an admissible action in state s, letting RAV E(a) denote the average vectorial reward associated to a, letting RAV E p (a) denote the perspective projection of RAV E(a) on the Pareto front, then the action selected is the one minimizing

R(a) = RAV E p (a) -RAV E(a) 2 (4)
Remark. MO-MCTS theoretical analysis is hindered as value function W dynamically depends on archive P (Eq. ( 3)). However, the reward estimates do not undergo any

+ 1) 1/b == (n s ) 1/b ) then Select a * = argmax {W (s,

Experimental validation

This section presents the experimental validation of MO-MCTS, with two goals in mind. The first goal of experiments is to assess the MO-MCTS performance comparatively to the state of the art in MORL [START_REF] Vamplew | Empirical evaluation methods for multiobjective reinforcement learning algorithms[END_REF]. The study will consider the artificial Deep Sea Treasure (DST) problem (section 4.1).

The second goal of experiments is to assess the performance and scalability of MO-MCTS in a real-world setting, that of grid scheduling problems (section 4.2).

All reported results are averaged over 11 runs unless stated otherwise. The computational times are measured on a PC with Intel dual-core CPU 2.66GHz.

Deep Sea Treasure

The Deep Sea Treasure (DST) problem was firstly introduced by [START_REF] Vamplew | Empirical evaluation methods for multiobjective reinforcement learning algorithms[END_REF]. The state space of DST consists of a 10 × 11 grid (Fig. 2(a)). The action space of DST includes four actions (up, down, left and right), each deterministically sending the agent to one adjacent square in the indicated direction, except when the agent would cross the border line of the grid or touch the sea floor, in which case the agent keeps in the same place. Each policy, with the top left square as initial state, gets a two dimensional reward : the time spent until reaching a terminal state or reaching the time horizon T = 100, and the treasure attached to the terminal state (depicted in Fig. 2(a)). The 10 non-dominated vectorial rewards in the form of (-time, treasure) are depicted in the two-dimensional plane in Fig. 2(b), forming a non-convex Pareto front.

Baseline algorithm

As mentioned in the introduction, the state of the art in MORL considers a scalar aggregation (e.g. a weighted sum) of rewards associated to all objectives. Numerous multiple-policy MORL algorithms have been proposed [START_REF] Natarajan | Dynamic preferences in multi-criteria reinforcement learning[END_REF]; [START_REF] Tesauro | Managing power consumption and performance of computing systems using reinforcement learning[END_REF]; [START_REF] Barrett | Learning all optimal policies with multiple criteria[END_REF]) using the weighted sum of the objectives (with several weight settings) as scalar reward, which is optimized with standard reinforcement learning algorithms. The differences between the above algorithms are how they share the information between different weight settings and which weight settings they choose to optimize. In the following, MO-MCTS is compared to Multi-Objective Q-Learning (MOQL) [START_REF] Vamplew | Empirical evaluation methods for multiobjective reinforcement learning algorithms[END_REF]). Choosing MOQL as baseline is motivated as it is able to yield all policies found by other linear-scalarisation based approaches, provided that a sufficient number of weight settings be considered.

Formally, in the two objective reinforcement learning case, MOQL optimizes independently m scalar RL problems through Q-learning, where the i-th problem considers reward

r i = (1 -λ i ) × r1 + λ i × r2, where 0 ≤ λ i ≤ 1, i = 1, 2, .
. . , m define the m weight settings of MOQL, and r1 (respectively r2) is the first (resp. the second) objective reward. In its simplest version, the overall computational effort is equally divided between the m scalar RL problems. The computational effort allocated to the each weight setting is further equally divided into n tr training phases; after the j-th training phase, the performance of the i-th weight setting is measured by the two-dimensional vectorial reward, noted r i,j , of the current greedy policy. The m vectorial rewards of all weight settings {r 1,j , r 2,j , . . . , r m,j } all together compose the Pareto front of MOQL at training phase j.

Experimental setting

The DST problem is concerned with minimizing the search time (maximizing its opposite) and maximizing the treasure value. Accordingly, the reference point used in the hypervolume indicator calculation is set to (-100,0).

We use the same MOQL experimental setting as in [START_REF] Vamplew | Empirical evaluation methods for multiobjective reinforcement learning algorithms[END_REF]:

• -greedy exploration is used with = 0.1.

• Learning rate α is set to 0.1.

• The state-action value table is optimistically initialized (time = 0, treasure = 124).

• Due to the episodic nature of DST, no discounting is used in MOQL (γ = 1).

• The number m of weight settings ranges in {3, 7, 21}, with 10455) as it is not asymptotically consistent. This is explained by the fact that the Pareto front of DST is not convex. As is widely known [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF], linear-scalarisation based approaches of MOO fail to discover solutions in non-convex regions of the Pareto front. Actually, the plateau of MOQL corresponds to the discovery of the extreme points (-19,124) and(-1,1) of the Pareto front, as confirmed by Fig. 4(a). In the meanwhile, MO-MCTS improves its performance as time increases, and it reaches a better hyper-volume indicator than MOQL after 40,000 time steps. Note that each time step in MO-MCTS is computationally heavier than for MOQL (for 315,000 time steps, MO-MCTS takes 82 secs versus 27 secs for MOQL).

λ i = i-1 m-1 , i = 1, 2, . . . , m.

Grid scheduling

Pertaining to the domain of autonomic computing [START_REF] Tesauro | Managing power consumption and performance of computing systems using reinforcement learning[END_REF], the problem of grid scheduling has been selected to establish a proof on the scalability of MO-MCTS. The presented experimental validation considers the problem of grid scheduling, referring the reader to [START_REF] Yu | Workflow Scheduling Algorithms for Grid Computing[END_REF] for a comprehensive presentation of the field. Grid scheduling is concerned with scheduling J tasks on m distinct computational resources with different unit time costs and processing capabilities. As tasks are interdependent and resources are heterogeneous, job scheduling is an NP-hard combinatorial optimization problem [START_REF] Ullman | NP-complete scheduling problems[END_REF].

Grid scheduling naturally aims at minimizing the so-called makespan, that is the overall job completion time. But other objectives such as energy consumption, monetary cost, or the allocation fairness w.r.t. the resource providers become increasingly important. In the rest of section 4.2, two objectives will be considered, the makespan and the cost of the solution3 .

Baseline algorithms

The state of the art in grid scheduling is achieved by stochastic optimization algorithms [START_REF] Yu | Workflow Scheduling Algorithms for Grid Computing[END_REF]. The two prominent multi-objective variants thereof are NSGA-II [START_REF] Deb | A fast elitist non-dominated sorting genetic algorithm for multiobjective optimization: NSGA-II[END_REF] and SMS-EMOA [START_REF] Beume | SMS-EMOA: Multiobjective selection based on dominated hypervolume[END_REF]. Both algorithms can be viewed as importance sampling methods. They maintain a population of solutions, initially defined as random execution plans. Iteratively, the solutions with best Pareto rank and best crowded distance (a density estimation of neighboring points in NSGA-II) or hyper-volume indicator (in SMS-EMOA) are selected and undergo unary or binary stochastic perturbations.

Experimental setting

A simulated grid environment containing 3 resources with different unit time costs and processing capabilities (cost 1 = 20, speed 1 = 10; cost 2 = 2, speed 2 = 5; cost 3 = 1, speed 3 = 1) is defined. We firstly compare the performance of MO-MCTS and baseline algorithms on a realistic bio-informatic workflow EBI ClustalW2, which performs a ClustalW multiple sequence alignment using the EBI's WSClustalW2 service 4 . This workflow contains 21 tasks and 23 precedence pairs (graph density q = 12%), assuming that all workloads are equal. Secondly, the scalability of MO-MCTS is tested through experiments based on artificially generated workflows containing respectively 20, 30 and 40 tasks with graph density q = 15%.

As evidenced from the literature [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF], MCTS performances heavily depend on the so-called random phase (section 2.2). Preliminary experiments showed that a uniform action selection in the random phase was ineffective on grid scheduling problem. A simple heuristic which allocates the task with maximum (respectively minimum) expected finish time to the fastest (resp. slowest) resource is implemented in the random phase.

The parameters of all algorithms have been selected after preliminary experiments, using the same amount of computational resources for a fair comparison. The progressive widening parameter b in MO-MCTS is set to 4. The exploration vs exploitation trade-off parameters associated to the makespan and the cost objectives, c time and c cost , are both set to 5 × 10 -3 . The parameters used for NSGA-II (respectively SMS-EMOA) involve a population size of 200 (resp. 120) individuals, of which 100 are selected and undergo stochastic unary and binary variations (resp. one-point re-ordering, and resource exchange among two individuals). For all three algorithms, the number N of tree-walks a.k.a. evaluation budget is set to 10,000. The reference point in each experiment is set to (z t , z c ), where z t and z c respectively denote the maximal makespan and cost.

The performance indicator is the difference between the actual Pareto front found in the run, and the reference Pareto front P * gathering all non-dominated vectorial rewards obtained in all runs of all three algorithms. The run with Pareto front P is assessed from its hyper-volume indicator regret w.r.t. the reference Pareto front (the smaller, the better): Overall, the main weakness of MO-MCTS is its computational runtime, ca 5 times higher than that of NSGA-II and SMS-EMOA5 . Such disadvantage can be alleviated when the evaluation time of one strategy is far more than the time of one tree-walk in MO-MCTS.

Discussion

As mentioned, the state of the art in MORL is divided into single-policy and multiple policy algorithms [START_REF] Vamplew | Empirical evaluation methods for multiobjective reinforcement learning algorithms[END_REF]. In the former case, the authors use a set of preferences between objectives which are user-specified or derived from the problem domain (e.g. defining preferred regions [START_REF] Mannor | A geometric approach to multi-criterion reinforcement learning[END_REF] or setting weights on the objectives [START_REF] Tesauro | Managing power consumption and performance of computing systems using reinforcement learning[END_REF]) to aggregate the multiple objectives in a single one. The strength of the single-policy approach is its simplicity; its long known limitation is that it cannot discover a policy in non-convex regions of the Pareto front [START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF].

In the multiple-policy case, multiple Pareto optimal vectorial rewards can be obtained by optimization of different scalarized RL problems under different weight settings. Natara- Interestingly, MO-MCTS likewise maintains vectorial reward estimates for all visited nodes with complexity O(B|P | d/2 logN ) in the N -th tree-walk, which is lower than that of one value iteration in [START_REF] Barrett | Learning all optimal policies with multiple criteria[END_REF], considering that the size of P is of the same order of magnitude as the number n of non-dominated Q vectors.

In summary, the main strength of MO-MCTS is its ability to discover policies lying in the non-convex regions of the Pareto front. To our knowledge 6 , this feature is unique in the MORL literature. On the negative side, MO-MCTS requires some domain knowledge when solving large scale problems (e.g. grid scheduling). Further, it suffers from a higher computational cost compared to stochastic multi-objective optimization algorithms NSGA-II and SMS-EMOA. The average complexity of generating one solution in NSGA-II is O(dλ), where λ is the population size; the complexity of SMS-EMOA is O(λ d/2 ). Both algorithms use a fixed size Pareto archive. On the contrary, MO-MCTS with a complexity of O(B|P | d/2 logN ) pays a logarithmic price in the number N of tree-walks.

6. A general polynomial result of MOO has been proposed by [START_REF] Chatterjee | Markov decision processes with multiple long-run average objectives[END_REF], which claims that for all irreducible MDP with multiple long-run average objectives, the Pareto front can be -approximated in time polynomial in . However this claim relies on the assumption that finding some Pareto optimal point can be reduced to optimizing a single objective: optimize a convex combination of objectives using as set of positive weights (page 2, Chatterjee ( 2007)), which does not hold for non-convex Pareto fronts. Furthermore, the approach relies on the -approximation of the Pareto front proposed by [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF], which assumes the existence of an oracle telling for each vectorial reward whether it is -Pareto-dominated (Thm. 2, page 4, [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF]).

Conclusion and perspectives

The multi-objective extension of MCTS presented in this paper has been validated on two problems : Deep Sea Treasure (DST) and grid scheduling. Compared to the linearscalarisation based MORL approaches, which fail to discover vectorial rewards in the nonconvex regions of the Pareto front, MO-MCTS solves DST and experimentally converges to the Pareto front. In the real-world grid scheduling problem, MO-MCTS yields comparable performances to the state of the art at the price of a higher computational cost. As grid scheduling is an extensively studied problem with major industrial impacts, it might thus be considered promising that MO-MCTS first results match the state of the art of the domain.

Only deterministic settings have been considered in the paper. On-going experiments, investigating the impact of stochastic transition models, show that the MO-MCTS performance degrades gracefully as the stochasticity of the environment increases.

As mentioned, a major perspective for further work is to establish the consistency of MO-MCTS. Another perspective is to refine the RAVE heuristics (e.g. considering the context of task allocation in grid scheduling), and reduce the computational cost, through systematically pruning the archive. Other measures similar to the hyper-volume indicator, e.g. the logarithmic hyper-volume indicator investigated by [START_REF] Friedrich | The logarithmic hypervolume indicator[END_REF] will also be considered.

  The left figure shows vectorial rewards in the two-dimensional objective plane. The non-dominated vectorial rewards are depicted as black crosses. The hypervolume indicator of these solutions w.r.t reference point z in the lower-left corner is the surface of the shaded region. The right figure shows the perspective projection r p x of r x on the piecewise linear envelope of the Pareto front (section 3.2).

  Figure 2: The Deep Sea Treasure problem. Left: the DST state space with black cells as sea-floor, grey cells as terminal states, the treasure value is indicated in each cell. The initial position is the upper left cell. Right: the Pareto front in the time×treasure plane. distribution change per se; they are updated and the confidence increases with the number of tree-walks as in UCT. The only change affects the value function W (s, a), which needs to be recomputed for all child nodes of every visited node when the Pareto front P is updated. Let B denote the average branching factor in the MO-MCTS tree, and let N denote the number of tree-walks. As each tree-walk adds a new node in the search tree, the number of nodes in the tree is N + 1. The average length of a tree-path thus is in O(log N ). Depending on the number d of objectives, the hyper-volume indicator is computed with complexity O(|P | d/2 ) for d > 3 (respectively O(|P |) for d = 2 and O(|P | log (|P |)) for d = 3) (Beume et al., 2009). The complexity of each tree-walk thus is O(B|P | d/2 logN ), where |P | is at most the number N of tree-walks.MO-MCTS parameters are i) the total number of tree-walks N , ii) the exploration vs exploitation trade-off parameter c i for every i-th objective ; iii) the b parameter used in the progressive widening heuristic; and iv) the reference point z.

•

  Training time is set to 15,000 time steps for each weight setting, totaling 45,000 time steps for m = 3-MOQL, 105,000 times steps for m = 7-MOQL, and 315,000 time steps for m = 21-MOQL. • The number of training phases n tr is set to 150. MO-MCTS parameters include the parameter b used in progressive widening, and the exploration vs. exploitation trade-off parameters associated to the time cost objective and the treasure value objective. After a few preliminary experiments, b is set to 2, c time is set to 20,000 and c treasure is set to 150. The overall training time for MO-MCTS is 315,000 time steps, ca 15,600 tree-walks. The performance is reported as the hyper-volume indicator (averaged over 11 independent runs with the same experimental setting), and the Pareto front of the MO-MCTS run with median hyper-volume indicator, in the time×treasure plane. Left: The hyper-volume indicator of MO-MCTS and m = 21-MOQL. Right: The hyper-volume indicator of MOQL for m = 3, 7, 21. All results, averaged over 11 independent runs, are reported vs the number of training time steps.

Fig. 3

 3 Fig.3displays the hyper-volume indicator performance of MO-MCTS and that of MOQL for m = 3, 7, 21. It is observed that for m = 7 or 21, MOQL reaches a performance plateau (10062) within 20,000 time steps. MOQL does not reach the optimal hyper-volume indicator (10455) as it is not asymptotically consistent. This is explained by the fact that the Pareto front of DST is not convex. As is widely known[START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF], linear-scalarisation based approaches of MOO fail to discover solutions in non-convex regions of the Pareto front. Actually, the plateau of MOQL corresponds to the discovery of the extreme points(-19,124) and (-1,1) of the Pareto front, as confirmed by Fig.4(a). In the meanwhile, MO-MCTS improves its performance as time increases, and it reaches a better hyper-volume indicator than MOQL after 40,000 time steps. Note that each time step in MO-MCTS is computationally heavier than for MOQL (for 315,000 time steps, MO-MCTS takes 82 secs versus 27 secs for MOQL). Fig. 3(b) shows the influence of m on MOQL. For m = 7, MOQL reaches the performance plateau before MOQL for m = 21 (respectively 8,000 time steps vs 20,000 time steps). However, Fig. 3(b) shows the instability of the average hyper-volume indicator for m = 7, and shows that the instability increases as m decreases to 3. The fact that for m = 3 MOQL fails to reach the MOQL performance plateau is explained as the extreme point (-19,124) can be missed in some runs as the discount parameter γ is 1 (by consistency with Vamplew et al. (2010)). Therefore the 124 treasure might be discovered later than in time 19. The percentage of times out of 11 runs that each non-dominated vectorial reward is discovered for at least one test episode during the training process of MO-MCTS and MOQL for m = 21 is displayed in Fig. 4(b). This picture shows that MOQL can discover

Fig. 3

 3 Fig.3displays the hyper-volume indicator performance of MO-MCTS and that of MOQL for m = 3, 7, 21. It is observed that for m = 7 or 21, MOQL reaches a performance plateau (10062) within 20,000 time steps. MOQL does not reach the optimal hyper-volume indicator (10455) as it is not asymptotically consistent. This is explained by the fact that the Pareto front of DST is not convex. As is widely known[START_REF] Deb | Multi-objective optimization using evolutionary algorithms[END_REF], linear-scalarisation based approaches of MOO fail to discover solutions in non-convex regions of the Pareto front. Actually, the plateau of MOQL corresponds to the discovery of the extreme points(-19,124) and (-1,1) of the Pareto front, as confirmed by Fig.4(a). In the meanwhile, MO-MCTS improves its performance as time increases, and it reaches a better hyper-volume indicator than MOQL after 40,000 time steps. Note that each time step in MO-MCTS is computationally heavier than for MOQL (for 315,000 time steps, MO-MCTS takes 82 secs versus 27 secs for MOQL). Fig. 3(b) shows the influence of m on MOQL. For m = 7, MOQL reaches the performance plateau before MOQL for m = 21 (respectively 8,000 time steps vs 20,000 time steps). However, Fig. 3(b) shows the instability of the average hyper-volume indicator for m = 7, and shows that the instability increases as m decreases to 3. The fact that for m = 3 MOQL fails to reach the MOQL performance plateau is explained as the extreme point (-19,124) can be missed in some runs as the discount parameter γ is 1 (by consistency with Vamplew et al. (2010)). Therefore the 124 treasure might be discovered later than in time 19. The percentage of times out of 11 runs that each non-dominated vectorial reward is discovered for at least one test episode during the training process of MO-MCTS and MOQL for m = 21 is displayed in Fig. 4(b). This picture shows that MOQL can discover

F

  Fig.5displays the comparative hyper-volume indicator regrets of MO-MCTS, NSGA-II and SMS-EMOA on EBI ClustalW2 workflow scheduling and on artificial jobs with a number J of tasks ranging in 20, 30 and 40 with graph density q = 15%. Fig.6shows the Pareto front discovered by MO-MCTS, NSGA-II and SMS-EMOA after N = 100, 1000 and 10000 policy evaluations (tree-walks), comparatively to the reference Pareto front. On all considered problems regardless of their size, MO-MCTS outperforms both NSGA-II and SMS-EMOA throughout the search process. The good performance of MO-MCTS is explained as MO-MCTS discovers solutions in the low cost and small makespan regions, much earlier than NSGA-II and SMS-EMOA. More generally, MO-MCTS tends to explore more widely the Pareto front than NSGA-II and SMS-EMOA. In counterpart, MO-MCTS performances are slightly worse in the lower region of the Pareto front, than that of NSGA-II and SMS-EMOA. Overall, the main weakness of MO-MCTS is its computational runtime, ca 5 times higher than that of NSGA-II and SMS-EMOA 5 . Such disadvantage can be alleviated when the evaluation time of one strategy is far more than the time of one tree-walk in MO-MCTS.

Figure 6 :

 6 Figure 6: Progression of the Pareto-optimal solutions found for N = 100, 1000 and 10000 for MO-MCTS, NSGA-II and SMS-EMOA on the EBI ClustalW2 workflow. The reference Pareto front is indicated by circles. jan and Tadepalli (2005) show that the efficiency of MOQL can be improved by sharing information between different weight settings. A hot topic in multiple-policy MORL is how to design the weight setting and share information among the different scalarized RL problems. In the case where the Pareto front is known, the design of the weight settings is made easier (provided that the Pareto front is convex). When the Pareto front is unknown, one alternative provided by Barrett and Narayanan (2008) is to maintain Q-vectors instead of Q-values for each pair (state, action). Through an adaptive selection of weight settings corresponding to the vectorial rewards on the boundary of the convex set of the current Qvectors, this algorithm narrows down the set of selected weight settings, at the expense of a higher complexity in each value iteration: the O(|S| 2 |A|) complexity of standard Q-learning is multiplied by a factor O(n d ), where n is the number of points on the convex hull of the Q-vectors and d is the number of objectives.Interestingly, MO-MCTS likewise maintains vectorial reward estimates for all visited nodes with complexity O(B|P | d/2 logN ) in the N -th tree-walk, which is lower than that of one value iteration in[START_REF] Barrett | Learning all optimal policies with multiple criteria[END_REF], considering that the size of P is of the same order of magnitude as the number n of non-dominated Q vectors.In summary, the main strength of MO-MCTS is its ability to discover policies lying in the non-convex regions of the Pareto front. To our knowledge 6 , this feature is unique in the MORL literature. On the negative side, MO-MCTS requires some domain knowledge when solving large scale problems (e.g. grid scheduling). Further, it suffers from a higher computational cost compared to stochastic multi-objective optimization algorithms NSGA-II and SMS-EMOA. The average complexity of generating one solution in NSGA-II is O(dλ), where λ is the population size; the complexity of SMS-EMOA is O(λ d/2 ). Both algorithms use a fixed size Pareto archive. On the contrary, MO-MCTS with a complexity of O(B|P | d/2 logN ) pays a logarithmic price in the number N of tree-walks.

  Algorithm 1 MO-MCTS MoMCTS Input: number N of tree-walks Output: search tree T Initialize T ← initial state, P ← {} for i = 1 to N do r u ← TreeWalk(T , P, initial state ) if r u is not dominated by any point in P then Eliminate all points dominated by r u in P P ← P ∪ {r u } end if end for TreeWalk Input: search tree T , archive P , state s Output: reward vector r u //Test of the Progressive Widening condition, section 2.2 if s is not a leaf node, and ( (n s

Another option is to use a dynamically weighted combination of the reward rs,a and RAV E(a) in Eq.(1), see e.g.[START_REF] Gaudel | Feature selection as a one-player game[END_REF].

Another possibility would be to define r p s,a as the orthogonal projection of rs,a onto P. However, the use of orthogonal projection might have induced discontinuities of value function W w.r.t. rs,a, since P is not necessarily convex.

As both objectives in the grid scheduling problem are to be minimized, the plus sign in the r.h.s. of Eq. (2) is changed to minus sign, in order to provide duly optimistic estimates of the objective rewards.

The complete description is available at http://www.myexperiment.org/workflows/203.html.

On workflow EBI ClustalW2, the average execution time of MO-MCTS, NSGA-II and SMS-EMOA are respectively 142 secs, 31 secs and 32 secs.

Acknowledgments

We wish to thank Ilya Loshchilov, Jean-Baptiste Hoock, Dawei Feng, Romaric Gaudel, and Julien Perez for many discussions on UCT, MOO and MORL. We also warmly thank the anonymous reviewers for their many remarks and critiques on an earlier version of the paper.


Vincent De Rudnicki
email: vincent.derudnicki@irstea.fr

Jean-Paul Douzals

Michel Tolosa

Nicolas Sidos

Eric Cotteux

SPRAYING QUALITY ASSESSMENT OF SPRAYERS DEVOTED TO MOSQUITO CONTROL

Keywords: Mosquito control, spraying, spatial distribution, biological efficacy

Mosquito control operators in France are mainly public and have at their disposal a wide range of spraying techniques to control mosquitoes. Due to the lack of commercial solutions, and in order to meet technical objectives and comply with regulations, they look to continuously improve their spraying application techniques.

In the framework of the European Life+ project LIFE08 ENV/F/000488, the aim of this paper is to describe a new approach in order to evaluate sprayer's performance comparing Droplet distribution on the ground for larvicides and in the air for spatial adulticiding.

Introduction

Mosquito control in France is achieved through the spraying of insecticide in natural areas including water surfaces a wide range of sprayers with a combination of terrestrial and aerial applications. Classical evaluation of the application is mainly related to biological efficacy in terms of mosquito (larvae or adults) mortality [START_REF] Dayal | Different parameters that affect droplet-size distribution from nasal sprays using the Malvern Spraytec[END_REF]. The IMCM Life + project encompasses the evaluation of the spraying quality of terrestrial sprayers for both larvicide and adulticide applications by testing sprayer performance in terms of droplet sizes and deposits. A two step methodology was developed by Irstea (ex_Cemagref) in order to get accurate data from different spraying techniques to be compared with biological efficacy.

Material and Methods

Four different sprayers (Table 1) were tested through droplet size measurements and ground or atmospheric deposits for pure water and ad hoc biocide (i.e. BTi incl. in Aquabac XT® or VectoBac 12 AS® specialties for larvicide and Aqua K Othrin EW® for adulticide). Droplet sizes were measured by using a Malvern Spraytec device by using light diffraction measurements. 1. Literature on such an experimental particle seizer indicates easy setting up as well as reliable reproducibility of results [START_REF] Dayal | Different parameters that affect droplet-size distribution from nasal sprays using the Malvern Spraytec[END_REF].

Spatial distribution on the ground for larvicide

Ground deposits of larvicide were estimated with the use of BSF tracer (1 g/l: Brilliant Sulfoflavine) dosage in Petri dishes placed every meter on distances varying from 20 m to 80 m depending on the sprayer. Due to short spray range in the case of Argo/ATV (1 table1) 3 lines of 17 boxes were placed at 0.5m in accordance with ISO/CD 24253 [START_REF]ISO/AWI 24253-1 Matériel de protection des cultures --Essais de mesurage du dépôt des pulvérisateurs à rampe --Partie 1: Mesurages au champ du dépôt au sol[END_REF]). Weather conditions

Weather conditions were recorded by using a RM Young 3D Ultrasonic weather station. Table 2 recapitulates this information for the tests. It should be noted that in all cases (larvicide or adulticide), spraying applications were carried out under the wind as the collecting grid was adapted depending on the weather conditions.

Measurement method of deposit

After spraying phase and a lag time of 20 min, Petri dishes were individually collected. Dye contents was measured through spectrofluorometry (Perkin Elmer 45 LS) with the help of a a calibration curve. Results are directly expressed in terms of field dosage for the different sampling positions For larvicide application, the dosage corresponds to the amount measured in one dish (58 cm²) and considered as representative of the local deposits. The recovery rate corresponds to the integral of the values under the distribution curve. For adulticide applications, the calculated amount is expressed in ȝg/cm² of collector; the surface of collection corresponds to a half perimetr (0,1 cm) * length of the wire (37 cm).

Results & conclusion

Droplets granulometry

A single measurement of droplet size with pure water does not give reliable information of sprayability of a real mixture. In general, Dv50 is lower when mixtures are used. Droplet sizes measurement let appear significant differences between water and mixtures (Fig 6) for all kind of sprayers and particularly for Fogger, ARGO and knacksack mist blower for which the reduction reaches 50% ( Fig 7).

FIGURE 6: comparison of DV50 droplet sizes for each apparatus for water and product used. In general droplet sizes are coherent regarding the use of those sprayers with larger droplets in the case of the larvicide application compared to adulticide (These measurements are confirmed by a percentage of the size of droplets lower than 100 ȝm, strongly required in the case of the adulticide application [START_REF] Knepper | Aerially applied, Liquid Bacillius Thuringiensis Var. Israelensis (H-14) for control of Spring Aedes Mosquitoes in Michigan[END_REF]. One also can notice the notable shift in Granulometry when products are used which induce smaller droplets.

Measurements of granulometry with the product made possible the characterization of each apparatus and to check the relevance of the design with respect to the type of application.

Ϯ͘ϰ͘ Spatial distribution of ground deposits for larvicide in the case of larvicide application, Martignani Phantom and ARGO system were tested.

Conclusion

The characterization of mosquito control was achieved through distribution of the droplet sizes and ground or atmospheric deposits distribution. A rather good correlation is observed between the size of drops with the chemical and the type of application.

In the case of larvicide application lower spray ranges were shown compared to expectations but results were consistent with previous studies [START_REF] Jp | Spraying quality assessment of a mist blower used on banana crops[END_REF]. The protocol experienced for adulticide application showed that test benches could be extended as deposits up to 100 m were found for the canon mist blower -ULV mode or 70 m for the fogger. However the global amount of adulticide collected varied in great proportion depending on the sprayer. In conclusion, this preliminary study on sprayer performance will allow the implementation of Better Management Practices among mosquito control operators. A second objective will be to link physical deposits with biological efficacy.

FIGURE 1 :

 1 FIGURE 1: Granulometry laser using diffraction

FIGURE 3 :

 3 FIGURE 3: Collecting grid for the ARGO/ATV system

FIGURE 4 :

 4 FIGURE 4: Specific vertical supports to evaluate air adulticide treatment 2.4.Weather conditions

FIGURE 7 :

 7 FIGURE 7: Percentage of reduction Product/water

FIGURE 8 :

 8 FIGURE 8: Distribution Curves of Martignani for the 3 tests

Figure 12 :

 12 Figure 12: Deposits distribution in the air -Canon ULV AQUA K-OTHRINE EW

TABLE 1 :

 1 List of sprayers tested

	Sprayer	Product used	Settings	Forwar d Speed	Theoretical Spray Range	Test bench
	Argo/ATV	Vectobac 12AS®	Teejet TT 02 8 km/h	4 m / side	50 m
	Martignani 300 l/h Martignani 200 l/h	Aquabac XT ® Aquabac XT ®	Peripheral diffusers		30 m	80 m
	Martignani 45 l/h London Fogger STHIL 420 "atomiser	Aqua K -Othrin EW®	Central diffuser Calib. Pellet 0.5 and 0.8	9 km/h 3 km/h	50 m 40 m 10 m	88 m 22 m

TABLE 2 :

 2 Weather conditions

	ƐƉƌĂLJĞƌ	dĞŵƉ	ZĞůĂƚŝ|Ğ	tŝŶĚ ďƵƌƐƚ	ŽƌŝĞŶƚĂƚŝŽŶ
		Σ	,ƵŵŝĚŝƚLJ й	ŬŵͬŚ
	Z'K	ϭϳ͘ϭ	ϰϬ	ϭϵͬϮϲ	^K
	ĂŶŽŶ DĂƌƚŝŐŶĂŶŝ ƋƵĂďĂĐ yd ϯϬϬ	ϭϳ͕ϳ	ϰϱ	ϭϳͬϮϲ	^K
	ĂŶŽŶ DĂƌƚŝŐŶĂŶŝ ƋƵĂďĂĐ yd ϮϬϬ	ϭϲ͕ϳ	ϰϬ	ϭϵͬϯϬ	^
	ĂŶŽŶ DĂƌƚŝŐŶĂŶŝ sĞĐƚŽĂĐ ϭϮ ^ ϯϬϬ	ϭϴ	ϳϮ	ϮϮͬϯϭ	^
	ĂŶŽŶ h>s	ϭϳ	ϰϱ	ϮϬͬϮϴ	^K
		ϭϳ	ϰϱ	ϵͬϭϳ	E
	knacksack mist blower ^d,/>	Ϯϭ	ϭϰ	ϭϲͬϯϭ	E

CIGR-Ageng 2012. International Conference on Agricultural Engineering, 8-12 Juillet 2012, Valence, Espagne