# Periodic agent-state based Q-learning for POMDPs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 24 of its 77 references that are in the map.
- First posted on arXiv 8 Jul 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [Mastering Atari with Discrete World Models](https://mlsanity.com/paper/2010.02193/) (2020)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [The Option-Critic Architecture](https://mlsanity.com/paper/1609.05140/) (2016)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Goal-Conditioned Reinforcement Learning with Imagined Subgoals](https://mlsanity.com/paper/2107.00541/) (2021)
- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [MICo: Improved representations via sampling-based state similarity for Markov decision processes](https://mlsanity.com/paper/2106.08229/) (2021)
- [Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes](https://mlsanity.com/paper/1302.1525/) (2013)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Solving POMDPs by Searching in Policy Space](https://mlsanity.com/paper/1301.7380/) (2013)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [Deep Hierarchical Reinforcement Learning Algorithm in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/1805.04419/) (2018)
- [The Reactor: A fast and sample-efficient Actor-Critic agent for Reinforcement Learning](https://mlsanity.com/paper/1704.04651/) (2017)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Efficient Learning and Planning with Compressed Predictive States](https://mlsanity.com/paper/1312.0286/) (2013)
- [Approximate information state based convergence analysis of recurrent Q-learning](https://mlsanity.com/paper/2306.05991/) (2023)
- [Reinforcement Learning in POMDPs with Memoryless Options and Option-Observation Initiation Sets](https://mlsanity.com/paper/1708.06551/) (2017)

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

- [Active Measuring in Reinforcement Learning With Delayed Negative Effects](https://mlsanity.com/paper/2510.14315/) (2025)
- [Learning to Hand Off: Provably Convergent Workflow Learning under Interface Constraints](https://mlsanity.com/paper/2605.19140/) (2026)
- [Convergence of regularized agent-state-based Q-learning in POMDPs](https://mlsanity.com/paper/2508.21314/) (2025)
- [Agent policies from higher-order causal functions](https://mlsanity.com/paper/2512.10937/) (2025)
- [Memoryless Policy Iteration for Episodic POMDPs](https://mlsanity.com/paper/2512.11082/) (2025)
- [Reinforcement Learning with Function Approximation for Non-Markov Processes](https://mlsanity.com/paper/2601.00151/) (2026)

## Abstract (arXiv)

The standard approach for Partially Observable Markov Decision Processes (POMDPs) is to convert them to a fully observed belief-state MDP. However, the belief state depends on the system model and is therefore not viable in reinforcement learning (RL) settings. A widely used alternative is to use an agent state, which is a model-free, recursively updateable function of the observation history. Examples include frame stacking and recurrent neural networks. Since the agent state is model-free, it is used to adapt standard RL algorithms to POMDPs. However, standard RL algorithms like Q-learning learn a stationary policy. Our main thesis that we illustrate via examples is that because the agent state does not satisfy the Markov property, non-stationary agent-state based policies can outperform stationary ones. To leverage this feature, we propose PASQL (periodic agent-state based Q-learning), which is a variant of agent-state-based Q-learning that learns periodic policies. By combining ideas from periodic Markov chains and stochastic approximation, we rigorously establish that PASQL converges to a cyclic limit and characterize the approximation error of the converged periodic policy. Finally, we present a numerical experiment to highlight the salient features of PASQL and demonstrate the benefit of learning periodic policies over stationary policies.