# Reinforcement Learning with Function Approximation for Non-Markov Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 1 Jan 2026.

## 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, 10 of 10)

- [Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States](https://mlsanity.com/paper/2102.05261/) (2021)
- [Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2010.07452/) (2020)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency](https://mlsanity.com/paper/2204.09787/) (2022)
- [Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity](https://mlsanity.com/paper/2111.06781/) (2021)
- [Reinforcement Learning in Non-Markovian Environments](https://mlsanity.com/paper/2211.01595/) (2022)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Weak Feller Property of Non-linear Filters](https://mlsanity.com/paper/1812.05509/) (2018)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)

## Abstract (arXiv)

We study reinforcement learning methods with linear function approximation under non-Markov state and cost processes. We first consider the policy evaluation method and show that the algorithm converges under suitable ergodicity conditions on the underlying non-Markov processes. Furthermore, we show that the limit corresponds to the fixed point of a joint operator composed of an orthogonal projection and the Bellman operator of an auxiliary Markov decision process. For Q-learning with linear function approximation, as in the Markov setting, convergence is not guaranteed in general. We show, however, that for the special case where the basis functions are chosen based on quantization maps, the convergence can be shown under similar ergodicity conditions. Finally, we apply our results to partially observed Markov decision processes, where finite-memory variables are used as state representations, and we derive explicit error bounds for the limits of the resulting learning algorithms.