We study the offline contextual bandit problem, where we aim to acquire an optimal policy using observational data.
However, this data usually contains two deficiencies: (i) some variables that confound actions are not observed, and (ii) missing observations exist in the collected data.
Unobserved confounders lead to a confounding bias and missing observations cause bias and inefficiency problems.
To overcome these challenges and learn the optimal policy from the observed dataset, we present a new algorithm called Causal-Adjusted Pessimistic (CAP) policy learning, which forms the reward function as the solution of an integral equation system, builds a confidence set, and greedily takes action with pessimism.
With mild assumptions on the data, we develop an upper bound to the suboptimality of CAP for the offline contextual bandit problem.

§ INTRODUCTION

Contextual bandit is a mathematical framework that models the  decision-making problem under uncertainty.
In specific, in a contextual bandit, the agent chooses an action
based on an observation (also known as the context), and observes a random reward that depends on the observation and the action taken.
Such a framework

finds wide applications  in areas such as  healthcare ([Raghu et al., 2017, Prasad et al., 2017, Komorowski et al., 2018]), robotics ([Pinto and Gupta, 2016]), and computational advertising ([Bottou et al., 2013]).

Typical online policy learning algorithms require many interactions between the agent and the environment.
However, in various applications of offline contextual bandit, e.g., autonomous driving ([Shalev-Shwartz et al., 2016]) and healthcare ([Gottesman et al., 2019]), collecting online generated data could take too much cost and be unethical.
On the other hand, there are many historically recorded dataset for tasks where policy learning could be applied.
For example, driving data generated by human ([Sun et al., 2020]) and medical records ([Chakraborty and Murphy, 2014]).
Therefore, in this work, we study the offline policy learning problem, aiming to learn an optimal policy from previously collected dataset and require no interactions with the environment.

To learn the optimal policy from an offline dataset in real-world practice, three challenges must be addressed: confounding effects, partially missing observations, and partial data coverage.
Confounding effects arise because it is often impossible to conduct randomized controlled trials or collect all necessary covariates. [Pearl, 2009, Hernán and Robins, 2010].
For instance, medical data may intentionally omit a patient's health condition and medical history due to privacy concerns. [Brookhart et al., 2010].
In this example, the hidden information serves as the confounders. To address this, the power of side observations is used to adjust for unobserved confounders.

However, key information like side observations or context are often subject to partial missingness due to various reasons such as privacy concerns, attrition, or experimental errors. For example, lab test results that serve as side observations may be lost due to inability to conduct the tests or failure to store the results. Even worse, as the causes of missing observation problem vary, the missing pattern might be either at random or not at random [Rubin, 1976, Yang et al., 2019]. When the partial missingness is at random, the full data distribution is identifiable and multiple methods can provide reasonable estimates [Qu and Lipkovich, 2009, Seaman and White, 2014]. On the other hand, missingness not at random is a more challenging issue, since the missingness mechanism can depend on other factors or even the missing value itself. In this work, we aim to handle the challenge of side observations missing not at random.

The last main challenge is the partial coverage of the actions in the offline dataset. the observational dataset is collected beyond the control of the learner, and the action space can usually be too large for sufficient exploration. This means that conditions on full coverage of the action space by the data set in order to learn a good interventional policy usually fails to hold in real world practice [Fujimoto et al., 2019, Fu et al., 2020]. In this paper, we therefore explore the question:

Is it possible to design a provably efficient algorithm for offline learning confounded contextual
bandit problem with side observations and missing values under mild assumptions on the dataset?

Our answer to this question is affirmative.
Fortunately, there are methods that can help us accurately estimate the value of a policy from offline data affected by unobserved confounders if we have access to some side observations.
Two typical examples of side observations we explore in this work are instrumental variables (IV) ([Baiocchi et al., 2014, Wong, 2021, Chen et al., 2011]) and proxy variables (PV) ([Miao et al., 2018]).
Informally, IVs are variables that affect the reward only through the action, while PVs serve as negative control for the confounding effects.
Therefore, we investigate the use of side observations to mitigate the confounding bias in this paper.

For the partially missing observation challenge, we consider the case where both the context of the bandit and the side observations collected in the offline dataset are subject to missingness not at random.
Let us take the missingness of context $X$ for example. Let $R_X$ denote the binary missingness indicator for $X$. We assume that $X$ is totally missing if $R_X=0$.
The key idea we adopt to overcome the missingness issue is using the distributional information of the outcome to compensate for the missingness in the contexts or oberservations under certain completeness conditions.
Similar ideas can be found in [Yang et al., 2019, Ding and Geng, 2014], though they consider a different setting with missing elementary values in a vectorized random variable.
To address the challenges of confounding effects and non-random missing observations, we present a new approach that formulates the policy evaluation problem as solving an integral equation system (IES) with bridge functions. We demonstrate that the solution to the IES preserves the conditional average treatment effect (CATE), which enables us to further optimize the policy. In contrast to conventional causal methods that rely only on summary statistics such as the expectation of the outcome, our method leverages the full distributional information of the outcome.

Given the limitations of finite samples and incomplete coverage of the action set in our offline dataset, we incorporate the principle of pessimism into our approach for learning the optimal policy [Jin et al., 2021, Buckman et al., 2020, Xie et al., 2021].
In order to do pessimistic policy optimization, We must quantify the uncertainty in estimating the CATE from the IES.
To do so, we propose a Causal-Adjusted Pessimistic (CAP) policy optimization algorithm, which has two components: the uncertainty quantification step for estimating the CATE from the IES, and the policy optimization step based on the uncertainty quantification result.
In the CAP algorithm, the IES is solved by reducing the moment restriction equation system to a minimax problem via Fenchel duality.
After the uncertainty quantification step, the CAP algorithm takes greedy policy based on the confidence set constructed.

Our contribution can be summarized in three perspectives.
First, we developed a general framework to model the contextual bandit problem with confounded offline dataset and missing observations not at random.
Under this framework, we derive a novel integral equation system (IES) for identification.
We convert the IES to a minimax optimization problem, whose solution respects the CATE and the loss function of the minimax optimization problem paves the way for uncertainty quantification.
We emphasize that when the side observations are likely missing and the conditional moment restrictions form a system of equations rather than a single equation, it is non-trivial to select a proper way to do uncertainty quantification.
Finally, we propose a Causal-Adjusted Pessimistic (CAP) policy optimization algorithm and prove that our algorithms achieves fast statistical rate of sub-optimality for contextual bandit with side observations serving as instrumental variable and proxy variables.
To the best of our knowledge, this paper is the first one proposing a provably efficient algorithm for offline confounded contextual bandit with observations missing not at random.

§.§ Related Works

Offline reinforcement learning.
Literatures on offline reinforcement learning, especially those on pessimistic algorithms, are related to our work ([Antos et al., 2007, Munos and Szepesvári, 2008, Chen and Jiang, 2019, Liu et al., 2020, Zanette, 2021, Xie et al., 2021, Yin and Wang, 2021, Rashidinejad et al., 2021, Zhan et al., 2022, Yin et al., 2022, Yan et al., 2022]).
The major difficulty of offline reinforcement learning is the distribution shift between the policy generating the collected data and the class of target policies.
To overcome the distribution shift problem, we have to incorporate pessimism [Jin et al., 2021, Xie et al., 2021, Buckman et al., 2020, Uehara and Sun, 2021].

Causal inference.
A series of previous works in causal inference address adjusting the confounding bias via use of side observations like instrumental variables [Chen et al., 2011, Chen et al., 2021, Chen and Qiu, 2016, Bennett et al., 2019, Bennett et al., 2023, Wong, 2021, Athey and Wager, 2019] or proxy variables [Bennett and Kallus, 2021, Pearl, 2009, Miao et al., 2018, Lee and Bareinboim, 2021].
Among these works, [Pearl, 2009, Miao et al., 2018, Lee and Bareinboim, 2021] are most relevant to this paper since the our framework covers side observations proposed in them.
In comparison, these works studied the identification of certain side observations.
As the task in this paper is to learn the optimal policy, we make further effort to construct confidence sets.
Additionally, a large volume of works discuss the missing observation problem in causal inference ([Rubin, 2004, Qu and Lipkovich, 2009, Crowe et al., 2010, Mitra and Reiter, 2011, Seaman and White, 2014, Yang et al., 2019]).
[Yang et al., 2019] is particularly related to our work as it discusses identification for the case in which confounders are missing not at random.
The model in [Yang et al., 2019] assumes that there is chance to observe some data of confounders, while we study a model assuming confounders are completely missing and the side observations are missing not at random.

§.§ Preliminaries

In this paper, we let $\Delta(\cA)$ denote distributions over $\cA$.
We denote the inner product by  $\langle \cdot, \cdot \rangle$.
For any function $f$, we let $\cO(f)$ denote $Cf$ and $\tilde{\cO}(f)$ to denote $\cO(f\cdot\text{poly}(\log f))$.
We use calligraphic symbols $\sF$ and $\vH$ to represent function classes.
We use $\overset{\cE}{\lesssim}$ and $\overset{\cE}{\gtrsim}$ to represent the inequality that holds on some event $\cE$.

Critical radius. We define the localized empirical Rademacher complexity with respect to data set $\cD=\{x_i\}_{i=1}^n$ and function class $\sF:\cX\rightarrow [-c, c]$ as

\begin{align*}
\cR_\cD(\eta; \sF)=\EE\sbr{\sup_{f\in\sF, \nbr{f}_\cD\le \eta}\frac 1 n \sum_{i=1}^n\varepsilon_i f(x_i)}.
\end{align*}

The critical radius of $\sF$ on dataset $\cD$ is defined as any positive solution $\eta_\cD$ to $\cR_\cD(\eta;\sF)\le \eta^2/c$. Note that the critical radius $\eta_\cD$ is also a random quantity.

§.§ Roadmap

In <ref> we formalize the problem of policy learning for contextual bandit problem with confounding bias and missing observations.
In <ref> we discuss the challenges of policy learning problem shown in <ref> and show how these challenges motivate us to develop an algorithm framework named CAP policy learning to solve them.
In <ref> and <ref> we expand details about the step of constructing confidence set in the CAP algorithm described in <ref>.
The convergence results for the CAP algorithm are provided in <ref>.
In <ref> we give convergence analysis of the CAP algorithm in an extended policy class.
Lastly, we show that the CAP algorithm could be applied to the linear Dynamic Treatment Regime (DTRs) problem in <ref> and to the one-step linear Partially Observable Markov Decision Process (POMDP) in <ref>, both with the sub-optimality guaranteed to converge at a rate of $\tcO(T^{-1/2})$.

§ PROBLEM FORMULATION

In this section, we formalize the contextual bandit problem with confounding bias and missing observations.
We describe the casual structure of confounded contextual bandit in <ref>, the procedure of data collecting in <ref>, and the performance metric in <ref>.

§.§ Confounded Contextual Bandit

In this paper we study the offline policy learning in confounded contextual bandit (CCB).
Each trial can be represented by a tuple of random variables

$$(U, X, A, Y, O), $$

where $U\in\cU$ is the confounder, $X\in\cX$ is the context, $A\in\cA$ is the treatment, $Y\in\mathbb{R}$ is the reward, and $O\in\cO$ denotes the side observations.
We assume that variables for different trials are independent and identically distributed.
In offline learning, the data is collected through the observational process, and a newly selected policy is carried out in the interventional process.

The observational process and the interventional process of a CCB with side observations are depicted in Figure <ref>.

In each trial, there is an unmeasured confounder $U$ which has impacts on $O$, $A$, $X$, and $Y$.
As $U$ is not measured, the value of $U$ is not accessible in the data collected.
For example, sensitive information that is not allowed to reveal could be modeled by such unmeasured confounder.
Since $U$ affects all of $O$, $A$, $X$, and $Y$, the confounder $U$ serves as a common cause for the model.
Context $X$ is coupled with confounder $U$, and side observations $O$ can be caused by both confounder $U$ and context $X$.

A treatment $A$ is then selected following some policy $\pib(\cdot|U, X, O)$.
After the treatment is carried out, the environment generates a reward $Y$.
Suppose there are $T$ trials in total, then the full dataset $\tilde{\cD}$, which is distinguished from the dataset $\cD$ defined later, can be represented as

$$\tilde{\cD}=\{(u_t, x_t,a_t,y_t,o_t)\}_{t=1}^T.$$

Then by some missingness mechanism, records of $x_t$ and $o_t$ in some trials are possibly lost.
Additonally, recall that $u_t$ is also unmeasured and thus not included in the dataset.
The dataset collected for policy learning is defined as

$$\cD=\{(\check x_t, a_t, y_t, \check o_t)\}_{t=1}^T,$$

where $\check x_t$ either takes the value of $x_t$, if $x_t$ is not lost, or takes a special value of $\text{None}$, if $x_t$ is lost.
Similarly, $\check o_t$ either takes value of $r_t$ or $\text{None}$, depending on whether $o_t$ is lost.
More details about the observational process is presented in <ref>.

Given the dataset $\cD$ collected in the observational process, the goal of policy learning in CCB is to build a new policy $\pi$, which is called the interventional policy.
The interventional policy $\pi$ is executed in the interventional process.
In the interventional process, the unmeasured confounder $U$ still has impacts on both the context $X$ and the reward $Y$.
As the confounder $U$ is unmeasured, the agent could only observe the context $X$ and must decide an action $A$ to take only depending on the context $X$.
The rules for the agent to make decision in the interventional process is modeled by the interventional policy $\pi: \cX\rightarrow\Delta(\cA)$.
The agent aims to learn an interventional policy $\pi$ that maximizes the expected reward.
We discuss more details about the interventional process and performance metric in <ref>.

[hiddenstate] (U) $U$;
[missingstate] (X) [below=of U] $X$;
[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] $A$;
[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] $Y$;

[double] (U) edge (X);
[blue, normal] (U) edge (A);
[blue, normal] (X) edge (A);
[normal] (A) edge (Y);
[normal] (U) edge (Y);
[normal] (X) edge (Y);

[missingstate] (O) [above=of A] $O$;
[blue, dashed, normal] (O) edge (A);
[dashed, normal] (U) edge (O);
[dashed, normal] (X) edge (O);
[dashed, normal] (O) edge[bend left=-20] (Y);

DAG of the observational process in CCB

[hiddenstate] (U) $U$;
[missingstate] (X) [below=of U] $X$;
[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] $A$;
[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] $Y$;

[double] (U) edge (X);
[red, normal] (U) edge (A);
[red, normal] (X) edge (A);
[normal] (A) edge (Y);
[normal] (U) edge (Y);
[normal] (X) edge (Y);

[hiddenstate] (O) [above=of A] $O$;
[dashed, normal] (U) edge (O);
[dashed, normal] (X) edge (O);
[dashed, normal] (O) edge[bend left=-20] (Y);

DAG of the interventional process in CCB

A DAG illustrating the observational and the interventional process in CCB. Here,  the white nodes represent the observed variables, the light gray nodes represent the variables missing not at random and the dark nodes represent unmeasured variables. A dashed line means the causal effect might either exist or not.

§.§ Observational Process

The observational process describes how the offline dataset is collected, which is depicted in Figure <ref>.
In the $t$-th trial of the observational process, the environment selects $(u_t, x_t, o_t)$ as a realization of $(U, X, O)$ according to the prior $\pr(u, x, o)$.

The agent then conducts a treatment according to the observational policy $\pib: \cX\times \cO \times \cU\rightarrow \Delta(\cA)$. We remark that it is very common for the observational policy to be confounded by $U$, which can be understood as the agent's natural predilections, e.g., the playing agent in the observational procedure has a preference for certain treatments due to some hidden causes encoded by $U$ [Bareinboim et al., 2015].
After the treatment is conducted, a reward $Y$ depending on $(U, X, O, A)$ is received by the agent. The joint distribution $\pob$ in the observational process is thereby given by

\begin{align}\label{def:pob}
\pob(u, x, o, a, y) = \pr(u, x, o) \cdot  \pib(a\given u, x, o) \cdot \pr(y\given u, x, o, a).
\end{align}

Here we provide two typical examples of side observations in the observational process.
[Side observations as instrumental variable]
In a confounded contextual bandit with instrumental variable (CCB-IV) shown in Figure <ref>, $O$ corresponds to instrumental variable $Z$, which is assumed to be independent of confounder $U$ and outcome $Y$. The observational policy is given by $\pib(a\given u, x, z)$.

[Side observations as proxy variables]
In a confounded contextual bandit with proxy variables (CCB-PV) shown in Figure <ref>, $O$ corresponds to the negative controls $(Z, W)$. It is assumed that $W\indep A\given (U, X)$ holds for the outcome proxy $W$ and $Z\indep (Y, W)\given (A, X, U)$ holds for the treatment proxy $Z$. The observational policy is given by $\pib(a\given u, x, z)$.

Suppose there are $T$ trials in the observational process and the full dataset is denoted by $\tilde \cD = \{(u_t, x_t, a_t, y_t, o_t)\}_{t=1}^T$.
We emphasize that $\tilde\cD$ is not the dataset that will be used for policy learning due to the unmeasurement of the confounder $u_t$ and the missingness in both the contexts $x_t$ and the side observations $o_t$.

We formally discuss the missingness mechanism in the following paragraph.

Missingness Mechanism.

In addition to the unmeasurement of confounder $U$, we assume that side observations $O$ and context $X$ in our model are subject to missingness, which extends the missingness mechanism in [Yang et al., 2019, Yang et al., 2017]
where missingness was assumed to be not at random but independent of outcome $Y$.
We denote the observed dataset as $\cD = \{(\check x_t, a_t, y_t, \check o_t)\}_{t=1}^T$, where $\check x_t$ and $\check o_t$ denote the context and the side observations that we truly observe.

Let random variables $R_X$ and $R_O$ denote the missingness indicators for $X$ and $O$, respectively.
Let $r_{X, t}$ and $r_{O, t}$ denote realizations of $R_X$ and $R_O$ in the $t$-th trial.

When $r_{X,t}=1$, the record of $x_t$ is not missing and $r_{X,t}=0$ indicates that the record of $x_t$ is lost.
We introduce a special dummy value $\text{None}$ to represent a missing record.
So $\check x_t$ takes values in $\{x_t, \text{None}\}$ by the rule of

\begin{equation*}
\check x_t = \left\{
\begin{aligned}
& x_t & \quad \text{if } r_{X,t} = 1 \\
& \text{None} & \quad \text{if } r_{X,t} = 0
\end{aligned}
\right.
\end{equation*}

In contrast to assuming the observations to be missing randomly [Rubin, 2004, Qu and Lipkovich, 2009, Crowe et al., 2010, Mitra and Reiter, 2011, Seaman and White, 2014], in this paper we study a more general and challenging setting in which the missingness is not at random, i.e., $R_X$ and $R_O$ are not independent of the model $(U,X,A,Y,O)$.
As $R_X$ and $R_O$ could be dependent of $(U,X,A,Y,O)$, our results covers the case of malicious adversarial missing.
We revisit the previous two examples to illustrate the missingness.
[Example <ref> revisited]
In the CCB-IV, we allow $R_X$ to be caused by $(Z, X, A)$ and $R_Z$ to be caused by $(Z, X)$.

[Example <ref> revisited]
In the CCB-PV, we allow $R_X$ to be caused by $X$, $R_Z$ to be caused by $(Z, U, A, X)$, and $R_W$ to be caused by $(W, X, A)$.

Identifying the causal effect in the presence of missingness is nontrivial because the missingness interferes with the structure of the observational dataset.
For instance, when conditioning on $R_X=1$ in the CCB-IV, the instrumental variable $Z$ might no longer be independent of the confounder $U$, which leads to failure of conventional identification approaches.
More details on the difficulties brought by the missingness mechanism as well as the method we use to address the missingness issue will be provided case by case in <ref>.

§.§ Interventional Process

In the interventional process, an interventional policy is carried out after the model is learned from the offline dataset.
The interventional process is different from the observational process in the following three aspects:

(i) side observations $O$ appearing in the dataset are unmeasurable while context $X$ is fully measurable in the interventional process;

(ii) the agent follows an interventional policy $\pie:\cX\rightarrow \Delta(\cA)$ which is independent of $U$ and $O$ since they are unable to measure in the interventional process;

(iii) context $X$ follows a new marginal distribution $\tilde p(x)$ in the interventional process.

Aspect (i) indicates that only the context is revealed to the agent in the interventional process. Therefore, the interventional policy is context-dependent, as is stated in (ii).
We remark that (iii) can be understood through the idea of a marginal distribution shift in $X$ between the observational group and the interventional group, which is very common in real-world practice.

For example, when studying the effect of recommended ads' type ($A$) on the clicking rates ($Y$) with users' age ($X$) serving as the context, we might have an interventional group whose age distribution differs from the observational group.
Another example is the in-context learning paradigm,  where the task specification procedure can be viewed as "conditioning" the model on a certain context presented by the input texts/token [Brown et al., 2020, Radford et al., 2019].
Following (i)-(iii), the joint distribution $\pin{\pie}$ of random variables in the interventional process is given by

\begin{align}\label{def:pin}
\pin{\pie}(u, x, o, a, y) = \tpr(x) \pr(u, o\given x) \pie(a\given x) \pr(y\given u, x, o, a).
\end{align}

Diagrammatic explanations of the interventional process are given in Figure <ref>.
We see that the DAG of the interventional model is given by substituting the blue incoming edges to treatment $A$ encoded by $\pib$ in the observational model with the orange incoming edges encoded by $\pie$, while the remaining part of the DAG remains unchanged except for the marginal distribution of $X$.

Reward function and policy optimization.
In the interventional process, the average reward $v^\pie$ is defined as

\begin{align}
v^\pie = \EE_{\pin{\pie}}\sbr{Y},\label{def:v}
\end{align}

where $\EE_{\pin{\pie}}$ corresponds to the expectation taken with respect to $\pin{\pie}$ defined in (<ref>).
Our target is to find  $\piestar\in\Pie:\cX\rightarrow \Delta(\cX)$ that optimizes the average reward,

\begin{align*}
\piestar= \arg\max_{\pie\in\Pie} v^\pie.
\end{align*}

Correspondingly, we define the performance metric as the following sub-optimality,

\begin{align}
\text{SubOpt}(\pie) = v^\piestar - v^\pie.\label{def: SubOpt}
\end{align}

In summary, our goal is to design a learning algorithm that returns a policy $\hat \pi$ based on the offline dataset $\cD$ collected in the observational process. Here the dataset is subject to unmeasured confounder and missingness.

§ CAP ALGORITHM

In this section, we first investigate the main challenges of such an offline bandit problem, including the issue of confounding and missing data and also the spurious correlation that arises in the decomposition of the sub-optimality in <ref>.
We then put forward an algorithm framework named Causal-Adjusted Pessimistic (CAP) policy learning in the face of such challenges in <ref>.

§.§ Challenges in the Offline Setting

The offline learning problem in the CCB boils down to the following two questions:
(i) how to evaluate the average reward given an interventional policy; (ii) how to efficiently find an interventional policy that maximizes the average reward.
When trying to answer these two questions, we encounter two major challenges: (i) confounded and missing data; (ii) spurious correlation in the sub-optimality.
We briefly discuss where these challenges stem from and what technologies we use to overcome these challenges in this subsection.

Challenges in average reward evaluation: confounded and missing data.
The key to the problem of evaluating the average reward (<ref>) in the interventional process is to learn the conditional average treatment effect (CATE) defined as

\begin{align*}
\gstar(x, a)=\EEob\sbr{Y\given X=x, \doopt(A=a)},
\end{align*}

where $\EEob$ is an abbreviation for $\EE_{\pob}$.
Here, the do-calculus $\doopt(A=a)$ in the condition means that the expectation is taken with respect to the distribution obtained by deleting $\pib(a\given u, x, o)$ from the product decomposition of $\pob$ in (<ref>) and restricting $A=a$.

Learning the CATE is important since the average reward is related to the CATE by

\begin{align}\label{eq:v to CATE}
v^\pie = \EE_{\pin{\pie}}\sbr{\gstar(X, A)}.
\end{align}

In the presence of confounding bias [VanderWeele et al., 2008, Jager et al., 2008], learning the CATE needs tools borrowed from causal inference.
To control for the confounding bias, a typical way is to exploit side observations $O$ in the offline data [Lipsitch et al., 2010, Singh, 2020].
Instances of controlling the confounding bias using side observations are presented in Examples <ref> and <ref> where instrumental variable (IV) [Cragg and Donald, 1993, Arellano and Bover, 1995, Newey and Powell, 2003] or proxy variables (PV) [Tchetgen et al., 2020, Ying et al., 2021] are introduced for negative controls.

However, our problem is still challenging given the fact that the missingness bias is coupled with the confounding bias.
Note that identification with outcome-independent missingness is rather trivial in the unconfounded contextual bandit setting with tuple $(X, A, Y, R_X)$ where $R_X$ is caused by $(X, A)$.
The simplest way is to use the dataset without missingness, i.e., conditioning on $R_X=1$ and estimate $\EEob\sbr{Y\given X=x, A=a, R_X=1}$.
Such a method is valid since we have $R_X\indep Y\given (X, A)$ without confounders.
However, in the confounded contextual bandit setting, the causal effect is identified with the aid of side observations, and some model assumptions related to these side observations are broken when simply conditioning on $(R_X, R_O)=\ind$.
Take the CCB-IV case for instance. The IV independence assumption $Z\indep U\given X$ is broken by conditioning on $R_X=1$ since $R_X$ also depends on confounded action $A$.

As we will show in <ref>, the CATE learning problem is addressed by solving a novel integral equation system (IES), in which the integral equations are coupled together, and the CATE is obtained as the solution to the IES.

Challenges in policy optimization: spurious correlation.
We discuss the second question on how to efficiently optimize the interventional policy.
Let $g$ denote an estimation of the CATE and $\gstar$ denote the exact $\CATE$ thereafter.
Following (<ref>), we define the average reward function corresponding to $g$ and $\pie$ as

\begin{align}
v(g, \pie) = \EE_{\pin{\pie}}\sbr{g(X, A)}.\label{def:v approx}
\end{align}

It is okay if we simply take a greedy policy $\hat \pi$ that maximizes $v(g, \pie)$. However, such a greedy policy can sometimes be misleading.
A little calculation of the sub-optimality helps gain intuition.
We let $\tpr(x)=\ind(x=x_0)$ for brevity. By definition of the sub-optimality in (<ref>) and the fact that $\hat \pie$ is greedy with respect to $g$, we have

\begin{align}
\SubOpt(\hat \pi) \le \underbrace{\langle \gstar(x_0, \cdot)-g(x_0, \cdot), \piestar(\cdot\given x_0) \rangle}_{\text{(i)}} + \underbrace{\langle g(x_0,\cdot) - \gstar(x_0, \cdot), \hat\pie(\cdot\given x_0) \rangle}_{\text{(ii)}}. \label{eq:spurious subopt}
\end{align}

Note that $\piestar$ in term (i) is intrinsic to the bandit model and does not depend on $g$. In contrast, $\hat \pie$ in term (ii) is coupled with the estimated $g$, which yields the spurious correlation [Jin et al., 2021] and makes term (ii) hard to control.
Bounding term (ii) usually needs strong assumptions on the "uniform coverage" of the dataset $\cD$ as in the existing bandit and RL literature [Brandfonbrener et al., 2020, Tennenholtz et al., 2021, Laroche et al., 2019], which occasionally fails to hold in practice.

Instead, we adopt the technique of uncertainty quantification and pessimism to cope with the spurious correlation challenges. Similar techniques have been applied to other problems in the existing literature [Jin et al., 2021, Uehara and Sun, 2021, Zhan et al., 2022, Rashidinejad et al., 2021]. Our work successfully integrates such techniques with the confounded and missing data scenarios. Specifically, we first construct a confidence set $\CICATE$ for the estimated $g$ based on the offline data such that $\gstar\in\CICATE$ holds with high probability.
If the policy is optimized with respect to $g\in\CICATE$ that minimizes $v(g, \cdot)$, it follows that $v(g, \hat \pie)\le v(\gstar, \hat \pie)$, and the spurious correlation in term (ii) vanishes. Then, the estimated policy is given by

\begin{align*}
\piepessi = \arg\sup_{\pie\in\Pie} \inf_{g\in\CICATE} v(g, \pie).
\end{align*}

Moreover, it is also shown that pessimism can promote exploration [Auer et al., 2008, Azar et al., 2017] and help weaken the assumptions on the concentrability coefficient or the data coverage [Buckman et al., 2020].

§.§ Algorithm Outline

Now that we have answered the two questions raised in the last subsection by (i) identifying the CATE from an integral equation system (IES); (ii) optimizing the policy with a pessimistic estimator $g$ selected from some confidence set $\CICATE$.
What remains to clarify is how to construct the confidence set $\CICATE$ based on the IES.
As we will show in  <ref>, learning the CATE from the IES can be alternatively done by minimizing some empirical loss function $\cL_\cD(\vh)$ on the hypothesis class $\vH$, where $\vh$ is an estimated solution to the IES.
We are then inspired to construct the confidence set as a level set of $\vH$ with respect to metric $\cL_\cD(\cdot)$ and a threshold $e_\cD$.
The whole procedure is summarized in the following Causal-Adjusted Pessimistic (CAP) policy learning algorithm.

Causal-Adjusted Pessimistic (CAP) policy learning

dataset $\cD = \{\check x_t, a_t, y_t, \check o_t\}_{t=1}^T$ from the observational process, hypothesis space $\vH$, policy class $\Pie$, threshold $e_\cD$.
(i) Construct confidence set $\CICATE(e_\cD)$ as the level set of $\vH$ with respect to metric $\cL_\cD(\cdot)$ and threshold $e_\cD$.
(ii) $\piepessi=\arg\sup_{\pie\in\Pie}\inf_{g\in \CICATE(e_\cD)} v(g, \pie)$.

The IESs for identifying the CATE in both the CCB-IV and the CCB-PV settings are formulated in <ref>, and a united form is presented with use of a linear operator $\cT$.
Based on such a united form, the loss function $\cL_\cD(\cdot)$ and the confidence set $\CICATE$ is constructed using the technique of minimax estimator. More details about constructing $\CICATE$ are provided in <ref>.

§ CAUSAL IDENTIFICATION OF CATE

In this section, we show how to identify the CATE for CCB-IV and CCB-PV with missingness. Under certain completeness assumptions, the CATE is learnable through solving an integral equation system (IES). We also give explanations for the IES in the matrix form and compare the IES to standard identification equations without missingness to highlight how we address the missingness issue. A united form for the IES with a linear operator $\cT$ is provided in <ref>.

§.§ Identification in Confounded Contextual Bandit with Instrumental Variable

[hiddenstate] (U) $U$;
[missingstate] (X) [below=of U] $X$;
[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] $A$;
[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] $Y$;

[double] (U) edge (X);
[blue, normal] (U) edge (A);
[blue, normal] (X) edge (A);
[normal] (A) edge (Y);
[normal] (U) edge (Y);
[normal] (X) edge (Y);

[missingstate] (Z) [above=of A] $Z$;
[blue, normal] (Z) edge (A);
[normal] (X) edge (Z);

DAG of the observational process in CCB-IV

[hiddenstate] (U) $U$;
[missingstate] (X) [below=of U] $X$;
[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] $A$;
[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] $Y$;

[double] (U) edge (X);
[red, normal] (X) edge (A);
[normal] (A) edge (Y);
[normal] (U) edge (Y);
[normal] (X) edge (Y);

[hiddenstate] (Z) [above=of A] $Z$;
[normal] (X) edge (Z);

DAG of the interventional process in CCB-IV

A DAG illustrating the introduction of side observations ($O=Z$) in CCB-IV and the difference between the observational model and the interventional model in CCB-IV. Here,  the white nodes represent observed variables, the light grey nodes represent the variables with missingness not at random and the dark nodes represent unmeasured variables. A line with arrows at both ends means that the causal effect going in each way is allowed and therefore, the direction is not specified.

Instrumental variable (IV) regression is a method in causal statistics for estimating the confounded causal effect of treatment $A$ on outcome $Y$. Researchers in
economics employ IV to overcome issues of strategic interaction, e.g., supply cost shifters ($Z$) only influence sales ($Y$) via price ($A$), thereby identifying counterfactual demand even though prices are confounded by supply and demand market forces [Wright, 1928, Blundell et al., 2012].

Our model for confounded contextual bandit with instrumental variable (CCB-IV) is illustrated in Figure <ref>. In contrast to the standard IV model without context, we assume the IV to depend on the context $X$, for the reason that the IV usually appears as a recommendation of the treatment given by an advisor based on the current context.
The model assumptions for CCB-IV are summarized as follows.
[Model assumptions for observational process in CCB-IV]
We assume that the following assumptions hold for the observational process of the CCB-IV.

(i) (Structured reward). $Y=f(A, X)+\epsilon$ where $\epsilon \indep A\given (X, U)$;

(ii) (IV completeness). $\EEob[\sigma(X, A)\given Z=z, R_Z=1] = 0$ holds for all $z\in\cZ$ if and only if $\sigma(X, A)=0$ holds almost surely;

(iii) (IV independence). For the IV, we assume that $Z\indep (U, \epsilon)\given X$;

(iv) (Unconfounded and outcome-independent missingness).
We allow $R_X$ to be caused by $(Z, X, A)$ and $R_Z$ to be caused by $(Z, X)$.

The model assumption in (i) can be viewed as a generalization of the semi-parametric contextual bandits, whose outcome is given by $Y(a)=\langle \theta, X_a\rangle+g(X)+\epsilon$ when selecting treatment $a$ [Krishnamurthy et al., 2018].

The context $X=(X_{a_1}, \cdots, X_{a_{|\cA|}})$ is a tuple and each element corresponds to a feature for an action.
Moreover, $\epsilon$ can be viewed as a treatment-independent noise.
The IV completeness assumption in (ii) ensures that different IV ($Z$) generates enough variation in $(X, A)$ and the IV independence assumption in (iii) ensures that the IV is not confounded and is independent of the noise.
Combining (i) and (iii) we see that the IV is also outcome-independent, i.e., $Z\indep Y\given (A,U,X)$.
We remark that assumptions (i)-(iii) are standard in the IV literature [Baiocchi et al., 2014, Newey and Powell, 2003, Singh et al., 2019, Chen and Qiu, 2016, Chen et al., 2011], and an IV satisfying these assumptions is referred to as a valid IV.
Assumption (iv) shows that the missingness is unconfounded and outcome-independent, since $R_X$ and $R_Z$ are neither caused nor have a direct effect on $U$ and $Y$.
We remark that the missingness issue cannot be addressed trivially by only using the dataset subject to $(R_X, R_Z)=\ind$. Note that we have $(U, Z)\rightarrow A$ and $A\rightarrow R_X$ in Figure <ref>. Conditioning on $R_X=\ind$ will therefore create an edge between $Z$ and $U$ and break the IV independence assumption.
Fortunately, we have the following theorem to identify the CATE in the CCB-IV model with missingness.

Suppose that Assumption <ref> holds.
If there exist functions $h_1:\cY\times\cA\times\cZ\rightarrow \RR$ and $g:\cA\times\cX\rightarrow \RR$ satisfying,

\begin{align}
&\EEob\sbr{h_1(Y, A, Z) - Y\given Z=z, R_Z=1} = 0, \label{eq:IV bridge 1}\\
&\EEob\sbr{g(X, A) - h_1(Y, A, Z)\given A=a, X=x, Z=z, (R_Z, R_X)=\ind}=0 \label{eq:IV bridge 2},
\end{align}

it follows that $g(x, a)\overset{\text{a.s.}}{=}\gstar(x, a)$ where $\gstar(x, a)$ is the CATE.

See <ref> for a detailed proof.

An understanding of Theorem <ref> in the matrix form.
We give a matrix explanation of the method we use to overcome the confounding and missingness issue in Theorem <ref>.
We first study what happens if there is no missingness issue but just confounding effect.
Suppose $R_Z\equiv R_X\equiv 1$, a simple Combination of (<ref>) and (<ref>) gives the following identification equation,

\begin{align}
\EEob\sbr{Y\given Z=z}
% =\sum_{a\in\cA} g(a, X)P(X, a\given z, R_Z=1)
=\EEob\sbr{g^*(A, X)\given Z=z},\label{eq:IV standard id}
\end{align}

which corresponds to the standard identification in the IV model <cit.>. Since (<ref>) is learnable from the dataset without missingness, we can thus overcome the confounding issue and recover the CATE with the distributional information encoded in the side observation $Z$.

For the missingness issue, we remark that additionally conditioning on $R_Z=1$ on both sides of (<ref>) still recovers the exact CATE, i.e.,

\begin{align}\label{eq:iv matrix id with R_Z}
\EEob\sbr{Y\given Z=z, R_Z=1}
% =\sum_{a\in\cA} g(a, X)P(X, a\given z, R_Z=1)
=\EEob\sbr{g^*(A, X)\given Z=z, R_Z=1},
\end{align}

which is proved in <ref>.
Thus, we just need to focus on the missingness in $X$.
The difficulty is that we cannot simply evaluate the right-hand side of (<ref>) based on the observed data since $\pob(x, a\given z, R_Z=1)\neq \pob(x, a\given z, (R_X, R_Z)=\ind)$.

To address the problem of missingness in $X$, we have the following observation

\begin{align}
P(Y, a\given z, R_Z=1) = P(Y\given X, a, z, (R_Z, R_X)=\ind) \cdot  P(X, a\given z, R_Z=1), \label{eq:IV chain rule}
\end{align}

where $P(Y\given X)=\{\pob(y_i\given x_j)\}_{ij}$ denotes a matrix of size $|\cY|\times |\cX|$ whose element in row $i$ and column $j$ is $\pob(y_i\given x_j)$. In the following, we use capital $P$ to denote the matrix formed by matrixing the mass function.
We remark that (<ref>) is a direct result following the chain rule and the fact that $R_X$ is outcome-independent, i.e., $R_X\indep (Y, R_Z)\given (A, Z, X)$.
By assuming $\text{rank}(P(Y\given X, a, z, (R_X, R_Z)=\ind))=|\cX|$, the Moore-Penrose inverse exists and we have $P(X, a\given z, R_Z=1)=P(Y\given X, a, z, (R_Z, R_X)\allowbreak =\ind)^\dagger P(Y, a\given z, R_Z=1)$.
Now we can rewrite (<ref>) as

\begin{align}
\EEob\sbr{Y\given Z=z, R_Z=1} &=\sum_{a\in\cA}\underbrace{g(a, X)P(Y\given X, a, z, (R_X, R_Z)=\ind)^\dagger}_{\displaystyle{=: h_1(Y, a, z)}} P(Y, a\given z, R_Z=1),\label{eq:IV matrix id}
\end{align}

where $g(X, a)=\{g(x_i, a)\}_{i}$ and $P(Y, a\given z, R_Z=1)=\{p(y_i, a\given z, R_Z=1)\}_i$ are column vectors and $h_1(Y, a, z)=\{h_1(y_i, a, z)_i\}$ is a column vector defined by the under-brace in (<ref>).
The benefit of introducing $h_1$ is that $h_1$ can be directly learned from the observed dataset.
As a matter of fact, the definition of $h_1$ leads to (<ref>) and plugging $h_1$ into (<ref>) gives (<ref>).
For the bridge function $h_1$ to exist, we need $\text{rank}(P(Y\given X, a, z))=|\cX|$, which implies that the conditional distribution of $Y$ should be informative enough to recover the missing distribution of $X$.
So to overcome the missingness issue, we additionally exploit the distributional information of the outcome rather than merely using the average.
In the continuous setting, the equivalent condition for $h_1$ to exist can be expressed as follows.

A solution $h=(h_1, g)$ to the IES in Theorem <ref> exists if and only if there exists a solution $h_1$ to the following equation,

\begin{align}
\EEob\sbr{\gstar(A, X)-h_1(Y, A, Z)\given A=a, X=x, Z=z, R_Z=1}=0, \quad \forall (a, x, z)\in \cA\times\cX\times\cZ, \label{cond:iv bridge exist}
\end{align}

where $\gstar$ is the exact CATE. We leave the proof for <ref>.

Such a condition corresponds to the study of the linear inverse problem. It follows from Picard's theorem that certain completeness conditions are required <cit.>. See <ref> for more details.

Integral equation system.
In the following, we assume that the condition in Remark <ref> holds.
We remark that (<ref>) and (<ref>) form an integral equation system (IES), meaning that separately solving (<ref>) or (<ref>) alone would not  give the correct answer. The reason is that not all $h_1$ satisfying (<ref>) respect (<ref>).

To illustrate the point, let us consider a special tabular case. Suppose $\epsilon=0$ and $y=f(x, a)$ where $f$ is invertible with respect to $x$ for any fixed $a$. We thus have $g(x, a)=f(x,a)$ as the CATE and the independent condition $Y\indep Z\given (X, A)$. It follows from (<ref>) that

\begin{align*}
h_1(Y, a, z)\given_{Y=y}=g(a, X)P(Y\given X, a, (R_X, R_Z)=\ind)^{-1}\given_{Y=y} = g(a, f^{-1}(y, a))=y,
\end{align*}

is the unique solution for $h_1$.

However, solving (<ref>) alone might give the following solution,

\begin{align*}
h_1(y, a, z)=\EEob\sbr{Y\given Z=z, R_Z=1}.
\end{align*}

Apparently, such a solution does not respect the solution $h_1(y, a, z)=y$ given by (<ref>).
Therefore, we see that (<ref>) and (<ref>) are coupled together. What matters about the IES is that we have to construct the confidence set for $h_1$ and $g$ as a whole instead of using a nested structure. Details for quantifying the uncertainty that arises from the solving the IES empirically are defered to <ref>.

§.§ Identification for Confounded Contextual Bandit with Proximal Variable

The idea behind CCB-PV is to identify the causal effect using two auxiliary side observations $Z$ and $W$ as negative controls to check for spurious relationships in the existence of unobserved confounder [Singh, 2020, Miao et al., 2018].
The model is depicted in Figure <ref>.

We present the model assumptions as follows.

[hiddenstate] (U) $U$;
[missingstate] (X) [below=of U] $X$;
[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] $A$;
[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] $Y$;

[double] (U) edge (X);
[blue, normal] (U) edge (A);
[blue, normal] (X) edge (A);
[normal] (A) edge (Y);
[normal] (U) edge (Y);
[normal] (X) edge (Y);

[missingstate] (Z) [above=of A] $Z$;
[missingstate] (W) [above=of Y] $W$;
[normal] (A) edge (Z);
[dashed, double] (X) edge (Z);
[dashed, normal] (X) edge (W);
[double] (U) edge (Z);
[normal] (U) edge (W);
[normal] (W) edge (Y);

DAG of the observational process in CCB-PV

[hiddenstate] (U) $U$;
[missingstate] (X) [below=of U] $X$;
[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] $A$;
[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] $Y$;

[double] (U) edge (X);
[red, normal] (X) edge (A);
[normal] (A) edge (Y);
[normal] (U) edge (Y);
[normal] (X) edge (Y);

[hiddenstate] (Z) [above=of A] $Z$;
[hiddenstate] (W) [above=of Y] $W$;
[normal] (A) edge (Z);
[dashed, double] (X) edge (Z);
[dashed, normal] (X) edge (W);
[double] (U) edge (Z);
[normal] (U) edge (W);
[normal] (W) edge (Y);

DAG of the interventional process in CCB-PV

A DAG illustrating the introduction of side observations ($O=(Z, W)$) in CCB-PV and the difference between the observational model and the interventional model in CCB-PV. Here,  the white nodes represent observed variables, the light grey nodes represent the variables with missingness not at random and the dark nodes represent unmeasured variables. A dashed line between two variables means they can either have explicit causal effect or not. A line with arrows at both ends means that the causal effect going in each way is allowed and therefore, the direction is not specified.

[Model assumptions for the observational process in CCB-PV]
We assume that for the CCB-PV with outcome independent missingness, the following assumptions hold for the observational process,

(i) (PV completeness).

For any $a\in\cA, x\in\cX$,  $\EEob\sbr{\sigma(U)\given X=x, A=a, Z=z, R_Z=1}=0$ holds for any $z\in\cZ$ if and only if $\sigma(u)\overset{\text{a.s.}}{=} 0$ holds.

(ii) (PV independence). $W\indep A\given (U, X)$ and $Z\indep (Y, W)\given (A, X,U)$.

(iii) (Unconfounded and outcome-independent missingness). We assume that $R_W$ is caused by $(W, X, A)$, $R_X$ is caused by $X$, and $R_Z$ is caused by $(Z, U, A, X)$.

We remark that (i) and (ii) in Assumption <ref> are standard for identification in the PV setting [Miao et al., 2018, Miao et al., 2018, Nair and Jiang, 2021, Cui et al., 2020, Bennett and Kallus, 2021]. Here, (iii) is the unconfounded and outcome-independent missingness assumption, with an exception that $Z$ is allowed to be confounded.
We remark that the missingness issue cannot be addressed trivially by conditioning on $(R_Z, R_X, R_W)=\ind$, since the PV independence assumption $W\indep A\given (U, X)$ no longer holds when conditioning on $R_W=1$. Moreover, conditioning on $R_Z=1$ also yields a distribution shift in $U$, rendering a bias in identifying the CATE.
An example of POMDP with such a missingness mechanism is given in <ref>.
Now, we provide the identification formula for the CCB-PV as follows.

Suppose Assumption <ref> holds.
If there exist bridge functions $h_1:\cY\times\cA\times\cX\times\cZ\rightarrow\RR$, $h_2:\cA\times\cW\times\cX\rightarrow \RR$, $h_3:\cY\times\cA\times\cX\times\cA\rightarrow\RR$ and $g:\cX\times\cA\rightarrow \RR$ satisfying,

\begin{align}
&\EEob\sbr{h_1(Y, A, X, Z) - Y\given A=a, X=x, Z=z, (R_X, R_Z)=\ind} = 0,\label{eq:PV ID 1}\\
&\EEob\sbr{h_2(A, W, X) - h_1(Y, A, X, Z)\given (A, W, X, Z)=(a, w, x, z), (R_W, R_X, R_Z)=\ind}=0, \label{eq:PV ID 2}\\
&\EEob\sbr{h_3(Y, A, X, a')-h_2(a', W, X)\given A=a, W=w, X=x, (R_W, R_X)=\ind}=0 \label{eq:PV ID 3}, \\
&\EEob\sbr{g(X, a') - h_3(Y, A, X, a')\given X=x, R_X=1}=0, \label{eq:PV ID 4}
\end{align}

for any $(x, a, z, w, a')\in\cX\times\cA\times\cZ\times\cW\times\cA$,
it follows that $g(x, a)\overset{\text{a.s.}}{=}\gstar(x, a)$ where $\gstar(x, a)$ is the CATE.

See <ref> for a detailed proof.

The matrix explanation for the CCB-PV is similar to the CCB-IV case. See <ref> for more details. We give the following conditions on the existence of a solution to the above-mentioned IES.

A solution $h=(h_1, h_2, h_3, g)$ to the IES in Theorem <ref> exists if and only if the following three conditions are satisfied:

(i) There exists a solution $h_2$ to $\EEob\sbr{h_2(A, W, X)-Y\given A=a, X=x, U=u}=0$;

(ii) For any solution $h_2$ in (i), there exists a solution $h_1$ to (<ref>) and a solution $h_3$ to (<ref>).

The proof is given in <ref>.

Conditions (i)-(ii) also require certain property of completeness, as is discussed in the CCB-IV case. See <ref> for more details.
Note that (i) is a standard condition in proximal causal learning [Miao et al., 2018, Miao et al., 2018, Cui et al., 2020]. In a discrete setting, condition (i) means $\text{rank}(P(W\given U, x, a))=|U|$, showing that $W$ should couple enough information from the unmeasured confounder.
For $h_1$ and $h_3$ to exist, we just need $\text{rank}(P(Y\given W, a, x, z))=|\cW|$ and $\text{rank}(P(Y\given W, a, x))=|\cW|$, implying that $Y$ couples sufficient information of the missing variable $W$.
Analogue to the CCB-IV case, we remark that equations in the IES for CCB-PV are coupled and should be solved at the same time.

Pseudo random variable $A'$.
Here in the CCB-PV setting, we encounter an issue concerning $a'$ that appears in (<ref>) and (<ref>). Note that (<ref>) and (<ref>) should hold point-wise with respect to $a'$. However, if we treat each $a'\in\cA$ separately, we need to solve $\abr{\cA}$ equations, and the problem becomes intractable as $|\cA|$ grows larger, or we have a continuous treatment space. To overcome such a difficulty, we propose to treat $a'$ as a realization of a pseudo random variable $A'$, which is independent of the CCB-PV model and uniformly distributed across the action space.

Therefore, the joint distribution $\mu$ including $A'$ is given by

\begin{align*}
\mu(y, a, w, x, z, u, r_W, r_X, r_Z, a')=\pob(y, a, w, x, z, u, r_W, r_X, r_Z) u(a').
\end{align*}

Thereby, (<ref>) and (<ref>) can be written as,

\begin{align}
&\EEob\sbr{h_3(Y, A, X,  A')-h_2(A', W, X)\given A=a, W=w, X=x, A'=a', (R_W, R_X)=\ind}=0 \label{eq:PV ID 5}, \\
&\EEob\sbr{h_4(X, A') - h_3(Y, A, X, A')\given X=x, A'=a', R_X=1}=0. \label{eq:PV ID 6}
\end{align}

Here, by letting $A'\sim u(a)$, we try to learn an estimator that yields small error in each $a'$. Moreover, the dataset $\cD$ can be easily adjusted by adding an element $a_t'$ which is uniformly selected from $\cA$ and added to each sample, i.e., $\cD=\{\check x_t, a_t, y_t, \check w_t, \check z_t, a'_t\}_{t=1}^T$. By treating $A'$ as a pseudo random variable and $a'$ as its realization, we transform (<ref>) and (<ref>) into conditional moment equations, which facilitates our analysis of the IES in the sequel.

§.§ United Form for the IES

We summarize the IES discussed in both the CCB-IV and CCB-PV cases into the following united form

\begin{align}\label{eq:united form}
\EE_{\mu_k}[\alpha_k(\vh(\vX), \vY_k)\given \vZ_k]=0, \quad \forall k\in\cbr{1, \cdots, K},
\end{align}

$K$ denotes the total number of equations in the IES,

$\vh$ represents the vector of bridge functions to learn, i.e., $ \vh(\vX)= (h_1(\vX_1),\cdots, h_{K-1}(\vX_{K-1}), g(\vX_K))$ where $X_k$ is the random variable vector that $h_k$ depends on and $X$ is a union of $\{X_k\}_{k=1}^K$,

$\alpha_k$ is the linear function that is taken expectation with in the $k$-th equation of the IES, which depends on $h(X)$ and random variable vector $Y_k$,

$\vZ_k$ is the random variable vector that is conditioned on in the $k$-th equation of the IES,

$\mu_k$ denotes the joint distribution for $(\vX, \vY_k, \vZ_k)$ and $\EE_{\mu_k}$ is the expectation taken with respect to $\mu_k$,

We give an example to illustrate the united form in (<ref>).
Following the IES of CCB-PV in Theorem <ref>, we have $K=4$, $X=\bigcup_{k=1}^K \vX_k = \{Y, A, X, Z, W, A'\}$, $Y_1=Y$, $Z_1=\{A, X, Z\}$, $\mu_1(x, a, y, z)=\pob(x, a, y, z\given (R_X, R_Z)=\ind)$, and $\alpha_1(\vh(\vX), \vY_1)=h_1(Y, A, X, Z)-Y$.  Note that the joint distribution $\mu_k$ for the variables in each equation can be different. For example, the joint distribution for (<ref>) is conditioned on $(R_X, R_Z)=\ind$ while the joint distribution for (<ref>) is conditioned on $(R_W, R_X, R_Z)=\ind$.
Moreover, let $\cD_k$ denote the subset data of $\cD$ corresponding to the missingness condition in the $k$-th equation of the IES, e.g., in the CCB-PV case we have $\cD_1=\{(\check x_t, a_t, y_t, \check w_t, \check z_t, a'_t): (r_{X, t}, r_{Z, t})=\ind\}$, which is a subset of $\cD=\{(\check x_t, a_t, y_t, \check w_t, \check z_t, a'_t)\}_{t=1}^T$ and $\cD_1\sim\mu_1$.
Let $\cF(\vZ_k)$ denotes the functional space on $\vZ_k$.
Since $\alpha_k$ is linear, we can define a linear operator $\cT_k: \vH\rightarrow \cF(\vZ_k)$ for the united form of the IES in (<ref>) as

\begin{align}
\cT_k \vh (\cdot) :=\EE_{\mu_k}\sbr{\alpha_k(\vh(X), \vY_k)\given \vZ_k=\cdot}. \label{def:cT}
\end{align}

By letting $\vT\vh(z)=(\cT_1 h (z_1), \cdots, \cT_K h(z_K))$, the IES in (<ref>) can be alternatively expressed as

\begin{align}
\vT\vh(z) = 0.\label{eq:operator=0}
\end{align}

Note that the IES (<ref>) comprises a series of conditional moment equations, which is hard to solve with offline data. In the next section, we propose to transform the conditional moment equations into unconditional moment estimators.

§ ESTIMATION

In this section, we use the method of minimax estimation to transform the conditional moment restrictions in the IES into an unconditional moment minimax estimator with respect to $\cL_\cD(\cdot)$.
We then build the confidence set for the CATE as the level set in $\vH$ under metric $\cL_\cD(\cdot)$ and threshold $e_\cD$. Based on the confidence set, we integrate pessimism in policy optimization.

RMSE and unconditional moment criteria.
We let $\vH=\cH_1\times\cdots\times\cH_{K-1}\times\cG$ be the hypothesis space for $\vh$.
Following the idea of projected residual mean squared error (RMSE) minimization [Dikkala et al., 2020], our estimation target is good generalization performance subject to the following RMSE,

\begin{align}\label{def:RMSE}
\nbr{\vT\vh}^2_{\mu, 2}:= \sum_{k=1}^K \EE_{\mu_k}\sbr{\cT_k \vh(\vZ_k)}^2 = \sum_{k=1}^K \EE_{\mu_k}\sbr{\rbr{\EE_{\mu_k}\sbr{\alpha_k(\vh(X), \vY_k)\given \vZ_k}}^2},
\end{align}

where $\vT\vh=(\cT_1\vh, \cdots, \cT_K\vh)$ and $\mu=(\mu_1, \cdots, \mu_K)$. Note that solving the conditional moment equations (<ref>) corresponds to finding the $\vh\in\vH$ that minimizes the RMSE.
However, learning the causal relationship with conditional moment restrictions is a challenging task. It has been investigated in the existing literature how to transform conditional moment conditions into unconditional moment conditions, e.g., methods of importance weighting using conditional density ratio [Kato et al., 2021] or using linear sieve estimator [Ai and Chen, 2003] where the estimator has a rate of $n^{-1/4}$.
Inspired by the method of minimax estimation [Dikkala et al., 2020, Duan et al., 2021, Uehara et al., 2021] with fast rate of $n^{-1/2}$, we propose to approximate (<ref>) with an unconditional minimax estimator.
Specifically, we introduce a test function $\theta_k:\vZ_k\rightarrow \RR$ for each linear operator $T_k$. The function class for $\theta_k$ is $\Theta_k$, which we refer to as the dual function class.
The unconditional moment loss function that is used to replace the RMSE in (<ref>) is then given by

\begin{align}\label{def:L}
\cL(\vh) = \sum_{k=1}^K \cL_k(\vh), \text{ where } \cL_k(\vh)=\sup_{\theta_k\in\Theta_k}\EE_{\mu_k}\sbr{\alpha_k(\vh(X), \vY_k) \theta_k(\vZ_k)}-\frac 1 2 \norm{\theta_k}_{\mu_k, 2}^2.
\end{align}

By assuming the test function class $\Theta_k$ to be star-shaped, we always have $\cL_k(\vh)\ge 0$ (otherwise by letting $\theta_k=0$ there is a conflict with the fact that $\cL_k(\vh)$ takes the supremum over $\Theta_k$).
Note that as long as $\cT_k\vh\in\Theta_k$, the loss function $\cL(\cdot)$ is equivalent to the RMSE $\nbr{\cT(\cdot)}^2_{\mu, 2}$, which can be verified by the property of Fenchel duality (see <ref> for a detailed proof). Therefore, if we have $\cT_k\vh\in\Theta_k$, we see that any solution to (<ref>) is a minimizer to the unconditional moment loss function, i.e., $\vhstar=\arg\inf_{\vh} \cL(\vh)$.
In line with (<ref>),
we define the empirical loss function on the dataset $\cD$ as follows,

\begin{align*}
\cL_\cD(\vh) = \sum_{k=1}^K \cL_{k, \cD}(\vh), \text{ where } \cL_{k,\cD}(\vh)=\sup_{\theta_k\in\Theta_k}\EE_{\cD_k}\sbr{\alpha_k(\vh(X), \vY_k) \theta_k(\vZ_k)}-\frac 1 2 \norm{\theta_k}_{\cD_k, 2}^2,
\end{align*}

where $\cD_k$ is a subset of $\cD$ and we have $\cD_k\sim \mu_k$, as is discussed in <ref>.
We also have $\cL_{k, \cD}(\vh)\ge 0$ following the same argument that $\cL_{k, \cD}$ takes the supremum over the dual function class.
Now we are ready to build the confidence set $\CIH$ as the level set with respect to the metric $\cL_\cD(\cdot)$ and threshold $e_\cD$ as follows,

\begin{align}\label{def:CI}
\CIH(e_\cD) = \cbr{\vh\in\vH:  \vcL_{\cD}(\vh) \le  \inf_{\vh\in\vH}\vcL_{\cD}(\vh) + e_\cD}.
\end{align}

Correspondingly, the confidence set for the CATE is given by

\begin{align*}
\CICATE(e_\cD) = \cbr{g\in\cG: \exists\vh\in\CIH(e_\cD), \text{ s.t., } g=\vh^{(K)}},
\end{align*}

where $\vh^{(K)}$ is the last element of $\vh$.
Therefore, we have $g=h^{(K)}$ by noting that the last element of $\vh$ is the estimated CATE following both Theorems <ref> and <ref>.
We remark that building the confidence set is a way to address the aleatoric uncertainty stemming from the data generating process, as will be shown in Theorem <ref> that $\CIH(e_\cD)$ can capture an estimator $\vhHstar$ with small realizability error. On the other hand, we can eliminate the spurious correlation in (<ref>) with pessimism on such a confidence set, i.e., greedily selecting the policy that optimizes the pessimistic average reward function with $g\in\CICATE(e_\cD)$,

\begin{align*}
\piepessi = \arg\sup_{\pie\in\Pie} \inf_{g\in\CICATE(e_\cD)} v(g, \pie),
\end{align*}

where $v$ is the average reward function defined in (<ref>).
Here, we denote by $\gpessi{\pie}=\arg\inf_{g\in\CICATE(e_\cD)}v(g, \pie)$ the estimated pessimistic CATE under the interventional policy $\pie$.
By plugging in the definition of $\cL_\cD(\cdot)$ and $\CICATE(\cdot)$ in  Algorithm <ref>, we obtain the complete Causal-Adjusted Pessimistic (CAP) policy learning algorithm.

§ THEORETICAL RESULTS

Let $\vhstar$ denote the exact solution to (<ref>).
We allow the model to be misspecified, i.e., the exact solution might not be fully captured by the hypothesis space $\vH$.
To characterize the approximation error, we pose the following assumption on the realizability of the hypothesis class $\vH$.
[Realizability of hypothesis class]
Let $\vareH>0$ be the minimal positive value such that there exists $\vhHstar=\{\hHstark{1}, \cdots, \hHstark{K-1}, \gHstar\}\in\vH$ satisfying,

(i) $\nbr{\vT\vhHstar}_{ \mu, 2} \le \vareH$, where $\nbr{\vT\vhHstar}_{\mu, 2}$  is the RMSE defined in (<ref>).

(ii) $\sup_{v\in\cV} \nbr{\gHstar-\gstar}_{v, 2}\le \vareH$, where $\cV=\{v: v(x, a)=\tpr(x)\pie(a\given x), \forall \pie\in\Pie\}$.

Here, (i) characterizes the approximation error of $\vhHstar$ under the metric $\nbr{\cT(\cdot)}_{\mu, 2}$ where $\mu$ represents the distribution in the dataset, and the approximation error in (ii) is the supremum over all the possible measure that is realizable by the policy class $\Pie$.

We remark that $\vhHstar$ can be softly viewed as the projection of $\vhstar$ onto the hypothesis space $\vH$ with approximation error $\vareH$.
We then pose the following assumption on the compatibility of the test function class $\Theta_k$.
[Compatibility of test function class]
Suppose that for any $\vh\in\vH$ and for any $k\in\{1, \cdots, K\}$, it holds that
$\inf_{\theta_k\in\Theta_k} \nbr{\theta_k - \cT_k\vh}_{\mu_k, 2}\le \vareTheta$.

We give an example where the test function class has full compatibility. Following the discussion in [Dikkala et al., 2020], we consider a case where $\Theta_k$ lies in a Reproducing Kernel Hilbert space (RKHS) $\HH_{K_{\theta_k}}$ with RKHS kernel $K_{\theta_k}: \cZ_k\times\cZ_k\rightarrow \RR$. If $\alpha_k$ lies in another RKHS space $\HH_{K_{\alpha_k}}$ and the conditional density function $\pr(\vX, \vY_k\given \vZ_k)$ satisfies $\pr(\vX, \vY_k\given \cdot)\in \HH_{K_{\Theta_k}}$, we then have $\cT_k\vh\in \HH_{K_{\Theta_k}}$, which means that the dual function class has full compatibility. In addition, we pose the following assumption on the regularity of function classes $\vH$, $\vTheta$ and linear function $\alpha_k$.
We assume that $\alpha_k$ is $L_{\alpha, 1}$-Lipschitz continuous with respect to $h_j$ and $Y_k$ for all  $j,k\in\{1, \cdots, K\}$.
We assume that the support of $Y_k$ is bounded, i.e., $\nbr{\text{supp}(Y_k)}_\infty\le L_Y$.
Moreover, we assume that $\sup_{h\in\vH}\norm{h}_\infty\le L_{h}$ and $\sup_{\theta\in\vTheta}\norm{\theta}_\infty\le L_{\theta}$.

We justify the regularity assumption by the examples of CCB-IV and CCB-PV.
Following Theorems <ref> and <ref>,
we see that the continuity of $\alpha_k$ is apparent.
The regularity of $\vH$ and $\vTheta$ is easy to satisfy by choosing bounded function classes.
With bounded reward, it is straightforward that the linear function $\alpha_k(\vh, \vY_k)$ is globally bounded. Specifically, we can assume that  $\nbr{\alpha_k}_\infty\le L_\alpha$.

To characterize the properties of the confidence set Under these assumptions, we first define an event $\cE$ as

\begin{align}
\cE &= \Big\{\abr{\EE_{\cD_k}\sbr{\alpha_k(\vh, \cY_k) \theta_k(\cZ_k)} - \EE_{\mu_k}\sbr{\alpha_k(\vh, \cY_k) \theta_k(\cZ_k)}} \le \eta_k\rbr{L_\alpha\nbr{\theta_k}_{\mu_k, 2}+\eta_k},\nend
&\quad \abr{\norm{\theta_k}^2_{\cD_k, 2}-\norm{\theta_k}^2_{\mu_k, 2}}\le \frac 1 2\rbr{\norm{\theta_k}^2_{\mu_k, 2}+\eta_k^2},
\forall \vh\in \vH, \forall \theta_k\in\Theta_k, \forall k\in\{1, \cdots, K\}\Big\}.\label{def:cE}
\end{align}

where $\eta_k$ bounds the maximal critic radius for function classes $\cQ_k$ and $\Theta_k$ with respect to $\xi\in(0, 1)$. Here, we define function class $\cQ_k$ as

\begin{align*}
\cQ_k=\cbr{\alpha_k(\vh(\vX_k), \vY_k)\theta_k: \forall \vh\in\vH, \theta_k\in\Theta_k}.
\end{align*}

See <ref> for calculation of the critical radius in the case of linear function class.
We let $\eta^2=\sum_{k=1}^K \eta_k^2$ for simplicity. Now we give the following theorem, which shows that event $\cE$ holds with high probability and the confidence set built for uncertainty quantification enjoys some good properties.

Suppose that Assumptions <ref>, <ref> and <ref>  hold.
Event $\cE$ holds with probability at least $1-2K\xi$ and the confidence set enjoys the following properties on $\cE$,

(i). For the $\vhHstar$ satisfying Assumption <ref>, it holds that $\cL_\cD(\vhHstar) \le 2\vareH^2 + \rbr{2 L_\alpha^2+5 /4}\eta^2$. Moreover, if we set $e_\cD>2\vareH^2 + \rbr{2 L_\alpha^2+ 5/ 4}\eta^2$, it holds that $\gHstar\in\CICATE(e_\cD)$.

(ii). For all $\vh\in\CIH(e_\cD)$, we have,

\begin{align*}
\sup_{k\in\{1, \cdots, K\}}\nbr{\cT_k\vh}_{\mu_k, 2}\overset{\cE}{\lesssim} \cO(\vareTheta) + \cO(\vareH) + \cO\rbr{\sqrt{e_\cD}} +  \cO\rbr{\eta}.
\end{align*}

See <ref> for a detailed proof.

Theorem <ref> shows that event $\cE$ holds with a high probability.
We see from (i) that it is theoretically guaranteed that $\vhHstar$ lies within the confidence set by properly setting the threshold $e_\cD$. As will be shown shortly after, such a property is vital for the use of pessimism.
Property (ii) in Theorem <ref> shows that the RMSE for any $\vh\in\CIH(e_\cD)$ is well controlled on event $\cE$.
Now we are ready to present the convergence results for the sub-optimality defined in (<ref>). We give the following theorem on the sub-optimality for the CCB-IV.

Suppose that Assumption
<ref> for the CCB-IV model and the conditions in Remark <ref> hold.
Suppose that Assumptions
<ref>,  <ref>, and
<ref> for function classes $\vH$ and $\Theta$ hold.
The threshold $e_\cD$ for the confidence set is set to $e_{\cD}>2\vareH^2 + (2 L_\alpha^2+5/ 4)\eta^2$.
For the marginal distribution of context $\tpr$ in the interventional process and the optimal interventional policy $\piestar$, suppose that there exists $b_1:\cZ\rightarrow \RR$ satisfying

\begin{align}
\EEob\sbr{b_1(Z)\given A=a, X=x, R_Z=1} = \frac{\tpr(x)\piestar(a\given x)}{\pob(x, a\given R_Z=1)}.\label{cond:CCB-IV b1 exist}
\end{align}

The sub-optimality corresponding to $\piepessi$ for the CCB-IV is bounded on event $\cE$ with probability at least $1-4\xi$ by

\begin{align*}
\SubOpt(\piepessi) \overset{\cE}{\lesssim} \sum_{k=1}^2 \nbr{b_k}_{\mu_k, 2}\cdot \big(\cO(\vareTheta) + \cO(\vareH) + \cO\rbr{\sqrt{e_\cD}} +  \cO\rbr{\eta}\big),
\end{align*}

where $b_2:\cA\times\cX\times\cZ\rightarrow \RR$ is defined as,

\begin{gather}
b_2(a, x, z)=b_1(z)\frac{\pob(a, x, z\given R_Z=1)}{\pob(a, x, z\given(R_X, R_Z)=\ind)}.\label{eq:b2 IV}
\end{gather}

See <ref> and <ref> for a detailed proof.

Similarly, the convergence of sub-optimality for CCB-PV is given by

Suppose that Assumption
<ref> for the CCB-PV model and the conditions in Remark <ref> hold.
Suppose that Assumptions
<ref>, <ref>, and
<ref> for function classes $\vH$ and $\Theta$ hold.
The threshold $e_\cD$ for the confidence set is set to $e_{\cD}>2\vareH^2 + (2 L_\alpha^2+5/ 4)\eta^2$.
For the marginal context distribution  $\tpr$ in the interventional process and the optimal interventional policy $\piestar$, suppose that there exists $b_1:\cX\times\cA\times\cZ\rightarrow\RR$ satisfying

\begin{align}
\EEob\sbr{b_1(X, A, Z)\given X=x, U=u, A=a, R_Z=\ind} = \frac{\pob(u\given x)\tpr(x)\piestar(a\given x)}{\pob(u, x, a\given  R_Z=1)}.\label{cond:CCB-PV b1 exist}
\end{align}

The sub-optimality corresponding to $\piepessi$ for the CCB-PV is bounded with probability at least $1-8\xi$ by

\begin{align*}
\SubOpt(\piepessi) \lesssim \sum_{k=1}^4 \nbr{b_k}_{\mu_k, 2}\cdot \big(\cO(\vareTheta) + \cO(\vareH) + \cO\rbr{\sqrt{e_\cD}} +  \cO\rbr{\eta}\big),
\end{align*}

where $b_2:\cA\times\cW\times\cX\times\cZ$, $b_3:\cW\times\cX\times\cA\times\cA'$ and $b_4:\cX\times\cA'\rightarrow\RR$ are defined as

\begin{gather}
b_2(a, w, x, z) = b_1(x, a, z)\frac{\pob(a, w, x\given (R_X, R_Z)=\ind)}{\pob(a, w, x\given (R_W, R_X, R_Z)=\ind)}.\nend
b_3(w, x, a, a') = \frac{\tpr(x)\piestar(a'\given x)\pob(a, w\given x, R_X=1)}{u(a')\pob(x, a, w\given (R_W, R_X)=\ind)}, \quad
b_4(x, a') = \frac{\tpr(x)\piestar(a'\given x)}{\pob(x\given R_X=1)u(a')}.\nonumber
\end{gather}

See <ref> and <ref> for a detailed proof.

Remarks on the existence of $b_1$. We remark that the existence of $b_1$ in (<ref>) and (<ref>) are also related to the linear inverse problem,  as is discussed in <ref>. In the discrete setting, (<ref>) is automatically satisfied if the distribution shift ratio on the right-hand side is globally bounded. This is because we already have $\text{rank}(P(Z\given (A,X), R_Z=1))\ge |\cA|\times|\cX|$ by the IV completeness assumption and thus the Moore-Penrose inverse  $P(Z\given (A,X), R_Z=1)^+$ exists. Similarly, (<ref>) is also automatically satisfied in the discrete setting following the PV completeness assumption.

Significance of the main theorems.
Theorem <ref> and <ref> establish the convergence of the sub-optimality for the CAP algorithm in the offline confounded contextual bandit with missingness.
Such results are achieved by using the minimax estimator, building a confidence set for the CATE, and integrating pessimism in the policy optimization step.
Our theories deal with model misspecification in the hypothesis space and the dual function class. Moreover, the sub-optimality does not rely on the “uniform coverage” of the observational dataset, e.g., uniformly lower bounded densities of visitation measures [Yang et al., 2020, Liao et al., 2020, Duan et al., 2020].
This is because the distribution shift ratio $b_k$ only depends on the optimal policy $\piestar$, which is intrinsic to the bandit model, instead of the whole policy class $\Pie$. Therefore, we only require the dataset to “cover” certain distributions induced by $\piestar$.

Implications of the main theorems.
When it holds that $\eta\sim\tcO(n^{-1/2})$ (see <ref> for a calculation of the critical radius of the linear function class) and $\vareH=\vareTheta=0$, by setting $e_\cD\sim\tcO(n^{-1})$, Theorem <ref> and <ref> indicates that $\SubOpt(\piepessi)\sim\tcO(n^{-1/2})$, which corresponds to a “fast statistical rate” for minimax estimation [Uehara et al., 2021].

However, given the fact that the distribution shift ratio $b_k$ also stems from the missingness issue, we require some “compliance” of the data distribution with missingness in order for $b_k$ to be bounded. For instance, we require $\pob(a, x, z\given  R_Z=1)=\cO(\pob(a, x, z\given (R_X, R_Z)=\ind))$ for $b_2$ in (<ref>) to be bounded. Such a condition is reasonable if we consider a counterexample where $\pob(x_0\given R_Z)>0$ but $\pob(x_0\given (R_X, R_Z)=\ind)=0$ for $x_0\in \cX$, meaning that $x_0$ is totally missing from the observed dataset $\cD$. Therefore, there is no way to learn the CATE corresponding to $x_0$.
On the other hand, following the discussion in <ref> on the critical radius of a linear function class, we have $\eta_k\sim\cO(\sqrt{\log T_k/T_k})$ where $T_k=|\cD_k|$. Recall that $\cD_k$ may have different size since the conditional moment equations in the IES are subject to different missingness conditions.
Therefore, we also require $T_k$ being of the same order of $T$ for $\SubOpt(\piepessi)$ to enjoy a fast statistical rate.

§ EXTENDED POLICY CLASS FOR CCB-PV

In the previous discussion, since we assume that the side observations are not accessible in the interventional process, we restrict our interventional policy to the class $\pie:\cX\rightarrow \Delta(\cA)$.
In this section, we discuss an extension to the setting with accessible side observations in the interventional process.
Note that we have $Z\indep Y\given (X, A)$ in the CCB-IV, meaning that including the side observation $Z$ adds no additional information to the outcome and therefore the policy class $\pie:\cX\rightarrow \Delta(\cA)$ is good enough.
In the CCB-PV setting, however, it is possible to improve the performance by allowing the interventional policy to also depend on the side observations.
Specifically, we consider an extension of the CCB-PV setting where the interventional policy class is given by $\pie\in\Pie:\cX\times\cW\rightarrow \Delta(\cA)$.
We have to redefine the CATE and average reward function for the extended policy class by

\begin{align}
&\CATE(a, x, w) = \EEin\sbr{Y\given X=x, W=x, \doopt(a)}, \nonumber\\
&v^\pi(x) = \EE_{\pin{\pie}} \sbr{\CATE(A, X, W)\given X=x},\label{def:extended v}
\end{align}

where $\pin{\pie}$ is given  by plugging  $\pie=(a\given x, w)$ into the joint distribution of the interventional process in (<ref>).
Following the model in Assumption <ref>, we provide the identification IES as follows.

Suppose Assumption <ref> holds. For any interventional policy $\pie:\cX\times\cW\rightarrow\Delta(\cA)$, if there exist bridge functions $h_1:\cY\times\cA\times\cX\times\cZ\rightarrow\RR$, $h_2:\cA\times\cW\times\cX\rightarrow \RR$, $h_3:\cY\times\cA\times\cX\times\cA\rightarrow\RR$ and $g:\cX\rightarrow \RR$ satisfying,

\begin{align}
&\EEob\sbr{h_1(Y, A, X, Z)\given a,x,z, (R_X, R_Z)=\ind} = 0,
% \label{eq:PV ID extension 1}
\nend
&\EEob[h_2(A, W, X) - h_1(Y, A, X, Z)-Y\pie(A\given X, W)
\given a, w, x, z, (R_W, R_X, R_Z)=\ind]=0,
% \label{eq:PV ID extension 2}
\nend
&\EEob\sbr{h_3(Y, A, X)-\sum_{a'\in\cA}h_2(a', W, X)\given a, w, x, (R_W, R_X)=\ind}=0,
\label{eq:PV ID extension 3}
\\
&\EEob\sbr{g(X) - h_3(Y, A, X)\given x, R_X=1}=0,
\label{eq:PV ID extension 4}
\end{align}

it follows that $ v^\pie(x)\aseq g(x)$ where $v^\pie$ is the average reward.

See <ref> for a detailed proof.

Existence of the solution.
The conditions for existence of a solution to such an IES is similar to Remark <ref>, except that the first condition is adjusted by assuming there exists a solution $h_2$ to $\EEob\sbr{h_2(A, W, X)-Y\pie(A\given W, X)\given A=a, X=x, U=u}$ and the rest two conditions are just the same.

A comparison to Theorem <ref>.
The differences between these two versions of identification formula are in three folds: (i) The identification equations in Theorem <ref> are policy specific while those in Theorem <ref> hold for any interventional policy; (ii) there is no need for introducing a pseudo variable $A'$ here since $a'$ is already marginalized in (<ref>); (iii) $g$ corresponds to the average reward instead of the CATE.

Note that the linear function $\alpha$, the operator $\cT$ and the loss function $\cL_\cD$ should depend on policy $\pie$ and we denote them by $\alpha^\pie$, $\cT^\pie$ and $\cL_\cD^\pie$, respectively.
The confidence set is built for each $\pie$ by

\begin{align*}
\CICATE^\pie = \cbr{g\in\cG: \exists \vh\in\vH \text{, s.t., } g=\vh^{(K)} \text{ and }\cL_\cD^\pie(\vh)\le \inf_{\vh\in\vH}\cL_\cD^\pie(\vh)+e_\cD},
\end{align*}

Therefore, the estimated policy with pessimism is given by

\begin{align}
\piepessi = \arg\sup_{\pie\in\Pie} \inf_{g\in\CICATE^\pie(e_\cD)} v(g), \quad \text{where } v(g) = \int_{\cX} g(x) \tpr(x)\rd x.\label{def:extended piepessi}
\end{align}

Before we give the main theorem, we restate the realizability assumption (Assumption <ref>) as follows.
[Realizability of hypothesis class for extended CCB-PV]
Let $\vareH>0$ be the minimal positive value such that there exists $\vhHpie=\{\hHpiek{1}, \cdots, \hHpiek{K-1}, \gHpie\}\in\vH$ satisfying,

(i) $\sup_{\pie\in\Pie}\nbr{\vT^\pie\vhHpie}_{\mu, 2} \le \vareH$

(ii) $\sup_{\pie\in\Pie}\nbr{\gHpie-g^\pie}_{\tpr, 2}\le \vareH$, where $g^\pie$ is the exact solution to the identification equations in Theorem <ref>.

The compatibility assumption can be easily adjusted by assuming that $\inf_{\theta_k\in\Theta_k} \nbr{\theta_k - \cT_k^\pie\vh}_{\mu_k, 2}\le \vareTheta$ for any $\pie\in \Pie$. The regularity assumption remains the same, except that we also assume  $\nbr{\pie}_\infty$ to be bounded in order to have $\alpha^\pie_k$ globally bounded.
Now we provide the following theorem to characterize the convergence of sub-optimality for the CCB-PV with extended interventional policy.

Suppose that Assumptions <ref>, <ref>, <ref>,
<ref> hold and the solution to the IES in Theorem <ref> exists.
let $e_{\cD}>2\vareH^2 + (2 L_\alpha^2+5/ 4)\eta^2$, where $\eta=\sum_{k=1}^K\eta_k^2$ and $\eta_k$ bounds the maximal critic radius for function classes $\tilde\cQ_k=\cbr{\alpha_k^\pie(\vh(\vX_k), \vY_k)\theta_k: \forall \vh\in\vH, \theta_k\in\Theta_k, \pie\in\Pi}$ and $\Theta_k$. Suppose that for any $x\in\cX, u\in\cU$ and $a\in\cA$ there exists $b_1:\cX\times\cA\times\cZ\rightarrow\RR$ satisfying

\begin{align}
\EEob\sbr{b_1(X, A, Z)\given x, u, a, R_Z=1} = \frac{\pob(u\given x)\tpr(x)}{\pob(u, x, a\given R_Z=1)}.\label{cond:b1 PV extended}
\end{align}

The sub-optimality corresponding to $\piepessi$ for the CCB-PV with extended policy class is bounded with probability at least $1-8\xi$ by

\begin{align*}
\SubOpt(\piepessi) \lesssim \sum_{k=1}^4 \nbr{b_k}_{\mu_k, 2} \cdot \rbr{O(\vareTheta) + O(\vareH) + O\rbr{\sqrt{e_\cD}} +  O\rbr{\eta}},
\end{align*}

where $b_2:\cA\times\cW\times\cX\times\cZ\rightarrow\RR$, $b_3:\cW\times\cX\times\cA\rightarrow\RR$ and $b_4:\cX\rightarrow\RR$ are defined by

\begin{align*}
&b_2(a, w, x, z) = b_1(x, a, z)\frac{\pob(a, w, x\given (R_X, R_Z)=\ind)}{\pob(a, w, x\given (R_W, R_X, R_Z)=\ind)}, \\
&b_3(w, x, a) = \frac{\tpr(x)\pob(a, w\given x, R_X=1)}{\pob(x, a, w\given (R_W, R_X)=\ind)}, \\
&b_4(x) = \frac{\tpr(x)}{\pob(x\given R_X=1)}.
\end{align*}

See <ref> for a detailed proof.

The arguments are similar except that each action should be “uniformly covered” in the observational process if we want $b_1$ to be bounded by (<ref>), which implies that $|\cA|$ should be finite or a bounded set. Moreover, $\eta_k$ bounds the maximal critical radius for the function class $\tilde\cQ_k$, which also bounds the critical radius of the policy class $\Pie$. In <ref>, such a critical radius is calculated with linear function class assumptions for the one-step POMDP.

§ APPLICATION OF CCB-IV: LINEAR DYNAMIC TREATMENT REGIMES

Background. Dynamic treatment regimes (DTRs) is an extension of the individualized treatment rules (ITRs) to multi-steps. Estimating optimal policy can be challenging with unmeasured confounders in the observational dataset
[Chen and Zhang, 2021, Qi et al., 2021, Zhang and Bareinboim, 2019, Singh and Syrgkanis, 2022].
We consider a DTRs with two steps, which is graphically represented in Figure <ref>.

[missingstate] (X1) $X_1$;
[missingstate] (X2) [right=of X1] $X_2$;
[state] (A1) [below=of X1] $A_1$;
[state] (A2) [below=of X2] $A_2$;
[state] (Y1) [above=of X2] $Y_1$;
[state] (Y2) [right=of X2] $Y_2$;
[hiddenstate] (U) [below=of Y2] $U$;
[draw, fit=(X1) (X2) (A1) (A2)] (H) ;

[normal] (X1) edge (A1);
[normal, blue] (X1) edge (A2);
[normal] (X1) edge (X2);
[normal] (X1) edge (Y1);
[normal, blue] (X2) edge (A2);
[normal] (X2) edge (Y1);
[normal] (A1) edge (Y1);
[normal] (A1) edge (X2);
[normal, blue] (A1) edge (A2);
[normal, blue] (Y1) edge[bend left=40] (A2);
[normal] (U) edge (X2);
[normal] (U) edge (Y2);
[normal, blue] (U) edge (A2);
[normal] (H) edge (Y2);

DAG of the observational process in DTR

[state] (X1) $X_1$;
[state] (X2) [right=of X1] $X_2$;
[state] (A1) [below=of X1] $A_1$;
[state] (A2) [below=of X2] $A_2$;
[state] (Y1) [above=of X2] $Y_1$;
[state] (Y2) [right=of X2] $Y_2$;
[hiddenstate] (U) [below=of Y2] $U$;
[draw, fit=(X1) (X2) (A1) (A2)] (H) ;

[normal] (X1) edge (A1);
[normal, red] (X1) edge (A2);
[normal] (X1) edge (X2);
[normal] (X1) edge (Y1);
[normal, red] (X2) edge (A2);
[normal] (X2) edge (Y1);
[normal] (A1) edge (Y1);
[normal] (A1) edge (X2);
[normal, red] (A1) edge (A2);
[normal] (U) edge (X2);
[normal] (U) edge (Y2);
[normal] (H) edge (Y2);

DAG of the interventional process in DTR

A DAG illustrating the DTR model. Note that $Y_2$ depends on the whole trajectory $H$

In the observational process, at stage $i\in\{1, 2\}$, the treatment $A_i$ is selected based on the current state $X_i$ and the historical information $\{(X_j, A_j, Y_j)\}_{j=1}^{i-1}$. Then the state transits to $X_{i+1}$ and a reward $Y_i$ is generated. At the second state, $X_2$, $A_2$ and $Y_2$ are confounded by an unmeasured confounder $U$. Since the first step is not influenced by $U$, we have $Y_1\indep U\given (X_1, X_2, A_1)$. Therefore, we see that the first state reward $Y_1$ serves as an instrumental variable to $A_2$. Here, we provide table <ref> to illustrate the mapping from this two-stage DTRs to the CCB-IV model.

Variable Type     Two-step DTRs     Observability in $\cD$     Correspondence to CCB-IV

confounder          $U$                     unobservable        $U$

context             $(X_1, X_2, A_1)$       partially missing      $X$

treatment           $A_2$                   observable     $A$

outcome             $Y_2$                   observable     $Y$

IV                  $Y_1$                   observable     $Z$

Mapping of variables from the two-state DTRs to the CCB-IV.

We assume that $Y_2=f(X_1, X_2, A_1, A_2)+\varepsilon$ where $\varepsilon\indep (A_1, A_2)\given (U, X_1, X_2)$ and that $Y_1$ and $Y_2$ are fully observed, which satisfies the structured reward assumption.
For $Y_1$ to function as an IV, we require that $Y_1$ is complete over $(X_1, X_2, A_1, A_2)$.
Additionally, in the observational process, the missingness indicator $R_{X_1}$ is caused by $(X_1, A_1)$ and the missingness indicator $R_{X_2}$ is caused by $(X_1, A_1, X_2, A_2)$.
Therefore, the model assumptions for CCB-IV are satisfied.
By Theorem <ref>, the CATE $g(x_1, a_1, x_2, a_2)=\EEob\sbr{Y_2\given x_1, a_1, x_2, \doopt(a_2)}$ is identified by

\begin{align}
&\EEob\sbr{h_1(A, Y) - Y_2\given Y_1=y_1}=0, \label{eq:DTR ID 1}\\
&\EEob\sbr{g(X, A)-h_1(A, Y) \given (X, A, Y_1)=(x, a, y_1), (R_{X_1}, R_{X_2})=\ind}=0.\label{eq:DTR ID 2}
\end{align}

We assume that the solutions $h_1$ and $g$ always exist, which requires certain completeness conditions for $Y_2$ to restore the missingness in $X_1$ and $X_2$.
Here, we let $X=(X_1, X_2)$, $A=(A_1, A_2)$ and $Y=(Y_1, Y_2)$ in the remaining part of the section for DTRs example.

Note that $Y_2\indep \pib_1\given (X_1, A_1, X_2)$ in the observational settings, since $A_1$ is not confounded. We thereby have $g(x, a)=\EEob\sbr{Y_2\given x, \doopt(a)}$.
Our optimization target thereby corresponds to maximizing the average reward function on $\pie=(\pi_1, \pi_2)\in\Pi$,

\begin{align*}
v(g, \pie)=&\int_{\cX\times\cA} g(x,a) \tpr(x_1) \pob(x_2\given x_1, a_1)   \pi_1(a_1\given x_1) \pi_2(a_2\given x_1, a_1, x_2)
\rd x\rd a,
\end{align*}

where we assume that $\pob(x_2\given x_1, a_1)$ is already known for brevity, although a little extension of our framework is capable of dealing with unknown $\pob(x_2\given x_1, a_1)$ by learning from data. Moreover, we only consider $Y_2$ as the reward. We remark that, since the first stage is not confounded, $\EEob\sbr{Y_1\given x_1, \doopt(a_1), x_2}$ can also be easily learned and integrated into the average reward. Now we pose the following assumptions on the linearity of the DTRs model.

Linear function class. We make the following assumptions to ensure the existence of the bridge functions and the linearity of our DTRs model.
[Existence of linear bridge functions]
We assume that a solution $\vhstar=(\hstark{1}, \gstar)$ exists to the IES given by (<ref>) and (<ref>). Furthermore, we assume that $\hstark{1}, \gstar$ fall into the following function classes,

\begin{align*}
&\cH_1=\{h_1\given h_1(\cdot)=w_1^\top \phi_1(\cdot), \nbr{w_1}_2\le C_1, \nbr{\phi_1(\cdot)}_2\le 1\}, \\
&\cG=\{g\given g(\cdot)=w_2^\top \phi_2(\cdot), \nbr{w_2}_2\le C_2, \nbr{\phi_2(\cdot)}_2\le 1\},
\end{align*}

where $\phi_1:\cA\times\cY\rightarrow \RR^{m_1}$ and $\phi_2:\cX\times\cA\rightarrow \RR^{m_2}$.
Moreover, we assume that $\hstark{1}=(w_1^*)^\top \phi_1$ and $\gstar=(w_2^*)^\top\phi_2$.

Assumption <ref> assumes the existence and linearity of $\vh$.
We remark that it suffices for (i) to hold if $\EEob\sbr{Y_2\given y_1}$ is captured by the linear kernel $\EEob\sbr{\phi_2(X, A)\given y_1}$, and it suffices for assumption (ii) to hold if $\gstar(x, a)$ is captured by the linear kernel $\EEob\sbr{\phi_1(A, Y)\given y_1, x, a}$ for any $y_1\in\cY_1$.
In addition, Assumption <ref> also suggests that by using $\cH=\cH_1\times \cG$ as the hypothesis class, we have no realizability error, i.e., $\vareH=0$.
For the linear kernel $\phi_1$ and $\phi_2$, we continue to assume that their conditional expectation also falls into some linear spaces.
[Linearity of dual function class]
We assume that the conditional expectations of kernel $\phi_1$ and $\phi_2$ with respect to (<ref>)  and (<ref>) satisfy,

(i) $\EEob\sbr{\phi_1(A, Y)\given y_1} = W_1 \psi_1(y_1)$, where $\psi_1:\cY_1\rightarrow \RR^{d_1}$, $W_1\in\RR^{m_1\times d_1}$.

(ii) $\EEob\sbr{\phi_1(A, Y)\given (x, a, y_1), (R_{X_1}, R_{X_2})=\ind}=W_2\psi_2(x, a, y_1)$, where $\psi_2:\cX_1\times\cA_1\times\cX_2\times\cA_2\times\cY_1\rightarrow \RR^{d_2}$, $W_2\in\RR^{m_1\times d_2}$.

(iii) $\EEob\sbr{\phi_2(X, A)\given (x, a, y_1), (R_{X_1}, R_{X_2})=\ind}=W_3\psi_2(x, a, y_1)$, where $W_3\in\RR^{m_2\times d_2}$.

In Assumption <ref>, we remark that if the operator $T:\cF(\cA\times\cY)\rightarrow \cF(\cY_1)$ defined as $Tf(y_1) =\EEob\sbr{f(A, Y)\given y_1}$ is captured by the kernel $\psi_1(y_1)$, it suffices for $W_1$ to exists. Similarly, it suffices for (ii), (iii) to hold if the corresponding operators are captured by the linear kernel $\psi_2(x, a, y_1)$.
Following Assumption <ref>, it holds for the linear operator $\cT$ that

\begin{align*}
&\cT_1 \vh(y_1) = (w_1-w_1^*)^\top W_1 \psi_1(y_1), \\
&\cT_2 \vh(x, a, y_1) = \rbr{(w_2-w_2^*)^\top W_3-(w_1-w_1^*)^\top W_2}\psi_2(x, a, y_1),
\end{align*}

which suggests that $\cT_1\vh$ and $\cT_2\vh$ fall into the following linear function classes,

\begin{align*}
\Theta_k=\{\theta_k\given \theta_k(\cdot)= \beta_k^\top \psi_k(\cdot), \beta_k\in\RR^{d_k}, \nbr{\beta_k}\le D_k, \nbr{\psi_k(\cdot)}_2\le 1\},
\end{align*}

where we have $D_1>2C_1 \nbr{W_1}_F$ and $D_2> 2 (C_1\nbr{W_2}_F+C_2\nbr{W_3}_F)$.
By further letting $\vTheta=\Theta_1\times \Theta_2$, the dual function space has full compatibility, i.e., $\vareH$ and $\vareTheta$ are both zero. By Theorem <ref>, we have the following corollary to establish the convergence of the sub-optimality for the two-step linear DTRs.

Suppose that Assumptions <ref> and <ref> hold. Let $e_{\cD}>(2 L_\alpha^2+5/ 4)\eta^2$ where $\eta=\sum_{k=1}^2\eta_k^2$ and $\eta_k$ bounds the critic radius for function class $\cQ_k=\{\alpha_k(\vh, \cdot)\theta_k: \vh\in\vH, \theta_k\in\Theta_k\}$. Assume that for any $x\in\cX$ and $a\in\cA$, there exists $b_1:\cY_1\rightarrow \RR$ satisfying

\begin{align*}
\EEob\sbr{b_1(Y_1)\given x, a} = \frac{\tpr(x_1)\pob(x_2\given x_1, a_1)\piestar_1(a_1\given x_1)\piestar_2(a_2\given x_1, a_1, x_2)}{\pob(x_1, a_1, x_2, a_2)}.
\end{align*}

The sub-optimality of $\piepessi$ for the two-step DTRs is bounded with probability at least $1-4\xi$ by

\begin{align*}
\SubOpt(\piepessi) \lesssim  \rbr{\nbr{b_1}_{\mu_1, 2}+\nbr{b_2}_{\mu_2, 2}}\cdot \rbr{O\rbr{\sqrt{e_\cD}} +  O\rbr{\eta}},
\end{align*}

where $b_2:\cX\times\cA\times\cY_1\rightarrow \RR$ is defined by

\begin{gather*}
b_2(x,a, y_1)=\frac{b_1(y_1)\pob(x_1, a_1, x_2, a_2, y_1)}{\pob(x_1, a_1, x_2, a_2, y_1\given(R_{X_1}, R_{X_2})=\ind)}.
\end{gather*}

As is proved in <ref>, the critical radiuses are of order $\eta_1=\cO(\sqrt{(m_1+d_1)\log T/T})$ and $\eta_2=\cO(\sqrt{\max\{m_1+m_2+d_2\}\log T_2/T_2})$, where $T$ corresponds to the size of the whole dataset $\cD$ and $T_2$ corresponds to the size of the dataset satisfying $(R_{X_1}, R_{X_2})=\ind$. Such a result shows that the convergence rate is of the order $\cO(\sqrt{\log T_2/T_2})$ if we choose $e_\cD=\cO(\log T_2/T_2)$.
Note that $T_2$ is the total number of samples that are subject to no missingness, which requires that there should be a fixed proportion of samples on which we have fully observed contexts and side-observations to guarantee the fast convergence rate.

§ APPLICATION OF CCB-PV WITH EXTENDED POLICY CLASS: ONE-STEP LINEAR PARTIALLY OBSERVABLE MARKOV DECISION PROCESS

We consider a one-step Partially Observable Markov Decision Process (POMDP) following the example in [Shi et al., 2021, Uehara et al., 2021]. Here, the term "one-step" means that we only care about the policy and reward at the first step, but the environment is allowed to transit into the following steps.
The POMDP starts with a pre-observation $O^-$ and the environment transits into state $S$. An observation $O$ is generated according to $S$, and the agent in the observational process takes an action $A$ according to $\pib:\cS\rightarrow \Delta(\cA)$. After the action is conducted, a reward $Y_0$ is received and the environment transits into the following state $S^+$ with observation $O^+$.
Note that $Y$ is allowed to depend on $O$.
In the interventional process, since the agent gains no access to the hidden state, its policy can only depend on the observations.
We consider the extended interventional policy class discussed in <ref>, i.e.,  $\pie:\cO^-\times\cO\rightarrow\Delta(\cA)$ by viewing $O^-$ as the context ($X$ in CCB-PV) and $O$ as the outcome proxy ($W$ in CCB-PV).
Note that such a policy also captures the case where the policy only depends on $O$.

[hiddenstate] (S) [right=of O] $S$;
[missingstate] (O) [above=of S] $O$;
[missingstate] (O-) [left=of S] $O^-$;
[state] (A) [below=of S] $A$;
[hiddenstate] (S+) [right=of S] $S^+$;
[state] (Y) [below=of S+] $Y$;
[missingstate] (O+) [above=of S+] $O^+$;
[state] (A+) [right=of S+] $A^+$;
[normal] (O-) edge (S);
[normal] (O) edge (Y);
[normal] (S) edge (O);
[normal, blue] (S) edge (A);
[normal] (S) edge (S+);
[normal] (S) edge (Y);
[normal] (A) edge (S+);
[normal] (A) edge (Y);
[normal] (S+) edge (O+);
[normal] (S+) edge (A+);

DAG of the observational process in one-step POMDP.

[hiddenstate] (S) [right=of O] $S$;
[state] (O) [above=of S] $O$;
[state] (O-) [left=of S] $O^-$;
[state] (A) [below=of S] $A$;
[hiddenstate] (S+) [right=of S] $S^+$;
[state] (Y) [below=of S+] $Y$;
[state] (O+) [above=of S+] $O^+$;
[normal] (O-) edge (S);
[normal] (O) edge (Y);
[normal] (S) edge (O);
[normal] (S) edge (S+);
[normal] (S) edge (Y);
[normal] (A) edge (S+);
[normal] (A) edge (Y);
[normal] (S+) edge (O+);
[normal, red] (O) edge[bend left=-30] (A);
[normal, red] (O-) edge (A);

DAG of the interventional process in one-step POMDP.

A DAG illustration of the one-step POMDP model.

Missingness. Very similar to the DTRs example, we assume that $R_{O}$ is caused by $O$ and $A$ and $R_{O^+}$ is caused by $O^+$ and $A^+$ in the observational dataset. Note that the pre-observation $O^-$ is exogenous to the model, it is thereby reasonable to assume that $R_{O^-}$ only depends on $O^-$. A tricky part is that following the observational policy, we have that $A^+\sim \pib(a^+\given s^+)$ and $S^+\sim \pr(s^+\given s, a)$. It thus turns out that $R_{O^+}$ is alternatively caused by $(O^+, S, A)$.

Mapping to CCB-PV. We provide a mapping from this one-step POMDP to the CCB-PV in Table <ref>.
It is easy to verify that the assumption of PV independence and the assumption of unconfounded and outcome-independent missingness in Assumption <ref> both hold for this one-step POMDP. The PV complete assumption corresponds to assuming that $O^+$ is complete over $S$, i.e., for any $a\in\cA$, $o^-\in\cO^-$, $\EEob\sbr{\sigma(S)\given o^-, a, o^+, R_{O^+}=1}=0$ holds for any $o^+\in\cO^+$ if and only if $\sigma(S^+)\overset{\text{a.s.}}{=} 0$ holds. Such an assumption suggests this should be a non-degenerate MDP, i.e., $O^+$ still contains sufficient information of the hidden state of the previous step.
Then following Theorem <ref>, we have the $v^\pie(x)$ identified by

\begin{align}
&\EEob\sbr{h_1(Y, A, O^-, O^+) \given a, o^-, o^+, (R_{O^-}, R_{O^+})=\ind}=0, \label{eq:POMDP ID 1}\\
&\EEob\sbr{h_2(A, O, O^-) - h_1(Y, A, O^-, O^+)-Y\pie(A\given O^-, O)\given a, o, o^-, o^+, (R_{O}, R_{O^-}, R_{O^+})=\ind},
% \label{eq:POMDP ID 2}
\nend
&\EEob\sbr{h_3(Y, A, O^-)-\sum_{a'\in\cA} h_2(a', O, O^-)\given a, o, o^-, (R_{O}, R_{O^-})=\ind},
% \label{eq:POMDP ID 3}
\nend
&\EEob\sbr{g^\pie(O^-)-h_3(Y, A, O^-)\given o^-, R_{O^-}=1}=0, \label{eq:POMDP ID 4}
\end{align}

if the bridge functions exist.

Variable Type     One-step POMDP      Observability in $\cD$     Correspondence to CCB-PV

confounder              $S$     unobservable            $U$

context                 $O^-$     partially missing       $X$

treatment               $A$     observable              $A$

outcome                 $Y$     observable              $Y$

treatment proxy         $O^+$     partially missing       $Z$

outcome proxy           $O$     partially missing       $W$

Mapping of variables from the one-step POMDP to the CCB-PV.

Linear function class. Similar to the linear DTRs example, we characterize the existence of the bridge functions and the linearity of the one-step POMDP model. We assume that the interventional policy falls into some linear function class. Specifically, we let $\Pie$ be a subset of the following linear function class,

\begin{align}
\Pie = \cbr{\pie \bigg | \pie(a\given o, o^-)=\frac{\exp\rbr{w_0^\top\phi_0(a, o, o^-)}}{\sum_{a'\in\cA}\exp\rbr{w_0^\top\phi_0(a', o, o^-)}}, w_0\in\RR^{m_2}, \nbr{w_0}_2\le C_0,  \nbr{\phi_0(\cdot)}_2\le 1}.\label{def:linear policy}
\end{align}

[Existence of linear bridge function]
We assume that for any $\pie\in\Pie$, there exists $\vh^{\pie, *}=(h_1^{\pie, *}, h_2^{\pie, *}, h_3^{\pie, *}, g^{\pie, *})$ as a solution to the IES (<ref>)-(<ref>).
In addition, we assume that $h_1^{\pie, *}, h_2^{\pie, *}, h_3^{\pie, *}$ fall into the following linear function classes,

\begin{gather*}
\cH_k=\{h_k\given h_k(\cdot)= w_k^\top\phi_k(\cdot), w_k\in\RR^{m_k}, \nbr{w_k}_2\le C_k, \nbr{\phi_k(\cdot)}\le 1\}, \quad k=1, 2, 3,
\end{gather*}

with $h_k^{\pie, *}=(w_k^{\pie, *})^\top \phi_k$.

Assumption <ref> assumes the bridge functions to exist and fall into some linear function classes.
Now for the corresponding kernels $\phi_1$, $\phi_2$ and $\phi_3$, we assume their conditional moments are captured by kernel series $\psi_1, \psi_2, \psi_3, \psi_4$.
[Linearity of the dual function class]
We assume that the kernel $\phi_1$, $\phi_2$, $\phi_3$, $\psi_4$ satisfies

(i) $\EEob\sbr{\phi_1(Y, A, O^-, O^+)\given a, o^-, o^+, R_{o^+}=1} = W_1 \psi_1(a, o^-, o^+)$ where $\psi_1:\cA\times\cO^-\times\cO^+\rightarrow \RR^{d_1}$, $W_1\in \RR^{m_1\times d_1}$, and $\nbr{\psi_1(\cdot)}_2\le 1$.

(ii) $\EEob\sbr{\phi_1(Y, A, O^-, O^+)\given a, o, o^-, o^+, R_{O^+}=1}=W_2\psi_2(a, o, o^-, o^+)$ and $\EEob[\phi_2(A, O, O^-) \given a, o, \allowbreak o^-, o^+, R_{O^+}]=W_3\psi_2(a, o, o^-, o^+)$ where $\psi_2:\cA\times\cO\times\cO^-\times\cO^+\rightarrow \RR^{d_2}$, $W_2\in\RR^{m_1\times d_2}$, $W_3\in\RR^{m_2\times d_2}$, and $\nbr{\psi_2(\cdot)}_2\le 1$.

(iii) $\sum_{a'\in\cA}\phi_2(a', O, O^-)=W_4\psi_3(a, o, o^-)$ for any $a\in\cA$ and $\EEob\sbr{\phi_3(Y, A, O^-)\given a, o, o^-}=W_5\allowbreak \psi_3(a, o, o^-)$, where $\psi_3:\cA\times\cO\times\cO^-\rightarrow \RR^{d_3}$, $W_4\in\RR^{m_2\times d_3}$, $W_5\in \RR^{m_3\times d_3}$, and $\nbr{\psi_3(\cdot)}_2\le 1$.

(iv) $\EEob\sbr{\phi_3(Y, A, O^-)\given o^-}=W_6 \psi_4(o^-)$ where $\psi_4:\cO^-\rightarrow \RR^{m_4}$, $W_5\in\RR^{m_3\times m_4}$, and $\nbr{\psi_4(\cdot)}_2\le 1$.

Consider a linear operator $T:\cF(\cA, \cO, \cO^+)\rightarrow \cF(\cA, \cO^-, \cO^+)$ defined as $Tf(a, o^-, o^+)=\EEob\sbr{f(A, O, O^-)\given a, o^-, o^+, R_{o^+}=1}$.
Condition (i) of Assumption <ref> indicates that the operator $T$ is captured by the kernel $\psi_1(a, o^-, o^+)$.
The arguments for conditions (ii)-(iv) are similar.
Using condition (iv) of Assumption <ref> in conditional moment equation (<ref>), it holds for the CATE $g^{\pie, *}$  that,

\begin{align*}
g^{\pie, *}(o^-)=\EEob\sbr{\h{3}{\pie, *}(Y, A, O^-)\given o^-} = (w_3^{\pie, *} )^\top W_6 \psi_4(o^-),
\end{align*}

which implies that $g^{\pie, *}$ lies in the linear space $\cG=\{w_4\in\RR^{m_4}:\cO^-\rightarrow w_4^\top\psi_4(\cdot), \nbr{w_4}\le C_3\nbr{W_6}_F, \nbr{\psi_4(\cdot)}_2\le 1\}$.
Therefore, by letting $\vH=\cH_1\times \cH_2\times \cH_3\times \cG$ be the hypothesis space, we have the realizability error $\vareH$ equal to zero.
Combining Assumptions <ref> and <ref>, it further holds for the linear operator $\cT^\pie$ that,

\begin{align}
&\cT^\pie_1\vh(a,o^-, o^+)=(w_1-w_1^{\pie, *})^\top W_1 \psi_1(a, o^-, o^+), \nend
&\cT^\pie_2\vh(a, o, o^-, o^+)=\rbr{(w_2-w_2^{\pie, *})^\top W_3 - (w_1-w_1^{\pie, *})^\top W_2}\psi_2(a, o, o^-, o^+), \nend
&\cT^\pie_3\vh(a, o, o^-) = \rbr{(w_3-w_3^{\pie, *})^\top W_5- (w_2-w_2^{\pie, *})^\top W_4} \psi_3(a, o, o^-), \nend
&\cT^\pie_4\vh(o^-) = \rbr{(w_4-w_4^{\pie, *})^\top - (w_3-w_3^{\pie, *})^\top W_6}\psi_4(o^-).\nonumber
\end{align}

Therefore, $\cT^\pie_k\vh$ falls into the following linear function class

\begin{align*}
\Theta_k=\{\theta_k\given \theta_k(\cdot)=\beta_k^\top \psi_k(\cdot), \beta_k\in\RR^{d_k}, \nbr{\beta_k}\le D_k, \nbr{\psi_k(\cdot)}_2\le 1\}, \quad k=1, 2,3, 4,
\end{align*}

where we require $D_1>2C_1 \nbr{W_1}_F$, $D_2> 2 (C_1\nbr{W_2}_F+C_2\nbr{W_3}_F)$, $D_3> 2 (C_3\nbr{W_5}_F+C_2\nbr{W_4}_F)$, and $D_4> 2 (C_4+C_3\nbr{W_6}_F)$.
Using $\vH=\cH_1\times \cH_2\times \cH_3\times \cG$ as the hypothesis space and $\Theta=\Theta_1\times \Theta_2\times \Theta_3\times \Theta_4$ as the dual function class,  we have the following corollary for the convergence of the sub-optimality for the one-step linear POMDP by Theorem <ref>.

Suppose that Assumptions <ref> and <ref> hold. Let $e_{\cD}>(2 L_\alpha^2+5/ 4)\eta^2$ where $\eta=\sum_{k=1}^2\eta_k^2$ and $\eta_k$ bounds the critic radius for the function class $\cQ_k=\{\alpha_k^\pie(\vh, \cdot)\theta_k: \vh\in\vH, \theta_k\in\Theta_k, \pie\in\Pie\}$. Suppose that for any $o^-\in\cO^-$, $a\in\cA$ and $o^+\in\cO^+$ there exists $b_1:\cO^-\times\cA\times\cO^+\rightarrow\RR$ satisfying

\begin{align*}
\EEob\sbr{b_1(O^-, A, O^+)\given o^-, s, a, R_{O^+}=1} = \frac{\pob(s\given o^-)\tpr(o^-)}{\pob(s, o^-, a\given  R_{o^+}=1)}.
\end{align*}

The sub-optimality corresponding to $\piepessi$ for the CCB-PV is bounded with probability at least $1-2K\xi$ by

\begin{align*}
\SubOpt(\piepessi) \lesssim \sum_{k=1}^4 \nbr{b_k}_{\mu_k, 2} \cdot \rbr{ O\rbr{\sqrt{e_\cD}} +  O\rbr{\eta}},
\end{align*}

where $b_2:\cA\times\cO\times\cO^-\rightarrow \RR$, $b_3:\cO\times\cO^-\times\cA\rightarrow\RR$ and $b_4:\cO^-\rightarrow\RR$ characterize the distribution shift and are defined by

\begin{align*}
&b_2(a, o, o^-) = b_1(o^-, a, o^+)\frac{\pob(a, o, o^-\given (R_{O^-}, R_{O^+})=\ind)}{\pob(a, o, o^-\given (R_{O}, R_{O^-}, R_{O^+})=\ind)}, \\
&b_3(o, o^-, a) = \frac{\tpr(o^-)\pob(a, o\given o^-, R_{O^-}=1)}{\pob(o^-, a, o\given (R_{O}, R_{O^-})=\ind)}, \\
&b_4(o^-) = \frac{\tpr(o^-)}{\pob(o^-\given R_{O^-}=1)}.
\end{align*}

The critical radius is calculated in <ref>. The result can be summarized as $\eta=\cO(|\cA|\sqrt{\log T_2/T_2})$, where $T_2$ corresponds the total number of samples that are subject to no missingness in the observations $(O, O^-, O^+)$. Therefore, we establish the convergence of the sub-optimality for the one-step linear POMDP.

Discussion of RKHS Space.
We remark that a similar result can also be established for other function classes, e.g., the RKHS space.
Following Proposition 6.3 in [Duan et al., 2021], the critical radius for a RKHS space $\cF$ with kernel $K$ and bounded norm $\nbr{f}_\cK\le C$ is given by,

\begin{align*}
\eta=2\min_{j\in\NN} \cbr{\frac j T + C\sqrt{\frac{2}{T}\sum_{i=j+1}^\infty \lambda_i^\cF}},
\end{align*}

where $\lambda_i^\cF$ corresponds to the eigenvalues of the kernel $K$. If the eigenvalues decay exponentially with high probability, we can also obtain a fast convergence rate of order $\cO(\sqrt{1/T})$.

§ CONCLUSION

In this work, we propose a provably efficient algorithm CAP for offline confounded contextual bandit with missing observations.
The essential idea of the CAP algorithm is to (i) form an integration equation system (IES) for identification of the CATE; (ii) reformulate the IES as an unconditional moment minimax estimator and yield the confidence set from the estimator; (iii) Such an uncertainty quantification makes it valid to construct a policy taking greedy pessimistic action.
To the best of our knowledge, CAP is the first pessimism-based algorithm solving the offline confounded contextual bandit with missing observations.

§ PROOF OF THE IDENTIFICATION FOR CCB-IV AND CCB-PV

§ PROOF OF THE MAIN RESULTS

[Ai and Chen, 2003]
Ai, C. and Chen, X. (2003).
Efficient estimation of models with conditional moment restrictions
containing unknown functions.
Econometrica, 71 1795–1843.

[Antos et al., 2007]
Antos, A., Szepesvári, C. and Munos, R. (2007).
Fitted q-iteration in continuous action-space mdps.
Advances in neural information processing systems,

[Arellano and Bover, 1995]
Arellano, M. and Bover, O. (1995).
Another look at the instrumental variable estimation of
error-components models.
Journal of econometrics, 68 29–51.

[Athey and Wager, 2019]
Athey, S. and Wager, S. (2019).
Estimating treatment effects with causal forests: An application.
Observational Studies, 5 37–51.

[Auer et al., 2008]
Auer, P., Jaksch, T. and Ortner, R. (2008).
Near-optimal regret bounds for reinforcement learning.
Advances in neural information processing systems,

[Azar et al., 2017]
Azar, M. G., Osband, I. and Munos, R. (2017).
Minimax regret bounds for reinforcement learning.
In International Conference on Machine Learning. PMLR.

[Baiocchi et al., 2014]
Baiocchi, M., Cheng, J. and Small, D. S. (2014).
Instrumental variable methods for causal inference.
Statistics in medicine, 33 2297–2340.

[Bareinboim et al., 2015]
Bareinboim, E., Forney, A. and Pearl, J. (2015).
Bandits with unobserved confounders: A causal approach.
Advances in Neural Information Processing Systems,

[Bennett and Kallus, 2021]
Bennett, A. and Kallus, N. (2021).
Proximal reinforcement learning: Efficient off-policy evaluation in
partially observed markov decision processes.
arXiv preprint arXiv:2110.15332.

[Bennett et al., 2023]
Bennett, A., Kallus, N., Mao, X., Newey, W.,
Syrgkanis, V. and Uehara, M. (2023).
Minimax instrumental variable regression and $ l\_2 $ convergence
guarantees without identification or closedness.
arXiv preprint arXiv:2302.05404.

[Bennett et al., 2019]
Bennett, A., Kallus, N. and Schnabel, T. (2019).
Deep generalized method of moments for instrumental variable
Advances in neural information processing systems,

[Blundell et al., 2012]
Blundell, R., Horowitz, J. L. and Parey, M. (2012).
Measuring the price responsiveness of gasoline demand: Economic shape
restrictions and nonparametric demand estimation.
Quantitative Economics, 3 29–51.

[Borwein and Lewis, 2006]
Borwein, J. and Lewis, A. (2006).
Convex Analysis.

[Bottou et al., 2013]
Bottou, L., Peters, J., Quiñonero-Candela, J.,
Charles, D. X., Chickering, D. M., Portugaly, E.,
Ray, D., Simard, P. and Snelson, E. (2013).
Counterfactual reasoning and learning systems: The example of
computational advertising.
Journal of Machine Learning Research, 14.

[Brandfonbrener et al., 2020]
Brandfonbrener, D., Whitney, W. F., Ranganath, R. and
Bruna, J. (2020).
Bandit overfitting in offline policy learning.

[Brookhart et al., 2010]
Brookhart, M. A., Stürmer, T., Glynn, R. J.,
Rassen, J. and Schneeweiss, S. (2010).
Confounding control in healthcare database research: challenges and
potential approaches.
Medical care, 48 S114.

[Brown et al., 2020]
Brown, T., Mann, B., Ryder, N., Subbiah, M.,
Kaplan, J. D., Dhariwal, P., Neelakantan, A.,
Shyam, P., Sastry, G., Askell, A. et al. (2020).
Language models are few-shot learners.
Advances in neural information processing systems,
33 1877–1901.

[Buckman et al., 2020]
Buckman, J., Gelada, C. and Bellemare, M. G. (2020).
The importance of pessimism in fixed-dataset policy optimization.
arXiv preprint arXiv:2009.06799.

[Carrasco et al., 2007]
Carrasco, M., Florens, J.-P. and Renault, E. (2007).
Linear inverse problems in structural econometrics estimation based
on spectral decomposition and regularization.
Handbook of econometrics, 6 5633–5751.

[Chakraborty and Murphy, 2014]
Chakraborty, B. and Murphy, S. A. (2014).
Dynamic treatment regimes.
Annual review of statistics and its application, 1

[Chen et al., 2021]
Chen, J., Chen, X. and Tamer, E. (2021).
Efficient estimation in npiv models: A comparison of various neural
networks-based estimators.
arXiv preprint arXiv:2110.06763.

[Chen and Jiang, 2019]
Chen, J. and Jiang, N. (2019).
Information-theoretic considerations in batch reinforcement learning.
In International Conference on Machine Learning. PMLR.

[Chen and Zhang, 2021]
Chen, S. and Zhang, B. (2021).
Estimating and improving dynamic treatment regimes with a
time-varying instrumental variable.
arXiv preprint arXiv:2104.07822.

[Chen et al., 2011]
Chen, X., Hong, H. and Nekipelov, D. (2011).
Nonlinear models of measurement errors.
Journal of Economic Literature, 49 901–937.

[Chen and Qiu, 2016]
Chen, X. and Qiu, Y. J. J. (2016).
Methods for nonparametric and semiparametric regressions with
endogeneity: A gentle guide.
Annual Review of Economics, 8 259–290.

[Cragg and Donald, 1993]
Cragg, J. G. and Donald, S. G. (1993).
Testing identifiability and specification in instrumental variable
Econometric Theory, 9 222–240.

[Crowe et al., 2010]
Crowe, B. J., Lipkovich, I. A. and Wang, O. (2010).
Comparison of several imputation methods for missing baseline data in
propensity scores analysis of binary outcome.
Pharmaceutical statistics, 9 269–279.

[Cui et al., 2020]
Cui, Y., Pu, H., Shi, X., Miao, W. and
Tchetgen, E. T. (2020).
Semiparametric proximal causal inference.
arXiv preprint arXiv:2011.08411.

[Dai et al., 2017]
Dai, B., He, N., Pan, Y., Boots, B. and Song,
L. (2017).
Learning from conditional distributions via dual embeddings.
In Artificial Intelligence and Statistics. PMLR.

[Dikkala et al., 2020]
Dikkala, N., Lewis, G., Mackey, L. and Syrgkanis,
V. (2020).
Minimax estimation of conditional moment models.
Advances in Neural Information Processing Systems,
33 12248–12262.

[Ding and Geng, 2014]
Ding, P. and Geng, Z. (2014).
Identifiability of subgroup causal effects in randomized experiments
with nonignorable missing covariates.
Statistics in Medicine, 33 1121–1133.

[Duan et al., 2020]
Duan, Y., Jia, Z. and Wang, M. (2020).
Minimax-optimal off-policy evaluation with linear function
In International Conference on Machine Learning. PMLR.

[Duan et al., 2021]
Duan, Y., Jin, C. and Li, Z. (2021).
Risk bounds and rademacher complexity in batch reinforcement
In International Conference on Machine Learning. PMLR.

[Foster and Syrgkanis, 2019]
Foster, D. J. and Syrgkanis, V. (2019).
Orthogonal statistical learning.
arXiv preprint arXiv:1901.09036.

[Fu et al., 2020]
Fu, J., Kumar, A., Nachum, O., Tucker, G. and
Levine, S. (2020).
D4rl: Datasets for deep data-driven reinforcement learning.
arXiv preprint arXiv:2004.07219.

[Fujimoto et al., 2019]
Fujimoto, S., Meger, D. and Precup, D. (2019).
Off-policy deep reinforcement learning without exploration.
In International conference on machine learning. PMLR.

[Gottesman et al., 2019]
Gottesman, O., Johansson, F., Komorowski, M.,
Faisal, A., Sontag, D., Doshi-Velez, F. and Celi,
L. A. (2019).
Guidelines for reinforcement learning in healthcare.
Nature medicine, 25 16–18.

[Hernán and Robins, 2010]
Hernán, M. A. and Robins, J. M. (2010).
Causal inference.

[Jager et al., 2008]
Jager, K., Zoccali, C., Macleod, A. and Dekker, F.
Confounding: what it is and how to deal with it.
Kidney international, 73 256–260.

[Jin et al., 2021]
Jin, Y., Yang, Z. and Wang, Z. (2021).
Is pessimism provably efficient for offline rl?
In International Conference on Machine Learning. PMLR.

[Kato et al., 2021]
Kato, M., Kakehi, H., McAlinn, K. and Yasui, S.
Learning causal relationships from conditional moment conditions by
importance weighting.
arXiv preprint arXiv:2108.01312.

[Komorowski et al., 2018]
Komorowski, M., Celi, L. A., Badawi, O., Gordon,
A. C. and Faisal, A. A. (2018).
The artificial intelligence clinician learns optimal treatment
strategies for sepsis in intensive care.
Nature medicine, 24 1716–1720.

[Krishnamurthy et al., 2018]
Krishnamurthy, A., Wu, Z. S. and Syrgkanis, V. (2018).
Semiparametric contextual bandits.
In International Conference on Machine Learning. PMLR.

[Laroche et al., 2019]
Laroche, R., Trichelair, P. and Des Combes, R. T. (2019).
Safe policy improvement with baseline bootstrapping.
In International Conference on Machine Learning. PMLR.

[Lee and Bareinboim, 2021]
Lee, S. and Bareinboim, E. (2021).
Causal identification with matrix equations.
Advances in Neural Information Processing Systems,

[Liao et al., 2021]
Liao, L., Fu, Z., Yang, Z., Wang, Y., Kolar,
M. and Wang, Z. (2021).
Instrumental variable value iteration for causal offline
reinforcement learning.
arXiv preprint arXiv:2102.09907.

[Liao et al., 2020]
Liao, P., Qi, Z., Klasnja, P. and Murphy, S.
Batch policy learning in average reward markov decision processes.
arXiv preprint arXiv:2007.11771.

[Lipsitch et al., 2010]
Lipsitch, M., Tchetgen, E. T. and Cohen, T. (2010).
Negative controls: a tool for detecting confounding and bias in
observational studies.
Epidemiology (Cambridge, Mass.), 21 383.

[Liu et al., 2020]
Liu, Y., Swaminathan, A., Agarwal, A. and Brunskill,
E. (2020).
Provably good batch reinforcement learning without great exploration.
arXiv preprint arXiv:2007.08202.

[Miao et al., 2018]
Miao, W., Geng, Z. and Tchetgen Tchetgen, E. J.
Identifying causal effects with proxy variables of an unmeasured
Biometrika, 105 987–993.

[Miao et al., 2018]
Miao, W., Shi, X. and Tchetgen, E. T.
A confounding bridge approach for double negative control inference
on causal effects.
arXiv preprint arXiv:1808.04945.

[Mitra and Reiter, 2011]
Mitra, R. and Reiter, J. P. (2011).
Estimating propensity scores with missing covariate data using
general location mixture models.
Statistics in Medicine, 30 627–641.

[Munos and Szepesvári, 2008]
Munos, R. and Szepesvári, C. (2008).
Finite-time bounds for fitted value iteration.
Journal of Machine Learning Research, 9.

[Nair and Jiang, 2021]
Nair, Y. and Jiang, N. (2021).
A spectral approach to off-policy evaluation for pomdps.
arXiv preprint arXiv:2109.10502.

[Newey and Powell, 2003]
Newey, W. K. and Powell, J. L. (2003).
Instrumental variable estimation of nonparametric models.
Econometrica, 71 1565–1578.

[Pearl, 2009]
Pearl, J. (2009).
Cambridge university press.

[Pinto and Gupta, 2016]
Pinto, L. and Gupta, A. (2016).
Supersizing self-supervision: Learning to grasp from 50k tries and
700 robot hours.
In 2016 IEEE international conference on robotics and
automation (ICRA). IEEE.

[Prasad et al., 2017]
Prasad, N., Cheng, L.-F., Chivers, C., Draugelis,
M. and Engelhardt, B. E. (2017).
A reinforcement learning approach to weaning of mechanical
ventilation in intensive care units.
arXiv preprint arXiv:1704.06300.

[Qi et al., 2021]
Qi, Z., Miao, R. and Zhang, X. (2021).
Proximal learning for individualized treatment regimes under
unmeasured confounding.
arXiv preprint arXiv:2105.01187.

[Qu and Lipkovich, 2009]
Qu, Y. and Lipkovich, I. (2009).
Propensity score estimation with missing values using a multiple
imputation missingness pattern (mimp) approach.
Statistics in medicine, 28 1402–1414.

[Radford et al., 2019]
Radford, A., Wu, J., Child, R., Luan, D.,
Amodei, D., Sutskever, I. et al. (2019).
Language models are unsupervised multitask learners.
OpenAI blog, 1 9.

[Raghu et al., 2017]
Raghu, A., Komorowski, M., Celi, L. A., Szolovits,
P. and Ghassemi, M. (2017).
Continuous state-space models for optimal sepsis treatment: a deep
reinforcement learning approach.
In Machine Learning for Healthcare Conference. PMLR.

[Rashidinejad et al., 2021]
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J. and
Russell, S. (2021).
Bridging offline reinforcement learning and imitation learning: A
tale of pessimism.
Advances in Neural Information Processing Systems,

[Rubin, 1976]
Rubin, D. B. (1976).
Inference and missing data.
Biometrika, 63 581–592.

[Rubin, 2004]
Rubin, D. B. (2004).
Multiple imputation for nonresponse in surveys, vol. 81.
John Wiley & Sons.

[Seaman and White, 2014]
Seaman, S. and White, I. (2014).
Inverse probability weighting with missing predictors of treatment
assignment or missingness.
Communications in Statistics-Theory and Methods, 43

[Shalev-Shwartz et al., 2016]
Shalev-Shwartz, S., Shammah, S. and Shashua, A. (2016).
Safe, multi-agent, reinforcement learning for autonomous driving.
arXiv preprint arXiv:1610.03295.

[Shi et al., 2021]
Shi, C., Uehara, M. and Jiang, N. (2021).
A minimax learning approach to off-policy evaluation in partially
observable markov decision processes.
arXiv preprint arXiv:2111.06784.

[Singh, 2020]
Singh, R. (2020).
Kernel methods for unobserved confounding: Negative controls,
proxies, and instruments.
arXiv preprint arXiv:2012.10315.

[Singh et al., 2019]
Singh, R., Sahani, M. and Gretton, A. (2019).
Kernel instrumental variable regression.
Advances in Neural Information Processing Systems,

[Singh and Syrgkanis, 2022]
Singh, R. and Syrgkanis, V. (2022).
Automatic debiased machine learning for dynamic treatment effects.
arXiv preprint arXiv:2203.13887.

[Sun et al., 2020]
Sun, P., Kretzschmar, H., Dotiwalla, X., Chouard,
A., Patnaik, V., Tsui, P., Guo, J., Zhou, Y.,
Chai, Y., Caine, B. et al. (2020).
Scalability in perception for autonomous driving: Waymo open dataset.
In Proceedings of the IEEE/CVF conference on computer vision
and pattern recognition.

[Tchetgen et al., 2020]
Tchetgen, E. J. T., Ying, A., Cui, Y., Shi, X. and
Miao, W. (2020).
An introduction to proximal causal learning.
arXiv preprint arXiv:2009.10982.

[Tennenholtz et al., 2021]
Tennenholtz, G., Shalit, U., Mannor, S. and Efroni,
Y. (2021).
Bandits with partially observable confounded data.
In Uncertainty in Artificial Intelligence. PMLR.

[Uehara et al., 2021]
Uehara, M., Imaizumi, M., Jiang, N., Kallus, N.,
Sun, W. and Xie, T. (2021).
Finite sample analysis of minimax offline reinforcement learning:
Completeness, fast rates and first-order efficiency.
arXiv preprint arXiv:2102.02981.

[Uehara and Sun, 2021]
Uehara, M. and Sun, W. (2021).
Pessimistic model-based offline rl: Pac bounds and posterior sampling
under partial coverage.
arXiv e-prints arXiv–2107.

[VanderWeele et al., 2008]
VanderWeele, T. J., Hernán, M. A. and Robins, J. M.
Causal directed acyclic graphs and the direction of unmeasured
confounding bias.
Epidemiology (Cambridge, Mass.), 19 720.

[Wainwright, 2019]
Wainwright, M. J. (2019).
High-dimensional statistics: A non-asymptotic viewpoint,
vol. 48.
Cambridge University Press.

[Wong, 2021]
Wong, W. H. (2021).
An integral equation for the identification of causal effects in
nonlinear models.
arXiv preprint arXiv:2105.05299.

[Wright, 1928]
Wright, P. G. (1928).
Tariff on animal and vegetable oils.
Macmillan Company, New York.

[Xie et al., 2021]
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P. and
Agarwal, A. (2021).
Bellman-consistent pessimism for offline reinforcement learning.
Advances in neural information processing systems,

[Yan et al., 2022]
Yan, Y., Li, G., Chen, Y. and Fan, J. (2022).
The efficacy of pessimism in asynchronous q-learning.
arXiv preprint arXiv:2203.07368.

[Yang et al., 2020]
Yang, M., Nachum, O., Dai, B., Li, L. and
Schuurmans, D. (2020).
Off-policy evaluation via the regularized lagrangian.
Advances in Neural Information Processing Systems,
33 6551–6561.

[Yang et al., 2017]
Yang, S., Wang, L. and Ding, P. (2017).
Nonparametric identification of causal effects with confounders
subject to instrumental missingness.
Preprint. Available at.

[Yang et al., 2019]
Yang, S., Wang, L. and Ding, P. (2019).
Causal inference with confounders missing not at random.
Biometrika, 106 875–888.

[Yin et al., 2022]
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.05804.

[Yin and Wang, 2021]
Yin, M. and Wang, Y.-X. (2021).
Towards instance-optimal offline reinforcement learning with
Advances in neural information processing systems,

[Ying et al., 2021]
Ying, A., Miao, W., Shi, X. and Tchetgen, E. J. T.
Proximal causal inference for complex longitudinal studies.
arXiv preprint arXiv:2109.07030.

[Zanette, 2021]
Zanette, A. (2021).
Exponential lower bounds for batch reinforcement learning: Batch rl
can be exponentially harder than online rl.
In International Conference on Machine Learning. PMLR.

[Zhan et al., 2022]
Zhan, W., Huang, B., Huang, A., Jiang, N. and
Lee, J. D. (2022).
Offline reinforcement learning with realizability and single-policy
arXiv preprint arXiv:2202.04634.

[Zhang and Bareinboim, 2019]
Zhang, J. and Bareinboim, E. (2019).
Near-optimal reinforcement learning in dynamic treatment regimes.
In Advances in Neural Information Processing Systems
(H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox and R. Garnett, eds.), vol. 32. Curran Associates, Inc.

§ PROOF OF THE IDENTIFICATION FOR CCB-IV AND CCB-PV

§ PROOF OF THE MAIN RESULTS