Convergence of Sample Path Optimal Policies for Stochastic Dynamic Programming
Convergence of Sample Path Optimal Policies for Stochastic Dynamic Programming
Files
Publication or External Link
Date
2005
Authors
Fu, Michael C.
Jin, Xing
Advisor
Fu, Michael C.
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.