Refined Bounds on Near Optimality Finite Window Policies in POMDPs and Their Reinforcement Learning
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
Finding optimal policies for Partially Observable Markov Decision Processes (POMDPs) is challenging due to their uncountable state spaces when transformed into fully observable Markov Decision Processes (MDPs) using belief states. Traditional methods such as dynamic programming or policy iteration are difficult to apply in this context, necessitating the use of approximation methods on belief states or other techniques. Recently, in (Journal of Machine Learning Research, vol. 23, pp. 1-46, 2022) and (Mathematics of Operations Research, vol. 48, pp. 2066-2093, Nov. 2023), it was shown that sliding finite window based policies are near-optimal for POMDPs with standard Borel valued hidden state spaces, and can be learned via reinforcement learning, with error bounds explicitly dependent on a uniform filter stability term involving total variation in expectation and sample path-wise, respectively. In this paper, we refine these performance bounds and (i) extend them to bounds via uniform filter stability in expected Wasserstein distance leading to an error bound in expectation, and (ii) complementary conditions bounds via uniform filter stability in sample path-wise total variation distance leading to a uniform error bound. We present explicit examples. Our approach thus provides complementary and more refined bounds on the error terms in both total variation and Wasserstein metrics, offering more relaxed and stronger bounds over the approximation error in POMDP solutions on the performance and near optimality of sliding finite window control policies.
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 11 of its 33 references that are in the map. First posted on arXiv 6 Sep 2024.
Builds on
11 of 33 references.
References · 11
- 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
- 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
- 2015Asymptotic Optimality of Finite Approximations to Markov Decision Processes with Borel Spacescited by 14
- 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuitycited by 11
- 2023Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environmentscited by 7
- 2014Partially Observable Total-Cost Markov Decision Processes with Weakly Continuous Transition Probabilitiescited by 6
- 2018Weak Feller Property of Non-linear Filterscited by 6
- 2017Finite Model Approximations for Partially Observed Markov Decision Processes with Discounted Costcited by 4
- 2021Markov Decision Processes with Incomplete Information and Semi-Uniform Feller Transition Probabilitiescited by 2
- 2022Equivalent Conditions for Weak Continuity of Nonlinear Filterscited by 1
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Near Optimal Approximations and Finite Memory Policies for POMPDs with Continuous Spaces ↗
- 2024Partially Observed Optimal Stochastic Control: Regularity, Optimality, Approximations, and Learning
- 2025Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs
- 2025Scalable Policy-Based RL Algorithms for POMDPs
- 2025Learning POMDPs with Linear Function Approximation and Finite Memory
- 2023Safe Policy Improvement for POMDPs via Finite-State Controllers
- 2025Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spaces
- 2026Reinforcement Learning under State and Outcome Uncertainty: A Foundational Distributional Perspective