David Auger
email: david.auger@prism.uvsq.fr

Olivier Teytaud
email: olivier.teytaud@inria.fr

The Frontier of Decidability in Partially Observable Recursive Games

Keywords:

The classical decision problem associated with a game is whether a given player has a winning strategy, i.e. some strategy that leads almost surely to a victory, regardless of the other players' strategies. While this problem is relevant for deterministic fully observable games, for a partially observable game the requirement of winning with probability 1 is too strong. In fact, as shown in this paper, a game might be decidable for the simple criterion of almost sure victory, whereas optimal play (even in an approximate sense) is not computable.

We therefore propose another criterion, the decidability of which is equivalent to the computability of approximately optimal play. Then, we show that (i) this criterion is undecidable in the general case, even with deterministic games (no random part in the game), (ii) that it is in the jump 0', and that, even in the stochastic case, (iii) it becomes decidable if we add the requirement that the game halts almost surely whatever maybe the strategies of the players.

Introduction: partially observable recursive games

We consider two-player stochastic games where payoffs only occur when the game reaches absorbing states, which we call final states. The class of games that we consider is quite general and can be also viewed as an extension of the framework introduced by Everett [START_REF] Everett | Recursive games[END_REF], where we add stochasticity in transitions; on the other hand we will only consider games where players always choose their actions from a finite set, as opposed to Everett. We refer to these games as recursive games as in the terminology of Everett to insist on the fact that, contrary to general stochastic games, payoffs only occur at the end of the game.

More precisely, we consider two-player games G described by the following elements:

• a finite set S of states whose cardinal is denoted n ≥ 1 ; • a finite set A of actions whose cardinal is denoted k ≥ 1 ;

• a nonempty subset F of S, the set of final states ; with every f ∈ F is associated a rational number r f ∈ [-1; 1];

• a transition function q which associates to every element of (s, a 1 , a2 ) of S × A 2 a rational probability distribution on states; • an initial state s 0 ∈ S; • a finite set O, the set of observations;

• two observation filters, one for each player, which associate to every element (a 1 , a 2 , s) of A 2 × S an element of O.

Informally, the game starts in the initial state s 0 and then moves from state to state until a final state is reached. If the current state s is not a final state, both players must choose an action from A: then the transition function q gives a probability distribution q(a 1 , a 2 ) on states, according to which the new state is picked. Finally, when a final state f is reached, the game ends and the first player earns a score r f (and the second -r f since our games are zero-sum). In case the game never ends, we consider the score to be 0.

To this simple rules is added a layer modelling the partiality of observation. We will consider that every time two actions a 1 , a 2 have been chosen and a new state s t+1 is consequently reached, both players forget about their decisions and the new state, but receive an observation (or signal) which is in some sense the triple (a 1 , a 2 , s t+1 ) distorted by their respective observation filter. When the time comes when a player must choose an action, all the information available on the current play is the time t and the sequence o 0 , o 1 , • • • , o t-1 of observations received in the past.

This framework for rules and observability is enough to model different levels of randomization and observability, for instance:

• deterministic games, in which all transitions probabilities q(s, a 1 , a 2 ) are Dirac measures on a single state; • games with full observability, where both observation filters are the identity map from A 2 × S to itself; • games with no observability, where the observation filter of player i associates to a triple (a 1 , a 2 , s) the action a i , i.e. a player only observes his own action and nothing else. • one-player games, where player II has no role to play, i.e. for all states s, actions a 1 for I and a 2 , a 2 for II the probabilities q(s, a 1 , a 2 ) and q(s, a 1 , a 2 ) are the same. In this case observations and strategies of II play no role hence it can be considered that II has only one strategy.

We now state a few definitions in order to describe the game more formally.

• A history of length t ≥ 0 for a player is a finite sequence of t observations (o 0 , o • A strategy for a player is then defined as a map from the set of histories to the set of probability distributions on actions. We denote by Σ i the set of strategies for player i. If all probability distributions defining a strategy are Dirac measures on a single action (i.e. all decisions are based only on past observations and never randomized), the strategy is said to be pure, otherwise it is mixed.

Given two strategies σ 1 , σ 2 for players the issue of the game only depends on random choices due to the probability distributions in strategies and to stochastic transitions in the game. Precisely, with each t ≥ 0 is associated a current state until the game ends. The game behaves as follows :

• initialization : for t = 0 the current state s t is defined as the initial state s 0 and current histories h i 0 of players are empty; • while the current state is not a final state repeat :

choose randomly an action a i t for each player i = 1, 2 according to the probability distribution σ i (h i t ); choose randomly the new current state s t+1 according to the probability distribution q(s t , a 1 t , a 2 t ) on states; define observations o i t as the images by player's respective observability filters of (a 1 t , a 2 t , s t+1 ); let the histories h i t+1 at time t + 1 be h i t × o i t ; • let the score sc(σ 1 , σ 2 ) be r f , where f is the final current state.

The score is 0 if the game never halts. As we just said, once strategies σ 1 , σ 2 have been chosen by the players the issue of the game, and in particular the score sc(σ 1 , σ 2 ), is random. We are thus interested in maximizing the average score of the first player, regardless of the opponent's strategy, which we call the value v 1 of the first player and is defined by

sup σ 1 ∈Σ 1 inf σ 2 ∈Σ 2 Esc(σ 1 , σ 2 ).
If r f ∈ {0, 1} for all finite states (i.e. the issue is only win / loose), the problem of deciding whether an almost surely winning strategy exists for the first player exactly amounts to the question: does v 1 = 1 ?

Compacity of pure strategies

Since the sets of actions and observations are finite, for all t ≥ 0 the set O t of possible histories of length t is finite. From this easily follows the following lemma which will turn out to be useful. Lemma 1. Consider a finite recursive game G with a partial observability setting (general case). For any infinite set S of pure strategies of a player, we can find a sequence (σ t ) t≥0 with values in S and a pure strategy σ ∞ (possibly not in S) such that for all t ≥ 0

σ ∞ |t = σ t |t , (2)
where σ |t denotes the restriction of σ to O t .

Proof. This is similar to Koenig's Lemma. Since strategies in S are pure, the possible restrictions σ |0 of the σ ∈ S to O 0 (histories of length 0, i.e. the empty set) are in finite number. But since S is infinite, there must be an infinite subset of S composed with strategies having the same restriction, i.e. strategies that agree on time step 0. Now in this set S 0 , for similar reasons we can can find an infinite subset S 1 of strategies which agree on time step 1 -so that they agree in fact for t = 0, 1. We can inductively repeat the process and pick some σ t ∈ S t . Since σ t and σ t+1 agree on time steps 0 . . . t, we can define the strategy σ ∞ by (2).

Outline of the paper

Section 2 will show the main undecidability result, namely the undecidability of optimal play in partially observable games with finite state space, even in the deterministic setting. The section also contains the proof that this problem is in 0', the Turing degree of the halting problem. Section 3 then shows that for games which halt almost surely the problem becomes decidable. The conclusion summarizes the paper and illustrates it on existing games; an open problem around the phantom version of the Game of Go is proposed.

Undecidability of approximability for deterministic stochastic games with no observability

The classical definition of decidability in games is the existence of a sure win (∃SW, as in Table 1): the question, for which the decidability is investigated, is the existence of a strategy winning with probability 100 %, whatever may be the strategy of the opponent. This makes sense for fully observable games, because for such games, answering this question is sufficient for optimal play. But, for partially observable games, winning with probability 1 is usually impossible, whenever the situation is very good: partially observable games, as well as games with simultaneous actions, involve mixed strategies, introducing stochasticity in the analysis even when the game is deterministic [START_REF] Nash | Some games and machines for playing them[END_REF]. In particular, there are situations in which no strategy ensures a win with probability 100%; and, yet, there is a win with probability 99% or more. A good alternate decision problem is therefore an approximation of value function, as presented in Table 2.

Theorem 2. There is an algorithm which, given a finite recursive game G with either full observability, partial observability or no observability, builds a finite deterministic recursive game G with the same observability level and where both players have same values in G and G .

The Frontier of Decidability in Partially Observable Deterministic Games 5

(∃SW): Existence of an almost sure win Instance: a game. Question: is there a strategy for winning with probability 1 whatever may be the strategy of the opponent ? (V F A X, ): Value function approximation for X ∈]0, 1[ and < min(X, 1 -X).

Instance: a game with value ≥ X + or ≤ Xfor the first player. Question: is there a strategy for ensuring a win with probability ≥ X whatever may be the strategy of the opponent ?

Table 2. The Value Function Approximation problem for X and . The decision algorithm is allowed to be wrong if the value of the game is in ]X -, X + [.

Proof. We describe the transformation in high level language. First, duplicate states so that each transition probability q(s, a 1 , a 2 ) is a uniform distribution on a finite set of states -this clearly can be done since probabilities are supposed to be rational. From now on, suppose that G satisfies this property.

The new game G will have the same set S of states as G with initial and final states remaining the same. Let n be the number of states in G ; we define the set of actions of G as A = A × {1, 2, • • • , n!}. Let us describe the transition function q of G -since the game is deterministic, we define its values as states (instead of Dirac measures on states). For every state s and couple ((a

1 , i)(a 2 , j)) ∈ A 2 define q (s, (a 1 , i), (a 2 , j)) = s i+j[p]
where s 0 , s 1 , • • • , s p-1 is the set of p states which is the support of the uniform distribution q(s, a 1 , a 2 ). To ensure coherence one has to keep the same labelling of these states for a given couple (a 1 , a 2 ).

Finally the observability framework is the same as in G, with any rule about observations concerning i and j -hence one can ensure that G has no observability, or full observability, if G is in one of these cases.

To see that G and G have the same values (or value if G has one) consider for instance an -optimal strategy σ 1 for player I and let v 1 be the value of this player. We claim that the strategy consisting of playing the product strategy σ 1 × u, where u is the strategy consisting of a random uniform choice of i in {1, 2,

• • • , n!} ensures v -.
It simply follows from the fact that for all probability distributions v on {1, 2, • • • , n!}, the distribution u + v will be uniform on {1, 2, • • • , n!}, so u + v[k] will be uniform on {1, 2, • • • , k} since k divides n!. Hence the transition in G will mimic what happens in G when forgetting about i, j. Conversely, if a strategy in G ensures a value v -, it ensures v -against all strategies of II that play uniformly on j, hence the corresponding strategy in G ensures v -.

It is proved in [START_REF] Madani | On the undecidability of probabilistic planning and related stochastic optimization problems[END_REF] that the problem of approximating the maximum probability of acceptance for a probabilistic finite-state automaton (PFA) is undecidable; this is proved by reduction to known undecidability results on probabilistic finite automata [START_REF] Paz | Introduction to probabilistic automata[END_REF]. Classically, one uses for PFA a different formalism than the one we use here for games. It would be pointless to introduce here this notation thus we restate the theorem in our setting. The reader can easily check by the definition given in [START_REF] Madani | On the undecidability of probabilistic planning and related stochastic optimization problems[END_REF] that with our notation for games, a PFA exactly amounts to a one-player recursive game with stochastic transitions and no observability, where all rewards equal 1. The emptiness problem for PFA is then to decide whether for a given threshold τ the (only) player has a value greater than τ . Furthermore, they prove:

Theorem 3. [7] Consider C ∈]0, 1[ and 0 < δ < min(C, 1 -C).
Given a oneplayer recursive game with stochastic transitions, all rewards equal to 1 and no observability, such that one of the following cases holds:

(1) either the player has a value at least C + δ ;

(2) or the player has a value at most C -δ it is undecidable to compute which case hold.

From this, using Theorem 2 we directly deduce: Corollary 4. For all X ∈]0, 1[ and all ∈]0, min(X, 1 -X)[, the approximation value problem V F A X, for recursive games with no observation and deterministic transitions is undecidable.

V F A is in the Turing degree 0 of the halting problem

Here we prove that the problem of approximating the value for the first player in deterministic recursive games with partial observability where all rewards are Lemma 7. Let v 1 be the value of the first player and v 1 t be the value of the game restricted to the t first time steps (value for the first player). Then

lim t→∞ v 1 t = v 1 .
Proof. Consider > 0.

There clearly exist strategies ensuring v 1 t at time t since the game G t (restriction of G to t time steps) has finite horizon t and therefore boils down to a finite matrix game. By playing such a strategy in G, since rewards are positive we see that the sequence (v 1 t ) t is non-decreasing and that v 1 ≥ v 1 t for all t. Let now σ 1 be a strategy ensuring v 1 -for the first player. By Lemma 6 we see that

v 1 t ≥ v 1 t (σ 1 ) ≥ v 1 (σ 1 ) - for t big enough, so that v 1 t ≥ v 1 -2 .
With this last lemma the theorem follows quite easily: just build a machine which enumerates the values (v 1 t ) t≥0 , and stops if for some t (v 1 t ) > c.

Games that end almost surely

Lots of games, at least those that we really play with our friends and family, have particular rules ensuring that they will end. A notable exception is the game of Go with Japanese rules, in which loops are possible.

If a game has finite horizon, then it is surely decidable to solve V F A X,δ . Another case is when the game can end at every time step (by a transition to a final state with reward zero) with a given probability -then the game ends with probability 1 but with small probability can last for a long time.

In this section, we consider a game which is supposed to end with probability 1, regardless of what players do. We include in the analysis games with stochastic transitions. More precisely, we make the following hypothesis : for all strategies σ 1 , σ 2 , there almost surely exists t such that the game is over at time t. Theorem 8. The value approximation problem VFA is decidable for a stochastic game with reward in [-1, 1] and with partial observability that ends almost surely.

Remark:

The proof is much simpler if we consider only deterministic games; we here consider the general (stochastic) case.

Proof.

We show that, once > 0 is fixed, a brute-force search algorithm suffices to approximate the value of player 1 up to . More precisely, the algorithm can be described as follows:

The Frontier of Decidability in Partially Observable Deterministic Games 9 1: t ← 0 2: p ← 1 3: while p > 2 do 4:

t ← t + 1 5: compute the set Σ 1
|t of all pure strategies of player 1 from timesteps 0 to t;

6:
compute the set Σ 2 |t of all pure strategies of player 2 from timesteps 0 to t ;

7:
for each couple (σ

1 |t , σ 2 |t ) ∈ Σ 1 |t × Σ 2
|t , compute the probability that the game is not over at the end of timestep t under strategies (σ 1 |t , σ 2 |t );

8:
update p as the maximum of all values computed just above; 9: end while 10: compute the value of the game restricted to timesteps 0 to t and deliver this value as an -approximation.

Let us denote by T the random time (depending on the choice of strategies of both players) when the game ends (i.e. the first timestep where a final step is reached), with T = +∞ if the game never ends. By assumption, for all strategies we have T < +∞ almost surely. Note that this is equivalent to require this property for all choices of pure strategies, since mixed strategies are randomizations of pure strategies.

First, let us observe that if the algorithm given above ends, i.e. if condition on line 3 becomes false at some point, then t ends up with a value t 0 such that that for all choices of pure strategies the game will be over before t 0 with probability 1 -2 :

∀σ 1 , σ 2 strategies, P (T > t 0 ) ≤ 1 - 2 . (13)
Clearly, if (13) is true for all couples (σ 1 , σ 2 ) of pure strategies, then it is also true for all couples of mixed strategies.

Step 1: the brute-force algorithm, if it terminates, finds the correct answer with precision . So let us suppose for now that the algorithm terminates, hence a t 0 satisfying (13) is found. We will show that the value v 1 t0 of the first player for the game stopped at time t 0 , which we denote by G |t0 (all plays unfinished at t 0 get a reward 0, as in Lemma 6) is an -approximation of the value v 1 . Below, we will denote the restriction to G |t0 of a strategy σ in G by σ |t0 , and conversely if σ t0 is a strategy in G |t0 we will denote by σ any strategy consisting of playing according to σ |t0 at timesteps prior to t 0 and then playing arbitrarily.

Suppose that there is a mixed strategy σ 1 |t0 ensuring a value v to the first player in G |t0 . Then in G the first player can use any strategy σ 1 consisting of playing σ 1 |t0 until time t 0 and then playing arbitrarily. If v ≥ 0, then against any strategy σ 2 , player 1 ensures:

E[sc(σ 1 , σ 2 )] = P (T ≤ t 0 )E[sc(σ 1 , σ 2 ) | T ≤ t 0 ] + P (T > t 0 )E[sc(σ 1 , σ 2 ) | T > t 0 ] ≥ (1 - 2 )v - 2 ≥ v -.
If v < 0, then we also have

E[sc(σ 1 , σ 2 )] = P (T ≤ t 0 )E[sc(σ 1 , σ 2 ) | T ≤ t 0 ] + P (T > t 0 )E[sc(σ 1 , σ 2 ) | T > t 0 ] ≥ v - 2 ≥ v -.
From these two cases, we deduce that v 1 ≥ v 1 |t0 -. On the other hand, for any choice of a strategy σ 1 for the first player, there is a strategy σ 2 |t0 for the second player such that in

G |t0 E[sc t0 (σ 1 |t0 , σ 2 |t0 )] ≤ v 1 |t0 + 2 .
By playing this strategy σ 2 against σ 1 in G (playing according to σ 2 |t0 before t 0 and arbitrarily after ) it is easy to see by a similar analysis that v 1 ≤ v 1 |t0 + .

Step 2: The brute force algorithm always terminates. So our brute-force search algorithm, if it terminates, delivers an -approximation of v 1 . To prove that it always terminates, suppose the opposite: there is an > 0, and pure strategies (σ 1 t , σ 2 t ) for all t such that the probability that the game is over at time t 0 if players play accordingly to strategies (σ 1 t0 , σ 2 t0 ) is less than 1 -2 . By a minor variation on Lemma 1 it is easy to show the existence of pure strategies (σ 1 ∞ , σ 2 ∞ ) and of a subsequence (σ

1 k 1 t , σ 2 k 2 t ) t≥0 (with k 1 t , k 2 t ≥ t) of (σ 1 t , σ 2
t ) t≥0 such that for i = 1, 2 and all t ≥ 0, strategies σ i k i t and σ i ∞ coincide on times prior to t. Now if players play according to (σ 1 ∞ , σ 2 ∞ ) , then for all t, the probability that the game is not over at time k t is at least 2 , which contradicts the assumption that the game ends almost surely for any choice of strategies.

Conclusion

We have proposed an alternate decision problem for partially observable games (Table 2). This decision problem is based on the approximation of the probability of winning when playing optimally, instead of the existence of a strategy for winning surely.

This criterion:

• directly extends the classical decision problem in matrix games [START_REF] Nash | Some games and machines for playing them[END_REF],

The Frontier of Decidability in Partially Observable Deterministic Games 11

• is known as more relevant for partially observable games as it is closely related to optimal play (see examples in [12], showing that for some natural situations in real world games there is no move with winning probability 100% but there are strategies with winning probability 99% and other strategies with winning probability 1% -and therefore a refined decision criterion as our Value Function Approximation is required); • is significantly different from the classical decision problem in papers about decidability in games.

The third point is clear when comparing with published results with the classical decision problem in games (∃SW, recalled in Table 1): whereas [START_REF] Hearn | Games, Puzzles, and Computation[END_REF] shows decidability with 2 players and undecidability with 3 players (two players playing as a team against a third player, without communication inside the team), we show undecidability (Corollary 4) with 2 players. We have also shown that V F A X, is in O , and that V F A X, becomes approximable if we consider only games which halt almost surely.

Open problem.

An interesting open question is the game of Go. The game of Go is already famous for various mathematical results:

• PSPACE-completeness of Go ladders [START_REF] Lichtenstein | Go is polynomial-space hard[END_REF][START_REF] Crasmaru | Ladders are PSPACE-complete[END_REF],

• EXP-completeness of the complete game [START_REF] Robson | The complexity of go[END_REF],

• NP-completeness of some Tsume-Go [START_REF] Crasmaru | On the complexity of Tsume-Go[END_REF].

These results suggest that all restricted forms of Go are as complicated as possible for their category (i.e. NP-completeness when one player has only one reasonable move and the horizon is polynomial as in the Tsume-Go in [START_REF] Crasmaru | On the complexity of Tsume-Go[END_REF], EXP-completeness in the general case, PSPACE-completeness with polynomial horizon as in the case of ladders).

The game of Go with Japanese rules (in the less usual version of Go termed "Go with Chinese rules", the superko rule forbids loops) has the particularity that it can have loops, and not only in theory; this sometimes happen in real professional games. As phantom-Go is the partially observable variant of Go [START_REF] Cazenave | A phantom-go program[END_REF], it's a good candidate for undecidability results for a natural game. To the best of our knowledge, an undecidability result would be the first known case of real-world undecidable game really played by humans.

  The Frontier of Decidability in Partially Observable Deterministic Games 3

Table 1 .

 1 The Usual Definition of the decision problem for games. With this definition, decidability holds for 2-player games and there is[START_REF] Hearn | Games, Puzzles, and Computation[END_REF]) undecidability for 3-player games (one team of two players, without communication, against a third player).

D. Auger, O. Teytaud

D. Auger, O. Teytaud

D. Auger, O. Teytaud

D. Auger, O. Teytaud

D. Auger, O. Teytaud

Acknowledgements

Author #2 is very grateful to the BIRS seminar on Combinatorial Game Theory, to the Dagstuhl seminar on the Theory of Evolutionary Algorithms, and to the Bielefeld seminar on Search Methods. Author #2 is also grateful to National Science

The Frontier of Decidability in Partially Observable Deterministic Games 7 positive, while being undecidable, belongs to the undecidability class O , jump of the class of decidable problems [START_REF] Post | Recursively enumerable sets of positive integers and their decision problems[END_REF]. More precisely, we show that : Theorem 5. There is a Turing machine which, when given the description of a deterministic recursive game with partial observability and positive rewards, and a rational number c ≥ 0, halts if and only if the first player has a value v 1 > c.

The proof relies on the following lemma. We define sc t as the expected score, under the additional requirement that all games longer than t time steps have a reward 0. sc t is the non-asymptotic approximation of sc, and we will see below in which sense it is a reasonably good approximation. Lemma 6. Let G be a P.O. recursive game and σ 1 be a strategy for the first player. Denote

Proof. Consider a fixed σ 1 ∈ Σ 1 . We show Eq. 6. Suppose (in order to get a contradiction) that there exists an > 0 and for infinitely many t ≥ 0 some strategy σ 2

t for II such that

The strategies σ 2 t can be supposed pure. Apply then Lemma 1 to obtain a strategy σ 2 which coincides for all t ≥ 0 with some σ 2 t , where t ≥ t. Since we have

and the sum of all probabilities in the above sum is at most 1, there exist t 0 such that

Now by construction of σ 2 there is some strategy σ 2 t with t ≥ t 0 which coincides with σ 2 on t = 0, 1, • • • , t 0 , so that we can replace σ 2 by σ 2 t for the definition of the probability in [START_REF] Paz | Introduction to probabilistic automata[END_REF]. From this we deduce that

which is impossible by definition of v 1 (σ 1 ).


Youhei Akimoto
email: youhei.akimoto@lri.fr

Anne Auger
email: anne.auger@lri.fr

Nikolaus Hansen
email: nikolaus.hansen@lri.fr

Convergence of the Continuous Time Trajectories of Isotropic Evolution Strategies on Monotonic C 2 -composite Functions

The Information-Geometric Optimization (IGO) has been introduced as a unified framework for stochastic search algorithms. Given a parametrized family of probability distributions on the search space, the IGO turns an arbitrary optimization problem on the search space into an optimization problem on the parameter space of the probability distribution family and defines a natural gradient ascent on this space. From the natural gradients defined over the entire parameter space we obtain continuous time trajectories which are the solutions of an ordinary differential equation (ODE). Via discretization, the IGO naturally defines an iterated gradient ascent algorithm. Depending on the chosen distribution family, the IGO recovers several known algorithms such as the pure rank-µ update CMA-ES. Consequently, the continuous time IGO-trajectory can be viewed as an idealization of the original algorithm.

In this paper we study the continuous time trajectories of the IGO given the family of isotropic Gaussian distributions. These trajectories are a deterministic continuous time model of the underlying evolution strategy in the limit for population size to infinity and change rates to zero. On functions that are the composite of a monotone and a convex-quadratic function, we prove the global convergence of the solution of the ODE towards the global optimum. We extend this result to composites of monotone and twice continuously differentiable functions and prove local convergence towards local optima.

Introduction

Evolution Strategies (ESs) are stochastic search algorithms for numerical optimization. In ESs, candidate solutions are sampled using a Gaussian distribution parametrized by a mean vector and a covariance matrix. In state-of-the art ESs, those parameters are iteratively adapted using the ranking of the candidate solutions w.r.t. the objective function. Consequently, ESs are invariant to applying a monotonic transformation to the objective function. Adaptive ES algorithms are successfully applied in practice and there is ample empirical evidence that they converge linearly towards a local optimum of the objective function on a wide class of functions. However, their theoretical analysis even on simple functions is difficult as the state of the algorithm is given by both the mean vector and the covariance matrix that have a stochastic dynamic that needs to be simultaneously controlled. Their linear convergence to local optima is so far only proven for functions that are composite of a monotonic transformation with a convex quadratic functionhence function with a single optimum-for rather simple search algorithms compared to the covariance matrix adaptation evolution strategy (CMA-ES) that is considered as the state-of-the-art ES [START_REF] Auger | Convergence results for the (1, λ)-SA-ES using the theory of ϕ-irreducible Markov chains[END_REF][START_REF] Jägersküpper | Probabilistic runtime analysis of (1+, λ), ES using isotropic mutations[END_REF][START_REF] Jägersküpper | How the (1 + 1) ES using isotropic mutations minimizes positive definite quadratic forms[END_REF][START_REF] Jägersküpper | Algorithmic analysis of a basic evolutionary algorithm for continuous optimization[END_REF]. In this paper, instead of analyzing the exact stochastic dynamic of the algorithms, we consider the deterministic time continuous model underlying adaptive ESs that follows from the Information-Geometric Optimization (IGO) setting recently introduced [START_REF] Arnold | Information-geometric optimization algorithms: a unifying picture via invariance principles[END_REF].

The Information-Geometric Optimization is a unified framework for randomized search algorithms. Given a family of probability distributions parametrized by θ ∈ Θ, the original objective function, f , is transformed to a fitness function J θ defined on Θ. The IGO algorithm defined on Θ performs a natural gradient ascent aiming at maximizing J θ . For the family of Gaussian distributions, the IGO algorithm recovers the pure rank-µ update CMA-ES [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF], for the family of Bernoulli distributions, PBIL [START_REF] Baluja | Removing the genetics from the standard genetic algorithm[END_REF] is recovered. When the step-size for the gradient ascent algorithm (that corresponds to a learning rate in CMA-ES and PBIL) goes to zero, we obtain an ordinary differential equation (ODE) in θ. The set of solutions of this ODE, the IGO-flow, consists of continuous time models of the recovered algorithms in the limit of the population size going to infinity and the step-size (learning rate for ES or PBIL) to zero.

In this paper we analyze the convergence of the IGO-flow for isotropic ESs where the family of distributions is Gaussian with covariance matrix equal to an overall variance times the identity. The underlying algorithms are step-size adaptive ESs that resemble ESs with derandomized adaptation [START_REF] Ostermeier | A derandomized approach to self-adaptation of evolution strategies[END_REF] and encompass xNES [START_REF] Glasmachers | Exponential natural evolution strategies[END_REF] and the pure rank-µ update CMA-ES with only one variance parameter [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF]. Previous works have proposed and analyzed continuous models of ESs that are solutions of ODEs [START_REF] Yin | Establishing connections between evolutionary algorithms and stochastic approximation[END_REF][START_REF] Yin | Analyzing the (1, λ) evolution strategy via stochastic approximation methods[END_REF] using the machinery of stochastic approximation [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF][START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF]. The ODE variable in these studies encodes solely the mean vector of the search distribution and the overall variance is taken to be proportional to H(∇f ) where H is a smooth function with H(0) = 0. Consequently the model analyzed looses invariance to monotonic transformation of the objective function and scale-invariance, both being fundamental properties of virtually all ESs. The technique relies on the Lyapunov function approach and assumes the stability of critical points of the ODE [START_REF] Yin | Establishing connections between evolutionary algorithms and stochastic approximation[END_REF][START_REF] Yin | Analyzing the (1, λ) evolution strategy via stochastic approximation methods[END_REF]. In this paper, our approach also relies on the stability of the critical points of the ODE that we analyze by means of Lyapunov functions. However one difficulty stems from the fact that when convergence occurs, the variance typically converges to zero which is at the boundary of the definition domain Θ. To circumvent this difficulty we extend the standard Lyapunov method to be able to study stability of boundary points.

Applying the extended Lyapunov's method to the IGO-flow in the manifold of isotropic Gaussian distributions, we derive a sufficient condition on the so-called weight function w-parameter of the algorithm and usually chosen by the algorithm designerso that the IGO-flow converges to the global minimum independently of the starting point on objective functions that are composite of a monotonic function with a convex quadratic function. We will call those functions monotonic convex-quadratic-composite in the sequel. We then extend this result to functions that are the composition of a monotonic transformation and a twice continuously differentiable function, called monotonic C 2 -composite in the rest of the paper. We prove local convergence to a local optimum of the function in the sense that starting close enough from a local optimum, with a small enough variance, the IGO-flow converges to this local optimum.

The rest of the paper is organized as follows. In Section 2 we introduce the IGO-flow for the family of isotropic Gaussian distributions, which we call ES-IGO-flow. In Section 3 we extend the standard Lyapunov's method for proving stability. In Section 4 we apply the extended method to the ES-IGO-flow and provide convergence results of the ES-IGO-flow on monotonic convex-quadratic-composite functions and on monotonic C 2 -composite functions.

Notation. For A ⊂ X, where X is a topological space, we let A c denote the complement of A in X, A o the interior of A, A the closure of A, ∂A = A \ A o the boundary of A. Let R and R d be the sets of real numbers and d-dimensional real vectors, R 0 and R + denote the sets of non-negative and positive real numbers, respectively.

: C → [C 1,1 , C 1,2 , . . . , C 1,d , C 2,1 , . . . , C d,d ] T , where C i,j is the i, j-th element of C. We use both notations: θ = [m T , vec(C) T ] T and θ = (m, C).

The ES-IGO-flow

The IGO framework for continuous optimization with the family of Gaussian distributions is as follows. The original objective is to minimize an objective function f : R d → R. This objective function is mapped into a function on Θ. Hereunder, we suppose that f is µ Leb -measurable. Let w : [0, 1] → R be a bounded, non-increasing weight function. We define the weighted quantile function [START_REF] Arnold | Information-geometric optimization algorithms: a unifying picture via invariance principles[END_REF] as

W f θ (x) = w P θ [y : f (y) f (x)] . (1)
The function W f θ (x) is a preference weight for x according to the P θ -quantile. The fitness value of θ ′ given θ is defined as the expectation of the preference

W f θ over P θ ′ , J θ (θ ′ ) = E x∼P θ W f θ (x) . Note that since W f θ (x) depends on θ so does J θ (θ ′ ).
The function J θ is defined on a statistical manifold (Θ, I) equipped with the Fisher metric I as a Riemannian metric. The Fisher metric is the natural metric. It is compatible with relative entropy and with KL-divergence and is the only metric that does not depend on the chosen parametrization. Using log-likelihood trick and exchanging the order of differentiation and integration, the "vanilla" gradient of J θ at θ ′ = θ can be expressed as

∇ θ ′ J θ (θ ′ )| θ ′ =θ = E x∼P θ W f θ (x)∇ θ ln(p θ (x)
) . The natural gradient, that is, the gradient taken w.r.t. the Fisher metric, is given by the product of the inverse of the Fisher information matrix I θ at θ and the vanilla gradient, namely

I -1 θ ∇ θ ′ J θ (θ ′ )| θ ′ =θ .
The IGO ordinary differential equation is defined as

dθ dt = I -1 θ ∇ θ ′ J θ (θ ′ ) θ ′ =θ . (2)
Since the right-hand side (RHS) of the above ODE is independent of t the IGO ODE is autonomous. The IGO-flow is the set of solution trajectories of the above ODE [START_REF] Jägersküpper | Probabilistic runtime analysis of (1+, λ), ES using isotropic mutations[END_REF].

When the parameter θ encodes the mean vector and the covariance matrix of the gaussian distribution in the following way θ = [m T , vec(C) T ] T , the product of the inverse of the Fisher information matrix I -1 θ and the gradient of the log-likelihood ∇ θ ln(p θ (x)) can be written in an explicit form [START_REF] Akimoto | Theoretical foundation for CMA-ES from information geometry perspective[END_REF] and (2) reduces to

dθ dt = W f θ (x) x -m vec (x -m)(x -m) T -C P θ (dx) . (3)
The pure rank-µ update CMA-ES [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF] can be considered as an Euler scheme for solving (3) with a Monte-Carlo approximation of the integral. Let x 1 , . . . , x n be samples independently generated from P θ . Then, the quantile P θ [y : 1) is approximated by the number of solutions better than x i divided by n, i.e., {x j , j = 1, . . . , n :

f (y) f (x i )] in (
f (x j ) f (x i )} /n =: R i /n. Then W f θ (x i ) is approximated by w (R i -1/2)/n
, where w is the given weight function. The Euler scheme for approximating the solutions of (3) where the integral is approximated by Monte-Carlo leads to

θ t+1 = θ t + η n i=1 w (R i -1/2)/n n x i -m t vec (x i -m t )(x i -m t ) T -C t , (4)
where η is the time discretization step-size. This equation is equivalent to the pure rank-µ update CMA-ES when the learning rates η m and η C , for the update of m t and C t respectively, are set to the same value η, while they have different values in practice (η m = 1 and η C 1). The summation on the RHS in (4) converges to the RHS of (3) with probability one as λ → ∞ (Theorem 4 in [START_REF] Arnold | Information-geometric optimization algorithms: a unifying picture via invariance principles[END_REF]).

In the following, we study the simplified IGO-flow where the covariance matrix is parameterized by only a single variance parameter v as C = vI d . Under the parameter-

ization θ = [m T , v] T , (2) reduces to dθ dt = W f θ (x) x-m x-m 2 /d-v P θ (dx). Using the change of variable z = (x -m)/ √ v, the above ODE reads dθ dt = F θ (θ) , F θ (θ) = W f θ (m + √ vz) √ vz v( z 2 /d -1) P d (dz) (5)
and we rewrite it by part

dm dt = F m (θ) , F m (θ) = √ v W f θ (m + √ vz)zP d (dz) (6)
dv dt = F v (θ) , F v (θ) = v W f θ (m + √ vz)( z 2 /d -1)P d (dz) . (7)
The domain of this ODE is

Θ = {θ = (m, v) ∈ R d × R + }.
We call (5) the ES-IGO ordinary differential equation. The following proposition shows that for a Lipschitz continuous weight function w, solutions of the ODE (5) exist for any initial condition θ(0) ∈ Θ and are unique.

Proposition 1 (Existence and Uniqueness). Suppose w is Lipschitz continuous. Then the initial value problem: dθ dt = F θ (θ), θ(0) = θ 0 , has a unique solution on [0, ∞) for each θ 0 ∈ Θ, i.e. there is only one solution θ : R 0 → Θ to the initial value problem.

Proof. We can obtain a lower bound a(t) > 0 and an upper bound b(t) < ∞ for v(t) for each t 0 under a bounded w. Similarly, we can have an upper bound c(t) < ∞ for m(t) . Then we have that

(m(t), v(t)) ∈ E(t) = {x ∈ R d : x c(t)} × {x ∈ R + : a(t)
x b(t)} and E(t) is compact for each t 0. Meanwhile, F θ is locally Lipschitz continuous for a Lipschitz continuous w. Since E(t) is compact, the restriction of F θ into E(t) is Lipschitz continuous. Applying Theorem 3.2 in [START_REF] Khalil | Nonlinear systems[END_REF] that is an extension of the theorem known as Picard-Lindelöf theorem or Cauchy-Lipschitz theorem, we have the existence and uniqueness of the solution on each bounded interval [0, t]. Since t is arbitrary, we have the proposition.

⊓ ⊔

Now that we know that solutions of the ES-IGO ODE exist and are unique, we define the ES-IGO-flow as the mapping ϕ : R 0 × Θ → Θ, which maps (t, θ 0 ) to the solution θ(t) of ( 5) with initial condition θ(0) = θ 0 . Note that we can extend the domain of

F θ from Θ = R d × R + to Θ = R d × R 0 .
It is easy to see from ( 5) that the value of F θ (θ) at θ = (m, 0) is 0 for any m ∈ R d . However, we exclude the boundary ∂Θ from the domain for reasons that will become clear in the next section. Because the initial variance must be positive and the variance starting from positive region never reach the boundary in finite time, solutions ϕ(t, •) will stay in the domain Θ. However, as we will see, they can converge asymptotically towards points of the boundary.

Since J θ is adaptive, i.e. J θ1 (θ) = J θ2 (θ) for θ 1 = θ 2 in general, it is not trivial to determine whether the solutions to (2) converge to points where F θ (θ) = 01 . Even knowing that they converge to zeros of F θ (θ) is not helpful at all, because we have F θ (θ) = 0 for any θ with variance zero and we are actually interested in convergence to the point (x * , 0) where x * is a local optimum of f . Remark 1. Because of the invariance property of the natural gradient, the mean vector m(θ) and the variance v(θ) obey ( 6) and ( 7) under re-parameterization of the Gaussian distributions. Therefore, the trajectories of m and v are also independent of the parameterization. For instance, we obtain the same trajectories v(θ) for any of the following parameterizations: θ d+1 = v, θ d+1 = √ v, and θ d+1 = 1 2 ln v, although the trajectories of the parameters θ d+1 are of course different. Consequently, the same convergence results for m(θ) and v(θ) (see Section 4) will hold under any parameterization. Parameterizations θ = (m, v) and θ = (m, 1 2 ln v) correspond to the pure rank-µ update CMA-ES and the xNES with only one variance parameter. Thus, the continuous model to be analyzed encompasses both algorithms.

Remark 2. Theory of stochastic approximation says that a stochastic algorithm θ t+1 = θ t + ηh t follows the solution trajectories of the ODE dθ dt = E[h t | θ t = θ] in the limit for η to zero under several conditions. In our setting, θ encodes m and v and the noisy observation h t = λ i=1 w Ri I -1 θ ∇ θ ln p θ t (x i ), where w i , i = 1, . . . , λ, are predefined weights and R i is the ranking of x i . If we define w(p)

= λ i=1 w i λ-1 i-1 p i-1 (1 -p) λ-i in (1), then F θ (θ) = E[h t | θ t = θ]
and the ODE agrees with [START_REF] Arnold | Information-geometric optimization algorithms: a unifying picture via invariance principles[END_REF]. Therefore, (5) can be viewed as the limit behavior of adaptive-ES algorithms not only in the case η → 0 and λ → ∞ but also in the case η → 0 and finite λ. Indeed, it is possible to bound the difference between {θ t , t 0} and the solution θ(•) of the ODE (5) by extending Lemma 1 in Chapter 9 of [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF].The details are omitted due to the space limitation. 2

Extension of Lyapunov Stability Theorem

When convergence occurs, the variance typically converges to zero. Hence the study of the convergence of the solutions of the ODE will be carried out by analyzing the stability of the points θ * = (x * , 0). However, because points with variance zero are excluded from the domain Θ, we need to extend classical definitions of stability to be able to handle points located on the boundary of Θ.

Definition 1 (Stability). Consider the following system of differential equation

θ = F (θ), θ(0) = θ 0 ∈ D, (8)
where

F : D → R d θ is a continuous map and D ⊂ R d θ is open. Then θ * ∈ D is called -stable in the sense of Lyapunov 3 if for any ε > 0 there is δ > 0 such that θ 0 ∈ D ∩ B(θ * , δ) =⇒ θ(t) ∈ D ∩ B(θ * , ε
) for all t 0, where t → θ(t) is any solution of (8); locally attractive if there is δ > 0 such that θ 0 ∈ D ∩B(θ * , δ) =⇒ lim t→∞ θ(t)θ * = 0 for any solution t → θ(t) of (8); globally attractive if lim t→∞ θ(t)θ * = 0 for any θ 0 ∈ D and any solution t → θ(t) of (8); locally asymptotically stable if it is stable and locally attractive; globally asymptotically stable if it is stable and globally attractive.

We can now understand why we need to exclude points with variance zero from the domain Θ. Indeed, points with variance zero are points from where solutions of the 2 When H(θ) is a (natural) gradient of a function, the stochastic algorithm is called a stochastic gradient method. The theory of stochastic gradient method (e.g., [START_REF] Bonnabel | Stochastic gradient descent on Riemannian manifolds[END_REF]) relates the convergence of the stochastic algorithm with the zeros of H(θ). However, it is not applicable to our algorithm due to the reason mentioned above Remark 1. 3 Usually, stability is defined for stationary points. However, it is not the only case that a point is stable in our definition. Let θ * ∈ D be a stable point. If θ * ∈ D or F can be prolonged by continuity at θ * as lim θ→θ * F (θ) = F (θ * ), then F (θ * ) = 0. That is, θ * is a stationary point. However, lim θ→θ * F (θ) does not always exist for a stable boundary point θ * ∈ ∂D. For example, consider the ODE: dθ1/dt = -θ1/ θ 2 1 + θ 2 2 , dθ2/dt = -θ2. The domain is R × R+. Then, |θ1| and θ2 are monotonically decreasing to zero. Hence, (0, 0) is globally asymptotically stable. However, lim θ→(0,0) F (θ) does not exist.

ODE will never move because F θ (θ) = 0. Consequently, if we include points (x, 0) in Θ, none of these points can be attractive as in a neighborhood we always find θ 0 = (x 0 , 0) such that a solution starting in θ 0 stays there and cannot thus converge to any other point.

A standard technique to prove stability is Lyapunov's method that consists in finding a scalar function V : R d θ → R 0 that is positive except for a candidate stable point θ * with V (θ * ) = 0, and that is monotonically decreasing along any trajectory of the ODE. Such a function is called Lyapunov function (and is analogous to a potential function in dynamical systems). Lyapunov's method does not require the analysis of the solutions of the ODE. The standard Lyapunov's stability theorem gives practical conditions to verify that a function is indeed a Lyapunov function. However, because our candidate stable points are located on ∂Θ, we need to extend this standard theorem.

Lemma 1 (Extended Lyapunov Stability Method). Consider the autonomous system [START_REF] Ostermeier | A derandomized approach to self-adaptation of evolution strategies[END_REF], where

F : D → R d θ is a map and D ⊂ R d θ is the open domain of θ. Let θ * ∈ D be a candidate stable point. Suppose that there is an R > 0 such that (A1): F (θ) is continuous on D ∩ B(θ * , R); (A2):
there is a continuously differentiable V : R d θ → R such that for some strictly increasing continuous function α :

R + → R + satisfying lim p→∞ α(p) = ∞, V (θ * ) = 0, V (θ) α( θ -θ * ) ∀θ ∈ D ∩ B(θ * , R) \ {θ * } (9)
and

∇V (θ) T F (θ) < 0 ∀θ ∈ D ∩ B(θ * , R) \ {θ * }; (10)
(A3): for any r 1 and r 2 such that 0

< r 1 r 2 < R, if a solution θ(•) to (8) starting from D r1,r2 = {θ ∈ D : r 1 θ -θ * r 2 } stays in D r1,r2 for t ∈ [0, ∞), then there is a T 0 and a compact set E ⊂ D r1,r2 such that θ(t) ∈ E for t ∈ [T, ∞).
Then, θ * is locally asymptotically stable. If (A1) and (A2) hold with D replacing D ∩ B(θ * , R) and (A3) holds with R = ∞, then θ * is globally asymptotically stable.

Proof. We follow the proof of Theorem 4.1 in [START_REF] Khalil | Nonlinear systems[END_REF]. We have from assumptions (A1) and (A2) that there is δ < R such that θ * is stable and V (θ(t)) → Ṽ 0 for each θ 0 ∈ D ∩ B(θ * , δ). Moreover, under (A1) and (A2) with D replacing D ∩ B(θ * , R) we have that V (θ(t)) → Ṽ 0 for each θ 0 ∈ D. Since lim t→∞ V (θ(t)) → 0 implies lim t→∞ θθ * = 0 by [START_REF] Glasmachers | Exponential natural evolution strategies[END_REF], it is enough to show Ṽ = 0. We show Ṽ = 0 by contradiction argument. Assume that Ṽ > 0. Then, we have that for each θ 0 ∈ D (or ∈ D ∩ B(θ * , δ) for the case of local asymptotic stability) there are r 1 and r 2 such that 0 < r 1 r 2 ( δ) and θ(t) lies in D r1,r2 for t 0. Note that D r1,r2 is not necessarily a compact set. This is different from Theorem 4.1 in [START_REF] Khalil | Nonlinear systems[END_REF]. By assumption (A3) we have that there is a compact set E and T 0 such that θ(t) ∈ E for t T . Since V is continuously differentiable and F is continuous, ∇V (θ) T F (θ) is continuous. Then, the function θ → V (θ) T F (θ) has its maximum -β on the compact E and -β < 0 by [START_REF] Yin | Establishing connections between evolutionary algorithms and stochastic approximation[END_REF]. This leads to

V (θ(t)) V (θ(T )) -β(t -T ) ↓ -∞ as t → ∞. This contradicts the hypothesis that V > 0. Hence, Ṽ = 0 for any θ 0 ∈ D (or ∈ D ∩ B(θ * , δ)).
⊓ ⊔

Convergence of the ES-IGO-flow

In this section we study the convergence properties of the ES-IGO-flow ϕ : (t, θ 0 ) → θ(t), where θ(•) represents the solution to the ES-IGO ODE (5) with initial value θ(0) = θ 0 , i.e., dϕ(t,θ0) dt = F θ (ϕ(t, θ 0 )) and ϕ(0, θ 0 ) = θ 0 . By the definition of asymptotic stability, the global asymptotic stability of θ * ∈ Θ implies the global convergence, that is, lim t→∞ ϕ(t, θ 0 ) = θ * for all θ 0 ∈ Θ. Moreover, the local asymptotic stability of θ * ∈ Θ implies the local convergence, that is, ∃δ > 0 such that lim t→∞ ϕ(t, θ 0 ) = θ * for all θ 0 ∈ Θ ∩ B(θ * , δ). We will prove convergence properties of the ES-IGO-flow by applying Lemma 1. In order to prove our result we need to make the following assumption on w: (B1): w is non-increasing and Lipschitz continuous with w(0) > w(1); (B2):

w(P 1 [y : y z])(z 2 /d -1/d)P 1 (dz) = α > 0.
Assumption (B1) is not restrictive. Indeed, the non-increasing and non-constant property of w(•) is a natural requirement and any weight setting in (4) can be expressed, for any given population size n, as a discretization of some Lipschitz continuous weight function. Assumption (B2) is satisfied if and only if the variance v diverges exponentially on a linear function. In fact, F v (θ) defined in [START_REF] Baluja | Removing the genetics from the standard genetic algorithm[END_REF] reduces to v w(P 1 [y : y z])(z 2 /d -1/d)P 1 (dz) when f (x) = a T x for ∀a ∈ R d \ {0} and we have that v = αv and the solution is v(t) = v 0 exp(αt). Then, v(t) → ∞ as t → ∞. Assumption (B2) holds, for example, if w is convex and not linear.

Let G be the set of strictly increasing functions g : R → R that are µ Leb -measurable and C 2 be the set of twice continuously differentiable functions h : R d → R that are µ Leb -measurable. Under (B1) and (B2), we have the following main theorems.

Theorem 1. Suppose that the objective function f is a monotonic convex-quadraticcomposite function g • h, where g ∈ G and h is a convex quadratic function x → (xx * ) T A(xx * )/2 where A is positive definite and symmetric. Assume that (B1) and (B2) hold. Then, θ * = (x * , 0) ∈ Θ is the globally asymptotically stable point of the ES-IGO. Hence, we have the global convergence of ϕ(t, θ 0 ) to θ * . Proof. Since the ES-IGO does not explicitly utilize the function values but uses the quantile P θ [y : f (y) f (x)] which is equivalent to P θ [y :

g -1 • f (y) g -1 • f (x)],
without loss of generality we assume f = h.

According to Lemma 1, it is enough to show that (A1) and (A2) hold with D(= Θ) replacing D ∩ B(θ * , R) and (A3) holds with R = ∞. As is mentioned in the proof of Proposition 1, F θ is locally Lipschitz continuous for a Lipschitz continuous w. Thus, (A1) is satisfied under (B1).

We can choose as a Lyapunov candidate function

V (θ) = d i=1 (m i -x * i ) 2 +d•v = m -x * 2 + Tr(vI d ).
All the conditions on V described in (A2) are obvious except for the negativeness of ∇V (θ) T F θ (θ). To show the negativeness, rewrite F θ (θ) as W f θ (m + √ vz)F θ (θ, z)P d (dz). The idea is to show the (strictly) negative correlation between W f θ (m + √ vz) and ∇V (θ) T F θ (θ, z) by using an extension of the result in [18, Chapter 1] and apply the inequality

W f θ (m+ √ vz)∇V (θ) T F θ (θ, z)P d (dz) < W f θ (m + √ vz)P d (dz) ∇V (θ) T F θ (θ, z)P d (dz) = 0.
We use the non-increasing property of w with w(0) > w(1) in (B1) to show the negative correlation.

To prove (A3), we require (B2). Since a continuously differentiable function can be approximated by a linear function at any non-critical point x, the natural gradient F θ is approximated by that on a linear function in a small neighborhood of (x, 0). We use the property µ Leb [x : f (x) = f ] = 0 to approximate F θ . As is mentioned above, (B2) implies F v on a linear function is positive. By using the approximation and this property, we can show that E = D r1,r2 ∩{θ : v v} satisfies (A3) for some v > 0. ⊓ ⊔ We have that for any initial condition θ(0) = (m 0 , v 0 ), the search distribution P θ weakly converges to the Dirac measure δ x * concentrated at the global minimum point x * . This result is generalized to monotonic C 2 -composite functions using a quadratic Taylor approximation. However, global convergence becomes local convergence.

Theorem 2. Suppose that the objective function f is a monotonic C 2 -composite function g • h, where g ∈ G and h ∈ C 2 has the property that µ Leb [x : h(x) = s] = 0 for any s ∈ R. Assume that (B1) and (B2) hold. Let x * be a critical point of h, i.e. ∇h(x * ) = 0, with a positive definite Hessian matrix A. Then, θ * = (x * , 0) ∈ Θ is a locally asymptotically stable point of the ES-IGO. Hence, we have the local convergence of ϕ(t, θ 0 ) to θ * . Moreover, if x is not a critical point of h(•), for any θ 0 ∈ Θ, ϕ(t, θ 0 ) will never converge to θ = (x, 0).

Proof. As in the proof of Theorem 1, we assume f = h without loss of generality. The proofs of (A1) and (A3) carry over from Theorem 1 because we only used the property µ Leb [x : f (x) = f ] = 0. To show (A2), we use the Taylor approximation of the objective function f . Since f is approximated by a quadratic function in a neighborhood of a critical point x * , we approximate the natural gradient by the corresponding natural gradient on the quadratic function. Then, employing the same Lyapunov candidate function as in the previous theorem we can show (A2). Because of the approximation, we only have local asymptotic stability. The last statement of Theorem 2 is an immediate consequence of the approximation of the natural gradient and (B2).

⊓ ⊔

We have that starting from a point close enough to a local minimum point x * with a sufficiently small initial variance, the search distribution weakly converges to δ x * . It is not guaranteed for the parameter to converge somewhere when the initial mean is not close enough to the local optimum or the initial variance is not small enough. Theorem 2 also states that the convergence (m(t), v(t)) → (x, 0) does not happen for x such that ∇h(x) = 0. That is, the continuous time ES-IGO does not prematurely converge on a slope of the landscape of f .

Conclusion

In this paper we have proven the local convergence of the continuous time model associated to step-size adaptive ESs towards local minima on monotonic C 2 -composite functions. In the case of monotonic convex-quadratic-composite functions we have proven the global convergence, i.e. convergence independently of the initial condition (provided the initial step-size is strictly positive) towards the unique minimum. Our analysis relies on investigating the stability of critical points associated to the underlying ODE that follows from the Information Geometric Optimization setting. We use a classical method for the analysis of stability of critical points, based on Lyapunov functions. We have however extended the method to be able to handle convergence towards solutions at the boundary of the ODE definition domain. We believe that our approach is general enough to handle more difficult cases like the CMA-ES with a more general covariance matrix. We want to emphasize that the model we have analyzed is the correct model for step-size adaptive ESs as the ODE encodes both the mean vector and step-size and preserves fundamental invariance properties of the algorithm.

  Let x represent the Euclidean norm of x ∈ R d . The open and closed balls in R d centered at θ with radius r > 0 are denoted by B(θ, r) and B(θ, r). Let µ Leb denote the Lebesgue measure on either R or R d . Let P 1 and P d be the probability measures induced by the one-variate and d-variate standard normal distributions, p 1 and p d the probability density function induced by P 1 and P d w.r.t. µ Leb . Let p θ and P θ represent the probability density function w.r.t. µ Leb and the probability measure induced by the Gaussian distribution N (m(θ), C(θ)) parameterized by θ ∈ Θ, where the mean vector m(θ) is in R d and the covariance matrix C(θ) is a positive definite symmetric matrix of dimension d. We sometimes abbreviate m(θ(t)) and C(θ(t)) to m(t) and C(t). Let vec : R d×d → R d 2 denote the vectorization operator such that vec

If J θ is not adaptive and defined to be the expectation of the objective function f (x) over P θ , convergence to the zeros of the RHS of (2) is easily obtained. For example, see Theorem 12 and its proof in[START_REF] Malagò | Towards the geometry of estimation of distribution algorithms based on the exponential family[END_REF], where the solution to the system of a similar ODE whose RHS is the vanilla gradient of the expected objective function is derived and the convergence of the solution trajectory to the critical point of the expected function is proven.

Acknowledgments

This work was partially supported by the ANR-2010-COSI-002 grant (SIMINOLE) of the French National Research Agency and the ANR COSINUS project ANR-08-COSI-007-12.


Olivier Jacquin

Wilfried Glastre

Eric Lacot

Olivier Hugon

Hugues Guillet De Chatellus

Ramaz François

Acousto-optic laser optical feedback imaging

teaching and research institutions in France or abroad, or from public or private research centers.

Acousto-optic laser optical feedback imaging O. Jacquin 1,* , W. Glastre 1 , E. Lacot 1 , O.Hugon 1 , H. Guillet de Chatellus 1 and F.Ramaz 2 1 Centre National de la Recherche Scientifique / Université de Grenoble 1, Laboratoire Interdisciplinaire de Physique, UMR 5588,Grenoble, F-38041 2 Institut Langevin "ondes et images, CNRS : UMR7587 -ESPCI ParisTech -Université Paris VI -Pierre et Marie Curie -Université Paris VII -Paris Diderot *Corresponding author: Olivier.jacquin@ujf-grenoble.fr publishedin OPTICS LETTERS / Vol. 37, No. 13 / July 1, 2012

We present a photon noise and diffraction limited imaging method combining the imaging laser and ultrasonic waves. The laser optical feedback imaging (LOFI) technique is an ultrasensitive imaging method for imaging objects through or embedded within a scattering medium. However, LOFI performances are dramatically limited by parasitic optical feedback occurring in the experimental setup. In this work, we have tagged the ballistic photons by an acousto-optic effect in order to filter the parasitic feedback effect and to reach the theoretical and ultimate sensitivity of the LOFI technique. We present the principle and the experimental setup of the acousto-optic laser optical feedback imaging (AO-LOFI) technique, and we demonstrate the suppression of the parasitic feedback.

OCIS Codes: OCIS Codes:, (110.4280) , (110.3175) , (280.3420)

Context

Imaging objects through or embedded within a scattering media is a challenging problem linked to many medical applications such as cancer detection. The main challenge is to realize images through a turbid medium with both a high resolution and good signal to noise ratio (SNR). The information needed to obtain diffraction-limited images is carried by ballistic photons. However compared to scattered photons their number rapidly decreases with the depth, which dramatically reduces the SNR. Consequently, imaging through scattering media with diffraction-limited resolution requires both the detection of ballistic photons and the rejection of the scattered light. The filtering of the scattered light is generally achieved by limiting the depth of focus of the imaging setup. Efficient methods for accomplishing this goal include confocal microscopy [1], time resolved techniques [2] and optical coherent microscopy [3]. However, the thickness of the scattering medium explored with these techniques is limited to about twenty mean free paths and these methods require a high optical power in the medium to compensate for the losses in ballistic photons, which is often not compatible with medical application. To image deeper with a "good" SNR, there is a great interest in using the scattered photons since they decrease much slower than the ballistic ones. In this case, a millimetric resolution can be obtained by acoustic tagging of the scattered photon with a focalized ultrasonic wave, as in Acousto-Optical Coherence Tomography (AOCT) [4].

LOFI technique and imaging through turbid media

We propose to use the LOFI technique while focalizing an ultrasonic (US) wave in a scattering media in order to image embedded object with a diffraction-limited resolution. LOFI is an ultrasensitive laser autodyne interferometer and also a confocal imaging technique combining the great accuracy of optical interferometry with the very high sensitivity of class B lasers to optical feedback [5].In this autodyne method, the optical beating between a reference wave and the signal wave (the light back-reflected by the target) takes place inside the laser source cavity, and can be amplified by the laser gain. Thanks to a resonant amplification, an optical feedbacks as low as -130dB is then detectable in a 1Khz detection bandwidth, with a laser output power of a few mW [6].

The confocal nature of the method is set by the coupling between the intracavity light mode and the light backreflected by the target. Indeed, the fundamental transverse mode (TEM00mode) of the laser plays the role of a spatial filter, like the pinhole of a confocal microscope.

In the LOFI technique, the laser plays the role of both the emitter and of the detector, and the SNR of the method can easily be shot noise limited [7]. In conclusion, the LOFI method is a priori a powerful imaging method to realize simultaneously reflectivity and phase (i.e. profilometry) images under non-cooperative conditions such as imaging through a scattering media with a low optical power. However, parasitic optical feedbacks present in the experimental setup dramatically limit the lowest detectable target reflectivity [8]. Indeed, it may be problematic to detect a target signal of lower magnitude than the noise reinjected by the parasitic feedback. We have proposed in a previous paper a solution to isolate the parasitic feedback effect based on a two beams setup, which unfortunately limits the numerical aperture of the focusing lens and significantly decreases the resolution [8]. To avoid the parasitic optical feedback effect while preserving the lateral optical resolution, we propose here to locally tag the photons of interest (i.e. back-reflected by the target) with a focused US wave and to detect selectively these photons by heterodyne filtering.

LOFI setup with acoustic tagging A scheme of our experimental setup is shown in Fig 1.

First, we describe a conventional LOFI setupwithout local acoustic tagging (i.e. without the acoustic transducer of fig. 1) which is thesame as one describedin [7]. The laser is a cw Nd 3+ :YAG microchip with an output power Pout=40mW (i.e. pout=2.14x10 17 photon/s), at the wavelength λ=1064nm. The laser beam is frequency shifted through two acousto-optic modulators (AOM), the frequency shift is tunable and is noted FA/2. Then the laser beam is sent onto the studied target using a two-axis galvanometric mirror scanner and a focusing lens. The back-reflectedlight by the target is reinjected in the laser by the same path. After a round-trip of the light, the frequency shift introduced by the AOMs is FA. The photons re-injected inside the laser create an optical beating and lead to a modulation of the output power at the frequency FA. There is a resonant amplification of this modulation if FA is close to the laser relaxation frequency FR and in this case, the method is a priori shot noise limited. A beam splitter sends a fraction of the output power on the photodiode connected to a lock-in amplifier which gives the magnitude and the phase of the output power modulation. The LOFI images are built point by point by moving the laser beam on the target. Then, it is possible to realize simultaneously reflectivity and phase images of the target in non-cooperative conditions such as through turbid media. In our experiment, the target is located inside a glass tank filled with a scattering medium. The input side of the tank produces a parasitic feedback which degrades significantly the SNR of the LOFI images. In these conditions, the "LOFI signal" corresponds to the coherent sum of the light back-scattered by the tank and by the target [8]. The noise equivalent power (NEP) is given by the sum of the quantum noise of the laser and the noise due to the tank parasitic feedback, we neglect the others parasitic backscattering. The SNR is then given by [7,8]

p K r p R F p K d d r r r r SNR               (1)
where rpand rtare the effective reflection coefficients of the input side of the tank and of the target respectively,dP and dt are the laser-tank and the laser-target distances respectively, Κopt is the ratio between the light power at the input face of the tank and the power at the output of the laser, ΔF is the detection bandwidthand Rbs is the beam splitter reflectivity.

When the incident power Pout sent onto the target is increased in order to compensate for the scattering losses, the NEP is limited by the optical power back-reflected by the tank and the SNR shows an asymptotic behavior. The SNR is then intrinsically limited and there is no possibility to increase it. In a LOFI setup with acoustic tagging (AO-LOFI), a US transduceris immerged in the tank (fig. 1) to tag selectively by acousto-optic interaction, the photon that has traveled inside the tank. The selected transducer produces a focused US beam with a 1.75 mm diameter (at -6dB) at focus. The US frequency is noted FS/2 and is equal to 2.25MHz . The transducer operating in the cw regime is placed and oriented in order to optimize the transverse overlapping between the laser beam and the focal zone of the acoustic wave. The transducer is located near the input side of the tank (close to the scanner) in order to keep a good overlapping during the scan of the target. Because of the short interaction length, the acousto-optical interaction is the Raman-Nath diffraction regime. The laser beam is split into three diffraction orders: 0, +1 and -1. The diffracted light is shifted in frequency by +FS and -FS for the order +1 and -1 respectively. The total frequency shift of the re-injected light is FA+FS, FA and FA-FS for the diffraction orders +1, 0 and -1, respectively. The frequency shift of the parasitic feedback is always FAconsequently, it is possible to filter the parasitic feedback effect by selecting the frequency FA+FS or FA-FS as a reference for the lock-in detection. In these conditions, the AO-LOFI signal corresponds to the light back-reflected by the target, and the NEP is the quantum noise of the laser. The SNR is then given by [7]:

out US US t bs P F r R SNR   2 .  (2)
whereKus is the acousto-optic efficiency for the first diffraction order. Here, the SNR increases with the power sent on the target (Kopt.pout) and with the integration time of the detection (1/ΔF) and the NEP is shot noise limited.

Experimental results

Two images obtained with the LOFI and the AO-LOFI setups are shown on figures 2a and 2b respectively, for comparison. The target is a metallic rule immerged inside a glass tank filled with water and a low milk concentration (2%). The corresponding scattering losses are about 5dB/cm (about 12 mean free paths on a round trip). The target is located 5cm away from the input side of the tank. The total round trip backscattering losses are then about 50dB. The RF power sent on the acoustic transducer is about 6.4W. The integration time and the frequency reference of the lock'in detection are 100µs and 3MHz respectively for both setups On the images of fig. 2 we can distinguish the edge of the ruler with two graduations. We can consider two distinct parts in these images: the left part corresponds to the ruler and allows to evaluate the LOFI or AO-LOFI signals, while the right part without the target allows to evaluate the so-called NEP. In each image, an average value of the SNR has been calculated for LOFI or AO-LOFI signal and NEP (see fig. 2). The ratio between the signal values in both images gives an acousto-optic efficiency of 13%. Despite a lower photometric budget, the SNR is higher in the AO-LOFI image than in the LOFI image. In our example, the corresponding SNR is about 5 with AO-LOFIand only 1.6 with the conventional LOFI. This difference can be explained by the isolation of the parasitic feedback produced by the tank in fig. 2b. In order to confirm this isolation effect, we have evaluated the SNR for both setups by varying the optical losses (i.e. the parameter Κopt in eq. 1 and eq.2). The modulation has been obtained by a polarizer and a half-wave plate inserted between the beam splitter and the frequency shifter (fig. 1). So as to realize images with a wide range of Koptvalues, the scattering losses are lower than on fig. 2, (about 2dB/cm), which explains a higher SNR. The shape of the curves presented on fig. 3 is in good agreement with the predicted behavior by eq.1 and eq.2. The SNR has an asymptotic behavior versus K in LOFI images while it has a quasi linear evolution in AO-LOFI images. These results validate the parasitic feedback isolation in the AO-LOFI setup and the possibility to enhance the SNR with an increase of the integration time or with a higher laser output power.

Conclusion

We have demonstrated the possibility to filter the parasitic feedback effect in LOFI image by acoustic tagging of the ballistic photons close to the studied target, which considerably enhances the sensitivity of the LOFI technique. Measurements validate the possibility to implement LOFI with a NEP shot noise limited: the detection limit is then given by the quantum noise of the laser. In a future work, we will use this tagging to enhance the sensitivity of the Synthetic Aperture LOFI technique [9] We will study also be the possibility to remove the frequency shifter made of two AOMs, which is needed in the setup depicted in fig. 1 to lift the degeneration of the frequency shift between the diffraction orders +1 and -1.

Fig. 1 .

 1 Fig.1. Schematic diagram of LOFI setup with acoustic tagging (AO-LOFI).PD, photodiode; BS, beam splitter.

Fig. 2 .

 2 Images of the target in a scattering medium. a) with the LOFI setup at the FA reference frequency, FA=3MHz. b) with the AO-LOFI setup at the FA-FS frequency, FA=7.5MH and FS=4.5MHz. The left (resp. right) rectangle represents the area where the signal (resp. noise) is measured. Both rectangles represent 625 pixels.

Fig. 3 .

 3 Fig.3. SNR versus parameter Kopt, in LOFI and AO-LOFI images.

  :

	t	2	2 P	2	t	P	cos	2	2		P		t		.	opt	.	out
				2				out		P	opt	.	out
						bs