This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

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

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
John Rust (Department of Economics Yale University)

Additional information is available for the following registered author(s):

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.

Download Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.

File URL: http://129.3.20.41/eps/comp/papers/9704/9704001.pdf
File Format: application/pdf
File Function:
Download Restriction: no
File URL: http://129.3.20.41/eps/comp/papers/9704/9704001.ps.gz
File Format: application/postscript
File Function:
Download Restriction: no

Publisher Info
Paper provided by EconWPA in its series Computational Economics with number 9704001.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length: 50 pages
Date of creation: 21 Apr 1997
Date of revision:
Handle: RePEc:wpa:wuwpco:9704001

Note: TeX file, Postscript version submitted, 50 pages
Contact details of provider:
Web page: http://129.3.20.41

For technical questions regarding this item, or to correct its listing, contact: (EconWPA).

Related research
Keywords:

Other versions of this item:

Find related papers by JEL classification:
C8 - Mathematical and Quantitative Methods - - Data Collection and Data Estimation Methodology; Computer Programs

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:

  1. Rust, John, 1985. "Stationary Equilibrium in a Market for Durable Assets," Econometrica, Econometric Society, vol. 53(4), pages 783-805, July. [Downloadable!] (restricted)
  2. Keane, Michael P & Wolpin, Kenneth I, 1994. "The Solution and Estimation of Discrete Choice Dynamic Programming Models by Simulation and Interpolation: Monte Carlo Evidence," The Review of Economics and Statistics, MIT Press, vol. 76(4), pages 648-72, November. [Downloadable!] (restricted)
    Other versions:
  3. John Rust, 1997. "Using Randomization to Break the Curse of Dimensionality," Econometrica, Econometric Society, vol. 65(3), pages 487-516, May.
    Other versions:
  4. Judd, Kenneth L., 1996. "Approximation, perturbation, and projection methods in economic analysis," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 12, pages 509-585 Elsevier. [Downloadable!] (restricted)
  5. Ariel Pakes & Paul McGuire, 1997. "Stochastic Algorithms for Dynamic Models: Markov Perfect Equilibrium, and the 'Curse' of Dimensionality," Cowles Foundation Discussion Papers 1144, Cowles Foundation, Yale University. [Downloadable!]
  6. Tauchen, George & Hussey, Robert, 1991. "Quadrature-Based Methods for Obtaining Approximate Solutions to Nonlinear Asset Pricing Models," Econometrica, Econometric Society, vol. 59(2), pages 371-96, March. [Downloadable!] (restricted)
  7. Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, March. [Downloadable!]
  8. Rust, John, 1986. "When Is It Optimal to Kill Off the Market for Used Durable Goods?," Econometrica, Econometric Society, vol. 54(1), pages 65-86, January. [Downloadable!] (restricted)
  9. Lars Peter Hansen & Ellen R. McGrattan & Thomas J. Sargent, 1994. "Mechanics of forming and estimating dynamic linear economies," Staff Report 182, Federal Reserve Bank of Minneapolis. [Downloadable!]
    Other versions:
  10. Tauchen, George, 1990. "Solving the Stochastic Growth Model by Using Quadrature Methods and Value-Function Iterations," Journal of Business & Economic Statistics, American Statistical Association, vol. 8(1), pages 49-51, January.
Full references

Cited by:
(explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)

  1. John Rust & Joseph Traub & Henryk Wozniakowski, 1999. "No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case," Computational Economics 9902001, EconWPA. [Downloadable!]
  2. Hugo Benitez-Silva, . "A Dynamic Model of Labor Supply, Consumption/Saving, and Annuity Decisions under Uncertainty," Department of Economics Working Papers 00-06, SUNY-Stony Brook, Department of Economics. [Downloadable!]
  3. Hugo Benitez-Silva, 2000. "A Joint Model of Labor Supply and Consumption Decisions Under Uncertainty," Econometric Society World Congress 2000 Contributed Papers 0196, Econometric Society. [Downloadable!]
  4. Jacek B. Krawczyk, 2000. "A Markovian Approximated Solution To A Portfolio Management Problem," Computing in Economics and Finance 2000 233, Society for Computational Economics. [Downloadable!]
  5. Ronald Goettler & Ron Shachar, 2000. "Estimating Product Characteristics and Spatial Competition in the Network Television Industry," Econometric Society World Congress 2000 Contributed Papers 1691, Econometric Society. [Downloadable!]
  6. Michael Reiter, 1997. "Solving Higher-Dimensional Continuous Time Stochastic Control Problems by Value Function Regression," Economics Working Papers 299, Department of Economics and Business, Universitat Pompeu Fabra, revised Jun 1998. [Downloadable!]
  7. Hugo Benítez-Silva, 2003. "The Annuity Puzzle Revisited," Working Papers wp055, University of Michigan, Michigan Retirement Research Center. [Downloadable!]
  8. George J. Hall & John Rust, 1999. "An Empirical Model of Inventory Investment by Durable Commodity Intermediaries," Cowles Foundation Discussion Papers 1228, Cowles Foundation, Yale University. [Downloadable!]
    Other versions:
Statistics
Access and download statistics

Did you know? Apart from a small start up grant in the 1990's, RePEc has received no funding and lives on the help of volunteers.

This page was last updated on 2009-10-17.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.