Complexity Bounds for Deterministic Partially Observed Markov Decision Processes

Cyrille Vessaire (), Pierre Carpentier (), Jean-Philippe Chancelier (), Michel Lara () and Alejandro Rodríguez-Martínez ()
Additional contact information
Cyrille Vessaire: CERMICS, École des Ponts ParisTech
Pierre Carpentier: UMA, ENSTA Paris, IP Paris
Jean-Philippe Chancelier: CERMICS, École des Ponts ParisTech
Michel Lara: CERMICS, École des Ponts ParisTech
Alejandro Rodríguez-Martínez: TotalEnergies SE

Annals of Operations Research, 2025, vol. 344, issue 1, No 12, 345-382

Abstract: Abstract Partially Observed Markov Decision Processes (Pomdp) share the structure of Markov Decision Processs (Mdp) — with stages, states, actions, probability transitions, rewards — but for the notion of solutions. In a Pomdp, observation mappings provide partial and/or imperfect knowledge of the state, and a policy maps observations (and not states like in a Mdp) towards actions. Theroretically, a Pomdp can be solved by Dynamic Programming (DP), but with an information state made of probability distributions over the original state, hence DP suffers from the curse of dimensionality, even in the finite case. This is why, authors like (Littman, M. L. 1996). Algorithms for Sequential Decision Making. PhD thesis, Brown University) and (Bonet, B. 2009). Deterministic POMDPs revisited. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI ’09 (pp. 59-66). Arlington, Virginia, USA. AUAI Press) have studied the subclass of so-called Deterministic Partially Observed Markov Decision Processes (Det-Pomdp), where transitions and observations mappings are deterministic. In this paper, we improve on Littman’s complexity bounds. We then introduce and study a more restricted class, Separated Det-Pomdps, and give some new complexity bounds for this class.

Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06282-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:344:y:2025:i:1:d:10.1007_s10479-024-06282-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06282-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().