Scalable Policy-Based RL Algorithms for POMDPs
Authors: Ameya Anjarlekar
S. Rasoul Etesami
R. Srikant
Venue: NeurIPS 2025 poster ()
Keywords: Partially Observable Markov Decision Processes
TD Learning
Reinforcement Learning
Primary area: reinforcement_learning
TL;DR: We provide approximation bounds for an approach that solves a Partially Observable Reinforcement Learning (PORL) problem by approximating the corresponding POMDP model into a finite-state Markov Decision Process (MDP)

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

Scalable Policy-Based RL Algorithms for POMDPs
Ameya Anjarlekar
S. Rasoul Etesami UICC @resami1@111inote edu
UIUC
ameyasa2@illinois.
R. Srikant UICC
Derikant@illinoi..
Abstract
The continuous nature of belief states in POMDPs presents significant compu- tational challenges in learning the optimal policy. In this paper, consider approach that solves Partially Observable Reinforcement Learning (PORL) prob- lem by approximating the corresponding POMDP model into finite-state Markov Decision Process (MDP) (called Superstate MDP). We first derive theoretical guar- antees that improve upon prior work that relate the optimal value function of the transformed Superstate MDP to the optimal value function of the original POMDP. Next, we propose policy-based learning approach with linear function approxima- tion to learn the optimal policy for the Superstate MDP. Consequently, our approach shows that a POMDP can be approximately solved using TD-Jearning followed by Policy Optimization by treating it as an MDP, where the MDP state corresponds a finite history. We show that the approximation error decreases exponentially with the length of this history. To the best of our knowledge, our finite-time bounds are the first explicitly quantify the error introduced when applying standard TD learning to setting where the true dynamics are not Markovian.
Introduction
Reinforcement learning (RL) provides robust and systematic framework for solving sequential decision-making problems by modeling these problems as Markov Decision Processes (MDPs). However, many real-world systems such as robotic controllers must operate under uncertainty, handling incomplete, noisy, or ambiguous data, making traditional RL techniques ineffective for such problems Cassandra al. [1996].
To address such challenges, partially observable reinforcement learning (PORL) extends the RL frame- work by modeling these problems as Partially Observable Markov Decision Processes (POMDPs). This approach accounts for hidden states, enabling effective decision-making under uncertainty. Beyond these applications, PORL is widely applied in areas such autonomous driving Levinson et al. 2011 personalized content recommendations Li et al. 2010), medical diagnosis Hauskrecht and Fraser 2000), and games Brown and Sandholm [009 where decision- makinn under partial observability is crucial. As a result, addressing decision docision-maaiin making under uncertainty has become critical topic across diverse fields such as operations research and healthcare.
Although POMDPs provide a general framework for modeling decision- decision-making under uncertainty, solving them presents significant computational challenges even when the exact model of the POMDP is known. The early works of Smallwood and Sondik [1973] Aström 1965) focused on the planning problem and effectively converted POMDPs into MDPs via belief states. However, the continuous
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

nature of belief states and the SEPACE--competeer of solving POMDPs/Papadiminni and Tsissiklis [999]. Vlassis et al. [012] make these problems computationally intractable.
Various approaches have been proposed to address these limitations, with the aim of providing approx-
imate solutions for learning POMDPs by selecting actions based finite history of observations.
For example, Jaakkola et al. [994], Williams and Singh] 1998). Azizzadenesheli et al. [2016] select actions based solely on current observations, while others, such Loch and Singh 1998 Littman
1994]. consider past & observations to guide decision making. Nevertheless, while these approaches demonstrate empirical success, they lack rigorous theoretical performance guarantees.
In contrast, for learning fully observable MDPs, a wide range of Reinforcement Learning algorithms exist with provable sample complexity bounds, ranging from as Q-learning to policy-iteration-ban -baeed algorithms such as actor-critic and natural policy gradient (NPG). A comprehensive survey of these algorithms can be found in Bertsekas and T'itsiklis 1996 and (Sutton and Barto (2018).
approaches such
The empirical success of finite-histond seattehisttrr--baeee algorithms for POMDPs and the availability of perfor- mance guarantees for standard RL algorithms motivate a critical research question: Can we leverage standard RL algorithms to approximately learn optimal policy for POMDP by treating it as MDP, where the states correspond to the finite histories? Specifically, can we establish theoretical performance bounds for such approach?
In this paper, we address this question by considering a previously proposed approximation by Kara and Yüksel (2033 that maps POMDP to a finite-state MDP, called the super-state MDP by restricting the information at each time instant to a finite history of past observations. However, this approximation is difficult to study for the following reasons:
It is unclear whether using standard TD learning as the policy evaluation step in a problem where the true model is POMDP would result in good performance or even convergence.
The TD learning algorithm used in Cayci et al. [2024] uses m-step version of TD workaround, which is computationally more expensive than standard TD learning.
In view of the limitations of the prior work, our main contributions are stated as follows:
Approximation guarantees for POMDP to MDP transformation: A standard approach to assess the quality of a transformed MDP is to bound the difference between its optimal value function and that of the original POMDP. In prior work such as Kara and Yüksel (2023)
Subramanian and Mahajan 2019), this difference is bounded by the square of the expected horizon length, i.e., (I-y]z where y is the discount factor, while, Abel et al. (0016) provides
a bound of 1 [I-y)0 and the bound in Cayci et al. (2024) is polynomial in the horizon length. We improve upon these results by providing lighter bound. Additionally, while Kara and Yüksel 2023] provides bounds on the expected difference between the optimal value functions, establish a stronger worst-case bound.
A General Purpose Algebraic Identity: A key reason for improved bounds is the in- troduction of a novel algebraic result, i.e., Lemma which proves effective in bounding expressions of the form Em_ c,d,)), when vectors (a, c) and (b, d) are close to each other, and (b, d) corresponds to probability mass functions. Traditional approaches rely on decompositions and triangle inequality, often leading to loose bounds. contrast, our refined approach yields tighter guarantees, improving the existing bounds.
Our algebraic result is of broader interest and can be used to improve bounds in other analyses. As an example, we refine" the performance bounds in Subramanian and Mahajan [2019], which introduced approximate information states but lacked systematic method for constructing them. Additionally, while their deep learning-based approach provides an empirical solution, it optimizes an objective misaligned with the theoretical guarantees.
Addressing Challenges in Policy Optimization: Having established that the Superstate MDP is a strong approximation of the POMDP, we investigate whether standard Policy Optimization algorithms can effectively learn its optimal policy. A key challenge arises from the fact that learning samples correspond to belief states of the original POMDP rather
Proof is in the Appendix.

---

than the Superstate MDP, creating a sampling mismatch that raises concerns about whether applying standard RL techniques can yield strong performance guarantees.
Cayci et al. [2024] addresses this issue by modifying the TD-learning part of Policy Op- timization by employing an m-step TD-learning approach, leading to significantly higher work is the first to establish convergence guar- antees for a standard policy optimization algorithm that alternates between learning the Q-function for fixed policy using ID-learning and updating the policy accordingly. This avoids additional computational overhead while providing stronger theoretical guarantees.
computational complexity. In contrast,
Performance Bounds for Linear Function Approximation Setting: Apart from Cayci et al. [2024] which leads to higher computational cost, Kara and Yüksel [2023) considers Q-learning to learn the optimal policy for the Superstate MDP. However, along with relying ergodicity assumptions, their approach faces significant scalability challenges due to the difficulty of proving convergence for Q-learning with linear function approximation. In contrast, develop performance bounds for the Policy Optimization Algorithm and extend our analysis to the function approximation case, enabling scalability to large state spaces,
A key challenge in proving convergence for Policy Optimization algorithms lies in the non-stationary nature of the sampling policy during the TDDlearning phase. In contrast, the Q-Learning approach in Kara and Yüksel [2023] leverage stationary exploratory sampling policy, simplifying the analysis. Additionally, they assume an additional ergodicity condition and provide only asymptotic convergence guarantees. In comparison, our approach avoids such restrictive assumptions and establishes finite-time performance bounds.
Finally, another minor contribution of our work is to extend the analysis for the POLITEX algorithm in Abbasi- Yadkori et al.) (2019) to the discounted reward setting and analyze the regret of our algorithm with respect to the optimal value function of the POMDP.
2 Related Work
Planning algorithms for POMDP: Early POMDP algorithms assumed full model knowledge and focused on exact belief-state calculations. Techniques such Witness algorithm Cassandra et al. 1994). Lovejoy's 's suboptimal algorithm Lovejoy 1993). and incremental pruning Zhang and Liu [996] were aimed at making planning more efficient. Comprehensive surveys be found in Krishnamurthy (2016). MMurhyy] (200)] However, these approaches suffer from exponential complexity growth due reliance on precise belief-state calculations, limiting their practicality.
Using internal state representations to solve PORL problems: To address the challenge of continuous belief states, internal state representations have been proposed. Works like Jaakkola et al.
[1944), WWiliams and Singh [1998). |Azizzadenesheli et al. (2016) select actions based solely on
current observations, Woile|Loch and Singh] [ [998). |Lttman 1994]. consider past k observations to
guide
Additionally, sliding window control lers Williams and Singh [1998] Loch
and Singh (1998), Iara and Y Yüksel| [203). [Sng et al. [ Yu 2005] Cayci and Eryilmaz 2024]
Amiri and Magnússon| (2024) and memory- based techniques McCallum [1993.. Meuleau et al. 1999
have demonstrated practical success. However, most of these methods are heuristic and lack formal
guarantees.
Learning algorithms with provable guarantees: Recent efforts have focused on developing algorithms for solving PORL problems with theoretical guarantees. Du et al. [2019), EEroni et al. [2022) provide provable bounds, though these rely on the state decodability assumption, which implies that finite history of observations can perfectly infer the current state. Other approaches
Wang et al. 2022 Liu et al. 2022 Jin et al. 2020 target specific subclasses of PORL problems.
Deep learning inspired techniques: It is also worth mentioning prior work on empirical approaches using deep learning. In particular, recurrent neural networks (RNNs) Hausknecht and Stone (2013), Wierstra et al. [2007) and variational encoders Igl et al. 20188) have been used to model the uncertainty PORL by capturing temporal dependencies. While these techniques have demonstrated impressive empirical results, they lack rigorous performance guarantees.
3

---

3 Problem Description and Prior Results
In this section, we introduce the problem formulation and review some well-known prior results; for basic POMDP theory, the reader is referred to Krishnamurthy [2016].
3.1 POMDP Structure and Notations
We consider general finite-state POMDP model, which can be characterized as follows:
Consider set of finite states S, with the state of the system at time denoted by 8 E S, which is not observed. Also, assume that the initial state So is sampled from a distribution D, with the corresponding probability mass function represented by the vector To-
At any time f, the agent chooses action a from finite set of possible actions A, where, for simplicity, we assume that all actions from A are feasible for every state. The state then evolves according transition probability
P(s' s, s, = (s s'
s, a))
Morcover, the agent receives a reward r(s, a). which is the reward obtained if performing an action in state where assume finite reward, i.e., there exists such that [r(s, a) S F Vs, a.
Since states cannot be observed, we assume that information about them at each time is obtained through noisy discrete observation channel whose output Yt E y is chosen according to conditional distribution ( s) == P(y y St = s), where y is a finite set of observations. Therefore, after agent takes action az, it receives reward and observes V-+1-
Let H, foo, y1, 21,01. di.,a...... 0,., Ve) E TH be the entire observed history up time f, where H refers to the set of all possible histories (of any length) of the POMDP. Given a history H H and an initial distribution To over the states, denote the probability of being in state by ((8 H) P(s To) and define the belief state given history H by * x(H) (i(s sess In particular, the belief state] belongs to B C E(S), where
E(S) (a R E IG 1), and B refers to the of all possible belief states that can be realized using a history H E TH. Now, if at time i, the agent takes an action de and observes yt y. by Bayes' rule, the belief state can be updated follows
Ed ( 8 aa) ((s Ho) E. Eyr(s' H(-1)P(s" ( s")²
(1)
where H H, \ (yt,a,) Therefore, any belief state π x(H) be calculated recursively from the history H and using the belief update rule ①1 with the belief at f = given by πо-
The agent's goal learn the optimal policy (defined more precisely the next subsection) through sequential interactions with the environment.
3.2 Belief State MDP Representation of the POMDP
We note that POMDP can be reduced to a fully observed MDP by considering the belief states as the states of the MDP. This is discussed in detail below:
For any belief state let r(T, (s))sss), Thus, the POMDP reduces fully observed MDP where (π, E B x represents a state-action pair and r(T, a) is the corresponding reward for that state-action pair with the state transition law given by Eq. (I).
For any belief state π E IB and any policy p. we define the value function V/ (TT) as
V²( = E
(r(( at) ) To Tr).
(2)
t=0
where the belief states n. == π (H,) evolve using the update rule 1. when the actions are taken according to a, ula T:) Vt 2 0 with the initial belief state лo Here,
When there is ambiguity, drop the dependency of belief state on the history and write (H))

---

Y E [0, 1) is a discount factor. Our goal is to find an optimal policy (a π) corresponding each belief state π to maximize the expected cumulative discounted rewards (T))
For any belief state π E IB and for policy μa, we define the Q-value function as
(T, = E Σ (TT( at) no = π, 40 = =
where the belief states n., evolve using the update rule Og ulaa πT)) 4I
T and the actions taken according
1.
3.3 Bellman's Optimality and Uniqueness of Solution
Here, first present result from Krishnamurthy (2016) showing that the optimal value function satisfies Bellman's Optimality Equation, which can also be used to establish the existence and uniqueness of optimal solution to the POMDP.
Theorem Consider infinite horizon discounted reward POMDP with discount factor [0, 1), and finite state and action spaces S and A, respectively. Then,
1. For any belief state E IB, the optimal expected cumulative discounted reward max, VP(TT) is achieved by a stationary deterministic Markovian policy p".
2. For any belief state x rHH E TB, the optimal policy je and the optimal value function V satisfy the Bellman's 's Optimality Equation:
V. (T(H)) = max Σ ((s)H)((s,a) + Σv" (T(H (M(211 aEA
SES
ycy
where (H)) y. a) denotes the probability of the observation being y conditioned on the previous belief state being π π(H) ()) and action o. is taken, which can be calculated explicitly as ( (H), 1. a) = Σ., Φ(y 8')P(& ())
3. There always exists unique solution to the Bellman Optimality Equation 3
Let us denote the Bellman optimality operator in by T()). Also, let n² be the optimal policy and V V*" be the optimal value function. Then, the optimal value function V* satisfies the fixed-point equation
V = T(V*).
Therefore, using Theorem ! for any belief state π = T(H) E B, we can write
V (*(T) aed (T(T,a) + Σ (T(( (
Note that reducing the POMDP to an MDP using the belief-state formulation does not solve the problem of finding the optimal policy using reinforcement learning. This is because the belief states depend on the history, whose length increases with each time step. In the following section, we present scalable approach to bypass this intractability in solving infinite horizon POMDPs.
Algorithm and Theoretical Results
In this section, we describe our solution approach, develop an algorithm for approximately solving POMDPs, and provide theoretical guarantees on the performance of the algorithm.
'The symbol || denotes cocatenation. For example if H [yo, ap, yr, 41 then, H || [y.a) = (yo, ao, y1, 01.01.4. a.
5

---

4.1 Defining an Approximate MDP Using Finite Observations
Definition Given a POMDP and a fixed constant I N, let Hig be the set of all histories of length at most I. We refer to any element of H4s as Superstate. Moreover, we define G H - Hlg as the grouping operator for any finite-lnngth history E H. it returns the superstate obtained by truncat- ing H to its last I action-observation elements. In particular, if H = {00, y1, ................................ -1 Vt then
((H+) ((0max(12-441)ittt 00 (0=))(1=)):::-))
Vt
Next, we construct an MDP which consists of states corresponding to the Superstates. Since the number of Superstates is finite, resulting Superstate MDP is finite-state MDP, which can then be solved using existing RL techniques for finite-state MDPs in the literature. The Superstate MDP defined as follows. For every pair of Superstates B, B' E Hig, define
F(B,a)= 10000>nm :(s B) r)(,
(4)
P(B'| B,a)= Σ (B = B" 21 ())((sss)P(('' a)a)((s) B),
(5)
3.5,8'
where 1[-] is the logic indicator function and B {3/. a} means that the action-observation pair {y. }} concatenated to the end of the superstate B. Since the action and state spaces are bounded, an optimal value function always exists for discounted MDP with bounded rewards. Let (-) be the optimal value function for the Superstate MDP, which satisfies the following fixed-point equation
V = T(V),
where 7' is the Bellman's optimality operator for the corresponding Superstate MDP, Therefore, for any superstate B E Hig, we have
((V(B)
F(B,a)+ +7 Σ (.A)
max aεA
Now, for a policy y that is stationary with respect to the superstates, let define the Bellman's operator T by
T*(V(() = E F(B.a) + EP('' B.O)V(B)) VB E Hgg.
Then, the value function of the Superstate MDP with respect to policy μ. denoted by Va, must satisfy the fixed-point Bellman's 's operator, i.e.,
V v"=1"(("))
4.2 How good is the approximate MDP?
In this section, we compare optimal value function of the POMDP, denoted by V*, with optimal value function of the Superstate MDP, denoted by V. We will show that error between these two optimal value functions decays exponentially with the length of the truncated history I. To that end, we first state a standard assumption in filtering theory, i.e., the Uniform Filter Stability Condition, also used in prior work van Handel 22008,, which would be needed for our analysis to relate V and V. This condition ensures sufficient mixing, preventing the system from being trapped in a subset of states.
Assumption [Uniform Filter Stability Condition] Given any ग. T'' E E(S), and any a, y, let Ka.y be an operator such that
(Ka,y 2 v)( = E(s) s' (y s)
U('))) ((s)) s', a) 8")
Then, there exists p (0, 1) such that for any n, E(S), we have
Kay & n lrv (1 (1-p) p) || x 11zv Va A. y E y 'By notation yru = Eyr, ... yet } and ar:t = {ar; art1...., at) for any integers r S t. 'II Iyzv is the total variation norm
||aa,y

---

4.3 Intuition about Assumption 1
Assumption ! i.e., the Uniform Filter Stability Condition means that every new observation suffi- ciently informs the agent to reduce differences between any two prior beliefs ensuring the belief state "forgets" initial uncertainty and the filtering process is well- sell-behaved.
Now to ensure that the filter stability condition holds we need
1) Sufficiently Mixing State Transitions: The transition kernel P(s' s.a) should be mixing, meaning from any state s, there's positive probability to reach many other states s' over time.
2) Non-deterministic and Informative Observations: The observation kernel ( 8) must be non-deterministie but sufficiently informative, i.e., observations must have some noise or randomness.
To check whether the filter stability condition holds, one sufficient condition uses the Dobrushin Coefficients of the Transition kernel and the Observation Kernel.
From Theorem 5 of Kara and Yuksel 2020). if (1 - (1 (()) 1, then the filter stability condition holds. Here D(P) is the minimum Dobrushin coeffient of the Probability Transition kemnel across all possible actions and ((+) ) is the Dobrushin coefficient of the Observation kernel.
For example, the Dobrushin coefficient for the Probability Transition matrix 8(P) is defined as:
8(P) = =inf inf
min (P(z x a),), P(z y. v.)))
LI,EES
ZES
The term inside infa quantifies the minimum overlap between any two rows of the matrix P(. I., a).
Therefore, this quantity measures how similar the rows of the matrix are; smaller values indicate more mixing and hence, stronger contraction properties. As a result, when there is sufficient mixing-ie.. when every state has a non-trivial probability of transitioning to several other states or when every observation can be generated from multiple underlying states -te system exhibits filter stability.
This scenario is common in highly noisy or dynamic environments, where the belief update less sensitive the prior and more influenced by new observations. We also present in the Appendix B..l a model for a practical example where Assumption [ hholds
Additionally, for applications that do not satisfy Assumption [ one could consider multi-step variant where the system exhibits contraction after every & steps. We believe our results could be extended under this milder assumption, making it promising direction for future work.
Now, using this Uniform Filter Stability Condition, we prove Lemma states corresponding to the same Superstate are close to each other in terms of total variation distance. Further, the distance decays exponentially fast with the length of the truncated history.
which shows that all belief
Lemma 1 Let H and H' be two different histories corresponding to the same superstate, i.e.. g(H) = (HH). Then, under Assumption !
we have
[T()) - (H'' (1- p))
(6)
If two histories belong to the same superstate, their sequences of (action, observation) pairs over the past / steps are identical. Lemma] leverages the intuition that sufficiently informative observations allow the recent history to capture the current system state. Consequently, starting from different initial beliefs, the combination of informative observations and strong mixing ensures that, after enough time, the resulting belief states converge similar distributions.
Next, we establish an algebraic inequality that will be used to obtain tighter optimality bounds.
Lemma 2 Let a, b, c, d R be positive vectors such that E a; Em C; 1. Then,
a,b Σ cdl < la - cllı
|a c/1 bbb
max (bbbllo [Id]l + 1|b dlloo
dlloc-
(7)
2
4
Finally, using the above lemmas, can state one of our main results.
'roof of this lemma, well all subsequent lemmas and theorems, can be found in the Appendix
7

---

Theorem Let V be the optimal value function corresponding to the POMDP (or the belief state MDP), and let V be the optimal value function corresponding to the Superstate MDP. Then, under Assumption for every history И E H. with the corresponding belief state π (H) IB and the superstate ((H) E Hig,, we have
(H)) V 2F(1 - 0)¹
2 p)z
SMDP SPOMDP
(8)
(1 (1- (1->)(11-))))) - + 7(1 P))
Thus, the above result relates the optimal value functions of the POMDP and the Superstate MDP. Note that the difference between the two value functions decreases exponentially with the length of the truncated history I, with the error effectively becoming 0 as - co. Next, we propose an algorithm to learn the optimal policy corresponding to the Superstate MDP.
4.4
An Approximate Policy Optimization Algorithm to Learn the Optimal Policy corresponding to the Superstate MDP
To learn the optimal value function for the Superstate MDP, one might consider standard reinforcement learning techniques such Policy Optimization, which involves alternately learning the Q-function for a fixed policy and updating the policy. However, this learning process is not straightforward because the samples obtained at any time correspond the actual belief state π (H1). rather than the Superstate (H,). These issues due to sampling mismatch make the analysis of the TD-learning part of the algorithm non-trivial.
Additionally, we also consider the linear function approximation setting, where, given feature set & = {é(B, a) Rd B Hii,, E A}, we aim to find the best 0 E: B B( for some R > 0, such that Q(B,a) = oJ (B. a)d Further, since the feature vectors are bounded, we assume, without loss of generality, that || B, a) la S 1. Note that for the function approximation, we constrain the parameters 0 to lie within a ball of finite radius R. This is done to simplify the analysis of the function approximation part of the algorithm. The case without such a projection can analyzed as in Srikant and Ying [019]. Mitra 2024].
Algorithm 1: An Approximate TD Learning Algorithm for Superstate MDP
Input:
A fixed policy (x( B), which is stationary with respect to the Superstates B E Hig,, discount factor 7, projection radius R > O, stepsize sequence {et) total iterations Initialize 0, randomly in (R
Sample so ~ and set Hg = 0
for f = 0, o,
- do
Select action a, according to the policy u(- ((H.))
Receive reward re and observe yt-1
Update the history He+1 He (at, yt++
Select action ac+1 according to the policy u(- ((H++1))
if l' then
0 0,41/2 0, a [r + (00 0,+1 Projs(R) (0(+1/2)
00" (g(H.)) (HG(())))))
end
end Output: (",,)))
We now use standard Temporal Difference (TD) learning algorithm to learn the Q-function of the Superstate MDP corresponding to a fixed policy μ.. The main idea is to perform TD-update at every time t, to the value function of (HH,) using the reward rt and subsequent observation Vt+11 This process is summarized in Algorithm 1, While the TD learning algorithm is standard, we note that the model which the algorithm applied is not standard: we apply the algorithm pretending that the underlying model is an MDP while the true model is a POMDP. We leverage a key insight: if two belief states are close in total variation distance, their reward and transition functions can be proved
7 [3 R) denotes a d-dimensional Fuclidean hall radius R. Here, the superscript I' refers to the transpose of the vector é.
8

---

to be close, allowing us to perform TD-Learning by pretending that the underlying model is Superstate MDP while the true model is actually a POMDP.
Next, we show that under Assumption 1 and with sufficient exploration by the policies, the Superstate MDP admits contraction mapping.
Lemma Let PM E R4 x Bgdl be the probability transition matrix defined by Eq. 5 and
following policy μ.. Then, there exists a constant p' E (0,1) such that for all pairs of distributions di, d2 over the superstates such that (d)-d2)(i) # 0' and for all policies with sufficient exploration p(a B) 2 284 o, B, such that (1 - p)¹ < 8| we have
| - -dd rv I (1 - p') d2llrv.
Finally, we state the approximation bounds for the approximate TD-learning algorithm
Lemma 4 Suppose Assumptions 7 holds and consider that p(a B) 2 8 V a, B, such that
(1 p) < 6 all policies p. Let Q denote the Q-function obtained by running Algorithm 1 for r > 4(1 (01-7)) 7 iterations with a fixed stepsize &, = =1/V7. and 2log(1-pr}- Moreover, let
Ing
Q" be the actual O-function of the Superstate MDP corresponding to the policy p.. which satisfies
Q" a) = (Q" (B, a)) YB E &Hig a E A and let 0 == min IQ" TT 012. Then,
El T+1 - 100 - | 10 + +(11 (1- 2(1 7)
1 (1 2(1 - /T)
110, 0112 +
VT
(1-
+ +2R)²
2VT + C2(F + 2R) log
lORT
VFlog(1 p¹) + (1 pp' 22)2l 0f (RF+ R2 +
2 (1 p) (Ri R² 1 + (1 (1-phii) = ETD-Emer:
+ 2RF(1 p) + p
Algorithm 2: A Policy Optimization Based Algorithm to learn the Superstate MDP
Set Qo () = 0, AB E H A for i = 1,2, M do
Mi(a B) x exp (n ド (B, Initialize On randomly in ((
Sample so ~ D and set Hj = !
for t = 0 t + 1 do
Select action a, according to policy ue(- ((H)))
Observe reward r, and the next observation Mi+1
Update the history Hi+ = Hi ll 3t+1)
Select action a++1 according the policy ui(- ((H)++1)
if > I' then
(a.))) (()((())))
O1+1/2 = 0s+er
0.t1 = Projs (0++1/2)
end
end
(B. क ( (B(,))0+++
end
Next, we combine Algorithm with the POLITEX algorithm from Abbasi- Yadkori et al. 2019 for the policy update rule to learn the optimal policy. Note that the POLITEX algorithm is proposed for the average reward setting, whereas in this work, we extend their analysis to the discounted reward problem. The overall algorithm is outlined in Algorithm 2, where the inner loop performs TD learning, as described in Algorithm 1, while the outer loop performs policy updates using an exponential update rule which incorporates aggregate information from learned Q-functions.
Given how the policy is chosen in Algorithm non-zero d always exists

---

Next, to evaluate the performance of our algorithm, we use the following notion of regret. Similar definitions have also been used in He et al. (202T). Regret is therefore defined as
M 7+1--1
M
Rr-
(V" (TT (T(H)))
(T+1')
Vi
(HHH)
1=
(9)
where V"" and Vi are value functions of the actual POMDP and the Superstate MDP under optimal policy μ² and policy Hú, respectively. Here, the number of policy updates M and the number of inner TD learning iterations in each episode r are chosen such that M + (') = T. The intuition behind the definition that, suppose the algorithm stops the j-th inner iteration of the i-th policy update episode. Then, the error between the expected discounted reward corresponding to the optimal policy and the policy output by the algorithm is V ( (Ho)) - V (g (Ho)). Therefore, RT /'' can also be viewed the expected error incurred by the algorithm if stops uniformly chosen random time.
The following theorem provides an analytical upper bound on the regret of our proposed algorithm To
i=] be the policies learned in Algorithm 2 at the corresponding discrete time intervals t; [i 1)(T + +1") + 1,i(T (')], i .,... M. Moreover. let the regret RT be as defined in Eq. (9). Further let T /T and thus log T L' Toog 107
Theorem Let V be the optimal value function of the POMDP, and }
and M-
(r+T). Then, the regret is bounded as
RT S T (EFA Ema) - O(T3// log T)
(10)
where
M EPA = Σ
1 0. Q4 1l01
i=1
Erm = (1 - p)'[ 1- (1- (1-2(1- ((1-n)/vF))
(ARF+ 4/0 R2 +1 (1 (1-)))))
(1 (1-
2F
2Fy
)
(1- (1-
Since Algorithm 2 is devised optimize the Superstate MDP, small regret implies that the realized trajectory of the algorithm under the actual POMDP is also close to its optimal value.
Note that ÉPA is the error due to linear function approximation which can be reduced by using good set of feature vectors. Similarly, ÊHА is the error due to approximating the history using a truncated history of length / (Superstate). which quantifies the tradeoff between increased complexity in terms of the number of states in the Superstate MDP and the approximation error.
Conclusion
We show that standard policy optimization algorithms can effectively approximate an optimal POMDP policy by modeling as an MDP over finite histories, and provide convergence guarantees without the heavy computational cost or restrictive assumptions of prior methods. Our results also extend to the linear function approximation setting, ensuring scalability to large state spaces. Finally, we extend the POLITEX algorithm to the discounted reward setting and analyzed the regret with respect to the optimal POMDP value function. Overall, our work provides tighter theoretical guarantees, improved efficiency, and more scalable solution for solving PORL problems. Future work could focus on tightening the approximation bounds by leveraging more expressive function approximators, such as LSTMs or Transformer-basee architectures.
Acknowledgments and Disclosure of Funding
The work done in this paper was supported by NSF grants CNS 23-12714 and CCF 22-07547 and AFOSR grants TA9550-24-1-0002 and FA9550-23-1-0107. Additionally, Ameya was also supported by the Henderson Fellowship.
A direct comparison of our bound with Cayci et al. 2024 is also provided in the Appendix.
10

---

References
A. Cassandra, L. Kaelbling, and J. Kurien. Acting uncertainty: Discrete bayesian models for mobile-robot navigation. Technical report, USA, 1996.
Jesse Levinson, Jake Askeland. Jan Becker, Jennifer Dolson, David Held. Soeren Kammel, Zico Kolter, Dirk Langer, Oliver Pink, Vaughan Pratt, Michael Sokolsky, Ganymed Stanek, David Stavens, Alex Teichman, Moritz Werling, and Sebastian Thrun. Towards fully autonomous driving: Systems and algorithms. In Proceedings of IEEE Intelligent Vehicles Symposium (IV "II), pages 163 168, June 2011.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. contextual bandit approach to personalized news article recommendation. In Proceedings the 19th International Conference on World Wide Web, WWW '10, page 661-670, New York, NY, USA, 2010, Association for Computing Machinery. ISBN 9781605587998.
doi: 10. 01114//1772690017775555 URL https
//doi.org/ 1145/17 (icol.ooog/001111177777700112221
Milos Hauskrecht and Hamish Fraser. Planning treatment ischemic heart disease with partially observable markov decision processes. Artificial Intelligence in Medicine, 18(3):221-244, 2000. ISSN 0933-3657, doi: http:///ouuugg/oooooo066s3331170
URL WRRLhttps: //www
sciencedirect http:///ww...aaaa.........oaaaaa
Noam Brown and Tuomas Sandholm. Superhuman ai for wwwtim poker. 365:85 890, 2019.
365:885
Richard D. Smallwood and Edward J. Sondik. The optimal control of partially observable markov processes finite horizon. Operations Research, 2165):1071-108; 1973. doi: 10.1287/opre. 21.5.1071. URL 1t..00/..///tttpp/////aoo//////1
1.71
K.J Åström. Optimal control of markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10(1):174-205, 1965. ISSN 0022-247X. doi: https: http:////....1100002202022200000
https./ww..cieecedlleec.. com/
Christos H. Papadimitriou and John N. Tsitsiklis. The complexity of optimal queuing network control.
Mathematics of Operations Research, 24(2):293-305, 1999. doi: 10. (0.12887/000.2222.299. URL
https:://oi.oog
www.12277/ooo 24.2.........99.
Nikos Vlassis, Michael I.. Littman, and David Barber. On the computational complexity of stochastic controller optimization in pomdps. ACM Trans. Comput. Theory, 4(4), November 2012. ISSN 1942-3454. doi: 10. 11.144/2282559222885666 URL https:://oi..org/////// http://1..11/22382220 2382563
Tommi Jaakkola, Satinder P. Singh, and Michael I. Jordan. Reinforcement learning algorithm for partially observable markov decision problems. In Proceedings of the 7th International Conference on Neural Information Processing Systems, NIPS'94 94, page 345-352, Cambridge, MA, USA, 1994. MIT Press.
John Williams and Satinder Singh. Experimental results on learning stochastic memory-
less policies for partially observable markov decision processes. In M. Kearns, S. Solla, and D. Cohn, editors, Advances Neural Information Processing Systems, volume 11. MIT Press, 1998. URL
neur cwt.:e/ed....eerr..............e pappp fi files//aper/ 119fFF11/LL332222224044444422222
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar. Reinforcement learning of pomdps using spectral methods. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceed- ings of Machine Learning Reseurch, pages 193-256, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL httips:/pproceeednggs ml www.srrsssvlee azi Peizzadeneshell. html

---

John Loch and Satinder P. Singh. Using eligibility traces to find the best memoryless policy in partially observable markov decision processes. In Proceedings of the Fifteenth International Conference on Machine Learning, ICMI. '98, page 323-331, San Francisco, CA,, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 1558605568.
Michael L. Lituman. Memoryless policies: theoretical limitations and practical results. In Proceedings of the Third International Conference on Simulation of Adaptive Behavior: From Animals to Animats 3: From Animals to Animats 3, SAB94, page 238-245, Cambridge, MA, USA, 1994. MIT Press. ISBN 0262531224.
Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming, volume 3 of Anthropolog- ical Field Studies. Athena Scientific, 1996.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
Ali Devran Kara and Serdar Yüksel. Convergence of finite memory q learning for pomdps and optimality of learned policies under filter stability. Mathematics of Operations Research, 48 (4):2066-2093, 2023. doi: 10. 10.1287/moor.2022.3333.
URL //tp::::////iioo/ org/00............ 1287/
moor. 2022.1333
Semih Cayci, Niao He, and Srikant. Finite-time analysis of natural actor-critic for pomdps. SIAM Journal on Mathematics of Data Science, 6(4):869-896 2024. doi: 10.1137/331158768. URL
destps:/ddot .org/rgggg. / 10. 00t.11111722166665
Jayakumar Subramanian and Aditya Mahajan. Approximate information state for partially observed systems. In 2019 JEEE 58th Conference on Decision and Control (CDC), pages 1629-1636, 2019.
doi: 10.1 10.1109//DC40044..0 201.CD000022.2199..00 201.999999......9998.
David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state abstraction. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2915-2923, New York, New York, USA, 20-22 Jun 2016. PMLR. URL https://proceedings ml press v48///4//// 1008/abell55 htm.
Yasin Abbasi- Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellert Weisz. POLITEX: Regret bounds for policy iteration using expert prediction. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3692-3702. URL https: http://poocceeeeeeeeeeeeoc nee ml wwt.mmlr..pr.... wtt.mm.ttp..../eeeem.
PMLR, 09-15 Jun 2019.
https::/procedings
html
Anthony R. Cassandra, Leslie Pack Kaelbling, and Michael L. Littman. Acting optimally in partially
observable stochastic domains. In AAAI Conference Artificial Intelligence, 1994. URL
/ttts::/app..eeeatt iwschoonccccccclaac org/CorpusID :o:1coppuuu:::12775
William S. Lovejoy. Suboptimal policies, with bounds, for parameter adaptive decision processes.
Operations Research, 4163):583-59,, 1993. ISSN 0030364X, 15265463. URL htl.:tt:://// /www
jstor.
Nevin Lianwen Zhang and Wenju Liu. Planning in stochastic domains: Problem characteristics and approximation. 1996. URL http::/aao..eenntiicchh..aa wtt.:cchc..aa.ooooooooouu.u.aaa.
12681087
Vikram Krishnamurthy, Partially Observed Markoy Decision Processes: From Filtering to Controlled Sensing. Cambridge University Press, 2016.
Kevin P. Murphy. A survey of pomdp solution techniques. semanticschole wwtp/oopogggoo/..o.oooo
2007. URL https://api
26:1999951 httpr//ccccoaaa.oooooooooo/aaa22
Jaeyong Sung, Kenneth Salisbury, and Ashutosh Saxena. Learning to represent haptic feedback for
partially-observable tasks. In 2017 IEEE International Conference on Robotics and Automation (ICRA), page 2802-2809 IEEE Press, 2017. doi: 10.1 (.9/CCA..201...7 77989337777997... URL https
moei.orgg/000 / 2017. 2017.7989328 7989326
12

---

Huizhen Yu. A function approximation approach to estimation of policy gradient for pomdp with structured policies. In Proceedings of the Twenty-First Conference on Uncertainty Artifi- cial Intelligence, UAI'05, page 642-649, Arlington, Virginia, USA, 2005. AUAT Press. ISBN 0974903914.
Semih Cayci and Atilla Eryilmaz. Recurrent natural policy gradient for pomdps, 2024. URL https://arxiv otg/abs/////ooooooo/o.o/.p...ora als 2405. 18221
Mohsen Amiri and Sindri Magnússon. On the convergence of td-learning markov reward processes with hidden states. In European Control Conference, ECC 2024, Stockholm, Sweden, June 25-28, 2024, pages 2097-2104. IEEE, 2024. ISBN 978- 978-3-9071--410-77 doi: 19/3394998 2024. 10591 108. URL https: pettpss:/do..oom
doi wtt.:///....111/13366644444 200.44444222222222222 100.11.....111.. 10591108
Andrew McCallum. Overcoming incomplete perception with utile distinction memory. In Inter- national Conference on Machine Learning, 1993.
Nicolas Meuleau, Leonid Peshkin, Kee-Eung Kim, and Leslie Pack Kaclbling. Learning finite-state controllers for partially observable environments. In Proceedings the Fifteenth Conference Uncertainty in Artificial Intelligence, 9AI page 427-436, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606149.
Simon Du Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient RI with rich observations via latent state decoding. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1674. PMLR, 09-15 Jun 2019. URL htttttpp:///rroceeddinng
ml www.spresssssee. v du 1 9b. html
Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. Provable reinforce- ment learning with a short-term memory. ArXiv, abs/2202.039883, 2022. URL. https
7/api. oot.aammesccoooo....oooooossspps
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Embed control partially observed systems: Representation learning with provable sample efficiency, 05 2022.
Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. When is partially observable reinforcement learning not scary?, 2022. UtLhttss: org/ abs 2204. 08967
Chi Jin, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. Sample-efficient rein- forcement learning of undercomplete pomdps. ArXiv, abs/2006. 12484, 2020. URL https 7/api. www.smmantiioo wwweanticccccooooo wttp:/ooooe.D::1109066600
Matthew J. Hausknecht and Peter Stone. Deep recurrent g-laamnng for partially observable mdps. ArXiv, abss1550.006527, 2015. Utthttss::/ http:/pppp.maaiiiiiiaa.aacc.. wweenntiisccooli.o org/CorpusIDD 8696662
Daan Wierstra, Alexander Förster, Jan Peters, and Jürgen Schmidhuber. Solving deep memory pomdps with recurrent policy gradients. In International Conference on Artificial Neural Nenworks, 2007. URL //at:::://ap.... /ttps:/app..eenttttcccccc..e
www.etttttnnnnnoeeeeeeeee .wwplaaa.rrrrrggeeeeeee wttp:ooooooo: 140399355
Maximilian Igl, Luisa M. Zintgraf, Tuan Anh Le, Frank Wood, and Shimon Whiteson. Deep variational reinforcement learning for pomdps. In International Conference on Machine Learning. 2018. JRLttttss://
semant cscholar.......oooo
Ramon van Handel. Hidden markov models. Unpublished lecture notes, 2008
Ali Kara and Serdar Yuksel. Near optimality of finite memory feedback policies in partially observed markov decision processes, 10 2020.
R. Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 2803-2830. PMLR, 25-28 Jun 2019. URL https:: //ppocee/ ngs. ml www.lll.pees///// kant 9a html
13

---

Aritra Mitra. A simple finite-time analysis of td learning with linear function approximation. arXiv preprint arXiv:2403.024706 2024.
Jiafan He, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for dis- counted mdps. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, e Advances in Neural Information Processing Systems, volume 34, pages 22288-22222222 22300. Cur- Associates, Inc., 2021. URL https: /tttps::/proccceiiigi neur ips wt/pc//pppppeee.. files/ www.eeaaaaaaaaaaaaaaaaaaeeeeeeee Paper.
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. 01 2006. ISBN 978-0- 521-84108-5. doi: 10. 101107/C309980515549911
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267-274, 2002.
Bram Bakker. Reinforcement learning with long short-term memory. T. Dietterich, Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001. URL /ttptttps///prreeeednssssaae wtwp://wweeeannsrr..r........o.. wwppper.rppppppppppppppppppppeee htt.://ceeeeestt.ooo...o.oooe/es
fites//eeeess/eee//eeeep Paper. pdd
201
Fabian Paischer, Thomas Adler, Vihang Patil, Angela Bitto- Nettlnn Markus Holzleitner, Sebastian Lehner, Hamid Eghbalzadeh, and Sepp Hochreiter. History compression via language models in reinforcement learning, 05 2022.
Jinqiu Li, Enmin Zhao, Tong Wei, Junliang Xing, and Shiming Xiang. Dual critic reinforcement learning under partial observability. In The Thirty Anmual Conference on Neural Information Processing Systems, 2024. URL / net wtt.:/iwwwwee//ouuummmmmm GdurruYVGGGG
Tianwei Ni, Benjamin Eysenbach, Sergey Levine, and Ruslan Salakhutdinov. Recurrent model- free RI. is strong baseline for many POMDPs, 2022. URL httpps::////pperrere net
Forum? 0000mmm2200000000002100
Douglas Aberdeen, Olivier Buffet, and Owen Thomas. Policy-gradients for psrs and pomdps. In Marina Meila and Xiaotong Shen, editors, Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 3-10, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR. URL htttps:/pproceet
m mlr. wtr.press/vl. v abe dee.n html
14

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims made in the abstract and introduction reflect the paper's contributions
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
15

---

Justification:
Limitations are mentioned in the conclusion section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof'
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are provided in the main paper and the necessary proofs are provided the appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not contain any experiments
Guidelines:
16

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper does not include any experiments
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
public public//uides//CCe CodeeSummmo ss wswinnosiiigoooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NewrIPS code and data submission guidelines (https
/ Cnips.cc/pull
wttic//ggiiisseeeee.eeeeee..eese iess CodeS bubmi ss i ionPol icy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
17

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This paper does not include any experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include any experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include any experiments
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
18

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics and our paper confirms with the code.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: There are no negative societal impacts of this work the best of our knowledge
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks
Guidelines:
19

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of the package should be provided. For popular datasets, pppeerswiti www.swiiiioeeeee. com/ Gatasets s has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
20

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs are only used for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non standaadd components.
Please refer to our LLM policy (https: http:///eeerppp.ee////efeeeeeeee wttpa/cc//naneeeeee////00 2005/ LLM) for what should should not be described.
21

---

A Appendix A: Omitted Proofs
A.1 Proof of Lemma T
Let H and H' be two histories with the same superstate. 9(H)) = G(H) = {a1, 11, ........ 1) an wt Moreover, let & and t2 be lengths of H and H', respectively, Then,
we have
π (H) Kaym .... @ Karm @T((H
π (H') = Kar .... @ Ke @ T (H)
Using Assumption |
inductively, can write
(H) - (H = || .... @ Kai.u @ -1) Kay 8... @ Ka & @TH
$ (1 - ()H| T
-
< (1 p)¹
A.2 Proof of Lemma 2
Without loss of generality, let us assume Ejath
a:d4 - E, Gd, 2 0. We have
Σ a;b: Eends
cddi
Σ (a:
cb; + +d)
+ (b. d:)(a; + +c)
2
2
(a: (b; + dd)
+ b, d: (a: +G)
$
2
2
(a: - ci) mmxx(bs d.)
| bb di
) + b, - de (
(i + c;
2
2
20;
Σ
(a: c;)
by + di
2 ) + 1 be di (c=
(c: (cs- - az) (c==a=)) )]
2
b0.20
b, di + b; - di
ai 1 C; (m
(a; ci)
max((bs di)
2
k: 20.
bb - d: 1 (as (ci -aa)
Σ
+
2
be:
(a. c;) max(b;, d,) + cs b -ddd d[]+
d:l
+ Σ
| b di (a:
(c - ai)
20;20;
sa,
Σ
(a. - c;) max b/,, [1 [kd1l cillb - d||oo]
+
Σ
1|b - d|100
css (0:(c;
(c. a.)
2
20;
ke;
Σ
(a= (2) max [ [|]1,)) - Σ |bb - dl
C3 - 0g
+ -|b - d 20
=
2
$00, 24
|a
ellı
|aa |ccll1
max(1|b|l [o) - ||b dll
+ 11b d 20,
4
where the last equality follows from relations
Σ E,,
(a; - -c;) + + Enneyaa (a a;) = ||a clli
and Ena,zo (a: - ci) Eneeza, (cs a.)
E, ai
Σ. G 0. which together implies that
Ena,zo (at -ci) = Eme,pa, (G a.) la-elı
22

---

A.3 Proof of Theorem 2
Consider an arbitrary history H H with the corresponding superstate ((H) B. For any E A,
F(B,a)= Σnat (s H))(s,
Σ T( B)r(s,a) Σ T(s Mr(s,
Σ T(s) B) x H))lr(s,a)
2 - p)TT,
(11)
where the last inequality follows from Lemmal 1
Let = |V (T(()) - (l and note that ó finite since the value functions are finite.
8= - -
Ilx ||V (=(()) VBB)]
(12)
Next, we bound V ( ((((H)) for all H. Using Bellman's 's Optimality equation for the belief state MDP (POMDP) and superstate MDP, we have
IV* (T()) V(((H))
max Σ 7(s H))(s,)) +7
max (((B,)) + + Σ (1
Suppose à is the best action for the POMDP at belief state πe (H). Then can write V VV* (T(H)) (((HH) as
(*(T(H) ((G(H))
Σ a(s H))(s,))+++++))))))) + Σ V (T
max (((.a)+ + (i
(13)
Now, since the maximum value of the second term will be greater than evaluating the second term for à we have
- -(
s [I((s) T<$ - F(B,A))
-
+ 7 Σ
Σ
2( - p) + Σ r ( (T) Σ v(g(B ((.,)))
where in the second inequality we have used 11
Next, we note that E, ( ú) Σ, a)) 1, ((.) is probability distribution over the observation set y. Moreover, by the definition of 5 and since max (II ||*'l>>) S 1--y we can use Lemma 2 to upper-bound the second term in the above expression and obtain
- 2 P)F
8 | (H), (B),
+
(
F
8
= 2(1 - ((1-p)'i+e +7 (>
+
8
(14)
1-
2
23

---

Note that the above inequality holds for all H.
Furthermore, we bound the total variation norm in the above relation ( - (
Σ
jo vT)) - o(..
y
Dly s')p(s s, (T(8))(() H) -(s B))
y
8,6"
<ss H) <(s) B) Σ { s')P(s' s,
2| π II) ग (B)llv S 2 - p)¹
where the first inequality holds by the triangle inequality, and the second inequality is obtained using Now, we consider two cases. Case 1: 1- 2
Lemma 1
Therefore, have
(B)( ; ( F
8
2 2(1 p)'F
+
sup H
+ 5
(15)
11-7
2
Case 2: F <0
1-7
Therefore, we have
v - 2)
inf (T)(H), ((*(B), ; T) 1-
F
+ 0
(16)
H
2)
Now, both inf - a) sud (H(T)(H), ((T((B,,,@)) less than 2(1 - p))- Therefore, we can write
F
8
8 2 p)'F + +
2(1 p)¹
1 1-7
2
< 2(1 - p)'F
7
2(1 -
pp) p)
F
-
1 -
1- 2
01+ 7(1 111--0 DV))
2(1 - 0)'F
27(1 p)'F
1 1
1 1-7
(1 (1-
2(1 - p)/F
2- - p)r
8
+
(1 - 71 + X1-Øp]
71 7(1 p)-
1-7
$ 2(1 - --
275(1 - p)¹
+ -1- (1- - 7(1 - p)
(17)
(1 - 7)
A.4 Corollary
[
Additionally, if N is the number of states of the Superstate MDP. Then, we can state the following result:
Corollary IfN N the number of states in the Superstate MDP, then the difference of the optimal value functions in Theorem 2 caa be hoper-bounded as
< 2F(1 p) N
4F - - (1 21-1) - 7) NN -
|| - ((G()))
1-7
where K log(1/(1-p)) ToR([) TAI)
Proof:
For a fixed I, the number of superstates can be all possible histories of length at most 1. Thus,
N = 1 + |IIAA| + |2 + + DI'AA < |A
24

---

which implies
log |0
Therefore, (1 (1-p) p) (1 p) ( Similarly, since lext3
1 log N [) we have (1 p)d > N met Substituting these relations into Eq. gives us desired result.
A.5 Proof of Lemma 3
Let d1, d2 be distributions over the superstates and similarly be the canonical basis vectors in
Il Then there exists ai such that atj 2 0 and Σi, and l|d1 d2 llr and the following
holds
p - pd p''d2lrrv 11p d2)
= =1 ai pM (e: - e;illTV
ai (nlllipies &jillTV Σ 3
(18)
Note that the maximum value of the above term is Ens which is ||d, d2llTv. Therefore, if for some i,j we have oij and [| e,)lTTV < 1, we are guaranteed contraction.
Now suppose that e, corresponds a superstate B; and ej corresponds a superstate Bj
pP (es eEilTTV
Σ p(al B.) E
( (v. B1 + s''P(ss' 18,0)=(( B.)
V.8.6'
- Σ p(a B,) Σ [
tu, a}) = - s')P(s' (,)))(() Bj)llr
(19)
U.8.a!
Next, will show that if B, and Bj are two superstates which differ in the first two elements then [B - Byy < 1.
Therefore, focus pairs of B,, By such that (BB, (v.a)) which only differ in the first two elements. For such a pair, we can simplify further
(B, II {y, a}), i.e., Bi Bg
Σ m(a B₂)
Σ (B (v. B'- + s')P(s 8, s,))T(s) B₁)
M/8,8'
Eula| B₁)
Σ [[[[B,
(I a}) Ba] Φ s')((s' (s,a)((8 B;)l
B.8.0'
[|[u(a) B,) Σ
( s')((ss (,,))((s) B,) u(a Bj) Σ ( s')P(ss' (s,a)((s) By)yylllr
8,8!
1/2 Σ
ula| B,)
(')(s')P(5'' (,a))((s B,) u(a Bj) Σ Φ(y s')(('' s,)))(s B,)
$ 1/2 Σ
|u[a B,) Σ
4(y s')P(s' (, B,) Σ
ply s')PPss' s,a) B,]
V.a
9,8'
8.8"
(u(a Bi) - ul(a B2))
Σ Φ (')ls')((s (s,a)((s Ba]
< ||T(|] B²) - -T(s B,)l [a((a B,) p(a Bi)
< (1 /)¹ + |A/o
(20)
For the last inequality we assume that our policy has small exploration component such that p(a B) 2 8 v B. Therefore, for sufficiently large horizon length I exploration 6, assumption is automatically satisfied.
25

---

Therefore if as > 0 for pairs of B,, B, such that
( || (v, we are
guaranteed a contraction
Next, we will show that we can construct an algorithm such that 0z > 0 for all such pairs B;, Bj-
To construct 0i, the following greedy algorithm can be used. Let 01, U2 I2" be two probability distributions. Define the difference vector d = 01 - D2 and define:
Algorithm 3: A Greedy Algorithm to construct
Input:
Two discrete distributions
(v) (1), (1) and 02
(n))
(1), 0y o2(2)..... (2)))
Compute the difference vector A D1 U2 where A; (i) -12
Define the surplus set 5 = {i A; > 0} and the deficit set D = (i A < 0}
Initialize (ij 0 for all j
for each E S do
end
each
j E D atj < min, -4,
A
A ag
Ozj
See that first aij min( A, -A)). Therefore, since A, A, + 0, asy > 0. Additionally, the steps A; A, aij. A + A5 + asj ensures that either one of them goes and removed from the surplus/deficit set.
Additionally, it is straightforward
that E; |d]] Thus, Ao, Aj # Oujy 0
A.6 Proof of Lemma 4
We first introduce some notations that will be used to prove the result. Let us define
ge (0) == [r: + n (g(H++)), (+11) ) o² (g(H,,, a:) (( H.), at), and note that it can be written in a compact form as (0) = &R. + + ΦD, where IT
Dj diag [L[(BB, ax) (B, aB) BERSuaEA)
R₂ = [r. (Br, 0+) (B,a)] T
BEliginEAA
F, (BB, .), (B), = T[(Bt, = (B,a)) B((111444)1) (B',a'))
+ = [ a)) B))
Additionally, let g(0) = Φ + T Dr TT + TioTTO 0, where DP and Nu denote the stationary distribution and the state transition matrix for the Superstate MDP when following policy μt, respectively. In particular, wN (B', a' B,a) puaa B)P(B' B,a), where P(B' B, a) is given by (5). Similarly 7 : =r(BBa ( aE is the vector of rewards corresponding to the Superstate MDP as defined in (4). Finally, we also define
T) (0) (0 00-00 (g)) g(0)-
Next, we state and prove an auxiliary lemma that would be required for our main analysis.
Lemma The following inequalities are true.
(a) m (6.) < C1, where C1 = 2R 2(F + 2R).
(b) [9 (1) g. (62)l < C21l01 - 021 40, 02. where C2 (2F + 12R).
" [olvev denotes matrix obtained by concatenating vectors V. where each is column vector of the matrix.
Unless stated, the norms L2 norms..
26

---

Proof:
To show part (a), using the Cauchy-Schwarde inequality, we have
(0:) s II(0: () g(o.))ll s 2R 2
To prove part (b), for simplicity let B - ((H:), 0, a, and B' = ((H1))) a44 = a'. Then, l1 (01) - gr (02) || = 11(70 _ [B",
-B
- -
I ||0] 0 B, a) (B',d') - Φ² (B, a)ll s 2 - 82ll
Similarly, we can show that (lī(O)) g(t2)ll - 2||6 - -22l. Thus,
(n(())) 77 (02) = (0)( g(0:)) " (0: - 82 + 02 0) - ((e:(02) -((02)) T (02 0)]
< (01) - 5(0) |1100 - 02ll + 1|0- - (0(() - g(02)]l + (l0(0)) ((02)ll)
x (2F + 12R) [01 -22l-
We are now ready prove Lemma 4 Let consider the Lyapunov function
[())
0 01|
In order to show that 0, converges to Ó, we will show that [():) converges to 0, and obtain finite time bounds for the convergence. To that end, we first relate the successive iterates [(0,) and C(0c+1);
[(0++))
|0 e||
= [|Proj(ee11/2) - Proj(O)11
I ||0+1/22 - 0112
= |10 + (0.) -012
110, 011 + (0)))( + 2e (0:) 0)
S (F 2R)² [(0.) + +2,g (0.) 6).
(21)
where the last step follows from (0))l S F + 2R. By adding and subtracting @(0:) in Eq. (21) we get
2(0++1) S C(0.) +
2 ( (R)) + (0, 6) g(.)) + 20. - 0) (0.) - g(.)).
Next, we proceed to bound each of the terms in the above expression. We start by bounding 2e, (0, 0) (0:) in terms of [(O.). We can write
(0; - 0)² (0.)
20, - 0) ( >D" D D))
= =2c( (0: 81) DT 01) (T= 8)) + ( (0, 0)) T 6 TTo.)
< 2ecl 15 (0: - 1l (T 0.) Tu 0) Dr 2c, || 10 0) 1)
2 1) (0. - 00.-
where the first inequality uses the Cauchy-Schward inequaatyyy and the second inequality follows from the contraction property.
Next, will proceed to bound (0, 0) -(O.))). To that end, we will first relate (e())) with no (0.-). Note that since
|10++1
0,
|Proj(O; (0.)) Proj(O:)]l
< [|e))((0))] = (F + 22))..
we have 110, - -0--rlll S (F ( Σ - cs. Therefore, using Lemma (part b), we obtain
(0.) S ((((rr) C2
Σ G
27

---

Let Fe-r foo, Gu. To. U1....., Bt. dg. rt. Mt+1, 0(+1] ) be the filtration up to time t 1', such that conditioned on Fi-r. v., dr-r measurable and deterministic. We can now obtain an upper bound on ((-)(Or-r) as follows:
(0,:(0,-1)) = E [E (0--r) [r.-r1]
EE EE (Φ (0.-1' 0))
T (Ru - DDF) F(-w]]
+ E [ [ (0t-1- 0)) (0))((()))) (yF 02-1 -D pu Tf r) Fr-r]]
+ (0--v' - 0)) "i)"((() (D''"00 - -D F(-11]
TP [( - 0))((R( "RR, - -Dr)) + +00 (0,- - -0)) T (Drr- | [[]1]]]
T
+ E [E((" 8)) T (yE,0T 01rr' - -DD" "D pu 0()) F[-re]l
+ =B[ 0)) (D"440 0,- D2 v) F(-r]]
s 2RF(1 - p)² + B [ (00-1 - 61) T (D,F - D [[-v]]
+
0)) (y 00040000000
4" 0--r Fi-e]]
(0,-r- 0)) T (D= 2004"00000 0,- - D 0,-r) r) F Fr-r]]
+
(22)
where the inequality in (22 holds because using similar argument as in and 0g = a, we have r. D2i = E. r(s, a)=(s H,) (< B) v 27(1
II for all g(H,) = B
Next, let Pf denote the true probability transition matrix of the POMDP, i...
Pll (B' a' a, ((H)) = B) = p(a') B)
Σ
[ fu. a}) = B'I ( s')P(s' (,)))(( H.).
310,8'
We can bound the first term E [ (0--1 0)) (D,F DUF) Frre]] in 22 follows:
E [[E[((" (0 - 0)) 7 (Dir- DPT) | Fr-
[ - 0)) (B.D, pm D F(rl))
B[(Ø" ")["(((((" pm D. .P) Fe + B PM D. 1op0--ppp
pM ('F) Fr-r
BI( (0,-r 0)) (B(E((())F - PM D: 1 F(-1l Fe-e| + E[(" 1 PM D(F) Fi-rl)]
D.- P D 1 [i-r] + (| D.- PM
PM DMF) F[vellb]
< 21 -n) + E PM D.-15 PM D(7) Fr ||]]
2RF(1 pp) + R(1 | - Frrrll I|,
(23)
where the first inequality is derived using the Holder's inequality, and the second inequality holds because
[B[ Di-1 - PM - P=-))_ Fe-v]ll2
< <E[I[(P D pm DD [[-e]
ΣΣΣ Σ Σ
(B', [B,a] pm(B',d a' B,a)) (I((B.-,, = (B.,))
B
B
< 2F PH iS l|TV
Iu(al B)
Σ (I(((BI [v.a) = B'O(v/ 8)) (P(s') 8, s,))(((s)) B) - B)- H.)))
3.9.5'
Σ
Σ (T(g(B
|l [v.a] = Byb((y 1=)) (P(s' (T(( B) - =(s H.)))
B' V.a.a'
< 2F - (p),
where the last inequality holds using Lemma Therefore, solving Eq. 23 recursively, we get
p)
E [[E[( (0 01) (D)((D.F DMF F(rr)]] < FR 2(1 p) + 2 p (1 )'y") vt.
28

---

Similarly, since | & R, we can bound the sum of the last two terms in (22) as
E B [ (0.-r 01) (7 P:- - 7D pu 0--v) Fi-r
+ E [ (0--1' - ( -
(DaΦ""
- D. 0--r) Fr-r]]
)²)) $ ( (1) p¹)" +2 -2(--p")
p'
Therefore, putting everything together, for a constant stepsize e, we have
B[C(0++1)] & (1 - + 2c)) + 2 2R)² + 2eRr(1 - p)
+2e + R2 (1 - (11))))>)) 0¹)² +2 (1 P) =1-00")
+222(F 2
p
Using the above relation recursively, we have
B - 0112 - (1 2c 2ey)" 0l12 - (1 2E + 204)"
[ 22)² + 4cRF(1 - p)
2e(1 - 7)
p\') -2(-0-1)
2 + 12 + (1 p')r)) (1- +2
/
Therefore,
BlI - 1o I |6 1 + (1 2c + 200)"(10r- 10r11 A112
1 - (1 25 + 267)"1
[22(+ +2R)² + 4C22(F + 2 p)
+
26(1 7)
2c R2 + (1 ('r)) 0¹/² p
Finally, by choosing +/ and 1' [log(1-p) for sufficiently large such that 2e(1 -7) < 1, we
loy
get
2(1 2(1--2)7100 0112
E110"41 Q"11 11000 5 |100 - 17 + (1
VT
(1 (1(1 7)/ VF)
(
+ C2 log
log(1 - p/V + +RRF(1 - p)
71
2/T
2 (1 p) ( RF R2 (1 + (1 (1-ph)) + (1 - p²) xlag(1 3 RF + R + (1 phji] p'
lng
-ETD.Emor
A.7 Proof of Theorem
Before we prove the regret bound for our policy iteration algorithm, we first mention an important result from the online learning literature, which will be used to derive the result.
Consider game between two players consisting of M rounds. At the beginning of each round i, the environment chooses loss function 4 A [0, 1]. while the learner selects an action a; A. After both choices are made, the learner observes the loss ((;)), while the environment observes az The learner's goal is to minimize its regret with respect to fixed action a", which defined as
M
RM = Σ (((aa) - 4(a"))
The following lemma provides high probability bound on Ras-
Lemma 6 Cesa-Bianchi and Lugosi (2006) For the game mentioned above, assume that round i the learner chooses an action a; with probubility pı(a) exp(-1EZZ1y (())), where
7 / log A//M. Moreover, let 8 E 10, and a" A be arbitrary fixed action. Then regardless of how the environment plays, with probability at least 1 ô, we have
RM S /M log A1/2 + /olog (1/6)/2.
29

---

We will now use this result to prove the regret in Theorem
Using the definition of regret, we have
M
RT = (T+
E Σ
(T(H))) - V VI- (G(H)))
2m
B V (T(HH)) - ((G(H))) (T +1) Σ (T + 1) >
E -
- M( + (')
SPONDP + (T+
Σ - Vn
(24)
where the inequality is obtained using Theorem Lemma Kakade and Langford [2002]. for any
Therefore, using the Performance Difference M, we have
E E(V(G(Ho)) - Vm (H(H)))]
E Bar
[Q (g(Ho) (Q
Ba-
(G
+ E Es Barwiaa
[ (G(H)))
+ E Ea Ea-p p.. -i @ (g(H)) Q" (g( a')) d')]
Next, using Lemma
we know that B[1l Quo11ool S EII-earrr Vi. Therefore, write
M
(T 1')
E
V(G(H)))- - (g(H)))
M
= (T + 1')
Σ
E
E Ba-j.a' ~ - ((",,(())) + 2(T (1)++1))M M'MM
i=1
(T + 1E
Σ
(mi(- ("H)) (Ā(- ((Ho)), Qt1 (9(H))))))))
2M (T (')ET-Cror
(25)
where the last equality follows from the linearity of expectation and expanding the inner expectation. Now, we can apply Lemma upper-bound (25). To this end, we can think of game between the adversary and player, which occurs over M rounds. In each round i, the adversary chooses the loss function 4(-) == 2* (G(H), :). 13 and the player selects an action a; E A with probability (a(a.(9(Ho)) which due to the structure of the policy updates in Algorithm 2 follows the same exponential update rule as in Lemma 6 Moreover, since any MDP (and in particular the Superstate MDP) admits deterministic stationary policy Bertsekas and Tsitsiklis (199)), follows that f is deterministic policy that always selects an optimal fixed action a", L.C.,
Ma ((Ho)) = and ((lg((H)) = 0 Va aa"
By applying Lemma 6 we conclude that the expectation of the inner product 25 upper-bounded by
M log A
M (1/)
R
M6
2
2
Substituting this bound into 25) and combining it with 24 we obtain
12ehe Q-function is hoper-bounded by R. since ||0|]2 < R and [b((B,)) < 1. This only scales the regret bound Lemma by factor of R.
30

---

M log [AA]
M log (1/))
Rτ S (T+I')
MÒ +
+ [ + (') (2f1D-emro
SMDP SPOMDP
2
2
log [A
log M
= (T l')
VM +
+
+ (2ETD-error +
<SMDP SPOMDP
2
4
where in the second step, have chosen å 1/VM M and used the fact that M + = T. Finally, by choosing r + 1' vT and substituting the values for ETD-error and SPOMDP> we obtain the desired result.
A.8 Improving Bounds in Subramanian and Mahajan [2019 using Lemma 2
We state an important lemma from Subramanian and Mahajan 2019 For additional details, the reader is referred to Subramanian and Mahajan [2019]. Before stating the lemma, first present the definition of the approximate information state, as defined in /Subramanian and Mahajan (2199] Note that we have simplified the definition for the case of POMDPs.
Definition Define E Z to be an approximate information state and a : + Z to be the approximate information state generator. Further, define i Z A - R. to be the reward approxi- mation function. Additionally, let (f, 6) be fixed constants. Then Z = (H,) satisfie the following properties:
For any history He and action at, we have
E R
h4, Ar -fo(H)) H.
For any history H, and action o, and any Borel subset B E Z, define (b(B) P(Z41 B H. = h4, A az) and 0z (BB = PBB (HH), a.). Then
drv v1) 56.
Note that the grouping operator G in our work corresponds to the approximate information state generator in their paper.
Lemma Consider the approximate information state generator a to be a function which takes history H H. to upproximate information state Z, where for simplicity of our analysis, assume & is discrete set. Define a fixixed point equation for the approximate information states as follows:
(=z max (f(2,a) + (
Let Q" denote the solution of the fixed point equation and Q" denote the optimal Q-function for the POMDP. Then, for all histories H. HI, using results from Lemma 49 and Theorem 27 in Subramanian and Mahajan 22019, we have
2y0r 2
- (V))))
1--
In the following, we show how to modify the proof in Subramanian and Mahajan 2019 to obtain
better bound using Lemma
31

---

Proof:
=|max [R[Re + ?V*(H++1) H, = h4, A, = ue]] max [f(o(h)); ax) + Σ ((=))(22) |2,)]]
< [E[Re H₂ = hr A = f +1 (H+++)) He = A
= =b Σ (((2))((112))))
sctrl Σ
(he (y, H₂ = ,, A = =d) ) Σ v()))(2' 10(h),,)))
PP H₁ = h1, Ar a')
=e+7| Σ
Σ
V'
P(s He,a')
Eyer(he (v.a)==2/) Pyy He h4; At a¹)
yhe (u.a))=z))
V(E)((2 ohho)a
(26)
Suppose, for all HG, (V.(H.) - (o S w. This implies that
P(y H. he, Ar a')
Σ (" (u, (ho ll =v,a))==)) P(u H. = h4, A, a²)
E
v(=') ww
(ha (b.a)==))
wor(h, (v,a))=21)
(27)
At this point, we can use Lemma Therefore, obtain
< (1 (1) + + (7o011 (1- ))
2
70F
5 + 6/4 + (1-7)(1 7
(28)
A.9 Comparison of our bounds Theorem 2 with Caycl et al. (0024
We can do direct comparison with Theorem 4.4 of Cayci et al. [024] and show how obtained our improved bound. Specifically, our Theorem 3 aggregates the bound from our Theorem 2 the TD-learning error from Lemma and the final eтror due to policy optimization. Each component can be compared as follows:
1. Error due the mismatch between optimal value functions of the POMDP and SuperState MDP - corresponds to Theorem 2 and is comparable to einf in Cayci et al. 2024
2. Standard TD-learning first term of Coritic in Cayci et al. (2024]
the terms in Lemma 4 without (1 p)². comparable to the
3. Additional TD-learning error from sampling mismatch, i.e., the terms in Lemma with
(1 p) (comparable to Epa of Caycii et al. (2024).
4. Function approximation error - similar to loFA in Cayci et al. 2024
5. Policy optimization error comparable to cactor in Cayci et al. 2004
We improve upon the bounds in (1) and (3) which leads the difference mentioned at the beginning of this response. We believe our analysis offers a detailed decomposition and sharp insight into the sources of error.
B Analysis of the Practical Validity of Assumption 1
B.1 Analyzing Assumption for Practical Example
We consider a practical example of modelling Customer Behavior Modeling in Retail.
Here:
32

---

States represent engagement levels such as (Uninterested, Browsing, Considering, Purchasing). Observations features like the number and type of clicks (e.g., "Viewed Product", "Added to Cart").
In such systems, observations from adjacent engagement states tend to overlap significantl:: for instance, both "Browsing" and "Considering" may involve product views and occasional cart additions. Furthermore, customer behavior is highly dynamic- users frequently move between these states in short time spans (e.g., from "Considering" back to "Browsing" " or forward to "Purchasing"), ). This overlap in observation distributions and frequent transitions among states leads to high mixing, thereby increasing the Dobrushin coefficient and ensuring filter stability.
Next we present simplified example to model customer behaviour:
States: so (Uninterested), $1 (Browsing), 82 (Considering), 83 (Purchasing).
Actions: ag: Show generic homepage, aj Recommend trending products
Observations: yo: No clicks, y1 Viewed product, y2: Added to cart, ys: Purchased Transition Probabilities for ag:
81
81+1
Sg
81
82
$3
0.4
0.4
0.1
0.1
$1
0.3
0.3
0.2
0.2
0.2
0.3
0.3
0.2
$3
0.1
0.2
0.4
0.3
Transition Probabilities for a1:
8t
81+1
Su
81
$2
$3
0.4
0.3
0.2
0.1
$1
0.2
0.4
0.2
0.2
0.1
0.3
0.4
0.2
53
0.1
0.2
0.3
0.4
Observation Kernel:
8t
Vt
Y0
V1
1/2
1/3
80
0.8
0.2
0.0
0.0
51
0.3
0.5
0.2
0.0
0.1
0.3
0.4
0.2
83
0.0
0.1
0.3
0.6
Therefore, referring to Theorem Kara and Yuksel [2020]. we calculate the Dobrushian coeffients
be 5(P) 0.5 and ((D) 0.1, which satisfies the sufficient condition:
(1- ((P) 8()) 1,
implying that the Filter Stability condition is satisfied for this case.
We believe that Assumption [ covers many practical examples and future work can consider multi-step variant where the system exhibits contraction after every k steps. We believe that our results can be extended such setting.
B.2 A Counter Example
To motivate future work, we also provide a counter example (suggested by one of the reviewers) where Assumption [ does not hold.
Consider T-Maze as described Bakker 2001] Here we present an infinite-horizon variant. The domain consists of T-shaped maze, as shown in Fig The agent is initially located at the beginning of corridor (position S), which followed by a junction (position X) where the agent can step into two different directions, and can keep going into that direction. The goal of the agent is step into
33

---

S
Figure I: T-Maze
the correct direction, where the correct direction is determined by piece of information the agent given at the very beginning, when he is located at the beginning of the corridor (position S). The agent is given non-zero reward in every cell after taking the correct direction.
The T-maze naturally modelled as a POMDP. The hidden states consist of
An initial state 8g
States sf for every position in the corridor, including the junction, standing for the fact that the agent is in position and the initial observation specified that the correct direction is d {1, 2} (consider that d stands for "left" and d stands for right).
States r for E N and d E {1, standing for the fact that the agent is in the 7th cell after stepping into the first of the two possible directions, and given that the initial observation said that the correct direction
take is direction d
States of for E N and d E {1,2), standing for the fact that the agent is in the jth cell after stepping into the second of the two possible directions, and given that the initial observation said that the correct direction take is direction d.
Note that transitions in the hidden state space are deterministic. Given the entire history observations and actions, the agent can determine the current hidden state, hence belief' states are sharp, always assigning probability I to a hidden state and 0 to the others. If only suffix of the history is available, the agent can only determine its current location, and it cannot distinguish between states s! and s² between states r and rf and between states of and qf In other words, belief states will assign probability 1/2 to each of the two possible states.
The optimal value function, given an entire history H is roughly V = R(1(1 7))
However, the value of any superstate ((H) roughly V 72/ since the value is determined by the belief, which is uniform over non -on-distinguishabl stats once we remove the first observation. The difference between the two values V2/2, which constant wrt to I opposed to the bound which we obtain in Theorem 2 which goes to O for I + co. The reason why Theorem does not hold in this case is due the contraction property required for Assumption [ being con-applicable due to the unique structure of the POMDP.
C Experimental Results
C.1 Effect of History Length and Observation Noise
Previous works in the literature have focused heavily on solving POMDPs by considering past observations to design optimal policy. However, for the sake of completeness, we evaluate the performance of our algorithm on a partially observable variant of the FrozenLaak--vl environment. The environment is modified to introduce observation noise, where with probability p, the agent receives random observation different from the true state, All the implementation code is available Based- RL-For-POMDE
at this code
http:://iiitbb.comm/myaaaaaaaalt
34

---

The agent uses history-basee based state representation by maintaining the last & observation-actin action pairs. We study the impact of both the observation noise probability p and the history length the agent's performance.
Setup.
Environment: FrozenLake-vl with is_ is_ssippery-Faleee
Observation Noise: With probability the observed state is replaced with random incorrect state.
History:
The agent encodes the last (observation, action) pairs the state.
Algorithm: POLITEX with (D(O))bbsed Q-value estimation and exponentiated gradient policy updates.
Compute: All the experiments were performed on the Google Colab CPU.
The following plot captures the average reward per episode for varying history lengths k and observation noise levels p. The moving average was computed over a sliding window of episodes.
Results.
History Length
Average
100
0.00
1.00
3.25
1.30
2.50
H5000r Longth
Figure 2: Average reward per episode for varying history lengths k and observation noise levels
Observations.
Increasing the history length k consistently improves performance under partial observabil- ity.
Higher observation noise degrades performance, but the use of longer histories mitigates the effect.
Even with moderate to high noise levels (p = 0.3), using A allows the agent to recover much of the performance.
C.2
Comparison with Cayci et al. 20044
In our paper, we show that we improve upon the bound in Cayci et al. 20024] using a computationally lighter algorithm. To experimentally illustrate this result, we consider an example for simple partially observable Markov decision process (POMDP) with two states, two actions, and two observations. The environment is stochastic, with state transitions and observations defined by fixed probabilities. and rewards designed to encourage taking the correct action in the hidden state.
To handle partial observability, represent the agent's 's state by finite history of recent action- observation pairs, with history lengths of and tested.
For each setting, the agent trains over 200 episodes, each of fixed length 20 steps. The learning rate set to 0.1 and the discount factor 7 to 0.9. Policies are represented tabularly and updated greedily with respect to Q-values after each episode.
35

---

We measure the agent's 's performance by total reward accumulated per episode and analyze learning curves as well as final average rewards (averaged over the last 20 episodes) to assess convergence and policy quality.
Comparison Our Method vs. Cayci et al.
H-1 Caycl of
Our
Cayci
10
150
175
Episode
Figure 3: Comparing Moving Average Reward
Additionally, several prior works have empirically demonstrated the effectiveness of using finite histories of observations as surrogates for hidden states in partially observable reinforcement learning problems. For example, Paischer al. 2022 leverages pretrained language transformers compress observation histories into compact representations, showing improved sample efficiency on POMDP benchmarks. This is similar our work if we consider the feature vectors generated by the language transformers as the feature vectors. Similarly, Li et al. (2024) presents a framework that adaptively uses privileged state information during training while deploying policies that rely on observation histories. Other related studies, such as Ni et al.] [2022] and Aberdeen et al. [2007], support the use of history- history-based or memory- augmented policies with policy gradient methods,
example,Paischerr
36


Reviews:
[{"review_id": "MfLXRrBHiO", "reviewer": "Reviewer_KcfL", "summary": "The paper presents an improved RL algorithm for POMDPs based on the idea of operating over so-called *superstates*, which are history suffixes.  In fact, optimal behaviour is possible by acting according to *belief states*, which are a function of the current history of past observations and actions, since a belief corresponds to the probability distribution over the hidden states given the current history.  However, using beliefs directly is not generally tractable, and many different alternatives have been proposed in the literature, relying on either assumptions or heuristics.\nSuperstates are an approach where histories are approximated by their suffixes of a given length $l$.\nThe paper proves approximation guarantees for superstates, in terms of how accurately the value functions of the original POMDPs are captured by the MDP induced by superstates. The approximation guarantees provide the foundation to develop tractable RL techniques.  Specifically, the authors show convergence guarantees for policy optimisation, as well as performance bounds in the case of linear function approximation.", "questions": "**Q1.** What is the intuitive meaning of Assumption 1?\n\n**Q2.** How restrictive is Assumption 1? Could you please provide arguments on its generality, and provide examples where the assumption holds?\n\n**Q3.** Could you please discuss some of the assumptions of the algorithms you improve on, discussing how such assumptions related to your Assumption 1?\n\n**Q4.** Could you please provide an intuitive argument on why Lemma 1 holds? In other words, the high-level argument of the proof.", "limitations": "The main limitation is the lack of a discussion on how general or restrictive the main assumption (Assumption 1) is.\n\nThe example I provide above shows the limitations on the applicability of the proposed techniques.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\nThe research topic is **interesting and impactful**. RL algorithms are a challenging and active area of research. Improvements in these field are likely to have a significant impact on the research area. They may also have an impact in practice depending on applicability of the results. However, as it is the case for this paper, it is unclear how restrictive the required assumptions are in practice.\n\nThe paper looks **solid from a technical point of view**, except for some minor issues in the formal statements (e.g., some undefined notions, some glitches in notation).\n\nThe **presentation is clear**. The paper is easy to follow.\n\n\n## Weakenesses\n\n\n### The main assumption (Assumption 1)\n\nThe meaning (or intuition) of Assumption 1 is not given. It is only said that \"this condition ensures sufficient mixing, preventing the system from being trapped in a subset of states\".  Even more importantly, it is not discussed whether it is a reasonable assumption, e.g., how restrictive it is, and in which settings is expected to hold true.  Providing such a discussion is essential to substantiate the following claim in the conclusions:\n\"We show that standard policy optimization algorithms can effectively approximate an optimal POMDP policy ... without *restrictive assumptions* ...\"\n\n**Assumption 1 is clearly restrictive** in some way. In fact, I provide below a very simple POMDP for which the central Theorem 2 does not hold, implying that Assumption 1 is violated, unless the theorem is false. Thus, in order to support the significance of the contribution, it is extremely important to clarify in what way Assumption 1 is less restrictive than the assumptions considered in the existing literature.\n\n### Example (T-maze)\n\nThe T-maze is an elementary domain introduced in [*Reinforcement learning with long short-term memory*, Bram Bakker, NeurIPS 2021]. Here we present an infinite-horizon variant. The domain consists of a T-shaped maze, sketched in the figure below. The agent is initially located at the beginning of a corridor (position $\\mathtt{S}$), which is followed by a junction (position $\\mathtt{X}$) where the agent can step into two different directions, and can keep going into that direction. The goal of the agent is to step into the correct direction, where the correct direction is determined by a piece of information the agent is given at the very beginning, when he is located at the beginning of the corridor (position $\\mathtt{S}$).  The agent is given a non-zero reward $R > 0$ in every cell after taking the correct direction.\n\n                        .\n                        .\n                        .\n                        |\n                        |\n    S-------------------X\n                        |\n                        |\n                        .\n                        .\n                        .\n\nThe T-maze is naturally modelled as a POMDP. The hidden states consist of\n- an initial state $s_0$,\n- states $s_i^d$ for every position $i$ in the corridor, including the junction, standing for the fact that the agent is in position $i$ and the initial observation specified that the correct direction is $d \\in$ { $1,2$ } (say, e.g., that $1$ and $2$ stand for 'left' and 'right')\n- states $r_i^d$ for $i \\in \\mathbb{N}$ and $d \\in$ { $1, 2$ }, standing for the fact that the agent is in the $i$-th cell after stepping into the first of the two possible directions, and given that the initial observation said that the correct direction to take is direction $d$.\n- states $q_i^d$ for $i \\in \\mathbb{N}$ and $d \\in$ { $1, 2$ }, standing for the fact that the agent is in the $i$-th cell after stepping into the second of the two possible directions, and given that the initial observation said that the correct direction to take is direction $d$.\n\n\nNote that transitions in the hidden state space are deterministic.  Given the entire history of observations and actions, the agent can determine the current hidden state, hence belief states are sharp, always assigning probability $1$ to a hidden state and $0$ to the others.  If only a suffix of the history is available, the agent can only determine its current location, and it cannot distinguish between states $s_i^1$ and $s_i^1$, between states $r_i^1$ and $r_i^2$, and between states $q_i^1$ and $q_i^2$.  In other words, belief states will assign probability $1/2$ to each of the two possible states.\n\nThe optimal value, given an entire history $H$ is roughly $V^* = R \\cdot (1/1-\\gamma)$.  However, the value of any superstate $G(H)$ is roughly $V^* / 2$, since the value is determined by the belief, which is uniform over non-distinguishable stats once we remove the first observation. The difference between the two values i  difference is $V^* / 2 = R/2 \\cdot (1/1-\\gamma)$, which is constant wrt to $l$, as opposed to the bound provided by Theorem 2, which converges to $0$ when $l \\to \\infty$.\n\n\n\n### No experimental evalution\n\nAn experimental evaluation would help to assess the practical effectiveness of the proposed techniques. In particular, it would allow for assessing the impact of the main assumption (Assumption 1), and to draw conclusions on whether it is restrictive or not in terms of the existing benchmarks.\n\n\n\n## Additional Comments\n\n\n*Section 3.1.* The random variables $a_t$ for actions are never introduced. They should be introduced.\n\n*Section 3.1.* Rewards are not introduced, and they are an essential part of POMDPs. As a consequence of this, Lines 167 and Equation (3) mention the function $r(s,a)$ -- reward function of hidden state and action -- which is undefined.\n\nThe definitions of *value function* and *Q-value function* need to be slightly improved. Currently, their definitions index the random variables $\\mathbf{\\pi}_t$ and $a_t$ starting from t = 0. Thus, the definition of value function is valid only for the case where the given belief state $\\mathbf{\\pi}$ is the initial belief state $\\mathbf{\\pi}_0$. Similarly, the definition of Q-value function is valid only for the case where the given belief state $\\mathbf{\\pi}$ and action $a$ are the initial belief state $\\mathbf{\\pi}_0$ and the initial action $a_0$. In fact, $s_t$ is defined as the state at time $t$ (Line 139), and $a_t$ is not defined but I assume it it the action at time $t$.\n\nThe definitions should be generalised to take into account the possibility that the given belief state $\\mathbf{\\pi}$ and action $a$ are the belief state $\\mathbf{\\pi}_t$ and action $a_t$ at time $t$. This is important at least from a conceptual point of view, because otherwise it is not made explicit that a state or state-action pair occurring at time $t$ have a value. The general definition can be obtained by parametrising the two value functions by the time-step variable $t$. Then, the current definitions are recovered as the special case when $t = 0$.\n\nAssumption 1 mentions the quantity $K_{a,y}$, which is undefined.", "was_revised": true, "final_justification": "The discussion has helped me to get a better idea of the significance of the contribution. It is a solid paper overall, addressing a hard problem. However, the central Assumption 1 limits the applicability of the proposed techniques, and makes the contribution rather incremental compared to previous work. I will keep my score, which I believe it fairly summarises my assessment as just summarised.", "rebuttal": "We sincerely thank the reviewer for their thoughtful comments and valuable feedback, which have helped us improve the quality and clarity of the paper. We hope that the following clarifications help address the reviewer's concerns.\n\n## Regarding Assumption 1\n\nAssumption 1, i.e., the filter stability condition, means that every new observation sufficiently informs the agent to reduce differences between any two prior beliefs, ensuring the belief state “forgets” initial uncertainty and the filtering process is well-behaved. Therefore, one intuitive condition when Assumption 1 holds is when **the belief update is less sensitive to the prior and more influenced by new observations and actions**. This means that the next action and observation dictate what the next belief will be more than the current belief of the system.\n\nTherefore, to ensure that the filter stability condition holds, we need\n\n1) **Sufficiently Mixing State Transitions**: The transition kernel $\\mathcal{P}(s'\\mid s,a)$ should be mixing, meaning from any state s, there's a positive probability to reach many other states s' over time. \n\n2) **Non-deterministic and Informative Observations**: The observation kernel $\\phi(y\\mid s)$ must be non-deterministic but sufficiently informative.\n\nTo check whether the filter stability condition holds, one sufficient condition uses the Dobrushin Coefficients of the Transition kernel and the Observation Kernel. \n\nFrom Theorem 5 of [1], if $(1-\\delta(P))(2-\\delta(\\phi)) < 1$, then the filter stability condition holds. Here $\\delta(\\mathcal{P})$ is the minimum Dobrushin coeffient of the Transition kernel across all possible actions and $\\delta(\\phi)$ is the Dobrushin coefficient of the Observation kernel.\n\nLet P be a row-stochastic matrix over a finite state space $\\mathbb{S}$. The Dobrushin coefficient $\\delta(P)$ is defined as: $\\delta(P(.\\mid.,a)) = \\inf_{x, y \\in \\mathbb{S}} \\sum_{z \\in \\mathbb{S}} \\min( P(z\\mid x,a), P(z \\mid y,a)) $\n\nand \n$\\delta(P) = \\min_a \\delta(P(.\\mid.,a))$\n\nThis quantifies the minimum overlap between any two rows of the matrix P.\n\nThis quantity measures how similar the rows of the matrix are; larger values indicate more mixing and hence, stronger contraction properties. As a result, when there is sufficient mixing—i.e., when every state has a non-trivial probability of transitioning to several other states or when every observation can be generated from multiple underlying states—the system exhibits filter stability. This scenario is common in dynamic environments and/or environments that have noisy observations, where the belief update is less sensitive to the prior and more influenced by new observations.\n\nA practical example is **Customer Behavior Modeling in Retail**. Here:\n\nStates represent engagement levels such as {Uninterested, Browsing, Considering, Purchasing}.\n\nObservations are features like the number and type of clicks (e.g., “Viewed Product”, “Added to Cart”).\n\nIn such systems, observations from adjacent engagement states tend to overlap significantly: for instance, both “Browsing” and “Considering” may involve product views and occasional cart additions. Furthermore, customer behavior is highly dynamic—users frequently move between these states in short time spans (e.g., from \"Considering\" back to \"Browsing\" or forward to \"Purchasing\"). This overlap in observation distributions and frequent transitions among states leads to high mixing, thereby increasing the Dobrushin coefficient and ensuring filter stability.\n\nA Simplified example to model customer behaviour is as follows:\n\n**States**: $s_0$ (Uninterested), $s_1$ (browsing), $s_2$ (Considering), $s_3$ (Purchasing). \n\n**Actions**: $a_0$: Show generic homepage, $a_1$: Recommend trending products\n\n**Observations**: $y_0$: No clicks, $y_1$: Viewed product, $y_2$: Added to cart, $y_3$: Purchased\n\nSuppose the transition probabilities for $a_0$ are\n\n| $s_t$ → $s_{t+1}$ | $s_0$ | $s_1$ | $s_2$ | $s_3$ |\n| ----------------- | ----- | ----- | ----- | ----- |\n| **$s_0$**         | 0.4   | 0.4   | 0.1   | 0.1   |\n| **$s_1$**         | 0.3   | 0.3   | 0.2   | 0.2   |\n| **$s_2$**         | 0.2   | 0.3   | 0.3   | 0.2   |\n| **$s_3$**         | 0.1   | 0.2   | 0.4   | 0.3   |\n\nand for $a_1$ be\n\n| $s_t$ → $s_{t+1}$ | $s_0$ | $s_1$ | $s_2$ | $s_3$ |\n| ----------------- | ----- | ----- | ----- | ----- |\n| **$s_0$**         | 0.4   | 0.3   | 0.2   | 0.1   |\n| **$s_1$**         | 0.2   | 0.4   | 0.2   | 0.2   |\n| **$s_2$**         | 0.1   | 0.3   | 0.4   | 0.2   |\n| **$s_3$**         | 0.1   | 0.2   | 0.3   | 0.4   |\nand the observation kernel is \n\n| $s_t$ → $y_t$ | $y_0$ | $y_1$ | $y_2$ | $y_3$ |\n| ------------- | ----- | ----- | ----- | ----- |\n| **$s_0$**     | 0.8   | 0.2   | 0.0   | 0.0   |\n| **$s_1$**     | 0.3   | 0.5   | 0.2   | 0.0   |\n| **$s_2$**     | 0.1   | 0.3   | 0.4   | 0.2   |\n| **$s_3$**     | 0.0   | 0.1   | 0.3   | 0.6   |\n\nTherefore, $\\delta(P) = 0.5$ and $\\delta(\\phi) = 0.1$, which satisfies the sufficient condition $(1-\\delta(P))(2-\\delta(\\phi)) < 1$, which implies that the Filter Stability condition is satisfied for this case.\n\nAdditionally, for applications that do not satisfy Assumption 1, one could consider a multi-step variant where the system exhibits contraction after every k steps. We believe our results could be extended under this weaker assumption, making it a promising direction for future work.\n\n\n[1] Ali Devran Kara. 2022. Near optimality of finite memory feedback policies in partially observed Markov decision processes. J. Mach. Learn. Res. 23, 1, Article 11 (January 2022), 46 pages.\n\n## Comparison with Other Works\n\nCayci et al. consider an ergodicity condition that requires every superstate to be visited within a finite time interval. Under this assumption, they establish a filter stability condition similar to Assumption 1 in our work. However, to achieve meaningful performance guarantees, their method relies on an m-step TD learning setup to obtain accurate estimates of the Q-values, which significantly increases the computational cost of their algorithm. In contrast, our approach yields improved theoretical bounds with lower computational overhead.\n\nKara et al. adopt the same one-step filter stability condition used in our paper. This assumption is a standard tool in the analysis of partially observed systems, widely employed in control theory, filtering, and the POMDP literature to establish convergence, approximation, and learning guarantees. It provides a tractable framework for analyzing the evolution and stability of belief states over time. However, we note that Kara et al. only considered Q-learning without function approximation. One of our key contributions is to show that the same assumption allows us to get finite-time performance bounds for Policy Optimization using new techniques.\n\nIn comparison, several other works adopt the much stronger n-step decodability assumption, which assumes the cumulative observation sequence over n steps becomes informative enough to infer the underlying state. We believe that this is a significantly more restrictive condition than the filter stability assumption used in our analysis.\n\n## Intuition about Lemma 1\n\nIf two histories belong to the same superstate, then their sequences of (action, observation) pairs over the past l timesteps are identical. The key intuition behind Lemma 1 is that, when observations are sufficiently informative, the recent (action, observation) history contains enough information to accurately infer the current system state. As a result, starting from two different initial belief states, the combination of informative observations and strong mixing guarantees that, after a sufficiently long time, the corresponding belief states will converge to similar distributions.\n\n## Regarding More Experimental Evaluations\n\nReviewer TqLW has also made a similar comment. Due to space limitations, we have provided our response in the **Additional Experiments** section of the Comments to Reviewer TqLW.\n\n## Paper Formatting Concerns and Additional Comments made by the Reviewer\n\nThank you for pointing this out — we will address the formatting concerns in the revised draft"}, {"review_id": "aLIGQIMZBF", "reviewer": "Reviewer_TqLW", "summary": "This paper proposes a framework for approximately solving Partially Observable Markov Decision Processes (POMDPs) by transforming them into a fully observable finite-state Markov Decision Process (MDP) over superstates, truncated observation-action histories of fixed length. The key contributions are two-fold:\n- Theoretical Improvement: The authors derive a novel algebraic inequality (Lemma 2) that leads to an improved bound on the difference between the optimal value function of the original POMDP and that of the superstate MDP. The new bound decays exponentially with the history length.\n- Algorithmic Development: Building on this approximation, the paper proposes a policy optimization algorithm that alternates between TD learning and policy updates, and provides theoretical convergence guarantees, even under function approximation with linear features.\nThese results naturally support the success of RNN based Deep RL algorithms for POMDP.", "questions": "Given the connection to memory-based models like RNNs or Transformers, do you envision your theoretical results extending to neural function approximations, or at least guiding their design?", "limitations": "As mentioned in the weaknesses, the paper lacks a discussion of its limitations.\nAlthough the authors claim that limitations are addressed in the conclusion, I could not find any such discussion.\nAt a minimum, the paper should include a discussion on the practical limitations regarding the direct implementability of the proposed algorithm.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- General Algebraic Lemma: The paper introduces a simple yet powerful algebraic inequality (Lemma 2), which can be useful beyond this particular setting. Its generality suggests potential applications to a broader class of approximation analyses in RL and beyond.\n- Theoretical Justification for Practical Methods: The superstate MDP construction and the use of TD learning closely resemble many practical POMDP approaches, such as RNN-based methods and finite memory Q-learning (e.g., Recurrent DQN). The framework thus offers a theoretical explanation for the empirical success of such methods.\n\n**Weaknesses**\n- Lack of Empirical Validation: Although the theoretical results are sound and meaningful and the empirical validation may not be the scope of this paper, even a simple toy example could help ground the theory.\n- Limited Discussion of Limitations: While the theoretical contributions are strong, the paper does not clearly discuss the limitations of the approach. For instance, how large must the history length be in practice to get a reasonable approximation.", "was_revised": true, "final_justification": "The main concern was the implementability of the method, since it is often the case that POMDP algorithm with theoretical guarantees is hard to implement. The additional experiments provided by the author resolved the concern.\nI would maintain the score with accept recommendation.", "rebuttal": "We sincerely thank the reviewer for their thoughtful comments and valuable feedback, which have helped us improve the quality and clarity of the paper. We hope that the following clarifications help address the reviewer's concerns.\n\n## Additional Experiments\n\nThank you for the comment. We do have a simple experiment in the Appendix, which shows the improvement in the performance as the length of the fixed truncated history is increased. We have now added one additional example which we will present later in our response. Additionally, we will add more experiments in the longer version of the paper. A common approach in the RL community is to heuristically use a history of observations as the state, thus converting a POMDP problem into an MDP problem. Our main goal in the paper was to theoretically prove that this approach yields good performance. Prior theoretical results indicated that the performance was much poorer than what we were able to show. \n\nFor now, we have expanded on the simulations presented in the appendix of our paper in the following manner. In our paper, we show that we improve upon the bound in Cayci et al. using a computationally lighter algorithm. To experimentally illustrate this result, we consider an example for a simple partially observable Markov decision process (POMDP) with two states, two actions, and two observations. The environment is stochastic, with state transitions and observations defined by fixed probabilities, and rewards designed to encourage taking the correct action in the hidden state.\n\nTo handle partial observability, we represent the agent’s state by a finite history of recent action-observation pairs, with history lengths of 1 and 2 tested.\n\nFor each setting, the agent trains over 200 episodes, each of fixed length 20 steps. The learning rate $\\alpha$ is set to 0.1 and the discount factor $\\gamma$ to 0.9. Policies are represented tabularly and updated greedily with respect to Q-values after each episode.\n\nWe measure the agent's performance by total reward accumulated per episode and analyze learning curves as well as final average rewards (averaged over the last 20 episodes) to assess convergence and policy quality. Since we are not allowed to share figures as a rebuttal, we are presenting a table of relevant values to demonstrate the improvement of our approach against Cayci et al.\n\n| History Length (H) | Algorithm       | Episodes | EpLen | Alpha | Gamma | AvgReward |\n|--------------------|------------------|----------|--------|--------|--------|------------|\n| 1                  | Our              | 200      | 20     | 0.10   | 0.90   | 14.100     |\n| 1                  | Cayci et al.     | 200      | 20     | 0.10   | 0.90   | 7.900      |\n| 2                  | Our              | 200      | 20     | 0.10   | 0.90   | 16.100     |\n| 2                  | Cayci et al.     | 200      | 20     | 0.10   | 0.90   | 14.900     |\n\n\nAdditionally, since plots and figures are not allowed to be submitted for rebuttals, we present a short table which captures a moving average reward at episode numbers {20,40,60,80,100,120,140,160,180,200}\n\n| Episode | H=1 Our | H=1 Cayci et al. | H=2 Our | H=2 Cayci et al. |\n|---------|---------|-------------------|---------|-------------------|\n| 20      | 14.00   | 8.25              | 14.75   | 15.05             |\n| 40      | 14.00   | 7.70              | 15.35   | 13.30             |\n| 60      | 13.30   | 8.30              | 16.90   | 13.15             |\n| 80      | 13.20   | 8.20              | 16.15   | 14.75             |\n| 100     | 13.80   | 8.20              | 14.45   | 14.25             |\n| 120     | 13.70   | 7.60              | 16.20   | 12.90             |\n| 140     | 14.20   | 7.80              | 16.20   | 14.05             |\n| 160     | 14.30   | 7.70              | 14.90   | 14.10             |\n| 180     | 14.20   | 8.00              | 14.45   | 14.00             |\n| 200     | 14.25   | 7.95              | 16.40   | 13.30             |\n\n\nFrom this, we clearly see that 1) Increasing history length provides better results 2) Our algorithm performs better than Cayci et al. in terms of average reward.\n\nAdditionally, several prior works have empirically demonstrated the effectiveness of using finite histories of observations as surrogates for hidden states in partially observable reinforcement learning problems. For example, [1] leverages pretrained language transformers to compress observation histories into compact representations, showing improved sample efficiency on POMDP benchmarks. This is similar to our work if we consider the feature vectors generated by the language transformers as the feature vectors. Similarly, [2] presents a framework that adaptively uses privileged state information during training while deploying policies that rely on observation histories. Other related studies, such as [3] and [4], support the use of history-based or memory-augmented policies with policy gradient methods.\n\nThese empirical results suggest that the framework we analyze theoretically already has practical viability in reinforcement learning applications. However, we note that our work is the first to provide much tighter theoretical guarantees than available before.\n\n[1] Paischer, Fabian & Adler, Thomas & Patil, Vihang & Bitto-Nemling, Angela & Holzleitner, Markus & Lehner, Sebastian & Eghbalzadeh, Hamid & Hochreiter, Sepp. (2022). History Compression via Language Models in Reinforcement Learning. 10.48550/arXiv.2205.12258. \n\n[2] Jinqiu Li, Enmin Zhao, Tong Wei, Junliang Xing, and Shiming Xiang. 2025. Dual critic reinforcement learning under partial observability. In Proceedings of the 38th International Conference on Neural Information Processing Systems (NIPS '24), Vol. 37. Curran Associates Inc., Red Hook, NY, USA, Article 3704, 116676–116704.\n\n[3] Ni, T., Eysenbach, B. &amp; Salakhutdinov, R.. (2022). Recurrent Model-Free RL Can Be a Strong Baseline for Many POMDPs. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:16691-16723\n\n[4] Aberdeen, D., Buffet, O. &amp; Thomas, O.. (2007). Policy-Gradients for PSRs and POMDPs. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:3-10 \n\n## Discussion on Limitations\n\nThe analysis is limited to discrete states and actions. Additionally, our analysis is limited to linear function approximation. Therefore, a potential future work includes extending the analysis to RNNs or Transformer models. We will explicitly mention these limitations in the revised draft.\n\n ## Extension to RNNs or Neural function approximation\n\n In our paper, we focused on the linear function approximation case; however, we believe that a proof technique inspired by the proof and assumptions made in Cayci and Eryilmaz [2024] can be used to extend our analysis to RNNs. Additionally, one may use ideas from Neural Tangent Kernel (NTK) theory to extend results to neural function approximations."}, {"review_id": "VYmXLMqb5c", "reviewer": "Reviewer_jAwy", "summary": "In this paper, the authors address the problem of solving finite state and finite actions partially observable reinforcement learning problems. Specifically, they derive theoretical bounds on the approximation capability of superstate MDPs. Superstate MDPs have been introduced in previous work and are MDPs over histories of observation and actions of a fixed length. \n\nThe authors’ results show tighter bounds than previous work in the approximation capabilities of superstate MDPs, with an exponentially decaying error with the length of the history considered. Their proof rely on a bound on a specific algebraic identity with probability mass functions. \n\nThey use the proven bounds to show convergence of a TD-learning value estimation algorithm with linear approximation. They then extend the result to a policy optimization method using such TD-learning method in combination with a policy update method. The policy uses a softmax over the estimated Q-values. They show that the regret of the resulting algorithm is bounded by $T + O(T^{3/4} \\log T).$", "questions": "- How constraining is really the uniform filter stability condition in practice? Would standard POMDP benchmark problems satisfy it? Can you also provide some intuitions of its meaning?\n- In the proof for theorem 2, l492, you dropped the infinity norm why? You are also assuming that it is the same $\\hat{a}$ maximizing the r.h.s of the Bellman operator for $V^*$ and $\\tile{V}$, it does not seem correct, can you explain?\n- I did not follow the end of the proof of lemma 3, you are constructing the $coefficient$ and most of them are 0s, but what shows that some of them are not, and that those specific coefficient correspond to states that only differ in the first two elements?", "limitations": "The analysis is limited to discrete state and actions and linear approximation. This is clearly stated by the authors.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The problem of RL in partially observable environment is important and has many applications. Previous works have shown the strength of methods relying on finite histories empirically but, as acknowledged by the authors, there is no strong theoretical results to support them. \n\n- The result from the author seem to improve on previous work by providing tighter bounds for the approximation between the finite-history MDP representing the underlying POMDP.\n\n- The theoretical result of the regret analysis of the proposed method might be novel. The derived TD algorithm is not particularly novel, and consists of policy optimization with an augmented state that is the last l state+action pairs, actually common practice in deep RL but being formalized in this paper.\n\n**Weaknesses**\n\n1. Lack of discussion of the main assumption\n\nAssumption 1 is the main cornerstone of the results but no insights are provided. I think the authors should provide some intuitions about whether or not this assumption is strict and more details on when it holds or not. I understand that the total variation between reachable next belief state is smaller than the total variation between two belief state?\nThe result on the approximation quality of the MDP is mostly valid because of assumption 1, but little is said about the validity of this assumption.\n\n2. Weak empirical validation\n\nOne plot is provided in appendix for Frozen lake but no discussion of the result is provided. It is said that the resulting algorithm is more efficient than the previous work, but no direct comparison is provided. No comparison is provided against naïve baseline like standard Q-learning on an augmented state space stacking the history (no belief). \nWith POMDPs, the question of scalability of algorithms with the horizon is very important. I am surprised that it is not discussed much in the paper. \n\n3. presentation\n\nThe proofs were difficult to follow, and I have doubts on some steps (see questions) which makes it hard to evaluate correctness. \n\n-\tFor the proof of lemma 2, number the lines, and maybe add a few words explaining the step to make the review easier. The third step when you introduce the max was not obvious to me.\n-\tIn the proof of lemma 3, there is a typo l517, and l530.  The proof is really hard to follow and I was not really able to understand if it was correct. There is a switch from general distributions d1 and d2, to distribution over beliefs halfway.\n\n**Writing feedback**\n-\tThe related work on POMDP and internal state representation is a redundant with the intro\n-\tUsing $\\pi$ for the belief state is a bit confusing since it is traditionally used for policies. I suggest using $b$ as many POMDP papers do. Then you can use $\\pi$ instead of $\\mu$ for the policy.", "was_revised": true, "final_justification": "The authors clarified most of the concerns I had on the proofs of the theorems in the rebuttal. Thus I increase my score to borderline accept. It is still borderline because assumption 1 is quite limiting and the empirical evaluation is also limited (even if improved during the rebuttal).", "rebuttal": "We sincerely thank the reviewer for their thoughtful comments and valuable feedback, which have helped us improve the quality and clarity of the paper. We hope that the following clarifications help address the reviewer's concerns.\n\n## Clarification Regarding Proof of Theorem 2\n\nThere was a typo in the original proof for Theorem 2, where the infinity norm was not present in some steps, which might have led to your confusion. Due to the character limit, we are unable to provide the entire detailed proof. Therefore, we provide more detailed steps for the parts of the proof that were confusing to you. We will add more detailed steps to our proofs in the revised draft of the paper.\n\nLet $\\delta$ be defined as follows, \n\n\\begin{equation}\n     \\delta = ||  V^*\\big(\\boldsymbol{\\pi}(H) \\big) - \\tilde{V}\\big(\\mathcal{G}(H) \\big) ||  _{\\infty}\n\\end{equation}\n\nNext, we upper bound $|   V^*\\big(\\boldsymbol{\\pi}(H) \\big) - \\tilde{V}\\big(\\mathcal{G}(H) \\big)|$ for all $H$. First we can write it as\n\n\\begin{align}\n\\Big|\\max_a \\Big[ \\sum_s \\pi(s \\mid  H) r(s,a) + \\gamma \\sum_y V^*\\big(\\boldsymbol{\\pi}(H \\cup \\{y,a\\})\\big) \\sigma(\\boldsymbol{\\pi}(H),y,a)\\Big]\n    - \\max_a \\Big[ \\tilde{r}(B,a) + \\gamma \\sum_y \\tilde{V}\\big(\\mathcal{G}\\big(B \\cup \\{y,a\\})\\big)\\sigma(\\boldsymbol{\\pi}(B),y,a)\\Big] \\Big | .\n\\end{align}\n\nAssume WLOG that the first term is greater than the second term. Next, suppose $\\hat{a}$ maximizes $\\sum_s \\pi(s \\mid  H) r(s,a) + \\gamma \\sum_y V^*\\big(\\boldsymbol{\\pi}(H \\cup \\{y,a\\})\\big) \\sigma(\\boldsymbol{\\pi}(H),y,a)$. \n\nThen the above expression equals\n\n\\begin{align} \n    \\Big[ \\sum_s \\pi(s \\mid  H) r(s,\\hat{a}) + \\gamma \\sum_y V^*\\big(\\boldsymbol{\\pi}(H \\cup \\{y,\\hat{a}\\})\\big) \\sigma(\\boldsymbol{\\pi}(H),y,\\hat{a})\\Big] - \\max_a \\Big[\\tilde{r}(B,a) + \\gamma \\sum_y \\tilde{V}\\big(\\mathcal{G}\\big(B \\cup \\{y,a\\})\\big)\\sigma(\\boldsymbol{\\pi}(B),y,a)\\Big] \n\\end{align}\n\nFinally, since the maximum value of the second term will be greater than evaluating the second term for $a=\\hat{a}$, it is upper bounded as follows\n\n\\begin{align}\n\\leq \\Big[ \\sum_s \\pi(s \\mid  H) r(s,\\hat{a}) + \\gamma \\sum_y V^*\\big(\\boldsymbol{\\pi}(H \\cup \\{y,\\hat{a}\\})\\big) \\sigma(\\boldsymbol{\\pi}(H),y,\\hat{a})\\Big] - \\Big[\\tilde{r}(B,\\hat{a}) + \\gamma \\sum_y \\tilde{V}\\big(\\mathcal{G}\\big(B \\cup \\{y,\\hat{a}\\})\\big)\\sigma(\\boldsymbol{\\pi}(B),y,\\hat{a})\\Big] \n\\end{align}\n\nThen following same steps in the proof mentioned in the paper, we get\n\\begin{align}\n    |   V^*\\big(\\boldsymbol{\\pi}(H) \\big) - \\tilde{V}\\big(\\mathcal{G}(H) \\big)| \\leq 2(1-\\rho)^l\\bar{r} + \\gamma \\bigg[ \\big\\|   \\sigma(\\boldsymbol{\\pi}(H),\\cdot,\\hat{a})- \\sigma(\\boldsymbol{\\pi}(B),\\cdot,\\hat{a}) \\big\\|  _{TV}\\bigg(\\frac{\\bar{r}}{1-\\gamma} - \\frac{\\delta}{2}\\bigg) + \\delta\\bigg].\n\\end{align}\nTherefore,\nCase 1: If $\\big(\\frac{\\bar{r}}{1-\\gamma} - \\frac{\\delta}{2}\\big) > 0$. Then, we have\n\\begin{align}\n    \\delta \\leq  2(1-\\rho)^l\\bar{r} + \\gamma \\bigg[ \\sup_H ||   \\sigma(\\boldsymbol{\\pi}(H),\\cdot,\\hat{a})- \\sigma(\\boldsymbol{\\pi}(B),\\cdot,\\hat{a}) ||  _{TV}\\bigg(\\frac{\\bar{r}}{1-\\gamma} - \\frac{\\delta}{2}\\bigg) + \\delta\\bigg]\n\\end{align}\n\nOr in the other case we have\n\n\\begin{align}\n    \\delta \\leq  2(1-\\rho)^l\\bar{r} + \\gamma \\bigg[ \\inf_H ||   \\sigma(\\boldsymbol{\\pi}(H),\\cdot,\\hat{a})- \\sigma(\\boldsymbol{\\pi}(B),\\cdot,\\hat{a}) ||_{TV} \\bigg(\\frac{\\bar{r}}{1-\\gamma} - \\frac{\\delta}{2}\\bigg) + \\delta\\bigg]\n\\end{align}\n\nNow, since, both $\\inf_H ||   \\sigma(\\boldsymbol{\\pi}(H),\\cdot,\\hat{a})- \\sigma(\\boldsymbol{\\pi}(B),\\cdot,\\hat{a})  ||_{TV}$ and \n\n$\\sup_H ||   \\sigma(\\boldsymbol{\\pi}(H),\\cdot,\\hat{a})- \\sigma(\\boldsymbol{\\pi}(B),\\cdot,\\hat{a}) ||_{TV}$ are upper bounded by $2(1-\\rho)^l$, we get the mentioned result.\n\n\n## Clarification Regarding Proof of Lemma 3\n\nNext, to clarify the question regarding Lemma 3, we first present a short proof sketch detailing steps involved in the proof.\n\nWe first assume (we will construct such $\\alpha_{i,j}$ in algorithm 3) that there exists $\\alpha_{i,j} \\geq 0$ and $\\sum_{i,j} \\alpha_{i,j} = || d_1 - d_2 ||_{TV}$ such that \n\n$ || \\tilde{\\mathcal{P}}^{\\mu}d_1- \\tilde{\\mathcal{P}}^{\\mu}d_2 ||_{TV} $\n\n $ \\leq \\sum_{i,j} \\alpha_{i,j} || \\tilde{\\mathcal{P}}^{\\mu}(e_i-e_j)||_{TV}$\n\nNow, since $ || \\tilde{\\mathcal{P}}^{\\mu}(e_i-e_j)||_{TV}$ is less than or equal to 1,\n\n if we can prove that $|| \\tilde{\\mathcal{P}}^{\\mu}(e_i-e_j)||_{TV} < 1$ for some pair of $i,j$ such that $\\alpha_{i,j} > 0$, we are guaranteed a contraction\n\nNext, we show that if $e_i$ and $e_j$ are superstates which only differ in the first two elements, then for such $e_i, e_j$, $ || \\tilde{\\mathcal{P}}^{\\mu}(e_i-e_j)||_{TV} < 1$\n\nFinally, in the constructed algorithm we show that $\\alpha_{i,j} > 0$ for such pair of $e_i,e_j$. Now since $\\Delta_i, \\Delta_j \\neq 0$ we need to prove that $\\Delta_i, \\Delta_j \\neq 0 \\implies \\alpha_{i,j} > 0$. See that $\\alpha_{i,j} = \\min(\\Delta_i, - \\Delta_j)$. \n\nTherefore, since $\\Delta_i, \\Delta_j \\neq 0$, $\\alpha_{i,j} > 0$. Additionally, the steps $\\Delta_i \\leftarrow \\Delta_i - \\alpha_{i,j}$ and $\\Delta_j \\leftarrow \\Delta_j + \\alpha_{i,j}$ ensures either one of them goes to 0 and thus is removed from the surplus/deficit set ensuring that $\\alpha_{i,j}$ is not modified further.\n\n## Regarding Uniform Filter Stability Condition (Assumption 1)\nAssumption 1, i.e., the filter stability means that every new observation sufficiently informs the agent to reduce differences between any two prior beliefs, ensuring the belief state “forgets” initial uncertainty and the filtering process is well-behaved. Therefore, one intuitive condition when Assumption 1 holds is when **the belief update is less sensitive to the prior and more influenced by new observations and actions**. This means that the next action and observation dictate what the next belief will be more than the current belief of the system.\n\nTherefore, to ensure that the filter stability condition holds, we need\n\n1) **Sufficiently Mixing State Transitions**: The transition kernel $\\mathcal{P}(s'\\mid s,a)$ should be mixing, meaning from any state s, there's a positive probability to reach many other states s' over time. \n\n2) **Non-deterministic and Informative Observations**: The observation kernel $\\phi(y\\mid s)$ must be non-deterministic but sufficiently informative.\n\nTo check whether the filter stability condition holds, one sufficient condition uses the Dobrushin Coefficients of the Transition kernel and the Observation Kernel. \n\nFrom Theorem 5 of [1], if $(1-\\delta(P))(2-\\delta(\\phi)) < 1$, then the filter stability condition holds. Here $\\delta(\\mathcal{P})$ is the minimum Dobrushin coefficient of the Transition kernel across all possible actions and $\\delta(\\phi)$ is the Dobrushin coefficient of the Observation kernel.\n\nLet P be a row-stochastic matrix over a finite state space $\\mathbb{S}$. The Dobrushin coefficient $\\delta(P)$ is defined as: $\\delta(P(.\\mid.,a)) = \\inf_{x, y \\in \\mathbb{S}} \\sum_{z \\in \\mathbb{S}} \\min( P(z\\mid x,a), P(z \\mid y,a)) $\n\nand \n$\\delta(P) = \\min_a \\delta(P(.\\mid.,a))$\n\nThis quantifies the minimum overlap between any two rows of the matrix P.\n\nThis quantity measures how similar the rows of the matrix are; larger values indicate more mixing and hence, stronger contraction properties. As a result, when there is sufficient mixing—i.e., when every state has a non-trivial probability of transitioning to several other states or when every observation can be generated from multiple underlying states—the system exhibits filter stability. This scenario is common in dynamic environments or environments that have noisy observations, where the belief update is less sensitive to the prior and more influenced by new observations.\n\nA practical example is **Customer Behavior Modeling in Retail**. Here:\n\nStates represent engagement levels such as {Uninterested, Browsing, Considering, Purchasing}.\n\nObservations are features like the number and type of clicks (e.g., “Viewed Product”, “Added to Cart”).\n\nIn such systems, observations from adjacent engagement states tend to overlap significantly: for instance, both “Browsing” and “Considering” may involve product views and occasional cart additions. Furthermore, customer behavior is highly dynamic—users frequently move between these states in short time spans (e.g., from \"Considering\" back to \"Browsing\" or forward to \"Purchasing\"). This overlap in observation distributions and frequent transitions among states leads to high mixing, thereby increasing the Dobrushin coefficient and ensuring filter stability.\n\nAdditionally, Reviewer KcfL raised a similar concern. The reviewer may find the \"Regarding Assumption 1\" section of our rebuttal to Reviewer KcfL helpful, as it addresses this point in more detail.\n\n[1] Ali Devran Kara. 2022. Near optimality of finite memory feedback policies in partially observed Markov decision processes. J. Mach. Learn. Res. 23, 1, Article 11 (January 2022), 46 pages.\n\n## Empirical Validation\n\nReviewer TqLW has also made a similar comment. Due to space limitations, we have provided our response in the **Additional Experiments** section of the Comments to Reviewer TqLW, which provides an additional experiment comparing our work with Cayci et al.\n\n## Writing Feedback and Additional Comments made by the Reviewer\n\nThank you for pointing this out — we will address the formatting concerns in the revised draft"}, {"review_id": "dn6q55Uz2U", "reviewer": "Reviewer_2QJ5", "summary": "This paper addresses the challenges of solving partially observable reinforcement learning (PORL) problems, where the continuous belief states in POMDPs complicate optimal policy learning. The authors propose approximating the POMDP with a finite-state Markov Decision Process (MDP), referred to as a Superstate MDP, constructed from finite historical states. They establish theoretical guarantees that explicitly link the optimal value function of this simplified Superstate MDP to that of the original POMDP. Leveraging this framework, the authors introduce a policy-based learning approach utilizing linear function approximation, combining TD-learning and policy optimization to solve the approximated problem. They show that the approximation error decreases exponentially with the history length. Notably, this work provides the first finite-time error bounds quantifying the inaccuracies that arise when applying standard TD-learning methods to problems with non-Markovian dynamics.", "questions": "(Q1) Can you provide a comparison table of the current result with those from preexisting work, e.g. Subramanian and Mahajan 2019, Cayci et al. (2024), etc.\n\n(Q2) Can you provide empirical study result comparing your proposed algorithm with those preexisting ones referred, e.g. Cayci (2024)?\n\n(Q3) The paper builds upon the superstate MDP construction introduced by Kara and Yuksel (2023). How is the theoretical analysis presented here differs from Kara and Yuksel (2023)?\n\n(Q4) A related but distinct paper [1] explores convergence properties of TD learning in Markov Reward Processes incorporating hidden state information. Could the authors clarify the connections to and differences from their current framework and theoretical results?\n\n[1] Amiri, M., & Magnússon, S. (2024, June). On the Convergence of TD-Learning on Markov Reward Processes with Hidden States. In 2024 European Control Conference (ECC) (pp. 2097-2104). IEEE.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\nThe paper is clearly written and effectively identifies the research gap along with relevant literature. It is technically rigorous, and its the first to provide convergence guarantees for TD-learning within the POMDP framework.\n\nWeakness:\nplease refer to questions in the below.", "was_revised": true, "final_justification": "I appreciate the author's detailed response and I'll maintain my score.", "rebuttal": "We sincerely thank the reviewer for their thoughtful comments and valuable feedback, which have helped us improve the quality and clarity of the paper. We hope that the following clarifications help address the reviewer's concerns.\n\n## Comparison Table with Recent Work\n\nWe present below a comparison table of our results with preexisting works, namely, Kara et al., Mahajan et al and Cayci et al.\n\n| Aspect                           | Our Work                                                              | Mahajan et al.                                   | Cayci et al.                             | Kara et al.                                                               |\n| :------------------------------- | :-------------------------------------------------------------------- | :----------------------------------------------- | :---------------------------------------------- | :------------------------------------------------------------------------ |\n| **Value function gap bound** | Tighter bound; improves prior results with worst-case guarantee       | $ O\\left( \\frac{1}{(1-\\gamma)^2} \\right) $      | Polynomial in $ \\frac{1}{1-\\gamma} $            | $ O\\left( \\frac{1}{(1-\\gamma)^2} \\right) $ expected-case only             |\n| **Policy Optimization (PO) analysis** | First to show convergence for standard PO (TD-learning + policy update), no added complexity | Empirical deep RL; misaligned objective; no guarantees | Uses $ m $-step TD; high computational complexity | No PO analysis (Analyses Q-learning)                                      |\n| **Function approximation** | Finite-time bounds for PO with linear approximation                   | Not analyzed                                     | Analyzed but worse bounds                       | Do not analyze function approximation, also difficult to prove function approximation for Q-learning |                                                                  |\n| **Convergence guarantees** | Finite-time, non-asymptotic, under standard assumptions               | No theoretical convergence guarantees            | Requires $ m $-step TD; more computationally heavy | Asymptotic only                                                           |\n\n\n## Difference between the theoretical analysis presented in our paper and Kara and Yuksel (2023)\n\nThe theoretical analysis in this paper builds upon the superstate MDP construction introduced by Kara and Yuksel (2023), beyond that we study completely different algorithms and therefore the analysis is also different. Specifically, they study Q-learning without function approximation whereas we study policy based methods with function approximation. Some additional details on the differences between the two papers are as follows:\n\n**Improved Approximation Guarantees:** To obtain the result in Theorem 2, Kara and Yuksel (2023) use standard decomposition and triangle inequality techniques to bound errors, which can be loose and conservative. However, we introduce Lemma 2, which helps us to get a tighter bound.\n\n**Policy Optimization Algorithm:** \nKara and Yuksel (2023) focus on the Q-learning algorithm whereas our paper focuses on the TD-learning followed by Policy Optimization framework.\nTheir analysis benefits from a stationary exploratory sampling policy, which simplifies theory. Our work analyzes a TD-learning based policy optimization approach where the sampling policy changes at every update, making the sampling non-stationary relative to the underlying POMDP states. Additionally, we derive finite-time bounds which is not the case in Kara and Yuksel (2023). \n\n**Obtaining Finite Time Performance Bounds** The approach in Kara and Yuksel (2023) is to express the algorithm updates in terms of iterates which allows one to use Robbins-Monro type algorithms, to prove asymptotic convergence. Since our focus is on getting a Finite Time Performance Bound, we use a completely different analysis where we use the contraction property of the Bellman operator along with other algebraic techniques to relate the error improvement between successive steps of the TD-learning updates. Additionally, we need to handle an additional sampling mismatch error due to the non-stationary nature of the sampling policy while deriving bounds for TD-learning.\n\n**Extending to Function Approximation Setting:** We extend the theoretical guarantees to linear function approximation settings in policy optimization, allowing scalability to larger or continuous state spaces. Kara and Yuksel (2023) do not address this.\n\n**Providing Regret Bounds:** Since the algorithm updates the policy at every step, a more accurate way of capturing the performance of the algorithm is through regret bounds, which is not explored by Kara and Yuksel (2023).\n\n## Comparison to the work by Amiri and Magnusson\n\nThank you for letting us know about this reference. However, based on our reading of the paper, their algorithm does not seem to apply to POMDPs. Specifically, according to Assumption 2 in their paper, the hidden states and the observations evolve independently of each other. On the other hand, a key feature of POMDPs is that observations provide information about the hidden states. The only link in their paper between the hidden states and observations is through the reward function.\n\n## Empirical Validation\nReviewer TqLW has also made a similar comment. Due to space limitations, we have provided our response in the **Additional Experiments** section of the Comments to Reviewer TqLW, which provides an additional experiment comparing our work with Cayci et al."}]

Author rebuttal:

Meta-review: I am weakly positive on this paper. It contains interesting theoretical results that deserve an audience. However, it makes an assumption (assumption 1) that may be reasonable but that is not, as far as I can tell, widely adopted and known - unless it goes by another name. This assumption was not explained and justified in a way that made the reviewers comfortable that it was a clear and reasonable assumption. The paper did not initially provide any compelling experiments or detailed discussions of practical domains that might reassure readers that the assumptions were reasonable.

After some back and forth with the reviewers, the authors did address some of these concerns. They explained assumption 1 better, and they provided some modest experiments. This was sufficient to move all of the reviewers into "borderline accept", but none were interested is championing the paper. (In discussion, I asked if anybody was willing to champion the paper, and no reviewers did so.)

In summary, I think that this is interesting work that - as initially submitted - was less compelling than it could be due to minimally discussed assumptions and lack of experiments. The authors demonstrated that they can make a more compelling case, but the rebuttal process got them just barely over the bar in terms of being convincing to reviewers. I think this paper could be a fine poster for NeurIPS, though I also wonder if the authors could have more impact overall if they submitted to a future venue and included more compelling experiments and justifications in that paper.
Decision: Accept (poster)