A Comparison of Policy Iteration Methods for Solving Continuous-State, Infinite-Horizon Markovian Decision Problems Using Random, Quasi-random, and Deterministic Discretizations
AbstractThis 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 InfoIf 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.
Bibliographic InfoPaper provided by EconWPA in its series Computational Economics with number 9704001.
Length: 50 pages
Date of creation: 21 Apr 1997
Date of revision:
Note: TeX file, Postscript version submitted, 50 pages
Contact details of provider:
Web page: http://18.104.22.168
Find related papers by JEL classification:
- C8 - Mathematical and Quantitative Methods - - Data Collection and Data Estimation Methodology; Computer Programs
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.:
- John Rust & Department of Economics & University of Wisconsin, 1994.
"Using Randomization to Break the Curse of Dimensionality,"
9403001, EconWPA, revised 04 Jul 1994.
- John Rust, 1997. "Using Randomization to Break the Curse of Dimensionality," Econometrica, Econometric Society, vol. 65(3), pages 487-516, May.
- 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.
- Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, January.
- Lars Peter Hansen & Ellen R. McGrattan & Thomas J. Sargent, 1994.
"Mechanics of forming and estimating dynamic linear economies,"
182, Federal Reserve Bank of Minneapolis.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Rust, John, 1985. "Stationary Equilibrium in a Market for Durable Assets," Econometrica, Econometric Society, vol. 53(4), pages 783-805, July.
- 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.
- Reiter, Michael, 1999. "Solving higher-dimensional continuous-time stochastic control problems by value function regression," Journal of Economic Dynamics and Control, Elsevier, vol. 23(9-10), pages 1329-1353, September.
- George J. Hall & John Rust, 1999.
"An Empirical Model of Inventory Investment by Durable Commodity Intermediaries,"
Cowles Foundation Discussion Papers
1228, Cowles Foundation for Research in Economics, Yale University.
- Hall, George & Rust, John, 2000. "An empirical model of inventory investment by durable commodity intermediaries," Carnegie-Rochester Conference Series on Public Policy, Elsevier, vol. 52(1), pages 171-214, June.
- George Hall & John Rust, 1999. "An Empirical Model of Inventory Investment by Durable Commodity Intermediaries," Macroeconomics 9904005, EconWPA.
- Hugo Benítez-Silva, 2003. "The Annuity Puzzle Revisited," Working Papers wp055, University of Michigan, Michigan Retirement Research Center.
- John Rust & Joseph Traub & Henryk Wozniakowski, 1999. "No Curse of Dimensionality for Contraction Fixed Points Even in the Worst Case," Computational Economics 9902001, EconWPA.
- 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.
- Jacek B. Krawczyk, 2000. "A Markovian Approximated Solution To A Portfolio Management Problem," Computing in Economics and Finance 2000 233, Society for Computational Economics.
- 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.
- 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.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (EconWPA).
If references are entirely missing, you can add them using this form.