# Memoryless Policy Iteration for Episodic POMDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 11 Dec 2025.

## Builds on (most cited first, 17 of 17)

- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Solving POMDPs by Searching in Policy Space](https://mlsanity.com/paper/1301.7380/) (2013)
- [POMDP inference and robust solution via deep reinforcement learning: An application to railway optimal maintenance](https://mlsanity.com/paper/2307.08082/) (2023)
- [Provable Partially Observable Reinforcement Learning with Privileged Information](https://mlsanity.com/paper/2412.00985/) (2024)
- [The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs](https://mlsanity.com/paper/2110.07409/) (2021)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)
- [PAC Reinforcement Learning with Rich Observations](https://mlsanity.com/paper/1602.02722/) (2016)
- [Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies](https://mlsanity.com/paper/1608.04996/) (2016)
- [Reinforcement Learning in POMDPs with Memoryless Options and Option-Observation Initiation Sets](https://mlsanity.com/paper/1708.06551/) (2017)
- [Future memories are not needed for large classes of POMDPs](https://mlsanity.com/paper/2205.02580/) (2022)
- [SOAP-RL: Sequential Option Advantage Propagation for Reinforcement Learning in POMDP Environments](https://mlsanity.com/paper/2407.18913/) (2024)
- [Reinforcement Learning in POMDP's via Direct Gradient Ascent](https://mlsanity.com/paper/2512.02383/) (2025)

## Abstract (arXiv)

Memoryless and finite-memory policies offer a practical alternative for solving partially observable Markov decision processes (POMDPs), as they operate directly in the output space rather than in the high-dimensional belief space. However, extending classical methods such as policy iteration to this setting remains difficult; the output process is non-Markovian, making policy-improvement steps interdependent across stages. We introduce a new family of monotonically improving policy-iteration algorithms that alternate between single-stage output-based policy improvements and policy evaluations according to a prescribed periodic pattern. We show that this family admits optimal patterns that maximize a natural computational-efficiency index, and we identify the simplest pattern with minimal period. Building on this structure, we further develop a model-free variant that estimates values from data and learns memoryless policies directly. Across several POMDPs examples, our method achieves significant computational speedups over policy-gradient baselines and recent specialized algorithms in both model-based and model-free settings.