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.
Assumption 2: finite random variables
The sample space is finite and discrete for each node
I think your “policy graph” modeling approach makes some sense. It’s clever, but appears niche—I only see this approach from your SDDP.jl. The mainstream jargon is still “scenario tree” (e.g. Shapiro’s book doi.org/10.1137/1.9780898718751).
I’ve just spent some time reading some typical references including
(SDDP) Pereira, M.V., Pinto, L.M.: Multi-stage stochastic optimization applied to energy planning. Math. Program. 52 (1–3), 359–375 (1991)
and a few other application articles.
My summary is:
All algorithms are based on a (finite) scenario tree that is built in advance before training.
If I’m drafting a paper to describe the inadequacy of the SDDP-like methods for multistage stochastic programming, I’ll definitely say
The scenario tree (discretization) model—as a bedrock of the algorithms—is a brutally inaccurate way to represent the real (maybe continuous) stochastic process.
The eventual training results do not directly constitute executable policies, since the real-world realization of uncertainties are not necessarily identical to one of the discretized states.
That’s why I said the question I raised in this topic is a “main concern”—your SDDP.jl also entails this discretization prerequisite.
The scenario tree (discretization) model—as a bedrock of the algorithms—is a brutally inaccurate way to represent the real (maybe continuous) stochastic process.
It’s a model. There are good models and bad models. It might have a large or a small impact on the quality of the final policy. Look up “SAA”. People have thought about this before.
The eventual training results do not directly constitute executable policies, since the real-world realization of uncertainties are not necessarily identical to one of the discretized states.
This is wrong. SDDP.jl gives you exactly an executable policy that you can evaluate “off-chain” or “out-of-sample” for realizations different than the realisations used during training. The entire reason I don’t like to use scenario tree in the context of SDDP is that SDDP is not solving a finite scenario tree. It is building a value function (with pros and cons) that can be used as a decision rule for new realisations that were never seen before.
If the uncertainty appears only in the right-hand side, then the value function is a valid lower relaxation of the true function you would have build if you had trained on the full distribution. If the uncertainty appears in the constraints or the objective, the value function is an approximation with no quality bounds.