Optimal Control of Infinite Horizon Partially Observable Decision Processes Modeled As Generators of Probabilistic Regular Languages

Decision processes with incomplete state feedback have been traditionally modeled as Partially Observable Markov Decision Processes. In this paper, we present an alternative formulation based on probabilistic regular languages. The proposed approach generalizes the recently reported work on language measure theoretic optimal control for perfectly observable situations and shows that such a framework is far more computationally tractable to the classical alternative. In particular, we show that the infinite horizon decision problem under partial observation, modeled in the proposed framework, is $\epsilon$-approximable and, in general, is no harder to solve compared to the fully observable case. The approach is illustrated via two simple examples.