Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes
Authors: Andrew Bennett
Nathan Kallus
Miruna Oprescu
Wen Sun
Kaiwen Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Sensitivity Analysis
Robust MDPs
Semiparametric Efficiency
Primary area: causal_inference

Abstract: We study the evaluation of a policy under best- and worst-case perturbations to a Markov decision process (MDP), using transition observations from the original MDP, whether they are generated under the same or a different policy. This is an important problem when there is the possibility of a shift between historical and future environments, \emph{e.g.} due to unmeasured confounding, distributional shift, or an adversarial environment. We propose a perturbation model that allows changes in the transition kernel densities up to a given multiplicative factor or its reciprocal, extending the classic marginal sensitivity model (MSM) for single time-step decision-making to infinite-horizon RL. We characterize the sharp bounds on policy value under this model -- \emph{i.e.}, the tightest possible bounds based on transition observations from the original MDP -- and we study the estimation of these bounds from such transition observations. We develop an estimator with several important guarantees: it is semiparametrically efficient, and remains so even when certain necessary nuisance functions, such as worst-case Q-functions, are estimated at slow, nonparametric rates. Our estimator is also asymptotically normal, enabling straightforward statistical inference using Wald confidence intervals. Moreover, when certain nuisances are estimated inconsistently, the estimator still provides valid, albeit possibly not sharp, bounds on the policy value. We validate these properties in numerical simulations. The combination of accounting for environment shifts from train to test (robustness), being insensitive to nuisance-function estimation (orthogonality), and addressing the challenge of learning from finite samples (inference) together leads to credible and reliable policy evaluation.

Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes
Andrew Bennett"
Nathan Kallus* Cornell University kallus@cornell. edu edu
Morgan Stanley
andrew. bennet cennettt@oorganttanle.. com
Miruna Oprescu'
Wen Sun"
Kaiwen Wang" Cornell University
Cornell University
Comell University
amo78@cornell.eem
wB455@cornel1.cm edu
kw4378cornell1
Abstract
We study the evaluation of a policy under best- and worst-case perturbations to Markov decision process (MDP), using transition observations from the original MDP, whether they are generated under the same or a different policy. This is important problem when there is the possibility of shift between historical and future environments, e.g. due to unmeasured confounding, distributional shift, adversarial environment. We propose a perturbation model that allows changes in the transition kernel densities up to given multiplicative factor or its reciprocal, extending the classic marginal sensitivity model (MSM) for single time- step cecisionnmaking to mafinite-horizor RL. We characterize the sharp bounds on policy value under this model i.e., the tightest possible bounds based on transition observations from the original MDP and we study the estimation of these bounds from such transition observations. We develop an estimator with several important guarantees: it is semiparametrically efficient, and remains so even when certain necessary nuisance functions, such as worst-case Q-functions, are estimated at slow, nonparametric rates. Our estimator is also asymptotically normal, enabling straightforward statistical inference using Wald confidence intervals. Moreover, when certain nuisances estimated inconsistently, the estimator still provides valid, albeit possibly not sharp, bounds on the policy value. We validate these properties in numerical simulations. The combination of accounting for environment shifts from train to test (robustness), being insensitive to nuisance- function estimation (orthogonality), and addressing the challenge of learning from finite samples (inference) together leads to credible and reliable policy evaluation.
Introduction
Offline policy evaluation (OPE) from historical data is crucial in domains where active, on-policy experimentation is costly, risky, unethical, or otherwise operationally infeasible. Relevant domains range from medicine finance and recommendation systems. However, whenever historical data is used to study future behavior, there is a concern of non-stationarity shift between the environment generating the data (training environment) and the environment in which policy will be deployed (test environment). This may occur, e.g., due to general distributional shifts in the environment over time, unobserved confounding environment (such other agents) that may react when the agent is deployed. While standard OPE offline reinforcement learning (ORL) accounts for the change between the logging and evaluation policies, it may overlook the fact that the Markov decision process (MDP) too has changed. While
observed historical data, or adversarial elements of the
Alphabetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

this issue is particularly critical in high-stakes domains, it is broadly appealing to understand how value shifts across different environments in any application domain.
Robust MDPs [34, 56] model unknown environments by allowing an adversary to choose from any one environment in set. Therefore, they offer natural model for unknown environment shifts by simply considering all environments to which we could possibly shift. A variety of work addresses questions such as planning in a known robust MDP [30, 51, 80] as well online learning [6. 79]. Here we focus on a purely statistical estimation question: given observations of transitions from some unknown transition kernel. we wish to estimate the worst-case (or best-case) value of given evaluation policy in a robust MDP, defined by set of MDPs whose transition functions are centered around the observed transition kernel.
This setting captures the previously studied unconfounded robust OPE. problem [73], where the observed transition kernel corresponds to an MDP, and the observed transitions the result of applying some logging policy within this MDP. In such cases, the goal is to estimate policy values that are robust future changes in the MDP dynamics. However, our setting is more general in that also captures problems where the observed transitions are confounded by some unobserved variables, in which case they do not correspond to observations from the transition kernel of an MDP. In this case, the robust MDP and the robust policy value estimates are designed to account for worst-case (or best-case) impact of this confounding bias. In either case, as in ORL, we emphasize that we do not know the observational MDP, and can only access it via a sample of transitions. Furthermore, even in the simple case with no unmeasured confounding, in notable departure from standard ORL, the problem can be difficult even if the logging and evaluation policies are the same (the usually easy on-policy setting), since the policy can induce very different visitation distributions in the original and perturbed MDPs.
Such robust offline evaluation from transition data was considered in recent work [12, 59]. We build on this recent work by focusing the question of statistically efficient and robust estimation of the sharp bounds (i.e., the tightest possible given the data). Previous work focused on evaluation using only the Q-function under the worst-case environment (in some cases under relaxation of the adversary. leading to loose bounds). Thus, any error in its estimation translates directly to error in evaluation. In other words, flexible nonparametric modeling of this function can mean slow rates for estimated bounds and lack semiparametric efficiency. Moreover, without a clear understanding of the noise in the estimates, we cannot add confidence bands to the bounds, leading to bounds that are too tight.
We address these challenges by developing an orthogonalized estimation method that combines several nuisance functions: the worst-case Q-function, the state-visitation frequency in the worst-case environment, and threshold function characterizing the worst-case transition kernel. Our first key result is that, to first order, our estimator behaves as a sample average using the true values of these functions without having to estimate them at all, provided we just estimate them at certain slow nonparametric rates. This ensures we not only have a / Vrrrate of estimation even when nuisances are estimated more slowly, but also that our estimator asymptotically normal. This allows for the construction of confidence bands on the bounds, providing assurance that the true bound is captured. We further show that our asymptotic variance is in fact the minimum variance among all regular and asympiotically linear (RAL) estimators, ensuring semiparametric efficiency. Our second key result is that even if we do not estimate some of the nuisance functions correctly, we are still consistent to sharp or valid bounds. That is, even when we are biased due to misestimation of nuisances, our bias (if any) only enlarges our bounds, so they remain valid. We illustrate these guarantees numerically, Collectively, these guarantees lend substantial credibility to the bounds generated by our method.
Our contributions are summarized as follows:
1. We provide novel algorithms and analysis for learning robust Q-functions (Section 3) and robust visitation density ratios (Section 4) under the function approximation setting.
2. We derive the sharp and efficient estimator for the robust policy value, which is optimal in the
sense and is the gold standard in semiparametric estimation (Section 5). 3. We empirically validate the efficiency and sharpness of our approach (Section 6).
1.1 Related Works
Unobserved Confounding in Sequential Makksig OPE in robust MDPs is related to OPE bounds in confounded MDPs, where the behavior policy and the transition kernel are influenced by

---

unobserved confounders. The constraint Eq. (1) that defines our target robust MDP aligns with the Marginal Sensitivity Model (MSM) [66] employed in sensitivity analysis for causal inference. Yet. unlike the MSM, which limits the ratio of policy densities, our approach directly constrains the ratio of the transition kernels. Our formulation can be viewed as generalization of the MSM from traditional two-action no-horizon causal effects (where the constrains coincide) to multi-action infinite-horizon discounted MDPs, where the next state is the "potential outcome". In that sense, our model essentially serves an outcome-based sensitivity model [10]. This distinction is crucial it enables model to subsume the policy-basce MSM in cases where the policy is confounded. Nonetheless, the reverse does not hold, and the policy-based MSM does not imply transition kemel--based MSM for A >> 2. This point is further corroborated by [12], who explore the policy- -ased MSM within confounded MDPs and obtain non-sharp identification bounds when A > 2. In contrast, approach yields sharp identification in general, regardless of the number of actions and without placing assumptions on the behavior policy, which may or may not be confounded.
[13] also considered an MSM-like model in the transition kernel but their formulation assumes A = 2. [40] operates under the setting of [12] and required tabular states. We note that all these works including ours considers i.i.d. confounders at each step, which translates to a robust MDP with (s, a) --recttaggllartty and ensures that the worst-case problem is still an MDP rather than POMDP. The importance of this assumption was verified by [55], who showed that without it, the non-memoryless confounder can create exponential in-horizon changes in value.
Neyman Orthogonality and Semiparametrie Efficient Estimation. We leverage a body of research focusing on learning with nuisances functions (e.g., Q-functions) that we need to estimate from data but are not the primary target (e.g., policy value). Much of this research [7, 16, 17, 29, 64, 70, among others] aims to identify Neyman-orthogondl estimators, which are first order orthogonal (insensitive) to nuisance errors. This literature is tightly linked to the semiparametric efficient estimation literature scores can arise naturally from efficient influence functions [33, 62].
since Neyman-orthogone Going beyond the no-horizon causal inference setting, some explore such estimators in off-policy sequential-decisonn contexts [19, 38, 42, 48, 50]. Notably, [39] derive efficient influence functions and orthogonal estimation in standard, non-robust OPE in fhiiite-horizon RL, which coincides with unconfounded no-uneertynnty case (A = 1).
Moving beyond point-identified settings, some works explore orthogonality and efficiency for partial identification and sensitivity analysis. In the causal inference literature, efficient/orthogonaa estimation in the no-horizon setting has been studied extensively under several sensitivity models [10, 18, 24, 58). Closest to our work is [24] who provide orthogonal estimator and convergence rates under the MSM [66], which coincides with our setting under 7 = 1. In the sequential setting, [55] considers confounding at a single time step under the MSM, but their estimator is not orthogonal when the quantile function unknown. [12] provide a -ritd-Q-iteration learner with an orthogonalized loss function, but not orthogonal/efficient estimates of worst-case policy value.
2 Preliminaries
We consider MDP with state space S, action space A, transition kernel P(s' s, s,a). reward function r(s, a) E [0, 1] and initial state distribution d1 E ASS). We do not require S or A to be finite. We assume r and d1 known for simplicity, and it is standard to extend our analysis to when they are unknown. We are given a dataset D of n i.i.d. tuples (s; a; Ti, s() such that (st, 0;) v, & - P(. s, a) and r; = =r(s; az), where is arbitrary data-generating distribution. For discount factor y E [0. 1). let the Q function be the discounted cumulative rewards under a policy S + A, Qr.P(s. a) E, Ex, 7're(Se, ae) 81 = 8, dj a). Similarly, define the value function as P()
Qr, ((8, T) where we use the notation f(x, F) == Eu-n(s) (f(s, a)] for any function ʃ S A IR.
We are interested in estimating the value of a fixed target policy क. (a.k.a. evaluation policy) in an unobserved MDP with feasible perturbed transition kernel U. We say U is a feasible perturbation of the observed, nominal kernel P if for all s, a, s': we have
al(s')s.)) A (s, < aP(
< A(s,
(I)
where A(s.a) a) E oo) is a sensitivity parameter chosen by the practitioner. On the extremes, A == corresponds to no-confounding (i.e., classic OPE setting) and A = oo corresponds to maximal- confounding (i.e., worst or best outcome). We denote the set of all feasible perturbations of P by
3

---

U(P), which is an 8, d-rectangular set [51]. We define the best- and worst-case Q functions of as Q+ == suP (s,
(s, a) == inforu(P) (s, (2)
Thus, the goal of this paper is to estimate the best- and worst-case value of at the initial state,
V (1 Es [V= (si))-
where V=(s) (a)n(s))) (s) a)] and the + symbol signals that an equation should read twice, once with = and once with = For clarity, we focus the discussion in the main text estimating the worst-case policy value, V.. We provide a similar analysis for policy values under best-case perturbations (V2))) in Appendix B.
Compared standard OPE, robust OPE is more challenging since the best- and worst-case transition kernels U are unobserved as our dataset 'D is generated under P. For example, standard OPE is easy in the on-policy case i.e., if D were generated by nt, but our problem is still "off-data" and non-trivial.
Discounted Visitation Distributions. For any transition kernel U, define the discounted visitation
distribution of ग. under U as: (s) == (1 - 7) Eh >" (44))((s)) where d (g))((s) (s) is the probability of reaching state in the Markov chain induced by U and policy γi starting from di (.). We use 000 as shorthand for m di,U-> where U- denotes the worst-case kernel in (P)..
Bellman-type Operators. For any function f S A R and transition kernel U, recall the Bellman operator is defined as fu, == r(s,a) + -Eulf(s m)) s,a). For robust OPE, we define the following robust analog [ = r(s.a) + 7SuPueu(P) (u m) 8, s,a) and Trob [ a) = r(s,a) a) + + infereupp Ey [J m)) 8, s, Moreover, we define [v, := ylE (f m)) s.a] f(s--(ssa)) a). For any linear operator T, also let T' denote its adjoint: that is, for all f.g E (2(v). (f. = (T'..g). where (..-) is the inner product L2(r).
Conditional Value-at Risk (CVaR). For a random vari- able X, its upper/lower CVaRs at level r E [0, 1] is defined as the average outcome of the upper/lower 7 7-fraction of cases, and are formally defined as follows [61]:
E [vis)) ss
s,a
(s a)
B (s.
CVaR (s.
CVaR (s,
CVaRt = min + + bER
TB [E b)+]}
CVaR, = max E((X - 6)-1}.
where y4 = max(0, y) and y- == min(0, y) for E R. The optima are attained the upper/lower 7-th quantile of X which we denote as 3 (x) (X), i.e.
Figure 1: Lower and upper CVaRs and quantiles (3) of v(s') 8, distribution.
CVaR = (x))+ (x)))))))())))+++++))0)))>+))))) X (x)) CVaR, = 8, ( (X))
E[
If X has cumulative distribution function (CDF) which is differentiable at 3 (X), its CVaRs simplify to CVaR (X) E| X > 8+ (X) and CVaR, E[X X < 8, (X)). In the paper, F will often be set to + (A+1)-1e [0, 0.5).
Notations. We use x S y to mean that x S Cy holds for some universal constant C. The indicator function [[[] takes value if p true and 0 otherwise. For measure μt, we let [] := (E) denote the L2 norm of f. provided it exists. When μ is clear from context, we also use I| := (B))()))))/> to denote the Lp norm of f and [| = (x) to denote the empirical analog. For data sample of size n, define the empirical mean as E, [[()] = 1 Σm fxx).. For a nuisance function f, we reserve f" as its true value and f as the learned value from data. Moreover, we employ + and to denote functions corresponding to best- and worst-case bounds, respectively. See Appendix for comprehensive notation table.
2.1 Background: Non-robust OPE
We provide a quick primer on the double RL (DRL) estimator for classic OPE in non-robust MDPs [38], which combines estimates of the Q-function and density ratio w to achieve orthogonality, double robustness and semiparametrie efficiency. This sets the stage for our orthogonal estimator

---

in Section 5, which generalizes DRL to robust MDPs by incorporating the robust Q- Q-function and density ratio in the worst-case MDP, as described in Section 3 and Section respectively.
The DRI. estimator involves two nuisances: (1) g, for which the oracle (true value) is the Q-function of the target policy Q",, and (2) u., for which the oracle is the density ratio of the target policy's visitation distribution and the data distribution w = d/dj.r/de. In this section, let 17 (w, q) denote the DRL nuisances (outside this section, we use 7y to denote our robust estimator's 's nuisances) and let n" = (w",, QT)) denote their true values, then the recentered efficient influence function (EIF) of V non-robust MDPs given by:
(R a, s w. q) = V + a(s (r(s, 70(5', ( a)).
The DRL estimator uses cross-fitting learn nuísances rilki all data excluding the k-th fold D for k- = 1,2,.... K and estimates the OPE value via:
V = - "" DO (s, a, s': ()))
As we will see, this paves the way for the EIF of the robust value (Theorem 5.1) and our orthogonal estimator (Algorithm 3). There are two main guarantees for DRL: double robustness and semipara-
[D] such that [|ğ Q ll2 S r and || wh l|2 S xx Then, DRL enjoys [DDLL V S On (((n-1/- 1/2 + r""r)) which confers the algorithm double robustness properties. Moreover, if > ope is the efficiency bound (i.e., minimum achievable asymptotic variance among RAL estimators in nonparametric models for (s, a, s')), then vn( V
metric efficiency. Let r and rg be rate functions depending on
) 4 AO oo We seek similar guarantees for our orthogonal robust estimator.
3 Robust Q-Function Estimation with Fitted-Q Evaluation
In this section, we identify the robust Q-function using the robust Bellman equation and then derive convergence rates for iteratively minimizing the robust Bellman error.
3.1
Identification of the worst-case Q-function
The robust worst-case Q-function of n. denoted as Q satisfies the robust Bellman equation Q (s. = T (s, a), Vs, a since the uncertainty set (PP) factorizes over s, a [34]. While these equations may seem intractable due to the inf in the definition of Trab: [12] showed that Too has a closed form solution in terms of the CVaR under the observed kernel P.
Lemma 3.1. Set T(s, a) = (A(s, a) + +1) Then, for any q S x A + R.
T s, a) = r(s, a) + (s,
| s. 7(1 A (s, a)) CVaR (s..a) (u(()) ) | s, a),
where uss') = "e'-n("' [a(s', 1iliss,d d')], and E, CVaR, are under the observed kernel P(- 8, a,.
Lemma 3.1 implies that Q identified via the following equation of observable distributions: Q (s, a) r(s, +> -(s, a) (s', m)) s, a)+ (ss a)) CVaRR (s', m)) s,a].
Under no confounding (A(s, a) 1), this recovers the classic Bellman equation.
3.2 Estimating the Robust Q-Function with Robust FQE
In this section, we estimate Q via an iterative fitting algorithm based on fitted Q-evaluation (FQE) [54]. Our algorithm RobustFQE (Algorithm 1) proceeds for M iterations with two main steps in each iteration i. First, in Line 5, we estimate the lower-quantile of 1=-) s, a. Here, we assume access to an oracle QR for quantile regression, which is a well-established problem, allowing for the use of various existing algorithms. Second, in Line 6, we solve the tractable robust Bellman equation in Lemma 3.1 with the CVaR term estimated by its orthogonal estimating equation with the learned quantiles [57]. By orthogonally estimating CVaR, we achieve second-order dependence on the quantile estimation errors from the first step. Next, we minimize the mean squared error using a [0, (1 "1.
general function class, Q C S A -
To enable convergence guarantees, we make two assumptions. First, we assume that the quantile regression oracle has specific convergence rate, which can be guaranteed under certain smoothness conditions [9, 14, 27, 28, 52, 60, 65]. Distributional RI. may also modified to learn quantiles of the next state value and have shown benefits in practice [21, 22] and in theory [5, 75, 76, 78].
5

---

Algorithm 1 RobustFQE: Iterative fitting for estimating Q and B-.
1: Input: Number iterations M, Dataset D size n, Q-function class Q.
2: Initialize 0 (s') O.
3: for i = 1,2..... .M do
4: Set D; D(ni, D(ni/M -n(i 1)/M].
5: On the first half of D,, estimate the T(s, lower quantile of (,_, P(: s.
Let 3, (s, a) denote the learned lower quantiles from the quantile regression oracle QR.
6: Using the second half of Di solve the empirical robust Bellman equation by minimizing squared prediction error for the pseudo-outcome:
1. + arg min minggn
q [D.1/2 (0s (s, 8') g(8, a)) where a) >
y (s, -
+ 7(1 - (s,aa)
x + (s,
10 (s',d') - - (5,
7: Output: TMo 3o.
Assumption 3.2 (QR Oracle). For any v ::d S + [0, (1 - --))-) let the true T(s, a) qqaantie of u(s'), ~ P(s, a) be denoted by 8 (s, a). Given dataset DOR. assume QR outputs estimates 3. with bounded &o error: for any 6, w.p. 6, || oo < ePaon
The second assumption is completeness under the robust Bellman T Completeness is standard assumption in algorithms based on temporal-differene learning and without it, fitted- - can diverge or converge suboptimal fixed points [45, 68].
Assumption 3.3 (Completeness), For all g E Q, we have Too E Q.
We note that the current proofs of [12, 59] require a stronger completeness: Taq E Q for all & E Q and feasible 3. We circumvent the need for the stronger "all-3" completeness by bounding model misspecification least squares regression with second order error in the quantile regression.
Finally, we express our bounds with the critical radius e a standard tool for deriving fast rates in statistics; see Appendix D.2 for summary. Also, we denote the standard concentrability coefficient with Cā = ||dd_//ad]]] Il standard and necessary quantity for OPE.
Theorem 3.4. Let E denote the critical radius of Q. Under Assumptions 3.2 and 3.3, RobustFQE ensures that for any ò E (0, 1). w.p. 1 5,
1 - Q lla, S (1-
CT = + eer (n/2M, and
(1- ( V. x NM + +11-2)-1 = + eTaR(n/MM, (n/2M, 6/2M)).
For parametric classes (e.g., finite or linear), the critical radius converges at the standard Ö(n 112)) rate. Due to the orthogonal estimation of CVaR, we benefit from favorable second-order dependence on erroR which allows for quantile regression to converge at slower Ö(n -1/4) 1/4) rates. The main disadvantage of this direct approach is that it converges at slow sub-v/n rate if = converges at
sub-vnn n,, e.g., ox converges
Ö(n 1//-1/44 114) rate if Q is nonparametric with metric entropy at most 1/t² [71]. In Section 5, we present an orthogonal estimator that is both robust to slower rates of Q and achieves semiparametric efficiency.
4 Robust w-Function Estimation with Minimax Learning
Before we present our orthogonal estimator, we study another essential nuisance function: the robust visitation density ratio, i.e., the robust u-function [2, 39]. In this section, we first identify the worst- case transition kernel U- in our uncertainty set (PP). Then, we propose minimax estimator [69] for the robust w-function, an important nuisance function for our orthogonal estimator in Section 5.
Identification of U- The robust transition kernel U- defined as the feasible perturbed kernel that achieves the inf in the robust Bellman equation Q (s, a) T (s, a). Let F- s,a)

---

Algorithm 2 RobustMIL: Minimax Estimation of w with a Stabilizer
Input: Dataset D, prior stage estimate Ç. function classes W, W.F, stabilizer weight À > == A (s, + (1 (1
2: Define weights < {= a, s')
-.0) 0J.
3: Output:
e = arg min max E, (s.
f(s, + B, ((1.
WEW
JEF
(s, ((, a))...
P(V-($) S 8, be the next-state pushforward measure of the robust value function V- Then, U- is a convex combination of the nominal kernel P and a reweighting of P by an indicator function.
Lemma 4.1. Suppose F- (s, 8,a) = T, where 87 (8(8, a) is the lower 7-th quantile of F- (. 8, 8,0). Then,
U- (s' s, PPss s, (s a) + (----)((s.o)--(((( (5)) - (s, S 0].
(4)
The proof strategy decomposes U- into its nominal and perturbed components, leveraging the primal solution of CVaR, [3]; we formalize this in Appendix E.2.
Identification of w- Using the identification of U in Lemma 4.1, now identify the robust w-function based on the Bellman flow equations in the worst-case MDP. The Bellman flow in the
robust MDP is given by d' 00 (s) = (1 7) (s) + (3)((d- U- (s a). where d d0000 (s)
was defined in Section 2. Thus, the robust visitation density, defined as w (s) == dd (+)/ar(s). satisfies the following moment condition for all f + RR:
[[w (+)](() = (1 Ba, (f(()) + > (8, Bea
(5)
where we relaxed notation and defined w- (s) wr(s) m(a 8)/v(a I s). As before, in the unconfounded base (A = 1), this result recovers the classic Bellman flow.
4.1 Estimating with Robust Minimax Indirect Learning
We now propose a penalized minimax estimator for w= that generalizes the Minimax Indirect Learning (MIL) of [69] to our robust MDP setting. Our estimator, RobustMIL (Algorithm 2), leverages a general function class W S A - E, to approximately solve the moment equation in Eq. (5). It does so by minimizing the difference between the left- and right-hand sides of the equation across sufficiently large set of adversaries Since U- unknown, we approximate via Eq. (4) by plugging in threshold Ç(s, a, 8²) in the indicator function to approximate the true threshold < a, s') = (s') - B7(..0) (8, a). This yields the minimax objective in Eq. (6), where we also allow for an optional regularization of the adversary's 's norm which can be useful for obtaining fast convergence rates.
discriminator class F C x +> IR.
We make the following assumptions for MIL [69]. The first a regularity condition that (i) our function class has bounded outputs and (ii) is continuously distributed around the threshold. Assumption 4.2 (Regularity).
(i) suPweeu ||w|| < oc; (ii) the marginal CDF of V (s")
3 (s, a). Le.. Fạy) = P(V (s') 3 ((s,a) (s, a) S y). is boundedly differentiable around 0.
next-value distribution is discrete, we can use the discrete form of CVaR and (ii) can be removed.
The second is that the adversary class is rich enough to capture all projected errors under the adjoint of the operator Tv f(s, := ylEy [f(s', m) s, a] - f(s,a). Assumption 4.3 (w realizzabbll and completeness). w E W and Ti- -W-) CF
We note that Assumption 4.3 is monotone in the function class size and can be satisfied by making the function class more expressive, e.g., increasing size of the neural net. Our algorithms are also robust violations in Assumption 4.3, which we show in Appendix G.
We are now ready to state the main estimation result for w- in terms of the critical radius (Ap- pendix D.2) of the function class.
7

---

Algorithm 3 Orthogonal Estimator for Vag
1: Input: Dataset D, number of splits K.
2: for k = 1,2,... ........ K do
3: Use data D \ D& to learn (q [k], , 3-,11) with Algorithm and w- with Algorithm 2
4: for [kk- JynKK]..... [kn/K] do vi = (5, 0ig 54,07
5: Output: Vd= -i=1 1;
Theorem 4.4. Let ew denote the maximum critical radii of the following classes:
9 = [(,[[(,,, (8, (f(s, a) ( m)),
G2 = {ss,a,'')) s') (w(s, a) - w (s, ())(()))) - f(s, f Under Assumptions 4.2 and 4.3, RobustMIL ensures that for any 8, w.p. 1 5,
T w 112 - w + +Iī
-o -
+ (lg(116))
As before, the critical radius W converges an Onn11/2) rate for parametric classes. Notably, our bounds degrade linearly w.r.t. the loe error in <- for estimating < For example, if ((s, s') = ō(s') 3(s, a) where 0, 3 are estimated with RobustFQE, then the Ç-error can be bounded by 0 c- 1l + 1 3 loc). We present the full proof in Appendix G, where we also present more general result that is robust to misspecifications realizability and completeness (Assumption 4.3),
Orthogonal and Efficient Estimator for Robust Policy Value
In this section, we propose an orthogonal estimator that is robust against errors in the nuisances (exhibiting only second-order sensitivity), achieves semiparametric efficiency, and enables inference. Our estimator is based on the efficient influence function (EIF) of V which is the canonical gradient of statistical estimand [67]. The adoption of EIFs for developing efficient estimators is a broadly employed technique in causal inference [16, 43] and reinforcement learning [35, 39].
We define the collection of nuisance parameters by 17 (w . The notation î indicates that these functions are estimated from data, while the notation 1) denotes their true values.
Theorem 5.1 ((Recentered) Efficient Influence Function). The (RJEIF of VT, is given by:
(s, a, a. = Vā, + w (s, (s) +pp P (ss a s': 3 A(s. - (s') (ss) (1- ((s. (1 ---00)))(ssa)))) where + (v=()) (1-))) -
Remark 5.2. When = 1, there no shift in the target environment, and the weight on the CVaR term is zero. The (R)EIF then reduces to the (R)EIF in [39] for regular OPE with an infinite horizon. As A + oo, the CVaR term becomes predominant, with the quantile 3 (s, a) taking extreme values. This yields the (novel) (R)EFF for the problem in [25], where the expected value term is replaced solely by a CVaR component in the Bellman equation.
The ER)EIF forms the basis of our orthogonal estimator. First, we note that EE[b(s, (s, a, s'; " )] is an unbiased estimator of V2, Furthermore, the expression for ( a, sn depends only quantities 4 3 which can be estimated from data. Thus, can cast the expression Elgh(s, a, s'; 17 as a statistical estimand to be learned from the observed sample. This suggests natural two-stage estimator that we summarize in Algorithm 3. In the first stage, we estimate the nuisance parameters ?) from the data with K-fold cross-fittin tross-fitting; in the second stage, these estimates are incorporated into the (R)EIF expression and we calculate the empirical average using the observed data. We summarize our procedure in Algorithm 3.
The nuisance estimation is detailed in Sections 3.2 and 4.1. The reliance the EIF confers our estimator desirable statistical properties including a second order bias due to the nuisances, meaning the bias has product structure with respect the nuisance errors. Thus, this special structure orthogonalizes away the dependency on Q errors which now only appear in second order. Furthermore, our estimator is semiparametrically efficient in the sense that under mild consistency assumptions, it achieves minimum variance among all regular and asymptotically linear (RAL.) estimators. We provide theoretical justifications for these properties in the next section.
8

---

5.1 Theoretical Guarantees of the Orthogonal Estimator
We now characterize the theoretical properties of our orthogonal estimator. We consider the K-fold cross-fitted estimator in Algorithm given by
Vi = + E (,,,,,") (bss, a, s1
where nuisances 1716 k E [K] are trained on all data excluding the htth fold D.. The following
theorem outlines the theoretical guarantees of this estimator:
Theorem 5.3 (Efficiency of Vi Let n.p: rh Thpp be functions of the same size n = (D] such
that (w .M Furthermore, assume that the regularity conditions in Assumption 4.2 hold. Then:
w S "n [|q - -gllp S Srh and [|3- B11p S for any k E [K]
VV 1z + pp(r,,22n0 n, + (1 + )2)
(Rates)
Furthermore, if n22 22 = op()), 22222, = on 1/2), 12 = op(n 1/4), o1()-114), and ri =
1/4)_ then Vj, satisfies:
Vn(Va, - -V,) V NO,,), E= Var s';77)),
(Normality & Efficiency)
Moreover, E is the minimum achievable asymptotic variance among RAL estimators in the nonpara- metric model for (s,0, 8') (the efficiency bound).
We provide the intuition along with detailed proof in Appendix H. The first part of Theorem 5.3 implies that as long as we estimate the nuisances at rates faster that n -1/4 then we can learn ViJ at parametric rates. The second part of Theorem 5.3 states that under mild consistency assumptións, our estimator attains the efficiency bound and is asymptotically normal. That means, for example, can construct asymptotically valid lower 95%-confiience bound VJ, by simply subtracting 1.64 times se = + E ((s.,.))DD (19(8, a, s'; f/ )9)//22 Then, we can be sure to have bound on the worst-case RL policy value, accounting both for potential environment shift and finite data. Finally, in Appendix J, we describe two settings when our orthogonal estimator remains valid even if some nuisances are inconsistent, which is a desirable guarantee for sensitivity analysis [23].
Bringing it all together. We can instantiate Theorem 5.3 with the nuisance estimators from the previous sections. First, use RobustFQE to estimate q and ensuring |/ - Q |2 S ( enrR) Under smoothness conditions (Lemma D.2), the L.2 guarantee for q implies an T. guarantee
for q which also ensures an Les guarantee for 3- This ensures max (ll - Q |0 || 3 oo) well-controlled. Then, we can set (s a, = q (s', kt) - 8 (s,a) and run RobustMIL for estimating w- By Theorem 4.4, its projected-T.p error is O(e + I| - Q- + -| 3 [l
Therefore, the final rate via Theorem 5.3 is ((E + +erā) =W + l - - + || 3 11.)
Empirical Evaluation
We now provide a proof-of-concept empirical investigation to validate our theoretical findings. We experiment with our proposed methodology simple synthetic environment. First, we discuss our environment, followed by our approach for solving for the nuisances functions 77 Then, we provide empirical results for our orthogonal estimator, and compare its performance to weighted or direct estimators using the Q or w nuisances only. The code for our experiments is open-sourced and available at https:: / //gtthub........t/
Experimental Setup We consider synthetic MDP with one-dimensional state and two actions, modeled after simple control problem with non-deterministic dynamics. The task is to estimate the worst-case policy value Vj, of fixed candidate policy 7t across four different constant values of the sensitivity parameter: A(s,a) a) 21,2,4,8).

---

estimator
Estimated Ve
0.8
0.6
0
Orth
0.4
0.2
Ms. a)
Mean squared error (MSE) true worst-case policy value
A
Q
Orth
T
.000240 + .000170
.002722 + .002666
.000005 + .000006
2
.004053 + .001329
.003584 + .002311
.003244 + .000600
.009799 = .005172
.013862 + .009228
.008721 = .002543
.006247 = .003980 8
.052643 + .050839
.005713 + .002730
Figure 2: Results of our synthetic data experiments. We show results for our three estimators on all four A values, over 10 experiment replications. Above: Box plot summarizing range of policy value estimates for each combination estimator and A, with Horizontal red dashed lines showing the true worst-case policy values V Below: Table summarizing the corresponding MSE of these estimators for the true worst-case policy value, along with one standard deviation errors.
We considered three methods for estimating the robust value Va
Q (RobustFQE); Direct method using the estimated robust quality function Q only.
2. W (RobustMIL): importance-sampligg method using the estimated robust density ratio x only. Orth: Our orthogonal estimator which combines the former two, as described in Algorithm
We performed 10 replications of our experimental procedure, where for each replication we: (1) sampled dataset of 20,000 tuples using different fixed logging policy ma: (2) fit the nuisance functions Q 3 and w: following the method outlined in Algorithms and 2 for each A; and (3) estimated the corresponding robust policy value Vi for all estimators using the fitted nuisances.
Results We summarize our results Fig. 2. We note that all of our estimators are consistently valid for all values of A in our experiment. Notably, Orth consistently has the lowest mean squared error for the true worst-case policy value. In particular, incorporating the robust importance-samppl weights improves the RobustFQE estimator Q, even though these importance-samplinng weights by themselves (as in W) are much noisier estimators. This is consistent with our theory that the orthogonal estimator is semiparametrically efficient and insensitive errors in the nuisance functions.
Full experimental details, including our MDP, target/logging policies, methodology for computing the true robust policy values Vž, and nuisance estimation, are provided in Appendix K. Finally, we also performed an empirical evaluation in the real-world medical problem of sepsis management using the MIMIC-III dataset [36]. We detail these results in Appendix I..
7 Conclusion
We consider the problem of infinite-horizon OPE RL settings when there can be unknown, but bounded, shifts the transition distribution compared the transition distribution generating the data. This can arise due to unobserved confounding, where observed transitions do not reflect the true causal ones, non-stationarity in the environment, or adversarial environments. We propose sensitivity model for such transition kernel shifts analogous to the classic MSM for static decision making, and provide theoretical guarantees for identifying and estimating the sharp (i.e., tightest possible) bounds on the best/worst-case policy value, as well as the corresponding robust Q-function and state density ratio functions. Our estimator for the best/worst-case policy value is orthogonal (insensitive to how the nuisance functions are estimated) and achieves semiparametric efficiency (attaining the best possible asymptotic variance). Finally, our estimator also supports inference, ensuring can derive reliable bounds for the robust policy value even with finite data.
10

---

Acknowledgements
We thank the anonymous reviewers for their valuable feedback and insightful suggestions. This material is based upon work supported by the National Science Foundation under Grant Numbers 1846210, IIS-2154711, CAREER 2339395, and by the U.S. Department of Energy. Office of Science, Office of Advanced Scientific Computing Research, under Award Number DE-SC0023112.
References
[1] Alckh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, and Xuezhou Zhang. Provable benefits representational transfer in reinforcement learning. In The Thirty Sixth Annual Conference Learning Theory, pages 2114-2187. PMLR, 2023.
[2] Philip Amortila, Dylan Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. Harnessing density ratios for online reinforcement learning. arXiv preprint arXiv:2401.0968/ 2024.
[3] Marcus Ang, Jie Sun, and Qiang Yao. On the dual representation of coherent risk measures. Annals of Operations Reseurch, 262:29-46. 2018.
[4] Jean-Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers under the margin condition. arXiv preprint math/0507180, 2005.
[5] Alex Ayoub, Kaiwen Wang, Vincent Liu, Samuel Robertson, James McInerney, Dawen Liang, Nathan Kallus, and Csaba Szepesvári. Switching the loss reduces the cost in batch reinforcement learning. International Conference of Machine Learning, 2024.
[6] Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference Machine Learning, pages 511-520. PMLR, 2021.
[7] Alexandre Belloni, Victor Chernozhukov, Ivan Fernandez-Va and Christian Hansen. Program evaluation and causal inference with nigh-dimensional data. Econometrica, 85(1):233-298, 2017.
[8] Andrew Bennett, Nathan Kallus, and Miruna Oprescu. Low-rank mdps with continuous action spaces. arXiv preprint arXiv:2311.03564 2023.
[9] Pallab K Bhattacharya and Ashis Gangopadhyay. Kernel and nearest-neighbor estimation of conditional quantile. The Annals of Statistics, pages 1400-1415, 1990.
[10] Matteo Bonvini, Edward Kennedy, Valerie Ventura, and Larry Wasserman. Sensitivity analysis for marginal structural models. arXiv preprint arXiv:2210.0468// 2022.
[11] Haim Brezis and Petru Mironescu. Where sobolev interacts with gagliardo-nirenbery. Journal
of functional analysis, 277 28644 2019.
[12] David Bruns-Smith and Angela Zhou. Robust fitted-g-evaluation and iteration under sequentially exogenous unobserved confounders. arXiv preprint arXiv:2302.0000 00662, 2023.
[13] David A Bruns-Smith. Model-free and model-based policy evaluation when causality is uncertain. In International Conference Machine Learning, pages 1116-1126. PMLR, 2021.
[14] Domagoj Čevid, Loris Michel, Jeffrey Näf. Nicolai Meinshausen, and Peter Bühlmann. Distri- butional random forests: Heterogeneity adjustment and multivariate distributional regression. arXiv preprint arXiv:2005.1 14458, 2020.
[15] Jonathan Chang, Kaiwen Wang, Nathan Kallus, and Wen Sun. Learning bellman complete representations for offline policy evaluation. In International Conference on Machine Learning. pages 2938-2977 PMLR, 2022.
[16] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21(1):C1-C6. 2018. doi: 10.111 12097.
11

---

[17] Victor Chernozhukov, Mert Demirer, Esther Duflo, and Ivan Fernandez- Val. Generic machine learning inference on heterogeneous treatment effects in randomized experiments, with an application to immunization in india. Technical report, National Bureau of Economic Research, 2018.
[18] Victor Chernozhukov, Carlos Cinelli, Whitney Newey, Amit Sharma, and Vasilis Syrgkanis. Long story short: Omitted variable bias in causal machine learning. Technical report, National Bureau of Economic Research, 2022.
[19] Victor Chernozhukov, Whitney Newey, Rahul Singh, and Vasilis Syrgkanis. Automatic debiased machine learning for dynamic treatment effects and general nested functionals. arXiv preprint arXiv:2203. 13887, 2022.
[20] Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision- making: ovar optimization approach. Advances in neural information processing systems, 28, 2015.
[21] Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In International conference on machine learning, pages 1096-1105. PMLR, 2018.
[22] Will Dabney, Mark Rowland, Mare Bellemare, and Rémi Munos. Distributional reinforce- ment learning with quantile regression. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[23] Jacob Domn and Kevin Guo. Sharp sensitivity analysis for inverse propensity weighting via quantile balancing. Journal of the American Statistical Association, 118(544):245-2657) 2023.
[24] Jacob Dorn, Kevin Guo, and Nathan Kallus. Doubhy-vaiiddooubly--har sensitivity analysis for causal inference with unmeasured confounding. arXiv preprini arXiv:21 2021.
[25] Yihan Du, Siwei Wang, and Longbo Huang. Provably efficient risk-sensitive reinforcement learning: Iterated evar and worst path. In The Eleventh International Conference on Learning Representations, 2022.
[26] Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. In International Conference Machine Learning, pages 2892-2902. PMLR, 2021.
[27] Anouar El Ghouch and Mare G Genton. Local polynomial quantile regression with parametric features. Journal of the American Statistical Association, 104(488):1416-422) 2009.
[28] Kevin Elie-Dit Site-Di--Cone Cosaque and Véronique Maume-Deschane Random forest estimation of conditional distribution functions and conditional quantiles. Electronic Journal of Statistics, 16 (2)x6553-6583, 2022.
[29] Dylan Foster and Vasilis Syrgkanis. Orthogonal statistical learning. The Annals of Statistics, 51(3):879-908, 2023.
[30] Vineet Goyal and Julien larity. Mathematics of Operations Research, (8811:2033226 2023.
Robust markov decision processes: Beyond rectangu-
[31] Oliver Hines, Oliver Dukes, Karla Diaz-Ordaz, and Stijn Vansteelandt. Demystifying statistical learning based on efficient influence functtion. The American Statistician, 76(3):292-304, 2022.
[32] Ronald A Howard and James E Matheson. Risk-sensitive markov decision processes. Manage- ment science, 18(7):356-369, 1972.
[33] Hidehiko Ichimura and Whitney K Newey. The influence function of semiparametric estimators. Quantitative Economics, 13(1):29-61, 2022.
[34] Garud N Tyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
12

---

[35] Nan Jiang and Lihong Li. Doubly robust off- value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652 222. PMLR, 2016.
[36] Alistair EW Johnson, Tom Pollard, Lu Shen, Li-wei H Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. Mimic-iii, a freely accessible critical care database. Scientific data, 3(1):1-9, 2016.
[37] Nathan Kallus. What's 's the harm? sharp bounds on the fraction negatively affected by treatment. Advances in Neural Information Processing Systems, 35:15996-16009 2022.
[38] Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. The Journal of Machine Learning Research, 21(1): 6742-6804 2020.
[39] Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. Operations Research, 70(6):3282-333) 2022.
[40] Nathan Kallus and Angela Zhou. Confounding policy evaluation in infinite-horizon reinforcement learning. Advances in neural information processing systems, 53:22293-22304 2020.
[41] Nathan Kallus, Xiaojie Mao, Kaiwen Wang, and Zhengyuan Zhou. Doubly robust distribu- tionally robust off-policy evaluation and learning. In International Conference on Machine Learning, pages 10598-10632. PMLR, 2022.
[42] Edward H Kennedy. Nonparametric causal effects based on incremental propensity score interventions. Journal of the American Statistical Association, (146556):45--56, 2019.
[43] Edward H Kennedy. Towards optimal doubly robust estimation of heterogeneous causal effects. arXiv preprint wVXiv:2004.14497, 2020.
[44] Amirhossein Kiani, Chris Wang, and Angela Xu. Sepsis world model: A tnimic-based openai gym" world model" simulator for sepsis treatment. arXiv preprint arXiv:1912.07127, 2019.
[45] J Kolter. The fixed points of off-policy td. Advances in Neural Information Processing Systems, 24, 2011.
[46] Navdeep Kumar, Kfir Levy, Kaixin Wang, and Shie Mannor. Efficient policy iteration for robust markov decision processes via regularization. arXiv preprint arXiv:2205. /4327, 2022.
[47] Navdeep Kumar, Esther Derman, Matthicu Geist, Kfir Yehuda Levy, and Shie Mannor. Policy gradient for rectangular robust markov decision processes. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL MLpXRrjpa6.
met/forum?id-
[48] Mark Laan and James M Robins. Unified methods for censored longitudinal data and causality. Springer, 2003.
[49] Giovanni Leoni. first course in Sobolev spaces. American Mathematical Soc., 2017.
[50] Greg Lewis and Vasilis Syrgkanis. Double/debiased machine learning for dynamic treatment effects. In NeurIPS, pages
2021.
[51] Shie Mannor, Ofir Mebel, and Huan Xu. Robust mdps with k-rectangular uncertainty. Mathe- matics of Operations Research, 1144:148841150) 2016.
[52] Nicolai Meinshausen and Greg Ridgeway. Quantile regression forests. Journal of machine learning research, 7(6), 2006.
[53] Volodymyr Mnih. Playing atari with deep reinforcement learning. arXiv preprint 131.::131 2013.
[54] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008.
13

---

[55] Hongseok Namkoong, Ramtin Keramati, Steve Yadlowsky, and Emma Brunskill. Off-policy policy evaluation for sequential decisions under unobserved confounding, Advances Neural Information Processing Systems, 33: 13:18889-10 18889-18831, 18831, 2020.
[56] Arna Nilim and Laurent EI Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
[57] Tomasz Olma. Nonparametric estimation of truncated conditional expectation functions. arXiv preprint arXiv:2109.06/550 50, 2021.
[58] Miruna Oprescu, Jacob Dorn, Marah Ghoummaid, Andrew Jesson, Nathan Kallus, and Uri Shalit. B-learner: Quasi-oracle bounds on heterogeneous causal effects under hidden confounding. In International Conference on Machine Learning, pages 26599-26611 PMLR, 2023.
[59] Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust rein- forcement learning using offline data. Advances in neural information processing systems, 35: 52211-32224, 2022.
[60] Jeffrey S Racine and Kevin Li. Nonparametric conditional quantile estimation: A locally weighted quantile kernel approach. Journal of Econometrics, 201(1):72-94, 2017.
[61] R Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distribu- tions. Journal of banking & finance, 26(7):1443-1471, 2002.
[62] Anton Schick. On asymptotically efficient estimation in semiparametric models. The Annals of Statistics, pages 1139-1151, 1986.
[63] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint (xXiv1707.00644 2017.
[64] Vira Semenova and Victor Chernozhukov. Debiased machine learning of conditional average treatment effects and other causal functions. The Econometrics Journal, 24(2):664-289 2021.
[65] Ichiro Takeuchi, Quoc V Le, Timothy D Sears, Alexander J Smola, and Chris Williams. Nonparametric quantile estimation. Journal of machine learning research, 7, 2006.
[66] Zhiqiang Tan. A distributional approach for causal inference using propensity scores. Journal of the American Statistical Association, 101(476):1619-163) 2006.
[67] Anastasios A Tsiatis. Semiparametric theory and missing data, volume 4. Springer, 2006.
[68] John Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffferen learning with function approximation. Advances neural information processing systems, 9, 1996.
[69] Masatoshi Uchara, Masaaki Imaizumi, Nan Jiang. Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.002981, 2021.
[70] Mark J van der Laan, Sherri Rose, Wenjing Zheng, and Mark J van der Laan. Cross-validated targeted
estimation. Targeted learning: causal inference for observational and experimental data, pages 459-474, 2011.
[71] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[72] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[73] Jie Wang, Rui Gao, and Hongyuan Zha. Reliable off-policy evaluation for reinforcement learning. Operations Research, 72(2):699-716, 2024.
[74] Kaiwen Wang, Nathan Kallus, and Wen Sun. Near-minimax risk-sensitive reinforce- ment learning with evar. In International Conference on Machine Learning, pages 35864-35907. PMLR, 2023,
14

---

[75] Kaiwen Wang, Kevin Zhou, Runzhe Wu, Nathan Kallus, and Wen Sun. The benefits of being distributional: Small-loss bounds for reinforcement learning. Advances in Neural Information Processing Systems, 36, 2023.
[76] Kaiwen Wang, Nathan Kallus, and Wen Sun. The central role of the loss function in reinforce- ment learning. arXiv preprint 11Xx:22409.12799, 2024.
[77] Kaiwen Wang. Dawen Liang, Nathan Kallus, and Wen Sun. Risk-sensitive rl with optimized certainty equivalents via reduction to standard rl. arXiv preprint arXiv:2403.06323, 2024.
[78] Kaiwen Wang, Owen Oertell, Alekh Agarwal, Nathan Kallus, and Wen Sun. More benefits of being distributional: Second-order bounds for reinforcement learning, International Conference of Machine Learning, 2024.
[79] Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Advances in Neural Information Processing Systems, 34:7193-7206, 2021.
[80] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathematics of Operations Research, 38( (18(1)1133188) 183, 2013.
[81] Wenhao Xu, Xuefeng Gao, and Xuedong He. Regret bounds for Markov decision pro- cesses with recursive optimized certainty equivalents. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceed- ings the 40th International Conference Machine Learning, volume 202 of Proceed- ings of Machine Learning Research, pages 38400-38427. PMLR, 23-29 Jul 2023. URL https: htapsss//proceedigg.. mlr, press/v202/nse xu2ddd html.
15

---

Appendices
A Notations
Table 1: List of Notations
S,A
State and action spaces.
A(S)
The set of distributions supported by set S.
di
The initial state distribution.
a)
Tolerance parameter for kernel shift at (s, a). Takes values [1, oo].
T(s,a) a)
T(8, a) I+A(s.a) [0, z)-
V=,Q*
Robust value and quality functions of the target policy Mt.
x(
f(s,, x) == En- a)]-
U=($ (s,a)
Robust transition kernel which attains the best- worst-case value.
Tu, To.
Bellman operator under U and the robust Bellman operators.
Jv
Ju fs. == (f mt) ss f(s, a)
(s,
The upper r-th quantile of V**)' and lower r-th quantile of V-(5), 8' ~ P(s,a).
The -ddiccuuneed average visitation m under MDP with transition starting from d1. d d0.200
(s)), (s,
Data generating distribution. v(s) marginalizes over actions.
w = ddt /av. This is valid both as a function 8 or (s, a).
as)
w(s, m((ass)
u(als)
24,x-
max(0, x), (i, æ) respectively, for R. x S Cy for some constant C. Empirical average over n samples.
x Zz
En
I|
L norm, (E))
f*
True (oracle) value of parameter or function f.
J.J
Putative value of parameter or function f-
Estimated value of parameter or function f.
B
Results for Policy Evaluation Under Best-Cass Perturbations
In this section, we present analogous results for the best-case perturbation under the uncertainty set, corresponding to the supremum case of Eq. (2). We derive a similar orthogonal estimator with the properties outlined in Theorem 5.3, following the same reasoning presented in the main text.
Q+ Identification and Estimation.
We present the results of Lemma 3.1 for T
(s, a) r(s, a) + > (s.a) s. al 7(1 A (s, a)) CVaR (s.a)) (u(s') s, a).
Next, applying Assumption 3.2 and Assumption 3.3 to T we derive from Theorem 3.4 for Q that:
1 - Q S (11-))-(() 6. + (n/22 and
[(1 z) 1+t (s1) Va S M (1- of + emra aomaa(n/2M660 (n/2M,6/2M)
# Identification and Estimation. We first state the identification result for U- as in Lemma 4.1:
ut a,a)/P(s s,a) = =A-'(s, + A "I (s') B, (s) 0).
16

---

Algorithm 4 Orthogonal Estimator for Vil
1: Input: Dataset D, number of splits K.
2: for k = J...... K do
3: Use data D \ D& to learn (qt-14,, (t.lk) with Algorithm and wtilk with Algorithm 2
4: for [[k- JinKK,.... [kn/K] do v,. (56s, ai s,,07*)
5: Output: Vaj 1 Ei=1 v
Then, under Assumption 4.2 and Assumption 4.3 formulated for U+, the minimax rates from Theorem 4.4 given by:
(T - w )12 Sex en + 11 - + vlog(1/0)/n.
Orthogonal and Efficient Estimator for V Let the set of nuisance parameters be denoted by n7th (w+ (-))))) Then, the (recentered) efficient influence function (R)EIF (see Theorem 5.1) for in V2, is formulated as:
(s, a,s')n))) = Vi + w ()) pt (s,a,,8;; B+) A(s, ass.a)='u*(<>>
,,t - (s, where
A(s, (o (B + to (o0() 3 (s)
Using this (R)EIF, the orthogonal estimator for V is presented in Algorithm 4. We now restate Theorem 5.3 for V
Theorem B.1 (Efficiency of Vr,)) Les app am hp.. r be functions of |D| such that
1/ (w (0++ - ='> I n.p l1ğ - --'lpp S Thp and [|3 - -3811g 1Ip S r for any E [K]. Furthermore, assume that the regularity conditions Assumption 4.2 hold. Then:
IV Vv, S Op(n"
0pmmm112) -1/2) Or,2,,22 22.2 + (r%,,0022 (1)
(Rates)
Farthermore, if r r2.2 0p(1), 22,22,.2 (112), 19, op(n 1/4,, and r ro
op(n-1/44 then Vá, satisfies:
Vn(Vá, - Va.) S N), == Varlb(ss a, ((
(Normality & Efficiency)
Moreover, E is the minimum achievable asymptotic variance among RAL estimators the nonpara- metric model for (s, "s,a,'') (the efficiency bound).
C Additional Related Works
Robust MDPs. There is rich literature Robust MDPs [30, 34, 51, 80] with s, a-rectangular uncertainty sets, but these foundational works assumed knowledge the transition kernel. Recently, learning-based robust MDP algorithms have been proposed for uncertainty sets under the total variation [47, 59] and more generally Lp balls [46]. These Lp uncertainty sets are additive in nature, i.e., the adversary adds or subtracts vector in the lp ball to P(- a), whereas our uncertainty set is multiplicative in nature, i.e., the adversary can multiply or divide a bounded factor and is more commonly used in causal inference to model unobserved confounding. In the contextual bandit setting, [41] also derived efficiency bounds for robust OPE where both state distribution and reward distributions may shift their work is however restricted the one-step bandit setting while our full RL setting is more challenging.
Risk-Sensitive RL. Risk-sensitive RL is the problem of optimizing the risk measure of cumulative rewards [32] and is tightly related to robust MDPs [20]. For example, as we proved in Lemma 3. 3.1, the MSM uncertainty set is indeed equivalent risk- sensitisi RL with the dynamic risk measure AE + (1 A) CVaR,. We note that efficient online RL algorithms have been proposed for similar measures [25, 81J. Static risk-sensitive RL also modifies the Bellman equations in an augmented MDP [74, 77]. Our focus is on deriving the optimal off-policy evaluation estimators for the problem, which involves a different set of challenges such as deriving the efficiency bound and ensuring sharpness guarantees even when nuisances are estimated slowly.
17

---

D Additional Technical Details
D.1 Higher Order Norms via Smoothness
For any R+, define [æ] as the greatest integer that is strictly less than æ, and let and {z} = x- [ represent the fractional part. Thus, we obtain the distinct decomposition = [ {x). where [a] N and {z} E (0, 1].
Definition D.1 (a-smooth functions). Given E (0, o0) and X S IR., f: X R is a-smooth function if (1) the mixed derivatives up to [a] -order exist and are bounded; and (2) all |a orddr derivatives are {o} Hööder continuous [49].
Lemma D.2 (I. Bound for a-Smooth Functions). Let f X -> R,X C I be an a-smooth function as in Definition D.I. Then, if X is R a half-space or bounded Lipschitz domain in R there exists constant C such the following inequality holds:
11 S <CISIP part
Proof. This lemma is direct application of the fractional Fagliardo-Nirenheer interpolation inequal- ity (Theorem [11]) from the functional analysis literature. For more comprehensive exposition on this result, see Appendix A.I in [8].
D.2 Localized Rademacher Complexity and Critical Radius
Here, we recap the localized Rademacher complexity and critical radius which a standard complex- ity measure for obtaining fast rates for squared loss [72]. Let G be class of functions Z - IR Given n datapoints 21, .,.....9........................ Zn. the empirical localized Rademacher complexity is:
Rx,e, = Eg
sup LeGG-laall
Σ ciglz))
where Eg is expectation over n independent Rademacher random variables σ1, o..... i.e., E. [. = 2t Eo Note that when & = oo, there is no localization and RR (oc, 9) reduces to the vanilla Rademacher complexity. Let C' == sup llg|loo be the envelope of G. Then, the critical radius of & with n, called En, is the smallest that satisfies R, (E, e//c.
Unless otherwise stated, we will posit that G is star-shaped: there exists go E G such that for all g E G and [0, 1). we have ago (1 a)g E g. If not, we can replace by its star-hull, iee. the smallest star-shaped set containing G. We will also posit that G is symmetric for simplicity.
The critical radius is well-studied quantity in statistics [72] and also recently in RL [26, 69]. For example if has d VC-subgraph dimension, then w.p. 1- 8, En O ((Vllogn/n) For nonparametric models with metric entropy at most 1/t the critical radius also be bounded by On ((n=11(mmx(++3322)) [69], e.g., is O(n -1111/4) if =
E Proofs for Identification Results
E.1 Identification of robust Q
Lemma 3.1. Set T = (A(s,a) a) + +1 Then, for any q S RR
Tooa((8 a) = r(8, + - ((v())(((()) a. 711 - A- (x,a)) CVaR (().a) (u(s)) s,
where u(s') Ee'nn((e))) lg(s' d')], and E, CVaR, under the observed kernel P(. s,
18

---

Proof. Consider the uncertainty set in Trab where the constraint on U (Eq. (1)) can be rewritten as:
(' (al.a)-A--4 (x.0) A(s,a) - (s,aa. 0 <
((a)
Therefore, we can write (s's 8, A (s, (e.
Pss s, + (1- A-) s, where Thus, the constraints G are that G(: a) << S A(s, a) + Setting T(8,a) = M(E,0)II we can apply the primal
define G(s' s,a) U
1-A [a.a]
P(- 8, a) and || a
dG(e'ss.a
form of CVaR [3, 24] to obtain
inf aati)aa) GEP: Ger-laatioo dP(isaa) ST.
Eals((')] CVaR (e.a)) s,a].
Therefore, the supremum in Trab can be expressed as A (s, a) times the expectation under nominal P and (1 A (s, a)) times the above CVaR expression, which finishes the proof of the case.
For the + case, we can simply use sup instead of inf and upper CVaR instead of lower CVaR.
E.2 Identification of robust kernel and visitation
Lemma 4.1. Suppose P- (- a, = where (7, is the lower T-th quantile of
F- 8,a). Then,
U-8 (8 a.a) 8, = A
+ -1-A A (ss a) ([[[[[[S)) (8) I[(V B7 (s, a)) - 0]. (4)
Lemma E.1. Fix any v S + R and define the pushforward F. s,a) P(u(s)) S s.a). Suppose Fo (.((la)))))))) (s, 5,a) + ( - 7), where Bt,r, is the upper/lower T-quantile of F.. Then, suPueu(P) Bu(v(8') 8, E Exrut [u(s'] and inf By (u(s)) s.a) E (ea) where
(s' s,a)/P(s s, = =A= (15==) )r(s 11( - 8 (s, 2 0j.
Proof. We start with some intuitions. First, if the CDF of u(s') is differentiable (3 a), then CVaR (u(s') s, E[((s') f(8) 37 as, s, a] and the result follows immediately from Lemma 3.1 by noticing that the form of U exactly recovers the convex combination of expectation and CVaR. Alternatively, one to obtain the result.
the closed form solution of the primal CVaR as derived in [3]
We now provide a formal proof. Fix any 8, and let 7 788 Fix any function v(s)) E R. We want to show that the worst-case U- arg maxusu(P) By (o(s') 8, has closed form expression as shown in line 725. By the proof of Lemma 3,1 above, we can rewrite (+'s' s,a) Ps) | s,a) + +1 A (s, a) (s' s.a), where G+ Sr (ss.a) EE [u(()s))]. Thus, it suffices to simplify G+. To do so, we invoke the premise that the CDF of v(s") is differentiable at B3,, i.c. (o T.F. (s, |s This implies that the CVaR is exactly the conditional expectation of the 1 - T(s, a)-fraction of best outcomes, i.e. CVaR (u(s') s, a) E(u(s') v(s') (s. a). a). which in turn is equal to r E[uu(s))[[ 2 3 (s, a)] s, a] Thus, G G* s,a) = P(s' ss, a.)[(((((') 2 3 (s, a)).
arg maX
This concludes the proof for the case. The proof for the case follows identical steps.
F Proofs for Robust FQE
We prove more general result with approximate completeness, which shows that Theorem 3.4 robust approximate completeness.
Assumption F.1 (Approximate Completeness). max mingee [|g -etarglle S EoComp.
19

---

Theorem F.2. Assume Assumption F.I. Under the same setup as Theorem 3.4, we have
q - 1= 2 (1 (1- (VC) (5 + #acomp) +
and
Vit - (d) 9x 11, Ti]l S x + I- (V CF (= + #ccomp)
Proof.
Let U denote the worst-case kernel that satisfies V (1 Bd V (s1). Then,
Vi (1 Bd, O ($1, Tt) E), (V (s1) qK (1(1s
- (Tu²t @x a) 9x a)l
(Lemma F.3)
max 1=
Tut Th 11a + k/222
K/2
(Lemma F.4)
Consider any k= = 1,2,... By definition of U we have
T To 2k -laggn
(by def of U+)
d
where (5,s a) is the true quantile of 0 (s'). Denote gf == T and let 3t be the true upper/lower quantile of -h-1. 1. Recall the population loss function is
Lx = (1 as) -
( = r(s, a) + + (s,
+1(1 A (s.ss)) + (s. ((s,a)) The empirical loss Lu(g, 3) is if E is replaced by En. Note that To = arg mingee La (g. Br).
Nonparametric Least Squares with Model Misspecification. We will directly invoke [72, Theo- rem 13], which gives a fast rate for misspecified least squares with general nonparametric classes. We now bound the misspecification. Recall that at the k-th iteration, our regression Bayes-optimal is 2x (s, a, s')
ElyA"
s. TB, 0 a). By Lemma H.3, we know this is close to Tøg qh 1 (s, a) with
second order errors in 8: for any we have
T 9h-1
T
9k
< 1 Bille.
Av
Finally, by approximate completeness (Assumption F.1), there exists 9 E @ such that [[T ÿh- (s, gll < Eacomp- Putting this together: for any k, there exists g Q such that
lig - Tn a) l) S |1g Ts: Tn (s,, alat +
To, Th 18,, a) la
V EaComp + 1 11.
Therefore, [72, Theorem 13.13] (and concentration of least squares) certifies that:
Tz 9x-
S V
(EOcomp + En) + 11 1
1
Therefore, have proven:
< 9k -T 9h 1at latt
+1| Q=- - -
ik 0: 9k
9x dt
::
/ c# (Eacomp + tex) +13x 12..
This concludes the proof.
20

---

Lemma F.3 (Performance Difference). For any æ,, transition kernel P, and function f: x A - R. we have
V - E, [[(,
1 1-7 R (Tpf(s,a) - f(s,a))
Proof. See Lemma C.I of [15].
Lemma E4 (Unrolling). For any transition kernel P, and functions S1. J.......KKK S A R +_
satisfying fo(s, a) O, we have [| Tp fx 1a S I- max =12 115 TB f 1l.7 x/22
Proof. See Lemma C.2 of [15].
G Proofs for Robust Minimax Algorithm
Assumption G.1 (Approximate W W-realizability and completeness). Assume the following hold for
W and F:
(A) Approximate realizability: min Jueeew/lJJy-n (w=======-- w))l2 S @WReal;
(B) Approximate completeness: max minser|ls To (w -= S @WComp
We prove a more general result with approximate realizability and completeness, which implies Theorem 4.4 that is robust to misspecification in its assumptions.
Theorem G.2. Under Assumption G.1 and the same setup as Theorem 4.4, we have
1T w+) S se + +1 - + / 1og(1/0) + EWReal + WWoomp
Proof. For this proof, we focus on the worst-case kernel P of the form (=
P(s'[s.a)
(s) a)T s') s 0] where (*,s, a, 8') (- - g (s, This corresponds to the pure CVaR case of T the E part is identical standard non-robust RL kernel U+ can be handled similarly. Let P(s' s, a) denote our estimated robust kernel, which satisfies P(s' P(s' P(.' --- =>, s') s 0J. where Č(s, a, is the given prior stage estimate of ("(),a,8'== (s') (s,
omit it. The best-case
The key and only difference between our Algorithm 2 and the MIL algorithm (mmi)) of [69] that our next-state samples are importance weighted with g (s,,, a, s'), which is the density ratio of the estimated robust kernel (ss' a) and the nominal kernel P(s' | a). Note also that (= a, s') S (s, - a) co, and hence [S,, a, (ss))) Pe.am..""PPP..a Lf(ss) S Vlog(1/6)/n w.p.
[f('')]
1 5. Therefore, up to O( (loooo(//8)// errors, Algorithm can be viewed MIL applied to the MDP with kernel P.
To invoke the result of [69, Theorem 6.1] (in MDP with kernel P), we need to show that its assumptions met by bounding the model misspecificationn, i.e., Eq. (6) and Appendix C of [69]. Note that these misspecifications are w.r.t. the MDP with kernel P. since this is the MDP in which we're applying Theorem 6.1 of [69]. Specifically, the two errors we need to bound are, (A) approximate realizability: еΛ = min ( - w))ll; and (B) approximate completeness: ē = max minser || Jp(w w wp)lla where recall that Jp is the linear operator defined as Jrf(s, a) == ?EP[f(s', m) s, f(, a) and T.p is the adjoint.
21

---

Bounding misspecifications by || - 1o Since (" a, has marginal CDF that's boundedly differentiable around 0 (i.e.. (ii) of Assumption 4.2), [37, Lemma 3] implies that (*(s, a, a') satisfies a 1-margin (Definition H.2). Hence, Lemma H.3 and the continuity of (* a,,) 8') implies that
Pr Pr( 5 {) (T)))))) s s))
= =Pr( a, - 0] [[T (0, #0) 2 11ooo.
Thus, for any v: S + R.
(Ep-EEp E - (u(()) 8, all < 7 (s) s ( 5)) S 0)) |v(''))
2 |0l|oc Pr {[ a, s') s 0)
x |0||=|1 - 100
or cquivalently
EllPr 13, a) - | a, S 11 -
(7)
Equipped with Eq. (7), we can now bound the following two types of errors: (i) (f, (Tp. - -p))))
and (ii) (wp- wp.,h) h). where f.g S x A - and h - E, and Tp and wp are the Bellman operator and visitation density of target policy Ti in the MDP with kernel P.
For (i):
-pp)))
Ep)lo(s' m)) s,a]]]]
S <Bl Ep)]a(s' m) s.a]
2 [11ffl=oll((=<m)ll))) -5- loc
For (ii):
(w wp., h1
[(( wp. (s))
o/ d dr- TV
|/
--7 Edp- || s,a) P- (s,()l
(Eq. (9))
x C1
|x
1 1- _ 8, -
7
(Assumption 4.2(i)
x C11hllo
1 11 -
?
where C' ||dd" /dullo < <0.
For approximate realizability (Ex): for any W, we have
[T - w)ll2
I [[] - Jp- ((w (wmp-w)lez + 1| (wp wp- )112 + [Tpp (w* -w]l2
(wp -w, (Jp - -Jp- }91) + (wp wp. Jp. + +11Tp- (w- - w)ll2
$ [6 lol + 1Jpp (w* -w)-ww) w)l2
where 91 = ((Jp. Jp)'wu - w))/ll( (Jp. Jp)(wu - w)ll2. 92 = (Jp Wp. T/p (wp Wp-) )ll2- The last incquality uses (i) and (i)) with the fact that llg ol 00 and ||ga| lo < 30 as the w terms are bounded by our premise. Therefore, taking min over w and using Assumption G.I, we have A & I 5* ol + EWReal-
For approximate completeness (En): for any E W and E F, we have
|| Jp(n0= w
< |l - Tp. (w - wp- )12 + |[Jrr Jp)(ww-wr>>lb + 11Tp (wp - wp-)ll2
$ |l - Jp. (w - )12 + 11 1*1ooo,
22

---

for the same reason as as the error terms are the same. Thus, EB S 115 100 + WWompp
In sum, we have shown that the misspecification is at most O(II 50 + EWReal + EWComp). Therefore, [69, Theorem 6.1 and Appendix CJ ensures that w.p. 6, our learned satisfies,
5 wp)le S sew + 11. 1*
EWReal + WComp + vlog(1/8)/n.
Concluding the proof. The final step is to translate the above guarantee to 11Tp.. - wp The following shows that the switching cost is O(Il - 1=)) as before:
11 (ū up. )ll
- [[[Tp- - Jp) - wp. Ill + 11 w 1ITp(pp 11 - -ef:---pp-111 up
X cw + 11č 10 + EWReal + @woomp + vlog(1/8)/n.
This concludes the proof.
Lemma G.3 (Visitation performance-differeeee Let P.U - R. be non-negative measures, which should be thought of as transitions in discounted Markov chain. Assume U satisfies Ee (s' 8) S Define dy (1- Σ h- d'i where di Je1.22...,e-- (1()))(($2
.1)... Us 8h (a-1)ds1h-11 Assume the same for P.
Let F C S - IR be a function class that satisfies f E F - g(s) (f E F, i.e. closed under projection with P. Then, define the integral (probability) metric P| U| == supjer(EEp Eu (s))) Then we have,
||dp - d 5 7 Edtel P(-|)) ()]()))))
(8)
1-7
Proof. Recall Bellman's flow, which dp(s) (1 -(s-))d{ss) + -Egddp P(s (3). Fix any F.
The initial state distributions cancel, so we have,
[pd Eayy (+))
/Bandd B.r (1) [f()] - BEzdd B ((3
< BBgdd E, Pa- [s()) - -Rando E [[
+ TT P( [s])] 7TEadd E [s))
< (Bzndr Ez ((-.))))))) [s)] + BBadde (E (
Thus, taking supremum over F. we have
|p du ||5
//sup)
(Ezndr Egndd B() + Elgdd supl (BonP())) - E [f(})]] feF
feF
=>|ldp - du BB || P(: 33) - U(: (3)
(F closed under P-projection)
Rearranging terms finishes the proof.
If F is the class of functions with || S 1, then this recovers the TV distance, which gives,
||dr dy Il < 7 Edg P(- 8) U( s)]TT.
(9)
This generalizes Lemma E.3 of [1] to infinite horizon.
23

---

H Proofs and Additional Details for the Orthogonal Estimator
H.1 Intuition for Theorem 5.3
We provide some intuition for the results in Theorem 5.3. Consider the V- bound and let us decouple
the indicator I [o(s') [(s, a) I 0] that appears implicitly in the (o (s') 8 0--0--8s000 (s) notation
of Theorem 5.1. We augment the set of nuisances with Ç(8, a, 8') = (5") B (s, a) such that (8') (s,
[5(8, a,s') S 0j. We state the following lemma (which we elaborate upon in Lemmas H.4 and H.5 in the Appendix):
= (w (8') - 3- (s, [))TT
Lemma H.1 (Double sharpness with correct (*), Let (Elubs,, s':qq. w, 3.(*) ) be the expectation of (s')
the (R)EIF with arbitrary nuisance set (w, q, 8), but where the indicator [[(e[[s') S B (s,a))
has been replaced with the correct indicator T[(* (8, 0, 8') S 0). Then:
V Elpb(s, a, s'; w" (²,, (s a, a,s's s':q''' w, B* .(')
This lemma implies that if 3 (5*)- and Ç = C", then the estimator Vi, has a property known [24] in and w, meaning the bias vanishes when
as "double-robustnes either q or w is consistent. Moreover, the convergence rate would be (p(" This condition holds provided that B and Ç are correctly specified. However, estimation errors in B introduce an additional Op ((rH,co)² term, reflecting that / is first-order optimal for the CVaR component. Additionally, discrepancies between Ç and ( contribute an extra Op ((r9, to the error. While this discussion gives some insight into how we achieve the results in Theorem 5.3, we provide a a rigorous analysis in the next section.
[43] or "double-sharpnee"
H.2 Preliminaries
For this proof, our focus will be on Va, The argument for V is analogous, following symmetric approach. To improve the clarity of our exposition, we will omit the and r indices, assuming their presence is clear from the context.
For simplicity, we assume that is multiple of K such that Kng, where n is the size of fold. We let En,, E& denote the empirical averages over the entire sample and the 1.th fold, respectively. Recall that we use f (w, q, 3) and nf = =ww,, gg, f8*) to denote the estimated and oracle nuisances, respectively.
We further suppress the dependency on 8, a in and r and we write the term in Theorem 5.1 as A(s, a))-)
We justify this by noting that the analysis holds regardless of whether À and depend (10) Sometimes, it will be useful to decouple the indicator 1 [u(s') - B(s, a) < 0] implicit in the definition of p. In this case, augment the set of nuisances with ((s, s') v(s') B(ss a) and write p
p(,, a, 8 v, = (1 A)e(s") + ( a) + + +
p(8, a, 8 v, 3, = (1 -))(s'') + x(3(s, a) + (v(s') B(s, a))l [(8 a, 8¹) s 0)). (11)
Similarly define (1: w, q, 3, with the (;,,B,C)
H.3 Auxiliary Lemmas
Definition H.2 (Margin Condition). A function f X' + R of some random variable is said to satisfy the margin condition with sharpness E [0, oo] (or more succinctly, an a-margin) if there exist a fixed constant e > such that
Vt > 0: P(O < (x) < t) S at
If fXX either zero or bounded away from zero almost surely, then f satisfies an infinite margin, i.e., a [37, Lemma 2]. If f(X) is continuously distributed in a neighborhood around 0, i.e
24

---

its CDF is boundedly differentiable on (-e,0) U (0, for some E >> 0, then f has 1-margin [37,
Lemma 3].
Lemma H.3 (Margin Guarantees). For any f X + I satisfying o-margin (Definition II.2),
p E oo], and any + R. the following statements hold for some constant C > 0:
gllp p(+0)
( 0] - -[(()) ())(x))) - C
(12)
(X) S 0] + [I) - 0), f()) + 0J - C
glb p+0
(13)
where I1-11p is the LP norm and we set oct / x = in the exponents.
The proof Eq. (12) for any p [1, oo] and of Eq. (13) for p = oo given [4, Lemmas 5.1 and 5.2]. The proof of Eq. (13) for < oo is given in [37, Lemma 5]. Lemma H.4 (Sharpness with correct q² and (*). 1, ( (is s': w. u.q, 3) an unbiased estimator of Vš, when q" = 8", i.e.,
(1 - 1 on (s1) Elb(s, a, s' q", ,+)]
Proof. Since q" and 5* are correct, the robust Bellman equation holds, and so for every a
B A)v (s') X(8* (s, (1" f (s, a))-) 8, a] 0.
Thus, multiplying by any w does not change the fact that the debiasing term in &i has expectation zero. Since we have v*, the first term in is exactly the estimand, which concludes the proof. O
Lemma H.5 (Sharpness with correct w and (*), &.2 (s.,,,)) b(8, 8'; ",,g B, B,C) is an unbiased estimator VJ, when w w", = L...
(1 - 7,, (81) = -E/((s, "",
Proof. Let P denote the robust transition kernel and let d' denote the robust visitation measure under n, which satisfies: for all functions f.
Ex. [f a)] = (1 - 2),, f(s πT + +.
Since (* is correct, for any 8,8,0 a, we have
Ex-P(ss)) A)u(s') + ( - -(,)) (110, =0)) -Eg~P((.)) [1 A)o(8)) + Ar A []]
= -Es-r<sa [u(')],
(Lemma 4.1)
where in * we used P() That is, for all function f. we have
s 0]) = B(s, (1- = 0.
+ (1 - Ea (s1) + E[w" o B,C* a(s,a))]
(1 - 7) Eu, (11) + E, Eg Ir(s 7, - a(s,a)]
Eg (r(s, a)l + (1 - (00-)))2 Ea, u(s) + E a.d (s. [u(s')] g(s, o)]
Ex (r(s, a)]
(robust Bellman flow)
(1 (1-7) Va,
This concludes the proof.
H.4 Proof of Rates
The estimation error is given by:
1 K
D4 - Vj,
Exlb(s, a, 8'; Vū, <
Ealw(s,a, Vd,
K
K
25

---

We wish need to bound
E& (s, a, s': [ - VV - We have that:
[x(p(s, a, [ Va - [x a, s | Blyb(s, a, si ( + Bi a, s1 1/2)
The first term is (1/2) by the CLT. We are now interested in bounding the second term: n [s a, 8 7) V.
(14)
where we dropped the [k] indicator without loss of generality. We further decompose e = into two error terms, ε and EB, as follows:
E 7 = E pb 87 0.
0] E
Vbs f a s w 3,5
(Lemma H.S)
ph a 3) - E
(e4)
E (s, 3. E (s w ,BC
(E
Bounding A: Error from the incorrect indicator Ç.
(s, EA = 7AT - Bisss a) ((65)) - B(s.a)) (u - - ( s =0)
- Cy>T ( (6(s)) - 3(s, a)) (1 ((s') - ((s 20 -1 (3. a) s =0)
(Assumption 4.2)
$ {B(0 B(s, a) a)) (7(})) (1(56))) (
a) s s0] - -[0)())) (s, s0)
We break these terms down as follows:
E (0(s') A(. a) ((ss))))((s s -106) (100)--00000000000100000000000)0
-(( (1)))) (())) 20 -100
(Ei1)
+ +B(0(5') - - ((s) (I(()))
B(s.a) Is' - (s, s 01
(5
We first bound e₁¹- Assumption 4.2 implies
(3, a)l = 0)= 0, where d' < 1 is the min of 1 and the given neighborhood of zero and c" 2 1 is the max of 1 and the bound on the density in that neighborhood. This implies a margin condition with a 1 and c=/
P(O (s') - 3 (s, a)l S t) S d't, Vt (0c'),
We can instantiate the first part of Lemma H.3 with and obtain
= -(X)=
-
2g
E (s,,)) 6(8') + 3(ss
FtI
< - + 5(5, | -
-) (3,
#
To bound eg, first write
- - -00) (1000
| ((((s)) - -(.) (1 [8(6') -1(6())-
B(s, B(s, 50
- s 0))
- 50
s0 #1
(s, s 20) (0-1)/p
(Holder's inequality)
26

---

We can bound P -
- B(s, so] * #1(o*(s') (²),,))
=0) =0)
using the second part of
Lemma H.3 such that
22 x (((6) B(s,,)) - ()06))+8(s000)) (s,
(0(60) 3(s)0))v-(6) + (s,
p
= ||(06)) ((),a) - (s)) (s, -
s 110(ss) o (5))l + |5(5,a) (8,00) 2|z
Putting the of and 5 together, we have
A S (|((5') 0² (5))) + ||(5.0) - -8, a) -
(when E [1, oc))
- (s') + []0 -3-00,3))
(when p o0)
Bounding " Error with correct indicator but wrong nuisances, Now we focus on bounding
EB (1 - 33c)
- ((s
o))
-B(ū(s,)) - (6dt))))- (s.0))
((((s, ( Tiddsa)-ww(ssso(((ss0----a--- -
(Lemma H.4)
= =B(ū(s,a) w -60 (, - -:
In the Lemma H.4 step, we used
(1 Ed, (s1) El (1 (1-7)Ba, x -M) (8)).
Finally, note that
p(s, - p(s,a, )
= (1 -1- (11)))6(6) - + (10)0)=)0000++""0000000001111100
Due continuity of the CDF of (s') at (s, a) for all s, a, we have Pr( (s', s. <0 s. = and so the last term vanishes. Thus, we' Therefore.
we're re left with quantity that is at most X (0(s') - ( (s')).
S E(0(s, a) - -
w- (s, (Jv= (7(, (T==())))))) -0 ()))
< 11 (To - 22) q" 1|2.
(Holder's inequality)
Putting everything together, we obtain the desired rates:
V2, 12 00 1/2) |T (ū- w" 1l2ll6 q" 122 + 110
v*
28, + 3
= 0ppnn-1p0 + O, rr + (r 3 + (rā,p)) 1
2p
(when E [1, oc))
50p(m 1/2) + 1T (w 112110
q- 1|2 + 1 x* 11 2 + |
gr 2
=0 + (r + (r2,00)2 + 32)
(when p o0)
27

---

H.S Proof of Normality & Efficiency
In this part of the theorem, let:
1 K
Va.
K B,'""s
Then, we can write the following equality:
vn(Va. Vi = (Va - Va.) + v V - Vaj
SN((,
The second term converges in distribution to to (0, Σ) from the CLT and the fact that v is the efficient influence function. Thus, it remains to show that the first term is (1)) We decompose the first term as follows:
n
Va(Va - VV,)) = Vl
B[ 81 - ((
(15)
K
1 (E [V (s, as,
(16)
In Eq. (15), we have that [Bbb(s, a, 8 7( (s, a, s'; ]]] is bounded as in Eq. (Rates). Given the theorem's ss assumption about the nuisance rates, this term is op and Eq. (15) is (1). We now seek to control the E term Eq. (16). Letting Dj represent the samples in the 1thh fold, we leverage sample splitting show that the mean of Ex DD is 0:
ElER|
R
E [E (s) s,; (i)) (ss a, s' s':n")] Blpb(s, s' (1) (s Dal
where we consider (76 fixed with respect to the second expectation. The result follows from the fact that 7l does not depend on Dr. Then, we can invoke Chebyshev's 's inequality to obtain the following bound:
Ek Varle* Dx 2 Dr
1 2
P
S
Ve >0
Thus, we have shown that EK Dr Op(rree D211/2) On(n-1/3E((vi a,
s'; s': (ss a, )2 D2). Here, used the fact that пи n K (the size of D2)) and that K is fixed integer that doesn't grow with n. Moreover, & has conditional mean.
For the remainder of the analysis, we leave the conditioning on Dx implicit for simplicity. To bound E[(v(s, a, s': (() - (s,,, a, ")² Dx = [| a, ( (ss a, 8 17" 112, we use similar
notation and techniques in Appendix H.4:
(,, a, a'; H ((s a, s'm 112 10(s, s' s' 3) ass B.C. +ll0s,,,,8' 6 3, (*) - wis a 8i w", 3" 5,,((""
(01)
(02)
where we invoked Cauchy-Schwarz for the L2 norm. We bound 02 as follows:
02 S 11 a, w. 3) uss 0 3. 12
(02a)
11vb s': @ B, " 0 "''']
(72b)
(1b - v,,, w 8 <2)]l2
(02e)
< 1 00112 + 71 -|
||0||2117 7
921l2
(02a)
- 6- -i
(02))
|| " [|] | -8"112)
(azz)
28

---

Given our rate assumptions, our boundedness assumptions for wÚ the implicit boundedness of q², v"" w" , as well as the ordering of the L2 and Lo norms, 02 is (1)). We now bound the oi term:
02 = - ((ss)) - ()) B(s a)) 1 [10) = (s.
There are two cases in which the difference indicators is non-zero:
((s') - 3(s, a) and v²(s)) > (s. = 1[0(s') - B(s, = = 6(5') ((s. a) and v² 8 + l[((s)) ((s,a)] - [[v (s,a)) --
In the first case, 0(5')
(s)) 0 and thus
((6(5') - (T ( -(0))
In the second case, T(5') (ls.))20.((66))00 and
[(0(s') - -(s (I(((() < -1s. (
Going back to oi we have:
02 S 7 0| 3(s, 5 o² (s'))l1
1 02112 + -13 12)
By out theorem's assumptions, this term is also (1). Putting 0₁ and together, we have that [lyb(s, s'; a, ( (s, a, s'; 77) is (1) and D2 is (p 1/2). By the bounded convergence theorem, this implies that c is also (n-nn1/2) Then, the term in 16 is (1). which further means that Vn(Va. Va,) (1). Our proof is now complete.
I Derivation of the Efficient Influence Function
We use the e-contamination approach of [31] to derive an influence function (IF) for our estimand V The proof for V follows symmetrically. We note that since our tangent space the whole space as it factorizes in the trivial way (as in [39, Page 54]), the IF we derive is actually the efficient influence function (EIF).
Let P(s,, a, s') denote the data distribution. Consider the e-contamination P= a, 8)) (1 E), a, s') + cō(3, ā, 3"), where 5(2) is the dirac delta at ž, i.e., 8(2) has infinite mass at 2 and 0 mass elsewhere. Let V.- denote the robust value function under the transition kernel Pe(s' 8,a). Omitting the subscript means E O. The IF of V is then given by
d= (1 E Ve (81) (81)l==0-
de
We dedicate the rest of this section towards this goal, which will be obtained in Theorem I.5.
Lemma I.1.
d Ps s,a))e=0
5(3,0) a)
(8(3') P(s' ss)))).
de
a(
Proof. Use the fact (s's s,
Pelaass") Px(a,))
(1 (lae) and take derivative.
Lemma 1.2 (IF of conditional expectation). For any 8, and fe.
d
8(3, a) a(s,a)
d (s') s,a
Ep (f(('') s,a]]e=o de
(f(5') Erlf(s') s,,)) + Ep
- de
where f fo
29

---

Proof.
- Bp, (se 1,, s, = Σ f(s') - Ps s,a)l==o + Σ de fe le Pl= s,
d
de
de
a)
a(s,a) (Jo(3') | s, + Ep de 18.0
Lemma 1.3 (IF of conditional CVaR). For any T, 8, and fe.
d de (fe(8.)((((8')) 8 8,a]|==
0(5,ā)
(3,(8, + - (s, CVaR+(J(s)) (.,))
P(s,a) a)
d + Ep -- S (s,
de fe(( |
where f = fo and B, a) the (1 -h quantile of f(s)), s P(s,a).
Proof.
d
CVaRp, s,a]le=
(17)
de
d min Ep, [b+ (fc(s') - b)_ [s,a]le=o
(18)
de (r(s,))-- - s, s.a]
d
-
(19)
de
where the last equality is due to Danskin's theorem and the fact that (5 a) is the maximizer the CVaR dual form 0. Continuing, let (=(';s,, (s, --c (r a))_,
d
Ep (8': a) |
8(5, a)
d (s);;s,)))e=s) s.0
(g(s') s, Eplg(ss' s, a) s,a)) + Ep
(Lemma I.2)
P(s.a)
de
8(5, a)
(0 - CVaR)(((8)) s,a)) + Er T (f(8)) S (s, d
de l==o 8,
P(s, a)
This concludes the proof.
We now prove the key "one-step forward" lemma.
Lemma I.4 (One-Step Forward). For any state distribution v(s), we have
E EgeD
VE ($)1==0)
de
= v())T(a 8)
+ (1
@(5,ā)
-Q_(3aa)
d
+ BBnu Ex.P (11 A) + Ar -I II (8) (r
de
30

---

Proof. For any we have
d
(s1)
de
d
- Bai ((s))) ( +
+ A(1Bp)) [V= (52) sl + +AVaRR [V. (52) s1 al, d
de
(Bar (1 (1- d
E..r. [V. (#2) 81,
CVaR,, [V= (52) s1, a1
de
de
0(3, (V (V"(s') Ep [V s1.a1)) P(s), a1) d
=7(1 -1) A()
+ +7(1- 2) (e)(
Ep
VE (82)le=0 01
de
a1) (B, (8 a1) + (V (5) 3, -CVa ((
8(3,a)
+ 7>E (11)
Virr (s2)
+ 7AE (11) Ep "I [ (82) S (-1,
a1)
de
Taking expectation
have
ESNU
- Ve (+))e=o)
d
= 1/ (ā 8)
de
@(
((1 A) (s') 3,a +ACVaR (V (3,
+ +Byos Bx.P (1 (11 3 a) _ V (8 (=))l==00
d
de
Finally recall that V satisfies the Bellman equation, so
(1 V)E (s') 5, (C [s'] 5,
(5. r(s.a).
This concludes the proof.
Equipped with main one-step lemma, now unroll it infinite number of steps derive the IF of our estimand.
Theorem I.5 (IF of Estimand). Let us denote
g(3, a, 5') := r(3, + 7(1 A)V A)V + ((3,(3, + (v
(5') (V (s,,a)))
Then, we have
(s,0) P(5, a) ((5
Edi
Vc (s1)le=o de
Proof. Let dy, denote the h-th step visitation in the robust MDP, with transition Puob satisfying Parls'(s.a) (1 A) -I (s') S (s, Then notice that the final term of Lemma 1.4 is P(a' s,a)
exactly Egwy Er Pue _ V. (s')l s]]. Therefore.
d V (s1)l==0
Edi de
di (á) g(8,a,,')
d BBgdda Ve (82))==0)
P(5,a)
de
d1 (ā g(3,0,3)
(3)((( 8)
d V (ss)le=0)
(5) + 7 22
B.gndd rdd
a(5,a)
P(3.0)
de
Iterating the process, we have
d
(3) 3)
(3)
d (3, P(5, a)
Esd
v (51)l==0
Σ
P(s,a) g(5,0,55)
g (5, a, a,,",,
de
1=1
as desired.
31

---

Finally, we can conclude that the IF in Theorem 1.5 is in fact the efficient IF (EIF) because it is in the tangent space, as the tangent space is contains all functions [39].
Additional Validity Guarantees for Orthogonal Estimator
Our orthogonal estimator has additional desirable properties such as validity when some nuisances misspecified. Specifically, the bounds returned by orthogonal estimator will be asymptotically valid, though possibly loose, when some nuisances are inconsistent, i.e., do not converge to the their true values. Below, detail conditions under which we achieve validity. To be concise, we focus on the case as the + case is symmetric.
Validity with correct Q+. If - Q+, we obtain valid bounds even if w, 3 are inconsistent. Lemma J.1. For any w, B, we have Elbb(s, s'; "0: 3. < Vá, with equality when B = 87
Validity with Q = T. Q. Even if Q is misspecified, we still have valid bound if it solves Dellman-type equation of the dual CVaR form. For B S x + R, define:
(=, a() 7A (s,
Elf(s mT) s + + - A ( + a)) - 3(s,a)) s.a.
Lemma J.2. Fix any w, B. 15
then Bibls, a, 8 8g w] S VV.
Remark J.3. Lemmas J.1 and J.2 are dual to each other: in Lemma J.1. the plug-in is consistent while the debiasing correction erTs in the valid direction (i.e. 2 0 for + and < 0 for -). In Lemma J.2, the plug-in valid while the dehiasing correction has expectation zero.
J.1 Proofs for validity
Lemma J.1. For any B, we have
s Vi, with equality when B = B7.
Proof.
E|u(s,a,s':Q ,8, w), s (1 - Bd, VV Elo(s, Q (s,a))
= VV, +0 V
where the inequality comes from the fact that 33 is sub-optimal for = ( 3(s,a))_]. The same proof applies for Q+.
We now prove Lemma J.2. First, we show that the Ta perspective gives rise to a dual definition of Q= (dual Eq. (2)).
Lemma J.4.
(s, = arg min B: Qs(s.a), (s = arg max B:Qa=T, 9u Qs(s,a).
r(s, + + Ey (rs''s "''ssa'' .a') + 7 iif Ey [- replacing each infrre(P)) with the convex combination of E and CVaR from Lemma 3.1. Then, write each CVaR using the dual form, ie., maxx( + --1(s, (s)()) rectangularity, the scalar max separates per 8, a, so we can pull all the maxes out front as a max over (s,, a) functions. Note that not all B(s, a) functions have well-defined infinite sum this manner, as Ta is not always contraction. The condition Q2 T Qa exactly characterizes when this unrolling well-defined. Thus, Q is exactly the minimum Q whenever this procedure of unrolling with 3 is well-defined. This concludes the proof.
Proof. Unroll
B(s a)) }}. By 8, a-
32

---

Lemma J.2. Fix any w, B. 2 = -3 then Bib(s, q. 1g. w. $ Va.
Proof.
(s a, : 23. = RR, (V7 (s1)] Va.
The first equality is because the correction term is T UB Qg. which is zero since Q3 is fixed point. The inequality is due to Lemma J.4.
K
Additional Details for Main Experiment
K.1
Environment
We consider simple MDP with one-dimensional state space S [0, 5]. binary action space A = {0, 1J, reward function
r(, a) 26 -1
26
which we note takes values in the range [0, 1], and with transitions given by
P. 8, = 0) UnifClipls - 0.2, 8 ++1
P( 8,a
UnifClip(O.2s 0.02, + 0.5].
where UnifClip[a, b] denotes a uniform distribution between max(a, 0) and min 5). In addition, the environment always starts in initial state 50 2. Essentially, this is simple control environment, where high rewards are obtained by maintaining state as close to zero as possible, the action a = is control action that (in expectation) moves the state closer zero, and which occurs small reward cost, and the action = O is a passive action that allows the state to freely drift (with an overall drift away from zero).
K.2 Target Policy
We focus estimating the worst-case policy value V7, for the simple threshold-basee target policy ग. which takes action when 2 2, and a 0 whenever s 2.
K.3 Logging Policy and Data Sampling Procedure
We sample data using an evaluation policy m, which is an e-smoothed threshold policy similar to m Specifically, ma takes action
when 1.5 with probability 0.95, and takes action = 0 when < 1.5 with probability 0.95. We obtain a dataset {st, a,, s,, r.) by first rolling out with Tú for 1000 burn-in time steps, and then sampling the tuple (s, (s,a, s every 10 time steps. For each replication of our experiment, we sample 10,000 tuples in total.
K.4 Calculation of True Worst-Case Policy Values
major challenge in studying robust policy value estimation is that, even with ground truth knowledge of the MDP and/or access simulator, it may be intractable estimate the robust policy values V Fortunately, the above environment has the desirable property that we can analytically compute the best/worst-case transition distributions allowed by our sensitivity model, since matter what policy He the agent is acting with, it always strictly prefers transitions to smaller states. In detail, suppose that for some state, action pair (s, a) have P- 8, 8,a) Unif[ær v/. for some
< y S 5). Then, letting a 1/(1 + A(s, a)), it is easy to verify that the worst case transition kernel is given by
U- = - A un)fly alv ==).vl A A uniff(zz
33

---

That is, the worst case transition kernel is given by a mixture of two uniform distributions. Therefore, we can easily simulate rollouts with the best/worst case transition kemelss, and accurately estimate the robust policy values. This allows to validate our methodology in this synthetic environment. Specifically, for each A(s, a) we experiment with, we can compute the corresponding ground truth VJ, up arbitrary precision via Monte Carlo sampling, by rolling out trajectories with %e in the adversarial MDP according to the above worst-case transition kernel.
Note as well that if one wanted to estimate the best-case policy value, analogous reasoning would give us
a)nnn) U+ s.a) = (1 (s, a)) + +ay - z)] A (s,,,a y].
However, in our experiments we only concern ourselves with worst-case policy value estimation.
K.S Nuisance Estimation
We instantiate slight variations of Algorithms and using neural nets for the classes Q. B, and W used for fitting Q f_, and wt respectively, and linear sieves for the corresponding critic class Q that perform maximization over for the minimax estimation of w Specifically, grow the linear sieve for the critic class in data-driven way, as follows: at each step of the respective algorithm, we compute the best response qa E to the previous iterate solution we E W by optimizing over a neural net class, and then we append this best-response function to the set of functions in our linear sieve for the corresponding critic class, Full exact nuisance estimation details necessary for reproducibility will be available in our code release.
K.6 Estimators
We estimate the worst-case policy value using three different estimators:
Q: Direct estimator given by:
- (s))),
where 81 is the deterministic initial state.
W: Importance sampling-stye style estimator using w which is given by:
V
w (si, as Ears
where
E = A-A + -1-11 ANL (-(s)) 3- (s)
Orth: Our orthogonal estimator using EIF, given by
V
(8s, 0z 8/: ,
Note as well that we used simpler data splitting procedure rather than the cross-fitting procedure described in Algorithm 3. Specifically, we used the first 10,000 tuples for estimating nuisances, and the second 10,000 tuples for the final estimators. This was done for the sake of computational ease in running experiments with many replications, and was performed the same way for all methods.
In addition, for extra robustness, each experiment replication we ran the nuisance estimation pipeline 5 times (on the same fixed sampled dataset), and took the 80th percentile policy value estimates, since the estimators tend to under-estimate the true policy value by design, with greater under-estimation when the nuisance estimates are less well optimized.
34

---

L Empirical Investigation on Medical Application
Here, we describe an additional empirical investigation of our methodology on medical data. Specif- ically, we consider the problem of sepsis management using RL. For all parts of the investigation described below, fully complete details can be obtained from our code release.
L.1 Motivation of Investigation
Training RL models in simulated environments derived from real-world data is an exciting avenue for leveraging AT towards critical medical use cases. However, doing this obviously has the downside that, unless undergoes the very risky process of training RL. agent online via real medical interventions, one has to resort to training within simulators, and then has to account for the inevitable "sim-to-real" gap. Therefore, robust OPE methodology provides an interesting approach for estimating worst-case performance of RL models under potential changes in dynamics when moving real application.
L.2 RL Environment
Our RL environment is based on the OpenAl Gym sepsis simulator environment of [44]. This RL environment allows for simulation of dynamic sepsis management, which was created by training blackbox ML model to mimic observed transition dynamics from the real-world electronic health record-based MIMIC-III dataset [36]. This existing sepsis simulator is episodic environment that continues until the agent either recovers or dies. It has a 46-dimensional state space containing various vital measurements, a discrete action space containing 24 possible actions (where action is essentially the Cartesian product of some independent base actions). The reward function in this original simulator gives zero reward whenever an episode has terminated, +55 reward termination when if the patient survives, or a -15 reward at termination if the patient dies. Please see [44] and the code release linked therein for additional details.
We built an RL environment for our investigation by creating simple wrapper around this existing sepsis simulator, in order to make it fit our setup. In particular, we made the following key changes:
1. We made the environment infinite-horizon, by automatically looping to a new random starting state for fresh patient whenever the episode in the base simulator terminates
2. We normalized the reward function that it lies in range [0, 1], where:
(a) r(s, a) if patient dies
(b) r(s, a) = if patient recovers and discharged
(c) r(s, a) = 0.5 if treatment has not terminated for current patient
In addition, for this environment, we perform all experiments with = 0.95.
L.3 Policies for Investigation
We constructed RL policies for our empirical investigation by training some deep RI. models using the sepsis simulator environment.
In the case of the behavioral policy n. used to generate the observational offline data, trained this policy by running Proximal Policy Optimization (PPO: [63]] over a relatively large (16,000) number timesteps, in order to emulate reasonably good "current best practices" model for creating observational data.
In the case of the target policy to be evaluated, we trained this policy using Deep Q Learning (DQL: [53]), over relatively small (1,600) number timesteps, in order to emulate a potentially risky new candidate model.
35

---

Median Policy Value Estimate
A
W
Orth
1
.446 + .003
.386
+ .087
.532 + .008
2
.544 + .040
534
- .11
.515 = .036
4 .381 + .077
.287
= .106
.338 .086
Table 2: Median policy value estimate for sepsis management investigation, for each estimator and value A over 5 runs each estimator from random initial seeds. The values are given by half the difference between 80th and 20th percentiles.
L.4 Creating an Offline Dataset
Using behavioral policy which we created above, generated fixed offline dataset consisting of 20,000 observed tuples state, action, reward, and next state. Unlike with our main empirical investigation in the main paper, did not perform any "thinning" on these sampled tuples to make them more independent, so that the observed transitions are sequentially correlated as with real-world medical data.
L.5 Nuisance Estimation
We perform nuisance estimation almost identically in our main empirical investigation, with the only change being slight change to our neural network architectures to better handle the large discrete action space. Specifically, instead of training neural networks that take state as input and produce |AA| outputs (one per action), we train neural networks that take both state and action as inputs, using learnt cow-dimensional encoding of the actions, and produce a single output. Please our code release for details.
L.6 Estimators
We consider the same three estimators (Q. W, and Orth) in main empirical investigation. As in that investigation, we use these to estimate the worst-case policy value for the given A(s, a). In addition, as in the main experiments, we consider these estimators for various fixed A(s, a) that do not depend on a. In this case, we consider A E (1,2,4] as these reflect reasonable range of possible confounding strength for real application.
L.7 Results
Below, in Table 2 we show the estimated policy value for all three estimators for each fixed A E (1,2,4) 4). Here, we present the median policy value estimate over 5 runs of estimators from random starting seeds after removing outliers. 2 In addition, we present a + spread given by half the difference between the 80th and 20th percentiles.
Although for this investigation we cannot analytically compute the ground truth "true" adversarial policy values to evaluate against when A >> 1, we can still analyze the trends of these estimators and compare them those observed in our main synthetic experiment, and we can also compare their accuracy when = 1.
First, in the case of A = 1, we computed the true policy value of म, to be within the range 0. 0.532+00.00 0.002 with 95% confidence. This is almost exactly equal to the median Orth estimator, but far outside the spread of outputs of the Q estimator. That is, although the Q estimator has somewhat lower variance outputs over multiple runs for A compared with Orth, it appears to more biased.
Next, looking more broadly across all values of A, as in our main experiment, the Q and Orth estimators generally result in similar estimates to each other, and the W estimators very variable.
'Specifically, we exclude policy value estimates that lie outside the possible range of [0, 1]. which occasionally occur due to bad optimization from the starting seed.
36

---

This may reflect the relative difficulty of estimating the w nuisance function compared with Q and 3=; although both Orth and W are affected by this difficulty. the Orth estimator has a theoretical robustness to the errors of these nuisance functions that the W estimator does not, outlined in our theory.
We also observe that when A the Q estimator is significantly more stable than Orth, but when A > the stability of Orth is either comparable to or superior to Q. In order to understand this, first note that unlike our main experiments, here the repetitions are re-runs of the estimators with the offline sepsis dataset, these + spreads reflect potential computational errors rather than statistical errors. Given this, this pattern errors could be explained by the fact that when = 1 the estimation is extremely simple, reducing to standard FQI, whereas when A > 1 it requires more complex robust FQI estimation with simultaneous estimation of / That is, the difference in computational difficulty of estimating Orth versus may be smaller for A >
Overall, although it is hard definitively compare the accuracy of these estimators for given a fundamental lack of ground truth, given both similar pattern of results as in our synthetic experiments, as well the far greater accuracy of Orth when 1, it seems reasonably believe based on these results that our proposed Orth estimator may be more reliable than the existing robust FQI approach the estimator.
Finally, we consider the implication of our results for the problem of learning sepsis management policies from simulators. Our Orth estimator suggests that there is relatively little sensitivity of this environment deviations allowed by A 2, but very significant deviation allowed by A Indeed, given the reward structure described above, the worst-case results under A = 4 imply an extremely high mortality rate. Whether worst-case deviations of this magnitude are reasonable or not is unclear, and this is something that requires further investigation for future work on RL for sepsis management.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: Yes. we provide complete proofs for our theorems and describe detailed empirical validation for our proposed algorithms.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: Yes, we discussed where our assumptions may fail and settings not captured by the current paper, which we believe are directions for future research.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes, we provide full assumptions in the main paper and the complete proofs are written in the Appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes].
Justification: Yes, our experimental section includes all details needed to reproduce the main experimental results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes].
Justification:
Yes, our code is open-sourced https://githut: com/CausaMML adversarial-oper
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Yes, please see our experimental section and appendices for all training and evaluation details.
Justification:
Guidelines:
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes].
Justification: Yes, our experiments are replicated over multiple seeds and we report the confidence intervals.
8. Experiments Compute Resources
38

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes].
Justification: Yes, this paper is mostly focused on theory and our experiment is proof of concept and can be run on a standard GPU.
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics attps://neurip:: cctppblic//eeeeececcecccceceeeee wethiiihoieeeeeeeeeeeeee
Answer: [Yes].
Justification: Yes, we have reviewed the code ethics and believe our research conforms to
it.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This paper is about foundational research not tied to particular applications so we do not feel the need to highlight any societal impacts.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This paper is about foundational research not tied to particular applications so we do not feel the need to highlight any risks for misuse here.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA].
Justification: The paper does not use any existing assets.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA].
Justification: The paper does not involve crowdsourcing nor research with human subjects.
39


Reviews:
[{"review_id": "TJMgEhHYSn", "reviewer": "Reviewer_xbQo", "summary": "This paper studies statistically-efficient robust/optimistic (e.g., worst- or best-case within the uncertainty set $\\mathcal{U}$) off-policy evaluation with bounded Radon-Nikodym uncertainty sets centered around known nominal models. It proposes novel algorithms for computing robust/optimistic Q functions, and provides theoretical analysis for them. It further claims that the sharp and efficient estimators are optimal in the local-minimax sense, and provides preliminary experimental results to support the claim.", "questions": "* Why do you use bounded Radon-Nikodym derivative for defining ambiguity sets, as I haven't seen people doing this? Does it have any connections with other \"distances\", e.g. total variation, KL-divergence, or Wasserstein distance?", "limitations": "There are a few sentences discussing limitations of the setting, but a summary is missing.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "* The paper seems to include a wide collection of new theoretical results, with assumptions clearly stated and proofs attached.\n* The problem itself is simple, fundamental, and stated in an comprehensible way.", "weaknesses": "* The writing of this paper needs to be improved, at least for non-experts in this specific area.\n    * Frankly speaking, I'm having a lot of trouble following the paper, or even understand the problems and the results. Though I have to admit that I major in CS and don't have a strong statistics background.\n    * First and foremost, it doesn't seem like the $\\pm$ superscript is doing any good here, except confusing the reader for the first few moments. If I were to write this paper, I would just sell the story of \"robust OPE\", and say a sentence or two on how to re-interpret it as a optimistic evaluation scheme (I do think negating rewards is easier to understand).\n    * Some sentences are broken and not fully comprehensible (e.g., lines 193~195), some notations are left undefined before their first use (e.g., the $\\frac{dU}{dP}$ notation, which I regard as Radon-Nikodym derivative), and some paragraphs are duplicated with subtle differences (e.g., Lemma 4.1 and G.1).\n    * The literature review part (Section 1.1 and Appendix B) seems to be very incomplete, and some paragraphs seem irrelevant (e.g., lines 84~104). Since this is a paper on robust OPE, a more comprehensive review on existing works regarding robust MDPs and OPE methods is definitely needed, especially a comparison on the settings and the bounds.\n    * As far as I'm concerned, the flow of the whole paper needs major revision. For example, it's unclear why we need to estimate $w^{\\pm}$ in Section 4, until in the estimator for $V^{\\pm}\\_{d\\_1}$ is proposed in Section 5. Another issue is that I don't fully get the point why we need a few more complex procedures to estimate $V^{\\pm}\\_{d\\_1}$ after we've got the estimates for $Q^{\\pm}$. Besides, the key results are not explained in plain English (e.g., given the sentences between lines 211 and 217, I still don't see clearly what Theorem 3.4 means. What is the typical order of $\\varepsilon^{\\mathcal{Q}}_n$? What about the $\\mathrm{err}$ term?)\n    * Simply put, Sections 3~5 are not well-motivated, the results are not intuitively interpreted, and their connections need to be further specified.\n    * Personally, I expect to first see a full overview of the proposed algorithm and the \"ultimate\" end-to-end sample complexity result (which is now hidden in the paragraph \"Putting everything together\" on lines 316~322) to get the big picture, before diving into all the technical details introducing the subroutines.\n* Since I'm not an expert in this area, I don't fully understand the technical details. (***To AC:*** Please do take other reviewers' opinions for technical soundness. I've tried hard but failed to fully check the proofs.)\n    * Specifically, I don't follow the proofs in Sections E.5 (for the second part of Theorem 5.3), G.1 (for Lemma 3.1) and G.2 (for Lemma 4.1). The latter two don't seem like legit proofs in my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness: Paper is difficult to read**\n\nThank you for your detailed feedback on how the quality of writing in the paper could be improved. On some level, this is a very difficult research topic to present in a way that is easily accessible without at least some background in stats and/or causal inference, because of the topics that it considers (i.e. related to semiparametric efficiency theory, orthogonal ML, etc.) It is typical that papers on such topics, including many of the papers that we cite related to causal inference, double/debiased machine learning, or semiparametric efficiency theory, are similarly technically dense. Also, our work is cross-disciplanary between these research areas and RL too, so there is the additional challenge of making it accessible to both audiences, while also being technically rigorous enough for both.\n\nHowever, it is not our intention for the paper to be inaccessible, and we will work hard on improving its readability and accessibility for the final camera ready version, following the helpful advice of you and other reviewers. In particular, regarding your specific suggestions on improving readability:\n\n- **Use of $\\pm$:** Our use of the $\\pm$ notation is as a succinct way to denote that there are two different quantities being defined. For example, for the operator $\\mathcal{T}^\\pm$ defined in Lemma 3.1 in terms of $\\text{CVaR}^\\pm$, we are succinctly defining two different operators: $\\mathcal{T}^+$, which is defined in terms of $\\text{CVaR}^+$, and $\\mathcal{T}^-$, which is defined in terms of $\\text{CVaR}^-$. This was done because, ultimately, we are presenting estimators for both the worst-case and best-case policy values under the sensitivity model. However, we understand that this notation can be somewhat confusing and cumbersome, and so we propose the following change to the final camera ready version, which would eliminate all $\\pm$ notation: \n1. Instead of discussing both the best and worst cases (+/-) simultaneously, we will provide results only for worst case (-) in the main text.\n2. We will add a brief discussion about how the best-case version can be reduced to the worst-case version for a transformed MDP. (This reduction works by replacing all rewards $r(s,a)$ with $1-r(s,a)$, and then replacing the final estimator $\\psi$ with $1-\\psi$.)\n\n- **Definition of notations / writing quality:** Thank you for pointing out these issues, we will do a thorough edit of the paper to fix all such writing issues and ensure that all non-standard notations are defined. Regarding the Radon-Nikodym derivative, we would argue that this is standard probability theory notation, but we will clarify.\n\n- **Literature Review:** The part of the literature review that you highlighted is actually specifically about unobserved confounding in both sequential / non-sequential decision making, not about robust-MDPs (which, other than the works we cite and discuss, do **not** allow for unobserved confounding). Given limited space we focussed our literature review on the areas most related to our paper (focussing on settings that allow for unobserved confounding), and relegated our discussion of the literature on robust MDPs more generally to Appendix B (\"other related works\"). However, we will add some clearer pointers to this discussion in the related work section in the main paper.\n\n- **Ordering of Content in Paper:** We acknowledge the feedback here, and can understand how the order of the paper may seem unintuitive for readers unfamiliar with the related literature. We believe the current order is inuitive for readers familiar with similar orthogonal policy value estimators in non-robust settings, which are defined in terms of $Q$ and $W$, however it could be made more accessible. Therefore, we propose to present these existing orthogonal estimators for non-robust MDPs before Sections 3-5, explaining how they are defined in terms of $Q$/$W$. In addition, at this location we will foreshadow the Seciton 5 result that our estimator generalizes this estimator, using robust versions of the $Q$/$W$ functions, which are the $Q$/$W$ functions for the worst-case MDP. After this motivation, sections 3/4 will naturally follow, as they describe how to identify and estimate the robust $Q$/$W$ functions that we just introduced/defined. Similarly, section 5 will naturally follow after these as it puts together how these robust $Q$/$W$ functions are combined in the more general estimator that was previously foreshadowed. In order to make space for this, we will move some of the more technical content that is less important for the overall narrative to the appendix.\n\n**Weakness: Issues in Proofs**\n\nWhile we are open to feedback on how the presentation of our proofs could be improved, we have gone to great lengths to ensure that these results are technically sound. Could you please provide specific details about your claim that \"the latter two don't seem like legit proofs in my opinion\" about our proofs of Lemma 3.1 / Lemma 4.1 during the discussion period? This is a vague statement and we are not sure how to respond without more specific detail about what you find problematic with these proofs, but we are happy to defend the technical details of our proofs.\n\n\n**Q1: Why do you use bounded Radon-Nikodym derivative for defining ambiguity sets?**\n\nWe use this definition to allow for full generality to state spaces that could be either continuous or discrete, or some combination of the two. For discrete state spaces, this Radon-Nikkodym (RN) derivative is just the ratio of transition probabilities, whereas for continuous state spaces, this RN derivative is just the ratio of probability densities. In either case, as discussed in the paper, this definition comes naturally from generalizing the standard marginal sensitivity model used in causal inference in the single decision (i.e. non-RL, or horizon=1) setting. We will clarify this further in the final paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hWXF5AmdCX", "reviewer": "Reviewer_QdT5", "summary": "This paper studies off-policy evaluation problems in robust Markov decision processes, where the environment dynamics may change over time. The authors consider a perturbation model that modifies the transition probability up to a given multiplicative factor. They first propose two new algorithms for learning the Q-value function $Q$ and the density ratio function $w$. Then, they design a new policy value estimator based on the estimated nuisance parameters. The authors provide a theoretical analysis of the new algorithms and estimators, along with numerical experimental results to verify their effectiveness.", "questions": "See weakness part.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "a. The studied problem of off-policy evaluation in robust MDPs is interesting and meaningful.\n\nb. The theoretical analysis is solid. The proposed $Q$-function estimation algorithm achieves a $\\widetilde{\\mathcal{O}}(n^{-1/2})$ rate for parametric classes. More importantly, the proposed orthogonal estimator in Section 5 has a second-order dependence on the estimation error of nuisance parameters. As a result, it only requires the rate of nuisance parameter estimation to be faster than $n^{-1/4}$ to achieve an $n^{-1/2}$ rate.\n\nc. The numerical results align with the theoretical analysis; the orthogonal estimator consistently achieves the best performance compared to the $Q$ estimator and $w$ estimator.", "weaknesses": "a. This paper considers a perturbation model where the ratio between the modified transition kernel and the nominal kernel is bounded by a sensitivity parameter. In Algorithms 1 and 2, the learner needs access to the parameter $\\Lambda(s,a)$. However, it is unclear how to estimate $\\Lambda(s,a)$ in real-world scenarios. Additionally, the authors claim that the perturbation model is more general and captures confounded settings. More detailed analysis and explanations are needed to support this claim.\n\nb. Algorithm 2 requires solving a minimax optimization problem, which is usually very time-consuming in practice. In the experiments, the authors use an iterative method as an approximation. Is there any theoretical analysis for that implementation?\n\nc. Additional experiments using real-world datasets would help to better demonstrate the practical applicability of the proposed algorithms.\n\nMinor:\nRedundant content in line 194", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer QdT5, thank you for your review and positive feedback on our work. We appreciate your recognition of the problem's significance, our theoretical contributions, and the alignment of our numerical results with the theory.\n\n**Motivation for perturbation model**\n\nIf the cause of the perturbation is unobserved confounding, a common approach to set $\\Lambda(s,a)$ is to conduct an ablation study by withholding one feature of the state at a time. In a clinical setting, for example, smoking status or BMI could be withheld one by one, and the ratio in (1) calculated. A practitioner could then set $\\Lambda(s,a)$ by assuming that an unobserved confounder could induce a shift in the transition kernel up to, say, twice the maximum $\\Lambda(s,a)$ observed in the ablation study (see [1]). Another approach is to consider multiple $\\Lambda(s,a)$ values until a specific condition (e.g., the lower bound of the value being less than $\\alpha$, or less than 0 if $r \\in [-1, 1]$). For instance, [2] studied the effect of smoking on lung cancer and found that unobserved confounding had to be nine times larger in smokers ($\\Lambda = 9$) than in non-smokers to negate the measured negative effect of smoking. Since other features in the data had smaller $\\Lambda$ values (ranging from 1 to 3), the conclusion was that there is at least some negative effect of smoking despite the observational dataset being affected by unobserved confounding. We will add this discussion to the final draft. \n\nOur perturbation model has a one-to-one correspondence to the MSM model in the confounded setting, which places a constraint on the ratio of confounded and unconfounded policies (rather than the transition kernels). Specifically, our perturbation model implies the policy MSM and therefore it subsumes the confounded setting. However, the reverse is only true for $A=2$. For $A>2$, a bound on the policy ratio imples only a loose bound on the ratio of transition probabilities, thus yielding non-sharp bounds for $A>2$. This discussion is included in the related literature section. \n\n**Minimax optimization problem**\n\nA couple of points regarding the hardness of the minimax optimization problem and proposed solution:\n\n1. In general these kinds of minimax problems given by conditional moment conditions can be efficiently solved. For example, [4] show that an iterative procedure of solving a sequence of T least squares regression problems and cost-sensitive classification problems can guarantee a $log(T)/T$-approximate solution (which works via a reduction to no-regret learning, similar to the original theoretical analysis of boosting.)\n\n2. The solution we used is somewhat similar to that mentioned above, although differs a little. It can be seen as a special case of [5] motivated by the observation of [6] that such OWGMM estimators are equivalent to minimax estimators. The sieve-based procedure of [5] has strong theoretical guarantees of consistency and semiparametric efficiency when the sieve is grown sufficiently fast (as the number of data points $n$ increases), and we augment this kind of estimator by adding extra functions to the sieve via a similar no-regret style procedure as in [4], by iteratively computing the OWGMM estimator and finding the worst-case adversary function. This augmentation does nothing to subtract from its existing theoretical guarantees, but we find is empirically very helpful. Furthermore, since we compute the worst-case adversary at each iteration, it gives a computational certificate of how close to min-max optimality each iterate is, which can make the procedure trustworthy in practice. In terms of computation, this algorithm just involves minimizing a convex loss function a fixed number of times, and so is computationally efficient.\n\nWe will provide some discussion of this.\n\n\n**Additional experiments**\n\nFor the final version of the manuscript, we will include results using real-world healthcare data. Specifically, we will demonstrate how our method extends to complex, real=world scenarios via a case study using MIMIC-III data for off-policy evaluation of learned policies for the management of sepsis in the ICU with fluids and vasopressors (see [3] for example). \n\n[1] Hsu, J.Y. and Small, D.S., 2013. Calibrating sensitivity analyses to observed covariates in observational studies. Biometrics, 69(4), pp.803-811.\n\n[2] Cornfield, J., Haenszel, W., Hammond, E.C., Lilienfeld, A.M., Shimkin, M.B. and Wynder, E.L., 1959. Smoking and lung cancer: recent evidence and a discussion of some questions. Journal of the National Cancer institute, 22(1), pp.173-203.\n\n[3] Killian, T.W., Zhang, H., Subramanian, J., Fatemi, M. and Ghassemi, M., 2020. An empirical study of representation learning for reinforcement learning in healthcare. arXiv preprint arXiv:2011.11235.\n\n[4] Dikkala, N., Lewis, G., Mackey, L., & Syrgkanis, V. (2020). Minimax estimation of conditional moment models. Advances in Neural Information Processing Systems, 33, 12248-12262.\n\n[5] Hansen, L. P. (1982). Large sample properties of generalized method of moments estimators. Econometrica: Journal of the econometric society, 1029-1054.\n\n[6] Bennett, A., & Kallus, N. (2023). The variational method of moments. Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(3), 810-841.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Z8yhlZDxFE", "reviewer": "Reviewer_ghkS", "summary": "This paper studies the problem of evaluating a policy under best- and worst-case perturbations to a Markov decision process (MDP), given transition observations from the original MDP. The first contribution is the robust Q learing algorithm for CVaR problem, the second contribution is the estimation of robust visitation distribution in the function approximation setting and their complexity bounds.", "questions": "- There are several other important papers on robust offline reinforcement learning that are missing in this paper, e.g., \nDouble Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage\nJose Blanchet, Miao Lu, Tong Zhang, Han Zhong\nDistributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity\nLaixi Shi, Yuejie Chi\nComparison with existing robust offline RL is not clear in this paper. \n- The writing of this paper needs to be improved. Is Section 3 and Algorithm 1 only about CVaR?", "limitations": "na", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The problem studies in this paper is of significant practical importance, which is to evaluate the worst/best performance over an uncertainty set. The authors designed algorithms and derived their complexity bounds, which are shown to be optimal.", "weaknesses": "- The authors seem to be using offline and off-policy interchangably, which is misleading and confusing.\n- One important challenge in offline reinforcement learning is due to partial coverage and distribution shift. However,  this paper does not explicitly define the single-policy concentrability coefficient that measures the gap between the sampling distribution $\\nu$ and the target policy $\\pi$, and therefore did not consider this key challenge in the offline setting. \n- The notations are unnecessarily complicated, and many are used without being defined. For example, in algorithm 1 line 6, the hat on top of the expectation, and the subscript of the expectation is not clear.\n- There are many technical assumptions that remain unjustified. Please justify each of the assumptions, and provide examples when those assumptions can be satisfied, and how to verify those assumptions in practice.\n- The perturbation model in eq. (1) is unjustified. It could happen easily that $\\Lambda(s,a)$ is zero or infinite for some $(s,a)$. The authors shall explain why this perturbation model is of interest, and why this model is superior over existing uncertainty set models, e.g., those defined by KL divergence, TV.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer ghkS, thanks for acknowledging the strengths of the theoretical results. Please find our responses to your questions below:\n\n**W1: \"The authors seem to be using offline and off-policy interchangably, which is misleading and confusing.\"**\n\n**Author's Response:** We agree this may be confusing and will use \"off-policy\" consistently in revising since we focus only on evaluation.\n\n**W2: \"One important challenge in offline reinforcement learning is due to partial coverage and distribution shift. However, this paper does not explicitly define the single-policy concentrability coefficient that measures the gap between the sampling distribution $\\nu$ and the target policy $\\pi$, and therefore did not consider this key challenge in the offline setting.\"**\n\n**Author's Response:** The concentrability coefficient is defined in Line 208, and it makes an appearance in our guarantee for robust FQE. Note that our concentrability coefficient differs from the one from standard OPE since the target policy's distribution is under the *adversarial MDP*. We will make this more apparent in the revision. We will also clarify how concentrability makes an appearance in the (efficient) variance our estimator achieves (namely, $\\Sigma$ on Line 304). In particular, $\\Sigma=\\mathbb E[(\\frac{\\mathrm{d}d^{\\pm,\\infty}(s)}{\\mathrm{d}\\nu(s)})^2(\\frac{\\pi_{\\mathrm t}(a\\mid s)}{\\nu(a\\mid s)})^2(r(s,a)+\\gamma \\rho^\\pm(s,a,s';v^\\pm,\\beta^\\pm)-q^\\pm(s,a))^2]$. That is, the amount of distribution shift (in the adversarial MDP) makes an explicit appearance in the (minimal) variance of robust evaluation.\n\n**W3: \"The notations are unnecessarily complicated, and many are used without being defined. For example, in algorithm 1 line 6, the hat on top of the expectation, and the subscript of the expectation is not clear.\"**\n\n**Author's Response:** Thanks for catching, we use the \\hat on top of $\\mathbb{E}$ to denote empirical expectation (in this case, over the second split of $\\mathcal{D}_i$). For the camera-ready, we will try to simplify and reduce notation (e.g. we will focus the main text on the - case, rather than presenting both -/+ cases together). However, we do want to concede that the nature of orthogonal ML and semiparametric statistics is inherently very technical and many concepts / notations are needed to achieve the mathematical rigor consistent with past works addressing similar topics.\n\n**W4: \"There are many technical assumptions that remain unjustified. Please justify each of the assumptions, and provide examples when those assumptions can be satisfied, and how to verify those assumptions in practice.\"**\n\n**Author's Response:** We justify and discuss each of the assumptions right before / after they are stated. For example, Assumption 3.2 is discussed in lines 193-195; Assumption 3.3 in 199-200; Assumption 4.3 in Lines 254-255. We concede that these justifications are rather brief but we do note that our assumptions are *standard and known* in the OPE literature (Munos and Czepesvari 2008, Uehara et al. 2021). To improve readability, we will add more discussions about these assumptions for the camera-ready. \n\n**W5: \"The perturbation model in eq. (1) is unjustified. It could happen easily that $\\Lambda(s,a)$ is zero or infinite for some $(s,a)$. The authors shall explain why this perturbation model is of interest, and why this model is superior over existing uncertainty set models, e.g., those defined by KL divergence, TV.\"**\n\n**Author's Response:** Our perturbation model is a natural generalization of the celebrated Marginal Sensitivity Model (MSM; Tan 2006 [56]) from causal inference, which has been validated by many follow-up papers (e.g. Kallus and Zhou 2021 \"Minimax-Optimal Policy Learning under Unobserved Confounding\", Bruns-Smith and Zhou 2023 \"Robust Fitted-Q-Evaluation and Iteration under Sequentially Exogenous Unobserved Confounders\", and Dorn and Guo 2021 \"Sharp Sensitivity Analysis for Inverse Propensity Weighting via Quantile Balancing\", and many more). For example, the MSM importantly captures settings where the behavior policy and transition kernels may be perturbed by *unobserved confounders*, which is not captured by any those defined by KL or TV. Since the uncertainty set is a modeling choice there is no \"superiority\" of one over another, but the MSM does nicely capture possible unobserved selection effects. We elaborate on this point in Lines 84-93. Line 135 specifies $\\Lambda(s,a)\\in[1,\\infty)$.\n\n**Q1: \"There are several other important papers on robust offline reinforcement learning that are missing in this paper\"**\n\n**Author's Response:** Thanks for pointing out these two papers. Both papers are for the task of robust offline policy *learning* (OPL, i.e. learning a robust policy), whereas we focus on the task of robust off-policy evaluation (OPE, i.e. evaluating a policy's performance under distribution shift). Both are important problems with their own challenges. In practice, even if one is using robust policy learning, robust OPE is still of paramount interest, as it allows policy makers to reliably assess the actual performance of the learned policy under environment shifts or confounding. We will certainly add more discussion about robust policy learning and cite the papers you mentioned.\n\n**Q2: \"Is Section 3 and Algorithm 1 only about CVaR?\"**\n\n**Author's Response:** Yes, they are for robust Bellman equations with $\\lambda \\mathbb{E}+(1-\\lambda)\\text{CVaR}$. Indeed, one of our key insights is that the confounding-robust uncertainty set of Eq (1) can be equivalently expressed by the above robust Bellman equation, leading to tractable solutions in Sec 3 and Alg 1. We highlight that our approach can be easily extended to deal with other convex risk measures such as entropic risk or mean-variance (Markowitz), which we leave for future work.\n\nThanks again for your helpful feedback. We hope we have addressed your concerns and please let us know if you have any additional questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wQK538IIOX", "reviewer": "Reviewer_kuGv", "summary": "This paper proposes a statistical theory for off-policy evaluation given observational data from an unknown transition kernel of an original MDP, possibly under policies the same as or different from the target policy. This paper focuses on the situation of environment shift, i.e., the transition kernel of the MDPs at test time can shift from the original MDP to a certain extent. These transition kernels are assumed to be center around the observational transition kernel. This paper proposes new algorithms and sharp estimators for robust estimation of policy value. The proposed estimation method has several desired properties.. First, it is semiparametrically efficient, with a $\\sqrt{n}$-rate of estimation even when certain nuisance functions are estimated at slow parametric rates. The estimator is also asymptotically normal which enables easy statistical inference. Even when the nuisance functions are estimated with bias, the estimator is still constant. Numerical simulations verify the efficiency and sharpness of the proposed estimator.", "questions": "Please see weakness.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "**Significance**: \n\n**1.** This paper focuses on an important and challenging theoretical problem of policy evaluation under transition kernel shift. This is a very realistic and probably more common scenario compared to the classical OPE setting where only the policies shift.\n\n**2** This paper presents a credible statistical theory for policy evaluation under transition kernel shift and the existence of nuisance functions. The statistical analysis shows that strong statistical guarantee can be achieved for the proposed estimator.\n\n**Quality**: this paper has a good quality. \n\n**1.** The paper has a solid theoretical analysis, with well specified definitions and theorems.", "weaknesses": "**1.** This paper is purely theoretical and thus it is very hard to evaluate the practicability of the proposed estimation framework. The numerical simulation also only covers a very simplified synthetic environment. Thus it is unclear how useful or computationally efficient the proposed estimation framework really is.\n\n**2.** I feel this paper is missing a discussion of the line of work on OPE under POMDP. It seems that the OPE on POMDP is naturally connected with the topic of this paper, though I am not very familiar with that line of work. \n\n**Minor**:\n \n**1.** The notation of this paper is a bit heavy. For example, the plus-minus sign confused me for a while when I read about its meaning (“read twice”) at the bottom of page 3. But this is not a big issue and is sort of understandable given the complex framework of this paper. \n\n**2.** This paper is a bit hard to read for readers unfamiliar with this topic. No example or demonstration of any kind is given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer kuGv, thanks for acknowledging the importance of our problem and the strengths of our theoretical results. Please find our responses to your questions below:\n\n**W1: \"This paper is purely theoretical and thus it is very hard to evaluate the practicability of the proposed estimation framework. The numerical simulation also only covers a very simplified synthetic environment. Thus it is unclear how useful or computationally efficient the proposed estimation framework really is.\"**\n\n**Author's Response:** Thank you for the feedback. We would like to offer the following clarifications about usefulness and computational efficiency of our framework:\n1. While our paper is indeed theoretical, it builds upon the well-established marginal sensitivity model (MSM) framework, which has been practically validated in numerous prior studies (e.g. Kallus and Zhou 2021 \"Minimax-Optimal Policy Learning under Unobserved Confounding\", Bruns-Smith and Zhou 2023 \"Robust Fitted-Q-Evaluation and Iteration under Sequentially Exogenous Unobserved Confounders\", and Dorn and Guo 2021 \"Sharp Sensitivity Analysis for Inverse Propensity Weighting via Quantile Balancing\", and many more). Thus, we can be assured that the MSM framework is useful to the broader causal inference community. \n2. Our experiments, though synthetic, serve as a crucial proof of concept. We deliberately designed a synthetic environment where the ground truth $V^-$ is known, allowing us to compute the true error and show that our method converges the fastest.\n3. Regarding computational efficiency, our method is compatible with neural nets as demonstrated in our experiments. Hence, our method offers comparable computational efficiency to standard OPE methods such as doubly robust estimation. This scalability ensures that our approach remains practical for larger-scale applications.\n\n\n**W2: \"I feel this paper is missing a discussion of the line of work on OPE under POMDP. It seems that the OPE on POMDP is naturally connected with the topic of this paper, though I am not very familiar with that line of work.\"**\n\n**Author's Response:** Thanks for bringing up OPE for POMDPs. Indeed, there are several relevant lines of work in this area, each making *unverifiable* assumptions to identify the confounded policy value: \n1. Namkoong et al. (2020) assume confounding occurs at only one step;\n2. Shi et al. (2022) require access to auxiliary mediators;\n3. Bennett and Kallus (2023) utilize bridge functions from proximal causal inference.\n\nOur approach builds on the well-established Marginal Sensitivity Model (MSM) from Tan (2006) to *bound* policy value in the absence of assumptions that point-identify the value given observations. Our key contribution is providing statistically optimal (semiparametrically efficient) estimators for the sequential \"RL\" setting, whereas prior estimators for the MSM were limited to single-step scenarios. Some of this was discussed in our related works section (Sec 1.1). We will add more discussion to the camera-ready.\n\n**W3: \"The notation of this paper is a bit heavy. For example, the plus-minus sign confused me for a while when I read about its meaning (“read twice”) at the bottom of page 3. But this is not a big issue and is sort of understandable given the complex framework of this paper.\"**\n\n**Author's Response:** Thanks for the feedback about plus-minus. To improve readability for the camera-ready, we will focus on the minus case only in the main text and dedicate an appendix section to the symmetric plus case.\n\n**W4: \"This paper is a bit hard to read for readers unfamiliar with this topic. No example or demonstration of any kind is given.\"**\n\n**Author's Response:** We concur that the topic is quite technical and many concepts & notations from stats and RL are required to achieve the mathematical rigor consistent with past works addressing similar topics. To help with clarity, we will dedicate another appendix section to discuss examples, both further elaborating on our experiments, and how the MSM can be useful in real applications (e.g. as in Bruns-Smith and Zhou 2023).\n\n\nThanks again for your helpful feedback. We hope we have addressed your concerns and please let us know if you have any additional questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers agreed that this paper made solid contributions to off-policy evaluation in robust Markov decision processes by proposing two algorithms with theoretical guarantees along with numerical results to verify the effectiveness of the proposed algorithms.
Decision: Accept (poster)