Sophie Laruelle
email: sophie.laruelle@upmc.fr

Gilles Pagès
email: gilles.pages@upmc.fr

Stochastic Approximation with Averaging Innovation Applied to Finance

Keywords: Stochastic Approximation, sequence with low discrepancy, quasi-Monte Carlo, α-mixing process, Gàl-Koksma theorem, stationary process, ergodic control, two-armed bandit algorithm, calibration, optimal asset allocation, Value-at-Risk, Conditional Value-at-Risk. 2010 AMS Classification: 62L20, secondary: 37A25, 60G10, 93C40, 62P05, 91B32

The aim of the paper is to establish a convergence theorem for multi-dimensional stochastic approximation when the "innovations" satisfy some "light" averaging properties in the presence of a pathwise Lyapunov function. These averaging assumptions allow us to unify apparently remote frameworks where the innovations are simulated (possibly deterministic like in Quasi-Monte Carlo simulation) or exogenous (like market data) with ergodic properties. We propose several fields of applications and illustrate our results on five examples mainly motivated by Finance.

Introduction

The aim of this paper is to establish a convergence theorem for multi-dimensional recursive stochastic approximation in a non-standard framework (compared to the huge literature on this field, see [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF], [START_REF] Duflo | Algorithmes stochastiques[END_REF], [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF], [START_REF] Andrieu | Stability of stochastic approximation under verifiable conditions[END_REF], etc): we will significantly relax our assumption on the innovation process by only asking for some natural "light" ergodic or simply averaging assumptions, compensated by a reinforcement of the mean reversion assumption since we will require the existence of a pathwise Lyapunov function. We will show that this approach unifies seemingly remote settings: those where the innovations are simulated or even deterministic (quasi-Monte Carlo simulation) and those where the innovations are exogenous data (like market data). Especially in the latest case it may be not realistic to make a priori too stringent assumptions on the dynamics of such data process, like mixing or Markov. On the other hand, the pathwise Lyapunov assumption is definitely an intrinsic limitation to the kind of problem we can deal with, compared to the procedures extensively investigated in [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF] or more recently in [START_REF] Douc | Forgetting the initial distribution for hidden Markov models[END_REF] where innovations are Markovian and share mixing properties.

However, we provide several examples, mainly inspired by Finance, to illustrate the fact that the field of application of our framework is rather wide and can solve efficiently various kinds of problems, some of them having already been considered in the literature.

Let us be more specific: this paper presents convergence results for R d -valued stochastic approximation procedures of Robbins-Monro type (see [START_REF] Robbins | A stochastic approximation method[END_REF] for the original paper), namely

θ n+1 = θ n -γ n+1 H(θ n , Y n ), n ≥ 0, θ 0 ∈ R d , (1.1)
where H : R d × R q → R d is a Borel function, (γ n ) n≥1 a sequence of positive steps and the "innovation" sequence (Y n ) n≥0 satisfies some "elementary" averaging assumptions (θ 0 is assumed to be deterministic in this introduction for convenience simplicity). In fact, we will consider a slightly more general setting which includes an extra noisy term

θ n+1 = θ n -γ n+1 (H(θ n , Y n ) + ∆M n+1 ) , n ≥ 0, (1.2)
where (∆M n ) n≥1 is a sequence of R d -valued F n -adapted martingale increments for a filtration F n .

To establish the a.s. convergence of the sequence (θ n ) n≥0 toward its "target" θ * (to be specified later on), the idea is to make the assumption that the innovation sequence (Y n ) n≥0 satisfies an averaging property in a "linear" setting: typically that, for a wide enough class V of integrable functions (with respect to a probability measure ν),

∀f ∈ V, 1 n n-1 k=0 f (Y k ) -→ n→∞ R q f dν (1.3)
at a common rate of convergence to be specified further on. If V ⊃ C b (R q , R), this implies

1 n n-1 k=0 δ Y k (R q )
=⇒ n→∞ ν a.s.

by a separability argument (

(R q )
=⇒ denotes the weak convergence of probability measures). Such a sequence (Y n ) n≥0 is often called "stable" in the literature, at least when it is a Markov chain. If V = L 1 (ν), the sequence (Y n ) n≥0 may be called in short "ergodic" although no true ergodic framework comes in the game at this stage. The target of our recursive procedure (1.2) is then, as expected, a zero, if any, of the (asymptotic) mean function of the algorithm defined as h(θ) := R q H(θ, y)ν(dy).

The key assumption is the existence of pathwise Lyapunov function with respect to the innovation i.e. a function L satisfying ∇L(θ) | H(θ, y) -H(θ * , y) ≥ 0 for every θ and y. This assumption may look very stringent but in fact, it embodies standard framework of Stochastic Approximation with Markov representation of the form (1.1) when the (Y n ) n≥0 is i.i.d. since, under appropriate integrability assumptions, it can be rewritten as follows in canonical form

θ n+1 = θ n -γ n+1 H(θ n , Y n ) + ∆ M n+1 , n ≥ 0, θ 0 ∈ R d ,
where H(θ, •) = h(θ) and ∆ M n+1 = H(θ n , Y n )h(θ n ), n ≥ 0. Then (∆ M n ) n≥1 is a sequence of σ(Y 0 , . . . , Y n-1 )-martingale increments (under appropriate integrability assumptions). Finally H(θ, •) = h(θ) does not depend on y so that the above notion of pathwise Lyapunov function reduces to the standard one. The above canonical form has been extensively investigated (and extended) in many textbooks on Stochastic Approximation (see [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF], [START_REF] Duflo | Algorithmes stochastiques[END_REF], [START_REF] Kushner | Stochastic approximation methods for constrained and unconstrained systems[END_REF], [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF]).

Our main theorem (Theorem 2.1) let us retrieve almost entirely the classical results about L pboundedness and a.s. convergence of this procedure under standard Lyapunov assumption. Many extensions have been developed when (Y n ) n≥0 or even (θ n , Y n ) n≥0 have a Markovian dynamics (see the seminal textbook [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF] and more recent contributions like [START_REF] Douc | Forgetting the initial distribution for hidden Markov models[END_REF] and several references therein). The main constraint induced by such an approach is that the existence as well as assumptions on the solution of the Poisson equation related to this chain are needed.

As a first field of applications, we are interested in quasi-random numbers. The original idea of replacing by uniformly distributed sequences (with low discrepancy) i.i.d. innovations in recursive stochastic approximation procedures goes back to the early 1990's in [START_REF] Lapeyre | Sequences with low discrepancy-generalisation and application to Robbins-Monro[END_REF], leading to "Quasi-Stochastic Approximation" (QSA, referring to QM C for Quasi-Monte Carlo). The framework in [START_REF] Lapeyre | Sequences with low discrepancy-generalisation and application to Robbins-Monro[END_REF] was purely one-dimensional whereas many numerical tests h proved the efficiency of QSA in a multi-dimensional setting. The aim is to establish a convergence theorem in this higher dimensional setting under natural regularity assumptions (i.e. based on Lipschitz regularity rather than finite variation in the Hardy & Krause or in the measure sense, often encountered in the QMC world). As concerns the low discrepancy sequences, our framework is probably close to the most general one to get pointwise a.s. convergence of stochastic approximation.

As a second setting, we consider the case when (Y n ) n≥0 is a functional of α-mixing process satisfying a priori no Markov assumption. These processes are stationary and dependent, so more realistic to model inputs made of real data. To describe the class of functions V we need to prove the convergence of the series of covariance coefficients of the innovations. To this end we use some results in [START_REF] Peligrad | Central limit theorem for stationary linear processes[END_REF] and the covariance inequality for α-mixing process (see [START_REF] Doukhan | Mixing[END_REF]). Next with the probabilistic version of the Gàl-Koksma theorem (see [START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF] and [START_REF] Pagès | Sur la méthode du shift en simulation[END_REF][START_REF] Alaya | On the simulation of expectations of random variables depending on a stopping time[END_REF][START_REF] Ben Alaya | Rate of convergence for computing expectations of stopping functionals of an α-mixing process[END_REF]) we prove that this class is large enough (L 2+δ (ν) ⊂ V, δ > 0). Finally we examine the case of homogeneous Markov chain with (unique) invariant distribution ν. Several convergence results of stochastic approximation have been proved in this setting in [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF], but they all rely on the existence (and some regularity properties) of a solution to Poisson equation. To describe V we add an assumption on the transition of the chain which allows us to prove that this class does not depend on the initial value of the chain.

Finally we propose several examples of applications illustrated with numerical experiment. They can be parted in two classes: the first one devoted to simulated innovations (i.e. Numerical Probability methods) and the second one deals with the applications involving real data. Primarily we present a simple case of calibration: the search, for a derivative product in a financial model, of an implicit model parameter fitting with its market value. We implement the algorithm with both an i.i.d. sequence and a quasi-Monte Carlo sequence to compare their respective rates of convergence. The second example is devoted to the recursive computation of risk measures commonly considered in energy portfolio management: the Value-at-Risk and the Conditional-Value-at-Risk. We design a stochastic gradient and a companion procedure to compute risk measures (like in [START_REF] Bardou | Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling[END_REF][START_REF] Frikha | Contribution à la modélisation et à la gestion dynamique du risque des marchés de l'énergie[END_REF]) and we show that they can be successfully implemented in a QSA framework. In the third example, we solve numerically a "toy" long term investment problem leading to a static potential minimization derived from an ergodic control problem (see [START_REF] Løkka | A model for the long-term optimal capacity level of an investment project[END_REF]). The potential is related to the invariant measure of a diffusion so that the innovation relies on (inhomogeneous Markov) Euler schemes with decreasing step introduced in [START_REF] Lamberton | Recursive computation of the invariant distribution of a diffusion[END_REF] (see also [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF]). These three stochastic approximation procedures relie on simulated data. The fourth example is the so-called two-armed bandit introduced in learning automata and mathematical psychology in the 1950's (see [START_REF] Narendra | Use of stochastic automata for parameter self-optimization with multimodal performance criteria[END_REF]). Its a.s. behaviour in the i.i.d. setting has been extensively investigated in [START_REF] Lamberton | When can the two-armed bandit algorithm be trusted?[END_REF] and [START_REF] Lamberton | How fast is the bandit? Stoch[END_REF] and then partially extended in [START_REF] Tarrès | On ergodic two-armed bandits[END_REF] to a more general ergodic framework. We show how the starting point of this extension appears as a consequence our multiplicative case (Theorem 2.2). The last example describes a model of asset allocation across liquidity pools fully developed in [START_REF] Laruelle | Optimal split of orders across liquidity pools: a stochastic algorithm approach[END_REF] involving exogenous real market data, a priori sharing no Markov property but on which an averaging assumption seems natural (at least within a medium laps of time).

The paper is organized as follows: in Section 2 are stated and proved the two main results: Theorem 2.1 and its counterpart Theorem 2.2, for multiplicative noise. Section 3 is devoted to quasi-Stochastic Approximation, i.e. the case where the innovation process is an uniformly distributed deterministic sequence over [0, 1] q . Section 4 is devoted to applications to random innovations, namely additive noise, mixing process (functionals of α-mixing process), ergodic homogeneous Markov chain. Section 5 presents five examples of applications including numerical illustrations, mostly in connection with Finance: implicit correlation search, recursive computation of VaR and CVaR, long term investment evaluation, two-armed bandit algorithm and optimal allocation problem (more developed in [START_REF] Laruelle | Optimal split of orders across liquidity pools: a stochastic algorithm approach[END_REF]). -→ and (R q ) =⇒ will denote the weak convergence of probability measures on (R q , Bor(R q )). ∆a n = a na n-1 for every sequence (a n ) n .

Notations

Algorithm design and main theoretical result

In this paper, we consider the following general framework for recursive stochastic algorithms of the following form

θ n+1 = θ n -γ n+1 (H(θ n , Y n ) + ∆M n+1 ) , n ≥ 0, (2.4)
where (Y n ) n≥0 is an R q -valued sequence of F n -adapted random variables and (∆M n ) n≥1 is a sequence of F n -adapted martingale increment, all defined on a same filtered probability space (Ω, F, (F n ) n≥0 , P).

Moreover θ 0 ∈ L 1 R d (Ω, F 0 , P) and θ 0 is independent of (Y n , ∆M n+1 ) n≥0 . The positive step sequence (γ n ) n≥1 is non-increasing and H is a Borel function from R d × R q to R d .
In the following, we adopt a kind of compromise by assuming that (Y n ) n≥0 is a process satisfying some averaging properties and that the function H(θ * , •) belongs to a class of functions (to be specified further on) for which a rate of convergence (a.s. and in L p ) holds in (1.3). Moreover we need to reinforce the Lyapunov condition on the pseudo-mean function H which limits, at least theoretically, the range of application of the method.

Framework and assumptions

Let (Y n ) n≥0 be an R q -valued random variables sequence. We will say that the sequence (Y n ) n≥0 satisfies a ν-stability assumption or equivalently is ν-averaging if

P(dω)-a.s. 1 n n-1 k=0 δ Y k (ω) (R q ) =⇒ n→∞ ν. (2.5)
We will see that the stochastic approximation procedure defined by (2.4) is a recursive zero search of the (asymptotic) mean function

h(θ) := R q H(θ, y)ν(dy).
(2.6)

Let p ∈ [1, ∞) and let (ε n ) n≥0 be a sequence of nonnegative numbers such that ε n -→ n→∞ 0 and lim n inf nε n = 0. (2.7)
We denote by V εn,p the class of functions which convergence rate in (1.3) in both a.s. and in L p (P) sense is ε -1 n , namely

V εn,p = f ∈ L p (ν) | 1 n n-1 k=0 f (Y k ) -f dν P-a.s. & L p (P) = O(ε n ) . (2.8)

Main result

Now we are in a position to state an a.s.-convergence theorem "à la" Robbins-Siegmund.

H(θ * , •) ∈ V εn,p . (2.11)
Moreover, assume that H satisfies the following (quasi-)linear growth assumption

∀θ ∈ R d , ∀y ∈ R q , |H(θ, y)| ≤ C H φ(y)(1 + L(θ)) 1 2
(2.12)

and that the martingale increments sequence (∆M n ) n≥1 satisfies for every n ≥ 0, P-a.s.

   E |∆M n+1 | 2∨ p p-1 | F n ≤ C M φ(Y n ) 2∨ p p-1 (1 + L(θ n )) 1∨ p 2(p-1) if p > 1, |∆M n+1 | (1+L(θn)) 1 2 ≤ C M if p = 1 (2.13)
where C M is a positive real constant and

sup n≥0 φ(Y n ) 2∨ p p-1 < +∞.
Let γ = (γ n ) n≥1 be a nonnegative non-increasing sequence of "admissible" gain parameters satisfying Then, the recursive procedure defined by (2.4)

satisfies (L(θ n )) n≥0 is L 1 -bounded, L(θ n ) -→ n→∞ L ∞ < +∞ a.s., ∆θ n -→ n→∞ 0 a.s. and n≥1 ∇L(θ n ) | H(θ n , Y n ) -H(θ * , Y n ) < +∞. (b) A.s. convergence toward θ * . Furthermore, if {θ * } is a connected component of {L = L(θ * )} and the pseudo-mean function H satisfies the strict pathwise Lyapunov assumption ∀δ > 0, ∀θ ∈ R d \{θ * }, ∀y ∈ R q , ∇L(θ) | H(θ, y) -H(θ * , y) ≥ χ δ (y)Ψ δ (θ) (2.15)
where ν(χ δ ) > 0, Ψ δ is l.s.c. and positive on R d \{θ * } and δ>0 {Ψ δ = 0} = {θ * }, then

θ n a.s. -→ n→∞ θ * .
Remark. The conditions on the step sequence γ = (γ n ) n≥1 and (ε n ) n≥1 are satisfied for example by

ε n = n -β , β ∈ (0, 1], and γ n = c n a , 1 -β < a ≤ 1, c > 0. (2.16)
Proof. First step: We introduce the function

Λ(θ) := 1 + L(θ)
as a Lyapunov function instead of L(θ) like in the classical case. It follows from the fundamental formula of calculus that there exists ξ n+1 ∈ (θ n , θ n+1 ) such that

Λ(θ n+1 ) = Λ(θ n ) + ∇Λ(θ n ) | ∆θ n+1 + ∇Λ(ξ n+1 ) -∇Λ(θ n ) | ∆θ n+1 ≤ Λ(θ n ) + ∇Λ(θ n ) | ∆θ n+1 + |∇Λ(ξ n+1 ) -∇Λ(θ n )||∆θ n+1 |.
Lemma 2.1. The new Lyapunov function Λ satisfies the two following properties

(i) ∇Λ is bounded (so that Λ is Lipschitz). (ii) ∀θ, θ ′ ∈ R d , |∇Λ(θ ′ ) -∇Λ(θ)| ≤ C L |θ ′ -θ| Λ(θ) .
Proof of Lemma 2.1.

(i) ∇Λ = ∇L 2 √
1+L is bounded by (2.9), consequently Λ is Lipschitz.

(ii) Let θ, θ ′ ∈ R d , ∇Λ(θ) -∇Λ(θ ′ ) ≤ |∇L(θ) -∇L(θ ′ )| 2 1 + L(θ) + |∇L(θ ′ )| 2 1 + L(θ ′ ) -1 + L(θ) 1 + L(θ) 1 + L(θ ′ ) ≤ [∇L] Lip 2 1 + L(θ) θ -θ ′ + C 2 1 + L(θ) [Λ] Lip θ -θ ′ ≤ 1 2 ([∇L] Lip + C[Λ] Lip ) |θ -θ ′ | Λ(θ) = C L |θ -θ ′ | Λ(θ) .
Thus, applying the above lemma to θ = θ n and θ ′ = ξ n+1 , and noting that |ξ n+1 -

θ n | ≤ |∆θ n+1 | yields Λ(θ n+1 ) ≤ Λ(θ n ) -γ n+1 ∇Λ(θ n ) | H(θ n , Y n ) -γ n+1 ∇Λ(θ n ) | ∆M n+1 + C L |∆θ n+1 | 2 1 + L(θ n ) = Λ(θ n ) -γ n+1 ∇Λ(θ n ) | H(θ n , Y n ) -H(θ * , Y n ) -γ n+1 ∇Λ(θ n ) | H(θ * , Y n ) -γ n+1 ∇Λ(θ n ) | ∆M n+1 + C L γ 2 n+1 |H(θ n , Y n ) + ∆M n+1 | 2 1 + L(θ n ) .
We have for every n ≥ 0,

|γ n+1 ∇Λ(θ n ) | H(θ * , Y n ) | ≤ C Λ γ n+1 φ(Y n ) ∈ L 1 (P) since ∇Λ is bounded. Besides E [ ∇Λ(θ n ) | ∆M n+1 | F n ] = 0, n ≥ 0,
since ∆M n is a true martingale increment and ∇Λ is bounded. Furthermore, owing to (2.12) and (2.13)

E |H(θ n , Y n ) + ∆M n+1 | 2 1 + L(θ n ) | F n ≤ Cφ 2 (Y n )Λ(θ n )
(where conditional expectation is extended to positive random variables). Consequently,

E [Λ(θ n+1 ) | F n ] ≤ Λ(θ n ) 1 + C ′ L γ 2 n+1 φ(Y n ) 2 -γ n+1 ∇Λ(θ n ) | H(θ n , Y n ) -H(θ * , Y n ) -γ n+1 ∇Λ(θ n ) | H(θ * , Y n ) .
(2.17)

We set V n :=

A n B n
, n ≥ 1 where

A n := Λ(θ n ) + n-1 k=0 γ k+1 ∇Λ(θ k ) | H(θ k , Y k ) -H(θ * , Y k ) , B n := n k=1 1 + C ′ L γ 2 k φ(Y k-1 ) 2 .
Using the mean-reverting assumption (2.15) implies that (A n ) n≥0 is a nonnegative process and B n is

F n-1 -adapted, n ≥ 1. Elementary computations first show that E [A n+1 | F n ] ≤ A n B n+1 B n -γ n+1 ∇Λ(θ n ) | H(θ * , Y n ) which finally yields ∀n ≥ 0, E [V n+1 | F n ] ≤ V n -∆W n+1 , (2.18)
where

W n := n-1 k=0 γ k+1 ∇Λ(θ k ) | H(θ * , Y k
) with γ n := γn Bn , n ≥ 0. Second step: Now our aim is to prove that the sequence (W n ) n≥0 is L 1 -bounded and a.s. converges. To this end we set S * n := n-1 k=0 H(θ * , Y k ), then it follows

W n = n-1 k=0 γ k+1 ∇Λ(θ k ) | ∆S * k+1 = γ n ∇Λ(θ n-1 ) | S * n - n-1 k=1 S * k | γ k+1 ∇Λ(θ k ) -γ k ∇Λ(θ k-1 ) .
First, since ∇Λ is bounded, note that

γ n |∇Λ(θ n-1 )| |S * n | ≤ ∇Λ ∞ nε n γ n |S * n | nε n ≤ ∇Λ ∞ nε n γ n |S * n |
S * k | γ k+1 ∇Λ(θ k ) -γ k ∇Λ(θ k-1 ) = n-1 k=1 S * k | ∇Λ(θ k ) ∆ γ k+1 + n-1 k=1 γ k S * k | ∇Λ(θ k ) -∇Λ(θ k-1 ) . As ∇Λ = ∇L 2 √ 1 + L is bounded by construction, we have n k=1 |∆ γ k+1 S * k | ∇Λ(θ k ) | ≤ n k=1 |∆ γ k+1 | |S * k | ∇Λ ∞ ≤ ∇Λ ∞ n k=1 kε k |∆ γ k+1 | S * k kε k . Now, using that a 1+a ≤ √ a, a > 0, |∆ γ k+1 | ≤ |∆γ k+1 | + γ k C ′ L γ 2 k+1 φ(Y k ) 2 B k+1 ≤ |∆γ k+1 | + γ k C ′ L γ 2 k+1 φ(Y k ) 2 1 + C ′ L γ 2 k+1 φ(Y k ) 2 ≤ |∆γ k+1 | + C ′ L γ k γ k+1 φ(Y k ).
Hence

n k=1 |∆ γ k+1 S * k | ∇Λ(θ k ) | ≤ ∇Λ ∞ n k=1 kε k |∆γ k+1 | S * k kε k + C ′ L n k=1 kε k γ k γ k+1 φ(Y k ) S * k kε k . By Hölder's Inequality E φ(Y k ) S * k kε k ≤ φ(Y k ) p p-1 S * k kε k p . As S * k kε k n≥0 is bounded, γ is admissible and sup k≥0 φ(Y k ) p p-1 < +∞, then the series n k=1 ∆ γ k S * k | ∇Λ(θ k )
is absolutely converging in L 1 (P).

We study now the series

n k=1 γ k S * k | ∇Λ(θ k ) -∇Λ(θ k-1
) . We have

|∇Λ(θ k ) -∇Λ(θ k-1 )| ≤ C ′ L |∆θ k | 1 + L(θ k-1 ) ≤ C ′ L γ k |H(θ k-1 , Y k-1 )| + |∆M k | 1 + L(θ k-1
) .

We are interested in the L 1 -convergence of the series

n k=1 γ 2 k |S * k | |H(θ k-1 , Y k-1 )| 1 + L(θ k-1 ) and n k=1 γ 2 k |S * k | |∆M k | 1 + L(θ k-1
) .

For the first sum, as

|H(θ k-1 , Y k-1 )| 1 + L(θ k-1 ) ≤ C H φ(Y k-1 ), we then come to n k=1 C H γ 2 k E [|S * k | |φ(Y k-1
)|] and by Hölder's inequality we obtain

E [|S * k | |φ(Y k-1 )|] ≤ S * k p φ(Y k-1 ) p p-1 < +∞ because S * k p = O (kε k ) by (2.8) and sup n≥0 φ(Y n ) p p-1 < +∞. Furthermore, as k≥1 kε k γ 2 k < +∞ by (2.14), then the series n k=1 γ 2 k |S * k | |H(θ k-1 , Y k-1 )| 1 + L(θ k-1 ) converges in L 1 .
For the second sum, we derive from Hölder's inequality (with p and p p-1 ) and (2.13) that

E |S * k | |∆M k | 1 + L(θ k-1 ) ≤ S * k p |∆M k | 1 + L(θ k-1 ) p p-1 ≤ C M S * k p φ(Y k-1 ) p p-1 ∨2 < +∞.
This yields that

n k=1 γ 2 k |S * k | |∆M k | 1 + L(θ k-1 )
converges in L 1 too. Finally we then obtain that W n a.s.

-→ n→∞ W ∞ and sup n≥0 W n 1 < +∞. Thus we have that

(V n + W n ) -≤ W - n ≤ |W n | ∈ L 1 (P) since sup n≥0 W n 1 < +∞. As V 0 = Λ(θ 0 ) ≤ C(1+|θ 0 |) ∈ L 1 , it follows by induction from (2.18) that, for every n ≥ 0, E V n < +∞. Hence S n := V n + W n , n ≥ 0, is a true supermartingale with an L 1 -bounded negative part. We then deduce that S n a.s. -→ n→∞ S ∞ ∈ L 1 . Now W n a.s. -→ n→∞ W ∞ implies V n a.s. -→ n→∞ V ∞ < +∞ a.s.
Third step: Now we show that the product B n converges a.s. to derive that A n converges a.s..

In fact n≥1 γ 2 n φ 2 (Y n-1 ) < +∞ a.s., since sup n≥0 E φ 2 (Y n ) < +∞
γ n ∇Λ(θ n-1 ) | H(θ n-1 , Y n-1 ) -H(θ * , Y n-1 ) < +∞ a.s. (2.19) Consequently Λ(θ n ) a.s. -→ n→∞ Λ ∞ < +∞ a.s. As lim |θ|→+∞ L(θ) = +∞, lim |θ|→+∞ Λ(θ) = +∞, then the sequence (θ n ) n≥0 is a.s.-bounded and L(θ n ) a.s. -→ n→∞ L ∞ < +∞ a.s. Now let us show that ∆θ n -→ n→+∞ 0. In fact, |∆θ n+1 | 2 ≤ Cγ 2 n+1 |H(θ n , Y n )| 2 + |∆M n+1 | 2 , so that E |∆θ n+1 | 2 | F n ≤ Cγ 2 n+1 φ(Y n ) 2 (1 + L(θ n )) and (L(θ n )) n≥0 being a.s. bounded, n≥0 E |∆θ n+1 | 2 | F n < +∞. a.s.
which classically implies that n≥0 |∆θ n+1 | 2 < +∞ a.s.

Fourth step: To prove the convergence of θ n toward θ * , we use Assumptions (2.15) and (2. [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF]) to deduce that

n≥1 γ n χ δ (Y n-1 )Ψ δ (θ n-1 ) < +∞ a.s. (2.20) Now, n k=0 γ k+1 χ δ (Y k ) = n k=0 γ k+1 ∆S χ k = γ n+1 S χ n - n-1 k=1 ∆γ k+2 S χ k where S χ n = n k=0 χ δ (Y k ) and we set S χ 0 = 0 and ∆S χ 0 = 0. By Assumption (2.5), S χ n n → ν(χ δ ) > 0 as n → ∞. Let n 0 be the smallest integer such that ∀n ≥ n 0 , S χ n n ≥ ǫ 0 = ν(χ δ ) 2 > 0.
Then, a standard discrete integration by part yields

∀n ≥ n 0 , n k=n 0 γ k+1 χ δ (Y k ) = nγ n+1 S χ n n -C n 0 + n-1 k=n 0 k(-∆γ k+2 ) S χ k k a.s.,
where

C n 0 = γ n 0 +1 S χ n 0 -1 . Therefore, using that the sequence (-∆γ n ) n≥1 is nonnegative, n k=n 0 γ k+1 χ δ (Y k ) ≥ nγ n+1 ǫ 0 -C n 0 + n-1 k=n 0 k(-∆γ k+2 )ǫ 0 = ǫ 0 nγ n+1 + n-1 k=n 0 k(-∆γ k+2 ) -C n 0 = ǫ 0 γ n+1 + n 0 γ n 0 +1 + n-1 k=n 0 +1 γ k+1 -C n 0
by a reverse discrete integration by parts. Finally

n k=n 0 γ k+1 χ δ (Y k ) ≥ ǫ 0 γ n+1 + n-1 k=n 0 +1 γ k+1 -C n 0 → ∞ as n → ∞ since n≥1 γ n = +∞. We have then shown that k≥0 γ k+1 χ δ (Y k ) = +∞ a.s.
Combining this fact with (2.20) classically implies that

lim inf n Ψ δ (θ n ) = 0. Let Θ ∞ be the set of limiting points of the sequence (θ n ) n≥0 . Θ ∞ is a compact connected set since (θ n ) n≥0 is bounded and ∆θ n -→ n→∞ 0. Moreover {Ψ δ = 0} is closed because Ψ δ ≤ 0 and l.s.c. and Θ ∞ is closed too. So Θ ∞ ∩ {Ψ δ = 0}
is a family of nonempty compact sets which decreases as δ ց 0 since it is bounded. As a consequence,

δ>0 (Θ ∞ ∩ {Ψ δ = 0}) = ∅.
The other assumption on Ψ δ implies δ>0

(Θ ∞ ∩ {Ψ δ = 0}) ⊂ δ>0 {Ψ δ = 0} = {θ * },
so that in fact it is reduced to θ * . Hence θ * is a limiting point of (θ n ) n≥0 which implies that L(θ n ) converges towards L(θ * ). By the assumption on the Lyapunov function L,

{θ * } is a connected component of {L = L(θ * )} and as Θ ∞ is connected, Θ ∞ = {θ * }. Therefore θ n a.s.
-→ θ * as n → ∞.

Back to the i.i.d. innovation setting. ⊲ Theorem 2.1 contains the standard martingale approach "à la" Robbins-Siegmund in the i.i.d. setting. Indeed, we consider the recursive procedure

θ n+1 = θ n -γ n+1 K(θ n , Y n+1 ), n ≥ 0,
where (Y n ) n≥1 is i.i.d. with distribution ν and θ 0 is independent of (Y n ) n≥1 (all defined on (Ω, A, P)).

We set

F n = σ(θ 0 , Y 1 , . . . , Y n ), n ≥ 0, p = 2, H(θ, y) = h(θ) with h(θ) = R q K(θ, y)ν(dy) and ∆M n+1 = K(θ n , Y n+1 ) -E [K(θ n , Y n+1 ) | F n ] . Assume that ∀θ ∈ R d , K(θ, Y 1 ) 2 ≤ C K (1 + L(θ)) 1 2 .
Then Assumption (2.12) is satisfied by h and (2.13) holds (with φ ≡ 1). Furthermore, by combining (2.7) and (2.14), we retrieve the step assumption in the standard Robbins-Monro Theorem, namely

n≥1 γ n = +∞ and n≥1 γ 2 n < +∞.
⊲ Another (naive) way to apply Theorem 2.1 in this i.i.d. setting is to focus, under the above assumption on the averaging property so that: then H = K and ∆M n ≡ 0. We still consider the above procedure but we assume furthermore the existence of a pathwise Lyapunov function. By noticing that (K(θ * , Y n )) n≥1 is i.i.d. and in L 2 , it follows from the quadratic law of large numbers (at rate n -1 2 ) and the Law of Iterated Logarithm at rate

O(ε n ) with ε n = log log n n that K(θ * , •) ∈ V εn,2 .
As a consequence the condition (2.14) is clearly more restrictive than the above regular one, however any step of the form

γ n = c n α , c > 0, 3 4 < α ≤ 1 satisfies (2.14).

The case of multiplicative noise

If we assume that the function H in (2.4) is of the following form

∀θ ∈ R d , ∀y ∈ R q , H(θ, y) = χ(y)h(θ) + H(θ * , y), (2.21)
where χ is a Borel function such that ν

(χ) = 1, χ ∈ V εn,p and sup n≥0 χ(Y n ) 2∨ p p-1 < +∞, H(θ * , •) ∈ V εn,p and sup n≥0 H(θ * , Y n ) 2∨ p p-1
< +∞, h is Lipschitz bounded with h(θ * ) = 0, then we replace the growth assumption (2.12) on H by one on the mean function h, i.e.

∀θ ∈ R d , ∀y ∈ R q , |h(θ)| ≤ C h 1 + L(θ) (2.22)
and the pathwise mean-reverting assumption (2.15) is the classical -→ n→∞ θ * .

∀θ ∈ R d \ {θ * }, ∇L | h (θ) > 0. ( 2
Proof. First step: This setting cannot be reduced to the general setting. We use the same notations as in the proof of Theorem 2.1. With the new form of the function H, we obtain

Λ(θ n+1 ) ≤ Λ(θ n ) -γ n+1 ∇Λ(θ n ) | χ(Y n )h(θ n ) -γ n+1 ∇Λ(θ n ) | H(θ * , Y n ) -γ n+1 ∇Λ(θ n ) | ∆M n+1 + C L γ 2 n+1 |H(θ n , Y n ) + ∆M n+1 | 2 1 + L(θ n ) .
By the same arguments as before we get

E [Λ(θ n+1 ) | F n ] ≤ Λ(θ n ) 1 + C ′ L γ 2 n+1 φ(Y n ) 2 -γ n+1 ∇Λ(θ n ) | χ(Y n )h(θ n ) -γ n+1 ∇Λ(θ n ) | H(θ * , Y n ) .
We set

V n := A n B n
, where

A n := Λ(θ n ) + n-1 k=0 γ k+1 ∇Λ | h (θ k ) and B n := n k=1 1 + C ′ L γ 2 k φ(Y k-1 ) 2 . Using the mean-reverting assumption (2.23) implies that (A n ) n≥0 is a nonnegative process whereas (B n ) n≥0 is still F n-1 -adapted. Elementary computations show that E [A n+1 | F n ] ≤ A n B n+1 B n -γ n+1 ∇Λ(θ n ) | H(θ * , Y n ) -γ n+1 χ(Y n ) ∇Λ | h (θ n ) where χ(Y n ) := χ(Y n ) -ν(χ), n ≥ 0. Finally we have ∀n ≥ 0, E [V n+1 | F n ] ≤ V n -∆W n+1 -∆Z n+1 , (2.24)
where

W n := n-1 k=0 γ k+1 ∇Λ(θ k ) | H(θ * , Y k ) and Z n := n-1 k=0 γ k+1 χ(Y k ) ∇Λ | h (θ k ) with γ n := γn Bn , n ≥ 0.
Second step: Following the lines of the proof of Theorem 2.1 we show that the sequence (W n ) n≥0 is L 1 -bounded and a.s. converges. Now our aim is to prove the same results for the sequence (Z n ) n≥0 .

To this end we set S χ n := n-1 k=0 χ(Y k ), then it follows

Z n = n-1 k=0 γ k+1 ∆S χ k+1 ∇Λ | h (θ k ) = γ n S χ n ∇Λ | h (θ n-1 )- n-1 k=1 S χ k ( γ k+1 ∇Λ | h (θ k ) -γ k ∇Λ | h (θ k-1 )) .
By the same methods as for the sequence (W n ) n≥0 (i.e. using assumptions on H, Λ and (γ n ) n≥1 ), we obtain that

Z n a.s. -→ n→∞ Z ∞ and sup n≥0 Z n 1 < +∞.
Thus we have that

(V n + W n + Z n ) -≤ (W n + Z n ) -≤ |W n + Z n | ∈ L 1 (P) since sup n≥0 W n + Z n 1 < +∞. As V 0 = Λ(θ 0 ) ≤ C(1+|θ 0 |) ∈ L 1
, it follows by induction from (2.18) that, for every n ≥ 0, E V n < +∞. Hence S n := V n + W n + Z n , n ≥ 0, is a true supermartingale with a L 1 -bounded negative part. We then deduce that S n a.s.

-

→ n→∞ S ∞ ∈ L 1 . Now W n a.s. -→ n→∞ W ∞ and Z n a.s. -→ Z ∞ imply that V n a.s. -→ n→∞ V ∞ < +∞ a.s.
Third step: Like in the proof of Theorem 2.1, we have that B n a.s.

-→ n→∞ B ∞ < +∞ which implies that

A n a.s.
-→ n→∞ A ∞ < +∞. Therefore using the mean-reverting property (2.23) of h with respect to ∇Λ, we classically derive that

n≥0 γ n+1 ν(χ) ∇Λ | h (θ n ) < +∞ a.s.
(2.25)

The end of the proof follows the lines of the one of Theorem 2.1.

Application to quasi-stochastic approximation

This section is devoted to quasi-random innovations: the innovation sequence (Y n ) n≥0 becomes a deterministic uniformly distributed (u.d.) sequence (ξ n+1 ) n≥0 over a unit hypercube [0, 1] q , i.e.

θ n+1 = θ n -γ n+1 H(θ n , ξ n+1 ), n ≥ 0, θ 0 ∈ R d .
We extend the one-dimensional result first introduced in [START_REF] Lapeyre | Sequences with low discrepancy-generalisation and application to Robbins-Monro[END_REF] (see more recently [START_REF] Mehta | Q-learning and Pontryagin's minimum principle[END_REF][START_REF] Shirodkar | Quasi stochastic approximation[END_REF]) to a general multi-dimensional setting with unbounded function H. We first recall few definitions and properties of u.d. sequences (see [START_REF] Niederreiter | Random number generation and quasi-Monte Carlo methods[END_REF] and the reference therein). We emphasize how to apply Theorem 2.1 when H has "bounded variation" on [0, 1] q and when H is Lipschitz continuous.

Definition and characterisation

Definition 3.1. A [0, 1] q -valued sequence (ξ n ) n≥1 is uniformly distributed (u.d.) on [0, 1] q if 1 n n k=1 δ ξ k (R q ) =⇒ U ([0, 1] q ) as n → ∞.
The proposition below provides a characterisation of uniform distribution for a sequence (ξ n ) n≥1 . . We refer to [START_REF] Niederreiter | Random number generation and quasi-Monte Carlo methods[END_REF][START_REF] Bouleau | Numerical methods for stochastic processes[END_REF] for examples of such sequences (like Halton, Kakutani, Sobol' sequences, etc).

Proposition 3.1. (a) Let (ξ n ) n≥1 be a [0, 1] q -valued sequence. Then (ξ n ) n≥1 is uniformly distributed on [0, 1] q if and only if D * n (ξ) := sup x∈[0,1] q 1 n n k=1 1 0,x (ξ k ) - q i=1 x i -→ 0 as n → ∞,

Standard classes V εn,1 for quasi-stochastic approximation

We set here Y n = ξ n+1 , F n = {∅, Ω} and ∆M n+1 ≡ 0, n ≥ 0. The strong Lyapunov condition on H is crucial here. Note that the function φ becomes useless since we always consider the case p = 1. To apply Theorem 2.1, we mainly need to specify the accessible classes V εn,1 in such a framework.

⊲ Function with finite variation. A function f : [0, 1] q → R has finite variation in the measure sense if there exists a signed measure ν on ([0, 1] d , Bor([0, 1] q ) such that ν({0}) = 0 and

∀ x ∈ [0, 1] q , f (x) = f (1) + ν([[0, 1 -x]]) where [[x, y]] = q i=1 [x i , y i ] if x ≤ y (componentwise)
and is empty otherwise and 1 = (1, . . . , 1). The variation V (f ) of f is then defined as |ν|([0, 1] q ) where ν denotes the total variation measure attached to ν. For further details on this notion of variation, see [START_REF] Bouleau | Numerical methods for stochastic processes[END_REF]. When q = 1 this notion coincide with left continuous functions with finite variations. As concerns the slightly more general notion of finite variation in the the Hardy and Krause sense, see [START_REF] Niederreiter | Random number generation and quasi-Monte Carlo methods[END_REF] and the references therein). The role of finite variation is emphasized by the following error bound. Proposition 3.2 (Koksma-Hlawka Inequality). Let ξ = (ξ 1 , . . . , ξ n ) ∈ ([0, 1] q ) n and let f be a function with finite variation V (f ), either in the Hardy & Krause or in the measure sense. Then

1 n n k=1 f (ξ k ) - [0,1] q f (u)λ q (du) ≤ V (f )D * n (ξ). Hence, if (ξ n ) n≥1 has a low discrepancy, the class V = {f : [0, 1] q → R s.t. V (f ) < +∞} of functions with finite variations satisfies V ⊂ V εn,1 with ε n = (log n) q n
. Consequently, if H(θ, •) ∈ V, the assumptions on admissible (non-increasing) step sequences (γ n ) n≥1 in Theorem 2.1 reads

n≥1 γ n = +∞, γ n (log n) q → 0 and k≥1 max(|∆γ n+1 | , γ 2 n )(log n) q < +∞.
so that the choice of γ n := c n ρ , 1 2 < ρ ≤ 1, is admissible (like in the i.i.d. setting). ⊲ Lipschitz continuous functions. If q ≥ 2 it is difficult to check whether f has finite variations in any sense: in fact these functions become "rare" as q increases. If we look for more natural regularity assumption to be satisfied by H(θ * , •) like Lipschitz continuity, the following theorem due to Proinov (see [START_REF] Proȋnov | Discrepancy and integration of continuous functions[END_REF]) provides an alternative (but less "attractive") error bound. Theorem 3.1. (Proinov) Assume R q is equipped with the ℓ ∞ -norm (x 1 , . . . , x q ) ∞ := max 1≤i≤q x i . Let (ξ 1 , . . . , ξ n ) ∈ ([0, 1] q ) ⊗n . For every continuous function f : [0, 1] q → R,

1 n n k=1 f (ξ k ) - [0,1] q f (u)λ q (du) ≤ C q w f D * n (ξ 1 , . . . , ξ n ) 1 q
where w f (δ) := sup

x,y∈[0,1] q ,|x-y| ∞ ≤δ |f (x) -f (y)|, δ ∈ (0, 1), is the ℓ ∞ -uniform continuity modulus of f and C q ∈ (0, ∞) is a universal constant only depending on q. If q = 1, C q = 1 and if q ≥ 2, C q ∈ [1, 4]. As a consequence Lip([0, 1] q , R) ⊂ V εn,1 with ε n = log n n 1 q
(with obvious extensions to Hölder functions).

Consequently, if H(θ * , •) ∈ V, the assumptions on admissible (non-increasing) step sequences (γ n ) n≥1 in Theorem 2.1 reads

n≥1 γ n = +∞, γ n (log n)n 1-1 q → 0 and k≥1 max(|∆γ n+1 | , γ 2 n )(log n)n 1-1 q < +∞.
so that the choice of γ n := c n is always admissible (more generally γ n = cn -ρ , 1 -1 q < ρ ≤ 1). An application of "quasi-Stochastic Approximation" is proposed in Section 5.1 (see also [START_REF] Frikha | Contribution à la modélisation et à la gestion dynamique du risque des marchés de l'énergie[END_REF]).

Applications to different types of random innovations

This section is devoted to some first applications of the above theorem. By applications, we mean here printing out some classes of random innovation processes (Y n ) n≥0 for which the averaging rate assumption (2.8) is naturally satisfied by "large" class V εn,p .

First we present a simple framework of stochastic approximation where the noise is additive which is studied in [START_REF] Dedecker | Weak dependence: with examples and applications[END_REF] with some mixing properties, but here we only need (2.5). We showed in [START_REF] Laruelle | Optimal split of orders across liquidity pools: a stochastic algorithm approach[END_REF] how easily our result applies to real life stochastic optimization problem (as far as convergence is concerned).

Afterwards we focus on mixing innovations: we consider that the sequence (Y n ) n≥0 is a functional of a stationary α-mixing process (satisfying condition on the summability of the mixing coefficients).

The last application is the case of an homogeneous Markov chain which can be seen as a possible more elementary counterpart of some (convergence) result obtained e.g. in [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF]. Some (quasi-optimal) a.s. rate of convergence can be obtained if H is smooth enough in θ (see [START_REF] Laruelle | Analyse d'algorithmes stochastiques appliqués à la Finance[END_REF]), but to establish a regular Central Limit Theorem it is most likely that we cannot avoid to deal with the Poisson equation.

Recursive procedure with additive noise

We consider here the case where the function H is the sum of the mean function h and a noise, namely ∀θ ∈ R d , ∀y ∈ R q , H(θ, y) = h(θ) + y, and ∆M n+1 ≡ 0.

In this framework, the Lyapunov assumption (2.15) becomes classical involving only the mean function

h, namely ∀θ ∈ R d \ {θ * } ∇L | h (θ) > 0.
Likewise, the growth control assumption (2.12) amounts to

∀θ ∈ R d , |h(θ)| ≤ C h 1 + L(θ), provided the moment assumption sup n Y n p p-1
< +∞, for some p ∈ (1, ∞], is satisfied (take φ(y) := |y| ∨ 1). The martingale is vanishing in this example. Finally the step assumption (2.14) is ruled by the averaging rate of the sequence (Y n ) n≥0 .

Functional of a stationary α-mixing process

Here we provide a short background on α-mixing processes and their functionals. Our motivation here is to relax as much as possible our assumption on (Y n ) n≥0 in order to apply stochastic approximation methods to exogenous possibly non Markovian stationary data.

We aim now at applying our convergence theorem to input sequences (Y n ) n≥0 which are (causal) functionals of an α-mixing process. Consider a stationary R q -valued process X = (X k ) k∈Z , its natural filtration

F n = F X n := σ(X k , k ≤ n) and G n = G X n := σ(X k , k ≥ n).
The α-mixing coefficients are defined as follows

α n = sup {|P(U ∩ V ) -P(U )P(V )| , U ∈ F k , V ∈ G k+n , k ≥ 0} . (4.26)
Let f be a measurable mapping from (R q ) Z to R. Let (Y k ) k∈Z be a causal functional of X, i.e.

∀n ∈ Z, Y n := f (. . . , X n-1 , X n ). Then (Y n ) n≥0 is a stationary process with marginal distribution ν = L(Y 0 ). The proposition below show that if (X n ) n∈Z is α-mixing "fast enough" then H(θ * , •) "almost" lies in V n -1 2 ,2
(up to logarithmic factor) as soon as E|H(θ * , Y 0 )| 2+δ < +∞ for a δ > 0 (so is true for H(θ, •) since we do not know θ * a priori).

Proposition 4.1. Assume g ∈ L 2+δ (ν), δ > 0, and that one of the following assumptions holds (a) For all n ∈ Z, Y n := f (. . . , X n-1 , X n ) where X is a stationary α-mixing process satisfying

k≥1 α δ 2(2+δ) k √ k < +∞ (4.27)
and assume the following regularity assumption on f

∀ 0 ≤ k ′ ≤ k, E [g(Y k ) -g(f ((0, . . . , 0, X k ′ , . . . , X k )) | F 0 ] 2 ≤ Ca k-k ′ (4.28)
for a real constant C > 0 and a nonnegative real sequence (a k ) k≥0 satisfying (4.30)

k≥1 a k √ k < +∞. (4.29) (b) Y n = X n , n ≥ 0,
Then g ∈ V ε (η) n ,2 , with ε (η) n = (log n) 3 2 +η n -1 2
, for every η > 0. (4.31) In particular g lies in V n -β ,2 for every β ∈ (0, 1 2 ).

Remarks. Condition (4.30) is satisfied when the underlying process X is geometrically α-mixing.

Slightly refined results could be obtained by calling upon Philip and Stout's Law of Iterated Logarithm but the resulting claims would be significantly more technical to state for little practical benefit.

An applicationof this result (based on real data) is briefly developed in Section 5.5. The proof of Proposition4.1 relies on the Gàl-Koksma Theorem (see [START_REF] Gál | Sur l'ordre de grandeur des fonctions sommables[END_REF] and [START_REF] Pagès | Sur la méthode du shift en simulation[END_REF] for a probabilistic version). We state it here in a stationary framework. Theorem 4.1. (Gàl-Koksma's Theorem) Let (Ω, F, P) be a probability space and let (Z n ) n≥1 be a sequence of random variables belonging to L p , p ≥ 1, satisfying

E |Z 1 + Z 2 + • • • + Z N | p = O(Ψ(N ))
where Ψ(N ) N , N ≥ 1, is a nondecreasing sequence. Then for every η > 0,

Z 1 (ω) + Z 2 (ω) + • • • + Z N (ω) = o (Ψ(N )(log(N )) p+1+η ) 1 p P(dω)-a.s.
Remark. The conditions on X and Z come from a result established in [START_REF] Dedecker | On the weak invariance principle for non-adapted sequences under projective criteria[END_REF]: by setting

P 0 (Z k ) := E [Z k | F 0 ] -E [Z k | F -1 ], if k∈Z P 0 (Z k ) 2 < +∞ then k∈Z |Cov(Z 0 , Z k )| < +∞. (4.32)
Moreover using [START_REF] Peligrad | Central limit theorem for stationary linear processes[END_REF], condition (4.32) is satisfied as soon as

∞ k=1 1 √ k E [Z k | F 0 ] 2 < +∞. (4.33)
Proof of Proposition 4.1. Let Z n = g(Y n ) -R q g(y)ν(dy), n ∈ Z. Without loss of generality we may assume R q g(y)ν(dy) = 0.

(a) We will rely on the above Gal-Koksma Theorem (Theorem 4.1). First, we evaluate

E |Z 0 + • • • + Z n-1 | 2 . Setting S Z k = k j=1 E [Z j Z 0 ], k ∈ N, elementary computations lead to E |Z 0 + • • • + Z n-1 | 2 = nEZ 2 0 + 2 n-1 k=1 k j=1 E [Z j Z 0 ] = nEZ 2 0 + 2 n-1 k=1 S Z k = n EZ 2 0 + 2 n n-1 k=1 S Z k .
To establish that S Z n converges, we will establish (4.33).We set, for 0

≤ k ′ ≤ k, F k ′ ,k = σ(X ℓ , k ′ ≤ ℓ ≤ k). Then Z k = Z k -E[Z k | F k ′ ,k ] + E[Z k | F k ′ ,k ].
We derive from the definition of conditional expectation that

E Z k -E[Z k | F k ′ ,k ] | F 0 2 ≤ Z k -E[Z k | F k ′ ,k ] 2 ≤ Z k -g • f (. . . , 0, . . . , 0, X k ′ , . . . , X k ) 2 so that E [Z k | F 0 ] 2 ≤ E Z k -E[Z k | F k ′ ,k ] | F 0 2 + E E[Z k | F k ′ ,k ] | F 0 2 ≤ E [g • f (. . . , X 0 , . . . , X k ′ , . . . , X k ) -g • f (, . . . , 0, X k ′ , . . . , X k ) | F 0 ] 2 + E E[Z k | F k ′ ,k ] | F 0 2 ≤ Ca k-k ′ + α 1 r k ′ g • f (0, . . . , 0, X k ′ , . . . , X k ) p
owing to Assumption (4.28) on g • f and the classical covariance inequality for α-mixing process (see [START_REF] Doukhan | Mixing[END_REF], Theorem 3(1), p.9) with 1 r + 1 p = 1 2 , r, p > 2. As g ∈ L 2+δ (ν), δ > 0, we may set p = 2 + δ, r = 2(2+δ) δ and k ′ = k/2. Then we obtain

E [Z k | F 0 ] 2 ≤ Ca k/2 + α δ 2(2+δ) k/2 g • f (0, . . . , 0, X k/2 , . . . , X k ) 2+δ .
As a consequence, by using (4.27) and (4.29), we have

∞ k=1 1 √ k E (Z k | F 0 ) 2 < +∞,
which implies (owing to (4.32)) that S Z k converges. Now, by Cesaro's Lemma we have

E |Z 0 + • • • + Z n-1 | 2 = O(n) or equivalently 1 n Z 0 + • • • + Z n-1 ) 2 = O n -1 2 .
Thus, one concludes by by Gal-Koksma's Theorem since, for every η > 0,

Z 0 + • • • + Z n-1 n = o (log n) 3 2 +η
√ n P-a.s.

(b) If we assume that Y n = X n , n ≥ 0, we directly use the covariance inequality for α-mixing process

|Cov (Z j , Z 0 )| ≤ 8α 1 r j Z 0 p Z 0 q ,
where 1 r + 1 p + 1 q = 1. By symmetry, we take p = q > 2 and we get

E Z j Z 0 ≤ 8α 1-2 p j Z 0 2 p .
As g ∈ L 2+δ , δ > 0, we may set p = 2 + δ and we obtain α

Homogeneous Markov chain

Assume that the innovation process (Y n ) n≥0 is an R q -valued homogeneous Markov chain which transition is (P (y, dz)) y∈R q and starting distribution µ = L(Y 0 ). For convenience we will assume that the chain lives on its canonical space ((R q ) N , Bor(R q ) ⊗N ).

Application of the convergence theorem

We consider the classical Markov stochastic approximation procedure procedure

θ n+1 = θ n -γ n+1 K(θ n , Y n+1 ), n ≥ 0, (4.34)
where K : R d × R q → R d is a Borel function satisfying (4.35) below and θ 0 : (Ω, A, P) → R d is independent of (Y n ) n≥0 . Note that (Y n ) n≥0 remains is still a Markov chain with respect to F n = σ(θ 0 , Y 0 , . . . , Y n ), n ≥ 0. Set H(θ, y) := P K(θ, .) (y) and ∆M

n+1 := K(θ n , Y n+1 ) -E [K(θ n , Y n+1 ) | F n ].
Then the procedure has the canonical form (1.2) with respect to the filtration (F n ) n≥0 .

Remark. If we consider that the Markov chain starts from Y 1 , then

F n = σ(θ 0 , Y 1 , . . . , Y n ) and E K(θ 0 , Y 1 )|F 0 = E [K(θ, Y 1 )] |θ=θ 0 = µP (K(θ, .)) |θ=θ 0 since θ 0 and Y 1 are independent. Let p ∈ [1, ∞) and set r = 2 ∨ p p-1 ∈ [2, +∞].
We make the following growth assumption on the function K

∀θ ∈ R d , ∀y ∈ R q , |K(θ, y)| ≤ C K φ(y) 1 + L(θ) (4.35)
where L : R d → R + satisfies (2.9) and sup n≥0 φ(Y n ) r < +∞. Then H satisfies (2.12) with φ(y) = P φ(y) = E y φ(Y 1 ) ≤ φ L r (P (y,dz)) < +∞ and ∆M n+1 satisfies (2.13) with φ(y) = φ L r (P (y,dz)) so that, finally, we may choose φ(y) = φ L r (P (y,dz)) , having in mind -→ n→+∞ θ * .

that φ(Y n ) r = φ(Y n+1 ) r .

Ergodic framework description

We will say that the Markov chain (Y n ) n≥0 (starting from Y 0 L ∼ µ) is ν-ergodic (resp. ν-stable) under P µ if for every bounded Borel (resp. continuous) function f : R q → R, P µ -a.s.

1

n n-1 k=0 f (Y k ) -→ n→∞ R q f dν. (4.36)
As soon as the transition (P (y, dz)) y∈R q of (Y n ) n≥0 is Feller, the above ν-stability property implies that ν is an invariant distribution of the chain, i.e. νP = ν. In case of ν-ergodicity the same conclusion holds unconditionally. As a consequence the whole sequence (Y n ) n≥0 is stationary under P ν .

Let us focus on the case µ = ν. If (4.36) holds (with µ = ν), it is classical background that the whole chain is ergodic under P ν (on the canonical space) for the shift operator Θ, i.e. by Birkhoff's theorem, for every functional F : ((R q ) N , Bor(R q ) ⊗N ) → R, F ∈ L p (P ν ),

1 n n-1 k=0 F • Θ k -→ n→∞ E ν (F ) P ν -a.s. and in L p (P ν ), so that by considering F ((y n ) n≥0 ) = f (y 0 ), f ∈ L p (ν), we finally get that V 0 + ,p (P ν ) = L p (ν).
Note that if the set of invariant distributions for P (convex and) weakly compact and if ν is extremal in it (so will be e.g. the case if ν is unique!) then the chain is ergodic under P ν so that the above equality still holds. Furthermore, we know by a straightforward application of Gàl-Koksma Theorem that for any g ∈ L 2 (ν) for which the related Poisson Equation gν(g) = ϕ g -P ϕ g has a solution ϕ g ∈ L 2 (ν), then

E ν |g(Y 0 ) + • • • + g(Y n-1 ) -nν(g)| 2 = E ν |ϕ g (Y 0 ) -P ϕ g (Y n-1 ) + 1≤k≤n-2 ϕ g (Y k ) -P ϕ g (Y k-1 )| 2 ≤ 6ν(ϕ 2 g ) + 3(n -2)ν (ϕ g -P ϕ g ) 2 = O(n) so that β∈(0, 1 2 ) V n -β ,2 (P ν ) ⊃ L 2 (ν).
Now we will make a connection between the classes V εn,p (P ν ) and V εn,p ′ (P y ) which will provide examples of non-stationary (Markovian) innovations that can be "plugged" in stochastic Approximation procedures in the spirit of Theorem 2.1.

Proposition 4.3. Let p ∈ [1, +∞) and let p ′ ∈ (0, p]. If (Y n ) n≥0 is P ν -ergodic and P (y, dz) = g(y, z)ν(dz), y ∈ R q where g : (R q ) 2 → R + satisfies ν(dz)-a.e., g(•, z) > 0. Then ν is the unique invariant distribution of P and for every sequence (ε n ) n≥0 satisfying (2.7),

∀y ∈ R q , g(y, •) ∈ L p p-p ′ (ν) =⇒ V εn,p ′ (P y ) ⊃ V εn,p (P ν ).
Proof. It follows form the assumption that any invariant distribution ν ′ is equivalent to ν which implies classically uniqueness.

⊲ The a.s. rate. Let f ∈ L p (ν), y ∈ R q and A f := ω : 1 n n-1 k=0 f (Y k (ω)) - R q f dν = O(ε n ) . Since lim inf n nε n > 0, if Θ denotes the shift operator on the canonical space of the chain (Y n ) n≥0 , A f clearly satisfies A f = Θ -1 (A f ) i.e. 1 A f = 1 A f • Θ. Therefore P y (A f ) = E y (1 A f ) = E y (1 A f • Θ) = E y (P Y 1 (A f )).
Assume now f ∈ V εn,p (P ν ). By assumption

P ν (A f ) = 1. Let y ∈ R q . Then P ν (A f ) = R q ν(dz)P z (A f ) = 1 so that ν(dz)-a.s. P z (A f ) = 1. Now P (y, dz) ≪ ν(dz) implies R q P (y, dz)P z (A f ) = 1 i.e. E y [P Y 1 (A f )] = 1 or equivalently P y (A f ) = 1. ⊲ The L p ′ -rate. Let p ′ ∈ (0, p], let f ∈ V εn,p (P ν ) ⊂ L p (ν) and ϕ n,p ′ (y) := 1 n n-1 k=0 f (Y k (ω)) -R q f dν L p ′ (Py) . 1 n n-1 k=0 f (Y k (ω)) - R q f dν L p (ν) = O(ε n ) so that R q φ p n (y)ν(dy) = O(ε p n ). (4.37)
Assume temporarily that p ′ ≥ 1. Consequently, Minkowski inequality implies

ϕ n,p ′ (y) ≤ f (y) -R q f dν n + 1 - 1 n 1 n -1 n-1 k=1 f (Y k ) - R q f dν L p ′ (Py) = f (y) -R q f dν n + 1 - 1 n   E y   E   1 n -1 n-1 k=1 f (Y k ) - R q f dν p ′ | F 1       1 p ′ = f (y) -R q f dν n + 1 - 1 n ϕ n-1,p ′ (Y 1 ) L p ′ (Py) .
where we used the Markov property in the last equality. Since P (y, dz) = g(y, z)ν(dz), we derive from Hölder's Inequality (applied to r = p p ′ and s = p p-p ′ )

E y ϕ n-1 (Y 1 ) p ′ = R q ϕ n-1 (z) p ′ P (y, dz) = R q ϕ n-1 (z) p ′ g(y, z)ν(dz) ≤ g(y, •) L p p-p ′ (ν) R q ϕ n-1 (y) p ν(dy) p ′ p ≤ g(y, •) L p p-p ′ (ν)
O(ε p ′ n ) owing to (4.37).

Finally

ϕ n (y) ≤ c n + 1 - 1 n g(y, •) p p-p ′ O(ε n ) = O(ε n ) i.
e. f ∈ V εn,p ′ (P y ). The case p ′ ∈ (0, 1) follows by the usual adjustments (pseudo-Minkowski inequality, etc).

Comments. By contrast with the approach of [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF], it is not mandatory to solve the Poisson equation related to the pseudo-transition

Π θn (Y n , dz) = P (Y n+1 ∈ dz | F n )
of the algorithm. Indeed, they assume there exists a function v θ := v(θ, •) solution to

Id -Π θ v θ = H(θ, •) -h(θ) (4.38)
(Assumption (H 4 ) in [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF] p. 220). The target θ * is then a zero of the mean function h (not canonically defined at this stage in [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF]). In our setting, Π θ (y, dz) = P (y, dz) since the dynamics of (Y n )n ≥ 0 does not depend upon θ, so that Condition (4.38) reads

v(θ, y) - R q v(θ, z)P (y, dz) = H(θ, y) -h(θ)
where the mean function is naturally defined by

h(θ) = R q H(θ, y)ν(dy)
(ν is the unique invariant probability measure for P ). Then the family of Poisson equations (indexed by the parameter θ) reads v(θ, y) -P v(θ, y) = H(θ, y)h(θ).

A formal solution is given by v(θ, y) = k≥0 P k (H(θ, •)h(θ)) (y), but the point is precisely to establish its existence and its properties by using the mixing properties of the semi-group P (see [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF]).

Applications and numerical examples

This section is devoted to several examples (mainly inspired by in Finance) of application of convergence theorems in the different frameworks developed in Section 3 and 4.

Application to implicit correlation search by quasi-stochastic approximation

Consider a 2-dimensional Black-Scholes model i.e. X t 0 = e rt (riskless asset) and

∀t ≥ 0, X i t = x i 0 e (r-σ 2 i 2 )t+σ i W i t , x i 0 > 0, i = 1, 2,
for the two risky assets where

W 1 , W 2 t = ρt, ρ ∈ [-1, 1]
. Consider a best-of call option characterized by its payoff max X 1 T , X 2 T -K + . We will use a stochastic recursive procedure to solve the inverse problem in ρ

P BoC (x 1 0 , x 2 0 , K, σ 1 , σ 2 , r, ρ, T ) = P market 0 20
where P market 0 is the quoted premium of the option (mark-to-market) with

P BoC (x 1 0 , x 2 0 , K, σ 1 , σ 2 , r, ρ, T ) := e -rT E max X 1 T , X 2 T -K + = e -rT E max x 1 0 e µ 1 T +σ 1 √ T Z 1 , x 2 0 e µ 2 T +σ 2 √ T ρZ 1 + √ 1-ρ 2 Z 2 -K + where µ i = r - σ 2 i 2 , i = 1, 2, Z = (Z 1 , Z 2 ) d = N (0, I 2 )
. We assume from now on that this equation (in ρ) has at least one solution, say ρ * . The most convenient way to prevent edge effects due to the fact that ρ ∈ [-1, 1] is to use a trigonometric parametrization of the correlation by setting ρ = cos θ, θ ∈ R. This introduces an over-parametrization since θ and 2πθ yield the same solution inside [0, 2π], but this is not at all a significant problem for practical implementation (a careful examination shows that in fact one equilibrium is repulsive and one is attractive). From now on, for convenience, we will just mention the dependence of the premium function in the variable θ, namely

θ -→ P (θ) := P BoC (x 1 0 , x 2 0 , K, σ 1 , σ 2 , r, cos(θ), T ).
The function P is a 2π-periodic continuous function. Extracting the implicit correlation from the market amounts to solving P (θ) = P market 0 (with ρ = cos θ).

We need the following additional assumption

P market 0 ∈ (min θ P, max θ P )
i.e. that P market 0 is not an extremal value of P . It is natural to set for every θ ∈ R and every

z = (z 1 , z 2 ) ∈ R 2 H(θ, z) = e -rT max x 1 0 e µ 1 T +σ 1 √ T z 1 , x 2 0 e µ 2 T +σ 2 √ T (z 1 cos θ+z 2 sin θ) -K + -P market 0
and to define the recursive procedure

θ n+1 = θ n -γ n+1 H(θ n , Z n+1 ), n ≥ 0, where Z n+1 L ∼ N (0, I 2 ),
and the gain parameter sequence satisfies (2.14). For every z ∈ R 2 , θ -→ H(θ, z) is continuous and 2π-periodic which implies that the mean function h(θ) := EH(θ, Z 1 ) = P (θ) -P market 0 and θ -→ E H 2 (θ, Z 1 ) are both continuous and 2π-periodic as well (hence bounded).

The main difficulty to apply Theorem 2.1 is to find out the appropriate Lyapunov function. The quoted value P market 0 is not an extremum of the function P , hence 2π 0 h ± (θ)dθ > 0 where h ± := max(±h, 0). We consider θ * 0 any (fixed) solution to the equation h(θ) = 0 and two real numbers

β ± such that 0 < β + < 2π 0 h + (θ)dθ 2π 0 h -(θ)dθ < β - and we set g(θ) := 1 {h>0} (θ) + β + 1 {h<0} (θ) if θ ≥ θ * 0 1 {h>0} (θ) + β -1 {h<0} (θ) if θ < θ * 0 . The function θ -→ g(θ)h(θ) = h + -β ± h -
is continuous and "positively" 2π-periodic on [θ * 0 , ∞) and "negatively" 2π-periodic on (-∞, θ * 0 ]. Moreover, gh(θ) = 0 iff h(θ) = 0 so that gh(θ * 0 ) = gh(θ * 0 -) = 0 which ensures on the way the continuity of gh on R. Furthermore 2π 0 gh(θ)dθ > 0 and 0 -2π gh(θ)dθ < 0 so that, on the one hand, lim θ→±∞ θ 0 gh(u)du = +∞ and, on the other hand, there exists a real constant C > 0 such that the function

L(θ) = θ 0 gh(u)du + C is nonnegative. Its derivative is given by L ′ = gh so that L ′ h = gh 2 ≥ 0 and {L ′ h = 0} = {h = 0}.
It remains to prove that L ′ is Lipschitz continuous. One checks by applying the usual differentiation theorem for functions defined by an integral that, if σ 1 = σ 2 or x 1 = x 2 , then P is differentiable on the whole real line, otherwise it is differentiable only on R \ 2πZ, and in both cases

P ′ (θ) = σ 2 √ T E 1 {X 2 T >max(X 1 T ,K)} X 2 T (cos(θ)Z 2 -sin(θ)Z 1 ) .
Furthermore, with obvious notations, as soon as P ′ (θ) exists,

P ′ (θ) ≤ E X 2 T (cos(θ)Z 2 -sin(θ)Z 1 ) .
The right handside of the inequality defined a 2π-periodic continuous function, hence bounded on the real line. Consequently |P ′ (θ)| is bounded. It follows that the 2π-periodic functions h and h ± are Lipschitz continuous which implies in turn that L ′ = gh is Lipschitz as well. Moreover, one can show that the equation P (θ) = P market 0 market has finitely many solutions on every interval of length 2π. One may apply Theorem 2.1 to derive that θ n will converge toward a solution θ * of the equation P (θ) = P market 0 . Numerical illustration. We set the model parameters to the following values

x 1 0 = x 2 0 = 100, r = 0.10, σ 1 = σ 2 = 0.30, ρ = -0.50
and the payoff parameters T = 1, K = 100.

The implicit correlation search recursive procedure is implemented with a sequence of some quasirandom normal numbers, namely

(ζ 1 n , ζ 2 n ) = -2 log (ξ 1 n ) sin 2πξ 2 n , -2 log (ξ 1 n ) cos 2πξ 2 n ,
where

ξ n = (ξ 1 n , ξ 2 n ), n ≥ 1
, is simply a regular 2-dimensional Halton sequence (see [START_REF] Niederreiter | Random number generation and quasi-Monte Carlo methods[END_REF] for a definition). The Black-Scholes reference price 30.75 is used as a market price so that the target of the stochastic algorithm is θ * ∈ arccos(-0.5). The parameters of the stochastic approximation procedure are

θ 0 = 0, n = 10 5 , γ n = 8 n , n ≥ 1.
The choice of θ 0 is "blind" on purpose (see Figure 1).

Recursive omputation of the VaR and the CVaR

Another example of application is the recursive computation of financial risk measure which are the best known and the most common: the Value-at-Risk (VaR) and the Conditional Value-at-Risk (CVaR). This risk measures evaluate the extreme losses of a portfolio potentially faced by traders. The recursive computation of the VaR and the CVaR was introduced in [START_REF] Bardou | Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling[END_REF], based on the formulation as an optimization problem (see [START_REF] Rockafellar | Conditional value-at-risk: optimization approach[END_REF]) and on an unconstrained importance sampling procedure developed in [START_REF] Lemaire | Unconstrained recursive importance sampling[END_REF]. These variance reduction aspects are not investigated here.

Definitions and formulation

Let Y : (Ω, A, P) → R be a random variable representative of a loss (Y ≥ 0 is a loss equal to Y ).

Definition 5.1. The Value at Risk (at confidence level α ∈ (0, 1), α ≈ 1) of a given portfolio is the (lowest) α-quantile of the distribution Y i.e.

V aR α (Y ) := inf {θ | P(Y ≤ θ) ≥ α} .

As soon as the distribution function of Y has no atom, the value at risk satisfies P (Y ≤ V aR α (Y )) = α and if the distribution function F Y of Y is also increasing (strictly) then, it is the unique solution. As this risk measure is not consistent (see [START_REF] Föllmer | Stochastic finance[END_REF]), another consistent risk measure is provided by the Conditional value at Risk when Y ∈ L 1 (P) with a continuous distribution (no atom). The following formulation of the V aR α (Y ) and CV aR α (Y ) as solutions to an optimization problem is due to Rockafellar and Uryasev in [START_REF] Rockafellar | Conditional value-at-risk: optimization approach[END_REF].

CV aR α (Y ) = min θ θ + 1 1 -α E (Y -θ) + with V aR α (Y ) = inf arg min θ θ + 1 1 -α E(Y -θ) + .
5.2.2 Stochastic gradient for the computation of both V aR α (Y ) and CV aR α (Y )

⊲ Computation of the V aR α (Y ). What precedes suggests to implement a stochastic gradient descent derived from the above convex objective function V (θ) = θ +1 1-α E(Yθ) + . Assume that Y ∈ L 1 (P) with a continuous increasing distribution function F Y (for the sake of simplicity, see [START_REF] Bardou | Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling[END_REF] for a slightly more general framework). Let ν = L(Y ). We check that

lim θ→+∞ V (θ) θ = 1 and lim θ→+∞ V (-θ) θ = α 1 -α hence lim θ→±∞ V (θ) = +∞. so that {V aR α (Y )} = argmin R V . We check that V ′ (θ) = E[H(θ, Y )]
where

H(θ, y) := 1 - 1 1 -α 1 {y≥θ} .
Note that H is uniformly bounded by 1 ∨ α 1-α . This leads to devise the stochastic gradient descent

θ n+1 = θ n -γ n+1 H(θ n , Y n ), n ≥ 0, θ 0 ∈ L 1 (P).
whose unique target is θ * = V aR α (Y ). It is clear that, for every y ∈ R, θ → H(θ, y) is nondecreasing so that L(θ) = 1 2 (θθ * ) 2 is a good candidate as a Lyapunov function. In fact it is even a strict pathwise Lyapunov function in the sense of (2.15) by setting for every δ > 0, Ψ δ (θ) = δ1 |θ-θ * |>δ and χ δ (y) = 1 |y-θ * |≤δ .

As soon as (Y n ) ≥0 is ν-averaging, there exists a sequence (ε n ) n≥1 such that, for every θ ∈ R, 1 {y≥θ} ∈ V εn,2 since the empirical distribution measure a.s. (and subsequently in L 2 ) converges uniformly toward F Y . Finally, as soon as the step sequence (γ n ) n≥1 is admissible for (ε n ) n≥1 , Theorem 2.1 implies that θ n a.s.

-→ n→∞ θ * = V aR α (Y ).

In practice γ n = c/n, c > 0, is always admissible given the rate of convergence of the empirical measure in usual applications. Of course, when the Y n are i.i.d., standard martingale arguments "à la Robbins-Monro" make things straightforward under less stringent assumptions on the step sequence.

⊲ Computation of the CV aR α (Y ). The idea to compute the CV aR α (Y ) is to devise a companion procedure of the above stochastic gradient by setting, ζ 0 = 0 and for every n ≥ 0,

ζ n+1 = ζ n - 1 n + 1 (ζ n -v(θ n , Y n )) with v(θ, y) := θ + (y -θ) + 1 -α .
One checks that for every n ≥ 0,

ζ n = 1 n n-1 k=0 v(θ k , Y k ) = 1 n n-1 k=0 v(θ * , Y k ) + 1 n n-1 k=0 v(θ k , Y k ) -v(θ * , Y k )
Using that v is Lipschitz continuous in θ uniformly in y, we derive that the second term in the right hand side of the above equality goes to 0 a.s. as θ n → 0 a.s.

As concerns the first term, still in right hand side, first note that v(θ * , y) has a linear growth in y so it will a.s. go to E v(θ * , Y ) = V (θ * ) = CV aR α (Y ) as soon as, e.g., sup n≥1

Long term investment evaluation (and inhomogeneous Markov innovations)

In this example we deal with averaging inhomogeneous Markov innovations, namely the Euler scheme with decreasing step of a Brownian diffusion. To describe the functional class V εn,p , we rely on an approach developed in [START_REF] Lamberton | Recursive computation of the invariant distribution of a diffusion[END_REF] and [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF] to compute the invariant measure of a diffusion.

Computation of the invariant distribution of a diffusion

We consider a stochastic recursive algorithm for the computation of the invariant distribution ν introduced in [START_REF] Lamberton | Recursive computation of the invariant distribution of a diffusion[END_REF] of a Brownian diffusion process

dY t = b(Y t )dt + σ(Y t )dW t (5.39)
where b : R q → R q and σ : R q → M q,ℓ (R) (matrices with q rows and ℓ columns) are Lipschitz continuous, and W is a ℓ-dimensional Brownian motion. We denote by A its infinitesimal generator and by (P t ) t≥0 its transition semi-group. First, we introduce the Euler discretization of (5.39) with a step γ n vanishing to 0, i.e.

∀n ∈ N, Ȳn+1 = Ȳn + γn+1 b( Ȳn ) + √ γn+1 σ( Ȳn )U n+1 , (5.40)
where Ȳ0 ∈ L 0 R q (Ω, F, P) and (U n ) n≥1 is R ℓ -valued normalized white noise defined on a probability space (Ω, F, P), independent of Ȳ0 . The step sequence γ := (γ n ) n≥1 satisfies the conditions ∀n ≥ 1, γn ≥ 0, lim n→∞ γn = 0 and Γn := δ Ȳk (ω) .

(5.42)

We will use ν n (ω, f ) which can be compute recursively to approximate ν(f ).

Definition 5.3. (Strong condition of stability) A diffusion with generator A satisfies a strong stability condition of type (V, α) if there exists a (so-called Lyapunov) function V ∈ C 2 (R q , [1, +∞[) such that lim |y|→+∞ V (y) = +∞ and ∃ α > 0, ∃ β ≥ 0 such that AV ≤ -αV + β.

Remark. If the (V, α)-strong stability condition holds then (5.39) admits a strong solution starting from any y ∈ R d and admits at least one invariant distribution ν (i.e. νP t = ν, t ≥ 0). The terminology "averaging" refers here to the fact that if A is (V, α)-stable (and the invariant distribution ν is unique for the sake of simplicity) then, as soon as (γ, η) is averaging (see e.g. [START_REF] Lamberton | Recursive computation of the invariant distribution of a diffusion[END_REF], [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF] or [START_REF] Lemaire | An adaptive scheme for the approximation of dissipative systems[END_REF]), then sup n≥0 EV ( Ȳn ) < +∞ and P(dω)-a.s.

ν η n (ω, dy) := 1 H n n-1 k=0 η k δ Ȳk (ω) (R d ) =⇒ ν.
Example. If γn = γ0 n r , 0 < r < 1, and η n ≡ 1, then (γ, 1) is averaging. We assume that the diffusion (Y t ) t≥0 satisfies a strong condition of stability of type (V, α) with V sub-quadratic and that the invariant measure ν is unique. Besides the coefficients b and σ satisfy |b| 2 + Tr(σσ t ) = O(V ). Then the Euler scheme with decreasing step ( Ȳn ) n≥0 defined by (5.40) satisfies a strong condition of stability of type (W, n 0 ) where W is a function depending upon V and the moments of U 1 , namely

∀n ≥ n 0 , E W ( Ȳn+1 ) | σ Ȳk , 0 ≤ k ≤ n ≤ (1 -α γn+1 ) W ( Ȳn ) + β. ⊲ If U 1 is sub-normal (typically if U 1 is normal), and Tr(σσ * ) ≤ C σ V 1-ζ ,
we may choose W = exp(λV ζ ) with λ small enough (see [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF] Proposition III.2 p. 36).

⊲ If U 1 has a moment of order 2(p + 1), p ≥ 2, then W = V p+1 (idem).

Assume that the function f : R q → R admits a regular enough solution φ to the Poisson equation

Aφ = -(f -ν(f )), (5.43)
i.e. belonging to the set

E p,W := φ ∈ C p (R q , R), ∀j ∈ {0, . . . , p}, ∀y ∈ R q , D j φ(y) 2 = o W (y) V j (y)
and satisfying D p φ Lipschitz. For such functions φ, let us to define the functions D q , 3 ≤ q ≤ p, by ∀y ∈ R q , D q (y) = q j≥q/2

C q-j j j! D j φ(y) • (b(y)) ⊗(q-j) , E (σ(y)U 1 ) ⊗(2j-q) . They will appear in the development of the error of order p, p ≥ 3.

Theorem 5.1. Let p ≥ 2 such that U 1 ∈ L 2(p+1) and φ ∈ E p,W solution to Poisson equation (5.43) such that D p φ is Lipschitz. Define q * by q * = min q∈{3,...,p} {D q = 0} ∧ (p + 1).

(Note that if U 1 L ∼ N (0, I q ) then q * = 4). Let Γ(β) n = n k=1 γβ k , β ∈ R.
Assume that the couples (γ, 1) and (γ, 1 γ ) are averaging and that (γ n ) n≥1 is non-increasing. If q * ≤ p and

Γ(q * /2-1) n Γ(-1) n -→ n→+∞ ξ ∈]0, +∞], Γ(q * /2-1) n γn -1 n≥1 is non-increasing, n≥1 1 Γ(q * /2-1) n ∆ 1 γn < +∞ and n≥1 1 γn Γ(q * /2-1) n 2 < +∞, then f ∈ V εn,2 with ε n = Γ(q * /2-1) n n -→ n→+∞ 0.
Corollary 5.1. If γn = γ0 n r , γ0 > 0, the above theorem holds true when 0 < r ≤ 1 q * -1 and ε n = n -r(q * /2-1) . In particular, for a Gaussian Euler scheme, ε n = n -r . Sketch of proof of Theorem 5.1. Proposition V.4 in [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF] gives

n Γ(q * /2-1) n 1 n n-1 k=0 f ( Ȳk ) -ν(f ) 2 = M n + S n 2 + o(1)
where

M n = 1 Γ(q * /2-1) n n k=1 1 γk ∇φ( Ȳk-1 ) | σ( Ȳk-1 )U k and S n = p q=q * 1 Γ(q * /2-1) n n k=1 γ q 2 -1 k D q ( Ȳk-1 ).
Using that φ ∈ E p,W , i.e. that for every q, |D q | 2 = o(W ), and that sup n E W ( Ȳn ) < +∞ (according to the stability condition of the Euler scheme), we get (see the remark after Proposition V.1 p.62 in [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF]),

M n 2 ≤ Γ(-1) n Γ(q * /2-1) n sup 0≤k≤n-1 σ * ∇φ( Ȳk ) 2 < +∞ since Γ(-1) n / Γ(q * /2-1) n -→ n→+∞ ξ -1 ∈]0, +∞[ and sup n S n 2 < +∞.

Application to the minimization of a potential

The aim is to minimize a convex potential V : R q → R having a minimum (e.g. because lim |θ|→+∞ V (θ) = +∞) assumed to be unique. We also assume that V has a representation as the expectation with respect to the invariant distribution ν of an ergodic diffusion, say Y defined above. Typically V appears as the long run limit (under appropriate assumptions) of a functional through Birkhoff's Theorem:

V (θ) = lim t→+∞ 1 T T 0 v(θ, Y t+s ) ds = E ν 1 T T 0 v(θ, Y s ds = R q
v(θ, y)ν(dy).

We make the following assumptions

(i) Integrability: ∀y ∈ R q , θ → v(θ, y) is convex. (ii) Pathwise convexity: ∀θ ∈ R d , v(θ, •) ∈ L 1 (ν). (iii) Differentiability: ∀θ ∈ R d , ∇ θ v(θ, y) exists. (iv) Uniform integrability: ∀θ ∈ R d , |v(θ,y)-v(θ ′ ,y)| |θ-θ ′ | θ ′ ∈[θ-η θ ,θ+η θ ]\{θ}
, η θ > 0, is uniformly integrable.

Then (using uniqueness of θ * ),

θ * = argmin θ∈R d R q v(θ, y)ν(dy) iff R q ∇ θ v(θ * , y)ν(dy) = 0,
At this stage the idea is to devise a stochastic gradient (gradient based recursive zero search) using the Gaussian Euler scheme ( Ȳn ) n≥0 with decreasing step γn = γ0 n -1 3 , γ0 > 0, of Y as an ν-averaging innovation process with rate ε n = Γn /n → 0:

∀n ≥ 0, θ n+1 = θ n -γ n+1 ∇ θ v(θ n , Ȳn ), θ 0 ∈ R q . Let p ∈ [1, ∞) such that ∇ θ v satisfies the growth assumption (2.12) with L(θ) = |θ -θ * | 2 , ∇ θ v(θ * , •) ∈ V εn,p
and (γ n ) n≥1 is admissible for ε n given by Corollary 5.1, then Theorem 2.1 implies that θ n → θ * a.s.

Toy numerical example. We consider a long-term investment project (see the example in [START_REF] Løkka | A model for the long-term optimal capacity level of an investment project[END_REF]) which yields payoff at a rate that depends on the installed capacity level and on the value of an underlying state process modeled with an ergodic diffusion. The process Y represents an economic indicator such as the asset demand or its discounted price. Our aim is to determine the capacity expansion strategy that maximizes the long-term average payoff resulting from the project operation. So it is an ergodic control problem in a microeconomic framework. In [START_REF] Løkka | A model for the long-term optimal capacity level of an investment project[END_REF] is shown that this dynamical optimization problem is equivalent (see above) to a static optimization problem involving the stationary distribution ν of Y and the (concave) running payoff function C, namely, still following [START_REF] Løkka | A model for the long-term optimal capacity level of an investment project[END_REF],

∀ θ ∈ R + , ∀ y ∈ R + , C(θ, y) = y α θ β -c θ where α, β ∈ (0, 1) and c ∈ (0, ∞).
The term y α θ β can be identified to the so-called Cobb-Douglas production function, while the term c θ measures the cost of capital use. Our task is to minimize θ,y) is singular at θ = 0, we will introduce the increasing convex with linear growth change of variable θ = θ + ( θ2 + 1)

R q (-1) y α θ β -c θ ν(dy) (so that of course θ * = βEY α 1 c 1 1-β !). Since ∇ θ C(
1/2 ρ( θ) , ρ( θ) = 1 1-β 1 θ<0 + 1 θ≥0 , from R onto (0, ∞) and we consider ∇ θ v( θ, y) = -∇ θ C θ + ( θ2 + 1) 1/2 ρ( θ) , y , θ ∈ R, y ∈ R + .
Still following [START_REF] Løkka | A model for the long-term optimal capacity level of an investment project[END_REF], the dynamics of the underlying state process Y is modeled by the one-dimensional CIR diffusion (whose diffusion coefficient is unfortunately not Lipschitz), namely

dY t = κ (ϑ -Y t ) dt + σ |Y t |dW t , Y 0 > 0, (5.44)
where κ, ϑ, σ > 0 are constants satisfying 2κϑ > σ 2 so that (Y t ) t≥0 is (0, ∞)-valued.

The resulting stochastic gradient procedure with step ( γ n ) n≥1 reads ∀n ≥ 0, θ n+1 = θ nγ n+1 ∇ θ v( θ n , Ȳn ), θ 0 ∈ R, where (γ n ) n≥1 is admissible with respect to ε n = Γn /n and ( Ȳn ) n≥0 the Euler scheme with step γn = γ0 n -1/3 (L( θ) = | θθ * | 2 is still a pathwise Lyapunov function). One checks that ∇ θ v satisfies (2.12) with φ(y) ≡ c α,β y α , c α,β > 0 and p = 2 since sup n E Ȳ 2 n < +∞ and α ∈ (0, 1). The invariant distribution of Y is a Gamma law which density is given by

ν(dy) = 1 Γ 2κϑ σ 2 y 2κϑ σ 2 -1 exp 2κ σ 2 ϑ log 2κ σ 2 -y 1 {y>0} ,
where Γ is the gamma function. Thus we can compute the previous integral, namely . Figure 2 illustrates the convergence of the algorithm (the parameters are specified in the caption).

R + y α ν(dy) = Γ 2κϑ σ 2 + α Γ 2κϑ
If one considers a basket of assets modeled by a Wishart process (see [START_REF] Bru | Wishart processes[END_REF] and [START_REF] Gouriéroux | The Wishart autoregressive process of multivariate stochastic volatility[END_REF]), a similar long-term ergodic control process can be devised. Closed forms are no longer available for the static optimization problem. However, our numerical approach can be extended straightforwardly (provided one has at hand an efficient method of simulation for Wishart process, like that proposed in [START_REF] Gouriéroux | The Wishart autoregressive process of multivariate stochastic volatility[END_REF]).

The ergodic two-armed bandit

An application of the multiplicative setting is the so-called two-armed bandit algorithm introduced in mathematical psychology, learning automata (see [START_REF] Norman | On the linear model two absorbing barriers[END_REF][START_REF] Narendra | Use of stochastic automata for parameter self-optimization with multimodal performance criteria[END_REF]) and more recently asset allocation ( [START_REF] Lamberton | When can the two-armed bandit algorithm be trusted?[END_REF]). Criteria on a.s. convergence under pure i.i.d. assumptions were obtained in [START_REF] Lamberton | When can the two-armed bandit algorithm be trusted?[END_REF][START_REF] Lamberton | How fast is the bandit? Stoch[END_REF] and under ergodic assumptions in [START_REF] Tarrès | On ergodic two-armed bandits[END_REF]. A penalized version of this algorithm is also studied in [START_REF] Lamberton | A penalized bandit algorithm[END_REF]. This algorithm is defined as follows: at each step n ≥ 0, one plays arm A (resp. arm B) at random with probability θ n (resp. 1θ n ), where θ 0 = θ ∈ (0, 1) and θ n is updated according the following "rewarding" rule: for every n ≥ 0, θ n+1 = θ n + γ n+1 (1θ n )1 {U n+1 ≤θn}∩A n+1θ n 1 {U n+1 >θn}∩B n+1 (5.45) where (U n ) n≥1 is an i.i.d. sequence of uniform random variables, independent of (A n ) n≥1 and (B n ) n≥1 which are two sequences of (possibly dependent) events evaluating the performances of the arms A and B respectively (A n is the event "A's performance is satisfactory ay time n" idem for B n and B). This stochastic procedure can be rewritten in a canonical form as follows

θ n+1 = θ n + γ n+1 1 A n+1 -1 B n+1 h(θ n ) + γ n+1 ∆M n+1 , θ 0 = θ ∈ (0, 1) (5.46)
where h(θ) = θ(1θ), M n := n k=1 m k , M 0 := 0, with

m k := 1 A k (1 -θ k-1 ) 1 {U n+1 ≤θn} -θ k-1 + 1 B k θ k-1 (1 -θ k-1 ) -1 {U n+1 >θn} .
We make the assumption that A outperforms B in average i.e. that ν(A) > ν(B) where where 1 is the target and 0 is a trap. Further investigations on θ * are carried in [START_REF] Tarrès | On ergodic two-armed bandits[END_REF] in this ergodic framework to analyze the fallibility of the algorithm which extend former results established in [START_REF] Lamberton | When can the two-armed bandit algorithm be trusted?[END_REF][START_REF] Lamberton | How fast is the bandit? Stoch[END_REF] in the purely i.i.d. setting.

Optimal split of orders across liquidity pools

This is an example of application in Finance to be implemented exclusively on real data. It is an optimal allocation problem which solved by a stochastic Lagrangian approach originally developed in [START_REF] Laruelle | Optimal split of orders across liquidity pools: a stochastic algorithm approach[END_REF]. Here, only numerical results with real market data are presented.

Model description

The principle of a Dark pool is to propose a price with no guarantee of executed quantity at the occasion of an OTC transaction. Usually this price is lower than the one offered on the regular market. So one can model the impact of the existence of N dark pools (N ≥ 2) on a given transaction as follows: let V > 0 be the random volume to be executed, let θ i ∈ (0, 1) be the discount factor proposed by the dark pool i. Let r i denote the percentage of V sent to the dark pool i for execution. Let D i ≥ 0 be the quantity of securities that can be delivered (or made available) by the dark pool i at price θ i S.

The remainder of the order is to be executed on the regular market, at price S. Then the cost C of the whole executed order is given by

C = S N i=1 θ i min (r i V, D i ) + S V - N i=1 min (r i V, D i ) = S V - N i=1 ρ i min r i V, D i
where ρ i = 1θ i ∈ (0, 1), i = 1, . . . , N . Minimizing the mean execution cost, given the price S, amounts to solving the following maximization problem We assume that for all i ∈ I N , V > 0 P-a.s., P(D i > 0) > 0 and the distribution function of D i V is continuous on R + , (5.48) then ϕ i , i ∈ I N , are everywhere differentiable on the unit interval [0, 1] with

ϕ ′ i (u) = ρ i E 1 {uV ≤D i } V , u ∈ (0, 1] , ( 5

  • | • denotes the canonical Euclidean inner product and |•| its related norm on R d . The almost sure convergence will be denoted by a.s.

n≥1 γ n = +∞, nε n γ n -→ n→∞ 0, and n≥1 nε n max γ 2 n

 2 , |∆γ n+1 | < +∞.(2.14)

  where D * n (ξ) is called the discrepancy at the origin or star discrepancy. (b) There exists sequences, called sequences with low discrepancy such that D * n (ξ) = log d n n

  and X is a stationary α-mixing process satisfying the condition

.

  The condition (4.27) can be replaced by the less stringent Ibragimov's condition (4.30) to complete the proof.

Figure 1 :

 1 Figure 1: B-S Best-of-Call option. T = 1, r = 0.10, σ 1 = σ 2 = 0.30, x 1 0 = x 2 0 = 100, K = 100. Left: convergence of θ n toward a θ * (up to n = 10000). Right: convergence of ρ n := cos(θ n ) toward -0.5.

Definition 5 . 2 .

 52 Let Y ∈ L 1 (P) with an atomless distribution. The Conditional value at Risk (at level α) is the conditional expectation of the portfolio loss Y beyond V aR α (Y ), i.e. CV aR α (Y ) := E [Y |Y ≥ V aR α (Y )] .

Proposition 5 . 1 .

 51 (Rockafellar and Uryasev) Let Y ∈ L 1 (P) with an atomless distribution. The functionV : θ → θ + 1 1-α E (Yθ) + is convex, and

For every n ≥ 1

 1 and every ω ∈ Ω, set ν n (ω, dy)

σ 2

 2 in fact a closed form for θ * given by θ * = βΓ 2κϑ

Figure 2 :

 2 Figure 2: Convergence towards the optimal capacity level of the investment project: κ = 1, ϑ = 1, σ = 1.5, α = 0.8, β = 0.7, c = 0.5, n = 10 5 , γ n = 5 n .

  convergences hold at rate ε n satisfying (2.7). Then applying Theorem 2.2 withY k := 1 A k+1 -1 B k+1 , k ≥ 0,and χ(y) = y ν(A)-ν(B) , we get a first convergence result: as soon as (γ n ) n≥1 is admissible in the sense of (2.14) for the sequence (ε n ) n≥1 , θ n a.s. -→ n→∞ θ * ∈ {0, 1} .

  S min r i V, D i , r ∈ P N(5.47) whereP N := r = (r i ) 1≤i≤N ∈ R N + | N i=1 r i = 1 .It is then convenient to include the price S into both random variables V and D i by considering V := V S and D i := D i S instead of V and D i .Let I N = {1, . . . , N }. We set for all r = (r 1 , . . . , r N ) ∈ P N , Φ(r 1 , . . . , r N ) := N i=1 ϕ i (r i ), where∀i ∈ I N , ϕ i (u) := ρ i E (min (uV, D i )) , u ∈ [0, 1] .

  .49) and one extends ϕ i , i ∈ I N , on the whole real line into a concave nondecreasing function with lim ±∞ ϕ i = ±∞. So we can formally extend Φ on the whole affine hyperplane spanned by P N i.e.H N := r = (r 1 , . . . , r N ) ∈ R N | N i=1 r i = 1 .

  Theorem 2.1. (a) Boundedness. Let h : R d → R d satisfying (2.6), H : R d ×R q → R d a Borel function and let (Y n ) n≥0 be a ν-stable sequence (i.e. satisfying (2.5)). Assume there exists a continuously differentiable function L : R d → R + satisfying

	∇L is Lipschitz continuous and |∇L| 2 ≤ C (1 + L)	(2.9)
	and that the pseudo-mean function H satisfies the pathwise Lyapunov assumption
	∀θ ∈ R d \{θ * }, ∀y ∈ R q ,	∇L(θ) | H(θ, y) -H(θ * , y) ≥ 0.	(2.10)
	Let p ∈ [1, ∞) and let (ε n ) n≥1 be a sequence satisfying (2.7). Assume that

  nε n which a.s. goes to 0 as n goes to infinity since nε n γ n -→

	bounded. Moreover	n→∞ n |] ≤ nε n γ n ∇Λ ∞ 0 by (2.14) and E [ γ n |∇Λ(θ n-1 )| |S * S * n nε n 1	S * n nε n n≥1	remains a.s.
	which converges to 0 in L 1 because nε n γ n -→ n→∞	0 and H(θ * , •) ∈ V εn,p . On the other hand,
	n-1
	k=1

  and n≥1 γ 2 n < +∞ by combining (2.7) and (2.14), which in turn implies

	that B n	a.s.

-→ n→∞ B ∞ < +∞. As a consequence A n a.s.

-→ n→∞ A ∞ < +∞. Therefore using the mean reverting property (2.15) of H with respect to ∇Λ, we classically derive that n≥1

  Now, the proposition below straightforwardly follows from Theorem 2.1. Proposition 4.2. Let p ∈ [1, ∞) and θ * ∈ R d . If K satisfies (4.35) and H satisfies the strict pathwise Lyapunov assumption (2.15), if (γ n ) n≥1 satisfies (2.14) for a sequence (ε n ) n≥1 satisfying (2.7) and H(θ * , •) ∈ V εn,p , then the recursive procedure with Markov innovations defined by (4.34) converges, i.e.

	θ n	a.s.

  Definition 5.4. (a) A couple (γ, η) is an averaging step-weight system if the sequences (γ n ) n≥1 and (η n ) n≥1 are nonnegative, general terms of a non-converging series and such that

	lim n γn = 0,	n≥1	1 H n	∆	η n γn +	< +∞ and	n≥1	η n H n √ γn	2	< +∞,
	where H n = n k=1 η k . (b) In particular, if η n ≡ 1, then (γ, 1) is an averaging step-weight system if
	lim n γn = 0,	n≥1	1 n	1 γn	-	1 γn+1	< +∞ and	n≥1	1 n 2 γn	< +∞.

n n-1 k=0 |Y k | 1+η < +∞ a.s.for an η > 0 by combining standard uniform integrability arguments (with respect to the empirical measure) and the ν-stability of (Y n ) n≥0 . In practice one must keep in mind that an adaptive importance sampling procedure like that detailed in[START_REF] Bardou | Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling[END_REF] should be added. For a QM C implementation of the procedure, see[START_REF] Frikha | Contribution à la modélisation et à la gestion dynamique du risque des marchés de l'énergie[END_REF].

Design of the recursive procedure

We aim at solving the following maximization problem max r∈P N Φ(r). The Lagrangian associated to the sole affine constraint suggests that any r * ∈ arg max P N Φ iff ϕ ′ i (r * i ) is constant when i runs over

Then using the representation of the derivatives ϕ ′ i yields r * ∈ arg max

Consequently, this leads to the following recursive zero search procedure

where for every i ∈ I N , r ∈ P N , every V > 0 and every D 1 , . . . , D N ≥ 0,

where (Y n ) n≥1 is a sequence of random vectors with nonnegative components such that, for every

). The underlying idea of the algorithm is to reward the dark pools which outperform the mean of the N dark pools by increasing the allocated volume sent at the next step (and conversely). For sake of simplicity that argmax P N Φ = {r * } ⊂ int(P N ). Our "light" ν-averaging assumption is to assume that there exists an exponent η ∈ (0, 1] such that for every u ∈ R + and every i ∈ I N

s. and in L 2 (P)

(5.51) (which hold under geometric α-mixing assumptions on (D n , V n ) n≥1 ). Under additional technical assumptions on the support of L(Y n ) (see [START_REF] Laruelle | Optimal split of orders across liquidity pools: a stochastic algorithm approach[END_REF]), we can apply Theorem 2.1: if the sequence (γ n ) n≥1 satisfies (2.14), we get that the algorithm defined by (5.50) a.s. converges towards r * = argmax P N Φ.

Numerical Tests

We consider the shortage setting, i.e. EV > N i=1 ED i because it is the most interesting case and the most common in the market. Now, we introduce an index to measure the performances of our recursive allocation procedure.

⊲ Relative cost reduction (w.r.t. the regular market): it is defined as the ratios between the cost reduction of the execution using dark pools and the cost resulting from an execution on the regular market, i.e., for every n ≥ 1,

We have considered for V the traded volumes of a very liquid security -namely the asset BNPduring an 11 day period. Then we selected the N most correlated assets (in terms of traded volumes) with the original asset. These assets are denoted S i , i = 1, . . . , N and we considered their traded volumes during the same 11 day period. Finally, the available volumes of each dark pool i have been modeled as follows using the mixing function

where α i , i = 1, . . . , N are the recombining coefficients, β i , i = 1, . . . , N some scaling factors and E V and E S i stand for the empirical mean of the data sets of V and S i . The simulations presented here have been made with four dark pools (N = 4). Since the data used here cover 11 days, it is clear that, unlike the simulated data, these pseudo-real data are not stationary: in particular they are subject to daily changes of trend and volatility (at least). To highlight the resulting changes in the response of the algorithms, we have specified the days by drawing vertical doted lines. The dark pool pseudo-data parameters are set to β = (0.1, 0.2, 0.3, 0.2) t , α = (0.4, 0.6, 0.8, 0.2) t and the dark pool trading (rebate) parameters are set to ρ = (0.0, 0.02, 0.04, 0.06) t . We benchmarked -see Figure 3 -the algorithm on the whole data set (11 days) as though it were stationary. In particular, the running means of the performances are computed from the very beginning for the first 1500 data, and then by a moving average computed on a window of 1500 data.