Information Relaxations and Duality in Stochastic Dynamic Programs

TLDR

Complex stochastic dynamic programs, such as inventory control and option pricing, are difficult to solve optimally. The paper introduces a duality‑based technique that relaxes nonanticipativity constraints to compute upper bounds on stochastic dynamic program values, aiming to simplify solution of complex problems. The method relaxes nonanticipativity by adding penalties for violations and studies penalty properties to derive dual bounds. The dual bounds complement simulation‑based lower bounds, and in inventory control and option pricing examples they are tight and computationally efficient.

Abstract

We describe a general technique for determining upper bounds on maximal values (or lower bounds on minimal costs) in stochastic dynamic programs. In this approach, we relax the nonanticipativity constraints that require decisions to depend only on the information available at the time a decision is made and impose a “penalty” that punishes violations of nonanticipativity. In applications, the hope is that this relaxed version of the problem will be simpler to solve than the original dynamic program. The upper bounds provided by this dual approach complement lower bounds on values that may be found by simulating with heuristic policies. We describe the theory underlying this dual approach and establish weak duality, strong duality, and complementary slackness results that are analogous to the duality results of linear programming. We also study properties of good penalties. Finally, we demonstrate the use of this dual approach in an adaptive inventory control problem with an unknown and changing demand distribution and in valuing options with stochastic volatilities and interest rates. These are complex problems of significant practical interest that are quite difficult to solve to optimality. In these examples, our dual approach requires relatively little additional computation and leads to tight bounds on the optimal values.