Duality of upper bounds in stochastic dynamic programming

For multistage stochastic programming problems with stagewise independent uncertainty, dynamic programming algorithms calculate polyhedral approximations for the value functions at each stage.  The SDDP algorithm provides piecewise linear lower bounds, in the spirit of the L-shaped algorithm, and corresponding upper bounds took a longer time to appear.  One strategy uses the primal dynamic programming recursion to build inner approximations of the value functions, while a second one builds lower approximations for the conjugate of the value functions.  The resulting dynamic programming recursion for the conjugate value functions do not decompose over scenarios, which suggests a Lagrangian relaxation.  We prove that this Lagrangian relaxation corresponds exactly to the inner upper bounds for a natural choice of multipliers.