Readers of this list may be interested in the following article that was
just published in JAIR:
Lusena, C., Goldsmith, J. and Mundhenk, M. (2001)
"Nonapproximability Results for Partially Observable Markov Decision
Processes",
Volume 14, pages 83-103.
Available in PDF, PostScript and compressed PostScript.
For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/lusena01a.html
More detailed instructions are below.
Abstract: We show that for several variations of partially observable
Markov decision processes, polynomial-time algorithms for finding
control policies are unlikely to or simply don't have guarantees of
finding policies within a constant factor or a constant summand of
optimal. Here ``unlikely'' means ``unless some complexity classes
collapse,'' where the collapses considered are P=NP, P=PSPACE, or
P=EXP. Until or unless these collapses are shown to hold, any
control-policy designer must choose between such performance
guarantees and efficient computation.
The article is available via:
-- comp.ai.jair.papers (also see comp.ai.jair.announce)
-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/
For direct access to this article and related files try:
http://www.jair.org/abstracts/lusena01a.html
-- Anonymous FTP from either of the two sites below.
Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume14/lusena01a.ps
The University of Genoa (Italy):
ftp://ftp.mrg.dist.unige.it/pub/jair/pub/volume14/lusena01a.ps
The compressed PostScript file is named lusena01a.ps.Z (247K)
For more information about JAIR, visit our WWW or FTP sites, or
contact [EMAIL PROTECTED]
