Research map / Reinforcement learning / MDPs and planning
Scalable Policy-Based RL Algorithms for POMDPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
The paper approximates a finite-state POMDP by a finite-history "Superstate" MDP and proves tighter value-approximation bounds, plus finite-time guarantees for TD learning with linear function approximation inside a POLITEX-style policy optimization loop.
Problem
Solving partially observable RL (POMDPs) is computationally intractable because belief states are continuous; prior finite-history approximations lacked tight value bounds and rigorous guarantees for standard TD/policy optimization under non-Markovian sampling.
Approach
Treat the POMDP as a finite-state Superstate MDP over the last l action-observation pairs, derive a tighter exponential-in-l value approximation bound via a new algebraic inequality, and show plain TD learning (pretending the model is Markov) plus policy optimization (POLITEX-style, discounted) yields finite-time regret bounds with linear function approximation.
Key results
- Value approximation error between POMDP and Superstate MDP decays as (1-rho)^l, improving prior 1/(1-gamma)^2 and 1/(1-gamma)^3 bounds to a tighter worst-case bound.
- Finite-time regret bound R_T <= T(xi_FA + xi_HA) + O(T^{3/4} log T) for the TD plus policy optimization algorithm with linear function approximation.
- The paper's bounds show a tradeoff between Superstate MDP size (exponential in history length l) and approximation error that decays exponentially in l.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase truncated history length l | Superstate MDP approximation of a POMDP · POMDP to Superstate MDP | optimal-value error upper bound: (1-\rho)^l | Helped |
| use standard TD learning on finite-history superstates instead of the prior m-step TD workaround | Policy Optimization for the Superstate MDP · Superstate MDP | computational complexity | Helped |
Limitations
- Requires the uniform filter stability assumption (contraction of the belief filter), which may not hold in all environments.
- Theoretical only; no empirical experiments reported.
- Regret bounds include linear-function-approximation and truncation error terms; the Superstate space grows exponentially with history length.
Experimental setup
Metrics: regret value function approximation error (sup-norm)
Baselines: m-step TD superstate approach Q-learning with linear function approximation for superstate MDP prior approximate information state bounds
Builds on: POLITEX Superstate MDP (prior finite-history approximation) uniform filter stability condition
Closest papers by meaning
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.90)
- Model-based Reinforcement Learning for Confounded POMDPs (ICML 2024 · similarity 0.90)
- Periodic agent-state based Q-learning for POMDPs (NeurIPS 2024 · similarity 0.89)
- A Policy Gradient Method for Confounded POMDPs (ICLR 2024 · similarity 0.88)
- Rethinking Transformers in Solving POMDPs (ICML 2024 · similarity 0.88)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.