The policy graph decomposition of multistage stochastic programming problems

We propose the policy graph as a structured way of formulating a general class of multistage stochastic programming problems in a way that leads to a natural decomposition. We also propose an extension to the stochastic dual dynamic programming algorithm to solve a subset of problems formulated as a policy graph. This subset includes discrete‐time, convex, infinite‐horizon, multistage stochastic programming problems with continuous state and control variables. To demonstrate the utility of our algorithm, we solve an existing multistage stochastic programming problem from the literature based on pastoral dairy farming. We show that the finite‐horizon model in the literature suffers from end‐of‐horizon effects, which we are able to overcome with an infinite‐horizon model.