  This paper presents an algorithmic study and complexity analysis for solving
distributionally robust multistage convex optimization (DR-MCO). We generalize
the usual consecutive dual dynamic programming (DDP) algorithm to DR-MCO and
propose a new nonconsecutive DDP algorithm that explores the stages in an
adaptive fashion. We introduce dual bounds in the DDP recursions to prevent the
growth of Lipschitz constants of the dual approximations caused by recursive
cutting plane methods. We then provide a thorough subproblem-oracle-based
complexity analysis of the proposed algorithms, proving both upper complexity
bounds and a matching lower bound. To the best of our knowledge, this is the
first nonasymptotic complexity result for DDP-type algorithms on DR-MCO, which
reveals that in some practical settings the new nonconsecutive DDP algorithm
scales linearly with respect to the number of stages. Numerical examples are
given to show the effectiveness of the proposed nonconsecutive DDP algorithm
and the dual-bounding technique, including the reduction of the computation
time or the number of subproblem oracle evaluations, and the capability to
solve problems without relatively complete recourse.
