Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
48,175 characters · 11 sections · 23 citation commands
A Policy Gradient Method for Confounded POMDPs
Policy gradient methods in reinforcement learning (RL) have been extensively studied and utilized across many tasks due to their adaptability and straightforward implementation schemes sutton1999policy,kakade2001natural,silver2014deterministic. Despite its success in practice peters2006policy,peters2008reinforcement,yu2017seqgan,qiu2019deep,li2022continuous, most existing policy gradient methods were developed for the fully observable environment with Markovian transition dynamics, which may not known a priori. Little work has been done for the partially observable Markov decision processes (POMDPs), which is a more practical model for sequential decision making in many applications sawaki1978optimal,albright1979structural,monahan1982state,singh1994learning,jaakkola1994reinforcement,cassandra1998survey,young2013pomdp,zhang2016markov,bravo2019use. In this paper, we study policy gradient methods for finite-horizon and confounded POMDPs with continuous state and observation spaces under the offline setting. Compared to existing literature, we consider a more general setting where a flexible non-parametric model is used for the system dynamics of POMDPs, and the history-dependent policy class is indexed by a finite-dimensional parameter. We establish both statistical and computational convergence guarantees for the proposed policy gradient method in POMDPs under the offline setting.
There are several challenges for studying policy gradient methods in confounded POMDPs under the offline setting. First of all, in the offline data, the unobserved state variables at each decision point are unmeasured confounders that can simultaneously affect the action, the reward and the future transition. Directly implementing standard policy gradient methods can incur bias estimation, leading to suboptimal policies. Therefore identification is required for estimating the gradient of history-dependent policies using the offline data. Second, when the state and observation spaces are continuous, function approximation is inevitable for the gradient estimation. How to non-parametrically and consistently estimate the policy gradient in POMDPs remains unknown. Lastly, since the policy value to be optimized is a non-concave function with respect to the policy parameter, together with unobserved continuous states, a global convergence for finding the optimal policy in POMDPs is challenging. For example, the potentially misspecified policy class cannot ensure the improvement of the policy value by the estimated gradient towards optimality.
\noindentOur main contribution: We propose a policy gradient method in the offline setting for POMDPs under a non-parametric model with both statistical and computational guarantees. Specifically, we first establish a novel identification for directly estimating the gradient of any (history-dependent) policy using the offline data, circumventing the issue of partial observability. Based on the identification result, which leads to solving a sequence of conditional moment equations, we adopt the min-max estimating procedure to compute the policy gradient non-parametrically using the offline data. The estimated policy gradient is then incorporated into the gradient ascent algorithm for learning the optimal history-dependent policy. As for theoretical contribution, we investigate the statistical error for estimating the policy gradient at each step of our algorithm. In particular, we provide a non-asymptotic error bound for estimating the gradient uniformly over the policy class in terms of all key parameters. To establish the global (i.e., computational) convergence of our proposed algorithm, we study the landscape of the policy value in POMDPs, and leverage the compatible function approximation for proving the global convergence of the proposed policy learning algorithm. To the best of our knowledge, this is the first work studying policy gradient methods for POMDPs under the offline setting with a complete characterization of both statistical and computational errors.
\noindentPolicy gradient in MDPs and POMDPs. There are mainly two lines of research on policy gradient methods in Markov decision processes (MDPs). The first line focuses on off-policy policy gradient estimation williams1992simple,precup2000eligibility,degris2012off,silver2014deterministic,hanna2018towards,liu2019off,tosatto2020nonparametric,xu2020improved,kallus2020statistically,xu2021doubly,tosatto2021batch,ni2022optimal,tosatto2022temporal. The second line focuses on the convergence of gradient ascent methods wang2019neural,bhandari2019global,mei2020global,liu2020improved,zhang2020global,hambly2021policy,agarwal2021theory,xiao2022convergence. Little work has been done on the policy gradient in POMDPs. azizzadenesheli2018policy was among the first that studied a policy gradient method in POMDPs in the online setting, where the unobserved state at each decision point did not directly affect the action, and thus there was no confounding issue in their setting. As a result, the gradient can be estimated by generating trajectories from the underlying environment. In contrast, our work, which considers POMDPs in the offline setting, meets the significant challenge caused by the unobserved state, necessitating a more thorough analysis for identifying the policy gradient using the offline data. The presence of unobserved states also poses additional challenges in demonstrating the global convergence of policy gradient methods for learning the optimal history-dependent policy. A substantial analysis is required for controlling the error related to the growing dimension of the policy class in terms of the length of horizon.
\noindentConfounded POMDP. Employing proxy variables for identification in confounded POMDPs has attracted great attention in recent years. For example, the identification of policy value given a single policy has been investigated tennenholtz2020off,bennett2021proximal,nair2021spectral,shi2022minimax,miao2022off. However, these studies are unsuitable for policy learning because identifying all policy values within a large policy class to find the best one is computationally infeasible. Another line of research focuses on policy learning in confounded POMDPs guo2022provably,lu2022pessimism,wang2022blessing. Nevertheless, these works either lack computational algorithms guo2022provably,lu2022pessimism or necessitate a restrictive memorylessness assumption imposed on the unmeasured confounder wang2022blessing. In contrast to the aforementioned works, we directly identify the policy gradient rather than the policy value, enabling the construction of an efficient algorithm through gradient ascent update. Furthermore, the proposed policy iteration algorithm circumvents the restrictive memoryless assumption imposed on the unobserved state that is typically necessary for fitted-Q-type algorithms in POMDPs.
We consider a finite-horizon and episodic POMDP represented by \(\mathcal{M}:=(\mathcal{S}, \mathcal{O}, \mathcal{A}, T, \nu_1, \\\{P_t\}_{t=1}^T, \{\mathcal E_t\}_{t=1}^T, \{r_t\}_{t=1}^T)\), where $\mathcal{S}$, $\mathcal{O}$ and $\mathcal{A}$ denote the state space, the observation space, and the action space respectively. In this paper, both $\mathcal{S}$ and $\mathcal O$ are considered to be continuous, while $\mathcal A$ is finite. The integer $T$ is set as the total length of the horizon. We use $\nu_1 \in \Delta(\mathcal{S})$ to denote the distribution of the initial state, where $\Delta(\mathcal{S})$ is a class of all probability distributions over $\mathcal{S}$. Denote $\{P_t\}_{t=1}^T$ to be the collection of state transition kernels over $\mathcal{S}\times\mathcal{A}$ to $ \mathcal{S}$, and $\{\mathcal{E}_t\}_{t=1}^T$ to be the collection of observation emission kernels over $\mathcal{S}$ to $\mathcal{O}$. Lastly, $\{r_t\}_{t=1}^T$ denotes the collection of reward functions, i.e., $r_t:\mathcal{S}\times\mathcal{A}\to [-1, 1]$ at each decision point $t$. In a POMDP, given the current (hidden) state $S_t$ at each decision point $t$, an observation $O_t\sim \mathcal{E}_t(\cdot\mid S_t)$ is observed. Then the agent selects an action $A_t$, and receives a reward $R_t$ with $\mathbb{E}[R_t\mid S_t=s,A_t=a]=r_t(s,a)$ for every $(s, a)$. The system then transits to the next state $S_{t+1}$ according to the transition kernel $P_t(\cdot\mid S_t,A_t)$. The corresponding directed acyclic graph (DAG) is depicted in Figure (ref). Different from MDP, the state variable $S_t$ cannot be observed in the POMDP.
In this paper, we focus on finding an optimal history-dependent policy for POMDPs. Let $H_t:=(O_1, A_1,...,O_t, A_t)\in \mathcal{H}_t$, where $\mathcal{H}_t:=\prod_{j=1}^t \mathcal{O}\times\mathcal{A}$ denotes the space of observable history up to time $t$. Then at each $t$, the history-dependent policy $\pi_t$ is defined as a function mapping from $\mathcal{O}\times \mathcal{H}_{t-1}$ to $\Delta(\mathcal{A})$. Given such a policy $\pi = \{\pi_t\}_{t = 1}^T$, the corresponding value is defined as \[\mathcal{V}(\pi):=\mathbb{E}^{\pi}[\sum_{t=1}^T R_t\mid S_1\sim\nu_1],\] where $\mathbb{E}^{\pi}$ is taken with respect to the distribution induced by the policy $\pi$. We aim to develop a policy gradient method in the offline setting to find an optimal policy $\pi^*$ defined as, \[\pi^* \in \arg\max_{\pi \in \Pi} \mathcal{V}(\pi),\] where $\Pi$ is a pre-specified class of all history-dependent policies. To achieve this goal, for each decision point $t$, we consider a pre-specified class $\Pi_{\Theta_t}$ to model $\pi^\ast_t$. A generic element of $\Pi_{\Theta_t}$ is denoted by $\pi_{\theta_t}$, where $\theta_t\in \Theta_t\subset\mathbb{R}^{d_{\Theta_t}}$. The overall policy class is then represented by $\Pi_\Theta = \bigotimes_{t = 1}^T \Pi_{\Theta_t}$. Let $\theta:=vec(\theta_1,\theta_2,...,\theta_T)\in\Theta\subset \mathbb{R}^{d_{\Theta}}$ be the concatenation of the policy parameters in each step, where $d_\Theta=\sum_{t=1}^T d_{\Theta_t}$. Similarly, we denote $\pi_\theta = \{\pi_{\theta_t}\}_{t=1}^T \in\Pi_\Theta$.
In the offline setting, an agent cannot interact with the environment but only has access to an offline dataset generated by some behavior policy $\{\pi^b_t\}_{t=1}^T$. We assume that the behavior policy depends on the unobserved state $S_t$, i.e., $\pi_t^b: \mathcal{S}\to \Delta(\mathcal{A})$ for each $t$. We use $\mathbb{P}^{\pi^b}$ to denote the offline data distribution and summarize the data as $\mathcal{D}:=(o_t^n,a_t^n,r_t^n)^{n=1:N}_{t=1:T}$, which are $N$ i.i.d. copies from $\mathbb{P}^{\pi^b}$.
To find an optimal policy $\pi^\ast$ using the offline data, the policy gradient $\nabla_\theta \mathcal{V}(\pi_\theta)=\nabla_\theta \mathbb{E}^{\pi_\theta}[\sum_{t=1}^T R_t\mid S_1\sim \nu_1]$ needs to be computed/estimated as an ascent direction when one is searching over the policy parameter space $\Theta$. In the vanilla policy gradient method, one can approximate the optimal policy $\pi^\ast$ via updating the policy parameter $\theta$ iteratively for finitely many times, i.e., at $(k+1)$-th step, we can obtain $\theta^{(k+1)}$ via
where $\eta_k $ is a pre-specified stepsize. To implement the update rule ((ref)), there are two main issues in our problem: (1) estimation of the policy gradient $\nabla_\theta \mathcal{V}(\pi_\theta)$ based on the offline dataset $\mathcal{D}$ with function approximations and (2) the global convergence of the policy gradient method in POMDPs. The challenge of Problem (1) lies in that the state variable $S_t$ is not observed and the policy gradient may not be identified by the offline data. Furthermore, function approximations are needed when both state and observation spaces are continuous. The challenge of Problem (2){ originates from the non-concavity of $\mathcal{V}(\pi_\theta)$, which requires an in-depth analysis of the underlying POMDP structure. Additionally, the limited capacity of the policy class complicates the global convergence of gradient ascent methods when state and observation spaces are continuous.} In the following sections, we provide a solution to address these two issues and derive a non-asymptotic upper bound on the suboptimality gap of the output policy given by our algorithm.
{\bf Notations}. Throughout this paper, we assume that $\mathbb{E}$ is taken with respect to the offline distribution, and $\mathbb{E}^{\pi_\theta}$ is taken with respect to distributions induced by $\pi_\theta$. Similarly, we use the notation $X\perp \!\!\! \perp Y\mid Z$ when $X$ and $Y$ are conditionally independent given $Z$ under the offline distribution. For any two sequences $\{a_n\}_{n=1}^\infty$, $\{b_n\}_{n=1}^\infty$, $a_n\lesssim b_n$ denotes $a_n\le C b_n$ for some $N,C>0$ and every $n>N$. If $a_n\lesssim b_n$ and $b_n\lesssim a_n$, then $a_n\asymp b_n$. Big $O$ and $O_P$ are used as conventions. For any policy $\pi$ that depends on the observed data, the suboptimality gap is defined as \[\operatorname{SubOpt}(\pi):=\mathcal{V}(\pi^{\star})-\mathcal{V}(\pi).\]
Since the state variable $S_t$ is unobserved in POMDPs, standard off-policy gradient estimation methods developed in MDPs kallus2020statistically are no longer applicable. As seen from Figure (ref), $S_t$ can be regarded as a time-varying unmeasured confounder as it simultaneously confounds the action $A_t$, the outcome $R_t$ and the future state $S_{t+1}$ in the offline data. Therefore ignoring the effect of $S_t$ will lead to a biased estimation of the policy gradient. To elaborate, we take a partially observable contextual bandit as a simple example. Under some direct calculations, we can show that $\nabla_\theta \mathcal{V}({\pi_\theta}) = \mathbb{E}_{S_1\sim\nu_1}[\sum_a \mathbb{E}[ R_1\nabla_{\theta_1}\pi_{\theta_1}(a\mid O_1)\mid S_1, A_1 =a]]$, which implies that any vanilla estimation procedures based on this equation are not suitable because $S_1$ is not observable - the observable triple $(A_1,O_1,R_1)$ alone is not enough to estimate $\nabla_\theta \mathcal{V}({\pi_\theta})$. One may also think of ignoring $S_1$ and simply applying any standard off-policy gradient estimation method developed in MDPs by treating $O_1$ as the state. However, it can be seen that this naive method will incur a non-negligible bias due to $\mathbb E[R_1\mid S_1,O_1, A_1=a]\neq \mathbb E[R_1\mid O_1, A_1=a]$ in general. The failure of the naive method is also demonstrated through a simulation study of a toy example (see Appendix (ref)). It can be seen that the naive estimator cannot converge to the true policy gradient no matter how large the sample size would be. In contrast, the proposed estimator (introduced later) is consistent.
In the following, we present a novel identification for addressing the issue of partial observability in POMDPs. Specifically, we develop a non-parametric identification result for estimating $\nabla_\theta \mathcal{V}(\pi_\theta)$ via solving a series of conditional moment equations by using the observed data generated by the behavior policy. Such non-parametric identification results will allow general function approximations for estimating the policy gradient, which is inevitable when state and observation spaces are continuous.
To begin with, we assume the availability of some baseline covariates, represented by $O_0$, that carry some information before the decision-making process. The initial data for all individuals can be recorded as $\{o_0^n\}_{n=1}^N$. To enable the observable trajectory $\{O_t\}_{t=0}^T$ for identifying the policy gradient, we impose Assumption (ref) in the following.
{Assumption (ref) basically requires $O_0$ is pre-collected before the decision process, which is mild. Next, we rely on the existence of certain bridge functions that link the policy gradient and the offline data distribution, which are summarized in the following assumption.
We refer to $\{b^{\pi_\theta}_{V,t}\}_{t=1}^T$ as value bridge functions, and $\{b^{\pi_\theta}_{\nabla V,t}\}_{t=1}^T$ as gradient bridge functions. Intuitively, the value bridge functions and gradient bridge functions can be understood as bridges that link the value functions as well as their gradients for $\pi_\theta$ with the offline distribution induced by $\pi^b$ in POMDPs. Under some mild regularity conditions stated in Appendix (ref), one can ensure that Assumption (ref) always holds. The usage of such bridge functions for identification was first introduced in the field of proximal causal inference miao2018confounding,tchetgen2020introduction, and has been investigated in off-policy evaluation for confounded POMDPs bennett2021proximal,shi2022minimax,miao2022off.\ Here we generalize the idea along with the following completeness assumption for identifying the policy gradient.
Assumption (ref) is imposed to identify the policy gradient by using the observable $\{O_0, H_{t-1}\}$ instead of unobservable $S_t$. There are many commonly-used models such as exponential families newey2003instrumental and location-scale families hu2018nonparametric that can ensure the completeness stated in Assumption (ref). The completeness assumption is also widely made in identification problems when there exists unmeasured confounding darolles2011nonparametric,miao2018confounding.
Intuitively, the combination of Assumption (ref) and (ref) implies that for each action, the confounding effect of the unobservable state $S_t$ on the bridge function matches the confounding effect of the unobservable state $S_t$ on the outcome of interest, i.e., gradients of future cummulative rewards. Hence the bridge function can be used as a good "substitute". In addition, the bridge function can correct the bias because it is conditionally independent of $A_t$ given $S_t$, which allows us to identify the policy value and policy gradient. Finally, under Assumptions (ref)-(ref), we obtain the key identification result summarized in Theorem (ref).
{
}
According to ((ref)) and conditional moment restrictions ((ref)) and ((ref)), the policy gradient can then be estimated from the offline dataset $\mathcal{D}$. This is due to the fact that both bridge functions and conditional moment restrictions rely solely on the observed data. In Appendix (ref), we use a generic partially observable discrete contextual bandit to illustrate the idea of Theorem (ref). This example shows that the policy gradient can be explicitly identified as a form of matrix multiplications using observed variables. In Appendix (ref), we conduct a simulation study under a partially observable discrete contextual bandit to demonstrate the effectiveness of the proposed identification results.
In the subsequent section, we present a min-max estimation method based on ((ref)-(ref)) utilizing the offline dataset $\mathcal{D}$ when state and observation space is continuous and $T>1$, and describe a policy gradient ascent algorithm grounded in the estimated policy gradient.
In this section, we estimate $\nabla_\theta \mathcal{V}(\pi_\theta)$ based on offline data $\mathcal{D}=\{o_0^n,(o_t^n,a_t^n,r_t^n)_{t=1}^T\}_{n=1}^N$ and then use a gradient ascent method with the estimated $\nabla_\theta \mathcal{V}(\pi_\theta)$ for policy optimization. For the sake of clarity, we introduce some additional variables used in Sections (ref) and (ref). Let $\mathcal{Z}_t:=\mathcal{O}\times[-1,1]\times\mathcal{A}\times \mathcal{O}\times\mathcal{H}_{t-1}$, $\mathcal{X}_t:=\mathcal{A}\times\mathcal{H}_{t-1}\times\mathcal{O}$ and $\mathcal{W}_t:=\mathcal{A}\times\mathcal{O}\times\mathcal{H}_{t-1}$. Then we define three variables $Z_t\in\mathcal{Z}_t$, $X_t\in\mathcal{X}_t$, $W_t\in\mathcal{W}_t$ as $Z_t:=(O_{t+1},R_t, A_t,O_t,H_{t-1})$, $X_t:=(A_t,H_{t-1},O_0)$ and $W_t:=(A_t,O_t,H_{t-1})$.
\noindentConditional moment restrictions. By Theorem (ref), for each $\pi_\theta\in \Pi_\Theta$, to estimate the policy gradient, it suffices to solve a sequence of conditional moment restrictions:
Equations ((ref)) and ((ref)) form a sequential nonparametric instrumental variables (NPIV) problem, where $Z_t$ can be regarded as an endogenous variable and $X_t$ as an instrumental variable. Let $b_t:=(b_{\nabla V,t}^\top,b_{ V,t})^\top: \mathcal{W}_t\to \mathbb{R}^{d_\Theta+1}$ for each $t$. Define $m(Z_t;b_{t},b_{t+1},\theta_t):=(m_{\nabla V}(Z_t;b_{\nabla V,t},b_{V,t+1},b_{\nabla V,t+1},\theta_t)^\top,m_{ V}(Z_t;b_{ V,t},b_{V,t+1},\theta_t))^\top:\mathcal{Z}_t\to \mathbb{R}^{d_\Theta+1}$. Consequently, solving ((ref)) and ((ref)) is equivalent to solving
Therefore, for any measurable $f: \mathcal{X}_t\to \mathbb R^{d_\Theta+1}$, it holds that $\mathbb{E}[m(Z_t;b_{t},b_{t+1},\theta_t)^\top f(X_t)]=0, \forall t=1,...,T.$ In this way, we are able to use the unconditional expectations rather than the conditional one ((ref)). Since the moment restriction holds for infinitely many unconstrained $f(\cdot)$'s, a min-max strategy with some pre-specified function classes can be employed to find a solution.
\noindentMin-max estimation procedure. Motivated by the above discussion, to solve ((ref)), we sequentially adopt the min-max estimator from dikkala2020minimax that permits non-parametric function approximation such as Reproducing Kernel Hilbert Space (RKHS), random forests, and Neural Networks (NN). In particular, let $\widehat{b}_{T+1}^{\pi_\theta}=0$, we can estimate $b_{t}^{\pi_\theta}$ sequentially for $t=T,...,1$ by solving
where \(\Psi_{t,N}(b, f,\widehat{b}_{t+1}^{\pi_\theta},\pi_\theta):=\frac{1}{N}\sum_{n=1}^N m(Z_t;b,\widehat{b}_{t+1}^{\pi_\theta},\theta_t)^{\top} f(X_{t}^n)\), the spaces $\mathcal{B}^{(t)}=\{b: \mathcal{W}_t\to \mathbb{R}^{d_\Theta+1}\mid b_{j}=0,\forall 1\le j\le \sum_{i=1}^{t-1} d_{\Theta_{i}}\}$ are used for modeling the bridge function, and the spaces of the test functions \(\mathcal{F}^{(t)}:=\{f: \mathcal{X}_t \rightarrow \mathbb{R}^{d_\Theta+1} \mid \quad f_j \in \mathcal{F}^{(t)}_j\text{ with } f_{j}=0,\forall 1\le j\le \sum_{i=1}^{t-1} d_{\Theta_{i}}\}\). In particular, $\mathcal{F}^{(t)}_j=\{f_j: \mathcal{X}_t\to \mathbb{R}\}, j=1,....,d_\Theta+1$ are some user-defined function spaces such as RKHS. $\|f\|_{N,2,2}^2$ is the empirical $\mathcal{L}^2$ norm defined as $\|f\|_{N,2,2}:=(\frac{1}{N}\sum_{n=1}^N\|f(x_t^n)\|_{\ell^2}^2)^{1 / 2}$, and $\|b\|^2_{\mathcal{B}^{(t)}}$, $\|f\|^2_{\mathcal{F}^{(t)}}$ denote the functional norm (see Definition (ref)) of $b$, $f$ associated with $\mathcal{B}^{(t)}$, $\mathcal{F}^{(t)}$ respectively. Moreover, $\Psi_{t,N}(b, f,\widehat{b}_{t+1}^{\pi_\theta},\pi_\theta)$, can be understood as an empirical loss function measuring the violation of ((ref)). Finally, $\lambda_N$, $\mu_N$, $\xi_N$ are all tuning parameters. It is worth noting that at each iteration $t$, the first $(t-1)$ blocks of the solution $b_t^{\pi_\theta}$ to ((ref)) are all zero according to the conditional moment restriction ((ref)). Thus this restriction is also necessary to impose when constructing the bridge function class $\mathcal{B}^{(t)}$ and the test function class $\mathcal{F}^{(t)}$ as described above.
\noindentPolicy gradient estimation. After solving ((ref)) for $T$ times, we obtain $\widehat{b}_1^{\pi_\theta}$ and estimate the policy gradient $\nabla_\theta \mathcal{V}(\pi_\theta)$ by a plug-in estimator
where $\widehat{b}_{1,1:d_\Theta}^{\pi_\theta}$ is formed by the first $d_\Theta$ elements of the vector $\widehat{b}_1^{\pi_\theta}$. The numerical results of an instantiation can be found in Appendix (ref).
Policy optimization. With the estimated policy gradient, we can develop a policy gradient ascent algorithm for learning an optimal policy, i.e., iteratively updating the policy parameter $\theta$ via the rule \[\theta^{(k+1)}=\theta^{(k)}+\eta_k \widehat{\nabla_{\theta^{(k)}} \mathcal{V}(\pi_{\theta^{(k)}})}.\] Algorithm (ref) summarizes the proposed policy gradient ascent algorithm for POMDP in offline RL. More details can be found in Appendix (ref). Specifically, assuming all function classes are reproducing kernel Hilbert spaces (RKHSs), the min-max optimization problem ((ref)) in step 5 leads to a quadratic concave inner maximization problem and a quadratic convex outer minimization problem. Consequently, a closed-form solution of ((ref)) can be obtained, as demonstrated in Appendix H. Furthermore, we can show that the computational time of Algorithm (ref) is of the order $Kd_\Theta N^2 T\max\{T,N\}$, where $K$ is the number of iterations. The details of the derivation can be found in Appendix (ref).
This section studies theoretical performance of the proposed algorithm in finding $\pi^\ast$. We show that, given the output $\widehat{\pi}$ from Algorithm (ref), under proper assumptions, the suboptimality $\operatorname{SubOpt}(\widehat{\pi})=\mathcal{V}(\pi^*)-\mathcal{V}(\widehat{\pi})$ converges to $0$ as the sample size $N\to\infty$ and the number of iterations $K\to\infty$. In particular, we provide a non-asymptotic upper bound on the suboptimality $\operatorname{SubOpt}(\widehat{\pi})$ that depends on $N$ and $K$. The suboptimality consists of two terms: the statistical error for estimating the policy gradient at each iteration and the optimization error for implementing the gradient ascent algorithm.
To begin with, we impose the following assumption for analyzing the statistical error.
Assumption (ref)(a) is a commonly-made full coverage assumption in offline RL chen2019information,xie2020q. It essentially requires that the offline distribution $\mathbb{P}^{\pi^b}$ can calibrate the distribution $\mathbb{P}^{\pi_\theta}$ induced by $\pi_\theta$ for all $\theta$. See Appendix (ref) for more discussions on Assumption (ref)(a). Assumption (ref)(b) requires that $\mathcal{B}^{(t)}$ is sufficiently large such that there is no model misspecification error when solving the conditional moment restriction ((ref)). It is often called Bellman closedness in the MDP setting xie2021bellman. Assumption (ref)(c) requires that the testing function classes $\{\mathcal{F}^{(t)}\}_{t=1}^T$ are large enough to capture the projection of $m(Z_t;b_{t},b_{t+1},\theta_t)$ onto the space $\mathcal{X}_t$. Under this assumption, solving the min-max ((ref)) is equivalent to minimizing $\mathcal{L}^2(\ell^2,\mathbb{P}^{\pi^b})$-norm (see Definition (ref)) of $\mathbb{E}[m(Z_t;b_{t},\widehat{b}^{\pi_\theta}_{t+1},\theta_t)\mid X_t]$, which provides the projected residual mean squared error (RMSE) of the min-max estimator $\widehat{b}_t^{\pi_\theta}$ returned by ((ref)). See dikkala2020minimax for more details. Assumptions (ref)(d)-(e) are two mild technical conditions, which can be easily satisfied.
Next, we present the finite-sample error bound on the statistical error for policy gradient uniformly over all $\theta\in\Theta$. {All required lemmas and a complete proof are provided in Appendix (ref).}
As seen from Theorem (ref), the estimation error achieves an optimal statistical convergence rate in the sense that $\sup_{\theta\in\Theta}\|\nabla_\theta\mathcal{V}(\pi_\theta)-\widehat{\nabla_\theta\mathcal{V}(\pi_\theta)}\|_{\ell^2}=O_P(1/ \sqrt{N})$. The ill-posedness measure $\tau_{\max}$ quantifies how hard to obtain RMSE from the projected RMSE of $\widehat{b}_{t}^{\pi_\theta}$. It is commonly used in the literature of conditional moment restrictions (e.g., chen2012estimation). The term $d_\Theta$ comes from the dimension of the target parameter (i.e., policy gradient) and a need for an upper bound uniformly over $\theta\in \Theta$. The upper bound $\mathcal{M}_\mathcal{B}$ can be understood as the size of gradient that scales with $T^2$ as discussed in Appendix (ref). The term $\gamma(\mathcal{F},\mathcal{B})$ can be quantified by VC-dimension or metric entropy of the user-defined function classes. For example, when $\{\mathcal{F}^{(t)}_j\}_{j=1,t=1}^{d_\Theta+1,T}$, $\{\mathcal{B}_j^{(t)}\}_{j=1,t=1}^{d_\Theta+1,T}$ are all linear function classes. i.e. $\mathcal{B}_j^{(t)}=\{\phi_{j,t}(\cdot)^T \omega:\omega\in\mathbb R^d\}$ and $\mathcal{F}_j^{(t)}=\{\psi_{j,t}(\cdot)^T \omega:\omega\in\mathbb R^d\}$, then $\gamma(\mathcal{B},\mathcal{F})\asymp d$. When $\{\mathcal{F}^{(t)}_j\}_{j=1,t=1}^{d_\Theta+1,T}$, $\{\mathcal{B}_j^{(t)}\}_{j=1,t=1}^{d_\Theta+1,T}$ are all general RKHS, then $\gamma(\mathcal{F},\mathcal{B})$ is quantified by the speed of eigen-decay for RKHS. More results for $\gamma(\mathcal{F},\mathcal{B})$ are provided in Appendix (ref).
We then investigate the computational error of the proposed algorithm and establish a non-asymptotic upper bound on the suboptimality of $\widehat{\pi}$. Firstly, we present the following assumption.
Assumption (ref)(a) is satisfied by a wide range of policy classes. For example, the well-known log-linear policy classes satisfy Assumption (ref)(a) (see remark 6.7 of agarwal2021theory). The positive definiteness of $F_t(\theta)$ in Assumption (ref)(b) is also commonly used in the literature related to the (natural) policy gradient methods. See Appendix (ref) for more discussion. Assumption (ref)(c) is satisfied if Assumption (ref)(e) holds in our setting. Indeed, $L$ scales with $T^4$ in the POMDP setting. {See Appendix (ref) for further discussion.}
Next, we provide a non-asymptotic upper bound for $\operatorname{SubOpt}(\widehat{\pi})$ in terms of all key parameters.
According to Theorem (ref), we have an upper bound on the suboptimality gap in terms of statistical error, optimization error and an approximation error. As we can see, $\operatorname{SubOpt}(\widehat{\pi})=O_P(\frac{1}{\sqrt{N}}+\frac{1}{\sqrt{K}})+ \varepsilon_{approx}$, which matches the existing result in MDPs (Theorem 3 of xu2021doubly). In Appendix (ref), we further discuss how finding a history-dependent optimal policy in our confounded POMDP setting affects the suboptimality and computational time of the proposed algorithm compared with that in the standard MDP setting.
We evaluate the performance of Algorithm (ref) by conducting a simulation study using RKHS endowed with a Gaussian kernel. Details of of the simulation setup can be found in Appendix (ref). Figure (ref) summarizes the performance of three methods: the proposed method, the naive method and behavioral cloning. According to Figure (ref), the proposed method can find the in-class optimal policy, since the proposed policy gradient estimation procedure has uniformly good performance over the policy class. Consequently, at each iteration, the proposed policy gradient estimator can be sufficiently close to the true policy gradient and find the correct update direction in the optimization step. In contrast, the naive method cannot achieve the in-class optimal policy no matter how large the number $K$ of iterations is, because there exists an irreducible bias in the policy gradient estimation at each iteration. Furthermore, the performance of behavior cloning is significantly worse than the proposed algorithm, since the behavior cloning only clones the behavior policy that generates data instead of finding the optimal actions. This demonstrates the superior performance of our method in finding an optimal policy in the confounded POMDP.
In this paper, we propose the first policy gradient method for POMDPs in the offline setting. Under some technical conditions, we establish a non-asymptotic upper bound on suboptimality, which is polynomial in all key parameters. There are several promising directions for future research. For example, it will be interesting to study if our suboptimality bound is minimax optimal and explore more efficient algorithms under the current setting. In addition, by leveraging the idea of pessimism, one may develop an algorithm by only requiring the partial coverage, relaxing Assumption (ref)(a). Lastly, applying the proposed algorithm in practical RL problems with unobserved state variables could be intriguing.
\addcontentsline{toc}{section}{Appendix}