Reinforcement Learning with Function Approximation for Non-Markov Processes
On the map: Deep reinforcement learning methods → RL theory and sample complexity
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.
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.
Builds on
10 of 25 references.
Closest ancestors · 1
Same direction, newest first
Other references · 9
- 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 43
- 2020Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processescited by 23
- 2021Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stabilitycited by 22
- 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 16
- 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuitycited by 11
- 2022Reinforcement Learning in Non-Markovian Environmentscited by 10
- 2023Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environmentscited by 7
- 2018Weak Feller Property of Non-linear Filterscited by 6
- 2024A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimizationcited by 4
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2025Learning POMDPs with Linear Function Approximation and Finite Memory
- 2026Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergence
- 2026Reinforcement Learning for Discounted and Ergodic Control of Diffusion Processes
- 2026Mathematical methods of reinforcement learning
- 2025Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spaces
- 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem
- 2026Continuous-time reinforcement learning: ellipticity enables model-free value function approximation
- 2024On Bellman equations for continuous-time policy evaluation I: discretization and approximation