What question did this study set out to answer?

This research aims to create a robust dynamic programming formulation to reduce sensitivity to uncertainty in transition probabilities.

May 1, 2005

Robust Dynamic Programming

Key Points

This research aims to create a robust dynamic programming formulation to reduce sensitivity to uncertainty in transition probabilities.
Developed a robust formulation for discrete time dynamic programming (DP) with ambiguous transition probabilities.
Proven results for finite and infinite horizon DP using a rectangularity property in sets of conditional measures.
Utilized techniques from previous studies to construct suitable sets of measures for optimal policy determination.
Proved that the robust formulation can extend known DP results to accommodate ambiguity.
Established that robust dynamic programming corresponds to stochastic zero-sum games with perfect information.

Abstract

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.

Mark Helpful

Bookmark

Relay