Upper Bounds and Policy Quality in Multistage Stochastic Programming

In Multistage Stochastic Programming, one of the main objects are the value functions for each stage, encapsulating the expected future costs for a given state of the system. The SDDP algorithm of Pereira and Pinto produces lower estimates of the value functions at each stage, which in turn induces a multistage policy. In the risk-neutral setting, the cost of such a policy can be estimated by Monte-Carlo, and yields an upper bound for the optimal value of the problem. In the risk-averse case, due to the variable weighting of scenarios, such elementary estimates are not easily available, and a natural alternative is to construct upper bounds for the value functions themselves, which correspondingly model the risk-adjusted costs. This can be performed either with inner approximations or through the dual problem, which both require an estimate of the Lipschitz constant of the value functions. We show that both methods yield policies with guaranteed performance, and we illustrate them on numerical examples of energy planning problems.