TITLE: Bridging Stochastic and Dynamic Programming: A Unified Framework for Sequential Decision Problems

SPEAKER: Warren Powell

ABSTRACT:

Stochastic programming and dynamic programming have thrived in different communities, largely motivated by different applications. Dynamic programming has long been associated with small-scale applications, plagued by the well-known “curse of dimensionality.” Stochastic programming, on the other hand, has been presented as a “richer framework” that scales to large-scale applications. In this talk, I will argue that both of these are myths. I will present a perspective that puts stochastic programming, “dynamic programming” and stochastic search into a common framework where all sequential decision problems are dynamic programs which can be solved using one of four classes of policies. I will offer a formal definition of a state variable (widely overlooked or even avoided in our community), and use this not only to show that “stochastic programming” is actually a form of dynamic programming, but also to show how widely used algorithmic strategies based on scenario trees can be streamlined. Ultimately, I hope to help provide students with a simple, easy-to-follow template for modeling stochastic dynamic problems which mimics the powerful language of mathematical programming.