Convergence of Sample Path Optimal Policies for Stochastic Dynamic Programming

Loading...
Thumbnail Image

Files

TR_2005-84.pdf (181.79 KB)
No. of downloads: 986

Publication or External Link

Date

2005

Citation

DRUM DOI

Abstract

We consider the solution of stochastic dynamic programs using sample path estimates. Applying the theory of large deviations, we derive probability error bounds associated with the convergence of the estimated optimal policy to the true optimal policy, for finite horizon problems. These bounds decay at an exponential rate, in contrast with the usual canonical (inverse) square root rate associated with estimation of the value (cost-to-go) function itself. These results have practical implications for Monte Carlo simulation-based solution approaches to stochastic dynamic programming problems where it is impractical to extract the explicit transition probabilities of the underlying system model.

Notes

Rights