Pierre Carpentier

Jean-Philippe Chancelier

Michel De Lara

Thomas Martin

Tristan Rigaut

Time Block Decomposition of Multistage Stochastic Optimization Problems

Keywords: multistage stochastic optimization, dynamic programming, time scales, time block decomposition, decision-hazard-decision

Multistage stochastic optimization problems are, by essence, complex as their solutions are functions of both stages and uncertainties. Their large scale nature makes decomposition methods appealing, like dynamic programming which is a sequential decomposition using a state variable defined at all stages. By contrast, in this paper we introduce the notion of state reduction by time blocks, that is, at stages that are not necessarily all the original stages. Then, we prove a dynamic programming equation with value functions that are functions of a state only at some stages. This equation crosses over time blocks, but involves a dynamic optimization inside each block. We illustrate our contribution by showing its potential in three applications in multistage stochastic optimization: mixing dynamic programming and stochastic programming, two-time-scale optimization problems, decision-hazard-decision optimization problems.

Introduction

Solutions of multistage stochastic optimization problems are functions of both time and uncertainties. This makes such problems complex. However, their structure makes decomposition methods appealing to solve them [START_REF] Ruszczyński | Decomposition methods[END_REF]. One of the most common approaches are time decomposition (state-based resolution methods), like stochastic dynamic programming, in stochastic optimal control, and scenario decomposition, like progressive hedging, in stochastic programming. On the one hand, stochastic programming deals with an underlying random process taking a finite number of values, called scenarios [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory. The society for industrial and applied mathematics and the mathematical programming society[END_REF]. Solutions are indexed by a scenario tree, the size of which increases exponentially with the number of stages (hence generally a few stages in practice). However, to overcome this obstacle, stochastic programming takes advantage of scenario decomposition methods (progressive hedging [START_REF] Rockafellar | Scenarios and policy aggregation in optimization under uncertainty[END_REF]). On the other hand, stochastic control deals with a state model driven by a white noise, that is, the noise is made of a sequence of independent random variables. Under such assumptions, stochastic dynamic programming is able to handle many stages, as it offers reduction of the search for a solution among state feedbacks (instead of functions of the past noise) [START_REF] Bellman | Dynamic Programming[END_REF][START_REF] Carpentier | Stochastic Multi-Stage Optimization[END_REF].

In a word, dynamic programming is good at handling multiple stages -but at the price of assuming that noises are stagewise independent -whereas stochastic programming does not require such assumption, but can only handle a few stages. Could we take advantage of both methods? Is there a way to apply stochastic dynamic programming at a slow time scale -a scale at which noises could be considered statistically independent -crossing over fast time scale optimization problems where independence would not hold? This question is one of the motivations of this paper, and we indeed provide a method to decompose multistage stochastic optimization problems by time blocks. This decomposition method and the main result are, mathematically speaking, quite natural, but the main difficulty is notational. Indeed, the rigorous formulation of multistage stochastic optimization problems on so-called history spaces requires rather heavy notation.

Although specialists in stochastic optimal control and dynamic programming will find the results as natural and non surprising, or as part of folklore, the fact is that we have not been able to find references that treat the case of a state defined only at a subset of stages. This is why we set out to write this paper, without any real theoretical ambition, but with the objective that this result be established and can be used for applications using several forms of decomposition 1 . This is also why we present three (theoretical) applications in multistage stochastic optimization: mixing dynamic programming and stochastic programming, twotime-scale optimization problems, decision-hazard-decision optimization problems.

As there are several ways to tackle the difficulties of dealing with a large number of time steps, we compare our approach with other ones. In this paper, we propose an exact decomposition of a multistage stochastic optimization problem by time blocks using a state defined only at a subset of stages, to be distinguished from either time aggregation or approximate decomposition by timescales, which both yield approximate problems. We discuss both now.

Time aggregation consists in grouping the time steps, that is, in considering a partition of the time steps in time blocks and "aggregating" variables and constraints in each time block. To our knowledge, this approach was initiated in [START_REF] Birge | Aggregation bounds in stochastic linear programming[END_REF] for stochastic linear programs. For such linear programs, it is indeed easily conceived that, by summing ("aggregating") linear constraints, one obtains lower bounds for minimization problems. This approach was generalized in the paper [START_REF] Wright | Primal-dual aggregation and disaggregation for stochastic linear programs[END_REF] which puts forward a measure-theoretic framework with coarser and finer filtrations, and uses linear duality. Then, this was extended in [START_REF] Kuhn | Aggregation and discretization in multistage stochastic programming[END_REF] for stochastic convex programs, using filtrations and convex duality. The main idea can be sketched as follows: the coarser filtration is used to reduce the measurability of the decision variables, whereas the finer filtration is used to enlarge the measurability of the dual variables associated with the constraints, so that the optimal value of the problem obtained by using these two filtrations is an upper bound of the true optimal value; exchanging the role of the filtrations leads to a lower bound. Thus, with time aggregation, one obtains simpler problems that are lower and upper bounds for the original minimization stochastic problems, hence are approximations.

In approximate decomposition by timescales, one identifies several timescales in the original multistage stochastic optimization problem and then sets up an optimization problem for each timescale. It is approximate in that the connexion between the problems formulated for each timescale and the whole multistage problem is not explicit.

Approximate decomposition by timescales can be done in the context of dynamic programming, with the value functions obtained for a given timescale entering the final cost of the problem at the finer timescale. This approach gives a cascade of easier to solve optimization problems, and again corresponds to approximate the original problem. An example of this approach can be found in [START_REF] Cheng | Co-optimizing battery storage for the frequency regulation and energy arbitrage using multi-scale dynamic programming[END_REF] where -for a problem involving both the control of the storage of a battery (5 minutes time steps) and the frequency regulation (2 seconds time steps) -is introduced a first hourly resource model whose resolution by dynamic programming leads to value functions used in a five minute storage model as final costs. The value functions, obtained by solving by dynamic programming this second model, are themselves used in a 2 seconds frequency model. Another possibility arises when the considered optimization problem displays a periodical behavior. In that case, a natural time block decomposition is given by the period of the system. In [START_REF] Shapiro | Periodical multistage stochastic programs[END_REF], by taking into account such a periodical pattern in the dynamic programming equations, one significantly reduces the computational effort to solve the problem using a fixed point approach. Finally, [START_REF] Porteiro | Towards multi-timescale energy provisioning using stochastic dual dynamic programming[END_REF] presents a preliminary work on extending the Stochastic Dual Dynamic Programming approach to two-time-scale problems, such as those encountered in energy systems involving both long-term hydro storages and short-term battery storages.

Approximate decomposition by timescales can also be done in the framework of stochastic programming. In [START_REF] Kaut | Multi-horizon stochastic programming[END_REF], the authors introduce a slow scenario tree, that is, a tree involving only the time stages of the slow time scale; but at each node of this slow scenario tree are attached fast time scale scenarios, which do not interfere with the other nodes of the slow scenario tree. The structure allows one to model and solve problems that need to combine strategic (long term) and operational (short term) uncertainty, without the explosion in the problem size that would follow from using a standard multistage model. The special situation where decisions are taken only at the slow time scale (whereas uncertainties occur at each time stage) is considered in [START_REF] Glanzer | Multiscale stochastic optimization: modeling aspects and scenario generation[END_REF]. The authors propose to build a scenario tree branching at the slow time stages, and designed using the theory of bridge processes between two consecutive nodes in order to represent the noise at the fast time scale.

The paper is organized as follows. In Sect. 2, we present stochastic dynamic programming with histories as a way to solve a stochastic optimal control problem formulated in discrete time. In Sect. 3, we revisit the notion of "state" by defining state reduction by time blocks 2.1 The Bertsekas-Shreve setting [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF] To obtain a stochastic dynamic programming with histories requires technical assumptions. Indeed, as Bertsekas and Shreve notice at the beginning of [1, §7.6]: "The dynamic programming algorithm is centered around infimization of functions, and this is intimately connected with projections of sets"; "Unfortunately, the projection of a Borel-measurable set need not be Borel-measurable. In Borel spaces, however, the projection of a Borel-measurable set is an analytic set". They devote [1, §7.6] to the definition and study of analytic sets, and in [1, §7.7] define universally measurable functions, as well as lower semianalytic functions.

We call Borel space (X, B X ) a Borel set X equipped with its Borel σ-field B X [1, Definition 7.7, p. 118]. By abuse of notation, we often speak of the Borel space X. There exist two other interesting σ-fields: the analytic σ-field A X [1, Definition 7.19, p. 171]; the universal σ-field U X [1, Definition 7.18, p. 167]. We have the inclusions

B X ⊂ A X ⊂ U X [1, p. 171].
For any Borel space X, subset X ⊂ X and numerical function ϕ : X → R, the function ϕ is said to be lower semianalytic [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Definition 7.21] if the subset X is analytic (X ∈ A X ) and if the subset x ∈ X ϕ(x) < c is analytic for all c ∈ R. We denote by L 0 + (X) the space of lower semianalytic nonnegative numerical functions over X.

For a Borel space X (resp. Y) equipped with the Borel σ-field B X (resp. B Y ), a mapping f : X → Y is said to be universally measurable [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Definition 7.20,p. 171

] (resp. Borel-measurable) if, for all B ∈ B Y , f -1 (B) ∈ U X (resp. f -1 (B) ∈ B X ).
Histories and history spaces. For each time t ∈ 0, T -1 , the control u t takes its values in a Borel space U t . For each time t ∈ 0, T , the uncertainty w t takes its values in a Borel space W t . For t ∈ 0, T , we define the history space H t as the product Borel space [1, Proposition 7.13, p. 119]

H t = W 0 × t s=1 (U s-1 × W s ) , (1)
with the particular case

H 0 = W 0 , H 0 = W 0 . A generic element h t = w 0 , (u s-1 , w s ) s∈ 1,t = (w 0 , u 0 , w 1 , u 1 , w 2 , . . ., u t-2 , w t-1 , u t-1 , w t ) ∈ H t is called a history at time t. For 1 ≤ r ≤ s ≤ t, we introduce the (r : s)-history subpart h r:s = (u r-1 , w r , . . . , u s-1 , w s ) ∈ H r:s = s τ =r (U τ -1 × W τ )
, so that we have h t = (h r-1 , h r:t ).

History feedbacks. For 0 ≤ r ≤ t ≤ T -1, we define a (r : t)-history feedback as a sequence γ s s∈ r,t of universally measurable mappings γ s : H s → U s . We call Γ r:t the set of (r : t)-history feedbacks. The history feedbacks reflect the following information structure. At the end of the time interval [t -1, t[, an uncertainty variable w t is revealed. Then, at the beginning of the time interval [t, t + 1[, a decision-maker chooses a control u t contingent on no more than the past, giving the chronology

w 0 u 0 w 1 u 1 • • • w t u t • • • w T -1 u T -1 w T . (2
ρ t-1:t : H t-1 → ∆(W t ) , ∀t ∈ 1, T . (3)
Thus, for any past history h t-1 ∈ H t-1 , we have that ρ t-1:t (h t-1 ) ∈ ∆(W t ), the space of probability measures over W t . It is common practice (see [1, Definition 7.12, p. 134]) to use the notation ρ t-1:t ( dw t |h t-1 ) to denote this probability distribution, element of ∆(W t ). So, the notation |h t is here to evoke a conditional distribution (of the next uncertainty knowing the past history), but it is not introduced as a conditional distribution, but simply as a way to express a parametric dependence (as explicitely said in [1, Definition 7.12, p. 134]). We could have indifferently written ρ t-1:t ( dw t , h t-1 ) or ρ t-1:t ( dw t ; h t-1 ). We define, for any feedback {γ s } s∈ t,T-1 ∈ Γ t:T-1 , a new sequence of Borel-measurable stochastic kernels ρ γ t:T : H t → ∆(H T ), that capture the transitions between histories when the dynamics h s+1 = h s , u s , w s+1 is driven by u s = γ s (h s ) for all s in t, T -1 (see Definition 14 in Appendix A for the detailed construction of ρ γ r:t ). Note that ρ γ t:T generates a probability distribution on the space H T of histories over the whole timespan 0, T .

Cost function.

The cost criterion to be minimized is a nonnegative2 and lower semianalytic numerical function j :

H T → [0, +∞] . (4)
Notice that (4) does not represent a cost at final time, but a cost function of the whole history h T = (w 0 , u 0 , w 1 , u 1 , . . . , w T -1 , u T -1 , w T ) ∈ H T . As h T contains all past controls and uncertainties, a function j : H T → [0, +∞] covers the most general case. For instance, the function j can have the special form of a sum of time block costs, like in Equation ( 16).

Stochastic dynamic programming equation with histories

Family of optimization problems. We consider the following family of optimization problems, indexed by t in 0, T -1 and parameterized by the history h t ∈ H t : for all t in 0, T -1 , we define the minimum value

V t (h t ) = inf γ t:T -1 ∈Γ t:T -1 H T j(h T )ρ γ t:T ( dh T | h t ) , ∀h t ∈ H t , (5a)
and we also define

V T (h T ) = j(h T ) , ∀h T ∈ H T . (5b)
The numerical function V t : H t → [0, +∞] is called the value function at time t.

Next, we show how the sequence {V t } t∈ 0,T of value functions can be used to solve, via dynamic programming, the optimization problem of interest, that is, the one starting at t = 0, whose value is (recall that h 0 = w 0 )

V 0 (w 0 ) = inf γ 0:T -1 ∈Γ 0:T -1 H T j(h T )ρ γ 0:T ( dh T | w 0 ) . (6)
Bellman operators and dynamic programming. We show that the value functions in (5) are Bellman functions, in that they are solution of a Bellman or dynamic programming equation.

Theorem 1

We suppose to be in the setting of §2.1. For t in 0, T -1 , we define the Bellman operator B t+1:t by, for all ϕ ∈ L 0 + (H t+1 ) and for all h t ∈ H t ,

B t+1:t ϕ (h t ) = inf ut∈Ut W t+1 ϕ(h t , u t , w t+1 )ρ t:t+1 (dw t+1 | h t ) . (7a)
Then, the Bellman operators are such that

B t+1:t : L 0 + (H t+1 ) → L 0 + (H t ) , (7b)
and the value functions V t defined in (5) are lower semianalytic and satisfy the Bellman equation, or (stochastic) dynamic programming equation,

V T = j , V t = B t+1:t V t+1 , for t ∈ 0, T -1 . ( 8
)
The proof is sketched in Appendix A. This theorem is inspired by [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Chap. 8], with the feature that the state x t is, in our case, the canonical history h t , with the canonical dynamics h t+1 = h t , u t , w t+1 . This quite general dynamic programming result is the basis of all future developments in this paper. Although the recalls and statements presented in this Sect. 2 are mostly straightforward consequences of results already established in the literature, the developments are indispensable to tackle time block decomposition in the forthcoming Sect. 3.

State reduction by time blocks and dynamic programming

In standard approaches to solve, by dynamic programming, a stochastic optimal control problem formulated in discrete time, either a state is given for all times (as in [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF], [START_REF] Birge | Aggregation bounds in stochastic linear programming[END_REF], [START_REF] Carpentier | Stochastic Multi-Stage Optimization[END_REF] and [START_REF] Carpentier | Time Block Decomposition of Multistage Stochastic Optimization Problems[END_REF]), or no state is given (as in [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF], [START_REF] Glanzer | Multiscale stochastic optimization: modeling aspects and scenario generation[END_REF]). In this paper, our approach is intermediate, in that a state is possibly obtained, but only at certain times. Thus, in this section, we consider the question of reducing the history using a compressed "state" variable. Differing with traditional practice, such a variable may not be available at any time t ∈ 0, T , but at some specified times 0 = t 0 < • • • < t N = T . We have recalled in Sect. 2 that the history h t is itself a state variable with associated canonical dynamics h t+1 = h t , u t , w t+1 . However, the size of this canonical state increases with time t, which is an unpleasant feature for dynamic programming -quickly leading to the well-known curse of dimensionalityhence the practical need to introduce a (ideally low dimensional) state space, at least at some specified times, as done in this paper. As already said in the introduction, the main difficulty in achieving this goal is notational. In §3.1, we start by introducing the notion of state reduction on a single time block. In §3.2, we move to state reduction on multiple consecutive time blocks and we give the corresponding dynamic programming equations across time blocks. In §3.3, we conclude on how we obtain reduced optimal feedbacks.

State reduction on a single time block

We first present the case where the reduction only occurs at two times denoted by r and t, and such that 0 ≤ r < t ≤ T . Definition 2 Let X r and X t be two Borel state spaces, θ r and θ t be two Borel-measurable reduction mappings

θ r : H r → X r , θ t : H t → X t , (9a)
and f r:t be a Borel-measurable dynamics

f r:t : X r × H r+1:t → X t . (9b)
The triplet (θ r , θ t , f r:t ) is called a state reduction across r, t if we have3

θ t (h r , h r+1:t ) = f r:t θ r (h r ), h r+1:t , ∀h t ∈ H t . (9c)
The state reduction (θ r , θ t , f r:t ) is said to be compatible with the sequence {ρ s-1:s } r+1≤s≤t of Borel-measurable stochastic kernels (3) if

• there exists a Borel-measurable reduced stochastic kernel ρ r:r+1 : X r → ∆(W r+1 ), such that the stochastic kernel ρ r:r+1 in (3) can be factored, for all h r ∈ H r , as ρ r:r+1 ( dw r+1 | h r ) = ρ r:r+1 dw r+1 θ r (h r ) ,

• for all s in r+2, t , there exists a Borel-measurable reduced stochastic kernel ρ s-1:s : X r × H r+1:s-1 → ∆(W s ), such that the stochastic kernel ρ s-1:s can be factored, for all h s-1 ∈ H s-1 , as ρ s-1:s dw s (h r , h r+1:s-1 ) = ρ s-1:s dw s θ r (h r ), h r+1:s-1 .

The above definition is similar to the sufficient statistics idea in stochastic control: the state variable, which summarizes the history, is sufficient for the controller to design its control policy ( [23, p. 19], [1, Definition 10.6], [START_REF] Subramanian | Approximate information state for partially observed systems[END_REF]). However, sufficient statistics in the stochastic control literature are defined at the original time stages. By contrast, Definition 2 -and the coming Definition 4 -consider a notion of sufficient statistics only for a subset of time stages.

According to Definition 2, the triplet (θ r , θ t , f r:t ) is a state reduction across r, t if and only if the diagram in the left part of Figure 1 is commutative; it is compatible if and only if the diagram in the middle part of Figure 1 is commutative.

H r × H r+1:t H t X r × H r+1:t X t θ r I d I d θ t f r:t H r × H r+1:s-1 ∆(W s ) X r × H r+1:s-1 θ r I d ρ s-1:s ρ s-1:s L 0 + (H t ) L 0 + (H r ) L 0 + (X t ) L 0 + (X r ) B t:r θ ⋆ t B t:r θ ⋆ r 1 Figure 1: Commutative diagrams in case of state reduction
The following proposition is the key ingredient to formulate dynamic programming equations with a reduced state.

Proposition 3 Under the assumptions of §2.1, we define the Bellman operator across t, r , B t:r :

L 0 + (H t ) → L 0 + (H r ) by B t:r = B r+1:r • • • • • B t:t-1 , (10)
where the one time step operators B s:s-1 , for s in r+1, t are defined in (7a).

Suppose that there exists a state reduction (θ r , θ t , f r:t ) that is compatible with the sequence {ρ s-1:s } s∈ r+1,t of stochastic kernels (3). Then, there exists a reduced Bellman operator across t, r , B t:r : L 0 + (X t ) → L 0 + (X r ), such that

B t:r φt • θ r = B t:r ( φt • θ t ) , ∀ φt ∈ L 0 + (X t ) . ( 11
)
For any φt ∈ L 0 + (X t ) and for any x r ∈ X r , we have that

B t:r φt = inf ur∈Ur W r+1 ρ r:r+1 ( dw r+1 | x r ) inf u r+1 ∈U r+1 W r+2 ρ r+1:r+2 ( dw r+2 | x r , u r , w r+1 ) • • • inf u t-1 ∈U t-1 Wt ρ t-1:t ( dw t | x r , u r , w r+1 , . . . , u t-2 , w t-1 ) φt f r:t (x r , u r , w r+1 , . . . , u t-1 , w t ) . (12)
The formula [START_REF] Kaut | Multi-horizon stochastic programming[END_REF] represents a nested sequence of infima of integrals (with respect to different stochastic kernels). The proof of Proposition 3 is given in Appendix A. Proposition 3 can be interpreted as follows. Denoting by θ t : L 0 + (X t ) → L 0 + (H t ) the operator defined by θ t ( φt ) = φt • θ t for any φt ∈ L 0 + (X t ), the relation [START_REF] Hernández | Discrete-Time Markov Control Processes: Basic Optimality Criteria[END_REF] rewrites as θ r • B t:r = B t:r • θ t , that is, Proposition 3 states that the diagram in the right part of Figure 1 is commutative.

State reduction on multiple consecutive time blocks and dynamic programming equations

Proposition 3 can easily be extended to the case of multiple consecutive time blocks

t i , t i+1 , with N ∈ N * , i ∈ 0, N -1 and 0 = t 0 < • • • < t N = T .
Definition 4 Let {X t i } i∈ 0,N be a family of Borel state spaces, {θ t i } i∈ 0,N be a family of Borel-measurable reduction mappings θ t i : H t i → X t i , and {f t i :t i+1 } i∈ 0,N -1 be a family of Borel-measurable dynamics

f t i :t i+1 : X t i × H t i +1:t i+1 → X t i+1 .
The family {X t i } i∈ 0,N , {θ t i } i∈ 0,N , {f t i :t i+1 } i∈ 0,N -1 is called a state reduction across the consecutive time blocks t i , t i+1 , i ∈ 0, N -1 if every triplet (θ t i , θ t i+1 , f t i :t i+1 ) is a state reduction across t i , t i+1 , for i in 0, N -1 .

The state reduction across the consecutive time blocks t i , t i+1 is said to be compatible with the family {ρ s-1:s } s∈ 1,T of stochastic kernels given in (3) if every triplet (θ t i , θ t i+1 , f t i :t i+1 ) is compatible with the family {ρ s-1:s } s∈ t i +1,t i+1 , for i in 0, N -1 .

Remark 5 (Composed state dynamics as a reduction mapping)

There is a practical case where state reductions can readily be obtained, namely, when the model is given by controlled state dynamics driven by noises. In that case, we are given a sequence {X s } s∈ 0,T of Borel state spaces and a sequence {f s:s+1 } s∈ 0,T -1 of Borel-measurable dynamics f s:s+1 :

X s × U s × W s+1 → X s+1 . ( 13
)
For any time s ∈ 0, T -1 , we define the composition

f 0:s+1 = f s:s+1 • f s-1:s • . . . • f 0:1
with the abuse of notation that the composition is performed on the state argument. Setting W 0 = X 0 , we obtain that f 0:s+1 : H s+1 → X s+1 is a Borel-measurable mapping from the history space H s+1 taking values in the state space X s+1 . Now, given a natural number N > 0 and an increasing sequence 0 = t 0 < • • • < t N = T of times, we define the sequence θ t i i∈ 0,N of Borel-measurable reduction mappings by θ t i = f 0:t i : H t i → X t i for i > 0, and by θ 0 = I d (the identity mapping on W 0 ) for i = 0. Moreover, given i and j ∈ 0, N , with i < j we obtain, for all h t j ∈ H t j , that

θ t j (h t j ) = θ t j (h t i , h t i +1:t j ) = f t i :t j θ t i (h t i ), h t i +1:t j , (14)
with f t i :t j = f t j -1:t j • f t j -2:t j -1 • . . . • f t i :t i +1
which gives the state reduction Equation (9c).

Remark 6 (Block independent exogenous noises and stochastic kernels)

There is a practical case where compatible state reductions can readily be obtained. Assume that the sequence {ρ s-1:s } s∈ 1,T of stochastic kernels in (3) are mappings whose arguments do not include the control part (that is, depend at most on the history uncertainty part (see (44a)). If we interpret stochastic kernels as (conditional) distributions of noises (random process), this means that the system dynamics are driven by an exogenous noise process, say {W t } t∈ 1,T .

Assume moreover that the stochastic kernels give rise to noises that are independent block by block, in the sense that the random vectors W 0 , (W t ) t∈ 1,t 1 , (W t ) t∈ t 1 +1,t 2 , . . . , (W t ) t∈ t i +1,t i+1 , . . . , (W t ) t∈ t N -2 +1,t N -1 , (W t ) t∈ t N -1 +1,t N are stochastically independent. Then, from Definitions 2 and 4, we deduce that any state reduction across the same time blocks is compatible with the stochastic kernels.

Assuming the existence of a state reduction across the consecutive time blocks t i , t i+1 compatible with the sequence of stochastic kernels (3), we obtain the existence of a sequence of reduced Bellman operators across the time blocks t i , t i+1 as an immediate consequence of multiple applications of Proposition 3, that is, B t i+1 :t

i : L 0 + (X t i+1 ) → L 0 + (X t i ), i ∈ 0, N -1 , such that, for any function φt i+1 ∈ L 0 + (X t i+1 ), we have that B t i+1 :t i φt i+1 •θ t i = B t i+1 :t i ( φt i+1 • θ t i+1
). We now consider the family of optimization problems defined by the associated value functions [START_REF] Carpentier | Stochastic Multi-Stage Optimization[END_REF]. Thanks to the state reductions, we can enounce the following two theorems which establish dynamic programming equations across consecutive time blocks. The first one, Theorem 7, states a dynamic programming equation for an optimization problem in Mayer form (that is, just involving a final cost). The second one, Theorem 8, is more general as it involves both instantaneous costs and a final cost. As it is well known that the second case can be reduced to a Mayer form through a state augmentation, the proof of Theorem 8 easily follows from the proof of Theorem 7.

Theorem 7 (Time block decomposition for the Mayer form) We assume to be in the setting of §2.1. Suppose that a state reduction

{X t i } i∈ 0,N , {θ t i } i∈ 0,N , {f t i :t i+1 } i∈ 0,N -1 ex- ists across the consecutive time blocks { t i , t i+1 } i∈ 0,N -1 , satisfying 0 = t 0 < • • • < t N = T ,
which is compatible with the sequence {ρ s-1:s } s∈ 1,T of stochastic kernels given in [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF].

Suppose that there exists a reduced cost criterion  :

X T → [0, +∞],
which is a nonnegative lower semianalytic function and is such that the cost function j in (4) can be factored as j =  • θ T . We define the sequence of reduced value functions { Ṽt i } i∈ 0,N , where Ṽt i :

X t i → [0, +∞] for i ∈ 0, N , by Ṽt N =  and Ṽt i = B t i+1 :t i Ṽt i+1 , ∀i ∈ 0, N -1 , (15)
where the reduced Bellman operators

{ B t i+1 :t i } i∈ 0,N -1 across the intervals { t i , t i+1 } i∈ 0,N -1
are given in [START_REF] Kaut | Multi-horizon stochastic programming[END_REF]. Then, the sequence

{V t i } i∈ 0,N in (5) satisfies V t i = Ṽt i • θ t i , for all i ∈ 0, N .
Proof. The proof is an immediate consequence of multiple applications of Theorem 1 and Proposition 3.

Finally, we consider the special case where the criterion j : H T → [0, +∞] is factored as

j(h T ) = N -1 i=0 t i θ t i (h t i ), h t i +1:t i+1 + t N θ t N (h t N ) , (16)
where the numerical functions { t i } i∈ 0,N are nonnegative lower semianalytic, with t i :

X t i × H t i +1:t i+1 → [0, +∞] for i ∈ 0, N .
The associated optimization problems, indexed by i ∈ 0, N -1 and parameterized by h t i ∈ H t i , are given by

V t i (h t i ) = inf γ t i :T -1 ∈Γ t i :T -1 H T N -1 j=i t j θ t j (h t j ), h t j +1:t j+1 + t N θ t N (h t N ) ρ γ t i :T ( dh T | h t i ) , (17a)
and, for i = N ,

V t N (h t N ) = t N θ t N (h t N ) . (17b)
These Bellman equations are a special case of Equations ( 5) when the cost criterion j is given by [START_REF] Puterman | Markov Decision Processes[END_REF]. It is left to the reader to prove that the following theorem holds true 4 .

Theorem 8 (Taking care of instantaneous costs in addition to final cost) Suppose that the assumptions of Theorem 7 are satisfied, but for the cost criterion j : H T → [0, +∞] defined by Equation [START_REF] Puterman | Markov Decision Processes[END_REF].

We define the sequence of reduced value functions { Ṽt i } i∈ 0,N , where Ṽt i :

X t i → [0, +∞] for i ∈ 0, N , by Ṽt N = t N and Ṽt i = B t i+1 :t i Ṽt i+1 , ∀i ∈ 0, N -1 , (18)
where the reduced Bellman operator B t i+1 :t i across t i , t i+1 are given, for any i ∈ 0, N -1 , for any φt i+1 ∈ L 0 + (X t i+1 ) and for any x t i ∈ X t i , by

B t i+1 :t i φt i+1 (x t i ) = inf ut i ∈Ut i W t i +1 ρ t i :t i +1 ( dw t i +1 | x t i ) inf u t i +1 ∈U t i +1 W t i +2 ρ t i +1:t i +2 ( dw t i +2 | x t i , u t i , w t i +1 ) • • • inf u t i+1 -1 ∈U t i+1 -1 Wt i+1 ρ t i+1 -1:t i+1 ( dw t i+1 | x t i , u t i , w t i +1 , . . . , u t i+1 -2 , w t i+1 -1 ) t i (x t i , u t i , w t i +1 , . . . , u t i+1 -1 , w t i+1 ) + φt i+1 f t i :t i+1 (x t i , u t i , w t i +1 , . . . , u t i+1 -1 , w t i+1 ) . ( 19
)
Then, the sequence

{V t i } i∈ 0,N in Equations (17) satisfies V t i = Ṽt i • θ t i , for all i ∈ 0, N .
Here again, Formula (19) represents a nested sequence of infima of integrals (with respect to different stochastic kernels). Of course, solving Equation [START_REF] Porteiro | Towards multi-timescale energy provisioning using stochastic dual dynamic programming[END_REF] or Equation ( 19) can be as difficult as solving the original Bellman equation. However, the interest of such time block decomposition will be illustrated on different applications in Sect. 4, Sect. 5 and Sect. 6.

State reduction on multiple consecutive time blocks and reduced optimal feedbacks

As in the classical dynamic programming framework [1, p. 190], we recover the property that the search of an optimal policy among all policies (history feedbacks) can be limited to the search of an optimal state feedback. This is the most important result in practice.

Proposition 9 Under the assumptions of Theorem 7, the reduced value functions { Ṽt i } i∈ 0,N defined in [START_REF] Porteiro | Towards multi-timescale energy provisioning using stochastic dual dynamic programming[END_REF] are equal to the minimum value of the following optimization problems, parameterized by the reduced history (state)

x t i ∈ X t i Ṽt i (x t i ) = inf γ t i :T -1 ∈Γ x t i t i :T -1 H t i+1 :T (x t i , h t i +1:T )˜ γ t i :T ( dh t i +1:T | x t i , h t i+1 :t ) , ∀x t i ∈ X t i , (20a)
and

ṼT (x T ) = (x T ) , ∀x T ∈ X T , (20b)
where the mapping  is given by

 = •f t N -1 :t N •f t N -2 :t N -1 •. . .•f t i :t i+1
(with, as already noted, the abuse of notation that the composition is performed on the state argument), where ˜ γ t i :T

is the reduced stochastic kernel (see Definition 2) associated with the kernel γ t i :T , the kernel γ t i :T being given in the factorization of the kernel ρ γ r:t , namely ρ γ r:t

( dh t | h r ) = δ hr ( dh r ) ⊗ γ r:t ( dh r+1:t | h r )
given by (48), δ being the Dirac measure, and where Γ

xt i t i :T -1
is the set of (t i :T -1)-reduced history feedbacks, that is, the set of sequences γ s s∈ t i ,T -1 of universally measurable mappings γ s :

X t i × H t i +1:s → U s .
Proof. Using Theorem 7, we have that, for all i ∈ 0, N , V t i = Ṽt i • θ t i , with Ṽt i satisfying the Bellman equation ( 15). For establishing that Ṽt i is a value function satisfying Equation [START_REF] Shapiro | Periodical multistage stochastic programs[END_REF], we now prove that, in the definition of V t i in Equation ( 5), we can replace the space Γ t i :T -1 of history feedbacks by the space Γ xt i t i :T -1 state feedbacks. We proceed as follows. Following [1, Chapter 8], we use the Bellman equation ( 19) to obtain -minimizers for each problem [START_REF] Carpentier | Stochastic Multi-Stage Optimization[END_REF]. As -minimizers are obtained by recursively solving Equations [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory. The society for industrial and applied mathematics and the mathematical programming society[END_REF], they are obtained by solving (up to ) parametric optimization problems. Thus, we easily get, using [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Proposition 8.3,p. 200], that an -minimizer at time t ∈ t i , t i+1 is a universally measurable function of (θ(h t i ), h t i+1 :t ). From this last fact, we get that -in the value function definition of V t i given in Equation ( 5) -the space Γ 0:T -1 can be replaced by the space of feedbacks given by universally measurable functions of the ordered pair (θ(h t i ), h t i+1 :t ) without changing the value function.

Finally, when considering Equation ( 5) -with this restricted space of state feedbacks, and considered at time t i for i ∈ 0, N -we obtain that the cost to be minimized is now parameterized by θ(h t i ) -as it is the case for the cost to be integrated and also for the stochatic kernels induced by the state feedbacks. By setting x i = θ(h t i ), the obtained optimization problem is the right hand side of ( 20), that we call Ṽt i (x t i ), and we have that, for all i ∈ 0, N , V t i = Ṽt i • θ t i . It remains to prove that Ṽt i = Ṽt i , for all i ∈ 0, N . By a proof similar to the one of Theorem 7, we show that the sequence { Ṽt i } i∈ 0,N satisfies the Bellman equation [START_REF] Porteiro | Towards multi-timescale energy provisioning using stochastic dual dynamic programming[END_REF]. By uniqueness, the sequence

{ Ṽt i } i∈ 0,N coincides with the sequence { Ṽt i } i∈ 0,N .

Mixing dynamic programming and stochastic programming

As a first application of the formalism developed in §3.2, we show how dynamic programming and stochastic programming can be mixed (which was the original motivation for the paper, see Footnote 1). The proof of the following proposition is a straightforward application of Theorem 8 combined with Remark 6.

Proposition 10 Suppose that the assumptions of Theorem 7 are satisfied. We consider multiple consecutive time blocks t i , t i+1 , with N ∈ N * , i ∈ 0, N -1 and 0 = t 0 < • • • < t N = T , and we assume that

• a state reduction {X t i } i∈ 0,N , {θ t i } i∈ 0,N , {f t i :t i+1 } i∈ 0,N -1 exists across the consec- utive time blocks { t i , t i+1 } i∈ 0,N -1 ,
• the noises are exogeneous and time block independent, that is, the elements of the sequence {ρ s-1:s } s∈ 1,T in (3) are, for all i ∈ 0, N -1 and r ∈ [t i , t i+1 ), of the form

ρ r:r+1 : W t i × • • • × W r → ∆(W r+1 ) , (21)
which means that the distribution of the uncertainty w r+1 is only function of the past uncertainties (w t i , . . . , w r ) within the time block,

• the cost criterion j : H T → [0, +∞] can be factored as

j(h T ) = N -1 i=0 t i θ t i (h t i ), h t i +1:t i+1 + t N θ t N (h t N ) , (22)
where the numerical functions { t i } i∈ 0,N are nonnegative lower semianalytic, with

t i : X t i × H t i +1:t i+1 → [0, +∞] for i ∈ 0, N .
Then, the multistage stochastic optimization problem (6) can be solved by the following algorithm.

Initialization. Define Ṽt N = t N : X T → [0, +∞].
Backward recursion. Suppose that the function Ṽt i+1 : X t i+1 → [0, +∞] is known at index i+1 ∈ 1, N . Then, for each state x t i ∈ X t i (for instance on a grid approximating the set X t i , or on X t i itself when finite and small enough), compute the previous Bellman value function Ṽt i at index i as

Ṽt i (x t i ) = inf ut i ∈Ut i W t i +1 ρ t i :t i +1 ( dw t i +1 | w t i ) inf u t i +1 ∈U t i +1 W t i +2 ρ t i +1:t i +2 ( dw t i +2 | w t i , w t i +1 ) • • • inf u t i+1 -1 ∈U t i+1 -1 Wt i+1 ρ t i+1 -1:t i+1 ( dw t i+1 | w t i , w t i +1 , . . . , w t i+1 -1 ) t i (x t i , u t i , w t i +1 , . . . , u t i+1 -1 , w t i+1 ) + Ṽt i+1 f t i :t i+1 (x t i , u t i , w t i +1 , . . . , u t i+1 -1 , w t i+1 ) . ( 23
)
Final step. Compute V 0 (w 0 ) = Ṽt 0 θ t 0 (w t 0 ) .

In many practical situations, all the uncertainty sets W 0 , . . . , W T are finite and the computation in ( 23) is tractable by using stochastic programming and scenario tree techniques, which do not require stagewise independence of the noises. We are thus able to take advantage of both the dynamic programming world and the stochastic programming world:

• use dynamic programming at a selection of time stages (for instance, at those of the slow time scale) and across the corresponding time blocks (for instance, across consecutive slow time stages), when noises are stochastically independent block by block; that yields Bellman value functions only for the chosen selection of time stages (for instance, at the slow time scale);

• use stochastic programming inside time blocks (for instance, at fast time scale, within two consecutive slow time stages); the fast time scale final cost function of a block is given by the Bellman value function computed at the slow time scale which corresponds to the terminal time stage of the block; no stagewise independence assumption is required within time blocks (for instance, for the short time scale noises).

Remark 11 As a special case, it is straightforward to check that the triplet

{W t i } i∈ 0,N , {θ t i } i∈ 0,N , {f t i :t i+1 } i∈ 0,N -1 , with
• the reduction mapping θ t i given by θ t i (h t i ) = w t i for all i ∈ 0, N ,

• the dynamics f t i :t i+1 given by f t i :t i+1 (w t i , h t i +1:t i+1 ) = w t i+1 , for all i ∈ 0, N -1 .

is a state reduction across the consecutive time blocks t i , t i+1 , i ∈ 0, N -1 which is compatible with the sequence of stochastic kernels given by Equation [START_REF] Street | Assessing the cost of the hazard-decision simplification in multistage stochastic hydrothermal scheduling[END_REF]. Thus, Proposition 10 applies. But, in this special case, the optimal controls can be computed in parallel with respect to time blocks, as the term Ṽt i+1 (w t i+1 ) is a constant in [START_REF] Whittle | Optimization over Time: Dynamic Programming and Stochastic Control[END_REF]. What is interesting in [START_REF] Whittle | Optimization over Time: Dynamic Programming and Stochastic Control[END_REF] is the added fact that the optimal strategy which was, a priori, searched as feedbacks depending on the whole history is in fact made up of independent strategies, each defined on a single time block and made up of feedbacks depending only on the block history (the history within the block).

Numerical illustration. To numerically illustrate the mixing between dynamic programming and stochastic programming, we consider a toy optimization problem over a time span 0, T , where T is an even natural number (for instance T = 24 for an hourly period problem during a day). The problem involves a storage, the state x t of which is driven by a dynamics involving a control variable u t and a noise variable w t+1 . We assume that the noises during the first half time span, that is, for t ∈ 1, T /2 , are independent of the noises during the second half time span, that is, for t ∈ T /2, T . We also assume that each noise variable w t can only take two possibles values, so that the whole uncertainty process can be represented by a binary tree.

In this problem, we consider the two consecutive time blocks 0, T /2 and T /2, T , and the state reduction is given in a straightforward manner by the variable x t (as explained in Remark 5). Thus, we are able to compute Bellman functions by the algorithm given in Proposition 10. We illustrate the algorithm for the horizon T = 24.

• The Bellman function Ṽ24 is given by the final cost function of the problem.

• The Bellman function Ṽ12 is approximated by discretization and it is computed on a grid involving n points (x 1 , . . . , x n ). For i ∈ 1, n , each value Ṽ12 (x i ) is obtained by solving a stochastic programming problem on the time span 12, 24 , that is, on a tree involving 2 12 leaves (as each noise variable w t can only take two possibles values).

• The optimal cost of the optimization problem is Ṽ0 (x 0 ), obtained again by stochastic programming on the time span 0, 12 , that is, by solving a stochastic optimization problem on a tree involving 2 12 leaves, the final cost being given by the function Ṽ12 .

Gathering the calculations performed by this algorithm, we obtain that solving the global problem by mixing dynamic programming and stochastic programming is done by solving (n + 1) stochastic optimization programs on scenario trees, each involving 2 12 leaves. The total number of leaves to explore -when solving the problem by this mixing method -is (n + 1)2 12 ≈ 4(n + 1) 10 3 , which gives an estimation of the algorithm computational effort. This mixing method is to be compared with a pure scenario tree method, that is, when the problem is solved by a stochastic optimization program on a scenario tree over the whole time horizon on 24 hours, the total number of leaves to explore being 2 24 ≈ 1.6 10 7 . Even using a fairly fine state discretization grid, for example a grid containing 100 points, the resolution by mixing dynamic programming and stochastic programming -when compared to the pure stochastic programming approach -leads to a quite significant gain, namely a factor 1.6 × 10 7 /4(100 + 1) × 10 3 ≈ 40 in our case.

We performed numerical experiments with a single computer equipped with 12 Intel Core i5-10500 CPU and 16 GB of RAM. We used the LP package of the solver Gurobi 9.51. Apart from the solver, all our code has been implemented with the Julia language and the JuMP modeler. As we failed to obtain a solution for the original problem on a tree for the horizon T = 24, we performed numerical tests for shorter horizons, hence for smaller numbers of time steps. For every T ∈ {12, 14, 16, 18, 20, 24}, we considered that a state reduction existed at time T /2. The results are gathered in Table 1, and show that the computational time -that is, the CPU time needed to create the LP model by JuMP and to solve it by Gurobi -needed by the pure scenario tree method is very rapidly increasing with the number of time steps, whereas the computational time needed by the mixing method grows very slowly with the number of time steps, at least for the different horizons under consideration. Finally, note that the mixing method can be easily parallelized since the computation of the n values ṼT/2 (x i ) i∈ 1,n of the Bellman function ṼT/2 can be performed in parallel, reducing the CPU time by a factor (n + 1)/2, that is, approximately 50 in our case.

Horizon T Mixing method Pure scenario tree method 12 6.5 s 0. As a second application of the formalism developed in §3.2, we show how to tackle a class of two-time-scale optimization problems. Indeed, some decisions problems naturally involve two different time scales, because of the timing of decisions -as for example long term investment decision and short term monitoring of physical devices. In §5.1 and §5.2 we detail the structure and we formulate the two-time-scale optimization problems that we consider. In §5.3, we show how to decompose such problems by time blocks. In §5.4, we illustrate the approach on a crude oil procurement problem.

Structure of a two-time-scale optimization problem

We provide the data for a two-time-scale multistage optimization problem.

Two time scales. The slow time scale is represented by a finite totally ordered set (S, ) as follows -where s + denotes the successor of s ∈ S and s -its predecessor, and where we use the notation t ≺ t for t t and t = t -

min S = s ≺ • • • ≺ s -≺ s ≺ s + ≺ • • • ≺ s = max S , (24a)
and the fast time scale by a finite totally ordered set (F, ):

min F = f ≺ • • • ≺ f -≺ f ≺ f + ≺ • • • ≺ f = max F . (24b)
In a sense to be made more rigorous later (once a unified timeline will have been defined), each slow time interval [s, s + [ is made up of |F| (cardinality of F) fast time steps, hence the denomination "two-time-scale". For instance, S = {M o, T u, W e, T h, F r, Sa, Su} may represent days, whereas F = 1, 24 may represent hours within a day. In some problems, we might even take F = 0, 24 to handle the fact that two decisions (one slow and one fast) are taken at midnight, hence an additional fast time step 0.

Unified timeline. We define the unified timeline of the decision problem in two steps. First, we equip the product set S × F with the following lexicographic order:

(s, f ) ≺ • • • ≺ (s -, f ) ≺ (s, f ) ≺ (s, f + ) ≺ • • • (25) • • • ≺ (s, f -) ≺ (s, f ) ≺ (s + , f ) ≺ • • • ≺ (s, f ) .
More formally, we denote by (s, f ) + the successor of (s, f ) in S × F \ {(s, f )}, with

(s, f ) + = (s, f + ) if f = f , (s + , f ) if f = f . (26a)
Similarly, we denote by (s, f ) -the predecessor of (s, f

) in S × F \ {(s, f )}, with (s, f ) -= (s, f -) if f = f , (s -, f ) if f = f . (26b)
In the product set S×F, the first time (s, f ) does not coincide with a slow time (the couple (M o, 0) does not correspond to Monday in our running example in §5.4). Thus, we add to the product set S×F an extra time denoted by (s -, f ), corresponding to the extra slow time s -, which is such that (s, f ) -= (s -, f ). We denote by S the set {s -} ∪ S and by S×F the set (s -, f ) ∪ (S×F), also called the extended timeline when equipped with an order as follows (where we use the notation (s,

f ) ≺ (s , f ) for (s, f ) (s , f ) and (s, f ) = (s , f )) (s -, f ) ≺ (s, f ) ≺ • • • ≺ (s -, f ) ≺ (s, f ) ≺ (s, f + ) ≺ • • • • • • ≺ (s, f -) ≺ (s, f ) ≺ (s + , f ) ≺ • • • ≺ (s, f ) . ( 27
)
The two-time-scale optimization problem will be formulated on the extended timeline S×F, which we trivially identify with the time set 0, T , where T = |S| × |F|.

Decisions. We suppose given

• a family {U s s } s∈S\{s} of slow time scale decision Borel spaces, and a family {W s s } s∈S of slow time scale uncertainty Borel spaces,

• a family {U sf (s,f ) } (s,f )∈S×(F\{ f })
of fast time scale decision Borel spaces, and a family

{W sf (s,f ) } (s,f )∈S×(F\{f })
of fast time scale uncertainty Borel spaces.

Dynamics. We suppose given a family {X sf (s,f ) } (s,f )∈S×F of fast time scale state Borel spaces.

For the sake of simplicity, we set X s s = X sf (s, f ) for all s ∈ S. Thus, the slow time s ∈ S is identified with the two scale time (s, f ), as illustrated in Figure 2. We also suppose given

s - s s + s- s (s -, f ) (s, f ) (s, f ) (s + , f ) (s + , f ) (s -, f ) (s, f ) (s, f ) S • • • • • • {s}×F S×F • • • {s + }×F • • • • • • {s}×F 1 Figure 2:
The product timeline with an extra starting point (s -, f ) a family {G s s } s∈S\{s} of slow time scale dynamics Borel-measurable mappings, that represent the evolution "driven at the slow time scale" given, for s ∈ S \ {s}, by5

G s s : X s s ×U s s ×W s s + → X sf (s + ,f ) , x s s , u s s , w s s + → x sf (s + ,f ) = G s s x s s , u s s , w s s + . (28a)
We suppose given a family {G sf (s,f ) }

(s,f )∈S×(F\{ f })
of fast time scale dynamics Borel-measurable mappings, that represent the evolution "driven at the fast time scale" given, for all s ∈ S and f ∈ F \ { f }, by

G sf (s,f ) : X sf (s,f ) ×U sf (s,f ) ×W sf (s,f ) + → X sf (s,f ) + , x sf (s,f ) , u sf (s,f ) , w sf (s,f ) + → x sf (s,f ) + = G sf (s,f ) x sf (s,f ) , u sf (s,f ) , w sf (s,f ) + . ( 28b
)
Cost functions. We suppose given a family {Λ s } s∈S\{s} of slow time scale nonnegative lower semianalytic cost functions, with

Λ s -: X s s -×U s s -×W s s × f ∈F\{ f } X sf (s,f ) ×U sf (s,f ) ×W sf (s,f ) + interval ]s -,s[={(s,f ),...,(s, f -)} → [0, +∞] ,
for s ∈ S, and a slow time scale nonnegative lower semianalytic final cost function Λ s

Λ s : X s s → [0, +∞] ,
that make up, by summation, an intertemporal cost

s∈S Λ s -x s s -, u s s -, w s s , (x sf (s,f ) , u sf (s,f ) , w sf (s,f ) + ) f ∈F\{ f } + Λ s x s s . (30)
Stochastic kernels. Finally, we suppose given a family of constant slow time scale Borelmeasurable stochastic kernels {ρ s s:

s + } s∈S\{s} ρ s s:s + ∈ ∆(W s s + ) , ∀s ∈ S \ {s} , (31a)
and, for each s ∈ S, a family {ρ sf (s,f ):(s,f )

+ } f ∈F\{ f } of fast time scale Borel-measurable stochastic kernels ρ sf (s,f ):(s,f ) + : W s s × f f =f + W sf (s,f ) in interval [s -,s[ -→ ∆(W sf (s,f ) + ) , ∀s ∈ S , ∀f ∈ F\{ f } , (31b)
with the convention that the Cartesian products of spaces in Equations (31a) and (31b) reduce to nothing when the upper index of the Cartesian product is strictly lower that the corresponding lower index. Note that, for a given s ∈ S, each fast time scale stochastic kernel ρ sf (s,f ):(s,f ) + , only depends on the noises of the slow time interval [s -, s[= {(s -, f ), (s, f ), . . . , (s, f -)}. The (constant) assumption (31a) and the (single block) assumption (31b) correspond to stochastic independence between time blocks, and will be useful in the proof of Proposition 12.

Formulation of a two-time-scale optimization problem on the product timeline

To apply Theorem 7, we introduce sets associated with the extended timeline (27) by

X (s,f ) = X s s if f = f X sf (s,f ) if f = f , ∀(s, f ) ∈ S×F , (32a)
U (s,f ) = U s s if f = f U sf (s,f ) if f = f , ∀(s, f ) ∈ S×F \ {(s, f )} , (32b)
W (s,f ) = W s s if f = f W sf (s,f ) if f = f , ∀(s, f ) ∈ S×F , (32c)
with the particular case of the extra initial slow time

W (s -, f ) = X s s -, (32d)
and a family of state dynamics G (s,f ) :

X (s,f ) ×U (s,f ) ×W (s,f ) + → X (s,f ) + defined by G (s,f ) = G s s if f = f G sf (s,f ) if f = f , ∀(s, f ) ∈ S×F \ {(s, f )} . ( 33
) s s + (s, f ) (s + , f ) (s + , f + ) (s + , f -) (s + , f )   X s s (= X sf (s, f ) ) ×U s s ×W s s +      X sf (s + ,f ) ×U sf (s + ,f ) ×W sf (s + ,f ) +       X sf (s + ,f + ) ×U sf (s,f + ) ×W sf (s + ,f + ) +       X sf (s + , f -) ×U sf (s + , f -) ×W sf (s + , f )       X sf (s + , f ) (= X s s + ) ×U s s + ×W s (s + ) +       X (s, f ) ×U (s, f ) ×W (s, f ) +       X (s + ,f ) ×U (s + ,f ) ×W (s + ,f ) +       X (s + ,f + ) ×U (s,f + ) ×W (s + ,f + ) +      X(s + , f -) ×U (s + , f -) ×W (s + , f )      X (s + , f ) ×U (s + , f ) ×W (s + , f ) +    • • • G s s G sf (s + ,f ) • • • G sf (s + , f -) G (s, f ) G (s + ,f ) • • • G (s + , f -) 1
Figure 3: Original dynamics and their reformulation on the product timeline on the slow time interval [s, s

+ [= {(s, f ), (s + , f ), . . . , (s + , f -)}
From these spaces, we deduce the history spaces and the histories for all (s, f ) ∈ S×F

H (s,f ) = W (s -, f ) × (s,f ) (s ,f ) (s,f ) U (s ,f ) -× W (s ,f ) , (34a)
h (s,f ) = w (s -, f ) , u (s ,f ) -, w (s ,f ) (s,f ) (s ,f ) (s,f ) , (34b)
and, for suitable indices, the partial history sets and the partial histories

H (s,f ):(s ,f ) = (s,f ) (s ,f ) (s ,f ) (U (s ,f ) -× W (s ,f ) ) , (35a)
h (s,f ):(s ,f ) = (u (s ,f ) -, w (s ,f ) ) (s,f ) (s ,f ) (s ,f ) . (35b)
The cost criterion formulated in Equation (30) combined with state dynamics leads to a (nonnegative lower semianalytic) cost criterion j :

H (s, f ) → [0, +∞].
Based on the stochastic kernels (31a) and (31b), we introduce stochastic kernels ρ (s,f ):(s,f ) + associated with the extended timeline (27), for each (s, f ) ∈ S×F \ {s, f }, by ρ (s,f ):(s,f ) + :

H (s,f ) -→ ∆(W (s,f ) + ) with ρ (s,f ):(s,f ) + dw (s,f ) + h (s,f ) = ρ s s:s + ( dw s s + ) if f = f , ρ sf (s,f ):(s,f ) + dw sf (s,f + ) w s s , w sf (s,f + ) , • • • , w sf (s,f ) if f = f .
Note that, for f = f , the stochastic kernels ρ (s,f ):(s,f ) + : H (s,f ):(s,f ) → ∆(W (s,f ) + ), only depend on the partial history uncertainty part from (s, f ) to (s, f ), and not on the (past) controls. The components of the problem are now formulated on the extended timeline S×F, already identified with the time set 0, T . Thus, we are in the framework of §2.1 and we aim at solving an optimization problem as formulated in Equation (6).

Two-time-scale decomposition

The existence of Bellman equations for a two-time-scale optimization problem is given by the following proposition.

Proposition 12 Consider a two-time-scale optimization problem as formulated in §5.1 and §5.2. The optimization problem (6) has a solution given by a dynamic programming equation at the slow scale. More precisely, let {V s } s∈S be given by V s = Λ s and, for s ∈ S \ {s}, by the backward induction6

V s (x s s ) = inf

u s s ∈U s s W s s + ρ s s:s + ( dw s s + ) inf u sf (s + ,f ) ∈U sf (s + ,f ) W sf (s + ,f + ) ρ sf (s + ,f ):(s + ,f + ) ( dw sf (s + ,f + ) | w s s + ) • • • inf u sf (s + , f -) ∈U sf (s + , f -) W sf (s + , f ) ρ sf (s + , f -):(s + , f ) ( dw sf (s + , f ) | w s s + , w sf (s + ,f + ) , • • • , w sf (s + , f -) ) Λ s (x s s , u s s , w s s + , . . . , u sf (s + , f -) , w sf (s + , f ) ) + V s + G s:s + (x s s , u s s , w s s + , . . . , u sf (s + , f -) , w sf (s + , f ) ) , (36)
where G s:s + is the composition

G s:s + = G sf (s + , f -) • • • • • G sf (s + ,f ) • G s
s associated with the state dynamics defined in (28). Then, the value of the optimization problem (6) is given by V s -(x s s -), where the initial condition x s s -corresponds to w 0 in (6), as stated by (32d).

Proof. The proof is an application of Theorem 8 with the help of Remarks 5 and 6. First, we have re-framed in §5.2 the two-time-scale optimization problems described in §5.1 in the formalism of §2.1 with the help of the extended timeline (27). Second, as we are given state dynamics (33) on the extended timeline and thanks to Remark 5, we obtain a state reduction at times {(s, f )} s∈S by composition of the state dynamics. Moreover, as the slow time scale stochastic kernels given by Equation (31a) are constant, the state reduction across the slow time scale is compatible with the stochastic kernels (see Remark 6). We are thus able to apply Theorem 8 and obtain the slow time scale Bellman recursion (36) as a special case of Equation [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory. The society for industrial and applied mathematics and the mathematical programming society[END_REF].

The slow time scale Bellman equation (36) is as difficult to solve as the Bellman equation on the extended timeline. However, the interest of (36) lies elsewhere. Imagine that one is able to obtain, in a relatively easy way, lower V s and upper V s approximations of V s in (36). Then, in order to obtain optimal controls for the optimization problem [START_REF] Carpentier | Time Block Decomposition of Multistage Stochastic Optimization Problems[END_REF], one can proceed as follows. By replacing the last term V s + of (36) by either V s + or V s + , one can now solve a (lower or upper) surrogate of Equation (36) and thus obtain the optimal controls on the time interval [s, s + [= {(s, f ), (s + , f ), . . . , (s + , f -)}. For instance, one could use scenario decomposition methods, like progressive hedging [START_REF] Rockafellar | Scenarios and policy aggregation in optimization under uncertainty[END_REF], that do not require statistical independence of noises within the slow time interval [s, s + [. Thus, the two-time-scale stochastic optimization problem as formulated in §5.1 and §5.2 can be approximatively solved, from below and from above, by a mix of slow time scale dynamic programming and of (for example) progressive hedging (or any other method, including dynamic programming).

Illustration with the crude oil procurement problem

This illustration stems from a research work done in partnership with TotalEnergies, in the context of a PhD thesis [START_REF] Martin | Stochastic Optimization for the Procurement of Crude Oil in Refineries[END_REF]. Crude oil procurement is the part of the oil supply chain that sits between the production of crude oil and its processing in a refinery. The goal of procurement is to purchase crude oil from various suppliers around the world and having it delivered in time to the refinery to be processed. As illustrated in Figure 4, every month (on the bottom line) a refinery receives crudes that have been bought during the 8 previous weeks (on the upper line). end cost associated with the state

u sf (M 1 ,1) u sf (M 1 ,2) u sf (M 1 ,3) u sf (M 1 ,4) u sf (M 2 ,1) u sf (M 2 ,2) u sf (M 2 ,3) u sf (M 2 ,4) u sf (M 3 ,1) u sf (M 3 ,2) u sf (M 3 ,3) u sf (M 3 ,4) u s M 0 u s M 1 u s M 2 M 0 M 1 1 2 3 4 M 2 1 2 3 4
x s M 3 = x sf (M 3 ,5)
valuation of the buffers and stocks in the refinery before the beginning of the month M 4

Table 2: Identification of the elements introduced in §5.1 with elements of the crude oil procurement problem refinery are made at the beginning of each month, and crude consumption is set once a month. On the other hand, crude oil shipments can be purchased at the frequency of the week; every week, a selection of shipments is presented to the decision-maker who must decide which shipments to purchase. Following the construction of the extended timeline in (27), we represent by the sequence

(M 0 , 5) ≺ (M 1 , 1) ≺ (M 1 , 2) ≺ (M 1 , 3) ≺ (M 1 , 4) ≺ (M 1 , 5) ≺ (M 2 , 1) ≺ (M 2 , 2) ≺ (M 2 , 3) ≺ (M 2 , 4) ≺ (M 2 , 5) (37) ≺ (M 3 , 1) ≺ (M 3 , 2) ≺ (M 3 , 3) ≺ (M 3 , 4) ≺ (M 3 , 5)
the timeline associated with Figure 4 (notice that we consider that a month is made of 4 weeks). The initial time stage (M 0 , 5) corresponds to the additional time (s -, f ) in ( 27). The times (M 1 , 5) and (M 2 , 5) both represent the "end of the month" when a consumption decision (slow scale decision u s s on the bottom line of Figure 4) is taken. We now illustrate how the crude oil procurement problem can be put in the form of a two-time-scale optimization problem such as presented in §5.1. For this purpose, we proceed to the identifications in Table 2.

We call s-buffer (resp. s --buffer), the temporary stock that is created at the beginning of the month s (resp. s -) and that will be delivered two months after. For instance, in Figure 4, the yellow disks represent the M 1 -buffer and the red disks represent the M 2 -buffer. We introduce the state variable x sf (s,f ) = s --buffer, s-buffer, refinery stocks , together with the accumulation dynamics G sf (s,f ) for the buffers, and the accumulation dynamics G s s for the stocks. Regarding the criterion to minimize, it is an intertemporal cost like in (30) with slow time scale cost functions Λ s -made of minus the purchases of crude oil plus the selling of finished products inside a week. Supposing that the products prices are independent month by month, we represent this assumption by a family of constant stochastic kernels {ρ s s:s + } s∈S\{s} . By contrast, we do not assume that the crude prices are independent week by week, and the possible dependency is modeled by stochastic kernels ρ sf (s,f ):(s,f ) + for f ∈ F\{ f }. Now that all the elements from §5.1 have been identified, Proposition 12 enables us to write a dynamic programming equation such as (36) at the scale of the month, without losing the time-dependency of crude prices inside the month.

Decision-hazard-decision optimization problems

In multistage stochastic optimization, the decision-hazard-decision (DHD) framework corresponds to the case where, at the beginning of each time interval, a decision is taken without knowing the uncertainty that will materialize at the end of the time interval (decisionhazard), and, at the end of the time interval, a recourse decision is possible knowing this uncertainty (hazard-decision). The reader is referred to [5, §1.2.1] for the notions of decisionhazard and hazard-decision in stochastic optimal control. A discussion about these notions and an application in stochastic thermal scheduling can also be found in [START_REF] Street | Assessing the cost of the hazard-decision simplification in multistage stochastic hydrothermal scheduling[END_REF].

In §6.1, we provide motivation for the decision-hazard-decision framework. In §6.2, we formalize the decision-hazard-decision framework and we provide a dynamic programming equation.

Motivation for the decision-hazard-decision framework

We illustrate our motivation to develop a formalism for the decision-hazard-decision framework with a single dam management problem. We suppose given a stochastic process {A t } t∈ 1,T on a probability space. We can model the dynamics of the water volume in a dam by

S t+1 = min S , S t -Q t + A t+1 , ∀t ∈ 0, T -1 , ( 38
)
where Alternatively, we can model the dynamics of the water volume in a dam by

S
S t+1 = S t -Q t + A t+1 -R t+1 , ∀t ∈ 0, T -1 , (39)
where the new control variable R t+1 is the spilled volume, decided at the end of period [t, t + 1[, supposed to depend both on the stock S t and on the inflow water A t+1 , and chosen such that 0 ≤ S t -Q t + A t+1 -R t+1 ≤ S . Thus, with the formulation (39), we "pay the price" to add one control R t+1 , but we obtain a linear model instead of the nonlinear model (38). This is especially interesting when using the stochastic dual dynamic programming (SDDP) algorithm, for which the linearity of the dynamics is used to obtain the convexity properties required by the algorithm.

Decision-hazard-decision framework and dynamic programming equation

Let {U t } t∈ 0,T -1 (head or "before" controls), {U t } t∈ 1,T (tail or "after" controls), {W t } t∈ 1,T (uncertainties) and {X t } t∈ 0,T (states) be sequences of Borel spaces. Let also be given Borelmeasurable dynamics mappings

f t : X t × U t × W t+1 × U t+1 → X t+1 , ∀t ∈ 0, T -1 , (40a)
nonnegative lower semianalytic instantaneous cost functions

L t : X t × U t × W t+1 × U t+1 → [0, +∞] , ∀t ∈ 0, T -1 , (40b)
and a nonnegative lower semianalytic final cost function

K : X T → [0, +∞] . (40c)
Finally, we suppose given a Borel probability space (Ω, F, P), a random variable X 0 : Ω → X 0 , and a stochastic process {W t } t∈ 1,T (noise process), where W t : Ω → W t for t ∈ 1, T . Thus equipped, we consider the following multistage stochastic optimization problem inf

{(U t ,U t+1 )} t∈ 0,T -1 E T -1 t=0 L t (X t , U t , W t+1 , U t+1 ) + K(X T ) , (41a)
σ(U t ) ⊂ σ(X 0 , W 1 , . . . , W t ) , ∀t ∈ 0, T -1 , (41b)
σ(U t ) ⊂ σ(X 0 , W 1 , . . . , W t ) , ∀t ∈ 1, T , (41c)
X t+1 = f t (X t , U t , W t+1 , U t+1 ) , ∀t ∈ 0, T -1 . (41d)
Thus, in the above setting, during the time interval between two time steps, the decisionmaker makes two decisions. Proposition 13 If the a random variable X 0 is deterministic with value x 0 , and if the noise process {W t } t∈ 1,T is white, that is, is made of independent random variables, then the value V 0 (x 0 ) of the multistage stochastic optimization problem (41) is given by the dynamic programming backward induction

V T (x) = K(x) , (42a)
and, for t ∈ 0, T -1 ,

V t (x) = inf u t ∈U t E inf u t+1 ∈U t+1 L t (x, u t , W t+1 , u t+1 ) + V t+1 f t (x, u t , W t+1 , u t+1 ) . ( 42b
)
Proof. As the statement is made with random variables, whereas the theory has been developed with stochastic kernels, we make the link as follows: for each time t ∈ 1, T , the stochastic kernel ρ t-1:t in (3) is the probability distribution of the random variable W t . This done, the proof is an application of Theorem 8, as follows (we just sketch the procedure, as the detailed proof can be found in the preprint [START_REF] Carpentier | Time Block Decomposition of Multistage Stochastic Optimization Problems[END_REF]). We rename the uncertainty sets {W t } t∈ 1,T as {W t } t∈ 1,T and for each time t ∈ 1, T we introduce a spurious uncertainty variable w t taking values in a singleton set W t = { w t }, so that we obtain the following sequence of events

w 0 =x 0 u 0 w 1 u 1 w 1 spurious u 1 w 2 u 2 w 2 spurious u 2 . . . w T -1 u T -1 w T -1 spurious u T -1 w T u T w T spurious .
Proceeding this way, we have doubled the timeline as time t has been "duplicated" in the ordered pair (t, ) and (t, ). With this, we embed the decision-hazard-decision structure as a particular case of multiple consecutive time blocks (of size 2) as in §3.2.

Equation (42) can be solved using the stochastic dual dynamic programming (SDDP) algorithm provided that lower semicontinuity and convexity of the value functions are preserved. This is ensured first by assuming linearity in the dynamics -a feature that may be obtained by modeling the problem in the decision-hazard-decision framework as illustrated in §6.1 -and second by assuming lower semicontinuity for the cost functions as well as compactness for the existence of optimal controls.

Conclusion and perspectives

As said in the introduction, decomposition methods are appealing to tackle multistage stochastic optimization problems, as they are naturally large scale. The most common approaches are time decomposition (and state-based resolution methods, like stochastic dynamic programming, in stochastic optimal control), and scenario decomposition (like progressive hedging in stochastic programming).

This paper is part of a general research program that consists in mixing different decomposition bricks. Space decomposition methods have been investigated in [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF] and [START_REF] Carpentier | Mixed spatial and temporal decompositions for large-scale multistage stochastic optimization problems[END_REF]. Here, we have tackled the issue of using time block decomposition in such a way that stochastic dynamic programming is used at the slow time scale with an appropriate white noise assumption, whereas stochastic programming methods such as progressive hedging can be used at the fast time scale where such an independence assumption does not hold. This approach paves the way of mixing time decomposition with scenario decomposition. For this purpose, we have revisited the notion of state, and have provided a way to perform time decomposition but only across specified time blocks.

Otherwise stated, the flow is given by Φ γ r:t (h r , w r+1:t ) = (h r , u r , w r+1 , u r+1 , w r+2 , . . . , u t-1 , w t ) , (45b) with h s = (h r , u r , w r+1 , . . . , u s-1 , w s ) , r < s ≤ t , (45c) and

u s = γ s (h s ) , r ≤ s ≤ t -1 . (45d)
When 0 ≤ r = t ≤ T , we put Φ γ r:r : H r → H r , h r → h r . With this convention, the expression Φ γ r:t makes sense when 0 ≤ r ≤ t ≤ T . The mapping Φ γ r:t gives the history at time t as a function of the initial history h r at time r and of the history feedbacks {γ s } s∈ r,t -1 ∈ Γ r:t-1 . An immediate consequence of this definition are the flow properties:

Φ γ r:t+1 (h r , w r+1:t+1 ) = Φ γ r:t (h r , w r+1:t ), γ t Φ γ r:t (h r , w r+1:t ) , w t+1 , 0 ≤ r ≤ t ≤ T -1 , (46a)
Φ γ r:t (h r , w r+1:t ) = Φ γ r+1:t h r , γ r (h r ), w r+1 , w r+2:t , 0 ≤ r < t ≤ T . (46b)
We recall that L 0 + (H t ) denotes the space of lower semianalytic nonnegative numerical functions over H t . Definition 14 Let r and t be given such that 0 ≤ r ≤ t ≤ T .

• When 0 ≤ r < t ≤ T , for a (r : t -1)-history feedback γ = {γ s } s∈ r,t-1 ∈ Γ r:t-1 , and for a family {ρ s-1:s } s∈ r+1,t of Borel-measurable stochastic kernels ρ s-1:s : H s-1 → ∆(W s ) , s ∈ r+1, t , we define a Borel-measurable stochastic kernel ρ γ r:t : H r → ∆(H t ) such that, for any numerical function ϕ ∈ L 0 + (H t ), we have that

Ht ϕ(h r , h r+1:t )ρ γ r:t ( dh t | h r ) = W r+1:t ϕ Φ γ r:t (h r , w r+1:t ) t s=r+1 ρ s-1:s dw s Φ γ r:s-1 (h r , w r+1:s-1 ) . (47)
• When 0 ≤ r = t ≤ T , we define ρ γ r:r : H r → ∆(H r ) by ρ γ r:r ( dh r | h r ) = δ hr ( dh r ) where δ represents the Dirac measure.

The stochastic kernels ρ γ r:t on H t , given by (47), are of the form

ρ γ r:t ( dh t | h r ) = ρ γ r:t ( dh r dh r+1:t | h r ) = δ hr ( dh r ) ⊗ γ r:t ( dh r+1:t | h r ) , (48)
where, for each h r ∈ H r , the probability distribution γ r:t ( dh r+1:t | h r ) only charges the histories visited by the flow from r+1 to t. The construction of the stochastic kernels ρ γ r:t is developed in [1, p. 190] for relaxed history feedbacks and obtained by using [

=

W s+1:t ϕ Φ γ s:t (h s , w s+1:t ) W s+1:t t s =s+1 ρ s -1:s dw s Φ γ s:s -1 (h s , w s+1:s -1 )
by Definition (47)

= W s+1:t ϕ Φ γ s:t (h s , w s+1:t ) ρ s:s+1 dw s+1 h s W s+1:t t s =s+2 ρ s -1:s dw s Φ γ s:s -1 (h s , w s+1:s -1 ) = W s+1:t ϕ Φ γ s+1:t (h s , γ s (h s ), w s+1 ), w s+2:t ρ s:s+1 dw s+1 h s t s =s+2 ρ s -1:s dw s Φ γ s+1:s -1 (h s , γ s (h s ), w s+1 ), w s+2:s -1 (by the flow property (46b)) = W s+1 ρ s:s+1 dw s+1 h s W s+2:t ϕ Φ γ s+1:t (h s , γ s (h s ), w s+1 ), w s+2:t t s =s+2 ρ s -1:s dw s Φ γ s+1:s -1 (h s , γ s (h s ), w s+1 ), w s+2:s -1 by Fubini Theorem = W s+1 ρ s:s+1 dw s+1 h s Ht ϕ (h s , γ s (h s ), w s+1 ), h s+2:t ρ γ s+1:t dh t (h s , γ s (h s ), w s+1 ) by Definition (47) = Ht ϕ (h s , γ s (h s ), w s+1 ), h s+2:t W s+1 ρ s:s+1 dw s+1 h s ρ γ s+1:t dh t (h s , γ s (h s ), w s+1 ) (50b)
by Fubini Theorem. As the two expressions (50a) and (50b) are equal for any ϕ ∈ L 0 + (H t ), we deduce the flow property (49).

Proof of Theorem 1. We only give a sketch of the proof, as it is a variation on different results of [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF], the framework of which we follow.

Proof. We are in the setting of [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Chap. 7,Chap. 8]. We take the history space H t for state space, and the state dynamics

f h t , u t , w t+1 = h t , u t , w t+1 = h t+1 ∈ H t+1 = H t × U t × W t+1 . (51)
Then, the family {ρ s-1:s } s∈ 1,T of Borel-measurable stochastic kernels (3) gives a family of disturbance kernels (vocabulary of [1, p 189]) that do not depend on the current control. The criterion to be minimized ( 4) is a function of the history at time T , thus of the state at time T . We consider the finite horizon model with final cost corresponding to the optimization problem defined by the associated value function ( 6):

V 0 (w 0 ) = inf γ 0:T -1 ∈Γ 0:T -1 H T j(h T )ρ γ 0:T ( dh T | w 0 ) = inf γ 0:T -1 ∈Γ 0:T -1 W 1:T j Φ γ 0:T (w 0:T ) T s=1 ρ s-1:s dw s Φ γ 0:s-1 (w 0:s-1 ) , (by (47))
where the flows Φ γ 0:s for s ∈ 0, T -1 are defined by Equation (45a), and where we are minimizing over the so-called state-feedbacks. Then, the proof of Theorem 1 follows from the results developed in Chap. 7, 8 and 10 of [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF] in a Borel setting.

The Bellman operators in (7a) satisfy (7b) because, by Lemma 7.30(4) and Propositions 7.47 and 7.48 in [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF], we have that 7

ϕ ∈ L 0 + (H t+1 ) =⇒ B t+1:t ϕ ∈ L 0 + (H t ), for t in 0, T -1 .
Since we are considering a finite horizon model with a final cost, we detail the steps needed to use the results of [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Chap. 8]. The final cost at time T can be turned into an instantaneous cost at time T -1 by inserting the state dynamics (51) in the final cost. Getting rid of the disturbance in the expected cost by using the disturbance kernel is standard practice. Then, we can turn this non-homogeneous finite horizon model into a finite horizon model with homogeneous dynamics and costs by following the steps of [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Chap. 10]. Using [1, Proposition 8.2, p. 198], we obtain that the family of optimization problems defined by the associated value functions [START_REF] Carpentier | Stochastic Multi-Stage Optimization[END_REF], when minimizing over the relaxed state feedbacks, satisfies the Bellman equation ( 8); we conclude with [1, Proposition 8.4, p. 203] which covers the minimization over state feedbacks.

The Bellman equation ( 8) is a consequence of [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Proposition 8.2,p. 198].

To finish, Theorem 1 is valid under the general Borel assumptions of [1, Chap. 8] and with the specific (F + ) assumption needed for [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Proposition 8.4,p. 203]; this last assumption is fulfilled here since we have assumed that the cost criterion (4) is nonnegative.

Proof of Proposition 3.

We suppose to be in the framework of §2.1.

Proof. We are in the setting of [START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF]Chap. 7,Chap. 8]. Let φt : X t → [0, +∞] be a given lower semianalytic nonnegative numerical function, and let ϕ t : H t → [0, +∞] be

ϕ t = φt • θ t . (52)
Let ϕ r : H r → [0, +∞] be the lower semianalytic nonnegative numerical function obtained by applying the Bellman operator B t:r across t, r (see [START_REF] Glanzer | Multiscale stochastic optimization: modeling aspects and scenario generation[END_REF]) to the lower semianalytic nonnegative numerical function ϕ t :

ϕ r = B t:r ϕ t = B r+1:r • • • • • B t:t-1 ϕ t . (53)
By [1, Lemma 7.30(3), p. 178] -on the stability of lower semianalytic functions under right composition with a Borel-measurable mapping -we get that the nonnegative numerical function ϕ r is lower semianalytic. We show that there exists a lower semianalytic nonnegative numerical function φr :

X r → [0, +∞] such that ϕ r = φr • θ r . (54)
First, we show by backward induction that, for all s ∈ r, t , there exists a lower semianalytic nonnegative numerical function ϕ s such that ϕ s (h s ) = ϕ s (θ r (h r ), h r+1:s ). Second, we prove that the function φr = ϕ r satisfies (54) and is lower semianalytic.

• For s = t, we have, by (52) and by (9c), that ϕ t (h t ) = φt θ t (h t ) = φt f r:t (θ r (h r ), h r+1:t ) , so that the nonnegative numerical function ϕ t is given by φt • f r:t . By [1, Lemma 7.30(3), p. 178], ϕ t is a lower semianalytic numerical function.

• Assume that, at s+1, the result holds true, that is, ϕ s+1 (h s+1 ) = ϕ s+1 (θ r (h r ), h r+1:s+1 ), where the numerical function ϕ s+1 is nonnegative lower semianalytic. Then, by (53), ϕ s+1 (x r , (h r+1:s , u s , w s+1 )) ρ s:s+1 dw s+1 (x r , h r+1:s ) .

ϕ s (h s ) = B s+1:s ϕ s+1 (h s ) = inf us∈Us W s+1 ϕ s+1 (h s ,
By [1, p. 196] (right before Lemma 8.2), we get that the numerical function ϕ s is nonnegative lower semianalytic. Thus, we have shown that the result holds true at time s.

The induction implies that, at time r, the expression of ϕ r (h r ) is ϕ r (h r ) = ϕ r θ r (h r ) , since the term h r+1:r vanishes. Choosing φr = ϕ r gives the expected result.

Forewords for additional material

We provide here additional material to the paper [START_REF] Carpentier | Time Block Decomposition of Multistage Stochastic Optimization Problems[END_REF]. In Appendix B, we survey several frameworks and approaches to solve, by dynamic programming, a stochastic optimal control problem formulated in discrete time. In Appendix C, we make the link between the setting of two-time-scale optimization problems (as developed in Sect. 5 with stochastic kernels) and the framework of stochastic optimal control (with random variables). In Appendix D, we give a detailed proof of Proposition 13 concerning the decision-hazard-decision approach. In Appendix E, we present a framework for two-time-scale multistage optimization problems which is more general than in Sect. 5.

B A brief survey of frameworks for stochastic dynamic programming in discrete time

We sketch mathematical frameworks for stochastic dynamic programming in discrete time to be found in the literature. In what follows, t 0 ∈ N and T ∈ N * are two natural numbers such that t 0 < T . We use the notation r, s = {r, r + 1, . . . , s -1, s} for any two natural numbers r, s such that r ≤ s.

Witsenhausen approach. The most general stochastic dynamic programming principle is sketched by Witsenhausen at the end of [START_REF] Witsenhausen | On policy independence of conditional expectations[END_REF]. However, we do not detail it as its formalism is too far from the following ones, though we will touch the subject when we discuss Yüksel's approach below. We present here what Witsenhausen calls an optimal stochastic control problem in standard form (see [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF]). The ingredients are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive natural numbers;

2. (X t 0 , X t 0 ) (nature), (X t 0 +1 , X t 0 +1 ), . . . , (X T , X T ) (state spaces) are measurable spaces;

3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces);

4. I t is a subfield of X t , for t ∈ t 0 , T -1 (information);

5. f t : (X t × U t , X t ⊗ U t ) → (X t+1 , X t+1 ) is measurable, for t ∈ t 0 , T -1 (dynamics); 6. π t 0 is a probability on (X t 0 , X t 0 ); 7. j : (X T , X T ) → R is a measurable function (criterion).
With these ingredients, Witsenhausen formulates a stochastic optimization problem, whose solutions are to be searched among adapted feedbacks, namely λ t : (X t , X t ) → (U t , U t ) with the property that λ -1 t (U t ) ⊂ I t for all t ∈ t 0 , T -1 . Then, he establishes a dynamic programming equation, where the Bellman functions are function of the (unconditional) distribution of the original state x t ∈ X t , and where the minimization is done over adapted feedbacks. The main objective of Witsenhausen is to establish a dynamic programming equation for nonclassical information patterns.

Evstigneev approach. The ingredients of the approach developed in [START_REF] Evstigneev | Measurable selection and dynamic programming[END_REF] are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive natural numbers; 2. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces); 3. (Ω, F) is a measurable space (nature); 4. F t t∈ t 0 ,T -1 is a filtration of F (information); 5. P is a probability on (Ω, F);

6. j : (Ω × t∈ t 0 ,T -1 U t , F ⊗ t∈ t 0 ,T -1 U t ) → R is a measurable function (criterion).
With these ingredients, Evstigneev formulates a stochastic optimization problem, whose solutions are to be searched among adapted processes, namely random processes with values in t∈ t 0 ,T -1 U t and adapted to the filtration F t t∈ t 0 ,T -1 . Then, he establishes a dynamic programming equation, where the Bellman function at time t is an F t -integrand depending on controls up to time t (random variables) and where the minimization is done over F tmeasurable random variables at time t. The main objective of Evstigneev is to establish an existence theorem for an optimal adapted process (under proper technical assumptions, especially on the objective function j, that we do not detail here). Notice that there is no notion of state variable.

Puterman approach. The ingredients of the approach developed in [AM5, Sect. 2.1] are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive natural numbers; 2. (X t 0 , X t 0 ), . . . , (X T , X T ) are measurable spaces (state spaces); 3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces); 4. ν t:t+1 : X t × U t → ∆(X t+1 ) is a stochastic kernel, for t ∈ t 0 , T -1 (transitions); 5. L t : X t × U t → R, for t ∈ t 0 , T -1 , and K : X T → R, are measurable functions (instantaneous and final costs).

With these ingredients, Puterman formulates a stochastic optimization problem with a time additive cost function over given state and control spaces, whose solutions are to be searched among history feedbacks, namely sequences of mappings X t 0 × t-1 s=t 0 (U s × X s+1 ) → U t . Then, he establishes a dynamic programming equation, where the Bellman functions are function of the history h t ∈ X t 0 × t-1 s=t 0 (U s × X s+1 ). He identifies cases where no loss of optimality results from reducing the search to Markovian feedbacks X t → U t . In such cases, the Bellman functions are function of the state x t ∈ X t , and the minimization in the dynamic programming equation is done over controls u t ∈ U t . The main objective of Puterman is to explore infinite horizon criteria, average reward criteria, the continuous time case, and to present many examples.

Hernández-Lerma and Lasserre approach. The ingredients of the approach developed in [AM4, §2.2, §3.2, §3.3] are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive natural numbers; 2. (X t 0 , X t 0 ), . . . , (X T , X T ) are Borel spaces (state spaces); 3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are Borel spaces (control spaces); there are also feasible state-dependent control constraints that we do not present here;

4. ν t:t+1 : X t × U t → ∆(X t+1 ), for t ∈ t 0 , T -1 , are Borel-measurable stochastic kernels (transitions); 5. L t : X t × U t → R, for t ∈ t 0 , T -1 , and K : X T → R are Borel-measurable functions (instantaneous and final costs).

With these ingredients, Hernández-Lerma and Lasserre formulate a stochastic optimization problem with a time additive cost function over given state and control spaces. They introduce the "canonical construction" where the history at time t consists in the states and the controls prior to t. Then, they study optimization problems whose solutions (policies) are to be searched among history feedbacks (or randomized history feedbacks), namely sequences of mappings X t 0 × t-1 s=t 0 (U s × X s+1 ) → U t . They identify cases where no loss of optimality results from reducing the search to (relaxed) Markovian feedbacks X t → U t . Then, they establish a dynamic programming equation, where the Bellman functions are function of the state x t ∈ X t , and where the minimization is done over controls u t ∈ U t . For finite horizon problems, the mathematical challenge is to set up a mathematical framework -the Borel assumptions plus additional topological ones presented in [AM4, §3.3] -for which optimal policies exists. The main objective of [START_REF] Hernández | Discrete-Time Markov Control Processes: Basic Optimality Criteria[END_REF] is to offer a unified and comprehensive treatment of discrete-time Markov control processes, with emphasis on the case of Borel state and control spaces, and possibly unbounded costs and noncompact control constraint sets.

Bertsekas and Shreve approach. The ingredients of the approach developed in [START_REF] Bertsekas | Stochastic Optimal Control: The Discrete-Time Case[END_REF] (more precisely in [AM1, Definition 10.1]) are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive natural numbers; 2. (X t 0 , X t 0 ), . . . , (X T , X T ) are Borel spaces (state spaces); With these ingredients, Bertsekas and Shreve formulate a stochastic optimization problem with a time additive cost function over given state spaces, control spaces and uncertainty spaces. They introduce the notion of history at time t which consists in the states and the controls prior to t and study optimization problems whose solutions (policies) are to be searched among history feedbacks (or relaxed history feedbacks), namely sequences of mappings from history space X t 0 × t-1 s=t 0 (U s × X s+1 ) → U t . They identify cases where no loss of optimality results from reducing the search to (relaxed) Markovian feedbacks X t → U t . Then, they establish a dynamic programming equation, where the Bellman functions are function of the state x t ∈ X t , and where the minimization is done over controls u t ∈ U t . For finite horizon problems, the mathematical challenge is to set up a mathematical framework (the Borel assumptions) for which optimal policies exists. The main objective of Bertsekas and Shreve is to state conditions under which the dynamic programming equation is mathematically sound in the context of Borel spaces. The interested reader will find all the subtleties in [AM1, Chapter 7].

Yüksel approach. As said at the beginning, the most general stochastic dynamic programming principle is sketched by Witsenhausen at the end of [START_REF] Witsenhausen | On policy independence of conditional expectations[END_REF]. This approach builds upon the so-called Witsenhausen intrinsic model [START_REF] Witsenhausen | The intrinsic model for discrete stochastic control: Some open problems[END_REF] which does not consider state, but information under the form of σ-fields (see [AM 9] for the functional form). In [AM 6], Witsenhausen provides conditions to express stochastic control optimization problemswith information constraints, but without state -in standard form with a state (the first approach that we have considered above).

Although Witsenhausen established a dynamic programming equation in [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF], Yüksel notes in [START_REF] Yüksel | A universal dynamic program and refined existence results for decentralized stochastic control[END_REF] that "Witsenhausen's construction [. . . ] does not address the well-posedness of such a dynamic program" and that "the existence problem was not considered". In the spirit of [START_REF] Witsenhausen | A standard form for sequential stochastic control[END_REF], Yüksel entails in [AM10] "a general approach establishing that any sequential team optimization may admit a formulation appropriate for a dynamic programming analysis". One of the contributions of [START_REF] Yüksel | A universal dynamic program and refined existence results for decentralized stochastic control[END_REF] is to propose a construction of standard Borel controlled state and action spaces and to establish a universal dynamic program for stochastic control optimization problems -with information constraints, but without state -thus addressing some of the issues raised and left open by Witsenhausen. The ingredients are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive natural numbers; This said, our preoccupation could be adapted to any of the above frameworks. Indeed, our objective is to establish a dynamic programming equation with a state, not at any time t ∈ t 0 , T , but at some specified instants t 0 < t 1 < • • • < t N = T . In §3.2, the state spaces are introduced as image sets (codomains) of what we call (time block) history reduction mappings (where history at time t consists of all uncertainties and controls prior to time t).

C Supplement to Sect. 5

We make the link between the setting of two-time-scale optimization problems (as developed in Sect. 5 with stochastic kernels) and the framework of stochastic optimal control (with random variables).

The property that the stochastic kernels (31) do not depend on any decision variable makes it possible to build a probability ρ (s,f ):(s, f ) on the product space W (s,f ):(s, f ) by The integral cost given in the right hand side of Equation (57a) can be reformulated as a mathematical expectation, denoted by E, with respect to the probability ρ (s,f ):(s, f ) by introducing random variables for the exogeneous noises as projection mappings from W (s,f ):(s, f ) to W (s,f ) for all (s, f ) ∈ S×F W (s,f ) : W (s,f ):(s, f ) → W (s,f ) , ∀(s, f ) ∈ S×F , (58) and obtaining random variables for the states and the control through the dynamics equations (57b)-(57c) and the feedback equations (57d)-(57e

ρ (s,f ):(s, f ) = s∈S ρ s s:s + ( dw s s + ) ⊗ ρ sf (s + ,f ):(s + ,f + ) ( dw sf (s + ,f + ) | w s s + ) ⊗ • • • ⊗ ρ sf (
U sf (s,f ) ∈ U sf (s,f ) , ∀s ∈ S , ∀f ∈ F \ { f } , (59e)
σ U sf (s,f ) ⊂ σ {W s s } s s , {W sf (s ,f ) } (s ,f ) (s,f ) , ∀s ∈ S , ∀f ∈ F \ { f } , (59f)
where the two feedback constraints in (57d) and (57e) are reformulated as measurability constraints (59e) and (59g), using the σ-fields generated by random variables (of course, a formal equivalence would require to be more specific about spaces to use Doob functional Lemma).

D Detailed proof of Proposition 13 (Sect.6)

As indicated in the sketchy proof of Proposition 13, we give here a detailed proof of this latter. For this purpose, we first flesh out the ingredients necessary to formulate a multistage stochastic optimization problem with decision-hazard-decision information structure. Second, we provide in Theorem 16 a Bellman equation for such a multistage stochastic optimization problem (see Equation ( 70)). Third, we give the proof of Theorem 16 which is derived through an embeding of the decision-hazard-decision structure as a particular case of multiple consecutive time blocks followed by an application of Theorem 8.

History. Let T ∈ N * . For each time t ∈ 0, T -1 , the head decision u t takes values in a Borel space U t . For each time t ∈ 1, T , the tail decision u t takes values in a Borel space U t . For each time t ∈ 1, T , the uncertainty w t takes its values in a Borel space W t . For time t = 0, the uncertainty w 0 takes its values in a Borel space W 0 . At the beginning of the time interval [t, t+1[, the decision-maker makes a head decision u t . What is new -in comparison with the classical decision-hazard framework -is that, at and a nonnegative lower semianalytic final cost function

K : X T → [0, +∞] . (63c)
Second, we recursively define a family of Borel-measurable reduction mappings θ t : H t → X t by the following forward recursion for t ∈ 0, T -1 θ t+1 (h t+1 ) = f t θ t (h t ), u t , w t+1 , u t+1 , and θ 0 (h 0 ) = h 0 ,

γ T (h T ) = γ T (h T ) , ∀h T ∈ H T .

In fact, in the special case (61) we are developing here, ρ γ ,γ t:T

does not depend on the history feedbacks but reduces to the product ρ γ ,γ t:T = ρ t-1:t ⊗ . . . ⊗ ρ T -1:T .

(68)

Theorem 16 We assume to be in the setting of §2.1. We define the sequence of reduced value functions {V t } t∈ 0,T , where V t : X t → [0, +∞] for t ∈ 0, T , by

V T = K T and V t = B t+1:t V t+1 , ∀t ∈ 0, T -1 , (69)
where the reduced Bellman operator B t+1:t are given, for any t ∈ 0, T -1 , for any ϕ t+1 ∈ L 0 + (X t+1 ) and for any x t ∈ X t , by Then, the multistage (two-time-scale) stochastic optimization problem -formulated like in [START_REF] Carpentier | Time Block Decomposition of Multistage Stochastic Optimization Problems[END_REF] with the data in §E.1 -has a solution given by a dynamic programming equation at the slow scale. More precisely, let {V s } s∈S be a sequence of functions given by V s+ = Λ s+ and, for s ∈ S, by the backward induction

B
V s (x s ) = inf u (s + ,f ) ∈U (s + ,f ) W (s + ,f + ) ρ (s + ,f ):(s + ,f + ) ( dw (s + ,f + ) | w s + ) • • • inf u (s + , f -) ∈U (s + , f -) W (s + , f ) ρ (s + , f -):(s + , f ) ( dw (s + , f ) | w s + , w (s + ,f + ) , • • • , w (s + , f -) ) Λ s x s , (u (s ,f ) -, w (s ,f ) ) (s,f + ) (s ,f ) (s + ,f ) + V s + f s x s , (u (s ,f ) -, w (s ,f ) ) (s,f + ) (s ,f ) (s + ,f ) . ( 85
)
Then, the value of the optimization problem (6) is given by V s (x s ), where the initial condition x s corresponds to w 0 in (6), as stated by (81b).

Proof. The proof is an application of Theorem 8 with the help of Remarks 5 and 6. First, we have framed the multistage (two-time-scale) stochastic optimization problem in the formalism of §2.1 with the help of the extended timeline (79c). Second, we have by assumption a state reduction at times {(s, f )} s∈S by composition of the state dynamics. Moreover, as the slow time scale stochastic kernels given by Equation (80a) are constant, the state reduction across the slow time scale is compatible with the stochastic kernels (see Remark 6). We are thus able to apply Theorem 8 and obtain the slow time scale Bellman recursion (85) as a special case of Equation [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory. The society for industrial and applied mathematics and the mathematical programming society[END_REF]. This ends the proof.

Figure 4 :

 4 Figure 4: Procurement of crude oil over 3 months M 1 , M 2 and M 3 , where a circle • denotes purchase decisions and a square denotes consumption decisions

  u s , w s+1 ) ρ s:s+1 ( dw s+1 | h s ) (by definition (7a) of the Bellman operator) = inf us∈Us W s+1 ϕ s+1 (θ r (h r ), (h r+1:s , u s , w s+1 )) inf us∈Us W s+1 ρ s:s+1 ( dw s+1 | h s ) (by the induction assumption) = inf us∈Us W s+1 ϕ s+1 (θ r (h r ), (h r+1:s , u s , w s+1 )) inf us∈Us W s+1 ρ s:s+1 dw s+1 (θ r (h r ), h r+1:s ) (by compatibility of the stochastic kernel) = ϕ s θ r (h r ), h r+1:s , where ϕ s x r , h r+1:s = inf us∈Us W s+1

Table 1 :

 1 Computational time (in seconds) needed for solving the problem by both the mixing method and the pure scenario tree method, for different horizons 5 Two-time-scale optimization problems

	5 s

  is the maximal dam volume, S t is the volume (stock) of water at the beginning of period [t, t + 1[, A t+1 is the inflow water volume (rain, etc.)during [t, t + 1[, Q t is the turbined outflow volume during [t, t + 1[. The control variable Q t is decided at the beginning of period [t, t + 1[, chosen such that 0 ≤ Q t ≤ S t ,supposed to depend on the stock S t but not on the inflow water A t+1 (as A t+1 takes place during [t, t + 1[, hence materializes at t + 1, hence the time index t + 1). The min operation in Equation (38) ensures that the dam volume always remains below its maximal capacity S , but induces a nonlinearity in the dynamics. This nonlinear dynamics is an obstacle to apply stochastic dual dynamic programming (SDDP).

  , at the end of the time interval [t, t + 1[, when a next random variable W t+1 is revealed, the decision-maker has the possibility to make a tail decision U t+1 . This latter decision U t+1 can be thought as a recourse variable for a two stage stochastic optimization problem that would take place inside the time interval [t, t + 1[. Note that, because of the term (U t , U t+1 ) in the cost function L t and in the dynamics f t , considering the pair (U t , U t ) as the control variable at time t would not satisfy the assumptions of Theorem 8.

At the end of the time interval [t -1, t[, a random variable W t is revealed, and then, at the beginning of the time interval [t, t + 1[, the decision-maker makes a head decision U t . What is new -in comparison with the classical decision-hazard framework -is that

  1, Proposition 7.45, p. 175]. Proposition 15 The family {ρ γ s:t } s∈ r,t of stochastic kernels of Definition 14 has the flow property: ρ γ s:t ( dh t | h s ) = W s+1 ρ s:s+1 ( dw s+1 | h s )ρ γ s+1:t dh t h s , γ s (h s ), w s+1 , ∀s < t .

		(49)
	Proof. Let s < t. For any ϕ ∈ L 0 + (H t ), we have that
	Ht	ϕ(h s , h s+1:t )ρ γ s:t dh t h s

  3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are Borel spaces (control spaces); there are also feasible state-dependent control constraints that we do not present here; 4. (W t 0 , W t 0 ),. . . , (W T , W T ) are Borel spaces (noise); 5. f t : (X t ×U t ×W t , X t ⊗U t ⊗W t ) → (X t+1 , X t+1 ), for t ∈ t 0 , T -1 , are Borel-measurable mappings (dynamics); 6. ρ t:t+1 : X t × U t → ∆(W t+1 ), for t ∈ t 0 , T -1 , are Borel-measurable stochastic kernels (noise distributions); 7. L t : X t × U t → R, for t ∈ t 0 , T -1 , and K : X T → R are lower semianalytic functions (instantaneous and final costs).

  2. (Ω, F) is a measurable space (nature); 3. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are measurable spaces (control spaces); 4. (Y t 0 , Y t 0 ), . . . , (Y T -1 , Y T -1 ) are measurable spaces ("observation" spaces); 5. η t : (Ω × s∈ t 0 ,t U s , F ⊗ s∈ t 0 ,t U s ) → (U t , U t ) t∈ t 0 ,T -1 are measurable mappings ("measurement constraints"); 6. P is a probability on (Ω, F);7. j : (Ω × t∈ t 0 ,T -1 U t , F ⊗ t∈ t 0 ,T -1 U t ) → R + is a measurable function (criterion).With these ingredients, Yüksel formulates a stochastic team optimization problem whose solutions (policies) are to be searched among sequences of measurable mappings ("design constraints") Y t-1 → U t , and their "randomized" versions (so-called strategic measures). He establishes a dynamic programming equation, where the Bellman functions are function of probability distributions and where the minimization is done over proper design mappings. One objective of Yüksel is to set up a mathematical framework under which the dynamic programming equation is mathematically sound [AM10, Theorem 3.6]. < • • • < t N = T are the indices of multiple consecutive time blocks t 0 , t 1 , . . . , t N -1 , t N , with N ≥ 1 a natural number; 7. (X t j , X t j ) j∈ 0,N are Borel spaces (time block state spaces); 8. θ t j : W t 0 × The framework developed in the paper [AM2] is intermediate between the ones of Evstigneev in [AM3] and of Yüksel in [AM10] -notable by the absence of a state space -and the ones of Witsenhausen [AM6], Hernández-Lerma and Lasserre [AM4], Bertsekas and Shreve [AM 1] and Puterman [AM5] -where the state spaces are given for all times.

					Borel-measurable
	stochastic kernels (noise distributions);
	5. j : (W t 0 × T -1 s=t 0 (U s ×W s+1 ), W t 0 ⊗ T -1 s=t 0 (U s ⊗W s+1 )) → [0, +∞] is a nonnegative lower semianalytic function (criterion);
	6. t 0 t j -1 s=t 0 (U s × W s+1 ) → X t j	j∈ 1,N	and θ t 0 : W t 0 → X t 0 are Borel-measurable
	mappings (time block reduction of history towards state);
	9. f t j :t j+1 : X t j ×	t j+1 -1 s=t j (U s ×W s+1 ) → X t j+1	j∈ 0,N -1	are Borel-measurable mappings (time
	block dynamics).

Our approach. The ingredients that we use (in Sect. 2 and in Sect. 3) are the following:

1. time t ∈ t 0 , T is discrete and runs among a finite set of consecutive natural numbers; 2. (U t 0 , U t 0 ),. . . , (U T -1 , U T -1 ) are Borel spaces (control spaces); 3. (W t 0 , W t 0 ),. . . , (W T , W T ) are Borel spaces (noise); 4. ρ t:t+1 : W t 0 × t-1 s=t 0 (U s × W s+1 ) → ∆(W t+1 ), for t ∈ t 0 , T -1 , are

  s + , f -):(s + , f ) ( dw sf (s + , f ) | w s s + , w sf (s + ,f + ) , • • • , w sf (s + , f -) ) . (56)Then, with the notations given in §5.1 and using the probability definied in Equation (56), Problem[START_REF] Carpentier | Time Block Decomposition of Multistage Stochastic Optimization Problems[END_REF], may be rewritten asV s -(x s s -) = inf (s,f ):(s, f ) dw s s , dw sf (s,f + ) • • • dw sf (s, f -) , dw sf + = G sf (s,f ) (x sf (s,f ) , u sf (s,f ) , w sf (s,f ) + ) , ∀s ∈ S , ∀f ∈ F \ { f } ,(57b)x sf (s + ,f ) = G s s (x s s , u s s , w s s + ) , ∀s ∈ S \ {s} ,(57c)u s s = γ s {u (s ,f ) , w (s ,f ) + } (s ,f )≺(s, f ) , ∀s ∈ S \ {s} ,(57d)u sf (s,f ) = γ (s,f ) {u (s ,f ) , w (s ,f ) + } (s ,f )≺(s,f ) , ∀s ∈ S , ∀f ∈ F \ { f } . (57e)

	γ	W (s,f ):(s, f )	Λ s x s s
		+	s∈S	Λ s x s s -, u s s -, w s s , {x sf (s,f ) , u sf (s,f ) , w sf (s,f ) + }
				(s, f )	(57a)
	s.t. x sf (s,f )

f ∈F\{ f } ρ

  ). This leads to a reformulation of Problem (57) as a classical stochastic optimal control problem infE s∈S Λ s X s s -, U s s -, W s , {X sf (s,f ) , U sf (s,f ) , W f (s,f ) + } + = G sf (s,f ) (X sf (s,f ) , U sf (s,f ) , W sf (s,f ) + ) , ∀s ∈ S , ∀f ∈ F \ { f } ,(59b)X sf (s + ,f ) = G s s X s s , U s s , W s s + , ∀s ∈ S\{s} ,

	f ∈F\{ f }	+ Λ s X s s	(59a)
	s.t. X sf (s,f ) (59c)
	U s s ∈ U s s , ∀s ∈ S\{s} , σ(U s		(59d)

s ) ⊂ σ({W s s } s s , {W sf (s ,f ) } (s ,f ) (s, f ) ) , ∀s ∈ S\{s} ,

  and consider a nonnegative and lower semianalytic numerical function j :H T → [0, +∞] defined by j(h T ) = θ t (h t ), u t , w t+1 , u t+1 + K θ T (h T ) . (65)For t ∈ 0, T , we define value functions byV t (h t ) = inf γ ∈Γ t:T -1 ,γ ∈Γ t+1:T H T j(h T )ρ γ ,γ t:T ( dh T | h t ) , ∀h t ∈ H t ,has to be understood as ρ γ t:T (seeDefinition 14), withγ t (h t ) = γ t (h t ) , ∀h t ∈ H t ,(67a)γ t (h t ) = γ t (h t ), γ t h t , γ t (h t ) , ∀t ∈ t + 1, T -1 , ∀h t ∈ H t ,

	T -1
	t=0	L (66)
	where ρ γ ,γ t:T

t

  t+1:t ϕ t+1 (x t ) = inf u t ∈U t W t ρ t-1:t ( dw t ) inf u t+1 ∈U t+1 L t (x t , u t , w t+1 , u t+1 ) + ϕ t+1 f t (x t , u t , w t+1 , u t+1 ) .Then, the value function V 0 given in Equation (66) coincides with the value function V 0 .State reductions and slow time scale dynamics. Let {X s } s∈S be a sequence of Borel (state) spaces (where X s = W (s,f ) ), {θ s } s∈S be a sequence of Borel-measurable reduction mappings θ s : H (s,f ) → X s (where θ s = Id : H (s,f ) = W (s,f ) → X s = W (s,f ) ), and {f s } s∈S be a sequence of Borel-measurable dynamicsf s : X s × H (s,f + ):(s + ,f ) → X s + , ∀s ∈ S . (83)Cost functions. We suppose given a family {Λ s } s∈S of slow time scale nonnegative lower semianalytic cost functions, withΛ s : X s × H (s,f + ):(s + ,f ) → [0, +∞] , ∀s ∈ S (84a)and a slow time scale nonnegative lower semianalytic final cost function Λ s+Λ s : X s+ → [0, +∞] .(84b)With the slow time scale cost functions and final cost function, we make up, by summation, a (nonnegative lower semianalytic) cost criterion j : H (s + ,f ) → [0, +∞] given by j(h (s + ,f ) ) = Suppose that the family {X s } s∈S , {θ s } s∈S , {f s } s∈S is a state reduction across the consecutive time blocks [(s, f ), (s, f )], for s ∈ S (where we identify f (s,f ):(s, f ) = f s in Definition 4).

	(84c)
	E.2 Two-time-scale dynamic programming
	Proposition 17
	(70)

s∈S Λ s θ s (h (s,f ) ), h (s,f + ):(s + ,f ) + Λ s+ θ s+ (h (s + ,f ) .

The starting point of our reflections on this subject were conversations that three of us held with Roger Wets in Bogota in

We discussed the interest and the way of mixing the techniques of scenario trees (to be able to take into account correlated noises) with the techniques of dynamic programming (to have a vision of the optimal future costs by means of value functions).

We could also consider a cost criterion j : H t → R, either bounded function, or uniformly bounded below function. However, for the sake of simplicity, we will deal in the sequel with nonnegative numerical functions. The case j(h T ) = +∞ materializes joint constraints between uncertainties and controls in h T .

Notice that, if only the couple (θ r , f r:t ) is given, we can define the reduction mapping θ t by (9c), and thus obtain a triplet (θ r , θ t , f r:t ) which is a state reduction across r, t .

The proof uses[START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF] Lemma 7.30 (3,[START_REF] Birge | Aggregation bounds in stochastic linear programming[END_REF]] on the stability of lower semianalytic numerical functions under addition and under right composition with a Borel-measurable mapping.

We stress that the slow time scale dynamics (28a) yields as output the first fast state of the slow period (and not the next slow state). Thus, the slow time scale dynamics (28a) is not a dynamics from one slow state to the next slow state.

Here again, the formula (36) represents a nested sequence of infima of integrals (with respect to different stochastic kernels).

More precisely, the property (7b) is a consequence of the properties that i) the Bellman operator (7a) corresponds to the operator T (with g = 0 and α = 1) in[START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF] Definition

8.5, p. 195] ii) that T (J) is lower semianalytic whenever J also is, as explained right above[START_REF] Barty | Decomposition of large-scale stochastic optimal control problems[END_REF] Lemma 8.2, p. 196].

Acknowledgements. We thank Roger Wets for fruitful discussions about the possibility of mixing stochastic dynamic programming with progressive hedging.

A Technical details and proofs

We suppose to be in the framework of §2.1. We introduce the notations

Let 0 ≤ r ≤ s ≤ t ≤ T . From a history h t ∈ H t , we extract the (r : s)-history uncertainty part [h t ] W r:s = (w r , . . . , w s ) = w r:s ∈ W r:s , 0 ≤ r ≤ s ≤ t ,

the (r : s)-history control part (notice that the indices are special)

Flows. Let r and t be given such that 0 ≤ r < t ≤ T . For a (r : t -1)-history feedback γ = {γ s } s∈ r,t -1 ∈ Γ r:t-1 , we define the flow Φ γ r:t by Φ γ r:t : H r × W r+1:t → H t (45a) (h r , w r+1:t ) → h r , γ r (h r ), w r+1 , γ r+1 h r , γ r (h r ), w r+1 , w r+2 , • • • , γ t-1 (h t-1 ), w t .

the end of the time interval [t, t + 1[, when an uncertainty variable w t+1 is revealed, the decision-maker has the possibility to make a tail decision u t+1 . This latter decision u t+1 can be thought as a recourse variable for a two stage stochastic optimization problem that would take place inside the time interval [t, t + 1[. We call w 0 the uncertainty happening right before the first decision. The interplay between uncertainties and decisions is thus as follows (compare the chronology with the one in (2)):

History Spaces. For t ∈ 0, T , we define the head history space as the product Borel space

We also define, for t ∈ 1, T , the tail history space as the product Borel space

Stochastic kernels. We introduce a family {ρ t-1:t } t∈ 1,T of probability distributions (constant Borel-measurable stochastic kernels), with

History feedbacks. For t ∈ 0, T -1 , a head history feedback at time t is a universally measurable mapping

We call Γ t the set of head history feedbacks at time t, and we define Γ t:

We also define, for all t ∈ 1, T , a tail history feedback at time t as a universally measurable mapping γ t :

We call Γ t the set of tail history feedbacks at time t, and we define Γ t:

Value functions. Let {X t } t∈ 0,T (states) be sequences of Borel spaces with X 0 = W 0 . Let also be given Borel-measurable dynamics mappings

nonnegative lower semianalytic instantaneous cost functions

Proof. We embed the decision-hazard-decision structure as a particular case of multiple consecutive time blocks (of size 2) as in §3.2 in order to use Theorem 8 to obtain the reduced Bellman equation [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory. The society for industrial and applied mathematics and the mathematical programming society[END_REF] which boils down to Equation (70) in the decision-hazard-decision case. For each time t ∈ 1, T , we introduce a spurious uncertainty variable w t taking values in a singleton set W t = { w t }, so that we obtain the following chronology

Proceeding this way, we have doubled the timeline as time t has been "duplicated" in the ordered pair (t, ) and (t, ). We introduce new notations to explicitely deal with the new duplicated timeline. An element of the duplicated timeline is denoted by τ . For τ ∈ 0, 2T , we introduce the sets

For τ ∈ 0, 2T , we define the history space H τ as the product Borel space

Then, given the times τ i = 2i for i ∈ 0, T , we consider the consecutive time blocks τ i , τ i+1 , for i ∈ 0, T -1 whose union covers the doubled timeline. For i ∈ 0, T , we define the state spaces X τ i = X i . Using Equation (63a), we define a family of Borel-measurable dynamics {f τ i :τ i+1 } i∈ 0,T -1 by

We recursively define a family of Borel-measurable reduction mappings θ τ i : H t i → X t i by the following forward recursion for i ∈ 0, T -1

to obtain the family {X τ i } i∈ 0,T , {θ τ i } i∈ 0,T , {f τ i :τ i+1 } i∈ 0,T -1 which gives a state reduction across the consecutive time blocks τ i , τ i+1 , i ∈ 0, T -1 . It is worth noting that, for i ∈ 0, T , we have that θ τ i = θ i where the mapping θ i is defined in Equation (64). Now, for each i ∈ 1, T we consider the family of stochastic kernels {ρ i-1:i } i∈ 1,T given by Equation (61) which are probability distributions and the family of spurious stochastic kernels {ρ i-1:i } i∈ 1,T which are Dirac measures at fixed points { w i } i∈ 1,T . The state reduction across the consecutive time blocks τ i , τ i+1 is indeed compatible with the family {ρ τ -1:τ } τ ∈ 0,2T of stochastic kernels given by

Finally we introduce the familly of cost functions { τ i } i∈ 0,T , given by

Now, using Theorem 8 we obtain that the value function V 0 given in Equation (66) coincides with the value function Ṽ0 where the sequence of reduced value functions { Ṽτ i } i∈ 0,T , with Ṽτ i :

and where the reduced Bellman operator B τ i+1 :τ i across τ i , τ i+1 are given, for any i ∈ 0, N -1 , for any φτ i+1 ∈ L 0 + (X τ i+1 ) and for any x τ i ∈ X τ i , by Equation ( 19) that we reproduce here:

It remains to show that Equation (78) gives Equation (70) that is, for i ∈ 0, T -1 , B i+1:i = B τ i+1 :τ i and for i ∈ 0, T V i = Ṽτ i . Note that, using the definition of τ i+1 , we have that τ i+1 -1 = 2(i + 1) -1 = 2i + 1 = τ i + 1 and thus we only have two minimization problems in Equation (78). We obtain successively

(by ( 76) and (73)) = inf

from which the end of the proof follows.

E Two-time-scale dynamic programming

We present a framework for two-time-scale multistage optimization problems which is more general than in Sect. 5, as we do not require dynamics and states at the fast time-scale.

In §E.1, we detail the data needed to formulate the two-time-scale optimization problems that we consider. In §E.2, we show how to decompose such problems by slow time blocks.

E.1 Data for two-time-scale multistage optimization problem

Two time scales and unified extended timeline. We consider the same setting as in §5.1 in what regards the two time-scales S and

but with an extra final slow time s+ (with S = S ∪ {s + }) and the unified extended timeline S×F = (S×F) ∪ (s

Note that, at the difference of §5.1, as the state dynamics is only defined at the slow time scale, it is more convenient to add an extra final time s+ rather than an initial extra time (s -, f ). The extended timeline S×F can be identified with the time set 0, T , so that we are in the framework of §2.1.

In conformity with the above unified extended timeline -and, as in §3.2, we will consider state reduction on multiple consecutive time blocks, but in the special case where each block is made of all the fast time steps between two consecutive slow time steps -we define

[(s, f ), (s

Decision and uncertainty spaces, stochastic kernels. For the rest, to the difference with §5.1, we consider decision Borel spaces {U (s,f ) } (s,f )∈S×F , uncertainty Borel spaces {W (s,f ) } (s,f )∈S×F , stochastic kernels

Note that, for a given s ∈ S, each stochastic kernel ρ (s,f ) depends at most on the noises of the slow time block [(s, f ), (s, f )] in (79d). The (constant) assumption (80a) and the (single block) assumption (80b) correspond to stochastic independence between time blocks, and will be useful in the proof of Proposition 17.

History spaces. In conformity with the unified extended timeline (79c) and with the decision and uncertainty spaces, we deduce the history Borel spaces and the histories for all (s, f ) ∈ S×F

and, for suitable indices, the partial history sets and the partial histories

h (s,f ):(s ,f ) = (u (s ,f ) -, w (s ,f ) ) (s,f ) (s ,f ) (s ,f ) . (82b)