A Policy Gradient Method for Confounded POMDPs
Authors: Mao Hong
Zhengling Qi
Yanxun Xu
Venue: ICLR 2024 poster (2024)
Keywords: Offline Reinforcement Learning
Confounded POMDP
Policy Gradient
Statistical Guarantee
Function Approximation
Primary area: learning theory
TL;DR: We propose a policy gradient method for Confounded POMDPs with theoretical guarantees.

Abstract: In this paper, we propose a policy gradient method for confounded partially observable Markov decision processes (POMDPs) with continuous state and observation spaces in the offline setting. We first establish a novel identification result to non-parametrically estimate any history-dependent policy gradient under POMDPs using the offline data. The identification enables us to solve a sequence of conditional moment restrictions and adopt the min-max learning procedure with general function approximation for estimating the policy gradient. We then provide a finite-sample non-asymptotic bound for estimating the gradient uniformly over a pre-specified policy class in terms of the sample size, length of horizon, concentratability coefficient and the measure of ill-posedness in solving the conditional moment restrictions. Lastly, by deploying the proposed gradient estimation in the gradient ascent algorithm, we show the global convergence of the proposed algorithm in finding the history-dependent optimal policy under some technical conditions. To the best of our knowledge, this is the first work studying the policy gradient method for POMDPs under the offline setting.

Published as a conference paper at ICLR 2024
A POLICY GRADIENT METHOD FOR CONFOUNDED POMDPS
Mao Hong
Zhengling Qi George Washington University q weehenglinggee edu
Yanxun Xu
Johns Hopkins University mhong2 6 jhu. edu
Johns Hopkins University yanxun xuê juu edu
ABSTRACT
In this paper, we propose a policy gradient method for confounded partially ob- servable Markov decision processes (POMDPs) with continuous state and obser- vation spaces in the offline setting. We first establish a novel identification re- sult to pon-parametrically estimate any history-dependent policy gradient under POMDPs using the offline data. The identification enables us to solve sequence of conditional moment restrictions and adopt the min-max learning procedure with general function approximation for estimating the policy gradient. We then pro- vide saitl non-asymptotic bound for estimating the gradient uniformly over a pre-specified policy class in terms of the sample size, length of horizon, concentratability coefficient and the measure of ill-posedness in solving the condi- tional moment restrictions. Lastly, by deploying the proposed gradient estimation in the gradient ascent algorithm, we show the global convergence of the proposed algorithm in finding the history-dependent optimal policy under some technical conditions. To the best of our knowledge, this the first work studying the policy gradient method for POMDPs under the offline setting.
INTRODUCTION
Policy gradient methods in reinforcement learning (RL) have been extensively studied and utilized across many tasks due to their adaptability and straightforward implementation schemes (Sutton et al.
1999 1999|99aaaa Kakade 2001, Silver et al. 2014). Despite its success in practice (Peters & Schaal 2006]]
2008 Yu et al.) 2017
al. 2019 et al. 2022), most existing policy gradient methods were
developed for the fully observable environment with Markovian transition dynamics, which may not known priori. Little work has been done for the partially observable Markov decision processes (POMDPs), which is more practical model for sequential decision making in many applications
(Sawaki & Ichikawal 1978 Albright 1979 Monahan 1982. Singh et al. 1994 Jaakkola al. 1994
Cassandra 1998 Young et al. [013 Zhang & Bareinboim 2016 Bravo et al. 2019). 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 more general setting where a flexible non-parametric model used for the system dynamics of POMDPs, and the history-dependent policy class is indexed by finte-dimeensionl 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 simultancously affect the action, the reward and the future tran- sition. 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 contin- uous, function approximation is inevitable for the gradient estimation. How to non non-paramettically 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, global convergence for finding the optimal policy in POMDPs is
"Corresponding author.

---

Published as a conference paper at ICLR 2024
challenging. For example, the potentially misspecified policy class cannot ensure the improvement of the policy value by the estimated gradient towards optimality.
Our main contribution: We propose policy gradient method in the offline setting for POMDPs under a non-parametric model with both statistical and computational guarantees. Specifically, we first establish novel identification for directly estimating the gradient of any thistory-dependder policy using the offline data, circumventing the issue of partial observability. Based on the identifi- cation 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 then incorporated into the gradient ascent algorithm for learning the optimal iistory-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 algo- rithm, 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.
RELATED WORK
Policy 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 (Williams) 1992, Precup
2000
Degris et al. 2012; Silver et al. 2014; Hanna & Stone,
2018 Liu et al.] 2019 Tosatto al.
2020
Xu et al. 2020 Kallus & Uehara [2020] [uu al. | 1021
Tosatto et al. 2021 Ni et al. 2022 Tosatto et al. 2022). The second line focuses on the convergence
of gradient ascent methods (Wang et al. 2019
Bhandari & Russo 2019; Mei et al., 2020 Liu al.,
2020 (Zhang et al. 2220;; Hambly et al. [202]] Agarwal et al.
[022) Little work has
al.j (2018) 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 result, the gradient can be estimated by generating trajectories from the under- lying environment. In contrast, our work, which considers POMDPs the offline setting, meets the significant challenge caused by the unobserved state, necessitating 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 learn- ing 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.
been done on the policy gradient in POMDPs. Azizzadenesheli
Confounded 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 sin- gle policy has been investigated (Tennenholtz et al.] 2020 Bennett & Kallus) 2021] Nair & Jiang. 2021 Shi et al., 2022 Miao et al. 2022). However, these studies are unsuitable for policy learning because identilying all policy values within a large policy class to find the best one is computation- ally infeasible. Another line of research focuses on policy learning in confounded POMDPs (Guo)
et al. 2022 Lu et al. 2022. Wang et al. 2022). Nevertheless, these works either lack computational algorithms Guo et al.] 2022; Lu et al.
2022 or necessitate a restrictive memorylessness assump-
tion imposed on the unmeasured confounder (Wang et al. 2022). In contrast to the aforementioned works, we directly identify the policy gradient rather than the policy value, enabling the construction of 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- -ttpee algorithms in POMDPs.
3 PRELIMINARIES AND NOTATIONS
We consider finite-horizon and episodic POMDP represented by M: OS, (P.)T-1. (E, (r.)T=.) where S, and A denote the state space, the observation space, and the action space respectively. In this paper, both S and O are considered to be continuous, while A is finite.
2

---

Published as a conference paper at ICLR 2024
The integer T is set as the total length of the horizon. We use 11 E A(S) to denote the distribution of the initial state, where A(S) is a class of all probability distributions over S. Denote {Pi to be the collection of state transition kernels over S A to S, and {E to be the collection of observation emission kernels over S to O. Lastly, {re} denotes the collection of reward functions, i.e., ry S x A [-1,1] 1] each decision point t. In POMDP, given the current (hidden) state St at each decision point é, an observation O ~ E S() is observed. Then the agent selects an action A,, and receives a reward Rt with R[ | S; = 5, A, = aj rr(ss, a) for every (s, a). The system then transits to the next state S1+1 according to the transition kernel Pt(- St,AA) At). The corresponding directed acyclic graph (DAG) is depicted in Figure [I Different from MDP, the state variable S, cannot be observed in the POMDP.
In this paper, we focus on finding an optimal history (O1, AI.... O,, At) Hs, where H4 := [T O A denotes the space of observable history up to time t. Then each t. the
policy for POMDPs. Let H, ==
policy मe is defined as a function mapping from O x H4-1 to (AA). Given such a policy π = = the corresponding value is defined as
T
(TT) = E
Re SS m1],
where E is taken with respect to the distribution induced by the policy æ. We aim develop policy gradient method in the offline setting to find an optimal policy x defined as, π arg max V(T)..
where ll 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 Iee, to model क.. A generic element of Il,, is denoted by Te,, where 0, O, C Rdo, The overall policy class is then represented by He Ø'=1 Te, Let == vec(O1, (0,, 02, ..., 0r) E C Rdde be the concatenation of the policy parameters in each step, where de = Σ de, Similarly, we denote Tо = { } E Ile.
T
In the offline setting, an agent cannot interact with the environment but only has access to an offline dataset generated by some behavior policy {T²]T= We assume that the behavior policy depends on the unobserved state S,, i.e., o. S - A(A) for each L. We use pa to denote the offline data distribution and summarize the data as D == (o,, al, r7 pny-=1:N which are N i..dd. copies from pa'
To find an optimal policy x² using the offline data, the policy gradient VoV(TO) VoE E Re SS ~ v1] needs to be computed/estimated as an ascent direction when one is searching over the policy parameter space Ô. In the vanilla policy gradient method, one can approx- imate the optimal policy T via updating the policy parameter iteratively for finitely many times, i... at (k+ + 1)-th step. we can obtain g(+++1 via
g(k-1) g(k) + me VoV((T))o=pcc))
where Te is a pre-specified stepsize. To implement the update rule (T). there are two main issues in our problem: (1) estimation of the policy gradient (oV( based the offline dataset D with function approximations and (2) the global convergence of the policy gradient method in POMDPs. The challenge of Problem (I) lies in that the state variable S, 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 Problem (2) originates from the non-concavity of (TT)) 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.
Notations. Throughout this paper, we assume that E is taken with respect to the offline distribution, and E is taken with respect to distributions induced by ng. Similarly, we use the notation X JLL Y Z when X and Y are conditionally independent given Z under the offline distribution. For any two sequences {a,, ) == [6, On < bn, denotes an < C6, for some N, C' >> 0 and every n > N. If a, & bn and bn S an, then Gn x bn- Big O and Op are used as conventions. For any policy π that depends on the observed data, the suboptimality gap is defined as SubOpt(T) == V(=*) - (TT).
3

---

Published as a conference paper at ICLR 2024
Figure I: The directed acyclic graph of the data generating process POMDPs, where states St not observed. Green arrows indicate the generation of actions via the behavior policy, while red arrows indicate the generation through a history-dependent policy.
POLICY GRADIENT IDENTIFICATION
Since the state variable S, is unobserved in POMDPs, standard off-policy gradient estimation meth- ods developed in MDPs (Kallus & Uchara 2020) are no longer applicable. As seen from Figure I St can be regarded as a time-varying unmeasured confounder as it simultaneously confounds the action A, the outcome R, and the future state S1+1 in the offline data. Therefore ignoring the ef- fect of St will lead biased estimation of the policy gradient. To elaborate, we take a partially observable contextual bandit as simple example. Under some direct calculations, we can show that VoV( = ~v, 1/,, E|R V Ve,Te, Te, (a O1) SI, Ai = al]. which implies that any vanilla estimation procedures based on this equation are not suitable because Si is not observable the observable triple (A1, O1, R1) alone not enough to estimate VgV( One may also think of ignoring S1 and simply applying any standard off off-policy gradient estimation method developed in MDPs by treating O₂ as the state. However, it can be seen that this naive method will incur a non- negligible bias due to [ O1, A naive method also demonstrated through a simulation study of a toy example (see Appendix KK). 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.
F [R[, 01, A1 a] in general. The failure of the
In the following, we present a novel identification for addressing the issue of partial observability in POMDPs. Specifically, we develop non-parametric identification result for estimating VaV(ma) via solving series of conditional moment equations by using the observed data generated by the behavior policy. Such non- parametreeic identification results will allow general function approxima- tions 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 Oo, that carry some information before the decision-making process. The initial data for all individuals can be recorded as {oß N m==1- To enable the observable trajectory {Ot) for identifying the policy gradient, impose Assumption in the following.
Assumption 1. Under the offline distribution Ip=", holds that
Oo 1L (O,, O..1, Sc, Ar, HL-1, =t= L,.,, T.
(2)
basically requires Ou 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.
Assumption I
Assumption 2 (Existence of V-bridge and VV-bridge functions). For any Fe E lll there exist real-valued bridge functions {677 Ax x O x H,-1 + RJ and valtor bridge functions (DTVV. E A O x H4- - dR T that satisfy the following conditional moment restrictions:
Blb (A,, O,, H.-1) 1) A,, H. Opl (R, (A, Oz, H.-1)
+ Σ
bie (a', Oc+1: H1) To. (A, Or, H,-1) | Ag, H;-1, (3)
a'EAA
4

---

Published as a conference paper at ICLR 2024
E Oz, H1-1)) H,-1, Ool -E((R, "iietzla'' Oc+1, Otm1 H.)) vva+ila ( (4 Ho, (As O2 He-1) A,, H, Ool.
(4)
no. (Al Oz, H1-1) +
Σ b
where D and bTe VV,T+1 are set to be 0.
We refer to (f value bridge functions, and (i I itively, the value bridge functions and gradient bridge functions can be understood as bridges that link the value functions as well as their gradients for ze with the offline distribution induced by T in POMDPs. Under some mild regularity conditions stated in Appendix B one can ensure that Assumption always holds. The usage of such bridge functions for identification was first intro- duced in the field of proximal causal inference (Miao al. 2018 Tchetgen et al.) 2020), and has been investigated in off-policy evaluation for confounded POMDPs (Bennett & Kallus [202] Shi al.) 2022; Miao al. 2022). Here generalize the idea along with the following completeness assumption for identifying the policy gradient.
gradient bridge functions. Intu-
Assumption (Completeness). For any measurable function 9r : S x A x H4-1 + R, and any T,
Elg Sr Ar, H(-1) A,, H,,1, = 0
almost surely if and only if (S,, A,, H;-1) almost surely.
Assumption 3 is imposed to identify the policy gradient by using the observable {Oo. H instead of unobservable St. There many commonly-used models such exponential families (Newey & Powell 2003) and location-scale families (Hu & Shiu 2018) that can ensure the completeness stated in Assuupptoo 3 The completeness assumption is also widely made in identification problems when
there exists unmeasured confounding (Darolles et al. 2011 Miao et al. 2018).
Intuitively, the combination of Assumption 2 and implies that for each action, the confounding effect of the unobservable state S. on the bridge function matches the confounding effect of the unobservable state S₂ on the outcome of interest, i.e., gradients of future cummulative rewards. Hence the bridge function can be used as good "substitute". In addition, the bridge function can correct the bias because identify the policy value and policy gradient. Finally, under Assumptions identification result summarized in [
conditionally independent of A, given S,, which allows us to
we obtain the key
Theorem (Policy gradient identification). Under Assumptions 7 for any To E lll, the policy gradient and policy value for To can be identified as
VoV(To) = E Σ b (a, O1)] and V(TO)) = EE| by (a, O1)].
(5)
a
aEA
According to (5) and conditional moment restrictions 3 and 4 the policy gradient can then be
estimated from the offline dataset D. This is due the fact that both bridge functions and conditional moment restrictions rely solely on the observed data. In Appendix [B.6] we use generic partially observable discrete contextual bandit to illustrate the idea of Theorem This example shows that the policy gradient can be explicitly identified as form of matrix muliplications using observed variables. In Appendix K 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 3 utilizing the offline dataset 'D when state and observation space is continuous and T > 1, and describe policy gradient ascent algorithm grounded in the estimated policy gradient.
POLICY GRADIENT ESTIMATION AND OPTIMIZATION
In this section, we estimate V (T)()))) based on offline data D = for: (of af r [T= 1N and then gradient ascent method with the estimated V& VTV())) for policy optimization. For the sake of clarity, we introduce some additional variables used in Sections 5 and 6 Let Z, == O x [-1, 1] x
A x O H4-1, X, == A H O and W, A O x H Then define three variables
5

---

Published as a conference paper at ICLR 2024
Z Z₁, X2 E Nr We E We as Z = 10,41,R,44 A,, Or, H1-1), X (A,, HL,, Ou) and We == (A,,O, H(-1).
Conditional moment restrictions. By Theorem ! for each To E Ill. to estimate the policy gradi- ent, it suffices to solve a sequence of conditional moment restrictions:
Blmv bv,,, bv, 0₂) Xx] 0, and.
(6)
E|mer (Z bVV,a, bV.c+1, bVVa++1 0,) Xx] = 0, Vt L,,..., T, where
m-(-) = bv:e (A,, Ot, H2-1) (Re +
Σ
br,etila', O++1, H.)) (Ae O,, Hr-1),
d'EA
(.) = boV, - (Re + Σ bv. H.), - Σ bevitiild Oct1, Ho)Te.
d'EA
a'EA
Equations 66 and 7 form a sequential nonparametric instrumental variables (NPIV) prob- lem, where Z, can be regarded as an endogenous variable and X, as instrumental vari- W, + Rdo+1 for each t. Define m (Z b,, bet1, 0.) = (Zz:bvy.. bv,,e, 0e)T, my (n;(Zz;; b,)),, Zt - Rdo+1, Consequently, solving and is equivalent to solving
able. Let b2 = bv.e)
B[m(( (4; by, bet1, 01) X,] = = 1,.,.
(8)
Therefore, for any measurable ʃ X4 + Rdo+1, it holds that E[m(Ze by, b,,,, s(x)) = 0, 0, 1, ..... T. In this way, we are able to use the unconditional expectations rather than the conditional one (8). Since the moment restriction holds for infinitely many unconstrained (('ss, a min-max strategy with some pre-specified function classes can be employed to find a solution.
Min-max estimation procedure. Motivated by the above discussion, to solve ( we sequen- tially adopt the min-max estimator from Dikkala et al. (020) that permits non- non-parametric function approximation such as Reproducing Kernel Hilbert Space (RKHS), random forests, and Neural Net- works (NN). In particular, let 6741 = O. we can estimate 6, sequentially for t = T, by solving
6 arg min sup (b. f, BEB()) FEF()
B B mo) AN AN + MN | EN
where Me,N (b, f, 1 no) == N DN m(Zii b, bif (6) the spaces B {b : W, Id bj = 0, v1 S - Ei=l ] are used for modeling the bridge function, and the spaces
of the test functions F()) = (ʃ : X, + +d +1 S3 F with fj = 0, S E de. In partieular, F/11 [/ X. - RJ = 1, ..... de 1 are some user-defined function spaces such as RKHS. 2, is the empirical L norm defined as | ( Σm (I ) and [|61| |l.11 denote the functional norm (see Definition D.3 of 6, f associated with B(t), (()) respectively. Moreover, Vr.N(b, (b. J, b.f1: can be understood as an empirical loss function measuring the violation of (8) Finally, AN. JUN, EN are all tuning parameters. It is worth noting that at each iteration f, the first (t 1) blocks of the solution 6,' to (8) are all zero according to the conditional moment restriction 4 Thus this restriction is also necessary to impose when constructing the bridge function class B and the test function class fi()) as described above.
Policy gradient estimation. After solving gradient VoV()))) by a plug-in estimator
9 for T times, we obtain 8T and estimate the policy
N Σ
VOV(TO)
1
8
b (a, o')],
(10)
N
aEA
where D b7,i is formed by the first de elements of the vector iyo. The numerical results of an instantiation can be found in Appendix L
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 0 via the rule
@(++1) ((k) + 1/k V (g0)) (F

---

Published as a conference paper at ICLR 2024
Algorithm I summarizes the proposed policy gradient ascent algorithm for POMDP in offline RL. More details can be found in Appendix [.] Specifically, assuming all function classes are re- producing kernel Hilbert spaces (RKHSs), the min-max optimization problem (9) in step 5 leads to a quadratic concave inner maximization problem and a quadratic convex outer minimization problem. Consequently, closed-form solution of (9) can be obtained, demonstrated in Ap- pendix H. Furthermore, we can show that the computational time of Algorithm [ is of the order N max(T, NJ where K is the number of iterations. The details of the derivation can be found in Appendix .2
Algorithm Policy gradient ascent for POMDP in offline RL
Input: Dataset D, step sizes [ K-1 function classes [T= (F
1: Initialization: ((U) IRdo
2: for k from 0 to K 1 do
< 3: Initialization: Let by+1 = R
4: for from T to 1 do
5: Solve the optimization problem (9 by plugging in 0,41 To0n for 0g (7(0))
6: end for
7: Let 6 (a 11,1 be the vector formed by the first de elements of D7 (
8: Compute VO(H) V(TT())) Em= oy (a, of and update.
9: Update 1( g(h) + 176 V VO(N) (TTg(a)).
10: end for
Output: के Unil(( Ii-1: to Y I (igk-n)==11
6 THEORETICAL RESULTS
This section studies theoretical performance of the proposed algorithm in finding x². We show that, given the output from Algorithm [. under proper assumptions, the suboptimality SubOpt(R) V(TT) (RR) converges to 0 as the sample size N + oo and the number of iterations K + co. In particular, we provide a non-ase non-asymptottc upper bound on the suboptimality SubOpt(R) 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.
6.1 STATISTICAL ERROR FOR POLICY GRADIENT
To begin with, impose the following assumption for analyzing the statistical error. Assumption 4. The following conditions hold.
(a) (Full coverage). Cz. := supege max 1 (E 1T (S.,H())
)21) < oo where
pt" (8., 1..H--1371 (73 (A.S.)
Pe ())) denotes the density function of the marginal distribution of (Se, Hi-1) following x. [B())==) For any
(b) (Richness of
1.., T, E O and b E B0+1), there exists be E B(t) depending on by41 and such that the conditional moment equation (8) is satisfied.
(c) (Richness of F (F))) IT.)) For any t =,..., T. E O, b BB+++ b. B(,, we have
Elmml Ze; be, by41, 0.) X.) E (()) For any f E F(t), we have rf E FF) Vr 1-
TE and (F(1)TT There exist constants Mg and My such that for any 1...., T, supo, E, be(a, oe he11le S MB for every b, E B(t), and
(d) (Uniform boundness of (B(
that sup,, (z < My for every f F(t).
(e) There exists a constant < oo such that supr,e
|| log Te, (at ot, (o,hh--))les 1)lle= G.
Assumption is commonly-made made full coverage assumption in offline RL (Chen Jiang 2019
Xie & Jiang 2020). It essentially requires that the offline distribution pa can calibrate the distri- bution ins induced by тe for all 0. See Appendix B.4 for more discussions on Assumption aa) Assumption 4bb) requires that B(t) is sufficiently large such that there is no model misspecification error when solving the conditional moment restriction (8). It is often called Bellman closedness in the MDP setting (Xie et al., 202T). Assumption 4 requires that the testing function classes

---

all linear Published as a conference paper at ICLR 2024
(F(() are large enough capture the projection of m bt, b2+1.01) onto the space &z Un- der this assumption, solving the min-max (9) is equivalent minimizing L (2 IP )-norm (see Definition D.4 of Elmm(Ze Ze; be, b,41, 0t) Xe). which provides the projected residual mean squared
error (RMSE) of the min-max estimator 8,"0 returned by (9). See Dikkala et al. (2020) for more details. Assumptions 4 de)((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 A E O All required lemmas and complete proof are provided in Appendix F
Theorem 2 (Policy gradient estimation error). Under Assumptions for some constant C1 > 0,
with probability at least 1 Ç it holds that
sup (VoV(TT)TT)) - VoV(To)lle M log(eiT/(n(F.B) AE
MrMrdey
(11)
N
where Tmax is measure of ill-posednness (See Definition D.I and (F, B) measures the complexity of user-defined bridge function classes and test function classes and is independent of de, N.
As seen from Theorem 2 the estimation error achieves an optimal statistical convergence rate in OP(1/VN), The ill-posedness measure Tmax
the sense that suppee ((Te) VoV(TT))le quantifies how hard to obtain RMSE from the projected RMSE of b It is commonly used in the literature of conditional moment restrictions (c.g.. Chen & Pouzo (0022). The term de comes from the dimension of the target parameter (i.e., policy gradient) and a need for an upper bound uniformly over 0 O. The upper bound Ms can be understood the size of gradient that scales with T as discussed in Appendix B The term y(F, B) can be quantified by VC-dimension or metric entropy
of the user-defined function classes. For example, when (F(()) do 1,T
1= (8(4) 5=11== 11-- 1,T
function classes. i.e. B () : w Rd) and f/ (B, F) d. When (-,") 1
(.).))) w w E Rd), then (. (8 10 J==1,t=1 are all general RKHS, then (F, B) is quantified
by the speed of eigen-decay for RKHS, More results for (FF B) are provided in Appendix
6.2 SUBOPTIMALITY
We then investigate the computational error of the proposed algorithm and establish non- asymptotic upper bound on the suboptimality of न. Firstly, we present the following assumption.
Assumption 5. The following conditions hold. (a) (B-smoothness)) For 1 < t < T and any a₂ A, E E 10,hi-1 E H4-1, there exists a constant
s. log Ta, (at | Ot, hz-1) - Vo, log Te: (at Ot, 11-1))le= S 3 - 01 (b) (Positive definiteness of Fisher information matrix). For each t = 1, ..., T and any 0 E O, let To, (A, Or, H111) then the matrix F((0)
> O, such that &,
F,(0) : =E 9, log ne, (A, O,, O,,H),,V log To,
μ.. Iás, is positive semidefinite for some positive constant μ.
(c) (L-smoothnesss) (TTT) is L-smooth with respect to 0 per Definition D.6 in Appendix D
Assumption ((a) is satisfied by a wide range of policy classes. For example, the well-known log- linear policy classes satisfy Assumption 5 a)) (see remark 6.7 of[Agarwal et al. (202T). The positive
definiteness of Fi( in Assumption 5 b) is also commonly used in the literature related to the (natural) policy gradient methods. See Appendix [B.] for more discussion. Assumption [cc is satisfied if Assumption 4[e) holds in our setting. Indeed, L scales with T in the POMDP setting.
See Appendix B for further discussion.
Next, we provide a non-asymptotic upper bound for SubOpt(F) in terms of all key parameters.
Theorem 3 (Suboptimality). Under Assumptions we have
S with probability at least 1 - C, for some e > 0,
+ /)vde VK
(1 + T O+, T5. do log(cT/()
V(To-)-
05k5K-1 V(TTOO)) S
max
T
+
N
optinization erior
statistical
8

---

Published as a conference paper at ICLR 2024
+ (1 ! VK T2 F de $ log (gg(c//)
+ + Capproz:
(12)
N
componond error between statistical and optimization errurs
where Capprox is defined in Definition D.2 in Appendix D which is used to measure the expressive power of policy class in finding the optimal policy. In particular, when K x N, we have
SubOpt = 0p((1 + 1 max 7 225 log(
1 + +1+
1 dde p4.5) + E Eapproz. 1 VK
VN
According to Theorem 3 we have upper bound the suboptimality gap in terms of sta- tistical error, optimization error and an approximation error. As we can see, SubOpt(ã) = Op( VK Eapproz, which matches the existing result in MDPs (Theorem 3 of Xu et al. 2021 ) In Appendix [B.7 we further discuss how finding history-dependent optimal policy in our confounded POMDP setting affects the suboptimality and computational time of the proposed algorithm compared with that the standard MDP setting.
NUMERICAL RESULTS
We evaluate the performance of Algorithm [ by conducting simulation study using RKHS en- dowed with a Gaussian kernel. Details of of the simulation setup can be found in Appendix L Figure summarizes the performance of three methods: the proposed method, the naive method and behavioral cloning. According to Figure 2 the proposed method can find the in-class optimal policy, since the proposed policy gradient estimation procedure has uniformly good performance the policy class. Consequently, at each iteration, the proposed policy gradient estimator be sufficienlly 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 matter how large the number K of iterations is, because there exists an irreducible bias in the policy gradient estimation 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.
Performance
05
6.6
Gradin
Grsbal optina vake wing aaoa tehenerdansg
20 rect cites proppese mothce
-62
15
05
Beriton
Figure 2: Policy values versus iterations under different methods.
DISCUSSION AND LIMITATIONS
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 suboptimality, which is polynomial all key parameters. There are several promising directions for future research. For example, it will be interesting 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, may develop algorithm by only requiring the partial coverage. relaxing Assumption 4a).. Lastly, applying the proposed algorithm in practical RL problems with unobserved state variables could be intriguing.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors wish thank anonymous reviewers for their feedback on an early version of this paper. The work of Xu was supported by NSF 1918854, NSF 1940107, and NIH ROIMH1
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431-453 4456,, 2021.
S Christian Albright. Structural results for partially observable markov decision processes. Opera- tions Research, 2765):044-11053, 1979.
Kamyar Avizzadenesheli, Yisong Yue, and Animashree Anandkumar. Policy gradient in partially observable environments: Approximation and convergence. arXiv preprint arXiv:/8/0.0111 18/0.07900, 2018.
Andrew Bennett and Nathan Kallus. Proximal reinforcement learning: Efficient off-po evalua- tion in partially observed markov decision processes. arXiv preprint arXiv:2110.15332 2021.
Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint 1X06:v990.0/7000 2019.
Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor- critic algorithms. Automatica, 45(11):2411-2482, 2009.
Raissa Zurli Bittencourt Bravo, Adriana Leiras. and Fernando Luiz Cyrino Oliveira. The use of uav s in humanitarian relief: an application of pomdp-based methodology for finding victims. Production and Operations Management, 28(2):421-440, 2019.
Marine Carrasco, Jean-Pierre Florens, and Eric Renault. Linear inverse problems in structural econo- metrics estimation based on spectral decomposition and regularization. Handbook of economet- rics, 6:5633-5751, 2007.
Anthony Cassandra. survey of pomdp applications. Working notes of AAAI 1998 sympo- sium on planning with parlially observable Markov decision processes, volume 1724, 1998.
Jinglin Chen and Nan Jiang. Information-theoreti considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Xiaohong Chen and Demian Pouzo. Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals. Econometrica, 80(1):277-321, 2012.
Serge Darolles, Yanqin Fan, Jean-Pierre Florens, and Eric Renault. Nonparametric instrumental regression. Econometrica,
2011.
Thomas Degris, Martha White, and Richard S Sutton. Off-policy actor-critic. arXiv: 4839, 2012.
arXiv preprint
Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation of con- ditional moment models. Advances in Neural Information Processing Systems, 33: 1111222822266 2020.
Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global optimum convergence of momentum- based policy gradient. In International Conference on Artificial Intelligence and Statistics, pp- 1910-1934. PMLR, 2022.
llyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for fisher-non-degenerate policies. arXiv preprint arXiv:2302.017344 2023.
Dylan J Foster and Vasilis Syrgkanis.
Orthogonal statistical learning. arXiv preprint
arXiv: 10X000900000006 2019.
10

---

Published as a conference paper at ICLR 2024
Hongyi Guo, Qi Cai, Yufeng Zhang. Zhuoran Yang, and Zhaoran Wang. Provably efficient of- fline reinforcement learning for partially observable markov decision processes. In International Conference on Machine Learning, pp. 8016-8038. PMLR, 2022.
Ben Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods for the noisy linear quadratic regulator over a finite horizon. SIAM Journal on Control and Optimization, (9(5):3359-339) 2021.
Josiah P Hanna and Peter Stone. Towards data efficient off-poliey policy gradient. In AAAI Spring Symposia, 2018.
Yingyao Hu and Ji-Liang Shiu. Nonparametric identification using instrumental variables: sufficient conditions for completeness. Econometric Theory, 34(3):659-693, 2018.
Tommi Jaakkola, Satinder Singh, and Michael Jordan. Reinforcement learning algorithm for par- tially observable markov decision problems. Advances in neural information processing systems, 7, 1994.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Nathan Kallus and Masatoshi Uchara. Statistically efficient off-policy policy gradients. In Interna- fional Conference on Machine Learning, pp. 5089-5100. PMLR, 2020.
Rainer Kress, V Maz'ya ya, and V Kozlov. Linear integral equations, volume 82. Springer, 1989.
Guofa Li, Shenglong Li, Shen Li, and Xingda Qu. Continuous decision-making for autonomous driving at intersections using deep deterministic policy gradient. IET Intelligent Transport Sys- tems, 16(12):1669 1681, 2022.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced)) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624-7636, 2020.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off Off-policy policy gradient with state distribution correction. arXiv preprint (XXiv:190.008777 2019.
Miao Lu, Yifei Min, Zhaoran Wang, and Zhuoran Yang. Pessimism in the face of confounders: Prov- ably efficient offline reinforcement learning in partially observable markov decision processes. arXiv preprint 1rXXi:2205.13550 2022.
Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, and Patrick Thiran. Stochas- tic second-order methods provably beat sgd for gradient-dominatd functions. arXiv preprint arXiv:2205. 12856, 2022.
Andreas Maurer. vector-contraction incquality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, 2016. Proceedings 27, pp. 3-17. Springer, 2016.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference Machine Learning, pp- 6820-6829. PMLR, 2020.
Rui Miao, Zhengling Qi, and Xiaoke Zhang. Off-policy evaluation for episodic partially observ- able markov decision processes under non-parametric models. arXiv preprint arXiv:2209. 10064, 2022.
Wang Miao, Xu Shi, and Eric Tchetgen Tchetgen. A confounding bridge approach for double negative control inference causal effects. arXiv preprint 1808 04945. 2018.
George E Monahan. State of the art-a survey of partially observable markov decision processes: theory, models, and algorithms. Management science, 28(1):1-16, 1982.
Yash Nair and Nan Jiang. A spectral approach to off-policy evaluation for pomdps. arXiv preprint arXiv:2109, 10502, 2021.
11

---

Published as a conference paper at ICLR 2024
Whitney K Newey and James L Powell. Instrumental variable estimation of nonparametric models. Econometrica, 7 71(5):1565-15777 2003.
Chengzhuo Ni, Ruiqi Zhang, Xiang Ji, Xuezhou Zhang, and Mengdi Wang. Optimal estimation of policy gradient via double fitted iteration. International Conference on Machine Learning, pp- 16724-16783. PMLR, 2022.
Jan Peters and Stefan Schaal. Policy gradient methods for roboties. 2006 JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2011222122222 2225. IEEE, 2006.
Jan Peters and Stefan Schaal. Natural actor-critie. Neurocomputing, 71(7-9): 1190, 2008a.
Jan Peters and Stefan Schaal. Reinforcement learning of motor skills with policy gradients. Neural networks, (44):682-697,22 2008b.
Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000.
Chengrun Qiu, Yang Hu, Yan Chen, and Bing Zeng. Deep deterministic policy gradient (ddpg)- based energy harvesting wireless communications. IEEE Internet of Things Journal, 6(5):8577- 8588, 2019.
2019.
Katsushige Sawaki and Akira Ichikawa. Optimal control for partially observable markov decision processes over an infinite horizon. Journal of the Operations Research Society of Japan, 21(1): 1-16, 1978.
Chengehun Shi. Masatoshi Uehara, Jiawei Huang, and Nan Jiang. A minimax learning approach to off-policy evaluation confounded partially observable markov decision processes. Interna- tional Conference on Machine Learning, pp. 20057-20094. PMLR, 2022.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pp- 387-395, Pmlr, 2014.
Satinder P Singh, Tommi Jaakkola, and Michael I Jordan. Learning without state-estimation in partially observable markovian decision processes. In Machine Learning Proceedings 1994, pp- 284-292 Elsevier, 1994.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Eric Tchetgen Tchetgen, Andrew Ying, Yifan Cui. Xu Shi. and Wang Miao. An introduction to proximal causal learning. arXiv preprint arXiv:2009.10982 2020.
Guy Tennenholtz, Uri Shalit, and Shie Mannor. Off-policy evaluation in partially observable en- vironments. In Proceedings of the AAAI Conference on Artificial Intelligecee volume 34, pp- 10276-10283, 2020.
Samuele Tosatto, Joao Carvalho, Hany Abdulsamad, and Jan Peters. nonparametric off-policy policy gradient. In International Conference Artificial Intelligence and Statistics, pp. 167- 177. PMLR, 2020.
Samuele Tosatto, Joao Carvalho, and Jan Peters. Batch reinforcement learning with nonparametric off-policy policy gradient. IEEE Transactions on Puttern Analysis and Machine Intelligence, 44 (10):5996-6010) 66000, 2021.
Samuele Tosatto, Andrew Patterson, Martha White, and Rupam Mahmood. A temporal-difference approach to policy gradient estimation. In International Conference on Machine Learning, pp- 21609-21632. PMLR. 2022.
Martin Wainwright. High- digle-diimssionall statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
12

---

Published as a conference paper at ICLR 2024
Jiayi Wang, Zhengling Qi, and Chengchun Shi. Blessing from experts: Super reinforcement learning in confounded environments. arXiv preprint arXiv:2209.15448, 2022.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909, 01 150, 2019.
Ronald Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Reinforcement learning, pp. 5-32, 1992.
Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-36, 2022.
Tengyang Xie and Nan Jiang. Q approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pp. 550-559. PMLR, 2020.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consiste pessimism for offline reinforcement learning. Advances neural information processing systems, 34:6683-6694, 2021.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In Uncertainty in Artificial Intelligence, pp. 541-551. PMLR, 2020.
Tengyu Xu, Zhuoran Yang, Zhaoran Wang, and Yingbin Liang, Doubly robust off-policy actor-critic: Convergence and optimality. International Conference on Machine Learning, pp. 11581- 11591. PMLR, 2021.
Steve Young, Milica Gasic, Blaise Thomson, and Jason D Williams. Pomdp-basee statistical spoken dialog systems: A review. Proceedings of the IEEE, 101-5):160-1119, 2013.
Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu. Seggan: Sequence generative adversarial nets with policy gradient. In Proceedings of the AAAI conference artificial intelligence, volume 31, 2017.
Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. International Conference on Artificial Intelligence and Statistics, pp- 3332-3380. PMLR, 2022.
Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic meth- ods for offline reinforcement learning. Advances in neural information processing systems, 34: 13626-13640, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pp. 2730-2775. PMLR, 2022.
Junzhe Zhang and Elias Bareinboim. Markov decision processes with unobserved confounders: A causal approach. Technical report, Technical report, Technical Report R R-23, Purdue AI Lab, 2016.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6); 3586-3612, 2020.
13

---

Published as a conference paper at ICLR 2024
CONTENTS
Introduction
2
Related work
Preliminaries and notations
Policy gradient identification
Policy gradient estimation and optimization
6
Theoretical results
Statistical enror for policy gradient
6.2
Suboptimality
7
Numerical results
8
Discussion and limitations
List of notations
16
Further discussions
17
B. Existence of bridge functions
17
B.2
Scale of Mg.
18
B 3
Scale of L
19
Assumption
19
B.5
Assumption
20
B.6
An explicit form of the identification result for tabular cases
20
B.7
Increased complexity due to history-dependent policies in POMDPs
21
Further results related to Theorem
21
Definitions and auxiliary lemmas
22
Proofs for policy gradient identifications
24
Proofs for policy gradient estimations
28
Decomposition error
28
F2
Bounds for the decomposition
35
One-step estimation)
38
Bounds for critical radius and one-step errors
47
F4.
VC Classes
47
R4.2
RKHSS
49
14

---

Published as a conference paper at ICLR 2024
F.5
Policy gradient estimation errors
51
Proofs for suboptimality
51
G.1 An auxiliary proposition with oracle policy gradients
52
G.2 Proof of suboptimality
55
Proofs for lemmas
60
Proof of Lemma
60
2
Proof of Lemmal
61
Proof of Lemma
61
4
Proof of Lemma
62
H.5
Proof of Lemma
63
H.6 6 Proof of Lemma
66
Proof of Lemma
70
Implementation
71
Implementation details using RKHS
71
I.2
Computational complexity of Algorithm using RKHS
72
1.3
More discussions on practical implementations
73
Simulation details
73
Additional numerical results for tabular cases
74
Additional numerical results for continuous cases
74
15

---

Published as a conference paper at ICLR 2024
A
LIST OF NOTATIONS
Table 1: List of notations
Notations
Descriptions
M T St e
an episodic POMDP
length of horizon
unobserved state at stage t and state space
O₂ E
observed variable at stage and space of observation
A E
action at stage and discrete action space distribution of the initial state
[Pa)
collection of state transition kernels over S x A to S collection of observation emission kernels over S to collection of reward functions, i.e. Fr 8 A 1- history (O1, A1, Oz) a destory-epeedeett policy the behaviour policy
{ri
Hi
π IT TEl TO, IT de To
parameterized policy
dimension of policy parameter space expectation w.r.t. the distribution induced by any policy π
E
E ((T) D
expectation taken w.r.t. offline distribution
policy value of ı defined as E" D R4 S1
v1]
offline data {oj (o of 1=1/==1
X LL Y L zz
X and Y are conditionally independent given
TT bv:
true and estimated value-bridge functions at true and estimated gradient-briee functions at t an element in the value-bridge function class an element in the gradient- brrige function class concatenation of bvv, and by; an element in the test function class moment function defined in (8)
v bavv
bv.
bov
be
f
Z
argument of m, defined as (O++1, Re, Ar, O2, H(-1) argument of by, defined as (Ae, O,, H,-1) argument of f, defined as (Ae, Ht-1, Oo) the bridge function class the test function class
W,
X,
BiO
F())
2
population C noorm, defined as (E (Ex=pad ((X)
1/2
|/
empirical L norm, defined as ( E |I (am)
1/2
function norm associated with 8(9)
If rl
function norm associated with F(A)
VEN
empirical loss function (9)
VoV (me) ((k)
estimated policy gradient of 0
the policy parameter at the k: - th iteration in gradient ascent
step size gradient ascent
the output policy
AN. uN. En C. Tmax MR. My (F, B)
tunning parameters in 9
concentratability coefficient defined in Assumption 4 a measure of ill-posedness defined in D.I
the upper bounds for bridge & test function classes (Assumption 4 a complexity measure of bridge & test function classes the smallest eigenvalue of Fisher information matrix (Assumption 5
μ K
number of iterations in gradient ascent transferred compatible function approximation error (Definition D.2
Eapprox
16

---

Published as a conference paper at ICLR 2024
B FURTHER DISCUSSIONS
B.1 EXISTENCE OF BRIDGE FUNCTIONS
In this section, discuss sufficient conditions for Assumption 2 Assumption 2 is about the cxis- tence of solutions to a sequence of linear integral equations. A rigorous study on this problem is to utilize tools from singular value decomposition in functional analysis (Kress et al. 1989). Specifi- cally, we present the following result from Kress et al. (189)..
Lemma 1 (Theorem 15.16 in Kress et al. (1899). ). Given Hilbert spaces H1 and H2, compact operator K H1 m> H2 and its adjoint operator K* : H2 ++ H,, there exists singular system (Ans Pnr vn) t of with nonzero singular values {An} and orthogonal sequences {Gn E H1}
and (th H2] such that
= -x Km = >nnPn-
Lemma 2 (Thearem 15.18 in Kress et al. (1989). Given Hilbert spaces Hi and H2, compact operator K Hy + H2 and its adjoint operator K" H2 + Hi, there exists singular sys- tem (Av, Ov, b/))y== of K, with singular values { and orthogonal sequences {ov} C H1 and {ve}} C H2 such that Ká,, Vo and K Ov. Given 9 H2, the Fredholm integral equation of the first kind Kh = is solvable if and only if
(a) g Ker (K*) and
(b) Ev= XT2 1,2KK Kg vuyi²²
< do where Ker (K*) = : = 0} is the null space of K*, and
denotes the orthogonal complement to a set.
We then present the following sufficient conditions for the existence of bridge functions.
For probability measure function μa, let L {u(x)) denote the space of all squared integrable func- tions of & with respect to measure p(x), which is a Hilbert space endowed with the inner product (g1 + 92) 91 (1)))))())))((1) For all de; h4-1, L, define the following operator
ia LL (Ho,la, (or I at, he-1)} L {HoolA AA, , ae, h1-1)}
h + E (h (Ot, Ae, H(-1) Oo ou, A, at, Hi-1 h2-1).
and its adjoint operator
K hee 1it
.2 (OolA (0o a 11-1)) + L (1o, H. (or Oe; 1
g E (g (O,, A, at, H:-1) O: o1; At 0t, Hi-1 h4-13
Assumption (Completeness). For any measuruble function gt : O x Hi-1 - and any
TT
E [g. (Oo, As, H(-1) Or, Ar, H[-1] = 0 almost surely if and only if g: (Oo, Ar, H1-1) = O almost surely.
Assumption (Regularities Assumptions). For any O, = On O2 = 01, A₁ = 02 H h1-1 and
st (a) Sooxo H., op, at, b1-1)fo.00 H, (oo | az hew dz < oo, where
fo.1On.A..H and Ao. are conditional density functions.
(b) For any uniformly bounded 91 92, 9s O x H4 R, A θ
[ E (RR, + (Or+1, (1))) (Ae Or, 11-1) Oo = on, Ar = des H:-1 = 1311
(13)
SoulAr (00 at, h 00.
and
| TE (E 92 H.) (A, Oc, H.-1)) + ga H,) (Ai Oi, H,-1)
Ou 0. as, He- h,-1 - fool AcHH, (ou at, hi-1)dou 0o, each i 1, 1,... de
(c) There exists singular decomposition (Ney 1stw: Por he isti Vaa. ( ==1 of Karch 1:t such that for all uniformly bounded 91, 92, 9s : O x H. + R, E e
2 he- 1 pla |TB (RR + 91 (Ot+1, HO)) (Az Oz, H,,
(14)
Op = op, A = at, H 1 = 11-1) Vi 1:51)) 00.
17

---

Published as a conference paper at ICLR 2024
and
Maih 13: KIE + 92 (0++1, (Ae Oz, H2-1)) + 02 HT)
(Ae Or, H2-1) 1) Oo 00. Ar = 0t, H,-1 he- 1) Varke mwl) < oc, for each i 1, de.
Next, we prove that completeness (Assumption 6 and regularities (Assumption 7 are sufficient conditions for the existence of bridge functions that satisfy Assumption 2
Proof. For = T, ...... 1, by Assumption (),, Kayh, hi 1:r is a compact operator for each (ae, hz-1) A x Hi-1 (Example 2.3 Carrasco et al. (2007), so there exists a singular value system stated in
Assumption (c) according Lemma
Then by Assumption we have Ker [ (K
ar. we have, by the definition of Ker, K Kan lg (Oo, Ar, 11111 Or, a2, Ho-1 h1-1] O, which implies that g 0 a.s.. There- fore Ker K (Karhteritt)
since for any 9 Ker K
L (HoslA, (00 | aa. h1-1)). Conse- quently, by Assumption (b), all the terms on the right-hand side equations 3 are actually in Ker K (h. for every a, A,h4-1 E H4-1- Therefore condition (a) in Lemma 2 has been verified, Further, condition (b) in Lemma is also satisfied according to Assumption cc. There- fore, all the conditions in Lemma 2 are satisfied by recursively applying the above argument from t = To f = 1, which ensures the existence of solutions to the linear integral equations
0 and Ker K (e-it
B.2 SCALE OF MB-
In this section, we discuss the scale of Mg which is the upper bound for the bridge function classes. We first consider the scale of b%g We notice that for every t and any we need to find solution by. that satisfies
Elbv,a(A,, Or, H1-1) Oo, Ar. H = B[ + bv. 0(41, Oo. Hr-1).
Now we consider the solution by In particular, according to the proofs for identification in Ap- pendix at t = T, we have
Σ (a Or, HT-1) Oo, Hr-1] = E(Rr Oo, Hr-1).
Since |R S 1, we need to guarantee | (a, 0r. H On. HT I To this end, a sufficient condition should be set as 1.. (a, Or, HH I 1. Similarly, for each t, we have
T
Σ bv. O,, H,, 0g H,-1l1 S E
R Og H, 11l ST
(15)
jum
Therefore, sufficient condition should be set as Σ., (a, O, H, On, H1loo S 7+1 Therefore the upper bound for the value bridge function class should scale with T.
Next, consider be According to equation 169 in the proof of identification result, have
E
be (a, Or, H4-1) St, Hi-1
E Re V Vong (a O,, H,-1) 1 St, H Ar = a]
18

---

Published as a conference paper at ICLR 2024
E
To ve (d', O++1; ma) Oe, H+-1) St H A =
Wi,41 O2+1. ( Vo) O₁, H(-1) S₁ H1 A, a
E.
Ro, (al Oz, Vo (a O,, H+-1) St, H,- --,-, A = a)
(16)
E
b Dev O1, He) (a O2. H(-1) St. 11 A
E
Σ Wittila (,', 02+1, Ho)mo, (a Or, H.- no (a O₁, Hi-1) St, Ht-1,
At t, we notice that E. Te, (a Or, H(-1) = for each (O,, H2-1). In addition, we have log ne, (a Or, | S G by Assumption Aee Therefore, we have a relationship that
E Σ bee bev. H, 1) St, H,-1
lee lees
G c (1+ v1x++) G 2
-+
k=t
(17)
Therefore, sufficient condition on E.
TT bav,e(a, O₂, H1-1) should be
sup Σ oi,be-1
TTu bev; (a, or, h- s -++
Furthermore, since || Ile || lle, sufficient condition on the norm || || could also be sup...h, 1 I. v (a, Or, 12-11))l0 le= G(T C(T-too 1
Recall that Mg denotes the uniform upper bound over all t, therefore MB scales with 72 under our settings.
B.3 SCALE
In this section, we consider the scale of the Lipschitz constant I. such that
(Vo)((T)) V V(To)) S L| l'|l.
suffices to consider the upper bound of the scale of the Hessian matrix of ((TT): supa (VVV ||| We adopt the result from Proposition 5.2 in Xu et al. (020) in the MDPs settings. The key their proof is that o log PTo (T) ΣT Vo log To, where r denotes the trajectory generated according to .e. This result also holds under the POMDP settings by adding the unobserved and history 14-11 1. See See equation (18) for verification. Consequently, following the proof of Proposition 5.2 in Xu
ct al. 2020), we get sup, (mT)) scales with G2T3 where G == supt, os [[ log me (a, 1) scales with /T in our settings. Therefore, we have that I. scales with T
ot, h
B.4 ASSUMPTION 4 4A
Assumption a)) requires that the offline distribution pa can calibrate the distribution Td induced by ma for all 0, which might not be satisfied in some practical scenarios. In the following, discuss on practical scenarios where this assumption is not satisfied and propose a potential way to address this concern.
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 usu- ally satisfied. This is because data collection these trials typically randomized, ensuring a comprehensive representation by the behavior policy. However, note that in domains such as
19

---

Published as a conference paper at ICLR 2024
electronic medical records, meeting the full coverage assumption may pose challenges due ethi- cal 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 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.
Di (St, H1-1) 1=1.., Di (St, H. HI-1)T S.)
= max (E
?2) < oc.
xb
This partial coverage assumption only needs that the offline distribution p= can calibrate the distri- bution T. induced by the in-class optimal policy, which is milder condition compared to the full coverage assumption.
B.5 ASSUMPTION C)
Policies that satisfy Assumption ((c) are named Fisher-non-des risher-non-degenerate policies in the field of (natu-
ral) policy gradient. This assumption was assumed originally in the pioneering works on the natural
policy gradient and the natural actor-critic method. See for example Kakale/ 200Te][Peters Peterss& & Schaal
(008a): BBhatnagar& et al. (2009). Recently, there is also line of work studying the policy gradient-
based algorithms by assuming Fisher-non-degeneren policies. See for example Zhang et al. (2020);
Liu et al. (2020); Xu et al. (2021); Ding et al. (2022); Masiha et al.] (2022; Yuan al. (022 ;
Fatkhullin et al. (023)) We summarize common policy classes that satisfy this assumption: the
Gaussian policies with full row rank feature map, subclass of neural net mean parametrization,
full-rank exponential family distributions with a parametrized mean, etc. For more examples, we
direct you to section 8 of Ding al. (2022). section B.2 of Liu et al. (202)) and Appendix of
Fatkhullin et al. (203)).
B.6 AN EXPLICIT FORM OF THE IDENTIFICATION RESULT FOR TABULAR CASES
We present a specific identification result here by taking a generic partially observable discrete con- textual bandit (i.e., single stage, finite state/action spaces) as illustrative example, which provides an explicit substantiation of Thcorem [] We first introduce some additional notations. For random variables X, Y taking values on {01, [....... Tm.) and {vi, ... }n
P(X Y) to denote = v,). Also, PPX) denotes a column vector with
matrix with (X Y) == pd (X x, P.(X): p=² (X = xz). M is used to denote the Moore-Penrose inverse of a matrix M. Then have the following identification results. The proof can be adapted directly from Appendix E. of
Shi et al. (2022).
Example 1. In a partially observable discrete contextual bandit, if rank((((O) | Si)) = |SS| and ran | ())) = S|), then under Assumption [
the following results hold:
VoV(To)
Σ ri Nonola o (ri,, Oo, a1) PPO Oo, an) (1) (PP()))
(18)
01.01.71
In particular, ler B B Oz) be a de x 10 matrix storing the gradient bridge value, then we have
BTG VV. (a) = Σ ri Voraaa PPrr Oo. a)P(() O),a)t. 01.71
(19)
As special case, Example shows that the policy gradient can be explicitly identified as form of matrix multiplications using observed variables in a discrete contextual bandit. We note that rank([P(O, {1)) [S], rank(P(Ou,
S1)) |S] are sufficient conditions for guaranteeing Assumptions 3 in this case. They imply that O, O₂ carry sufficient information about S, under the offline distribution and that the linear systems (discrete versions of linear integral operators
20

---

Published as a conference paper at ICLR 2024
304 44 have solutions. Under the given assumptions, the term Eg, (r1, 01 $1 a1 a1apppp"()))))))))) inside VaVi = Er Tip= (ri,0) 81,a1) 0i "r) (s1) can be expressed into term that only involves observable variables.
B.7 INCREASED COMPLEXITY DUE TO IISTORY-DEPENDENT POLICIES IN POMDPS
In this section, we discuss how the inclusion of history impacts the complexity of policy gradient ascent for confounded POMDPs under offline settings across statistical, optimization, and computa- tional aspects. Specifically, we illustrate this with the example of log-linear policy:
To. (at Oz, h1) exp(0, (a Ot, ht-1)).
Statistical Aspect. In terms of statistical estimation, we examine the upper bound presented in Theorem 2 for the policy gradient estimation emror. First, the dimension of the policy space de implicitly depends on T. At each step I, de is a feature map from a space of dimension ([A[dimm(() (O) to space of dimension de,. To preserve information adequately, it's reasonable assume that de, grows with t. In contrast, in MDP settings, a fixed de, assumption may suffice for all t. Second, the function classes for the bridge functions and test functions should also be rich enough because they are functions of histories that scale with at each stage t. Therefore the complexity of the function classes (F, B) also grows when the number of stages T increases. These factors collectively contribute to the complexity of estimation when dealing with distory-deeendent policies.
Optimization Aspect. We discuss the assumptions in Section 6.22 which mainly affects the complexity in the optimization aspect. Regarding Assumption 5(a), when (, ot, hr-1) in compact region with [idx 0t, h1-1)lls < B, is straightforward to show that [Vo log To, (a: oc. h4-1) Vo, log Toy (at ot, h4-1))l S B² 110, f'lle- This assures that the Lipschitz constant remains unaffected by the historical dependence. Assumption 5)) requires the positive definiteness of the Fisher information matrix, where the constant implicitly depends on the number of stage T. Intuitively. obtaining a large μ becomes more challenging in the con- text of history-dependent policies due to the high dimensionality of the history space. A potential approach to mitigate this challenge involves mapping the history to a lower-dimensional space that retains sufficient information. For Assumption 5 c), the scale of the constant J. increases when con- sidering history, compared to the standard MDP settings. See Appendix [B.3 for more details. It's evident that the historical dependence amplifies the complexity through Assumptions 5(b) and 5(c). Furthermore, the dimension of the parameter space de, implicitly depending on T, heightens the challenge of gradient ascent for the same reasons elucidated in the statistical aspect.
Computational Aspect. We focus on the analysis of the computational complexity of Algo- rithm using RKHSs, Gaussian kernels, and log-line log-linear policies, yielding a time complexity of See Appendix [.2] for more details. Compared to the standard MDP
OK max settings, the introduction of history-dependence primarily increases the computational complexities in two steps: the evaluation of the empirical kernel matrix to derive the closed-form solution for the min-max optimization problem (9) and the update of the policy parameter. For the empirical kernel matrix evaluation, kernel functions must be computed in the history space, task that scales with T. Furthermore, we need de operations update each coordinate, where de implicitly depends on T.
C FURTHER RESULTS RELATED TO THEOREM 2
In this section, we present two examples of Theorem 2 In particular, we consider the case when all the related function classes are VC subgraphs, which commonly considered in parametric settings. For example, the finite-dimensional linear function classes with dimension d has a VC-dimension d+1. 1. Additionally, we study the case when all the function classes are RKHSs, which are commonly used in nonparametric estimation.
Before we present the main result, two more assumptions are considered. Assumption g is a Lips- chitz assumption imposed the policy space. The commonly-used log-linear policy class satisfies this condition. See C.3.3 in Zanette et al.] (202I). Assumption g is a technical assumption that allows to conveniently express the upper bound in terms of the dimension for parameter space rather than the complexity of policy space. Assumption[[i an eigen-decay assumption imposed for the RKHSs. Intuitively, the eigen-decay rate measures the size of RKHS.
21

---

Published as a conference paper at ICLR 2024
Then we have the following two main results. The proofs and more details provided in Appendix
Theorem 4 (Policy gradient estimation error with VC dimension). Under Assumptions with probability at least Ç it holds that
log (T)S))(FF))) log N
Mg.TmaMM.MMMde where F) denotes max {{ {(V)T")) )
sup EE0
VoV - (To)
N
(V(B))))
Theorem 5 (Policy gradient estimation error in RKHSs). Under Assumptions probability at least - Ç holds that
2
4
g
with
sup [oV((T)) VoV(To)lle o
(20)
<C Tax MgMMxldaM) Vlog (c/T/CC) NN
m mmin
1420K 2
112umax 2-1/0min
where ((de) max dg
do
}. Here Omax
max Kgg.v v aKg
mmin = min v vv) defined in Assumption measure the eigen-decay rates of RKHSs.
D DEFINITIONS AND AUXILIARY LEMMAS
In this section, we list some definitions and auxiliary lemmas.
Definition D.1 (Measure of ill-posedness). At each i, given the bridge function class B(O), the mea- sure of ill-posedness is defined as
lIb(
Tt
sup BEB
|E (b(W))
X.] 112.2
(21)
Let Tiax = max be the maximum of the measure of ill posseddeesss across T decision points.
The following definition adapted from Liu al. 22020) Ding et 2022): Yuan al. (002);
Fatkhullin et al. (202)) in our POMDP settings. The transferred compatible function approximation
error Eapproz is used to measure the expressive power of the policy class. becomes small when
space of the policy parameter increases (Wang et al. 2019 Liu et al. 2020).
Definition D.2 (Transferred compatible function approximation error). The transferred compatible function approximation error Eapprox is defined as
ET [A] (Ar, Or, St, Hr-1) - - (0) Vv, log Ta, To, (A, Or, Hr H1-1)) 0r, (Ar,
sup AE
Vo,
where Ag is the advantage function defined in Definition D.7 and w (0) Rdde is defined as arg min,o, E (A.7 (Ac, Oz, St, Hz-1) w. Vo, log ne, (A, Or, H+)
Definition D.3 (Functional norm associated with vector-valued function class). For any vector- valued function class H. (h Rd d2d2 h (h1,..,,he hy E Hy V1 S j d2), functional norm || l| associated with H. is defined as [|]] == (Eiz |1 where || Il is functional norm associated with H4.
(poo))))))) Definition D.4 (CP."")) -orm)). For any vector-valued h E H. the population L norm with respect to Pa is defined as ||h]] == [|b| (e(llc((eerr))) = (EE (Rx~g->> (1)())11))1 When h. is real-valued notations ||hl| for simplicity.
Lemma (Policy gradient in POMDPs). For any mg E Ie., we have
VoV(TT)) = T
R
Va log no, (A, O,, H Hy-1)
(22)
==1
22

---

Published as a conference paper at ICLR 2024
where V log ne, (at ot, h4-1) is de -dmenssional vector with only non-zero elements in its t-th block for every t.
Lemma 4 (Theorem 14.1 Wainwright (2019). Given a star-shaped and b-uniformly bounded function class F, let on be any positive solution of the inequality
Rx, 8²
Then for any 2 8ns we have
1 for all I EEA F
I1 -1 S 11/112
2
02 a2 with probability at least c1e cie br
Here
R, F).
denotes the localized population Rademacher complexity.
The following lemma is generalization of lemma when f is a vector-valued function. The idea to incorporate a contraction inequality from Maurer (2016) for the vector-valued function. The rest proof is adapted from Wainwright (2019).
Lemma 5. Given star-shuped and l-uniformly bounded function class F, let on be any positive solution of the inequality
[ 82
for any le = -,..., d. Then for any t 2 8n we have
di2
11112,2 11 11 2
for all F
(23)
with probability at least cie - Here
Rn (x).
denotes the localized population Rademacher complexity of the projection of F on its k-th coordi- nate.
Definition D.5 (Star convex hull of H). For a function class H. we define star(?) = (rh h E H.r E [0, 1]}-
Lemma 6 (Lemmaa 11 of Foster & Syrgkanis
(019
Consider function class F, with Ad 41 log(2ean)) be any solution to the C2n
sup ol < 1, and pick any fo E F. Let
inequalities:
Vt (1....,d)) d) R (6, star (F), f7)) 58
Moreover assume that the loss & L-Lipschitz in its first argument with respect the E norm. Then for some universal constants Cs, Co. with probability 1 - Cs exp (cand?)).
PP (C, - - P (C,
11-)1 18Ld5, { {11s [15- f2 + {n). vf
Definition D.6 (L-smoothnesss) A continuously differentiable function f R2 + IR is L-smooth if V is L-Lipschitz i.e., all x, y E domain (f),, it holds that [V fw))lee < L || 1oc--llo ylle.
Lemma 7 (Ascent Lemma). If the function f D + R is L-smooth over set X' C D, then for any (r,y) E X:
f(y) > (xx) (VI()),
Definition D.7. Let the value function V and the action-value function Q of a policy Ty E IIg be defined as
(ot, h--1) To
Rí Or or, St St, H:-1 h4-1],
(24)
1=1
23

---

Published as a conference paper at ICLR 2024
and
T A. - az. O₂ = o. = sc. He-1 = he-1l.
Qi (at, Ot, St, he-1) 1
Rg
(25)
j=t
Then the advantage function & is defined
A (at, Ot, St, h4-1) = Qi (at, Ot, 81, h4-1) V² (ot, 81, h111)-))
(26)
Lemma 8 (Performance difference lemma for POMDP). For any two policies ne, we holds that
lll,
V(TO) V(TTr) = Σ E [A] Os, H1-1)).
(27)
Remark: Lemma 8 relies the assumption that {R, 12 j=t-1 1P St. Se41, H, for each which satisfied under our POMDP settings according to Figure
Lemma (Policy gradient in POMDPs (I), For any me E Ie, we have
T Σ
VaV(TO)) = E
Rs
Vo log na, (A₃ Oj, H H5-1)
(28)
where Ve log ne, (at oz, h(-1) is de di-dieensional vector with only non-zero elements in its t-th block for every
Lemma 10 (Policy gradient for POMDPs (II)). For any my Il the policy gradient can be expressed as
VOV(TO)
Σ E Io Vogooge, H,,1) (A,, Oc, H(-1)l
(29)
1=1
where V log Te, (at block for every t.
or, h-1) is de de-dimensional vector with only non-zero elements its t-th
E PROOFS FOR POLICY GRADIENT IDENTIFICATIONS
In this section, present complete proof of the identification results summarized in Theorem I In the first part, we show that under Assumptions 2 we obtain another sequence of conditional moment restrictions that projected the unobserved (S,, At, Hr-1). In the second part, show by mathematical inductions that
T
E
To (a, O,, H,-1) St, H.-1l
E
St. He-1]
j=t
and
T Σ
E
Σ ve (a, O,, H4,1)) St, H4-1 V
VO
R
Se, H
LaEA
j=t
for all t = TT T,... 1. In the third part, we conclude the proof of Theorem
Part
Suppose (Dv with b. 0 satisfy equation 3
Then we have
be H1-1, Ar) Oo. 11
-E
E bT,
St, Ov. H Ao] be,,(O,, H,0,,,,.0 H4-1, A.) St, H. Ar
Ou, H Hr-1, Ar]
(30)
-E
E
Oo, He-1, Ao by Oo 11 O, St, Ar, H:-1
24

---

Published as a conference paper at ICLR 2024
and
E
Re (a Ot, H1-1) Σ
Di Vi Oc+1, H,) O₂, H+-1) Oo. Hi-1, A
B E. ReToo (a Oz, H1-1)
Di (a, O He) On, H1-1)) St, Oo, A
Oo, Hi-IAA
(31)
=B E ReTO, (a Or, H{-1)
DiVie (a. Oc+1. H.) (A H,,)) St, H,,1, As
Oo, H.
(by Oo Re, Oz O++1 St, A,, H1-1).
Combining equations
31 31
we have
E
b7. (O,, H1 At) St, H1
10, H0-1, Ar
E
E.. Re (a O,, H,-1)
St. Hi-1, Ap ] Oo. Ab ]
(32)
Diet1 (a, Oc+1, O₁, H(-1)
(by
Therefore, by Assumption 3 we have
E
To (O,,
H1-1, (,-,H,H,111 AD St. Ad
(33)
=E (a 12,11)11) + Σ bv.44 (a, O4+1, Hi)TO, (Ae Oc, Hc-1) | S, H: Ag
33) shows that the solutions to also solve similar conditional moment restriction with unobserved Sy. Next, we consider the gradient bridge functions.
Equation
Suppose [DVV.r. DT with VTT+1 = Te DV.T-1 0 satisfy (4). Then we have
(Oz, H;-1, Oo. Ar, H4-1 b To
-E
DTV, H S., Ou, Ad, H.-1]
Oo. Ar, Hc-1]
(34)
E
(O,, H,-1, St, A,, H.-1]
Oo, Ar, Hr-1] by Oo 11 Or | Sr, Ar, H
25

---

Published as a conference paper at ICLR 2024
and
E
(Re Σ Vet41 (a, (4),,H)))VoT4, (A, Oz, H1-1) Σ
bov Oc+1, Hi)
To, (A, Or, He Oo, H
=E E [R,
(1) Oz, St, So, A., Hi-1
Hi-)) O2, Hc-1) |A, St, Oo Ar, H1-1
10. Hi-
E
E
6 bevi 04,1
00, Ac,tte
E
(Re, Σ
bi Oc41, Hi))) (4 O., H+-1) St, Ar, Hi-1
1 Ae, He-1
E
E
b Dev (a, Oc+1; H.) (Ae 1,, H+-1) St, A,, H,-1
Oo, A2, Hz-1
(by Oo IL RG, O,, O St, Ar, H1-1)
(35)
Combining the above two equations, have
E
E
.Tu VV,
(O,, H(-1, At) Sz, Ar, Ho-1] Oo. Ar, [1-11]
-E
E
RR
Th Vi44 (a, 01.1, Vo) O,, H,-1) St. Ar, He-1
Oo. Ar, H
+
EE
E
Σ
To bov i (a, Oc+1,
Ho) H
|0, H4-1) St, Ar, Hh-1
Oo, Ar, lh21
by (4)
(36)
Therefore, by Assumption 3 we have
bev. Hr, Ar) Se, Ar, Hr-1
=E (Re + Σ bi:41 (1, Vo) 10, H:-1) St, A,, Hi-1
(37)
Σ
The bev. (a, Oct1, Hi) (Ae Or, Ht-1) Se, Ar, Hz-1
Equation 37 basically shows that the solutions to also solve similar integral equation with unobserved S.-
In the rest of the appendix, will utilize equations 33 37 several times. Next, move to Part of the proof.
Part II In this part, show by mathematical inductions that E b7 (a, Or, Hc-1) T IT, Re St, H(-1] and EnE bevv, (a, O₁, Hz-1) St, H
St, H1-1]
Ve E R2 St, H.-1] for all / = T,..., 1, which are summarized in the following lem-
mas.
Lemma 11. Under Assumptions
it holds for all t T, T..... that
E 6%% Or, H(-1) St, Hi-1
Rs St, H:-1).
(38)
26

---

and Published as a conference paper at ICLR 2024
Lemma 12. Under assumptions Assumptions it holds for all T, 1 that
E
AAA, (a, Oz, H1-1) S, H VgE
Σ Ry St, Hi-1
(39)
LAEA
Proofs Lemma and Lemma are provided in Appendix
Part III In the third part, we conclude the proof of Theorem
! by utilizing Lemma
I1 and Lemma
12
In particular, we express the policy gradient as
(oV(TO)
T
V V
Rr
by definition of policy value
1=1
=Volis
E
Σ Re
S
by the law of total expectation
=VelDs
ne
Rs [1,, Ho
by Ho
(40)
-ES
VgET
Σ Re S1, Ho
by interchanging order of integration and derivative
=Bsinri
bev. (a, O1, Ho) | St, Ho
by Lemma I2
bevv. (a, 01) 1
by Ho
=E
(a,
Similarly, we can express the policy value as
((TT)
T
=
Rs
by definition policy value
T
-Es
R₁ | Si
by the law of total expectation
t=1
=Es, w
no
R₁ | S1, Ho
by Ho 0
-Es
E
Ui (a, O2, Ho)
S1, Ho
by Lemma 11
-Es wm
E
Σ big (a. 01) S
by Ho
E
Σ U (a, 01)
Consequently, we have (DV(TT) = E. byv, (a, 0:)] and V(Te)
E. 67% (a, O.)].
complete the proof of Theorem 4.5.
27

---

Published as a conference paper at ICLR 2024
F PROOFS FOR POLICY GRADIENT ESTIMATIONS
In this section, we provide a complete proof of Theorem
Proof sketch We briefly summarize the sketch of proofs here. The goal is provide supage, (T VoV(TT)lles finite-sample upper bound with high probability, which will appear in the suboptimality gap studied in section for policy learning. To achieve this goal, we first decompose the -norm of VoV(TT) VoV(TT) into summations of one-step errors mainly caused by min-max estimation procedure at each t. Then we provide finite-samp saite-sample upper bounds for these one-step emrors uniformly over all 0 θ and all f = 1...., T by adopting uniform laws of I e can be
large numbers. Finally, the fimite-samlle upper bound on supsee ( VTV(TT))l obtained by combining the decomposition of errors and the analysis of one-step errors. the rest of this section, we present rigorous analysis for each step.
F.1 DECOMPOSITION OF ERROR
let (b7%, bTg bi denote set of bridge equations that solve the conditional moment equa- tions 4. i.e. true bridge functions that can identify the policy values and policy gradients. Similarly, we let (b7,- Dyy D denote the set of functions returned by the Algorithm Then, we consider the following decomposition of the error as
12'
VOV(TO) VoV(TT)
E"
b Vavi (a,(a))))) 01)] E
8 v. (a, 01)l
=E =E"
by vvv 0z)] -E*
E="
TTe Vavi (a. 0,)1 E" Σ The
0,)] 2²"
bovv. (a, O1)l
(41)
The way of analyzing the second term is standard by using techniques from the empirical process theory, and we leave this term to the final. Now we consider first term.
B
Σ (a, -1)-0:)-- Ebov,(a,00)
=B" 6
(bTH (bVV,1
(A1, 02) 3an (A1 011] by A1 Il O₂ S
mT mT((A (A1 |1)
=F"
1
(1 (bev, (A,, - T (A1, (1), S S1,A1]
(42)
(A [()
=B"
E*
[80 [ 01) As,
m (A1 Si)
E=
ET Vevv. O1) S,, A1]
( S1)
For the first term of the last equation, expand by using the conditional moment equation in the unobserved space (37), and thus we have
R
ET
IT (A,, |
Ti(A (i)
"
B
(R1 + Σ (a', (aaaa'',00 O2, HoTO, (A1 O1)
(A1 (()))
bavz (a.,a' O2, mo, (A1 01) Sr A
28

---

Published as a conference paper at ICLR 2024
=F"
ET
(R1 Σ
by Viylaa
(e2g(a'O2, O2, HI)) (A1 01) Si, A
(A1 (i)
+ E=
E² Σ
bon b (a', , O2, Hi (A1 (01) S
(A1 (11)
=B"
(AI |()) ETd
(Ri + Σ Wiz(d', ( O2, Ho),) (41 01) S1
R=
(A1 81) E="
(R1 + Σ Wal 02, H2), (41 01) S1, A
+ E=
(A1 S1) E=
(R1 + Σb bVz(a', 02, b, o (A1 O1)) 11
(43)
+ -F="
E=
( ,a', O2. H1 MO, (A1 | (1) S A
(A Si)
R=*
(A 81) E=
Tate bevi2(d', O2, Hi) (Ai | O0)) S, A
+ E=d
E=
bev. (a', 02, HI)To, (A1 | (2) 1,
(A 81)
=F"
End
(Dii(a'' O2, H₂) bii O2, H H))) (A1 01) S1, A
( (())
+ E=
E=
(Ri
Tia (az O2, (o)) (Ai (A)) 01) St, A
AA 51)
+ F
AA 8i) E=
Σ (b (o ,00, H1) To b O2, H1 Ho) (A1 O1) St, A
+ R.a
E=a
Σ To bav. O2, HI) (A1 (A1 01) S1, A
(A1 Si)
Now we add the second term back and have,
E
Vevi (a, 01)
=F"²
BT
bee (AI, 01) ((),
m (A1 (1)
E**
ETd
TT ( 0i)
|St,A]] (
(A S()
=7"
(b (al, , O2, Hh) - - O2, Hz) (A1 01) S A
(Ai (())
+ E=
(A1 81) E=
(R1 + Σ
ST
(44)
+ g
(11 Si) E
(b To Liiilaa Oz. Hn) 3o b O2, Hi) (A1 O1) St,
29

---

Published as a conference paper at ICLR 2024
+ R=
E=
Divvi O2, MI (A1 101) SI, A1
(A Si)
E
En
( (AI,) 01) St, A1,
(A1 (1)
11 111
where
= Ex
1 E=
(R) Σ
02, Hi)) (A1 10))
(Ai 51)
(45)
v.. (a', ,0, H1 TT, (A1 01) b (A1, 01) 8 A1
and
11
=
(1 (1) E
(a O2 H1) 02, (AI 10)) S1, A
(46)
and
111
Ex
AA 51) E="
O2, H1) , Hi))To, (A1 O1) S1, A
(47)
Intuitively, the term I can regarded as the error caused by solving equation 37 the term can be understood as the estimation error for the V-bridge function in the previous step, and term I/I can be viewed as the estimation error for the gradient bridge function the previous step.
We deal with the term III at first. We introduce the following lemma that is useful for analyzing the term III.
Lemma 13. For any function fo A O He-1 + Rd, the following holds:
p (St. H(-1)
fi(Ac, Ot, H11--)
pF (St, H up (Ae St)
(48)
De (S,-1: H To, (A,-1 Or- H(-2)
1""
Σ fe(a, Or, Hr,
b 1, H| b _ (Ar1 St-1)
30

---

Published as a conference paper at ICLR 2024
Then, according to Lemma 13
we have
111 = E=
(A1 8i) E= Σ ( O2, H1)
Dev.2 (a', O2. Hi)) (A1 01) S A1]
E=
(b (bei: O2, H1) b 0z, HT) (Ai 101)
(A1 1 (1)
P5" (S2, H1)
E=
(6 VVV (A2, O2, H1) ( O2, H1)) by Lemma B
(Av.((A2,
p2 (S2, H1 J A2 S2)
P2 (S2, H1)
E=
(b (Dvv2(A2, O2, H1)
pz (S2, H1 ( (2 S2)
-V (A2, O2, H1 A2, S2, HI
= -ET
D2 (S2, H1)
E=
(bee (b O2, H1)
D (S2, H2 |T
A2 (S2)
-vv.22 (Az, O2, H1)) A2, S2 H1)
(49)
We notice that by using the conditional moment equation equation 37 again for Ea 1ev.2( (22, O2, H1) A2, S2. Hi we can further get three terms using the same strategy for analyzing E= F(AA 10v,i(A1 01) Bev, (A2, O1))] O1)) previously. Specifically, have
Th (S2, H1)
IIT I =
15 (S2, Hi )m² m A2 82) TF*
(0 O2, 02,H, H1)
(50)
vVV2 (A2, O2, H13) A2, H1
= (a) + (b) + (c)
where
P2 Jo (S2, H1)
(a) E=
E=a (R2 + Eirisaa Oz, VoTo, O2, Hi)
pd (S2, H1 m Ag 22)
baivala', Oz, H2) ) TT, (A2
O2, H1) B
O2, H1) A2, H1
(51)
and
(b)
p (S2, H1)
=
ET
(bVi .00,0,, H2) - -8% By H2)))
(52)
pp (S2, H1 11)r A2 S2)
V o T82
(Ag
O2, Hn)
S2, A2, Hıll
and
(c)
p2 (S2, H1)
= =
Br
Σ
To
(a',O,,,,,,,, Os, H2) - J Bovzld' Oz, Hz))
(53)
ps (S2, H1) 82)
To, (A2
02, S2, A2, H1]].
31

---

Published as a conference paper at ICLR 2024
Then analyze term (c) by Lemma 13 again.
For general 6, we define , (St, H,-1) as P. (S, which denotes the density ratio at time l. Then, by induction, we have the following decomposition:
(S.
T
T-1
E
(v,
- E
Et
(54)
1=1
t=1
where
K: ( H2-1) (A (Ss)
Et :==="" 1F
Bad
(Ry - Ebieon (
0z+1, Hi) (At Oz, H+-1)
Teee Dove4a (a', Oct1, Ho) (Ap Oz, H+-1) The V (A,, O2. H+-1) St A,, H
(55)
and
E7 =
(Se, He-1)
E=²
B=a
5o (V (d', Oc+1, H:) - Dy, (d', O Ho))
(56)
(AAe Si)
a'
VOTo, (Ap | Oz,, H2-1)
St, Ht-1]l-
Now we analyze Et using Lemma function
again. Since Hi-1 = (At-1, O1-1 H(-2), we can define
fe(A,, Oz, Hi-1)
H:-1) by, O2, logg) O H1-2).
By using the operation Te Vo log TT VoTT, express E
2 (St, H1-1)
=E"
ENd
E Sitald', Oct1, Ho)) 1O, H:-1) St, H:-1
T (Ar. (St)
* (S,, H4-1)
= -
Sstild', Oct1, H.))TO, (A. Or, H,-1)
T| (A, |Sa))
K: * (Se+1, Ht)
17
S441 (A441 O4+1, Hi)
by Lemma 13
(A SS41)
1 (St+1, H₂)
(bV,441 (A: O H²)
n (At+1
S141)
Dv,++
(Ar+1 Oct1: Vo log ne, (Ae Or, Hr 1))
(57)
Ty
2 (Se+1, Hi)
(1iT (1v (A(41: O H,)
T (Att1 S441)
(Art1, Oz41, H,), log Te, (A, Or, 1lt-1) S A4t1,
bv.++1
*41141 (S++1, H²)
Vg log no, (A, O, H H²=1)
O H,)
(At+1 S1+1)
by.4 B. (At+1, O141, H,)) S1
Then consider
32

---

Published as a conference paper at ICLR 2024
Erd
(Ac+1, Oc+1, O041HH) H₂) [e441 (At+1 O241,H, Hz)
DV.e4 (Ar+1. Oc+1, H.)) S141, Hi
=E" "
+
bv, 2 Ow42,
(Ar- Oct1, Hi) Se41, Hzs Ac+1
a'
E"
TTo (iit41 (Ac+1 Oct1. Ho)) S441, As-1. Ho) by equation 33
[Re+1 (Att1 O2+1, H,)
+
bv 2d', O442, H4t1) ( Or+1, Hi) St41 He, Ae+1
E"
Re+11 (A++1 Oc-1, H₂)
B 27/ ,102,
(A--1 Oc+1, Hi) S441, He, A++1
+ E=
[Be41 (A++1 Oc-1,
Fite 2// O142, H141) (Ar-1 Oct1, Hi) S441, Hes A4t1
Tioo ( Oc+1, H.)) A0415 He
(b (a' Oct2, Hzt1)
T V,142 (a', O+t2, H(+1)) (Aet1 O441, Hi) S441, He, A6t1
R (A 12-1,
Tot 8i (a', 0122, O H141) (A (A-1 Oc+1, Hi) St41, He, Ast1
+
a'
E
Tro (A Oct1, Hc)) S41, Ac-1- Hg
(58)
Therefore,
To =Ba²
111 (S++1, Hi)
V log ma (Ae Or, Hr- H)-
[172et (Aet1, Oct1, H.)
T (A441 S(+1)
(Ae+1, O141; H₂)) S1+1, A H,
Vi++1
1h. (S+41, H₂)
1
(A411 S(+1) V log ne, (Ae Or, H1, 1)-1)
[Be+ITou (Ar+1 O H.)
Dro (0 O042, He+1)TH (Ar41 O4H1HH,
+
1 (Art1, O+11, | S441,
v.441
To
(S Hy)
+ E
A Stt1) V Vo Tg, (A, | O,, H, B
Iovirzld' O142, H(n)
33

---

Published as a conference paper at ICLR 2024
be Vat2ld', Ou42, To. (Ae41 I O241, S141, A441, Hi
(59)
The first term can be understood as the estimation error for the min-max estimator, and the second term is caused by the estimation error for the value bridge functiin from the last step. Notice that the second term can be analyzed by using Lemma 13 again by setting
Je+2(Ar4,, O+t2, H+t1)
(60)
=002)42(AA22 O422, H++1) - DV, DV,4+2(A422) O+22, H441)) no, (Ae Ot, H+-1).
By induction, we have
T
Et
ej
(61)
|=
where
R (S3r
(S, H)-1)
ej =F=
Vo logog no, (Ae O,, H+-1))B* [RyTo, Hj-1)
(A |S₂)
+ Σ B s+ ,a'00++1. 02+1, (A₃ O₁, H5-1) O, Hj-1)) Aj, H
(62)
We note that V log no, (A, O2, H1-1) is always measurable with repect to the sigma-field gener- ated by H for each j 2 t ++1 1. Therefore the term V log To, (A, Or, H(-1) is always kept for each j + 1 in Ej-
In summary, we can decompose the policy gradient as
T
T-1 T
E=
Σ bev, (a, -
- (a O1)
E +
Σ
Σ
ej
(63)
t=1
t=l
j=t+1
where
Ne (St, H,-1)
Et =1=
1ET
(Re + Σ Big
EDbeeee Setetildi HeT (Ai Or, H1:1)
n (Ae St))
Bate bov.44
Oc+1, (a': Hi)TO, (Ag 10,, H1-1) bee, Oz. H.-1) St A,, H
(64)
and
To 3 (A Aj (S,)
(S), H)-1)
ej =
Vo log no, (Ax O,, 1 [Rzmo,AA;
0,, H5-1)
+ Bi
H2) (A, H O,
Aj, H5-1
(65)
& denotes the one-step enror caused by min-max estimation for the conditional operator for gra- dient bridge time while e, denotes the one-step error caused by min-man estimation for the conditional operator for value bridge at time l.
In the section, upper bound them in terms of density ratio, one-step and ill- ill-posedness.
34

---

Published as a conference paper at ICLR 2024
F.2 BOUNDS FOR THE DECOMPOSITION
Recall from the previous section that
(T)( (oV(TT)
VV, (a, 01)] - E=
Ja V (a, 01)1 E="
Σ
b Vv, (a, 01)] - -R-
Σ b V (a, 01)
+ Σ Σ oj E"
b (a 0,)]
-
b (a, O1)l by equation (63
j=
(66)
Then by the triangular inequality, we have
(oV(no) VoV(To))le
T-1
4 Σ
Σ e
E=
I The (a, 01)] - T (a, Oi)]lle=
(67)
1=H+1
1ale
Σ
|eellee j-
Σ
|
E (a (a, 0i)] - P3nh I ba
The third term can be upper bounded by the uniform law of large numbers according to the empirical processes which involve the size of (1)), In the following, we consider the first term and the second term.
By Assumption 4 bb). for each b Rag Vi+1 VV++1 and any 0, there exists solution
(o: tions 3 and the arguments in Part I in the proof of Theorem (Appendix bi 1 0),
bi, (b ( 0), bv,, V.++1 B Vv.++1: 0) to the conditional moment equations 3 M By Assump-
va (b Deee B 0) and (b%) 1+111
Tae bVv,44100) also satisfies the conditional moment equations
that depend on the latent states (33) 37 Therefore, we have
Ki (St, H+-1)
E2 =B=
18
(R4 + Eov.e (a' (2'10 11)) (A, Oz, H1:1)
x (A, Si))
Os, H+-1) - B Oc, H.-1) St, Ar, H--1 B Vv..41 0e41, Ho)TO, (Ae 10,
K . (Se, Hz-1)
O,, H,,1)
x (A, (.)
bev. (A,, Oz, H1-1)
Sc. Ar,
Ac. Hr-]]]
by plugging the solution to (37
K T6
(St, H:-1)
=
B7e Bov.4 ()(,, O₁, H1-1) O,, (1-1))
x (A, (.)
(68)
and
N5 , (S,, H3-1)
Ej =
Vo log Te. (As Or, H4, 11-11)1=** (A, (Ay H,;1)
(A, |S,)
+
Wish Oš+1. (a'OO++1, 13,1:H,)m Hy) (T, (A₃ O5, Hı-1) (4. [S Aj, H5-1
P (S); H1-1)
V log ग.. (As Or, H4, 11-11)1"" 1, O,, H;-1)
7) |S,)
35

---

Published as a conference paper at ICLR 2024
100 O,, (S, H,-1 by plugging in the solution to 33
(S, H1-1)
V.g log nØ. (At Oz, 11111
Tÿ(A, |S₁)
(bV, (A), H - byg (Aj, Oj. H H,-1))
(69)
Then we upper bound |eelle= and |eelle. For clarity, we write by. Dōv. to denote bi Caalbiar 0), (e ( 0) if there is confusion.
| 1ee
2,2
de
no (S,, H1, H1-1)
27
(Vevas(Ar, Or, H:-1)
Tra Dev. (Ac, Oz, flo-1))
(A, |(i)
i=1
$
Te (Sc, H H(-1)
des
E
Σ
Ex
[A, O2, H1-1)
(As Si))
Be (Ac, Oz, He He-1))
1/2
To (Se, H H(-1)
do
B
Bx
(b (A,, O2, H:-1)
T (Ap Se)
1/2
Bio (Ac, Oz, H
( H(-1)
1 O,, H1,1) Jag (ee.. Or, Hr
(A, Si)
SCHollbV,, (Ae, Os, H(-1) - B (A,, O,, Hr (1
capes poot by Assumption 4 a)
SCHTBIL (ovv,(A,, O,, H1-1) - be O,, H4-)) Oo, A,, H,-1 || ((
by Definition D.I
where the term ||E= (bv,, Oc, H.-1) - b O., 11,-1) Oo, Ar, Hr-1| (2 is
the projected residual mean squared error (RMSE) for the min-max estimation operator (Dikkala al. 2020). We use the notation Tx,
projection operator into the space generated by X Oo Ae. H.-1). And the projected RMSE can be denoted as
| (bv. (by... B 0) E loyp
For the second term, we have |eelle= = V Edee og where
36

---

Published as a conference paper at ICLR 2024
E= [.... 1)
2 [....]]]
2
sup 0e,
Vo o log To, (at) I or,
1n-1)_lleeeee B=n [1 [1...1)
HJ,,H-11
-G²
E*a
-
(A
S2)
by Assumption e)
which does not depend the index i. Therefore we have
|
T
R (S,,
SG
de
Brd
O,, H
T) (8))
i=!
T Σ de.
x (S}, H)-1)
T+. (Aj (5) 7)
27
SG
End
i=1
E (0tr) (A,, H (Ag, O,. (A,, H)))))²]] (
GGuuch--Shwaate inequality)
T Σ i=1
(S,, (S,,
27
SG
de.
En
T (A₁ (s)
(A,, Oj H)-1)
-By7, (Aj, Oz. H2-1)) ca(m
T
SC,OG
de, [,011,1(440000,1-11-00,,,,,,,,,,
T
-C,oG
Σ
de, Ty
[,
lepp
Similarly, we can use the notation for the projected RMSE:
Tx, (iv ( Byg -
In summary, we have the upper bound for VOV(TT))
VoV(To)lle::
(TV(TT) - VoV(TT)l
T
|lee|ee=
Σ
Σ
lleille + 1|=
Bee (a. 01)] E-
Σ
B (a, 0,)]le
1=1 j=t+1
T
CheTe
|xx
Dee De
0) - Tao
-
37

---

Published as a conference paper at ICLR 2024
T-1
T
T
Σ
Σ
C
Σ
de,
Tx,, 1 V5+1, 0)
-Dpps
t=l j=1+1
i=!
+ |
b bev,
(a, 01)1
-
Ex
8 (a, Or)llle.
(70)
All the undetermined terms are one-step errors, and we provide finite-sample error bounds on each three in the next section.
F.3 ONE-STEP ESTIMATION
In this section, we upper bounds three terms from the previous section separately:
Tx, (b b vv..41. 0) bev. lll Mererr Tx, [br, 0) b%% ce and
| [Ea D (a, Ot)]
| P=n [. Vav (a, Oi)llle>.
We first introduce concepts from the empirical process that are used measure the size of func- tion classes. The following definition is adapted from Wainwright (2019) and Foster & Syrgkanis (211))
Definition F.1 (Localize population Rademacher complexity and critical radius.). Given any real- valued function class 9 defined over random vector X and any radius > 0, the local population Rademacher complexity is given by
R2 (), EE,xl
sup 0EG:llolla.255
n
egg (X:)
where {x,1/= are i.i.d. copies of X and {G)) are i...d. Rademacher random variables tak- 1 1-1,+1] with equal probability. Further, assume that G is a l-uniformly bounded vector-valued function class {g- X' + IRd, sup, (1g(z))le> 1]. Let G) denotes the k-th coordi- nate projection of G. Assume that Glk is a star-shaped function class, iee. agk E Glg for any go G) and scalar E [-1,1]. Then the critical radius of 9, denoted by 5n, is the solution the inequality
ing values in
8) 58.
max
In this work, critical radius is used the theoretical analysis to measure the size of function classes, which provides a way to get uniform law of large numbers with a convergence rate at each time At each f, the uniformness comes from the previous iteration f + 1, and the policy parameter 0 E θ. Compared to the well-known VC- dimension or Rademacher complexity that is also used the measure the size of function classes, this localized version potentially provides optimal rates by utilizing local information.
functions f E F(t), estimated i ((++1) from
In the following parts, utilize critical radius obtain the convergence rate of one-step estimation errors.
Part I We first upper bound the one-step estimation error about the conditional moment operator Te
on the gradient bridge functions Tx, ( 4 0)
bVv, -
C2 pm. The proof
techniques are adapted from Dikkala et al. (2020); Miao et al. 2022
Luet al. (002). The difference To
that we develop an upper bound that uniformly over (b7), with a random vector that needs a vector-formed uniform law.
V 0), and we are dealing
We let ( and B(6) denote the function space that contain value bridge and gradient bridge respec- tively. Then (t)) B(() x B()) We aim to upper bound the following term:
Tx, bb bev. (
sup #E8 Ee b Ee8++
sup
where Be is denoted as the min-max estimator when plugging in (by, 1. b 8) in equa- tion 9 and (bv,e+1 beveti, 0) denotes the solution to (37) by Assumption (b).
38

---

Published as a conference paper at ICLR 2024
In the proof, assume that the function classes are already norm-constrained for clarity, and there is no penalty term related to the norm of functions in the definition of loss functions. Furthermore, we assume that M without loss of generality. In addition, for simplicity, abuse the notations of loss functions used in section 5 Specifically, we are focusing on the loss functions for the gradient bridge functions here.
Consider 2N (bvv,,, bya+1, bov.44, f. which defined as
N
Σ
(mov(Gl,n wwwe://.../b...bb::///o/uu F(Xe,a).
N
We use (, dv.e+1 bo 0, f) to denotes the population version which is
ET
bov.e, (r... f()))((())))) f(xo)]
Further, we use 2 bro.. to denote
/or s(Xx.)) 111/112,,2-
N
Similarly, (b bv...... is used to denote
E"
(mvv byve, (vv,e,,0)) s(x.)) 111
Then the min-max estimator is defined as
b
arg min sup eev. fEFO
given any bv 1 E B((-") bov.. E B(+)), E e.
The true biv. (depending on (yy.41,bbv..t 0)) satisfies that
V bVv.41,
given any bv;++1 B(( .vv.e+ e B(+")) 0 e.
Furthermore, in order to get a clear uniform bound with respect to we introduce the following assumption:
Assumption 8. There exists constant 3 such that the following holds for all I = I,..., T
To: (a os h(-1) (e, (a oz, he-1)) s 3 0'11 for all or, h2-1 E O x Hi-1-
A
Then we start our proof. The key term that used in the proof is called sup-loss which is defined as
sup Dye by,et, boverr, 0, V..N bv bov.er 0, 221 JEFO
(71)
In our proof, we will upper bound and lower bound the sup-loss. We will show that the upper
bound of the sup-loss is small term that converges to 0, and the lower bound turns out to be an
projected RMSE. In this way, provide finite-sample upper bound for the projected RMSE. We highlight that the described upper bound and lower bound should hold uniformly for any bv E B(++2) .evatt E p(t+1) O.
39

---

Published as a conference paper at ICLR 2024
Upper bound the sup-loss 71 We first consider the following decomposition. For any bv,e-1
BB+), bvv,t1 E B( . θ we have
ViN (o
0,
=,, bv.
f) XIIf1l -VN (brv,, bv. bvv.4+1 f. - Wi.N b,, f, - >llf 1
+ ( bo
VV,,N bv. bov, 0. - vI,v (6 ww..II, f2
+ inf SEFi
211f113.222
-Ve,N WV.v((vv. bv.+1, bVv.1+1 0, V, (
- 2111/11
-inf inf I-V..Nbbvv. bv. bw..1,, 0, f) 211fl (by symmetry and shapes of Wt,N)
JEFiI)
V,,N -Vr.N bv. DVv.+4. N. bv 1...f 2f
+ inf L-V,,N(beve b,,,,, bov.++,, 1) + 2115 (by symmetry of F) SeFi
"b.v..vv...bv. bov.44 0, V,,N (bvv, bv.et, 22 I| 1|
sup JeFin
-
- 211
-Vr.N bv. dvv.141, f) - W.,N bv. brv.., f. - 2111
sup by,,, SEFO
(72)
Taking SEF both sides of the inequality, get
sup V. brver,,, SEFO
2 sup V V. bv. bev.e+,, f. V,,N fEriO
f. 12
sup FeFW
(73)
Rearranging, we have
sup Vr.nbbvve. bVv.cr,, f) - Ve,N (b, bvv.er.. 0, - 22 fEP(
< sup by.e,,,b,..e,,,vv... f, sup fE)())
(b brve..
fEF())
<2 sup bv. 0, f) (by definition of bev.)). SEF())
(74)
It suffices to upper bound sup V. bv.41, b((+2) bvvit4 (1+1) 0 O To this end, apply two uniform laws from the empirical processes theory (Wainwright) 2019 Foster Syrgkanis 2019).
uniformly for bv,
For any by.++ E ()++))
.ev.t Blf+'), A E θ, we have VA MN by.e,,
sup
SEFO
(75)
ben f) 13
sup
SEFO
40

---

Published as a conference paper at ICLR 2024
To upper bound Sup)) V. (b byv.e+1 f),, it it sufficient to upper bound V (bb by, b4 0, f) and lower bound 2 uniformly for F()) To this end, apply Lemma reector-valued version of Theorem 14.1 of Wainwrighh (2019) and Lemma
6 (Lemma 11 of Foster & Syrgkamis (2019)) that are able to relate the empirical version to the
population version uniformly.
For the first term Vr,N (b b bVV 0, f), have that is equal to 1 >>
(mov Ceoov((eerii nZ b by, bVv,++1, 0))² f(Xe,n) We apply Lemma here. We let C in Lemma bbe L, == (mvv 25 bvv by byv,e-1,,) O))* s(X;) where 9 2(G+1)M
(Z;: b bvv 0))² f(x)). By the conditional moment equation for the have gg I 2G++iMM [mayllas:llllll.. S
gradient bridge function equation
2[G+1)MM llmovlloo.2 I 1.
In partieular, have
gl S
2(G + 1)M8
1
$
| by Assumption 4()
2(G + 1)M8
1
Re +
Σ
bv (a', Oct1, VoTTL
2(G + 1)
d'EA
Σ
bavat+ (a', Oc+1, He) To, 1lo.2
d'EA
2( + 1)MB l1bv,
Ra+ Σ
by, (0l,001, 02,1, Hi)
ne, V log me
a'EA
EEn
bovan (a', Oc+1, He) To, 1bo,2
1
2(G + 1)M8 |
1
Rí
Σ by,42 (a', 02,1, Hi) no. Vo log Te, 1bo,2
2(G + 1)MB
a'EA
dovee (a', O241, H,) ne, 10. 1o,2
2(G + 1)MB
a'EA
2(G + 1)M8 1
G(1+
Σ
bv,et1 (a', Oct1, Hi) lloo)
2( + 1)MB
a'EA
Σ
bovett (a', O141, H₂) lloc,
2(G + 1)MB
a'EA
MB + 2(G + 1)MB
GMs + 2(G + 1)MB
MB
2G + 1)MB
<1.
(76)
Also, Cg is trivially Lipschitz continuous w.r.t. g with constant 2(G 1)MB. Let g" be 0, and Lemma shows that with probability least. 1 Ç, holds uniformly for all f E F(0 bystt
41

---

Published as a conference paper at ICLR 2024
B(+1) .vva4 E Bet" that
VI D <18(2(G + 1)M8))n,, (1lgl12 + 62
(77)
<18(2(G + 1)ME),n, (11f dn,,))
for a fixed 0, where on,, dn + co log(er/5) radius of the function class
N and EN is the upper bound on the critical
Q0 = 2(G + 1)MB mvv bov br (x:) Z, 24 - R
(78)
for all r E [-1, 1], ba E B bv. E BV 1l++1) bvv.t+ B(f+"!!
To tackle the uniformness with respect to 0, we consider an e-net θ the Euclidean space. In particular, according to Example 5.8 of Wainwright (2019), if O is bounded with radius R for all t, then the covering number of θ2 in the norm is not greater than (1+ + 2/t e )d We let N(c, Ur e))
denote the corresponding covering number. In addition, the uniformness with respect should also be considered.
Below, apply standard union bound with the Lipschitz property of V.,N derive uniform law concerning / and t.
We first consider the Lipschitz property for the population version Vr:
V. De byver,,
(b Drv.
= =I(bv, - (Re + (1 - bVV.e+1Te. T (bVV, - (Re + b1. - fl
-I(R, bv; ( (VOTO. VorTe) (bVV;4+1TO, boV.
<(I[RRe bv; ( V VorTo))lle= |1(bEV.++TTO (0; - V o ||e + MBLTO. TTo =Mol|TT, Vo log no.
oे V log To; ||e- + Mg (To Top
=Mol|Te, Vo log ne. ne, V log no; Te, Vo. log mØh To V log noz 11 + MBlTO, TTp
<M&( log Te. Vo log Toy 11e2 + || IT, V log To; To; V log Toy (lea) MEl TTp
<M&(I log Te. Vo log Toy |lea + To. Top Vor log Tey (lea) MolTO, Tep1
(79)
By Assumption 5 b). we have
[/ log To.
Ve log 51 0flles.
(80)
By Assumption 8 have
[To Top 11100 021le2.
(81)
for some constant B.
By Assumption 4 e), we have
V or log To S /da.ll Vo. log nop few S G.
(82)
Therefore
by. byy.e,,,,, -V,(bbv. by,t1 bvv. 6'
<Ma(IVVolg log To. Vo log Toy 11. |O. To: V log To; (1(a) + Mg|TT, Te:
(83)
<MBB110, 0,1 + M3 /e, G110, 0'l1e= + Ms 0'11e=
S0g,8,c /o. 10, 0.1e
42

---

Published as a conference paper at ICLR 2024
By similar argument, also show that
N ( b 1rv,++1,0,1) VV bov,+1,, D) Sc MB v de, 1. 0% 1ea.
(84)
Next, apply union bound given Vide -ae,-net net of θ2 For each 6s. we are able find 0 in this net such that the following holds uniformly w.r.t. 1,.., T...,T,0, 0r E Oc, f. by byV V vda
M V dyse+ b f) v (, by,e 1,
N, br f) Vr bv, b f)l
8', f) - Vb bv. b f) + LINN htt. bov,
+ (w,
V.(bov,,, bv.r+l bev.+i, O2, (2)/)
log(cITN(
(85)
Vda.
<36(G + ()M +co
)l1f222
1
N
log(cITNN
O 0r,8%)/5)
Vda,
+ (sup R. + col
)) + B,3, MBC
N
1,0
with probability at least -
Topter TN( ..,22/E)
/do,
For simplicity, we let da denote supr, SN. + co
Then we have
VV.N (V 0) (b (y. bov.41,, 0,
(86)
<36(G M dn) + 20,,3,0 MBe
uniformly for all parameters with probability least 1 C.
Next we consider the term || By applying Lemma 5 directly, and let o5 = 6N. +
(og(er() where ÓN.F denotes the eritical radius of F(() for all t. With probability at least C.
cov N
holds uniformly for all f E F(t) that
| 11 s 1111112. + 2 2d00z.
(87)
Given 86
with probability at least 1 2ç, it holds uniformly for all f E e B(+)1) bvv B((+'), O that
87
sup V (byv. bv Dov.et1,
feFO
sup by.er, 0, f) 21
fej())
S sup (V, by. btw.er,,,bvv....,.p 18 1)) + 5n)
FEF())
-X1l 2c 9.3. by 86
S sup
bov.e
1) 1) (1Ifl2,2 + gn)
feFW
1
- - + - ~ +
d + 20 3, MB by 87
$ sup
(V. byv.+1,bvv.e.,.66 + 3, Mge
JeFo
+ sup [18(2(G - 1)MMs) dn) Xll S1 + >11/1222 do SEFO
1
1
43

---

Published as a conference paper at ICLR 2024
sup [18(2(G + 1)M))+++))1)))) 6n) X11f122 + 22 211f11222 +12d0033 + 2c B SEFO
- 182 1)MBB) - 1)M8)08 + l 22d003 + 2 3, MBBE
(88)
2A
where the second equality is due v. v. bvet, bv,4,, 0 f) 0 by Assumption 4b), and the final inequality due to the fact / l2.2 {allfll2,2 - blll S a² /4b.
Lower bound the sup loss equation 71 To begin with, we define a function ft Tx, lovv V (bvv.++1: by 0)] E8 (W,,, bev; (bvv. (v, Xx]] where W, :=
(A,, O₁, H1). Then E (+() by Assumption c).
We need another localized uniform law for lower bounding the empirical sup-loss. We first define function class
(w))))) 2MB [b (err(bbb.tt,.bveee... (wi)"
(89)
bov, BB f F(9) byset E B(+11) bbv,++ E B(tt , re(-1111000))
We then notice that ,N V DVV.e,, V V.,N br.41, 0, can be written as
N Σ
- (W.))) ((,,n)
(90)
By Lemma 6 we have a uniform law for
T (bvv,
V1,N byyr
(91)
Σ (bov. -boo:W::.---.........)) ((Xe,))
over the function space E,,..
Specifically. we let Cy in Lemma be as Cg = (bvv,)(Ws) (w.) where I (bvV.(
((X)). We have lg S ZMEg (bbv (wll S 2Mg (llbvv.lllo.22 | 20,2)) 1. Also, bg is trivially Lipschitz tinuous w.r.t. g with constant 2M.. Let g" be O, and Lemma Tomnaasshon shows that with probability least Ç. 1.C, it holds uniformly for all t = I,... T, E F()), by; B((++1) .bva441 E B(f"), θ that
IMS
(V f) Ve,N dy bvv,+i, f, (V,(b,v.. 0, (. bver,,,...e,,,,...... 0,,
(92)
<36M8o5 5z)
<36MB0 (115 ||,2 + dz).
where 6 &N N
log(er T/O) and ÓN is the upper bound on the critical radius of the function
class E.
Now we are ready to lower bound the sup-loss (bvalbvv by.4,, X.] is assumed to be (1) by Assumption 4C,, we also have Le E Flt by star-shaped of F()) Therefore, we have
Since f. ET (or,
sup V Wan:bovv. bras,, beveer (L..bbbv, bevarr 0, - 11 TEF()
44

---

Published as a conference paper at ICLR 2024
Ve, by 0, f.)) Ve,n b,, 0, 1 (.25)) 22
2 bvet. bv..++,,vvv..,.. 8, 2 f() belberesbr.ett, bv,, 0, 2
1 36MMd= f2l12, + 6z)
2 1. by 92
2 W. b,..,, 0,
f1) Ve(bbv,es bv,e41, boV, 0, (.)))
11 3 -/2 (111112122 + 2 $1.ftll2.22
1
-88
2 ddo83) by (87)
2 [1fell2,2 18.M883 12. -22 36.
-/2 (1lfollB.22
1
_11.ull2222 dd003)
2
2
1 31
( 2 4
)115:12,2-
3 7 1o00
(93)
where the first equality is due
0 1 ( Ve(bbv brv 0.
Me
beit,,,bv,.ti br, (W)) - -wt)
=
2
1 " - (V:)) - Xx)((x)))
ET
(94)
E="
[llfellie]
Combining upper bound and lower bound By combining (74 88 (93). have with probability
at least 1 - -3C (by recalling that we applied three uniform laws), it holds uniformly for all f E F())
bv. (((+1) .vv..+ E B(+t1), O that
1 31
X
2 1 18M - 36MBo2 z dooz
loup-loss by 933
(95)
<2 sup
V L by. 0, by 74
tEF
18 112GG)))MM)3) 1)) + Adook + 2c,, MBc by
88
By rearranging, have
alI/a - 5
(96)
where
32
a == 2 4
(97)
b b 18MBd
(98)
and
51
c 3
4 ded3
(99)
1
(2 + 1)M + 36(2 1)MB) }oH 20
45

---

ón S sup d + col Published as a conference paper at ICLR 2024
By solving the quadratic inequality (96),
and setting À
for guaranteeing >
have
b
+
b2
c
c
+
(100)
2a
4a
a
2a
2a
Since 1lfell2.2 is exactly the projected RMSE by definition, we have with probability at least - 3Ç that
Tx,
sup sup
sup beva
(3((2
t 0, e
b 1
b
a
1
5A
18MB0= +
36MB8 +
4 dodf
31
V
3A
2
18 1)M3)² 36 |
68 + 2c 20
50 MMda + dd + (2(G d) + /MC)
(101)
[og(CTTN((
(1(2) Vde
where dn denotes sup,,9 9 NN a + co By setting e nzz and the fact that log N( Vder"" Or,
and 8= =ōN,= + co
log(o, T/C)
N
02, ()) < de, log(1 + ////do. ) we have
log(T) + dg. + log(1 + N
(102)
N
1.
Furthermore, Ve d is a high-order term and therefore can be dropped.
Part II In this part, we aim to upper bound the estimation error
Tx, (V -By8 B
caused by the value bridge functions.
The idea similar to the previous section. By upper bounding the sup-loss, we have a convergence rate involving the critical radius of function classes. By lower bounding the sup-loss, we have the projected RMSE as the lower bound. By combining the upper bound and lower bound of the sup- loss, we finally provide an upper bound for the projected RMSE. Three applications of uniform laws are also involved. We omit the proof here as it can be viewed as a special case of Part I.
We state the result here. Let My denote the upper bound for B() the projected RMSE is upper bounded by
With probability at least 3Ç,
Ix,, (bi (bW5 bV:
1 ||/eper))
sup AEE
sup b
(103)
5o Mvrx + 8elagms + Mvōr).
where
8= (((w)).)2)) + 2My
Ibv - biaebv,eti 0)] (wx))(xx);
(104)
by E B . E ((1) betth E B B(++1) 0.
46

---

Published as a conference paper at ICLR 2024
and
T [=((2))))) 2MV
lbv,lar, oc, 1-1) ReTo, (ar) or, h(-1)
Σ (v, 0--1 h4 TT, (a: oc. (11)
(105)
for all E 11, bv, E BV bv,,+1 E By 1) , θ}.
Here 6x NNNN + cov/
logle//C and dr åN, + Ingles/C) òFlde-1 = ÖN. co Novio
(ng(es/() for some constants co. C1, where 8N.N ÓN,6r SN are the critical radius of N
coy V N,
F
lde+1, respectively.
T Vv, (a, 01)] - EEn Part III. Finally, we consider | E,
Deo (a, Oi)llee.
By applying Lemma 6 with probability at least 1 - 5, we have
(a 0z)l -== E ba Oi)lle S (0 ded (Mavdodgyy
sup bov.
(106)
where 8 ag)
/o /oy/bostay
logles/() and 8 N, denots the critical radius of BVV-
(1)
F.4 BOUNDS FOR CRITICAL RADIUS ONE-STEP ERRORS
According to the previous section, it suffices to upper bound the critical radius for function classes F, F. E, N, Y. We assume that for each B there function space g defined as
G = -((ot,b-1) + g(0,, hr- 1): g hr-1) = Σ 0,, B
(107)
Similarly, define
cWVy = [(o, 12-1) + g(o,, he- = Σ
E B( (108)
F.4.1 VC CLASSES
We first consider 94,0 at each f, 0,0, which contains the function of the form "ZC+IJME (bvv,
R2 VoTO, IV.+1 VoTo, N0.9VV.44)" ft for any r [-1, 1], ft E F((), Or E Or, bvv, E B @VV.+1 E GCV and gV.++1 E ((t+1) For simplicity, we assume that all these function classes are extended to their convex hull. Then can drop the [-1, 1] here. Also, 2(G + 1) is scaling constant as defined in the previous section. Without loss of generality, we drop the constant MB and assume that all functions involved here are uniformly bounded by 1.
Suppose that FF(),s B(t),, G&t"") g(ttl), are the e-coverings of the original spaces in the l norm. Then there exist (fr. bov,, Ivv.4 Iv.+1) F00,e F(0,,, following holds.
((+1),, g(t+1). such that the BLt, g gy
For any fixed have
I1(bvv, R₂ VoTO. - -V. VoTe. T0. fo
- (bTV. - R. VONE :v.++ VOTT T0,0vV.+11" Felloc -R.JVVAHH) ' fo)llo + +I((bvv. - VVVO 9V.4+1 VOTO. To..vV.et1) fe-
<11(bov,, - RR V - -V.++1 V DOTA,
(boV: Rs VOTE -v.++ VOTS. - Jallbo
47

---

Published as a conference paper at ICLR 2024
<l((f f + |l(bvv, VoTo, 9V,4+1 VoTe. T0.0VV.142)
(bvv Rs V. VOTO - Gv VoTo - T6,
SII(f bo). + | bvv, + V de, llu Iv, 11avve+1 -VV,,411lo0, Svdell(J 1oo000 + dodl - bov,elo,,0
+ GV 1l gvotello + dellovv,.e 9vv,4411o0.00
SeI <cIvdes dec
for some constant C1.
We notice that the coverings involved above do not depend 0. Therefore, F(th///vve pft)./// x ((tt)).//e /i x ((tt+))//a /d is net that covers Q4,0 for every 0
O
Let V denote the VC-dimension of function space. Then we have the following result.
According to Corollary 14.3 in Wainwright (2019). C.2 in Dikkala al. (2020), Lemma D.4, D.5 in Miao et al. 2022). we have with probability at least S that the following holds
(B,F)
log(1/C) N
SupôN, S doy
N
(V(J))) de+1, م= {
de+1. و-
where F) denotes max
Similarly, we can get upper bound the critical radius for all the other involved function spaces by using the same strategies. However, point that ōn is the dominating term. In particular, by using covering numbers, we have
(B,F)
log(1/<) N
EN.5, S day
N
and
(FF) N
log(1/{)
NN S
N
For more details regarding bounding critical radius by VC-dimension, readers also refer to Lemma D.5 and Example in Miao et al. (2022). which focuses on the off-policy evaluation given one fixed policy. As side product, our result for estimating the V-bridge functions recovers results in Miao al. 2022). Moreover, have extra dde used for policy optimization.
Recall that
log(T/C) + d, log N
8n S oN + co 1.0
(109)
N
Consequently, we have with probability least 1 -
| (bv.. Tie 6 0)
byv.
(A( S MEdeT
log (ciT/C) log
N
where T comes from T applications of Corollary 14.3 in Wainwright (0119).
By similar argument, have with probability least 1 1-
|xx, (B -B73
|I lepee S VMTT /doy
log (cIT/C) (FF, BB) log N
N
When B and F are not norm norm-constrained (Miao et al. 2022 we need to consider || ||I and || ||=- In this case, with an extra requirement boundedness of conditional moment operators w.r.t. l| and ||.,, an extra factor T occurs. In this case, we have
Tx, (EV. Bag 6 0) beers p2p S MEdeT?
log (cIT/S) BB) log N
N
48

---

Published as a conference paper at ICLR 2024
and [xx, (br 8) - leaper & M Vday
log (TT BB,,BBBBB8) Bog N
where vMB is due to Appendix B.2 which implies Mv x v MB..
F.4.2 RKHSS
In this section, consider the case that {
(F(²) de de+1.7
{ ( de+1.2
de+1.T g(t)
j-
are all j=1+t
j=1,t=1
RKHS. Typically, we need consider sums of reproducing kernels (12.4.1
Wainwright 2019)
and tensor products of reproducing kernels (12.4.2 in Wainwright (2019))
We consider 24.0 first, which contains the function of the form r (((G+))Mg (bvv, Rs VoTo
@V+41 VeTe, - To..vve++1) ft. for any E [-1, ft E F(l) 0g E Or bvv. E BLy SVV.+1 E g(v"") and gv.++1 gl For simplicity, we assume that all these function classes are extended to their star convex hull. Then we can drop the E [-, and To here. Since VaTo Tg Vo log Ta
which is also bounded by G, we can let g(++1)
{G g-g E g(tt))). Also, 2(G + 1) is scaling constant as defined in the previous section. Without loss of generality, we drop the constant Mg and assume that all functions involved here are uniformly bounded by 1.
Then 2r,0 can be expressed as
{(h) - h22 h2) J E() by E star(B hg E star(g(+"), h2. ((++1) Vj = 1,.... de}.
We assume that each star is an RKHS with common kernel K8 for each j = 1, ..., de. Similarly, star(g((v) ) has a common kernel Kg. for each j = 1,..., de. ((+++)) has a kernel Kg.v. Finally, the kernel for the test functions is denoted Ky.
Then according to 12.4.1 and 12.4.2 in Wainwright (2019), 24,0 can be expanded as an RKHS with kernel Kn = プ de
(KB + Kg.vv Kg.v) & Ky.
We use {-) to denote sequence of decreasing sorted eigenvalues of a kerne.. Then ac- cording to Corollary 14.5 of Wainwright (2019), the localized population Rademacher complexity should satisfy
(x S
min (Ag(Kn), 83}.
(110)
Furthermore, by Weyl's inequality, we have
de
25(Kn) = 2イ
KB + Kg.vv + kg,v) 8 Kr)
1=1
((K5 + Kg.vv + Kg.v) @ Kx)
5 de max
[ي + Kavvv Kav) + KaVV + Ko.v)d (Kz)),
(111)
We consider the following assumption for measuring the size of RKHSs.
Assumption (Polynomial eigen-decay RKHS kernels). There exist constants OKg
2.
aKo.v }. 0Kg. > 1. 0K₃ 5. > such that >y(KB) < -a (y ej 22Kg, ov, (K < ej -20kk and (K(K)) < cj-20k7 for every j = 1,2,
We note that the polynomial eigen-decay rate for RKHSs is commonly considered in practice (e.g.
a-order Sobolev space).
49

---

Published as a conference paper at ICLR 2024
Under Assumption we have
XK(Ka)
Sde max {> T (KB) + 1 (Kg,vv) + X 1 (Kg,)) \ [/g (Kz)}
Sde max (3de) max (Rgg v. (g, (ej 2008 + cj va + ej 2 do
20x5 ej -2ax)=
(112)
For clarity, we dmax denote max aKg.v (K) and let amin denote minfakg- V (Kg }. Then we have
Xy(Ka) & max dg 20max 220mia 1 142Kyy j- 1-2Ky }.
de
(113)
Consequently, according equation 110equation 113
sufficient conditions for
R.v (6; (6,0) $ 8²
8
min { (dg
(21+20mox 2-20min 82) S 5 akz > Omin
N
and
min 142a8y j- -aax, 88) 68 if akz S amin
de
By some direct calculations, we have
1 20maxx
min { 20 j- 20 82) S
20
(114)
N
N
and
8
1+2aks 2220, ,82 8
de
142aK
min
dg
S
(115)
N
1420 Ky 2-1/0Kz
1422
2+ 14177mia
Therefore, we have 6
I(ak, S amin) +
I(ak, > amin).
N 2 1/ukz
2
1+2Kg
142omax
We notice that N I-1ooKy
Ilakr S amia))
I(ak, > amin) is also an asymptotic upper
bound for E, and JZ()) Consequently, we have
Txx (B Dae 0) B ) $ Mgh(da)T Vlog (c: (CTT N
1
Zermanx (1/wk (7/0min)
1420gr
where h(da) max(de, dg Qmin = min (aKk. a.o. ako Similarly, we have
241/0K
d2 3-1/0mmn
with Qmax max a.a.v v. ev and
| (0, 3
I S v VMT2 Vde Vlog (ciT/S) N
maxl (1/ 11/ 4/
50

---

Published as a conference paper at ICLR 2024
F.5
POLICY GRADIENT ESTIMATION ERRORS
Recall that we have
[Vg)(Te) VoV(ma)l
T [x,, ( (V.eea D vv,,e11;0) bev. (0)
(116)
Σ
Σ GooG
Ede,7 Tx, bV., (6 V. b9:s
<2(pmh)
vv 01)] -
E=
bev. (a, 01)lee
Plugging in the results from section F3 have that with probability at least C.
VoV((TT) (OV(TT)) 10
log (FF B) log N
Tmax
N
log (T/S) (FF))(FFB)) B8) log N
(117)
+ G
de, Tmax M5T de
N
log (T/S)((F, (F,((FF)))))))))) Bog N
20t Tmax
since MB T
{ |=ر {v(B detti, j=1,t=1}
det
where F), denotes max
In the more general nonparametric function classes RKHSs, have
(oV(TT) VoV(TT))le
SC Mig Vlog / N
N F1 1/7mmn
(118)
T
+ CrrG
de, Tiax MMT's V de log (cTT/)) N
N 2tmmx((1/K M/mmnn
Vlg (cTT(()) NN 24max mimm
1420Kz 7 2fllagy
1+20max
where li(d)) = max(de, de Omin min((aka: (KK,, (Kg measure the eigen-decay rates of RKHSs. See section F.4.2 for details.
d
Here Omax max maxfakg: aKg v (Kg sv
G PROOFS FOR SUBOPTIMALITY
In this section, we present a complete proof of Theorem 3 We first assume that we have access to an oracle policy gradient that depends on the unobserved states. Then, by borrowing the analysis of global convergence of natural policy gradient (NPG) algorithm, we establish a global convergence result of policy gradient methods for finite-horizon POMDP with history-dependen policies. Then we establish an upper bound on the suboptimality of ā by replacing the oracle policy gradient with the estimated policy gradient.
51

---

Published as a conference paper at ICLR 2024
G.1 AN AUXILIARY PROPOSITION WITH ORACLE POLICY GRADIENTS
In this section, we present the global convergence of the proposed gradient ascent algorithm when the oracle policy gradient can be accessed in the finite-horizon POMDP. The idea motivated by Liu et al. (2020) which is focused on the infinite-horizon MDP case.
Proposition Given an initial 8(0,, let { K-1
k-1 be generated by @(k+1) B(k) +
v gcw) ((TTO))). Then, under Assumptions e) and (b-)), we have
K-1
V(TTO))
(TT(()))
K-1 1
T
3m K-1
<G
V de, (w (o(k)) v Vayo V(TTOw))))e +
Σ
IV oos ((TOOO) (119)
K
2 K
K=
k=
E
[KL(T"( oz, (1-1)))TTTT h(-1))] Eapproz
Kn
In Proposition T. the first term measures the distance between the NPG update direction and the policy gradient (PG) update direction, which can be essentially upper bounded by the norm of PG according to Assumption (].). Therefore, according to the PG update rule, the first term converges because g(k) converges stationary points. For the same reason, the second term also converges to O. The third term is (()), ), and the final term is an approximation error.
Next, we present proof Proposition
proof Proposition 7 shows that
We start from the performance difference lemma g for POMDP, which
T
V(TT.) - (TTO()))
E
tr. [A700)) (ar, Or, Sr, ho-1)
(120)
1=1
Let wh be the minimizer of the loss function defined in Definition D.2 for given ((), i.e.
w (k) arg min
(ANoun (at, oc, 82, he-1)
E
(121)
w (e log x oee (at oe, ((-)))))) )?)
Then we have a decomposition of the difference between policy values.
(TT.)) (TTOCA))
T
EE ( (a.
(Agott) 0r, he,
E
(a he
(A,000) (ac, 02, 01, (x)
(k), (ollTToooo Vo
lolog To.
(K)
t=1
((vo.t)]T T log To.
E
(0..0 (0..0e.8 kt
T
Aga (alt)) (ar, Oc, St, he-1) 1) ( T log To. (K)
(ar be
(a)
52

---

Published as a conference paper at ICLR 2024
T
(oL by 10mp [1m_7] - w/( Ve log 0.
ba [10f (2) To log To
(1)
(122)
(e)
We analyze these three terms separately. For the first term (a), by applying Jensen's inequality E[X] $ v [|
for each t 1,.., T, we have
(0)
(k) (ac, oz, St, h2-1) 1 (wit.) Ve log Te.
Te. (1)) B:0. (AATatt) (1, (w)) Volog
)
21
B
1=1
Sapprror (by Definition
D.2
(123)
For the second term (b), by Assumption fc), we have
(6)
[wu! - ( T Ve log (A)
E 8t te
[(w - -w (x)) T Vo log 88.
(1)
E 1h [[(w//] w!hh )|ee= Vo Volog To,
(((
(6) llea
(Cauchy-Schwartz)
E aa bu 1)-Pf00 [[!!
(K) w. (*) )1ee (2 de, Vo log mp. 11
v de (w w/ (b) (Assumption Fe))
For the third term (c) Σt E (a or Me [wwett) Vp log To. we employ B-
(k)
smoothness of log(To), i.e. Assumption (()). According to Assumption ()b and by Taylor's theo- rem, it holds that
log no; (at or, log Te. (as or, or, (1-1) V log Te, (as I or, 1) (0) 0.) < 2 for each as, or, h--1 x O H.-1.
B 10: 0,112-
Let 6r be 0 (K++1) and Or be R( here. We then have
To(e+1) (at I ocs he-1)
Vo log n. )no (a: or h--1) (o(t+1)- 0.!)
8 110
- 1 + +lo
2
Tole (at oc, f1-1))
(124)
53

---

Published as a conference paper at ICLR 2024
Recall that 0f++1) 0(-h) mpe (K) have
by definition. Plugging this term into the above equation and
To(e-1) (as Oc. h1-1) Tg(h) (at Oz, 12-1)
Vo. log mptt (at I oz, ho-1) (u(h)) I 11 2 | (b) 1 11:a + log
(125)
The third term Ei=1 1 ((w)tt) Vo. log T8. can then be upper bounded by
(k)
[(voftt TVo log To,
(k)
T
To(++1) (at Oe, hx-1)
B (a 17
"1 2
1
(k) 12:s + log
by equation 125
To(h) (as | oc, he-
E 10- [KL(T" (- oc, (e-))
oz, h(-1))
1=1
KKL(TT (- oc, (111 or, 11))
By
m 1
(k)
(126)
where we use (L(pllg) Ex-pl- log ((x) p(z)
in the last step.
Now combine these three terms (a)(b(() together and average them with respect to k. Then we have
1 K
V(TO.)
((TOW))
K
k=0
K-1
(V(o)) (TT(())))
K
K-1 T
Seapprox + +G
de, (w w(()) (2) )eea
K
1m
t=1
K-
KL( Or, (4, O,, 11--1) KL(*'( Oe, H4- O H+-1
k=0 t=1
K-1 T
7
Σ
3
mml
(2)
1|2a
2
k=0
(127)
where the third term can be simplified by changing the order of summation:
I
K-1
E Boo [L((T' (- hr, (- oes ht))))
K=0
(L (-1 ocs he- MTTTREN or, he-1)
B B he 1 [KT((T (: he hc,))))))
(T( (. ot, ha (,l::e-)lFFFce or, he-1)
54

---

Published as a conference paper at ICLR 2024
T (os hn Npp6
[
oz, h 1)00 1 h4 hz-1) (by telescoping).
K
In summary, we have
K-1
V(TO-)
((TOW))
K
k=
Capproe +
de, (1 (k) w/ )
11e=
37
2
[KL(TT()) oz, 1/ 1 ot, 14-1)))
K
G.2 PROOF OF SUBOPTIMALITY
In this section, we present proof for Theorem by leveraging Proposition [ and Theorem 2
For clarity, we let let Es := V pie) (TT(()))) V V (Tor)) ) where V goc (TTgge)) denotes the oracle true policy gradient evaluated at ((k) and Vaca (TT(()) represents the estimated one from the min- max estimation procedure
By setting wi as V oge)
(TTT(o)) in Proposition we have
V(To-) 1
(TT())
K
km0
0
K-1 T
Bn 1 K-1
Seapproz +G
Σ
v de, (w (O(k)) -V Vol ((TT +
Σ V Bls ((TTOC)) 1|.
K
2 K
(a)
(6)
E Boode 1)=
[K[(T (- or, h 1) ot, h))l)))
Km
t=1
(c)
(128)
We first upper bound (a) we have
K- ΣT / /o (w -V V Mee To this end,
(a)
K
T
G
de,
(w [. (B(+)) - V
K
k= 1=1
<G
max
de,
(
Vo(to VTT MMl
K
maX:=1.T / de,
K-1
T
<G
|V )(و) ((TT)(N))
V m000 V( (T
K
k=0
55

---

Published as a conference paper at ICLR 2024
+ G
max 1:T
de.
K-
[1 (B(6)) - V 6500) V(T (TT )
(129)
K
k=0
max V /de,
<G
/T
VV ocks (TTT(())))) - V 0(0) ((To(t))))
K
k=
+
G
m de.
Kw (0l4)) (0(k))
V V(TTOa))ll
k=0
m&x
I:T
de,
VT
K-1
Exlle +
G
max
de.
K
Σ
T
( (0(1))
V Vogo ((TT())lle
K
K
km0
k=
==1
(a.1]
(a.2)
We note that (a.1) is a term caused by estimation emoo. Now we focus on (a.2). Recall that (o(K)) is defined in Definition D.2 which is the minimizer of the loss function related to com- patible function approximation. Here we provide an explicit expression for w (0(*)).
Given a parameter 0, we notice that minimizing with respect to w = vec(w1,. WT)
Blooorsihh Duae [AA7 (ar, Or, St, h1-1) w, T Ve, log ne, (az Ot, hz- 1))
equivalent minimizing
E 110 [A7 (ar, O1, 8t, w, Vo, log ne, (at or, ho-1))
for each 1 wec(w-,1 (0), ...,,.... (... (()) with dimension dg. Since it convex quadratic optimization, we can get (0) by directly setting the derivative to be zero. By calculating the derivative of the loss function at with respect to we and set it as zero, we get
T....T T by concatenating all the (.) into vector (0)
E (a 1
[A (az, or, St, 11-1) Ve, log ne, (at | Ot, h1-1))
E -a 13
Va, log To, (at or, 11-1) Vo, log To, (at ot, h4-1) Wt
(130)
=E - =F(()),; (by (ssumption
V log na, (at or, h1 Ve, log TT. (a, or hy
Wr
In addition, by the expression of policy gradient from Lemma 10 we have
T
(mo)
E Vo lo no, (A, Or, Q," (A,, St, Ha-1))
(131)
Since Easa Te, (al oc, hx-1) 1, we can also show that
V.V (TT)
log тe, (A, Or, (1, A5 (A,, Se, H(-1)] Vo To Σ
(132)
[=1
by simple calculation and expressing At = Qt - 1/2 where V does not depend on a, Therefore, we have
T Σ
Vo, (mTo
Te VV, log no, (A, O., H.-1) A55 (A,, O., St, H.-1)]
(133)
t=
for each 1 1,...??
56

---

Published as a conference paper at ICLR 2024
Plugging equation 133 into 1300 and we have
Voo) = Fe(
(134)
Therefore w!th (0) F. (0(A)) V A V ( (maw)) for each 1,... T, where the non-singularity
of (0(4)) is implied by Assumption c). This is actually a direction for natural policy gradient (Agarwal al. (022))
Consequently, we have
[| (Qck)) - of V(T poooe
=I|F,- (8( ggn (T V
=I(47 (00k)) - 1 0f V (TTC)) llez
(135)
<1((F] (0(k) 1)2 ((+)) V (Tac))) lee (lll2 denotes matrix 2-norm)
<(1FFF (8 |||2, | V 0 V (TTCE)) |lea
) 06 V (TTTO))
<(1 + 1
lle by Assumption ((c).
Plug equation
135
into
129 and we have
(a)
S(a.1) + (a.2)
=G 1.. v de.
VT
Ex aa + G
max V de.
K-1 T
(k) (0(())
oog (TTT())ll
K
K
m1 v de.
K-
max v de.
K 1-1- T
<G
[xlle + G
(1
>/ )mw) V (TTgL)) llez
K
K
k=0
k= t=1
max V de
K
max de
K-1 T
VT
[x Ø + G
FV 0 V (TTCC)) lle
K
K
k=
k=
11 Vde.
K-1
| + max dde,
K
<G
VT
(1+
VT 1
Voo 0oo (Tow)) ) ll.
K
K
(136)
Now need to upper bound 1 Σ
K-1 |I Voun (TT(a)) l1. We will relate the gradient with the k=
improvement in each step. Since (TTo) is assumed to be L-smooth w.r.t. 8, then according to lemma
7 we have
(TTOT+))) - V(TO())
L 11( -100++1)00011111
2 (V (ce V((TOC)), 010+1) (((+0)) -0())
0
-n ow: ((TOWN)) V Vaw (TTT())))) - TT2L,
/Voces V(TT )12
2
- oow ((TTO(N) ) V B()) (TTT()))) )} + 77 V )c (TTOW))) Voc (TTT()))) - Voceo ((TT()))
722
V g00) ((TTA())) ) - V (TT(O) + V Dce (((T(()) )
2
1/2 [2| Exll + 2 ocss (TTO(N)) )l²²
2nl V 000) V( \1
"d ( V ocs ((TTON)) )11 | 1|2)
1721, (2) 1all2 + 2 0c (TTOOC)) )|2)
=n/ (00) (TTTO())) M12 " D (TTOOL)) 2| Frx (122)
17
| 80l V(T 1 2 T, 11
(137)
57

---

Published as a conference paper at ICLR 2024
Therefore we have
K
Ln²²)
pee) V(TTO()))
K
1 K-1
1 K-1
Σ (V(To))+))) V((Tocn))) 2 Lnj²)
Σ
Ex
(138)
K
K
km0
kmm
k Σ
(V(Fa(n))) - V(TT((o)) +12 + Liq²)
1x
K
k=0
Let IT. we have
1
K-1
K-1
16L K (M(TO(K)) - ((TT(O)) )) +
3
E 11
(139)
K
K
k=0
Therefore, the following holds
V occ (TTOO)))
K
K
V V(TT((H))
(140)
K
k=
k
<
(TTOC)))))))) - ((TT(CO)) )) + 3
Σ
K
k=
Plug equation 140
into equation 136 and we have
(a)
<G
maxt
dde.
T
K
Exlle
=G
maxx L:T
/de
(1+ 1 |
K-1
V 0oe) V (TT(O) llee
K
K
11 V de. VT
K
SG
Σ
1Balle
K
h=0
K-1
+
max 1.7 P
V do.
1 +
16L((((TONN)) - V )) +
Σ
|| 11
VK
k=
(141)
We also have
(b)
K
3n
V Vic (TT())))
2 K
K
3n 1
V / (TTO()) - ((TOE)) + Vow (1
2 K
(142)
3n 1
(2| 0(h) ((TT())) - Vocks ((TOCCe) )11 2 2/1V (oc) mck) ( 112)
2 K
3n 32T
Bn 8 K-1
(V(TOL))) ((TT()))) +
Σ Ex
2 K
2 K 0=0
58

---

Published as a conference paper at ICLR 2024
where the last inequality is from equation (339) Combining all the results, we have
V(TT.)
max
V(TT())
O:K
K
<V(TT=)
V(TOON))
K
k=0
Sappprox + (a) + (b) (c)
1 K-1 T
.n K
Eapproz G
de, ( ( V )ow p(T ))lle +
Voci V(TTO()))
K
2 K
km t=1
R 0=
E
[KL(TT( Or, hy (| Ot he--)))
Kn t=1
Sepprro
ho 11 [KT((=( Oe, 1e, (: 1 11-1))
Kn
t=1
mT v de. /T
K-1
+ G
Σ
|xllez
K
k=0
K
G max V de, (1 + 1
VvT
16L(((TT(N)) V(TT(0))) )) +
|
by [41] for (a)
p
VK
k= 0
(+)
Bn 32L (V(To())) - (TT((O) +
8
K-1
+
Σ k=0
|x
by 142 for (b)
(143)
2 K
K
We note that equation 143 provides an upper bound in terms of all key parameters. In addition, (+)
the dominating term. We now employ Theorem 2 for explicitly quantifying [x According to Theorem 2 we have that with probability at least C. holds that
log (T/S))(FF))
sup
E S
Tmax MaMedy
(144)
N
k=u:k-1
For simplicity, we can drop the terms y(F, B) and My, and get
log (T/C) N
P S Tiax T Made
(145)
k=0:K-1
with probability at least 1 1-C. Ç.
Then, we have that with probability at least 1 5
(TT-) V(T)
((+) + Eapprox
max Vde, (1 1 -V 11111
dde (1+ -vVT
+ max E=l
1
VK
VK
log (T/C)
K
Tmax Cro Made
Eapproz
(146)
SvdaVT L
M2 2.5 log (T/C)
+ VTVR22
max C
+ Eapprox
VK
N
SVdgVT L
log (T/S)
+ T
Made
+ Eapproz
VK
59

---

Published as a conference paper at ICLR 2024
where the last inequality holds if K N. In particular, we have x T and MB x T according to Appendix B.2 B.3 probability least 1 C, we have
Consequently, with
T.3 max
log (T/S)
V(TO-) - V(T) -(F)) X dd
C
T T dg
Eapproz-
(147)
VK
VN
Remark: we can consider specific examples such as VC subgraphs and RKHSs for analyzing supk=0:k- |E See Appendix C for details.
H PROOFS FOR LEMMAS
H.1 PROOF OF LEMMA 3
Let Tij denote trajectory from to j. i.c. Taj == (S, O,, R..,.,, Sj, Aj, O,, R2). Then we have
VoV(Ta)
T
=V
Σ
R
j=l
T
V
Re)ddP (TuT)
RidP"c(TTT)
8
RidPTe (Ti:t
0
Rs V.Vor Roddo (T:))
Rs Vo log pn (T:t)d (Tia))
Σ
R₂
V. log Tay (Aj 0,, H Idd by equation 148
j=l
To
log To, (A, (A₂1 1g,
j=1
where
Va log Pro (Tia)
Vo log
p(R; A.) O, H,-)) SS)p(S: | 4-1)
(148)
==1
Va log n.. (Ar O, H,,1)
1=1
with p(S, So, Ao) (Si).
60

---

Published as a conference paper at ICLR 2024
H.2 PROOF OF LEMMA
We provide a sketch of proof here. Readers can refer to Wainwright (2019): Maurer 2016): Syrgkanis f0r more details.
Poster
Define the following function indexed by E (0, 1]:
(r) = sup (mF)
1111122 - 11
where (2(r; E EF11f122 s
Let & be the event that the inequality 23 is violated. We also define an auxiliary event A(r) ==
(r) 2 dr2). J. By a contraction argument from Maurer (2016) and the Talagrand's concentration inequality (Theorem 3.27 of Wainwright (2019)) we get the tail bound for (r). Specifically, we have (r) 2 25 I C1 cxp(= for constants 61, C2. Finally, according the proof of Lemma 14.8 in Wainwright (2019), we get that & is contained in A(r), which has exponentially small probability.
H.3 PROOF OF LEMMA 3
Recall that we defined
T
0700 (s) az. Oj, h1-1) TM
Σ
Rs |S 8j, A₁ = aj,
aj, Hー-1
hj-1, Oj oj].
(149)
t=j
and
(1))) = To
Rτ Sj s, H, = -h h, = oz].
(150)
tmj
Then notice that
(sy, Oj. h5-1)
T
RR Sg 8j, h1
t=
T
= E
R₂ S₁ $j. = h og. -, = =s H5-1 = h Oj = 0j]
-E Te
110500 os o3
(151)
and
A8, H,11)
=R[R
Sj. A,] +
Rí Sj. Aj. H3]
T
RE[R, | (S, + [
Re 15,1,
t=j-1
-E[R, (8,,A1) A, E
S1+1 0,+1, A441, H4] S,, Ay, HH-1,
EE( |S, 1,1 + [Q] | 0 H,) | 4,, H,
=E[R, S, + 1 O,, H]
(152)
61

---

Published as a conference paper at ICLR 2024
For clarity, we denote E[Ry Sy s. Aj as a)) Then have
(11, - Vi" (11,
(E) (S2, O2. Hi) A1, $1, 01l
(S2, O2, H1) A1, o1] V/ (1),
H| 4 4
(S2, Hi) A1, 01]]
-1 O2 (1 A1, 01] V/' (11, by 151 [52
(2, (5. 02 H1) A1, s1
4)) (82, 02 H A1, 01] Vi (1),
(S, H1) 1/ (52, 02, H1) A1, 01, E (QT (A1, 81, 81, 01)] - VT (s1, by (52
-V" 02 H1) V (S,, H1)
81, o1] [ (A1, (1, VT (81,
-V" 02 (1 - V/2 (S2, 02 H1) o11) (A1, $1, 01) by Definition D.7
-V (S2, 02, 111) VTT (S2, 02 H1) 51, 01.01] - (A1, $1, 01,01]] ] by law of total expectation.
(153)
Next, we consider 1/2T (S,, 02 H1) - V (52, 02, H1)-
(S,, O2 H1) V (S,, 02 H
= (S2. O2, H1 - E0 (r2 A2) + E[V3 (S,, 03, H2) A2, Oz, Hi] S2, Oz, Hi]
+ E A2) + EVV (Sg, 0z. H2) Ag, S2 O2. Hi]
S2, O2, H1] - V/2" (S2, 0z. H4)
=E" [E[V (S,, Oz H2) V3" (Sg, O2, H12 A2, 02 H1
S2, 02, H[]
+ - (r2rr A2) + EV (Sy, O3 H₂)
A2, S2 H S2, 02, H1] - V (S2, Oz. H1) by [51 [5T) 152
=B" EVV 03. H2) V3 (S,, 0g H₂)
A2, 02 H1] S2, O2, Hi]
+ E (A2, S2, 02 H1) S2, O2. H1
(S,, 02 H1) by 152
[ O3, H2) V (83, O3, H2)
82, O2, H1] E [A (A2, S2, O2, Hi) S2, Oz, Hi]
(154)
Plug 154 into 153) and we have
Vi (81, 01) - VI 01)
=E" (Ss, O3, H2) - V (S,, H2) 81, 01] + EE"AA"" (A2, S2, O2, Hi) 81, + + [AT' (A1, 01)
(155)
where we have used the fact that given (S2, O2. H1). (S3, O3, Hz) is independent S₁, 01 and the law of total expectation.
Repeating this procedure and using (S O441, H+) TL (S1, 0,) (Sk, Ok, H4-1), we have
(i( VT (5),
Σ
E [AT' (Ai, S,, O, 11,-1) 51,
(156)
t=1
By taking expectation with respect to S1, O1, we have
((T)) V(=) B (A,, Oz, H.-1)).
(157)
H.4 PROOF OF LEMMA I0
Proof. Let TH. denotes the trajectory ($1,01, 01, f1,...,.., ST, or, ar, rT).
(TV(TT)
62

---

Published as a conference paper at ICLR 2024
VoE R
Σ
R2
T
=Vo
Ri RP) (TI:T)
T
R₂) Vo log p (T::T) ) (T1:T)
=E
R
Vo log (A 1
Oi, Hi-1)
by Lemma
86
0 log t0, (A, 0s, H;-1)
Rg
by changing the order of summation for and
T
T
n0
Oi, H1-1) V (o, |
Σ
Rr
1=1
B
ET
Vo VologTo,: Oi, Hi-1)
R₁ St, As, O,, H:-1
by law of total expectation
E
Ve log (Ai Oi, 11-1)
Σ
Rs St A., Og H4-1
by measurability
T
B no
[ To O, H,-1),, A,, O,, H1-1)] by definition of Q,
(158)
H.5 PROOF OF LEMMA II
proof of Lemmal 17
We prove it by induction. At the base step t T, we have
Te [T
ST. HT-1]
=E E
E
Rr
SI. HT-1, Arl
Sr, 1r-1, Sr, Hy-1l by law of total expectation
E
E [RT
Sr. HT Or, = a) ne, (a HT-1) -1] ST, HT Orl | ST, HTT
E
E RR
ST. 1r-1::0,,1 = a} ner (a Or, HT-1) ST, Hr-1
a
E
Σ
E [T
Sr. H7 11 a]
n.r (a Or, HT- 1) ST. HT
by Ry 1l Or ST, AT,
a
E [Rr]]
Sr. H1 - Ar |. (a Or, Hr-1) Sr. H
E Rr -T A ne, (a Or Hr-1) Sr. H Ar al by Or 1l Ar ST. HT-1
Σ
E [RTTe, Or, HT-1) Sr, H Ar = a) by Or 1L Rr Sr, Ar, HT-1
Σ E (Or, HT Sr. HT-1, Ar
by 33
63

---

Published as a conference paper at ICLR 2024
V. (Or, Hr.. Sr. Hy by Or IT Ar Hr-1
B
by (a Or, HT) ST, -1
(159)
According to the above derivation, we have shown E. ( 11,,,,,,,,,, =
Ei=s Rr Sj: 1 when = T. We proceed with the derivation by induction. Assume that E EEn by (a, Oj. H1 11) Sj, 11 E E Re Sj. H3-1 holds for j = k + 1, we
E
will show that also holds for j = k.
For k, first notice that
T
Σ Re Sk: Ha-1
= 18 [Ra Sk, HE-1] R
Σ
Rs Sk. H Ha-1
Next, we analyze these two terms separately. Analyzing the first term is the same as Ene [Rr Sr, 11 by replacing 7 with k.
Te
R
Sk, HR-1]
E To
[E RR
Sk: Hk-1; Ok, As] Sk: H 1, Ok] Sk, H4-1] by law of total expectation
=
E [Rx
Se, Hk-1, Ok, A To (a Ok, Hk-1) Sk, HR-1, Ok] Sk. Hk-1
E
E R
Sk, H H--1, Ok, A = al no, (a Ok. Hk-1) Sk, HK-1
E
E [Rx]
Sk. Hg- A4 al no. (a Oz HR-1)
Sk. Hk-1
by R& 1l Oz Sk, Ag. HK-1
E [Ry St. H4 A+ = a
Te. (a O Hx-1)
Sk. Hk-1]
E [R St H Av = a] E no. (a O₁, Hx-1)
S₁. HR-1, Ap = by On 11 Ag Sky H
E RRATO Ok, H+-1) Sk, H A = al by O2 Rs Sk, As, HK-1
Oz, Hb-1) Sk, H A a) E RRATo (a
(160)
For the second term, we have
R₁ Sk. H4-1
T
=B
T
R₂ | Skt1, H Su
Se, Ha-1
by law of total expectation
1=++1
Σ
Ry Se41, Hx
Skk, He-1 by (RoJT-t41 LL. Sa S Hy
[==+1
64

---

Published as a conference paper at ICLR 2024
1 V,++ (a', 0k-1, Hx) ) 5k+1, Ht
Sk: Hk-1
by assumption in induction
=E"
Σ V ( (k',0--1, Sk+1, HR, Sk
Sk. Hk-1
Ok+1 -T Ske Sk+1 Hk
=E
+ (a', 00 H&) Sk, Hk-1
by law of total expectation
(161)
R
Vik++ ,a', 0k-1, H&) Sk, H Ok, A&
Sk. H Hk-1
by law of total expectation
] bv. V 1 (a', Ok+1. H&) Sk, H Ok, As = a
E
E
To. Ok. H ) Sk. H
a
E
E
Th V (a', Ok+1, Ha) (a Ox, H
Sk H Oz. A4
Skk Hk
(by measurability)
E
E
Vik+1 HT) Oz. Hx-1)
Sk. Hg- Ok, A₁ =
Sk H H
E
E
6 W.tti (a', Ok+1, Ha)oo O2, Hx-1)
Sk. H Ok, Ax = a
Sk. 11
a
(by
IL Av Sk))
E
6. W (a', Ok+1, Ha)TO (a Ok. Ha-1) Sk. H4- As = a by law of total expectation
Combine equations [160 161 and we have
E
Σ R4 Sk. HK-1
T
=
[R Sby Hk-1] + 19
Σ 1=
Rs Sk, Ha-1
[RETn, (a Oz, Hx-1
Sk, Hr-1, = al
Σ WV Ok+1, Ha) (a Ok. Hk-1) Sk. H4 As = a by 160 161
Σ
E Ra Ok, Ha-1) + Σ
To D7. ( Ok+1, Hz) (a Ok. Hx Sk, H A
a
bi O2. Ha-1) Sk, H AB =a] by 133
E
E
bi (a, Oz. Ha
Sk, H by On 1l A Sk. Ha-1
E
Σ
Uo (a, On, Hx-1) Sk, HK-1
65

---

Published as a conference paper at ICLR 2024
Therefore, E Ei=k Rs Sk, HE-1 = (OR, Hx-1) Sk, Hk- also holds for k;
it holds for j = k + 1. By the induction argument, the proof is done.
H.6 PROOF OF LEMMA 12
Proof.
VOE
RT
ST, Hr-1]
VEE
E T0
E [TT
ST, HT Or, S7, Hr- Or] Sr. Hy-1] by law of total expectation
E
E
SI, Hr Or, Ar = a) ne, (a Oz, Hr-1) Sr. HI Orl Sr, Hr-1 Rr
VELE
E [RT
ST, HT,, = a) To, (a Or, HT-1) ST, HT-1
VE
E [Rt
ST, Hr 1, Ar = a) nor (a Or, HT ST, HT
by Rr 1L Or ST, HT-1
E
E RT Ar a Vo, nor (a Or. Hr-1) Sr, HT-1
|RT
ST.
B To
Or. Hy-1) Sr, Hr-1l
E
[RT]
E V (a Or. Hr-1) Sr, HT Ar = = by Or 1l Ar Sr. Hr-1
E
R2 pr -er (a Oz H
ST, H -1 Ar a) by Or 11 Ry Sr, Ar, HT-1
E V H|
- ST. H1 Ar = a by 37
bou (Oz: H1 E
by Or 1l Ar Sr, Hr-1
=E
Σ be ( a7) Sr.
ST. HT-1
According the above derivation, have shown E bivv (0j, H Sz. Hy-1
ΣT_ R4 S 1,111 when j T. We proceed with the derivation by induction. As- sume that E. (oVVV (O,, H,-1) Sj. H VoETO Et= R. S,, H holds for j = 1: + 1,
V.lET
will show that it also holds for k.
For j = k. we first notice that
T
T
VE
Σ
Re
Sk. HR- = VelE [R Sk, Mx-1] + VelETT
Σ
R, St, H
t=k
(163)
Next, we analyze these terms separately. ValEao [Rr ST, HT-1] by replacing T with k.
Analyzing the first term is the same as
VO [R
Sk. HB-1)
66

---

Published as a conference paper at ICLR 2024
VE E
E [R
Sk, Hk--, Os, Sk, 1 O&] Sk. Hx-1] by law of total expectation
V
E
E
[R
Sk. Hk-1 Ok. A4 a) no (a Oky Hxx-1) Sk, HK Oul Sky 1
VoR E
E RR
Sk. HR-1, Oz. A = _a
no, (a Ok, Hk-1) Sk, Hk-1
=VE
E R
Sk. HR-1, A2 = T O2, H Sp, Ha-1
by Rs 11 O2 Sx,, An. Ha-1
(164)
E
Σ E RRx
Sk. 11,11,111100 A = a) VoTo, (a
On, Hx-1) Sky H
E [Rg SE. H -- A a nM (a
On. HR-1) Sk. H
E [R Sy. H Ax E AT (a
Ok, Hx-1) Sk, Hg-1, Ag al by Oz 11 As Sk H
E [R (a
Oz. H2-1)
Sk H A& = by O2 TT R Sk. As. H
For the second term, have
T
VelETN
Re
Sk. Ha-1
l+=++1
EN00
Re Sk+1, Hk. St
Sk. Hk-1
by law of total expectation
T
T
Σ
Re Sk+1. Hx
Sk Ha-1
by (Rele b7 St Sk+1,, Hx
1=
Sk+1, Hh& th Wi (d', Okt1, H&)
E
Sk, HK-1
by Lemma
(165)
V.E=
E
Σ birn (d', OutI, H&) Sa+1, As, Ok, Hu-1
Sky Ha-l
by expanding Hy
Vo
2 bik+1 (a', Ok+1, Hx) 8241, axs ok, hx-1
po(s ax ok, hw-1 Sk. 1a
a'
/ V
=
Σ Wiit (a', Okt1, Ha) 8841, ak, on, Mx-1
po(8 ans Ok, hw-1 Sk, H 1) dayd
+ E Σ
6% bi (a', Ox+1, Ha) 8k41, ak. oh, h2-1
Vepo(sut1. an ok, hw-1 Sk, 1tl11ddda..... 1 doa
=7 +
where
1=
VoE
Σ
Too DVkkzaa' (a',0x+1,
Ok+1, H&) 8kt1, ak ok. hx-1 Po (8 at ox, hx-1 St.
67

---

Published as a conference paper at ICLR 2024
R
VOE
(x'00 H&) Sk+1, Ak, Ok, Hk
Sk, Hk-1
2
8 E
ba (11+4ldd,000m ,k+1 Hx) Sk+1, Hp
Sk: Hk-1
by Hr = (Ak. Ok: Hk-1)
a'
12
V E
Σ
Re Sk41, H
Sk, H
by Lemma 11
x=b+1
be DVV, (d', Ok+1, Hu)
Sk+1, 11
Sk Hi-1
by assumption in induction
n
E
b vvv O Hx) Sk+1, Har Sh
Sk. Ha-1
Ok+1
Sk Sk+1, He
b Dvv (d', Ok+I, H&) Sk, HK-1
by law of total expectation
(166)
E
b 6 (d', (x+1,HH) Sk, HI-1, Ow, Ab
Ski 1
by law of total expectation
b D (d', 0K+1 H&) Sk, Ha-1, 0s. As =
TB. (a Ok. Hk-1)
Sk: Hk-1
E
a &vv (d'0 HR To, (a) On, HR-1) Sk, HK-1 OR, As = a
Sk Ha-1
E
I
Tee I Ox+10 Ha) To (a Oz. Hx-1) Sk HR-1. Oz A
Sx Hk-1
E
E
VV. (a', Hz)1.HH)TT (a Oz. Hx-1) 1) Sk H Oz 4
Sk.: HR- As =
by O
11 A₁ S5
E
b V (a', Ok41, Ha)Te (a On, Hp-1) | Sk, 1 As by law of total expectation
a²
and
11
E
Te (a', 0k+1, Hx) sk+1, ak. oh, h
Tepe(sa+1e ax, ok, h4-1 Sk, Hy- day
E
Te Viti (a', Ok+1, Hx) sk+1, ak: O ha-1
( log pe x po) (SR+1, ags Ok, ha-1 Sk, H dss+ day
me
by (a', O k--1 Hx) Sk+1, As, Ok, Ha-1
o log (Sk+1. Ag, Os, H Se, H+-1) Sk, HK-1)
68

---

Published as a conference paper at ICLR 2024
=
Σ
t Vi++ ( 0k-1, Hx) 1 AR, Ok, Hk-1
Sk: Hk-1
V log po 1 Ak: Ok, Hk-1 Sky Hk-1)
=
b% V,A+ (a', Ok-1, Sk+1 Hi
Sk. Hk-1
Ve lolgoo((Skt.: Ag, Ok, Hk-1 Sk. Hk-1)
Σ V, (a', 00--0-111 Ha) Sk+1, Hks Sk
Vg Vglogpo(Sk+1 Ags ORT H Sky Hk-1) Skk, Ha-1
(by Ok+1 1. Sk 1k+1, Hk)
=6
Σ
Ok+1, Ha) Sk, Hk-1 Vo Vologpo(Sut1 Ak. Ok. Hk-1 Sk. HK-1) baee V.k+1 (
=
Σ Di (a', Ok.00 HR) Ve wog.pp(SS41. Ass Oss HK-1 Sks HK-1) 1) Ski HK-1
Σ 1 (a', O0001 Ha) Vy log To. (Ax Ox, Hk-1) Sky Hx-1 by (16
=
Di (a', 0k-1, Hz) no, (Ax Ok: Hx-1) Ok, Ars Sk. Hk-1 | Sk, Ha-1
V. (a', Ok-1, Ok Au, Sr, Hk
Volog Tox (Ax 1 Ok,
Hx-1) Sk Ha-1
E
E
bv 1 (a', Ok+1. H&) Oz = a, Sk. Ha-1
V a log nH (a Ok, Ha- Ha-1)TO, (a Ok, H1-1)] Sk HK-1]
E
V (a', 0x,1, Ha) On, A = o, Sk, Ha-1 VaTo, (a Ok, Ha 1) Sk, Ha-1
E
E
b7 1 1 (a', Ok+1, Ha) (a O₂, Hx-1) Oz, = a, Sk. HK-1
Sky Hk-1
E
E
b V. ( (a',0x+1 H&) Vo On, H Oz, As. = Sr. H
Sg Ha-1
a!
E
E
6 V.++ (a', Ok+1 V On, H4 Oz, As Sk, H
Sk,, 14 Ak
a
E
67 (a', Ok+1, Ha) Os, Ha-1) St, H4-1, A+
(167)
where
Vo log (88+1, ax, Ok, h4-1 8k,, hR-1)
Vo log (pg(p((s aks on, 8k, hi- (a Ok 88, lb-
Va log [p(s#+1 ak, 8& (ax, on sk, 1x-1)3 by Se41 ll (Ox, Hx-1) Sx, Av
Ve log po (ax, On sk, hx-))
(168)
Vo log (ax Ok. 8k. h1-11-pp ()po
8k, hx-1)}
~v log pa (ax ORR Sk, hx-1)
Ve log ne, (ax | ok, 14--1110 by As 11. Ss Ok, Ha-1-
69

---

Published as a conference paper at ICLR 2024
Combining equations (164 165
166
167
and we have
VBET Σ
Rs. Sk, Hk-1
T
=V VB R Sk, 11 + VoE
Σ
Rs Sk. Hk-1
L
RR V 0 (a
OR. H1-1) )
Sk. Hk-1, As= = a] + 7 + 17 by (644 165
R& 0 (a
Ok. H1-1) Sk. H,,1, A== =a
bTn VV Ox. Oz. Hk-1)
Sk. Hk- A = a
Σ
Ui Vih-1 (1), Vo) Ox, Hx-1)
Sk. Hy Ag = a
by 166 167
E
TT
OO. Hy
Sr. A+ = a, H by 37
E
bTt (O H Sk. H by O₂ 1T A& Sk H
=E
b (a, On, Hx-1) Sr, H
(169)
Therefore, V. Σ Re Sk. Ha-1 = ba Ox, Hk-1) Sk, Hk-1 also holds for j k if it holds for j k 1. By induction, the proof is done.
beva
H.7 PROOF OF LEMMA 13
We need to show
Pi 2 (St; H.-1)
St(Ar. Ot, H1-1)
pp (St, H, m (A, S.)
(170)
=Ba
P (S: H, ne, (At-1 0t- H(-2)
Σ f( Oz, H--)
(S, H,- -/ (Ar-1 S
To see this, we calculate these two terms separately.
pf (S,,
f((A,, Or, H1-1)
pF" (St, H.-1)a((A St)
p7 (st,
felas, or, 11-1)ppp" (ar, oc, st, do-
Ps (st, (o
(t))
DT. (84, 14-1)
Selars oc, be 1)- se)p(or st)pe (st, hu ddhhhrs
"T" (st, (se,ht-1) ( (s))
pt (st, h(-1)
Σ vF" (80, h4 8.)
fe(a, or, h ( st)p(or st)p; he-,
Jor
Σ Sela, se)pe" Ty (St, hy ddodddddd
00,81,
(171)
70

---

Published as a conference paper at ICLR 2024
The first equality is simply from expanding the expectation. The second equality is based on O2 TT Ag. St. The third equality is by taking expectation with respect to A at first. The final equality is by canceling out the same terms.
Now we analyze another term.
Pi- (S.-1, H2-2) (A,-1 O O1-1,He21
E
Σ Scla, Or, Hr,
pT- pT-1(S: (S H |o (At-1 St-1)
/
Pi (9:-1, h/t T (0:1 0--1111-2)
Σ fela, hi,-1)
(8-1 -ي |ل 01-1 1 8t-1)
nd (or, ap- 01-1, - -o-
p/ (  (a)- 0
fela, ((la,0t,h-11))
Pr- (8--
8/-1)
/
(0t, Se, /hsh dds. 1dde-2 (marginalization over S.)
Pi To 10-1 (a=-1 1 14-)
fela,or,he-1))
pf- ($1
(4-1 St-1)
= / Pi (8-1 (0c-1 0 hr Σ
p(o: | s))p(se 01-1, (111 1
-d
- =f 01.
Σ oi st)P (5t, (a-
(172)
where the third equality is by expanding the joint density under the assumptions POMDP. The fourth equality is by canceling out all the same terms. The last equality is by noticing that Pt (st, 14-1) p(8t St-1, (at-1
(0-1,h4-))p(04
st-1)p? (st-1, h22)). Then
the proof is done by comparing these two terms.
The proof is done by comparing equation 171 and equation 172
I IMPLEMENTATION
1.1 IMPLEMENTATION DETAILS USING RKHS
We provide implementation details for Algorithm in this section. Specifically, we mainly focus on steps 4-6 for estimating the policy gradient when function classes are assumed to be RKHSs.
For specific coordinate j each iteration B.0 be set RKHS endowed with reproducing kernel K 1 o (:))) and canonical RKHS norm 11g(0
k =ço Similarly, f:(() can be set as a RKHS endowed with reproducing kernel K (+:)) and a canonical RKHS norm ||را00 = able to get the closed-form solution of the min-max optimization problem 9 for each coordinate by adopting Propositions 9, 10 in Appendix E.3 of Dikkala et al. (2020). Specifically, can first get two empirical kernel matrices based on the offline data:
|| ||x yo. Then, with these bridge function classes and test function classes,
K BB N [K plo (lab, of, M1 (of, of N.N
and
F(0 N == |K 200 (lat,
(a og, la
71

---

Published as a conference paper at ICLR 2024
Given these two empirical kernel matrices, we define matrix
M
K 3 .N Ng K Fo NN + IN)
where X, f are tuning parameters and In denotes the N x N identity matrix.
Next, if j I de. then we consider the empirical "gradient response vector" Vt,.N R whose n-th element Vegii = (rī + En big+ (a', oi+1 [V En ( (eive1 (a', 1241, (2)1,, To, | o², (r,,h;1)) where Hll denotes the j-th coordinate. if = de +1, then we consider the empirical "value response vector" 1,,,++1,N E IN whose n-th element Ke,d = (r? + En. Dy, oft1 h2)) (af (p-1)
of (i-h)- +
We note that the empirical "gradient response vector" and the empirical "value response vector" can be understood as the empirical version of the "response" (i.e. evaluated at the offline dataset) on the right hand sides of equations 4 in Assumption [ All the involved terms are computable because we know the form of reproducing kernel functions (e.g. Gaussian kernel), the form of policies and
their gradients (e.g. log-linear policies), the bridge functions B% V,,+1: D V that have been learned from the previous iteration t + 1 and the given offline dataset = {(of. oj" ri (r1))=ii 1. Finally, by adopting the mentioned results in Dikkala al. (2020), for each coordinate j 1,..., de + 1, the solution to the min-max optimization problem is given in the following form:
679 = Σ
anick ogo (laf, of 1))1))))
n=1
where On,t. is the n-th element of the N-dimensional vector
atj := (Kg M.l... + 45pKK .x) N'K3go MII. WoSNN.
Here j is a tuning parameter and (-) denotes the Phoor-Penrooee pseudo-inverse The hyper- parameters &, X can be chosen by using cross-validation suggested in Dikkala et al. 2020). Repeating this procedure sequentially for T T,.... 1 and we get (.)()) whose j- th coordinate is En anigK "og (laP, of, (8).)) with anj = [an,1. 02,11, oN,
g MM.....KK B IN 45plK .x) (Kgg), g() M MIJ.NY We then use the first de el- ements of (+) (i.e. j 1.....dg) to estimate the policy gradient, by following the procedure described at steps 7.8 of Algorithm
Specifically, we compute 61,3 (a, AQAA oo), and i I.
Em 2n,1kK (lay. [a, oi)) for each j L....dd.,
Lastly we estimate the policy gradient evaluated at g(A) by 1/ E (Ene 1111do (a, of),, and the first stage for estimation is done. In the subsequent stage, we employ the estimated policy gradient to update the parameter using the procedure described in step 9 of Algorithm I
1.2 COMPUTATIONAL COMPLEXITY OF ALGORITHM I USING RKHS
We discuss the computational complexity of Algorithm I usiig RKHS here. We first focus the steps 4-6 regarding the min-max estimation procedure. At each t, for a specific j - th coordinate, we follow the implementation details described above.
(a) Computing Kg(0 .N and K p(tt) .N' can be seen that we need to first evaluate the empirical kernel matrix K gle .N and K K-0,,N- As they are both N x N matrix, it takes N2 operations to evaluate each element (kernel function values between two vectors with length Adim(O)dim(() which is the dimension of the history space He. Here we note that both dim(O) and dim (A) are fixed, and we care about the key parameter the scale with t. Throughout this discussion, we sim- ply ignore OO) and (Am. The complexity of computing the kernel function value for two vectors with dimension depends on the specific kernel functions we For example, for linear kernels, the computational complexity of evaluating the kernel function O(t). For more complex kernels like polynomial kernel, this complexity is higher than linear and depends the degree of
72

---

Published as a conference paper at ICLR 2024
the polynomial. For the Gaussian kernel (RBF) that we used in numerical experiments, the com- putational complexity is usually O(t). Consequently, the computational complexity of evaluating two empirical kernel matrices is O(N
(b) Computing M,.,.N- The computation of M.,..N involves taking the square root of matrices, matrix multiplications, and the calculation of the inverse of matrix. The computational time is dominated by the calculation of the inverse of a matrix, which is O(N3).
(c) Computing no. (a, oc, he,,) 1) and TT, (a, Or. h1-1) for any fixed 01, h4-1). The computational time depends on the specific policy class. For the log-linear policy class with TT, (at Ot, h1-1) xx exp(0, Φlor, at, h)-1)), we have Va, mo, (az 0t, (1)) Φ00r, dt hx-1) Eet Te, (a) oz, (o,he-1)0(0, d/e h1-1). It can be seen directly that both the computational time in evaluating (at) 0s, and Vo, (as ot, h1-1) is O(de,)
(d) Computing It..N. For each n, it takes (dde.) to compute Te, (a or, "".h") and To. (o
of, 11-1) for log-linear policies according to (c). In addition, it takes O(N(t + 1)) to compute ( (a' 1-111 and b 02+1, h()) according to (f). Since we need to do the same operation for each n, the computational time for this step is O(Nde, + N 1))
(c) Computing ar.j. Having the results of k ((t) .N' (kzg", .N' Me,,,NN and Yi,,N, we are able to calculate the coefficient at.j- The computation of or, involves matrix multiplication and solving a linear system. The computational time is (NN))
(ae, (f) Computing (ae, Ot, 1t-1) for any fixed (dt, Ot, h1-1). involves the calculation of N ker- nel function values and linear combination of them. For the Gaussian kernel, the computational complexity is (l) for each n. Therefore the computational complexity this step is O(N)).
We note that at each i, steps (a), (b), (d), (e), (f) should be repeated de + 1 times, while (c) is only repeated T times. Consequently, the computational time for solving the min-max optimization problem for each t is ( dg N3 + NNg + N2 + ddgttd (d N As we repeat the procedure from = T to t = 1, the computational complexity of steps 4-6 in Algorithm is Odd NT).
can be easily seen that the computational time of steps 8,9 is dominated by the one of steps 4-6. Consequently, by considering the for-loop over k, the overall computational complexity of Algorithm is
O(Kd max (T, N))
by assuming history-dependent log-linear policy class and RKHS with Gaussian kernels.
1.3 MORE DISCUSSIONS ON PRACTICAL IMPLEMENTATIONS
In practical implementations 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 N N (which takes O(N*)) and evaluating the empirical kernel matrix on the space of history (taking approximately ((NT)). 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, a potential alterna- tive 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 alter- nately using gradient ascent and gradient descent only once in each iteration can be performed. In this case, Algorithm could be potentially expedited, contributing to faster computations.
J SIMULATION DETAILS
In this section, we provide the simulation details for the numerical results of the conducted experi- ment as shown in section
73

---

Published as a conference paper at ICLR 2024
Table 2: Comparisons of policy gradient estimations under the proposed method and the naive
method at the uniform random policy when O = S = A= [+1,-114 -1}. Simulated data are generated
by assuming P(S. 1) = 5. POO, So) 0.8, P(Si = So) = 0.95, P(O,, = S1) = 0.8,
m | -1) = 0.3, (a | 01) x exp(Oa_,or)) ). m) T
RI T+expl - 48, A1] 1, mb (++ 1) = m
= number of stages; N = number of samples. Means (standard deviations) of VV - VVIIIIV
reported based 20 replicates.
SAMPLE SIZE
T=1, PROPOSED
T=1, NAIVE
T=2, PROPOSED
T=2
N 500
0.124 (0.011)
0,115 (0.0011)
0.192 (0.0189)
0.345 (0.011)
N 2000
0.073 (0.006)
0.110 (0.005)
0.133 (0.012)
0.342 (0.007)
N = 8000
0.031 (0.003)
0.110 (0.003)
0.066 (0.004)
0.352 (0.003)
We consider T 7=2 2 and N = 10000. Simulated data are generated by assuming
So ~ umif(-2, (bmmmi(-222)
Oo ~ 0.8N 0.1) + 0.2N (-, 0.1), ~ M 0.1),
S
(+11 S; > - m,(11| - S, 0) 0.3,
O, ~ (S, 0.1) + 0.2N
2
(S, Ar) = + exp( A., 1,
no. (A (O)) exp(0, Φc(A,, O.)),
where 6r.1 (1), 01) == 20,I(a, > 0, > 0). (1,2 01) == 20,I(a; < 0, 02 > >0). 01,3 o;):= :=
20, > 0, 0r < 0), the, (0t, o.) == 20,T(ar < 0,0, < 0) for 1,2. The dimension of policy class de- 8.
K ADDITIONAL NUMERICAL RESULTS FOR TABULAR CASES
Table reports the normalized l2 norm of the error for the policy gradient estimator under the proposed method and the naive method. We can see that the proposed method under both single- stage and multi-stage settings is consistent, i.e. the error of the policy gradient estimator approaches to as the sample size N increases. In contrast, the naive estimator has an irreducible bias (*< 0.11) in the single-stage setting, and this bias becomes significantly larger (ss 0.352) in the multi-stage setting, indicating that the bias caused by unmeasured confounding may be more severe when the number of stages increases.
L ADDITIONAL NUMERICAL RESULTS FOR CONTINUOUS CONTINUOUS CASES
Numerical results of policy gradient estimation in the function approximation settings. We consider an example with continuous state/observation space and T = 2, and implement the pro- posed policy gradient estimation procedure (9) using RKHS. Simulation results of the proposed method and the naive method for estimating policy gradient are provided in Figure 3 We observe that the naive estimator has an irreducible bias. In contrast, the proposed estimator eliminates the bias and outperforms the naive estimator significantly. Simulation details can be found in Appendix D
Computational time. We summarize the computational time (in seconds) of running Algorithm with varying sample sizes in table 3 For all scenarios, the proposed method only takes minutes to find the optimal policy.
74

---

Published as a conference paper at ICLR 2024
baka
Extomadd grddent-huu
Figure 3: Comparisons of the proposed policy gradient and the naive policy gradient estimators to the truth at the uniform random policy. Results are computed using 20 replicates under T 2, N 10000 with general function approximations.
Table 3: Computational time (in seconds) for T 2, do 8, K
50 with varying sample sizes
N.
SAMPLE SIZE
TIME
N 200
9.81563
N 1000
28.79569
N 5000
118,81537
N 10000
227.02766
75


Reviews:
[{"review_id": "8jGlXbwRYV", "reviewer": "Reviewer_5Pwh", "summary": "This paper introduces a novel policy gradient method for confounded partially observable Markov decision processes (POMDPs), and proves it converges to global optimal under certain assumptions. Their method estimates the policy gradient using bridge functions calculated from offline data, which is adopted from min-max estimator of [Dikkala et al. (2020)]. The paper provides a finite-sample non-asymptotic bound for estimating the gradient uniformly over a pre-specified policy class. Additionally, the authors show the global convergence of the proposed algorithm in finding the history-dependent optimal policy under certain technical conditions. This work is claimed to be the first to study the policy gradient method for POMDPs under the offline setting.\n\nThe paper also discusses the challenges in studying policy gradient methods in confounded POMDPs under the offline setting, such as the bias in estimation due to unobserved state variables, the need for function approximation in continuous spaces, and the challenge in achieving global convergence for finding the optimal policy.\n\nThe authors contribute by proposing a policy gradient method with both statistical and computational guarantees, establishing a non-asymptotic error bound for estimating the policy gradient, and providing a solution for global convergence in POMDPs.", "questions": "[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. 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). With this work, I also love to see more about computational complexity (and polynomial / NP-hardness / ...) of specific classes of POMDPs.\n\nI must note that I am unable to specifically identify any of the assumptions as unreasonable, but I guess Assumption 2 is the most critical assumption. \n\nReferences:\n- Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy\ngradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(1):4431–4506, 2021.\n- Vlassis, Nikos, Michael L. Littman, and David Barber. \"On the computational complexity of stochastic controller optimization in POMDPs.\" ACM Transactions on Computation Theory (TOCT) 4.4 (2012): 1-8.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Dsiclaimer:** I should first note that the results of this paper are super technical. A proper review of this article needs a full working week of my time, which clearly I couldn't put. I tried going through Appendix A and B, but even then I cannot say I understood completely.\n\nDespite these challenges, it is evident that the results derived in this paper solid. Establishing any form of convergence for the Policy Gradient (PG) algorithms within the context of POMDPs is immensely valuable to the community. Furthermore, their method for gradient estimation in this study presents itself as a potentially advantageous tool in its own right.", "weaknesses": "Given the technical nature of this paper, I am compelled to express my reservations about the suitability of the ICLR conference as the platform for its publication. I believe that this work might find a more fitting home in a scholarly journal, where reviewers are afforded ample time to thoroughly validate the results presented. Additionally, the attempt to condense the material into a 9-page format has significantly hindered its readability. In particular, the contents of Appendix A are critical enough that they warrant inclusion (or partial inclusion) in the main body of the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T6WBMk4qkN", "reviewer": "Reviewer_YGPH", "summary": "This paper proposes a policy gradient method for confounded partially observable Markov decision processes (POMDPs) in the offline setting with novel gradient identification and estimation. Also, a theoretical analysis of the suboptimality of the proposed method is provided. Finally, numerical experiments are conducted to evaluate the performance of the algorithm.", "questions": "1. In the third paragraph of Section 3, does the definition of history $\\mathcal{H}_{t}$ lack the subscript on $\\mathcal{O}$ and $\\mathcal{A}$?\n2. The notation $Z_{t}$ has already been defined in Section 3; however, another $\\mathcal{z}$ is used in Section 5 as additional notation. Are they the same things?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The gradient identification proposed is new to confounded POMDPs, and the policy gradient based on that is complimented by strong theoretical guarantees. The statistical error of the gradient estimation and the suboptimal of the obtained policy are both discussed with a comprehensive analysis. Also, The theoretical results are also complimented by experimental results.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s5bvUaY00d", "reviewer": "Reviewer_KDFK", "summary": "This paper introduces a policy gradient method tailored for confounded POMDPs with continuous state and observation spaces in the offline learning context. The authors present a novel method for non-parametrically estimating any history-dependent policy gradient in POMDPs using offline data. They employ a min-max learning procedure with general function approximation to estimate the policy gradient through solving a sequence of conditional moment restrictions.\n\nThe authors provide a finite-sample, non-asymptotic bound for the gradient estimation. Using the proposed gradient estimation method within a gradient ascent algorithm, the paper demonstrates the global convergence of the algorithm.", "questions": "How might the proposed method be adapted or extended to accommodate partial coverage assumptions, and what would be the technical challenges associated with such an adaptation? Could you provide insights or discuss potential ways for relaxing the full coverage assumptions while maintaining the theoretical guarantees of the method?\n\n\n================================================\n\n**After Rebuttal:**\n\nThank you for the detailed response. I feel like my concerns have been addressed by the authors' response, and I would like to raise my score to 8.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper addresses a challenging problem on policy gradient methods for POMDPs in the offline setting with continuous state and observation spaces. This is a novel contribution to the best of my knowledge; most existing work on policy gradient methods has been centered around fully observable environments. \n\n- The paper’s contributions seem to be significant with the global convergence result of the algorithm to find the history-dependent optimal policy. Additionally, the identification result for non-parametrically estimating any history-dependent policy gradient under POMDPs using offline data is a unique contribution.", "weaknesses": "- The paper introduces a significant number of symbols and notations, which might overwhelm readers, especially those who are less familiar with the topic. To improve clarity, the authors could consider providing a table or appendix that lists all the symbols used along with their definitions. Additionally, they might simplify the notation where possible and ensure that each symbol is clearly defined upon its first use. For example, the notation seems to be quite heavy at the end of Page 5 where $\\mathcal{Z_t}$ and $\\mathcal{W_t}$ are introduced.\n\n- The full coverage assumptions stated in Assumption 4(a) and Assumption 5(a) are indeed common in offline RL literature, but they bring about challenges and potential limitations to the proposed method in the paper. \n\n1. **Full Coverage Assumption (Assumption 4(a))**: This assumption, which requires that the offline distribution $P_{\\pi_b}$ can calibrate the distribution $P_{\\pi_\\theta}$ induced by $\\pi_\\theta$ for all $\\theta$, is strong and might not always be satisfied in practical scenarios. In real-world applications, especially in domains like healthcare or finance, obtaining an offline dataset that sufficiently covers all possible actions and states can be impractical due to ethical, logistical, or financial constraints. The paper could improve by discussing the potential implications of this assumption, providing guidance on how to assess whether this assumption is reasonable in a given setting, or suggesting alternative approaches if the assumption is not met.\n\n2. **Optimal Policy Coverage (Assumption 5(a))**: This assumption requires that the optimal policy $\\pi^*$ is covered by all the policies in the class. While this condition ensures that the policy class is rich enough to contain the optimal policy, it might be too restrictive in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y1bUJP7cgh", "reviewer": "Reviewer_4mko", "summary": "This paper theoretically studies the problem of offline policy optimization in POMDPs from a confounded offline data dataset, following the line of previous works on confounded POMDPs and policy gradient in MDPs. The core contribution is a deconfounded policy gradient ascent algorithm (Algorithm 1) based on proximal causal inference with theoretical guarantees. There are also numerical demonstrations to show the effectiveness of the proposed method.", "questions": "1. Continued from Weakness 1., I would appreciate it if the authors could highlight more on the technical contributions behind the main theory, especially when compared with the previous line of works listed.\n2. Continued from Weakness 2., it seems that the paper does not contain any discussion of a concrete policy class example. I think this is important since we are now dealing with history-dependent policy class which is different from previous MDP policy gradient problems. How does the dependence on history change (or not change) the difficulty of doing policy gradient and why? It would be great if such discussions can be included.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The confounded offline POMDP setting itself is a well-motivated problem, and based on existing works it is natural to ask how to learn the optimal history dependent policy with computational efficiency. The authors answer this question by looking into the policy gradient style method which has not been explored in this literature.\n2. The idea of using bridge functions (originated from proximal causal inference) to identify not only the policy value $\\mathcal{V}(\\pi_{\\theta})$ but also the policy gradient $\\nabla_{\\theta}\\mathcal{V}(\\pi_{\\theta})$ is new.\n3. The theoretical derivations of the policy gradient identification is novel and is of independent interest to future research in confounded offline RL area.\n4. The theoretical results are self-content and sound.", "weaknesses": "1. From my viewpoint, by looking into the previous line of works, the main theory (Sections 6.1 & 6.2) of this work is mostly based on **(i)** the theoretical understanding of statistical analysis for using minimax estimator to solve bridge functions in confounded offline POMDP settings, e.g., [1, 2, 3]; **(ii)** the analysis of global convergence of policy gradient ascent methods in standard MDP settings, e.g., [4, 5]. So the technical contributions of the main theory part are somehow weakened given these prior works.\n2. As stated in 1., a consequence is that the theoretical assumptions regarding the policy gradient analysis (Section 6.2) are mostly adapted directly from those for MDP setups. How to understand these assumptions in POMDP settings with a history dependent policy class is less discussed.\n\n**References:**\n\n[1] Bennett, Andrew, and Nathan Kallus. \"Proximal Reinforcement Learning: Efficient Off-policy Evaluation in Partially Observed Markov Decision Processes.\" *Operations Research* (2023).\n\n[2] Shi, Chengchun, et al. \"A Minimax Learning Approach to Off-policy Evaluation in Confounded Partially Observable Markov Decision Processes.\" *International Conference on Machine Learning*. PMLR, 2022.\n\n[3] Lu, Miao, et al. \"Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes.\" *The Eleventh International Conference on Learning Representations*, 2023.\n\n[4] Agarwal, Alekh, et al. \"On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift.\" *The Journal of Machine Learning Research* 22.1 (2021): 4431-4506.\n\n[5] Liu, Yanli, et al. \"An Improved Analysis of (Variance-reduced) Policy Gradient and Natural Policy Gradient Methods.\" *Advances in Neural Information Processing Systems* 33 (2020): 7624-7636.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)