Recurrent Natural Policy Gradient for POMDPs
Authors: Semih Cayci
Atilla Eryilmaz
Venue: Accepted by TMLR ()

Abstract: Solving partially observable Markov decision processes (POMDPs) is a long-standing challenge in reinforcement learning (RL) due to the inherent curse of dimensionality arising from the non-stationarity of optimal policies. In this paper, we address this by integrating recurrent neural network (RNN) architectures into a natural policy gradient (NPG) method and a multi-step temporal difference (TD) method within a natural actor-critic (NAC) framework for computational efficiency. We establish non-asymptotic theoretical guarantees for this method, which demonstrate its effectiveness for solving POMDPs and identify the pathological cases that stem from long-term dependencies. By integrating RNNs into the NAC framework with theoretical guarantees, this work advances the theoretical foundation of RL for POMDPs and provides a scalable framework for solving complex decision-making problems.

Published in Transactions on Machine Learning Research (10/2025)
Recurrent Natural Policy Gradient for POMDPs
Semih Cayci
cayck@maahc..
Department of Mathematics RWTH Aochen University
Atilla Eryilmaz
eryilmaz. M0rina..@@os..cm edu
Department Electrical and Computer Engineering The Ohio State University
Reviewed on OpenReview: https: // openreview. net/ net/ forum? id- 600 I0vgg
Abstract
Solving partially observable Markov decision processes (POMDPs) remains fundamen- tal challenge in reinforcement learning (RL), primarily due to the curse of dimensionality induced by the non-stationarity of optimal policies. In this work, we study a. natural actor- critic (NAC) algorithm that integrates recurrent neural network (RNN) architectures into a natural policy gradient (NPG) method and a temporal difference (TD) learning method. This framework leverages the representational capacity of RNNNs address non-stationarity in RL to solve POMDPs while retaining the statistical and computational efficiency of nat- ural gradient methods in RL. We provide non-asymplotic theoretical guarantees for this method, including bounds on sample and iteration complexity to achieve global optimality up to function approximation. Additionally, we characterize pathological cases that stem from long-tore oon-termm dependencies, thereby explaining limitations of RNNNbased policy optimiza- lion for POMDPs.
1 Introduction
Reinforcement learning (RL) for partially observable Markov decision processes (POMDPs) has been particularly challenging problem due to the absence of an optimal stationary policy, which leads to curse of dimensionality as the space of non-stationary policies grows exponentially over time (Krishnamurthy, 2016; Murphy, 2000). To address this curse of dimensionality solving POMDPs, finite-memory (Yu Bertsekas, 2008; Yu, 2012; Kara & Yüksel, 2023; Cayci et al., 2024a) and RNN-based (Lin & Mitchell, 1993; Whitehead & Lin, 1995; Wierstra et al., 2010; Mnih et al., 2014; Ni et al., 2021; Lu et al., 2024) model-free RL approaches are widely used to solve POMDPs. Despite the empirical success of RNN-based model-free RL methods, rigorous ical understanding of their performance in the POMDP setting remains limited.
We begin by outlining two key observations that motivate our approach:
Observation 1. Recurrent neural networks (RNNs) have been extensively employed in model-free reinforce- ment learning (RL) to solve partially observable Markov decision processes (POMDPs) (Whitchead & Lin, 1995; Wierstra et al., 2010; Mnih et al., 2014). Recent work Ni al. (2021) demonstrates that RNN-based model-free RL can perform competitively with more sophisticated and structured approaches under appro- priate hyperparameter and architecture choices. In Lu et al. (2024), shortcomings of emerging transformers in solving POMDPs were demonstrated, and it was shown, somewhat surprisingly, that particular recurrent architectures can achieve superior practical performance in certain scenarios. However, despite this plethora of works that demonstrate the effectiveness of RNN-based model-free algorithms for solving POMDPs, a concrete thcoretical understanding of these methods still in a nascent stage. This is particularly impor- tant since, as noted by Ni al. (2021), RNN-based model-free RL algorithms are sensitive to optimization parameters, and identification of provably good choices is important for practice.

---

Published in Transactions on Machine Learning Research (10/2025)
Observation 2. Natural policy gradient (NPG) framework has been shown to be effective in solving MDPs due to its versatility in encompassing powerful function approximators, such as deep neural networks (Wang et al., 2019; Cayci et al., 2024b). However, naïve application of such non-recurrent model-free RL algorithms to solve POMDPs has been observed to be ineffective (Ni et al., 2021), which necessitate careful incorporation of recurrent architectures into the policy opt imiizaatiion framework. This calls for the need to incorporate and analyze policy optimization, particularly NPG framework, augmented with recurrent architectures, to obtain a provably effective solution for POMDPs.
Our study is motivated by these observations and guided by the following key questions, each addressed in this work:
Q1. How can we achieve (i) provably effective and (ii) computaatoon/memooyyfffiiiee policy evaluation for non-stationary policics in partially obscrvable environments?
> A temporal difference (TD) learning a algorithm with an IndRNN (Rec-TD) overcomes the so-called percep- tual aliasing problem imperative in memoryless TD learning for POMDPs (Singh et al., 1994), and achieves near-optimal policy evaluation, provided a sufficiently large network (Theorem 5.4 and Remark 5.5). Our analysis identifies the exploding semé-gradients pathology in policy evaluation, which can significantly in- crease network and iteration complexities to mitigate perceptual aliasing under long-term dependencies (Remark 5.6), and demonstrates the role of regularization to mitigate this. We also provide empirical results in random-POMDP instances in Appendix C.
Q2- How can we parameterize non-stationary policies by a rich and practically feasible class of RNNS and perform efficient. policy optimization?
> We represent non-stationary policies using IndRNNs with SOFTMAX paramoterization as a form of finite- state controller, and perform computationally efficient NPG updates (based on path-based compatible func- tion approximation for POMDPs) for policy optimization. The policy optimization update (called Rec-NPG) is aided by Rec-TD as the critic (Section 4).
Q3- What are the memory, computation and sample complexitics of the resulting Rec-NAC method, which employs Rec-NPG for policy updates and Rec-TD for policy evaluation?
> Our non-asymptotic analyses of Rec-TD (Thcorem 5.4) and Rec-NPG (Theorem 6.3) demonstrate their near-optimality in the large-network limit while highlighting dependencies on memory, long-term POMDP dynamics, and RNN smoothness. Pathological cases with long-term dependencies may require exponentially growing resources (Remarks 5.6-6.4).
These results establish principled and scalable RL solutions for POMDPs, offering insights into the interplay between memory, smoothness, and optimization complexity.
1.1 Previous work
Natural policy gradient method, proposed by Kakade (2001), has been extensively investigated for MDPs (Agarwal et al., 2020; Cen et al., 2020; Khodadadian et al., 2021; Liu et al., 2020; Cayci et al., 2024c), and analyses of NPG with feedforward neural networks (FNNs) have been established by Wang et al. (2019); Liu et al. (2019); Cayci al. (2024b). As these works consider MDPs, the policies are stationary. In our case, the analysis of RNNs and POMDPs constitute very significant challenge.
Standard TD learning, which does not have a memory structure, was shown to be suboptimal for POMDPs (Singh et al., 1994). We incorporate RNNs into TD learning as a form of memory to address this problem in this work.
In Yu (2012); Singh et al. (1994); Uchara et al. (2022); Kara & Yüksel (2023); Cayci et al. (2024a), finite- memory policies based on sliding-windors approximations of the history were investigated. Bilinear frame- works with mesory-based policies (Uehara et al., 2022) and Hilbert space embeddings with deterministic
2

---

Published in Transactions on Machine Learning Research (10/2025)
latent dynamics (Uchara al., 2023) enable samplo-efficient learning under specific model structures. In Guo et al. (2022), an offline RT, algorithm for the specific class of linear POMDPs was proposed. Unlike these existing works, our approach integrates RNNs with NAC methods, providing a scalable and theoretically grounded framework for general POMDPs without roquiring structural assumptions such as deterministic transitions, fixed memory windows, or linear POMDP dynamics. Value- and policy-based model--rre RL algorithms based on RNNs have been widely considered in practice solve POMDPs (Lin & Mitchell, 1993; Whitehead & Lin, 1995; Wierstra al., 2010; Mnih et al., 2014; Ni et al., 2021; Lu et al., 2024). However, these works are predominantly experimental, thus there is no theoretical analysis of RNN-based RL methods for POMDPs to the best of our knowledge. In this work, we also present theoretical guarantees for RNN- based NPG for POMDPs. For structural results on the hardness of RL for POMDPs, we refer to (Liu et al.,
2022; Singh et al., 1994).
1.2 Notation
For finite set A, (4A {v E R EoEx Vo 1} is the set of probability vectors over the set A. (a) = Unif(-a,a) a) for a E R4.
2
Preliminaries on Partially Observable Markov Decision Processes
In this paper, consider a discrete-time infinite-horizon partially observable Markov decision process (POMDP) with the (nonlinear) dynamics
(S s|Su, A4, k =)= P((,, At), IPY:, y|S:) ((S..))) y),
for any s 8 and y E Y, where is an S-valued state, Y, Y-valued observation, and A, is an A-valued control process with the stochastic kernels P x A x S [0, 1] and & 3 00. We consider finite but arbitrarily large A, V and S, where
A R
Y C d2
for some d1, d2 E 24 with d := d1 + d2, and Ik a)llz S 1 for any (v. E V x A. In this setting, the state process (St)ee is not observable by the controller. Let
Yo: (Z-11, Yi), if
if
(1)
be the history process, which is available to the controller at time t E N, and
2. : (Z. (Yo, Ao.... ... Y,, Ar),
(2)
be the history-action process.
Definition 2.1 (Admissible policy). An admissible control policy (mt)ee is a sequence of measurable mappings n. (Y A)* x Y + A(A), and the control at time is chosen under n, randomly
P(A: = Z| = 2.) = T. 2x)
for any 2, E (Y x A)* x Y. We denote the class of all admissible policies by IINM-
If an action a is taken at state s, then a deterministic reward r(s,a) with |r(s, a)l S Too < oo is obtained. Definition 2.2 (Value function, Q-function, advantage function). Let æ be an admissible policy, and μ E AYY.. The value function under æ with discount factor (0, 1) is defined as
V. (zt) = E²
k- (rS,, Aa) Ze 21
(3)
3

---

Published in Transactions on Machine Learning Research (10/2025)
for any E (Y x A) x Y. Similarly, the state-action value function (also known Q-function) and the advantage function under are defined as
D0 (E.) E
k r(Sk, An) = =
(4)
k=
A2 = (2t, -1, (z)),
for any & (Y' x A)+1, respectively.
Given initial observation distribution A(Y), the optimization problem is
max (M),,, TElluM
(5)
where
(=())= = Σ
Vo (30)
NEY
We denote an optimal policy as x² E arg max V (H).
=Eller Remark 2.3 (Curse of history in RL for POMDPs). Note that the problem in equation 5 is significantly more challenging than its subcase of (fully-observable) MDPs since there may not exist optimal stationary policy (Krishnamurthh, 2016; Singh et al., 1994). As such, the policy search is over non-stationary randomized policies of type π = (mo, .1....) where He (Y x A)' x Y + A(A) depends on the history of observations Z4 = (Y,, Ag, Yi,..., A,-1, Y,) for L E N. this case, direct extensions of the existing reinforcement learning methods for MDPs become intractable, even for finite A: the memory complexity of non-stationary policy क NN at epoch E N is O(l AI+1), growing exponentially.
In the following section, we formally introduce the RNN architecture that we study in this paper.
3 Independently Recurrent Neural Network Architecture
We consider an independently recurrent neural network (IndRNN) architecture in this work (Li et al., 2018; 2019). This architecture has been featured in POPGym (Morad et al., 2023) as it enables RNNs with large sequence lengths by handling long dependencies in practical applications. In other works, it has been shown to effective for POMDPs practice as well (Lu et al., 2024; Elelimy et al., 2024).
Let X, (Y,, A,) E Rd, therefore Z, (Xo, XI...., X2) for any & E Z4 by equation 2. The central structure in an IndRNN is the sequence of hidden states H, = (H, _ ...., H(m)) E Rm for L = 0, 0,1, which evolves according to
H (Zg
(2;WW W.U) = (2 W.U)+ ( (U,, (i), for all i [m],
(6)
with the initial condition 11 (Zo: W, = e((U,, where e: IR + R is a smooth activation function, W = diag(Wi W2,,... W mm) and is an m x matrix whose i-th row is U. for i E [m]. We assume a smooth activation function o with le(2)] S 2o. le'(2)) S 0i and [e"(=) S l for all R, which satisfied by many widely-used activation functions including tanh and the sigmoid function. We consider a lincar readout layer with weights E R" which leads to the output
F(Ze; W.U,C)
c.l U,U.
(7)
The operation of an independently recurrent neural network is illustrated in Figure Following the neural tangent kernel literature, we omit the task of training the linear output layer c E R for simplicity, and study the training dynamics of (W, U), which is the main challenge (Du et al., 2018; Oymak & Soltanolkotabi,
4

---

Published in Transactions on Machine Learning Research (10/2025)
H
hiddon stats
ouupa
Figure 1: An independently recurrent neural network (IndRNN) in the RL context.
2020; Cai et al., 2019; Wang et al., 2019). Consequently, we denote the learnable parameters of an IndRNN compactly the vector form as
θ
2
Wi U,
R (md1+)) where θ, = E Rd+1 for [m].
(8)
mm
We use θ and (W, U) interchangeably throughout the paper.
A key feature of the neural tangent kernel analysis the random initialization (Bai Lee, 2019; Chizat et al., 2019; Cayci al., 2023).
Definition 3.1 (Symmetric random initialization). Let (c² = (cf, 0 (e be a random vector such that
ci
iid
(Id(1),
O =
iid
Rad(a)
U
(O, Ta)
0
D and O
1+m/2 = O
itm/2
for i = 1,2, 1.,, as Co.
m
We call (c,, θ²) a symmetric random initialization, and denote the distribution of (c",0")
2
For both policy optimization (Algorithm 1) and policy evaluation (Algorithm 2), the IndRNNs are randomly initialized according to Definition 3.1. Such random initialization schemes are widely adopted in practice, and play a fundamental role the theoretical analysis of deep learning algorithms Bai & Lee (2019); Chizat al. (2019); Wang al. (2019); Cai al. (2019); Liu al. (2019).
In the following subsection, define the reference function class determined by overparameterized IndRNNs in detailed way, which will be instrumental in the theoretical results and their analyses. We note that this subsection can be skipped for those who would like to focus on the algorithmic design.
3.1 Reference Function Class for Independently Recurrent Neural Networks
A fundamental question in reinforcement learning with function approxination is to determine concrete reference function class for the function approximation architecture that is used for approximation in the value and policy spaces (Bertsekas & Tsitsiklis, 1996). In this subsection, we will identify and discuss the reference function class defined by the IndRNN architecture that will be used for incorporating memory to solve POMDPs. In order to motivate the discussion, we first overview basic reference function classes for (fully-observable) MDPs, then extend the discussion to POMDPs.
Function approximation in MDPs. Let us consider based reinforcement learning in the case of MDPs, where the objective is to learn the Q-function under given stationary policy The approximation

---

Published in Transactions on Machine Learning Research (10/2025)
error for given reference class F of functions f: x A + R is
Capp == inf E. (Q= - f(s.a)) fE
(9)
For example, if linear function approximation scheme with a given feature map o 3 A - RP is used,
then the reference function class is f := {(s,a) + 0 á(s,a) 0 R² span( where o := 16 (s. ass a)ls,a is the feature matrix. In the case of linear MDPs Jin et al. (2020), we have Q & and Eapp + = 0: otherwise TD()) with this linear approximation scheme has an inevitable approximation error I-7 Capp (app ($) (Bertsckas & Tsitsiklis, 1996). The reference function class for randomly-initialzzed single hidden-layer feedforward neural network with frozen output layer is
NTK = {(,, a) + Euo (ow)) T V Vue(((s, a), uo))] such that (ao=: < xoj,
(10)
where v: Rdd + Rd (Liu et al., 2019; Wang et al., 2019; Cayci et al., 2023). Technically, the completion of FNK yields the reproducing kernel Hilbert space (RKHS) of the so-called neural tangent kernel
Euo n (x,2²):== = Euo V o(ug x)
V Vue(u x')] x TT a'E[g' (igg(Mu (up x) (uj x')l for any x, ESXA
and its explicit analysis shows that it provably rich (Ji al., 2019). For a detailed discussion on the function space NIK and its role in reinforcement learning, we refer to Section A.2 in Liu et al. (2019) and Cayci et al. (2024b). Due to the concrete approximation bounds for FNTK, the representational assumption QT E FNTK is standard in the theoretical analyses of neural TD learning for MDPs, and the objective is to prove that neural TD learning can learn any Q" E FNIK using samples with finite-time and finite- sample guarantees (Cai et al., 2019; Wang et al., 2019; Cai et al., 2019; Cayci et al., 2023). Without the reprosentational assumption Q E FNTK, the optimality guarantecs in Cai et al. (2019); Liu et al. (2019); Wang et al. (2019); Cayci et al. (2023) hold up to an additional error term proportional to tapp (
Function approximation in RL for POMDPs. Analogous to the approximation error analysis in RL for MDPs discussed earlier, our objective here is to identify suitable reference function class for the IndRNN architecture defined in equation 7. Building on the framework of Cayci & Eryilmaz (2025), present an infinite-width characterization of IndRNNs in the neural tangent kernel (NTK) regime. This directly extends the reference function class FNTK in 10 for foedforward neural networks in the neural RL literature (Cai et al., 2019; Wang et al., 2019; Cayci et al., 2024b) to the partially observable setting with recurrent models. We note that our reference function class reduces to the feedforward neural networks as a specific case (see Remark 3.4).
For any E 2+ and imput Z, symmetric initialization ensures that Pi(Z:0) 0. Furthermore, the first-order Taylor expansion of F2 at θ E Rmm(+1) around @ yields
v 09) +0 0 o 0012) 10-
(11)
As m - oc, the linear part by the reproducing kernel Hilbert space (RKHS) of the recurrent neural tangent kernel defined as
is able to approximate a rich class of functions determined
Ke (2, = lim (Z m-
for E Z.. In the following, we characterize this sequence of reprodueing kernel Hilbert spaces for & Z,. explicitly, following Cayci & Eryilmaz (2025).
Let (ad(a) and uo ~ NNO, Ia) be independent random variables, and 6g = (wo, Mo). Given a sequence z = (In, .). E (Y x A)2+,, let
he 0o) == g(uphu-1(2-11:6)) + (4o, xx)) for = 0, 1,
with the initial condition h-1 == O. and
(Ec; 0o) == e 1 + (uo. zz))-
6

---

Published in Transactions on Machine Learning Research (10/2025)
Then, the neural tangent random feature mapping' at time is defined as
the (Z 0o)
Σ u
I IZ
Ze-k
1=0
Based on the sequence of neural langent random features, the neural langent. random feature matrix is defined as (z)00) o (2; 0o), where
vo (z0: v (21:00)
V (2:66)) =
(12)
:
Tht (3T 0n)
for any T E Z4.
Definition 3.2 (Transportation mapping). Let H be the set of mappings v Rl+d - RRldd such that
(00)
v00)) = (n)))))
for 0o (wn, un) with B]]lo(0,)) < oc, where wn ~ Rad(a) and un ~ ~N Ia). We call
U M a transportation mapping, following Ji Telgarsky (2019); et al. (2019).
Definition 3.3 (Reference function class for IndRNNs). We define the reference function class of IndRNNs for any soquence-length T 2
FI = Z E ((Vr((E)0)))(00) = (7-
: H (
where ft v) BisT (3y: (o)) for any E (Y' A) The same transportation mapping is used define ft for all E N, which is characteristic feature of weight-sharing in RNNs. We denote F Foc. Remark 3.4 (Reduction FNTK). Note that selting T yields the random feature map
( 0o) = ( V..e(( (uo: )0)))
since Vue((ro, uo)) = xoe' ((x0, uo)). Hence, for any v H, we have
$ = (T) + (u)) T Vue( ( ua))] (llvvauv))l < [c),
which is exactly the reference function class FNTK for feedforward neural networks given in equation 10. In other words, {.Fr E }+} contains FTK with $ = NNK, which the reference function class neural RL literature for MDPs (Wang et al., 2019; Liu et al., 2019). F dense in the space of continuous functions on a compact set (Ji et al., 2019).
Remark 3.5 (Fully-connected RNNs) IndRNNs utilize diagonal hidden-to-hidder weight matrix W, which was shown to be very effective in handling long-term dependencies in RL compared to convent ional RNNs, GRU and LSTM architectures (Morad et al., 2023). In addition to its practical benefits, IndRNNs have thcoretical niceties as well, as they enable (i) explicit characterization of the reference function class, and (ii) direct control and analysis the spectral radius of W. Both of these theoretical amonities are lost when W does not inherit a diagonal structure.
3.2 Max- Norm Projection for IndRNNs
Given an initialization (W()), c) as in Definition 3.1 and a vector p = (pw: Pw) E RR of projection radii, we define the compactly-supporree set of weights 9ppm [mm(d+1)
2p.m = e m(d+1) max [ - Wa((0)= S Pw Vm
max IU U.(O)] S
Pu
(13)
Vm
The feature uses complicated weighted-sum all past imputs ze. 1, leading discounted memory tackle non-stationarity. & scaled with w Rad(a), thus yields fading memory approximation of the history a
7

---

Published in Transactions on Machine Learning Research (10/2025)
Given any symmetric random initialization (W()), U(0),)) c) and p RS. the set 2pmm is compact and convex subset of Rmld+1), and for any @ E ppm, we have
max mm
[Wa Wo)(0)) v
Pw
Vm
Pu
max Isis
|U; - U:(0)1l -
mm
Let
Proje, (0) wEB. (W.( Vmn
arg min (W..
W: - wxl.
arg min
IU; U/ 1//22
(14)
u, B.
ic(m]
As such, the projection operator Projo.... [-] onto 4pm called the max-norm projection (or regularization) (Goodfellow et al., 2013; Srebro et al., 2004). As an immediate consequence, e E 9p.m implics that [Wal s y Om, which implies strict control over max]e[m] [Wa]- As we will see in Section 5 and Section 6, such a strict control over the norm of the hidden-to-hiddden weights Wa has a significant importance in stabilizing the training of IndRNNs. Similar projection mechanisms for IndRNNs are adopted in practice as well (Morad et al., 2023). For further details, refer to Appendix A.
Wa (o) (a)) S Py
4 Rec-NAC: A High-Level Algorithmic View
In this scction, we present a high-level description of our Recurrent Natural Actor-Critic (Rec-NAC) Algo- rithmn with two inner loops, critic (called Rec-TD) and actor (called Rec-NPG), for policy optimization with RNNs. The details of the inner loops of the algorithm will be given in the succeeding sections, We use admissible policy (me) that is parameterized by recurrent neural network (Fe(s; +))teN of the form given in equation 7 with a network width m E Z+. To that end, for any t E N, let
(alze) = En'ea exp (Fi (²); a
(15)
for any 2, E (Y x A) x Y and a e A with the parameter & E lm(d+1), The high-level operation Rec-NAC is summarized in Algorithm
Algorithm Recurrent Natural Actor-Critic (Rec-NAC) High-level description 1: Initialize the actor RNN as (c, ((0)) ~ ço (see Definition 3.1).
for n = 0, 1,2, .,,
do Critic. Independently initialize the weights of the critic IndRNN as (c", (0)) Co. Run Rec-TD TD in Algorithm 2 for Kid itcrations, and obtain O == K ΣRCK (*) Estimate O ((x) by :-) @*) for all t < <.
4:
5:
6:
Actor Apply projected-SGD to obtain
T Σ 1=
In (A/2)) 2)
Wn E argmin ET wEft
r
7:
where the estimated advantage function is
A (2t, (z),0) (x, -
(2,))
for ((((()=== = P((: and ()()()) En'er at 1(n)) (a (a'1 )( (,,a)-
Policy update.
( + 1) ((n) 17 Wn.
10: end for
8

---

Published in Transactions on Machine Learning Research (10/2025)
For information regarding the algorithmic tools, i.e. random initialization and max-norm regularization for RNNs, we refer to Section A.
In the following two sections, we derive the critic (Section 5) and the actor (Section 6) in full detail, and provide concrete performance bounds for these methods in each section.
5
Critic: Recurrent Temporal Difference Learning (Rec-TD)
In this section, we study a policy evaluation method for POMDPs, which will serve as the critic.
Policy evaluation problem. Consider the policy evaluation problem for POMDPs under a given admissible policy x IINM- Given an initial observation distribution μ A(Y), policy evaluation aims to solve
Σ 7 - 2
min R7(0) E @E0p.m
(16)
where T E N is the sequence length (i.e., the length of the truncated trajectory Z), and {Fr : t N} is an IndRNN given in equation 7 we drop the superscript for simplicity throughout the discussion. The expectation in (+) is with respect to the joint probability law PT the stochastic process {(S), A,, Y)) E [0, }}} where Za ~ μ.
5.1 Recurrent TD Learning Algorithm
In this section, we present a multi-step temporal difference learning algorithm for computing the sequence of state-action value functions {07 E N} for large POMDPs.
We assume access to sampling oracle capable of generating independent trajectories from a given initial state distribution (Bhandari et al., 2018; Cai et al., 2019).
Assumption 5.1 (Sampling oracle). Given an initial state distribution μ, we assume that the system can be independently started from Su (,, i.c., independent trajectories {(S,, Yz, A,) :t [T]} PT* are obtained.
Rec-TD is presented in Algorithm 2. We study the performance of Rec-TD numerically in Section C under long-term and short-term dependencies to validate our thcoretical results in Section 5.2. Remark 5.2 (Intuition behind Rec-TD). In stochastic optimization setting, the loss-minimization for Rr(O) would be solved by using gradient descent, where the gradient is
VoRi 2 -
On the other hand, the target function O7 is unknown and to be learned. Following the bootstrapping idea for MDPs in Sutton (1988), we exploit an extended non-stationary Bellman equation in Proposition B.3. and use rr + 7 FF [Z41; θ) as a bootstrap estimate for the unknown O, (2)) Note that, in the realizable case with O*) = (f). (.), & E Z4 for some O*, we have [VR (*)) = O, motivating the use of the stochastic approximation this partially observable setting.
5.2 Theoretical Analysis of Rec-TD; Finite-Time Bounds and Global Near-Optimality
In the following, we prove that Rec-TD with max-norm regularization achioves global optimality in ex- pectation. To characterize the impact of long-term dependencies on the performance of Rec-TD, let pr(x) = E |a|*, and (x) = - 1)]x/*, x E N.
In the following, we present regularity condition on the stale-action value functions. Assumption 5.3 (Regularity of (27))). (or e F with a transportation mapping (Vw. Du) E H such that suPpeR411 [1)]l0))2 Mu and supgese11 (0)( S Uv.

---

Published in Transactions on Machine Learning Research (10/2025)
Algorithm 2 Recurrent TD Learning Algorithm
Input: step-size 0, max-norm projection radius (Pws (Pw) sequence-length T. 2: Initialize (c, (0)) Ço according to Definition 3.1.
3: for A = 0, 1, 2,.., K - do
4: Sample an initial state Si ~ μ independently.
5: Observe Y ~ ((S...) :).
Choose an action A no(-1
Set VR 0. for t= 0.0....., do
State transition 8/41 P((S A)), Observe y ( (1+))
10:
11:
Choose an action A4+1 ~ T (-1Z/-1)
12:
Compute temporal difference 5, (Z, (k)) where
6, 0) 0) 7 -R(E)))
13:
Update stochastic semi-gradient:
VR VR 7%,
14:
end for
15:
Parameter update with max-norm projection
O + 1) Projo, [O(k) - n (RT]-
16: end for
Assumption 5.3 is representational assumption, stating that (0T); lies in the RKHS induced by the random features (2; 0o) defined in equation 12. It directly extends Assumption 4.1 in Wang et al. (2019) and Assumption 2 in Cayci et al. (2024b) to POMDPs, and exactly recovers these assumptions when T = (see Remark 3.4).
Theorem 5.4 (Finite-time bounds for Rec-TD). Under Assumptions 5.1-5.3, for any projection radius v= (Mw, un) and step-size > 0, Rec- TD with max-norm projection achieves the following error bound:
K-1 (=(0(())) s VK (1-7)
1
cf
K-1
Σ
+ (1
Σ
w
(17)
K
(1 7)3
2)
(1
K K
k=0
k=0
(9)
for any E N, where
19,c2) poly (pr((a (aa Purm" m/2m=1/2)e)) e)), pumm=113e)::llllllll11)
are distonce-depender constants that do not depend on K, and we.k = - (E((F((2;0(K)) - 27 (Z+)) is
wniformly bounded sequence for k,k E N. Furthermore, the loss at average-iterate, E[RT ( Σ O admits the same upper bound the regret upper bound in equation 17, up to multiplicative factor of 10.
The proof of Theorem 5.4 can be found in Section B.
Assumption 5.1 is critical to obtain finitc-time bounds in Theorem 5.4, and holds when the system can be restarted independently from the initial state distribution Bhandari el al. (2018). In the specific case of fully- observable MDPs, the process {(S,, time arguments under uniform ergodicity assumptions are used for analysis under Markovian sampling from single trajectory without independent restarts (Bhandari al., 2018; Cayci al., 2023). On the other hand, in the case of POMDPs, ((Se, A&): k N) is not Markov chain under general non-stationary
e N} is a Markov chain under any stationary policy, and mixing
10

---

Published in Transactions on Machine Learning Research (10/2025)
policy л. In the specific case of policies parameterized by RNNs with hidden state {Hx k N), the augmented process {(S,, Ag, Yx, Hx) : l E NJ forms Markov process. The challenge here is that the state space for this augmented Markov process may be very large or even continuous, and standard theoretical tools (e.g., mixing time arguments) can become much more involved. Under Assumption 5.3, Theorem 5.4 implies the global e-optimality of Rec-TD as the sequence-length T - oo for sufficiently large number of iterations K = -(C /E²) and network width = O /e²). If we omit Assumption 5.3, the error bound in Theorem 5.4 still holds with an additional error term O - capp(
where
Σ 7 (M(Z)) t=0
Capp (T)
inf /EST
E
is the function approximation error.
Remark 5.5 (Overcoming perceptual aliasing with Rec-TD). Memoryless TD learning suffers from a non- vanishing optimality gap in POMDPs, known as perceptual aliasing (Singh et al., 1994). To address this, Rec-TD integrates T-slep stochastic approximation with an RNN, enabling it to retain memory. Accordingly, Theorem 5.4 establishes that as T + oo, Rec-TD reduces R arbitrarily small values, given sufficiently large network width and itcration count K.
Remark 5.6 (The impact of long-term dependencies). Note that both constants cl", cf? polynomially depend on pr (m))m). As noted in Goodfellow et al. (2016), the spectral radius of (W(k) k E NJ determines the degree of long-term dependencies in the problem as it scales Hç. Consistent with this observation, bounds depend on
am == a +
Pw vm
Amax [W] (K))
= max W;,(k))., =E(m)
for any & E N. Note that Theorem 5.4 requires Pw 2 Mwy thus max4e[m] [W:(k)] should be sufficiently large depending on the RKHS norm v. Let > 0 be any given target error.
1, then it is easy to see that pr(eiam) S I-eram Thus, the Short-term memory. If Om Ø1
extra term (0) in equation 17 vanishes at geometric rate as T -> oc, yet m (network-width) and K compplion-oomplextt)) are still ((1/s²). Rec-TD is very efficient in that case.
1 as T - xo, both m and K grow at a rate O ((eram)?7/e? while Long-term memory. If om 0
the extra term (9) in equation 17 vanishes at a geometric rate. As such, the required network size and iterations grow at geometric rate with T in systems with long-term memory, constituting the pathological case.
Theorem 5.4 emphasizes the critical importance of max-norm projection and large neural network size m in stabilizing the training of IndRNNs by Rec-TD, and guides the choice of the projection radius p. Interestingly, if (O7 tt < T}- E Fy has an RKHS norm Vw < 1/01, then Rec-TD with a projection radius Pw 2 W and overparameterization m > 1 yields significantly improved policy evaluation performance in terms of cll ofa for large T. Similar projection mechanisms on (W; i [m]} are widely used for IndRNNs in practice, for instance in Morad et al. (2023), to enhance stability.
The performance of Rec- TD is studied numerically in Random-POMDP instances in Section C.
6 Actor: Recurrent Natural Policy Gradient (Rec-NPG) for POMDPs
The goal is to solve the following problem for given initial distribution μ A(Y) and R3o'
max y=² (1) such that Tb E 2pmm:
(PO)
(ERm(d+1)
11

---

Published in Transactions on Machine Learning Research (10/2025)
6.1 Recurrent Natural Policy Gradient for POMDPs
In this section, we describe the recurrent natural policy gradient (Rec-NPG) algorithm for non-stationary reinforcement learning, First, we formally establish in Prop. D.2 that the policy gradient under partial obscrvability takes the form
V&VT ==
Σ
t=
where the state S, in the MDP framework is replaced by the process history Z, in POMDP. Fisher information matrix under a policy x² is defined as
GT( = ET y In (A In I
( Z,)
for initial observation distribution μ E (Y)) Rec-NPG updates the policy parameters by
((n + 1) = (nn) + (*()n)) V (4);
(18)
for an initial parameter (()) and step-size > 0, where G denotes the Moore-Penrose inverse a matrix This update rule is the same spirit as the NPG introduced in Kakade (2001), however, due to the non-stationary nature of the partially observable MDP, it has significant complications that we will address.
In order to avoid computaaionnaly-expesssiie policy updates in equation 18, utilize the following exten- sion of the compatible function approximation in Kakade (2001) to the case of non-stationary policies for POMDPs.
Proposition 6.1 (Compatible function approximation for non-stationary policies). For any $ Rmd(+1) and initial observation distribution μ,, let
(u 1) Ep
(' In (A, AT (Z)))
(19)
1=
for w E 1d++1)) Then, have
(
(n) arg min Cy(w; 4).
(20)
wERmid+1)
We have the following remark regarding the intricacies of compatible function approximation in the POMDP setting.
Remark 6.2 (Path-based compatible function approximation with truncation). For MDPs, the compatible function approximation crror (u: measure, from which one obtain unbiased samples (Agarwal et al., 2020; Konda & Tsitsiklis, 2003). Thus, the infinite-horionn can be handled without any loss. On the other hand, for POMDPs as in equation 19, this simplification is impossible due to the non-stationarity. As such, we use a path-based method for a sequence-length T E with
(w; Φ) be expressed by using the discounted stato-action occupancy
(T(W; 2
Σ
I/ -A|Z))-AAAZ,
where Ar Q.(21, oz) EaEs :t (alz)) is the advantage function.
Given a policy with parameter ((n), the corresponding output of the critic, which obtained by Rec-TD with the average-itorate as
((n) F((:0*) for 6" 1
Σ (*),,,
Kid
12

---

Published in Transactions on Machine Learning Research (10/2025)
the actor aims to solve the following problem:
TE BLer lr (w; ((n), )(m) 16", ((n).....
min wwR
We utilize stochastic gradient descent (SGD) solve the above problem. Let Z7 P7 1 1s be an independent random sequence for &o E N, 2, (0) and
Wn + 1) = an (k) - Tagg (w (k); ((n), )())). @n (k: + +1 = Projap.. [ (k + 1)},
A stochastic estimate G (f())) (1) is computed as Wn == Kugs En Koge (n),,, followed by
(n + 1) = (n) + Thpp Wh.
In the following, we present thcoretical analysis of this policy optimization algorithm.
6.2 Theoretical Analysis of Rec-NAC for POMDPs
We establish an error bound on the best-iterate for the Rec-NPG. The significance of the following result is two-fold: (i) it will explicitly connect the optimality gap to the compatible function approximation error, and (ii) it will explicitly show the impact of truncation on the performance of path-based policy optimization for the non-stationary case.
Theorem 6.3. Assume that Pf is absolutely continuous with respect to PT this assmmption, let
Sin)in for all a < N. Under
Pr
#
max 0Sn<N
(m) Pr
be the concentrability coefficient, and
Vn = Va
V=' (4) - Da (4), n <
be the optimality gap. Rec-NPG after N E 24 steps with step-size Maps yields
VN and projection radius TR2
In |n
llpl pr(ame1) 1-y m4
TT + (1-
min E.l Vo[Va] OSn<N
Σ n=0
Eo (f(n), wi.))
(1 (1-7)VN
where E, is the conditional expectation given the symmetric random initialization (c ((0) ~ Co, and
(0,w) == Σ M In (ArlZ.)w AFT A.)..
KTT
Remark 6.4. We have the following remarks.
The ivenessveness of Rec-NPG is proportional to the approximation power of the IndRNN used for policy parameterization, as reflected in T in Theorem 6.3. We further characterize this error term in Propositions 6.6-6.8 in the following.
The terms Lt, Br. As, X grow at rate (e(0rmm). Thus, if am > eT then and N should grow at a rate (0m@1)² implying the curse of dimensionality (more generally, it known as the exploding gradient problem Goodfellow et al. (2016)). On the other hand, if am < o7 then L,, Sc, A4, X are all (1)) for all f, implying efficient learning of POMDPs. This establishes very interesting connection between the memory in the system, the continuity and smoothness of the RNN with respect to its parameters, and the optimality gap under Rec-NPG.
13

---

Published in Transactions on Machine Learning Research (10/2025)
The term 2x (1-7)²
is due truncating the trajectory T, and vanishes with large T.
Rec-NPG achieves e-optimality (up to the compatible function approximation and truncation errors) with N = ((1/2) steps and m O(1/c)) neural network width for any c 0.
Remark 6.5. The quantity x in Proposition 6.8 the so-called concentrability coefficient in policy gradient methods (Agarwal et al., 2020; Bhandari Russo, 2019; Wang al., 2019), and determines the complexity of exploration. Note that it is defined in terms of path probabilities 17 in the non-stationary setting. By making the assumption < 00, we assume that the policies T perform sufficient exploration to visit each trajectory visited by x² with positive probability. In order to establish similar bounds without this assumption, entropic regularization is widely used to encourage exploration in practical scenarios Ahmed et al. (2019); Cen et al. (2020); Cayci et al. (2024c). The benefits of using entropic regularization in policy optimization for POMDPs to encourage exploration is an interesting future research direction.
In the following, we decompose the compatible function approximation error et into the approximation error for the RNN and the statistical errors. To that end, let
app..n
inf E wEltp.m
Σ 7 V
(((2; - O 9(n) (Z,)
ET
be the approximation error where the expectation is with respect to Pf 9())
E (ā ((()) n].
be the error in the critic (sec equation 16), and finally let
s (w(r(wn:: (n), (0))) ((k), n| in(r((((ur )())))m)) o(k), k n).
be the error in the policy update via compatible function approximation. Proposition 6.6 (Error decomposition for =. For any Z+, we have
T-1
E
9(n) p
[Er(un; ((n), [m)]] ((k),, S n
Σ
y 1 + SEapp.n + GEtd,n + 28
m
From Theorem 5.4, we have, for Mh = O(1/VKu))
ftdn S poly(pr(@1am)))
+ pp))
(Ked
menitic
and by Theorem 14.8 in Shalev-Shward & Ben-David (2014), we have, for Tagd = O(1/ OLL/VKKg))) (Kgd))
Esgd,n S poly(pr(eram)) (Ipla) Kgga).
As such, the statistical errors in the critic and the policy update (i.c., Etd.ns Esgd.n) can be made arbitrarily small by using larger Ka,, Kaga and larger mentic- The remaining quantity to characterize the approximation error, which is of critical importance for a small optimality gap as shown in Theorem 6.3 and Proposition 6.6. In the following, we will provide finer characterization of sapp.n and identify class of POMDPs that can be efficienll solved using Rec-NPG.
Assumption 6.7. For an index set. J and E R2
So: we consider class HI. of transportation mappings
sup 10 (0)) BERe+1.EE sup
}
000 1 jjEJ,
<
(ww) Vu
|| (0)1
(1)
pER--i
14

---

Published in Transactions on Machine Learning Research (10/2025)
and also the corresponding infinite-width limit
F,, == B(V v Conv()S,,))
where (g) the NTRF matrix, defined in equation 12.
We assumne that there exists an index set J and E RR such that @ E EI for all n N.
This representational assumption implies that the Q-functions under all iterate policies * throughout the Rec-NPG iterations = 0, l.... can be represented by convex combinations of a fized set of mappings in the NTK function class & indexed by J. As we will see, the richness of J as mcasured by a relevant Rademacher complexity will play an important role in bounding the approximation error. To that end, for a = (z1,0t) at) E (V A)+,1, let.
G = V Vo ( (z o)o()) : u Hsch.
and
Radm (G
E sup
eg (0)))).
(ad ((U))Suu
gEG
Note that v E H. above can be replaced with E Conv(H)u,) without any loss. In that case, since the mapping v65) + ob)) E G is linear, G is replaced with Conv(Gi)) without changing the Rademacher complexity (Mohri et al., 2018).
The following provides finer characterization of the approximation error.
Proposition 6.8. Under Assumplion 6.7, if p E v, then
2
1
Radm + Lr|lpl|21 In (2T) x A(T/0)
Capp.n 1-7
max max 2
OSACT (ETXA))+))
m
for all simultaneously with probability at least 1 over the random initialization for any E (0, 1). Remark 6.9. An interesting case that lead to vanishing approximation error (as m + oo) is |J| < co. Then, Proposition 6.8 reduces to Cayci et al. (2024b) (with T = 1 for FNNs) with the complexity term (V In(121/8) by the finite-class lemma (Mohri et al., 2018). In this case, the Q-functions throughout m
n = 0, 1,... lie in the convex hull of [J] fixed functions in & generated by {b(i) E :jEj,, Remark 6.10. As noted in Cayei et al. (2024b), in static problem (e.g., the regression problem in supervised learning policy evaluation in Section 5) with a target function f E E, the approximation error is easy to characterize:
(n (V
V ((0)) fa(z))]=O
(21)
by Hoeffding inequality with wn = vm cap ca, (0)
iEim]
In the dynamical policy optimization problem, the representational assumption Q= 9(m) I does not imply arbitrarily small approximation error since the function Q *(x) also depends on (()). Thus,
H (Z;; + (0) (m))
=
with : := 1 v (m)
(0))lem) (1)
for v (n) E H may not converge to the target function Q=*(m) as m + oc
because of the correlated V H. (zg (1)) across i [m]. To address this, characterize the uniform approximation error as in Proposition 6.8 for the random features of the actor RNN in approximating all Q ((x) for all based Rademacher complexity.
15

---

Published in Transactions on Machine Learning Research (10/2025)
7 Conclusion
We studied RNN-bbsed policy evaluation and policy optimization methods with finite-time analyses, which demonstrate the eflectiveness of the NPG method equipped with RNNs for POMDPs. An important limita- tion Rec-NPG is that its memory and sample complexity significantly increases in POMDPs with long- term dependencies as pointed out Remarks 5.6-6.4. In order to mitigate these issues, as an extension of this work, imput normalization (Zucchet & Orvicto, 2024) and preconditioned Rec-TD updates to incorporate curvalure information (Martens & Sutskever, 2011) important directions for future research.
Acknowledgments
This work was funded by the Federal Ministry of Education and Research (BMBF) and the Ministry of Culture and Science of the German State of North Rhine- Rhine-Westplee Westphalia (MKW) under the Excellence Strategy of the Federal Government and the Länder. Atilla Eryilmaz's research was supported in part by NSF AI Institute (AL-EDGE) 2112471, CNS-NcTS-2106679, and the ARO Grant W911NF-24-1-0103.
References
Alckh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods in markov decision processes. In Conference Learning Theory, pp. 64-66. PMLRR 2020.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy policy optimization. In International Conference Machine Learning, pp- 151-160. PMLR, 2019.
Yu Bai and Jason Lee, Beyond linearization: On quadratic and higher-order approximation of wide neural networks. Xiviv preprint arXi::1910001619, 2019.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906. 016 2019.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with
linear function approximation. In Conference on learning theory, pp. 1691 1692. PMLR, 2018.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-diiference learning converges global optima. Advances in Neural Information Processing Systems, 32, 2019.
nonasymptotic analysis. SIAM Journal on Mathematics of Data Science, 7(2): 854, 2025. Semih Cayci and Atilla Eryilmaz. Convergence of gradient descent for recurrent neural networks: A
Semih Cayci, Siddhartha Satpathi, Niao He, and Rayadurgam Srikant. Sample complexity and overparame- terization bounds for temporal difference learning with neural network approximation. JEEE Transactions on Automatic Control, 2023.
Semih Cayci, Niao He, and R Srikant. Finite-time analysis of natural actor-critic for pomdps. SIAM Journal on Mathematics of Data Science, 6(4):869-88) 8960999966400 2024a.
Semih Cayci, Niao He, and R. Srikant. Finite-time analysis of antropy-regularizrr neural natural actor- critic algorithm. Transactions on Machine Learning Research, 2024b. ISSN 2835-8856. URL https: / h//openrevew.nee///eeeeeeeeeeeee www.://oroumm/tttkaakg....
Semih Cayci, Niao He, and Rayadurgam Srikant. Convergence of entropyy-rogularized natural policy gradient with linear function approximation. STAM Journal on Oplimization, 34(3):2729 2755, 2024c.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejic Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXio preprint ar orXii:2007.065: 2020.
16

---

Published in Transactions on Machine Learning Research (10/2025)
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances W. Neural Information Processing Systems, 32, 2019.
Thomas M Cover and Joy A Thomas. Elements of information theory (wiley series in telecommunications and signal processing), 2006.
Simon S Du, Xiyu Zhai, Barnabas Poezos, and Aarti Singh. Gradient descent provably optimizes over-
parameterized neural networks. In International Conference on Learning Representations, 2018.
Esraa Elelimy, Adam White, Michael Bowling, and Martha White. Real-time recurrent learning using trace units in reinforcement learning. arXiv preprint NXN0:2209900449, 2024.
Ian Goodfellow, David Warde-Farley, Mehdi Mirza, Aaron Courville, and Yoshua Bengio. Maxout nelworks. In International conference on machine learning, pp. 1319-1327. PMLR, 2013.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016
Hongyi Guo, Qi Cai, Yufeng Zhang, Zhuoran Yang, and Zhaoran Wang. Provably efficient offline reinforce- ment learning for partially observable markov decision processes. In International Conference on Machine Learning, pp. 8016-8038. PMLR, 2022.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks arXiv preprint arXiu: 12292. 2019.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and universal approximation. In International Conference on Learning Hepresentations, 2019.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on learning theory, pp. 2137-2143. PMLR, 2020.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc.
19th International Conference on Machine Learning. Citeseer, 2002.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Ali Devran Kara and Serdar Yüksel. Convergence of finite memory learning for pomdps and near optimality of learned policies under filter stability. Mathematics of Operations Research, 48(4):2066-2) 2093, 2023.
Sajad Khodadadian, Prakirt Raj Jhunjhunwala, Sushil Mahavir Varma, and Siva Theja Maguluri. On the linear convergence of natural policy gradient algorithm. arXiv preprint 00002150..114, 2021.
Vijay R Konda and John N Tsitsiklis. On actor-critic algorithms. SIAM journal on Control and Optimization, 42(4):1143-1166, 2003.
Vikram Krishnamurthy. Partially observed Markov decision processes. Cambridge university press, 2016.
Shuai Li, Wanqing Li, Chris Cook, Ce Zhu, and Yanbo Gao. Independently Recurrent Neural Network (In- dRNN): Building A Longer and Deeper RNN. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognation (CVPR), pp. 5457-54466, 2018.
Shuai Li, Wanqing Li, Chris Cook, Yanbo Gao, and Ce Zhu. Deep Independently Recurrent Neural Network (IndRNN). arviv preprint ar Xic:119100000 06211,, 2019.
Long-Ji Lin and Tom M. Mitchell. Reinforcement Learning With Hidden States, pp. 269 278. The MIT Press, April 1993. ISBN 9780262287159. doi: 10.7551 0..755//mipprss/31166...000 URL http://dx doi. org/10.7551/mis 11551/mmtppess/3111 0038.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trus region poliey optimization attains globally optimal policy. arXiv preprint arXiv:1906. 10306, 2019.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary? In Conference Learning Theory, pp.
PMTR, 2022.
17

---

Published in Transactions on Machine Learning Research (10/2025)
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information. Processing Systems, 33: 7624 7636, 2020.
Chenhao Lu, Ruizhe Shi, Yuyao Lău, Kaizhe Hu, Simon Du, and Huazhe Xu. Rethinking transformers solving pomdps. arXiv preprint arXiv:2405.1 17358, 2024.
James Martens and llya Sutskever. Learning recurrent neural networks with hessian-free optimization. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 1883-1040, 2011.
Volodymyy Mnih, Nicolas Heess, Alex Graves, et al. Recurrent models of visual attention. Advances in neural information processing systems, 27, 2014.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Steven Morad, Ryan Kortvelesy, Matteo Bettini, Stephan Liwicki, and Amanda Prorok. POPGym: Bench- marking Partially Observable Reinforcement Learning. In International Conference on Learning Repre- sentations (ICLR) Workshops, 2023. URL https://openreviee .ew. http://oorriiiiicccrrttttto
Kevin P Murphy. A survey of pomdp solution techniques. environment, 2(10). 2000.
Tianwei Ni, Benjamin Eysenbach, and Ruslan Salakhutdinov. Recurrent model-free rl can be a strong baseline for many pomdps. arXiv prepriat wrXiv:2110.05033 05038, 2021.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparamcterization: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-105, 2020.
Shai Shalev-Shwarzz and Shai Ben-David. Understanding machine learning: From theory to algorithms.
Cambridge university press, 2014.
Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Learning without state-cstimation in partially observable markovian decision processes. In Machine Learning Proceedings 1994, pp. 284 292. Elsevier, 1994.
Nathan Srebro, Jason Rennie, and Tommi Jaakkola. Maximum maximum-margin matrix factorization. Advances in neural information processing systems, 17, 2004.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1): 1929-1958, 2014.
Richard S Sutton. Learning predict by the methods of temporal differences. Muchine learning, 3:9 44, 1988.
Matus Telgarsky. Deep learning theory lecture notes. https://mjt.com www.noii.iiii.......ooo.iiiiiiii edu/ /lt// 2021. Version: 2021-10-27 v0.0-c7150P2d (alpha).
Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Provably efficient rein- forcement learning in partially observable dynamical systems. Advances in Neural Information Processing Systems, 35:578 592, 2022.
Masatoshi Uehara, Ayush Sekhari, Jason D Lee, Nathan Kallus, and Wen Sun. Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings. In International Conference on Machine Learning, pp. 34615-34641. PMLR, 2023.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global opti- mality and rates of convergence. ar Xiv preprint or Xxx::19999000 0100000000,00000 2019.
18

---

Published in Transactions on Machine Learning Research (10/2025)
Steven D Whitchead and Long-Ji Lin. Reinforcement learning of non-markov decision processes. Artificial intelligence, 73(1-2):271-305 1995.
Daan Wierstra, Alexander Förster, Jan Peters, and Jürgen Schmidhuber. Recurrent policy gradients. Logic Journal of TGPL, 18(5):620 634, 2010.
Huizhen Yu. A function approximation approach to estimation of policy gradient for pomdp with structured policies. arXie preprint orXiv:1207.1421, 2012.
Huizhen Yu and Dimitri P Bertsekas. On near optimality of the set of finite-state controllers for average cost pomdp. Mathematics of Operations Research, 33(1):1-11, 2008.
Nicolas Zuechet and Antonio Orvieto. Recurrent neural networks: vanishing and exploding gradients are not the end of the story. Advances in Neural Information Processing Systems, 11:139402-13944 2024.
A Algorithmic Tools for Recurrent Neural Networks
A.1 Max-Norm Projection for Recurrent Neural Networks
Max-norm regularization, proposed by Srebro et al. (2004), has been shown to be very effective across broad spectrum of deep learning problems (Srivastava et al., 2014; Goodfellow et al., 2013). In this work, incorporate max-norm regularization (around the random initialization) into the recurrent natural policy gradient for sharp convergence guarantees. To that end, given an initialization (W(0), U(0), as in Definition 3.1 and a vector p = -Pw, Pu) E 1R30 of projection radii, we define the compactly-supporrtel set as
of weights 0pm C pm((+1)
pp.m {o (md++)) IW, Wa(0)) S
Pw max |IU U,(O)]I Vm
Pu m
(22)
Given any ric random initialization (W(O), (()) c) and E R30: the set 2p.m is compact and convex subset of gm(d+1), and for any O E 0pms we have
max S
W (o) v vm
|U; - U.(0))l S Pu
max Isis
mm
Let
Proje, [0]
arg min (O), ym
W -
arg min u. E. (U.10)
IU;
(23)
wEB.
vE[m]
As such, the projection operator Proje pm H onto 2pmm m is called the mar-norm projection (or regularization).
Note that we have || Pw: ||U Pu and ||0 ( S lellz in the f2 geometry for any θ E Pp.m. Therefore, although the max-norm parameter class 2p.m C (O E Rmid+1) ||O - (00) - [|pll2): the ez-projected Cai et al. (2019); Wang et al. (2019); Liu et al. (2019) and max-norm projected Cayci et al. (2024b) optimization algorithms recover exactly the same function class (i.e., RKHS associated with the neural tangent kernel studied Ji et al. (2019); Telgarsky (2021), see Section 3.1).
B Proofs for Section
An important quantity in the analysis of recurrent neural networks the following:
(1) (E: θ) = W.Hl! (5, ( O),
for any hidden unit E [m] and θ E Rm(d+1), The following Lipschitzness and smoothness results for θ, (z;))) and θ (f)
19

---

Published in Transactions on Machine Learning Research (10/2025)
Lemma B.1 (Local continuity of hidden states; Lemma 1-2 in Cayci & Eryilmaz (2025)). Given p R3 and 2 0, let am
vm Then, for any 2 (Y A) with supreN y/
1 E N and E [m],
a:
θ + H (Z:: )
Lipsschhit continuous with L, = (e0 + 1) (mmml))
, H1 (z) + 3m-smooth with Br = 0 (d (e(mm))) 2o (e(aml))),
θ + _ [2: ) is A--Lpsschitz with A: v2(e0 + 1 +mm Lt),
o , r (Zt θ Xt Xe-smooth with Xt = v2(L, + am3)),
in pp Consequently, for any θ 2pmm:
sup max [F((z 0) & Lr |lll2: T N, $E OSTST
(24)
2
sup (2; O))
mm (02 + -
e(0] L N,
(25)
2, ||l|
sup #
- 0) -- - (FF( -
(26)
m
with probability over the symmetric random initialization (W(O), U(0), c) Ço-
The following result builds on Proposition 3.8 in Cayci & Eryilmaz (2025), and identifies the approximation crror for approximating f E f by using randomly-initialized IndRNNs of width m. Unlike the supervised learning setting in Cayci & Eryilmaz (2025), the approximation error in the RL setting is P/ -norm
Lemma B.2 (Approximation error between RNN-NTRF and RNN-NTK). Let f E I with the transportation mapping v E H, and let
6 = 0,(0)
_c)(),(0))i [m].
(27)
Vm
for the initialization (W()), Co in Def. 3.1. Let
(!) voF((((()) (
If PT induces compaclly-supporter marginal distribulion for X,, 1 N such that ||Xe|la S a.s. and
[Z, e N} is independent from the random initialization (W(0), U(0), then have
2 1 + (a01)
ET
(28)
m
where the outer expectation is with respect to the random initialization (W U(0). c) ~ So-
Proof. For any hidden unit i E [m], let
G = (0)) Σ w. *o)
(2-x-12---11,0000 X(-k
II (2-;
j=0
Then, it is straightforward to see that
FLin (Z,;
= m
Σ So.
(29)
1=1
20

---

Published in Transactions on Machine Learning Research (10/2025)
and Z[ [l almost surely. Note that {sr i [m/2]} is independent and identically
distributed and Çi = S++m/2 for any E [m/2]. Also, with probability we have
(0) Σ W. (0)
12--, X1-b
k
I (2,,( II j=0
((()()))
a k+1 V
1 0
A=
||l| er V 1 eō Po(a))).
where follows from Cauchy-Schwaad inequality, follows from the uniform bound supzeR le(=)] s or and almost-sure bounds ||Xa]l2 and [W,:(0]| S a, and (0) follows from E Hy. From these bounds,
Var(<)) 1 |1c. 1 = || 11 (1 + p ie [m].
(30)
Therefore,
E
(Z.) - (Z,
(2: 9
=E
E
(5:
Elç, 2.1)
m
17
2 12
E
E
(4: R[G 21)
m
m/2 m2/2
4
E
E [(4 - Z.)) (S E,S Zx)),
4 Var(G)) - - - pa
E Σ
m
where the first identity is from Fubini's theorem, the second identity is from the symmetricity of the random initialization, the fourth identity is due to the independent initialization for i m/2, and the inequality is from the bound in equation 30.
Proposition B.3 (Non-stationary Bellman equation). For E NN we have
(T))) E" + Zi 2s E (r(). Ad + ( E0
for any t z.
Proof of Theorem 5.4. Since (Q te N) I, let the point of attraction è be defined as in equation 27, and the potential function be defined as
( ||0 - و
(31)
Then, from the exn-expansyvity of the projection operator onto the convex set 2p.ms we have the following incquality:
T-1
((O(++1) < ((O)))) 2n
(111 21 (32)
1=0
21

---

Published in Transactions on Machine Learning Research (10/2025)
Let E| = El-jo(k)................. ((0),,2) Then, obtain
T-1 7 R4
-) (()(A)) R
6)
t=
o VZ (k))
(33)
Bounding E( ). By using the Bellman equation in the non-stationary sctting (cf. Proposition B.3), notice
that
6. (z(11:
= ir + =
+ (Z,) - 0(())
Secondly, perform fhange-of-feature as follows:
(()) θ) (V))) ((K) A) +err
(34)
where
20/l|e11
2 |e
err, (1) := -V(1;000 -), and lerr S
m
m
by Lemma B.1. Furthermore,
(VE((2),00)))000) = =14m (z
(35)
(((Z);0(1)) (2,") + eer + err
(2)
(3)
(36)
where
(2) (Z, 0(k)) F.(Z;
err
err (3) - F.Lin (Z,, (2,))
Thus,
1 -2,1 1 2 (4+1() (2,) F((Z;;
3
1 0(:)) Σ
(i)
err
tkk
By equation 24, we have
sup $ElL
(5x(1 0())) r 22TT||lll 6max
Now, let Week == (Z)) F. (()))))) 1/2 where the expectation is over the joint distribution of (k)) and Z4. Then,
1.] < -w, + 70 + 8max
E Jerr
2,6l
==1
From equation 25, we have
E err
(2) t.k
<
2 Vm
(02A3 + eixT)
From the approximation bound in Lemma B.2, we gel
2||0|12
+ o7 pr (a
Elerr t.k
S
E Elerr 33)
m
22

---

Published in Transactions on Machine Learning Research (10/2025)
Also, note that W (wij + w2+1,)) Putting these together, obtain the following bound for every & E (0, ... 7 1):
)el S - + 2 3(u + wh,x) + dmax
CT
2
mm'
where
Cr = 11 2(e2 + eixr)llel1 21lullav 14 + eù pr(a0))
Hence, we obtain the following upper bound:
T-1
w/w + 8max Cr +
Σ B
) -1 (122
Σ
Σ ? ++
Wit1k
(1-7)
< 1 Σ 2
wwf + 2 w7, + (1 - 7mmm
Cr 8max
(37)
KT
Bounding E[( ].. Using the triangle inequality, obtain:
Σ KT
S
((K))l2
KI
Since (kk) E ppmm for every k E N as consequence of the max-norm regularization, we have
66 (z ((-)) s 6ax ro 2T. +2TT1|ll22.
(7, 1 Ve. H1 " 0())) < < 12
for every t < T with probability 1 since θ + H1 (1) (Z,; O;) is L,-Lipschitz continuous by Lemma B.1. Hence, we obtain:
Sma
(2R -
(38)
1-7
Final step. Now, taking expectation over (2, O()) in equation 33, and substituting equation 37 and equation 38, we obtain:
dmax Cr
+ 1/ 82 L2
E + 1)) - ((O())) S -n(11 - 7) Σ W b
+ + ",, + n (1 - 7m
(1 7)2
for every & E N. Note that v(e(0)) < ||113. Thus, telescoping sum over k= =
K - O.1,...,,K
yields
K-1
< ||013
1702 max L Ómax CT
7
K-1
K
Σ
(T((())))
11 <)K
(1 7)3 (1 7m (1 7)
+
T
(39)
K=0
k==0
The final inequality in the proof stems from the linearization result Lemma B.2, and directly follows from
Rr
1 K
Σ ((k))
4 Σ Rr(O(K) + 6 K R<K
Vm (e2 + eixr) 1le|
KEK
which directly follows from Cayci & Eryilmaz (2025), Corollary 1.
In the following, we study the error under mean-path Rec-TD learning algorithm.
23

---

Published in Transactions on Machine Learning Research (10/2025)
Theorem B.4 (Finite-time bounds for mean-path Rec-TD). For K N, with the step-size choice yy
(1-2)"
mean-path Rec-TD learning achieves the following error bound: 641.7
E (T(((H)))
2|11/3 Puuk + Crêmax & (1- () +
+ (CT)) + 16, 27 1 + 11011))
K
1-7 (1-7)2vm
RCK
where OT and Lr are terms that do not depend on K.
Theorem B.4 indicates that if noiseless semi-gradient is used in Rec-TD, then the rate can be improved from O (Vx) to O (R), indicating the potential limits of using variance-reduction schemes.
Proof of Theorem B.4. At any iteration h E N, let
VRr(O(A)) == B (((Z);
(40)
be the mean-path semi-gradient. First, note that
(VR -
(41)
Bounding ||Rr(0)) For any h E N, t < T, we have
E [55 2) c y [ 2 :: θ (2, +27 O)
Since VFF(2 θ) L,, the following incquality holds:
E [1
S | 3, < 11)
LT (rE -1 (1
(42)
where we used Jensen's inequality, the law of iterated expectations, and triangle inequality. From the above incquality, we obtain
(9)2(9))2
Σ 1110011
< LT7 Σ
E Fe+ ( - LT Σ
('E/ FF(2,;
KT
KT
3
LT
?E
(2
27, (2/g ) +
"1R( (2
1-7 ?
KT
K<
Lo
(')
E
(Z, 1)+ 11
E
-)) - (7,))
VI ?
K<
22 + LT || + ea pr(e1a) V1 -
Vm
where 1 follows from triangle inequality, 2 follows from equation 42, follows from Cauchy-Schware incquality and the monotonicity of the geometric scries T + EieT 7", follows from Jenson's inequality, and finally ① follows from Lemma B.2. Hence, we obtain
SLZ v 13 + (e1a)
[
(43)
(1 7)m
24

---

Published in Transactions on Machine Learning Research (10/2025)
Bounding [[())(((H) - ( First, note that
[VR)(((k)) (Rr(0))2 ||
Σ >* 06( <<T
6)) ||12
We make the following decomposition for each t t<? T:
100)
5, 6, 7 θ) 5,(2, (()))
0))
+ +F.( (()) (6. (2
(44)
2 0]1 - L. S LT almost surely for any O E 9 p.m. which holds for (k) (due to the max-norm projection) and + As such, by triangle inequality,
By Lemma B.1, we have | 0)1 S max and | P.
[ 611
[VRr(((()) - (RT(()12 v Σ n'
6max
L 6) - 5, (2 (,(2411;((()1
m
ETT
mmax
37 11111 + 12
+LT E
Σ 7 10,( Q) 1::21:10000
(45)
m
(4)
Note that
Σ (10) - 6 6,(2/11:001 KT
Σ >> (FF41 : + [F((Z))) - Fi(Z,; O(K))).
1<T
2
Σ 7d - ( + l)) - 0112.
(46)
KT
where the second line follows from the Lipschitz contimuity of F,(;; 0). Then, adding and subtracting Or to each term, we obtain
Σ 7/ - KT
0)1 2
Σ 7f -) (2))) - -F(Z))
KT
+ O1 (47)
Taking expectation, we obtain
2
E Σ 7 ((6)
E
-(1)
vI
7
KTT
2
E
(1F.( (2:3)) +r +ll2-
V1
L
By Lemma B.2 and equation 25, we have
4
+ 4 (e2 exxx))11l111
E[F((Z,;)) (2,)) <
1112 pp)
m
m
for any < T. Thus,
2
E Σ 18, ((K)) - (z θ)
01 VI-
E
> (()))
T
4
(1111201 (1 + 20)pr(oe1) + (62 + exx1)ll111) +-² Lr |0(k) - 1|| <||p||2+|
m v11 - 7)3
25

---

Published in Transactions on Machine Learning Research (10/2025)
This results in the following bound:
C
2
5, -. v
(--VRT(((K)))
+y
Lr(leell + (1ll1)))
(48)
VT-
vm
Substituting the local smoothness result in equation 48 into equation 45, obtain
2 VR2(0(()) - VR, VR, Lr
-Iーン ( (R)(0(())
C (3)
T L1 (llpl2 + [1uel22)
CT
+
Vm
m
Thus, obtain
1612 (VR)(((K)) - (O) S 1-7 Rr((())) + ) + 4(C)/)) L 1111))
(49)
Using equation 43 and equation 49 together, we obtain
Rr(((() (())((()) - (
1-7 (C7)²
16 2T L1 (11pl12 1111))
(50)
m
In the final step, we use equation 33, equation 37 and equation 50 together:
Crêmax
E + 1)) - ((O())) - 7) + " + "11 (1-7)ym
(32I)ERT(((())
(C,))
+ +
+ 16, 2T L (llell + 1m(1)) (51)
1-7
m
where the expectation is over the random initialization. Choosing (1-7)² 6447 we obtain
( + 1)) ((O()))) < 711 -)) ERr(((()) m
Crômax
TnTaar wT. + 77 (1 7m
2
n7² (Or)) 2
167 26 L (1lel1 +1x11)) (52)
m
Telescoping sum over == 0, 10.., K and re-arranging terms, obtain:
1 Σ (((((())
2|12113 FTTT (1 7nn
+ CTdmax +1 ((2))
+ 16, 14<0P111 + -1m11) (53)
E
K
1 1-7 2)-
K<K
C Numerical Experiments for Rec-TD
In the following, we will demonstrate the numerical performance of Rec-TD for a given non-stationary policy n7 greedyy
POMDP setting. We consider randomly-generated finite POMDP instance with [ r(s,a) Un 1] for all (s,a) S A. For fixed ambient dimension d 8, random feature mapping (v, a) + ply, a) ~ NO, La), V(y.a)~YYA..
A =8
e-greedy policy. Let
(*(t) E arg max Tj
05j<t
26

---

Published in Transactions on Machine Learning Research (10/2025)
be the instance before at which the maximum reward was obtained, and let
w.p. min{ 2+1
TO Pexp)
c- greedy (a
A
(54)
-a=
w.p. 1 - min{ 10 Pexp)
2+1
be the groody policy with a user-specified exploration probability Pexp E 10. The long-term dependencies in this greedy policy are obviously controlled by Pexpi a small exploration probability will make the policy (thus, the corresponding Q-functions) more history-dependent. Since the exact computation of (Ω7 )ren is highly intractable for POMDPs, we use (empirical) mean-squared temporal difference (MSTD) as a surrogate loss.
Example (Short-term memory). We first consider the performance of Rec-TD with learning rate " 0.05, discount factor y 0.9 and RNNs with various choices of network width m. For Pexp 0.8, the performance of Rec-TD is demonstrated in Figure 2. Consistent with the theoretical results in Theorem
(a) Mean-squared TD, T =
(b) 1 m
Σ, [1)())) (O)I,, =
1 (c) m
Σ.
W..(k) (0), T
Figure Mcan-squared TD and (mean) parameter deviation under Rec-TD for the case Pexp 0.8 and Y = 0.9. The mean curve and confidence intervals (90%) stem from trials.
5.4, Rec-TD (1) achieves smaller error with larger network width m, (2) requires smaller deviation from the random initialization ((0), which is known as the lazy training phenomenon.
Example 2 (Long-term memory). In the second example, we consider the same POMDP with same random samples, and an RNN with the same ncural network initialization. The exploration probability is reduced to Pesp = 0.25, which leads to longer dependency on the history. This impact can be observed in Figure 3c, which implies a larger spectral radius compared to Example (in comparison with Figure 2c).
375
418
325
333
200
1240 1480 1000 1000 2000
1900 18:00 2040
0006
(a) Mean-squared TD, T 8
(b) 1 (V.()) (O)) 8
(c) 1 Σ. Wi((k) Wo.( T 8.
Figure 3: Mean-squared TD and (mean) parameter deviation under Rec-TD for the case Pexp 0.25 and 0.9. The mean curve and confidence intervals (90%) stem from 5 trials.
In Figure 4, we investigate the impact of the truncation level T on the MSTD performance with Peo = 0.25, which implies long-term dependency, for an RNN with m = 256 units. Inereasing implies larger MSTD due to long-term dependencies, validating the theoretical results.
the empirical mean of independently sampled Erex (e(s) : kENN) NN where (TP(((()) Ei' (67(2);
27

---

P(s sss, (() Published in Transactions on Machine Learning Research (10/2025)
D Policy Gradients under Partial Observability
In this section, we will provide basic results for policy gradients under POMDPs, which is critical to develop the natural policy gradient method for POMDPs.
Proposition D.1. Let a' INNM be an admissible policy, and let Zσ PT v. Then, for any < T, conditional distribution of St given Ze is independent of n'. Furthermore, for any π LNN,, the conditional distribution of ((S,, + + (Ze+1) given Z₁ is independent of x².
Proof of Prop. D.1. Let the belief at time t N be defined
(((s) IP(S = s
(55)
For any non-stationary admissible policy the belief function is poliey-independent. To see this, note that
t-1
P(S, st, Zi = tz)
Σ
P(Sp = so|Yo (o 20)
II D 2x+1))
(1))...t_1)EE
k=
II
Σ
P(S. = solYo 3) II
(EE)
k=
since IT-= (x(ak(z)) does not depend the summands (su: .., 81-1) note that we the notation
P(sk+1 18h; an) = P(sk, un. (Se+1 8k+1)) and ((vn(s)) = (8*k, (Y=- = yk)). Thus,
be(st) E 1ES PSS so|Yo y) I1 P Iskk an (x) F(So = %/ 3) k= P(s 16 as (o)oor++1ls (5)42)
independent of æ. As such, we have
E" [r. + (2++)1)) =
Σ (s)) Ire + 7V4, = 2, St- =|,
SE8
Σ
bi(s)) (r(s;, A1) + P(sc-lls 1 (Zi, ((+1))
5156 18S DEY
= Err + ( =z]]
in other words, the conditional distribution of r r(S,, A,) + - (Z+41) given {2, 2 is independent of x². We also know from Prop. B.3 that
ET [r + 7VT 17 1 x,] B + (Z++) = (z.)
355
12400
200.00
2000
22203
Figure 4: MSTD performance with = 256 with various sequence lengths T with Pexp 0.25. Increasing T implies larger MSTD.
28

---

Published in Transactions on Machine Learning Research (10/2025)
The next result generalizes the policy gradient theorem to POMDPs. We note that there is an extension of REINFORCE-type policy gradient for POMDPs in Wierstra et al. (2010). The following result is a different and improved version as it ① provides a variance-reduced unbiased estimate of the policy gradient for POMDPs, and more importantly ? yields the compatible function approximation (Prop. 6.1) that yields natural policy gradient (NPG) for POMDPs.
Proposition D.2 (Policy gradient POMDPs). For any + E Rmid+1), we have
V&L" (n) = "
Σ r o At) V ( 1=0
(56)
for any μ E A(Y).
Proof of Prop. D.2. For any E N, we have
V (zt) = Σ क5 (a)l (2),01) (x)
(57)
ae
by Prop. B.3. Thus, obtain
VV (=)) Σ Vh (od==)) (z,, + Σ Va (z),
E"
(2, + (2i, znl.
(58)
Now, note that
2 (z,, az) = E(r(S Ad) +
= at),
= be(()) r(st, ax) + Σ P(eeall 0z)
be(st)
Σ
plutt be( (et))
8t41
where 2++1 (t. As consequence of Prop. D.1, we have V E., be(s))r(ss, ar) 0, and also
Vo (z), = = (8t) Σ 1188,1182000 (z)
Σ Heenl
8111
9111
= In + 2+1
14 14+ = (zx, at),
(A++ Zz
= =yE"
V
In
(Ax
2f (Zx, An) Ze = (2,, ar)
k=
Using the above recursive formula for V O along with the law of iterated expectations in equation 58, we obtain
Va (z)) Vx))"(())= = E="
V In In (Au (Au) 2F (Z Ab) Le 21)
(59)
Since we have V := V/ and also V+ (H) V. ((20))= (zo) Es, Vom" (20) by the linearity of gradient, conclude the proof.
(20)
Note on the baseline. Similar to the case of fully-observable MDPs, adding a baseline of" (21) to the @-function does not change the policy gradients since Σ. (e(a)z) In (alz)) (zc)
q:" Ea (al()) oi (z) En o. (alz))= 0. Thus, we also have
V (4) E.
Σ AAAT Σ
Vo (A
(60)
which uses of Vr the baseline, akin to the fully-observable case.
29

---

Published in Transactions on Machine Learning Research (10/2025)
The following result extends the compatible function approximation theorem in Kakade (2001) to POMDPs.
Proof of Prop. 6.1. The proof is identical to Kakade (2001). By first-order condition for optimality, we have
V In 2 (Arlz.) (v In (As] AA A (2i) = (C - VoDT =0;
2
t=0
which concludes the proof.
E
Theoretical Analysis of Rec-NPG
First, we prove structural results for RNNs in the kernel regime, which will be key in the analysis later.
E.1 Log-Linearization of SoftMax Policies Parameterized by RNNs
The key idea behind the neural Langent. kernel (NTK) analysis is linearization around the random initializa- tion. To that end, let
0) == (V e
(61)
for any O Im((+)) We define the log- linearized policy as follows:
exp(Trtin 05 ())
t (a|z)) En'e exp(Ptt (oo0ttt"(,, (2;aa;)))
LE N.
(62)
The first result bounds the Kullbac--Leibler divergence between म, + and its log-linearized version म," In the case of FNNs with ReLU activation functions, a similar result was presented in Cayci et al. (2024b). The following result extends this idea to (i) RNNs, and (ii) smooth activation functions.
Proposition E.1 (Log-linearization error). For any I E N and (z+,a) (Y x A)+1, we have
In mt (a|z))
sup ((xx))4)
(Aiez + Xxei) 1 (0)) Vm
(63)
(a|z))
for any N. Consequently, we have (-(2))) < (-12)) and #े (112,) & nt(-122), and
6
max (2KL (.1z)] (+1x),, DKa (7 (1)=)) (1=)))) (1 <
Vm ( e2 + xxei) 11 (00)
(64)
for all 2 E (V x A)++1 and t E N.
Proof. Fix (z,, a) E (Y x 1)+ By the log-sum inequality Cover Thomas (2006), we have
Σ. exp (P +)) Σ. exp(F((2(,,;))) D))
ln
Σ
(a|2)) (F, 1) ae(z,, ()))
aEA
Using the same argument, we obtain
E. exp( (F +)) E. exp(pF exp((F(2), +))
In
+ (a|zz) + o: (alz:) - (FL ④) - Fe(e,, T)
(65)
aEA
Thus, we have
म (a|=+)
< (1 + (a|z+) + -. (a|zz)) (z, :; Fe(Es, a; 4)
ni T (a)z+)
30

---

Published in Transactions on Machine Learning Research (10/2025)
By using Lemma B.1, we have ((FA)))) |F (2); @) #)(2 - /m (A] xi@i) - +(011 By
using the last two incqualitics together, and noting that + 5, (a|z1) + m. (a|z)) - 3, we conclude that
# (alzz) In x (a|z,)
S mm (Alez + xx (
Since the right-hand side of the above incquality is independent of (24, a), we deduce that the result holds for all (zt, a), thus concluding the proof.
The following result will be important in establishing the Lyapunov drift analysis of Rec-NPG.
Proposition E.2 (Smoothness of In #8 (a]z)). For any E N, have
sup (Yxa))(
V In
V In म. (a/z)ll2 S Li1 22112. (a|zx) (alza)
for any $ Φ e Im((++))
Proof. Consider a general log- linerr parameterization
(a( & 0), x E X.
Then, if supaex ||0=|12 < B < 00, then 0 + In (o(x) has -i-Lisschitz continuous gradients for each æ E X
Agarwal et al. (2020). The remaining part is to prove a uniform upper bound for Fi2 (00)]l2. To that end, notice that
Ve, (1,;;((000 1e---VVVi Vi, (2; ((0), & ( x A) i [m].
1 vm /
From
the local
Lipschitz
continuity
result in Lemma B.1,
we
have
sups sm (1 [V H (zn ((0) < L, for any e [m]. Thus, for any 2,, we have
m
V (0))
Va H (2)) (0)) L3
(66)
E.2 Theoretical Analysis of Rec-NPG
For any 1NNM, we define the potential function as
T-
-(x) : E
Σ
x' 2KL ( (1
(67)
Then, we have the following drift inequality. Proposition E.3 (Drift inequality). For any n N, the drift can be bounded as follows:
T
((xx(1+)) (n))) < -mpps (V (v= (1)) - yru (H)) By
Σ 7 (v In In (m)) (AolZe)un - AT m(n) (zi)
T-1
+ 1mpg ET
2' A ((n) (Ze)
Tmp
E
Vin
me
1(x) (Arlz))
4(1) (Ailz)) Wn V ग.
+ 2
1
Umpel
1
T-1
Σ
L
12 T-
Σ
eA + x
1=
31

---

Published in Transactions on Machine Learning Research (10/2025)
Proof. First, note that the drift can be expressed
T-1
((n) (A))
L( ((xx(()) = E
Σ
(A(l))
In
+ + (Arl21)
0
aE
Then, with a log- log-lincar transformation,
T-1
+(n++)) (ArlZa) {(n) (.))lze)
(P())) (Ar) ((x)) (Ar)
= (A.)Z))
L( - = E. t=
77 (A,
In
+ In n.
+ -In
aE
R
(Acl
((n+1)
(Ap)
By using the lgg-lnnerriation bound in Prop. E.1 twice in the above inequality, we obtain
L - - ET
क
(A,ZZ))
P(n)) (A, # In
12
Σ (A,ez xxer)llell. (68)
((++1) (At)Zz) H1
mm
By the smoothness result in Prop. E.2, we have
(((t (a.lz)) In a, (a) Vin V (a)=2))) +1 +(n))) S - 11 +1 -
In n.
Thus, we obtain
((x) (aglze)
Umpg 111pe12 S -mig ftllwall S - IIn
x
Tnps V In t
[(() (aelz))unn
He
(()+1)
(as (2+)
because of the max-norm gradient clipping that yiclds || S llellz and $(n + 1) = ((n) + Mmpghh for any n N. Using this in equation 68, we gel
(t (m)) < Mpps E
Σ V In म. (m)) (arlz))wn+ t=0
12 Vm
Σ t=
1 _ mnp pl
(69)
An important technical result that will be useful in our analysis is the pathwise performance difference lemma, which was originally developed in Kakade & Langford (2002) for fully-observable MDPs.
Lemma E.4 (Pathwise Performance Difference Lemma). Let $ Φ' Rm((+1) be two parameters. Then, we have
Drer (N) - 1x²² (1) E
Ap Ar).
t=0
The proof of Lemma E.4 is an extension of Agarwal et al. (2020) to non-stationary policies, and can be found at the end of this subsection.
Using Lemma E.4 equation 69, we obtain
T-1
( < Tnpg -TTpgg(" (v= (1) (x)- Min) (p)) (w)))(mmpg B
7 (v In In (") - A Apptm) (Zi)
((n)
12 T-1
Ex + Mapg
A (Z))
m(n)
+
r (A} l2 + xler + 2 Nmps L. (70)
p
m
Finally, we replace the term Vnn n, term, and conclude the proof by considering the telescoping sum, and noting that [I( = log [A] since (1(; by symmetric initialization.
((m) 12) with Vin n
(n)) (2) by including the corresponding error
32

---

Published in Transactions on Machine Learning Research (10/2025)
Proof of Theorem 6.3. We prove Theorem 6.3 by bounding the numbered terms in Prop. E.3. Bounding 1 in Prop. E.3. Recall that pr(7)= = ExeT Y. Then, by using Jensen's 's inequality,
(0() V In Tt
(Arlz))un - AA "1) (2i) 2 PT pT(
Σ
7
V
In Te
*(n) (1) (Aol -77 (Zx)
t=0
1=
=: V: RE (D) wn),
where & yields a measure argument from PT to PT (
Bounding 2 in Prop. E.3. supx.a (r(s, a)) I roo, therefore [A] (2,)
1-y for any t N (Y
A)++1, and π E NNNM-
Bounding 3 in Prop. E.3. For any E N, Cauchy-Schwarz inequality implies
V In n, ((m) (anlz)) - V Vln (ln (ailz))) wn S V In n, ((x) (aelze) - V Vln x (()) (ax) 122lell2
Recall that
V Vln V.i ((())))0))))))))))))))))))))))
Σ [a
PInmf(all2) VF, Φ) -) E VF(((2))
First, from local B--Lipschitzness of 4; +
(Ze 2,) (=;
for t 2pmm by Lemma B.1, we have
VV, (2, F(2 (0)) = 1
Va, (2) - Va, (2: (o)
Vm
Bellelee
m
for any n E N since max; (n( - (0)(0) S
Melk vm
by max-norm projection. Thus,
3llpll2
(()))) V ((E;) -
LEN.
(71)
Vm
Thus,
V In t, ((m) (a. - V In n. 4(m)
(a.l2))22 <
Bellel1z
(al2))
# ((m)) (al (2;
m
+
((n)
(2 Fi (00)
From equation 66, we have
V (()) (aclz)))) - V Ium, ((x) (arl=e)l2
<
28, 1elle
+ 22,
(Te (m) (+[=)) (()=)))))))))))))))))))))))))()
vm
where DTV denotes the total-variation distance between two probability measures. By Pinsker's inequality Cover & Thomas (2006), obtain
23.11pl1z V In # (1)) (ark)) - v In (()) I (arlz)l) <
+ v2L.// 9KL (., (")=()))) | (m)) (1(n))()a) (-120))
(72)
Fm
33

---

Published in Transactions on Machine Learning Research (10/2025)
By the log- rngrrincarinttinn result in Prop. E.1, have
2.ellpl1z vm
A2 + Xie
|V Vi 1 (aglz<)
(agl=))) - V In Tt ((m) [0)222)l22 S
+ v121, 101l
(73)
v mm
Thus, we have
(vin th (a) - -V m (a))(()))) wn S 11l12
23c .m
V12L,
A4 + Xx01
m 1/4
Proof of Lemma E.4. For any yo E V, we have:
00
Va (yo) VT((())))) = E
2'6 Zo To] 17' ('T))),
E
ri (Z,) vT()z) Zo = =00 (20),
E
7' + ( - -VT s0].
where r. = =r(S, A.) and the last identity holds since
x
Σ
(T) (20) + Σ Vi (V++((++1)
Then, letting ri r(st, at) and by using law of iterated expectations,
Va (uo) Va (vo) = B
7 E [r + (V - y0
(74)
1=U
which holds because
E [rx + 7V7h (Z(+ [| N [re + > (7++1) Zo).
The conditional expoctation of ? given {Ze = is independent of n':
ET [r: + 70 (Z++1))) = Σ (e(s) [ra + V2 Zz. St s),
sE8
Σ
Σ be
+(o0s-le (Z,,
(Zi, vc+1))
S1.81
JEY
= Blr + 7V 7 24 =,]:
based Prop. D.1. We also know from Prop. B.3 that
ET [r (Z+ म Bire + (2+122 = (E.)
Using the above identity in equation 74, obtain
2
yr (r() - yT (vo) E
Σ
7 (27 (Z:) - (2)) yo]
(75)
which concludes the proof.
34

---

Published in Transactions on Machine Learning Research (10/2025)
Proof of Prop. 6.6. For any w, we have
00
l (w; Q s 26r(w: ((n), (()) + Σ (A, m(n) (Zt, Ac) - (7,, A:))
(76)
Let In = (( S n) and Hn == (((()) n). Then, since
=gd, (ler(wn;; (n), ( 2,0 (0,p)
inf
((r(w;;(n)) )())))
we obtain
(ler(wn: ((n), 2 2m)im)) )|Hm]] S 2E inf Ele((w; (n). )17)) gm + 2(tdd, + Egg.,n),
(77)
which uses the fact that Var(X < [[ for any square-integrable X. We also have
inf E(er ((n), 17H s 2inf ((er(w: (n), Q" (()) 176,++2 Σ 7 (A, 2(n) (1) (Ze, ((. A1)) (78)
which further implics that
Blint (m)), )(m)) H..] S 2E[inl B[(r(w; (()), 2= |Hn]]Gn) + 20rd.
Thus,
(ler(wnn ((n). 2 HHm]] S 4E inf E[er ((n), )= )=)(())))))))) 11,, + -Etd,n 2Esgd,
(79)
For any E Blnd p),
[[er(w; (n),, Q (m)) [7Hn] S E
F. (2; (( OF (Z.))
KT
(V 4 FZ, (Z;; OF 4(n) (Z,))² + (VF.(Z; (()
$ 2E
which implies that
inf (w) e= ) |HHm]]
28 2aap..n + 211p||3L] - H..),
tT
< 2p + 211p11
Σ 8882
m KT
using equation 71. Hence,
Eler(wn: ((n), Q" 9(m) 176l )
811p112
Σ x0p SEapp.n 6.ed,n 25sgd,
m
concluding the proof.
Proof of Prop. 6.8. Under Assumption 6.7, consider f(0(zx)) 16(b (zei (ou)) for wl5) Hsg Let
w/th = 1 Go 1) (F, == 1,2....,m.
(80)
Vm
for any j E J. Since || 2 < ||l||2 and p z u, we have
inf wEst mn
v Fi(z;; ((0)ww - 1100 S V Ft(;;; (())) -!()(())
(z+)
(81)
(0.p)
35

---

Published in Transactions on Machine Learning Research (10/2025)
Thus, aim to find uniform upper bound for the second term over E J. For each 2, have
((()) 1
m Σ (2,00)000
thus [ (0))w()) = f1(00 (zt). Furthermore, from Lemma B.1, since ((0) E 9pm obviously, we have
VI H ( (Z () s L,lp/12 & Lellel12, a.s..
max 1S
Thus, by McDiarmid's inequality Mohri al. (2018), we have with probability least - 6,
V Fi(5; ( (z)) S 2Radm (Gt²) L log(2/5)
sup
(82)
JEJ
for each T and Σ. By union bound,
- Fi(2; (()) - (z)) < 2 max Radm (G + L log(27| x Al(t1/0)
sup max jEJ &
(83)
log(2T W x A/T
2 2 max max RGdm((ff)) + L 11llll22 0SteT
(84)
m
simultancously for all with probability 2 1 - 8. Therefore,
inf ET
s(n)
Σ 1 FZ ((0)
1100
v(n) /
Σ
1h sup / (())vu()) - -1(0)2
KT
KT
jEJ
log(2T Y A /8)
max max Radm (G²²) LT 1111ll2 0St<T
7
m
36


Reviews:
[{"review_id": "iVqyxmJYzE", "reviewer": "Reviewer_76rN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* POMDPs are a hard problem and RNN-based algorithms are a standard approach that are lacking guarantees. This paper proposes a way to get such guarantees under some assumptions on the representation. \n\n## Major comments\n\n* This paper combines many technical ideas from previous work and relatively non-intersecting fields (POMDPs and MDP algorithms, neural network theory, optimization) so it is fairly difficult to understand well without the full background on all these topics. Typically, section 3.1 introduces \"IndRNNs\" based on Cayci & Eryilmaz (2024), as \"a class of learnable mappings by RNNs in the so-called kernel regime, extending the function classes in previous literature on neural RL methods\". That's quite a mouthful and also I am not sure I understand what this sentence says. What are \"learnable mappings by RNNs\"? This is the part of the background literature I know the less and I think it could deserve a little bit more intuition and explanations in plain English. This part is clearly instrumental in getting the convergence rates but it feels quite orthogonal to the algorithm itself so I think it could also be placed differently because at the moment it stands in between the problem formulation and the algorithm description in a perhaps awkward way. \n\n* In the same vein, section 4 describes the overall algorithm and pushes the critic to section 5, but then section 6 comes back on the actor. Why not explaining the actor fully in section 4. I think the structure of the paper needs some more thoughts. \n\n* Theorem 5.4: there is a middle term that does not go to 0 with K (only with m). Is that okay? How do you justify this? Also it is stated with \"Rec-TD with max-norm regularization\" but where is this regularization in Algorithm 2?\n\n* You gave up on running any experiments? This is definitely a theory paper and I think it has enough contributions as such, but when one claims to bridge theory and practice, it is a lot more convincing if practice also aligns with the findings so the absence of experiments should be justified. Why did you not run any experiment? \n\n## Minor\n\n* I was confused in Algorithm 1 by \"where Q=...\" while there is no Q in the equation above. You want to say \"where A=... and Q=...\" because Q is in A.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is a theory paper proposing a Natural Policy Gradient algorithm (actor-critic) for POMDPs and showing convergence guarantees under a number of assumptions. \n\nThe idea  and main contributions are the following:\n* Parametrize the policy (actor) with an \"Independently recurrent NN\" (section 3), which simplifies the training dynamics and allows to get convergence rates,\n* Use a TD-learning algorithm for the critic (section 5) and get convergence bound on the risk (th 5.4), ie on the approximation of the Q-function.\n* Use NPG for the actor updates (section 6), which is now a non-stationary policy due to the POMDP, and prove error bounds on the best iterate (th 6.3)", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* improved writing and paper structure\n* comments and intuitions for section 3\n* experiments?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vEYvIx6b6r", "reviewer": "Reviewer_qNLx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The finite-time bounds result for Rec-TD is novel and valuable as it quantifies the error in terms of the network width, number of iterations, and memory horizon.  The results show that the error bound decreases with the number of iterations and the network width, which is expected. But It also shows that there is an additional term that depends on $\\gamma^{T}$, which clearly indicates the difficulty of dealing with long-term memory problems where $T \\rightarrow \\infty$.\n- In Theorem 6.3, the paper shows the error bounds for the Rec-NPG. The results show how the error bounds depend on a few things: 1) The number of iterations, where the error obviously decreases as we do more iterations. 2)The network size, increasing the network size, reduces the error. 3)The truncation horizon, we again see the $\\gamma^{T}$. These results align with the analysis of the Rec-TD, but it’s valuable to see the consistency of the results when we move to the control setting. \n\n### Weakness: \n- In the abstract and again in the introduction and Section 5.1, it is mentioned that the paper studies multi-step TD; however, the theoretical analysis and the algorithm only use one-step TD errors. \n- In Independent RNNs, the W matrix is diagonal. However, the analysis still involves matrix-vector multiplications with W, which unnecessarily complicates the maths.\n- The notations used in Definition 3.1 were not properly introduced. It’s unclear what W(0) and U(0) mean. \n- The theorems need more explanations on what they show.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper analyzes some of the theoretical properties for combining diagonal recurrent architectures with natural policy gradient methods to solve POMDPs. \nThe paper asks three important questions that are nicely built on top of each other. Starting with the policy evaluation setting, the paper shows that using IndRNNs with TD for policy evaluation (Rec-TD) can achieve a near-optimal solution, and it characterizes some issues that appear when dealing with long-term memory. Then, moving to the control problem, the paper discusses the use of IndRNNs for policy parametrization (Rec-NPG). Finally, the paper then analyses the combination of Rec-TD and Rec-NPG and shows that there’s an exponential growth in the resources required when dealing with long-term memory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- A brief discussion on how this analysis could be extended to a Dense recurrent layer would be a nice addition. I am not sure where the diagonal properties of the IndRNNs were used in the analysis. \n- Changing the matrix-vector multiplications with W to element-wise multiplications would make the maths more readable. \n- Remove the multi-step TD claims.\n- Include a limitation section discussing which of the assumptions made are reasonable from a practical view and which are more constraining. \n- Previous work [1] has analyzed the exploding gradient for diagonal recurrence, proposing that a simple normalization on the inputs mitigates this issue. I wonder if having such normalization would help get rid of the exploding issue in the analysis. Maybe a brief discussion on how this affects the bounds of the critic error is useful. \n\n\n\n[1] Zucchet, Nicolas, and Antonio Orvieto. \"Recurrent neural networks: vanishing and exploding gradients are not the end of the story.\" Advances in Neural Information Processing Systems 37 (2024): 139402-139443.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hv6Sgp6ud3", "reviewer": "Reviewer_q1Mw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The work is sound technically, and its presentation is clear. The RNN-NAC class of algorithms are important in solving POMDP and the provided analyses significantly improve understanding on these algorithms' behavior.\n\nThere are no major weaknesses in my view, but addressing some of my clarifying questions (cf. Requested Changes) may help strengthen the work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work pioneers the formal analysis of a class of NAC algorithms, which uses RNN to represent both their critic and actor to circumvent POMDP challenges, i.e., a “PO” setup implies the need to keep the policy search space to history-dependent and randomized but such search (without tricks like RNN or other form of memory retention/policy representation) implies exponential memory complexity and non-vanishing optimality gap. Authors obtain error bounds (gap to “optimality”) for both policy evaluation (Rec-TD with max-norm regularization) and policy optimization (Rec-NPG best-iterate), where dependency on memory (T), time/iteration (N), sample (K), and RNN class specification (e.g., $m$, $\\varrho$, $\\alpha_m$, $\\rho$, $\\nu$) are characterized explicitly, under some conditions. When these gap vanish (or not) are further discussed; some of which reveal long-term memory as pathological case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "[1] On the long-term memory pathology case of Theorem 5.4, it seems that “long-term” here (as discussed below Remark 5.6) refers to the choice of RNN ($\\alpha$, $\\varrho_1$). Should I understand this discussion as a guide to avoid setting my $W(0)$ and activation in the way that $\\alpha_m > \\frac{1}{\\varrho_1}$? Or is this long-term memory setting unavoidable (or even useful) in certain circumstances (say, for RNN training aspect separate from bounding the Rec-TD error)?\n\n[2] While the long-term pathology source seems to come from the choice of RNN (cf. Qn [1]), it seems that the long-term memory illustration in Random-POMDP (Appendix C) refers to a different source, i.e. exploratory policy with small exploration rate. While I can understand that small rate does cause longer historical dependency, I can’t seem to see this in the term $p_T(\\alpha_m*\\varrho_1)$. Is it related to another term in Eqn (10)? Or should I understand Appendix C separately from the bound in Eqn (10)?\n\n[3] On Theorem 6.3 providing best-iterate error bound, am I right to understand that this bound does not guarantee the algorithm to avoid divergence or collapsing? If true, can Authors provide some intuition on (a) what currently prevents obtaining stronger results, (b) when divergence/collapse might happen during training, how likely or unlikely?\n\n[4] Am I right to understand that with RNN encoding, errors that are originally dependent on memory ($T$) are transferred into RNN approximation error, s.t. “boundedness” now relies on the assumption that RNN class is rich enough to suppress the error? If true, is the specific RNN class in Section 3 chosen to supply such richness? Can Authors discuss the necessity of NTK IndRNN, e.g., whether an alternative class of RNN may cause some terms in the current Error bounds to possibly explode?\n\n[5] To speak form algorithmic perspective, I would want to know how I can utilize the obtained bounds here to guide my hyperparameter (both RNN and RL) choice. While I understand that some Assumptions are difficult to flesh out and some terms rely on the POMDP instance, it would be useful to discuss some examples of when the theoretical bounds can directly translate to training guidelines. Perhaps Authors can expand from the short-term vs long-term memory discussion in Sec 5.2.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)