is it a prerequisite to restrict the number of uncertainty realizations in each stage to be finite, if I adopt a Markov-SDDP algorithm to tackle a multistage stochastic program?
, who answered:
Short answer: No — finiteness of the true uncertainty is not a mathematical prerequisite for Markovian SDDP. What you do need is a finite sampled support per iteration and a finite Markov state space for the dynamic program you are approximating.
I can’t believe its answer.
I think:
to carry out a Markov-SDDP algorithm on a computer, we need to construct a concrete finite scenario tree (in the form of transition probabilities across a series of discrete uncertainty states) beforehand. Otherwise how can we store infinitely many cutting plane surrogates?
The short answer seems pretty reasonable to me. In SDDP.jl we require a finite sample space chosen a priori, but this isn’t strictly necessary. If the uncertainty appears only in the right-hand side of linear constraints you could sample from the true continuous distribution on the backward pass and still obtain a valid lower bound on the policy. There are various open questions in the literature about whether the algorithm would converge etc, but that’s a different topic.
Let’s please keep this forum focused on Julia-, JuMP-, and in this case, SDDP.jl-related questions. I don’t think that theoretical details of the SDDP algorithm are on-topic.
First it’s not only theoretic, but also algorithmic, directly affecting how we organize julia/JuMP/SDDP.jl code. Second it’s not detail but basic concerns when we are dealing with real-world problems.
You probably hadn’t got my idea, I guess.
For canonical SDDPs (i.e. assuming stagewise independence), we have only one cost-to-go function at each stage. Whereas for Markovian SDDPs, there are cardinality-of-support-ly many cost-to-go functions, each one should be associated with a cutting plane surrogate.
If we don’t pre-build a deterministic scenario tree which is used throughout the entire training, we would require (possibly) infinitely many cutting plane models? That’s where I find the bot’s answer questionable.
You need a finite number of nodes in the graph, but within a node you could have a continuous sample space for the nodewise-independent random variable. There are two sources of uncertainty (the Markov chain driving transitions between the nodes, and the random variable within a node), and they are treated separately in the algorithm.
In theory it’s also possible to dynamically add new nodes to the graph during the iterations, and you could construct an out-of-sample policy for an “off-chain” node on a forward pass by interpolating between some of the finite value functions. This is effectively what we do with the objective state and partially observable algorithms.
I don’t find it useful to talk about scenario trees in the context of SDDP.