Ir directamente a la navegación principal Ir directamente a la búsqueda Ir directamente al contenido principal

The complexity of policy evaluation for finite-horizon partially-observable markov decision processes

Producción científica: Conference contribution › revisión exhaustiva

9 Citas (Scopus)

Resumen

A partially-observable Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. We consider several flavors of finite-horizon POMDPs. Our results concern the complexity of the policy evaluation and policy existence problems, which are characterized in terms of completeness for complexity classes. We prove a new upper bound for the policy evaluation problem for POMDPs, showing it is complete for Probabilistic Logspace. From this, we prove policy existence problems for several variants of unobservable, succinctly represented MDPs to be complete for NPPP , a class for which not many natural problems are known to be complete.

Idioma originalEnglish
Título de la publicación alojadaMathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings
EditoresIgor Privara, Peter Ruzicka
Páginas129-138
Número de páginas10
DOI
EstadoPublished - 1997
Evento22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997 - Bratislava, Slovakia
Duración: ago 25 1997 → ago 29 1997

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen1295
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conference

Conference22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997
País/TerritorioSlovakia
CiudadBratislava
Período8/25/97 → 8/29/97

Nota bibliográfica

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1997.

Financiación

FinanciadoresNúmero del financiador
National Science Foundation (NSF)CCR-9315354, CCR-9509603

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Huella

    Profundice en los temas de investigación de 'The complexity of policy evaluation for finite-horizon partially-observable markov decision processes'. En conjunto forman una huella única.

    Citar esto