A Comparison of Policy Iteration Methods for Solving Continuous-State, Infinite-Horizon Markovian Decision Problems Using Random, Quasi-random, and Deterministic Discretizations

John Rust ()

Computational Economics from EconWPA

Abstract: This paper compares the performance of the Howard (1960) policy iteration algorithm for infinite-horizon continuous-state Markovian decision processes (MDP's) using alternative random, quasi- random, and deterministic discretizations of the state space, or grids. Each grid corresponds to an embedded finite state MDP whose solution is used to approximate the solution to the original continuous-state Markovian decision process. I extend a result of Rust (1997), to show that policy iteration using random grids succeeds in breaking the curse of dimensionality involved in approximating the solution to a class of continuous-state discrete-action MDP's known as discrete decision processes (DDP's). I compare this ``random policy iteration algorithm'' (RPI) with policy iteration algorithms using deterministically chosen grids including uniform grids and quadrature grids both of which are subject to the curse of dimensionality. I also compare the RPI algorithm to deterministic policy iteration algorithms based on quasi-random or `low discrepancy grids' such as the Sobol' and Tezuka sequences.

JEL-codes: C8 (search for similar items in EconPapers)
Date: 1997-04-21
Note: TeX file, Postscript version submitted, 50 pages
View list of references View citations in EconPapers

Downloads: (external link)
http://129.3.20.41/eps/comp/papers/9704/9704001.pdf (application/pdf)
http://129.3.20.41/eps/comp/papers/9704/9704001.ps.gz (application/postscript)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: http://EconPapers.repec.org/RePEc:wpa:wuwpco:9704001

Access Statistics for this paper

More papers in Computational Economics from EconWPA
Series data maintained by EconWPA ().