This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Iyengar, G. N. Search for Related Content

Robust Dynamic Programming

IEOR Department, Columbia University, New York, New York 10027
garud{at}ieor.columbia.edu, http://www.columbia.edu/~gi10

In this paper we propose a robust formulation for discrete time dynamic programming (DP). The objective of the robust formulation is to systematically mitigate the sensitivity of the DP optimal policy to ambiguity in the underlying transition probabilities. The ambiguity is modeled by associating a set of conditional measures with each state-action pair. Consequently, in the robust formulation each policy has a set of measures associated with it. We prove that when this set of measures has a certain "rectangularity" property, all of the main results for finite and infinite horizon DP extend to natural robust counterparts. We discuss techniques from Nilim and El Ghaoui [17] for constructing suitable sets of conditional measures that allow one to efficiently solve for the optimal robust policy. We also show that robust DP is equivalent to stochastic zero-sum games with perfect information.

Key Words: dynamic programming; robust optimization; Markov decision processes; ambiguity
History: Received: December 17, 2002; revision received: October 10, 2003;revision received: June 11, 2004;

This article has been cited by other articles:

				B. Sandikci, L. M. Maillart, A. J. Schaefer, O. Alagoz, and M. S. Roberts Estimating the Patient's Price of Privacy in Liver Transplantation Operations Research, November 1, 2008; 56(6): 1393 - 1410. [Abstract] [PDF]

				A. Ben-Tal, B. Golany, A. Nemirovski, and J.-P. Vial Retailer-Supplier Flexible Commitments Contracts: A Robust Optimization Approach MSOM, January 1, 2005; 7(3): 248 - 271. [Abstract] [PDF]