Advanced Search
MyIDEAS: Login to save this paper or follow this series

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

Contents:

Author Info

  • John Rust

    (Department of Economics Yale University)

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

If you experience problems downloading a file, check if you have the proper application to view it first. 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://128.118.178.162/eps/comp/papers/9704/9704001.pdf
Download Restriction: no

File URL: http://128.118.178.162/eps/comp/papers/9704/9704001.ps.gz
Download Restriction: no

Bibliographic Info

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

as in new window
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://128.118.178.162

Related research

Keywords:

Find related papers by JEL classification:

References

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.:
as in new window
  1. 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.
  2. 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.
  3. Michael P. Keane & Kenneth I. Wolpin, 1994. "The solution and estimation of discrete choice dynamic programming models by simulation and interpolation: Monte Carlo evidence," Staff Report 181, Federal Reserve Bank of Minneapolis.
  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.
  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 for Research in Economics, Yale University.
  6. Anderson, Evan W. & McGrattan, Ellen R. & Hansen, Lars Peter & Sargent, Thomas J., 1996. "Mechanics of forming and estimating dynamic linear economies," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 4, pages 171-252 Elsevier.
  7. Rust, John, 1985. "Stationary Equilibrium in a Market for Durable Assets," Econometrica, Econometric Society, vol. 53(4), pages 783-805, July.
  8. John Rust & Department of Economics & University of Wisconsin, 1994. "Using Randomization to Break the Curse of Dimensionality," Computational Economics 9403001, EconWPA, revised 04 Jul 1994.
  9. 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.
  10. Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, Spring.
Full references (including those not matched with items on IDEAS)

Citations

Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. George Hall & John Rust, 1999. "An Empirical Model of Inventory Investment by Durable Commodity Intermediaries," Macroeconomics 9904005, EconWPA.
  2. Jacek B. Krawczyk, 2000. "A Markovian Approximated Solution To A Portfolio Management Problem," Computing in Economics and Finance 2000 233, Society for Computational Economics.
  3. Hugo Benitez-Silva, 2000. "A Dynamic Model Of Labor Supply, Consumption/Saving, And Annuity Decisions Under Uncertainty," Computing in Economics and Finance 2000 128, Society for Computational Economics.
  4. Hugo Benítez-Silva, 2003. "The Annuity Puzzle Revisited," Working Papers wp055, University of Michigan, Michigan Retirement Research Center.
  5. 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.
  6. 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.
  7. John Rust & Joseph Traub & Henryk Wozniakowski, 1999. "No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case," Computational Economics 9902001, EconWPA.
  8. 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.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:wpa:wuwpco:9704001. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (EconWPA).

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.