# POMDPs under Probabilistic Semantics

arXiv: https://arxiv.org/abs/1408.2058 · HTML: https://mlsanity.com/paper/1408.2058/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2014.

## Built on by (most cited first, 1 of 1)

- [Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning](https://mlsanity.com/paper/2105.01225/) (2021)

## Abstract (arXiv)

We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) quantitative constraint defines the set of paths where the payoff is at least a given threshold lambda_1 in (0,1]; and (ii) qualitative constraint which is a special case of quantitative constraint with lambda_1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraint are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraint we show that the problem of deciding the existence of a finite-memory controller is undecidable.