Huyên Pham

Xiaoli Wei

Discrete time McKean-Vlasov control problem: a dynamic programming approach

Keywords: MSC Classification: 60K35, 49L20 McKean-Vlasov equation, dynamic programming, calculus of variations

We consider the stochastic optimal control problem of nonlinear mean-field systems in discrete time. We reformulate the problem into a deterministic control problem with marginal distribution as controlled state variable, and prove that dynamic programming principle holds in its general form. We apply our method for solving explicitly the mean-variance portfolio selection and the multivariate linear-quadratic McKean-Vlasov control problem.

Introduction

The problem studied in this paper concerns the optimal control of nonlinear stochastic dynamical systems in discrete time of McKean-Vlasov type. Such topic is related to the modeling of collective behaviors for a large number of players with mutual interactions, which has led to the theory of mean-field games (MFGs), introduced in [START_REF] Lasry | Mean-field games[END_REF] and [START_REF] Huang | Large population stochastic dynamic games: closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle[END_REF].

Since the emergence of MFG theory, the optimal control of mean-field dynamical systems has attracted a lot of interest in the literature, mostly in continuous time. It has been first studied in [START_REF] Ahmed | Controlled McKean-Vlasov equation[END_REF] by functional analysis method with a value function expressed in terms of the Nisio semigroup of operators. More recently, several papers have adopted the stochastic maximum principle for characterizing solutions to the controlled McKean-Vlasov systems in terms of adjoint backward stochastic differential equations (BSDEs), see [START_REF] Andersson | A maximum principle for SDEs of mean-field type[END_REF], [START_REF] Buckdahn | A general maximum principle for SDEs of mean-field type[END_REF], [START_REF] Carmona | Forward-backward Stochastic Differential Equations and Controlled McKean Vlasov Dynamics[END_REF]. We also refer to the paper [START_REF] Yong | A linear-quadratic optimal control problem for mean-field stochastic differential equations[END_REF] which focused on the linear-quadratic (LQ) case where the BSDE from the maximum principle leads to a Riccati equation system. It 1 is mentioned in these papers that due to the non-markovian nature of the McKean-Vlasov systems, dynamic programming (also called Bellman optimality) principle does not hold and the problem is time inconsistent in general. Indeed, the standard Markov property of the state process, say X, is ruled out, however, as noticed in [START_REF] Bensoussan | Mean Field Games and Mean Field Type Control Theory[END_REF], this can be restored by working with the marginal distribution of X. The dynamic programming has then been applied independently in [START_REF] Bensoussan | The Master equation in mean-field theory[END_REF] and [START_REF] Laurière | Dynamic programming for mean-field type control[END_REF] for a specific control problem where the objective function depends upon statistics of X like its mean value, with a mean-field interaction on the drift of the diffusion dynamics of X, and in particular by assuming the existence at all times of a density function for the marginal distribution of X.

The purpose of this paper is to provide a detailed analysis of the dynamic programming method for the optimal control of nonlinear mean-field systems in discrete time, where the coefficients may depend both upon the marginal distributions of the state and of the control. The case of continuous time McKean-Vlasov equations requires more technicalities and mathematical tools, and will be addressed in [START_REF] Pham | Bellman equation for McKean-Vlasov control problem[END_REF]. The discrete time framework has been also considered in [START_REF] Elliott | Discrete time mean-field stochastic linear-quadratic optimal control problems[END_REF] for LQ problem, and arises naturally in situations where signal values are available only at certain times. On the other hand, it can also be viewed as the discrete time version or approximation of the optimal control of continuous time McKean-Vlasov stochastic differential equations. Our methodology is the following. By using closed-loop (also called feedback) controls, we first convert the stochastic optimal control problem into a deterministic control problem involving only the marginal distribution of the state process. We then derive the deterministic evolution of the controlled marginal distribution, and prove in its general form the dynamic programming principle (DPP). This gives sufficient conditions for optimality in terms of calculus of variations in the space of feedback control functions. Classical DPP for stochastic control problem without mean-field interaction falls within our approach. We finally apply our method for solving explicitly the meanvariance portfolio selection problem and the multivariate LQ mean-field control problem, and retrieve in particular the results obtained in [START_REF] Elliott | Discrete time mean-field stochastic linear-quadratic optimal control problems[END_REF] by four different approaches.

The outline of the paper is as follows. The next section formulates the McKean-Vlasov control problem in discrete time. In Section 3, we develop the dynamic programming method in this framework. Section 4 is devoted to applications of the DPP with explicit solutions in the LQ case including the mean-variance problem.

McKean-Vlasov control problem

We consider a general class of optimal control of mean-field type in discrete time. We are given two measurable spaces (E, B(E)) and (A, B(A)) representing respectively the state space, and the control space. We denote by P(E) and P(A) the set of probability measures on (E, B(E)) and (A, B(A)). On a probability space (Ω, F, P), we consider a controlled stochastic dynamics of McKean-Vlasov type:

X α k+1 = F k+1 (X α k , P X α k , α k , P α k , ε k+1 ), k ∈ N, X α 0 = ξ, (2.1)
for some measurable functions F k defined from E×P(E)×A×P(A)×R d into E, where (ε k ) k is a sequence of i.i.d. random variables, independent of the initial random value ξ, and we denote by F = (F k ) k the filtration with F k the σ-algebra generated by {ξ, ε 1 , . . . , ε k }. Here, (X α k ) k is the state process valued in E controlled by the F-adapted process (α k ) k valued in A, and we adopted the usual notation in the sequel of the paper: given a random variable Y on (Ω, F, P), P Y denotes its probability distribution under P. Thus, the dynamics of (X α k ) depends at any time k of its marginal distribution, but also of the marginal distribution of the control, which represents an additional mean-field feature with respect to classical McKean Vlasov equations, and also considered recently in [START_REF] Elliott | Discrete time mean-field stochastic linear-quadratic optimal control problems[END_REF] and [START_REF] Yong | A linear-quadratic optimal control problem for mean-field stochastic differential equations[END_REF].

Let us now precise the assumptions on the McKean-Vlasov equation. We shall assume that (E, |.|) is a normed space (most often R d ), (A, |.|) is also a normed space (typically a subset of R m ), and we denote by P 2 (E) the space of square integrable probability measures over E , i.e. µ ∈ P(E) s.t. µ 2 2 := E |x| 2 µ(dx) < ∞, and similarly for P 2 (A). For any (x, µ, a, λ) ∈ E × P(E) × A × P(A), and k ∈ N, we denote by P k+1 (x, µ, a, λ, dx ′ ) the probability distribution of the E-valued random variable F k+1 (x, µ, a, λ, ε k+1 ) on (Ω, F, P), and we assume (H1) For any k ∈ N, there exists some positive constant C k,F s.t. for all (x, a, µ, λ) ∈ E × A × P(E) × P(A):

E |x ′ | 2 P k+1 (x, µ, a, λ, dx ′ ) = E F k+1 (x, µ, a, λ, ε k+1 ) 2 ≤ C k,F (1 + |x| 2 + |a| 2 + µ 2 2 + λ 2 2 ).
Assuming that the initial random value ξ is square integrable, and considering admissible controls α which are square integrable, i.e. E|α k | 2 < ∞, for any k, it is then clear under (H1) that E|X α k | 2 < ∞, i.e. P X α k ∈ P 2 (E), and there exists some positive constant C k s.t.

E|X α k | 2 ≤ C k 1 + E|ξ| 2 + k-1 j=0 E|α j | 2 . (2.
2)

The cost functional associated to the system (2.1) over a finite horizon n ∈ N \ {0} is:

J(α) := E n-1 k=0 f k (X α k , P X α k , α k , P α k ) + g(X α n , P X α n ) , (2.3)
for any square integrable F-adapted processes α valued in A, where the running cost functions f k , k = 0, . . . , n -1, are measurable real-valued functions on E × P 2 (E) × A × P 2 (A), and the terminal cost function g is a real-valued measurable function on E × P 2 (E). We shall assume (H2) There exist some positive constant C g and for any k = 0, . . . , n -1, some positive constant C k,f s.t. for all (x, a, µ, λ) ∈ E × A × P 2 (E) × P 2 (A):

f k (x, µ, a, λ) ≤ C k,f (1 + |x| 2 + |a| 2 + µ 2 2 + λ 2 2 ), g(x, µ) ≤ C g (1 + |x| 2 + µ 2 2 ).
Under (H1)-(H2), the cost functional J(α) is well-defined and finite for any admissible control, and the objective is to minimize over all admissible controls the cost functional, i.e. by solving

V 0 := inf α J(α), (2.4)
and when V 0 > -∞, find an optimal control α * i.e. achieving the minimum in (2.4) if it exists. Problem (2.1)-(2.4) arises in the study of collective behaviors of a large number of players (particles) resulting from mean-field interactions: typically, the controlled dynamics of a system of N symmetric particles are given by

X i,α i k+1 = F k+1 (X i,α i k , 1 N N j=1 δ X j,α i k , α i k , 1 N N j=1 δ α j k , ε i k+1 ), i = 1, . . . , N,
(here δ x is the Dirac measure at x) and by assuming that a center decides of the general same policy α i = α for all players with same running and terminal gain functions, the propagation of chaos argument from McKean-Vlasov theory (see [START_REF] Sznitman | Topics in propagation of chaos[END_REF]) states that when the number of players N goes to infinity, the problem of each agent is asymptotically reduced to the problem of a single agent with controlled dynamics (2.1) and objective (2.4). We refer to [START_REF] Carmona | Control of McKean-Vlasov dynamics versus mean field games[END_REF] for a detailed discussion about optimal control of McKean-Vlasov equations and connection with equilibrium of large populations of individuals with mean-field interactions.

Dynamic programming

In this section, we make the standing assumptions (H1)-(H2), and our purpose is to show that dynamic programming principle holds for problem (2.4), which we would like to combine with some Markov property of the controlled state process. However, notice that the McKean-Vlasov type dependence on the dynamics of the state process rules out the standard Markov property of the controlled process (X α k ). Actually, this Markov property can be restored by considering its probability law (P X α k ) k . To be more precise and for the sake of definiteness, we shall restrict ourselves to controls α = (α k ) k given in closed-loop (or feedback) form:

α k = αk (X α k ), k = 0, . . . , n -1, (3.1)
for some deterministic measurable functions αk of the state. Notice that the feedback control may also depend on the (deterministic) marginal distribution, and it will be indeed the case for the optimal one, but to alleviate notation, we omit this dependence which is implicit through the deterministic function αk . We denote by A E the set of measurable functions on E valued in A, which satisfy a linear growth condition, and by A the set of admissible controls α in closed loop form (3.1) with αk in A E , k ∈ N. We shall often identify α ∈ A with the sequence (α k ) k in A E via (3.1). Notice that any α ∈ A satisfies the square integrability condition, i.e. E|α k | 2 < ∞, for all k. Indeed from the linear growth condition on αk in A E , we have

E|α k | 2 ≤ C α (1 + E|X α k | 2 )
for some constant C α (depending on α), which gives the square integrability condition by (2.2).

Next, we show that the initial stochastic control problem can be reduced to a deterministic control problem. Indeed, the key point is to observe by definition of P X α k and noting that P α k is the image by αk of P X α k for a feedback control α ∈ A, that the gain functional in (2.3) can be rewritten as:

J(α) = n-1 k=0 fk (P X α k , αk ) + ĝ(P X α n ), (3.2)
where fk , k = 0, . . . , n -1, are defined on P 2 (E) × A E , ĝ is defined on P 2 (E) by: fk (µ, α) :

= E f k (x, µ, α(x), α ⋆ µ)µ(dx), ĝ(µ) := E g(x, µ)µ(dx), (3.3)
and α ⋆ µ ∈ P 2 (A) denotes the image by α ∈ A E of the measure µ ∈ P 2 (E):

α ⋆ µ (B) = µ α-1 (B) , ∀B ∈ B(A).
Hence, the original problem (2.4) is transformed into a deterministic control problem involving the infinite dimensional marginal distribution process. Let us then define the dynamic version for problem (2.4):

V α k := inf β∈A k (α) n-1 j=k fj (P X β j , βj ) + ĝ(P X β n ), k = 0, . . . , n, (3.4)
for α ∈ A, where A k (α) = {β ∈ A : β j = α j , j = 0, . . . , k -1}, with the convention that

A 0 (α) = A, so that V 0 = inf α∈A J(α) is equal to V α 0 . It is clear that V α k < ∞,
and we shall assume that

V α k > -∞, k = 0, . . . , n, α ∈ A. (3.5)
Remark 3.1 The finiteness condition (3.5) can be checked a priori directly from the assumptions on the model. For example, when f k , g, hence fk , g, k = 0, . . . , n -1, are lower-bounded functions, condition (3.5) clearly holds. Another example is the case when f k (x, µ, a, λ), k = 0, . . . , n -1, and g are lower bounded by a quadratic function in x, µ, and λ, so that by the linear growth condition on α,

fk (µ, α) + ĝ(x, µ) ≥ -C k 1 + µ 2 , ∀µ ∈ P 2 (E), α ∈ A E ,
and we are able to derive moment estimates on X α k , uniformly in α:

P X α k 2 2 = E[|X α k | 2 ] ≤ C k ,
which arises typically when A is bounded from (2.2). Then, it is clear that (3.5) holds true. Otherwise, this finiteness condition can be checked a posteriori from a verification theorem, see Theorem 3.2.

2

The dynamic programming principle (DPP) for the deterministic control problem (3.4) takes the following formulation:

   V α n = ĝ(P X α n ) V α k = inf β∈A k (α) fk (P X β k , βk ) + V β k+1 , k = 0, . . . , n -1.
(3.6)

Proof. In the context of deterministic control problem, the proof of the DPP is standard and does not require any measurable selection arguments. For sake of completeness and since it is quite elementary, we give it. Denote by J k (α) the cost functional at time k, i.e.

J k (α) := n-1 j=k fk (P X α k , αk ) + ĝ(P X α n ), k = 0, . . . , n, so that V α k = inf β∈A k (α) J k (β)
, and by W α k the r.h.s. of (3.6). Then,

W α k = inf β∈A k (α) fk (P X β k , βk ) + inf γ∈A k+1 (β) J k+1 (γ) = inf β∈A k (α) inf γ∈A k+1 (β) fk (P X β k , βk ) + J k+1 (γ) = inf β∈A k (α) inf γ∈A k+1 (β) fk (P X γ k , γk ) + J k+1 (γ) = inf γ∈{A k+1 (β):β∈A k (α)} J k (γ),
where we used in the third equality the fact that

X β k = X γ k , β k = γ k for γ ∈ A k+1 (β)
. Finally, we notice that {A k+1 (β) : β ∈ A k (α)} = A k (α). Indeed, the inclusion ⊂ is clear while for the converse inclusion, it suffices to observe that any γ in A k (α) satisfies obviously γ ∈ A k+1 (γ). This proves the required equality:

W α k = V α k . 2
Let us now show how one can simplify the DPP by exploiting the flow property of (P X α k ) k for any admissible control α in feedback form ∈ A. Actually, we can derive the evolution of the controlled deterministic process (P X α k ) k . Lemma 3.2 For any admissible control in closed-loop form α ∈ A, we have

P X α k+1 = Φ k+1 P X α k , αk , k ∈ N, P X α 0 = P ξ (3.7)
where Φ k+1 is the measurable function defined from P 2 (E) × A E into P 2 (E) by:

Φ k+1 (µ, α)(dx ′ ) = E µ(dx)P k+1 (x, µ, α(x), α ⋆ µ, dx ′ ). (3.8)
Proof. Fix α ∈ A. Recall from the definition of the transition probability P k+1 (x, µ, a, λ, dx ′ ) associated to (2.1) that

P X α k+1 ∈ dx ′ F k = P k+1 (X α k , P X α k , α k , P α k , dx ′ ), k ∈ N. (3.9)
For any bounded measurable function ϕ on E, we have by the law of iterated conditional expectation and (3.9):

E ϕ(X α k+1 ) = E E ϕ(X α k+1 ) F k = E E ϕ(x ′ )P k+1 (X α k , P X α k , α k , P α k , dx ′ ) = E E×E ϕ(x ′ )P k+1 (x, P X α k , αk (x), αk ⋆ P X α k , dx ′ )P X α k (dx)
where we used in the last equality the fact that α k = αk (X ) k , the calculation of the value processes V α k can be reduced to the recursive computation of deterministic functions (called value functions) on P(E). ), k = 0, . . . , n, where (v k ) k is the sequence of value functions defined recursively on P 2 (E) by:

   v n (µ) = ĝ(µ) v k (µ) = inf α∈A E fk (µ, α) + v k+1 Φ k+1 (µ, α) (3.10
)

for k = 0, . . . , n -1, µ ∈ P 2 (E).
Proof. First observe that for any

β ∈ A k (α), X β k = X α k , k = 0, . . . , n.
Let us prove the result by backward induction. For k = n, the result clearly holds since

V α n = ĝ(P X α n ). Suppose now that at time k + 1, V α k+1 = v k+1 (P X α k+1
) for some deterministic function v k+1 and any α ∈ A. Then, from the DPP (3.6) and Lemma 3.2, we get

V α k = inf β∈A k (α) fk (P X α k , βk ) + v k+1 (P X β k+1 ) = inf β∈A k (α) w k (P X α k , βk ) (3.11)
where

w k (µ, α) := fk (µ, α) + v k+1 Φ k+1 µ, α .
Now, for any β ∈ A k (α), and since βk is valued in A E , we clearly have:

w k (µ, β k ) ≥ inf α∈A E w k (µ, α
), and so inf β∈A k (α) w k (µ, βk ) ≥ inf α∈A E w k (µ, α). Conversely, for any α ∈ A E , the control β defined by β j = α j , j ≤ k -1, and βj = α for j ≥ k, lies in A k (α), so: w k (µ, α) ≥ inf β∈A k (α) w k (µ, βk ), and thus inf β∈A k (α) w k (µ, βk ) = inf α∈A E w k (µ, α). We conclude from (3.11) that:

V α k = v k (P X α k ) with v k (µ) = inf α∈A E w k (µ,
f k (X α k , P X α k , α k ) = fk (X α k , E[X α k ], α k ), k = 0, . . . , n -1, g(X α n , P X α n ) = ḡ(X α n , E[X α n ]
), which arise for example in mean-variance problem (see Section 4). It is claimed in [START_REF] Björk | A general theory of Markovian time inconsistent stochastic control problems[END_REF] and [START_REF] Yong | A linear-quadratic optimal control problem for mean-field stochastic differential equations[END_REF] that Bellman optimality principle does not hold, and therefore the problem is time-inconsistent. This is true when one takes into account only the state process X α (that is its realization), since it is not Markovian, but as shown in this section, dynamic programming principle holds whenever we consider the marginal distribution as state variable. This gives more information and the price to paid is the infinite-dimensional feature of the marginal distribution state variable.

2

We complete the above Bellman's optimality principle with a verification theorem, which gives a sufficient condition for finding an optimal control. Theorem 3.2 (Verification theorem) (i) Suppose we can find a sequence of real-valued functions w k , k = 0, . . . , n, defined on P 2 (E) and satisfying the dynamic programming relation:

   w n (µ) = ĝ(µ) w k (µ) = inf α∈A E fk (µ, α) + w k+1 Φ k+1 (µ, α) (3.12)
for k = 0, . . . , n -1, µ ∈ P 2 (E). Then V α k = w k (P X α k

), for all k = 0, . . . , n, α ∈ A, and thus w k = v k . (ii) Moreover, suppose that at any time k and µ ∈ P(E), the infimum in (3.12) for w k (µ) is attained, by some α * k (., µ) in A E . Then, by defining by induction the control α * in feedback form by α

* k = α * k (X α * k , P X α * k
), k = 0, . . . , n -1, we have

V 0 = J(α * ),
which means that α * ∈ A is an optimal control.

Proof. (i) Fix some α ∈ A, and arbitrary β ∈ A associated to a feedback sequence ( βk ) k in A E . Then, from the dynamic programming relation (3.12) for w k , and recalling the evolution (3.7) of the controlled marginal distribution P X β k

, we have

w k (P X β k ) ≤ fk (P X β k , βk ) + v k+1 (P X β k+1
), k = 0, . . . , n -1.

By induction and since w n = ĝ, this gives

w k (P X β k ) ≤ n-1 j=k fj (P X β j , βj ) + ĝ(P X β n
).

By noting that P

X α k = P X β k
, when β ∈ A k (α), and since β is arbitrary, this proves that

w k (P X α k ) ≤ V α k .
In particular, V α k > -∞, i.e. relation (3.5) holds, and then by Theorem 3.1, V α k is characterized by the sequence of value functions (v k ) k defined by the DP (3.10). This DP obviously defines by backward induction a unique sequence of functions on P 2 (E), hence w k = v k , k = 0, . . . , n, and therefore V α k = w k (P X α k

). (ii) By definition of α * k which attains the infimum in (3.12), we have

w k P X α * k = fk (P X α * k , α * k (., P X α * k )) + w k+1 P X α * k+1
, k = 0, . . . , n -1.

By induction this implies that

V 0 = w 0 (P ξ ) = n-1 k=0 fk P X α * k , α * k (., P X α * k ) + ĝ(P X α * n ) = J(α * ),
which shows that α * is an optimal control. 2

The above verification theorem, which consists in solving the dynamic programming relation (3.12), is useful to check a posteriori the finiteness condition (3.5), and can be applied in practice fo find explicit solutions to some McKean-Vlasov control problems, as investigated in the next section.

Applications

Special cases

We consider some particular cases, and provide the special forms of the DPP.

No mean-field interaction

We first consider the standard control case where there is no mean-field interaction in the dynamics of the state process, i.e. F k+1 (x, a, ε k+1 ), hence P k+1 (x, a, dx ′ ) do not depend on µ, λ, as well as in the cost functions f k (x, a) and g(x). For simplicity, we assume that A is a bounded set, which ensures the finiteness condition (3.5). In this case, we can see that the value functions v k are in the form

v k (µ) = E ṽk (x)µ(dx), k = 0, . . . , n, (4.1)
where the functions ṽk defined on E satisfy the classical dynamic programming principle:

ṽn (x) = g(x) ṽk (x) = inf a∈A f k (x, a) + E ṽk+1 (X α k+1 ) X α k = x, α k = a , (4.2)
for k = 0, . . . , n -1. Let us check this result by backward induction. This holds true for k = n since v n (µ) = ĝ(µ) = E g(x)µ(dx). Suppose that (4.1) holds true at time k + 1. Then, from the DPP (3.10), (3.8) and Fubini's theorem, we have

v k (µ) = inf α∈A E E f k (x, α(x))µ(dx) + E ṽk+1 (x ′ )Φ k+1 (µ, α)(dx ′ ) = inf α∈A E E f k (x, α(x)) + E ṽk+1 (x ′ )P k+1 (x, α(x), dx ′ ) µ(dx) = inf α∈A E E wk (x, α(x))µ(dx)
where we set wk (x, a) = f k (x, a) + E ṽk+1 (x ′ )P k+1 (x, a, dx ′ ). Now, we observe that inf

α∈A E E wk (x, α(x))µ(dx) = E inf a∈A wk (x, a)µ(dx). ( 4

First order interactions

We consider the case of first order interactions, i.e. the dependence of the model coefficients upon the probability measures is linear in the sense that for any (x, µ, a)

∈ E × P 2 (E) × A, α ∈ A E , P k+1 (x, µ, a, α ⋆ µ, dx ′ ) = E Pk+1 (x, y, a, α(y), dx ′ )µ(dy), f k (x, µ, a, α ⋆ µ) = E fk (x, y, a, α(y))µ(dy), g(x, µ) = E g(x, y)µ(dy),
for some transition probability kernels Pk+1 from E×E×A×A into E, measurable functions fk defined on E × E × A × A, k = 0, . . . , n -1, and g defined on E × E. In this case, the value functions v k are in the reduced form

v k (µ) = E 2 n-k+1 ṽk (x 2 n-k+1 )µ(dx 2 n-k+1 ), k = 0, . . . , n,
where we denote by x p the p-tuple (x 1 , . . . , x p ) ∈ E p , by µ(dx p ) the product measure µ(dx 1 ) ⊗ . . . ⊗ µ(dx p ), and the functions ṽk are defined recursively on E 2 n-k+1 by

         ṽn (x, y) = g(x, y) ṽk (x 2 n-k , y 2 n-k ) = inf α∈A E fk (x 1 , y 1 , α(x 1 ), α(y 1 )) + E 2 n-k ṽk+1 (x ′ 2 n-k ) Pk+1 (x 2 n-k , y 2 n-k , α(x 2 n-k ), α(y 2 n-k ), dx ′ 2 n-k ) ,
where we set

Pk+1 (x p , y p , α(x p ), α(y p ), dx ′ p ) = Pk+1 (x 1 , y 1 , α(x 1 ), α(y 1 ), dx ′ 1 ) ⊗ . . . ⊗ Pk+1 (x p , y p , α(x p ), α(y p ), dx ′ p ).
This result is easily checked by induction from the DPP (3.10), and it is left to the reader.

Linear-quadratic McKean-Vlasov control problem

We consider a general multivariate linear McKean-Vlasov dynamics in

E = R d with control valued in A = R m : X α k+1 = B k X α k + Bk E[X α k ] + C k α k + Ck E[α k ] (4.4) + D k X α k + Dk E[X α k ] + H k α k + Hk E[α k ])ε k+1 , k = 0, . . . , n -1,
starting from X α 0 = ξ, where B k , Bk , D k , Dk are constant matrices in R d×d , C k , Ck , H k , Hk are constant matrices in R d×m , and (ε k ) is a sequence of i.i.d. random variables with distribution N (0, 1), independent of ξ. The quadratic cost functional to be minimized is given by

J(α) = E n-1 k=0 (X α k ) ⊺ Q k X α k + E[X α k ] ⊺ Qk E[X α k ] + L ⊺ k X α k + L⊺ k E[X α k ] + α ⊺ k R k α k + E[α k ] ⊺ Rk E[α k ] + X α n ⊺ QX α n + E[X α n ] ⊺ QE[X α n ] + L ⊺ X α n + L⊺ E[X α k ] , (4.5)
for some constants matrices

Q k , Qk , Q, Q, in R d×d , R k , Rk in R m×m , and vectors L k , Lk , L, L ∈ R d , k = 0, . . . , n -1.
Here x ⊺ denotes the transpose of a matrix/vector x. Since the cost functions are real-valued, we may assume w.l.o.g. that all these matrices Q k , Qk , Q, Q, R k and Rk are symmetric. This model is in the form (2.1) and associated to a transition probability satisfying:

P k+1 (x, µ, a, λ, dx ′ ) ; N M k (x, µ, a, λ); Σ k (x, µ, a, λ)Σ k (x, µ, a, λ) ⊺ (4.6) M k (x, µ, a, λ) = B k x + Bk μ + C k a + Ck λ Σ k (x, µ, a, λ) = D k x + Dk μ + H k a + Hk λ
where we set for any

µ ∈ P 2 (R d ) (resp. P 2 (R m )) symmetric matrix Λ ∈ R d×d (resp. in R m×m ): μ := xµ(dx), μ2 (Λ) := x ⊺ Λxµ(dx), Var(µ)(Λ) := μ2 (Λ) -μ⊺ Λμ,
and in the form (2.3), hence (3.2) for feedback controls, with

fk (µ, α) = Var(µ)(Q k ) + μ⊺ (Q k + Qk )μ + (L k + Lk ) ⊺ μ + Var(α ⋆ µ)(R k ) + α ⋆ µ ⊺ (R k + Rk )α ⋆ µ ĝ(µ) = Var(µ)(Q) + μ⊺ (Q + Q)μ + (L + L) ⊺ μ.
We look for candidate w k , k = 0, . . . , n, of values functions satisfying the dynamic programming principle (3.10), in the quadratic form:

w k (µ) = Var(µ)(Λ k ) + μ⊺ Γ k μ + ρ ⊺ k μ + χ k , (4.7)
for some constant symmetric matrices Λ k and Γ k in R d×d , vector ρ k ∈ R d and real χ k to be determined below. We proceed by backward induction. For k = n, we see that

w k = ĝ (= v k ) iff Λ n = Q, Γ n = Q + Q, ρ n = L + L, χ n = 0. (4.8)
Now, suppose that the form (4.7) holds true at time k + 1, and observe from (3.8) and (4.6) that for any µ ∈ P 2 (R d ), α ∈ A E , Λ ∈ R d×d , we have by Fubini's theorem:

Φ k+1 (µ, α) = R d E Y (x, µ, α) µ(dx) Φ k+1 (µ, α) 2 (Λ) = R d E Y (x, µ, α) ⊺ ΛY (x, µ, α) µ(dx),
where Y (x, µ, α)

; N M k (x, µ, α(x), α ⋆ µ); Σ k (x, µ, α(x), α ⋆ µ)Σ k (x, µ, α(x), α ⋆ µ) ⊺ . Therefore, Φ k+1 (µ, α) = (B k + Bk )μ + (C k + Ck )α ⋆ µ,
and after some tedious but straightforward calculation:

Var(Φ k+1 (µ, α))(Λ) = Φ k+1 (µ, α) 2 (Λ) -Φ k+1 (µ, α) ⊺ ΛΦ k+1 (µ, α) = R d Σ k (x, µ, α(x), α ⋆ µ) ⊺ ΛΣ(x, µ, α(x), α ⋆ µ) + M k (x, µ, α(x), α ⋆ µ) ⊺ ΛM (x, µ, α(x), α ⋆ µ) µ(dx) -(B k + Bk )μ + (C k + Ck )α ⋆ µ ⊺ Λ (B k + Bk )μ + (C k + Ck )α ⋆ µ = Var(µ)(B ⊺ k ΛB k + D ⊺ k ΛD k ) + μ⊺ (D k + Dk ) ⊺ Λ(D k + Dk )μ + Var(α * µ)(H ⊺ k ΛH k + C ⊺ k ΛC k ) + α ⋆ µ ⊺ (H k + Hk ) ⊺ Λ(H k + Hk )α ⋆ µ + 2 R d (x -μ) ⊺ (D ⊺ k ΛH k + B ⊺ k ΛC k )α(x)µ(dx) + 2μ ⊺ (D k + Dk ) ⊺ Λ(H k + Hk )α ⋆ µ.
Then, w k satisfies the DPP (3.10) iff

w k (µ) = inf α∈A E fk (µ, α) + Var(Φ k+1 (µ, α))(Λ k+1 ) + Φ k+1 (µ, α) ⊺ Γ k+1 Φ k+1 (µ, α) (4.9) = Var(µ)(Q k + B ⊺ k Λ k+1 B k + D ⊺ k Λ k+1 D k ) + inf α∈A E G µ k+1 (α) + μ⊺ Q k + Qk + (D k + Dk ) ⊺ Λ k+1 (D k + Dk ) + (B k + Bk ) ⊺ Γ k+1 (B k + Bk ) μ + L k + Lk + (B k + Bk ) ⊺ ρ k+1 ⊺ μ + χ k+1 , (4.10)
where we define the function G µ k+1 : L 2 (µ; A) → R by

G µ k+1 (α) = Var(α ⋆ µ)(V k ) + α ⋆ µ ⊺ W k α ⋆ µ + 2 R d (x -μ) ⊺ S k α(x)µ(dx) + 2μ ⊺ T k α ⋆ µ + ρ ⊺ k+1 (C k + Ck )α ⋆ µ, (4.11)
and we set

V k = V k (Λ k+1 ), W k = W k (Λ k+1 , Γ k+1 ), S k = S k (Λ k+1 ), T k = T k (Λ k+1 , Γ k+1 ), with          V k (Λ k+1 ) = R k + H ⊺ k Λ k+1 H k + C ⊺ k Λ k+1 C k ; W k (Λ k+1 , Γ k+1 ) = R k + Rk + (C k + Ck ) ⊺ Γ k+1 (C k + Ck ) + (H k + Hk ) ⊺ Λ k+1 (H k + Hk ) S k (Λ k+1 ) = D ⊺ k Λ k+1 H k + B ⊺ k Λ k+1 C k ; T k (Λ k+1 , Γ k+1 ) = (D k + Dk ) ⊺ Λ k+1 (H k + Hk ) + (B k + Bk )) ⊺ Γ k+1 (C k + Ck ).
(4.12) Here, L 2 (µ; A) ⊃ A E is the Hilbert space of measurable functions on E = R d valued in A = R m and square integrable w.r.t. µ ∈ P 2 (E).

We now search for the infimum of the function G µ k+1 , and shall make the following assumptions on the symmetric matrices of the quadratic cost functional and on the coefficients of the state dynamics:

(c0) Q ≥ 0, Q + Q ≥ 0, Q k ≥ 0, Q k + Qk ≥ 0, R k ≥ 0, R k + Rk ≥ 0, k = 0, . . . , n -1,
and for all k = 0, . . . , n -1 (with the convention that

Q n = Q, Qn = Q) (c1) R k > 0, or [rank(C k ) = d, Q k+1 > 0], or [rank(H k ) = d, Q k+1 > 0], (c2) R k + Rk > 0, or [rank(C k + Ck ) = d, Q k+1 + Qk+1 > 0], or [rank(H k + Hk ) = d, Q k+1 > 0]. Conditions (c0)-(c1)-(c2
) is slightly weaker than the condition in [START_REF] Elliott | Discrete time mean-field stochastic linear-quadratic optimal control problems[END_REF] (see their Theorem 3.1), where the condition (c0) is strengthened to R k > 0 and R k + Rk > 0 for all k = 0, . . . , n -1, for ensuring the existence of an optimal control. We relax this positivity condition with the conditions (c1)-(c2) in order to include the case of mean-variance problem (see the example at the end of this section). Actually, as we shall see in Remark 4.1, these conditions will guarantee that for Λ k , Γ k to be determined below, the function G µ k+1 is convex and coercive on L 2 (µ; A) for any k = 0, . . . , n -1. For the moment, we derive after some straightforward calculation the Gateaux derivative of G µ k+1 at α in the direction β ∈ L 2 (µ; A), which is given by:

DG µ k+1 (α; β) := lim ε→0 G µ k+1 (α + εβ) -G µ k+1 (α) ε = R d g k+1 (x, α)β(x)µ(dx) with g k+1 (x, α) = 2α(x) ⊺ V k + 2α ⋆ µ ⊺ W k -V k + 2(x -µ) ⊺ S k + 2μ ⊺ T k + ρ ⊺ k+1 (C k + Ck ).
We shall check later in Remark 4.1 that V k and W k are positive symmetric matrices, hence invertible. We thus see that DG µ k+1 (α; .) vanishes for α = α * k (., µ) s.t. g k+1 (x, α * k (., µ)) = 0 for all x ∈ R d , which gives:

α * k (x, µ) = -V -1 k S ⊺ k (x -μ) -W -1 k T ⊺ k μ - 1 2 W -1 k (C k + Ck ) ⊺ ρ k+1 (4.13)
and then after some straightforward caculation:

G µ k+1 (α * k (., µ)) = -Var(µ) S k V -1 k S ⊺ k -μ⊺ T k W -1 k T ⊺ k μ -μ⊺ T k W -1 k (C k + Ck ) ⊺ ρ k+1 - 1 4 ρ ⊺ k+1 (C k + Ck )W -1 k (C k + Ck ) ⊺ ρ k+1 .
Assuming for the moment that α * k (., µ) attains the infimum of G µ k+1 (this is a consequence of the convexity and coercivity of G µ k+1 shown in Remark 4.1), and plugging the above expression in (4.9), we see that w k is like the function µ → G µ k+1 (α * k (., µ)), a linear combination of terms in Var(µ)(.), μ⊺ (.)μ, and by identification with the form (4.7), we obtain an inductive relation for Λ

k , Γ k , ρ k , χ k :              Λ k = Q k + B ⊺ k Λ k+1 B k + D ⊺ k Λ k+1 D k -S k (Λ k+1 )V -1 k (Λ k+1 )S ⊺ k (Λ k+1 ) Γ k = (Q k + Qk ) + (B k + Bk ) ⊺ Γ k+1 (B k + Bk ) + (D k + Dk ) ⊺ Λ k+1 (D k + Dk ) -T k (Λ k+1 , Γ k+1 )W -1 k (Λ k+1 , Γ k+1 )T ⊺ k (Λ k+1 , Γ k+1 ) ρ k = L k + Lk + (B k + Bk ) -(C k + Ck )W -1 k (Λ k+1 , Γ k+1 )T ⊺ k (Λ k+1 , Γ k+1 ) ρ k+1 χ k = χ k+1 -1 4 ρ ⊺ k+1 (C k + Ck )W -1 k (Λ k+1 , Γ k+1 )(C k + Ck ) ⊺ ρ k+1 . ( 4
.14) for all k = 0, . . . , n-1, starting from the terminal condition (4.8). The relations for (Λ k , Γ k ) in (4.14) are two algebraic Riccati difference equations, while the equations for ρ k and χ k are linear equations once (Λ k , Γ k ) are determined. This system (4.14) is the same as the one obtained in [START_REF] Elliott | Discrete time mean-field stochastic linear-quadratic optimal control problems[END_REF]. In the particular mean-variance problem considered at the end of this section, we can obtain explicit closed-form expressions for the solutions (Λ k , Γ k , ρ k , χ k ) to this Riccati system. However, in general, there are no closed-form formulae, and these quantities are simply computed by induction.

In the following remark, we check the issues that have left open up to now. Remark 4.1 Let conditions (c0)-(c1)-(c2) hold. We prove by backward induction that for all k = 1, . . . , n, the matrices

V k-1 = V k-1 (Λ k ), W k-1 = W k-1 (Λ k , Γ k )
are symmetric positive, hence invertible, with (Λ k , Γ k ) given by (4.14), together with the nonnegativity of the symmetric matrices Λ k , Γ k , which will immediately gives the convexity and coercivity of the function G µ k in (4.11) for µ ∈ P 2 (R d ). At time k = n, we have Λ n = Q ≥ 0, Γ n = Q + Q ≥ 0, and thus from (4.12), the d × d matrices

V n-1 = V n-1 (Λ n ), W n-1 = W n-1 (Λ n , Γ n ) are symmetric positive under (c0)-(c1)- ( c2
): indeed, for example if R n-1 = 0, then the rank condition on C n-1 or H n-1 together with the positivity of Λ n = Q in (c1) will ensure that V n-1 is positive. Now, suppose that the assertion is true at time k + 1, i.e. V k , W k are symmetric positive, and Λ k+1 , Γ k+1 are symmetric nonnegative. Then, it is clear from (4.14) that Λ k and Γ k are symmetric, and noting that they can be rewritten from the expression of V k , W k , S k , T k in (4.12) as

                   Λ k = Q k + S k V -1 k R k S k V -1 k ⊺ + B k -C k (S k V -1 k ) ⊺ ⊺ Λ k+1 B k -C k (S k V -1 k ) ⊺ + D k -H k (S k V -1 k ) ⊺ ⊺ Λ k+1 D k -H k (S k V -1 k ) ⊺ Γ k = Q k + Qk + T k W -1 k (R k + Rk ) T k W -1 k ⊺ + B k + Bk -(C k + Ck )(T k W -1 k ) ⊺ ⊺ Γ k+1 B k + Bk -(C k + Ck )(T k W -1 k ) ⊺ + D k + Dk -(H k + Hk )(T k W -1 k ) ⊺ ⊺ Γ k+1 D k + Dk -(H k + Hk )(T k W -1 k ) ⊺ ,
it is also clear that they are nonnegative under (c0). Finally from the expression (4.12) at time k -1, we see that V k-1 = V k-1 (Λ k ) and W k-1 = W k-1 (Λ k , Γ k ) are symmetric positive under (c0)-(c1)-(c2), which shows the required assertion. 2

In view of the above derivation and Remark 4.1, it follows that the functions w k , k = 0, . . . , n, given in the quadratic form (4.7) with (Λ k , Γ k , ρ k , χ k ) as in (4.14), satisfy by construction the DPP (3.10), and by the verification theorem, this implies that the value functions are given by v k = w k , while the optimal control is given in feedback form from (4.13) by:

α * k = αk (X * k , P X * k ) = -V -1 k S ⊺ k X * k -E[X * k ] -W -1 k T ⊺ k E[X * k ], (4.15)
where X * k = X α * k is the optimal wealth process with the feedback control α * . We retrieve the expression obtained in [START_REF] Elliott | Discrete time mean-field stochastic linear-quadratic optimal control problems[END_REF] (see e.g. their Theorem 3.1). We can push further our calculations to get an explicit form of the optimal control expressed only in terms of the state process (and not on its mean). Indeed, from the linear dynamics (4.4), we have

E[X * k+1 ] = (B k + Bk )E[X * k ] + (C k + Ck )E[α * k ] = (B k + Bk )E[X * k ] -(C k + Ck ) W ⊺ k -1 T ⊺ k E[X * k ] = N k E[X * k ],
with N k = B k + Bk -(C k + Ck )W -1 k T k , for k = 0, . . . , n -1, and so by induction:

E[X * k ] = N k-1 . . . N 0 E[ξ].
Plugging into (4.15), this gives the explicit form of the optimal control as We observe that the optimal control at any time k does not only depend on the current state X * k but also on its the initial state ξ (via its mean).

α * k = -V -1 k S ⊺ k X * k + V -1 k S ⊺ k -W -1 k T ⊺ k N k-
where X * k = X α * k is the optimal wealth process with the feedback control α * . It is then explicitly written from (4.16) by

α * k = - b σ 2 + b 2 ∆ X * k -x 0 - 1 γ 1 + b 2 σ 2 ∆ n . (4.19)
We then observe that the optimal control at any time k does not only depend on the current wealth X * k but also on the initial wealth x 0 . This expression (4.19) of the optimal control is the discrete time analog of the continuous time optimal control obtained in [START_REF] Li | Continuous-time mean-variance portfolio selection: a stochastic LQ framework[END_REF] or [START_REF] Andersson | A maximum principle for SDEs of mean-field type[END_REF]. Actually, if we view (4.17) as a time discretization (with a time step ∆ = T /n) of a continuous time Black-Scholes model for the stock price over [0, T ], with a controlled wealth dynamics dX α t = α t (bdt + σdW t ), X α 0 = x 0 , then by sending n to infinity (hence ∆ to zero) into (4.19), we retrieve the closed-form expression of the optimal control in [START_REF] Li | Continuous-time mean-variance portfolio selection: a stochastic LQ framework[END_REF] or [START_REF] Andersson | A maximum principle for SDEs of mean-field type[END_REF]:

α * t = - b σ 2 X α * t -x 0 - 1 γ exp b 2 σ 2 T .

Lemma 3 . 1 (

 31 Dynamic Programming Principle) Under (3.5), we have

Theorem 3 . 1 (

 31 Dynamic programming and value functions) Under (3.5), we have for any α ∈ A, V α k = v k (P X α k

  a)µ(dx) + ε, which shows (4.3) since ε is arbitrary. Therefore, we have v k (µ) = E ṽk (x)µ(dx) with ṽk (x) = inf a∈A wk (x, a) = inf a∈A f k (x, a) + E ṽk+1 (x ′ )P k+1 (x, a, dx ′ ) , which is the relation (4.2) at time k from the definition of the transition probability P k+1 .

  1 . . . N 0 E[ξ], k = 0, . . . , n -1. (4.[START_REF] Yong | A linear-quadratic optimal control problem for mean-field stochastic differential equations[END_REF]

  Relation (3.7) is the Fokker-Planck equation in discrete time for the marginal distribution of the controlled process (X α k ). In absence of control and McKean-Vlasov type dependence, i.e. P k+1 (x, dx ′ ) does not depend on (µ, a, λ), we retrieve the standard Fokker-Planck equation with a linear function Φ k+1 (µ) = µP k+1 . In our McKean-Vlasov control context, the function Φ k+1 (µ, α) is nonlinear in µ.

			α k ) is in closed loop form, the
	definition of P X α k relation for P X α k .	, and noting that P α k = αk ⋆ P X α k	. This shows the required inductive 2
	Remark 3.2

2

By exploiting the inductive relation (3.7) on the controlled process (P X α k

  α), i.e. given by(3.10). 2 Remark 3.3 Problem (2.4) includes the case where the cost functional in (2.3) is a nonlinear function of the expected value of the state process, i.e. the running cost functions and the terminal gain function are in the form:

  .3) Indeed, since for any α ∈ A E , the value α(x) is valued in A for any x ∈ E, it is clear that the inequality ≥ in (4.

3) holds true. Conversely, for any ε > 0, and x ∈ E, one can find αε (x) in A such that wk (x, αε (x)) ≤ inf a∈A wk (x, a) + ε.

By a measurable selection theorem, the map x → αε (x) can be chosen measurable, and since A is bounded, the function αε lies in A E . It follows that inf α∈A E E wk (x, α(x))µ(dx) ≤ E wk (x, αε (x))µ(dx) ≤

Example: Mean-variance portfolio selection

The mean-variance discrete-time problem consists in minimizing the cost functional:

for some γ > 0, with a dynamics for the wealth process (X α k ) valued in E = R controlled by the amount α k valued in A = R invested in the stock at time k (we assume zero interest rate):

Conditions (c0)-(c1)-(c2) are clearly satisfied, and the Riccati system (4.14

, together with the terminal condition Λ n = γ 2 , Γ n = 0, ρ n = -1, χ n = 0. This leads by induction to the explicit form for (Λ k , Γ k , ρ k , χ k ):

The value functions are then explicitly given by

for all k = 0, . . . , n, µ ∈ P 2 (R). Moreover, the optimal control is given in feedback form from (4.15) by:

,