Reinforcement learning in Partially Observable Markov Decision Processes (POMDPs) is notoriously hard because the optimal policy depends on the entire history, leading to a long‑range dependence curse. Recent works have shown that a class of POMDPs satisfying a filter‑stability condition can be approximated by a super‑state MDP constructed from a truncated history window; the value gap decays exponentially with the window length. Existing finite‑time analyses, however, either restrict themselves to linear function approximation or assume an i.i.d. sampling oracle, both of which are unrealistic for actual POMDP trajectories.
Our contributions are threefold:
- We derive a point‑wise approximation error bound for the finite‑state MDP surrogate, quantifying how well the super‑state MDP approximates the original POMDP.
- By applying Temporal‑Difference (TD) learning to the super‑state transitions and targeting the Bellman fixed point, we prove a finite‑time critic error bound under nonlinear neural value‑function approximation.
- Combining the neural critic error bound with a policy mirror descent framework yields a finite‑time sublinear regret guarantee against the optimal POMDP value. To the best of our knowledge, this is the first sublinear regret result based on neural function approximation for finite‑memory POMDPs.
Numerical experiments corroborate the theoretical bounds and demonstrate superior sample efficiency compared with linear‑approximation baselines.
Review: The paper delivers the first neural‑network‑based finite‑time sublinear regret guarantee for finite‑memory POMDPs, bridging a critical gap between theory and practice in partially observable reinforcement learning.