Show simple item record

An Asymptotically Efficient Algorithm for Finite Horizon Stochastic Dynamic Programming Problems

dc.contributor.advisorFu, Michael C.en_US
dc.contributor.advisorMarcus, Steven I.en_US
dc.contributor.authorChang, Hyeong Sooen_US
dc.contributor.authorFu, Michael C.en_US
dc.contributor.authorMarcus, Steven I.en_US
dc.description.abstractWe 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.en_US
dc.format.extent259013 bytes
dc.relation.ispartofseriesISR; TR 2003-26en_US
dc.titleAn Asymptotically Efficient Algorithm for Finite Horizon Stochastic Dynamic Programming Problemsen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record