Paul Gassiat

Idris Kharroubi

Huyên Pham

Time discretization and quantization methods for optimal multiple switching problem

Keywords: Optimal switching, quantization of random variables, discrete-time approximation, Markov chains, numerical probability MSC Classification: 65C20, 65N50, 93E20

. A priori L p -error estimates are stated in terms of quantization errors. Finally, some numerical tests are performed for an optimal switching problem with two regimes.

Introduction

On some filtered probability space (Ω, F, F = (F t ) t≥0 , P), let us introduce the controlled regime-switching diffusion in R d governed by dX t = b(X t , α t )dt + σ(X t , α t )dW t , where W is a standard d-dimensional Brownian motion, α = (τ n , ι n ) n ∈ A is the switching control represented by a nondecreasing sequence of stopping times (τ n ) together with a sequence (ι n ) of F τn -measurable random variables valued in a finite set {1, . . . , q}, and α t is the current regime process, i.e. α t = ι n for τ n ≤ t < τ n+1 . We then consider the optimal switching problem over a finite horizon:

V 0 = sup α∈A E T 0 f (X t , α t )dt + g(X T , α T ) - τn≤T c(X τn , ι n-1 , ι n ) .
(1.1)

Optimal switching problems can be seen as sequential optimal stopping problems belonging to the class of impulse control problems, and arise in many applied fields, for example in real option pricing in economics and finance. It has attracted a lot of interest during the past decades, and we refer to Chapter 5 in the book [START_REF] Pham | Continuous time stochastic control and optimization with financial applications[END_REF] and the references therein for a survey of some applications and results in this topic. It is well-known that optimal switching problems are related via the dynamic programming approach to a system of variational inequalities with inter-connected obstacles in the form:

min - ∂v i ∂t -b(x, i).D x v i - 1 2 tr(σ(x, i)σ(x, i) ′ D 2 x v i ) -f (x, i) , (1.2)
v i -max j =i (v j -c(x, i, j)) = 0 on [0, T ) × R d ,
together with the terminal condition v i (T, x) = g(x, i), for any i = 1, . . . , q. Here v i (t, x) is the value function to the optimal switching problem starting at time t ∈ [0, T ] from the state X t = x ∈ R d and the regime α t = i ∈ {1, . . . , q}, and the solution to the system (1.2) has to be understood in the weak sense, e.g. viscosity sense. The purpose of this paper is to solve numerically the optimal switching problem (1.1), and consequently the system of variational inequalities (1.2). These equations can be solved by analytical methods (finite differences, finite elements, etc ...), see e.g. [START_REF] Maroso | Analyse numérique de problèmes de contrôle stochastique[END_REF], but are known to require heavy computations, especially in high dimension. Alternatively, when the state process is uncontrolled, i.e. regime-independent, optimal switching problems are connected to multi-dimensional reflected Backward Stochastic Differential Equations (BSDEs) with oblique reflections, as shown in [START_REF] Hamadène | Switching problem and related system of reflected BSDEs[END_REF] and [START_REF] Hu | Multi-dimensional BSDE with oblique reflection and optimal switching[END_REF], and the recent paper [START_REF] Chassagneux | Discrete-time approximation of multidimensional BSDEs with oblique reflections[END_REF] introduced a discretely obliquely reflected numerical scheme to solve such BSDEs. From a computational viewpoint, there are rather few papers dealing with numerical experiments for optimal switching problems. The special case of two regimes for switching problems can be reduced to the resolution of a single BSDE with two reflecting barriers when considering the difference value process, and is exploited numerically in [START_REF] Hamadène | On the starting and stopping problem: application in reversible investments[END_REF]. We mention also the paper [START_REF] Carmona | Pricing asset scheduling flexibility using optimal switching[END_REF], which solves an optimal switching problem with three regimes by considering a cascade of reflected BSDEs with one reflecting barrier derived from an iteration on the number of switches.

We propose probabilistic numerical methods based on dynamic programming and optimal quantization methods combined with a suitable time discretization procedure for computing the solution to optimal multiple switching problem. Quantization methods were introduced in [START_REF] Bally | A quantization algorithm for solving discrete time multidimensional optimal stopping problems[END_REF] for solving variational inequality with given obstacle associated to optimal stopping problem of some diffusion process (X t ). The basic idea is the following. One first approximates the (continuous-time) optimal stopping problem by the Snell envelope for the Markov chain ( Xt k ) defined as the Euler scheme of the (uncontrolled) diffusion X, and then spatially discretize each random vector Xt k by a random vector taking finite values through a quantization procedure. More precisely, ( Xt k ) k is approximated by ( Xk ) k where Xk is the projection of Xt k on a finite grid in the state space following the closest neighbor rule. The induced L p -quantization error, Xt k -Xk p , depends only on the distribution of Xt k and the grid, which may be chosen in order to minimize the quantization error. Such an optimal choice, called optimal quantization, is achieved by the competitive learning vector quantization algorithm (or Kohonen algorithm) developed in full details in [START_REF] Bally | A quantization algorithm for solving discrete time multidimensional optimal stopping problems[END_REF]. One finally computes the approximation of the optimal stopping problem by a quantization tree algorithm, which mimics the backward dynamic programming of the Snell envelope. In this paper, we develop quantization methods to our general framework of optimal switching problem. With respect to standard optimal stopping problems, some new features arise on one hand from the regime-dependent state process, and on the other hand from the multiple switching times, and the discrete sum for the cumulated switching costs.

We first study a time discretization of the optimal switching problem by considering an Euler-type scheme with step h = T /m for the regime-dependent state process (X t ) controlled by the switching strategy α:

Xt k+1 = Xt k + b( Xt k , α t k )h + σ( Xt k , α t k )
√ h ϑ k+1 , t k = kh, k = 0, . . . , m, (1.3) where ϑ k , k = 1, . . . , m, are iid, and N (0, I d )-distributed. We then introduce the optimal switching problem for the discrete-time process ( Xt k ) controlled by switching strategies with stopping times valued in the discrete time grid {t k , k = 0, . . . , m}. The convergence of this discrete-time problem is analyzed, and we prove that the error is in general of order h 1 2 -ε , and this estimate holds true with ε = 0, as for optimal stopping problems, when the switching costs c(i, j) do not depend on the state process. Arguments of the proof rely on a regularity result of the controlled diffusion with respect to the switching strategy, and moment estimates on the number of switches. This extends the convergence rate result in [START_REF] Chassagneux | Discrete-time approximation of multidimensional BSDEs with oblique reflections[END_REF] derived in the case where X is regime-independent.

Next, we propose approximation schemes by quantization for computing explicitly the solution to the discrete-time optimal switching problem. Since the controlled Markov chain ( Xt k ) k cannot be directly quantized as in standard optimal stopping problems, we adopt a Markovian quantization approach in the spirit of [START_REF] Pagès | Optimal quantization methods and applications to numerical problems in finance[END_REF], by considering an optimal quantization of the Gaussian random vector ϑ k+1 arising in the Euler scheme (1.3). A quantization tree algorithm is then designed for computing the approximating value function, and we provide error estimates in terms of the quantization errors ϑ k -θk p and state space grid parameters. Alternatively, in the case of regime-independent state process, we propose a quantization algorithm in the vein of [START_REF] Bally | A quantization algorithm for solving discrete time multidimensional optimal stopping problems[END_REF] based on marginal quantization of the uncontrolled Markov chain ( Xt k ) k . A priori L p -error estimates are also established in terms of quantization errors Xt k -Xk p . Finally, some numerical tests on the two quantization algorithms are performed for an optimal switching problem with two regimes.

The plan of this paper is organized as follows. Section 2 formulates the optimal switching problem and sets the standing assumptions. We also show some preliminary results about moment estimates on the number of switches. We describe in Section 3 the time discretization procedure, and study the rate of convergence of the discrete-time approximation for the optimal switching problem. Section 4 is devoted to the approximation schemes by quantization for the explicit computation of the value function to the discrete-time optimal switching problem, and to the error analysis. Finally, we illustrate our results with some numerical tests in Section 5.

Optimal switching problem 2.1 Formulation and assumptions

We formulate the finite horizon multiple switching problem. Let us fix a finite time T ∈ (0, ∞), and some filtered probability space (Ω, F, F = (F t ) t≥0 , P) satisfying the usual conditions. Let I q = {1, . . . , q} be the set of all possible regimes (or activity modes). A switching control is a double sequence α = (τ n , ι n ) n≥0 , where (τ n ) is a nondecreasing sequence of stopping times, and ι n are F τn -measurable random variables valued in I q . The switching control α = (τ n , ι n ) is said to be admissible, and denoted by α ∈ A, if there exists an integer-valued random variable N with τ N > T a.s. Given α = (τ n , ι n ) n≥0 ∈ A, we may then associate the indicator of the regime value defined at any time t ∈ [0, T ] by

I t = ι 0 1 {0≤t<τ 0 } + n≥0 ι n 1 {τn≤t<τ n+1 } ,
which we shall sometimes identify with the switching control α, and we introduce N (α) the (random) number of switches before T :

N (α) = # n ≥ 1 : τ n ≤ T .
For α ∈ A, we consider the controlled regime-switching diffusion process valued in R d , governed by the dynamics

dX s = b(X s , I s )ds + σ(X s , I s )dW s , X 0 = x 0 ∈ R d , (2.1)
where W is a standard d-dimensional Brownian motion on (Ω, F, F = (F t ) 0≤t≤T , P). We shall assume that the coefficients b i = b(., i): R d → R d , and σ i (.) = σ(., i) : R d → R d×d , i ∈ I q , satisfy the usual Lipschitz conditions. We are given a running reward, terminal gain functions f, g : R d × I q → R, and a cost function c : R d × I q × I q → R, and we set f i (.) = f (., i), g i (.) = g(., i), c ij (.) = c(., i, j), i, j ∈ I q . We shall assume the Lipschitz condition:

(Hl) The coefficients f i , g i and c ij , i, j ∈ I q are Lipschitz continuous on R d .

We also make the natural triangular condition on the functions c ij representing the instantaneous cost for switching from regime i to j:

(Hc) c ii (.) = 0, i ∈ I q , inf x∈R d c ij (x) > 0, for i, j ∈ I q , j = i, inf x∈R d c ij (x) + c jk (x) -c ik (x)] > 0, for i, j, k ∈ I q , j = i, k.
The triangular condition on the switching costs c ij in (Hc) means that when one changes from regime i to some regime j, then it is not optimal to switch again immediately to another regime, since it would induce a higher total cost, and so one should stay for a while in the regime j.

The expected total profit over [0, T ] for running the system with the admissible switching control α = (τ n , ι n ) ∈ A is given by:

J 0 (α) = E T 0 f (X t , I t )dt + g(X T , I T ) - N (α) n=1 c(X τn , ι n-1 , ι n ) .
The maximal profit is then defined by

V 0 = sup α∈A J 0 (α).
(

The dynamic version of this optimal switching problem is formulated as follows. For (t, i) ∈ [0, T ] × I q , we denote by A t,i the set of admissible switching controls α = (τ n , ι n ) starting from i at time t, i.e. τ 0 = t, ι 0 = i. Given α ∈ A t,i , and x ∈ R d , and under the Lipschitz conditions on b, σ, there exists a unique strong solution to (2.1) starting from x at time t, and denoted by {X t,x,α s , t ≤ s ≤ T }. It is then given by

X t,x,α s = x + τn≤s τ n+1 ∧s τn b ιn (X t,x,α u )du + τ n+1 ∧s τn σ ιn (X t,x,α u )dW u , t ≤ s ≤ T.(2.
3)

The value function of the optimal switching problem is defined by

v i (t, x) = sup α∈A t,i E T t f (X t,x,α s , I s )ds + g(X t,x,α T , I T ) - N (α) n=1 c(X t,x,α τn , ι n-1 , ι n ) ,(2.4) for any (t, x, i) ∈ [0, T ] × R d × I q , so that V 0 = max i∈Iq v i (0, x 0 ).
For simplicity, we shall also make the assumption

g i (x) ≥ max j∈Iq [g j (x) -c ij (x)], ∀(x, i) ∈ R d × I q . (2.5)
This means that any switching decision at horizon T induces a terminal profit, which is smaller than a no-decision at this time, and is thus suboptimal. Therefore, the terminal condition for the value function is given by:

v i (T, x) = g i (x), (x, i) ∈ R d × I q .
Otherwise, it is given in general by v i (T, x) = max j∈Iq [g j (x)c ij (x)].

Notations

Preliminaries

We first show that one can restrict the optimal switching problem to controls α with bounded moments of N (α). More precisely, let us associate to a strategy α ∈ A t,i , the cumulated cost process C t,x,α defined by

C t,x,α u = n≥1 c(X t,x,α τn , ι n-1 , ι n )1 τn≤u , t ≤ u ≤ T.
We then consider for x ∈ R d and a positive sequence K = (K p ) p∈N the subset A K t,i (x) of A t,i defined by

A K t,i (x) = α ∈ A t,i : E C t,x,α T p ≤ K p (1 + |x| p ), ∀p ≥ 1 .
In the sequel, we shall assume that for each (t, x, i) ∈ [0, T ] × R d × I q , the optimal switching problem v i (t, x) admits an optimal strategy α * satisfying E |C t,x,α * T | 2 < ∞. The existence of an optimal strategy α * with E|C t,x,α * T | 2 < ∞ is a wide assumption that is valid under (Hl) and (Hg) in the case where the diffusion X is not controlled i.e. the functions b and σ do not depend on the variable i and the function c does not depend on the variable x, as shown in Theorem 3.1 of [START_REF] Hu | Multi-dimensional BSDE with oblique reflection and optimal switching[END_REF]. Proposition 2.1 Assume that (Hl) and (Hc) holds. Then there exists a positive sequence K = ( Kp ) p such that

v i (t, x) = sup α∈A K t,i (x) E T t f (X t,x,α s , I s )ds + g(X t,x,α T , I T ) - N (α) n=1 c(X t,x,α τn , ι n-1 , ι n ) (2.6) for any (t, x, i) ∈ [0, T ] × R d × I q .
Remark 2.1 Under the uniformly strict positive condition on the switching costs in (Hc), there exists some positive constant η > 0 s.t. N (α) ≤ ηC t,x,α T for any (t, x, i) ∈ [0, T ]×R d ×I q , α ∈ A t,i . Thus, for any α ∈ A K t,i (x), we have

E N (α) p ≤ ηK p (1 + |x| p ),
which means that in the value functions v i (t, x) of optimal switching problems, one can restrict to controls α for which the moments of N (α) are bounded by a constant depending on x.

Before proving Proposition 2.1, we need the following Lemmata.

Lemma 2.1 For all p ≥ 1, there exists a positive constant K p such that

sup α∈A t,i sup s∈[t,T ] X t,x,α s p ≤ K p (1 + |x|) , for all (t, x, i) ∈ [0, T ] × R d × I q .
Proof. Fix p ≥ 1. Then, we have from the definition of X t,x,α s in(2.3), for (t,

x, i) ∈ [0, T ] × R d × I q , α ∈ A t,i : E sup s∈[t,r] X t,
|v i (t, x)| ≤ K 1 + |x| , for all (t, x, i) ∈ [0, T ] × R d × I q .
Proof. Under the linear growth condition on f i , g i in (Hl), and the nonnegativity of the switching costs in (Hc), there exists some positive constant K s.t.

E T t f (X t,x,α s , I s )ds + g(X t,x,α T , I T ) - N (α) n=1 c(X t,x,α τn , ι n-1 , ι n ) ≤ K 1 + E sup u∈[0,T ] X t,x,α u , for all (t, x, i) ∈ [0, T ] × R d × I q , α ∈ A t , i.
By combining with the estimate in Lemma 2.1, this shows that

v i (t, x) ≤ K(1 + |x|) .
Moreover, by considering the strategy α 0 with no intervention i.e. N (α 0 ) = 0, we have

v i (t, x) ≥ E T t f (X t,x,α 0 s , i)ds + g(X t,x,α 0 T , i) ≥ -K 1 + E sup u∈[0,T ] X t,x,α u .
Again, by the estimate in Lemma 2.1, this proves that

v i (t, x) ≥ -K(1 + |x|) ,
and therefore the required linear growth condition on v i . 2

We now turn to the proof of the Proposition.

Proof of Proposition 2.1.

Fix (t, x, i) ∈ [0, T ] × R d × I q . Denote by α * = (τ * n , ζ * n ) n≥0 an optimal strategy associated to v i (t, x): v i (t, x) = E T t f (X t,x,α * s , I * s )ds + g(X t,x,α * T , I * T ) - N (α * ) n=1 c(X t,x,α * τn , ι * n-1 , ι * n ) . (2.7)
where I * is the indicator regime associated to α * . Consider the process (Y t,x,α * , Z t,x,α * ) solution to the following Backward Stochastic Differential Equation (BSDE)

Y t,x,α * u = g(X t,x,α * T , I * T ) + T u f (X t,x,α * s , I * s )ds (2.8) - T u Z t,x,α * s dW s -C t,x,α * T + C t,x,α * u , t ≤ u ≤ T
and satisfying the condition

E sup s∈[t,T ] |Y t,x,α * s | 2 + E T t |Z t,x,α * s | 2 ds < ∞.
Such a solution exists under (Hl), Lemma 2.1 and

E |C t,x,α * T | 2 < ∞.
Moreover, by taking expectation in (2.8) and from the dynamic programming principle for the value function in (2.7), we have

Y t,x,α * u = v I * u u, X t,x,α * u , t ≤ u ≤ T.
From Lemma 2.1 and 2.2, there exists for each p ≥ 1 a constant K p such that

E sup u∈[t,T ] |Y t,x,α * u | p ≤ K p 1 + |x| p . (2.9)
We now prove that there exists a sequence K = ( Kp ) p which does not depend on (t, x, i) such that

E |C t,x,α * T | p ≤ Kp (1 + |x| p ) . (2.10) Applying Itô's formula to |Y t,x,α * | 2 in (2.8), we have |Y t,x,α * t | 2 + T t |Z t,x,α * s | 2 ds = |g(X t,x,α * T , I * T )| 2 + 2 T t Y t,x,α * s f (X t,x,α * s , I * s )ds -2 T t Y t,x,α * s Z t,x,α * s dW s -2 T t Y t,x,α * s dC t,x,α * s .
Using (Hl) and the inequality 2ab ≤ a 2 + b 2 for a, b ∈ R, we get

T t |Z t,x,α * s | 2 ds ≤ K 1 + sup s∈[t,T ] |X t,x,α * s | 2 + sup s∈[t,T ] |Y t,x,α * s | 2 + |C t,x,α * T -C t,x,α * t | sup s∈[t,T ] |Y t,x,α * s | -2 T t Y t,x,α * s Z t,x,α * s dW s . (2.11)
Moreover, from (2.8), we have

|C t,x,α * T -C t,x,α * t | 2 ≤ K 1 + sup s∈[t,T ] |X t,x,α * s | 2 + sup s∈[t,T ] |Y t,x,α * s | 2 + T t Z t,x,α * s dW s 2 (2.12)
Combining (2.11) and (2.12) and using the inequality ab

≤ a 2 2ε + εb 2 2 , for a, b ∈ R and ε > 0, we obtain T t |Z t,x,α * s | 2 ds ≤ K (1 + ε) 1 + sup s∈[t,T ] |X t,x,α * s | 2 + sup s∈[t,T ] |Y t,x,α * s | 2 ε + 1 ε + ε T t Z t,x,α * s dW s 2 -2 T t Y t,x,α * s Z t,x,α * s dW s .
Elevating the previous estimate to the power p/2 and taking expectation, it follows from BDG inequality, Lemma 2.1 and (2.9) that

E T t |Z t,x,α * s | 2 ds p 2 ≤ K p (1 + ε p 2 ) 1 + E sup s∈[t,T ] |X t,x,α * s | p + ε p 2 + 1 ε p 2 E sup s∈[t,T ] |Y t,x,α * s | p + ε p 2 E T t Z t,x,α * s dW s p + E T t Y t,x,α * s Z t,x,α * s dW s p 2 ≤ K p (1 + |x| p ) 1 + ε p 2 + 1 ε p 2 + ε p 2 E T t |Z t,x,α * s | 2 ds p 2 + E T t |Y t,x,α * s Z t,x,α * s | 2 ds p 4
(2.13)

≤ K p (1 + |x| p ) 1 + ε p 2 + 1 ε p 2 + ε p 2 E T t |Z t,x,α * s | 2 ds p 2
, where we used again the inequality ab ≤ a 2 2ε + εb 2 2 for the last term in the r.h.s of (2.13). Taking ε small enough, this yields

E T t |Z t,x,α * s | 2 ds p 2 ≤ K p 1 + |x| p ,
Elevating now inequality (2.12) to the power p/2, and using the previous inequality together with BDG inequality, we get with the estimate of Lemma 2.1 and (2.9):

E|C t,x,α * T -C t,x,α * t | p ≤ Kp (1 + |x| p ), (2.14)
for some positive constant Kp . Since α * is optimal, and from the triangular condition in (Hc), we know that at the initial time t, there is at most one decision time τ * 1 . Thus, from the linear growth condition on the switching cost,

E[|C t,x,α * t | p ] ≤ Kp (1 + |x| p ), which implies with (2.14) that α * ∈ A K t,i
, and proves the required result. 2

In the sequel of this paper, we shall assume that (Hl) and (Hc) stand in force.

Time discretization

We first consider a time discretization of [0, T ] with time step h = T /m ≤ 1, and partition

T h = {t k = kh, k = 0, . . . , m}. For (t k , i) ∈ T h × I q , we denote by A h t k ,i the set of admissible switching controls α = (τ n , ι n ) n in A t k ,i
, such that τ n are valued in {ℓh, ℓ = k, . . . , m}, and we consider the value functions for the discretized optimal switching problem:

v h i (t k , x) = sup α∈A h t k ,i E m-1 ℓ=k f (X t k ,x,α t ℓ , I t ℓ )h + g(X t k ,x,α tm , I tm ) - N (α) n=1 c(X t k ,x,α τn , ι n-1 , ι n ) , (3.1)
for (t k , i, x) ∈ T h × I q × R d .
The next result provides an error analysis between the continuous-time optimal switching problem and its discrete-time version. Theorem 3.1 For any ε > 0, there exists a positive constant K ε (not depending on h) such that

|v i (t k , x) -v h i (t k , x)| ≤ K ε (1 + |x|)h 1 2 -ε , for all (t k , x, i) ∈ T h × R d × I q .
Moreover if the cost functions c ij , i, i ∈ I q , do not depend on x, then the previous inequality also holds for ε = 0.

Remark 3.1 For optimal stopping problems, it is known that the approximation by the discrete-time version gives an error of order h 1 2 , see e.g. [START_REF] Lamberton | Brownian optimal stopping and random walks[END_REF] and [START_REF] Bally | Error analysis of the quantization algorithm for obstacle problems[END_REF]. We recover this rate of convergence for multiple switching problems when the switching costs do not depend on the state process. However, in the general case, the error is of order h 1 2 -ε for any ε > 0. Such feature was showed in [START_REF] Chassagneux | Discrete-time approximation of multidimensional BSDEs with oblique reflections[END_REF] in the case of uncontrolled state process X, and is extended here when X may be influenced through its drift and diffusion coefficient by the switching control.

Before proving this Theorem, we need the two following lemmata. The first one deals with the regularity in time of the controlled diffusion uniformly in the control, and the second one deals with the regularity of the controlled diffusion with respect to the control. Lemma 3.1 For any p ≥ 1, there exists a constant K p such that

sup α∈A t k ,i max k≤ℓ≤m-1 sup s∈[t ℓ ,t ℓ+1 ] X t k ,x,α s -X t k ,x,α t ℓ p ≤ K p (1 + |x|)h 1 2 , for all x ∈ R d , i ∈ I q , k = 0, . . . , n.
Proof. Fix p ≥ 1. From the definition of X t,x,α in (2.3), we have for all (t k , x, i) ∈

T h × R d × I q and α ∈ A t k ,i , E sup u∈[t ℓ ,s] X t,x,α u -X t,x,α t ℓ p ≤ K p E s t ℓ |b Iu (X t,x,α u )|du p + E sup u∈[t ℓ ,s] u t ℓ σ Ir (X t,x,α r )dW r p , for all s ∈ [t ℓ , t ℓ+1 ].
From BDG and Jensen inequalities for p ≥ 2, we then have

E sup u∈[t ℓ ,s] X t,x,α u -X t,x,α t ℓ p ≤ K p h p 2 -1 E s t ℓ b Iu (X t,x,α u ) p du + E s t ℓ σ Iu (X t,x,α u ) p du ,
From the linear growth conditions on b i and σ i , for i ∈ I q , and Lemma 2.1, we conclude that the following inequality

E sup s∈[t ℓ ,t ℓ+1 ] X t,x,α s -X t,x,α t ℓ p ≤ K p (1 + |x| p )h p 2 ,
holds for p ≥ 2, and then also for p ≥ 1 by Hölder inequality. 2

For a strategy α = (τ n , ι n ) n ∈ A t k ,i we denote by α = (τ n , ιn ) n the strategy of

A h t k ,i defined by τn = min{t ℓ ∈ T h : t ℓ ≥ τ n } , ιn = ι n , n ∈ N.
The strategy α can be seen as the approximation of the strategy α by an element of A h t k ,i . We then have the following regularity result of the diffusion in the control α. Lemma 3.2 There exists a constant K such that

sup s∈[t k ,T ] X t k ,x,α s -X t k ,x, α s 2 ≤ K E[N (α) 2 ] 1 4 (1 + |x|)h 1 2 , for all x ∈ R d , i ∈ I q , k = 0, . . . , n and α ∈ A t k ,i .
Proof. From the definition of X t,x,α and X t,x, α, for (

t k , x, i) ∈ T h × R d × I q , α ∈ A K t k ,i
, we have by BDG inequality:

E sup u∈[t k ,s] X t,x,α s -X t,x, α s 2 ≤ K E s t k b(X t,x,α u , I u ) -b(X t,x, α u , Ĩu ) 2 du + E s t k σ(X t,x,α u , I u ) -σ(X t,x, α u , Ĩu ) 2 du ,
for all s ∈ [t k , T ]. Then using Lipschitz property of b i and σ i for i ∈ I q we get:

E sup u∈[t k ,s] X t,x,α s -X t,x, α s 2 ≤ K E s t k X t,x,α u -X t,x, α u 2 du + E s t k b(X t,x,α u , I u ) -b(X t,x,α u , Ĩu ) 2 du + E s t k σ(X t,x,α u , I u ) -σ(X t,x,α u , Ĩu ) 2 du ≤ K E s t k sup r∈[t k ,u] X t,x,α r -X t,x, α r 2 du (3.2) + E sup u∈[t k ,T ] X t,
E sup u∈[t k ,s] X t,x,α u -X t,x, α u 2 ≤ K E s t k sup r∈[t k ,u] X t,x,α r -X t,x, α r 2 du + E[N (α) 2 ] 1 2 (1 + |x| 2 )h , for all s ∈ [t k , T ].
We conclude with Gronwall's Lemma.

2

We are now ready to prove the convergence result for the time discretization of the optimal switching problem.

Proof of Theorem 3.1. We introduce the auxiliary function ṽh i defined by

ṽh i (t k , x) = sup α∈A h t k ,i E T t k f (X t k ,x,α s , I s )ds + g(X t k ,x,α T , I T ) - N (α) n=1 c(X t k ,x,α τn , ι n-1 , ι n ) , for all (t k , x) ∈ T h × R d . We then write |v i (t k , x) -v h i (t k , x)| ≤ |v i (t k , x) -ṽh i (t k , x)| + |ṽ h i (t k , x) -v h i (t k , x)| ,
and study each of the two terms in the right-hand side.

• Let us investigate the first term. By definition of the approximating strategy α = (τ n , ιn ) n ∈ A h t k ,i of α ∈ A t k ,i , we see that the auxiliary value function ṽh i may be written as

ṽh i (t k , x) = sup α∈A t k ,i E T t k f (X t k ,x, α s , Ĩs )ds + g(X t k ,x, α T , ĨT ) - N (α) n=1 c(X t k ,x, α τn , ιn-1 , ιn ) ,
where Ĩ is the indicator of the regime value associated to α. Fix now a positive sequence K = ( Kp ) p s.t. relation (2.6) in Proposition 2.1 holds, and observe that sup

α∈A K t k ,i (x) E T t k f (X t k ,x, α s , Ĩs )ds + g(X t k ,x, α T , ĨT ) - N (α) n=1 c(X t k ,x, α τn , ιn-1 , ιn ) ≤ ṽh i (t k , x) ≤ v i (t k , x) = sup α∈A K t k ,i (x) E T t k f (X t k ,x,α s , I s )ds + g(X t k ,x,α T , I T ) - N (α) n=1 c(X t k ,x,α τn , ι n-1 , ι n ) .
We then have

|v i (t k , x) -ṽh i (t k , x)| ≤ sup α∈A K t k ,i (x) ∆ 1 t k ,x (α) + ∆ 2 t k ,x (α) , (3.3)
with

∆ 1 t k ,x (α) = E T t k f (X t k ,x,α s , I s ) -f (X t k ,x, α s , Ĩs ) ds + g(X t k ,x,α T , I T ) -g(X t,x, α T , ĨT ) , ∆ 2 t k ,x (α) = E N (α) n=1 c(X t k ,x,α τn , ι n-1 , ι n ) -c(X t k ,x, α τn , ιn-1 , ιn ) .
Under (Hl), and by definition of α, there exists some positive constant K s.t.

∆ 1 t k ,x (α) ≤ K sup s∈[t k ,T ] E X t k ,x,α s -X t k ,x, α s + E sup s∈[t k ,T ] X t k ,x,α s + 1 T t k 1 Is = Ĩs ds . ≤ K sup s∈[t k ,T ] E X t k ,x,α s -X t k ,x, α s (3.4) + 1 + sup s∈[t k ,T ] X t k ,x,α s 2 E T t k 1 Is = Ĩs ds 1 2 ,
by Cauchy-Schwarz inequality. For α ∈ A K t k ,i (x), we have by Remark 2.1

E T t k 1 Is = Ĩs ds ≤ hE N (α) ≤ η K1 (1 + |x|)h,
for some positive constant η > 0. By using this last estimate together with Lemmata 2.1 and 3.2 into (3.4), we obtain the existence of some constant K s.t.

sup

α∈A K t k ,i (x) ∆ 1 t k ,x (α) ≤ K(1 + |x|)h 1 2 , (3.5) for all (t k , x, i) ∈ T h × R d × I q .
We now turn to the term ∆ 2 t,x (α). Under (Hl), and by definition of α, there exists some positive constant K s.t.

∆ 2 t k ,x (α) ≤ KE N (α) n=1 X t k ,x,α τn -X t k ,x, α τn ≤ K E N (α) n=1 X t k ,x,α τn -X t k ,x,α τn + E N (α) sup s∈[t k ,T ] X t k ,x,α s -X t k ,x, α s ≤ K E N (α) n=1 X t k ,x,α τn -X t k ,x,α τn + N (α) 2 sup s∈[t k ,T ] X t k ,x,α s -X t k ,x, α s 2 , (3.6)
by Cauchy-Schwarz inequality. For α ∈ A K t k ,i (x) with Remark 2.1, and from Lemma 3.2, we get the existence of some positive constant K s.t.

N (α) 2 sup s∈[t k ,T ] X t k ,x,α s -X t k ,x, α s 2 ≤ K(1 + |x|)h 1 2 . (3.7)
On the other hand, for any ε ∈ (0, 1], we have from Hölder inequality applied to expectation and Jensen's inequality applied to the summation:

E N (α) n=1 X t k ,x,α τn -X t k ,x,α τn ≤ E N (α) n=1 X t k ,x,α τn -X t k ,x,α τn 1 ε ε ≤ E |N (α)| 1 ε -1 N (α) n=1 X t k ,x,α τn -X t k ,x,α τn 1 ε ε ≤ 2 n-1 ℓ=k E |N (α)| 1 ε sup s∈[t ℓ ,t ℓ+1 ] X t,x,α s -X t,x,α t ℓ 1 ε ε ≤ 2 h ε N (α)| 2 ε max k≤ℓ≤m-1 sup s∈[t ℓ ,t ℓ+1 ] X t,x,α s -X t,x,α t ℓ 2 ε
by Cauchy-Schwarz inequality. By Lemma 3.1, this yields the existence of some positive constant K ε s.t.

E N (α) n=1 X t k ,x,α τn -X t k ,x,α τn ≤ K ε (1 + |x|)h 1 2 -ε . (3.8)
By plugging (3.7) and (3.8) into (3.6), we then get

∆ 2 t,x (α) ≤ K ε (1 + |x|)h 1 2 -ε . (3.9)
Combining (3.5) and (3.9), we obtain with (3.3)

|v i (t k , x) -ṽh i (t k , x)| ≤ K ε (1 + |x|)h 1 2 -ε .
In the case where c does not depend on the variable x, we have ∆ 2 t,x (α) = 0, and so by (3.3), (3.5):

|v i (t k , x) -ṽh i (t k , x)| ≤ K(1 + |x|)h 1 2 .
• For the second term, we have by definition of v h i and ṽh i :

|ṽ h i (t k , x) -v h i (t k , x)| ≤ sup α∈A h t k ,i E m-1 ℓ=k t ℓ+1 t ℓ f (X t,x,α s , I s ) -f (X t,x,α t ℓ , I s ) ds , since I s = I t ℓ on [t ℓ , t ℓ+1
). Under (Hl), we get

|ṽ h i (t k , x) -v h i (t k , x)| ≤ K sup α∈A h t k ,i max k≤ℓ≤m-1 sup s∈[t ℓ ,t ℓ+1 ] E X t,x,α s -X t,x,α t ℓ ,
for some positive constant K, and by Lemma 3.1, this shows that

|ṽ h i (t k , x) -v h i (t k , x)| ≤ K(1 + |x|)h 1 2 .
2

In a second step, we approximate the continuous-time (controlled) diffusion by a discretetime (controlled) Markov chain following an Euler type scheme. For any (t k , x, i)

∈ T h × R d × I q , α ∈ A h t k ,i , we introduce ( Xh,t k ,x,α t ℓ
) k≤ℓ≤m defined by:

Xh,t k ,x,α t k = x, Xh,t k ,x,α t ℓ+1 = F h It ℓ ( Xh,t k ,x,α t ℓ , ϑ ℓ+1 ), k ≤ ℓ ≤ m -1,
where

F h i (x, ϑ k+1 ) = x + b i (x)h + σ i (x) √ h ϑ k+1 ,
and

ϑ k+1 = (W t k+1 -W t k )/ √ h, k = 0, . . . ,
≤ K p (1 + |x|), (3.10)
for some positive constant K p , not depending on (h, t k , x, i). Moreover, one can also derive the standard estimate for the Euler scheme, as e.g. in section 10.2 of [START_REF] Kloeden | Numerical solution of stochastic differential equations[END_REF]:

sup α∈A h t k ,i max ℓ=k,...,m X t k ,x,α t ℓ -Xh,t k ,x,α t ℓ p ≤ K p (1 + |x|) √ h. (3.11)
We then associate to the Euler controlled Markov chain, the value functions vh i , i ∈ I q , for the optimal switching problem:

vh i (t k , x) = sup α∈A h t k ,i E m-1 ℓ=k f ( Xh,t k ,x,α t ℓ , I t ℓ )h + g( Xh,t k ,x,α tm , I tm ) - N (α) n=1 c( Xh,t k ,x,α τn , ι n-1 , ι n ) . (3.12)
The next result provides the error analysis between v h i by vh i , and thus of the continuous time optimal switching problem v i by its Euler discrete-time approximation vh i .

Theorem 3.2 There exists a constant K (not depending on h) such that

v h i (t k , x) -vh i (t k , x) ≤ K(1 + |x|) √ h, (3.13
)

for all (t k , x, i) ∈ T h × R d × I q .
Remark 3.2 The above theorem combined with Theorem 3.1 gives the rate of convergence for the approximation of the continuous time optimal switching problem by its Euler discrete-time version: For any ε > 0, there exists a positive constant K ε s.t.

|v i (t k , x) -vh i (t k , x)| ≤ K ε (1 + |x|)h 1 2 -ε , (3.14)
for all (t k , x, i) ∈ T h × R d × I q . Moreover if the cost functions c ij , i, i ∈ I q , do not depend on x, then the previous inequality also holds for ε = 0.

Proof of Theorem 3.2.

• Step 1. For (t k , x, i) ∈ T h × R d × I q , denote
by α h, * (resp. ᾱh, * ) the optimal switching strategy corresponding to v h i (t k , x) (resp. vh i (t k , x)). Let us prove that there exists some constant K, not depending on (t k , x, i, h), such that

E N (α h, * ) 2 + E N ( ᾱh, * ) 2 ≤ K(1 + |x| 2 ). (3.15)
We use discrete-time arguments, which are analog to the continuous-time case in the proof of Proposition 2.1. For α h, * optimal strategy to v h i (t k , x) with corresponding indicator regime I h, * , and to alleviate notations, we denote by

Y ℓ = v h I h, * t ℓ (t k , X t k ,x,α h, * t ℓ ), F ℓ = f (X t k ,x,α h, * t ℓ , I h, * t ℓ ), c ℓ = c(X t k ,x,α h, * t ℓ
, I h, * t ℓ-1 , I h, * t ℓ ), for ℓ = k, . . . , m. From the estimates on X t k ,x,α t ℓ in Lemma 2.1, we know that

E sup k≤ℓ≤m |Y ℓ | 2 + |F ℓ | 2 + |c ℓ | 2 ≤ K(1 + |x| 2 ), (3.16)
for some positive constant K. Moreover, by the DPP for the value function v h i , we have :

Y ℓ = E [Y ℓ+1 |F t ℓ ] + hF ℓ -c ℓ , ℓ = k, . . . , m -1. Letting ∆M ℓ+1 := Y ℓ+1 -E[Y ℓ+1 |F t ℓ ], we obtain in particular m-1 ℓ=k c ℓ = h m-1 ℓ=k F ℓ - m-1 ℓ=k ∆M ℓ+1 + (Y m -Y k ),
and so by (3.16)

E m ℓ=k c ℓ 2 ≤ K(1 + |x| 2 ) + 3 E   m-1 ℓ=k ∆M ℓ+1 2   = K(1 + |x| 2 ) + 3 E m-1 ℓ=k ∆M 2 ℓ+1 .
(3.17)

Now by writing that

Y 2 m -Y 2 0 = m-1 ℓ=k Y 2 ℓ+1 -Y 2 ℓ = m-1 ℓ=k (Y ℓ+1 -Y ℓ )(Y ℓ+1 + Y ℓ ) = m-1 ℓ=k (∆M ℓ+1 -hF ℓ + c ℓ )(2Y ℓ + ∆M ℓ+1 -hF ℓ + c ℓ ), we get m-1 ℓ=k ∆M 2 ℓ+1 = Y 2 m -Y 2 0 - m-1 ℓ=0 hF ℓ (hF ℓ -2Y ℓ -2c l ) -2 m-1 ℓ=0 c l Y l - m-1 ℓ=0 ∆M ℓ+1 (2Y ℓ -2hF ℓ + 2c ℓ ) - m-1 ℓ=0 c 2 ℓ .
Since E ∆M ℓ+1 |F t ℓ = 0, this shows that

E m-1 ℓ=k ∆M 2 ℓ+1 ≤ E Y 2 m - m-1 ℓ=0 hF ℓ (hF ℓ -2Y ℓ -2c ℓ ) -2 m-1 ℓ=0 c ℓ Y ℓ ≤ K(1 + |x| 2 ) + 2E m-1 ℓ=0 c ℓ Y ℓ , (3.18)
where we used again (3.16). Now since c ℓ ≥ 0,

E m-1 ℓ=0 c ℓ Y ℓ ≤ E m-1 ℓ=0 c ℓ sup k≤ℓ≤m-1 |Y ℓ | ≤ εE m-1 ℓ=k ∆M 2 ℓ+1 + K 1 + 1 ε (1 + |x| 2 ),
for all ε > 0, by (3.16), (3.17) and Cauchy-Schwarz inequality. Hence taking ε small enough and plugging this estimate into (3.18), we obtain

E m-1 ℓ=k ∆M 2 ℓ+1 ≤ K(1 + |x| 2 ).
Using (3.17) one more time and recalling that N (α h, * ) ≤ η ℓ c ℓ for some η > 0 under the uniformly lower bound condition in (Hc), we thus obtain

E N (α h, * ) 2 ≤ K(1 + |x| 2 ).
The proof for N ( ᾱh, * ) is the same, by using estimate (3.10) on Xh,t k ,x,α t ℓ

. • Step 2. By

Step 1, the supremum in the definitions (3.1) and (3.12) of v h i (t k , x) and vh i (t k , x) can be taken over

A h,K t k ,i (x) = α ∈ A h t k ,i s.t. E|N (α)| 2 ≤ K(1 + |x| 2 )
. Now, for any α ∈ A h,K t k ,i (x), we have under (Hl) and by Cauchy-Schwarz inequality

E m-1 ℓ=k h f (X t k ,x,α t ℓ , I t ℓ ) -f ( Xh,t k ,x,α t ℓ , I t ℓ ) + g(X t k ,x,α tm , I tm ) -g( Xh,t k ,x,α tm , I tm ) + N (α) n=1 c(X t k ,x,α τn , ι n-1 , ι n ) -c( Xh,t k ,x,α τn , ι n-1 , ι n ) ≤ KE (1 + N (α)) sup k≤ℓ≤m X t k ,x,α t ℓ -Xh,t k ,x,α t ℓ ≤ K(1 + |x|) sup k≤ℓ≤m X t k ,x,α t ℓ -Xh,t k ,x,α t ℓ 2 ≤ K(1 + |x| 2 ) √ h, (3.19)
by (3.11). Taking the supremum over α ∈ A h,K t k ,i (x) into (3.19), this shows that

v h i (t k , x) -vh i (t k , x) ≤ K(1 + |x| 2 ) √ h.

4 Approximation schemes by optimal quantization

In this section, for a fixed time discretization step h, we focus on a computational approximation for the value functions vh i , i ∈ I q , defined in (3.12). To alleviate notations, we shall often omit the dependence on h in the superscripts, and write e.g. vi = vh i . The corresponding dynamic programming relation for vi is written in the backward induction:

vi (t m , x) = g i (x), vi (t k , x) = max E vi (t k+1 , Xt k ,x,i t k+1 ) + f i (x)h , max j =i [v j (t k , x) -c ij (x)] ,
for k = 0, . . . , m -1, (i, x) ∈ I q × R d , where Xt k ,x,i is the solution to the Euler scheme:

Xt k ,x,i t k+1 = F h i (x, ϑ k+1 ) := x + b i (x)h + σ i (x) √ h ϑ k+1 .
Observe that under the triangular condition on the switching costs c ij in (Hc), these backward relations can be written as an explicit discrete-time scheme:

vi (t m , x) = g i (x) (4.1) vi (t k , x) = max j∈Iq E vj (t k+1 , Xt k ,x,j t k+1 ) + f j (x)h -c ij (x) , (4.2)
for k = 0, . . . , m -1, (i, x) ∈ I q × R d . Next, the practical implementation for this scheme requires a computational approximation of the expectations arising in the above dynamic programming formulae, and a space discretization for the state process X valued in R d . We shall propose two numerical approximations schemes by optimal quantization methods, the second one in the particular case where the state process X is not controlled by the switching control.

A Markovian quantization method

Let X be a bounded lattice grid on R d with step δ/d and size R, namely X = (δ/d)Z d ∩ B(0, R) = {x ∈ R d : x = (δ/d)z for some z ∈ Z d , and |x| ≤ R}. We then denote by Proj X the projection on the grid X according to the closest neighbour rule, which satisfies

|x -Proj X (x)| ≤ max(|x| -R, 0) + δ, ∀x ∈ R d . (4.3)
At each time step t k ∈ T h , and point space-grid x ∈ X, we have to compute in (4.2) expectations in the form E ϕ( Xt k ,x,i t k+1 ) , for ϕ(.) = vh i (t k+1 , .), i ∈ I q . We shall then use an optimal quantization for the Gaussian random variable ϑ k+1 , which consists in approximating the distribution of ϑ ; N (0, I d ) by the discrete law of a random variable θ of support N points w l , l = 1, . . . , N , in R d , and defined as the projection of ϑ on the grid {w 1 , . . . , w N } following the closest neighbor rule. The grid {w 1 , . . . , w N } is optimized in order to minimize the distorsion error, i.e. the quadratic L 2 -norm ϑ -θ 2 . This optimal grid and the associated weights {π 1 , . . . , π N } are downloaded from the website: "http://www.quantize.mathsfi.com/downloads". We refer to the survey article [START_REF] Pagès | Optimal quantization methods and applications to numerical problems in finance[END_REF] for more details on the theoretical and computational aspects of optimal quantization methods. In the vein of [START_REF] Pagès | An optimal Markovian quantization algorithm for multi-dimensional stochastic control problem[END_REF], we introduce the quantized Euler scheme:

Xt k ,x,i t k+1 = Proj X (F h i (x, θ)),
and define the value functions vi on T m × X, i ∈ I q in backward induction by

vi (t m , x) = g i (x) vi (t k , x) = max j∈Iq E vj (t k+1 , Xt k ,x,j t k+1 ) + f j (x)h -c ij (x) , k = 0, . . . , m -1.
This numerical scheme can be computed explicitly according to the following recursive algorithm:

vi (t m , x) = g i (x), (x, i) ∈ X × I q vi (t k , x) = max j∈Iq N l=1 π l vj t k+1 , Proj X (F h j (x, w l )) + f j (x)h -c ij (x) , (x, i) ∈ X × I q ,
for k = 0, . . . , m-1. At each time step, we need to make O(N ) computations for each point of the grid X. Therefore, the global complexity of the algorithm is of order O(mN (R/δ) d ).

The main result of this paragraph is to provide an error analysis and rate of convergence for the approximation of vi by vi . Theorem 4.1 There exists a constant K (not depending on h) such that

vi (t k , x) -vi (t k , x) ≤ K exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h δ h + h -1/2 ϑ -θ 2 1 + |x| + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + ( δ h ) 2 ,
for all (t k , x, i) ∈ T h × X × I q . In the case where the switching costs c ij do not depend on x, the above estimation is stengthened into:

vi (t k , x) -vi (t k , x) ≤ K h -1/2 ϑ -θ 2 exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + δ h 2 .
Remark 4.1 The estimation in Theorem 4.1 consists of error terms related to

• the space discretization parameters δ, R, which have to be chosen s.t. δ/h and 1/Rh go to zero.

• the quantization error ϑ -θ p of the normal distribution N (0, I d ), which converges to zero at a rate N 1 d , where N is the number of grid points chosen s.t. h

-1 2 N -1 d goes to zero.
By combining with the discrete-time approximation error (3.14), and by choosing grid parameters δ, 1/R of order h 3 2 , and a number of points N of order 1/h d , we see that the error estimate between the value function of the continuous-time optimal switching problem and its approximation by Markovian quantization is of order h 1 2 . With these values of the parameters, we then see that the complexity of this Markovian quantization algorithm is of order O(1/h 4d+1 ).

Let us now focus on the proof of Theorem 4.1. First, notice from the dynamic programming principle that the value functions vi , i ∈ I q , admit the Markov control problem representation:

vi (t k , x) = sup α∈A h t k ,i E m-1 ℓ=k f ( Xt k ,x,α t ℓ , I t ℓ )h + g( Xt k ,x,α tm , I tm ) - N (α) n=1 c( Xt k ,x,α τn , ι n-1 , ι n ) , (4.4)
where Xt k ,x,α is defined by

Xt k ,x,α t k = x, Xt k ,x,α t ℓ+1 = Proj X F h It ℓ ( Xt k ,x,α t ℓ , θℓ+1 ) , k ≤ ℓ ≤ m -1, for α ∈ A h t k ,i
, and θk+1 , k = 0, . . . , m -1, are iid, θ-distributed, and independent of F t k . We first prove several estimates on Xt k ,x,α . Lemma 4.1 For each p ≥ 1 there exists a constant K p (not depending on h) such that sup

α∈A h t k ,i ,k≤ℓ≤m Xt k ,x,α t ℓ p + sup α∈A h t k ,i ,k≤ℓ≤m-1 F h It ℓ Xt k ,x,α t ℓ , θk+1 p (4.5) ≤ K p exp K p h -1/2 ϑ -θ p 1 + |x| + δ h , for all (t k , x, i) ∈ T h × X × I q .
Proof. We fix (t k , x, i) ∈ T h × X × I q , α ∈ A h t k ,i , and denote Xt ℓ = Xt k ,x,α t ℓ

, k ≤ ℓ ≤ m. First by standard estimates on solutions to SDEs, we have

F h It ℓ ( Xt ℓ , ϑ ℓ+1 ) p ≤ e Kph Xt ℓ p + K p h. (4.6)
Then, by using the linear growth property of σ and the fact that θℓ+1 , ϑ ℓ+1 are independent of Xt ℓ , we obtain

F h It ℓ ( Xt ℓ , ϑ ℓ+1 ) -F h It ℓ ( Xt ℓ , θℓ+1 ) p ≤ Kh 1/2 1 + Xt ℓ p ϑ -θ p . ( 4
+ K p h + Kh 1/2 Xt ℓ p + 1 ϑ -θ p ≤ e Kph (1 + Kh 1/2 ϑ -θ p ) Xt ℓ p + K p h + δ + Kh 1/2 ϑ -θ p .
By induction, recalling that h T m , and since 1 + y m m ≤ e y for all y ≥ 0, we obtain

Xt ℓ p ≤ K p exp K p h -1/2 ϑ -θ p 1 + |x| + δ h + h -1/2 ϑ -θ p ≤ K p exp K ′ p h -1/2 ϑ -θ p 1 + |x| + δ h ,
for all k ≤ ℓ ≤ m. The estimate for F h ( Xt ℓ , ϑ ℓ+1 ) then follows from (4.6). 2

Lemma 4.2 There exists some constant K (not depending on h) such that sup

α∈A h t k ,i sup k≤ℓ≤m Xt k ,x,α t ℓ -Xt k ,x,α t ℓ 2 ≤ K h -1/2 ϑ -θ 2 exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + δ h 2 , (4.8
)

for all (t k , x, i) ∈ T h × X × I q .
Proof. As before we fix (t k , x, i), α and omit the dependence on (t k , x, i, α) in Xt ℓ . Let us first show an estimate on Xt ℓ+1 -

Xt ℓ+1 2 . For k ≤ ℓ ≤ m -1, we get Xt ℓ+1 -Xt ℓ+1 2 ≤ Xt ℓ+1 -F h It ℓ ( Xt ℓ , θℓ+1 ) 2 + F h It ℓ ( Xt ℓ , θℓ+1 ) -F h It ℓ ( Xt ℓ , ϑ ℓ+1 ) 2 + F h It ℓ ( Xt ℓ , ϑ ℓ+1 ) -F h It ℓ ( Xt ℓ , ϑ ℓ+1 ) 2 . (4.9)
On the other hand, since

y -Proj X (y) ≤ δ + |y|1 {|y|≥R} ≤ δ + |y| 2 R ,
by inequality (4.3), we have

Xt ℓ+1 -F h It ℓ ( Xt ℓ , θℓ+1 ) 2 ≤ δ + Xt ℓ 2 4 R . (4.10)
Furthermore by standard estimates for the Euler scheme (see e.g. Lemma A.1 in [START_REF] Pagès | An optimal Markovian quantization algorithm for multi-dimensional stochastic control problem[END_REF]), we have

F h It ℓ ( Xt ℓ , ϑ ℓ+1 ) -F h It ℓ ( Xt ℓ , ϑ ℓ+1 ) 2 ≤ (1 + Kh) Xt ℓ -Xt ℓ 2 .
Plugging these last two inequalities and (4.7) into (4.9), we get :

Xt ℓ+1 -Xt ℓ+1 2 ≤ (1 + Kh) Xt ℓ -Xt ℓ 2 + Kh 1/2 Xt ℓ 2 + 1 ϑ -θ 2 + δ + Xt ℓ 2 4 R .
Finally since Xt k = Xt k = x, we obtain by induction, and using the estimates (4.5) on Xt ℓ 4 :

Xt ℓ -Xt ℓ 2 ≤ K h -1/2 ϑ -θ 2 exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + δ h 2 , (4.11)
for all k ≤ ℓ ≤ m. Now by definition of Xt k , Xt k , we may write for k ≤ ℓ ≤ m -1:

Xt ℓ+1 -Xt ℓ+1 = ( Xt ℓ -Xt ℓ ) + h b( Xt ℓ , I t ℓ ) -b( Xt ℓ , I t ℓ ) + √ h σ( Xt ℓ , I t ℓ ) θℓ+1 -σ( Xt ℓ , I t ℓ )ϑ ℓ+1 + Proj X F h It ℓ Xt ℓ , θℓ+1 ) -F h It ℓ Xt ℓ , θℓ+1 , Since Xt k = Xt k (= x)
, we obtain by induction:

sup k≤ℓ≤m Xt ℓ -Xt ℓ 2 ≤ h m-1 ℓ=k b( Xt ℓ , I t ℓ ) -b( Xt ℓ , I t ℓ ) 2 + √ h sup k≤ℓ≤m r≤ℓ σ( Xtr , I tr ) θr+1 -σ( Xtr , I tr )ϑ r+1 2 + m-1 ℓ=k Proj X F h It ℓ ( Xt ℓ , θℓ+1 ) -F h It ℓ Xt ℓ , θℓ+1 2 . (4.12)
We now bound each of the three terms in the right hand side of (4.12). First, by the Lipschitz property of b and (4.11), we have

h m-1 ℓ=k b( Xt ℓ , I t ℓ ) -b( Xt ℓ , I t ℓ ) 2 ≤ K h -1/2 ϑ -θ 2 exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + δ h 2 .
Next, recalling that θℓ+1 is independent of F t ℓ , with distribution law θ, and since θ is an optimal L 2 -quantizer of ϑ, it follows that E[ θℓ+1

|F t ℓ ] = E[ θ] = E[ϑ] = 0.
Thus, the process ( r≤ℓ σ( Xtr , I tr ) θr+1σ( Xtr , I tr )ϑ r+1 ) ℓ is a F t ℓ -martingale, and from Doob's inequality, we have:

sup k≤ℓ≤m r≤ℓ σ( Xtr , I tr ) θr+1 -σ( Xtr , I tr )ϑ r+1 2 ≤ K E m-1 ℓ=k σ( Xt ℓ , I t ℓ ) θℓ+1 -σ( Xt ℓ , I t ℓ )ϑ ℓ+1 2 1 2 .
By writing from the Lipschitz condition on σ i that

σ( Xt ℓ , I t ℓ ) θℓ+1 -σ( Xt ℓ , I t ℓ )ϑ ℓ+1 2 ≤ K Xt ℓ -Xt ℓ 2 ϑ ℓ+1 2 + 1 + Xt ℓ 2 ϑ ℓ+1 -θℓ+1 2 ,
and since ϑ ℓ+1 , θℓ+1 are independent of F t ℓ , we then obtain

√ h sup k≤ℓ≤m r≤ℓ σ( Xtr , I tr ) θr+1 -σ( Xtr , I tr )ϑ r+1 2 ≤ K sup k≤ℓ≤m-1 Xt ℓ -Xt ℓ 2 + 1 + Xt ℓ 2 ϑ -θ 2 ≤ K h -1/2 ϑ -θ 2 exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + δ h 2 ,
where we used the estimates (4.5) and (4.11). Finally the third term in (4.12) is bounded as before by (4.10). 2

Proof of Theorem 4.1. For (t k , x, i) ∈ T h × X × I q , denote by α * the optimal switching strategy corresponding to vi (t k , x). Then, similarly as in the derivation of (3.15), by using the estimation (4.5) for Xt k ,x,α t ℓ 2 , we get the existence of some constant K, not depending on (t k , x, i, h), such that

E N ( α * ) 2 ≤ K exp Kh -1/2 ϑ -θ 2 1 + |x| 2 + δ 2 h 2 .
Therefore, the supremum in the representation (3.1) of vi (t k , x) can be taken over the subset Âh,K

t k ,i (x) = α ∈ A h t k ,i s.t. E|N (α)| 2 ≤ K exp Kh -1/2 ϑ -θ 2 1 + |x| 2 + δ 2 h 2
. Then, for α ∈ Âh,K t k ,i (x), we have under (Hl) and by Cauchy-Schwarz inequality

E m-1 ℓ=k h f ( Xt k ,x,α t ℓ , I t ℓ ) -f ( Xt k ,x,α t ℓ , I t ℓ ) + g( Xt k ,x,α tm , I tm ) -g( Xt k ,x,α tm , I tm ) + N (α) n=1 c( Xt k ,x,α τn , ι n-1 , ι n ) -c( Xh,t k ,x,α τn , ι n-1 , ι n ) ≤ KE (1 + N (α)) sup k≤ℓ≤m Xt k ,x,α t ℓ -Xt k ,x,α t ℓ ≤ K exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h sup k≤ℓ≤m Xt k ,x,α t ℓ -Xt k ,x,α t ℓ 2 ≤ K exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h δ h + h -1/2 ϑ -θ 2 1 + |x| + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + δ h 2 , (4.13)
by Lemma 4.2. Taking the supremum over α ∈ Âh,K t k ,i (x) in the above inequality, we obtain an estimate for |v i (t k , x)vi (t k , x)| with an upper bound given by the r.h.s. of (4.13), which gives the required result.

Finally, notice that in the special case where the switching cost functions c ij do not depend on x, we have

vi (t k , x) -vi (t k , x) ≤ sup α∈A h t k ,i E m-1 ℓ=k h f ( Xt k ,x,α t ℓ , I t ℓ ) -f ( Xt k ,x,α t ℓ , I t ℓ ) + g( Xt k ,x,α tm , I tm ) -g( Xt k ,x,α tm , I tm ) ≤ K sup α∈A h t k ,i ,k≤ℓ≤m E Xt k ,x,α t ℓ -Xt k ,x,α t ℓ ≤ K h -1/2 ϑ -θ 2 exp Kh -1/2 ϑ -θ 2 1 + |x| + δ h + δ h + 1 Rh exp Kh -1/2 ϑ -θ 4 1 + |x| 2 + δ h 2 ,
by the estimate in Lemma 4.2. 2

Marginal quantization in the uncontrolled diffusion case

In this paragraph, we consider the special case where the diffusion X is not controlled, i.e. b i = b, σ i = σ. The Euler scheme for X, denoted by X, is given by:

X0 = X 0 , Xt k+1 = F h ( Xt k , ϑ k+1 ) := Xt k + b( Xt k )h + σ( Xt k ) √ h ϑ k+1 , k = 0, . . . , m -1,
where

ϑ k+1 = (W t k+1 -W t k )/ √ h, k = 0, . . . , m-1, are iid, N (0, I d )-distributed, independent of F t k .
Let us recall the well-known estimate: for any p ≥ 1, there exists some K p s.t.

Xt k p ≤ K p X 0 p . (4.14)
Notice that the backward dynamic programming formulae (4.1)-(4.2) for vi can be written in this case as:

vi (t m , .) = g i (.), i ∈ I q vi (t k , .) = max j∈Iq [P h vj (t k+1 , .) + hf j -c ij ]. (4.15)
Here P h is the probability transition kernel of the Markov chain X, given by:

P h ϕ(x) = E ϕ( Xt k+1 )| Xt k = x = E[ϕ(F h (x, ϑ))], (4.16)
where ϑ is N (0, I d )-distributed. Let us next consider the family of discrete-time processes ( Ȳ i t k ) k=0,...,m , i ∈ I q , defined by:

Ȳ i t k = vi (t k , Xt k ), k = 0, . . . , m, i ∈ I q .
Remark 4.2 By the Markov property of the Euler scheme X w.r.t. (F t k ) k , we see that ( Ȳ i t k ) k=0,...,m , i ∈ I q , satisfy the backward induction:

Ȳ i tm = g i ( Xtm ) = g i ( XT ), i ∈ I q Ȳ i t k = max j∈Iq E Ȳ j t k+1 F t k + hf j ( Xt k ) -c ij ( Xt k ) , k = 0, . . . , m -1,
and is represented as

Ȳ i t k = ess sup α∈A h t k ,i E m-1 ℓ=k f ( Xt ℓ , I t ℓ )h + g( Xtm , I tm ) - N (α) n=1 c( Xτn , ι n-1 , ι n ) F t k .
On the other hand, the continuous-time optimal switching problem (2.4) admits a representation in terms of the following reflected Backward Stochastic Differential Equations (BSDE):

Y i t = g i (X T ) + T t f (X s )ds - T t Z i s dW s + K i T -K i t , i ∈ I q , 0 ≤ t ≤ T, Y i t ≥ max j =i [Y j t -c ij (X t )] and T 0 Y i t -max j =i [Y j t -c ij (X t )] dK i t = 0. (4.17)
We know from [START_REF] Djehiche | A finite horizon optimal multiple switching problem[END_REF], [START_REF] Hu | Multi-dimensional BSDE with oblique reflection and optimal switching[END_REF] or [START_REF] Hamadène | Switching problem and related system of reflected BSDEs[END_REF] that there exists a unique solution (Y, Z, K) = (Y i , Z i , K i ) i∈Iq solution to (4.17) with Y ∈ S 2 (R q ), the set of adapted continuous processes valued in

R q s.t. E[sup 0≤t≤T |Y t | 2 ] < ∞, Z ∈ M 2 (R q
), the set of predictable processes valued in R q s.t.

E[ T 0 |Z t | 2 dt] < ∞, and
K i ∈ S 2 (R), K i 0 = 0, K i is nondecreasing. Moreover, we have Y i t = v i (t, X t ), i ∈ I q , = ess sup α∈A t,i E T t f (X s , I s )ds + g(X T , I T ) - N (α) n=1 c(X τn , ι n-1 , ι n ) F t , 0 ≤ t ≤ T.
We recall from [START_REF] Chassagneux | Discrete-time approximation of multidimensional BSDEs with oblique reflections[END_REF] the error estimation: for any ε > 0, there exists some constant K ε s.t. max k=0,...,m

Y i t k -Ȳ i t k 2 ≤ K ε X 0 2 h 1 2 -ε ,
for all i ∈ I q , and ε can be chosen equal to zero when the switching costs c ij do not depend on x.

We propose now an optimal quantization method in the vein of [START_REF] Bally | Error analysis of the quantization algorithm for obstacle problems[END_REF] for optimal stopping problems, for a computational approximation of ( Ȳ i t k ) k=0,...,m . This is based on results about optimal quantization of each marginal distribution of the Markov chain ( Xt k ) 0≤k≤m . Let us recall the construction. For each time step k = 0, . . . , m, we are given a grid Γ k = {x 1 k , . . . , x N k k } of N k points in R d , and we define the quantizer Xk = Proj k ( Xt k ) of Xt k where Proj k denotes a closest neighbour projection on Γ k . For N k being fixed, the grid Γ k is said to be L p -optimal if it minimizes the L p -quantization error: Xt k -Proj k ( Xt k ) p . Optimal grids Γ k are produced by a stochastic recursive algorithm, called Competitive Learning Vector Quantization (or also Kohonen Algorithm), and relying on Monte-Carlo simulations of Xt k , k = 0, . . . , m. We refer to [START_REF] Pagès | Optimal quantization methods and applications to numerical problems in finance[END_REF] for details about the CLVQ algorithm. We also compute the transition weights

π ll ′ k = P[ Xk+1 = x l ′ k+1 | Xk = x l k ] = P ( Xt k+1 , Xt k ) ∈ C l ′ (Γ k+1 ) × C l (Γ k ) P Xt k ∈ C l (Γ k ) , where C l (Γ k ) ⊂ {x ∈ R d : |x -x l k | = min y∈Γ k |x -y|}, l = 1, . . . , N k
, is a Voronoi tesselation of Γ k . These weights can be computed either during the CLVQ phase, or by a regular Monte-Carlo simulation once the grids Γ k are settled. The associated discrete probability transition Pk from Xk to Xk+1 , k = 0, . . . , m -1, is given by:

Pk ϕ(x l k ) := N k+1 l ′ =1 π ll ′ k ϕ(x l ′ k+1 ) = E ϕ( Xk+1 ) Xk = x l k .
One then defines by backward induction the sequence of R q -valued functions vk = (v i k ) i∈Iq computed explicitly on Γ k , k = 0, . . . , m, by the quantization tree algorithm:

vi m = g i , i ∈ I q , vi k = max j∈Iq Pk vj k+1 + hf j -c ij , k = 0, . . . , m -1. (4.18)
The discrete-time processes ( Ȳ i t k ) k=0,...,m , i ∈ I q , are then approximated by the quantized processes ( Ŷ i k ) k=0,...,m , i ∈ I q defined by

Ŷ i k = vi k ( Xk ), k = 0, . . . , m, i ∈ I q .
The rest of this section is devoted to the error analysis between Ȳ i and Ŷ i . The analysis follows arguments as in [START_REF] Bally | A quantization algorithm for solving discrete time multidimensional optimal stopping problems[END_REF] for optimal stopping problems, but has to be slightly modified since the functions vi (t k , .) are not Lipschitz in general when the switching costs depend on x. Let us introduce the subset LLip(R d ) of measurable functions ϕ on R d satisfying:

|ϕ(x) -ϕ(y)| ≤ K(1 + |x| + |y|)|x -y|, ∀x, y ∈ R d ,
for some positive constant K, and denote by Lemma 4.3 The functions vi (t k , .), k = 0, . . . , m, i ∈ I q , lie in LLip(R d ), and [v i (t k , .)] LLip is bounded by a constant not depending on (k, i, h).

Proof. We set vi k = vi (t k , .). From the representation (3.12), we have

vi k (x) = sup α∈A h t k ,i E m-1 ℓ=k f ( Xt k ,x t ℓ , I t ℓ )h + g( Xt k ,x tm , I tm ) - N (α) n=1 c( Xt k ,x τn , ι n-1 , ι n ) ,
where Xt k ,x is the solution to the Euler scheme starting from x at time t k . From (3.15), notice that in the above representation for vi k (x), one can restrict the supremum to

A h,K t k ,i (x) = α ∈ A h t k ,i s.t. E|N (α)| 2 ≤ K(1 + |x| 2
) for some positive constant K not depending on (t k , x, i, h). Then, as in the proof of Theorem 4.1, we have for any x, y ∈ R d , and

α ∈ A h,K t k ,i (x) ∪ A h,K t k ,i (y), E m-1 ℓ=k h f ( Xt k ,x t ℓ , I t ℓ ) -f ( Xt k ,y t ℓ , I t ℓ ) + g( Xt k ,x tm , I tm ) -g( Xt k ,y tm , I tm ) + N (α) n=1 c( Xt k ,x τn , ι n-1 , ι n ) -c( Xt k ,x τn , ι n-1 , ι n ) ≤ K 1 + N (α) 2 sup k≤ℓ≤m Xt k ,x t ℓ -Xt k ,y t ℓ 2 ≤ K(1 + |x| + |y|)|x -y|,
by standard Lipschitz estimates on the Euler scheme. By taking the supremum over A h,K t k ,i (x) ∪ A h,K t k ,i (y) in the above inequality, this shows that

|v i k (x) -vi k (y)| ≤ K(1 + |x| + |y|)|x -y|, i.e. vi k ∈ LLip(R d ) with [v i k ] LLip ≤ K. 2
The next Lemma shows that the probability transition kernel of the Euler scheme preserves the growth linear Lipschitz property. Lemma 4.4 For any ϕ ∈ LLip(R d ), the function P h ϕ also lies in LLip(R d ), and there exists some constant K, not depending on h, such that

[P h ϕ] LLip ≤ √ 3(1 + O(h))[ϕ] LLip ,
where O(h) denotes any function s.t. O(h)/h is bounded when h goes to zero.

Proof. From (4.16) and Cauchy-Schwarz inequality, we have for any x, y ∈ R d :

|P h ϕ(x) -P h ϕ(y)| ≤ E ϕ(F h (x, ϑ)) -ϕ(F h (y, ϑ)) 2 1/2 ≤ [ϕ] GLip E 1 + |F h (x, ϑ)| + |F h (y, ϑ)|) 2 F h (x, ϑ) -F h (y, ϑ) 2 1/2 ≤ √ 3[ϕ] GLip E (1 + |F h (x, ϑ)| 2 + |F h (y, ϑ)| 2 )|F h (x, ϑ) -F h (y, ϑ)| 2 1 2 , (4.19)
where we used the relation (a+b+c) 2 ≤ 3(a 2 +b 2 +c 2 ). Since ϑ has a symmetric distribution, we have

E 1 + |F h (x, ϑ)| 2 + |F h (y, ϑ)| 2 |F h (x, ϑ) -F h (y, ϑ)| 2 = 1 2 E 1 + |F h (x, ϑ)| 2 + |F h (y, ϑ)| 2 |F h (x, ϑ) -F h (y, ϑ)| 2 + 1 + |F h (x, -ϑ)| 2 + |F h (y, -ϑ)| 2 |F h (x, -ϑ) -F h (y, -ϑ)| 2 A straightforward calculation gives 1 2 1 + |F h (x, ϑ)| 2 + |F h (y, ϑ)| 2 |F h (x, ϑ) -F h (y, ϑ)| 2 + 1 + |F h (x, -ϑ)| 2 + |F h (y, -ϑ)| 2 |F h (x, -ϑ) -F h (y, -ϑ)| 2 = 1 + |x + hb(x)| 2 + |y + hb(y)| 2 + h|σ(x)ϑ| 2 + h|σ(y)ϑ| 2 x -y + h(b(x) -b(y)) 2 + h|(σ(x) -σ(y))ϑ| 2 |x + hb(x)| 2 + |y + hb(y)| 2 + 4h x + hb(x)|σ(x)ϑ + y + hb(y)|σ(y)ϑ x -y + h(b(x) -b(y))|(σ(x) -σ(y))ϑ + h 2 (|σ(x)ϑ| 2 + |σ(y)ϑ| 2 )|(σ(x) -σ(y))ϑ| 2 .
By Lipschitz continuity of b and σ, and the fact that E|ϑ| 4 < ∞, we deduce that

E (1 + |F h (x, ϑ)| 2 + |F h (y, ϑ)| 2 )|F h (x, ϑ) -F h (y, ϑ)| 2 ≤ (1 + O(h))(1 + |x| 2 + |y| 2 )|x -y| 2 .
Plugging this last inequality into (4.19) shows the required result. 2

We now pass to the main result of this section by providing some a priori estimates for Ȳt k -Ŷk in terms of the quantization error Xt k -Xk . Theorem 4.2 There exists some positive constant K, not depending on h, such that

max i∈Iq Ȳ i t k -Ŷ i k p ≤ K m ℓ=k (1 + X 0 r + Xℓ r ) Xt ℓ -Xℓ s , (4.20)
for any k = 0, . . . , m, and

(p, r, s) ∈ (1, ∞) s.t. 1 p = 1 r + 1 s .
Proof. We set vi k = vi (t k , .), and by misuse of notations, we also set Ȳ i k = Ȳ i t k = vi k ( Xk ). From the recursive induction (4.15) (resp. (4.18)) on vi k (resp. vi k ), and the trivial inequality | max j ājmax j âj | ≤ max j |ā jâj |, we have for all i ∈ I q :

| Ȳ i k -Ŷ i k | = |v i k ( Xt k ) -vi k ( Xk )| ≤ max j∈Iq P h vj k+1 ( Xt k ) + hf j ( Xt k ) -c ij ( Xt k ) -Pk vj k+1 ( Xk ) + hf j ( Xk ) -c ij ( Xk ) ≤ max j∈Iq P h vj k+1 ( Xt k ) -Pk vj k+1 ( Xk ) + h f j ( Xt k ) -f j ( Xk ) + c ij ( Xt k ) -c ij ( Xk ) ≤ K Xt k -Xk + max j∈Iq P h vj k+1 ( Xt k ) -Pk vj k+1 ( Xk )
by the Lipschitz property of f j and c ij , and so

max i∈Iq Ȳ i k -Ŷ i k p ≤ K Xt k -Xk p + max i∈Iq P h vi k+1 ( Xt k ) -Pk vi k+1 ( Xk ) p (4.21)
Writing Êk for the conditional expectation w.r.t. Xk , we have for any i ∈ I q

P h vi k+1 ( Xt k ) -Pk vi k+1 ( Xk ) ≤ P h vi k+1 ( Xt k ) -P h vi k+1 ( Xk ) + P h vi k+1 ( Xk ) -Êk [P h v i k+1 ( Xt k )] + Êk [P h vi k+1 ( Xt k )] -Pk vi k+1 ( Xk ) = P h vi k+1 ( Xt k ) -P h vi k+1 ( Xk ) + Êk [P h vi k+1 ( Xk ) -P h vi k+1 ( Xt k )] + Êk [ Ȳ i k+1 -Ŷ i k+1 ] .
Since Êk is a L p -contraction, we then obtain

P h vi k+1 ( Xt k ) -Pk vi k+1 ( Xk ) p ≤ 2 P h vi k+1 ( Xt k ) -P h vi k+1 ( Xk ) p + Ȳ i k+1 -Ŷ i k+1 p ≤ K(1 + O(h)) 1 + Xt k + Xk Xt k -Xk p + Ȳ i k+1 -Ŷ i k+1 p ≤ K(1 + O(h)) 1 + X 0 r + Xk r Xt k -Xk s + Ȳ i k+1 -Ŷ i k+1 p , (4.22)
where we used Lemmata 4.4 and 4.

Ȳ i t k -Ŷ i k 1 ≤ K(1 + X 0 2 ) m ℓ=k Xt ℓ -Xℓ 2 ,
for all k = 0, . . . , m. In particular, if X 0 = x 0 is deterministic, then X0 = x 0 , and we have an error estimation by quantization of the value function function for the discrete-time optimal switching problem at the initial date measured by:

max i∈Iq vi (0, x 0 ) -vi 0 (x 0 ) ≤ K(1 + |x 0 |) m k=1 Xt k -Xk 2 (4.23)
Suppose that one has at hand a global stack of N points for the whole space-time grid, to be dispatched with N k points for each kth-time step, i.e. m k=1 N k = N . Then, as in [START_REF] Bally | A quantization algorithm for solving discrete time multidimensional optimal stopping problems[END_REF], in the case of uniformly elliptic diffusion with bounded Lipschitz coefficients b and σ, one can optimize over the N k 's by using the rate of convergence for the miminal L 2 -quantization error given by Zador's theorem: .

Xt k -Xk 2 ∼ J 2,d ϕ k 1 2 d d+2 N 1 d k as N k → ∞,
By combining with the estimate (3.14), we obtain an error bound between the value function of the continuous-time optimal switching problem and its approximation by marginal quantization of order h 1 2 when choosing a number of points by grid N h of order 1/h 3d 2 . This has to be compared with the number of points N of lower order 1/h d in the Markovian quantization approach, see Remark 4.1. The complexity of this marginal quantization algorithm is of order O ( m k=1 N k N k+1 ). In terms of h, if we take N k = N h = 1/h 3d 2 , we then need O(1/h 3d+1 ) operations to compute the value function. Recall that the Markovian quantization method requires a complexity of higher order O(1/h 4d+1 ), but provides in compensation an approximation of the value function in the whole space grid X.

Numerical tests

We test our quantization algorithms by comparison results with explicit formulae for optimal switching problems derived from chapter 5 in [START_REF] Pham | Continuous time stochastic control and optimization with financial applications[END_REF]. The formulae are obtained for infinite horizon problems, that we adapt to our case by taking as the final gain the (discounted) value function for the infinite horizon problem.

We consider a two-regime switching problem where the diffusion is independent of the regime and follows a geometric Brownian motion, i.e. b(x, i) = bx, σ(x, i) = σx, and the switching costs are constant c(x, i, j) = c ij ,i, j = 1, 2. The profit functions are in the form f i (t, x) = e -βt k i x γ i , i = 1, 2. From Theorem 5.3.5 in [START_REF] Pham | Continuous time stochastic control and optimization with financial applications[END_REF]), the value functions are given by:

v 1 (0, x) = A 1 x m + + K 1 k 1 x γ 1 , x < x * 1 B 2 x m -+ K 2 k 2 x γ 2 -c 12 , x ≥ x * 1 v 2 (0, x) =      A 2 x m + + K 2 k 2 x γ 2 , x < x * 2 A 1 x m + + K 1 k 1 x γ 1 -c 21 x * 2 ≤ x ≤ x * 2 B 2 x m -+ K 2 k 2 x γ 2 , x > x * 2 ,
where A i , B i , K i , x * 2 and x * 2 depend explicitly on the parameters. In the sequel, we take for value of the parameters: b = 0, σ = 1, c 01 = c 10 = 0.5, k 1 = 2, k 2 = 1, γ 1 = 1/3, γ 2 = 2/3, β = 1.

We compute the value function in regime 2 taken at X 0 = 3.0 by means of the first algorithm (Markovian quantization). We take R = 10X 0 and vary m, δ and N . The results are compared with the exact value in Table 1. Notice that the algorithm seems to be quite robust and provides good results even when δm and m R do not satisfy the constraints given by our theoretical estimates in Remark 4.1.

In Table 2, we have computed the value with the marginal quantization algorithm. We make vary the number of time steps m and the total number of grid points N (dispatched between the different time steps as described in Remark 4.3). We have used optimal quantization of the Brownian motion, and the transition probabilities π ll ′ k were computed by Monte-Carlo simulations with 10 6 sample paths (for an analysis of the error induced by this Monte-Carlo approximation, see Section 4 in [START_REF] Bally | Error analysis of the quantization algorithm for obstacle problems[END_REF]). We have also indicated the time spent for these computations. Actually, almost all of this time comes from the Monte-Carlo computations, as the tree descent algorithm is very fast (less than 1s for all the tested parameters).

For the two methods, we look at the impact of the quantization number for each time step (resp. N and N h) on the precision of the results. As our theoretical estimates showed (see Remarks 4.1 and 4.3), for the first method, increasing N higher than h -1 does not seem to improve the precision, whereas for the second method, we can see for several values of h that changing N h from h -1 to h -2 or h -3 improves the precision.

Comparing the two tables, the first method seems to provide precise estimates with slightly faster computation times, and it has the further advantage of computing simultaneously the value functions at any points of the space discretization grid X. However, since most of the time spent by our second algorithm was devoted to the calculation of the transition probabilities π ll ′ k , if these were computed beforehand and stored offline, the marginal quantization method becomes more competitive.

(m, 1/δ, N ) v2 (0, 3.0) Numerical error (%) Algorithm time (s) [START_REF] Kloeden | Numerical solution of stochastic differential equations[END_REF][START_REF] Kloeden | Numerical solution of stochastic differential equations[END_REF][START_REF] Kloeden | Numerical solution of stochastic differential equations[END_REF] 2

[ϕ]

  LLip = sup x,y∈R d ,x =y |ϕ(x)ϕ(y)| (1 + |x| + |y|)|x -y| .

.,

  where ϕ k is the probability density function of Xt k , and ϕ r = ( |ϕ(u)| r du) t k , for some constant K depending only on b, σ, T , d.Substituting into (4.23) with Zador's theorem, we obtainmax i∈Iq vi (0, x 0 )vi 0 (x 0 ) ≤ K(1 + |x 0 |)For fixed h = T /m and N , the sum in the upper bound of the above inequality is minimized over the size of the grids Γ k , k = 1, . . . , m with where ⌈x⌉ := min{k ∈ N, k ≥ x}, and we have a global rate of convergence given by: max i∈Iq vi (0, x 0 )vi 0 (x 0 ) ≤ K(1+ |x 0 |) h( N h) 1 d

  . |.| will denote the canonical Euclidian norm on R d , and (.|.) the corresponding inner product. For any p ≥ 1, and Y random variable on (Ω, F, P), we denote by Y p = (E|Y | p )

	1 p .

  m -1, are iid, N (0, I d )-distributed, independent of F t k . Similarly as in Lemma 2.1, we have the L p -estimate:

	sup α∈A h t k ,i	max ℓ=k,...,m	Xh,t k ,x,α t ℓ	p

  .7) Combining (4.6),(4.7) and the fact that |Proj X (y)| ≤ |y| + δ for all y ∈ R d , we get

	Xt ℓ+1 p	≤ δ + e Kph	Xt ℓ p

  Xm p by the Lipschitz condition on g i , we conclude by induction. 2 Remark 4.3 Assume that Xk is chosen to be an L 2 -optimal quantizer of Xt k for each k = 0, . . . , m. It is in particular a stationary quantizer in the sense that E[ Xt k | Xk ] = Xk (see[START_REF] Pagès | Optimal quantization methods and applications to numerical problems in finance[END_REF]), and by Jensen's inequality, we deduce that Xk 2 ≤ Xt k 2 .

		3, Hölder's inequality and (4.14). Substituting (4.22)
	into (4.21), we get
	max i∈Iq	Ȳ i k -Ŷ i k p
	≤ K(1 + O(h)) 1 + X 0 r + Xk r	Xt k -Xk s	+ max i∈Iq	Ȳ i k+1 -Ŷ i k+1 p
					Recalling (4.14), the
	inequality (4.20) in Theorem 4.2 gives
	max i∈Iq

, for all k = 0, . . . , m -1. Since max i∈Iq Ȳ i m -Ŷ i m p = max i∈Iq g i ( Xtm )g( Xm ) p ≤ K Xtm -

Table 2 :

 2 Results obtained by marginal quantization

		.1925	3.0	0.2
	(10,10,100)	2.1863	2.7	0.5
	(10,10,1000)	2.1852	2.7	1.4
	(10,100,1000)	2.1882	2.8	8.5
	(10,100,5000)	2.1882	2.8	40
	(100,10,100)	2.1218	0.31	1.0
	(100,10,1000)	2.1213	0.33	8.0
	(100,10,5000)	2.1213	0.33	39
	(100,100,100)	2.1250	0.16	8.6
	(100,100,1000)	2.1250	0.16	82
	Exact value	2.1285
	Table 1: Results obtained by Markovian quantization
	(m, N )	Ŷ 2 0	Numerical error (%) Algorithm time (s)
	(10,100)	2.2080	3.7	4.4
	(10,1000)	2.2174	4.2	4.9
	(10,10000)	2.1276	0.04	5.8
	(100,1000)	2.1233	0.24	36
	(100,10000) 2.1316	0.15	48
	(100,50000) 2.1301	0.07	65
	(1000,10000) 2.1161	0.58	353
	(1000,50000) 2.1213	0.34	498


M.D Jan Laco
email: lacoj@lfhk.cuni.cz

Ales Ryska

Petr Celakovsky

Helena Dolezalova

Radovan Mottl

Lubos Tucek

a Clinicopathological Study of 6 Cases From Central Europe

Keywords: salivary gland, chronic sclerosing sialadenitis, Küttner tumor, IgG4plasma cells salivary gland, chronic sclerosing sialadenitis, Küttner tumor, IgG4-plasma cells

Introduction

Chronic sclerosing sialadenitis (CSS), also known as "Küttner tumor", is the most common disease of the submandibular gland affecting middle-aged and elderly patients with slight male predominance. [START_REF] Ellis | Tumor-like conditions[END_REF][START_REF] Isacsson | Chronic sialadenitis of the submandibular gland: a retrospective study of 108 cases[END_REF] It frequently manifests as a firm, painless swelling, clinically mimicking salivary neoplasm. [START_REF] Chan | Kuttner tumor (chronic sclerosing sialadenitis) of the submandibular gland: an underdiagnosed entity[END_REF] Sialomicroliths, which accumulate during secretory inactivity in normal salivary glands, are thought to play an important role in the pathogenesis of CSS. [START_REF] Harrison | Role of microliths in the aetiology of chronic submandibular sialadenitis: a clinicopathological investigation of 154 cases[END_REF][START_REF] Harrison | Causes, natural history, and incidence of salivary stones and obstructions[END_REF] Based on the results of two recent studies analysing a total of 25 cases, [START_REF] Kitagawa | Abundant IgG4-positive plasma cell infiltration characterizes chronic sclerosing sialadenitis (Küttner´s tumor)[END_REF][START_REF] Geyer | Chronic sclerosing sialadenitis (Küttner tumor) is an IgG4-associated disease[END_REF] it has been proposed that CSS may be a part of the spectrum of IgG4-related disease. IgG4-related disease is an expanding and frequently underdiagnosed condition comprising entities such as retroperitoneal and mediastinal fibrosis, Riedel´s thyroiditis, inflammatory pseudotumor of the orbit and some forms of interstitial pneumonia and tubulointerstitial nephritis (see review by Bateman and Deheragoda 8 ).

Since the two aforementioned studies analyzed samples from Japanese and American populations [START_REF] Kitagawa | Abundant IgG4-positive plasma cell infiltration characterizes chronic sclerosing sialadenitis (Küttner´s tumor)[END_REF][START_REF] Geyer | Chronic sclerosing sialadenitis (Küttner tumor) is an IgG4-associated disease[END_REF] and there is no series from the European region, the aim of our study was to compare reported results with findings from a central European cohort and eventually to extend the spectrum of clinicopathologic features of IgG4-related disease. A total of 105 cases of chronic sialadenitis of the submandibular gland diagnosed over a period of 13 years (1998-2010) were retrieved from the archives of the Fingerland Department of Pathology. Six (5.7%) of the cases were originally diagnosed as chronic sclerosing sialadenitis (CSS)/Küttner tumor using the following criteria: presence of intensive lymphoplasmacellular inflammation, extensive fibrosis and acinar atrophy, without formation of obvious lymphoepithelial islands. [START_REF] Ellis | Tumor-like conditions[END_REF] As controls, we examined 6 age and gender-matched consecutive cases of chronic sialadenitis-not otherwise specified (CSNOS), originally diagnosed in cases without features indicative of CSS (see above) and without obvious lymphoepithelial islands formation. Clinical information of the patients was obtained from clinical charts.

The tissue specimens were obtained during surgery performed at the Departments of Otorhinolaryngology and Dentistry, Medical Faculty and Faculty Hospital, Hradec Kralove.

The samples were immediately fixed in 10% formalin, routinely processed, embedded in paraffin, and stained with hematoxylin-eosin and elastica-van Gieson. Paraffin-embedded tissue blocks (median 4 blocks per case; range 2-7) were available for immunohistochemical analysis in all cases.

Indirect immunohistochemistry was performed using monoclonal/polyclonal antibodies against CD20 (L26, 1:300), CD79α (JCB117, 1:100), CD3 (polyclonal, 1:200), CD138 (MI15, 1:50), immunoglobulin light chain kappa (BJK) (R10-21-F3, 1:400), immunoglobulin light chain lambda (BJL) (N10/2, 1:25), IgG (polyclonal, FLEX), IgG4 (HP6025, 1:100), and bcl-6 (PG-B6p, 1:5). The source of IgG4 was Invitrogen (Camarillo, USA), of BJL Diagnostic BioSystems (Pleasanton, USA), and that of the remaining antibodies was Dako (Glostrup, Denmark). Antigen retrieval was performed in a water bath for 40 minutes at 97°C in the target retrieval buffers at different pH values -pH 6.0 (buffer S1700) for CD20, CD79α, CD138, BJK and BJL and pH 9.9 (buffer S3308) for CD3, IgG4 and bcl-6. Endogenous peroxidase activity was inhibited by immersing the sections in 3% hydrogene peroxide. Finally the sections were incubated with EnVision™ Dual Link System-HRP (Dako). The reaction was visualized using diaminobenzidine. For detection of IgG, a ready-to-use system -EnVision™ FLEX Target Retrieval Solution High pH (Dako) was utilized.

The histopathologic evaluation was perfomed according to the guidelines proposed by Geyer et al. [START_REF] Geyer | Chronic sclerosing sialadenitis (Küttner tumor) is an IgG4-associated disease[END_REF] Phlebitis was defined as perivenular inflammation; if associated with progressive destruction of the venular wall and obliteration of the lumen, it was classified as obliterative In addition, the presence of ductal lymphocytes (i.e. lymphocytes within the epithelium of smaller ducts without formation of obvious lymphoepithelial islands), parenchymal neutrophils (i.e. neutrophils within smaller ducts), intraductal secretory material with microcalcifications and periductal granulomas was recorded. The numbers of IgG and IgG4-positive plasma cells in three high-power fields (HPF, 10x eyepiece and 40x lens) were counted in the areas in which the inflammation was most intense. The counting was done in the same fields on the slides stained for IgG and IgG4. An IgG4/IgG ratio was calculated for each case.

As there were just 6 CSS-cases, only basic descriptive statistical analysis was performed.

Clinical data

The clinical data of the patients are shown in Table 1. The CSS series comprises 4 females and 2 males aged 32-76 years (mean 57±16 years; median 59 years). One of the patient with CSS had a history of Hashimoto thyroiditis with hypothyroidism. In the CSNOS group, there was one patient with Hashimoto thyroiditis and another with diabetes mellitus, type 1. None of the patients in either group had a history of IgG4-related disease.

All the CCS patients presented with a 2 to 9 months (mean 6±2 months; median 6 months) history of neck swelling, which was painful in only one case. The swelling was unilateral in all patients. The left submandibular gland was involved in 4 cases and the right, in 2 cases. None of the patients developed parotid gland lesions. Cervical lymphadenopathy was present in 2 patients. Serum IgG4 level was not measured in any of the patients. All of the patients underwent total submandibulectomy with local lymphadenectomy in 2 cases. There were 4 CSS patients with a clinical diagnosis of sialadenitis-not otherwise specified and 2 with sialolithiasis.

Although none of the patients received corticosteroid therapy postoperatively, none of them showed any of the IgG4-related disease during the follow-up period, which ranged from 14-89 months (mean 63 ± 26 months; median 69 months).

Gross findings

The resected submandibular glands of patients with CSS measured 45-60 mm in largest diameter. In one case, a sialolith measuring 4 mm was identified.

Microscopic findings

The microscopic findings are summarized in Table 2. In all cases, the inflammation was limited to the salivary gland without extension to periglandular tissue.

All the CSS cases showed similar morphologic features -preservation of lobular architecture, dense lymphoplasmacellular inflammation and variable degree of acinar atrophy and loss. In 3/6 of the cases, the entire gland was diffusely involved while in the remaining cases, the changes were focal, involving 70-90% of the gland parenchyma. The lobules were separated by cellular fibrous bands of varied thickness composed of plump fibroblasts intermixed with small lymphocytes and plasma cells (Fig. 1). The inflammatory infiltrate was severe in most cases and showed periductal and intralobular distribution. Plasma cell clusters were frequently present. Follicular hyperplasia was a consistent feature and it was considered Ductal structure was generally preserved. Although there were some areas showing changes suggestive of lymphoepithelial island development, no well formed lymphoepithelial islands were seen. In 5/6 cases, dense eosinophilic secretory material was present within small intralobular ducts/acini. This was frequently accompanied by the presence of parenchymal neutrophils with occasional formation of intraluminal neutrophilic collections (Fig. 3). A microlith, located in a small intralobular duct, was seen in only one case. Eosinophils were generally inconspicious and periductal granulomas were absent. In 4 cases, non-obliterative phlebitis of interlobular veins was observed and in 3 cases, obliterative phlebitis, confirmed using elastica staining, was seen (Fig. 4).

The CSNOS cases also showed preservation of lobular architecture, lymphoplasmacellular inflammation and varied degrees of acinar loss and atrophy. The changes were diffuse in 4 cases and focal in 2 (affecting 30% and 60% of the gland parenchyma in the 1 st and 2 nd cases, respectively). Unlike CSS, the fibrous bands in CSNOS were rather hypocellular and hyalinized without conspicious inflammatory cells. The lymphoplasmacellular infiltrate was mild to moderate and, like CSS, had periductal and intralobular distribution. Follicular hyperplasia was seen in 4/6 cases but was never florid. No ductal lymphocytes were observed. In 2/6 cases, dense eosinophilic secretory material was present in small intralobular ducts. This was accompanied by the presence of parenchymal neutrophils in one case. Neither eosinophils nor periductal granulomas were present in any case. Non-obliterative and obliterative phlebitis were both absent.

Immunohistochemically, the lymphocytic infiltrate in both CSS and CSNOS was composed of both CD20/CD79α-positive B-lymphocytes and CD3-positive T-lymphocytes.

The former formed lymphoid follicles while the latter were dispersed diffusely within the gland. The germinal center cells expressed bcl-6 protein. The CD138-positive plasma cells were polyclonal, expressing both kappa and lambda immunoglobulin light chains. The numbers of IgG-and IgG4-positive plasma cells per 1 HPF (Figs. 5 and6) and the IgG4/IgG ratios are detailed in Table 2. In general, all three values were higher in CSS than in CSNOS. Since the time the concept of IgG4-related disease was introduced by Yoshida et al. [START_REF] Yoshida | Chronic pancreatitis caused by an autoimmune abnormality: proposal of the concept of autoimmune pancreatitis[END_REF] in their work regarding autoimmune pancreatitis, several other entities have been recognized as being members of the IgG4-related disease family. These entities include, besides autoimmune pancreatitis, [START_REF] Klöppel | Autoimmune pancreatitis: histo-and immunopathological features[END_REF] retroperitoneal fibrosis (Ormond´s disease), [START_REF] Kamisawa | Autoimmune pancreatitis associated with retroperitoneal fibrosis[END_REF] mediastinal fibrosis, [START_REF] Zen | A case of retroperitoneal and mediastinal fibrosis exhibiting elevated levels of IgG4 in the absence of sclerosing pancreatitis (autoimmune pancreatitis)[END_REF] sclerosing thyroiditis, [START_REF] Komatsu | High prevalence of hypothyroidism in patients with autoimmune pancreatitis[END_REF] certain forms of chronic gastritis, colitis and cholecystitis, [START_REF] Kamisawa | A clinicopathological entity of IgG4-related autoimmune disease[END_REF] and inflammatory aortic aneurysm [START_REF] Sakata | IgG4-positive plasma cells in inflammatory abdominal aortic aneurysm: the possibility of an aortic manifestation of IgG4-related sclerosing disease[END_REF][START_REF] Ishida | IgG4-related inflammatory aneurysm of the aortic arch[END_REF] Other examples are orbital inflammatory pseudotumor and certain forms of interstitial pneumonia, tubulointerstitial nephritis, chronic prostatitis, hepatitis, etc. [START_REF] Bateman | IgG4-related systemic sclerosing disease -an emerging and under-diagnosed condition[END_REF] It has become evident, that all these conditions may manifest synchronously and/or metachronously even in the absence of autoimmune pancreatitis. [START_REF] Kamisawa | IgG4-related sclerosing disease[END_REF] Interestingly, none of our patients had a history of IgG4-related disease. Neither did they develop other forms of IgG4-related disease during follow-up period.

The precise pathogenesis of IgG4-related disease remains poorly understood; no triggers have yet been identified. IgG4 is the rarest IgG subtype, accounting for up to 6% of total serum IgG. [START_REF] Van Der Zee | Immunochemical characteristics of IgG4 antibodies[END_REF] Because of its intrinsic weakness caused by variable loss of covalent interaction between the heavy chains, IgG4 shows poor antigen binding and complement activation. About 75% of patients with some form of IgG4-related disease develop both increased serum IgG4 levels and high numbers of tissue IgG4-producing plasma cells, the latter being identified using immunohistochemistry. [START_REF] Bateman | IgG4-related systemic sclerosing disease -an emerging and under-diagnosed condition[END_REF] While the originally proposed cut-off of > 10 IgG4-positive plasma cells per 1 high power field (HPF) was accepted as diagnostic for autoimmune pancreatitis, [START_REF] Kamisawa | Close relationship between autoimmune pancreatitis and multifocal fibrosclerosis[END_REF] recently suggested level of > 20 IgG4-positive plasma cells per 1 HPF was shown to increase the sensitivity and specificity to 43% and 100%, respectively. [START_REF] Klöppel | Autoimmune pancreatitis: histo-and immunopathological features[END_REF] Still it is unclear as to whether the IgG4-producing plasma cells play an etiological role or if they simply represent a diagnostically useful marker.

Most patients with IgG4-related disease would benefit from corticosteroid therapy. [START_REF] Bateman | IgG4-related systemic sclerosing disease -an emerging and under-diagnosed condition[END_REF] Chronic sclerosing sialadenitis (CSS) was first described as a cause of unilateral swelling of the submandibular gland by Küttner in 1896, hence the term "Küttner tumor". As originally described, it predominantly involves the submandibular glands. CSS usually presents in middle aged or elderly patients with slight male predominance. [START_REF] Ellis | Tumor-like conditions[END_REF] To the best of our knowledge, the literature contains reports of only 28 cases of CSS recognized as IgG4-related disease. These 28 cases are from 2 larger series 6,7 reporting 13 and 12 cases respectively, 1 report of 2 cases, [START_REF] Abe | Immunoglobulin G4-related sclerosing sialadenitis: report of two cases and review of the literature[END_REF] and a case report describing salivary duct carcinoma arising in a background of CSS. [START_REF] Gill | Salivary duct carcinoma arising in IgG4-related autoimmune disease of the parotid gland[END_REF] These cases include 1 Chinese, 13 American and 14 Japanese patients. No data on the European population is available so far. In general, the clinicopathological findings described in previous studies are in agreement with our current report. Thus, including our 6 cases, there are a total of 34 cases of CSS in the literature proven to be IgG4-related disease.

Of these 34 cases, 19 were male and 15 female, aged 27-76 years (mean 62 years).

Two of them had underlying autoimmune disease (1 with Graves disease, [START_REF] Kitagawa | Abundant IgG4-positive plasma cell infiltration characterizes chronic sclerosing sialadenitis (Küttner´s tumor)[END_REF] another, from our study, with Hashimoto thyroiditis). Nine patients experienced extrasalivary manifestation of IgG4-related disease with multiorgan involvement in 3 patients. [START_REF] Kitagawa | Abundant IgG4-positive plasma cell infiltration characterizes chronic sclerosing sialadenitis (Küttner´s tumor)[END_REF] Sclerosing pancreatitis was the most common extrasalivary presentation (in 5 patients). The other forms of IgG4-related disease seen were sclerosing cholangitis, dacryadenitis, prostatitis, "lung and bilateral renal nodules", retroperitoneal fibrosis and generalized lymphadenopathy. Only 1 case of CSS occured in the parotid gland, [START_REF] Kitagawa | Abundant IgG4-positive plasma cell infiltration characterizes chronic sclerosing sialadenitis (Küttner´s tumor)[END_REF] suggesting that the principal site of involvement is the submandibular gland. Cervical lymphadenopathy was encountered in 8 patients. When administered, corticosteroid therapy was beneficial for a majority of the CSS-patients.

The microscopic appearance of CSS was similar in all cases with preservation of lobular architecture, interlobular cellular fibrosis and intensive lymphoplasmacellular infiltrate with various degrees of acinar atrophy. The high cellularity of the interlobular fibrous tissue appears to be a characteristic feature of CSS as it contrasts with the rather hypocellular hyalinized fibrous bands without significant numbers of inflammatory cells seen in CSNOS. The inflammatory infiltrate was regarded to be severe in most cases of CSS with the presence of large activated follicles with germinal centres (florid follicular hyperplasia). In addition, both non-obliterative and obliterative forms of phlebitis were found in most of the CCS cases, the latter being easier appreaciated using elastica staining. The less frequently observed findings included ductal lymphocytes (sometimes referred to as lymphocytic exocytosis) somewhat similar to that of developing lymphoepithelial islands. Well formed lymphoepithelial islands [START_REF] Ihrler | Lymphoepithelial duct lesions in Sjögren-type sialadenitis[END_REF] (characteristic but not necessarily pathognomonic for Sjögren-type sialadenitis) were seen in only 2 cases 7 of the 34 cases. Parenchymal neutrophils (sometimes referred to as granulocytic epithelial lesion) with eosinophilic secretory material, presumably mucin, within small ducts/acini were sometimes seen. In addition, occasional microlith formation was observed. In one of our cases, a small stone was found on gross examination. We hypothesize that stones may develop in the setting of CSS, probably as a result of altered saliva production due to acinar injury. Therefore, all cases of "sialolithiasis" featuring any of the above listed findings should be tested for presence of IgG4-positive plasma cells.

The number of IgG4-positive plasma cells was consistently highly elevated in our cases as in all previous reports. [START_REF] Kitagawa | Abundant IgG4-positive plasma cell infiltration characterizes chronic sclerosing sialadenitis (Küttner´s tumor)[END_REF][START_REF] Geyer | Chronic sclerosing sialadenitis (Küttner tumor) is an IgG4-associated disease[END_REF][START_REF] Abe | Immunoglobulin G4-related sclerosing sialadenitis: report of two cases and review of the literature[END_REF][START_REF] Gill | Salivary duct carcinoma arising in IgG4-related autoimmune disease of the parotid gland[END_REF] In the previous reports, the count of IgG4-positive plasma cells per 1 HPF ranged from 62 to 608 (mean about 180 / 1HPF) and in our study it ranged from 62 to 235 (mean 138 / 1HPF). In the previous reports, the IgG4/IgG ratio ranged from 0.40 to 1.00 (mean about 0.77) while in our study, it ranged from 0.61 to 0.92 (mean 0.79). These values are higher than the values from the control cases [START_REF] Kitagawa | Abundant IgG4-positive plasma cell infiltration characterizes chronic sclerosing sialadenitis (Küttner´s tumor)[END_REF][START_REF] Geyer | Chronic sclerosing sialadenitis (Küttner tumor) is an IgG4-associated disease[END_REF] in which the number of IgG4-positive plasma cells per 1 HPF did not exceed 44 (in our series 23) and the IgG4/IgG ratio 0.14 (in our series 0.26). Based on these findings, the cut-off > 50 IgG4-positive plasma cells per 1 HPF appears to be a reasonable threshold for the diagnosis of CSS, and produces a sensitivity and specificity of 100%.

In summary, we present results from 6 European cases of CSS which support and confirm findings from previous studies. CSS should be regarded as a part of the spectrum of IgG4-related disease. All cases of sialadenitis and/or sialolithiasis featuring any of the above mentioned histological findings should be tested for the presence of IgG4-producing plasma cells as the patients should be followed up to enable early detection of possible subsequent extrasalivary manifestations of IgG4-related disease. A majority of such patients would benefit from corticosteroid therapy.

F

  in 3 cases. Ductal lymphocytes in intralobular ducts were seen in 3 cases (Fig 2).

5 F

 5 It frequently manifests as a firm swelling, clinically mimicking salivary gland neoplasm. Sialomicroliths, which accumulate during secretory inactivity of normal salivary glands, are considered to be etiologic factors in the development of CSS. Sialoliths on the other hand are thought to develop secondary to the sialadenitis.4,

Fig. 1 Fig. 2 Fig. 3 Fig. 4 Fig. 5 Fig. 6 Fig. 1 Fig. 2 Fig. 3 Fig. 4 Fig. 5 Fig. 6

 123456123456 Fig. 1 Dense chronic inflammation within lobules which are separated by variably thick fibrous septa in CSS (HE, original magnification ×40) Fig. 2 Ductal lymphocytes -presence of intraepithelial lymphocytes resembling developing lymphoepithelial island in CSS (HE, original magnification ×300) Fig. 3 Parenchymal neutrophils -small collections of neutrophils and dense eosinophilic secretory material in very atrophic parenchyma in CSS (HE, original magnification ×400) Fig. 4 Obliterative phlebitis may be easily overlooked in the inflammatory background in CSS (HE, original magnification ×200). Inset: Elastica staining facilitates its recognition (original magnification ×200) Fig. 5 Numerous IgG-positive plasma cells in CSS (original magnification ×400) Fig. 6 Numerous IgG4-positive plasma cells in CSS (original magnification ×400)

Published on behalf of the British Division of the International Academy of Pathology Histopathology

Acknowledgements

The authors thank Mrs. M. Zakova for her excellent technical support and Dr. F.A. Sobande for English language correction. Supported by Research Project of the Ministry of Health of the Czech Republic No. 00179906.

Published on behalf of the British Division of the International Academy of Pathology Histopathology