archive of the former site EconWPA.wustl.edu

Please do not link or reference this page. Use one of the following URLs:
ideas.repec.org as http://ideas.repec.org/p/wpa/wuwpco/9704001.html
econpapers.repec.org as http://econpapers.repec.org/paper/wpawuwpco/9704001.htm

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

 
Paper:ewp-comp/9704001
From: John Rust <   > 
Date: Mon, 21 Apr 1997 22:09:06 GMT

Abstract:
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.

Postscript files:(viewing .ps)
      archive: 9704001.ps  or 9704001.ps.gz  is 5311957 bytes, 8-23-97.
Acrobat pdf files:(viewing .pdf)
      archive: 9704001.pdf  is 12853648 bytes, 3-22-97, or 9704001.pdf.gz 
Access statistics for this paper at LogEc which is a part of the RePEc project as was/is EconWPA.
Translate to another language with babel.altavista.com EconWPA reference ewp-comp/9704001
RePEc reference RePEc:wpa:wuwpco:9704001 send e-mail to

EconWPA began as a conversation between Bob Parks and Larry Blume on January 28, 1993. I located Paul Ginsparg's archive (then xxx.lanl.gov) and he graciously installed his software on a Sun Sparc system which was supporting the department of economics email and computation. EconWPA began accepting papers July 1, 1993 and had ftp, email, gopher and web interfaces. The web interface for submissions was engineered into existence in July 1995. A complete and catastrophic machine failure in 1999 caused the loss of EconWPA's email new paper announcment service at which time there were over 15,000 subscriptions with over 8,000 unique email addresses.

In 2005, Arts and Sciences commandeered the computing services that I had provided to the Department of Economics since 1987. Some might say that the department was sold out, others would (erroneously) claim that centralization is efficient, and still others would claim that I have few marketing skills.

I was told that I could keep operating EconWPA (as well as many other services including rfe.wustl.edu, barnett.wustl.edu, and three RePEc servers) but I would receive no support (hardware, software, or anthing else) and (as had been the case) no compensation. At that point, given the apparent low valuation of my activities by the department, and university, it made no sense for me to continue operating EconWPA or other services.

Thanks to all who have supported EconWPA in the past.

A Chinese curse states May you live in intersting times. I have. Bob Parks - Jan 2006