Robust Optimization is Hard. Try Bounded Backward Induction Instead.

Abstract

Worst-case sequential decision problems are notoriously difficult. Adjustable robust optimization models of such problems either oversimplify the decision rules to obtain tractability or become intractable outside convex settings. Motivated by these limitations, the paper introduces bounded backward induction, a method for computing optimal adaptive policies in finite-horizon max-min dynamic programs with finite state, action, and scenario sets. Analogous to branch-and-bound methods in mathematical programming, the approach prunes the decision tree using bounds on value functions. The paper develops a dual bounding framework, constructs lookahead policies with performance guarantees, and analyzes budget-style scenario sets. Applied to a media selection problem with yield uncertainty, the approach solves instances far beyond the reach of backward induction and provides managerial insight into the resulting decisions. We also extend many of the results to stochastic dynamic programming.