Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
95,828 characters · 21 sections · 61 citation commands
Quantile-Optimal Policy Learning under Unmeasured Confounding
Offline reinforcement learning (RL) 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 rubin1974estimating—factors influencing both the actions and rewards, yet not observed by the learner. These unobserved confounders naturally arise in the 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 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 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) angrist1996identification, baiocchi2014instrumental and negative controls (NC) 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 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.
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 yin2022near, uehara2021finite, jin2021pessimism, xie2021bellman, rashidinejad2021bridging and offline contextual bandits li2012unbiased, lee2021optidice, metevier2019offline. Within this literature, cassel2023general, zhu2020thompson, prashanth2020concentration study nonlinear objective functions in contextual bandits without confounding bias. 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 abadie2002instrumental, chernozhukov2005iv,horowitz2007nonparametric, chernozhukov2008instrumental, chen2012estimation, gagliardini2012nonparametric. Recently, a few papers have explored quantile policy learning. wang2018learning investigates quantile-optimal treatment regimes; linn2017interactive proposes quantile regression to indirectly and approximately optimize the quantile of outcomes within specific classes of decision rules; 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 rubin1974estimating, rosenbaum1983central, lee2010improving, liu2024encoding, instrumental variables angrist1996identification, ai2003efficient, newey2003instrumental, chen2003estimation, chernozhukov2008instrumental, chen2012estimation, baiocchi2014instrumental, hartford2017deep, and negative controls 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, chen2003estimation, chen2012estimation, chen2015sieve, chen2014local and others have studied nonparametric quantile IV, and miao2018identifying, kallus2021causal have considered nonparametric NC with linear objectives. In Theorem (ref) of this paper, we extend the frameworks of chen2012estimation and 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 dong2023pasta, chen2023unified. Our work extends that of 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.
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))$.
In Section (ref), 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) and (ref) focus on the IV approach to address unobserved confounding. In Section (ref), 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), we present a thorough theoretical analysis of the regret of our algorithm. Section (ref) conducts simulation experiments to illustrate the performance of the algorithm. Section (ref) concludes the paper with a short discussion. In \S(ref), we present how our algorithm can be adapted to policy learning under other nonlinear objective functions. \S(ref) extends the IV results of Sections (ref) and (ref) to those using the NC approach.
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.
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
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 (ref). 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 angrist1996identification or a negative control exposure-outcome pair 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:
Here $p(y{\,|\,} u, x, o, a)$ is the same as in (ref). 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) and (ref) 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 angrist1996identification, and by $(E, V)$ when it represents the negative control exposure-outcome pair lipsitch2010negative.
\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 chernozhukov2008instrumental. In the language of do-calculus pearl1995causal, we have
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:
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
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.
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 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 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 dowd2006after to spectral utility measures, which integrate gains over various quantiles using preference-based weighting functions, is also relevant. In Example (ref), 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,
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).
The offline quantile policy learning problem introduced in Section (ref) 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 nonlinear functional integral equations. This tackles the complication stemming from the nonlinear quantile objective with confounders. Furthermore, to handle challenge (iii), we incorporate the 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).
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 (ref). A naive quantile regression of \(Y\) on \(A\) and \(X\) is inadequate due to endogeneity introduced by unmeasured confounders \(U\) 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 newey2003instrumental,hartford2017deep. The general NPQIV model, however, necessitates a more stringent set of assumptions chen2014local. Following the treatment of Section 6 in chen2012estimation, we employ a simplified version of the NPQIV model incorporating the additive error assumption and conditional moment restriction:
By chen2014local, with some regularity conditions, Assumption (ref) holds by the underlying causal structure of the ODCP in the IV case, as depicted in Figure (ref)-(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) as
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:
with respect to $h$. If $h^{*}_{\alpha}$ further is the unique solution to (ref), we can estimate it by solving the conditional moment restriction in (ref) based on the offline data.
We note that $W(D, h)$ is a nonlinear function of $h$ and the conditional moment restriction in (ref) 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:
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 chamberlain1992efficiency, ai2003efficient, newey2003instrumental, chen2009nonlinear. Under the identifiability and realizability assumption (i.e., Assumption (ref)) introduced later, this equation identifies the structural quantile function $h^{*}_{\alpha}$.
As we will show in Theorem (ref), 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.
The conditional moment restriction in (ref) 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 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
Note that for any function $h$ we have
Therefore, we can construct an estimator $h\in\cH$ of $h^{*}_{\alpha}$ by minimizing (ref) 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
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 dai2017learning. Therefore, we replace the problem of minimizing (ref) by minimizing (ref). Note that the expectation in (ref) 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 (ref), i.e.,
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}$.
Based on the loss function $\cL_{n}(h)$ defined in (ref), 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 (ref). 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
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)$ 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:
where $e_n$ is a small positive threshold we will determine later. We will show in Theorem (ref) (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:
Here (ref) 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). 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 (ref), which is solved by minimizing the loss function $\cL_{n}(h)$ in (ref). Second, we construct a solution set (ref) based on the sublevel sets of the loss function in (ref). Finally, we construct a policy ${\hat{\pi}}$ from the solution set (ref) by solving the optimization problem in (ref).
\paragraph{Benefit of pessimism.} To see the benefit of the pessimism principle, recall the regret decomposition in (ref) for $ {\hat{\pi}}$ constructed in (ref). We let $\hat{h} := \arg\inf_{h\in{\mathcal{S}}(e_n)} v(h, {\hat{\pi}})$. Then, by (ref), 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 (ref), 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) (i)). As a result, we have
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 (ref) by adding a regularization term $\lambda_n \cdot \mathcal{E}_n(h).$ The regularized version of the pessimistic policy is then defined as:
This approach reformulates the data-dependent constrained optimization problem in (ref) into its augmented Lagrangian counterpart. The idea is motivated from 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).
Comparing (ref) with (ref), 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, xie2021bellman uses the mirror descent method to optimize the regularized version of the pessimistic policy. We remark that while rashidinejad2022optimal and 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.
In this section, we establish regret guarantees for the pessimistic policy learning algorithms established in (ref) and (ref). 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 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 (ref). When the solution set $\mathcal{S}(e_n)$ contains $h^{*}_{\alpha}$ and the offline data is sufficiently regular, by the regret decomposition in (ref), 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 (ref) 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). 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 (ref). We will focus on the theory of the regularized algorithm in Section (ref). We introduce several technical assumptions in the sequel and provide a detailed discussion of some of them—specifically, Assumptions (ref), (ref), (ref), (ref), and Condition (ref)---in \S(ref).
We first establish theoretical guarantees for the solution set ${\mathcal{S}} (e_n)$ constructed in (ref). 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 (ref). 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}.$
Assumption (ref) 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 chen2012estimation. Assumption (ref) ensures that the test function class is rich enough to approximate $\cTh$ for all $h \in \cH.$ Assumption (ref) 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
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
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).
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 dikkala2020minimax, uehara2021finite, miao2023personalized leverages the critical radius of the localized Rademacher complexity of the function classes as developed in 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 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), where we establish that Condition (ref) is satisfied for some $\eta_n = \tilde{\cO}(n^{-1/2})$ given that $\cH$ and $\Theta$ are suitably selected. Consequently, Assumption (ref) 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) holds. In the following theorem, we prove that, on event $\cE$, the solution set ${\mathcal{S}}(e_n)$ exhibits some favorable properties.
Theorem (ref) (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 (ref). Theorem (ref) (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) (i) to the regret decomposition in (ref) and establish an upper bound of $\mathrm{Regret}({\hat{\pi}})$.
The upper bound in Corollary (ref) 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)$.
Assumption (ref) 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 chen2012estimation. We now give a consistent result for any $h \in {\mathcal{S}}(e_n).$
Theorem (ref) 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 ai2012semiparametric, we introduce the notion of pathwise derivative of $\cTh$ evaluated at $h^{*}_{\alpha}$, in the direction $h-h^{*}_{\alpha}$, as follows:
We then define a pseudo-metric on ${\mathcal{S}}(e_n)$ based on the pathwise derivative:
where the term inside the expectation is defined as
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), 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) and Theorem (ref). We introduce the following assumption on the local curvature of $\cT$ around $h^{*}_{\alpha}$.
Assumption (ref) 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).
Assumption (ref) 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 (ref) based on the solution set ${\mathcal{S}}(e_n)$.
Before presenting the theorem, we introduce an assumption on the coverage of the offline data.
Assumption (ref) 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) 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}}.$
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) implies that the regret of ${\hat{\pi}}$ is bounded by $\cO(\eta_n).$ As we will show in Theorem (ref) in \S(ref), $\eta_n = \tilde{\cO}(n^{-1/2})$ when $\cH$ and $\Theta$ are chosen to be linear spaces, which corresponds to a “fast statistical rate” uehara2021finite. This rate aligns with those reported in the existing minimax estimation literature dikkala2020minimax, li2022pessimism. It is noteworthy that this rate is equivalent to that observed in scenarios involving linear objectives 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.
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
By this definition, we can simplify the regret of ${\hat{\pi}}_R$ similar to (ref) as follows.
Lemma (ref) 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) (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)$.
Assumptions similar to Assumption (ref) are commonly encountered in the literature of M-estimation 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) can be effectively bounded.
It remains to bound the first term on the right-hand side of (ref). 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.
Theorem (ref) 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) 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) and Theorem (ref).
Theorem (ref) 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), $\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) 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) in \S(ref). 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 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 rashidinejad2022optimal. Note that 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 xie2021bellman and 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.
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 (ref), against a greedy benchmark that does not incorporate pessimism. The simulation results demonstrate the benefits of pessimism, particularly in scenarios with insufficient data coverage.
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 (ref), 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: \[
\sim \mathcal{N} \left(
,
\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{Outcome $Y$.} As shown in (ref), we generate $Y$ according to the structural model:
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:
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 (ref), 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$.
We compare the pessimistic regularized policy learning algorithm (Algorithm (ref)) 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 (ref), any function $h $ in $\mathcal{H}$ can be written as
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 (ref). Note that supremum over $\theta $ in (ref) 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) with $\lambda_n = \sqrt{n}$, where $n$ is the sample size. This choice of $\lambda_n$ is suggested by Theorem (ref) for linear function classes, with $\epsilon_{R}$ set to zero. Note that (ref) 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 (ref) and reduce the problem to solving
Here we let $\pi(h)$ denote the greedy policy with respect to $h$. For example, for the function $h(\cdot; \beta)$ defined in (ref), 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 (ref) 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 (ref) 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).
We introduce the parameter of structured proportion $p$ in Section (ref). 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) and (ref), 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.
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.