Optimality of affine policies in multi-stage robust optimization

In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, box-constrained, multi-stage robust optimization. Our results cover the finite horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. Our proof methodology, based on techniques from polyhedral geometry, is elegant and conceptually simple, and entails efficient algorithms for the case of piecewise affine state costs, when computing the optimal affine policies can be done by solving a single linear program.