Scalable Policy-Based RL Algorithms for POMDPs

AI summary

Overview

Research area: Reinforcement learning theory, specifically partially observable reinforcement learning (PORL), approximate MDP transformations, temporal-difference (TD) learning, and policy optimization.

Technical level: Advanced. The paper is a theoretical machine learning paper built around lemmas, contraction arguments in total variation distance, and finite-time error bounds. The plain-language sections below are written for a general reader, but the results themselves are technical.

Scope: The paper proves that a POMDP can be approximately solved by converting it into a finite-state "Superstate" MDP based on a truncated history, then applying standard TD learning followed by policy optimization with linear function approximation.

What This Paper Is About

POMDPs model decision-making when the agent cannot observe the true state and must infer it from noisy observations, which makes the belief state continuous and the problem computationally intractable (the paper cites PSPACE-completeness from Papadimitriou and Tsitsiklis [1999] and Vlassis et al. [2012]). The authors study an approximation, previously proposed by Kara and Yüksel [2023], that replaces the full history with the most recent finite history of action-observation pairs, producing a finite-state MDP called the Superstate MDP. Their goal is to prove tighter approximation guarantees for this transformation and to show that ordinary TD learning and policy optimization—not specially modified, more expensive variants—can learn the optimal policy of the Superstate MDP.

Key Contributions

1. Tighter POMDP-to-MDP approximation bound. Prior work (Kara and Yüksel [2023], Subramanian and Mahajan [2019]) bounds the value-function gap by 1/(1−γ)², Abel et al. [2016] by 1/(1−γ)³, and Cayci et al. [2024] by a quantity polynomial in the horizon length. This paper provides a tighter bound and, unlike Kara and Yüksel [2023] which bounds the expected difference, establishes a worst-case bound.

2. A general-purpose algebraic identity (Lemma 2). A new inequality bounding expressions of the form |Σᵢ(aᵢbᵢ − cᵢdᵢ)| when the vectors (a, c) and (b, d) are close and (b, d) are probability mass functions. The authors note this result is of broader interest and use it to refine the performance bounds of Subramanian and Mahajan [2019].

3. Convergence guarantees for standard policy optimization. The paper is, to the authors' knowledge, the first to establish convergence guarantees for a standard policy optimization algorithm that alternates between TD learning of the Q-function for a fixed policy and a policy update, while the true underlying model is a POMDP. This avoids the m-step TD workaround used in Cayci et al. [2024], which is computationally more expensive.

4. Extension to linear function approximation. The analysis is extended to the function-approximation setting, enabling scalability to large state spaces. Unlike Kara and Yüksel [2023], who use Q-learning with ergodicity assumptions and give only asymptotic guarantees, this work avoids those assumptions and provides finite-time bounds. A further minor contribution extends the POLITEX analysis of Abbasi-Yadkori et al. [2019] to the discounted reward setting.

Main Findings

• Value-function gap decays exponentially in history length. Theorem 2 shows that under the Uniform Filter Stability Condition (Assumption 1), for every history H, |V*(π(H)) − Ṽ(𝒢(H))|_∞ ≤ 2r̄(1−ρ)^l/(1−γ) + 2r̄γ(1−ρ)^l/((1−γ)((1−γ) + γ(1−ρ)^l)) := ξ^SMDP_POMDP. The error goes to 0 as l → ∞.

• Belief states sharing a superstate are close. Lemma 1 proves that if two histories H and H′ map to the same superstate (𝒢(H) = 𝒢(H′)), then ‖π(H) − π(H′)|_TV ≤ (1−ρ)^l.

• The Superstate MDP is a contraction. Lemma 3 shows that, under Assumption 1 and sufficient exploration μ(a|B) ≥ δ for all a, B with (1−ρ)^l < δ|𝔸|, the Superstate MDP's transition matrix satisfies ‖P̃^μ d₁ − P̃^μ d₂‖_TV ≤ (1−ρ′)‖d₁ − d₂‖_TV for some ρ′ ∈ (0,1).

• Finite-time TD error bound. Lemma 4 gives an explicit bound ξ_TD-Error on the expected error between the Q-function learned by Algorithm 1 and the true Q̃^μ of the Superstate MDP, for τ > 4(1−γ)² iterations with fixed stepsize ε_t = 1/√τ and l′ = log τ / (2 log(1−ρ′)). The bound includes the function-approximation term ‖Φᵀθ̂ − Q̃^μ‖_∞, a term (1 − 2(1−γ)/√τ)^τ‖θ_l − θ̂‖₂, and terms scaling as (r̄ + 2R)²/(2√τ) and C₂(r̄ + 2R) log τ / (√τ log(1−ρ′)), along with contributions proportional to (1−ρ)^l.

• First finite-time bounds for TD learning under non-Markovian dynamics. The authors state that, to their knowledge, these are the first finite-time bounds that explicitly quantify the error introduced when applying standard TD learning in a setting where the true dynamics are not Markovian.

• Sufficient condition for filter stability. Following Theorem 5 of Kara and Yuksel [2020], the Uniform Filter Stability Condition holds if (1 − δ(𝒫))(1 − δ(φ)) < 1, where δ(𝒫) is the minimum Dobrushin coefficient of the transition kernel across actions and δ(φ) is the Dobrushin coefficient of the observation kernel.

Methodology in Plain English

The authors first reduce the POMDP to a belief-state MDP, which is exact but has continuous states that depend on ever-growing histories. To make this tractable, they define a "grouping operator" 𝒢 that truncates any history to its last l action-observation pairs; each truncated history is a "superstate," and there are only finitely many of them. They then build a finite-state MDP over superstates with rewards r̃(B,a) and transition probabilities P̃(B′|B,a) defined by summing over the underlying states and observations.

Because two different histories can map to the same superstate, the key theoretical step is showing that their belief states are close in total variation distance—this requires an assumption that observations are informative enough to make the filter "forget" its prior (the Uniform Filter Stability Condition). The authors then use a new algebraic inequality (Lemma 2) to chain these belief-state closeness results into a bound on the difference between the POMDP's optimal value function and the Superstate MDP's optimal value function.

For the learning part, the practical difficulty is a sampling mismatch: the data the agent collects correspond to real belief states of the POMDP, not to superstates of the approximating MDP. Algorithm 1 runs ordinary TD updates as if the model were the Superstate MDP, using the superstate of the current history as the state. Algorithm 2 wraps this in a policy optimization loop where the policy is a softmax (μᵢ(a|B) ∝ exp(η Σⱼ Q̄^{μ_{j−1}}(B,a))) over the accumulated Q-value estimates from previous iterations; the Q-function is approximated linearly as Q(B,a) = φᵀ(B,a)θ with ‖φ(B,a)‖₂ ≤ 1 and θ constrained to a ball of radius R.

Why This Matters

Impact on research: The work closes a gap between empirically successful finite-history heuristics for POMDPs and the sample-complexity theory that exists for fully observable MDPs. It shows that standard RL machinery—TD learning and policy optimization—can be applied to a non-Markovian problem with quantified error, and it supplies a reusable algebraic tool (Lemma 2) that improves bounds in other analyses.

Real-world applications (as listed in the paper):

• Robotic controllers operating under uncertainty with incomplete, noisy, or ambiguous data
• Autonomous driving
• Personalized content recommendations
• Medical diagnosis
• Games

The paper also notes that decision-making under uncertainty is a critical topic across fields such as operations research and healthcare.

Industry relevance: Because the approach scales via linear function approximation and avoids the extra computational cost of m-step TD learning, it is directly relevant to practitioners who want to apply standard, well-understood RL pipelines to partially observable problems rather than bespoke POMDP solvers or recurrent deep learning architectures (RNNs, variational encoders), which the paper notes lack rigorous performance guarantees.

Future Directions

• Weaker stability assumptions: The authors suggest that for applications not satisfying Assumption 1, a multi-step variant could be considered where the system exhibits contraction after every k steps, and they believe their results could be extended under this weaker assumption.
• Constructing approximate information states: The paper refines bounds from Subramanian and Mahajan [2019], which introduced approximate information states but lacked a systematic method for constructing them; developing such a construction is a natural next step.
• Removing the projection constraint: The parameter projection onto a ball of radius R is used to simplify the function-approximation analysis; the authors point to Srikant and Ying [2019] and Mitra [2024] for analyzing the case without projection.
• Regret and policy-optimization extensions: The authors extended POLITEX to discounted rewards and analyze regret with respect to the POMDP's optimal value function, leaving open further refinement of regret guarantees for this class of algorithms.

Target Audience

This paper is aimed at reinforcement learning theorists and graduate students working on partially observable decision-making, approximate MDP abstractions, and finite-time convergence analysis of TD learning and policy optimization. It is also relevant to researchers familiar with Subramanian and Mahajan [2019], Kara and Yüksel [2023], Cayci et al. [2024], and Abbasi-Yadkori et al. [2019], whose bounds and algorithms it directly improves or extends. Practitioners seeking scalable, provably grounded RL for partially observable systems will find the algorithm structure useful, but the paper's value lies primarily in its theoretical guarantees rather than implementation details.

Authors’ abstract

The continuous nature of belief states in POMDPs presents significant computational challenges in learning the optimal policy. In this paper, we consider an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating the corresponding POMDP model into a finite-state Markov Decision Process (MDP) (called Superstate MDP). We first derive theoretical guarantees that improve upon prior work that relate the optimal value function of the transformed Superstate MDP to the optimal value function of the original POMDP. Next, we propose a policy-based learning approach with linear function approximation to learn the optimal policy for the Superstate MDP. Consequently, our approach shows that a POMDP can be approximately solved using TD-learning followed by Policy Optimization by treating it as an MDP, where the MDP state corresponds to a finite history. We show that the approximation error decreases exponentially with the length of this history. To the best of our knowledge, our finite-time bounds are the first to explicitly quantify the error introduced when applying standard TD learning to a setting where the true dynamics are not Markovian.