# Learning Finite-State Controllers for Partially Observable Environments

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

## Key facts

- Cited by 18 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 23 Jan 2013.

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

- [UniVLA: Learning to Act Anywhere with Task-centric Latent Actions](https://mlsanity.com/paper/2505.06111/) (2025)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [Reinforcement Learning for Versatile, Dynamic, and Robust Bipedal Locomotion Control](https://mlsanity.com/paper/2401.16889/) (2024)
- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [Safe Policy Improvement for POMDPs via Finite-State Controllers](https://mlsanity.com/paper/2301.04939/) (2023)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy](https://mlsanity.com/paper/2407.07333/) (2024)
- [Cochain Perspectives on Temporal-Difference Signals for Learning Beyond Markov Dynamics](https://mlsanity.com/paper/2602.06939/) (2026)
- [RoVerFly: Robust and Versatile Implicit Hybrid Control of Quadrotor-Payload Systems](https://mlsanity.com/paper/2509.11149/) (2025)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)
- [Distributed Control using Reinforcement Learning with Temporal-Logic-Based Reward Shaping](https://mlsanity.com/paper/2203.04172/) (2022)
- [Reconciling Rewards with Predictive State Representations](https://mlsanity.com/paper/2106.03926/) (2021)
- [Learning What to Memorize: Using Intrinsic Motivation to Form Useful Memory in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2110.12810/) (2021)
- [How memory architecture affects learning in a simple POMDP: the two-hypothesis testing problem](https://mlsanity.com/paper/2106.08849/) (2021)
- [Reward Learning using Structural Motifs in Inverse Reinforcement Learning](https://mlsanity.com/paper/2209.13489/) (2022)
- [Anticipating Oblivious Opponents in Stochastic Games](https://mlsanity.com/paper/2409.11671/) (2024)
- [A Multi-Agent, Policy-Gradient approach to Network Routing](https://mlsanity.com/paper/2512.03211/) (2025)
- [Compositional Behavioral Semantics for State Abstraction in Reinforcement Learning](https://mlsanity.com/paper/2606.25357/) (2026)

## Abstract (arXiv)

Reactive (memoryless) policies are sufficient in completely observable Markov decision processes (MDPs), but some kind of memory is usually necessary for optimal control of a partially observable MDP. Policies with finite memory can be represented as finite-state automata. In this paper, we extend Baird and Moore's VAPS algorithm to the problem of learning general finite-state automata. Because it performs stochastic gradient descent, this algorithm can be shown to converge to a locally optimal finite-state controller. We provide the details of the algorithm and then consider the question of under what conditions stochastic gradient descent will outperform exact gradient descent. We conclude with empirical results comparing the performance of stochastic and exact gradient descent, and showing the ability of our algorithm to extract the useful information contained in the sequence of past observations to compensate for the lack of observability at each time-step.