L Abbas-Turki
email: lokmane.abbasturki@sorbonne-universite.fr.

B Diallo

G Pagès

Conditional Monte Carlo Learning for Diffusions II: extended methodology and application to risk measures and early stopping problems

, we presented a One-layered Nested Monte Carlo (1NMC) to simulate functionals U of a Markov process X. Based on a judicious combination between regression and 1NMC used for localization purpose, this methodology allows to simulate U t≥s conditionally on X s . The parallel suitability and scalability of 1NMC makes this algorithm very competitive to simulate quantities that are almost impossible to simulate with other methods. In this paper, using the double layer of trajectories, we explain further the mathematical background of the control on the bias propagation. With this double layer structure, we also detail how to adjust the variance to get a better approximation of the second moment from the regression. In normal and log-normal models, this variance adjustment allows a better description of tail events. Since we applied this algorithm on Backward Stochastic Differential Equations in CMCLDI, we show here its strength for the simulation of risk measures and optimal stopping problems. Two highly dimensional numerical examples are executed in few minutes on one Graphics Processing Unit (GPU).

Introduction

Various contributions like [START_REF] Abbas-Turki | XVA principles, nested Monte Carlo strategies, and GPU optimizations[END_REF][START_REF] Broadie | Risk estimation via regression[END_REF][START_REF] Giorgi | Weak Error for Nested Multilevel Monte Carlo[END_REF][START_REF] Gordy | Nested Simulation in Portfolio Risk Measurement[END_REF][START_REF] Lee | Computing the distribution function of a conditional expectation via Monte Carlo: Discrete conditioning spaces[END_REF] show an increasing interest in Nested Monte Carlo (NMC) simulation. NMC used to be avoided due to the heavy computations that it involves, but it becomes relevant as it can be very efficiently implemented on massively parallel architectures like Graphics Processing Units (GPUs). Its perfect scalability with respect to an increasing computing capability makes it a sustainable solution for various applications. In CMCLDI [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF], we proposed local analytical approximations of functionals of a diffusion using various regressions within One-layered Nested Monte Carlo (1NMC) simulation. As 1NMC is two layers of Monte Carlo simulations, the inner trajectories are used for regressions when the outer ones are used for localization purpose. The conditional learning stands then for regressions conditional to various starting points on the outer trajectories.

In the present work as well as in CMCLDI [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF], we choose local regressions even though it can be replaced by local Neural Networks (NNs). Unlike [START_REF] Buehler | Deep hedging[END_REF][START_REF] Han | Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations[END_REF][START_REF] Goudenège | Variance Reduction Applied to Machine Learning for Pricing Bermudan/American Options in High Dimension[END_REF] where NNs are global on the whole Monte Carlo realizations, regressions are sufficient when made local using 1NMC and their implementation is also very efficient using batch parallel processing [START_REF] Abbas-Turki | Resolving small random symmetric linear systems on graphics processing units[END_REF]. We already demonstrated the effectiveness of our methodology on a large number of Backward Stochastic Differential Equations (BSDEs) examples presented in CMCLDI. We also showed that the bias backpropagation can be removed using a new simple trick that is only possible because of the nested nature of the proposed algorithm.

In this contribution, CMCLD part II (CMCLDII), we push further the capabilities of CMCLDI (cf. [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF]) using a small modification that allows to get accurate approximations of the variance of the simulated functionals of diffusions. This modification plays an important role to simulate tail events necessary to risk measures and optimal stopping strategies. To make as simple as possible the explanation of the introduced modifications, we use the same generic example presented in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF].

On a filtered probability space (Ω, F, (F t ) 0≤t≤T , P), the generic example is driven by an F t -Markov process (X t ) t∈[0,T ] taking its values on R d 1 . Given the fine time discretization S = {t 0 , ..., t 2 L } = 0, T /2 L , ..., T , the functional U s of X is defined for s ∈ S by

(f ) U s = u s (X s ) = E s   2 L k=s2 L /T f (t k , X t k , X t k+1 )   = E s≤t k ≤T f (t k , X t k , X t k+1 ) F s ,
where E s (•) = E • F s , the expectation is always considered under P, each deterministic function f (t k , •, •) is B(R d 1 ) ⊗ B(R d 1 )-measurable and assumed to satisfy the square integrability condition E(f 2 (t k , X t k , X t k+1 )) < +∞ with convention f (t 2 L , X t 2 L , X t 2 L +1 ) = f (t 2 L , X t 2 L ). From the Markov assumption, for each s ∈ S, the B(R d 1 )-measurable function u s is deterministic.

1NMC requires the simulation of a first layer (X m 0 ) m 0 =1,...,M 0 of outer trajectories of the process X that are kept in the machine's random-access memory, then a second (X m 0 ,m 1 ) m 1 =1,...,M 1 unstored layer of inner trajectories, on the top of each outer one indexed by m 0 . Introducing a discretization set S ⊂ S for the process U , it is then possible to define an inner simulation U m 0 ,m 1 = u m 0 ,S (X m 0 ,m 1 ) and an outer simulation U m 0 = u m 0 ,S . Defined in CMCLDI, u m 0 ,S and u m 0 ,S are respectively the coarse and the fine approximations of the deterministic function u introduced in (f ). The approximation u m 0 ,S is considered as an average value on the realizations u m 0 ,S (X m 0 ,m 1 ) and thus it averages out and reduces the approximation errors of u m 0 ,S .

To improve further the coarse approximation, we replace the expression u m 0 ,S s j ,s k (x) = u m 0 ,S s k ,s k + t T m 0 s j ,s k ,M 1 (x)B m 0 ,S s j ,s k ,

given in CMCLDI by u m 0 ,S s j ,s k (x) = u m 0 ,S s j ,s k + t T m 0 s j ,s k ,M 1 (x) B m 0 ,S s j ,s k ,

with B m 0 ,S s j ,s k = γ m 0 ,S s j ,s k B m 0 ,S s j ,s k (1.3) and u m 0 ,S s j ,s k = u m 0 ,S s k ,s k +

(1 -γ m 0 ,S s j ,s k )

M 1 M 1 m 1 =1
t T m 0 s j ,s k ,M 1 (X m 0 ,m 1 s j ,s k )B m 0 ,S s j ,s k , (

where t is used for the transpose operator, s j < s k ≤ s k are increments from S, T m 0 (X m 0 ,m 1 s j ,s k )B m 0 ,S s j ,s k .

Consequently, for each m 0 = 1, ..., M 0 , the benefit of (1.2) compared to (1.1) would be to better simulate the second moment u • (X m 0 ,m 1 ) without changing the accuracy of the first moment given that the latter is generally very well approximated using regressions.

In the same fashion as for stopping bias backpropagation (cf. CMCLDI [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF]), the variance adjustment is based on the tower property used to obtain the equality

E (Var s (U s )) = E E s [U s -E s (U s )] 2 = E [U s -E s (U s )] 2
true for s > s > 0. For s = s j and s = s k with (s j , s k ) as above, this equality allows us to choose the adjustment parameter γ m 0 ,S s,s that makes the average variance E (Var s (U s )) estimated by 1

M 0 M 0 m 0 =1 1 M 1 M 1 m 1 =1 u m 0 ,S s,s (X m 0 ,m 1 s,s ) -M 1 m 1 =1 u m 0 ,S s,s (X m 0 ,m 1 s,s )/M 1 2 equal to E [U s -E s (U s )] 2 estimated by 1 M 0 M 0 m 0 =1 u m 0 ,S s ,s -M 1 m 1 =1 u m 0 ,S s,s (X m 0 ,m 1 s,s )/M 1 2 .
Thus, the value of γ m 0 ,S s,s improves significantly the accuracy of the former estimator using the latter one. Using numerically the tower property to get the variance adjustment parameter γ m 0 ,S is made possible by the nested nature of the proposed simulation. We take fully advantage of this (nested structure, tower property) combination for the proposed variance adjustment trick. Other applications could benefit from this combination to improve the simulation result.

The rest of this paper is organized as follows. In Section 2, we recall the main steps of the algorithm including the variance adjustment modification and its adaptation to an optimal stopping problem. In Section 3, we express the value of γ m 0 ,S , provide an iterative construction of the discretization set S and explore in-depth the use of the tower property for local bias control and local variance adjustment. Previously presented in CMCLDI, stopping the bias backpropagation comes at the expense of an additional error term studied in Section 4. Section 5 concludes this paper with a successful simulation of both an American option and a risk measure examples in very high dimensions.

Methodology extension and application to optimal stopping problems

In [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF], we presented the algorithm steps and what should be done to stabilize it. We explained the whole methodology on a simple problem and we showed its benefits when one has to simulate the composition of functionals of a Markov process. Large number of BSDEs and Reflected BSDEs (RBSDEs) are specific composition of functionals of a forward process assumed Markov in various situations. In [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF], we already presented the adaptation of our methodology on the One step forward Dynamic Programming (ODP ) discretization scheme (cf. [START_REF] Gobet | Error expansion for the discretization of backward stochastic differential equations[END_REF][START_REF] Lemor | Rate of convergence of an empirical regression method for solving generalized backward stochastic differential equations[END_REF]) of BSDEs. In this section, we start by briefly introducing the needed notations then explain the new modified version of our algorithm on the generic example defined in (f ). We finally apply the new modified version to a RBSDE without a Z term.

Starting with notations, we introduce S = {t 0 , ..., t 2 L } = {0, ∆ t , 2∆ t , ..., T } as a fine discretization set and S ⊂ S as a coarser one with ∆ t = T /2 L . We then simulate the outer trajectories (X m 0

• ) m 0 =1,...,M 0 as well as the inner ones (X m 0 ,m 1 s j ,•

) m 0 =1,...,M 0 ,m 1 =1,...,M 1 s j ∈S that start at the top of each realization X m 0 s j with s j ∈ S. Given the Borel-measurable functions

(E t k ) k=0,...,2 L -1 : R d 1 +d 2 → R d 1 , we define X m 0 t k = E t k-1 (X m 0 t k-1 , ξ m 0 t k ), when k ≥ 1 and X m 0 t 0 = x 0 , (2.1)
X m 0 ,m 1 s j ,t k = E t k-1 (X m 0 ,m 1 s j ,t k-1 , ξ m 0 ,m 1 s j ,t k ) and X m 0 ,m 1 s j ,s j m 1 =1,...,M 1 +M 1 = X m 0 s j . (2.2)
Since we focus essentially on the diffusion case, the functions (E t k ) k=0,...,2 L -1 can be obtained with a discretization scheme to get for instance

E t k (x, ξ) = x + ∆ t b(t k , x) + σ(t k , x)ξ (2.3)
with the usual (cf. [START_REF] Pagès | Numerical probability: an introduction with applications to finance[END_REF]) Lipschitz continuity condition on the coefficients b(t, x) and σ(t, x) uniformly with respect to t ∈ [0, T ]. Introducing outer W m 0 and inner

W m 0 ,m 1 realizations of an R d 2 -Brownian motion W , we define ξ m 0 t k = W m 0 t k -W m 0 t k-1 and ξ m 0 ,m 1 s j ,t k = W m 0 ,m 1 s j ,t k -W m 0 ,m 1 s j ,t k-1 where W 1 , ..., W M 0 are independent with W m 0 ,m 1 s j ,t k = W m 0 ,m 1 s j ,t k-1 + ∆W m 0 ,m 1 s j ,t k and W m 0 ,m 1 s j ,s j m 1 =1,...,M 1 +M 1 = W m 0 s j and (∆W m 0 ,m 1 s j ,t k ) (m 0 ,m 1 )∈{1,...,M 0 }×{1,...,M 1 +M 1 } k∈{j,...,2 L },j∈{1,...,2 L } are independent Brownian motion increments independent from W 1 , ..., W M 0 with E([∆W m 0 ,m 1 s j ,t k ] 2 ) = ∆ t . The resulting components of the vector (ξ m 0 ,m 1 t j ,t k ) (m 0 ,m 1 )∈{1,...,M 0 }×{1,...,M 1 +M 1 } k∈{j,...,2 L },j∈{1,...,2 L } , (ξ m 0 t k ) m 0 =1,...,M 0 k=1,...,2 L
are independent realizations with the same normal distribution.

We use

X m 0 ,m 1 ,1 •,• , ..., X m 0 ,m 1 ,d 1 •,• to denote the d 1 components of X m 0 ,m 1 •,•
and use the notation X m 0 ,m 1 s j ,s l :s k for (X m 0 ,m 1 s j ,s l , X m 0 ,m 1 s j ,s l +∆t , ..., X m 0 ,m 1 s j ,s k -∆t , X m 0 ,m 1 s j ,s k ) for s j , s k ∈ S with s j < s k . We remind also the notation of the stabilized regression basis T m 0 t j ,t k ,M 1 defined in CMCLDI (cf. [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF]) for any couple t j < t k from the fine discretization grid. The cardinal of the basis

T m 0 •,•,M 1 is equal to d 1 with d 1 ≤ d 1 . T m 0 •,•,M 1
is also indexed by the number M 1 of trajectories needed for the approximation of regression matrices and that are independent from those used in the backward induction. We also reduce any superfluous dependence structure as well as the memory occupation by re-simulating on the fly each realization that has not to be constantly stored. For example, if an inner trajectory is needed α times in the backward induction, we simulate α independent copies of it and use each copy once.

Finally, introducing ∧ and ∨ notations for

x ∧ y = min(x, y) and x ∨ y = max(x, y),

we remind the definition of the time operator δ S that associates to each s ∈ S the next increment in S. For a fixed index j ∈ {1, ..., 2 L }, we define δ S s j (•) on (s k ) k≤j , taken its values in S ∩ [s j , s j ], by

δ S s j (s k ) = s j ∧ min{s ∈ S; s k < s ≤ s j } (2.4)
with min(∅) = ∞ and the couple (s j , s j ) sets the minimal and the maximal time increment of the performed regressions conditionally on the realization X m 0 s j of the Markov process X. The couple (s, s), mainly s, sets the learning depth conditional to the information available at time s. Given a coarse discretization set S, definitions 2.1 and 2.2 express the value of (s, s) s∈S .

When S is fixed, the notation δ S s j can be replaced by δ s j . When s k < s j , the notation δ S s j can be replaced by δ S . When S is fixed and s k < s j , we can simplify both indices and use δ instead of δ S s j . Given a coarse discretization set S, the operator δ has the following properties Pr1. s j = δ s j (s j ) = δ(s j ).

Pr2. As long as

s j 1 ∨ s j 2 ≤ s k < s j 1 ∧ s j 2 , δ s j 1 (s k ) = δ s j 2 (s k ) = δ(s k ).
Pr3. The nth composition of δ s j denoted δ n s j (•) is equal to s j when n ≥ |S∩]s j , s j ]| where | • | denotes the cardinal.

Variance adjustment modification on the generic example

When applied for the simulation of U defined by (f ), the proposed learning procedure associates to each scenario m 0 and to each discretization set S a couple of function families ( u m 0 ,S , u m 0 ,S ). Given s j < s k ≤ s k increments from S, equations (1.2), (1.3) and (1.4) parametrizes the definition of u m 0 ,S with respect to the variance adjustment parameter γ m 0 ,S s j ,s k . Thus, we generalize the definition of u m 0 ,S introduced in CMCLDI (cf. [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF]) which is obtained straightforwardly if we take γ m 0 ,S s j ,s k = 1. Regarding the regression vector B m 0 ,S s j ,s k used in (1.3), its value is obtained from an estimation of the vector a ∈ R d 1 that minimizes the quadratic error given by

E B m 0 ,S,δs j (s k ) s j ,s k (X m 0 ,m 1 s j ,s k :δs j (s k ) ) -t aT m 0 s j ,s k ,M 1 (X m 0 ,m 1 s j ,s k ) 2 (2.5)
with X m 0 ,m 1 s j ,s k :δs j (s k ) = X m 0 ,m 1 s j ,s k , X m 0 ,m 1 s j ,s k +∆t , ..., X m 0 ,m 1 s j ,δs j (s k )-∆t , X m 0 ,m 1 s j ,δs j (s k ) and

B m 0 ,S,δs j (s k ) s j ,s k (x) = u m 0 ,S s j ,δs j (s k ) xδ s j (s k )-s k ∆ t -u m 0 ,S s k ,s k + δs j (s k )-s k ∆ t -1 l=1 f (t ks k +l , x l , x l+1 ) (2.6)
where k s k = s k /∆ t -1, x = (x 1 , ..., x (δs j (s k )-s k )/∆t ) with each coordinate of x belonging to

R d 1 .
We keep however the same definition of u m 0 ,S given in CMCLDI (cf. [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF]) which is reminded hereafter. For s j < s k < s j and s ∈ {s k , s k + ∆ t , ..., δ(s k ) -∆ t }, the fine approximation at X m 0 s is defined by

u m 0 ,S s,s k = 1 M 1 M 1 m 1 =1   u m 0 ,S s k ,δ(s k ) (X m 0 ,m 1 s,δ(s k ) ) + δ(s k ) t l+1 >s f (t l , X m 0 ,m 1 s,t l , X m 0 ,m 1 s,t l+1 )   . (2.7)
To complete this inductive interconnected backward definition of u and u, we set the final coarse approximation to

u m 0 ,S s j ,s j (x) = f (T, x) if s j = T,
u m 0 ,S s j ,s j (x) = u m 0 ,S δ(s j ),s j (x) if s j < T.

(2.8)

For s j ∈ S, s j and s j , expressed in Definition 2.1, are really needed when T is sufficiently big or the variance produced by X is large enough. Otherwise, (2.8) can be replaced by When s k = δ s j (s j ) and u m 0 ,S s j ,s k = u m 0 ,S s k ,s k (when γ m 0 ,S s j ,s k = 1), one can check the coherence of the previous definitions aimed to approximate U defined in (f ). Indeed, (2.7) would provide for any s ∈ {s j , s j + ∆ t , ..., δ(s j ) -

u m 0 ,S s j ,T (x) = f (t 2 L , x) = f (T, x).
s k = δ s j (s j ), δ 2 (s j ) = δ(s k ) = s j = t 2 L = T , u m 0 ,S s j ,s k = u m 0 ,S s k ,
∆ t } = {s j , s j + ∆ t , ..., s k -∆ t } u m 0 ,S s,s j = 1 M 1 M 1 m 1 =1   u m 0 ,S s j ,s k (X m 0 ,m 1 s,s k ) + s k t l+1 >s f (t l , X m 0 ,m 1 s,t l , X m 0 ,m 1 s,t l+1 )   (2.9)
where the term u m 0 ,S s j ,s k , defined in (1.2), is obtained through the projection of the sum

δ(s k ) t l+1 >s k f (t l , X m 0 ,m 1 s j ,t l , X m 0 ,m 1 s j ,t l+1 ) + u m 0 ,S s j ,δ(s k ) (X m 0 ,m 1 s j ,δ(s k ) ) on T m 0 s j ,s k ,M 1 (X m 0 ,m 1 s j ,s k ).
In addition, if we had δ 2 (s j ) = δ(s k ) = s j = t 2 L = T then (2.8) would make u m 0 ,S s j ,δ(s k ) (•) = f (t 2 L , •) and as s ∈ {s j , s j + ∆ t , ..., s k -∆ t } the definition of u m 0 ,S s,s j would involve

s k t l+1 >s f (t l , X m 0 ,m 1 s,t l , X m 0 ,m 1 s,t l+1 )
plus the projection of

t 2 L t l+1 >s k f (t l , X m 0 ,m 1 s j ,t l , X m 0 ,m 1 s j ,t l+1 ) + f (T, X m 0 ,m 1 s j ,T
) as shown on Figure 1.

u m 0 ,S s k ,s k is equal to 1 M 1 M 1 m 1 =1   t 2 L t l+1 >s k f (t l , X m 0 ,m 1 s k ,t l , X m 0 ,m 1 s k ,t l+1 ) + f (T, X m 0 ,m 1 s k ,T )   as δ(s k ) = T .
Once we replaced (1.1) by (1.2), Definition 2.1 hereafter is similar to Definition 3.1 presented in CMCLDI.

Definition 2.1. Given a discretization set S ⊂ S • For any s ∈ S, s is set to be equal to δ(s) and s is set backwardly to be the largest discretization time u ∈ S∩]s, δ(s)] that satisfies

1 M 0 M 0 m 0 =1   u m 0 ,S s,u -u m 0 ,S δ(s),δ(s) - δ(s) t l+1 >s f (t l , X m 0 t l , X m 0 t l+1 )   < S s (2.10)
where { S s } s∈S is a family of positive bias tuning parameters.

• For k < j ∈ {1, ..., 2 L } that satisfy s j < s k ≤ s j < t 2 L = T , the simulation U m 0 ,m 1 s j ,s k of U around X m 0 s k conditionally on X m 0 s j is set to be equal to u m 0 ,S s j ,s k (X m 0 ,m 1 s j ,s k ) where u is given in (1.2) and (2.8). • For k ∈ {1, ..., 2 L } and s ∈ {s k , s k + ∆ t , ..., δ(s k ) -∆ t } -{0}, the simulation U m 0 s of U at X m 0 s is set to be equal to u m 0 ,S s,s k with u expressed in (2.7). • The average U lear 0 of learned values on U 0 is equal to U lear 0 = 1 M 0 M 0 m 0 =1 u m 0 ,S 0,0 (2.11)
and the simulated value U sim 0 of U 0 is equal to

U sim 0 = 1 M 0 M 0 m 0 =1   u m 0 ,S δ(0),δ(0) + δ(0) t l+1 >0 f (t l , X m 0 t l , X m 0 t l+1 )   (2.12)
with u expressed in (2.7).

In contrast to the inner layer approximation U m 0 ,m 1 which is only defined on S, the outer layer approximation U m 0 is defined on the whole fine discretization set S. At t = 0, inner and outer trajectories coincide and yield U lear 0 and U sim 0 as two possible approximations of U 0 . The value of s depends on δ(s) whose value involves the one of δ 2 (s) and so on till T . In Section 3.1, we provide an example of how to update iteratively (s, s) s∈S with respect to the discretization set S.

It is remarkable that the term on the left of inequality (2.10) makes possible the estimation of the average bias. In Section 3.2, we introduce a local bias estimation that allows a more stringent bias control. None of these bias estimations is possible without the double layer structure of NMC1. The choice of the tuning parameters { S s } s∈S reflects a compromise between the targetted accuracy and the required complexity. This choice has to take into account the standard deviation of the estimator

1 M 0 M 0 m 0 =1 u m 0 ,S s,u -u m 0 ,S δ(s),δ(s) -δ(s) t l+1 >s f (t l , X m 0 t l , X m 0 t l+1 ) .

Application on RBSDEs with a Markov forward process

The variance adjustment trick introduced in this paper was not needed for the BSDE examples studied in CMCLDI. However, when the considered example requires a better description of the tail distribution, the choice γ m 0 ,S

•,• = 1 becomes insufficient. Here, we consider an application to RBSDEs like the one presented in [START_REF] Bouchard | Discrete time approximation and Monte Carlo simulation of backward stochastic differential equations[END_REF] with the final condition function g(•) and the driver {f (t k , •)} 2 L -1 k=0 assumed to be L-Lipschitz. We want to propose a double layer approximation V m 0 and V m 0 ,m 1 of the Snell envelope V , solution to

(Snl) V T = g(X T ) and for k < 2 L : V t k = g(X t k )∨E t k [V t k+1 +∆ t f (t k , V t k+1 )],
that can be done using straightforwardly the recipe of Section 2.1 combined with a maximization by g. We introduce the coarse w m 0 ,S and the fine w m 0 ,S approximations of the process V defined by

V t k = E t k [V t k+1 +∆ t f (t k , V t k+1 )].
(2.13)

Then, given a discretization set S and indices k < j ∈ {1, ..., 2 L } that satisfy s j < s k < s j and using δ s j (s k ) defined in (2.4), we set the coarse approximation

v s j ,s k around X m 0 s k conditionally on X m 0 s j to v m 0 ,S s j ,s k (x) = w m 0 ,S s j ,s k (x) ∨ g(x), (2.14)
and the fine approximation

v s,s k at X m 0 s , s ∈ {s k , s k + ∆ t , ..., δ s j (s k ) -∆ t }, to v m 0 ,S s,s k = w m 0 ,S s,s k ∨ g(X m 0 s ). (2.15) Denoting ∆ s = δ s j (s k ) -s and ∆ s k = δ s j (s k ) -s k , we define w m 0 ,S s,s k = 1 M 1 M 1 m 1 =1 ∆ s f (s k , v m 0 ,S s k ,δs j (s k ) (X m 0 ,m 1 s,δs j (s k ) )) + v m 0 ,S s k ,δs j (s k ) (X m 0 ,m 1 s,δs j (s k ) ) , (2.16)
w m 0 ,S s j ,s k (x) = w m 0 ,S s j ,s k + t T m 0 s j ,s k ,M 1 (x) C m 0 ,S s j ,s k , (2.17)
where

w m 0 ,S s j ,s k = w m 0 ,S s k ,s k + (1 -γ m 0 ,S s j ,s k ) M 1 M 1 m 1 =1 t T m 0 s j ,s k ,M 1 (X m 0 ,m 1 s j ,s k )C m 0 ,S s j ,s k , (2.18)
C m 0 ,S s j ,s k = γ m 0 ,S s j ,s k C m 0 ,S s j ,s k with C m 0 ,S s j ,s k = ( Λ m 0 s j ,s k ,M 1 ) -1 M 1 M 1 m 1 =1 C m 0 ,S,δs j (s k ) s j ,s k ,M 1 (X m 0 ,m 1 s j ,s k , X m 0 ,m 1 s j ,δs j (s k ) )
and

C m 0 ,S,δs j (s k ) s j ,s k ,M 1 (x , x) = T m 0 s j ,s k ,M 1 (x )C m 0 ,S,δs j (s k ) s j ,s k (x) with C m 0 ,S,δs j (s k ) s j ,s k (x) =   ∆ s k f (s k , v m 0 ,S s j ,δs j (s k ) (x)) + v m 0 ,S s j ,δs j (s k ) (x) -w m 0 ,S s k ,s k   , (2.19)
with a final coarse approximation given by

v m 0 ,S s j ,s j (x) = g(x) if s j = t 2 L , v m 0 ,S s j ,s j (x) = v m 0 ,S δs j (s j ),s j (x) if s j < t 2 L .
(2.20)

Definition 2.2. Given a discretization set S ⊂ S • For any s ∈ S, s is set to be equal to δ(s) and s is set backwardly to be the largest discretization time u ∈ S∩]s, δ(s)] that satisfies

1 M 0 M 0 m 0 =1 w m 0 ,S s,u -v m 0 ,S δ(s),δ(s) -(δ(s) -s)f (s, v m 0 ,S δ(s),δ(s) ) < S s (2.21)
where { S s } s∈S is a family of positive bias tuning parameters.

• For k < j ∈ {1, ..., 2 L } that satisfy s j < s k ≤ s j < t 2 L = T , the simulation V m 0 ,m 1 s j ,s k of V around X m 0 s k conditionally on X m 0 s j is set to be equal to v m 0 ,S s j ,s k (X m 0 ,m 1 s j ,s k )
where v is given in (2.14), (2.17) and (2.20). [START_REF] Giorgi | Weak Error for Nested Multilevel Monte Carlo[END_REF]) and (2.16).

• For k ∈ {1, ..., 2 L } and s ∈ {s k , s k + ∆ t , ..., δ(s k ) -∆ t } -{0}, the simulation V m 0 s of V at X m 0 s is set to be equal to v m 0 ,S s,s k with v expressed in (2.
• The average V lear 0 of the learned values on V 0 is equal to

V lear 0 = 1 M 0 M 0 m 0 =1 v m 0 ,S 0,0 , (2.22)
and the simulated value

V sim 0 of V 0 is equal to V sim 0 = g(x 0 ) ∨ 1 M 0 M 0 m 0 =1 δ(0)f δ(0), v m 0 ,S δ(0),δ(0) + v m 0 ,S δ(0),δ(0) . (2.23)
Similar to Definition 2.1, the inner layer approximation V m 0 ,m 1 is only defined on S when the outer layer approximation V m 0 is defined on the whole fine discretization set S. At t = 0, inner and outer trajectories coincide and yield V lear 0 and V sim 0 as two possible approximations of V 0 . Similar also to Definition 2.1, it is remarkable that the term on the left of inequality (2.21) makes possible the estimation of the average bias.

Although using an optimal stopping formulation [START_REF] Clément | An analysis of a least squares regression algorithm for American option pricing[END_REF] of the dynamic programming is known to provide better numerical results [START_REF] Longstaff | Valuing American options by simulation: A simple least-squares approach[END_REF], we prefered here to use 1NMC on the top of the original algorithm [START_REF] Tsitsiklis | Regression methods for pricing complex American-style options[END_REF] since its error estimates remains similar to the one presented for BSDEs. As a future work, we would like to apply variance reduction methods with 1NMC and provide very accurate double layer estimations of the optimal stopping strategy.

3 Learning the values of S and γ m 0 ,S s j ,s k m 0 =1,...,M 0 s j ∈S,s k ∈S∩]s j ,s j ] Till now, the proposed learning methodology introduced M 0 , M 1 , M 1 , S, S

• and γ •,S •,• as hyperparameters. In a Monte Carlo simulation, the standard and efficient way to know what is the appropriate number of trajectories that have to be simulated is through the estimated confidence interval. The same can be done for the number of outer and inner trajectories in 1NMC. We only draw attention to the number of trajectories M 1 and M 1 that have to be sufficient given the number of terms d 1 in T m 0 •,•,M 1 used for the regression.

We refer the reader to [START_REF] Newey | Convergence rates and asymptotic normality for series estimators[END_REF] for asymptotic relations between the size of the projection basis and the number of needed realizations. Consequently, the choice of M 0 , M 1 and M 1 have to be specific to each application and set during the numerical simulation. The same can be said for the tuning parameter S

• as its value should be proportional to 1/ √ M 0 . Indeed, from the left term in inequalities (2.10) and (2.21), the user has to make a numerical compromise between accuracy and complexity when picking the value of S • . In this section, we want to relieve the use of S and of γ •,S

•,• as hyperparameters. We start by specifying iteratively the coarse discretization set S. At each iteration, we show also how to update the couple (s, s) for any s ∈ S. The iterative choice of S and of (s, s) s∈S is made to keep the bias under control and thus to conserve the first moment of simulations. Moreover, we detail how to conserve the second moment of simulations using an appropriate value for the variance adjustment parameter γ •,S

•,• . The latter choice is further refined when the number M 0 of simulated outer trajectories makes possible a local variance adjustment.

The iterative construction of S and (s, s) s∈S presented in Section 3.1 as well as the expression of γ •,S

•,• presented in Section 3.2 are only given as an example and thus are not restrictive.

An example of iterative definition of S and update of (s, s) s∈S

Like definitions 3.1 and 3.2 in CMCLDI, definitions 2.1 and 2.2 in Section 2 are intentionally announced without specifying the coarse discretization set S. Indeed, the presented methodology can be applied for any S. It is then possible to use it for an iterative family {S i } i=0,...,L-L where L is an integer chosen in this section ∈]L/2, L]. When i increases the coarse discretization gets finer in the sense of inclusion S 0 ⊆ S 1 ⊆ ... ⊆ S L-L .

For i = 0, ..., L -L , we define the set S i through the values taken by the decreasing sequence (T -s i j ) j=0,...,2 L . When i = 0, (s 0 j ) j=0,...,2 L is a homogeneously distributed sequence where each term is repeated 2 L-L times as follows

s 0 j = j2 L 2 L T 2 L where • is the ceiling function. ( 3.1)
that yields S 0 = {0, T /2 L , ..., (2 L -1)T /2 L , T }. The value of s i 0 stays the same for any iteration and is then given by s i 0 i=1,...,L-L = 0.

To define (s i j ) j=1,...,2 L for i = 1, ..., L -L , we introduce a scale Q i and a translation q i parameters. Since we want to keep each S i as coarse as possible, the translation parameter q i sets the starting index from which we should refine the discretization. q 0 = 0 and q i is given by

q i = q i-1 ∨ max j ∈ {q i-1 + 1, ..., 2 L }; K i-1 j (3.2)
where the condition K i-1 j has to be specific to each application. Expression (3.2) ensures an increasing translation parameter q i with respect to the iteration index i. The scale parameter Q i = 2 L-L -i is used to know the number of terms that should be equal to each other. Thus, for indices bigger than q i , when the iteration index i increases Q i = 2 L-L -i decreases and the discretization becomes finer.

For i = 1, ..., L -L , we choose the following induction

s i j = s i-1 j 1 j≤q i + ŝi-1 j 1 j>q i , (3.3)
where the values of (ŝ i-1 j ) j=0,...,2 L are given by      when j ≤ q i-1 define ŝi-1

j = s i-1 j otherwise, for j > q i-1 /Q i set ŝi j Q i j j=Q i (j -1)+1 = s i-1 Q i j + s i-1 Q i (j -1)
2 .

(3.4)

The notation s i j

Q i j j=Q i (j -1)+1
is used for s i Q i (j -1)+1 , ..., s i Q i j . Similar to S i defined through (T -s i j ) j=0,...,2 L , we introduce S i to be the set of values taken by (T -ŝi j ) j=0,...,2 L . From (3.4), one can easily see that S i ⊆ S i and thus for any s ∈ S i we have the inequality

δ S i (s) ≤ δ S i (s).
(3.5)

In Figure 2, we illustrate how this discretization strategy is implemented when L > L/2. As shown on Figure 2, because S i is the set of the values taken by (T -s i j ) j=0,...,2 L , the increment δ(s) -s decreases as the value of the increment s ∈ S i decreases. To counterbalance a rapid decrease of the time increment δ(s) -s when s gets smaller, the condition K i-1 j in (3.2) has to take into account the accumulation of bias through backpropagation. The value of K i j given in Definition 3.1 allows then to increase the discretization steps only when the estimated gained accuracy is larger than the maximum accumulation of bias. Definition 3.2 provides an updating strategy for (s j , s j ) (s j ) j=0,...,2 L ∈S i associated to the iterative construction of S i given in Definition 3.1. We will use the notation (s j (s i j ), s j (s i j )) to show an explicit dependence of the updating strategy on the sequence (s i j ) j=0,...,2 L involved in the definition of S i . Definition 3.1. Given an iteration step i = 0, ..., L -L -1 for which the values of (s i j ) j=0,...,2 L , S i , S i , { S i s } s∈S i and q i are known, given j ∈ {q i + 1, ..., 2 L } we define the condition

K i j ="e S i s < ε S i s for s ∈ (T -s i k ) q i +1≤k≤j " where for s ∈ (T -s i k ) q i +1≤k≤j we have δ S i (s) = δ S i (δ S i (s)
) and the definition of the couple (e S i s , ε S i s ) is specified for the simulation of (f ) by

e S i s = 1 M 0 M 1 M 0 m 0 =1 M 1 m 1 =1 u m 0 , S i δ S i (s),δ S i (s) (X m 0 ,m 1 δ S i (s),δ S i (s) ) -u m 0 ,S i s,δ S i (s) (X m 0 ,m 1 δ S i (s),δ S i (s) ) , ε S i s = u∈S i ∩]s,s] S i u
and specified for the simulation of (Snl) by

e S i s = 1 M 0 M 1 M 0 m 0 =1 M 1 m 1 =1 w m 0 , S i δ S i (s),δ S i (s) (X m 0 ,m 1 δ S i (s),δ S i (s) ) -w m 0 ,S i s,δ S i (s) (X m 0 ,m 1 δ S i (s),δ S i (s) ) , ε S i s = u∈S i ∩]s,s] L |S i ∩]s,u]| S i u with |S i ∩]s, u]| denotes the cardinal of the finite set S i ∩]s, u].
The bias backpropagation of simulation (f ) is linear when the one associated to simulation (Snl) is not. Thus, the definition of the maximum bias accumulation ε S i s associated to (Snl) involves a sum on the Lipschitz constant L to the power of lag index, given here by |S i ∩]s, u]|, multiplied by the maximal accepted bias S i u per increment u ∈ S i ∩]s, s]. e S i is defined as the average difference between the estimation u m 0 ,S i (resp. w m 0 ,S i ) that involves the discretization set S i and the estimation u m 0 , S i (resp. w m 0 , S i ) that involves a finer discretization set S i . Using actualization (3.3) given (3.2) and K i j expressed in Definition 3.1, we basically make the discretization set finer only when the difference between approximations is superior to the maximal accumulation of bias ε S i . Definition 3.2. Given an iteration step i = 1, ..., L-L for which the values of (s i j ) j=0,...,2 L , (s i-1 j ) j=0,...,2 L , S i and q i are known, introducing we set s j (s i j ) = δ S i (T -s i j ) and s j (s i j ) = s j (s i-1 j ) ∧ max(S i,(f ) T -s i j ) for the simulation of (f ) or s j (s i j ) = s j (s i-1 j ) ∧ max(S i,(Snl) T -s i j ) for the simulation of (Snl). As illustrated on Figure 3 and on Figure 4, the value of s j (s i j ) given in Definition 3.2 can change depending on s j (s i-1 j ) > max(S i,(•) T -s i j ) is true or not. Indeed, since S i is finer than S i-1 , the bias backpropagation associated to S i can be larger than the one associated to S i-1 and thus max(S i,(•) T -s i j ) can happen to be significantly smaller than s j (s i-1 j ).

S i,(f ) s = {u ∈ S i ∩]s, δ S i (s)] that satisfies (2.

From global to local bias control and variance adjustment 3.2.1 Local bias control

Given s ∈ S, the couple (s, s) was expressed in Definition 2.1 as well as in Definition 2.2 and an updating strategy for (s, s) was established in Definition 3.2 when S is constructed iteratively. In order to reduce the bias backpropagation, these definitions used the double layer Monte Carlo to control the average bias. Indeed, as 1

M 0 M 0 m 0 =1 u m 0 ,S s,u and 1 M 0 M 0 m 0 =1 u m 0 ,S δ(s),δ(s) + δ(s) t l+1 >s f (t l , X m 0 t l , X m 0 t l+1 ) are both approximations of the same expectation E(U s ) = E U δ(s) + δ(s) t l+1 >s f (t l , X m 0 t l , X m 0 t l+1 )
, it is natural to have them almost equal. The same can be said for 1

M 0 M 0 m 0 =1 v m 0 ,S δ(s),δ(s) + (δ(s) -s)f (s, v m 0 ,S δ(s),δ(s) ) and for 1 M 0 M 0 m 0 =1 w m 0 ,S s,u that are both approximations of E V δ(s) + (δ(s) -s)f (s, V δ(s) ) = E E s V δ(s) + (δ(s) -s)f (s, V δ(s) )
. For large values of M 0 , the difference between these approximations is due to bias. A judicious method to reduce this bias backpropagation is to adjust the number of successive regressions through the appropriate choice of u involved in 1

M 0 M 0 m 0 =1 u m 0 ,S s,u
and in 1 M 0 M 0 m 0 =1 w m 0 ,S s,u . In definitions 2.1 and 2.2, we select s as the largest value of u for which the bias remains under some threshold. This choice of s, with s = δ(s), sets the learning depth conditional to the information available at s ∈ S.

The choice of (s) s∈S ought to decrease the global average value of the bias. More local approach can be developed using equalities

E U s 1 {Us∈[a,b]} = E   1 {Us∈[a,b]}   U δ(s) + δ(s) t l+1 >s f (t l , X m 0 t l , X m 0 t l+1 )     (3.6) E V δ(s) +(δ(s) -s)f (s, V δ(s) ) 1 {Vs∈[a,b]} = E 1 {Vs∈[a,b]} E s V δ(s) +(δ(s) -s)f (s, V δ(s) ) (3.7)
which are true for any localizing interval [a, b]. Considering the generic example (f ) with equality (3.6), when M 0 is large enough, one can sort { u m 0 ,S s,u } m 0 ≤M 0 and define a subdivision of localizing intervals {[a q , a q+1 ]} q≥1 then choose u = s that does not induce a large difference between 1

M 0 M 0 m 0 =1 1 { u m 0 ,S s,s ∈[aq,a q+1 ]} u m 0 ,S δ(s),δ(s) + δ(s) t l+1 >s f (t l , X m 0 t l , X m 0 t l+1 ) and 1 M 0 M 0 m 0 =1 u m 0 ,S s,s 1 { u m 0 ,S s,s
∈[aq,a q+1 ]} for all qs. The local increase of bias can be tracked for any s ∈ S ∩ [δ(s), s[ and each interval [a q , a q+1 ] using the difference

1 M 0 M 0 m 0 =1 1 { u m 0 ,S s,s ∈[aq,a q+1 ]}   u m 0 ,S s,s -u m 0 ,S δ(s),δ(s) - δ(s) t l+1 >s f (t l , X m 0 t l , X m 0 t l+1 )   . (3.8)
The same can be done for (Snl) with equality (3.7). Although the local tracking of bias was not necessary in our simulations, it is quite remarkable to point out the strength of bias control induced by 1NMC. Provided that M 0 is sufficiently large, it is basically possible to remove any bias backpropagation.

From global to local value of

γ m 0 ,S s j ,s k m 0 =1,...,M 0 s j ∈S,s k ∈S∩]s j ,s j ]
Given s j ∈ S and s k ∈ S∩]s j , s j ], various values can be considered for γ m 0 ,S s j ,s k . The straight choice is to take γ m 0 ,S s j ,s k = 1 which reduces the procedure to a standard regression like in CMCLDI. However, this is not the suitable choice for problems that heavily depend on tail distribution. Indeed, given two arbitrary square integrable random variables χ 1 and χ 2 , consider χ 3 to be the regression of χ 1 on a σ(χ 2 )-measurable basis. Because generally regression preserves the mean value, it is reasonable to assume E(χ 3 ) = E(χ 1 ). However, projections reduce the value of the second moment i.e. E(χ 2

3 ) < E(χ 2 1 ) and thus Var(χ 3 ) < Var(χ 1 ). The latter fact becomes a real problem for tail distribution in case Var(χ 3 ) < Var(E(χ 1 |χ 2 )). Some contributions tackle rare event simulation using a change of probability trick [START_REF] Bucklew | Introduction to rare event simulation[END_REF][START_REF] Glasserman | Monte Carlo methods in financial engineering[END_REF] and more recent contribution [START_REF] Agarwal | Study of new rare event simulation schemes and their application to extreme scenario generation[END_REF] implements reversible shaking transformations.

In case E(χ 3 ) = E(χ 1 ) = 0, given that we know a good approximation of Var(E(χ 1 |χ 2 )), it is possible to adjust the projected value χ 3 with a parametter γ to make Var(γχ 3 ) ≈ Var(E(χ 1 |χ 2 )). Thus, γχ 3 has the appropriate variance for the price of a slight increase of the quadratic error since

E [χ 1 -γχ 3 ] 2 = E [χ 1 -χ 3 ] 2 + (1 -γ) 2 γ 2 E [E(χ 1 |χ 2 )] 2 then E ([χ 1 -γχ 3 ] 2 ) ≈ E ([χ 1 -χ 3 ] 2
) provided that γ is slightly bigger than 1. This basic idea is adapted hereafter to adjust the variance of the coarse estimators u m 0 ,S and w m 0 ,S . Using the global and local bias control presented above, we established strong constraints to make u m 0 ,S and v m 0 ,S almost unbiased estimators of U and V respectively given in (f ) and (Snl). It is then possible to use their values to propose an appropriate adjustment of the variance. For s j < s with s = s k , δ(s k ), the whole idea is based on the following equality

E Var s j (Θ s ) = E E s j Θ s -E s j (Θ s ) 2 = E Θ s -E s j (Θ s ) 2
true for any square integrable process Θ and thus when Θ = U or when Θ = V with U defined in (f ) and V defined in (2.13).

For Θ = U, V we associate θ m 0 ,S = u m 0 ,S , w m 0 ,S respectively as fine approximations and θ m 0 ,S = u m 0 ,S , w m 0 ,S respectively as coarse ones. We also set H m 0 ,S = B m 0 ,S , C m 0 ,S which are subsequently the regression vector associated to either u m 0 ,S or w m 0 ,S . To define

m 0 ,S s j ,s (X m 0 ,m 1 s j ,s ) 2 . (3.11)
Because expressions (3.10) and (3.11) are the estimators of E s j Θ s -E s j (Θ s ) 2 and of

E Θ s -E s j (Θ s )
2 respectively, it is natural to have asymptotically (as M 1 → ∞ and

M 0 → ∞) the equality (σ S 0,s j ,s [θ]) 2 = 1 M 0 M 0 m 0 =1 (σ m 0 ,S s j ,s [θ]) 2 (3.12)
for both s = s k , δ(s k ). For θ = u, w, the estimators 1

M 1 M 1 m 1 =1 θ m 0 ,S s j ,s (X m 0 ,m 1 s j ,s
) and θ m 0 ,S s,s have negligible bias. Thus, we can reasonably assume inductively that (3.12) is true for s = δ(s k ). Afterwards, we choose the appropriate value of γ m 0 ,S s j ,s k that makes σ m 0 ,S s j ,s k satisfy (3.12) for s = s k . We have then the following definition. Definition 3.3. For a discretization set S ⊂ S, s j ∈ S, s k ∈ S∩]s j , s j ], θ = u, w and H m 0 ,S = B m 0 ,S , C m 0 ,S assuming by backward induction that γ m 0 ,S s j ,s is known for all s = s j , ..., δ(s k ) and given a positive tuning value < 1/3, we set then

γ m 0 ,S s j ,s k = σ m 0 ,S s j ,δ(s k ) [θ] σ m 0 ,S s j ,s k [θ, H] s k -s j δ(s k ) -s j 1 δ(s k )-s j < + σ S 0,s j ,s k [θ] σ S 0,s j ,δ(s k ) [θ] 1 δ(s k )-s j ≥ . (3.13)
According to (3.13), when δ(s k ) -s j is small and a fortiori s k -s j is small then the conditional variance (σ m 0 ,S s j ,s k [θ]) 2 has to be linear with respect to time increment s k -s j . This fact can be justified for diffusions using first order Taylor expansion of φ(t, β t ) around φ(t, 0), for a standard Brownian motion β and a smooth function φ. Also according to (3.13), when δ(s k ) -s j becomes sufficiently big, the conditional variance (σ m 0 ,S s j ,s k [θ]) 2 has the same average decreasing ratio

σ S 0,s j ,s k [θ] σ S 0,s j ,δ(s k ) [θ] 2 with respect to (σ m 0 ,S s j ,δ(s k ) [θ]) 2 .
Although Definition 3.3 works well in our simulations, it can be turned into a more local variance adjustment. In fact, similar to what was proposed for the bias control in (3.6) and (3.7), for s j < s with s = s k , δ(s k ), the equality

E Var s j (Θ s )1 {Vars j (Θ δ(s k ) )∈[a,b]} = E 1 {Vars j (Θ δ(s k ) )∈[a,b]} Θ s -E s j (Θ s ) 2
is true for any localizing interval [a, b]. When M 0 is sufficiently large, one can sort {(σ m 0 ,S s j ,δ(s k ) [θ]) 2 } 1≤m 0 ≤M 0 to define a family of localizing intervals {[a q , a q+1 ]} q≥1 and set

(σ S,q 0,s j ,s [θ]) 2 = 1 M 0 M 0 m 0 =1 1 {(σ m 0 ,S s j ,δ(s k ) ) 2 ∈[aq,a q+1 ]} θ m 0 ,S s,s - 1 M 1 M 1 m 1 =1 θ m 0 ,S s j ,s (X m 0 ,m 1 s j ,s ) 2 .
Condition (3.12) can be then replaced by its localized version

(σ S,q 0,s j ,s [θ]) 2 = 1 M 0 M 0 m 0 =1 1 {(σ m 0 ,S s j ,δ(s k ) [θ]) 2 ∈[aq,a q+1 ]} (σ m 0 ,S s j ,s [θ]) 2 . (3.14)
If σ m 0 ,S s j ,δ(s k ) [θ] ∈ [a q 0 , a q 0 +1 ], for some q 0 , then it makes sense to replace (3.13) by

γ m 0 ,S s j ,s k = σ m 0 ,S s j ,δ(s k ) [θ] σ m 0 ,S s j ,s k [θ, H] s k -s j δ(s k ) -s j 1 δ(s k )-s j < + σ S,q 0 0,s j ,s k [θ] σ S,q 0 0,s j ,δ(s k ) [θ] 1 δ(s k )-s j ≥ . (3.15)
The local variance adjustment (3.15) was not necessary in our simulations. Nevertheless, it is quite remarkable to point out the high flexibility of the multilayer setting induced by 1NMC. Thus when M 0 and M 1 are sufficiently large, one sees that this double layer Monte Carlo makes possible a very fine tracking of both the bias of the first layer fine estimators (U m 0 , V m 0 ) and the variance of the second layer coarse estimator (U m 0 ,m 1 , V m 0 ,m 1 ).

Error estimates for regression with different starting points

After expressing error estimates for both coarse and fine approximations in CMCLDI (Section 4), we showed in Section 5.4 the importance of using the couple (s, s) s∈S to cut the bias propagation. Indeed, it is usual that successive regressions associated to a large learning depth (the cardinal |[s, s] ∩ S| is large for s ∈ S) induce the accumulation of significant errors, especially for nonlinear problems. When the standard compromise to reduce these errors is to choose a coarser set S, our trick shortens the distance |s -s| to cut the propagation of these errors without decreasing the precision on S. This trick could then introduce a new stage of approximation by making s < T for some s ∈ S.

In this section, we present a control on this new stage of approximation used in the generic example of [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF](Section 3.1) extended in Section 2.1 which is adapted to BSDEs in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF](Section 3.2) and to RBSDEs in Section 2.2. Focusing on the generic example, equation (2.7) defines u m 0 ,S s,s k for any s ∈ {s k , s k + ∆ t , ..., δ s j (s k ) -∆ t } using u m 0 ,S s k ,δs j (s k ) (•) which is deduced from a regression on X m 0 ,m 1 s k ,δs j (s k ) instead of a regression on X m 0 ,m 1 s,δs j (s k ) . Thus, provided that s is sufficiently close to s k we replaced a regressed function obtained from inner trajectories starting at s by a regressed function obtained from inner trajectories starting at s k on the same outer trajectory m 0 . We performed a similar approximation in (2.8) when s j < T as we defined u m 0 ,S s j ,s j to be equal to u m 0 ,S δs j (s j ),s j i.e. we replaced a regression on X m 0 ,m 1 s j ,s j by a regression on X m 0 ,m 1 δs j (s j ),s j . The adaptation of (2.7) yields similar approximations in (2.16) and in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF](3.12) when the adaptation of (2.8) yields similar approximations in (2.20) and in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF] (3.14).

For s j < s < s k , we consequently approximate the regressed function u m 0 ,S s j ,s k (•) resulting form the projection of

T t l+1 >s k f (t l , X m 0 ,m 1 s j ,t l , X m 0 ,m 1 s j ,t l+1 ) on X m 0 ,m 1 s j ,s k
by the regressed function u m 0 ,S s j ,s (•) resulting form the projection of

T t l+1 >s k f (t l , X m 0 ,m 1 s,t l , X m 0 ,m 1 s,t l+1 ) on X m 0 ,m 1 s,s k
and vice versa. These two approximations are not absurd since one can straightforwardly see, from the Markov property, that

u s k (x) = E T t l ≥s k f (t l , X m 0 ,m 1 s j ,t l , X m 0 ,m 1 s j ,t l+1 ) X m 0 ,m 1 s j ,s k = x = E T t l ≥s k f (t l , X m 0 ,m 1 s,t l , X m 0 ,m 1 s,t l+1 ) X m 0 ,m 1 s,s k = x . (4.1)
In the following, we denote E m 0 s j the conditional expectation knowing the trajectory (X m 0 t ) t≥s j . When E s j is the usual conditional expectation knowing X m 0 s j , E m 0 s j is needed since the regression basis depends on X m 0 . In Proposition 4.1, we establish a control on

E m 0 s j u m 0 ,S s j ,s k (X m 0 ,m 1 s,s k ) -u s k (X m 0 ,m 1 s,s k ) 2
and on E m 0 s u m 0 ,S s,s k (X m 0 ,m 1 s j ,s k ) -u s k (X m 0 ,m 1 s j ,s k ) 2 using two auxilary processes X and X defined for t l ≥ s by

       X m 0 ,m 1 s j ,s,s = X m 0 s , X m 0 ,m 1 s j ,s,s = X m 0 ,m 1 s j ,s
and for

t l = s + ∆ t , ..., T X m 0 ,m 1 s j ,s,t l = E t l-1 (E t l-2 (...E s (X m 0 s , ξ m 0 ,m 1 s j ,s+∆t ), ...ξ m 0 ,m 1 s j ,t l-1 ), ξ m 0 ,m 1 s j ,t l ) X m 0 ,m 1 s j ,s,t l = E t l-1 (E t l-2 (...E s (X m 0 ,m 1 s j ,s , ξ m 0 ,m 1 s,s+∆t ), ...ξ m 0 ,m 1 s,t l-1 ), ξ m 0 ,m 1 s,t l ). (4.2)
where E is given in (2.3). As shown on Figure 5 for

t l > s k , X m 0 ,m 1 s j ,s,t l is defined using X m 0 ,m 1 s,s = X m 0 s
and increments from the process X m 0 ,m 1 s j ,t l , in contrast to X m 0 ,m 1 s j ,s,t l defined using X m 0 ,m 1 s j ,s and increments from the process X m 0 ,m 1 s,t l . Proposition 4.1 provides a strong formulation of a possible compromise between two error terms on the right of each inequality. Proposition 4.1. For any t ∈ S, we assume u t is [u t ] Lip -Lipschitz. For s j < s < s k taking their values in the discretization set S, we define

K m 0 2,s j ,s k = [u s k ] Lip + E m 0 s j (|B m 0 ,S s j ,s k | 2 d 1
)

and K m 0 2,s,s k = [u s k ] Lip + E m 0 s (|B m 0 ,S s,s k | 2 d 1 ) where | • | d 1 is the Euclidean norm on R d 1 , then E m0 s u m0,S s,s k (X m0,m1 sj ,s k ) -u s k (X m0,m1 sj ,s k ) 2 ≤ E m0 s u m0,S s,s k (X m0,m1 s,s k ) -u s k (X m0,m1 s,s k ) 2 +K m0 2,s,s k E m0 s X m0,m1 sj ,s,s k -X m0,m1 s,s k 2 d 1 (4.3
T t l+1 >s k f (t l , X m 0 ,m 1 s j ,t l , X m 0 ,m 1 s j ,t l+1 ) on X m 0 ,m 1 s j ,s k compared to regression of T t l+1 >s k f (t l , X m 0 ,m 1 s,t l , X m 0 ,m 1 s,t l+1 ) on X m 0 ,m 1 s,s k with s ∈ {s j + ∆ t , ..., s k -∆ t }.
and

E m0 sj u m0,S sj ,s k (X m0,m1 s,s k ) -u s k (X m0,m1 s,s k ) 2 ≤ E m0 sj u m0,S sj ,s k (X m0,m1 sj ,s k ) -u s k (X m0,m1 sj ,s k ) 2 +K m0 2,sj ,s k E m0 sj X m0,m1 sj ,s,s k -X m0,m1 sj ,s k 2 d 1 . (4.4)
Proof. As we simulate several independent copies of X m 0 ,m 1 (cf. few lines before (2.4)), we make sure that the approximations u are independent from X m 0 ,m 1 , from X m 0 ,m 1 and from X m 0 ,m 1 conditionally on X m 0 . Moreover, from definition (4.2), (X m 0 ,m 1 s j ,s,t l ) t l ≥s has the same law as (X m 0 ,m 1 s,t l ) t l ≥s and ( X m 0 ,m 1 s j ,s,t l ) t l ≥s has the same law as (X m 0 ,m 1 s j ,t l ) t l ≥s . Then one can write the following

E m0 s u m0,S s,s k (X m0,m1 sj ,s k ) -u s k (X m0,m1 sj ,s k ) 2 = E m0 s u m0,S s,s k ( X m0,m1 sj ,s,s k ) -u s k ( X m0,m1 sj ,s,s k ) 2 ≤ E m0 s u m0,S s,s k ( X m0,m1 sj ,s,s k ) -u m0,S s,s k (X m0,m1 s,s k ) 2 + E m0 s u m0,S s,s k (X m0,m1 s,s k ) -u s k (X m0,m1 s,s k ) 2 + E m0 s u s k (X m0,m1 s,s k ) -u s k ( X m0,m1 sj ,s,s k ) 2 (4.5)
as well as

E m0 sj u m0,S sj ,s k (X m0,m1 s,s k ) -u s k (X m0,m1 s,s k ) 2 = E m0 sj u m0,S sj ,s k (X m0,m1 sj ,s,s k ) -u s k (X m0,m1 sj ,s,s k ) 2 ≤ E m0 sj u m0,S sj ,s k (X m0,m1 sj ,s,s k ) -u m0,S sj ,s k (X m0,m1 sj ,s k ) 2 + E m0 sj u m0,S sj ,s k (X m0,m1 sj ,s k ) -u s k (X m0,m1 sj ,s k ) 2 + E m0 sj u s k (X m0,m1 sj ,s k ) -u s k (X m0,m1 sj ,s,s k ) 2 (4.6)
which yield (4.3) and (4.4). Remark 4.1.

• We introduced notation K m 0 2,•,• since K m 0 1,•,
• was already used in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF] to control the bias term W. Indeed, Proposition 4.2 in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF] establishes the following upper bound on the bias at time s k involving the mean squared error at time δ(s k )

E m0 sj [W m0,S sj ,s k (X m0,m1 sj ,s k )] 2 ≤ K m0 1,sj ,s k E m0 sj [u m0,S sj ,δ(s k ) (X m0,m1 sj ,δ(s k ) ) -u δ(s k ) (X m0,m1 sj ,δ(s k ) )] 2 .
• In addition to the bias term W, Proposition 4.2 in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF] introduced also a variance term V and a regression error term R that can be used to decompose each mean squared error involved in the right side of inequality (4.3) and of inequality (4.4). For instance, using Proposition 4.2 of [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF] we have

E m0 sj [u m0,S sj ,s k (X m0,m1 sj ,s k ) -u s k (X m0,m1 sj ,s k )] 2 = E m0 sj (V m0,S sj ,s k (X m0,m1 sj ,s k )) +E m0 sj [R m0,S sj ,s k (X m0,m1 sj ,s k ) + W m0,S sj ,s k (X m0,m1 sj ,s k )] 2
which leads to a compromise between (regression error R+ V+ bias W)

and K m 0 2,s j ,s k E m 0 s j X m 0 ,m 1 s j ,s,s k -X m 0 ,m 1 s j ,s k 2 d 1
in (4.4). As the latter term can be made very small with a continuity argument and fine discretization, we can thus stop the bias backpropagation by accepting an error that is virtually equal to zero! Proposition 4.1 requires Lipschitz property of U that is fulfilled if f is Lipschitz. If f and g are Lipschitz, one can also show Lipschitz property for V solution of (Snl). It is then possible to replace U by V , u by v and B by C in Proposition 4.1. In contrast to U and V , it is harder to establish Lipschitz property of the solution of a discretized BSDE with a Z term. Using similar steps to the one presented in [START_REF] Pagès | Improved error bounds for quantization based numerical schemes for BSDE and nonlinear filtering[END_REF], Lemma 4.1 shows this Lipschitz property for the One step forward Dynamic Programming (ODP ) scheme

     Ŷs k = E s k Ŷδ(s k ) + ∆ s k f s k (X s k , Ŷδ(s k ) , Ẑs k ) Ẑs k = 1 ∆s k E s k Ŷδ(s k ) (W δ(s k ) -W s k ) = 1 √ ∆s k E s k Ŷδ(s k ) ζ δ(s k )
where f uses the X component and the vector ζ δ(s k ) has a normal distribution N (0, I d 1 ). Replacing s k by k, ∆ s k by ∆ k and using Markov property (cf [START_REF] Gobet | Linear regression MDP scheme for discrete backward stochastic differential equations under general conditions[END_REF]) with

y k (x) = E (y k+1 (E k (x, ζ k+1 )) + ∆ k f k (x, y k+1 (E k (x, ζ k+1 )), z k (x))) z k (x) = 1 √ ∆ k E (y k+1 (E k (x, ζ k+1 ))ζ k+1 ) , then Ŷs k = y k (X s k ) and Ẑs k = z k (X s k ).
Lemma 4.1. Assume that f (t, x, y, z) is [f ] Lip -Lipschitz continuous with respect to x, y and z uniformly in t ∈ [0, T ], for the particular case f (T, x) we denote by [f T ] Lip the Lipschitz coefficient. The coefficients b(t, x) and σ(t, x) of the Markov process (2.3) are also assumed Lipschitz continuous in x uniformly with respect to t ∈ [0, T ] with Lipschitz coefficients denoted [b] Lip and [σ] Lip . For a fixed value n 0 ≥ 1, we assume that all increments ∆ k are smaller than T /n 0 and we define

C = [f ] Lip 1 + d 1 [f ] Lip 2 + T [f ] Lip 2n 0 2 + C b,σ with C b,σ = [b] Lip + 1 2 [σ] 2 Lip , then for every time index k, y k is [y k ] Lip -Lipschitz continuous with [y k ] Lip [y k+1 ] Lip e ∆ k C + ∆ k [f ] Lip .
Moreover the functions z k are [z k ] Lip -Lipschitz continuous with

[z k ] Lip 1 √ ∆ k [y k+1 ] Lip e ∆ k C b,σ,T d 1 .
If ∆ k = h is homogeneous with respect to k, we have

[y k ] Lip [f T ] Lip + [f ] Lip C e C(T -s k )
and

[z k ] Lip d 1 n 0 T [f T ] Lip + [f ] Lip C e C(T -s k ) e T n 0 C b,σ,T .
Proof. Assume by backward induction that y k+1 is [y k+1 ] Lip -Lipschitz continuous. For every x, x ∈ R d 1 , we have

y k (x) -y k (x ) = E [y k+1 (E k (x, ζ k+1 )) -y k+1 (E k (x , ζ k+1 ))] +∆ k E [f k (x, y k+1 (E k (x, ζ k+1 )), z k (x)) -f k (x , y k+1 (E k (x, ζ k+1 )), z k (x))] +∆ k E [f k (x , y k+1 (E k (x, ζ k+1 )), z k (x)) -f k (x , y k+1 (E k (x , ζ k+1 )), z k (x))] +∆ k E [f k (x , y k+1 (E k (x , ζ k+1 )), z k (x)) -f k (x , y k+1 (E k (x , ζ k+1 )), z k (x ))]
and, for any random vector ζ ∼ N (0, I d 1 )

z k (x) -z k (x ) = 1 √ ∆ k E ([y k+1 (E k (x, ζ)) -y k+1 (E k (x , ζ))]ζ) . (4.7)
We denote, when the denominator of these expressions are not equal to zero

J x,x = [f k (x, y k+1 (E k (x, ζ k+1 )), z k (x)) -f k (x , y k+1 (E k (x, ζ k+1 ), z k (x))] | x -x | 2 d 1 t (x -x ) K x,x = [f k (x , y k+1 (E k (x, ζ k+1 ), z k (x)) -f k (x , y k+1 (E k (x , ζ k+1 ), z k (x))] y k+1 (E k (x, ζ k+1 )) -y k+1 (E k (x , ζ k+1 )) L x,x = [f k (x , y k+1 (E k (x , ζ k+1 ), z k (x)) -f k (x , y k+1 (E k (x , ζ k+1 ), z k (x ))] | z k (x) -z k (x ) | 2 d 1 t (z k (x) -z k (x ))
where, for any

x, x ∈ R d 1 , | x | d 1 =
x, x and x, x = t xx . When the denominator is zero we set these quantities to 0 as well. Then J x,x , K x,x and L x,x are σ(ζ k+1 )-measurable random vectors bounded by [f ] Lip and

y k (x) -y k (x ) = E [(y k+1 (E k (x, ζ k+1 )) -y k+1 (E k (x , ζ k+1 ))) (1 + ∆ k K x,x )] + ∆ k E (L x,x ), z k (x) -z k (x ) + ∆ k E [J x,x ](x -x ).
Note that

E (L x,x ), z k (x)-z k (x ) = E y k+1 (E k (x, ζ k+1 )) -y k+1 (E k (x , ζ k+1 )) E (L x,x ), ζ k+1 / ∆ k so that y k (x) -y k (x ) = E (y k+1 (E k (x, ζ k+1 )) -y k+1 (E k (x , ζ k+1 ))) (1 + ∆ k K x,x + ∆ k E (L x,x ), ζ k+1 ) + ∆ k E [J x,x ](x -x ).
Consequently, using Cauchy-Schwartz inequality for the first term on the right hand side of the above decomposition and |J x,x | ≤ [f ] Lip for the second,

|y k (x) -y k (x )| ≤ y k+1 (E k (x, ζ k+1 )) -y k+1 (E k (x , ζ k+1 ) 2 1 + ∆ k K x,x + ∆ k E (L x,x ), ζ k+1 2 + ∆ k [f ] Lip | x -x | d1 .
By elementary computations already carried out in [START_REF] Bally | A quantization algorithm for solving discrete time multidimensional optimal stopping problems[END_REF][START_REF] Pagès | Improved error bounds for quantization based numerical schemes for BSDE and nonlinear filtering[END_REF], one classically has for the Euler scheme with step ∆ k ,

y k+1 (E k (x, ζ k+1 )) -y k+1 (E k (x , ζ k+1 ) 2 ≤ [y k+1 ] Lip E k (x, ζ k+1 ) -E k (x , ζ k+1 ) 2 ≤ [y k+1 ] Lip |x -x | d 1 1 + C b,σ ∆ k with C b,σ = [b] Lip + 1 2 [σ] 2
Lip . On the other hand

E 1 + ∆ k K x,x + ∆ k E L x,x , ζ k+1 2 = 1 + ∆ 2 k E K 2 x,x + ∆ k E|L x,x | 2 |ζ k+1 | 2 + 2∆ k E(K x,x ) + 2 ∆ k E (L x,x ), E ζ k+1 =0 +2∆ 3/2 k E [K x,x E (L x,x ), ζ k+1 ] ≤ 1 + ∆ k [f ] 2 Lip d 1 + ∆ 2 k [f ] 2 Lip + 2∆ 3/2 k [f ] 2 Lip d 1 + 2∆ k [f ] Lip ≤ 1 + 2∆ k [f ] Lip C f,d1,T
where we used E|ζ 1 | 2 = d 1 in the first inequality and for fixed n

0 > 1 given ∆ k ≤ T /n 0 we set C f,d 1 ,T = 1 + d 1 [f ] Lip 2 + T [f ] Lip 2n 0 2
. Thus, we obtain

1 + ∆ k K x,x + ∆ k E (L x,x ), ζ k+1 2 ≤ 1 + [f ] Lip C f,d 1 ,T ∆ k .
Plugging these in the above upper bound yields

| y k (x) -y k (x ) | [y k+1 ] Lip 1 + [f ] Lip C f,d 1 ,T ∆ k ) 1 + C b,σ ∆ k + ∆ k [f ] Lip | x -x | d 1 i.e. [y k ] Lip ≤ [y k+1 ] Lip 1 + [f ] Lip C f,d 1 ,T ∆ k ) 1 + C b,σ ∆ k + ∆ k [f ] Lip ≤ [y k+1 ] Lip e ∆ k C + ∆ k [f ] Lip with C = [f ] Lip C f,d 1 ,T + C b,σ .
As for the z term, using Lipschitz property of y k+1 and Cauchy-Schwarz's inequality then E|ζ

1 | 2 = d 1 and E k (x, ζ k+1 ) -E k (x , ζ k+1 ) 2 ≤ |x -x | d 1 1 + C b,σ ∆ k we get | z k (x) -z k (x ) | d 1 1 √ ∆ k [y k+1 ] Lip d 1 i=1 E [(E k (x, ζ k+1 ) -E k (x, ζ k+1 ))] 2 E ζ i k+1 2 1 √ ∆ k [y k+1 ] Lip d 1 e ∆ k C b,σ | x -x | d 1 . Thus, z k is Lipschitz continuous with coefficient [z k ] Lip satisfying [z k ] Lip 1 √ ∆ k [y k+1 ] Lip e ∆ k C b,σ,T d 1 .

Assuming homogeneous time increment ∆

k = h = T /n with n ≤ 2 L , then for k ≤ n we have e Ckh [y k ] Lip [y k+1 ] Lip e C(k+1)h + e Ckh [f ] Lip h.
which yields

e Ckh [y k ] Lip [f T ] Lip e Cnh + [f ] Lip h n-1 l=k e Clh [f T ] Lip e CT + [f ] Lip h e CT -e Ckh e Ch -1 [f T ] Lip e CT + [f ] Lip h e CT e Ch -1 [f T ] Lip e CT + [f ] Lip e CT /C. Finally we have [y k ] Lip [f T ] Lip e C(T -s k ) + [f ] Lip e C(T -s k ) /C (4.8) and [z k ] Lip 1 √ h ([f T ] Lip + [f ] Lip C )e C(T -s k -h) e hC b,σ d 1 .
5 Some numerical results

In this section we test the presented conditional MC learning procedure on American option and risk measure. All simulations are run on a laptop that has an Intel i7-7700HQ CPU and a single GeForce GTX 1060 GPU programmed with the CUDA/C application programming interface. We refer the reader to [31] for an introduction to CUDA programming. Like in [START_REF] Abbas-Turki | Conditional Monte Carlo Learning for Diffusions I: main methodology and application to backward stochastic differential equations[END_REF], we used the code of the contribution [START_REF] Abbas-Turki | Resolving small random symmetric linear systems on graphics processing units[END_REF] in order to perform the batch parallel regressions induced by the proposed 1NMC simulation combined with local regressions. The very competitive execution times that we present hereafter are possible not only because of the GPU use but also due to the adaptation of parallelization strategies presented in [START_REF] Abbas-Turki | Resolving small random symmetric linear systems on graphics processing units[END_REF].

American geometric put option

Given the (Snl) setting of Section 2.2 with a driver f = 0, we consider an American geometric put option with constant interest rate r and a payoff

g(x) = K - d 1 i=1 (x i ) 1/d 1 + (5.1)
with an asset X given by X We approximate the price V 0 associated to payoff (5.1). We choose the dimension d 1 = 20 to make sure that the variance of g(X) is sufficiently large. We point out however that it works well for d 1 = 100. In Table 1 we show the price of an American geometric put option, calculated by simulated expression V sim 0 , for different maturities. Indeed, V learn 0 provides almost the same values. From top to bottom we have: a variance adjustment [VA], a bias control [BC] and a combination of [BC] and [VA]. We show that the simulated expression with a combination of [BC] and [VA] gives a good approximation of the price even for long maturity T = 2. One can strengthen the bias control on a finer discretization time grid S but this will increase further the complexity. In Table 1 [VA] + [BC], we choose a standard time discretization for the approximation of American options with s = (s + 1/4) ∧ T and we show that the variance adjustment is needed for better approximation of the conditional expectation of scenarios close to the exercise frontier. , 1}, we implement on the left the conditional MC procedure using s = T . On the right, we implement the conditional MC procedure controling the bias with s = s + 1 4 ∧ T . We show that the control allows to reduce the bias propagation. Figure 7 shows the approximation of the American geometric put option, calculated by learned and simulated expression, with respect to the number of inner trajectories for different maturities. Both expressions converge to the benchmark value for 2 9 outer trajectories and 2 12 inner trajectories in 3 seconds.

i t = X i s exp (r -σ 2 2 )(t -s) + σ(W i t -W i s ) , t > s, 1 ≤ i ≤ d 1 , r = log(1.1), σ = 0.4, K = X i 0 = 100 and d 1 = 20.

Initial Margin

We consider a portfolio of one hundred put options, the price U s k of the portfolio at time step s k is given by

U s k = d 1 i=0 e -(T -s k )r E s k K -X i T + (5.2)
with an asset X given by X i t = X i s exp (r -σ 2 2 )(t -s) + σ(W i t -W i s ) , t > s, 1 ≤ i ≤ d 1 , with r the interest rate, K the strike and T the maturity.

We calculate the Initial Margin (IM) of this portfolio that is an amount posted by the counterparty (or the bank) to overcome the loss of the portfolio during the liquidation period after a default. IM is formalized here as follows

IM s k = ES a s k (L s k ,δ(s k ) ) (5.3)
where the loss of the portfolio at time s k over a period ∆ s k is denoted L s k ,δ(s k ) and is defined here by

L s k ,δ(s k ) = U δ(s k ) -U s k ,
and the expected shortfall ES of level a is defined at time s k for any random variable Y by

ES a s k (Y ) = 1 (1 -a) 1 a VaR α s k (Y )dα.
The value-at-risk VaR α (Y ) of level α of some random variable Y conditionally to F s k is defined by VaR α s k (Y ) = inf{x ∈ R : P(Y ≤ x | F s k ) ≥ α}. We considered the following parameters: T = 1, d 1 = 100, K = X i 0 = 100, r = 0.01, a = 99% and ∆ s k = 1 32 . For each s k ∈ S = l 32 ; l = 0, ..., 32 , we simulate U s k using u m 0 ,S s k ,T and we simulate U δ(s k ) using u m 0 ,S s k ,s k +∆s k (X m 0 ,m 1 s k ,s k +∆s k

). A benchmark approximation of the IM is obtained using Black & Scholes formula for put options.

Figue 8 shows few distributions of the loss process. From top to bottom we show different time steps s k ∈ { 29 32 , 19 32 , 9 32 }. On the left, we perform the procedure without variance adjustment and on the right we perform the variance adjustment. We show that the variance adjustment is necessary to fit the benchmark distribution of the loss process. Figure 9 shows the initial margin distribution. From top to bottom we show different time steps s k ∈ { 29 32 , 19 32 , 9 32 }. The tail distribution of the loss process is very well approximated and provides a fairly good representation of the distribution of IM. Figure 10 shows the mean of IM with respect to the time horizon of the portfolio at the top and the L2 relative error at the bottom. The relative error is sufficiently small as it is generally less than 8% and does not exceed 11%.

Figure 1 :

 1 Figure 1: An example for (2.9) when sk = δ s j (s j ), δ 2 (s j ) = δ(s k ) = s j = t 2 L = T ,

q 0 1 qFigure 2 :

 12 Figure 2: An example for (3.3) when L = 5, L = 3, S 0 = 0,T 8 , T 4 , 3T 8 , T 2 , 5T 8 , 3T 4 , 7T 8 , T and S 1 = 0, T 16 , T 8 , 3T 16 , T 4 , 5T 16 , 3T 8 , 7T 16 , T 2 , 9T 16 , 5T 8 , 11T 16 , 3T 4 , 7T 8 , T .

  10) when S = S i } and S i,(Snl) s = {u ∈ S i ∩]s, δ S i (s)] that satisfies (2.21) when S = S i }

q 0 1 qFigure 3 :

 13 Figure 3: An example for Definition 3.2 based on the example of Figure 2. Here, for j = 27, 28 we have s j (s 0 j ) > max(S 1,(•) T -s 1 j ).

q 0 1 qFigure 4 :

 14 Figure 4: An example for Definition 3.2 based on the example of Figure 2. Here, for j = 27, 28 we have s j (s 0 j ) ≤ max(S 1,(•) T -s 1 j ).

Figure 5 :

 5 Figure 5: Regression of

Table 1 :

 1 Numerical simulations for American option (5.1) simulated formula, [BC] bias control [VA] variance adjustment: d 1 = 20, M 0 = 2 11 , M 1 = 2 12 . (s + 1/4) ∧ T ) (± 0.041) (± 0.061) (± 0.089) [VA] + [BC] (s + 1/4) ∧ T ) (± 0.035) (± 0.037) (± 0.055

Figure 6 0 M 0 m 0

 6000 Figure6shows the difference between two approximations 1 M 0

Figure 6 : 1 M 0 M 0 m 0 1 M 0 M 0 m 0

 610001000 Figure 6: 1 M 0

Figure 7 :

 7 Figure 7: Numerical approximation of the price V 0 : d 1 = 20, M 0 = 2 9 , T = 1, L = 3.

Figure 8 :

 8 Figure 8: Numerical approximation of loss L s,s+ 1 32 distribution [Left] Without variance adjustment, [Right] With variance adjustment; [top to bottom] s k ∈ { 29 32 , 19 32 , 9 32 }; M 0 = 2 8 , M 1 = 2 8 × 5.

Figure 9 :

 9 Figure 9: Numerical approximation of IM s distribution: [top to bottom] s ∈ { 29 32 , 19 32 , 9 32 }; M 0 = 2 8 , M 1 = 2 8 × 5.

  s k , L = 5 and S = {t 0 , t 4 , t 8 , t 12 , t 16 , t 20 , t 24 , t 28 , t 32 }.

Figure 10: Initial Margin: [Top] mean of IM s ; [Bottom] L2 relative error.


Youssef Bouanan
email: youssef.bouanan@ims-bordeaux.fr

Gregory Zacharewicz
email: gregory.zacharewicz@ims-bordeaux.fr

Bruno Vallespir
email: bruno.vallespir@ims-bordeaux.fr

Judicael Ribault
email: jribault@gmail.com

Saikou Y Diallo
email: sdiallo@odu.edu

DEVS based Network: Modeling and Simulation of Propagation Processes in a Multi-Layers Network

Keywords: Diffusion Process, Multi-Layer Network, DEVS formalism, Agent-Based Modeling, ACM Classification I.6

This paper deals with diffusion process in a multi-layer network using DEVS (Discrete Event System Specification) formalism. Social interaction plays an important role in studying the propagation of information, innovation, ideas, and influence among its members. When an informational event appears it can either die out quickly or makes significant inroads into a population. Network diffusion process allows us to understand the dynamics and the propagation of information in Social Network (SN). These networks can consist of individuals, group of person or organizations. The interactions could be done by physical proximity contact, remote collaboration, any types of social meetings and some forms of verbal or written communication depending on the situations. In our work we use the DEVS formalism, extended by DS-DEVS and PDEVS in order to set to simulate the propagation phenomena within a multi-layer social network (MSN). The network agent behavior is represented in the form of atomic models or coupled models if they are complex, and the social network is managed using DS-DEVS.

INTRODUCTION

Many real-world systems can be modeled as networks, i.e., sets of interconnected entities. Several studies of networks employed an abstraction in which systems are represented as ordinary graphs [START_REF] Bollobás | Modern Graph Theory[END_REF]: the 'nodes' (or 'vertices') of the graphs represent some entity or agent, and a tie between a pair of nodes is represented using a single, static, unweighted 'edge' (or 'link'). Self-and multi-edges were also typically ignored. In real world, more than one kind of relationship can exist between two actors (e.g. family, friendship, religion and work ties) and that those ties can be so intertwined that it is impossible to analyze them separately [START_REF] Fienberg | Statistical Analysis of Multiple Sociometric Relations[END_REF][START_REF] Minor | New directions in multiplexity analysis[END_REF][START_REF] Szell | Multirelational organization of large-scale social networks in an online world[END_REF].

At the beginning such networks have been called multiplex network [START_REF] Monge | Theories of communication networks[END_REF]. The term is derived from communications theory which defines multiplex as combining multiple signals into one in such way that it is possible to separate them if needed. Recently, the area of multi-layered social network has started attracting more and more attention in research conducted within different domains [START_REF] Kazienko | Multidimensional social network in the social recommender system. Systems, Man and Cybernetics, Part A: Systems and Humans[END_REF][START_REF] Rodriguez | Exposing multi-relational networks to single-relational network analysis algorithms[END_REF][START_REF] Szell | Multirelational organization of large-scale social networks in an online world[END_REF], and the meaning of multiplex network has expanded and covers not only social relationships but any kind of connection, e.g. based on geography, occupation, kinship, hobbies, etc. [START_REF] Abraham | Low-distortion inference of latent similarities from a multiplex social network[END_REF].

Social interaction plays an important role in studying the propagation of information, innovation, ideas, and influence among its members. When an event appears -for example, the use of cell phones among students, the adoption of a new information system within the enterprise, or the rise of a political movement in an unstable society -it can either die out quickly or makes significant inroads into a population. Network diffusion process allows us to understand the dynamics and the propagation of information in social network. These networks can consist of individuals, group of person or organizations. The interactions could be done by physical contact, remote collaboration, any types of social meetings or some forms of verbal or written communication depending on the situations. The diffusion studies are numerous because diffusion phenomena are discussed in several disciplines: computer science (computer virus, information diffusion in a social network) [START_REF] Girvan | Simple model of epidemics with pathogen mutation[END_REF], biology (epidemics) [START_REF] Cauchemez | Role of social networks in shaping disease transmission during a community outbreak of 2009 H1N1 pandemic influenza[END_REF], physics, etc. In our case we diffuse a message enclosed in a data packet. This packet contains several pieces of information which influence the reaction of the individual and time life of the packet.

To this end, we analyze the topic of spreading processes in multilayer networks according to three main aspects: (A) how spreading processes can be modeled (Section 3), (B) what results can be obtained from these models (Section 4) and (C) how these results can be verified and validated (Section 5).This paper begins by introducing basic concepts (multilayer networks, spreading processes in multilayer networks and variables used to study these phenomena). Then, it provides model of individuals with DEVS characterized by a set of attributes and it presents our architecture to simulate the diffusion process in a multilayer network. The final part concerns our experiments and the conclusion.

PRELIMINARIES

In this section we introduce formal specification that can use to model and simulate a network. Then, we will present the concepts of multilayer network and dissemination processes in multilayer network.

In order to specify dynamical models, B.P. Zeigler introduced the Discrete EVent System Specification formalism (DEVS) [START_REF] Zeigler | Theory of modeling and simulation: integrating discrete event and continuous complex dynamic systems[END_REF]. With DEVS, a model of a large system can be decomposed into smaller component models with coupling specification between them. DEVS formalism defines two kinds of models: (1) atomic models that represent the basic models providing specifications for the dynamics of a sub-system using transition functions (external transition, internal transition); (2) coupled models or "network of models" that describe how to couple several component models together to form a new model. DEVS provides an automatic simulation based on time synchronization and message propagation.

In 1985, G. Klir was the first to introduce the concept of dynamic structures within a framework of modelling and simulation [START_REF] Klir | Architecture of systems problem solving[END_REF]. After, F. Barros introduced the DSDEVS formalism [START_REF] Barros | Modeling formalisms for dynamic structure systems[END_REF]. The latter constitutes the most satisfactory formalization for the modelling of dynamical changes in structure. Let us cite F. Barros writing about dynamic structure systems in general [START_REF] Barros | Modeling formalisms for dynamic structure systems[END_REF]: "[. . .] Structural changes can better reflect dynamic of real systems we want to model in which drastic changes of structure and behaviors can be observed". This assertion is particularly relevant in the context of MAS where relations between agents are likely to change dynamically. Thus, DSDEVS is worth for the formalization of MAS in the context of dynamical systems. A simple network (i.e. a single-layer network) can be represented by a graph [START_REF] Bollobás | Modern Graph Theory[END_REF][START_REF] Newman | Networks: an introduction[END_REF]. A graph is a tuple G = (V; E), where V is set of nodes (vertices) representing social entities: humans, organizations, departments etc., called also members, agents or instances and E  VV is a set of (ordered or unordered) edges (arcs, connections or ties) that connects pair of nodes. Since social networks usually represent one kind of relationships they are also called single-layered social network SSN [START_REF] Magnani | The ML-model for multi-layer social networks[END_REF]. A multilayer network is a data structure made of multiple layers, where each layer is a monoplex network. A multi-layered social network (MSN) is a network extended to multiple edges between pairs of nodes/actors. It is defined as a tuple <V, E, L> where:  V -is a set of actors (social entities);  E -is a set of tuples <v,e,l>, lL, v≠e;  L -is a set of distinct layers ( types of relationships).

Each layer in the MSN corresponds to one type of relationships between people. Different relationships can result from the character of connections, types of communication channel. The examples of different relationships can be: friendship, family or work. Different communication channels that result in different types of connections are: email exchange, VoIP calls, instant messenger chats, etc. These networks can be defined as a sequence of graphs:

{G}  = {(V, E)}  =1
Where E  V  V is the set of edges and  indexes the graphs or the type of relationships. In our networks, the nodes (agents) are the same across the different layers (i.e. V = V ,). In Figure 1, the example of three-layered social network is presented. The set of agents consists of {a, b, c, d, e}, they are connected with each other on three layers: l1 (family), l2 (friendship) and l3 (work).

Diffusion processes in networks have a long history in social sciences [START_REF] Rogers | Diffusion of innovativeness[END_REF]. With the advent of sufficient storage and computational power, this network diffusion process became an emerging research area in computer science [START_REF] Domingos | Mining social networks for viral marketing[END_REF]. Propagation models are designed to reproduce phenomena observed in social networks with applications in viral marketing, spread of disease and diffusion of ideas and innovations. Most models proposed recently are extensions from the independent cascade (IC) [START_REF] Goldenberg | Talk of the network: A complex systems look at the underlying process of word-of-mouth[END_REF] and the linear threshold models (LT) [START_REF] Granovetter | Threshold models of collective behavior[END_REF]. The two models characterize two different aspects of social interaction. The IC model focuses on individual (and independent) interaction and influence among friends in a social network. The IC models can also be identified with the so-called Susceptible/Infective/Recovered (SIR) model for the spread of disease in a network [START_REF] Bailey | The mathematical theory of infectious diseases and its applications[END_REF]. The LT model focuses on the threshold behavior in influence propagation, which we can frequently relate to; when enough of our friends bought a new phone, played a new computer game, or used new online social networks, we may be converted to follow the same action.

One of the important ideas in the context of dissemination processes in multilayer networks is the fact that elements can also spread from one layer to another. In general there are four possibilities for an element to traverse a multilayer network (Table 1): same-node inter-layer, when the cascade switches layer but remains on the same node, e.g., when an element is shared on different layers by the same actor; other-node inter-layer, when a cascade continues spreading to another node in another layer. In third type, other-node intra-layer, the cascade continues spreading through the same layer, e.g., spreading an information between friends. The fourth combination, same-node intralayer, is generally not considered meaningful and therefore omitted in all the diffusion studies we have considered.

Same Node

Other Node

Same Layer Unused

The item spreads to a different node on the same layer

Other Layer

The item switches layer but remains on the same node

The element continues spreading in a different node on the another layer Table 1. Different possibilities for spreading an element in a multilayer network.

MATERIALS AND METHODS

In this section, we propose an agent-based model for the information diffusion in a Multi-layer network.

Problem Statement

Several research studies attempted to model and simulate the influence diffusion in a social network. However, the focus is on one layer network (one link or relationship between persons) e.g., the message disseminates only within friends. In addition, they did not consider the individual and cultural factors on diffusion process; the message disseminates in the same way between two friends or two coworkers. Actually, the way how people communicate is highly dependent of the person who people are talking to. In the current work, we address the following issue: how to simulate the effects of information on population with a propagation algorithm of the effects across Multi-Layer social networks? The challenge is to improve the realism of socially intelligent agents and take into account the impact of individual's personality and cultural values in the diffusion model process.

Formalization of Human Behavior

In the agent-based model, individuals or group of individuals are represented as agents. Each agent is described by a set of attributes:

 Static attributes: gender, social status, religion, age class, ethnicity, leadership and language.

 Dynamic attributes (variables): opinion, interest, un/satisfied-needs.

Static attributes are intrinsic or unchanged parameters, i.e., time has no effect on them. Dynamic attributes evolve with time or events. For example, individuals can be reached or not by the information depending on its opinion and the social network configuration.

We use DEVS to describe the human behavior. DEVS is a well-defined formalism which has numerous advantages over other formalism in the modeling of complex dynamic system. The perception is specified by the arrival of external events on the model's ports. These events change the state of the agent. We can represent the actions of agent by a discrete event generated by the agent, i.e., the emission of an external event by an output function. In a simplified way, we can represent the agent's autonomy as the union of internal transitions of a DEVS model. Finally, Perception, action and autonomy formalize the behavior of the agent.

The following notations describe the server model. We do not describe detailed operations of this model; we just explain the role and interface of the server model (Server-Node). Figure 2 is an example that describes the message influence on the individual behavior and potentially its dissemination using the DEVS specifications. The first phase is used to configure and initialize the agent' attributes. Then, when the agent is in the "IDLE" phase, and if it receives an external event from another agent on port "In" (In? Packet), it moves to "phase_0". Here, the agent calculates the trust factor α(i,j) between him and the sender depending on the social pressure, similarity between him and the sender (based on the religion, language and age class) and its sensitivity to the message theme. If the trust factor is higher than a predefined threshold, the receiver moves to "phase_1" else it returns to "IDLE". Then, if the message is still strong enough, the receiver moves to "phase_2" else it returns to "IDLE". This message creates an impact on the individual, and eventually its behavior depending on the agent's opinion and the relationship between him and the sender. After a period, processing time, the receiver transmits the message on its ego-network. After the contact between receiver and sender, the receiver's variables (opinion, interest, satisfaction) change according to the message content, the sender and cultural factors.

Formal Specification of Social Network

As recalled previously, DEVS formalism is supporting describing static coupled models (or graphs). However, the relations between agents are able to change dynamically, requires a dynamic structure. Works to introduce this type of structure was proposed [START_REF] Barros | Modeling formalisms for dynamic structure systems[END_REF][START_REF] Uhrmacher | Dynamic structures in modeling and simulation: a reflective approach[END_REF] to be integrated in DEVS. The formalization of F. Barros called DS-DEVS for Dynamic-Structure DEVS, is more satisfactory in the case of social networks M&S since it preserves all the properties of DEVS, i.e. the modularity and the hierarchical decomposition. DS-DEVS is represented in the form of a coupled model thus which can couple itself with other models DEVS. It makes it possible to modify connections between its models and to add or remove its DEVS models at simulation run time on the occurrence of internal or external events.

We created a tool for the automatic instantiation of individuals attributes in behavioral DEVS models and relations between them (static SN graph from social science literature classical structure) to coupled models managed using DS-DEVS. The agents are instantiated in the form of atomic models or if they have a complex dynamics in coupled models (as described in Figure 3). DEVS allows here the possibility of defining dynamically each entity and simulating the evolution of the system.

Modeling and Simulating Dissemination Process in a Multi-Layer Network

In this work, we use an extension of social influence model called "User-centered model". Each behavioral model includes (a) social pressure, measured from the number of active neighbors, (b) the sensibility of the actor to the message or the item disseminated and (c) the similarity between the sender and the receiver of the item (Figure 4).

Then according to rules the information is touching the agent or not. Another barrier faced has been that each individual must contain concern (as an atomic or as a coupled model) about the network rules (to transmit or not the information on this specific network for example) as well as individual rules (affected or not by the message for example). This nonseparation of concern prevents us to reuse the model with other networks or in other study.

To overcome these two barriers, we presented a novel architecture described in Figure 5. We want to keep the separation of concerns at the network level, each network remains independant from the others. component a, a', and a'' are called Proxy and contains the specific network rules for each individual. Each component has a specific behavior depending on the type of the link connecting it to the ego-network. These components are connected to a Server representing the individual state and containing the individual rules. The sequence when an information arrive to a'' on Network1 is the following :

 component a'' sends an event to Server A  Server A reads the event and depending on its state (motivation) and rules, can propagate the information to its networks. Thus, an event is sent to components a, a' and a''.  Components a, a', and a'' read the event and depending on their state and rules, can diffuse the information to their neighbors. In this case a'' already has the information and does nothing; Pre-simulation: Before making a simulation, we build a new experiment by generating a multi-relational graph if it does not already exist in the repository. An experiment includes one or several groups. A group includes many individuals. A graph represents all relations between individuals. We opted for the storage of information in a database so that each experiment is easily accessible and replayable. The repository contains all the models available to execute the simulations, i.e., all the servers and proxies that will be used by the Graph-Executive to produce the simulation model.

Simulation:

The agent-based model is used to simulate the process of items diffusion in the network generated in the first step. The simulation starts with the experiment to simulate, as well as servers and proxies to use. In this way, for the same experiment, we can test different behavior algorithms. The Graph-Executive connects to the database to retrieve all the information from the experience to execute. It transforms the graph into a DEVS coupled model "DEVS network". Each node is transformed to a DEVS atomic model. The generator is used to prepare the item and send it to info-sources at time t = 0. The simulation is executed using to produces a result set in the form of a file. This part will be developed within the framework of VLE application (Virtual Laboratory Environment) [START_REF] Quesnel | The Virtual Laboratory Environment -An operational framework for multi-modelling, simulation and analysis of complex dynamical systems[END_REF].

Post-simulation:

The R script post-processes the simulation result. The result file is used to visualize the course of the simulation and to develop an analysis and conclusion. The analysis can lead to a new simulation, i.e., makes a new pre-simulation, simulation and postsimulation.

EXPERIMENT

Overview

The MSN concept introduced in this paper is illustrated by modeling and simulating the spread of information in a multi-layer social network. The goal of this experiment is to study the diffusion phenomena in the framework of multilayers networks. The analyze and study of the information influence processes initiated by starting point over network member attributes is done regarding temporal and sequential dynamic. Simulation is used to show that the topology of the network can affect the result of the diffusion process. In more details, a population of 350 agents has been generated according to social science population structure rules described in [START_REF] Forestier | Generating Multidimensional Social Network to Simulate the Propagation of Information[END_REF] and connected on three layers: family, friends and neighbors. These three layers represent the primary groups defined in [START_REF] Litwak | Primary group structures and their functions: Kin, neighbors, and friends[END_REF].

Assuming that all agents are starting in a state "0" (they don't received the message yet), and when an agent receives the message, its state changes to "1" if it has an interest to the message or changes to "2" if it receives the message but it has no interest to the message or the item. The agents in the state "2" block the spreading process and they do not update their behavior. However, agents in state "1" update their behavior and their parameters. In this case, the update of agent's opinion is based on the concept of opinion change described by [START_REF] Friedkin | Social influence networks and opinion change[END_REF]. Social influence occurs when a message emitter and a message receiver get in contact. The message emitter attempts to communicate position about an opinion to the receiver. As result of this conversation, the receiver of the message may shift her/his opinion some distance towards or away from that of the emitter's opinion. This opinion is characterized by the opinion number and the opinion confidence bounds. The study proposed to distinguish two categories of population: extremist and moderate people. The first category is located at the ends of the distribution of opinion (their uncertainty is lower, they block the messages).

Settings

We have driven in the experiment proposed two scenarios with the same population characteristics but with different configurations for the information spreading settings.

Scenario 1:

The goal of this scenario is to show the impact of agent's attributes and message characteristics on diffusion phenomenon. Therefore, we ply 40 simulations by connecting the generator (at time t=0) to the political leaders and changing randomly the topic of the message and its strength. Each layer has a different sensitivity to the theme of the message. We propose three themes: (1) message affects security and stability in the area; (2) message affects the religious community; and (3) it influence physical and social needs: health and employment. Then, we analyze these results to verify and validate the different hypotheses.

Scenario 2:

In this experiment, we fix all parameters in the model including the MSN structure, agent settings and message content and strength. Only the message starting point will be a changed. Before starting simulation, we connect the generator with three different agents (infosources). We change these points randomly for each simulation. In the end we store the result of 50 simulations in a csv file. After that, we analyze the variation of the final opinion depending on different combinations of starting point.

Result

Figure 7 presents outputs from scenario 1. It presents the average of agent's opinion for each simulation depending on message characteristics. For each iteration the strength of the message has been changed randomly between [START_REF] Bollobás | Modern Graph Theory[END_REF][START_REF] Cauchemez | Role of social networks in shaping disease transmission during a community outbreak of 2009 H1N1 pandemic influenza[END_REF] and the subject of the message between 1 and 4. These four message subjects influence the diffusion of the message according to each dimension. The payoff (efficiency) of the actions is affected by the message characteristics and the strengths of a message. The objective is to reveal how each agent is impacted over time by a message. Figure 7 shows that the messages spread in this example have majorly a negative impact on the opinion of the individuals regarding a given event. It is displayed by an average final opinion (value<5) mostly under the average initial opinion (value=5). Nevertheless it distinguishes that some couple of (message/content and message/strength) have a specific significant impact over a population.

At this level, statistical test are helpful for the validation of this work. Nevertheless even a simple analysis of the result reveals by simulation the possibility to maximize the effect of the message over a population. It can be done by giving the right strength and content value to the message (it can be adapted by tuning over replications of simulation run) in order to optimize the effects over the population and to control the effort regarding potential results. The conclusion of this experiment is that the topology or structure of a network is very important in diffusion phenomenon and even if the Node has a high eigenvalue or a good centrality the reach of the actions can be insignificant. Conversely, some starting points that were not identified as key agents (such as not leader and some sometime not well interconnected) can be revealed by simulation as key path to maximize the information diffusion (some picked in the Figure 8 are not leaders and not connected to important number of neighbors).

In this paper, we focused on statistical test in order to verify our hypothesis and to analyze the sensitivity of the simulation models. In the next step, we will adopt others verification and validation techniques of simulation models (e.g. comparing the results of our simulation with historical data).

CONCLUSION AND PERSPECTIVE

This paper presents the architecture of a multidimensional social network for modeling relationships between people.

It uses an MSN architecture to generate each dimension with its own rules: the friendship dimension is different from the neighbor dimension and cannot be generated in the same way. So, using an MSN has permitted a better partitioning of each social dimension of human life. Furthermore MSN also allows defining distinct propagation rules for each dimension. The MSN environment implemented proposes features to easily modify such as the strength of the message, the time of the day, the probability of acceptance for each dimension. The simulation has permitted to obtain first results to observe the impact of the population structure and behavior in the message diffusion process. The simulation of two scenarios has presented the interest of simulation to identify key info source in the population and the importance of the tuning over the message strength and content to maximize its impact on the population. One of the greatest things using an MSN is its adaptability. The tool allows easily adding or deleting a dimension in respect of the population's features.

Finally, the work presented in this paper is part of a defense related project but opens many possibilities for various application domains. Generating a population with an unseen level of cultural features can be used in marketing to simulate the adoption of a new product, in social science to observe dynamically the diffusion of information or the way an opinion changes.

Figure 1 .

 1 Figure 1. An example of the MSN.

Figure 2 .

 2 Figure 2. DEVS specification of agent model.

Figure 3 .

 3 Figure 3. Specification of a Network.

Figure 4 .

 4 Figure 4. Diffusion algorithm between agents. Then, at the structural level, flattening different layers into a single network was one possible way to simulate multilayer network. In this flattened network, individuals are connected to other individuals directly. Benefits are the simplicity of representation and the strict minimum number of components and bindings. One drawback is the nonseparation of concerns.

  a' sends an event to b' and d'; a sends an event to b.  components b, b' and d' send an event to respectively proxy B and D and so on.

Figure 5 .

 5 Figure 5. Proposed MSN implementation.In our case we implemented the diffusion model presented in the section 3.4 in the proxies and the server updates the agents behavior if it receives an notification from the proxies (the proxy has an interest to the item). This architecture allows us the integration of various diffusion model taking into account the caracteristics of the layer (type of relationship or the communication channel). This approach aims to enhance the reusability, the model representation, and thus eases the development. It's easy to add a new network: we just have to build the specific rules (if any) in a new Proxy component. We can change individuals without changing the networks. Drawbacks are the increased number of nodes and bindings.Four conditions can cause the end of the simulation:[START_REF] Bollobás | Modern Graph Theory[END_REF] The individual who receives the information does not have an interest;[START_REF] Fienberg | Statistical Analysis of Multiple Sociometric Relations[END_REF] The strength of the message to be propagated falls below a given threshold; (3) All nodes are inactive; (4) It has been a long time (higher than a given threshold) since the scenario occurred.

Figure 6 .

 6 Figure 6. Agent-Based Simulation Architecture.

Figure 7 .

 7 Figure 7. The final opinion of agents relative to the message characteristics.

Figure 8 .

 8 Figure 8. Number of agents affected relative to different info-sources.

Figure 8

 8 Figure8presents outputs of scenario 2. It shows the number of agent interested by the message during each iteration. For each iteration, three starting points have been randomly changed. This Figure permits to observe significant impact or insignificant effects. On one hand, several combinations do not trigger the propagation process for several reasons. On the other hand for instance one combination has a deep impact on the population reaching a pick of a bit less than 330 individuals. The reason of the success/fail can be depending on the info-sources egonetworks or the rejection of the messages by the receivers along the chain of diffusion process. This example remains conceptual. Then, domain dependent thresholds can be defined to set the significance barriers.

ACKNOWLEDGMENTS

This work is supported by the SICOMORES Project N° 132936073 funded by French DGA (Direction Générale de l'Armement) and MASA Group. It involves the following partners: IMS university of Bordeaux, LSIS university of Marseille and MASA Group.