# Stochastic Finite State Control of POMDPs with LTL Specifications

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jan 2020.

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

- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [Risk-Averse Stochastic Shortest Path Planning](https://mlsanity.com/paper/2103.14727/) (2021)
- [Designing Behavior Trees from Goal-Oriented LTLf Formulas](https://mlsanity.com/paper/2307.06399/) (2023)
- [Risk-Averse Decision Making Under Uncertainty](https://mlsanity.com/paper/2109.04082/) (2021)
- [Optimal Control of Logically Constrained Partially Observable and Multi-Agent Markov Decision Processes](https://mlsanity.com/paper/2305.14736/) (2023)
- [Model-free Motion Planning of Autonomous Agents for Complex Tasks in Partially Observable Environments](https://mlsanity.com/paper/2305.00561/) (2023)
- [Belief-State Query Policies for User-Aligned POMDPs](https://mlsanity.com/paper/2405.15907/) (2024)
- [Optimal sensor deception in stochastic environments with partial observability to mislead a robot to a decoy goal](https://mlsanity.com/paper/2503.05972/) (2025)
- [Control Synthesis in Partially Observable Environments for Complex Perception-Related Objectives](https://mlsanity.com/paper/2507.02942/) (2025)
- [Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives](https://mlsanity.com/paper/2605.12581/) (2026)
- [HyPOLE: Hyperproperty-Guided Multi-Agent Reinforcement Learning under Partial Observation](https://mlsanity.com/paper/2606.30966/) (2026)

## Abstract (arXiv)

Partially observable Markov decision processes (POMDPs) provide a modeling framework for autonomous decision making under uncertainty and imperfect sensing, e.g. robot manipulation and self-driving cars. However, optimal control of POMDPs is notoriously intractable. This paper considers the quantitative problem of synthesizing sub-optimal stochastic finite state controllers (sFSCs) for POMDPs such that the probability of satisfying a set of high-level specifications in terms of linear temporal logic (LTL) formulae is maximized. We begin by casting the latter problem into an optimization and use relaxations based on the Poisson equation and McCormick envelopes. Then, we propose an stochastic bounded policy iteration algorithm, leading to a controlled growth in sFSC size and an any time algorithm, where the performance of the controller improves with successive iterations, but can be stopped by the user based on time or memory considerations. We illustrate the proposed method by a robot navigation case study.