A Policy Gradient Method for Confounded POMDPs

We are grateful for your valuable feedback and the recognition you've given to our work. We would like to address your concerns in this response.

Weakness 1 and question 1 regarding technical contributions in Sections 6.1 & 6.2

Thank you for acknowledging one of our main theoretical contributions in the derivation of the identification results for the policy gradient. In addition to this, we would like to highlight some crucial technical contributions in estimation and optimization presented in Sections 6.1 and 6.2. Below we provide a detailed summary.

In the theoretical results related to the estimation of the policy gradient (section 6.1), our main technical contributions are as follows.

• Novel Error Decomposition. We derived a novel decomposition of error for policy gradient estimation, outlined in Appendix F.1 or equations (63)(64)(65). Existing works such as [1, 2, 3] typically consider the decomposition of the estimation error of policy value into multiple one-step errors caused by min-max estimation for the conditional operator of the value bridge function. In contrast, we study the decomposition of the estimation error of policy gradient, which turns out to involve one-step errors caused by min-max estimation for both the conditional operator of the value bridge function and the gradient bridge functions. This unique decomposition arises from our method of policy gradient identification, incorporating policy value identification results as assistance. Importantly, the derivation of this decomposition is not a trivial extension from existing works. Such error decomposition enhances the understanding of the source of all involved statistical errors, and can be potentially used to design more efficient or robust estimators for policy gradient in confounded POMDPs. For example, a direct idea is to simply consider more efficient/robust off-policy evaluation methods in confounded POMDPs and see if their incorporation can improve the efficiency/robustness of the policy gradient estimators by looking at the proposed error decomposition of the policy gradient.

• Focus on Policy Gradient Estimation with Dimension $>1$. In contrast to existing works [1, 2, 3], which primarily focused on policy value estimation with dimension equal to 1, our work uniquely concentrates on policy gradient estimation with dimensions greater than 1. This emphasis, driven by the significance of history-dependent policies, introduces an additional layer of complexity to the analysis. Specifically, the dimensionality of the policy parameter space, denoted as $d_\Theta$, becomes a crucial factor in our theoretical results. Therefore, our derivation of upper bounds with explicit dependence on $d_\Theta$ facilitates understanding of the complexity in higher-dimensional min-max estimation.

• Upper Bounds with Explicit Dependence on Key Parameters (in the Nonparametric Settings). In contrast to [1,2,3], our work provides upper bounds in terms of all key parameters when function classes are assumed to be RKHSs (see details in Appendix B). This allows for non-parametric estimation. Existing works often provide examples only under linear settings or with finite VC dimensions, making our results more versatile and applicable to a broader range of scenarios.

In the theoretical results related to the global convergence of the proposed algorithm (section 6.2), our main technical contributions are as follows.

• Extension from MDPs to POMDPs. Building upon the theoretical results of [4, 5], we extend their results from MDPs to POMDPs. This extension necessitates the incorporation of specific lemmas tailored for POMDPs, including the policy gradient lemma and the performance difference lemma (Lemmas 3, 8, 10). Our work thus contributes to advancing theoretical understanding in the context of POMDPs.

• Finite-horizon v.s. Infinite-horizon. While [4,5] focus on the infinite-horizon discounted MDPs, we study the finite-horizon settings. Therefore, our work requires us to study the upper bound with explicit dependence on the length of horizon $T$, especially when history is included in our POMDP settings.

References:

[1] Bennett, Andrew, and Nathan Kallus. "Proximal Reinforcement Learning: Efficient Off-policy Evaluation in Partially Observed Markov Decision Processes."

[2] Shi, Chengchun, et al. "A Minimax Learning Approach to Off-policy Evaluation in Confounded Partially Observable Markov Decision Processes."

[3] Lu, Miao, et al. "Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes."

[4] Agarwal, Alekh, et al. "On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift."

[5] Liu, Yanli, et al. "An Improved Analysis of (Variance-reduced) Policy Gradient and Natural Policy Gradient Methods."

We sincerely appreciate your constructive feedback and your acknowledgment of our work.

Regarding notations

Thank you for the valuable suggestion. We acknowledge the importance of clarity in notation. In response to your feedback, we have included a table in Appendix A that lists all the main notations used along with their definitions. Additionally, we have simplified the notations where feasible and ensured that each symbol is explicitly defined upon its initial use in the manuscript. See Section 5 in the revised version.

Regarding Full Coverage Assumption (Assumption 4(a))

Thank you for your suggestions. In the following, we discuss on practical scenarios in which this assumption is either met or not, and propose a potential way to address this concern. We have also added this discussion in Appendix B.4 of the revised manuscript.

In certain real-world applications, such as the sequential multiple assignment randomized trials (SMART) designed to build optimal adaptive interventions, the assumption of full coverage is usually satisfied. This is because data collection in these trials is typically randomized, ensuring a comprehensive representation by the behavior policy. However, we acknowledge that in domains such as electronic medical records, meeting the full coverage assumption may pose challenges due to ethical or logistical constraints.

To address scenarios where the full coverage assumption might not hold, we could incorporate the principle of pessimism into our approach. This involves penalizing state-action pairs that are rarely visited under the offline distribution. The idea of incorporating pessimism has been widely used in the offline RL literature for MDPs. For example, a practical implementation of this idea can be adapted from [Zhan et al., 2022], where a regularity term is added to the objective function to measure the discrepancy between the policy of interest and the behavior policy. By identifying and estimating the gradient of this modified objective function, we could potentially provide an upper bound on suboptimality and maintain a similar theoretical result by only assuming partial coverage, i.e. $C_{\pi^b}^{\pi_{\theta^*}}:=\max_{t=1,..,T}(\mathbb E^{\pi^b}[(\frac{p_t^{\pi_{\theta^*}}(S_t,H_{t-1})}{p_t^{\pi^b}(S_t,H_{t-1})\pi^b_t(A_t\mid S_t)})^2])^{\frac{1}{2}}<\infty.$ This partial coverage assumption only needs that the offline distribution $\mathbb{P}^{\pi^b}$ can calibrate the distribution $\mathbb{P}^{\pi_{\theta^*}}$ induced by the in-class optimal policy, which is a milder condition compared to the full coverage assumption.

Regarding Optimal Policy Coverage (Assumption 5(a))

Thank you for your comment on this assumption. Inspired by [Liu et al.][Masiha et al.], we can relax this assumption by introducing a transferred compatible function approximation error in the following way:

$\varepsilon _{approx}:=\sup _{\theta \in \Theta} \sum _{t=1}^T\left(\mathbb{E}^{\pi _{\theta^*}}\left[\left(\mathbb{A} _t^{\pi _\theta}\left(A _t, O _t, S _t, H _{t-1}\right)-w _t^*(\theta)^{\top} \nabla _{\theta _t} \log \pi _{\theta _t}\left(A _t \mid O _t, H _{t-1}\right)\right)^2\right]\right)^{\frac{1}{2}},$ where $w _t^*(\theta)$ denotes the optimal solution of the following optimization problem for each $\theta$: $\arg\min _{w _t} \sum _{t=1}^T\left(\mathbb{E}^{\pi _{\theta}}\left[\left(\mathbb{A} _t^{\pi _\theta}\left(A _t, O _t, S _t, H _{t-1}\right)-w _t^{\top} \nabla _{\theta _t} \log \pi _{\theta _t}\left(A _t \mid O _t, H _{t-1}\right)\right)^2\right]\right)^{\frac{1}{2}}.$

Note that this notion is similar to the definition (Def. C.2 in Appendix C) in our original paper, which also quantifies the richness of the policy class. It tends to be small when the policy class is sufficiently rich. In such cases, the requirement for optimal policy coverage (Assumption 5(a)) becomes unnecessary. In the revised manuscript, we have introduced this transferred compatible approximation error in Definition D.2, deleted the original optimal policy coverage assumption, and updated the results & proof of Theorem 3.

We respectfully hope that we have addressed your concerns. If you have any further questions or require more information to raise your initial score, please feel free to let us know.

Reference:

1. Zhan W, Huang B, Huang A, et al. Offline reinforcement learning with realizability and single-policy concentrability[C]//Conference on Learning Theory. PMLR, 2022: 2730-2775.

2. Liu Y, Zhang K, Basar T, et al. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods[J]. Advances in Neural Information Processing Systems, 2020, 33: 7624-7636.

3. Masiha S, Salehkaleybar S, He N, et al. Stochastic second-order methods improve best-known sample complexity of sgd for gradient-dominated functions[J]. Advances in Neural Information Processing Systems, 2022, 35: 10862-10875.

Thanks for your positive feedback and the upgraded score. We are again grateful for your time and efforts to review our paper and give constructive comments!

We are grateful for your insightful comment and would like to address your concerns in this response.

While I typically do not complain about the empirical results of a theory paper, I do expect that the authors could show how to implement such estimation and algorithm on real practical RL problems.

We appreciate your feedback and understand the importance of practical implementation in reinforcing the applicability of our proposed estimation and algorithm. In response to your suggestion, we have added discussion about the practical implementation of the proposed algorithm on real-world RL problems in Appendix I.3 of the revised manuscript.

First of all, an exact implementation method has been provided in Appendix I.1 of the manuscript. Specifically, assuming all function classes are reproducing kernel Hilbert spaces (RKHSs), the min-max optimization problem (9) comprises a quadratic concave inner maximization problem and a quadratic convex outer minimization problem. Consequently, a closed-form solution can be computed, as demonstrated in Appendix I.1.

In practical implementations on real RL problems, the exact execution of the proposed algorithm may sometimes computationally costly. For instance, when dealing with large sample sizes or a high number of stages, solving the min-max optimization problem (9) precisely in each iteration may become computationally expensive. Particularly, exact solutions with RKHSs involve calculating the inverse of an $N\times N$ (which takes $O(N^3)$) and evaluating the empirical kernel matrix on the space of history (taking approximately $O(N^2 T)$). Additionally, when assuming other function classes for bridge functions and test functions, such as neural networks, achieving an exact solution for the min-max optimization problem (9) is not feasible.

To enhance computational efficiency and accommodate general function classes, an alternative approach is to compute the (stochastic) gradient of the empirical loss function in the min-max optimization problem (9) with respect to $b$ and $f$ respectively. Subsequently, updating $f$ and $b$ alternately using gradient ascent and gradient descent only once in each iteration can be performed. In this case, gradient estimation is expedited, contributing to faster computations. We acknowledge the need for further exploration to assess its efficacy in real-world applications, and we consider this an avenue for future research.

In the third paragraph of Section 3, does the definition of history $\mathcal{H}_t$ lack the subscript on $\mathcal{O}$ and $\mathcal{A}$?

Thank you for your question. We assume the observation space $\mathcal{O}$ and the action space $\mathcal{A}$ are the same for each stage $t=1,2,...,T$, eliminating the need for subscripts on $\mathcal{O}$ and $\mathcal{A}$. The space of history $\mathcal{H}_t$ can be conceptualized as a product space. One can generalize the setting by allowing $\mathcal{O}$ and $\mathcal{A}$ to be time-dependent.

The notation $Z_t$ has already been defined in Section 3; however, another $z$ is used in Section 5 as additional notation. Are they the same things?

Thank you for pointing this out. They are not the same thing, and we have corrected the notations in the revised manuscript. We now use $\mathcal E_t$ rather than $Z_t$ to denote the emission kernel in Section 3.

We hope that we have addressed your concerns, and welcome any questions or feedback you may have. If the rebuttal reflects a better alignment with your expectations for the paper, we kindly ask you to consider raising your rating.

Thank you for your constructive feedback. We appreciate the opportunity to address each of your concerns.

[Vlassis et. al., 2012] have proved that finding a stochastic controller of polynomial size that achieves a certain target, is an NP-hard problem. Optimizing policy for confounded POMDPs is even more challenging. While [Vlassis et al., 2012] does not directly contradict this paper, it does raise questions about the real-world applicability of the assumptions made herein.

Thank you for bringing attention to [Vlassis et al., 2012], which addresses the computational complexity of finding a stochastic controller of polynomial size in POMDPs. We appreciate your acknowledgement of the challenges associated with policy learning in POMDPs, as demonstrated by the NP-hardness results presented in [Burago et al., 1996] and [Vlassis et al., 2012]. It is important to note that our proposed method is designed as an approximate solution, specifically tailored to address a subclass of confounded POMDPs based on the assumptions outlined in our paper. By doing so, we navigate away from the NP-hard complexity, focusing on a more manageable problem class. In the following, we discuss the sources of "approximation" and the underlying assumptions.

• Policy parameterization. In our work, the policy is indexed by a finite-dimensional parameter, introducing an approximation by restricting the policy class. The transferred compatible function approximation error $\varepsilon_{approx}$, presented in Theorem 3, quantifies the richness of the policy space.

• Gradient ascent as an iterative method. Convergence to the optimal solution is not guaranteed due to the non-concave nature of the policy value function with respect to the policy parameter. To address this, we leverage the commonly-considered gradient dominance property in the field of non-convex/non-concave optimization. This property arises from a notion of function approximation for the advantage function $\varepsilon_{approx}$ and the positive definiteness of the Fisher information matrix (as per Assumption 5(b)). Up to a finite number of iterations, the output policy value can approximate the optimal policy value. The related assumptions are commonly used in the literature on policy gradient methods in MDPs.

• Policy gradient identification and estimation. The approximation in our method stems from two main components: identification and estimation. 1) In the identification part, we restrict to a subclass of POMDPs that satisfies Assumptions 1, 2, and 3 in Section 4. These assumptions ensure that historical information and observations carry sufficient information about the latent state at each stage (completeness from Assumptions 1, 3) and that we can effectively use this information (Assumptions 1, 2) to derive a solution from observational data. In the tabular setting, this subclass of POMDPs is akin to (actually more general than) the under-completeness POMDPs introduced in [Jin et al. 2020]. 2) In the estimation part, we utilize offline samples to estimate the policy gradient instead of exact computation. We introduce function classes with controlled complexity to allow the use of a polynomial number of samples for policy gradient estimation. This relies on Assumption 4 in Section 6.1. Given our consideration of non-parametric models, the associated assumptions are weak.

We plan to study the policy gradient methods under looser assumptions in future research. Nevertheless, the current paper is a first try to study policy gradient for confounded POMDPs under offline settings.

Is there a possibility to provide examples that provide lower bounds? [Agrawal et. al.] provided an example demonstrating the necessity of distribution mismatch coefficient (which I presume it isn't very difficult to have a similar one for POMDPs).

Thank you for your suggestion to provide examples illustrating lower bounds. We believe a similar sparse-reward example can be developed to illustrate the necessity of the distribution mismatch coefficient in our problem. However, since we consider history-dependent policy in the confounded POMDP, the derivation of the policy gradient is much more involved. Because of the limited time for the rebuttal, achieving this for POMDPs is a more intricate task. Nevertheless, we assure you that we will strive to include such an example in the future revision.

1. Burago D, De Rougemont M, Slissenko A. On the complexity of partially observed Markov decision processes[J]. Theoretical Computer Science, 1996, 157(2): 161-183.

2. Vlassis N, Littman M L, Barber D. On the computational complexity of stochastic controller optimization in POMDPs[J]. ACM Transactions on Computation Theory (TOCT), 2012, 4(4): 1-8.

3. Jin C, Kakade S, Krishnamurthy A, et al. Sample-efficient reinforcement learning of undercomplete pomdps[J]. Advances in Neural Information Processing Systems, 2020, 33: 18530-18539.