Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Nonapproximability results for partially observable Markov decision processes
Autore:
Lusena, C; Goldsmith, J; Mundhenk, M;
Indirizzi:
Univ Kentucky, Dept Comp Sci, Lexington, KY 40506 USA Univ Kentucky Lexington KY USA 40506 pt Comp Sci, Lexington, KY 40506 USA Univ Trier, FB Informat 4, D-54286 Trier, Germany Univ Trier Trier Germany D-54286 , FB Informat 4, D-54286 Trier, Germany
Titolo Testata:
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
, volume: 14, anno: 2001,
pagine: 83 - 113
SICI:
1076-9757(2001)14:<83:NRFPOM>2.0.ZU;2-S
Fonte:
ISI
Lingua:
ENG
Soggetto:
FINITE-HORIZON; COMPLEXITY;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
38
Recensione:
Indirizzi per estratti:
Indirizzo: Lusena, C Univ Kentucky, Dept Comp Sci, Lexington, KY 40506 USA Univ Kentucky Lexington KY USA 40506 i, Lexington, KY 40506 USA
Citazione:
C. Lusena et al., "Nonapproximability results for partially observable Markov decision processes", J ARTIF I R, 14, 2001, pp. 83-113

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 "unlesssome 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.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 23/01/20 alle ore 03:42:00