The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
95,828 characters
Quantile-Optimal Policy Learning under Unmeasured Confounding
\maketitle
\vspace{-25pt}
\begin{abstract}
We study quantile-optimal policy learning where the goal is to find a policy whose reward distribution has the largest $\alpha$-quantile for some $\alpha \in (0, 1)$.
We focus on the offline setting whose generating process involves unobserved confounders. Such a problem suffers from three main challenges: (i) nonlinearity of the quantile objective as a functional of the reward distribution, (ii) unobserved confounding issue, and (iii) insufficient coverage of the offline dataset. To address these challenges, we propose a suite of causal-assisted policy learning methods that provably enjoy strong theoretical guarantees under mild conditions. In particular, to address (i) and (ii), using causal inference tools such as instrumental variables and negative controls, we propose to estimate the quantile objectives by solving nonlinear functional integral equations. Then we adopt a minimax estimation approach with nonparametric models to solve these integral equations, and propose to construct conservative policy estimates that address (iii). The final policy is the one that maximizes these pessimistic estimates. In addition, we propose a novel regularized policy learning method that is more amenable to computation. Finally, we prove that the policies learned by these methods are $\tilde{\cO}(n^{-1/2})$ quantile-optimal under a mild coverage assumption on the offline dataset. Here, $\tilde {\cO}(\cdot) $ omits poly-logarithmic factors. To the best of our knowledge, we propose the first sample-efficient policy learning algorithms for estimating the quantile-optimal policy when there exist unmeasured confounding.
\end{abstract}
\section{Introduction}
Offline reinforcement learning (RL) \citep{levine2020offline, prudencio2023survey} aims to learn the optimal decision-making policies from pre-collected datasets, where the learner has no control over the data collection process. This lack of control is further complicated by the fact that many real-world datasets suffer from incomplete information due to unmeasured confounders \citep{rubin1974estimating}—factors influencing both the actions and rewards, yet not observed by the learner.
These unobserved confounders naturally arise in the \emph{partially observable} setting,
where the behavior policy used to generate the actions is contingent on the state, while only noisy observations of the state are recorded in the data.
For example, in healthcare, electronic health records (EHR) may lack key details about a patient’s condition or treatment environment \citep{hernan2016using}, but decisions about treatment still need to be optimized based on the available data.
In many decision-making scenarios, rather than expected rewards, we are interested in optimizing more nuanced objectives involving quantiles of the
reward distribution.
For instance, to measure the efficacy of job training programs, it may be more meaningful to optimize for the median income increase, as the mean could be skewed by a few extreme cases.
Moreover, quantile-based objectives naturally arise when some notion of fairness is of interest \citep{yang2019fair, liu2022conformalized}.
In this paper, we tackle the problem of quantile-optimal policy learning in the offline setting where unmeasured confounders play a critical role. Our goal is to find a policy that maximizes the $\alpha$-th quantile of the reward distribution, conditioned on the context. Such a policy is learned based on a pre-collected offline dataset that involves unobserved confounders, which are hidden variables that simultaneously affect the rewards and actions stored in the data.
This problem is particularly challenging due to three core issues: (i) the quantile objective is a nonlinear functional of the reward distribution, making statistical learning and estimation more difficult; (ii) unmeasured confounders introduce bias into the learning problem, which can lead to misleading results if not properly accounted for; and (iii) the offline dataset often lacks full coverage, meaning that the distribution of the collected data might have insufficient overlap with that induced by some candidate policy, making it challenging to evaluate the performance of that policy.
To address these challenges, we propose a suite of novel, causal-assisted policy learning approaches. Our methods leverage powerful causal inference techniques, such as instrumental variables (IV) \citep{angrist1996identification, baiocchi2014instrumental} and negative controls (NC) \citep{lipsitch2010negative, tchetgen2020introduction}, to account for unmeasured confounding.
Leveraging these causal inference tools, we reduce the quantile-based learning problem to
the problem of solving {\bf nonlinear functional integral equations}, which are then solved as a minimax estimation in nonparametric nonlinear conditional moment models.
This enables us to address Challenges (i) and (ii).
Furthermore, to handle Challenge (iii), we propose to adopt the pessimism principle \citep{jin2021pessimism, xie2021bellman, rashidinejad2021bridging, buckman2020importance, lu2022pessimism}, which enables us to relax the requirement on data coverage.
We introduce two algorithms based on the pessimism idea --- a solution set constrained version and a regularized version. We note that pessimism penalizes candidate policies with large uncertainty and enables us to only focus on the policies that are covered by the dataset.
In particular, both our algorithms work as long as the offline data set has sufficient coverage over the optimal-policy induced distribution, regardless of whether the data set contains sufficient information about the suboptimal policies.
In this paper, we use quantile regret as the loss function. We establish that the proposed algorithms achieve sample-efficient $\widetilde O (n^{-1/2})$ suboptimality regret bounds, where $n$ is the sample size.
Here, $\widetilde O(\cdot)$ may include some logarithmic factors.
Compared to existing works that study offline policy learning with confounded datasets aiming to maximize expected rewards, our analysis is more complicated due to the nonlinear nature of the quantile-based objective function.
In particular, to get the suboptimality regret bounds, we leverage the local curvature of the nonlinear operator in the functional estimating equation. We examine the statistical error of the estimated quantile-based objective in terms of a local norm, defined using the first-order Taylor expansion of the nonlinear operator.
To the best of our knowledge, we establish the first provably sample-efficient algorithms for quantile-optimal policy learning under unmeasured confounding and insufficient support.
\paragraph{Our contributions.}
Our contributions are threefold.
First, leveraging causal tools such as IV and NC, we reduce the problem of quantile-optimal policy learning to a minimax estimation problem with nonlinear functional integral equations. To the best of our knowledge, we are the first to establish integral equations for the structural quantile function using NC. Second, to tackle the challenge of insufficient data coverage, we incorporate the principle of pessimism into our learning algorithm.
Specifically, we introduce two versions of pessimistic algorithms, which are both proved to be sample efficient.
Third, to analyze the pessimistic algorithms for quantile-optimal policy learning, we need to construct confidence sets for the nonlinear quantile-based minimax objective.
To this end, we establish a novel statistical analysis framework that leverages the local curvature of the nonlinear operator in the functional estimating equation. Our analysis can be extended to general nonlinear functional integral equations, which may be of independent interest.
\subsection{Related Literature}
Our work belongs to the intersection of offline decision making, quantile policy learning, causal inference with unobserved confounders, and limited support.
\paragraph{Offline decision making}
There is already a large literature on offline reinforcement learning \citep{yin2022near, uehara2021finite, jin2021pessimism, xie2021bellman, rashidinejad2021bridging} and offline contextual bandits \citep{li2012unbiased, lee2021optidice, metevier2019offline}. Within this literature, \citet{cassel2023general, zhu2020thompson, prashanth2020concentration} study nonlinear objective functions in contextual bandits without confounding bias. \citet{chen2023unified, wang2021provably} investigate causal policy learning with confounding variables, but using linear objective functions. Our work makes a new contribution to this literature by considering nonlinear objective functions with unobserved confounding and insufficient data coverage.
\paragraph{Quantile policy learning}
Quantile treatment effect has been extensively studied in Econometrics \citep{abadie2002instrumental, chernozhukov2005iv,horowitz2007nonparametric, chernozhukov2008instrumental, chen2012estimation, gagliardini2012nonparametric}. Recently, a few papers have explored quantile policy learning. \citet{wang2018learning} investigates quantile-optimal treatment regimes; \citet{linn2017interactive} proposes quantile regression to indirectly and approximately optimize the quantile of outcomes within specific classes of decision rules; \cite{fang2023fairness} incorporates the quantile of the reward as a regularization term in their objective to maximize the average reward. However, there are no published papers studying quantile policy learning in the offline setting with unobserved confounding.
\paragraph{Causal inference}
A huge body of works in causal inference has focused on addressing confounding bias through (observed) covariate adjustment \citep{rubin1974estimating, rosenbaum1983central, lee2010improving, liu2024encoding}, instrumental variables \citep{angrist1996identification, ai2003efficient, newey2003instrumental, chen2003estimation, chernozhukov2008instrumental, chen2012estimation, baiocchi2014instrumental, hartford2017deep}, and negative controls \citep{miao2018identifying, kallus2021causal}. While the covariate adjustment approach cannot address the unobserved confounding, the IV and NC methods can account for the unobserved confounding. While earlier literature on IV and NC focuses on linear objective functions within parametric settings, \citet{chen2003estimation, chen2012estimation, chen2015sieve, chen2014local} and others have studied nonparametric quantile IV, and \citet{miao2018identifying, kallus2021causal} have considered nonparametric NC with linear objectives. In Theorem \ref{thm: NC conditional moment restrictions} of this paper, we extend the frameworks of \citet{chen2012estimation} and \citet{kallus2021causal} to establish nonlinear functional integral equations of the structural quantile function using NC.
In addition, we incorporate the principle of pessimism to address the challenge of limited data coverage in offline quantile policy learning. There are some recent papers that combine pessimism with causal inference tools for confounded offline decision making under linear objective functions \citep{dong2023pasta, chen2023unified}. Our work extends that of \citet{chen2023unified} for maximizing an expected reward under pessimism to optimizing the quantile objective function under pessimism.
In summary, our paper aims at closing an important gap in the existing literature. By deriving integral equations that identify the structural quantile function using IV and NC, and by incorporating a principled pessimism step for offline policy learning with nonlinear objective functions, this work greatly expands the application capabilities of the current literature on offline policy learning.
\subsection{Notation}
We use upper-case letters to denote random variables and lower-case letters to denote the realizations of the corresponding random variables. For any set $\cB,$ we let $\Delta(\cB)$ denote the set of distributions over \(\mathcal{B}\). We let $p$ denote the density of random variables and ${\mathbb{P}}$ denote the probability of an event or probability mass function of a discrete random variable. We use the notation $:=$ to indicate a definition or assignment. We use $\overset{\cE}{\leq}$ and $\overset{\cE}{\geq}$ to represent the inequality that holds on some event $\cE$. For any $n,$ we let $\cO(n)$ denote $Cn$ for some arbitrary positive constant $C$ and $\tilde{\cO}(n)$ to denote $\cO(n\cdot\text{poly}(\log n))$.
\subsection{Roadmap}
In Section \ref{sec: offline decision making}, we define the offline decision-making problem with a quantile objective when confounding bias is present. We also present several examples motivated from real-world applications. Sections \ref{sec: algo} and \ref{sec: theoretical results} focus on the IV approach to address unobserved confounding. In Section \ref{sec: algo}, we first explain the use of IV for the identification and estimation of the causal quantity of interest. We then present two algorithms for IV-assisted quantile-optimal policy learning. In Section \ref{sec: theoretical results}, we present a thorough theoretical analysis of the regret of our algorithm. Section \ref{sec: experiment} conducts simulation experiments to illustrate the performance of the algorithm. Section \ref{sec: conclusion} concludes the paper with a short discussion. In \S\ref{sec: other applications}, we present how our algorithm can be adapted to policy learning under other nonlinear objective functions. \S\ref{sec: negative controls} extends the IV results of Sections \ref{sec: algo} and \ref{sec: theoretical results} to those using the NC approach.
\section{Offline Decision Making}\label{sec: offline decision making}
In this section, we introduce the problem of quantile-optimal policy learning within an offline contextual bandit setting, with unmeasured confounders and observed auxiliary variables (IV or NC). We first present the general framework in detail. We then introduce a few real-world motivating examples.
\subsection{Offline decision making with a quantile objective}
In the following, we formulate the problem of offline decision making with a quantile objective under a contextual bandit framework. Compared with the standard contextual bandits, our setup features the existence of unmeasured confounders and auxiliary variables.
Let \(\mathcal{A}\) represent the space of actions and \(\Delta(\mathcal{A})\) denote the set of distributions over \(\mathcal{A}\). Let \(X \in \mathcal{X}\) be the context, \(Y \in \mathbb{R}\) the reward, and \(O\) the auxiliary variables. Let \(U \in \mathcal{U}\) denote the unmeasured confounder that causally affects $A$ and $Y$ simultaneously.
The overarching learning problem is to learn a policy \(\pi: \cX\rightarrow\Delta(\cA)\) that maximizes the average structural quantile of the reward distribution based on an offline dataset, where the dataset does not include the unmeasured confounders $U$.
Specifically, the decision-making process involves two steps: first, collecting an offline dataset from a given distribution, and then learning a policy from the offline data to apply in an interventional process.
\paragraph{The offline data collection process (ODCP)}
Suppose there is a joint distribution \(p(u, x, o, a, y)\) over the random variables \((U, X, O, A, Y) \), which
specifies the joint distribution of the observed data.
We note that the joint distribution can be factorized as
\begin{align}\label{eq:odcp}
p(u, x, o, a, y) = p(u, x, o) \cdot p(a{\,|\,} u, x, o) \cdot p(y{\,|\,} u, x, o, a).
\end{align}
This factorization illustrates the generating process of the offline data. In particular, \(p (u, x, o)\) is the joint distribution of the confounder $U$, context $X$, and auxiliary variables $O$.
The term \(p (a {\,|\,} u, x, o)\) represents the behavior policy, which dictates how actions are selected based on \( (U, X, O) \).
The reward $Y$ is generated conditioning on \( (U, X, O, A) \) via \(p (y {\,|\,} u, x, o, a)\).
Let $n$ denote the number of samples.
Let \(\{u_i, x_i, o_i, a_i, y_i\}_{i=1}^{n}\) denote $n$ i.i.d. observations from the joint distribution in \eqref{eq:odcp}. As $U$ is unmeasured, the offline dataset only includes \(\{x_i, a_i, o_i, y_i\}_{i=1}^{n}\).
We note that, in the presence of unmeasured confounders, the auxiliary variables $O$ should be sufficiently informative for identifying the underlying causal structure. Thus, we need to pose additional assumptions to the joint distribution \(p(u, x, o, a, y)\). We will provide two examples of such assumptions in the subsequent subsection, where $O$ is an instrumental variable \citep{angrist1996identification} or a negative control exposure-outcome pair \citep{lipsitch2010negative}.
\paragraph{The Interventional process}
Suppose we learn a policy ${\pi} : \mathcal{X} \rightarrow \Delta(\mathcal{A})$ from the offline dataset, we then apply this policy in an interventional process to assess its performance.
In this process, we no longer observe the auxiliary variables. Moreover, the context $X$ may follow a different but known marginal distribution, denoted by $\widetilde p(x)$, than that in the ODCP.
Upon observing a new context $X \sim \widetilde p(x)$ from the environment, we select an action
$A \sim {\pi}(\cdot {\,|\,} X)$ from the learned policy, which generates a reward $Y$ from the same confounded data generating process as in the ODCP. Specifically, let $ {p_{\text{in}}^{\pi}}$ denote the joint distribution of random variables $(U, X, O, A, Y)$ in the interventional process under the policy ${\pi}$. We have the following factorization:
\begin{align}\label{eq:interventional}
{p_{\text{in}}^{\pi}}(u, x, o, a, y) = \tilde{p}(x) \cdot p(u, o {\,|\,} x) \cdot {\pi}(a{\,|\,} x)\cdot p(y{\,|\,} u, x, o, a).
\end{align}
Here $p(y{\,|\,} u, x, o, a)$ is the same as in \eqref{eq:odcp}.
Comparing with the joint distribution in the ODCP, we note that the interventional process is a surgical intervention on the ODCP, where we let the action $A$ depend only on the context $X$. Additionally, the joint distribution of $(U, X, O)$ is allowed to be different.
In the job training program example, the interventional process corresponds to the case where the government uses the learned policy to decide whether to allow a new worker to join the program based on their pre-intervention covariates.
\paragraph{Causal graphs --- IV and NC} From a causal inference perspective, ODCP and the interventional process can be viewed as two different data generating processes, with two different causal graphs. And the interventional process is a surgical intervention on the ODCP, where we remove the arrows coming into the node of $A$ except the one that comes from the context $X$. See Figures \ref{fig: IV DAG} and \ref{fig: NC DAG} for illustrations of the causal graphs of the ODCPs and interventional processes, when $O$ corresponds to an IV $Z$ or a negative control exposure-outcome pair $(E, V)$.
Informally, an IV is a random variable that affects the action $A$ but does not directly affect the reward $Y$. NC are a pair of random variables $(E, V)$,
which are called negative control exposure (NCE) and negative control outcome (NCO) respectively.
Intuitively, $E$ is an random variable that does not causally affect the reward $Y$, and $V$ is a random variable causally unaffected by either the action $A$ or the exposure $E$. We will focus on these causal assumptions in the rest of the paper. To be consistent with the notion in causal inference literature, in the sequel, we replace $O$ with $Z$ when it represents the IV \citep{angrist1996identification}, and by $(E, V)$ when it represents the negative control exposure-outcome pair \citep{lipsitch2010negative}.
\begin{figure}[h]
\centering
\begin{subfigure}[b]{0.4\linewidth}
\centering
\begin{tikzpicture}
\node[hiddenstate] (U) {$U$};
\node[state] (X) [below=of U] {$X$};
\node[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] {$A$};
\node[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] {$Y$};
\path[dashed] (U) edge (X);
\path[normal] (U) edge (A);
\path[normal] (X) edge (A);
\path[normal] (A) edge (Y);
\path[normal] (U) edge (Y);
\path[normal] (X) edge (Y);
\node[state] (Z) [left=of A] {$Z$};
\path[normal] (Z) edge (A);
\end{tikzpicture}
\caption{DAG of the ODCP for the IV. Note that $Z \indep Y {\,|\,} (X, A, U ).$}\label{fig: IV ODCP DAG}
\end{subfigure}\qquad
\begin{subfigure}[b]{0.4\linewidth}
\centering
\begin{tikzpicture}
\node[hiddenstate] (U) {$U$};
\node[state] (X) [below=of U] {$X$};
\node[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] {$A$};
\node[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] {$Y$};
\path[dashed] (U) edge (X);
\path[normal] (X) edge (A);
\path[normal] (A) edge (Y);
\path[normal] (U) edge (Y);
\path[normal] (X) edge (Y);
\end{tikzpicture}
\caption{DAG of the interventional process for the IV.}\label{fig: IV interventional DAG}
\end{subfigure}\qquad
\caption{(a) A DAG illustrating the causal relationship between random variables during ODCP when the IV is observed. The dashed edge implies that the causal relationship may be absent. The grey node indicates that $U$ is unmeasured. Here $Z$ is the auxiliary variables. Note that for $Z$ being a valid IV, $Z$ and $Y$ should be independent conditioning on $(X, A, U)$. (b) A DAG encoding the causal relationship between random variables in the interventional process. All arrows coming into the node $A$ have been removed other than the one from the node $X.$}\label{fig: IV DAG}
\end{figure}
\begin{figure}[h]
\centering
\begin{subfigure}[b]{0.4\linewidth}
\begin{tikzpicture}
\node[hiddenstate] (U) {$U$};
\node[state] (X) [below=of U] {$X$};
\node[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] {$A$};
\node[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] {$Y$};
\path[normal] (X) edge (A);
\path[normal] (A) edge (Y);
\path[normal] (U) edge (Y);
\path[normal] (U) edge (A);
\path[normal] (X) edge (Y);
\path[dashed] (U) edge (X);
\node[state] (E) [above=of A] {$E$};
\node[state] (V) [above=of Y] {$V$};
\path[normal] (U) edge (E);
\path[normal] (U) edge (V);
\path[dashed] (X) edge (V);
\path[dashed] (X) edge (E);
\path[dashed] (E) edge (A);
\path[dashed] (V) edge (Y);
\end{tikzpicture}
\caption{A DAG of the ODCP for the NC. Note that we have $V \indep A {\,|\,} (U, X)$ and $E \indep (Y, V) {\,|\,} (A, X, U).$}\label{fig: NC ODCP DAG}
\end{subfigure}\qquad
\begin{subfigure}[b]{0.23\linewidth}
\centering
\begin{tikzpicture}
\node[hiddenstate] (U) {$U$};
\node[state] (X) [below=of U] {$X$};
\node[state] (A) [left=of X, xshift=.27cm, yshift=-1cm] {$A$};
\node[state] (Y) [right=of X, xshift=-.27cm, yshift=-1cm] {$Y$};
\path[normal] (X) edge (A);
\path[normal] (A) edge (Y);
\path[normal] (U) edge (Y);
\path[normal] (X) edge (Y);
\path[dashed] (U) edge (X);
\node[hiddenstate] (E) [above=of A] {$E$};
\node[hiddenstate] (V) [above=of Y] {$V$};
\path[normal] (U) edge (E);
\path[normal] (U) edge (V);
\path[dashed] (X) edge (V);
\path[dashed] (X) edge (E);
\path[dashed] (V) edge (Y);
\end{tikzpicture}
\caption{A DAG of the interventional process for the NC.}\label{fig: NC interventional DAG}
\end{subfigure}\qquad
\caption{(a) A DAG illustrating the causal relationship between random variables of the ODCP when the NCE and the NCO are observed. The dashed edge implies that the causal relationship may be absent. (b) A DAG encoding the causal relationship between random variables in the interventional process. All arrows coming into the node $A$ have been removed other than the one from the node $X.$ Note in addition to $U,$ $E$ and $V$ are also not observed, indicated by the grey nodes.}\label{fig: NC DAG}
\end{figure}
\paragraph{Quantile objective and regret}
In the sequel, we denote the expectation over the distribution of random variables in ODCP as $\EE.$
For any fixed policy ${\pi},$ we denote the expectation over the distribution of random variables in the interventional process as $\EE_{{p_{\text{in}}^{\pi}}}.$ We aim to maximize the average structural quantile of the reward distribution. Let $\alpha \in (0,1)$ be a fixed scalar. Formally, given $X=x,$ for any action $a,$ we let $h^{*}_{\alpha}(a, x)$ denote the $\alpha$-quantile of the potential outcome $Y(a)$, which is called the structural quantile function \citep{chernozhukov2008instrumental}. In the language of do-calculus \citep{pearl1995causal}, we have
\begin{align}\label{eq:quantile_obj}
{\mathbb{P}}[Y \leq h^{*}_{\alpha}(A, X){\,|\,} X=x, \text{do}(A=a)]=\alpha
\end{align} under the interventional process ${p_{\text{in}}^{\pi}}$.
We assume that the potential outcome $Y(a)$ given $X$ is continuous; therefore, $h^{*}_{\alpha}(A, X)$ is uniquely defined. Thus, mathematically, our goal is to learn a policy $\pi: \cX\rightarrow\Delta(\cA)$ that maximizes the average structural quantile function:
\begin{align}\label{def: v}
v^{\pi}_{\alpha} := \EE_{{p_{\text{in}}^{\pi}}}\sbr{h^{*}_{\alpha}(A, X)},
\end{align}
where $X \sim \tilde p(x)$ and $A \sim {\pi}(\cdot {\,|\,} X).$
Let ${\pi^*}$ denote the optimal policy that maximizes the average structural quantile function. To measure the performance of a given policy ${\pi}$, we define the regret of $\pi$ as
\begin{align}\label{def: SubOpt}
\text{Regret}({\pi}) = v^{\pi^*}_{\alpha} - v^{\pi}_{\alpha}.
\end{align}
The regret is always nonnegative and characterizes the suboptimality of the policy $\pi$.
Additionally, we would like to highlight that our objective $v^{\pi}_{\alpha}$ is a nonlinear functional of the distribution of $Y$, which poses significant challenges to the theoretical analysis.
\subsection{Motivating Examples}
In many real-world applications, the objective often shifts from maximizing the average outcome to optimizing a specific quantile of the outcome distribution. This shift is particularly relevant when the focus is on distributional fairness or minimizing financial risk. Our framework is designed to address these challenges by enabling quantile optimization, which offers a more equitable approach compared to traditional average-based methods.
\paragraph{Labor market economics} Consider the previously mentioned example of job training programs designed to improve the distribution of workers' incomes \citep{abadie2002instrumental, chernozhukov2008instrumental}. In this context, the auxiliary variable $Z_i$ serves as an IV, which could be whether the worker was invited to participate in the program---this affects their likelihood of participation but does not directly impact their wage. Governments often aim to ensure that the majority of workers experience income gains.
Since the average utility can be heavily influenced by a few high-income workers, the focus shifts to optimizing specific quantiles of the utility distribution, such as the median or lower quantiles. This approach helps to ensure that the program benefits a broader range of workers, particularly those at the lower end of the income distribution.
\paragraph{Financial portfolio optimization}
Consider the design of models for optimizing financial portfolios, where the goal is to enhance portfolio gains. In this setting, let \(Y_i\) represent the \emph{gain} (or return) generated by the \(i\)-th portfolio over a specific period. The context \(X_i\) includes pre-investment characteristics such as market conditions, existing portfolio allocations, and investor risk tolerance. The action \(A_i\) denotes the portfolio strategy implemented, for instance, the allocation weights across different asset classes or the choice of specific financial instruments. An IV \(Z_i\) might be a factor that influences the chosen strategy \(A_i\) but is assumed not to affect the portfolio's gains \(Y_i\) directly, except through the strategy itself; examples could include changes in brokerage fee structures or certain types of financial advice that nudge strategy selection without containing direct information about future returns.
Financial institutions often aim for robust performance beyond simply maximizing expected gains. The distribution of portfolio gains can be heavily skewed, particularly by infrequent but large positive or negative events, making the mean gain an unreliable measure of typical performance or risk-adjusted return. Therefore, decision-makers may focus on optimizing specific quantiles of the gain distribution. For instance, they might aim to maximize a lower quantile (e.g., the 5th or 10th percentile gain) to ensure a degree of capital preservation or a minimum performance level, effectively managing downside risk. Alternatively, they might maximize the median gain for a robust measure of central tendency, or a higher quantile (e.g., the 75th percentile) to target ambitious but achievable upside potential.
A key challenge is the potential presence of unmeasured confounders \(U_i\) that could affect both the chosen portfolio strategy \(A_i\) and the realized gain \(Y_i\). Examples include evolving investor sentiment or private information, which may simultaneously influence asset allocation decisions and market performance, or unobserved market liquidity shocks that drive both strategic adjustments and gain outcomes. Furthermore, adapting concepts like spectral risk measures \citep{dowd2006after} to spectral utility measures, which integrate gains over various quantiles using preference-based weighting functions, is also relevant. In Example \ref{ex: quantile-based risk measures}, we demonstrate how our method can be adapted to minimize this measure.
\paragraph{Public health policy} Consider the scenario of reducing extreme hospital readmission times for patients post-surgery. Here, \(Y_i\) represents the post-surgery readmission time for the \(i\)-th patient, where lower values are better. \(A_i\) represents the type of post-surgery care provided, such as intensive monitoring versus a routine discharge process. \(X_i\) is a set of pre-surgery covariates of the patient (e.g., age, comorbidities).
To handle unmeasured confounders \(U_i\) (e.g., unrecorded severity of the patient's underlying condition that affects both the choice of post-surgery care and readmission risk), NC might be used. For example,
\begin{itemize}
\item The Negative Control Exposure (NCE) \(E_i\) could be the primary language spoken by the patient's initial care team. It influences communication and thus the nuanced details of care \(A_i\), but is not believed to directly affect the biological process of readmission \(Y_i\), conditional on \(A_i, X_i, U_i\).
\item The Negative Control Outcome (NCO) \(V_i\) could be a measure of patient satisfaction with hospital administrative processes during admission for the surgery. It is affected by general hospital quality \(U_i\), which also influences readmission time \(Y_i\), but is not affected by the specific post-surgery care \(A_i\) or the NCE \(E_i\).
\end{itemize}
In this context, the goal of the health system is often not just to reduce the average readmission time but to specifically mitigate the risk of very long readmission times (extreme cases), as these often indicate severe adverse events or poor post-surgical outcomes. Thus, the focus is on policy learning that optimizes an upper quantile of the readmission time distribution (e.g., minimizing the 90th or 95th percentile of readmission times).
\section{Causal-Assisted Pessimistic Policy Learning Algorithms}\label{sec: algo}
The offline quantile policy learning problem introduced in Section \ref{sec: offline decision making} involves three challenges: (i) the inherent nonlinearity of the quantile objective as a functional of the reward distribution; (ii) the presence of unmeasured confounders that bias naive estimation; and (iii) insufficient coverage in the offline dataset.
To surmount these obstacles, we develop a suite of algorithms founded on causal inference principles and the pessimism paradigm.
Specifically, to address challenges (i) and (ii), we leverage causal inference tools such as instrumental variables (IV) and negative controls (NC) to identify the structural quantile function nonparametrically, which can be solved using a minimax estimation approach to \emph{nonlinear functional integral equations}. This tackles the complication stemming from the nonlinear quantile objective with confounders. Furthermore, to handle challenge (iii), we incorporate the \emph{principle of pessimism}, which leads to the construction of conservative policy estimates. This enables us to focus on policies whose performance can be reliably evaluated with the available offline data.
For clarity, we will first detail these methodologies in the context of IV. The framework for NC, which shares a similar conceptual basis, will be discussed in \S\ref{sec: negative controls}.
\subsection{Causal Identification via Instrumental Variables}\label{sec: model}
Optimizing the average structural quantile function \( \EE_{{p_{\text{in}}^{\pi}}}\sbr{h^{*}_{\alpha}(A, X)} \) requires an initial, reliable estimate of the structural quantile function \(h^{*}_{\alpha}(A, X)\) itself.
Recall that $h^{*}_{\alpha}(A, X)$ is defined in \eqref{eq:quantile_obj}.
A naive quantile regression of \(Y\) on \(A\) and \(X\) is inadequate due to endogeneity introduced by unmeasured confounders \(U\) \citep{chernozhukov2008instrumental}, which leads to a confounding bias.
To address the confounding bias, we propose to use the IV $Z$ to identify \(h^{*}_{\alpha}(A, X)\).
A standard nonparametric IV model requires the IV $Z$ to satisfy three conditions: (i) relevance: the distribution of the action is not constant in the IV, (ii) exclusion restriction: the IV affect the reward only through action, and (iii) unconfounded instrument: the IV are conditionally independent of the error term \citep{newey2003instrumental,hartford2017deep}. The general NPQIV model, however, necessitates a more stringent set of assumptions \citep{chen2014local}. Following the treatment of Section 6 in \cite{chen2012estimation}, we employ a simplified version of the NPQIV model incorporating the additive error assumption and conditional moment restriction:
\begin{assumption}[Model Assumption for Quantile IV]\label{asp: model}
We assume that the following conditions hold for the IV model in the ODCP:
\begin{align} \label{eq:model_assumption}
Y=h^{*}_{\alpha}(A, X)+\epsilon \qquad \text{ and }\qquad {\mathbb{P}}(\epsilon \le 0 {\,|\,} X, Z)=\alpha.
\end{align}
Here, \(\epsilon\) is the structural error, dependent on \(U\), and its \(\alpha\)-quantile is zero conditional on \(X\) and \(Z\), but not necessarily conditional on \(X\) and \(A\).
\end{assumption}
By \citet{chen2014local}, with some regularity conditions, Assumption \ref{asp: model} holds by the underlying causal structure of the ODCP in the IV case, as depicted in Figure \ref{fig: IV DAG}-(a). In contrast to a standard regression model where the mean of the error term is assumed to be zero, we define $\epsilon$ as a structural error that adheres to a distinct conditional distribution assumption and is responsible for the confounding effect induced by the unmeasured confounders $U$.
Consequently, $\epsilon$ is not independent of $(A, X)$ and the condition ${\mathbb{P}}(\epsilon \le 0 {\,|\,} X, A) = \alpha$ does not hold. This subtlety renders the conventional quantile regression of $Y$ on $A$ and $X$ erroneous. Fortunately, the existence of the IV allows us to write Assumption \ref{asp: model} as
\begin{align*}
\EE \sbr{\ind \{Y \leq h^{*}_{\alpha} (A, X)\}{\,|\,} X, Z}=\alpha.
\end{align*}
If we write $\ind \{Y \leq h^{*}_{\alpha}(A, X)\} - \alpha$ as $W(D; h^{*}_{\alpha})$ where $D=(Y, X, A),$ we would then establish the relationship: $\EE \sbr{W(D; h^{*}_{\alpha}){\,|\,} X, Z}=0.$
That is, $h^{*}_{\alpha}$ is the solution to the following conditional moment restriction:
\begin{align}\label{def: conditional moment equation}
\EE \sbr{W(D; h){\,|\,} X, Z}=0
\end{align} with respect to $h$.
If $h^{*}_{\alpha}$ further is the unique solution to \eqref{def: conditional moment equation}, we can estimate it by solving the conditional moment restriction in \eqref{def: conditional moment equation} based on the offline data.
We note that $W(D, h)$ is a nonlinear function of $h$ and the conditional moment restriction in \eqref{def: conditional moment equation} is a nonlinear functional integral equation.
For any function $h$, we define a nonlinear operator ${\mathcal{T}}^{\textrm{IV}}$ that maps from a function of $(A, X)$ to a function of $(X, Z)$ as follows:
\begin{align*}
({\mathcal{T}}^{\textrm{IV}} h )(x,z) :=\EE\sbr{W(D; h){\,|\,} (X, Z)=(x,z)}.
\end{align*}
Then we have ${\mathcal{T}}^{\textrm{IV}} h^{*}_{\alpha} = 0$, i.e., a zero function, almost surely.
The equation of the form $\cT^{\textrm{IV}} h =0$ is referred to as conditional moment restriction in econometrics \citep{chamberlain1992efficiency, ai2003efficient, newey2003instrumental, chen2009nonlinear}.
Under the identifiability and realizability assumption (i.e., Assumption \ref{asp: identifiability and realizability}) introduced later, this equation identifies the structural quantile function $h^{*}_{\alpha}$.
As we will show in Theorem \ref{thm: NC conditional moment restrictions}, we can also use NC to identify $h^{*}_{\alpha}$ under a similar set of assumptions, where we introduce a similar nonlinear operator $\cT^{\textrm{NC}}$.
Consequently, estimating $h^{*}_{\alpha}$ reduces to solving the conditional moment restrictions $\cT^{\text{IV}} h = 0$ or $\cT^{\text{NC}} h = 0$. The only distinction between IV and NC is that $\cT^{\text{NC}}$ requires solving two conditional moment restrictions simultaneously, while $\cT^{\text{IV}}$ involves solving one. This difference is minimal, allowing us to use a similar approach for both cases. In fact, our methodology applies to any case where $h^{*}_{\alpha}$ can be identified by solving a conditional moment restriction of the form $\cT h = 0$ for some nonlinear operator $\cT$.
In the sequel, to highlight such generality, we use $\cT$ to denote $\cT^{\textrm{IV}}$ for the IV case.
\subsection{Minimax Estimation}
The conditional moment restriction in \eqref{def: conditional moment equation} is essentially a nonparametric inverse problem for $h$. It is impossible to find a closed-form solution. Various methods have been proposed to estimate the structural quantile function based on the conditional moment restriction. We adopt a minimax estimation strategy, inspired by \citet{dikkala2020minimax}, to estimate \(h^{*}_{\alpha}(A,X)\). Our approach transforms the moment restrictions into an unconditional loss function via Fenchel duality and estimates $h^{*}_{\alpha}$ by minimizing the loss function.
We first define a conditional residual mean squared error (RMSE) with respect to $h$ as
\begin{align}\label{def: RMSE}
\nbr{{\mathcal{T}}h}^2_{2}:= \EE\sbr{\rbr{\EE \sbr{W(D; h){\,|\,} X, Z}}^2}.
\end{align}
Note that for any function $h$ we have
\begin{align*}
\nbr{{\mathcal{T}}h}^2_{2} \geq 0, \text{~~ and~~} \nbr{{\mathcal{T}}h}^2_{2}=0 \text{ if and only if } \EE \sbr{W(D; h){\,|\,} X, Z}=0.
\end{align*}
Therefore, we can construct an estimator $h\in\cH$ of $h^{*}_{\alpha}$ by minimizing \eqref{def: RMSE} in a suitable hypothesis function space $\cH$. However, $\eqref{def: RMSE}$ is a squared conditional expectation. Estimating it using the squared empirical expectation introduces variance terms, leading to a bias. To address this, we first utilize the Fenchel duality of the function $x^2/2$ and reformulate $1/2 \cdot \nbr{{\mathcal{T}}h}^2_{2}$ as
\begin{align}\label{def: loss function}
\frac{1}{2}\nbr{{\mathcal{T}}h}^2_{2} &= \EE\sbr{\sup_{\theta \in \Theta}{\mathcal{T}}h(X, Z) \cdot \theta(X, Z)- \frac{1}{2} \cdot \abr{\theta (X,Z)}^2 }\nend
&= \sup_{\theta \in \Theta} \cbr{\EE\sbr{W(D; h) \cdot \theta(X, Z) - \frac{1}{2} \cdot \abr{\theta (X,Z)}^2 } }.
\end{align}
Here $\Theta$ is a function class over $\cX \times \cZ$ that contains the function ${\mathcal{T}}h$, and the last equality holds by the interchangeability principle \citep{dai2017learning}. Therefore, we replace the problem of minimizing \eqref{def: RMSE} by minimizing \eqref{def: loss function}.
Note that the expectation in \eqref{def: loss function} is taken with respect to the joint distribution of $(Y, A, X, Z)$ and can be unbiasedly estimated from data.
Let $\cL_{n}(h)$ denote the empirical version of \eqref{def: loss function}, i.e.,
\begin{align}\label{def: empirical loss function}
\cL_{n}(h)&:=\sup_{\theta\in\Theta}\cbr{\EE_n\sbr{W(D; h) \cdot \theta(X, Z)}-\frac 1 2 \vvvert\theta\vvvert_{n, 2}^2}\nend
&= \sup_{\theta\in\Theta} \cbr{\frac{1}{n}\sum_{i=1}^{n}\sbr{W(D_i; h)\cdot \theta(X_i, Z_i)} - \frac{1}{2n}\sum_{i=1}^{n}\theta^2(X_i, Z_i)},
\end{align}
where we introduce a real-valued test function class $\Theta$ on $\cX \times \cZ$ such that ${\mathcal{T}}h$ can be well approximated by some function in $\Theta$. As $\cL_{n}(h)$ can now be computed from the offline data, we can then estimate $h^{*}_{\alpha}$ by minimizing $\cL_{n}(h)$ with respect to $h \in \mathcal{H}$.
\subsection{Two Pessimistic Algorithms for Policy Learning}\label{sec: algorithm}
Based on the loss function $\cL_{n}(h)$ defined in \eqref{def: empirical loss function}, we can construct an estimator of $h^{*}_{\alpha}$ and use it to learn the optimal policy ${\pi^*}$ in the interventional process. We introduce two versions of algorithms based on the pessimism principle.
\paragraph{Challenge of insufficient data coverage.}
A major challenge of offline decision-making is to deal with the distribution shift between the ODCP that generates the observed action and the oracle policy. To see this, given $h$ and ${\pi},$ we denote $v(h, {\pi}) :=\EE_{{p_{\text{in}}^{\pi}}}\sbr{h(A, X)}.$ Suppose we have already obtained an estimator $\hat{h}$ of $h^{*}_{\alpha}$ from the offline data, e.g., by minimizing $\cL_{n}(h)$ in \eqref{def: empirical loss function}. We can then construct a policy by greedily maximizing $v (\hat{h}, {\pi}),$ which gives $\tilde{{\pi}} := \argsup_{{\pi}}v ( \hat{h}, {\pi}).$
To understand the performance of $\tilde{{\pi}}$, we can decompose its regret as
\begin{align} \label{eq: suboptimality decomposition}
\text{Regret}(\tilde{{\pi}}) &=v^{{\pi^*}}_{\alpha}-v^{\tilde{{\pi}}}_{\alpha} \nend
&= \underbrace{v^{{\pi^*}}_{\alpha} - v ( \hat{h}, {\pi^*}) }_{\displaystyle \text{(i)}} + \underbrace{v ( \hat{h}, {\pi^*}) - v (\hat{h}, \tilde{{\pi}}) }_{\displaystyle \text{(ii)}} + \underbrace{v ( \hat{h}, \tilde{{\pi}}) - v^{\tilde{{\pi}}}_{\alpha}}_{\displaystyle \text{(iii)}}.
\end{align}
Term (i) only depends on the oracle policy ${\pi^*}$ and the estimator $\hat{h}$. It captures the distribution shift between the interventional process and the ODCP in terms of $X$. When such a distribution shift is mild and $\hat{h}$ is a good estimator of $h^{*}_{\alpha}$, this term is small.
Term (ii) is upper bounded by zero by the optimality of $\tilde{{\pi}}$.
Term (iii) presents a unique subtlety: $\tilde{{\pi}}$ and $\hat{h}$ are both derived from offline data, creating spurious correlation.
That is, suppose $\hat h$ has a high estimation uncertainty for some suboptimal context-action pair $(x, a)$, causing $\tilde {{\pi}}$ to choose this suboptimal action at context $x$. Term (iii) will be large. In other words, because $\tilde{{\pi}}$ is learned from data and is inherently random, to make Term (iii) small, we need to ensure that $\hat{h}$ is a good estimator of $h^{*}_{\alpha}$ for all context-action pairs. Such a requirement is often too strong, especially when some parts of the context-action space are underexplored in the offline data.
\paragraph{The Solution set algorithm.} To tackle this challenge, we learn a pessimistic policy by doing uncertainty quantification on $\cL_{n}(h)$ \citep{yu2020mopo, kumar2020conservative, kidambi2020morel, jin2021pessimism, xie2021bellman, rashidinejad2021bridging, buckman2020importance}. Specifically, we first construct a solution set ${\mathcal{S}}(e_n)$ for $h$ based on $\cL_{n}(h)$ as:
\begin{align}\label{def: CI}
{\mathcal{S}}(e_n) := \cbr{h\in\cH: \cL_{n}(h) \le \inf_{h\in\cH}\cL_{n}(h) + e_n},
\end{align}
where $e_n$ is a small positive threshold we will determine later. We will show in Theorem \ref{thm: uncertainty quantification} (i) that, with high probability, $h^{*}_{\alpha}$ lies in ${\mathcal{S}}(e_n)$ by choosing $e_n$ properly.
Then, based on $ {\mathcal{S}}(e_n)$, we select the policy that optimizes the pessimistic average reward function:
\begin{align}\label{eq: pessimistic estimator}
{\hat{\pi}} := \arg\sup_{{\pi}} \inf_{h\in{\mathcal{S}}(e_n)} v(h, {\pi}).
\end{align}
Here \eqref{eq: pessimistic estimator} yields a pessimistic solution because
$ \inf_{h\in{\mathcal{S}}(e_n)} v(h, {\pi}) \leq v(h^{*}_{\alpha}, {\pi}) = v_{\alpha}^{\pi}$ for any ${\pi}$ and $h\in{\mathcal{S}}(e_n)$,
when $h^{*}_{\alpha}\in{\mathcal{S}}(e_n)$, which we will later show holds with high probability.
In other words, ${\hat{\pi}}$ is the policy that maximizes a pessimistic estimate of the objective function.
We state the details of this algorithm in Algorithm \ref{alg: meta}. To summarize, our algorithm consists of three steps.
First, we reduce the problem of estimating $h^{*}_{\alpha}$ to the problem of conditional moment restriction in \eqref{def: conditional moment equation}, which is solved by minimizing the loss function $\cL_{n}(h)$ in \eqref{def: loss function}.
Second, we construct a solution set \eqref{def: CI} based on the sublevel sets of the loss function in \eqref{def: empirical loss function}.
Finally, we construct a policy ${\hat{\pi}}$ from the solution set \eqref{def: CI} by solving the optimization problem in \eqref{eq: pessimistic estimator}.
\begin{algorithm}
\caption{Pessimistic Policy Learning Algorithm with Solution Sets}
\small
\begin{algorithmic}\label{alg: meta}
\REQUIRE Offline dataset $\cbr{a_i, x_i, z_i, y_i}_{i=1}^{n}$, hypothesis space $\cH$, test function space $\Theta$ and threshold $e_n$.
\STATE (i) Construct solution set ${\mathcal{S}}(e_n)$ as the sublevel set of $\cH$ with respect to metric $\cL_n(\cdot)$ and threshold $e_n$.
\STATE (ii) ${\hat{\pi}} :=\arg\sup_{{\pi}}\inf_{h\in {\mathcal{S}}(e_n)} v(h, {\pi})$.
\ENSURE ${\hat{\pi}}$.
\end{algorithmic}
\end{algorithm}
\paragraph{Benefit of pessimism.} To see the benefit of the pessimism principle, recall the regret decomposition in \eqref{eq: suboptimality decomposition} for $ {\hat{\pi}}$ constructed in \eqref{eq: pessimistic estimator}.
We let $\hat{h} := \arg\inf_{h\in{\mathcal{S}}(e_n)} v(h, {\hat{\pi}})$.
Then, by \eqref{eq: suboptimality decomposition}, we have
$$
v ( \hat{h}, {\pi^*}) - v ( \hat{h}, {\hat{\pi}} ) \leq 0 , \qquad v ( \hat{h}, {\hat{\pi}}) - v^{ {\hat{\pi}}}_{\alpha} = v ( \hat{h}, {\hat{\pi}}) - v ( h^{*}_{\alpha}, {\hat{\pi}}) \leq 0.
$$
Here, the first inequality is due to the optimality of ${\hat{\pi}}$ in \eqref{eq: pessimistic estimator}, and the second inequality is due to the fact that $h^{*}_{\alpha}\in{\mathcal{S}}(e_n)$ by our choice of $e_n$ (see Theorem \ref{thm: uncertainty quantification} (i)).
As a result, we have
\begin{align}
\label{eq:pess_upperbound}
\text{Regret}({\hat{\pi}}) \leq v^{{\pi^*}}_{\alpha} - v ( \hat{h}, {\pi^*}) = v\rbr{h^{*}_{\alpha}, {\pi^*}} - v ( \hat{h}, {\pi^*}) .
\end{align}
Therefore, we reduce the regret of the pessimistic policy ${\hat{\pi}}$ to a term that essentially measures the error of the estimator $\hat{h}$ in the interventional process.
In particular, this error is evaluated on the distribution induced by ${\pi^*}$, which is the oracle optimal policy.
In other words, as long as the offline data is sufficiently explorative to cover the support of the oracle policy, we can expect the regret of the pessimistic policy ${\hat{\pi}}$ to be small.
\paragraph{The Regularized algorithm.} As an intermediate step to learn ${\hat{\pi}},$ we need to minimize $v(h, {\pi})$ for $h$ restricted to ${\mathcal{S}}(e_n).$ This is an optimization problem with a data-dependent constraint, which is often computationally intractable in practice.
We now introduce a computationally benign version of the policy learning algorithm.
Let $\mathcal{E}_n(h)$ denote $\cL_{n}(h) - \inf_{h\in\cH}\cL_{n}(h).$ We modify the objective function in \eqref{eq: pessimistic estimator} by adding a regularization term $\lambda_n \cdot \mathcal{E}_n(h).$ The regularized version of the pessimistic policy is then defined as:
\begin{align}\label{eq:pess_reg}
{\hat{\pi}}_{R}:=\arg\sup_{{\pi}}\inf_{h\in \cH} \{v(h, {\pi}) + \lambda_n \cdot \mathcal{E}_n(h)\}.
\end{align}
This approach reformulates the data-dependent constrained optimization problem in \eqref{eq: pessimistic estimator} into its augmented Lagrangian counterpart. The idea is motivated from \cite{rashidinejad2022optimal}, which studies offline bandit and reinforcement learning without confounders. The additional regularization term $\lambda_n \cdot \mathcal{E}_n(h)$ can be viewed as the uncertainty of $h$. Thus, by adding this term, we effectively penalize the estimator $h$ based on its uncertainty.
Furthermore, when the estimator $h$ closely approximates $h^{*}_{\alpha}$, the regularization term approaches $\lambda_n \cdot \mathcal{E}_n(h^{*}_{\alpha})$, thereby becoming a small quantity. Consequently, we expect less bias when optimizing the augmented Lagrangian over ${\pi}$.
Thus, the regularization term does not induce significant bias to the optimization problem, while it can significantly penalize the uncertainty of the estimator $h$.
We summarise the regularized version of the algorithm in Algorithm \ref{alg: regularized version}.
Comparing \eqref{eq:pess_reg} with \eqref{eq: pessimistic estimator}, we see that the regularized version of the pessimistic policy ${\hat{\pi}}_{R}$ is obtained from an unconstrained optimization problem.
In practice, this is often more amenable to gradient-based optimization.
For example, \cite{xie2021bellman} uses the mirror descent method to optimize the regularized version of the pessimistic policy. We remark that while \cite{rashidinejad2022optimal} and \cite{xie2021bellman} advocate for the utilization of a regularized objective within their respective algorithms, these are explicitly tailored for the domains of offline bandit and offline reinforcement learning without addressing the issue of confounding effect. In contrast, our proposed algorithm is designed to remove the confounding bias, a pervasive challenge of causal inference under the setting of offline decision making.
\begin{algorithm}
\caption{Pessimistic Policy Learning Algorithm with Regularization}
\small
\begin{algorithmic}\label{alg: regularized version}
\REQUIRE Offline dataset $\cbr{a_i, x_i, z_i, y_i}_{i=1}^{n}$ from the ODCP, hypothesis space $\cH$, test function space $\Theta$ and regularization parameter $\lambda_n$.
\STATE ${\hat{\pi}}_{R}:=\arg\sup_{{\pi}}\inf_{h\in \cH} \{v(h, {\pi}) + \lambda_n \cdot \mathcal{E}_n(h)\}$.
\ENSURE ${\hat{\pi}}_R$.
\end{algorithmic}
\label{algo:regularized}
\end{algorithm}
\section{Theoretical Results}\label{sec: theoretical results}
In this section, we establish regret guarantees for the pessimistic policy learning algorithms established in \eqref{eq: pessimistic estimator} and \eqref{eq:pess_reg}.
The theoretical analysis for these algorithms, derived for learning the quantile-optimal policy, is nontrivial and distinct from the existing literature on learning the average-optimal policy for two main reasons. First, the standard concentration inequalities used in the existing literature do not work for $\nbr{\cTh}_{2}$ because of the nonlinearity of the operator $\cT$. Second, it is difficult to bound the regret of ${\hat{\pi}}$ or ${\hat{\pi}}_R$ in terms of $\nbr{\cTh}_{2}$.
To address the first challenge, we use bracketing number techniques from \citet{geer2000empirical, chen2003estimation}.
Addressing the second challenge requires us to link the estimation error of the estimated structural quantile function $\hat h$ to $ \| \cT\hat h\| _{2}$.
That is, we aim to link $\| \hat h - h^{*}_{\alpha} \|_{\bullet} $ to $\| \cT\hat h\| _{2}$, where $\| \cdot \|_{\bullet}$ is some norm.
To see this, consider the estimator $\hat {\pi} $ defined in \eqref{eq: pessimistic estimator}.
When the solution set $\mathcal{S}(e_n)$ contains $h^{*}_{\alpha}$ and the offline data is sufficiently regular, by the regret decomposition in \eqref{eq: suboptimality decomposition}, we can bound $\mathrm{Regret}(\hat {\pi} )$ by $\| \hat h - h^{*}_{\alpha} \|_2 $.
However, we cannot directly bound $ \| \hat h - h^{*}_{\alpha}\| _{2} $ by analyzing the loss function $\cL_{n}(h)$ in \eqref{def: empirical loss function} due to the nonlinearity of the operator $\cT$.
To bypass this issue, we perform a local expansion of $\cT\hat h$ around $h^{*}_{\alpha}$ and define a pseudo-metric $\vvvert\cdot\vvvert_{\mathrm{ps}}$ on the solution set ${\mathcal{S}}(e_n)$. This pseudo-metric acts as a bridge that connects the regret of $\hat {\pi}$ to $\| \cT\hat h \| _{2}$, which can be bounded using concentration tools.
As we show below, although we are focused on the instrumental variable setting, every theorem presented has an equivalent counterpart for negative controls, as detailed in \S\ref{app: theoretical analysis NC}. Moreover, the analysis can be extended to general settings where $h^{*}_{\alpha}$ is the solution to a nonlinear conditional moment restriction.
In the following, we first present the theoretical guarantees for the solution set algorithm, which yields the pessimistic estimator ${\hat{\pi}}$ defined in \eqref{eq: pessimistic estimator}. We will focus on the theory of the regularized algorithm in Section \ref{sec: theoretical analysis for the regularized set version algorithm}. We introduce several technical assumptions in the sequel and provide a detailed discussion of some of them—specifically, Assumptions \ref{asp: identifiability and realizability}, \ref{asp: regularity of Density}, \ref{asp: local curvature}, \ref{asp: data coverage}, and Condition \ref{con: high probability event}---in \S\ref{app: discussion assumptions}.
\subsection{Analysis of Solution Set ${\mathcal{S}} (e_n)$} \label{sec: analysis of solution set}
We first establish theoretical guarantees for the solution set ${\mathcal{S}} (e_n)$ constructed in \eqref{def: CI}. We will prove that, under proper conditions, ${\mathcal{S}} (e_n)$ contains the true structural quantile function $h^{*}_{\alpha}$ with high probability.
Moreover, for any function $h$ in ${\mathcal{S}} (e_n)$, we establish a uniform upper bound on the RMSE $\nbr{\cTh}_{2}$ defined in \eqref{def: RMSE}. To begin with, we impose a few conditions on the hypothesis and test function spaces. Note that a function class $\mathscr{F}$ is star-shaped if for every $f \in \mathscr{F}$ and $r \in [0, 1],$ we have $rf \in \mathscr{F}.$
\begin{assumption} [Identifiability and Realizability]\label{asp: identifiability and realizability}
We assume $h^{*}_{\alpha} \in \cH$ and $\EE \sbr{W(D; h^{*}_{\alpha}){\,|\,} X, Z}=0.$ Moreover, for any $h \in \cH$ with $\EE \sbr{W(D; h){\,|\,} X, Z}=0,$ we have $\nbr{h - h^{*}_{\alpha}}_{\infty}=0.$
\end{assumption}
\begin{assumption}[Compatibility of Test Function Class]\label{asp: compatibility of test function class}
We assume that $\Theta$ is sufficiently large such that,
for any $h\in\cH,$ $\inf_{\theta\in\Theta} \nbr{\theta - \cTh}_{2}=\epsilon_{\Theta}$ with $\epsilon_{\Theta}=\cO(n^{-1/2})$.
\end{assumption}
\begin{assumption}[Regularity of Function Classes]\label{asp: regularity of function classes}
We assume $\cH$ is compact with respect to the supremum norm $\nbr{\cdot}_{\infty} $ and $\Theta$ is star-shaped. We also assume the support of $h^{*}_{\alpha}(A, X)$ is bounded, i.e., $\nbr{(h^{*}_{\alpha}(A, X))}_\infty\le L_Y$. Moreover, it holds that $\sup_{h\in\cH}\nbr{h}_\infty\le L_{h}$ and $\sup_{\theta\in\Theta}\nbr{\theta}_\infty\le L_{\theta}$.
\end{assumption}
Assumption \ref{asp: identifiability and realizability} states that the conditional moment restriction identifies $h^{*}_{\alpha}$ and that the hypothesis space $\cH$ captures $h^{*}_{\alpha}.$ Moreover, $h^{*}_{\alpha}$ is the unique solution to the conditional moment restriction. This set of assumptions is typically required in the econometric literature \citep{chen2012estimation}. Assumption \ref{asp: compatibility of test function class} ensures that the test function class is rich enough to approximate $\cTh$ for all $h \in \cH.$ Assumption \ref{asp: regularity of function classes} can be easily satisfied by choosing $\cH$ and $\Theta$ to be standard uniformly bounded and closed function classes.
By assuming $\Theta$ is star-shaped, $\cL_{n}(\cdot)$ becomes a nonnegative function as $\Theta$ contains the zero function.
Due to the form of $\cL_{n}(\cdot ),$ it is natural to consider the function class
\begin{align*}
\cQ =\cbr{W(\cdot ; h)\cdot \theta(\cdot ): h\in\cH, \theta\in\Theta},
\end{align*}
which is parameterized by $(h, \theta)$.
Each element in $\cQ$ is a function of $ (Y, X, A, Z)$.
Since $\cL_{n}(h)$ is represented as the supremum of the addition of two terms, we define an event that quantifies the approximation error between each term in $\cL_{n}(h)$ and its population counterpart. This event will later be proved to have a high probability by using empirical process theory. Fix a sequence of small positive constants $\eta_n$ that decreases with $n.$ Let $\cE$ denote the event
\begin{align}\label{def:Event}
\cE \;=\;
\Bigl\{
\;\bigl|
\EE_n[q(D)] - \EE[q(D)]
\bigr|
\;\le\;
\eta_n\Bigl(\|\theta\|_{2}+\eta_n\Bigr),
\; \text{and}\;
\bigl|
\|\theta\|_{n,2}^{2} - \|\theta\|_{2}^{2}
\bigr|
\;\le\;
\tfrac12\Bigl(\|\theta\|_{2}^{2}+\eta_n^{2}\Bigr),
\;\forall\,q\in\cQ
\Bigr\}.
\end{align}
We impose a condition that ensures $\cE$ holds with high probability, which can be verified with concrete instantiations of $\cH$ and $\Theta$ in \S\ref{app: bracketing concentration}.
\begin{condition}\label{con: high probability event}
Suppose that Assumption \ref{asp: regularity of function classes} holds. For any $\xi>0,$ there exists $\eta_n > 0$ such that the event $\cE$ holds with probability at least $1-2\xi.$
\end{condition}
The set $\cE$ encapsulates two events that characterize the concentration of the function classes $\cQ$ and $\Theta$ separately. The term $\eta_n$ can be interpreted as the convergence rate of the tail bounds associated with the concentration of $\cQ$ and $\Theta$. In cases where $W(\cdot; h)$ is smooth in $h$, existing literature on the minimax estimation approach \citep{dikkala2020minimax, uehara2021finite, miao2023personalized} leverages the critical radius of the localized Rademacher complexity of the function classes as developed in \citet{wainwright2019high} to demonstrate that $\eta_n = \tilde{\cO}(n^{-1/2})$. Nevertheless, given that $W(\cdot; h)$ in our context includes an indicator function parametrized by $h$, this method is no longer applicable. To achieve a fast convergence rate, we borrow the tools from \citet{geer2000empirical}, which measure the complexity of the function class $\cQ$ and obtain the concentration bound via the bracketing number. For the detailed computation, we direct the reader to \S\ref{app: bracketing concentration}, where we establish that Condition \ref{con: high probability event} is satisfied for some $\eta_n = \tilde{\cO}(n^{-1/2})$ given that $\cH$ and $\Theta$ are suitably selected. Consequently, Assumption \ref{asp: compatibility of test function class} can be stated as $\inf_{\theta\in\Theta} \nbr{\theta - \cTh}_{2} = \cO(\eta_n)$.
The theoretical results for both the solution set and the regularized algorithms are built on the event $\cE$. So for the rest of the paper, we assume Condition \ref{con: high probability event} holds.
In the following theorem, we prove that, on event $\cE$, the solution set ${\mathcal{S}}(e_n)$ exhibits some favorable properties.
\begin{theorem}[Uncertainty Quantification]\label{thm: uncertainty quantification}
Suppose that Assumptions \ref{asp: identifiability and realizability}, \ref{asp: compatibility of test function class}, and \ref{asp: regularity of function classes} hold.
\begin{itemize}
\item[(i).] On event $\cE$, $\cL_{n}(h^{*}_{\alpha}) \le 13/4 \cdot \eta_n^2.$ Moreover, if we set $e_n> 13/4 \cdot \eta_n^2$, then $h^{*}_{\alpha}\in{\mathcal{S}}(e_n)$.
\item[(ii).] On event $\cE$, for all $h\in{\mathcal{S}}(e_n)$, we have,
\begin{align*}
\nbr{\cTh}_{2} = \cO\rbr{\sqrt{e_n}} + \cO\rbr{\eta_n}.
\end{align*}
\end{itemize}
\begin{proof}
See \S\ref{pro: uncertainty quantification} for a detailed proof.
\end{proof}
\end{theorem}
Theorem \ref{thm: uncertainty quantification} (i) states that when $e_n$ is chosen properly, the solution set ${\mathcal{S}}(e_n)$ captures $h^{*}_{\alpha}$ with high probability. This fact is indispensable for establishing pessimism, which further leads to the regret upper bound in \eqref{eq:pess_upperbound}.
Theorem \ref{thm: uncertainty quantification} (ii) characterizes the rate of conditional RMSE for all $h$ in ${\mathcal{S}}(e_n)$ uniformly.
As we will show subsequently, this result is crucial for establishing the final regret upper bound of the pessimistic algorithms.
In the following corollary, we apply Theorem \ref{thm: uncertainty quantification} (i) to the regret decomposition in \eqref{eq: suboptimality decomposition} and establish an upper bound of $\mathrm{Regret}({\hat{\pi}})$.
\begin{corollary}[Regret Decomposition] \label{cor: sub-optimality decomposition}
Recall that ${\hat{\pi}} := \argsup_{{\pi}} \inf_{h\in{\mathcal{S}}(e_n)} v(h, \pi).$ Suppose that Assumptions \ref{asp: identifiability and realizability}, \ref{asp: compatibility of test function class} and \ref{asp: regularity of function classes} hold. If $e_n>13/4 \cdot \eta_n^2,$ then on the event $\cE,$ the regret corresponding to ${\hat{\pi}}$ is bounded by
\begin{align} \label{eq:simplify_regret1}
\text{Regret}({\hat{\pi}}){\leq} v^{{\pi^*}}_{\alpha} - v ( {\hat h^{{\pi^*}}}, {\pi^*} ) = \EE_{{p_{\text{in}}^{\pi^*}}}\sbr{h^{*}_{\alpha}(A, X)-{\hat h^{{\pi^*}}}(A, X)}.
\end{align}
\begin{proof}
See \S\ref{proof: pessimism} for a detailed proof.
\end{proof}
\end{corollary}
\subsection{Local Expansion within the Solution Set}\label{sec: local expansion CI}
The upper bound in Corollary \ref{cor: sub-optimality decomposition} involves ${\hat h^{{\pi^*}}} - h^{*}_{\alpha}$, whose error cannot be directly connected to the RMSE $\nbr{\cT h}_{2}$ for some $h$.
In the following, we employ a local expansion of $\cT{\hat h^{{\pi^*}}}$ around $h^{*}_{\alpha}$ to bridge $\| {\hat h^{{\pi^*}}} - h^{*}_{\alpha}\|_{\bullet}$ for some norm $\| \cdot \|_{\bullet}$ to $\| \cT{\hat h^{{\pi^*}}}\| _{2}$.
To this end, we need to first ensure that any element in the solution set ${\mathcal{S}}(e_n)$ is a consistent estimator of $h^{*}_{\alpha}$.
Before presenting such a result, we first impose a regularity condition on the conditional density of $Y$ given $(A, X, Z)$.
\begin{assumption}[Regularity of Conditional Density]\label{asp: regularity of Density}
We assume that the conditional density of $Y$ given $(A, X, Z),$ $p_{Y{\,|\,} A, X, Z=(a, x, z)}(y)$ is continuous in $(y, a, x, z)$ and $\sup_{y}p_{Y{\,|\,} A, X, Z}(y) \leq K$ for some $K > 0$ for almost all $(A, X, Z).$
\end{assumption}
Assumption \ref{asp: regularity of Density} imposes some mild assumptions on the conditional density of $Y$ given $(A, X, Z),$ which is used to ensure that ${\mathcal{T}}$ is a continuous operator with respect to $\nbr{\cdot}_{\infty}.$ The assumption is standard in NPQIV \citep{chen2012estimation}. We now give a consistent result for any $h \in {\mathcal{S}}(e_n).$
\begin{theorem}[Consistency of functions in ${\mathcal{S}}(e_n)$]\label{thm: consistency}
Suppose that Assumptions \ref{asp: identifiability and realizability}, \ref{asp: compatibility of test function class}, \ref{asp: regularity of function classes} and \ref{asp: regularity of Density} hold. If $e_n=\cO(\eta_n^2 )$, then on the event $\cE,$ for any $h \in {\mathcal{S}}(e_n),$ we have $\nbr{h - h^{*}_{\alpha}}_{\infty} = o_{p}\rbr{1}$ and hence $\nbr{h - h^{*}_{\alpha}}_{2} = o_{p}\rbr{1}.$
\begin{proof}
See \S\ref{pro: consistency} for a detailed proof.
\end{proof}
\end{theorem}
Theorem \ref{thm: consistency} shows that if the threshold of the solution set is chosen properly, then any $h$ in ${\mathcal{S}}(e_n)$ is a consistent estimator of $h^{*}_{\alpha}.$ With consistency, one remaining step is required before advancing with local expansion: establishing the correct definition of the derivative of ${\mathcal{T}}h$ with respect to $h.$ Following \citet{ai2012semiparametric}, we introduce the notion of pathwise derivative of $\cTh$ evaluated at $h^{*}_{\alpha}$, in the direction $h-h^{*}_{\alpha}$, as follows:
\begin{align*}
\frac{d\cTh^{*}_{\alpha}}{dh}[h - h^{*}_{\alpha}] := \frac{d\EE [W(D;(1-r)h^{*}_{\alpha} + rh) {\,|\,} X, Z]}{dr}\, \Big| \,_{r=0}.
\end{align*}
We then define a pseudo-metric on ${\mathcal{S}}(e_n)$ based on the pathwise derivative:
\begin{align}
\label{eq: pseudometric}
\vvverth_1-h_2\vvvert_{\mathrm{ps}} := \sqrt{\EE \bigg[ \Big( \frac{d\cTh^{*}_{\alpha}}{dh}[h_1-h_2] \Big) ^{2} \bigg] },
\end{align}
where the term inside the expectation is defined as
\begin{align*}
\frac{d\cTh^{*}_{\alpha}}{dh}[h_1-h_2] = \frac{d\cTh^{*}_{\alpha}}{dh}[h_1-h^{*}_{\alpha}] - \frac{d\cTh^{*}_{\alpha}}{dh}[h_2-h^{*}_{\alpha}].
\end{align*}
In other words, for any $h_1$ and $h_2$, to compute the pseudo-metric $\vvverth_1-h_2\vvvert_{\mathrm{ps}}$, we first compute the pathwise derivative of $\cTh^{*}_{\alpha}$ evaluated at $h^{*}_{\alpha}$ in the direction of $h_1-h^{*}_{\alpha}$ and $h_2-h^{*}_{\alpha}$, and then take the square of the difference of the pathwise derivatives. In particular, suppose $\cT$ is a linear operator, e.g., $\cT$ can be viewed as a matrix. Then the pseudo-metric $\vvverth_1-h_2\vvvert_{\mathrm{ps}}$ reduces to a weighted $\ell_2$ norm, i.e., $\vvverth_1-h_2\vvvert_{\mathrm{ps}} ^2 = ( h_1-h_2)^\top (\cT ^\top \cT )( h_1-h_2).$
In Lemma \ref{lem: directional derivative}, we derive the closed form of the pseudo-metric for the IV case, which states that $$\vvverth-h^{*}_{\alpha}\vvvert_{\mathrm{ps}} = \sqrt{\EE[(\EE[p_{Y|{A,X,Z}}(h^{*}_{\alpha}(A, X))\cbr{h(X,A) - h^{*}_{\alpha}(A, X)}{\,|\,} X, Z])^2]}.$$
Let $\cH_{\epsilon} := \left\{ h\in\cH: \nbr{h-h^{*}_{\alpha}}_{2} \leq \epsilon\right\}\cap {\mathcal{S}}(e_n)$ be the restricted space of ${\mathcal{S}}(e_n)$ around the neighborhood of $h^{*}_{\alpha}$ where $\epsilon$ is a sufficiently small positive number such that ${\mathbb{P}}(\cE \cap \{ {\hat h^{{\pi^*}}} \in \cH_{\epsilon} \} ) \geq 1 - 3\xi.$ Such an $\epsilon$ is guaranteed to exist by Condition \ref{con: high probability event} and Theorem \ref{thm: consistency}.
We introduce the following assumption on the local curvature of $\cT$ around $h^{*}_{\alpha}$.
\begin{assumption}[Local Curvature]\label{asp: local curvature}
If we set $e_n>13/4 \cdot \eta_n^2$, then there exists a sufficiently small positive number $\epsilon$ and a finite constant $c_0>0$ such that for any $h \in \cH_{\epsilon},$ $\vvverth-h^{*}_{\alpha}\vvvert_{\mathrm{ps}} \leq c_0 \nbr{{\mathcal{T}}h}_{2}$.
\end{assumption}
Assumption \ref{asp: local curvature} characterizes the local curvature of $\cT$. In particular, note that $\cT h^{*}_{\alpha} = 0$. Thus, under (ii) we have $$\vvverth-h^{*}_{\alpha}\vvvert_{\mathrm{ps}} \leq c_0 \cdot \nbr{{\mathcal{T}}h - {\mathcal{T}} h^{*}_{\alpha}}_2,$$
which ensures that the RMSE dominates the pseudo-metric in the neighborhood of $h^{*}_{\alpha}$.
The parameter $c_0$ controls the local curvature of $\cT$ around $h^{*}_{\alpha}$. This assumption holds when the conditional moment restriction is locally linear around $h^{*}_{\alpha}.$
See the detailed discussion in \S\ref{app: discussion assumptions}.
\subsection{Regret of the Solution Set Offline Policy}\label{sec: regret SS}
Assumption \ref{asp: local curvature} allows us to do local expansion and link $\vvverth-h^{*}_{\alpha}\vvvert_{\mathrm{ps}}$ to $\nbr{{\mathcal{T}}h}_{2}.$
In the following, we establish the regret of the pessimistic estimator ${\hat{\pi}}$ in \eqref{eq: pessimistic estimator} based on the solution set ${\mathcal{S}}(e_n)$.
Before presenting the theorem, we introduce an assumption on the coverage of the offline data.
\begin{assumption}[Change of Measure]\label{asp: data coverage}
For the marginal distribution of context $\tilde{p}$ in the interventional process and the optimal interventional policy ${\pi^*}$, there exists a function $b: \cX \times \cZ \rightarrow \RR$ such that $\EE\sbr{b^2(X, Z)} < \infty$ and
\begin{align}\label{cond: b1 PV extended}
\EE\sbr{b(X, Z)p_{Y|{A,X,Z}}(h^{*}_{\alpha}(A, X)){\,|\,} A=a, X=x} = \frac{\tilde{p}(x){\pi^*}(a{\,|\,} x)}{p(x, a)}.
\end{align}
\end{assumption}
Assumption \ref{asp: data coverage} can be interpreted as a condition that requires the offline data in ODCP to cover the distribution induced by the oracle policy ${\pi^*}$. The existence of $b(x, z)$ bridges the joint distribution of $(X, A)$ under the ODCP and the one induced by ${\pi^*}.$ Recall that the upper bound of regret in Corollary \ref{cor: sub-optimality decomposition} involves evaluating the expectation under the interventional policy ${\pi^*}.$ The ability to change between measures enables us to evaluate this expectation under the distribution of ODCP.
Now we are ready to bound the regret of ${\hat{\pi}}.$
\begin{theorem}[Regret of Solution Set Algorithm]\label{thm: convergence of sub-optimality}
Suppose that structural model Assumption
\ref{asp: model} holds.
Suppose that Assumptions
\ref{asp: identifiability and realizability}, \ref{asp: compatibility of test function class}, and
\ref{asp: regularity of function classes} for function classes $\cH$ and $\Theta$ hold. Suppose also that Assumptions \ref{asp: local curvature} and \ref{asp: data coverage} hold.
If the threshold $e_n$ for the solution set satisfies $e_n> 13 /4 \cdot \eta_n^2,$ then, conditioning on the event $\cE \cap \{ {\hat h^{{\pi^*}}} \in \cH_{\epsilon} \}$, the regret of ${\hat{\pi}}$ is
\begin{align*}
\text{Regret}({\hat{\pi}}) = c_0\cdot \nbr{b}_{2}\cdot \cO\rbr{\sqrt{e_n} +\eta_n}.
\end{align*}
\begin{proof}
See \S\ref{proof: subopt} for a detailed proof.
\end{proof}
\end{theorem}
This theorem shows that the regret is bounded by
$\cO\rbr{\sqrt{e_n} +\eta_n}$
when $c_0$ and $\| b\|_2$ are regarded as constants.
If we set $e_n = \cO(\eta_n^2),$ Theorem \ref{thm: convergence of sub-optimality} implies that the regret of ${\hat{\pi}}$ is bounded by $\cO(\eta_n).$ As we will show in Theorem \ref{thm: concentration bound_linear} in \S\ref{app: bracketing concentration}, $\eta_n = \tilde{\cO}(n^{-1/2})$ when $\cH$ and $\Theta$ are chosen to be linear spaces, which corresponds to a “fast statistical rate” \citep{uehara2021finite}. This rate aligns with those reported in the existing minimax estimation literature \citep{dikkala2020minimax, li2022pessimism}. It is noteworthy that this rate is equivalent to that observed in scenarios involving linear objectives \citep{chen2023unified}, where the average reward is maximized rather than the average quantile. This indicates that there is no loss of efficiency when extending the analysis to the nonlinear case.
\subsection{Theoretical Analysis for the Regularized Algorithm}\label{sec: theoretical analysis for the regularized set version algorithm}
For the regularized algorithm, we apply a similar approach using local expansion at $h^{*}_{\alpha}$.
Specifically, for any fixed policy ${\pi}$, we define ${\hat h^{{\pi}}}_{R}$ as
\begin{align}\label{eq: hpessi reg}
{\hat h^{{\pi}}}_{R} := \arg\inf_{h\in\cH} \{v(h, {\pi}) + \lambda_n \cdot \mathcal{E}_n(h)\}.
\end{align}
By this definition, we can simplify the regret of ${\hat{\pi}}_R$ similar to \eqref{eq:simplify_regret1} as follows.
\begin{lemma}[Regret Decomposition]\label{cor: sub-optimality decomposition reg}
The regret of ${\hat{\pi}}_R$ is upper-bounded as follows:
\begin{align} \label{eq:regret_reg_bound}
\text{Regret}({\hat{\pi}}_R)
&\leq \EE_{{p_{\text{in}}^{\pi^*}}}\left[h^{*}_{\alpha}(A, X) - {\hat h^{{\pi^*}}}_R(A, X)\right]
+ \lambda_n \cdot \mathcal{E}_n(h^{*}_{\alpha}).
\end{align}
\end{lemma}
\begin{proof}
See \S\ref{proof: convergence of sub-optimality reg} for a detailed proof.
\end{proof}
Lemma \ref{cor: sub-optimality decomposition reg} states that the regret of ${\hat{\pi}}_R$ can be upper bounded by the average difference between $h^{*}_{\alpha} $ and ${\hat h^{{\pi^*}}}_R $ in the interventional process, plus a regularization term. Since we define $\mathcal{E}_n(h^{*}_{\alpha})$ as $\cL_{n}(h^{*}_{\alpha}) - \inf_{h\in\cH}\cL_{n}(h)$, this regularization term is comparatively straightforward to manage. The challenging part, $\cL_{n}(h^{*}_{\alpha})$, has already been addressed in Theorem \ref{thm: uncertainty quantification} (i).
Besides, $\inf_{h\in\cH}\cL_{n}(h)$ is the minimum value of the empirical loss function $\cL_{n}(h)$ over the hypothesis set $\cH$, which is often sufficiently small when the hypothesis set $\cH$ is rich enough. To capture this fact, we impose the following assumption on $\inf_{h\in\cH}\cL_{n}(h)$.
\begin{assumption}[Sample Criterion]\label{asp: sample criterion}
We assume that $\inf_{h\in\cH}\cL_{n}(h) = \cO(\eta_n^2).$
\end{assumption}
Assumptions similar to Assumption \ref{asp: sample criterion} are commonly encountered in the literature of M-estimation \citep{van2000asymptotic}. It holds when the empirical loss $\cL_{n}(h)$ can be minimized to a negligible level across the hypothesis set $\cH$. This is often satisfied when the optimization method employed in practice is effective.
Consequently, by appropriately selecting $\lambda_n$, the regularization term mentioned in Lemma \ref{cor: sub-optimality decomposition reg} can be effectively bounded.
It remains to bound the first term on the right-hand side of \eqref{eq:regret_reg_bound}.
We adopt a similar strategy as in the solution set algorithm. Specifically, we prove that ${\hat h^{{\pi}}}_{R}$ is consistent to $h^{*}_{\alpha}$ with any $\pi$. Consequently, we perform a local expansion of ${\hat h^{{\pi^*}}}_{R}$ around $h^{*}_{\alpha},$ allowing the regret to be linked to $\nbr{{\mathcal{T}}{\hat h^{{\pi^*}}}_{R}}_2$, which can be further bounded by analyzing the loss function $\cL_{n}$.
The following theorem establishes the consistency of ${\hat h^{{\pi}}}_{R}$ for $h^{*}_{\alpha}$ under the regularized algorithm.
\begin{theorem}[Consistency of ${\hat h^{{\pi}}}_{R}$]\label{thm: consistency of the estimator of the regularized version algorithm}
Suppose that Assumptions \ref{asp: identifiability and realizability}, \ref{asp: compatibility of test function class}, \ref{asp: regularity of function classes}, \ref{asp: regularity of Density} and \ref{asp: sample criterion} hold. For any $\epsilon_{R} > 0,$ if we set $\lambda_n \ge \eta_n^{-(1 + \epsilon_{R})},$ then on the event $\cE,$ for any ${\pi},$ we have $\|{\hat h^{\pi}}_{R} - h^{*}_{\alpha} \| _{\infty} = o_{p}\rbr{1}$ and hence $ \| {\hat h^{\pi}}_{R} - h^{*}_{\alpha} \| _{2} = o_{p}\rbr{1}.$
\begin{proof}
See \S\ref{pro: consistency of the estimator of the regularized version algorithm} for a detailed proof.
\end{proof}
\end{theorem}
Theorem \ref{thm: consistency of the estimator of the regularized version algorithm} states that on event $\cE,$ the estimated structural quantile function ${\hat h^{\pi}}_{R}$ is consistent to the ground-truth $h^{*}_{\alpha}$. Note the regularization parameter $\lambda_n$ in Theorem \ref{thm: consistency of the estimator of the regularized version algorithm} only depends on $\eta_n,$ which characterizes the magnitude of the concentration error. The quantity $\epsilon_{R}$ appears in the definition of $\lambda_n$ is crucial for the consistency result. Although consistency is theoretically guaranteed for infinitesimally small $\epsilon_{R}$, the convergence rate of ${\hat h^{{\pi^*}}}_{R}$ to $h^{*}_{\alpha}$ becomes slow when $\epsilon_{R}$ is too small. As we will see later, the choice of $\epsilon_{R}$ induces a trade-off in the regret of ${\hat{\pi}}_R$.
Given the consistency result, we are ready to perform a local expansion of ${\hat h^{{\pi^*}}}_{R}$ around $h^{*}_{\alpha}$ in a restricted space of $\cH$ around the neighborhood of $h^{*}_{\alpha}$. For a fixed $\lambda_n \ge \eta_n^{-\rbr{1 + \epsilon_{R}}},$ we fix a sufficiently small positive number $\epsilon$ such that the event $\cE \cap \cbr{{\hat h^{{\pi^*}}}_{R} \in \left\{ h\in\cH: \nbr{h-h^{*}_{\alpha}} _{2} \leq \epsilon\right\}}$ occurs with probability at least $1-3\xi.$ Such an $\epsilon$ is guaranteed to exist by Condition \ref{con: high probability event} and Theorem \ref{thm: consistency of the estimator of the regularized version algorithm}.
\begin{theorem}[Regret of the Regularized Algorithm]\label{thm: convergence of sub-optimality reg}
We assume all the assumptions made in Theorem \ref{thm: consistency of the estimator of the regularized version algorithm} hold and additionally impose Assumptions \ref{asp: local curvature} and \ref{asp: data coverage}.
Let $0 < \epsilon_{R} <1$ be any fixed number. We set the regularization parameter $\lambda_n$ to $\eta_n^{-(1 + \epsilon_{R})}$ in \eqref{eq:pess_reg}.
Then, conditioning on the event $\cE \cap \cbr{{\hat h^{{\pi^*}}}_{R} \in \left\{ h\in\cH: \nbr{h-h^{*}_{\alpha}}_{2} \leq \epsilon\right\}}$, the regret of ${\hat{\pi}}_R$ is
\begin{align*}
\text{Regret} ({\hat{\pi}}_{R}) = \cO\rbr{\eta_n^{1 - \epsilon_{R}}}.
\end{align*}
\begin{proof}
See \S\ref{proof: convergence of sub-optimality reg} for a detailed proof.
\end{proof}
\end{theorem}
Theorem \ref{thm: convergence of sub-optimality reg} implies that if we set $\lambda_n = \eta_n^{-\rbr{1 + \epsilon_{R}}},$ the regret of ${\hat{\pi}}_{R}$ is $\cO\rbr{\eta_n^{1 - \epsilon_{R}}}.$ Recall by Theorem \ref{thm: convergence of sub-optimality}, $\text{Regret}({\hat{\pi}})$ is $\cO(\eta_n)$ when $e_n$ is properly chosen. Thus, the regret of $ {\hat{\pi}}_{R}$ is larger than that of ${\hat{\pi}}$ by an infinitesimal amount $\epsilon_{R}$. A small value of $\epsilon_{R}$ slows the convergence of ${\hat h^{{\pi^*}}}_{R}$ toward $h^{*}_{\alpha}$. As a result, the constant $c_0$ in Assumption \ref{asp: local curvature} may be large, which can increase the regret. Essentially, the extra $\epsilon_{R}$ term can be viewed as the trade-off when converting an optimization problem with data-dependent constraints into a nonconstrained optimization problem in the nonlinear quantile case.
Furthermore, when selecting the function spaces $\cH$ and ${\Theta}$ as the linear function classes, we have $\eta_n = \tilde{\cO}(n^{-1/2})$ as shown in Theorem \ref{thm: concentration bound_linear} in \S\ref{app: bracketing concentration}. This leads to a regret rate of $\tilde{\cO}(n^{-1/2(1 - \epsilon_{R})})$ for the regularized algorithm, which outperforms the $\tilde{\cO}(n^{-1/3})$ rate associated with the regularized version of the pessimistic offline reinforcement learning algorithm studied in \cite{xie2021bellman}. Since $\epsilon_{R}$ can be infinitesimally small (ignoring $c_0$), our regret bound also closely matches the $\tilde{\cO}(n^{-1/2})$ regret of the augmented Lagrangian algorithm detailed in \cite{rashidinejad2022optimal}. Note that \citet{rashidinejad2022optimal} requires the knowledge of the propensity score, which is a strong assumption and is not required by our method. Furthermore, we would like to emphasize that the quantile objective considered in our work is a nonlinear functional of the reward distribution,
whereas \cite{xie2021bellman} and \cite{rashidinejad2022optimal} focus on the expected reward, which is a linear functional of the reward distribution. To the best of our knowledge, we are the first to establish the efficacy of the pessimism in the context of nonlinear quantile objectives and unobserved confounding, which is a significant extension of the existing literature on pessimistic offline reinforcement learning.
\section{Simulation Experiments} \label{sec: experiment}
In this section, we evaluate the performance of our approach via numerical simulations. We focus on a synthetic setting where the instrumental variables are available in the offline data.
We compare the pessimistic regularized policy learning algorithm, specified in \eqref{eq:pess_reg}, against a greedy benchmark that does not incorporate pessimism.
The simulation results demonstrate the benefits of pessimism, particularly in scenarios with insufficient data coverage.
\subsection{Data Generating Model}
\label{sec:simulation_data}
We consider a contextual bandit model with two-dimensional contexts, denoted by $X = (X_1, X_2)$, a binary action $A \in \{0, 1\}$, and a one-dimensional instrumental variable $Z$. The output variable $Y$ is generated according to \eqref{eq:model_assumption}, where the structural error $\epsilon$ represents an unmeasured confounder that simultaneously influences the action and the outcome.
We detail the data generation model below.
\paragraph{Context and instrument generation.}
We let $(X_1, X_2, Z)$ be drawn from a centered trivariate Gaussian distribution:
\[
\begin{bmatrix} X_1 \\ X_2 \\ Z \end{bmatrix} \sim \mathcal{N} \left( \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 & \rho & \rho \\ \rho & 1 & \rho \\ \rho & \rho & 1 \end{bmatrix} \right),
\]
where $\rho$ is a correlation coefficient. We set $\rho$ to $0.95$ in all experiments.
\paragraph{Structural error $\epsilon$.} For a given target quantile $\alpha$, we sample
the noise $\epsilon$ according to $\epsilon \sim \mathcal{N}(-\Phi^{-1}(\alpha), 1)$, where $\Phi(\cdot)$ is the cumulative distribution function (CDF) of a standard normal distribution. This construction ensures that the $\alpha$-quantile of $\epsilon$ is zero, i.e., $\mathbb{P}(\epsilon \le 0) = \alpha$.
\paragraph{Action $A$.}
Given a treatment assignment score $S$, which is introduced below, we generate a binary action $A$ from a Bernoulli distribution.
In particular, $\PP(A = 1 {\,|\,} S ) = \text{sigmoid}(S) = 1 / (1 + \exp(-S)) $, where $\text{sigmoid}(\cdot )$ is the sigmoid function.
\paragraph{\textbf{Outcome $Y$.}}
As shown in \eqref{eq:pess_reg}, we generate $Y$ according to the structural model:
\begin{align}\label{eq:model_simulation}
Y = \beta_1^* \cdot X_1 + \beta_2^* \cdot X_2 + \beta_3^* \cdot A \cdot X_1 + \beta_4^* \cdot A \cdot X_2 + \epsilon,
\end{align}
where $\beta ^* = (\beta_1^*, \beta_2^*, \beta_3^*, \beta_4^*)^\top = (1, 1, 3,2)^\top $ are the true coefficients.
Here, the term $\beta_1^* \cdot X_1 + \beta_2^* \cdot X_2 + \epsilon$ represents the baseline outcome, and $A \cdot (\beta_3^* \cdot X_1 + \beta_4^*\cdot X_2)$ is the additional effect due to action $A$.
\paragraph{Treatment assignment score $S$.}
The treatment assignment score $S$ is designed to introduce a lack of coverage in the data.
Specifically, we introduce two parameters, a structured proportion $p \in [0, 1]$ and two treatment biases $b_{+}$ and $b_{-}$.
For a fraction $p$ of the $n$ samples, we generate $S$ as follows:
\begin{align}\label{eq:assignment_bias}
S = X_1 + 0.5 \cdot X_2^2 + Z + b_{+} \cdot \ind(X_1 \ge 0) + b_{-} \cdot \ind (X_1 < 0) + \epsilon .
\end{align}
Here we set $b_{+} = 8$ and $b_{-} = -5$. Moreover, for the remaining fraction $(1 - p)$ of the samples, we generate $S$ from random noise: $S \sim \mathcal{N}(0, 1)$.
Our construction induces two layers of complexities in data coverage.
First, by having a nonzero $p$, we introduce out-of-distribution data points that are not generated from the confounded structural model.
We set $p$ as $0.7$ and $0.8$ in our experiments.
Second, by having the bias terms $b_{+}$ and $b_{-}$, we introduce a systematic bias in the treatment assignment. That is, we have more assigned actions for the region $X_1 \ge 0$ than for the region $X_1 < 0$.
\paragraph{Optimal policy $\pi^*$.}
By \eqref{eq:model_simulation}, it is straightforward to see that the quantile-optimal policy $\pi^*$ is a deterministic policy that outputs action $A = 1$ if and only if $\beta_3^* \cdot X_1 + \beta_4^* \cdot X_2 > 0$, i.e., $3 X_1 + 2 X_2 > 0$.
When this condition is not satisfied, the optimal action is $A = 0$.
\subsection{Algorithm Implementations}
We compare the pessimistic regularized policy learning algorithm (Algorithm \ref{algo:regularized}) against a greedy baseline that does not incorporate pessimism.
\paragraph{Linear hypothesis classes $\mathcal{H}$ and $\Theta$.}
We set $\mathcal{H}$ and $\Theta$ to be linear function classes with known features.
Specifically,
motivated by \eqref{eq:model_simulation}, any function $h $ in $\mathcal{H}$ can be written as
\begin{align}\label{eq:linear_hypothesis_h}
h(A, X; \beta) = \beta_1 X_1 + \beta_2 X_2 + A (\beta_3 X_1 + \beta_4 X_2),
\end{align}
where $\beta = (\beta_1, \beta_2, \beta_3, \beta_4)^\top$ is the parameter vector.
The test function space $\Theta$ is defined as a linear span of a set of polynomial basis functions involving $X_1, X_2,$ and $Z$:
$$
\bigl \{X_1, ~X_2, ~Z, ~ X_1X_2,~ X_1Z,~ X_2Z,~ X_1^2,~ X_2^2,~ Z^2, ~ X_1^2Z, ~ X_1X_2^2, ~ Z^3, ~ X_1^2X_2^2\bigr\}.
$$
\paragraph{Greedy approach.} This approach first estimates the structural quantile function $h_\alpha(A,X)$ by minimizing the empirical loss function $\mathcal{L}_n(h)$ in \eqref{def: empirical loss function}.
Note that supremum over $\theta $ in \eqref{def: empirical loss function} is a quadratic form, which can be solved exactly in closed form.
Thus, we can directly compute the gradient of $\mathcal{L}_n(h)$ with respect to the parameters $\beta$ of $h$.
We obtain an approximate minimizer $\hat h$ via direct gradient descent, with a constant stepsize $0.05$. After obtaining $\hat h$, we derive the greedy policy by solving $\max_{\pi} v(\hat{h}, \pi)$, which can be computed in closed form.
\paragraph{Pessimistic approach.} We approximately implement Algorithm \ref{algo:regularized} with $\lambda_n = \sqrt{n}$, where $n$ is the sample size. This choice of $\lambda_n$ is suggested by Theorem \ref{thm: convergence of sub-optimality reg} for linear function classes, with $\epsilon_{R}$ set to zero.
Note that \eqref{eq:pess_reg} involves a minimax optimization and that $\sup_{\pi} v(h, \pi)$ for any fixed $h \in \mathcal{H}$ can be computed in closed form.
We exchange the order of the supremum and infimum in \eqref{eq:pess_reg} and reduce the problem to solving
\begin{align}\label{eq:pess_reg_new}
\inf_{h \in \mathcal{H}} \bigl\{ V(h) + \lambda _n \cdot \mathcal{L}_n (h)\bigr\}, \qquad \text{where}~~V(h) = v\big(h, \pi(h)\big).
\end{align}
Here we let $\pi(h)$ denote the greedy policy with respect to $h$.
For example, for the function $h(\cdot; \beta)$ defined in \eqref{eq:linear_hypothesis_h}, the greedy policy $\pi(h)$ takes action one if and only if $\beta_3 X_1 + \beta_4 X_2 > 0$.
Another challenge is that $V(h)$ in \eqref{eq:pess_reg_new} is not differentiable with respect to the parameters of $h$.
Thanks to the low dimensionality of $\beta$, to solve this minimization problem, we use a randomized search method. That is, we draw $N=10^4$ random samples of $\beta$ from a Gaussian distribution centered at $\hat h$, evaluate the objective values in \eqref{eq:pess_reg_new} for each sampled $\beta$, and select the minimizer $\tilde h$.
The greedy policy corresponding to $\tilde h$ is regarded as an approximation of $\hat \pi_{R}$ in Algorithm \ref{algo:regularized}.
\subsection{Experiment Results}
We introduce the parameter of structured proportion $p$ in Section \ref{sec:simulation_data}.
We compare our pessimistic algorithm against the greedy baseline under different configurations of $(n, \alpha, p)$, where $n$ is the sample size and $\alpha$ is the target quantile.
In particular, we choose $n \in \{ 100, 150, 200, \ldots, 3000\}$, $\alpha \in \{ 0.15, 0.2, 0.25\}$, and $p \in \{ 0.7, 0.8\}$.
For each configuration, we generate $200$ independent datasets and compute the average regret of the learned policies.
We show the results for $p= 0.7$ and $p=0.8$ in Figures \ref{fig:results_prop_7} and \ref{fig:results_prop_8}, respectively.
The blue and red curves represent the average regret of the greedy and pessimistic approaches, respectively, while the shaded areas around the curves indicate one standard deviation above and below the mean. Our findings are summarized as follows.
\begin{figure}[h]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.355\textwidth, height=0.177\textheight]{images/alpha_15_prop_7.pdf} &
\includegraphics[width=0.335\textwidth, height=0.177\textheight]{images/alpha_20_prop_7.pdf} &
\includegraphics[width=0.331\textwidth, height=0.181\textheight]{images/alpha_25_prop_7.pdf} \\
(a) $(\alpha , p) = (0.15, 0.7)$ & (b) $(\alpha , p) = (0.2, 0.7)$ & (c) $(\alpha , p) = (0.25, 0.7)$ \\
\end{tabular}
\caption{Average regret of the greedy and pessimistic approaches for different sample sizes $n$ and quantile levels $\alpha$, with structured proportion $p = 0.7$. The first two plots clearly shows that pessimism outperforms the greedy approach. The third plot shows that their performances are comparable, with pessimism slightly better when $n$ is large.}
\label{fig:results_prop_7}
\end{figure}
\begin{itemize}
\item In all these figures, the width of the shaded areas is similar for both the greedy and pessimistic approaches, indicating that the variability of the regret is comparable for both methods.
\item For the quantile levels $\alpha = 0.15$ and $\alpha = 0.2$, the {\bf pessimistic approach consistently outperforms the greedy approach} when the sample size is large. This clearly demonstrates the advantage of incorporating pessimism, especially when the data coverage is insufficient.
In particular, with $(1-p)$ portion of out-of-distribution data added,
it seems to suggest that the signal from the observed data is not sufficient to estimate $h^{*}_{\alpha}$ accurately. In this case, pessimism benefits the learning process by avoiding overfitting to the observed data distribution, leading to lower regret.
\item Furthermore, it is worth noting that the reason why the greedy approach is inferior is not due to the limited sample size, but rather due to the insufficient coverage of the data generating distribution. In particular, as shown in the first two plots of Figures \ref{fig:results_prop_7} and \ref{fig:results_prop_8}, the margin between the greedy and pessimistic approaches is larger when the sample size is larger.
\item For the quantile level $\alpha = 0.25$, pessimism is slightly worse than the greedy approach. In particular, when $p = 0.7$, they are comparable when $n$ is large, as shown in Figure \ref{fig:results_prop_7}-(c). For some sample sizes, pessimism is slightly better.
For $p = 0.8$, the greedy approach outperforms the pessimistic approach, as shown in Figure \ref{fig:results_prop_8}-(c). In this case, both algorithms perform well with small regret.
This case suggests that when the data coverage is sufficient, greedy algorithm itself can achieve good performance, and the pessimistic approach does not provide significant additional benefits.
Moreover, note that the pessimistic approach is computationally more expensive, requiring random sampling in our implementation, and the optimization error can also contribute to the regret. Thus, when the data coverage is sufficient, the greedy approach can be preferred due to its simplicity and efficiency.
\item Furthermore, if we compare the performances of these algorithms across different values of $p$, we observe that both methods perform better when $p = 0.8$ than when $p = 0.7$. This is expected, as a larger structured proportion $p$ implies that the data is more representative of the underlying distribution, leading to better performance for both methods.
\end{itemize}
\begin{figure}[htbp]
\centering
\begin{tabular}{ccc}
\includegraphics[width=0.355\textwidth, height=0.179\textheight]{images/alpha_15_prop_8.pdf} &
\includegraphics[width=0.335\textwidth]{images/alpha_20_prop_8.pdf} &
\includegraphics[width=0.331\textwidth]{images/alpha_25_prop_8.pdf} \\
(a) $(\alpha , p) = (0.15, 0.8)$ & (b) $(\alpha , p) = (0.2, 0.8)$ & (c) $(\alpha , p) = (0.25, 0.8)$\\
\end{tabular}
\caption{Average regret of the greedy and pessimistic approaches for different sample sizes $n$ and quantile levels $\alpha$, with structured proportion $p = 0.8$.The first two plots clearly shows that pessimism outperforms the greedy approach. The third plot shows the greedy approach outperforms the pessimistic approach when $\alpha = 0.25$.}
\label{fig:results_prop_8}
\end{figure}
\section{Discussion}\label{sec: conclusion}
In this work, we propose a quantile-optimal policy learning algorithm where the goal is to find a policy whose reward distribution has the largest $\alpha$-th quantile for some $\alpha \in (0, 1)$. The idea is to (i) establish a variety of conditional moment restrictions for the identification of the quantile objectives of any policy with the help of instrumental variables and negative controls; (ii) adopt a minimax estimation approach with nonparametric models to solve these conditional moment restrictions, and construct conservative solutions for pessimistic policy learning. The final policy is the one that maximizes the pessimistic objective. In addition, we propose a novel regularized policy learning method that is computationally benign. We deliver a theoretical analysis to show that the proposed method is provably efficient. To the best of our knowledge, this is the first sample-efficient policy learning algorithm for estimating the quantile-optimal policy when there exists unmeasured confounding. Our work requires the observation of either instrumental variables or negative controls. However, we posit that the proposed algorithm is equally effective when the ODCP possesses different underlying causal structures, as long as the quantile treatment effect can be identified by conditional moment restrictions. We leave this investigation to future research.
\newpage
\bibliographystyle{ims}
\bibliography{reference}
\newpage