# Reinforcement Learning in Non-Markovian Environments

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 3 Nov 2022.

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

- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Deep Variational Reinforcement Learning for POMDPs](https://mlsanity.com/paper/1806.02426/) (2018)
- [Epistemic Neural Networks](https://mlsanity.com/paper/2107.08924/) (2021)
- [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)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Lifelong Learning with a Changing Action Set](https://mlsanity.com/paper/1906.01770/) (2019)

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

- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)
- [Approximate information state based convergence analysis of recurrent Q-learning](https://mlsanity.com/paper/2306.05991/) (2023)
- [Constructing Non-Markovian Decision Process via History Aggregator](https://mlsanity.com/paper/2506.24026/) (2025)
- [Convergence of regularized agent-state-based Q-learning in POMDPs](https://mlsanity.com/paper/2508.21314/) (2025)
- [Lattice Annotated Temporal (LAT) Logic for Non-Markovian Reasoning](https://mlsanity.com/paper/2509.02958/) (2025)
- [Reinforcement Learning with Function Approximation for Non-Markov Processes](https://mlsanity.com/paper/2601.00151/) (2026)
- [Stochastic approximation in non-markovian environments revisited](https://mlsanity.com/paper/2603.21091/) (2026)
- [Adaptive Agent Design](https://mlsanity.com/paper/2609.12486/) (2026)

## Abstract (arXiv)

Motivated by the novel paradigm developed by Van Roy and coauthors for reinforcement learning in arbitrary non-Markovian environments, we propose a related formulation and explicitly pin down the error caused by non-Markovianity of observations when the Q-learning algorithm is applied on this formulation. Based on this observation, we propose that the criterion for agent design should be to seek good approximations for certain conditional laws. Inspired by classical stochastic control, we show that our problem reduces to that of recursive computation of approximate sufficient statistics. This leads to an autoencoder-based scheme for agent design which is then numerically tested on partially observed reinforcement learning environments.