acceptodds
Under review as a conference paper at ICLR 2027

Finite-Time Convergence and Regret Guarantees for Neural Reinforcement Learning in POMDPs

Abstract

Reinforcement learning (RL) in Partially Observable Markov Decision Processes (POMDPs) is computationally challenging due to the curse of long-range dependence on history. Fortunately, recent studies have shown that a range of POMDPs that satisfy the filter stability assumption can be well approximated by a superstate Markov Decision Process (MDP) based on a truncated history in a finite-memory window, with a value gap that decays with the window length. However, existing finite-time convergence analyses on such superstate MDP surrogates are either limited to over-simplified linear function approximation or rely on an i.i.d. sampling oracle that is violated by POMDP trajectories, both of which severely limit the applicability of these theoretical results in practice. This motivates us to bridge the gap by investigating RL in POMDPs with \em nonlinear neural value function approximation. Our main contributions are threefold: i) We first establish a new finite-state MDP \em point-wise approximation error bound, which lays the foundation for our RL algorithm design and analysis in POMDPs; ii) By applying Temporal-Difference (TD) learning to POMDP-generated superstate transitions and targeting the Bellman fixed point of the superstate MDP, we prove a finite-time critic error bound with nonlinear neural value function approximation; and iii) By combining the neural critic function approximation error bound with the policy mirror descent framework, we obtain a finite-time sublinear regret against the optimal POMDP value. To the best of our knowledge, such a finite-time sublinear regret based on neural function approximation is the first in the literature for finite-memory POMDPs. Our numerical experiments also verify our theoretical results.

Primary area:
optimization
Keywords:
POMDP, Neural Function Approximation, RL

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_8XbbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers the problem of RL in finite-state POMDPs by using neural function approximation, with guarantees on the regret bound. The paper proposes a method for solving this problem, which learns a neural policy in a superstate MDP approximation of the POMDP, whose states correspond to truncated observation histories of a fixed finite length. The contributions of the paper are as follows. First, the paper establishes a new pointwise bound on the difference between the value functions of the POMDP and the superstate MDP approximation, under a filter stability assumption. Second, the paper considers a neural policy evaluation via TD learning in the superstate MDP, and establishes an error bound on the approximation which depends on the neural architecture size, sampling error, and the bound between the POMDP and the superstate MDP approximation. Third, by combining policy evaluation with policy mirror descent for policy updates, the paper obtains an algorithm for RL in finite-state POMDPs with sublinear regret bound (the bound is sublinear in the product of the number of TD iterations and the policy update iterations). The paper performs a small experiment on an 11-state POMDP where the algorithm is compared with Q-learning and actor-critic on the superstate MDP.

Critical strengths
  1. Novel method with guaranteed regret bounds. The paper considers an important and challenging problem of RL in POMDPs, and provides a theoretical analysis on the regret bound in finite-state POMDPs. The analysis is nontrivial and the bounds appear to be sound, although I haven't checked the appendix in detail. However, the bounds do not appear to be practically useful, see Weakness 1 below.

  2. Clarity. The paper is generally well written and easy to follow.

Critical weaknesses
  1. Regret bound for the sum of all policy updates. My main concern about the paper is that, while guaranteed regret bound is in principle an appealing property, I do not find the bound in this work to be practically useful. The regret bound in Theorem 3 and Corollary 4 considers the sum of regrets for all policies learned over all policy update iterations. Usually, one is interested in the regret bound for the final policy only, not all intermediate policy that a method has learned throughout the training process. This is reflected in the fact that the regret bound increases with the number of training iterations, which would not be useful for reasoning about the final policy.
    Moreover, the regret bound is sublinear in N=K⋅TN = K \cdot T which is the product of the number KK of policy evaluation iterations and the number TT of policy update iterations. Again, this is not a useful metric for reasoning about the regret of the final policy.

  2. Experiments. Experimental evaluation is limited to one toy example, an 11-state POMDP. Moreover, although the paper puts a lot of emphasis on neural vs linear function approximations, existing baselines that use linear function approximation and provide bounds are not considered in the experiments.

Questions for authors
  1. Why is regret bound computed as a sum of regrets over all policies πt\pi_t learned in all policy update iterations? Would it be possible to adapt your analysis to obtain a tighter bound on the regret of the final policy πT\pi_T only?

  2. Did you experimentally compare your method with the prior work of (Cayci et al. 2024) or (Anjarlekar et al. 2025) that use linear function approximation?

Reviewer_1GG4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper provides a theoretical sublinear regret bound for policy mirror descent under partially observable MDPs by utilizing nonlinear neural value function approximation through a finite-memory superstate MDP. There are two key features in this paper: (1) applies neural networks for value function approximation to overcome the limited expressiveness of linear models. (2) addresses the non-i.i.d. sampling issue inherent in on-policy POMDP trajectories by proving that a full-reset sampling mechanism yields explicit geometric mixing properties, rather than imposing it merely as an assumption.

Critical strengths
  1. This is a solid paper that leverages full-reset sampling and NTK to study regret under POMDPs, successfully bypassing the restrictive i.i.d. sampling assumption and linear function approximation limitations typically found in prior works.
  2. The theoretical analysis rigorously demonstrates that the proposed policy optimization algorithm achieves a sublinear regret.
  3. The empirical results successfully validate the theoretical sublinear regret bound.
Critical weaknesses
  1. The paper lacks a lower bound analysis, and the derived upper bound of O(N5/6)O(N^{5/6}) is relatively close to a linear regret, leaving the tightness of the bound open.
  2. The authors employ NTK for local linearization. This technique should ideally be formalized into a standalone lemma. To my knowledge, the error term resulting from NTK local linearization typically scales with a constant power of the network width mm, and this power exponent is often quite large, which could lead to a massive practical regret bound under neural function approximation.
  3. Although the authors claim to resolve the non-i.i.d. sampling issue, they actually rely on a full-reset sampling mechanism to reset the state. While not formally viewed as an assumption in the traditional sense, this essentially reduces the setup to an episodic MDP.
Questions for authors
  1. How can full-reset sampling be practically or theoretically applied with an infinite-horizon formulation, and how does it fundamentally differ from an episodic MDP. If this is a structural assumption, it should be explicitly stated. Furthermore, given that full-reset sampling is utilized, should the regret formulation be framed in terms of the number of episodes rather than total steps N?
  2. How do the authors ensure or verify that the filter stability assumption holds in the experimental environments?
  3. For the regret definition, can the author clarify the difference in [1], which considers the difference of value function under a visited state {s1,⋯ ,sT}\{s_1,\cdots,s_T\}?

[1] Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping

Reviewer_yyVsOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies reinforcement learning in finite POMDPs through a surrogate MDP whose states consist of the most recent ℓ\ell action–observation pairs. It combines a neural temporal-difference critic with an exponential-weights policy mirror descent update. The proposed analysis has three components. First, under a pointwise filter-stability assumption, the paper bounds the difference between the optimal POMDP value and the optimal surrogate-MDP value by O((1−ρ)ℓ/(1−γ)2)O((1-\rho)^\ell/(1-\gamma)^2). Second, it analyzes projected neural TD using POMDP trajectories with geometric resets, explicitly accounting for the mismatch between the actual sampling process and the surrogate Bellman operator. Third, it combines the critic bound with a concentrability assumption to obtain a cumulative policy-value regret bound. Under additional assumptions concerning approximation within a bounded neighborhood of random initialization, the paper claims O~(N5/6)\widetilde O(N^{5/6}) regret with K=N2/3K=N^{2/3}, T=N1/3T=N^{1/3}, logarithmically increasing memory, and sufficiently large network width. Experiments on CheeseMaze compare the method with neural Q-learning and actor-critic.

Critical strengths

The paper addresses a meaningful theoretical problem. Understanding neural TD trained on partially observed trajectories is valuable. The mismatch between the data-generating process and the surrogate Bellman fixed point is a real obstacle that conventional MDP analyses do not automatically resolve.

The sampling analysis distinguishes the relevant processes carefully. Lemma 6 analyzes the actual augmented chain (Sk,Bk,ak)(S_k,B_k,a_k), establishes its mixing under full resets, and compares its stationary marginal with the surrogate occupancy. This is stronger than simply applying a Markovian TD theorem to the truncated histories.

The error decomposition is informative. The analysis separates local-linearization error, approximation error, TD optimization error, temporal dependence, and finite-memory bias. Subject to the validity of its ingredients, this decomposition explains how memory, network size, and evaluation budget affect performance.

The policy optimization component is transparent. The exponential-weights update is explicit, and Appendix D makes its connection to mirror descent and cumulative critic estimates clear. The choice of KK and TT is also understandable from balancing critic accuracy against the number of policy updates.

Critical weaknesses
  1. The stated network normalization appears incompatible with Fact 1.

Section 3 defines

x^{(h)}=\frac{1}{\sqrt m}\text{ReLU}(W^{(h)}x^{(h-1)}), \qquad \widehat Q(x;W)=c^\top x^{(d)},$$ with entries of $U,W^{(h)}$ initialized as $\mathcal N(0,2)$, entries of $c$ as $\mathcal N(0,1)$, and $\|x\|_2=1$. A direct calculation for $d=1$, under exactly this parameterization, gives $$\mathbb E[\widehat Q(x;W_0)^2]=2m, \qquad \mathbb E[\|\nabla_W\widehat Q(x;W_0)\|_F^2]=m.$$ The output and gradient therefore have a typical scale of order $\sqrt m$. This conflicts with the bounds $|\widehat Q(x;W_0)|=O(\log m)$ and $\|\nabla_W\widehat Q\|_2=O(d)$ asserted in Fact 1 on page 20. This may originate from a missing normalization factor. However, the issue propagates into $Q_{\max}$, the stochastic-gradient bounds, the critic rate, and the policy-regret analysis. The intended parameterization must be specified, and the imported bounds checked against it. 2. The cited result of Shen et al. gives approximation rates depending on the target function’s modulus of continuity, with a power-law specialization for Hölder-continuous functions. It does not directly establish the paper’s claim for an arbitrary injective encoding and the stated architecture with fixed random input and output layers. A function on a finite encoded domain can be extended continuously, so the concern is not simply that the domain is discrete. The missing issue is control of the extension’s regularity and its dependence on the encoding, memory length, and policy. There is also a separate locality issue. The paper explicitly assumes $R^\dagger=O(1)$ in Corollaries 1 and 2, and this should be acknowledged rather than treated as an omitted assumption. The universal approximation does not establish that property. The approximating parameter may depend on width, depth, memory length, policy, and random initialization. Consequently, the headline result is conditional on a substantial local approximation property. A convincing treatment should either establish this property for a meaningful class of POMDPs or formulate a precise realizability assumption and explain its scope. The assertion that neural universal approximation removes the approximation floor is currently too broad. 3. The surrogate belief may be undefined under the stated assumptions. Lemma 3 assumes that a truncated window $B$ occurring within a longer history is itself an admissible history when initialized from $D$. This need not hold. For example, consider a fully observed, single-action process with deterministic transitions $$0\rightarrow1\rightarrow2\rightarrow2,$$ initial distribution $D=\delta_0$, and $\ell=1$. The window $B=(a,2)$ occurs at time 2, but observation $2$ is impossible after one transition from $D$. Therefore, $\mathcal U_{a,2}(D)$, used to define $b_B$, has a zero denominator. Filter stability holds exactly in this example because the current observation reveals the current state. Thus, Assumption 2 does not resolve the problem. 4. Corollary 2 requires \$ m\gtrsim\max\{N^2,N^{p/12}\}. \$; for the concatenated one-hot representation used in the experiments, the input dimension grows with memory length. With fixed observation and action alphabets, $p=\Theta(\ell)$; choosing $\ell=\Theta(\log N)$ makes the second width requirement quasipolynomial in $N$. So the trainable parameter count is $dm^2$, and Algorithm 2 explicitly updates every superstate. The number of possible superstates can grow exponentially with $\ell$. An implicit implementation using cumulative critics would introduce its own storage and evaluation costs. These observations do not invalidate a statistical result, but they substantially qualify its practical implications. The paper should track feature dimension, approximation constants, concentrability, and computational cost as memory increases. 5. The claimed distinction from linear approximation is overstated: the statements that linear approximation cannot support sublinear regret, or necessarily leaves an irreducible approximation floor, require qualification. On a finite superstate-action space, a linear model with one-hot features is exact. 6. The experiments provide limited validation of the theoretical contribution: the evaluation uses one small environment with 11 latent states and three training seeds. This is useful as an illustration but provides limited evidence about scalability or the proposed neural approximation advantage.
Questions for authors

Can you reconcile the Section 3 initialization with the output and gradient bounds in Fact 1, including the one-layer calculation above?

What result establishes Lemma 2 for fixed random UU and cc? Please identify the required regularity assumptions and explain how approximation constants depend on the feature encoding and memory length.

For which nontrivial POMDP classes is R†=O(1)R^\dagger=O(1) justified uniformly as m,ℓ,Tm,\ell,T vary; is this intended as an independent realizability assumption, and can it be made explicit in the main contribution statement?

What guarantees that every truncated window has positive likelihood when initialized from DD?

Can you state a guarantee for the learned policies’ values in the original POMDP?

How do pp, Cˉ∞\bar C_\infty, and computational cost scale with ℓ\ell?

Which theoretical algorithm components are implemented in the experiments? Please clarify projection, resets, critic reinitialization, fixed layers, the calculation of V∗V^*, and whether CheeseMaze satisfies Assumption 2. A linear/tabular PMD comparison would also be valuable.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.