Scalable Policy-Based RL Algorithms for POMDPs

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.

Comparison Table with Recent Work

We present below a comparison table of our results with preexisting works, namely, Kara et al., Mahajan et al and Cayci et al.

Difference between the theoretical analysis presented in our paper and Kara and Yuksel (2023)

The 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:

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.

Policy Optimization Algorithm: Kara and Yuksel (2023) focus on the Q-learning algorithm whereas our paper focuses on the TD-learning followed by Policy Optimization framework. Their 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).

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.

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.

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).

Comparison to the work by Amiri and Magnusson

Thank 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.

Empirical Validation

Reviewer 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.

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.

Clarification Regarding Proof of Theorem 2

There 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.

Let $\delta$ be defined as follows,

$

 \delta = ||  V^*\big(\boldsymbol{\pi}(H) \big) - \tilde{V}\big(\mathcal{G}(H) \big) ||  _{\infty}

$

Next, 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

$

\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] - \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 | .

$

Assume 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)$.

Then the above expression equals

$

\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] 

$

Finally, 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

$

\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]

$

Then following same steps in the proof mentioned in the paper, we get

$

|   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].

$

Therefore, Case 1: If $\big(\frac{\bar{r}}{1-\gamma} - \frac{\delta}{2}\big) > 0$. Then, we have

$

\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]

$

Or in the other case we have

$

\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]

$

Now, since, both $\inf_H || \sigma(\boldsymbol{\pi}(H),\cdot,\hat{a})- \sigma(\boldsymbol{\pi}(B),\cdot,\hat{a}) ||_{TV}$ and

$\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.

Clarification Regarding Proof of Lemma 3

Next, to clarify the question regarding Lemma 3, we first present a short proof sketch detailing steps involved in the proof.

We 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

$|| \tilde{\mathcal{P}}^{\mu}d_1- \tilde{\mathcal{P}}^{\mu}d_2 ||_{TV}$

$\leq \sum_{i,j} \alpha_{i,j} || \tilde{\mathcal{P}}^{\mu}(e_i-e_j)||_{TV}$

Now, since $|| \tilde{\mathcal{P}}^{\mu}(e_i-e_j)||_{TV}$ is less than or equal to 1,

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

Next, 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$

Finally, 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)$.

Therefore, 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.

Regarding Uniform Filter Stability Condition (Assumption 1)

Assumption 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.

Therefore, to ensure that the filter stability condition holds, we need

1. 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.

2. Non-deterministic and Informative Observations: The observation kernel $\phi(y\mid s)$ must be non-deterministic but sufficiently informative.

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 [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.

Let 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))$

and $\delta(P) = \min_a \delta(P(.\mid.,a))$

This quantifies the minimum overlap between any two rows of the matrix P.

This 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.

A practical example is Customer Behavior Modeling in Retail. Here:

States represent engagement levels such as {Uninterested, Browsing, Considering, Purchasing}.

Observations are 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 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.

Additionally, 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.

[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.

Empirical Validation

Reviewer 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.

Writing Feedback and Additional Comments made by the Reviewer

Thank you for pointing this out — we will address the formatting concerns in the revised draft

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.

Additional Experiments

Thank 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.

For 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.

To 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.

For 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.

We 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.

Additionally, 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}

From 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.

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, [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.

These 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.

[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.

[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.

[3] Ni, T., Eysenbach, B. & 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

[4] Aberdeen, D., Buffet, O. & 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

Discussion on Limitations

The 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.

Extension to RNNs or Neural function approximation

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.

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.

Regarding Assumption 1

Assumption 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.

Therefore, to ensure that the filter stability condition holds, we need

1. 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.

2. Non-deterministic and Informative Observations: The observation kernel $\phi(y\mid s)$ must be non-deterministic but sufficiently informative.

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 [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.

Let 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))$

and $\delta(P) = \min_a \delta(P(.\mid.,a))$

This quantifies the minimum overlap between any two rows of the matrix P.

This 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.

A practical example is Customer Behavior Modeling in Retail. Here:

States represent engagement levels such as {Uninterested, Browsing, Considering, Purchasing}.

Observations are 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 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.

A Simplified example to model customer behaviour is as follows:

States: $s_0$ (Uninterested), $s_1$ (browsing), $s_2$ (Considering), $s_3$ (Purchasing).

Actions: $a_0$: Show generic homepage, $a_1$: Recommend trending products

Observations: $y_0$: No clicks, $y_1$: Viewed product, $y_2$: Added to cart, $y_3$: Purchased

Suppose the transition probabilities for $a_0$ are

and for $a_1$ be

Therefore, $\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.

Additionally, 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.

[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.

Comparison with Other Works

Cayci 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.

Kara 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.

In 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.

Intuition about Lemma 1

If 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.

Regarding More Experimental Evaluations

Reviewer 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.

Paper Formatting Concerns and Additional Comments made by the Reviewer

Thank you for pointing this out — we will address the formatting concerns in the revised draft