Distributional Shift-Aware Off-Policy Interval Estimation:
A Unified Error Quantification Framework

We consider an infinite-horizon discounted Markov decision process (MDP) $\mathcal{M}=\{\mathcal{S},\mathcal{A},\mathds{P},\gamma,r,s^{0}\}$, where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $\mathds{P}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ is the Markov transition kernel for some probabilistic simplex $\Delta$, $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is the reward function, $\gamma\in[0,1)$ is the discounted factor and $s^{0}$ is the initial state. A policy $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ induces a distribution of the trajectory $s^{0},a^{0},r^{0},s^{1},\ldots$, where $a^{t}\sim\pi(\cdot|s^{t}),r^{t}=r(s^{t},a^{t}),s^{t+1}\sim\mathds{P}(\cdot|s^{t},a^{t})$ for any $t\geq 0$. The expected discounted return of a policy is defined as $J(\pi)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r^{t}|\pi]$. The discounted return when the trajectory starts with $(s,a)$ and all remaining actions are taken according to $\pi$ is called $q$-function $q^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow(-\infty,\bar{V}]$. The $q^{\pi}$ is the unique fixed point of the Bellman operator $\mathcal{B}^{\pi}$, satisfying the Bellman equation [61]: $\mathcal{B}^{\pi}q(s,a)\coloneqq r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathds{P}(\cdot|s,a)}[q(s^{\prime},\pi)].$ Here $q(s^{\prime},\pi)$ is denoted as shorthand for $\mathbb{E}_{a^{\prime}\sim\pi\left(\cdot|s^{\prime}\right)}\left[q\left(s^{\prime},a^{\prime}\right)\right]$, and we define $\mathds{P}^{\pi}q(s,a):=\mathbb{E}_{s^{\prime}\sim\mathds{P}(\cdot|s,a)}\left[q\left(s^{\prime},\pi\right)\right]$.

Another important notion is the normalized discounted visitation of $\pi$, defined as $d^{\pi}(s,a)\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}d^{\pi,t}(s,a)$, where $d^{\pi,t}$ is the marginal state-action distribution at the time-step $t$. Essentially, $d^{\pi}(s,a)$ characterizes the states and actions visited by $\pi$. For notation convenience, we write $\mathbb{E}_{d^{\pi}}[\cdot]$ to represent $\mathbb{E}_{d^{\pi}}\left[g\left(s,a,r,s^{\prime}\right)\right]:=\int_{s,a}d^{\pi}(s,a)\mathds{1}_{\{r=r(s,a)\}}\linebreak\mathbb{E}_{s^{\prime}\sim\mathds{P}(\cdot|s,a)}\left[g\left(s,a,r,s^{\prime}\right)\right].$ In the offline RL setting, there exists an unknown offline data-generating distribution $\mu$ induced by behavior policies. With a slight abuse of notation, we refer to the marginal distribution over $(s,a)$ and joint distribution over $(s,a,r,s^{\prime})$ as $\mu$. Despite the unknowns of $\mu$, we can observe a set of transition pairs, as offline dataset $\mathcal{D}_{1:n}\coloneqq\{s_{i},a_{i},r_{i},s^{\prime}_{i}\}^{n}_{i=1}$ sampling from $\mu$.

We make the following minimum data collection condition throughout the paper:

This condition relaxes the standard assumptions widely made in the RL literature, e.g., [38, 58, 37] typically require the sample path to be either i.i.d or weakly dependent. In contrast, we only require that the reward $r_{i}$ and the transition state $s^{\prime}_{i}$ follow the rules specified by $r$ and $\mathds{P}$, but do not impose any restrictions on the generation of the state-action pair $(s_{i},a_{i})$. Therefore, the dataset $\mathcal{D}_{1:n}$ can be collected as a set of multiple trajectories with interdependent samples, or under a mix of arbitrary unknown behavior policies. Ultimately, the goal of high-confidence OPE is to construct an efficient CI for estimating the return of policy $\pi$ using the offline dataset.

In this section, we provide a concise review of two essential concepts in OPE: marginalized importance sampling (MIS) [38] and linear programming (LP) [11]. These concepts form the foundation for our subsequent discussion. Following the definition of the MIS in [38], we have $\tau_{d^{\pi}/\mu}(s,a):=\frac{d^{\pi}(s,a)}{\mu(s,a)}$ to characterize the ratio of the visitation induced by target policy and behavior policy. If it exists, $\mathbb{E}_{d^{\pi}}\left[g\left(s,a,r,s^{\prime}\right)\right]=\mathbb{E}_{\tau_{d^{\pi}/\mu}}\left[g\left(s,a,r,s^{\prime}\right)\right]=\mathbb{E}_{\mu}\left[\tau_{d^{\pi}/\mu}(s,a)g\left(s,a,r,s^{\prime}\right)\right],$ where $\mathbb{E}_{\tau}[\cdot]:=\mathbb{E}_{\mu}[\tau(s,a)(\cdot)]$ is shorthand used throughout the paper. The return $J(\pi)$ can be obtained via re-weighting the reward with respect to the MIS weight, i.e., $J(\pi)=\frac{\mathbb{E}_{d^{\pi}}[r]}{1-\gamma}=\frac{\mathbb{E}_{\tau_{d^{\pi}/\mu}}[r]}{1-\gamma}$. Motivated by this fact, [67, 56] proposed a minimax estimator to estimate $\tau_{d^{\pi}/\mu}$ by searching a weight function $\tau(s,a):=\frac{d(s,a)}{\mu(s,a)}$ in a specified function class $\tau\in\Omega$ approximately:

Once $\tau_{d^{\pi}/\mu}$ is solved, the $d^{\pi}$ can be obtained using the chain rule, i.e., $d^{\pi}=\tau_{d^{\pi}/\mu}\cdot\mu$.

Recently, [46] showed that the above minimax problem has an equivalent solution to the LP problem [11]: $\text{maximize}_{d}\;\,\mathbb{H}(d)\equiv 0$ constrained on

where $\mathbb{H}(\cdot)$ is a functional that takes a visitation $d$ as input and is set to be a constant zero function for the LP problem. It is crucial to note that (2) is over-constrained for any given $s,a$. Specifically, the visitation $d^{\pi}$ can be uniquely identified solely based on the constraints. This over-constrained characteristic explains why $\mathbb{H}(d)$ can be set as a zero constant function and why (2) is sufficient to recover the optimal solution $d^{\pi}$. In the following, we will utilize this property to incorporate distributional shift information into the proposed framework.

We study the first major component in CI estimation, i.e., evaluation bias, and propose a value interval method to quantify it. The developed framework is robust to model misspecification and naturally encodes the distributional shift information. To begin with, we formally define the discriminator function, which serves a dual purpose in this work. For now, we primarily concentrate on one of these roles, which is to measure the extent of deviation between the offline data-generating distribution $\mu$ and the distribution induced by the target policy. Later, we will demonstrate the other role that the discriminator function plays in estimating CI in Section 4.

The family of Rényi entropy [54], Bhattacharyya distance [9], and simple quadratic form functions all satisfy the conditions outlined in Definition 3.1.

As discussed in Section 2.2, the LP problem (2) is over-constrained and the visitation $d^{\pi}$ can be uniquely identified. Consequently, one may replace the objective $\mathbb{H}(d)$ with another functional, provided that the newly-replaced functional does not affect the optimal solution $d^{*}=d^{\pi}$. Motivated by this observation, we propose to choose $\mathbb{H}(d)=\lambda\mathbb{E}_{\mu}[\mathbb{G}(\tau(s,a))]$ where $\tau(s,a):=\frac{d(s,a)}{\mu(s,a)}$, and the hyperparameter $\lambda\in\mathbb{R}$ user’s preference and degree of sensitivity to the distributional shift. When $\lambda<0$, it indicates that the user favors small distribution shifts and appeals to pessimistic evaluation, which encourages downgrading the policy associated with large distribution shifts. For $\lambda=0$, the user maintains a neutral attitude toward the distributional shift. Furthermore, our framework degenerates to (2) or (1) under this condition. From this perspective, both the minimax estimation in (1) and the LP problem in (2) can be considered special cases of our approach when we take $\lambda=0$. According to the connection between (1) and (2), we can convert the newly-defined LP problem with $\mathbb{H}(d)=\lambda\mathbb{E}_{\mu}[\mathbb{G}(\tau(s,a))]$ to a max-min problem. This can be expressed as $\min_{\tau\in\Omega}\max_{q\in\mathcal{Q}}L(q,\tau)$, where

Unfortunately, directly optimizing objective function $L(q,\tau)$ has some drawbacks. To comprehensively reveal these drawbacks, we first present a key lemma to support our arguments.

Lemma 3.1 suggests that the rationale behind $\min_{\tau\in\Omega}\max_{q\in\mathcal{Q}}L(q,\tau)$ is to find a “good” $\tau^{*}$ such that $\frac{\mathbb{E}_{\tau}[r(s,a)]}{1-\gamma}$ and $J^{\alpha}(\pi)$ are are sufficiently close when $q^{\pi}\in\mathcal{Q}$. Then $\tau^{*}$ can be plugged in $\frac{\mathbb{E}_{\tau}[r(s,a)]}{1-\gamma}$ to approximate $J^{\alpha}(\pi)$. In fact, this rationale also implicitly requires the existence of $\tau^{*}\in\Omega$. When $\Omega$ is misspecified, the evaluation will exhibit a high bias. For OPE problems significantly affected by the distributional shift, the true model is particularly challenging to specify [24, 7]. Additionally, another limitation of the min-max estimation is that the objective function $L(q,\tau)$ completely disregards the reward information.

Motivated by the above-mentioned drawbacks, we propose a more robust interval method for estimation. Free from any model-specification assumptions on $\Omega$, our proposal implicitly quantifies the evaluation bias resulting from model-misspecification error within the interval. According to Lemma 3.1 and assuming $q^{\pi}$ is correctly specified, the following inequality holds for any $\tau\in\Omega$:

where $\lambda^{-}:=-\min\{0,\lambda\}$. Similarly, the return $J(\pi)$ from above:

where $\lambda^{+}:=\max\{0,\lambda\}$. Considering that (3) and (4) hold for any $\tau\in\Omega$, we can optimize them over $\tau$ to obtain the tightest possible interval:

where we denote the upper bound and lower bound as $J^{+}(\pi)$ and $J^{-}(\pi)$, respectively. This optimization can also be interpreted as searching for the best $\tau^{*}$ within the class $\Omega$ to minimize the model-misspecification error. Based on the value interval in (5), we demonstrate that the evaluation bias, i.e., the model misspecification error of $\Omega$, is implicitly quantified in the interval and can be decomposed into two components.

Theorem 3.1 implies that the evaluation bias consists of two components: the model-misspecification error $\epsilon_{mis}$ and the bias caused by the discriminator function, denoted by $\epsilon_{dist}$. The latter can be effectively controlled by adjusting the magnitude of $\lambda$. The former, $\epsilon_{mis}$, is dependent on the wellness of the model specification on $\Omega$. In particular, if the class $\Omega$ is well-specified, it is possible for $\epsilon_{mis}$ to diminish to zero. We direct readers to Section A in the appendix for a more comprehensive discussion on the tightness and validity of the interval.

To conclude this section, we remark that the value interval (5) directly quantifies the evaluation bias and incorporates a well-controlled adjustment scheme for distributional shifts. As a result, our proposed framework is robust against both model-misspecification errors and bias estimation due to distributional shifts. It is important to note that the value interval (5) is not a CI, as it does not address the uncertainty arising from sampling. In the following section, we will explore uncertainty quantification using our established interval estimation framework.

In this section, we first examine the potential sources of uncertainty that may appear in CI estimation. We then establish two types of CIs for the scenarios when $\lambda=0$ and $\lambda<0$, and separately quantify the uncertainty in these two CIs. Intuitively, these two CIs represent neutral and pessimistic attitudes towards distributional shifts. We begin by presenting a key lemma for our proposal. Recall that we do not impose any independent or weakly dependent data collection assumptions, e.g., mixing conditions, for uncertainty quantification.

Lemma 3.2 suggests that there are two sources of uncertainty when constructing CI estimation. The first source originates from the estimand $\{\tau(s_{i},a_{i})(r_{i}+\gamma\mathds{P}^{\pi}q^{\pi}(s_{i},a_{i})-q^{\pi}(s_{i},a_{i}))\}^{n}_{i=1}$ and can be approximated by $\{\tau(s_{i},a_{i})(r_{i}+\gamma q^{\pi}(s^{\prime}_{i},\pi)-q^{\pi}(s_{i},a_{i}))\}^{n}_{i=1}$. The second source stems from the discriminator $\{\mathbb{G}(\tau(s_{i},a_{i}))\}^{n}_{i=1}$. Once the uncertainty of these two sources is quantified, it can be incorporated into the CIs according to Lemma 3.2.

In the following, we present our results on uncertainty quantification and establish the CI for the case when $\lambda=0$, which implies that distributional shift is not taken into account. Specifically, we characterize the uncertainty deviation, denoted by $\sigma_{n}$ in (8), which constitutes a major component of the proposed neutral CI in (7).

A closer examination of (7) and (8) reveals two key insights. Regarding the class $\mathcal{Q}$, even though the bias quantification necessitates searching possible $q$ uniformly over $\mathcal{Q}$, the statistical uncertainty deviation $\sigma_{n}$ can be evaluated point-wisely, specifically at the true $q$-function $q^{\pi}$, as shown in (8). Regarding the class $\Omega$, the result in (7) holds for any $\tau\in\Omega$, even if the specified $\Omega$ class does not capture the true $\tau$, i.e., $\tau_{d^{\pi}/\mu}$. This suggests that the CI in (7) is robust against model misspecification errors. The misspecification of $\Omega$ only influences the tightness of the CI but does not compromise the validity of the CI. Also, optimizing the confidence lower and upper bounds in (7) over $\tau\in\Omega$ can help tighten the CI.

We still need to determine the uncertainty deviation $\sigma_{n}$ in (8) to obtain a tractable CI. Typically, the deviation $\sigma_{n}$ depends on the complexity of hypothesis function class $\Omega$ and uniform concentration arguments. To measure the function class complexity, we use a generalized notation for the VC-dimension, called the pseudo-dimension (see Definition C.3 in the appendix). As for the uniform concentration arguments, we construct a martingale difference sequence, which allows us to apply the empirical Freedman’s concentration inequality [65]. In the following, we illustrate our general result for determining $\sigma_{n}$ using $L_{\infty}$ bounded classes for $\Omega$ modeling.

As shown in (9), the deviation $\sigma_{n}$ increases with the pseudo-dimension of $\Omega$ and decreases with the sample complexity of order $\mathcal{O}(1/\sqrt{n})$. Note that this is an information-theoretical result as finding the exact value of the pseudo-dimension for an arbitrary $L_{\infty}$-class function is challenging. To refine our result, we consider using a feature mapping class for modeling $\Omega$. Let $\phi:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$ be a $d$-dimensional feature mapping, and define a feature mapping class $\Omega_{\psi}$ as follows: $\Omega_{\psi}:=\{(s,a)\mapsto\langle\phi(s,a),\psi\rangle\,|\,\|\psi\|_{L_{2}}\leq\text{diam}_{\psi}\}$ where $\text{diam}_{\psi}\in(0,\infty)$.

Corollary 3.1 provides a tractable quantification of the uncertainty deviation $\sigma_{n}$. Each element in (10) is either user-specified or can be calculated using the offline data $\mathcal{D}_{1:n}$. Compared to the vanilla rate of $\mathcal{O}(1/\sqrt{n})$ in Theorem 3.3, the uncertainty deviation can vanish at a faster sublinear rate, i.e., $\mathcal{O}(1/n)$ if $\lambda_{\max}(\Sigma_{n})\ll\text{diam}_{\psi}$. This improvement in the rate of convergence benefits from our careful analysis of variance terms w.r.t. $\Omega_{\psi}$.

In this section, we establish the CI for $\lambda<0$, which we call the pessimistic CI. Since $\lambda\neq 0$, the pessimistic CI incorporates a newly-defined discriminator function in (3.1). In the case of $\lambda<0$, the pessimistic CI favors target policies with small distributional shifts. This property allows the pessimistic CI to be used to differentiate the goodness of policies that suffer from bias estimation issues due to distributional shifts [34]. Additionally, compared to the uncertainty quantification in the neutral CI, we need to take one more step to quantify the uncertainty arising from the estimand of the discriminator function. In the following theorem, we present our formal result in statistical sampling uncertainty quantification and establish the pessimistic CI.

The confidence upper bound in (11) is nearly identical to the one in the neutral CI, so we will not discuss it further here. However, the confidence lower bound in (11) differs from the one in (7). The current confidence lower bound incorporates distributional shift information as well as the corresponding uncertainty included in the deviation $\sigma^{L}_{n}$. By doing so, the estimand of the discriminator $\xi_{n}(\mathbb{G},\tau)$ helps to offset the bias evaluation caused by distributional shifts. When users follow the pessimism principle [31, 26], the confidence lower bound can make policy evaluation and optimization more reliable when the offline dataset is poorly explored or exhibits significant distributional shifts. Careful readers may notice that the involvement of the discriminator tends to widen the interval. However, the degree of widening can be well-controlled by $\lambda^{-}$. Additionally, due to the potentially tightest construction of the CI, which will be demonstrated in the next section, the pessimistic CI does not lead to overly pessimistic reasoning even with the inclusion of an extra discriminator.

To make (11) estimable, we need to determine the uncertainty deviations, $\sigma^{U}_{n}$ and $\sigma^{L}_{n}$. For $\sigma^{U}_{n}$, we can easily follow the derivation in the neutral CI. However, for $\sigma^{L}_{n}$, the quantification is slightly more complicated. To determine $\sigma^{L}_{n}$, we construct a pseudo estimator

such that $\{\widehat{L}^{q}_{n}(q^{\pi},\tau)+\lambda^{-}\xi_{n}(\mathbb{G},\tau)-n^{-1}\sum^{n}_{i=1}\mathcal{U}(s_{i},a_{i})\}$ forms a summation of a martingale difference sequence. We can then follow an almost identical martingale concentration technique as in Theorem 3.3 to determine $\sigma^{L}_{n}$, so we omit it here. In the next section, we will provide a more elegant and tighter approach for quantifying the uncertainty deviation $\sigma^{L}_{n}$.

As discussed in the previous sections, bias and uncertainty are two major sources of errors in CI estimations. In order to obtain a tight interval, one would expect to minimize both of them. Statistical uncertainty, as shown in (9), is highly dependent on the complexity of the function class, which is measured in terms of the pseudo-dimension $D_{\Omega}$. In general, a high pseudo-dimension indicates that the set of functions is complex and thus requires a sufficiently large deviation to control the uncertainty uniformly over all functions in the set. To minimize the uncertainty deviation, we prefer to model $\Omega$ using a parsimonious class of functions with a low pseudo-dimension. As for evaluation bias, Theorem 3.1 indicates that the model-misspecification error of $\Omega$ is a major component. Minimizing bias requires minimizing the model-misspecification error. Generally, a more expressive function class, i.e., with a high pseudo-dimension, is more likely to capture the true model and potentially reduce the bias due to model misspecification. For example, [59] allow the VC-dimension to diverge with the sample size to reduce the estimator’s bias due to model misspecification. If we translate this principle to our framework, it is equivalent to allowing the pseudo-dimension $D_{\Omega}=\mathcal{O}(n^{-\kappa})$, where $0<\kappa\leq 1$.

Taking both bias and uncertainty into account, we regrettably identify a tradeoff between them, as exemplified in Figure 1. On one hand, a more parsimonious function class can attain enhanced efficiency in uncertainty quantification. However, this comes at the expense of sacrificing the function class’s expressivity, consequently increasing the bias. On the other hand, a more expressive function class aids in reducing model misspecification errors but demands a higher cost to account for the uncertainty inherent in a complex set of functions. Is there a way to break the curse of the bias and uncertainty tradeoff? In the following sections, we will present our solution to this question.

In this section, we propose a kernel representation approach to break the curse of the tradeoff for the neutral CI in smooth MDP settings. Under this representation, the uncertainty deviation is independent of the function class complexity. We make use of a powerful tool in concentration measures, Pinelis’ inequality [48], to quantify the data-dependent uncertainty deviation in Hilbert space. As a result, this can achieve minimum costs regarding uncertainty quantification, while simultaneously allowing the model-misspecification error to be arbitrarily minimized due to the flexibility of the kernel representation. To begin with, we introduce the definition of the smooth MDP.

Smooth MDP settings are widely satisfied in many real-world applications and studies in the existing literature [35, 58]. Recall that our goal is to quantify the uncertainty deviation $\sup_{\tau\in\Omega}|\widehat{L}^{q}_{n}(q^{\pi},\tau)|$ in (8) to establish the CI. According to theorem 3.2 in [74], the maximizer of the problem $\sup_{\tau\in\Omega}|\widehat{L}^{q}_{n}(q^{\pi},\tau)|$, i.e., $\tau^{*}(s,a)$, is a continuous function in the smooth MDP setting $\mathcal{M}=\widetilde{\mathcal{M}}$. This motivates us to consider some smooth function classes for modeling $\Omega$, provided that these function classes can approximate continuous functionals sufficiently well. In particular, we model $\Omega$ in a bounded reproducing kernel Hilbert space (RKHS) equipped with a positive definite kernel $K(\cdot,\cdot)$, i.e., $\Omega_{RKHS}(C_{K})\coloneqq\{\tau\in RKHS:\|\tau\|_{RKHS}\leq C_{K}\}$, where $\|\cdot\|_{RKHS}$ denotes the kernel norm and the constant $C_{K}>0$. This kernel representation allows the maximization problem $\sup_{\tau\in\Omega_{RKHS}(C_{K})}|\widehat{L}^{q}_{n}(q^{\pi},\tau)|$ to have a simple closed-form solution $\tau^{*}$. We note that this is based on the maximum mean discrepancy [19]. Accordingly, the maximum value $(1-\gamma)\widehat{L}^{q}_{n}(q^{\pi},\tau^{*})$ equals to

where the square root operator is well-defined by the positive definite kernel $K(\cdot,\cdot)$.

The closed-form solution assists us to elaborate on uncertainty quantification. In (13), the function $\tau$ is maximized out and no longer appears in the sample estimand. Remarkably, the complexity of $\Omega$ does not influence the uncertainty deviation, which is now entirely independent of the function class complexity. This transforms the uniform uncertainty quantification into a point-wise uncertainty quantification focused on the global maximizer $\tau^{*}$, significantly reducing the uncertainty deviation. Furthermore, it has been demonstrated that Reproducing Kernel Hilbert Spaces (RKHS) can achieve arbitrarily small approximation errors when approximating continuous functions [2]. In other words, it is possible to minimize the model-misspecification error of $\Omega$ and even eliminate the error entirely, as long as the true model $\tau^{\star}$ is continuous, which holds in smooth MDP settings.

In summary, by leveraging the kernel representation, we observe a double descent phenomenon whereby the model-misspecification error and uncertainty deviation can be minimized simultaneously. Imposing a minor constraint on the continuity of MDPs, we overcome the curse of the bias and uncertainty tradeoff. In the following, we provide a brief overview of our method for quantifying the uncertainty deviation under the kernel representation. Inspired by the reproducing property, we initially construct a pseudo-estimator, i.e.,

and rewrite (13) with $\widehat{L}^{q}_{n}(q^{\pi},\tau^{*})=\sqrt{\|\frac{1}{n}\sum^{n}_{i=1}\Lambda(\cdot;i)\|_{RKHS}},$ where $\Lambda(\cdot;i):=\langle{q}^{\pi}(s_{i},a_{i})-r_{i}-\gamma{q}^{\pi}(s^{\prime},{\pi}),\sqrt{C_{K}}K(\{s_{i},a_{i}\},\cdot)\rangle.$ It can be seen that the sequence $\{\Lambda(\cdot;i)-\Lambda^{\text{pseudo}}(\cdot;i)\}^{n}_{i=1}$ forms a martingale difference sequence in Hilbert space with respect to the filtration $\mathcal{F}_{i}:=(s_{\leq i},a_{\leq i},r_{\leq i-1},s^{\prime}_{\leq i-1})$. This motivates us to use Pinelis’ inequality to quantify the uncertainty deviation as illustrated in the following theorem.

Theorem 4.1 achieves an order of $\mathcal{O}(1/\sqrt{n})$ convergence rate, which is as fast as the minimax rate in learning with i.i.d. data [68]. Enabled by the kernel representation, the upper bound $\varepsilon^{K}_{n}$ is independent of the complexity of $\Omega$. Let $\sigma_{n}=\varepsilon^{K}_{n}$, then the uncertainty deviation is significantly reduced compared to those in Theorem 3.3 or Corollary 3.1. Recall that we can optimize the upper and lower bound in the neutral CI (7) to minimize the bias, and obtain a possibly tightest interval. Intriguingly, the maximization problem $\sup_{q\in\mathcal{Q}}\widehat{M}^{\tau}_{n}(-q,\tau)$ within the CI also has a simple closed-form solution when $\mathcal{Q}$ belongs to a bounded RKHS [38]. This can be employed to alleviate the optimization burden and enhance stability. Now, together with the uncertainty defined in Theorem 4.1, we formulate the trade-off neutral CI as follows.

As demonstrated in Corollary 4.1, the unstable two-stage optimization problem, involving optimizing both $\tau$ and $q$, is decoupled into an easier solvable single-stage optimization.

In this section, we introduce a tradeoff-free pessimistic CI estimation. We make a further step in breaking the curse of the “bias-uncertainty” tradeoff without requiring any additional conditions, e.g., smoothness conditions for MDPs as discussed in the last section. In any general MDPs, the evaluation bias and statistical uncertainty in CI estimation can be minimized simultaneously without compromising one or the other. The main idea is to utilize Lagrangian duality and the curvature of the discriminator function $\mathbb{G}$. This is another motivation for defining a discriminator function as in (3.1), in addition to its role in handling distributional shifts. In the following, we characterize a unique and global optimizer related to the lower bound in (12), which builds a foundation for our subsequent methodological developments.

The proof of Proposition 4.1 relies on the Lagrangian duality and the strong convexity of $\mathbb{G}$. The analytical form (16) motivates us to construct an appropriate pseudo estimator to measure the uncertainty deviation which is independent of the complexity of $\Omega$. Define the pseudo estimator $\Gamma^{\text{pseudo}}$ as