Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes
Authors: Miao Lu
Yifei Min
Zhaoran Wang
Zhuoran Yang
Venue: ICLR 2023 poster (2023)

Abstract: We study offline reinforcement learning (RL) in partially observable Markov decision processes. In particular, we aim to learn an optimal policy from a dataset collected by a behavior policy which possibly depends on the latent state. Such a dataset is confounded in the sense that the latent state simultaneously affects the action and the observation, which is prohibitive for existing offline RL algorithms. To this end, we propose the \underline{P}roxy variable \underline{P}essimistic \underline{P}olicy \underline{O}ptimization (\texttt{P3O}) algorithm, which addresses the confounding bias and the distributional shift between the optimal and behavior policies in the context of general function approximation. At the core of \texttt{P3O} is a coupled sequence of pessimistic confidence regions  constructed via proximal causal inference, which is  formulated as  minimax estimation. Under a partial coverage assumption on the confounded dataset, we prove that \texttt{P3O} achieves a $n^{-1/2}$-suboptimality, where $n$ is the number of trajectories in the dataset. To our best knowledge, \texttt{P3O} is the first provably efficient offline RL algorithm for POMDPs with a confounded dataset.

Published as a conference paper at ICLR 2023
PESSIMISM IN THE FACE OF CONFOUNDERS: PROV- ABLY EFFICIENT OFFLINE REINFORCEMENT LEARNING IN PARTIALLY OBSERVABLE MARKOV DECISION PRO- CESSES
Miao Lu', Yifei Min', Zhaoran Wang', Zhuoran Yang²
University of Science and Technology of China, Yale University, Norttwesternn University
I ummi aoêma 11 ustc. edu. en, Shaoranwang@gmaa com (yifei. min, zhuoran. yang) @eyaleledll
ABSTRACT
We study offline reinforcement learning (RL) in partially observable Markov de- cision processes. In particular, we aim to learn an optimal policy from a dataset collected by a behavior policy which possibly depends on the latent state. Such dataset is confounded in the sense that the latent state simultaneously affects the action and the observation, which is prohibitive for existing offline RL algo- rithms. To this end, we propose the Proxy variable Pessimistic Policy Optimization (P3 algorithm, which addresses the confounding bias and the distributional shift between the optimal and behavior policies in the context of general function ap- proximation. At the core of 30 is coupled sequence of pessimistic confidence regions constructed via proximal causal inference, which is formulated as minimax estimation. Under partial coverage assumption the confounded dataset, we prove that P30 achieves n 11/2 11/--11//-appp -u/////ubppiimality. where is the number of trajecto- ries in the dataset. To our best knowledge, P30 the first provably efficient offline RL algorithm for POMDPs with confounded dataset.
INTRODUCTION
Offline reinforcement learning (RL) (Sutton and Barto, 2018) aims to learn an optimal policy of sequential decision making problem purely from an offline dataset collected priori, without any further interactions with the environment. Offline RL particularly pertinent to applications in critical domains such precision medicine (Gottesman al., 2019) and autonomous driving Shhlev--Swartz et al., 2016). In particular, in these scenarios, interacting with the environment online experiments might be risky, slow, even possibly unethical. But oftentimes offline datasets consisting of past interactions, e.g., treatment records for precision medicine (Chakraborty Chakraborty and Murphy (0044) and human driving data for autonomous driving (Sun et al. 2020), are adequately available. As a result, offline RL. has attracted substantial research interest recently (Levine et al. 2020))
and Moodie 2013
Most of the existing works on offline RL develop algorithms and theory on the model of Markov decision processes (MDPs). However, in many real-world applications, due certain privacy concerns or limitations of the sensor apparatus, the states of the environment cannot be directly stored in the offline datasets. Instead, only partial observations generated from the states of the environments are stored Muulac-Amola et al. 202I). For example, in precision medicine, a physician's 's treatment might consciously or subconsciously depend on the patient's mood and socioeconomic status (Zhang and Bareinboim 2016),, which are not recorded in the data due to privacy concerns. As another example, in autonomous driving, a human driver makes decisions based on multimodal information of the environment that is not limited to visual and auditory inputs, but only observations captured by LIDARs and cameras are stored in the datasets (Sun et al. 2020). In light the partial observations in the datasets, these situations (POMDPs) (Lovejoy] 199T). Existing offline RL methods for MDPs, which fail to handle partial observations, are thus not applicable.
better modeled as partially observable Markov decision processes

---

Published as a conference paper at ICLR 2023
In this work, we make the initial step towards studying offline RL in POMDPs where the datasets only contain partial observations of the states. In particular, motivated from the aforementioned real-world upplications, we consider the case where the behavior policy takes actions based on the states of the environment, which are not part of the dataset and thus are latent variables. Instead, the trajectories in datasets consist of partial observations emitted from the latent states, as well as the actions and rewards. For such a dataset, our goal is to learn an optimal policy in the context of general function approximation.
Furthermore, offline RL in POMDP suffers from several challenges. First of all, it is known that both planning and estimation in POMDPs are intractable in the worst case (Papadimitriou and Tsitsiklis 1987 Burago et al. 1996: Goldsmith and Mundhenk] 19988 Mundhenk et al. 2000; Vlassis et al. 2012). Thus, we have to identify a set of sufficient conditions that warrants efficient offline RI. More importantly, our problem faces the unique challenge of the confounding issue caused by the latent states, which does not appear in either online and offline MDPs or online POMDPs. In particular, both the actions and observations in the offline dataset depend on the unobserved latent states, and thus are confounded (Pearl 2009).
Such confounding issue is illustrated by causal graph in Figure [ As a result, directly applying offline RL methods for MDPs will nev- ertheless incur a considerable confounding bias. Besides, since the latent states evolve according to the Markov transition kernel, the causal struc- ture is thus dynamic, which makes the confound- ing issue more challenging to handle than that in static causal problems. Furthermore, apart from the confounding issue, since we aim to learn the optimal policy, our algorithm also needs to handle the distributional shift between the tra- jectories induced by the behavior policy and the family of target policies. Finally, to handle large observation spaces, we need to employ powerful function approximators. As result, the coupled challenges due to (i) the confounding bias, (ii) distributional shift, and (iii) large observation spaces that are distinctive in our problem neces- sitates new algorithm design and theory.
Oa-1
A--1
On
Outs
R
R
Figure I: Causal graph of the data generating pro- cess for offline RL in POMDP. Here Sr is the state at step h. Besides, An. Rs, and On are the action, immediate reward, and observation, respectively. The dotted nodes indicate that the variables are not stored the offline dataset. Solid arrows indicate the dependency among the variables. In specific, the action As is specified by the behavior policy which is function of S₁ (blue arrows). Moreover, both the observation On and reward R, depend on the state Sn (red arrows). We remark that Sh affects both As, and (O,, Rs) and thus serves as an unobserved confounder.
To this end, by leveraging tools from proximal causal inference (Lipsitch et al. 2010 Tehetgen et al. 2020 Miao et al. 2018b a). we propose the Proxy variable Pessimistic Policy Optimization (P30) algorithm, which provably addresses the challenge of the confounding bias and the distributional shift in the context of general function approximation. Specifically, we focus on benign class of POMDPs where the causal structure involving latent states can captured by the past and current observations, which serves as the negative control action and outcome respectively (Miao et al. 2018a b) Cui et al. 2020 [ingh] 2020) Kallus et al. 2021] Bennett and Kallus [021 Shi et al. 2021). Then the value of each policy can be identified by set of confounding bridge functions corresponding to that policy, which satisfy a sequence of backward moment equations that are similar to the celebrated Bellman equations in classical RL (Bellman and Kalaba 1965). Thus, by estimating these confounding bridge functions from offline data, we can estimate the value of each policy without incurring the confounding bias.
More concretely, P30 involves two components - policy evaluation via minimax estimation and policy optimization via pessimism. Specifically, to tackle the distributional shift, P30 returns the policy that maximizes pessimistic estimates of the values obtained by policy evaluation. Meanwhile, in policy evaluation, to ensure pessimism, we construct a coupled sequence of confidence regions for the confounding bridge functions via minimax estimation, using function approximators. Furthermore. under a partial coverage assumption on the confounded dataset, we prove that P30 achieves a Ö(H / IIog(Nium))/ suboptimality, where is the number of trajectories, H is the length of each trajectory, Min stands for the complexity of the employed function classes (c.g., the covering number), and (--) hides logarithmic factors. When specified to linear function classes, the suboptimality of
2

---

Published as a conference paper at ICLR 2023
Offline
Partial Obs.
Confounded Data
Policy Opt.
Xie et al.
2021
x
x
Uehara and Sun (0211)
X
x
Jin et al. 2020)
X
x
Efroni et al. (2022)
x
/
X
Liu et al. 2022)
Bennett and Kallus (021))
V
x
Shi et al. (2021)
P330 (ours)
Table 1:
We compare with most related representative works in closely related lines of research. The first line of research studies offline RL in standard MDPs without any partial observability. The second line of research studies online RL in POMDPs where the actions are specified by history-dependent policies. Thus, the actions does not directly depends on the latent states and thus these works do not involve the challenge due to confounded data. The third line of research studies OPE in POMDPs where the goal is to learn the value of the target policy as opposed to learning the optimal policy. As result, these works do not to need to handle the challenge of distributional shift via pessimism.
P 30 becomes H(/Hdd/m) where is the dimension of the feature mapping. To our best knowledge, establish the first provably efficient offline RL algorithm for POMDP with confounded dataset.
1.1 OVERVIEW OF TECHNIQUES
To deal with the coupled challenges of confounding bias, distributional shift, and large observational spaces, algorithm and analysis rely on the following technical ingredients.
Confidence regions based on minimax estimation via proximal causal inference. To handle the confounded offline dataset, use the proxy variables from proximal causal inference (Lipsitch et al., 2010 Tehetgen et al. 2020 Miao et al.) &0 b), which allows us to identify the value of each policy by of confounding bridge functions. These bridge functions only depend on observed variables and satisfy a set of backward conditional moment equations. We then estimate these bridge functions via minimax estimation (Dikkala al., 2020 Chermozhukov al. 2020. Uehara al. 202I). More importantly, to handle the distributional shift, we propose sequence of novel confidence regions for the bridge functions, which quantifies the uncertainty of minimax estimation based on finite data, This sequence of new confidence regions has not been considered in the previous works on off- policy evaluation (OPE) in POMDPs (Bennett and Kallus 2021 Shi al., (202T) as pessimism seems unnecessary in these works. Meanwhile, the confidence regions constructed the loss functions of the minimax estimation for bridge functions. Such a construction contrasts with previous works offline RL with confidence regions via maximum likelihood estimation (Uchara and Sun 2021 Liu et al. 2022) or least square regression (Xie et al. 2021). Furthermore, we develop novel theoretical analysis show that any function in the confidence regions enjoys fast statistical rate of convergence. Finally, leveraging the backwardly inductive nature of the bridge functions, our proposed confidence regions and analysis take the temporal structure into consideration. which might be of independent interest to the study on dynamic causal inference (Friston et al. 2003).
level set w.r.t.
Pessimism principle for learning POMDPs. To learn the optimal policy in the face of distributional shift, we adopt the pessimism principle which is shown to be effective in offline RL in MDPs (Liu
al. 22200 Jin al.] |021 Rashidinejad et al. | [eeaaa and Sun [02 Xie al. 2021 Yin and
Wang 2021 2 Zanette et al. 2021: Yin et al. 2022 Yan et al. (002). Specifically, the newly proposed confidence regions, combined with the identification result based on proximal causal inference, allows us to construct a novel pessimistic estimator for the value of each target policy. From a theoretical perspective, the identification result and the backward induction property of the bridge functions provide way of decomposing the suboptimality of the learned policy in terms of statistical errors of the bridge functions. When combined with the pessimism and the fast statistical rates enjoyed by any functions in the confidence regions, show that our proposed P30 algorithm efficiently learns the optimal policy under only a partial coverage assumption of the confounded dataset. We highlight that work firstly extend the pessimism principle to offline RI. in POMDPs with confounded data.
3

---

Published as a conference paper at ICLR 2023
1.2 RELATED WORK
Our work is closely related to the bodies of literature on (i) reinforcement learning POMDPs, (ii) offline reinforcement learning (in MDPs), and (iii) OPE via causal inference. Compared to the literature, our work simultancously involve partial observability, confounded data, and offline policy optimization simultancously. and thus involves the challenges faced by (iii) We summarize and contrast with most related existing works in Table [T
We defer the detailed discussion to Appendix B.I B.1
2 PRELIMINARIES
Notations. In the sequel, we use lower case letters (i.e., 8, o, and r) to represent dummy variables and upper case letters (i.c., S, A. O, and I') to represent random variables. We use the variables in the calligraphic font (i.e., S, A, and O) to represent the spaces of variables, and the blackboard bold font (i.e., IP and O) to represent probability kernels
2.1 EPISODIC PARTIALLY OBSERVABLE MARKOV DECISION PROCESS
We consider an episodic, finite-horizon POMDP, specified by a tuple (S, H,,, O) Here we let S, .A, and O denote the state, action, and observation spaces, respectively. The integer H e N denotes the length of each episode. The distribution μl (SS) denotes the distribution of the initial state. The set IP- (IPn hE[H) denotes the collection of state transition kernels where each kernel
(-I, S x A + ((S) characterizes the distribution of the next state sh+11 given that the agent takes action d₃ E A state 8,
and step h E [H]) The set O {0,) denotes the observation emission kernels where each kernel 0g (- 8) S + A(O) characterizes the distribution over observations given the current state s E at step denotes the collection of reward functions where each function (s(s, a) S A [0. 1] specifies the reward the agent receives when taking action a E A at state E S and step E [H].
)H
[H. Finally, the set R (R,} 1
Different from an MDP, in POMDP, only the observation the action a, and the reward are observable, while the state variable is unobservable. In each episode, the environment first samples an initial state S from μ1 (-). At each step h E [ff], the environment emits observation On from O, (. If an action Ad is taken, then the environment samples the next state S from (- AA) and assign reward R2 given by (S,,, Ag). .. In our setting, also let Oo O denote the prior observation before step = 1. We assume that Og is independent of other random variables in this episode given the first state S1.
2.2 OFFLINE DATA GENERATION: CONFOUNDED DATASET
Now we describe the data generation process. Motivated by real-world examples such as precision medicine and autonomous driving discussed in Section I we assume that the offline data is generated by some behavior policy T which has access to the latent states. Specifically, we let nh {^f H /==1 denote a collection of policies such that T& (-1s) :): S + A(AA) specifies the probability of taking action each
at state s and step h. This behavior policy induces a set of probability distribution pd = { on the trajectories of the POMDP, where PP) is the distribution of the variables at step h when following the policy T². Formally, we assume that the offline data is denoted by [(o,, (of at,
(o a r. 3 where is the number of trajectories. and for each e [n). (oh, (of, af.rt). ....)..... (o a r) independently sampled from pb. We highlight that such an offline dataset is confounded since the latent state Sh, which is not stored in the dataset, simultaneously affects the control variables (i.e., action A₂) and the outcome variables (i.e., observation On and reward R,). Such setting prohibitive for existing offline RL algorithms for MDPs as directly applying them will nevertheless incur a confounding bias that is not negligible.
r4)
2.3 LEARNING OBJECTIVE
The goal of offline RL is to learn optimal policy from the offline dataset which maximizes the expected cumulative reward. For POMDPs. the learned policy can only depend on the observable information mentioned in Section 2.1 To formally define the set policies of interest, we first define the
4

---

Published as a conference paper at ICLR 2023
space of observable history 1 {H such that T) _ {(01, a1), ".) (on, a. We use l' to denote the corresponding random variable.
) H-1 h==0 where each element T E Hr is (partial) trajectory
We denote by II(H)) the class of policies which make decisions based the current observation On E O and the history information Th-1 E HA-1- That means, a policy т = {TA E II(H) satisfies TT T (-1o,T) O x H4-1 + A(A). The choice of H induces the policy set (TH by specifying the input of the policies. We now introduce three examples of H. and the corresponding ((H).
Example 2.1 (Reactive policy (Azizzaeenesheli et al. (018)). The policy only depends on the current observation On Formally, we have H = {0] and therefore Th-1 = 2 for each E [H].
Example 2.2 (Finite-history policy (Efroni et al. ). The policy depends on the current obser- vation and the history of length at most k. Formally, we have Hh-1 1 = (O x A) min(k,h-1) and Th-1 = ((0), ot),... (Oh-1, 1,-0h11)) for some l E N, where the index = max {1, k).
2022 ). The policy depends on the current observation Example 2.3 (Full-history policy (Liu et al.,
and the full history. Formally, Ha-1 = (O A) () and Th-1 = ((01, (0h-1. Op 1)).
We illustrate these examples with causal graphs and a more detailed discussion in Appendix I. Now given policy π E II(H), we denote by (1T) the value of i that characterizes the expected cumulative rewards the agent receives by following æ. Formally, J(T)) is defined as
((x) Bs
Rn An)
(2.1)
where y E (0, 1] is the discount factor, E, denotes the expectation w.r.t. PM = (PP) h== which is the distribution of the trajectories induced by We define the suboptimality gap of any policy म as
SubOpt(A) == J(xx((x J()), where x' E arg max J(x)).
Earg
(2.2)
=EU(H)
Here x² is the optimal policy within II)... Our goal is to find some policy मे E II())) that minimizes the suboptimality gap (.2) based on the offline dataset D.
ALGORITHM: PROXY VARIABLE PESSIMISTIC POLICY OPTIMIZATION
As is previously discussed, the offline RL problem introduced in Section 2 for POMDPs suffers from three coupled challenges - (i) the confounding bias, (ii) distributional shift, and (iii) large observation spaces. In the sequel, we introduce algorithm that addresses all three challenges simultaneously. We first introduce the high-level idea for combating these challenges.
Offline RL for POMDPs is known to be intractable in the worst case (Krishnamurthy et al., 2016). So we first identify a benign class of POMDPs where the causal structure involving latent states can be captured by only the observable variables available in the dataset D. For such a class of POMDPs, by leveraging tools from proximal causal inference (Lipsitch et al. 2010 Tehetgen et al. 2020). we then seek to identify the value J (T) of the policy II(H) via some confounding bridge functions ba (Assumption 3.2) which only depend on the observable variables and thus can be estimated using
DD (Theorem 3.3 Identification via proximal causal inference will be discussed in Section 3.1
In addition, to estimate these confounding bridge functions, we utilize the the fact that these functions satisfy a sequence of conditional moment equations which resembles the Bellman equations in classical MDPs (Bellman and Kalaba 1965). Then we adopt the idea of minimax estimation (Dikkala) al. 2020 Kallus et al.) 2021: Uehara et al. 202T Duan et al., 202T which formulates the bridge functions as the solution to series of minimax optimization problems in (3.11) Additionally, the
loss function in minimax estimation readily incorporates function approximators and thus addresses
the challenge of large observation spaces.
To further handle the distributional shift, we extend the pessimism principle (Liu et al., 2020 Jin
et al. [202 Rashidingejd et al.) [021]] |ehara and Sun 2021; Xie et al. 2021] Yin and Wang 2021 Zanette et al. 2222)) to POMDPs with the help of the confounding bridge functions. In specific, based on the confounded dataset, we first construct novel confidence region CR (E) for ba based on
level sets with respect to the loss functions of the minimax estimation (See (3.12) for details). Our
algorithm, Proxy variable Pessimistic Policy Optimization (P 30), outputs the policy that maximizes pessimistic estimates the values of the policies within II).). The details of P 30 is summarized by Algorithm in Section 3.3
5

---

Published as a conference paper at ICLR 2023
3.1 POLICY VALUE IDENTIFICATION VIA PROXIMAL CAUSAL INFERENCE
To handle the confounded dataset D. we first identify the policy value ( for each E (IH)) using the idea of proxy variables. Following the notions of proximal causal inference (Tennenholtz
et al. 2020 Lipsitch et al. 2010), we assume that there exists negative control actions (Z and negative control outcomes WhE satisfying the following independence assumption.
Assumption 3.1 (Negative control). We assume there exist negative control variables (W h==1 and {2r measurable with respect to the observed trajectories, such that under Ph, it holds that
74, On, R,, Wh, Wh+1 An. Sh. h WA 1 A Sh.
(3.1)
We explain in detail the existence of such negative control variables for all the three different choices of history 7. in Examples 2.1 2.1222 2.2 and 2.3 respectively in Appendix [... [CI Besides Assumption 3.1 our identification of policy value also relies the notion of confounding bridge functions (Kallus ct al. 2021 Shi et al. 2021), for which we make the following assumption.
Assumption 3.2 (Confounding bridge functions). For any destory-dependett policy (H),, we assume the existence of the value bridge functions (bg A x W + R f and the weight bridge functions {q%, A x Z + R) which are defined as the solution to the following equations almost surely with respect to the measure ph:
En (A.. Wn] Zn| = Enp (An 1
+ 7 Σ Dh+iiaa, WhtI)TAA (An P2-1) An, Zn
(3.2)
(n Pn-1)
B. [uT (A, Zn)) An, Sh. Tm-1]=
(3.3)
T/K (AN
Here + is a zero function and (Sh, 11) in 3.3 is defined as the importance sampling ratio pn (Sa, 1'n = PT,, (S,, (S,, 1'n-1,,,111 11)
We use "confounding bridge function" and "bridge function" interchangeably throughout the paper. We remark that in the proximal causal inference literature, the existence of such bridge functions bears more generality than assuming certain complicated completeness conditions (Cui et al.) 2020). as discussed by Kallus al. (202I). The existence of such bridge functions justinied by conditions on the the rank of certain conditional probabilities or singular values of certain conditional expectation linear operators. See Appendix
for examples of Assmuption 3.2 under previous choice of H.
Now given Assumption 3.1 and 3.2 on the existence of proxy variables and bridge functions, we are ready to present the main identification result. It represents the true policy value J(TT) via the value bridge functions, is concluded in the following theorem.
Theorem 3.3 (Identification of policy value). Under Assumption dependent policy π E [1(H), it holds that
3.1 and 3.2 for any history-
((z)= = F(b"), where F(b") = Ezo Do((a,
(3.4)
LaEA
See Appendix D for detailed proof. Note that although we have assumed the existence of both the value bridge functions in (.2) and the weight bridge functions in (3.3). Theorem 3.3 represents J()) using only the value bridge functions. In (322) all the random variables involved are observed by the learner and distributed according to the data distribution ph, which means that the value bridge functions can be estimated from data. This overcomes the confounding issue.
3.2 POLICY EVALUATION VIA MINIMAX ESTIMATION WITH UNCERTAINTY QUANTIFICATION
According to Theorem 3.3 and Assumption 3.2 to estimate the value ((T) of क E I[))), it suffices
to estimate the value bridge functions (b% ! by solving (3.2). which is conditional moment equation. To this end, we adopt the method of minimax estimation (Dikkala et al.) 2020 Uehara et al.
2021 Duan et al. 202T). Furthermore, in order to handle the distributional shift between behavior

---

Published as a conference paper at ICLR 2023
policy and target policies, we construct sequence of confidence regions for {bg)) based on minimax estimation, which allows us to apply the pessimism principle by finding the most pessimistic estimates within the confidence regions.
Specifically, minimax estimation involves two function classes C {b A W + RJ and G G {g: : A x Z + R), interpreted the primal and dual function classes, respectively. Theoretical assumptions on B and G are presented in Section[] In order to find functions that satisfy (3.2). suffices to find b- (bI,... .b)) B@H such that the following conditional moment
(bn, 1 Zn) = Ex (An, Wa) - RATT (An OR, 1 1--
Σ a'EA
bati(d'' (An, T An. ZA
(3.5)
is equal to zero almost surely for all h [H], where b is zero function. Intuitively, the quantity can be interpreted as the "Bellman residual" of the value bridge functions b. Notice that being zero almost surely for all h [M] is actually a conditional moment equation, which
3.5
3.5
Is equivalent to finding b E B&H such that the following residual mean squared error (RMSE) is
minimized for all h:
C% (br, bb-1) E. [(7 (bs, bb+11 Z.
(3.6)
It might tempting directly minimize the empirical version of (36). However, this is not viable as one would obtain a biased estimator due to an additional variance term. The reason is that the quantity defined by (3.5 conditional expectation and therefore RMSE defined by (3.6) cannot be directly unbiasedly estimated from data (Farahmand et al.) 2016). In the sequel, we adopt the technique of minimax estimation to eircumvent this issue. In particular, we first use Fenchel duality to write (3.6) as
(b,, bb+1) = 4
max e (bn, 1)+1) Zx) g( An, 7p) - Ag(An. (1))-)((AA)))) DEC
2
A 0, (3.7)
which holds when the dual function class G is expressive enough such that f (br, by+ 1/2x G. Then thanks to the interchangeability principle (Rockafellar and Wets| 2009 Dai et al. 2017 Shapiro al. 202T), we can interchange the order of maximization and expectation and derive that
CT,(bnnbb+) b1+1) 4X max Exz, (b,, I Zn) g(A,, Zp) Ag( Z gEG
(3.8)
The core idea of minimax estimation is to minimize the empirical version of (3.8) instead of (3.6). and the benefit of doing is fast statistical rate of -112/) (Dikkala al, 2021), as we can see in the sequel. For simplicity, in the following, we define t with parameter >> O as
2020 Uehara et al.
B x B
@ (br, bb+1ig) = E [ (br, (in1)(An,) Zn) 9(An, - A0(An, 2.
(3.9)
and we denote by BA A. B B G + I the empirical version of $1 i. i.e.
R.h (bn = EGp [ (An, WT. RA (An
Σ ba 1) (An On In-1)) g(AA, Zn. Ag(An, Zn)² (3.10)
a'E.A
where Ex, denotes the empirical version of E, based on dataset D described in Section 2.2
Furthermore, note that the value bridge functions .b..... ......... by. admit sequential dependence structure. To handle such dependency, for any स E [TH)), h E [H). and bb+1 E B, we first define the minimax estimator by (bx++))) (aa++))a) as
(bx41)) = arg min max L. ih (bh, bb+1: 9)
(3.11)
beB
Based on 3.11 we propose a confidence region for b"Th = (bf, ... b7:) B as
CR (5) b R@H
max
(br, bn+1: max t (bx+)))) bx+1:)) s.. (3.12)
seC
gEG
7

---

Published as a conference paper at ICLR 2023
Algorithm Proxy variable Pessimistic Policy Optimization (P30)
Input: confidence parameter Ç > O, regularization parameter À 0, dataset ID classes B and G.
2: Construct minimax estimator confidence region CR" (E) for each и E [T(H) by (3.12).
3: Policy evaluation: pessimistically estimate (T) for each E [I(H) by (.13).
4: Policy optimization: set मे by (3.14).
5: Output: ßे = (Th mm))
From the above definition" | one can see that CR (5) is actually coupled sequence of confidence regions, where each single confidence region aims to cover a function b%, For notational simplicity, we use single notation CR" (5) denote all the confidence regions. Intuitively, the confidence region CR (E) contains all b E B whose RMSE does not exceed that of (b,, (bn++)), 1). ba+1) by much each [H]. The confidence region takes the sequential dependence of confounding bridge functions into consideration in the sense that each b E CR" (E) is restricted through the minimax estimation loss between continuous steps. As we show in Section D with high probability, the confidence region CR (E) contains the true bridge value functions b". More importantly, every b CR* (E) enjoys fast statistical rate of On 1/2).
Now combining the confidence region (3.12) and the identification formula (3.4), for any policy II(H),, adopt pessimistic estimate of the value of J (
Jeess (x)) = min F(b), where F(b) E,
Σ LAEAA
bi) Wi)
bi
(3.13)
bECR" (E)
3.3
POLICY OPTIMIZATION
Given the pessimistic value estimate 3.13 P30 chooses 7 which maximizes Jpess(T). that is,
arg max Jress (T).
(3.14)
=EI(HH)
we show that under some mild assumptions on the function classes IB and G and under only partial coverage assumption on the dataset ID, the suboptimality (2.2) of Algorithm decays at the fast statistical rate of O(n -1/2), where (-) omits H and factors that characterize the complexity of the function classes
We summarize the entire P3 algorithm in Algorithm In Section 4
4 THEORETICAL RESULTS
In this section, we present our theoretical results. For case of presentation, we first assume that both the primal function class B and the policy class 11(H) are finite sets with cardinality [IB] and [II(H)), respectively. But we allow the dual function class G to an infinite set. Our results can be easily extended to infinite B and II()) using the notion of covering numbers (Wainwright 2019), which we demonstrate with linear function approximation Section H.I
We first introduce some necessary assumptions for efficient learning of the optimal policy. To begin with, the following Assumption 4.1 ensures that the offline data generated by n¹ has good coverage over x*. The problem would become intractable without such an assumption (Chen and Jiang 2019). Assumption 4.1 (Partial coverage). We assume that the concentrability coefficient for the optimal policy n², defined as C=' == max E, [[q (As, ) satisfies that O +o0.
Very importantly, Assumption 4. only assumes the partial coverage, i.c., the optimal policy л¹ is well covered by " (Jin et al. uniform coverage, i.e., the entire policy class IT()) is covered by n (Chen and Jiang, 2019 9) in the sense that ma(+))I(H) C +oc. See Appendix B. for more about partial coverage in POMDP.
2021 Uehara and Sun 2021), which is significantly weaker than the
The next assumption is on the functions classes B and G. We require that and C are uniformly bounded, and that G is symmetric, star-shaped, and has bounded localized Rademacher complexity.
'We refer the readers to Appendix B.I for a detailed comparison of the minimax-typee loss (and confidence region) with the least-square-typeer loss (and confidence region) used by Xie al. (02T)
8

---

Published as a conference paper at ICLR 2023
Assumption 4.2 (Function classes IB and G). We assume the classes B and G satisfy that: i) There exist MB, Ms < to0 such that B, G are bounded by supses wew LaEA b(a, w) S Mg
suPbeg (u 2 (g(a, 2)1 & Mg: ii) is star-shaped, i.e. for any g E G and X E [0, 1}, holds that Ag E G; iii G symmetric, i.e. for any g E G, holds that -9 E G; iv) For any step h E [H], G has bounded critical radius hGG,.. which solves inequality Rn (G; a) S a² MMa.
where Ra(G, a) is the localized population Rademacher complexity of & under the distribution of (An: Zn) induced by n², that is,
n cg Zni 2mnl
Rr (R,
sup Lo
71
with l1912 defined as (g, 2,) random variables { independent of (An, Zn) and independently uniformly distributed on {+1,-1). Also, we denote ag = m OGg.h.
Finally, to ensure that the minimax estimation in Section 3.2 learns the value bridge functions
unbiasedly, we make the following completeness and realizability assumptions the function classes B and G which are standard in the literature (Dikkala et al., 22200] Xie et al.) [021] Shi et al., 2021).
Assumption 4.3 (Completeness and realizability). We assume that, i) completeness: for any h [H any क E IIH,), and any bn. b E IB, it holds that 2x R (bn, bn-1) 1) E G where ET, is defined in (3.5):
ti) realizability: for any h E [H. any π E II()), and any bn-1 E B, there exists b* such that C (b", bb+1) S CB for some CB < +o0, i.e., we assume that
max 0 5 (EII()) EB ERER
min E,3 (67 (An, [ +00.
Here the completeness assumption means the dual function class G is rich enough which guarantees the equivalence between (%,(') ()) and max @ (t.sg)) The realizability assumption means that the primal function class B is rich enough such that (3.2) always admits an (approximate) solution.
With these technical assumptions, we can establish our main theoretical results in the following theorem, which gives an upper bound of the suboptimality (2.2) of the policy ā output by Algorithm [
Theorem 4.4 (Suboptimality). Under Assumptions 3.2 4.1
4.2 and 4.3 by setting the regular-
ization parameter À and the confidence parameter { as X 1 and
8 MB Mî log( [B] (1))H//)\/
then probability at least 1 - 38, it holds that
SubOpt(ft S C.VC=* H MM
+ Ci OFV Mg 1/4
where = min 4c1 exp(-c2na Here C"', ..G. and Eg are defined in Assumption 4.1 4.2
and 4.3 respectively. And C2 C₁ c1, and 02 are some problem- independent universal constants.
We introduce all the key technical lemmas and sketch the proof of Theorem 4.4 in Section D We refer Appendix (or a detailed proof. When it holds that aggn Öm 1/2) and cg 0, Theorem i.plimplies that (f) < (n-1/2), which corresponds to a "fast statistical rate" for minimax estimation (Uehara et al. 202T). The derivation of such a fast rate relies on a novel analysis for the risk of functions in the confidence region, which is shown by Lemma D.3 in Section D Meanwhile, for many choices of the dual function class G. it holds that ag,n scales with vlogNN where NG. denotes the complexity measure of the class G. In such cases, the suboptimality also scales with VlogNG, without explicit dependence on the cardinality of the spaces S, A, or O. Finally, we highlight that, thanks to the principle of pessimism, the suboptimality of 30 depends only on the partial coverage concentrability coefficient C"" which can be significantly smaller than the uniform coverage concentrability coefficient sリрzеπι()) C In conclusion, when ag, /log////// and c3 = 0, the P 30 algorithm enjoys a Ö(H / C log suboptimality.
Linear function approximation. Theorem 4.4 can be readily extended the case of linear function approximation (LFA) with infinite-cardinality B and II(H), which yields an Ö( H/dd/n) subopti- mality. Due to space limit, we defer the detailed setup and main results of LFA to Appendix H.T
'The constant Ms might seem to be proportional to |A| due to the summation Eas A b(a, w). but it is not. The reason is that the definition of the true confounding bridge function in (3.2) involves a product with Ta (-1On, Ta-1) which is distribution over A. Thus the summation over A essentially average over A.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
Zhaoran Wang acknowledges National Science Foundation (Awards 2048075, 2008827, 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J.P. Morgan, and Two Sigma for their support. Zhuoran Yang acknowledges Simons Institute (Theory of Reinforcement Learning) for the support. The authors would like thank Zhihan Liu for helpful discussions on minimax estimators.
REFERENCES
ABBASI-YADEE YADKORI, Y., PÁL., D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24 2312-2320.
ANTOS, A., MUNOS, R. and SZEPESVÁRI, C. (2007). Fitted q-iteration in continuous action-space mdps
AUER, P. (2002). Using confidence bounds for exploitation-exxlorrtion trade-offs. Journal of Machine Learning Research 397-422.
AZIZZADENESHELI, K., YUE, Y. and ANANDKUMAR, A. (2018). Policy gradient in partially observable environments: Approximation and convergence. arXiv preprint arXiv: 181.008000
BELLMAN, R. and KALABA, R. E. (1965). Dynamic programming and modern control theory, vol. 81. Citeseer.
BENNETT, A. and KALLUS, N. (2021). Proximal reinforcement learning: Efficient off-policy evaluation in partially observed markov decision processes. arXiv preprint voXiv:2110.15332.
BENNETT, A., KALLUS, N., LI, L. and MOUSAVI, A. (2021). Off-policy evaluation in infinite-
horizon reinforcement learning with latent confounders. In International Conference Artificial Intelligence and Statistics. PMLR.
BUCKMAN, J., GELADA, C. and BELLEMARE, M. G. (2020). The importance of pessimism in fixed-dataset policy optimization. arXiv preprint vrXiv:2009.06799
BURAGO, D., DE ROUGEMONT, M. and SLISSENKO, A. (1996). On the complexity of partially observed Markov decision processes. Theoretical Computer Science 157 161-183.
CHAKRABORTY, B. and MOODIE, E. (2013). Statistical methods for dynamic treatment regimes. Springer-Veriee doi 10 978-1.
CHAKRABORTY, and MURPHY, S. A. (2014). Dynamic treatment regimes. Annual review of statistics and its application 447-464.
CHEN, J. and JIANG, N. (2019). Inforriaion-theerrtiicc considerations in batch reinforcement learning. In International Conference on Machine Learning. PMLR.
CHERNOZHUKOV. V., NEWEY, W., SINGH, R. and SYRGKANIS, V. (2020). Adversarial estimation of riesz representers. arXiv preprint arXiv:2101.0000
CUT, Y., PU, H., SHI, X., MIAO, W. and TCHETGEN, T. (2020). Semiparametric proximal causal inference. arXiv preprint arXiv:201 arXiv:2011.084// 1.084/1...
DAI, B., HE, N., PAN, Y., BooTS, and SONG, L. (2017). Learning from conditional distributions via dual embeddings. In Artificial Intelligence and Statistics. PMLR.
DANI, V., 9, HAYES, T. and KAKADE, S. M. (2008). Stochastic linear optimization under bandit feedback. s Annual Conference on Learning Theory 355-366.
DIKKALA, N., LEWIS, G., MACKEY, L. and SYRGKANIS. V. (2020). Minimax estimation of conditional moment models. Advances Neural Information Processing Systems 33 12248- 12262.
10

---

Published as a conference paper at ICLR 2023
DUAN, JIN, and LI, Z. (2021). Risk bounds and rademacher complexity in batch reinforcement learning. International Conference on Machine Learning. PMLR.
DULAC-ARNOLD, G., LEVINE, N., MANKOWITZ, D. J., LI, J., PADURARU, C., GOWAL, S. and HESTER, (2021). Challenges of real-worke reinforcement learning: definitions, benchmarks and analysis. Machine Learning 110 2419-2468.
EFRONI, Y., JIN, C., KRISHNAMURTINY, A. and MIRYOOSEFI, S. (2022). Provable reinforcement learning with a short-term memory. arXiv preprint arXiv:2202.03983
FARAHMAND, A.-M., GHAVAMZADEH, M., SZEPESVÁRI, C. and MANNOR, S. (2016). Regularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research 17 480904444400 4874.
FEI, Y. and Xu, R. (2022). Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforce- ment learning. In International Conference on Machine Learning. PMLR.
FOSTER, D. J. and SYRGKANIS, V. (2019). Orthogonal statistical learning. arXiv preprint arXiv:1901.099 0900009036.......
FRISTON, K. J., HARRISON, L. and PENNY, (2003). Dynamic causal modelling. Neuroimage 19 1273-1302.
GOLDSMITH, J. and MUNDHENK, M. (1998). Complexity issues in Markov decision processes, In Computational Complexity Conference.
GOTTESMAN, O., JOHAANSON,, F., KOMOROWSKI, M., FAISAL, A., SONTAG, D., DOSII-VELES F. and CELI, L. A. (2019). Guidelines for reinforcement learning in healthcare. Nature medicine 25 16-18.
GUo, Z. D., DOROUDI, S. and BRUNSKILL, E. (2016). A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics. PMLR.
HE, J., WANG, T., MIN, Y. and GU, Q. (2022). A simple and provably efficient algorithm for asynchronous federated contextual linear bandits. Advances in neural information processing systems.
HUANG, A., CHEN, J. and JIANG, N. (2023). Reinforcement learning low-rank mdps with density features. arXiv preprint arXiv:2302.02252.
JAFARNIA-JAHROMI, M., JAIN, R. and NAYYAR, A. (2021). Online learning for unknown partially observable mdps. arXiv preprint arXiv:2102.
JANNER, M., LI, Q. and LEVINE, S. (2021). Offline reinforcement learning as one big sequence modeling problem. Advances in neural information processing systems 34.
JIN, C., KAKADE, S., KRISHNAMURTHY,, A. and LIU, Q. (2020). Sample-efficient reinforcement learning of undercomplete pomdps. Advances in Neural Information Processing Systems 33 18530-18539.
JIN, Y., YANG, Z. and WANG, Z. (2021). Is pessimism provably efficient for offline ri? In International Conference Machine Learning, PMLR.
KALLUS, N., MAO, X. and UEHARA, M. (2021). Causal inference under unmeasured confounding
with negative controls: A minimax learning approach. arXiv preprint UrXiv:2103.1402:
KALLUS, N. and ZHOU, A. (2020). Confounding- robustt policy evaluation in infinite-horizon
reinforcement learning. Advances in Neural Information Processing Systems 33 22293-22304.
KALLUS, N. and ZHOU, A. (2021). Minimax-optimal policy learning under unobserved confounding. Management Science 67 2870-2890.
KIDAMBI, R., RAJESWARAN, A., NETRAPALLI, P. and JOACHIMS, T. (2020). Morel: Model-based offline reinforcement learning. arXiv preprint 25555

---

Published as a conference paper at ICLR 2023
KRISHNAMURTHY, A., AGARWAL, A. and LANGFORD, J. (2016). Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems 29.
KUMAR, A., ZHOU, A., TUCKER, G. and LEVINE, S. (2020). Conservative q-learning for offline
reinforcement learning. Advances Neural Information Processing Systems 33 1179-1191.
LEVINE, S., KUMAR, A., TUCKER, G. and Fu, (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643
L1. L., CHU, W., LANGFORD. J. and SCHAPIRE, R. E. (2010). A personalized news article recommendation. In Proceedings of the 19th international conference on World wide web.
approach to
LIPSITCH, M., TCHETGEN, E. T. and COHEN, T. (2010). Negative controls: tool for detecting confounding and bias in observational studies. Epidemiology (Cambridge, Mass.) 21 383.
LIU, Q., CHUNG, A., SZEPESVÁRI, C. and JIN, C. (2022). When is partially observable reinforce- ment learning not scary? arXiv preprint 2rXiv:2204.08967
LIU, Y., SWAMINATHAN, A., AGARWAL, A. and BRUNSKILL, E. (2020). Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202.
LOVEJOY, W. S. (1991). A survey of algorithmic methods for partially observed markov decision processes. Annals of Operations Research 28 47-65.
MASTOURI. A., ZHU, Y., GULTCHIN, L.,, KORBA, A., SILVA, R., KUSNER, M., GRETTON, A. and MUANDET, K. (2021). Proximal causal learning with kernels: Two-stage estimation and moment restriction, In International Conference on Machine Learning. PMLR.
MIAO, W., GENG, Z. and TCHETGEN TCHETGEE, E. (2018a). Identifying causal effects with proxy variables of unmeasured confounder. Biomerrika 105 987-993.
MIAO, W., SHI, X. and TcHETGEN, E. T. (2018b). A confounding bridge approach for double negative control inference on causal effects. arXiv preprint arXiv:/8083 04945.
MIN, Y., HE, J., WANG, T. and GU, Q. (2022a). Learning stochastic shortest path with linear function approximation. In International Conference on Machine Learning. PMLR.
MIN, Y., WANG, T., XU, R., WANG, Z., JORDAN, M. and YANG, Z. (2022b). Learn to match with no regret: Reinforcement learning in markov matching markets Advances in Neural Information Processing Systems.
MIN, Y., WANG, T., ZHOU, D. and GU, Q. (2021). Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems 34 7598-7610.
MUNDHENN, M., GOLDSMITH, J., LUSENA, C. and ALLENDER, E. (2000). Complexity of finite-horizon Markov decision process problems. Journal of the ACM (JACM) 47 681-720.
MUNOS, R. and SZEPESVÁRI, C. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research 9.
OBERST, M. and SONTAG, D. (2019). Counterfactual off-policy evaluation with gumbel-max structural causal models. In International Conference on Machine Learning. PMLR.
PAPADIMITRIOU, C. H. and TSITSIKLIS. J. N. (1987). The complexity of markov decision processes. Mathematics of operations research 12 441 450-
PEARL, (2009). Causality. Cambridge university press.
RASHIDINEJAD, P., ZHU, B., MA, C., JiAo, J. and RUSSELL, S. (2021). Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103.1 12011
ROCKAFELLAR, R. T. and WETS, R. J.-B. (2009). Variational analysis, vol. 317. Springer Science & Business Media.
12

---

Published as a conference paper at ICLR 2023
SHALEV-SHWARKE S.. SHAMMAH, S. and SHASHUA, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arxiv:1110.03295.
SHAPPRO, A., DENTCHEVA, D. and RUSZCZYNSKI, A. (2021). Lectures stochastic programming: modeling and theory. SIAM.
SIII, C., UEHARR,, M. and JIANG, N. (2021). A minimax learning approach to off-policy evaluation in partially observable markov decision processes. arXiv preprint arXiv:2111.0678.
SHI, C., WANG, X., LUO, S., ZhU, H., YE, and SoNG, R. (2022). Dynamic causal effects evaluation a/b testing with reinforcement learning framework. Journal of the American Statistical Association 1-29.
SINGH, R. (2020). Kernel methods for unobserved confounding: Negative controls, proxies, and instruments, arXiv preprint arXiv:2012.1033
SUN, P., KRETZSCHMAR, H., DOTIWALLA, X., CHOUARD, A., PATNAIK, V., TSUL, P., GUO, J., ZUOU, Y., CIAI,, Y., CAINE, B. ET AL. (2020). Scalability perception for autonomous driving: Waymo open dataset. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition.
SUTTON, R. S. and BARTO, A. G. (2018). Reinforcement learning: An introduction. MIT press.
TCHETGEN, T., YING, A., CUI, Y., SHI, X. and MIAO, W. (2020). An introduction to proximal causal learning, arXiv preprint arXiv:2009.10982.
TENNENHOLIZ, G., SHALIT, U. and MANNOR, S. (2020). Off-policy evaluation in partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34.
TSOUKALAS, A., ALBERTSON, T., TAGKOPOULOS, I. ET AL. (2015). From data optimal decision making: a data-driven, probabilistic machine learning approach to decision support for patients with sepsis. JMIR medical informatics 3 e3445.
UEHARA, M., IMAIZUMI, M., JIANG, N., KALLUS, N., SUN, W. and XIE, (2021). Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency, arXiv preprint arXiv:2102.02981.
UEHARA, M. and SUN, W. (2021). Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage. arXiv e-prints arXiv-2107
VLASSIS, N., LITTMAN, M. L. and BARBER, D. (2012). On the computational complexity of stochastic controller optimization in POMDPs. ACM Transactions on Computation Theory (TOCT) 4 1-8.
WAINWRIGHT, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, vol. 48. Cambridge University Press.
XIE, T., CHENG, C.-A., JIANG, N., MINEIRO, P. and AGARWAL, A. (2021). Bellman-consisse pessimism for offline reinforcement learning. Advances in neural information processing systems 34.
XIE, T. and JIANG, N. (2020). Q* approximation schemes for batch reinforcement learning: thcoretical comparison. In Conference Uncertainty in Artificial Intelligence. PMLR.
XIONG, Y., CHEN, N., GAO, X. and ZHOU, X. (2021). Sublinear regret for learning pomdps. arXiv 107.0363.
arXiv:2 1000
YAN, Y., LI, G., CHEN, Y. and FAN, J. (2022). The efficacy of pessimism in asynchronous leeaainng.. arXiv preprint arXiv:2203.07368.
YIN, M., DUAN, Y., WANG, M. and WANG, Y.-X. (2022). Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.0580.
13

---

Published as a conference paper at ICLR 2023
YIN, M. and WANG, Y.-X. (2021). Towards instance-optimall offline reinforcement learning with pessimism. Advances neural information processing systems 34.
YU, T., KUMAR, A., RAFAILOV, R., RAJESWARAN, A., LEVINE, S. and FINN, C. (2021). Combo: Conservative offline model-based policy optimization. Advances in Neural Information Processing Systems 34.
ZANETTE, A. (2021). Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online International Conference on Machine Learning. PMLR.
ZANETTE, A., WAINWRIGHT, M. J. and BRUNSKILL, E. (2021). Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems 34.
ZHAN, W., HUANG, B., HUANG, A., JIANG, N. and LEE, J. D. (2022). Offline reinforcement learning with realizability and single-policy concentrability. arXiv preprint arXiv:2202.0466 04264444..44...
ZHANG, J. and BAREINBOIM, E. (2016). Markov decision processes with unobserved confounders: causal approach. Tech. rep., Technical report, Technical Report R-23, Purdue Al Lab.
14

---

Published as a conference paper at ICLR 2023
CONTENTS
Introduction
I.1
Overview Techniques
Related Work
Preliminaries
2.1
Episodic Partially Observable Markov Decision Process
2.2
Offline Data Generation: Confounded Datasel
2.3
Learning Objective
3
Algorithm: Proxy Variable Pessimistic Policy Optimization
3.1
Policy Value Identification via Proximal Causal Inference
3,2
Policy Evaluation via Minimax Estimation with Uncertainty Quantification
3.3
Policy Optimization
4
Theoretical Results
8
Table of Notations
16
Further Discussion
17
B. Further Discussion Related Work
17
B.2 Discussion about the partial coverage
19
B.3 Potential Application: Real-world Example of Proximal Causal Inference in RL.
19
Proximal Causal Inference
20
Illustration of Examples
20
C.I.1
Reactive Policy (Example revisited
20
C.1.2
Finite-history Policy (Example 2.2 revisited)
20
1.3
Full-history Policy (Example 2.3
revisited)
21
C.2
Examination of Assumption 3.2
21
D Proof Sketches of Main Theoretical Resulf
23
Proof of Theoreermm3 3.3
24
Proof of Lemmas in Section ))
28
Proof of Lemma D.
29
Proof of Lemma D.2
Proof of Lemma D.3
32
Proof of Lemma
36
Proof of Theorem 4.4
37
15

---

Published as a conference paper at ICLR 2023
H
Details for Linear Function Approximation
38
Main Result for Linear Function Approximation
38
H.2
Auxiliary Results for Linear Function Approximation
39
H.
Proof of Corollary H.2
40
Proof of Lemmas in Appendix
42
Proof of L.5
42
H.4.2
Proof of Lemma
44
Auxiliary Lemmas
46
A
TABLE OF NOTATIONS
Table 2: Table of Notations
Notation
Meaning
(TT
H Policy value E,, 1>> K= A- RA]
bg oh
value bridge function, weight bridge function of a at step h
b", q
value bridge function vector, weight bridge function vector of π
CR (E)
confidence region of ba according (3.12)
an element in the confidence region CR CR" (E)
F(b), F(b)
mapping for identification with ((T) = F(b"), according to (3.4
"Bellman residual" for bridge functions, according to (3.5)
4%
residual mean square loss for 67 according to (36
4
mapping for minimax estimation, according to 3.9
Di (bn+1)
minimax estimator of bū given ba+1, according to
Jpess (T)
pessimistic estimator of J(T), according to (3.13)
policy returned by P30 algorithm, according to 3.1
In this section, we provide a comprehensive clarification on the use of notation in this paper.
We use lower case letters (i.e., 8, a, o, and 7) to represent dummy variables and upper case letters (i.e.. S, A, O, and I') to represent random variables. We use the variables in the calligraphic font (i.e., S. A. O, and H) to represent the spaces of variables, and the blackboard bold font (i.e., IP and O) to represent probability kernels.
We use H = (HA - to denote the space of observable history, where each element E Hr is (partial) trajectory such that тn S {(o),a1), (or, a. We use TO { to denote the behavior policy, where # S + A(A). We use = {TT) H E IT to denote a history- dependent policy with Ta : O x H4-1 + A(A). Also, we use π = { J h= to denote the optimal history-dependent policy. Offline data D is collected by T², as described in Section 2.2
H
We use ph (Ph) and p {PA !f to denote the distribution of trajectories under the policy " and म, respectively, where P and P denote the density of corresponding variables at step h. Also, we use E.,, and E, to denote the expectation w.r.t. the distribution pb and pT, We use É, to denote the empirical version of Ey,, which is calculated on data ID.
16

---

Published as a conference paper at ICLR 2023
Through out the paper, we use (-) to hide problem- indeendendeeeddnnt constants plus logarithm factors. The following table summaries the notations we used in our proposed algorithm design and theory.
constants and use (.) hide
B FURTHER DISCUSSION
B.1 FURTHER DISCUSSION ON RELATED WORK
Reinforcement learning in POMDPs. Our work is related to the recent line of research on developing
provably efficient online RL methods for POMDPs (Guo et al. 2016 Krishnamurthy et al.) [2066]
Jin et al. 2020, Xiong et al.) 2021; Jafamna-Jahrom et al., 2021; Efroni et al.) [0022] Liu al. 2022). In the online setting, the actions are specified by history-depende state does not directly affect the actions. Thus, the actions and observations in the online setting are not confounded by latent states. Consequently, although these work also conduct uncertainty quantification to encourage exploration, the confidence regions are not based on confounded data and are thus constructed differently.
policies and thus the latent
Offline reinforcement learning and pessimism. Our work is also related to the literature offline RL and particularly related to the works based on the pessimism principle (Antos et al. |,,70007 MMunos
and Szepesvári 2008; Chen and Jiang 2019 Buckman al.
2020 Liu et al. [2200] Min al.
2021;Uin et al.j 2021; Zanette|
Zanettee 202 1] Jin et al. Xie et al.
202 1
Uehara and Sun 202 Yin
and Wang 2021; Rashidinejad et al. 2021] Zhan et al. 2022] Yin al. 2022; Yan et al. 2022).
Offline RL faces the challenge of the distributional shift between the behavior policy and the family
of target policies. Without any coverage assumption on the offline data, the number of data needed
to find near-optimal policy can be exponentially large (Buckman et al.) 2020 Zanette (022T). To circumvent this problem, few existing works study offfine RL under a uniform coverage assumption, which requires the concentrability coefficients between the behavior and target policies are uniformly bounded. See, e.g., Antos et al. (2007); MMnos and Szepesvári (2008); Chen and Jiang (2019) and the references therein. Furthermore, more recent line of work aims to weaken the uniform coverage assumption by adopting the pessimism principle in algorithm design (Liu et al. 2020 Jin et al.) 2021 Rashidinejad et al. [202 [Uehara and Sun 2021 Xie al., [021 Yin and Wang 2022 Zanette et al.
2021 Yin et al. [2022] Yan et 2022). In particular, these works proves theoretically that pessimism effective in tackling the distributional shift of the offline dataset. In particular, by constructing pessimistic value function estimates, these works establish upper bounds on the suboptimality of the proposed methods based on significantly weaker partial coverage assumption. That is, these methods can find near-optimal policy as long as the dataset covers the optimal policy. The efficacy of pessimism has also been validated empirically in Kumar et al. (2020); Kidambi et al. (2020); Yu et al. (2021 1); Janner et al. (2021). Compared with these works pessimism, we focus on the more challenging setting of POMDP with a confounded dataset. To perform pessimism in the face of confounders,
conduct uncertainty quantification for the minimax estimation regarding the confounding bridge functions. Our work complements this line of research by successfully applying pessimism to confounded data.
OPE via causal inference. Our work is closely related to the line of research that employing tools from causal inference (Pearl 2009) for studying OPE with unobserved confounders (Oberst and
Sontag 2019; Kallus and Zhou| 2020; Bennett et al. [021 Kallus and Zhou 2021| Mastouri et al. 2021| Shi al. [202] [Bennett and Kallus| 2021 Shi et al.
2022). Among them, Bennett and Kallus (2021) Shi et al. (202)) are most relevant to our work. In particular, these works also leverage
proximal causal inference (Lipsitch et al.) 2010)) Miao et al. 20188 bl Cui et al.) [202 Tchetgen et al.
2020; Singh, 2020) to identify the value of the target policy in POMDPs. See Tchetgen et al. (2020) for a detailed survey of proximal causal inference. In comparison, this line of research only focuses on evaluating a single policy, whereas we focus on learning the optimal policy within class of target policies, As a result, we need to handle a more challenging distributional shift problem between the behavior policy and an entire class of target policies, opposed to single target policy in OPE, However, thanks to the pessimism, we establish theory based on a partial coverage assumption that is similar to that in the OPE literature. To achieve such goal, we conduct uncertainty quantification for the bridge function estimators, which is absent in the the works on OPE. As a result, our analysis is diff different from that in Bennett and Kallus (2021): Shi et al. (202)).
17

---

Published as a conference paper at ICLR 2023
Relations between minimax-typed loss and least-square-ypeed loss (Xie et al., 2021). During the preparation of this paper, we find that in the MDP setting, the pesst--qurr-typpee loss considered by (Xie et al. 2021) can be reformulated to the minimax-typed loss that consider in this paper with a different dual function class. To see this, consider the MDP setting with a single transition tuple (Sh, An, +1+ The goal is estimate the Bellman target (BVi+1): S x A - IR where B is the Bellman operator and Vh+1: S + R is fixed state-value function. For each (s,a) a) E E x A. (B" f141)(s, a) is given by
(Bfh+1)(sa)) = (s) + + (ds's V
Here R₁ is the reward function and is the unknown transition kernel. We use function class F to approximate the bellman target. Then
assume it is known for now, and PA. : 8 A A(8)
based the offline transition data D {s8, J, 07 1)++))==1 the least-square-typed loss function
given in Equation (3.1) of (Xie et al. 2021) becomes
(fw) ED [(fh(Shh An) RA (
-min EN ReEF
[JR(Shh An) Rr - -V++ (Sh+1)
(B.1)
where R2 is an abbreviation for R, An). Using the equality x² -22 -(x= 2) y), we can rewrite the least-square taperee-tppdddd loss (B.1) as
(h = sup
En [ f Ar) - 2R 2Vh+1 ( - fh)(Sh: FIFF
For derivation, we further rewrite first term as
(fn + (A) 2R, 2V
(Shh An) 2R, 2 (S -(Fh) ((h-- -h
With this, we can then rewrite the least-square-typet loss B.1
(h(h)) sup FREF
En (2fh(Sh, An) 2R,, 2Vh+1(S ( fh) (S) An)
- ((n Aw),aAn))))))) A.
Now by defining a new function class Gj depending on f as 9 = (5 - F}, we arrive that
(h+h)) sup o,
ED [ An) - Rr (n++(Sn++1 gh (Sh, An)
1 ggh(S. An)²]: (B.2) (Sp.
$1/2 $1/2 (bp- bR+1; 9n.) we consider in our
This shares the same form as the minimax-typpe -typed loss sup pn work, see 13.10p in the main text. But still there are differences. In (B.2), the dual function gh lies in a dual function class Gr, which depends on the primal function fn- While in our minimax-typed loss, the dual function class does not depends on the primal function.
x.h
Finally, we need to point out that even the two losses share the same form, the form of the confidence region considered by our work is different from that considered by Xie al. (202T). To see this, still using the previous notations, the confidence region in Xic al. (2021) (Equation (3.2)) becomes
(E) = fn E F: (1h) <
Mcanwhile, if we reduce confidence region to the above MDP setting, confidence region should be in the form of
CRA = { E F. Zymm (fn)
min JxEF
CT (t.m((h) SEJ.
(fh)
where CT denotes the Minimmxx-typed-lee on the second form of confidence region, which is key to the derivation fast statistical rates for elements in the confidence region based minimax estimation.
Our algorithm and theoretical analysis are based
18

---

Published as a conference paper at ICLR 2023
B.2 DISCUSSION ABOUT THE PARTIAL COVERAGE
More about the partial coverage (Assumption 4.1). Our work assumes the partial coverage of ID according Assumption 4.1 where we implicitly requires that Pf (Sp, 1)- /Pp (S,, [h-1) +oo for all т E [T)) (we call it the finite-ratio condition from here). We note that this finite-ratio condition can NOT be regarded as the full coverage assumption. Instead, this a regularity condition that arises from causal inference.
First of all, the finite-ratio condition is different from the full coverage assumption in standard MDPs. The Full coverage assumption in standard MDPs usually takes the form that
as) TEL ()( <C,
max
for some fixed C O. This condition means the density ratio of the marginal distributions of (s, a) between any target policy т and the behavior policy >² is uniformly bounded by a constant. This condition (or some similar form) a common and widely accepted form of full coverage in the MDP literature, e.g. (Chen and Jiang] 2019] Xie and Jiang 2020). Note that this constant C is uniform upper bound over the candidate policy class. Very importantly, this constant appears in the final error bound. The partial coverage assmuption in MDP, on the other hand, is commonly formulated as
Ph (s. a) (s, a)
<C,
This condition means the density ratio of the marginal distributions of (s,a) between only the optimal policy n' and the behavior policy n², is bounded by a constant. The form of this assumption is very close to Assumption 4.1 (Partial coverage) in paper. In other words, our Assumption 4.1 is version of the partial coverage assumption that tailored to the POMDP case. Notably, this constant C' in the partial coverage assumption also appears in the final error bound.
As a sharp comparison to both the full coverage and partial coverage assumptions, the finite-ratio condition that the quantity PT (S,, r)) /P (Sn,))-)) < +oo for all π E II(H) does not result in any constant factor that appears in the final error bound. In the case of infinite policy class IT(H), final error bound. Therefore,
allow the ratio to be arbitrarily large and that won't 't hurt this is not coverage assumption. Our finite-ratio condition is a regularity condition that arises from causal inference. This condition is needed to deal with the extra challenge of the confounding issue in our POMP setting. In related works studying OPE under confounded POMDP (Shi et al. 2021). this finite-ratio condition is also needed. Overall, our paper is indeed under partial coverage and the finite ration condition is not a kind of coverage assumption.
B.3 POTENTIAL APPLICATION: REAL-WORDD EXAMPLE OF PROXIMAL CAUSAL INFERENCE IN RL.
Let consider the real-world example of applying the POMDP model to sepsis treatment studied by Tsoukalas et al. (2015). In such an example, the state, action, observation, and reward of the POMDP given by the following:
State variable S₁ refers to the clinical state of the patient, e.g., sepsis, SIRS, Bacteremia, etc. Observable variable On, refers to all the information one can read from a medical device, such as the heart rate, the respiratory rate, blood pressure, blood test result of infection, etc.
Action A₁ refers to certain treatment given to the patient. For example, each antibiotic combination can be considered as an action. As mentioned in Tsoukalas et al. (2015). total of 48 antibiotics have been included in the patient's remedy.
Reward/cost values need to be provided empirically by physicians, based on the severity of each state. In the example of Ts rewards/costs include: Healthy (100,000), No SIRS (50,000). Probable Sepsis (PS, 5000), SIRS (-50), Bacteremia (-10,000), etc.
al. (2015), the states and their corresponding
Finally, a history trajectory is the record of antibiotic treatment received by the patient. The behavior policy is some treatment plans that have been applied to some patients to generate the dataset.
19

---

Published as a conference paper at ICLR 2023
When using reactive policies (Example 2.1 observation variable Oh-1 which reflects the patient's ' clinical state at the last treatment time step, and the negative control outcome variable (W;,) is just the observation variable O,, the current time step. Furthermore, when the observation O contains enough information to reflect the underlying state S, which basically implies certain full rank assumption, guarantee the existence of the bridge functions (See Appendix C
the negative control action variable (Z₁) is just the
then use Example C. to
C PROXIMAL CAUSAL INFERENCE
In this Section, we complement the discussion of proximal causal inference in Section 3.1
C.I ILLUSTRATION OF EXAMPLES
In this subsection, we give detailed discussions for the three examples of history-dependent policies mentioned in Section 2.3 In particular, we give causal graphs of the POMDP when adopting these policies. Also, we explain the choice of negative control variables for these policies in Section 3.1
C.I.1 REACTIVE POLICY (EXAMPLE 2.1 REVISITED)
When the target policy is a reactive policy, it only depends on the current observation O₁- That is, H4-1 [ and - Ø for each [#]. The causal graph for such a target policy is shown in Figure 2 In this case, we choose the negative control action as Zn O (node in green) and the negative control outcome as W O2 (node in yellow). ). By this choice, we can check the independence condition in Assumption 3.1 via Figure 2 i.e., under ph.
On 1 On, Ra, On+1 Sh, An On 1 An, Sh Sh.
Ax-1
An
O
Oh
O++1
Sa-1
Sn
S
R
R
Figure 2: Causal graph for reactive policy. The dotted nodes indicate that the variables are not stored in the offline dataset. Solid arrows indicate the dependency among the variables. Specifically, The red arrows depict the dependence of the target policy on the observable variables. The blue arrows depict the dependence of the behavior policy the latent state. The negative control action and outcome variables at the f-th step are filled in green and yellow, respectively.
C.1.2 FINITE-IISTORY POLICY (EXAMPLE 2.2 REVISITED)
When the target policy a is finite-length history policy, it depends on the current observation and history of length at most k. That is, H = (O A) 8 min(k,h-1} for some k N, lh- At), 10 An-1)) where the index = max(1, h k}. The causal graph for such a target policy is shown Figure B this case, we choose the negative control action Zn, = 0 (node in green) and the negative control outcome as W,, = O₂ (node in yellow). By this choice, we can check the independence condition Assumption 3.1 via Figure i.e., under Pbb
O-11 1 On, R4, Oh+1 Sh, A,, On A -....... O₁, Ar,
On L An, S On- A O₁, A
20

---

Published as a conference paper at ICLR 2023
A--1
A²
A
O11
O₂
Oh+1
S
S
Sh
S
R
Ri
R
Figure 3: Causal graph for finite-length history policy. Index I = max - k]. The dotted nodes indicate that the variables not stored in the offline dataset. Solid arrows indicate the dependeney among the variables. Specifically, The red arrows depict the dependence of the target policy on the observable variables. The blue arrows depict the dependence of the behavior policy the latent state. The negative control action and outcome variables at step h are filled in green and yellow.
C.1.3 FULLOHISTORY POLICY (EXAMPLE 2.3 REVISITED)
When the target policy is full-history policy, it depends on the current observation and the full history. That is, H (O x A) a)@(h-1) and - = ((O1, ...
(0 The causal graph for such target policy is shown in Figure 4 In this case, choose the negative control action as Zμ = Ou (node in green) and the negative control outcome as W, O₁ (node in yellow). this choice, check the independence condition in Assumption 3.1 via Figure 4 i.e., under P
Oo L On, RA, Ou+1 Sa, Ad, On-1, A4-1,". O1, A1,
On 1. An. Sh-1, 1, Oh-1, A O1, A Shh
A
A₁
O
On
Oh+1
Ov
S
Sh
S
R1
Figure 4: Causal graph for full-length history policy. The dotted nodes indicate that the variables not stored in the offline dataset. Solid arrows indicate the dependency among the variables. Specifically. The red arrows depict the dependence of the target policy on the observable variables. The blue arrows depict the dependence of the behavior policy the latent state. The negative control action and outcome variables at step h are filled in green and yellow, respectively.
C.2 EXAMINATION OF ASSUMPTION 3.2
In this subsection, we give concrete examples when the Assumption 3.2 holds, i.c., the confounding bridge functions exist.
21

---

Published as a conference paper at ICLR 2023
Example C.1 (Example revisited) For the tabular setting (i.e., S, A, and O finite spaces) and reactive policies (i.e., Th : O + ((A)), the sufficient condition under which Assumption 3.2 holds is that
rank (Ph (On|Sw) = |S], rank(P)(Onn11SA) = -|S, where Pn Pn (hh) denote an [S] |O] matrix whose (s, 0) element is ( = oSSh = 8), and P): ( is defined similarly.
(C.1)
Proof of Example C.1 Recall that for reactive policies, the history information FA-1 2. We first show that under condition (C.1)) there exist functions {b% 1 and {g% 1hm1 which solve the following equations
Ex ( An) S.]
= Ezd (An +7
bhtz (1- An.
(C.2)
(Sa)
En 10% (A,, 0 Sm]
(C.3)
2 (A,
Then show that the solutions to (C.2) and C.3 also solve (.2 and (3.3). The difference between (C.2) and (3.2) is that in (C.2) we condition on the latent state Sk. rather than the observable negative control variable Zn. In related literature (Bennett and Kallus [021 Shi et al. 2021), the solutions to
and CC.3 are referred to as unlearnable bridge functions.
We first show the existence of {bg 1 in a backward manner. Denote by bū+1 zero function. Suppose that 17,1 exists, we show that by, also exists. Since now spaces S, A. and O are discrete, we adopt the notation of matrix. In particular, we denote by
B R LAXIOo
B(a, o) bn((a,)) 0),
O O DISIIO
(ss 0) = Phn(On = o|S = =))
R. E RIIIII R(s, a) = Rags (ATTA(ANON)) + Σ D% (a', Ou+I)TT (An = a, S₁ =
The existence of 6g satisfying C.2) is equivalent to the existence of B solving the matrix equation
BOT= = R.
(C.4)
we known that the matrix O is of full column rank, which indicates that CC.4 admits a solution B. This proves the existence of b7. For ( we use similar method by considering
By condition
C.1
Q E R
Q(a = q)(a, 0),
0_ E RlSix|o
O 0s Ph(00 O|S = =);
M/ (SA = C(s,a) T (An = alSh = s)
C E S|
The existence of 9% satisfying
O is equivalent to the existence of Q solving the matrix equation
QO==C
(C.5)
By condition [.1 we known that the matrix O is of full column rank, which indicates that C.5
admits solution Q. This proves the existence of o.. Thus we have shown that there exists [bx 1 F
k=1
and { 9% T==1 which solve equation C22 and (C33). Finally it holds that any solution to C.2 and
C3.) also forms a solution (3.2) and (3.3). which has been shown in Theorem 11 in Shi al.
202
This finishes the proof of Example C.T
Example C.2 (Example 2.2 revisited). For the tabular setting and finite length policies (i.e., Th O x (O x k 1F + A(A)), the sufficient condition under which Assumption 3.2 holds is that, for any action E A.
rank (OxlAAr = a, Oh-hh~h1- --)) 10), rank(P) 1|A, = Sn, (-- = 10] (C.6)
where Ph PO a, 111 is |0| |0] matrix with (o, o'h-th element is Ph: A|An
a, O Oh-k-1 o') and Ph: (0, 4, a, Sh, T is [S||H |O] matrix defined similarly.
22

---

Published as a conference paper at ICLR 2023
Proof of Example C.2
To see this, first prove the existence of {b,). For simplicity, denote by
Pa (PR (On An a, On-R-1)) E [0
for each E A. Also, we denote that
B (br, (a, Oh)) E R0
Ra B RA (An On) + Σ 1/tt O141) ( nh (An O%) |A, a, Oh- 1) R
Then for each A, the existence of (a, ( -) is equivalent the existence of the solution P = R
Such linear equation admits a solution due to our assumption on the matrix Pa. This shows the existence of (b) }. For {q the deduction is similar by considering for each a E A.
T (P) (On A, Sp, a-1))) RRSI|H
Qa = (4h (a, Oh-Oh -h-k-1)) E [
C, Mh (Sh, h-11
E ||
x" (a St
By considering the equation that
T Qa = C.
and using the full rank assumption on matrix Ta, we can obtain the existence of {g This finishes the proof of Example C.2
D PROOF SKETCHES OF MAIN THEORETICAL RESULT
In this section, we sketch the proof of the main theoretical result Theorem 4.4 and we refer to Appendix G for detailed proof. For simplicity, we denote that for any [I
and B&n
Σ by (a, Wi) (aa LoEA
F(b)
F(b) - E.p
Σ by (a, LaEAA
(D.1)
By the definition D.I and Theorem 3.3 for any policy IIHH), it holds that ( F(b"), where we have denoted by b = [b] b7) the vector of true value bridge functions of which are given in (3.2).
Our proof to Theorem 4.4 relies on the following three key lemmas. The first lemma relates the different values of mapping F(-)) induced by true value bridge function ba and any other functions B to the RMSE loss which we aim to minimize by algorithm design. This indeed decomposes the suboptimality (.2).
Lemma D.1 (Suboptimality decomposition). Under Assumption 3.1
3.2 for any policy E II(H)
and b E @ it holds that
F(b*) F(b) < - C bbt1).
where the concentrability coefficient C is defined as C = suphetm Eyp [(T (A,, Zx))
Proof of Lemma D.1 See Appendix F.1 for a detailed proof.
The following two lemmas characterize the theoretical properties of the confidence region (R)(
Specifically, Lemma D.2 shows that with high probability the confidence region of π contains the true
value bridge function b Besides, Lemma D.3 shows that each bridge function vector b CR" CR*(E) (E)
enjoys fast statistical rate (Uehara et al.) 202 for its RMSE loss 2J, defined in (3.6). To obtain such fast rate, develop novel proof techniques in Appendix
23

---

Published as a conference paper at ICLR 2023
Lemma D.2 (Validity of confidence regions). Under Assumption 3.2 and 4.2 4.2 for any 0 < 8 < 1, by setting
< CIA+ M Ma 10g(B
for some problem-inder independent universal constant C₁ > and Ç = min (8, 4c, exp(-o2na ).
holds with probability at least 5 that ba E (E) for any policy x E II(H).
Proof of Lemma D.2 See Appendix F2 for a detailed proof.
Lemma D.3 (Accuracy of confidence regions). Under Assumption 3.2 4.2 and 4.3 by setting the
same as in Lemma D.2 and step h,
with probability at least 1 6/2, for any policy [HH. b CR (E),
(R)(
V (bn, bnt1) S for some
log( ((()))/
M
universal constant C > O, and Ç = min 4c exp(-cena
Proof of Lemma D.3
See Appendix H3 for a detailed proof.
When oG.n E 1/2 and cg 0, Lemma D.3 implies that (b,, bh+1) < Ō(n-1). Now with
Lemma D.1
Lemma D.2 and Lemma D.3 by the choice of &े in P30, we can show that
J(x²) ((a) < O(n 1/2)+ +
max F(b)
min F(b)
bECR (E)
BECR (5)
$ (0mn11/2)
max
F(b) min
F(b)
BECR (E)
BECR
Ö(n (1/2) +
max BECR
F(b) F(b
(E)
H
max
h VC
CT (bn, bn+1),
(D.2)
BECR
hml
where the first inequality holds by Lemma D.2 the second inequality holds from the optimality of ã in Algorithm [ the third inequality holds directly, and the last incquality holds by Lemma D.I. Finally, by applying Lemma D.3 to the right hand side of (D.2), we conclude the proof Theorem 4.4
E PROOF OF THEOREM 3.3
Proof of Theorem
3.3 For any step h, we denote Jn(x) = E. RA (Sh, An)]. We have that
(T) Ez (S An)
En E. RR (Sh, An) Sh, In
Es
Rn (n(Ss,
E
E
In-1)
Sn, Tn-1
LREAA
where the second and the last equality follows from the tower property of conditional expectation. Using the definition of density ratio (n,, TT-1) in Assumption 3.2
change the outer
24

---

Published as a conference paper at ICLR 2023
expectation to E by
(T) E
(nn, la-1) Br
Σ LaEA
Rs (S), Pa-1)
Sny h-
Σ
Rh (Sh, (a(aaOn,
lmm-)) ( (n(s I'm1))
LaEA
The Th(a (m-1)
Th (a/Sh) (Sn, a)
(5 rh-1)
(a)(a))
aaEA
(An 1h-1)
Ex''
(Sh An)
(Sn,
Sha OndIn-
(Ap (hh)
E Ra(Sns An) Thh (An lh-1) Mu (Sh. In-1)
(An)sA)
where step (a) follows from the fact that A, (-(())) and satisfies A₁ 1 On, r 1S under n².
Now using the definition (3.3) of weight bridge function zi in Assumption 3.2
we have that
(T) E [Rn An) (A, On I 1) E 10 (An. Zn)) Sn, An,
@ E [ AA) TTA (AA 10,, - 9% (An, Zn))
= ,,, B [R (S),, AA) TA (A, O 1'n-1) q% (An, 2n) An, 2y]]
E g [R), (Sp, AA) (AA OO,, (m-1) AA. Zn. 9% (An. Zn.)
where step (a) follows from the assumption that Zn. On, Rn An,
Th-1 by Assumption 3.1
Now using the definition (.2) of value bridge function by, in Assumption 3.2 we have that
(T)
E,
6% (An, Wh) -7 Σ Ege
b Wh+1) (An On I-- An. Zn
l% (An, Znn)
a'EA
Ey, [SSS, Ans On, Wh, WA+1, h-1) 9% (An; Zn)
EE, [E,, [f(S An. On, WR. W V141,In-11 (An, Zn))Sn, An, On, Wh, Wh+1: W I2-1ll,
-E,. [f(S,; An, On, Wh. WA W1+1, Th-1) (0-11)B... E (4% (A,, ; Zn) Sh,, An, On, Wh, W8+1, In-]),
E,, [f(Sh, An. On Wh. W (4+1.In-1 E 19% (Ap, Zn)) An,
where for simplicity we have denoted that
f(Sn, An, Ob, Wh, Wh+1,Ta h--1) = (An, Wn) - Σ a'EA
(a', ( (T (An On, Im-
and step (a) follows from the assumption that Zn, 1 On, Wh. Wh+1 Sp. An. Tn-1 by Assumption 3.1 By the definition (3.3) of weight bridge function 9h in Assumption 3.2 again, we have that
Nr 11 (An Sh))
(T)
Ey
f(Sh, An, On, Wh. Wh-1,
(OR(Ann Wi) - Σ 6h42(d' Wh+1)TA (A Or 1
Mh (S In-1)
Ex
Wh)
(A)
where step (a) just applies the definition of f. Now sum (TT over h E [H], we have that
H
(SI(S,,T))
((x)
h- (A(T) EEE
b9 (7 Wi)
(E.1)
(A)
(B)
where for simplicity we define An for h = ... H. as
(Sn, I
14- (Sh T 2
D = E,,
b7 (A,, Wx)
Σ
WA) (40
(An (Sh)
T (Ap Sh-1) a'EA
25

---

Published as a conference paper at ICLR 2023
In the sequel, deal with term (A) and (B) respectively. On the one hand, we have that
(F
(A)
(2)
O7 (E(A,,
(S To (o)
b7 (A1, Wi)
<4(A1
(A1(()) bi W S1, Wi ]]
Ex
E
09 (a, Wi)
mi(a(si)
Σ bi Wi)
where step (a) follows from the definition ni (Si, Po) in Assumption 3.2, step (b) follows from the fact that at h = 1, (S ro) = (S,, To), and step (c) follows from the assumption that
On the other hand, term (b) in [E. actually 0, which we show by proving that A. 0 for any h > 2. We denote by An A A and we consider A and A respectively, where
A1 W1 11 by Assumption
(n(S Tn-1),
b% Win
A h
E.
(A (,AnsS))) (Sh)
Ph- USh.
A 4/ E
Σ (a
T (An-1SSh-)
a'EA
In the sequel, we prove that A respectively.
A for the three cases of Ty in Example 2.1 2.2
and 2.3
We first focus on the simple case when policy æ is reactive. Since for reactive policies Ty, Ø, equivalently write μ4 (Sn, 11) as (s,) PR (P(())/PP Now for A,, we can rewrite as
Case 1: Reactive policy (Example 2.1
(AA) ( (R(S))R((ANSS)) (Ar)Sh)
A = Exp
(7, Wh))
(
Ph Jdsn
Σ Tifantih] [ Ph(wulonn an ddw,
(sn)
b% (an, wi)
Ph
OREA
I (wwnsws)dwww
(b)
PE (sn)ddan
by (an, wn.)
CLEA
Here step (a) expands the expectation by using integral against corresponding density functions, and step (b) follows from cancelling the same terms and the fact that W;, Ar, Sr, under Assumption 3.1 For AZ we can also rewrite it as
PT_ (S,
(A, 1
A
E5,
Σ bl(d',
Ph (S mb
1
a'EA
ph tot ton / 10-1(0n-11 1
( Pi(woolon 1, Oh-1)
P ( 1
(ah (02-1)
Σ
(ap, wn )dwn.
p n - anEA
26

---

Published as a conference paper at ICLR 2023
Here step (a) follows from expanding the expectation. It follows that (h-1(5h-1)dda So On On-1 18 1ddon-1 Σ aEA
A
1b)
Σ
Th ma-1(an-100h-1)
Oh EAA"
Ph S/ (s 1, I,,, Ph(wwlss)) by (ah, wh)
/ Ph( (ax, Wn )dw..
(
Σ
Ph. (sn)ds
64 E.EA
Here step (b) follows from cancelling the same terms and using the fact that Wh. I
S Ak-1, O by Assumption 3.1 and step (d) follows by marginalizing over
1h A, -11 Thus we have proved that A = A for reactive policies and consequentyy A = A A =
Case 2: Finite-history policy (Example 2.2). Now we have that 1 On) = OI-1JU The where the index max (0, h k: Similarly, we can first rewrite A}, as
PT (- (Sh. DA 1) (
A 11
E
67 (An, Win)
Th(anlsn (sn) J,
(8)
(h Ta (A-
an, Ta Th-1 dww
SxH
aNEA
(s Th-1)
b7 (a,, wh)
Ph (h) Th- 1 (ch 8/: Th-1)
Σ 4.EA SxHN.,
(s Tn dds Jw
Phwwals ) (ap, wn)-
Here step (a) follows from expanding the expectation, and step (b) follows from cancelling the same terms and using the fact that Wt An T I- under Assumption 3.1 For A}, we can also rewrite it
A Eyb
(S 1, D 2) mm 1 (An 1 Σ P 1
(a Wh))
ph (S Tn ) A 1Shh (ihh,,,T222) 22-2)
a'EA
(1)
Dh 1 - / On-11on-119n-))dnm
Σ 11
SxHA-2
(1 1hh an-1)dds
Ph Sh- an Oh- Th-2)
WW
PR (8h-1, 1, Th TT 100 Th-2)
by (an,
Ph. (s Th 2) (A1-115%-1
arEd
Σ
ai 01)ds (1)
df - / On On-r1on-119n-1)
E.E.A SXHA
Th- 10-1 / | Ph / Ph(walon) (2))))%66(0 6%( wh)
Σ
ah-1EA
(E.2)
(
Σ
PT Th- Th- / (h - (a,, wh).
Or SxHA-1
where the index / max h- h1 kj. In step (b), we have denoted by 7 = Th-2 {ar, 01 and it holds that Th-1 = T U (op-1- -. Here step (a) follows from expanding the expectation, step (b) follows from cancelling the same terms and using the fact that W;, 1 Sp-1, Ap-1, Sr
under Assumption 3.J] and step (c) follows by marginalizing Sn-1, A,, O, Thus we have proved that A A for finite-length history policies and consequently A A A =0.
27

---

Published as a conference paper at ICLR 2023
Case 3: Full-history policy (Example 2.3). For full history information The have that - U
{An, On} = Th. Following the same argument as in Case (Example 2.2 we can first show that
4 Σ
(s 7m-1)d /,
Ph(wwlsh)dag
(a,, wh)-
a.EA SxHa-1
Besides, for 22, by similar argument as in Case 2 except that don't need marginalize over A,, Oj in (E.2). we can show that
( Th 2)ds - - / On-1(on-11s
A Σ EA SxHa-2
Σ
Th-1 7h-2)
RM-1EA
Ph Ps
(uonlso 8h-1, an Oh- Tb-2) by (an, wh.)
= -E
(o Th- Idsnnda-1 /, (u ba.ddr. 6% (an, wh.)
EA SxHa-
Therefore, we show that A = 43 for full history policies and consequently An = =A - A =
Now we have shown that term (B) in E. is actually 0 for Example 2.1 Example 2.2 and Example
2.3 respectively, which allows us to conclude that
J(z) - E
Σ
[al
LaEAA
This finishes the proof of Theorem 3.3
F PROOF OF LEMMAS IN SECTION D
We first review and define several notations and quantities that are useful in the proof of the lemmas in Section Firstly, we define mapping f B x B - {A
3 + BR) as
bn+1) Zn. = En (An. Wv RA n (An 1n)
Σ a'EA
bati(a', Wh+1) m Anl I' n--1) Ans Zn
(EI)
Furthermore, for each step h E H). we define a joint space IT = A x W x x Hh-1 x W and
define mapping si IB x B [In IR]
5h (br, (An, WA, On, I Wh+1) = bp. (Ah, WT:) - (A
Σ
bn+i(d', (A (An Pn-1). (F2)
d'EA
When appropriate, we abbreviate J, = (A,, Wt, On, TA-1, Wh+1) E In in the sequel. Using definition ET and (F2), we further introduce mappings $b ", Px, B B + R as defined by 3.9
A J (b,, bb+1: = Eyp [eT bn+1) Zn) A(An, Zn) - >g 2
Pz,h (bn, bh+1:g) g) = T6 (bn, bu+1: Egg [E] (bu, bn )) (An, Zx) An, Zn)]
where we define that &T.h = T0 T Also, recall from 3..0 that the empirical version of T n. $ m. defined by AA no $n
A (bn, bnt1ig)= == E.y [sA (bn, b)+1)) (Tx) ((n, 7n) >g(An, Zn)?],
T (bn, bn+1:)) = = (br. b4t1:9) = -Ba [5x (bn, (bn. (x+t)(TT) -((An Zw)]
28

---

Published as a conference paper at ICLR 2023
Recall from 3.11 that given function bb+1 B, the minimax estimator by. (bb+1) is defined as by (b)+1) = min max 2,, bb+1:9)-
bEB
gea
Mcanwhile, define the following quantity for of theoretical analysis
6y (bb+1) = arg min max
$ x. (b, bigt.
(F.3)
DEB
geG
By the boundedness assumption B in Assumption 4.2 we have that 10. Ss completeness assumption on G Assumption 4.3 bn, b1+1 E B. Finally, for notational simplicity, we define for each G that,
< 2M,. By the
we also know that fg. (b), bn+1)
1 //2 2X E G for any
I E. 1,)
and we denote by Il its empirical version, i.c.,
| = E., (g(n,, 2x.
We remark that we have dropped the dependence of |/ on step since is clear from the context when used in the proofs and does not make any confusion.
F.1 PROOF OF LEMMA D.I
Proof of Lemina D.I By definition D.I of F(b), for any policy E IlH) and vector of functions B holds that
F(b - F(b)
(8)
(7 (a, W3) (a,
b7
LaEA
it(a)si) mi(a(Si)
(a, Wi) - bi (i)) (()(
Eege
LEAA
E
1
(a, Wi) b, (a). S₁, wi
(Ai(i))
Ex
(b7 (A1, W1) b, (A1, Wal)
(A)
where step (a) follows from Theorem 3.3 and and step (b) holds since Ai Wi S] by (3.3 at step 1, the weight bridge function of satisfies
Assumption 3.1 Notice that by definition equation
PT. (')
E (A)
(S, (T) (((A,()))
which further gives that
F(b") - F(b)
B Egg (A1, | To) (67 WT) (1A,, Wi)) B EEn, [ni (A1, A1, Wi, To] (A) Wi) b, (Ai, Wi))]
E, |6 (A1, (1) (A), 6, W1))].
where step (a)holds since Z1 1 W1 A1, S1, Ho by Assumption 3.1
Now we can further obtain that,
F(b*) F(b) E,
[o (A), Zi E [bT W1) (Ai, W Wi)[Ai, 21]
E,
qu (A1, Zz)
E53 RITI O1, Σ
(a W2) (A,
A Z1
E,o (b,(), Wi Zi] I
29

---

Published as a conference paper at ICLR 2023
where step (a) follows from the definition in (3.2) of value bridge function by in Assumption 3.2 Now to relate the difference between F(b") and F (b) with the RMSE loss Lj defined in (3.6). we rewrite the above equation the following,
F(b") F(b)
= Ezz op (A1, (1) E (ATA(A)
Σ
(3)
A1, Zi
- E
TA + Σ ( ro) 41, Z
+ E
[)) + Σ Wa)d A1, 2
}
-
(A1, Wi)
A1, Z1
oi (A1, Z1)
Σ
by W2) b2(a, W2) (1 (1(11011, A1. Z1
}
+ E
(ITa(A,101,, To)
Σ b2(a',
Po) b, Wi) A1, Z
(F.4)
We deal with the terms in the right-hand side of F.4 equals to
respectively. On the one hand, the first term
oi (A1, 1
Σ (ā W2) b2(a, ba)) (A,) A1. Z1
= >/B.g'
oi (A1, 71)
Σ
(a', (2) b2 (2) (1 Too
Ex
9i (A1, 21)
S1 A1, We Σ (b](', W2) - b2(a, (1
(
oi (A1, 21)
ST. A1 Σ
[b 12(a
(2)) W2)) TI (A, rm))
(1 lo)
(b)
Σ
(5 Wc) - b2(a, Wa)) n (A,10) ( Po)
(A)
where step (a) follows from the fact that Z, O₁, W2|1, AI, To according to Assumption 3.1 and step (b) follows from the definition (3.3) of weight bridge function of in Assumption 3.2 Now following the same argument as in showing A. = the proof Theorem 3.3
we can show that
Io)
E
Σ
65 (5 W2) - b2 (2) ( (A.10.,,
(A)
(5,, W2) - by (2 b2) Wa) & (A2, Zz)
E
(F.5)
On the other hand, the second term the R.H.S. of F.4 can be rewritten and bounded by
E, (A1, End
+
(4) To) (A1, WT) A1, 2
}
1/2
I SVCTE,
E,b RITI(A
Σ
by (.). - (,) A1. Zi
=Vo
VVTV.4T(bI... (bb,)b2))
(F.)
30

---

Published as a conference paper at ICLR 2023
where C" is defined C* == [[ Ex (A,, (A,. Zn)) the inequality follows from Cauchy-
Schwarz inequality, and the equality follows from the definition of L7 in (3.6). Combining (F.4).
F.5 with (F6). we can obtain that
F(b") ((b)
Z2) 65 (A2, W2) (2 wa))
S VCO V (T1, b2) +
% ty
(F.7)
Now applying the above argument the second term in the R.H.S. of (F.7) recursively, obtain that
F(b") F(b) S Σ 1== (
This finishes the proof of Lemma D.1
F.2 PROOF OF LEMMA D.2
Proof of Lemmal D.2 By the definition of the confidence region CR* (a) in (3122, we need to show for any policy π (H) and step h E [H), it holds that,
max T H. ( 6% (i
max 4b h (bn (b (6)+))) 6 (i S.
(F.8)
gEG
gEG
Notice that by Assumption 4.2 the function class G is symmetric and star-shaped, which indicates that
A (b 68+ (: T (6r (17 01:: = 0.
max
gEC
Therefore, in order to prove (.S suffices to show that
max gEC
T (b% 1 1:9) S.
(F.9
To relate the empirical expectation T (bg ( = t5 n. (b7, b -A11912 to its population
version, need localized uniform concentration inequalities. On the hand, to relate ||g and | 2,,. by Lemma I.1 (Theorem 14.1 of Wainwright (2019)), for some absolute constants e1, C2 > 0, it holds with probability at least - 0/2 that,
1 2 11913 +
M3 1og(2c1/5),
Vgg E G,
(F.10)
202n
where < = mā 2c1 exp(-c2naa / and us.. is the critical radius of function class C
defined in Assumption 4.2 On the other hand, to relate F (br, bat1ig) and o (b,, b
we invoke Lemma I.2 (Lemma
of (Foster and Syrgkanis 2019)). Specifically, for any given bn. bb+1 E B, E II..). and h E [H], Lemma I.2 we choose F = G, X' = A 2, ) In.
and loss function É(g( Ap. Zn). In. = Si (bn, bp+t1 (TT) ) - (AA, Zn.) where S defined (F.
T I, is defined in the beginning of Appendix [F] It holds that e is I-L.ipschitz continuous in the
first argument since for any g.g' E G, (An, Zn) E x Z, holds that
((g(An, 7n), Jn) - E(gg 7n), [n]] = |57 (b,, b (T.) lg(A 7x) g' Zk)
< 2Mss 1g( Ag. 7n) (An, Zx)l,
which indicates that = 2Mp. Now setting f = 0 in Lemma 1.2 we have that 8, in Lemma I.2
coincides with ag in Assumption 4.2 Then C2,02 > 0, it holds with probability at least 6/ (1())) that
conclude that for some absolute constants
T (bn, (: Pz.h (br, bat1:g)
= E. I Zn), 1n)] E, (C(g(An Zx), Iw)
Mg log | [B
18LM3 log (2c B [
- 1881119121
Vg E G, (F.11)
C2
C2n
31

---

Published as a conference paper at ICLR 2023
Applying union bound argument over bn, bi++1 B, E (TH), and [H), then have that (F.TT holds for any ba, h E B, g G, t E [T),), and h E [ with probability at least - 8/2. Now using these two concentration
where 5¹ min 2c [ [ H exp(-ognai,n/
inequalities (F.10) and (.III. we can further deduce that, for some absolute constants Ci C2 >
with probability at least 8.
max geG
T. (6% 6% 11
T (6%, ( - Aelا|i..
= max gEG
i Pn,h (b7, by :1 N1ll1 X 11
XMg log(2c1 /C)
max gE0
202n
Ma (0
18LM log BB
181111|l1
C2n
62
where Ç is given as < = min 2c1 exp(-o2na and ç given as Ç' = minf& 2c1 [ [I) H exp(-cama /MM3) for any policy E II(H) and step h. Then we can further bound the right-hand side the above inequality as
max A n.h (0% DT 11199)
9EG
X
M3 looloog22 B [ H/C)
I max DEC
T (b%, Dy 1i9)) + max NEC
1 18L
2
C2f
XMC log((21/ 18LM3 (og((e)) (()
202n
C2n
728L2
M3 (2c |B| (1)(H)))))5)
AM3 log [2, /S)
An
202
18LM3 (2c
B (I((A)HHSS
Here the last inequality holds from the fact that 1x,A(b7, bit)) = 0 since 67 and 6 are true bridge functions, and the fact that sup]talla {allglle - b11g115) < a² /4b for any b > 0. Now according to the choice of in Lemma D.2. using the fact that < Ç and L 2.2, we can conclude that, with probability at least -.
max A n.A. (6%, 1: gEG
728L MC log(22 (2c (P))
XM3 log(2c1/() 20nn
18LM3 log (2c, (C))
+
An
C27
0 (A+1 M3M3 log( H()))HH/S)
SE
n
This proves
F.9 and thus further indicates
F.8 Therefore, we finish the proof of Lemma D.2
F.3 PROOF OF LEMMA D.3
We first give the high-level idea for proving Lemma D.3 as following. order achieve the fast rate for the whole confidence region, we took series of novel proof steps.
We first introduce the following lemma, which claims that for any bb+1 E B, the 6* defined in (F3) satisfies that max -> x (b" (ba+1), b)t1: g) is well-bounded. The proof of lemma follows the same argument as in the proof of Lemma D.2 which we defer to Appendix F.4
Then given any bridge function in the confidence region, we identify key term (term (+) in (F.12) which is related to the RMSE of this bridge function. By carefully upper & lower bound this term,
32

---

Published as a conference paper at ICLR 2023
where Lemma F.1 is applied, eventually obtain quadratic inequality that the RMSE of this bridge function satisfies. By solving this inequality, we can derive an upper bound on the RMSE loss which is uniform over the bridge functions in the confidence region, which is exactly the fast rate of the whole confidence region.
Lemma F.1. For any function b B, policy n IIHH), and step E [M]. it holds with probability at least - 8/2 that
max Q
geG w. (6, (bn+1), bh+1ig) S 1/2 Mc.
where b" (b)+1) is defined in FF3 and & is defined in Lemma D.3
Proof of Lemma F.1
See Appendix
for a detailed proof.
With Lemma
F.1
are now ready give the proof of Lemma D.3
Proof of Lemma D.3
Let's consider that for any bn. bh+1 CR (E), we have that
Φ n. (br, bh+1ig)
max gEG 4 n (bn, bl+1i 9) D (6% (bn+1), bn+1gg) - 22119112..
max geG
+ Dn A (bh+1)) + \ll N1191|
We further write the above
max
1.,,, (b), bn+1: g) 2 SEG
max ge
2 Hn (bn, bb+1ig) - x (bn+1); bbt1i9) 21
min get
TT, (b,, (bn+1) bb+1: + Al19
O (b, bb+1ig) - n.. (b++1), bbtiig) g
max geG
(*)
max @ n. h (b) (bn+ 1), bn-1igh
(F.12)
9EG
Here step (a) follows from that G is symmetric, a (bn, hp-1i -g) = = - - (bn, hh+1: g). and that
sea { (b7 bx+1ig) Al191l... min gEG
n (b,, (bn+1)) but1: -g) + >11 11,
min
क n (b% (b1+4)) + ملاوام
.EG
T (b% (bn+ bn+1:g) \11ا|22,n
max
gEG
3t (ba bz41g)-
max
sEG
In the sequel, we upper and lower bound term (+) respectively.
Upper bound of term (+). By inequality (F.12) after rearranging terms, we can arrive that
A (6), (b,=1): bb + max $ (bn, bi+1ig)
max gEG
gEB
< max
T n
(b), (b)-1)) (bbb--)),b+igg)))
geG
+ max 1 (bn, b) gEG
max Φb (br (ba+1), gEG
+ max gEG
A (bn (bb+t))
On the one hand, by Lemma
F.1 we have that with probability at least 8/2.
max
A A. (67 (b)4)) b)4 S E 2/2 Mc,
(F.13)
geG
33

---

Published as a conference paper at ICLR 2023
and by the definition of by (b++1) in (3.11. holds simultaneously that
T n.h (bn (bn(b))), 15 S max & (bž, (bn- 1), bb+ S + 1/2 Mc.
max
(F.14)
geG
gEt
On the other hand, by the choice of CR" (C), holds that
max
F.A (b,. b)+1ig)
max
a n. (br bx+1i9) S
(F.15)
gEG
gEG
Consequently, by combining (..33)
and F.15). we conclude that with probability at least
1 - 8/2,
(x) 3 + 2c MG.
(F.16)
Lower bound of term (x). Forlower bound. we need two localized uniform concentration inequalities similar to 10 and (F.1T) the proof of Lemma D.2 On the one hand, by Lemma for some absolute constants 61, > 0, it holds with probability at least 1 8/4 that,
1 211911 2
MG 1og(4c1/()
11
Agg E G,
(F.17)
202n
where Ç = f 4c co. and ag.n is the critical radius of G defined in As-
sumption 4.2 On the other hand, following the same argument as in deriving (F.II) for any given
bn. 8/, + 1 E IB, II(H). and [H), in Lemma 1.2 we choose F = G, A Z.
and loss function
((g(An, I.) Sh (b,, (14)))())))(A) Zn) 5 (b2, bn+1) ( (A,, Zn);
where Si is defined in (F.1) and In E In is defined in the beginning of Appendix F It holds that & L-Lipschitz continuous its first argument with 2.M.. Now setting f 0 in Lemma [.2] we have that 5, in Lemma 1.2 coincides with agg, in Assumption 4.2 Then we have that for some that
absolute constants C1, > 0, it holds with probability at least 1 07 (
( ( (,n, bn+1ig) Tr 1 bn+15.9) - (Pa,n(bn g))13g)= - 2. bn+1;9))
= ICo((n 2n,, [N] - E,d (C(a(((( Z,), TW] Iw)
Mg log( 4c, 111
18L M3 log (4c) [B] (
S 1841111/y
Vg E G,
en
(F.18)
where = min 4c, [B] (T)))) H exp(p exp(-c2no8,,./MM (M)). Applying union bound argument over bn, 6b bb+1 E IB, E I1(H), and h E [H]]. we have that (F.18) holds for any bn 6h ba+1 IB,
g E G. v E IIHH), and [M] with probability at least 8/4. Finally, for simplicity, we denote that
M log 4c B (H)
M log(4c1/()
C,
(F.19)
C2n
202
Now ready prove the lower bound term (x). For simplicity, given fixed by, b E TB, we denote
0h = 2X
(T, bl+1) G,
where Eg is defined in F. and 9f E G due to Assumption 4.3 Now consider that
(+) max gEG
@ (bn, b)+1:g) क F (bj (bn+ 1. bn+lig) 2 g 1
A
T (bn, but13 &z (b7 (bn+ bn+ 97 9
11 2,n
34

---

Published as a conference paper at ICLR 2023
where the inequality follows from the fact that G is star-shaped and consequently 9 G. Then by applying concentration inequality (F.17) and (F.18), we have that
(*) 2 TT.h (bn, - 1i - x A (b, (111),)44419..... 18 119 18L
3
112 + !?? 2
|
133
M \l
18 |1 112
Cs Mc - 18L1
1/2
2 19 + o7
1 18
199 18L
A
2
EB3
1/2
Ms.
(F:20)
where the second inequality follows from that T7 (b* (bn+ 1), 1 S 6B inequality by (F.25) in the proof of Lemma F.T) and the fact that
1/2 Ms (we prove this
o 2x,1 (br, 14+1:9//22 = 4A B. (b + Zn) = N1l
Combining upper bound and lower bound of term (x). Now we are ready to combine the upper bound and lower bound of (+) to derive the bound on 2g (bn, bb+1). By combining upper bound
(F.16) and lower bound (F20). we have that with probability least 6, for any by bb+1 B, II(H), and h E [H].
11 18L 11 18
2
A 12 - CB
1/2
Ms S 35 + 26g 1/2 Mg.
(F.21)
2
This gives a quadratic inequality on 11, 112, i.e.,
AllgT
72hnn
11 ll2 188L2 +
2/ +
X
3 + 363
MG 0. 2
1/2
2
(A)
(B)
By solving this quadratic equation, we have that
1 ll S 1 A+ 1
A
VB X
V
4B
2X 21
Applying the definition of A and B, we conclude that, with probability at least 1 - 5,
1 5 Len +
72
18LL" +
12 +z 35 +
3 MG
1/2
1/2
X
<
72
Ltn
6v2
r 1,2
in + VX
V2 1/2 + 2/3 21/2 2/3 1/4 M2
CB
Therefore, we can bound the RMSE loss 2% (bh, bp+1) by
(bn, (bn, bn+1)= = 2A l2 < (144L + 12 1/2),n + 2V22, + 4V 1/2 + 4v 1/4 M 1/2
(F.22)
Plugging in the definition of 4n, l/ in F.19 E in Lemma D.3 and that T. = 2MR, we have that
(bn, bn41)
M3 log( 4c, [ H/S")
Ma 1og(4c//S) 2cgn
< (144L+ 1222LL)
+ 2V22
C2n
C((+1/A) M log [H)
+4V3.
+433
1/4 1/2
M
cB
S &CMMMMy
1/A) log( I I(H))HHC)
,, 1/4 2
for some constant Ō₁ 0 and Ç min min 4c₁ exp(-o2na Here in the second inequality have used the fact that < Ç- This finishes the proof of Lemma D.3
35

---

Published as a conference paper at ICLR 2023
F.4 PROOF OF LEMMA F.1
Proof of Lemma F.1 Following the proof of Lemma D.2 we first relate T (bn, bn+1i
Pr,1(bn, bb+1ig) g) Al and its population version Φ n.hh (bn, bn+1ig) via two localized uni-
form concentration inequalities. On the one hand, to relate l and I|gll.... by Lemmal I.1 (Theorem
14.1 of Wainwright (2019). for some absolute constants C1, 02 0, holds with probabiity least 1 - 8/4 that
1 2 2119113 Ma 1og(4ca/() Vg E G,
11 |1 S
(F.23)
202n
where Ç = min 4c1 exp(-canaa /M3) and ag.n is the critical radius of function class G defined in Assumption 4.2 On the other hand, to relate T (bp, b and 7T., ( (bn, ba+1: g). invoke Lemma 1.2 Lemmma 11 of (Foster and Syrgkanis) 2019)). Specifically, for any given bn, bi++1 E B, π E IT IT), and step ht in Lemma
1.2 we choose F G, X A x 2, y In. I (AA,, Zn) where f,, is defined in F.II and F We can see that l is L-Lipschitz continuous in the first argument since for any 9.9 E G. (A,, 2n)
and loss function (A,, Zn), IY) = si (b), b
In E In is defined in the beginning of Appendix
E A 2, holds that
((g(A An, Zn), Ib) - (An, 7b), [b)] = |5 (b,, bb (Tn)l (9( An. 7h) g (An Zh)l
I 2.Ms 1g( An. Zn) (A,,, Zn)l;
which indicates that I, = 2B Now setting / 0 in Lemma 1.2 we have that 6, in Lemma 1.2 coincides with ag in Assumption 4.2 Then we can conclude that for some absolute constants C1, 02 > 0. it holds with probability at least 5/( [ (T[ that, for all g E G,
o 7,, 9 Tr (br, ba+1:9)
= - (( Zn), An: Zn)l E. ((( Zn), An, Zm)]
M3. log (4c) [B] (BPI]())))) 18L Mg. log (4c) [ 2 (XH)HAH
C2n
C2n
(F.24)
Applying union bound argument over bn, bh+1 E B, π E II(H). and E [H]. we then have that (F.1I holds for any bb, ba+1 E B, g G, E [I()), and E [H]] with probability at least 1 8/4. Now using these two concentration
where Ç = min(d. 4c (H)) H exp(-c2ma8,..
inequalities (F23) and F.24. we can further deduce that, for some absolute constants c1 C2 > 0,
with probability at least 8/2.
max T.A (6%, 1b4+1),6--18)) 1i9 gEG
$ n. ( Allalle,, }
= max DEG
o (b7 (bn+1), b) Aleell + 1 XM log (4c1 log(4ci/C)
I max gEG
2c2n
M3 loog (4c, (
18L Ma. log 4ca B
2
181119||2
e2n
C2n
ME | (B)1(()))))))
< max nEB
Tr (bj, (ba+1), bb+119)) + max
2 1l11
18
9EG
con
XM3 (0((4)//))
18L M3 log (4g(4c1]0 (1))
202
c2n
728L2 MR log 4c 2
((S))
AMG log(4c1/9
1/2 Mg + 63
<
An
202
18L sMM
log B [
C2n
36

---

Published as a conference paper at ICLR 2023
where Ç is given Ç minfō, 4er exp(-ognai,, and 5 is given 5" (in 4c (1()) exp(-cana /. /M3)) for any policy 11(H) and step h E [M]. Here
the last inequality holds from the fact that
max 4 R. ( (b)+1)), b S S/ sEQ
1/2 Mg.
(F.25)
and that supiaalla {allg]12 bl[g|83 < /b/4b. Note that inequality (F255) holds according Assump-
tion 4.3 and 4.3 In fact, by Assumption 4.3 we can first obtain by quadratic optimization that for
max a 9EG n.h
(br, bl+1)
4A 2% (bn, bn+1).
for any functions ba, bb41 E B. Thus we can equivalently express by (bx+1) as
b% (b)++1) = arg min
bEB 41 (b, bn+1) = arg min L (b, bb+11)-
BEB
This further indicates the following bound on maxges n. (bg, (0n++),, 1 9) that
max n. (b% (bu+1),, b < max gEG
V Cn (b,, (bu+2), bx41) E (g(A, Za)² S CB
1/2 Mc.
9EG
by Cauchy-Sehee Schwarz inequality and Assumption 4.3 Now according to the choice of & in Lemma D.2 using the fact that 5 < 5 and L 2Mg,, max 3. n. (bb (bn+1) ), 1iig)
conclude that, with probability at least 1 - 6/2.
728L2 Mλ log 4e B (A))H/H) 9EG
XM 1og(441/S (S)
Xn
20mn
18T. Ma 4c B (T()))
log
1/2M
1/2 MG
C
C2n 50 (A (A+1/2) M M3
log(
(TH))
1/2 Ms
25+ 1/2 Mc.
+ C3
Therefore, we conclude the proof of Lemma
G PROOF OF THEOREM 4.4
Proof of Theorem 4.4 By the definition of F(b) and F(b) in (D.1) and the fact that J(T) F(b²)
according to Theorem 3.3 we first have that
((x)) (
= =(b=') - F(b*)
(F(("*) -((b")) + (F(b*)) - F(b))) + (F(b²)
F(b*))
(ii
(iii
We can bound term (i) and term (iii) via uniform concentration inequalities, which we present latter. For term (ii), via Lemma D.2 with probability at least 1 - 5, ba" E CR (ς) and b E (R)( which indicates that
(ii = F( F(b*) <
max F(b)
min F(b). BECR* (2)
(G.1)
BECR- (8)
From
G.
we can further bound term (ii) as
(ii) < max F(b) max min F(b)
bECR"* (E)
rell(M) bECRT(g)
< max
f(b) min
F(b)
bECR (8)
bECR (8)
F(b) F(b=*) + F((=*)
min f(b)
= max
bECR=* (E)
bECR"" (e)
F(b) F(b )
< max bECR** (E)
(G.2)
37

---

Published as a conference paper at ICLR 2023
Here the first inequality holds because (H))))(H))))) minbeCR=(e) F(b) = minbbecR(E)) F(b) by the definition of स from (3.14). The second inequality holds because by definition xt is the optimal policy in II())). The third inequality trivial. Now to further bound (G.2) by the RMSE loss defined in (3.6). consider
F(b) - -F(b"))
max bECR
(0)
2 2 max
F(bb) F(b)) +2 max BECR" (E)
F(b) F(b +2 F(b - F(b*))
bECR" (E)
(vi)
(iv)
where we can bound term (iv) and term (vi) via uniform concentration inequalities, which we present latter. For term (v), we invoke Lemma D.I and obtain that
2 max
FT V (bnsba41l 22C h-1
max V CT (bns bnt1)- BECR" (E)
BECR" (E) h=1
Now invoking Lemma D.3 with probabiiiyy at least 1 1-ő, max (E) v 1% (br,, bn+1) 1 is bounded by
V 2% (br, bn+ s M,MMM (A+ (A+ log( BECR" (E)
(TH))HH) (B + + 1/4 M/ (G.3)
max
π2
for each step h E [H]. where Ç min
In the sequel, we turn to deal with term (i), (ii). (iv), and (vi), respectively. To this end, it suffices apply uniform concentration inequalities bound F(b) and (bb) uniformly over E B@H, By Hoeffding inequality, we have that, with probability at least 1 - 5,
2M log (BB/5)
J( b) [(T, b)
VI E (TH),, vb E BO
(G.4)
Consequently, all (i), (iii), (iv), and (vi) are bounded by the right hand side of G.4 Finally, by combining G.33 and G.4 with probability at least 36, it holds that
((*))-((f S (i) + (iii) + (iv) + (vi) + (v)
< 2v 22CCm nm Σn
Eッーー h-1 CiMaMMN V
(A + 1/A) log( [B] [(H))//(
+Oie 1/4 1/M2
1=1
2M log( log([B// /8)
+ +4\
7
log (?)))H/)
I <VVC (A+1/A) 1/2 HM
CVVC Hc//AM M!?
n
for some gobblem-independeee constant C/ O. We finish the proof of Theorem 4.4 by taking
A =
H DETAILS FOR LINEAR FUNCTION APPROXIMATION
H.1 MAIN RESULT FOR LINEAR FUNCTION APPROXIMATION
In this subsection, we extend Theorem 4.4 to primal function class R. dual function class G, and policy class IT()) with linear structures. The linear structure assumption is commonly considered in the RL literature (Jin et al. 2021 Xie et al., 2021 Zanette et al. 2021 Duan et al.) 2021 Min et al. 2022a b Fei and Xu) 2022 Huang al. 2023), to mention few. And it can be viewed as an extension of linear bandits (Auer 2002; Dani et al. 2008: Li et al. 2010 Abbasi- Yadkori et al. 2011 1 He al. 2022) to multiple- nultiple-horizon setting. Note that the exact detail of the linear structure assumption might change across different works. our case, we consider linear function classes Bin. Gin and Tii. which is characterized by the following definition.
38

---

Published as a conference paper at ICLR 2023
Definition H.1 (Linear function approximation). Let Ø A W + =R be feature mapping for some integer N. We let the primal function class be = Bin where
b(. (b)(( (6(:,)))),. R 100 S Lb.
Bun =
sup WEW
Σ
b(a, w) S MB
aEA
Let 1/ = {wh A x O x H4-1 - R 11=1 be H feature mappings. We let the policy function class be II(H) = Min where Im [II m== and each Ii,, is defined as
exp ((vr (a, 0, B)) The (a(a,,, Ewee exp( ((in , o, 3))))
T = Th
B B
|1 I T
Finally, let where
2 + Rdd be another fnotherfeuturr feature mapping. We let the dual function class be G Gtin
Gin = {o (g()))))) = (1(:)),w)),u RR lelll Tgg
Assume without loss of generality that these feature mappings are normalized, ie.. 11 ll [M]la 1.
We note that Definition H.I is consistent with Assumption 4.2
One can see that [Bjin and Gio is uniformly bounded, Gjin is symmetric and star-shaped. And for other more detailed theoretical properties Bins Gin and Min. we refer the readers to Appendix H.2 for corresponding results.
Under linear funetion approximation, characterizes the suboptimality (2.2) of ā found by P30 when using Bin- Gia- and II as function classes.
extend Theorem 4.4 to the following corollary, which
Corollary H.2 (Suboptimality analysis: linear function approximation). With linear function ap- proximation (Definition H.T)), under Assumption 3.7 3.2 4.7 and 4.3 by setting the regularization parameter À and the confidence parameter & as and
& = C2M2] M3 dH loo (1 + Lo Hn/6)/n
then with probability least 1 6, it holds that
SubOpt(F) < CyyC=* Ha dH log (1 LoLz)H//) /n Cove Lg 1/4
Here C2 and C22 are cooblem-independenn universal constants.
Proof of Corollary H.2 See Appendix H.3 for detailed proof.
The guarantee Corollary H.2 is structurally similar to that of Theorem 4.4 except that we can explicitly compute the complexity of the linear function classes and policy class. When es P30 algorithm enjoys a O VC* H3d/n) suboptimality under the linear function approximation.
Compared to Theorem 4.4 Corollary H.2 does not explicitly assume Assumption 4.2 since it is
implicitly satisfied by Definition
H.2 AUXILIARY RESULTS FOR LINEAR FUNCTION APPROXIMATION
Here present results that bound the complexity of certain functions classes in the case of linear function approximation (Definition H.I.
Recall the definition of the bridge function class B@H where IB
Binn is defined
{D. b(:)) (b(s)),))))))))))))))))))))) TR. 1101|2 S Lt. sup
Ma w)) s MB }
Bin ==
Σ aEAA
weW
Denote by No (B) the e-covering number of B with respect to the too norm. That is, there exists a collection of functions (b. with N < ( such that for any E B, we can find some N. b' E ( satisfying
| 11 sup wEA.WEW
1b(a, w) V/a, w)l Se.
Se.
39

---

Published as a conference paper at ICLR 2023
Recall the policy function class II(H) M where Iin is defined
1 { T(aao,,))
e ((.(0.)))).)))
Ed'EA e(Vb(e 3 E RA, || s Lu unj.
Denote by No (Iln)) the e-covering number of Hlin with respect to the loo,1 norm, i.c.,
n' bo,,
sup Σ oEO,rEH
[T(a,, aalo,, r)
The upper bounds for these covering numbers are given by the following lemma.
Lemma H.3 (Lemma 6 in Zanette al. 2021). For any (0, 1), we have
2
log (B) - dlog
1
16L
Nog, (Mmn) & dlog
1+
The e-nets for the product function classes In the rest of Appendix H due to the proof, need to consider e-nets defined for the product function classes I@ and II(H) 11 Specifically, for BOH, we consider an e-net of B@H defined in the following way: for any b (bm)/1 E BOH there exists an b' (b in the c-net, such that
||ba by lla S.
By Lemma H. the cardinality of this c-net upper bounded by
log. No (IB @ S dH log (1 2Lm
Similarly, we consider an c-net defined for II(H) defined as the following: for any {TA 1 II(H), there exists n'
[m/ 1/ in the e-net such that
|| - T loo,1 S
Then by Lemma H.3 the cardinality this c-net is upper bounded by
log 2oo (II(H)) < dH log [1 16L
For the dual function class Gjin recall the definition of the critical radius ag,a in Assumption 4.2 The next lemma bound the critical radius of the linear dual function class G = Gtin-
Lemma H.4 (Lemma D.3 in Duan al. 2021). For the function class Gia defined in Definition H. its critical radius ag satisfies
2d
0g MG
where Mş supgeGm ||g]loo.
H.3 PROOF OF COROLLARY
We first introduce some lemmas needed for proving Corollary H.2
Their proof is deferred to
Appendix 1 and H.4.2
Lemma H.5 (Altemative of Lemma D.2 in the linear case). Let the function, policy and dual function class B B II(H) Iln and G Gin be defined as Definition H.1 Then under Assumption and by setting & such that
M2M3dH log (1 T. I. Hn/6 c <=C2-(A+) (2-)(A)))
n
for some problem-indepenuee independent universal constant C2 > 0, it holds with probability at least 1 that bat E CR (E) for any policy [TH.).
40

---

Published as a conference paper at ICLR 2023
Lemma H.6 (Alternative of Lemma D.3
in the linear case). Under Assumption 3.2 4.2 4.3 and
4.3 by setting the same & as in Lemma H.S CR (E), and step h,
with probability at least - 6, for any policy π I (H).
V F., (bn, bn+1) S C2 (1+ Ma vdH log (1 + L, Hn/8) /2/////111 / C2 Ms 12 for some
universal constant C2 > 0.
We are now ready to prove Corollary
H.2
Proof of Corollary H.2 We follow the proof of Theorem 4.4 and write
J(m')
J(
(J(T", b")) Jt "(a",b"') b²")) (Jaz", b")) j(T b²)) + (J(H. J(T, b²))
(iii)
(H.1)
We deal with term (ii) first. By Lemma HLS with probability least 1 8//2, b" CR (E) and ba E CR (E), which indicates that
(ii) = J(x", b²²)====="=" J( <
max J(TT,, b)
min bECR"(E)
J(H, b).
bECR (5)
Then following p.2 we can upper bound term (ii) by
(ii) S max BECR (5)
[(xt.b) - - b²))
< 2 max BECR (g)
[(Tt,b) - -J(T", b) +2
BECR (E) J(TT, b) -[(x,, "(x²,b²²))
max
(iv)
(v)
+ 2 [(x,,bb ) [TT,, [,Tr,b²')) b²))
(H.2)
(vi)
To bound term (v), we invoke Lemma D.I which holds regardless of the underlying function classes and obtain that
H
(v) = 2 max
Σ xh
(br, bn+1) S 2/
Σ
max
C% (bn, bn+1).
BECR" (E)
BECR (E)
Now by Lemma H.6 with probability at least max VCA (br, bb+1) 1) is bounded by
max bECR" (5)
CT bbb,)) bx41)
5 -
HH log (1 + LnLLHHn/ + Ö₂ M
1/1 vh E [M]. (H.3) "B
Now we deal with the term (i), (iii), (iv), and (vi), respectively. To this end, we apply uniform concentration inequalities to bound J(r, b) and JiT b) uniformly the e-net of and b as described in the proof of Lemma H.5 By Hoeffding's ' inequality, we have that, with probability at least 1 5, for all and b in their e-nets,
2M2 log(N....e...)/
J( - JTT. J(T.b)/ S
where Ne. and No. the covering numbers defined in Appendix H.2 Here the regularity assumption that |EaEA bi (a, w)) & Ma for all w E W and the detiniion of J(T, b) from (D.I). Consequently, for all π E IIH)) and b E B@N we have
2M2 log (og + 2M3c.
[(T, b) J(T, ()). <
(H.4)
41

---

Published as a conference paper at ICLR 2023
Next, all of (i), (iii), (iv), and (vi) are bounded by the R.H.S. of (H.4 Finally, by and (H.4) we have that
H.1
H..2
H.
( ((a)
- (i) + (ii) + (iv) + (vi)
< 22
A2 MBMe
dH log (1 + Hn/0))
+ C2
M 1/4
+4 2M log Nog
2M
n
Finally, by taking 1/n2, and plugging in the values of No, and Ne.= from Lemma H.3 get
J(x*) J(
dH log (1 + L1 Hn/o) C2 C2. (1+ Mc
< c* h-1
C2 M 1/1
n
HH log mgLan/6)
CyMBy
n
where C3 some problem-independden universal constant. We then simplify the expression and use the fact that
Mg sup (g(a, 2) sup Kv(a, w), S sup (aa(,, 2)122 ||wl22 S Lg
This gives the result Corollary H.2
H.4 PROOF OF LEMMAS IN APPENDIX
H.4.1 PROOF OF LEMMA H.5
Proof of Lemma H..5 First, for any (0, 1), consider arbitrary π = {mm and x' ( in The such that ||
for all h [H]. And consider arbitrary b (br 14 and b' = (8 Mr in Boof such that [|b 1/ I for all h [H]. Then by definition of a n. (bn, ())gg)) in (3.9) and B2
m/ boo,
7.6 (bn, bp 3. and that $ To and $A
F.A $0 n.
one can easily get that
M (bn, bn41gg) (bh, bh+1igh s [2e+ (e ( Mr < 4MR
n (bn, bn+1ig) Dr (6/ li) s < (E (E+ eM)) Mc s 4Mp
(H.5)
for all g E G.
Now, same as in the proof of Lemma D.2 we want to show: for any II(H),
max (b%, (ig)) S.
gEG
The rest of the proof would be very similar to that of Lemma D.2 with an additional covering argument. To begin with, again write (b% :
tn ho (b) b[t1g)) Al|g|l3,n
Same F.10). we have that with probability at least 1 - -6/2. M log(2c1/
1 11991
Illel.... |1 5
Vg E G,
(H.6)
2cz8
where Ç minf8, 2c exp(-c2nač,n MM and Ci, 02 are some universal constants.
Next, we upper bound & (bb, bp+1ig) - + t i (bn, b) for any л E II((), and E B
We first prove this for fixed e-net of Il(H) and R Specifically, choose an e-net of II(H)) such
that for any { == and म/ { in this e-net, it holds that || # llo,,1 S for all
42

---

Published as a conference paper at ICLR 2023
h. Also choose e-net of B such that for any b {b%, ) and b' =bb in the e-net, holds that ||6, - Kn al I с for all Denote the cardinality of these two c-net by Ne,, and N.. respectively. Then by the same argument behind (F.IT). get that, with probability at least 8/2. for any æ and b in their c-nets, and for any E G,
Tb (bp. bn+1ig)
a (bn, b
Ma log (2c) ebb
Ne H/C)
18LM log (2c. N H/()
$ $18L1g]22
(H.7)
C2
C2fl
where 5¹ mminf6,201N22 20, Ne, Ne, H exp(-cana /M2))
Now for any и E (H) and B by our construction of the c-nets, we can find x' and b' in the e-nets such that TA n 1 and libn 1/ I for all h. Then we have that with probability at least 1 - 6/2, for any π E ITH)) and b E B B and for any g E G,
P (br, bn+1i &x (br, bn+lig)
$ 1 n. (bn, bn+1ig) 9) T x' (b/, b + @arn th+1ig) 2 (b b/+1g
+ x' (b/- ::+1:
(x, bn+1ig)]
M3 log No. H/S)
18LM3 log (2c1
Ne. H/S)
S 88MMM - 18L|g/||/
C2n
C2n
(H.8)
where the first step is by the triangle inequality and the second steps is by
H..5 and HH.7
Now combine (..6) and H.8) with a union bound, we conclude that, with probability at least 1 - for any (1.
max Th gEG
n. (b,, bh+1: g)
T T. (b7, (4419) Allgll..n
= max gEC
XM log(2c1/()
S max gEG
1 (17, Dy b1+ig))
A|eall + 1911 +
202
M log No,,N.,ee. H/C)
18LM log (2c) (2,,N%,b Ne,
+ 18L/191/2
8.g
C2n
C2n
M3 log Ne.
S max gEG
max Pr (b7, (1+1)
11111 +18111
gEG
C2n
XM3 log(2c1/()
18LM log N2 H1/()
+ M.M
202n
c2n
7281.2 log( N2 c.b
N.. HI())
XM3 1og(2c1(5)
An
20zn
18LM3 (2g(22 No,
&.MMMGe,
(H.9)
Cnn
with <= m6n 20; exp(-c2nac /M)) and Ç' = min 68, Ne,N2,Ne,, H exp( e
for any policy π E II(H) and step h. Here the first inequality by (H.6) and (H.8), the second
inequality is trivial, and the last inequality holds from the fact that & (6,, b7 0413. ig) = 0 and the fact that sup {a]]g]] bl]g|[]) < a² ///4b.
43

---

Published as a conference paper at ICLR 2023
Now by Definition H.1
apply Lemma
H.3 with 10 $ Lb and
|S L and get that
log Ne.= S dH 1 16
1+ 2hb
log. Ne, - dH log
(H.10)
Now we pick e 1/n2, and together with HH.9 and (H.10). we get that
a. gEG n.h (b/ 9) sc (x+ 1/A) 1/2) M dH log (1 Hn/0) + n.
MR Mc
max
+ C
n²
where C' is some universal constant. Here we have plugged in the value of S. S and L = 2M2. Finally, by plugging in the value of agg, from Lemma H.4, we conclude that
max t 9EG n. (b,, by (19 Si (A+
MMMadH log (1 T Hn/6) + MR
n
where C is some problen-independent constant. Note that second term on the right hand side is smaller than the first term. Then the result follows from our choice of in Lemma H.5
H.4.2 PROOF OF LEMMA H.6
Proof of Lemma H.6 Consider any π E II()) and = -(b Mi E (R) Same as
F. we
have
A n. (bn, bn+1ig)
max gEG
a =, (br, bht1ig) T (b), bhtigg) 2211g|12.n
max gEG
max L n. (67 (bn+1), b1.g).)
geG
We again upper and lower bound term (+) respectively.
Upper bound of term (+). By the same argument as in the proof of Lemma F.I we have that: for any b E B g x E II(H), and h [H], it holds with probability at least 1 0/2 that
max F... (b, (b.+1), b 9) I 5 1/2 gEG
where bj, (bx+1) is defined in and is defined Lemma H.5
We then get
a max F. (br (ba+1), bb+1:)) < max gEG
- (b), (b.+1), b1: S 1/2 Mc.
(H.11)
SEG
where the first inequality follows from the definition of &y (b++1) in 3.11 Also note that, by the construction the confidence region CR*(E), we have
max 9E8
A F.A (bn, bx+rig) max t n.h (b (bx+1), b g) S &. .EG
(H.12)
Furthermore, we can write
A n.h (bj (bn+ 1), bb+1: + max A (br, bb+1:9) gEE
S max
gEC
< max A gEG
A (b) (bn. bn+1ig)
+ max L (bn, bb41ig) gEG
max
x. (br (ba+1) bbt1i geG
+ max 3. (6, (bh+))) b)+1ig).
geG
44

---

Published as a conference paper at ICLR 2023
Combining with (H.11 and (H.12) we get that, with probability least 1 -8/2.
3 2cp 1/2
Ms.
(H.13)
Lower bound of term (*). First of all, same F.177. holds with probability least 1 8/4 that,
1
My
1og(4c1/S)
|11ll n ||اا
Vig E G,
(H.14)
2
20gn
where < min 4e exp(-ezna } for some absolute constants с₁ and cg, and ag,, the eritical radius of G defined in Assumption
Second, we fix an e-net of [1(H) and an e-net of B as described in Appendix H.2 Denote by Ne. and Nr, their respective covering numbers. Then by the same argument behind (F.18) and union bound, we get that, with probability at least 1 - 8/4, for all { Mi b' {8, M in their e-nets, and for all g GG
{br. h= and
( ( bn415g) - $ 7. (K/, On- (n-1:))) - ( bb+1: (0n
D= n (b/2 b
M3 1og N. Ne, H/S))
18LM3 log (4c) Ne, H/())
$ <18L|1o1|a
(H.15)
C
o2n
where <' min(6, 4c Ne, exp(-ogna
We then use (H.5). and conclude that, with probability at least - 6/4, for all x E II(H), and b, b' B&H, and g G,
(
@ (n bn+1ig)
E Tr b(+1:9))
(2 (br, bn+1ig) - 2 (bh, bb+1:g))
Mă loggoog 12 H/S)
18LM3 log (4c, Na, Ne. H/(² + 8M Mgr.
< &187|1o1|2g
Cnn
c
(H.16)
In the sequel, for simplicity, we denote that
MG N.g H/())
M log(4c1/6
(H.17)
C2f
202n
where Ç and Ç are same as in (H.14) and (H.15).
Furthermore, given fixed bn bnt1 B, we denote
0%
2X 27 (bn, bb+1) E G,
(H.18)
where f is defined by (F.I and 9o E G follows from Assumption 4.3 We then have
(x) max 3EG
T n. (bn, bh+1ig) T. (b, (bx+1) 1)91
2X
T (bb, bh+15 (T..ggg/2))))) - L (6% (bn+1)) bb+ (/
11
12
2
where the inequality holds because g../2 /2 E G. Together with
H..14) and (H.16), we have
(x) 2 n. (bn, bn+ 15 l7.22
Dz (br (bn- bb /2) 18L,, 18Tan|199N12 18L,
X
1/3
8M Mae
1
112
2
2 AllgÃ|1 2 18Len 11 1|
1/2 Ms 18L1 8MaMse
3
2
1lo l2 - 187,,
|1
-
1/2 3/2 18L2
8MRMae
X
2
'n
(H.19)
45

---

Published as a conference paper at ICLR 2023
where the second inequality follows from the same reason in (.20
Finally, combine (H.19) and (H.13) and we get
1/2 1/2 M5 181, M. X
1 a8 of
S 35 + 2r M
B
This gives the following quadratic inequality w.r.t. 11
4 1881 + in + 35 + MMg 305/2 Mc S 0.
A 72L 1
By the fact that x.² Ax B implies S SAA V + 4B) A B, we have
72
4 { V>
>
1la -
18L
2 4.2 35 8Mp 363 3
We then plug in the values of 4n and 12 from (H.17). from Lemma H.5
Çand Ç" from below (H.14)
and (5.15), Ne.b and Ne. from Lemma H.3 og.a from Lemma H.4, the expression and we get
and set = 1/n2. Simplify
11 c C.c.c.(1) (1+ MgMe
dH log (1 L Hn/8)
M 1/2 1/4
CB
C.
n
where some problem-independen universal constant. C% (bn, bhn 12Ag l2. It follows that
By
H.18 and (3.6). we have
HH log (1 + LoL, Hn/0) + C2
V (bn, 11+1) 21|197 < C2-
M 1/4
cB
n
for some constant Öz. This finishes the proof.
I AUXILIARY LEMMAS
We introduce some useful lemmas for the uniform concentration over function classes. Before we present the lemmas, we first introduce several notations. For a function class F on probability space (X,, P), we denote by ||5'| the expectation of f(X)², that || Ex Ex~rlf(X)) Also, we denote by
1
(F, =
sup sEF.ILfllaS n
(X,)
(L.1)
the localized Rademacher complexity of JF with scale 8 > and size n E N. Here { and {X,)% are i.i.d. and independent. Each e, is uniformly distributed on [+1.-1} and each X; is distributed according to P. Finally, we denote by star(F) the star-shaped set induced by set F as
star (F) {aʃ E [0, 11, ʃ F).
(1.2)
Now are ready to present the lemmas for uniform concentration inequalities.
Lemma I.1 (Localized Uniform Concentration (Wainwright 2019)). Given a star-shaped and b-uniformly bounded function class F, let 8n be any positive solution of the inequality
R₂ (F;5) 8²
Then for any /. 2 8m. we have that
|1. |1 S 1111112 J1, VEEF
with probability at least exp(-c222 /1²). in addition no² 2 2 log log (1/5,)) /ez. then we have that
[l - |l - coôn. VfeF
with probability at least 1 ei exp(-chno0) /b2)
46

---

Published as a conference paper at ICLR 2023
Proof of Lemmal 1.1 See Theorem 14.1 of Wainwright (2019) for detailed proof.
Lemma 1.2 (Localized Uniform Concentration 2 (Foster and Syrgkanis 2019)). Consider a star-
shaped function class F : X H with sup ll I b, and pick any f E Also, consider loss function L
H IR which is L-Lipschitz its first argument with respect to the || -l2-norm. Now let 6% 2 4log (41 log (2c2n)) (c2n) be any solution to the inequality:
5²
Ra(star(F f"); S 6
Then for any 2 8n and some absolute constants c1, C2 > O, with probability - -a happ-22n11)/ /2n)2/12)) it holds that
(En 8)1 -., -BCC(()))))(((((()0))))))
I 18Lt (IIf 11, +t),
(1.3)
Jorany| J F. furthermr,e,, the loss function E is linear in J. i.e. E(I + = ((f(()) and f(af(x). = =al(f(x),2) then the lower bound on 8, is not required.
Proof of Lemma 1.2 See Lemma 11 of Foster and Syrgkanis 2019 for a detailed proof.
Remark L3. We remark that in the original Lemma 11 of Foster and Syrgkanist (2019), inequality
1.3) only holds for on and we extend it to any t 2 5n since according to Lemma 13.6 of Wainwright
2019) we know that R,,F; 5) is non-increasing function of on (0, +00), which indicates that
2 8n also solves the inequality.
47


Reviews:
[{"review_id": "vJV3P_utlef", "reviewer": "Reviewer_bBxr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studied offline policy evaluation and learning in POMDP setting with confounders. In this setting, the dataset is generated by a state depending policy, while the learner can only get access to observation. Based on some additional assumptions about negative control, bridge functions and concentrability coefficient and etc, the authors proposed a minimax approach to estimate policy value and a pessimism algorithm called P3O to identify near-optimal policy with bounded sub-optimality gap.", "summary_of_the_review": "This is a solid paper with some interesting results, while because similar techniques/frameworks have been well studied in settings different from this paper, the contribution and novelty is at the marginal level to me.", "strength_and_weaknesses": "### Strength\n\nThe assumptions in this paper is reasonable or frequently considered in previous works. The authors introduced the ideas of their methods very clearly and make this paper easy to follow although mathematically heavy. Although using pessimism is not a surprising idea for offline learning in POMDP, there are still some novelty and interesting parts in this paper.\n\n### Weakness\n\nThis paper is limited to the setting with latent states.\n\nThe learning framework (i.e. solving the bridge function for policy value estimation and using pessimism for policy learning so that sub-opt gap can be bounded via coverge w.r.t. optimal policies) is not something new and well-studied in previous literatures (although in different settings, the techniques and ideas are similar). So I'm feeling the novelty is kind of just above the marginal level.\n\nAlgorithm seems not computationally efficient.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "JjnHZ4ffxZy", "reviewer": "Reviewer_gsEb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The submission studies offline RL under POMDP settings. Besides the typical challenge of distribution shift, the submission also needs to resolve a confounding issue due to the latent states. The submission combines proximal causal inference and confidence region built by the minimax estimator to conduct a pessimistic value estimation. The proposed algorithm achieves a regret of order $\\tilde{O}(H\\sqrt{log(N_{fun})/n})$, where $n$ is the number of trajectories, $H$ is the length of each trajectory, and $N_{fun}$ is a complexity measure of the function class.", "summary_of_the_review": "Given the novelties of introducing proximal causal inference, the construction of the confidence region, and combining them to solve confounded data issue, I recommend a weak acceptance of the submission.", "strength_and_weaknesses": "Strengths\n- (a) The submission leverages developments in causal inference to remove confounding variables in POMDP settings.\n- (b) The construction of the confidence region combines the residual bridge functions seamlessly with the minimax estimator.\n- (c) The submission carefully compares notations and assumptions with those in the literature. \nRigorous analysis.\n\nWeaknesses\n- (d) The submission only applies the proximal causal inference to three policy types (C.1.1 to C.1.3). It would be better to have a systematic treatment for various confounding settings. \n- (e) Although the analysis of Theorem 4.4 is standard, the main context should briefly cover the main steps to achieve the claim result. The authors can justify the technical contribution in this part.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GZK9m8CgJp", "reviewer": "Reviewer_ttMi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposed the first provably efficient offline RL algorithm for POMDPs with a confounded dataset, which achieves $n^{-1/2}$ under partial coverage assumption. Specifically, the author solves three key difficulties: 1) To tacke the confounder issues, the paper assumes the existence of the proxy variables from causal inference and the bridge functions, but only the candidate is given, both are unobserved in the offline datasets. Then the author proposes the novel confidence regions 2) To tack the distributional shift, the author proposes pessimistic policy optimization 3) Finally, to tackle the large action space, the author allows the function approximation in their designed algorithm.", "summary_of_the_review": "This is a typical solid theoretical paper that is beyond the acceptance threshold. But it is unclear to me how realistic or practical this framework is.", "strength_and_weaknesses": "Strength: The results are solid and the analysis is sound. From my perspective, two main technical contributions are  1) The author formulates a causal inference-based setting to tackle the cofounder issues. 2) Based on this framework and given bridge function class, the author designed a confidence region estimator.\n\nWeakness: The paper is very abstract and considers the high-level framework. But such causal inference and the bridge function seems not very realistic to me. It would be if authors can give some real-world examples of those proxy variables or maybe test that on some causal datasets.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5eCpDGiERYf", "reviewer": "Reviewer_MuiH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers the offline RL problem in episodic-POMDPs. Specifically, data generation policy (or behavioral policy) is assumed to access the latent states while the target policy cannot, and the dataset does not contain trajectories of latent states. Basic idea is to combine the notion of bridge functions first proposed for the off-policy evaluation in POMDPs (e.g., Uehara et al., 2021), and the pessimism principle for offline RL which has gained a lot of attention recently. \n\nIn general, offline RL is intractable in POMDPs. To make the problem tractable, the paper assumes that additional observations (Z and W) are supplied such that short snapshots of trajectories satisfy a certain rank sufficiency assumption (e.g., weak-observability, Liu et al., 2022), under which the existence of bridge functions is known to be guaranteed. Under such conditions, the authors develop a simple offline RL algorithm and provide a polynomial upper bound under some additional assumptions. \n", "summary_of_the_review": "This paper initiates an important study on new problems, and could be a good addition to literature. ", "strength_and_weaknesses": "*Strength*\n\n- The paper tackles an important and challenging problem. Up to my best knowledge, this is the earliest kind of results that gives provable guarantees for offline RL in POMDPs. \n\n- The construction of confidence intervals around bridge functions, and analysis involving it, seems new. \n\n\n\n*Weakness*\n\n- Additional observations (Z and W) are somewhat non-standard and unjustified. Why couldn’t them be just a part of observations from the beginning?\n\n- This paper mostly uses the notions and assumptions defined in previous works. While related works are properly cited, they are hard to parse in general and would have been nicer if the paper has its own interpretation and intuition. For instance, the dependency of \\epsilon_B^{1/4} in the final result seems quite arbitrary. It’s not clear what it even means. \n\n- Related, coverage coefficient is defined in terms of $q_h^\\pi$. How this can be interpreted in tabular settings, or in fully observable setting (a.k.a. MDP)? Such explanations could be helpful for readers. \n\n- From a technical writing perspective, it is quite hard to follow. e.g., I cannot understand - how the construction of a confidence set is more challenging than standard problems? what is the intuition behind the construction and how do we expect it to give us polynomial bound? etc.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster