Digital Repository at the University of Maryland (DRUM)  >
Institute for Systems Research  >
Institute for Systems Research Technical Reports 

Please use this identifier to cite or link to this item:

Title: An Asymptotically Efficient Algorithm for Finite Horizon Stochastic Dynamic Programming Problems
Authors: Chang, Hyeong Soo
Fu, Michael C.
Marcus, Steven I.
Advisors: Fu, Michael C.
Marcus, Steven I.
Department/Program: ISR
Type: Technical Report
Keywords: NULL
Issue Date: 2003
Series/Report no.: ISR; TR 2003-26
Abstract: We present a novel algorithm, called ``Simulated Annealing Multiplicative Weights", for approximately solving large finite-horizon stochastic dynamic programming problems. The algorithm is ``asymptotically efficient" in the sense that a finite-time bound for the sample mean of the optimal value function over a given finite policy space can be obtained, and the bound approaches the optimal value as the number of iterations increases.The algorithm updates a probability distribution over the given policy space with a very simple rule, and the sequence of distributions generated by the algorithm converges to a distribution concentrated only on the optimal policies for the given policy space. We also discuss how to reduce the computational cost of the algorithm to apply it in practice.
Appears in Collections:Institute for Systems Research Technical Reports

Files in This Item:

File Description SizeFormatNo. of Downloads
TR_2003-26.pdf252.94 kBAdobe PDF491View/Open

All items in DRUM are protected by copyright, with all rights reserved.


DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments