Universal Off-Policy Evaluation
Authors: Yash Chandak
Scott Niekum
Bruno Castro da Silva
Erik Learned-Miller
Emma Brunskill
Philip S. Thomas
Venue: NeurIPS 2021 Poster (2021)
Keywords: metrics
distribution
CDF
off-policy evaluation
OPE
reinforcement learning
counterfactuals
high-confidence bounds
confidence intervals

Abstract: When faced with sequential decision-making problems, it is often useful to be able to predict what would happen if decisions were made using a new policy. Those predictions must often be based on data collected under some previously used decision-making rule.  Many previous methods enable such off-policy (or counterfactual) estimation of the _expected_ value of a performance measure called the return.  In this paper, we take the first steps towards a 'universal off-policy estimator' (UnO)---one that provides off-policy estimates and high-confidence bounds for _any_ parameter of the return distribution. We use UnO for estimating and simultaneously bounding the mean, variance, quantiles/median, inter-quantile range, CVaR, and the entire cumulative distribution of returns. Finally, we also discuss UnO's applicability in various settings, including fully observable, partially observable (i.e., with unobserved confounders), Markovian, non-Markovian, stationary, smoothly non-stationary, and discrete distribution shifts. 

Universal Off-Policy Evaluation
Yash Chandak University of Massachusetts
Scott Niekum University of Texas Austin
Bruno Castro da Silva University Massachusetts
Erik Learned- University of Massachusetts
Emma Brunskill Stanford University
Philip S. Thomas
University of Massachusetts
Abstract
When faced with sequential decision-making problems, it is often useful to be able to predict what would happen if decisions were made using a new policy. Those predictions must often be based data collected under some previously used decision-making rule. Many previous methods enable such off-policy (or coun- terfactual) estimation of the expected value of performance measure called the return. In this paper, we take the first steps towards a universal off-policy estimator (UnO)- that provides off-policy estimates and high-confidence bounds for any parameter of the return distribution. We use UnO for estimating and simultaneously bounding the mean, variance, quantiles/median, inter-quantile range, CVaR, and the entire cumulative distribution of returns. Finally, we also discuss UnO's I appli- cability in various settings, including fully observable, partially observable (i.e., with unobserved confounders), Markovian, non Markoianvi.n, stationary, smoothly non-stationary, and discrete distribution shifts.
1 Introduction
Problems requiring sequential decision decision-making are ubiquitous [5]. When online experimentation is costly dangerous, essential conduct off-policy evaluation before deploying a new policy; that is, one must leverage existing data collected using some policy 3 (called a behavior policy) evaluate performance metric of another policy (called the evaluation policy). For problems with high stakes, such as in terms of health [56] or financial assets [86], it is also crucial to provide high-confidence bounds on the desired performance metric ensure reliability and safety.
Perhaps the most widely studied performance metric in the off-policy setting is the expected return [83]. However, this metric can be limiting for many problems of interest. Safety-critical applications, such as automated healthcare, require minimizing the chances of risk-prone outcomes, and so performance metrics such value at risk (VaR) conditional value risk (CVaR) appropriate [49, 14]. By contrast, applications like online recommendations are subject to noisy data and call for robust metries like the median and other quantiles [2]. In order to improve user experiences, applications involving direct human-machine interaction, such as robotics and autonomous driving, focus on minimizing uncertainty in their outcomes and thus use metrics like variance and entropy [52, 84]. Recent work in distributional reinforcement learning (RL) have also investigated estimating the cumulative distribution of returns [7. 24] and its various statistical functionals [76]. While it may even be beneficial to use all of these different metrics simultaneously inform better decision-making, even individually estimating and bounding any performance metric, other than mean and variance, in the off eff-policy setting has remained an open problem.
more
This raises the main question of interest: How do we develop a universal off-policc method-one one that can estimate any desired performance metrics and can also provide finite-sample confidence bounds that hold simultaneously with high probability for those metrics?
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Off-policy methods can be broadly categorized as model-based or model-free [83]. Model-based methods typically require strong assumptions on the parametric model when statistical guarantees are needed. Further, using model-based approaches to estimate parameters other than the mean can also require estimating the distribution of rewards for every state-action pair in order to obtain the complete return distribution for any policy.
Prior Work:
By contrast, model-free methods are applicable popular technique of using importance- off off-policy distribution. Recent work by Chandak et al. [18] provides a specialized extension to only correct for the variance. Outside RL, works in the econometrics and causal inference literature have also considered quantile treatments [29, 99] and inferences on counterfactual distributions [28, 20, 36], but these methods are not developed for sequential decisions and do not provide any high-confidence bounds with guaranteed coverage. Further, they often mandate stationarity, identically distributed data, and full observability (i.e., no confounding).
wider variety of settings. Unfortunately, the returns [71] only corrects for the mean under the
Existing frequentist high-confidence bounds are not only specifically designed for either the mean or variance, but also hold only individually [92, 45, 18J. Instead of frequentist intervals, a Bayesian posterior distribution over the mean return and various statistics of that distribution can also be obtained [105]. We are not aware of any method that provides off-policy bounds or even estimates for any parameter of the return, while also handling different domain settings that are crucial for RL related tasks. Therefore, a detailed discussion of existing work is deferred to Appendix C.
Contributions: We take the first steps towards a universal aff-policy estimator (UnO) that estimates and bounds the entire distribution of returns, and then derives estimates and simultaneous bounds for all parameters of interest. With UnO, we make the following contributions:
A. For any distributional parameter (mean, variance, quantiles, entropy, CVaR, CDF, etc.), we provide an off-policy method to obtain (A.1) model-free estimators; (A.2) high-confidence bounds that have guaranteed coverage simultaneously for all parameters and that, perhaps surprisingly, often nearly match or outperform prior bounds specifically designed for the mean and the variance; and (A.3) approximate bounds using statistical bootstrapping that can often be significantly tighter.
B. The above advantages hold for (B.1) fully observable and partially observable (i.c., with unob- served confounders) settings, (B.2) Markovian and non- Markovian settings, and (B.3) settings with stationary, smoothly non-stationary, and discrete distribution shifts in a policy's 's performance.
Limitations: Our method uses importance sampling and thus (1) Requires knowledge of action probabilities under the behavior policy 3, (2) Any outcome under the evaluation policy should have a sufficient probability of occurring under 3, and (3) Variance of our estimators scales exponentially with the horizon length [39, 57], which may be unavoidable in non-Markovian domains [46].
For brevity, we first restrict our focus to the stationary setting. In Section 5, we discuss how to tackle non- stationarity and distribution shifts. A partially observable Markov decision process (POMDP) is tuple O, P, S2 R. 7, do), where S is the set of states, O is the set of observations, A is the set of actions, P is the transition function, Ω is the observation function, R is the reward function, 7 [0, 1] is the discount factor, and do is the starting state distribution. Although our results extend to the continuous setting, for notational case, we consider A. O, and the set of rewards to be finite. Since the true underlying states are only partially observable, the resulting rewards and transitions from one partially observed state to another are therefore also potentially non-Markovian [80]. We write Se, O2, Ar, and RS denote random variables for state, observation, action, and reward respectively at time t. Let D be a data set (H,) collected using behavior policies (3x))==- where each H, denotes the observed trajectory (O,. Ao, ((Au On), Ro. O1, ...). Notice that an observed trajectory contains ((,, and does not contain the states S,, for all t. Let
Notation:
G. (1=0) = X' R, be the return of H,, where Vi, Gmin < G, < Gmaxx for some finite constants Gmin and Gmax. and T is finite horizon length. Let G2 and H, be the random variables for returns and complete trajectorics under any policy т, respectively. Since the set of observations, actions, and rewards are finite, and T is finite, the total number of possible trajectories is finite. Let A' be the finite set of returns corresponding to these trajectories. Let Hr be the set of all possible trajectories for any policy Sometimes, to make the dependence explicit, we write g(h) to denote the return of trajectory h. Further, to ensure that samples in D are informative, we make a standard assumption that any outcome under π has sufficient probability of occurring under 33 (see Appendix B. for further discussion of assumptions in general).
2

---

Assumption 1. The set DD contains independent (not necessarily identically distributed) observed trajectories generated using (8.) such that for some (unknown) E 0, (3,(alo) <) (T(alo) = 0), for for all E O,a E A, and i E (1,2.... n.
2
Idea Summary
For the desired universal method, instead of considering each parameter individually, we suggest estimating the entire cumulative distribution function (CDF) of returns first:
VV E R, (= = Pr (G 5v).
Any distributional parameter, (b ). can then be estimated from the estimate of Fx. However, only have off-policy data from a behavior policy 3, and the typical use of importance sampling [71] only corrects for the mean return. To overcome this, we propose an estimator Fa that uses importance sampling from the perspective of the CDF to correct for the entire distribution of returns. The CDF
estimate, Fx. is then used obtain a plug-in estimator (Fx) for any distributional parameter (FF)).
Next, we show that this CDn-centric perspective provides the additional advantage that, we can compute 8 confidence band F : R + 2 such that
Pr Vv R. Pr (G, 2) F(v)) 2
then upper (or lower) high-confidence bound on any parameter, r/( F+), can be obtained by searching for a function F that maximizes (or minimizes) vi (F) and Vv TR has F(v) E F(v).
3 UnO: Universal Off-Policy Estimator
In the on-policy setting, one approach for estimating any parameter of returns, G.. might be first estimate its cumulative distribution Fa and then use that to estimate its parameter ((FF), However, doing this in the off-policy setting requires additional consideration as the entire distribution of the observed returns needs to be adjusted to estimate Fs since the data is collected using behavior policies that can be different from the evaluation policy π.
We begin by observing that Yu E R, (v) can be expanded using the fact that the probability that the return Gx equals is the sum of the probabilities of the trajectories H,, whose return equals x,
F (v) Gr -v)=
Σ
Pr(G, =))= Σ Pr(H, -h) (o00)==)))
TEX,ESV
FEX NEE
where 4 = 1 if A is true and otherwise. Now, observing that the indicator function can be one for most single value less than v as g(h) is deterministic scalar given h, (1) can be expressed as,
F+(1)= Σ Pr(H= h)
Σ
(o(k)==)
Pr(H, Pr(H h)) (1)(o(o)ss)))))))
HEAE
REVE
where the red color is used to highlight changes. Now, from Assumption as V3, Ha C Ho.
F2(1) = PI(H,, = (P)(H,,))(((Ga0 (1)((((0))))))
Pr(H,
Σ NEWP
Pr(HH = h) Pr(Ha h)
Pr(H+ = h) (1 ((((M)s))) (2)
NEWS
The form of (V) in (2) beneficial it suggests a way to not only perform off- aff-policy corrections
for one specific parameter, in prior works [71, 18). but for the entire cumulative distribution function (CDF) of return G,, Formally, let pt II T = ((,,OO, I,,,, denote the importance ratio for H.,
which is equal to Pr(H, = h)/ Pr(Hg = h)) (see Appendix D).
Then, based on (2), we propose the following non non-maraeettic and model-free estimator for F,.
VVER, Pa(e)= : Σ p.l..
Ressults be extended to hybrid probability measures using Radon-Nikodym derivatives.
3

---

Figure 1: An illustration of return distributions for and B. The CDF at any point V corresponds to the area un- der the probability distribution up until v. Having order statistics (G))) of samples (G.) drawn using B, (3) constructs an empirical estimate of the CDF for x (green shaded region) by correcting for the probability of ob- serving each G2 using the importance-samples counts of G S V. Additionally, weighted-IS (WIS) can be used as in (27) for a variance-reduced estimator for Fx.
π
Probability
G(y Gyy Gan Cao)
Ggs
Return
Figure 1 provides intuition for (3). In the following theorem, we establish that this estimator, Fn. unbiased and not only pointwise consistent, but also uniformly consistent estimator of F even when the data D is collected using multiple behavior policies (B+);_ 1- The proof (deferred to Appendix D) also illustrates that by using knowledge of action probabilities under the behavior policies, additional adjustments (e.g.. front-door or backdoor [70]) are required by F.. estimate Ez. even when the domain is non-Markoviag or has partial observability (confounders).
Theorem 1. Under Assumption 1, Fa is an unbiased and uniformly consistent estimator of Fs. YVER, ED (P(()) = =F(FR(()]=F((())
[P((v) - Fa((u] " O.
sup PER
Remark 1. Notice that the value of (v()) can be more than one, even though F (v) cannot have value greater than one for any u E R. This is an expected property of estimators based on importance sampling (IS). For example, the I8 estimates of expected return during off off-policy mean estimation can be smaller or larger than the smallest and largest possible return when > 1.
Having an estimator Fn of Fr. any parameter (FFx) can now be estimated using vb ((xz). However, some parameters like the mean Mr,, variance of. and entropy Hr, are naturally defined using the probability distribution dF, instead of the cumulative distribution F,. Similarly, parameters like the a-quantile Q: and inter-quantily range (which provide tail-robust measures for the mean and deviation from the mean) and conditional value at risk CVaR (which is tail-sensitive measure) are defined using the inverse CDF F- (a). Therefore, let (G be the order statistics for samples (G.) 1=1 and (())- = Gmin- Then, we define the off-policy estimator of the inverse CDF for all [0, 1], and the probability distribution estimator d,F, as,
(a) min {g ge (G (o(9) 2 a).
Fr (G (4)
where d (v) = vf * (()) for any i E (1....,n). Using (4), we now define off-policy estimators for parameters like the mean, variance, quantiles, and CVaR (see Appendix E. for more details on these). This procedure can be generalized to any other parameter of F₂ for which sample estimator vb( (f.) can be directly created using F, as plug-in estimator for Fx.
(f = Σ ab (G) -Ma()))) ?
(Fx)) = Σ dfa (G))))))
CVaR == 1 x
- df, (G) (G
(F(P))==;:
Remark 2. Let H4 be the observed trajectory for the G3 that gets mapped to G( when computing the order statistics. Note that d', (G)) equals ps/n.oor this H. This implies that the estimator for the mean, Ha (Fa), reduces exactly to the existing full call--rrjjector-baee
IS estimator [71].
Notice that many parameters and their sample estimates discussed above are nonlinear in Fx and Fn. respectively (the mean one exception). Therefore, even though F,, is an unbiased estimator of Fz. the sample estimator, u (F.). may biased estimator of sb( F=). This is expected behavior because even in the on- on-policy setting it is not possible to get unbiased estimates of some parameters (e.g., standard deviation), and UnO reduces to the on co-poiccy setting when π B. However, perhaps surprisingly, we establish in the following section that even when yb( (,.)) is biased estimator of (Fx), high-confidence upper and lower bounds can still be computed for both Fş and (FFx).

---

An illustration of Fa (in black) using five return samples and the confidence hand F (red shaded region) com- puted using (5) with confidence intervals (red lines) at three key points ( Notice that the vertical "steps" in F, can be of different heights and their total can be greater than 1 due to importance weighting, However, since we know that F7 never greater than 1, can be clipped at
Figure 2:
CDF
Giain
R4
R2
Kis
4 High-Confidence Bounds for UnO
Off-pooicy estimators are typically prone to high variance, and when the domain can be non- Markovian, the curse of horizon might be unavoidable [46]. For critical applications, this might be troublesome [94] and thus necessitates obtaining confidence intervals to determine how much our estimates can be trusted. Therefore, in this section, we aim to construct a set of possible CDFs F R + 2*, called confulence band, such that the true Fa (v) is within the set F(v) with high probability, i... Pr(vv= E I, Fa (v) E F(v)) 2 8, for any 8 E (0, 1]. Subsequently, we develop dinite-saplle bounds for any parameter (Fx,) using F.
In the on-policy setting. FF can be constructed using the DKW inequality [31] and tight constants [60]. However, its applicability to the off-policy setting is unclear as (a) unlike the on-policy CDF estimate, the "steps" of an off-policy CDF estimate are not of equal heights, (b) the "steps" do not sum to one (see Figure 2) and the maximum height of the steps need not be known either, and (c) DKW assumes samples are identically distributed, however, off-policy data D might be collected using multiple different behavior policies. This raises the question: How do we obtain F in the off-policy setting?
Before constructing a confidence band F, let us first focus on obtaining bounds for a single point, Fx (x).. Let X = p(1(E)))) Then, from Theorem L, we have that Ep[X] = Fa (xx). This implies that a confidence interval for the mean of X provides confidence interval for (x).. Using this observation, existing confidence intervals for the mean of a bounded random variable can be directly applied X to obtain a confidence interval for F3 (x).. For example, Thomas al. [91] present tight bounds for the mean of IS IS-based random variables by mitigating the variance resulting from the heavy tails associated with IS; we use their method on (k) to bound (x). Alternatively, recent work by Kuzborskij et al. [53] can potentially be used with a WIS-based Fz estimate (27).
Before moving further, we introduce some additional notation. Let (r5) be any K "key points" and let CI_ (K,, 6;) and CI (K., 6:) be the lower and the upper confidence bounds Fax (rs) constructed at each key point using the observation made in the previous paragraph, such that
Vie (I,..,,k) Pr (CII- (Ki, 8.) S Fr (x.) S CII 6.)) 2 1
We now use the following observation to obtain a band, F. that contains Fx with high confidence.
Because Fz is CDF, is necessarily monotonically non-decreasing. and so if F2 (m,) 2 CI -I_(K,, 6,) then for any V 2 Ks, Fx (z) must be no less than CI-(K, 6.). Similarly, if Fz Fx(K) < CI (re 6.) then for any p S Ki, (v) must also be no greater than CI+ (12, 84). Let Ko == Gmin. KK+1
Graxx CI (Kp, 5p) == O. and CI+ (KK+1, xx+1) = 1; then, as illustrated in Figure 2, we can construct a lower function F_ and an upper function F_ that encapsulate Fz with high probability,
if Gmaxi otherwise.
if < Gmin F+(1) = min CI (x) otherwise. R.20
0
F-())= max CI_ (K:, RiSH
(5)
Theorem 2. Under Assumption 1, for any E 1), if IK de S 8, then the confidence band defined by F_ and F+ provides guaranteed coverage for Fr. That is,
Pr VYVER, F-(v) & Fz()) ( F+(1)) 21-
5

---

Mean
Quantile
CVaR
Gain
Guas
Cain
Lower bound
Guas
Goin
G
be obtained using geometry. (Left) For a lower bound on the mean, we would want a CDF F E F that assigns as high a probability possible lower G values, and F+ is the CDF which does that. To obtain the mean of F+. the property that the mean of distribution is the area above the CDF on the positive x-axis minus the area below the CDF on the negative x-axis [3]. Hence, the mean of the distribution characterized by F+ is the area of the shaded blue region minus the area of the shaded purple region, and this value the high-confidence lower bound on the mean. (Middle) Similarly, within F, F- characterizes the distribution with the smallest a-quantile. (Right) Building upon the lower bounds for the mean and the quantile, Thomas and Learned- Milller [90] showed that the lower bound for a-CVaR can be obtained using the area of the shaded blue region minus the area of the shaded purple region, normalized by a. To get the upper bounds on the mean, quantile, and CVaR, analogous arguments hold using the lower bound CDF F_. See Appendix E.5 for discussions of variance, inter-quantile, entropy, and other parameters.
Figure 3: Given confidence band F, bounds for many parameters
Remark 3. Notice that any choice of (Re) results in valid band F. However, F can be made tighter by optimizing over the choice of (Ka) 1-11- In Appendix E.5, we present one such method using cross-validation to minimize the area enclosed within F.
Having obtained a high-confidence band for Fx, we now discuss how high-confidence bounds for any parameter (FF)) can be obtained using this band. Formally, with slight overload of notation let F be the set of all possible CDFs bounded between F_ and F-, that that is,
F
YUER, F S F(v) S F4()).
This band F contains many possible CDFs, one of which is F² with high probability. Therefore, to get lower upper bound, t v/+, on (F(x), we propose deriving CDF F that minimizes or maximizes (F), respectively, and we show that these contain (Fxx) )) with high probability:
e == inf FEF
(F)),
ei ;= sup (F). FEF
Theorem 3. Under Assumption for any - confulence band F, the confidence interval defined by vi and s/ provides guaranteed coverage for vi (F²)) That is,
Pr (r(v== 4レ S (FF,)) S 2/ 2 1
While obtaining wh_ might not look straightffrward, one can obtain closed-form expressions for many popular parameters of interest. In other cases, simple algorithms exist for computing & and th+ [74]. Figure provides geometric depictions of the closed-form expressions for some parameters.
Remark 4. Perhaps surprisingly, even though 2/ (FF)) may be biased, we can obtain high-confidence bounds with guaranteed coverage on any (F(Fa) using the confidence band F. In fact, confidence bounds for all parameters computed using (6) hold simultaneously with probability at least 8 as they are all derived from the same confidence band, F.
3.1. Statistical Bootstrapping: An important advantage of having constructed an off-policy estima- tor of any (bF²) is that it opens up the possibility of using resampling- essaepling-baeed methods, like statistical bootstrapping [32], to obtain approximate confidence intervals for v ((F)). ). In particular, we can use the bias-corrected and accelerated (BCa) bootstrap procedure obtain v and ri for (F.). This procedure is outlined in Algorithm in Appendix E.4.
Unlike the bounds from (6), BCa-based bounds do not offer guaranteed coverage and need to be computed individually for each parameter tb. However, they can be combined with UnO to get significantly tighter bounds with less data, albeit without guaranteed coverage.

---

5 Confounding, Distributional Shifts, and Smooth Non-Stationarities
A particular advantage of UnO is the remarkable simplicity with which the estimates and bounds for Fx or (F+)) can be extended to account for confounding, distributional shifts, and smooth non-stationarities that are prevalent in real-world applications [30].
Confounding / Partial Observability: Estimator F, in (3) accounts for partial observability when both π and [ have the same observation set. However, in systems like automated loan approval [94], data might have been collected using behavior policy 3 dependent race and gender that may no longer be allowable under modern laws. This can make the available observation, O, for an evaluation policy т different from the observations, O, for B, which may also have been a partial observation of the underlying true state S.
sensitive attributes like
However, an advantage of many such automated systems (c.g. online recommendation, automated healthcare, robotics) is the direct availability of behavior probabilities (,(A)O). In Appendix D, we provide generalized proofs for all the earlier results, showing that access to 3, (A(O) allows UnO to handle various sources of confounding even when Ô + O, without requiring any additional adjustments. When (A(OO) is not available, we allude possible alternatives in Appendix B.
Distribution Shifts: Many practical applications exhibit distribution shifts that might be discrete or abrupt. One example is when a medical treatment developed for one demographic is applied to
another [37]. To tackle discrete distributional shifts, let F(()) and F!2) denote the CDFs of returns under policy π in the first and the second domain, respectively. To make the problem tractable, similar
to prior work on characterizing distribution shifts [10], we assume that the Kolmogorov-Smiman
distance between F2f and rx? is bounded.
Assumption 2. There exists 2 0, such that sup
F() (P) Sc
VER
Given data D collected in the first domain, one can obtain the bounds FD) and F on F(") as in Section 4. Now since F( can differ from F() by at most at any point, we propose the following bounds for (22) for all E R and show that they readily provide guaranteed coverage for p(2)
F (2) (v) max(0,
( (v) -c), c).
FV) min(1, (v) + +
Theorem 4. Under Assumptions 1 and 2, Vo E (0, 11. the confidence band defined by F2(2) and F(
provides guaranteed coverage for F(2) That is, Pr(vv, F (v) S F (v) < F (v)) 2 1 6.
Smooth Non-stationarity:
The stationarity assumption is unreasonable for applications like online tutoring or recommendation systems, which must deal with drifts of students' interests seasonal fluctuations of customers' interests [93, 88]. In the worst case, however, even a small change in the transition dynamics result in large fluctuation of policy's performance and make the problem intractable. Therefore, similar to the work of Chandak et al. [16], we assume that the distribution of returns for any changes smoothly over the past episodes 1 to L,, and the E episodes in the future. In particular, we assume that the trend of F(()) (v) for all v can be modeled using least-squares regression using a nonlinear basis function Φ R -> IRdd (e.g., the Fourier basis, which is popular for modeling non-stationary trends [12)).
Assumption 3. For any 3w, Rd,, such that, Vi E [1, + F (v) ((1) ww.
Estimating (LL++)) can now be seen as time-series forecasting problem. Formally, for any key point K. let ((( (x) be the estimated CDF using H, observed in episode i. From Thcorem 1, we know that F(0 (x)) is an unbiased estimator of F.()) (ks); therefore, ( (k)) is an unbiased estimate for the underlying time-varying sequence (r+ (n)) Now, using methods from time-series literature, the trend of (F( (x)) can be analyzed to forecast (k). along with its CIs. In particular, we propose using wild bootstrap [58, 26), which provides approximate CIS with finite sample error of (LL-1/2) while also handling nor-normality and heteroskedasticity, which would oceur when dealing with iS-based estimates resulting from different behavior polices [16]. See Appendix E.6 for more details. Finally, using the bounds obtained using wild bootstrap at multiple key points, an entire confidence band can be obtained discussed in Section 4.
7

---

Empirical Studies
In this section, we provide empirical support for the established theoretical results for the proposed
UnO estimator and high-confidence bounds. To do so, we use the following domains: (1) An open source implementation [102] of the FDA-approved type-1 diabetes treatment simulator [59], (2) A stationary and a non-stationary recommender system domain, and (3) A continuous-state Gridworld with partial observability, where data is collected using multiple behavior policies. Detailed description for domains and the procedures for obtaining т and 5 are provided in Appendix F.1; code also publicly available here. In the following, we discuss four primary takeaway results.
(A) Characteristics of the UnO estimator: Figure reinforces the universality of UnO. As can be seen, UnO accurately estimate the entire CDF and wide range of its parameters: mean, variance, quantile, and CVaR.
Recommender System
Gricworld (POMDP)
0.8
0.0
0.6
3.6
0.6
3.4
Return
15
Return
327
207
10
101
10
-10
10
107
10
100
16
Quantile (0.5)
14
10
10'
16a
70'
10a
30P
101
127
10a
101
CVaR (0 25)
10
Number of Irajectories
Number of Trajectories
Number Trajectories
Figure 4: Performance trend of the proposed estimators and bounds three domains. The black dashed line is the true value of F, or e)(Fa, ), green is our UnO estimator, red is our CI-based UnO bound, blue is the bootstrap version of our UnO bound, and yellow is the baseline bound for the mean [91] or variance [18]. Each bound has two lines (upper and lower); however, some are not visible due overlaps. The shaded regions +2 standard error, computed using 30 trials. The plots in the top row are for CDFs obtained using 3 x 104.5 samples. The next four rows are for different parameters and share the same x-axis. Bounds were obtained for failure rate 8 0.05. Since the UnO-Boot and Baseline-CI methods do not hold simultaneously for all the parameters, they were made to hold with failure of 6/4 for a fair comparison (as there 4 parameters in this plot).
(B) Comparison of UnO with prior work: Recent works for bounding the mean [45, 35] assume confounding and Markovian structure. Therefore, for fair comparison, resort to the method

---

Non Stationary Domain (speed=0)
Non-Stationay Domain (speed=1)
Non Statiinattoyy Doma in (2peed=2)
0.75
0.5
0.5
0.50
0.0
0.25
0.0
0.00
Episode
X32
Episode
K1D
Episode
K10
0.5
0.8
0.0
0.4
0.4
0.4
0.0
0.0
2.5 -3.5
0.0
0.5
1.5
1.0
5.5
0.0
0.5
1.0 2.0
-2.3
0.0
0.5
3.5
Return
Retum
Retur
True
NOO-oonStationayy
UnO
Figure 5: (Top row) True rewards (unknown the RL agent) associated with each of the five items over the past 1000 episodes for different speeds of non-stationarity. Speed of 0 indicates stationary setting and higher speeds indicates greater degrees of non-stationariity (Bottom row). The black dashed line is the true value of the future distribution of returns under π:: F((++) where I. T= 1000 and f= 1. In red is our UnO bound that does not account for non-stationarity, and in blue is the wild-bootstrap version of our UnO bound that accounts for non-stationarity. The shaded region corresponds to one standard error computed using 30 trials. Bounds were obtained for a failure rate 5 = 0.05. (Left column) In the stationary setting, both the variants of UnO bounds approximately contain the true future CDF F (((--) In this setting, the UnO method designed only for stationary settings provides a tighter bound. (Middle & Right columns) As the domain becomes non-stationary, UnO bounds that do not account for non-stationarity fail adequately bound the true future CDF E((+() When the degree of non-stationarity is high, not accounting for con-stationarity can lead to significantly inaccurate bounds. By comparison, UnO bounds that use wild bootstrap to tackle non-stationarity provide a more accurate bound throughout. As expected, when the fluctuations due to non-stationarity increase, the width of the confidence band increases as well. These results illustrate (a) the importance of accounting for non-stationarity, when applicable, and (b) the flexibility offered by our proposed universal off- offlcylicy estimator, UnO, to tackle such settings.
of Thomas et al. [91] that can provide tight bounds even when the domain is non- non-Markon Markovian or has confounding (partial observability). Perhaps surprisingly, Figure shows that the proposed guaranteed coverage bounds, termed UnO-CI here, can be competitive with this existing specialized bound, termed Baseline-CI here, for the mean. fact, UnO-CI can often require an order of magnitude less data compared to the specialized bounds for variance [18]; we refer readers to Appendix F,2 for discussion on potential reasons. This suggests that the universality of UnO can be beneficial even when only one specific parameter is of interest.
(C) Finite-sample confidence bounds for other parameters using UnO: Figure 4 demonstrates that UnO-CI also successfully addresses the open question of providing guaranteed coverage bounds for multiple parameters simultancously without additional applications of the union bound. As expected, bounds for parameters like variance and CVaR that depend heavily on the distribution tails take more samples shrink than bounds on other parameters (like the median [quantile(O.5)]] Additional discussion on the observed trends for the bounds is provided in Appendix F.2.
The proposed UnO-Boot bounds, as discussed in Section 3.1, approximate and might not always hold with the specified probability. However, they stand out by providing significantly tighter, and thus more practicable, confidence intervals.
(D) Results for non-stationary settings: Results for this setting are presented in Figure 5. As discussed earlier, online recommendation systems for tutorials, movies, advertisements and other

---

products are ubiquitous. However, the popular assumption of stationarity is seldom applicable to these systems. In particular, personalizing for each user is challenging such settings as interests of user for different items among the recommendable products fluctuate over time. For an example, in the context of online shopping, interests of customers can vary based on seasonality or other unknown factors. To abstract such settings, in this domain the reward (interest of the user) associated with each item changes over time. See Figure 5 (top row) for visualization of the domain, for different "speeds" (degrees of non-stationarity).
In all the settings with different speeds, uniformly random policy was used as behavior policy / to collect data for 1000 episodes. To test the efficacy of UnO, when the future domain can be different from the past domains, the evaluation policy was chosen be a near-optimal policy for the future episode: 1000 + 1.
Conclusion
We have taken the first steps towards developing a universal off-policy estimator (UnO), closing the open question of whether it is possible to estimate and provide finite-sample bounds (that hold with high probability) for any parameter of the return distribution in the off-policy setting, with minimal assumptions the domain. Now, without being restricted to the most common and basic parameters, researchers and practitioners can fully characterize the (potentially dangerous or costly) behavior of a policy without having to deploy it.
There are many new questions regarding how UnO can be improved for policy evaluation by further reducing data requirements or weakening assumptions. Using UnO for policy improvement also remains an interesting future direction. Subsequent this work, Huang et al. [43] showed how models can be used to obtain UnO-style doubly robust estimators along with its convergence rates in the contextual bandit setting. This allows their method to also provide finite-sample uniform CDF bounds for a broad class of Lipschitz risk functionals.
Acknowledgements
We thank Shiv Shankar. Scott Jordan, Wes Cowley, and Nan Jiang for the feedback, corrections, and other contributions to this work. We would also like to thank Bo Liu, Akshay Krishnamurthy, Marc Bellemare, Ronald Parr, Josiah Hanmah, Sergey Levine, Jared Yeager, and the anonymous reviewers for their feedback on this work.
Research reported in this paper was sponsored in part by gift from Adobe, NSF award #2018372. and the DEVCOM Army Research Laboratory under Cooperative Agreement (ARL IoBT CRA). Research this paper also supported part by NSF 1724152,, IIS- 1638107 108, IIS- 1749204, IIS-19250822 ONR (N00014-18-2243) AFOSR 1--9550020-1-00777 and ARO (78372-CS, W91 1NIINF-11 19-2-3333. The views and conclusions contained in this document are those of the authors and should not be interpreted representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Acerbi and Tasche. On the coherence of expected shortfall. Journal of Banking & 2002.
Finance,
[2] J. Altschuler, V.-E Brunel, and A. Malek. Best arm identification for contaminated bandits. Journal of Machine Learning Research, 20(91):1-39, 2019.
[3] T. W. Anderson. Confidence limits for the expected value of an arbitrary bounded random vari- able with a continuous distribution function. Technical report, Stanford University, Department of Statistics, 1969.
[4] M. G. Azar, Munos, and H. Kappen. Minimax PAC bounds on the sample complexity of reinforeement learning with generative model. Machine Learning, 91(3):325-344 2013.
10

---

[5] A. G. Barto, P. S. Thomas, and R. S. Sutton. Some recent applications of reinforcement learning. In Proceedings of the Eighteenth Yale Workshop on Adaptive and Learning Systems, 2017.
[6] M. Bastani. Model-free intelligent diabetes management using machine learning. Master's s thesis, University of Alberta, 2014.
[7] M. G. Bellemare, W. Dabney, and R. Munos. A distributional perspective reinforcement 2017.
learning. arXiv preprint
[8] Y. Benjamini and Y. Hochberg. Controlling the false discovery rate: A practical and powerful approach to multiple testing. Journal of the Royal Statistical Society: Series B (Methodologi- 57)),57(1 1995.
[9] A. Bennett, N. Kallus, L. Li, and A. Mousavi. Off-policy evaluation in reinforcement learning with latent confounders. arXiv preprint arXiv:2007.13888 2020.
[10] V. W. Berger and Y. Zhou. Caimogorov-Smirooe test: Overview. Wiley Statsref: Statistics Reference Online, 2014.
[11] J. Bezanson, Edelman, S. Karpinski, and V. B. Shah. Julia: fresh approach numerical computing. SIAM Review, 59(1):65599)) 18,65-982200 2017.
[12] P. Bloomfield. Fourier Analysis of Time Series: An Introduction. John Wiley & Sons, 2004.
[13] D. B. Brown. Large deviations bounds for estimating conditional value-at-risk. Operations Research Letters, 35(6):722
2007.
[14] D. S. Brown, S. Nickum, and M. Petrik. Bayesian robust optimization for imitation learning. arXiv preprint arXiv:2007.12315, 2020.
[15] F. P. Cantelli. Sulla determinazione empirica delle leggi probabilita. Giorn, 1st. Ital, Attuari, 4(421-424), 1933,
[16] Y. Chandak, S. M. Jordan, G. Theocharous, M. White, and P. S. Thomas. Towards safe policy improvement for non-stationary MDPs. Neural Information Processing Systems, 2020.
[17] Y. Chandak, G. Theocharous, S. Shankar, S. Mahadeean, M. White, and P. S. Thomas. Optimizing for the future in non-stationary MDPs. International Conference on Machine Learning, 2020.
[18] Y. Chandak, S. Shankar, and P. S. Thomas. High confidence off-policy (or counterfactual) variance estimation. Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
[19] S. X. Chen, W. Härdle, and M. Li. An empirical likelihood goodness-off ff- test for time series. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 65(3):663-61) 678. 2003.
[20] V. Cheroozuukov, I. Fernández- Val, and B. Melly. Inference on counterfactual distributions. Econometrica, 81(6):2205-22) 2268, 2013.
[21] K.-J. Chung and M. J. Sobel. Discounted MDP's: Distribution functions and exponential utility maximization. SIAM Journal on Control and Optimizution, 25()):9--6, 1987.
[22] W. Dabney, G. Ostrovski, D. Silver, and R. Munos. Implicit quantile networks for distributional reinforcement learning. arXiv preprint arXiv: 180606693, 2018.
[23] W. Dabney, M. Rowland, M. Bellemare, and R. Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 32, 2018
[24] W. Dabney, Z. Kurth-Nelson, N. Uchida, C. K. Starkweather, D. Hassabis, R. Munos, and M. Botvinick. A distributional code for value in dopamine-based reinforcement learning. Nature, 577(7192):671-6755 2020.
[25] B. Dai, O. Nachum, Y. Chow, L.. Li, C. Szepesvári, and D. Schuurmans. Coindice: Off-policy confidence interval estimation. arXiv preprint arXiv:2010.1 /652,, 2020.
[26] R. Davidson and E. Flachaire. The wild bootstrap, tamed at last. Journal of Econometrics, 146(1):162-16,, 2008
[27] Dearden, Friedman, and S. Russell. Bayesian q-learning. AAAI/AAII, pages 761-768, 1998.
11

---

[28] J. DiNardo, N. M. Fortin, and T. Lemieux. Labor market institutions and the distribution of wages, 1992: A semiparametric approach. Technical report, National Bureau of Economic Research, 1995.
[29] S. G. Donald and Y.-C. Hsu. Estimation and inference for distribution functions and quantile functions in treatment effect models. Journal of Econometrics, 178:383-397, 2014.
[30] G. Dulac-Arnold, D. Mankowitz, and TT Hester. Challenges of real-world reinforcement learning. arXiv preprint arXiv: /2901, 2019.
[31] A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
[32] B. Efron and R. J. Tibshirami. An Introduction to the Bootstrap. CRC press, 1994.
[33] F. Faccio, L.. Kirsch, and Schmidhuber. Parameter-based value functions. arXiv preprint arXiv:2006.092 09226, 2020.
[34] R. Feldt and A. Stukalov. Blackboxoptim. jl, 2019.
[35] Y. Feng, 7. Tang, na zhang, and qiang liu. Non-asymptotic confidence intervals of off-policy evaluation: Primal and dual bounds. In International Conference on Learning Representations.
2021. URL htsps::/ openreview net / / forum? i dKg5D1215111 Lm.
[36] S. Firpo and C. Pinto. Identification and estimation of distributional impacts of interventions using changes in inequality measures. Journal of Applied Econometrics, 31(3):457-448) 2016.
[37] Y. Gao and Y. Cui. Deep transfer learning for reducing health care disparities arising from biomedical data inequality. Nature Communications, 11(1):1-8, 2020.
[38] V. Glivenko. Sulla determinazione empirica delle leggi di probabilita. Gion. 1st. Itll, Attauri., 4:92-99, 1933.
[39] Z. Guo, P. S. Thomas, and E. Brunskill. Using options and covariance testing for long horizon off off-policy policy evaluation. In Advances Neural Information Processing Systems, pages 2492- 2501, 2017.
[40] J. Hanna, P. Stone, and S. Niekum. Bootstrapping with models: Confidence intervals for off off-policy evaluation. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), May 2017.
[41] J. Hanna, S. Nickum, and P. Stone. Importance sampling policy evaluation with an estimated behavior policy. In International Conference on Machine Learning, pages 2605-2613. PMLR, 2019.
[42] J. Harb, T. Schaul, D. Precup, and P.-L. Bacon. Policy evaluation networks. arXiv preprint arXiv:2202.1 1833, 2020.
[43] A. Huang, L. Leqi, Z. C. Lipton, and K. Azizzadenesheli. Off-policy risk assessment in contextual bandits. arXiv preprint arXiv:2104.08977 2021.
[44] S. C. Jaquette. Markov decision processes with a new optimality criterion: Discrete time, The Annals of Statistics, pages 496-505, 1973.
[45] N. Jiang and J. Huang. Minimax confidence interval for off- off-policy evaluation and policy optimization. arXiv preprint arXiv:2002. 02081, 2020.
[46] N. Jiang and Li. Doubly robust off- off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652-661. PMLR, 2016.
[47] N. Kallus and M. Uehara. Double reinforcement learning for efficient off-policy evaluation in Markov decision processes. J. Mach. Learn. Res., 11:1 2020.
[48] N. Kallus and A. Zhou. Confounding-
policy evaluation in infinite-horizon reinforcement learning. arXiv preprint arXivv2002.0455 18, 2020.
[49] R. Keramati, C. Dann, A. Tamkin, and E. Brunskill. Being optimistic to be conservative: Quickly learning CVaR policy. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 34, pages 4436-4443 2020.
[50] K. Khetarpal, M. Riemer, I. Rish, and D. Precup. Towards continual reinforcement learning: A review and perspectives. arXiv preprint arXiv:2012.13490, 2020.
12

---

[51] I. Kostrikov and O. Nachum. Statistical bootstrapping for uncertainty estimation in off off-policy evaluation. arXiv preprint arXiv:2007.13609 2020.
[52] S. R. Kuindersma, R. A. Grupen, and A. G. Barto. Variable risk control via stochastic optimization. The International Journal of Robotics Research, 32(7):806-88)) 825, 2013.
[53] I. Kuzborskij. C. Vernade, A. György, and C. Szepesvári. Confident off-policy evaluation and selection through self-normalized importance weighting. arXiv preprint arXiv:2006. 10460, 2020.
[54] T. Lattimore and M. Hutter. PAC bounds for discounted MDPs. In International Conference Algorithmic Learning Theory, pages 320-334. Springer, 2012.
[55] E. Learned-Miin and J. DeStefano. A probabilistic upper bound differential entropy. IEEE Transactions on Information Theory, 54 (3((1))5522352335 2008.
[56] P. Liao, Klasnja, and S. Murphy, Off-policy estimation of long-term average outcomes with applications to mobile health. Journal of the American Statistical Association, pages 1-10, 2020.
[57] Q. Liu, L.. Li, Z. Tang, and D. Zhou. Breaking the curse of horizon: Infinite-horizon off- aff-policy estimation. In Advances in Neural Information Processing Systems, pages 5356-5366, 2018.
[58] E. Mammen. Bootstrap and wild bootstrap for high dimensional linear models. The Annals of Statistics, pages 255-285, 1993.
[59] C. D. Man, F. Micheletto, D. Lv, M. Breton, B. Kovatchev, and C. Cohelli. The UVA/PADOVA type diabetes simulator: New features. Journal of Diabetes Science and Technology. 8(1): 26-34, 2014.
[60] P. Massart. Probability, pages 1269-1283, 1990.
The tight constant in the Wooretzky-Kiefe-WWoofooo wntuuaiiieieeuuuliittttt The annals of
[61] A. M. Metelli, M. Papini. N. Montali, and M. Restelli. Importance sampling techniques for policy optimization. Journal of Machine Learning Research, 21(141):1-75, 2020.
[62] T. Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka. Nonparametric return distribution approximation for reinforcement learning. ICML, 2010.
[63] T. Morimura, M. Sugiyama, Kashima, H. Hachiya, and T. Tanaka. Parametric return density estimation for reinforcement learning. arXiv preprint
2012.
[64] O. Nachum and B. Dai. Reinforcement learning via Fenchel-Rockafella duality. arXiv preprint 2001:::0000016666 2020.
[65] H. Namkoong, R. Keramati, S. Yadlowsky, and E. Brunskill. Off-policy policy evaluation for sequential decisions under unobserved confounding. arXiv preprini urXiv:2003.05623 2020.
[66] S. Padakandla. A survey of reinforcement learning algorithms for dynamically varying environments. arXiv preprint arXiv:2005.10611 2020.
[67] M. Papini, A. M. Metelli, L. Lupo, and M. Restelli. Optimistic policy optimization via multiple importance sampling. In International Conference on Machine Learning, pages 4999-4999. PMLR, 2019.
[68] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint 1912:01112.0/777
2019.
[69] B. Pavse, I. Durugkar, J. P. Hanna, and P. Stone. Reducing sampling error in batch temporal difference learning. In Proceedings of the 37th International Conference on Machine Learning (ICML), July 2020.
[70] J. Pearl. Causality. Cambridge university press, 2009.
[71] D. Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[72] M. L. Puterman. Markov decision processes. Handbooks in operations research and manage-
ment science, 2:331-434. 1990.
[73] J. P. Romano and C. DiCiccio. Multiple data splitting for testing. Department of Statisties, Stanford University, 2019.
13

---

[74] J. Romano and M. Wolf. Explicit nonparametric confidence intervals for the variance with guaranteed coverage. Communications in Statistics- Theory and Methods, 3138):223-11250, 2002.
[75] M. Rowland, M. G. Bellemare, W. Dabney, R. Munos, and Y. W. Teh. An analysis of categorical distributional reinforcement learning. arXiv preprint arXiv: (a0:::800008800 2018.
[76] M. Rowland, R. Dadashi, S. Kumar, R. Munos, M. G. Bellemare, and W. Dabney. Statistics and samples distributional reinforeement learning. In International Conference on Machine Learning, pages 5528-5536. PMLR, 2019.
[77] T. Schaul, D. Horgan, K. Gregor, and D. Silver. Universal value function approximators, In International Conference on Machine Learning, pages 1312-1320. PMLR, 2015.
[78] P. K. Sen and J. M. Singer. Large Sample Methods in Statistics An Introduction With Applica- tions. Chapman & Hall, 1993.
[79] M. Shaikh. The Glivenko-Cantelli Theorem. http::/hommt uuci cago .ed/
~ -amsha i wwwwwb/wff.. les/glellll / venko- caaieeo--cneeelllll .dd.. Accessed: 2010-09-30.
[80] S. P. Singh, T. Jaakkola, and M. I. Jordan. Learning without state-estimation in partially observable Markovian decision processes. In Machine Learning Proceedings 1994, pages 284-292. Elsevier, 1994.
[81] M. J. Sobel. The variance of discounted Markov decision processes. Journal of Applied Probability, 19(4):794-802, 1982.
[82] D. A. Stephens. The Caatenl Lemma. http://wwwe httt::/wwoe..mperiaaa..co imperiallaaae uk/ - daas /MyWeb/ /M/3//333333 /3/3// Handouts/ veekoCantelll pdd, 2006.
[83] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT Press, Cambridge,
MA, 2 edition, 2018.
[84] A. Tamar, D. Di Castro, and Mannor. Learning the variance of the reward-to-go. The Journal of Machine Learning Research, 17(1):361-36, 2016.
[85] G. Tennenholtz, U. Shalit, and S. Mannor. Off-policy evaluation in partially observable environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10276-10283, 2020.
[86] G. Theocharous, S. Thomas, and M. Ghavamzadeh. Ad recommendation systems for life-time value optimization. In Proceedings of the 24th International Conference on World Wide Web, pages 1305-1310, 2015.
[87] G. Theocharous, S. Thomas, and M. Ghavamzadeh. Personalized ad recommendation systems for life-time value optimization with guarantees. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[88] G. Theocharous, Y. Chandak, P. Thomas, and F. de Nijs. Reinforcement learning for strategic recommendations. arXiv preprint arXiv:2009.078:
2020.
[89] P. Thomas and E. Brunskill. Importance sampling with unequal support. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[90] P. Thomas and E. Learned-Mille Concentration inequalities for conditional value at risk. In International Conference on Machine Learning, pages 6225-6233, 2019.
[91] P. Thomas, G. Theocharous, and M. Ghavamzadeh. High-confidence off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[92] P. Thomas, Theocharous, and M. Ghavamzadeh. High confidence policy improvement, In International Conference on Machine Learning, pages 2380-2388, 2015.
[93] P. S. Thomas, G. Theocharous, M. Ghavamzadeh, I. Durugkar, and E. Brunskill. Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing. In AAAI, pages 4740-4745, 2017.
[94] P. S. Thomas, B. C. da Silva, A. G. Barto. S. Giguere, Y. Brun, and E. Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(64668) 2019.
[95] M. Uehara, J. Huang, and N. Jiang. Minimax weight and q- q-function learning for off-policy evaluation. International Conference on Machine Learning, pages 9659-9668. PMIR, 2020.
14

---

[96] A. W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[97] G. Van Rossum and F. L. Drake Jr. Python tutorial, volume 620. Centrum voor Wiskunde en Informatica Amsterdam, 1995.
[98] E. Veach and L. J. Guibas. Optimally combining sampling techniques for Monte Carlo render- ing. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, pages 419-428, 1995.
[99] L. Wang, Y. Zhou, Song, and Sherwood. Quantile-optimal treatment regimes. Journal of the American Statistical Association, 123622):1243--2544 2018.
[100] T. Wang, M. Bowling, and D. Schuurmans. Dual representations for dynamic programming and reinforcement learning. 2007 IEEE International Symposium on Approximate Dynamic
Programming and Reinforcement Learning, pages 44-51. IEEE, 2007.
[101] D. White. Mean, variance, and probabilistic criteria in finite Markov decision processes; A review. Journal of Optimization Theory and Applications, 56(1):1-29, 1988.
[102] Xie, J. Harrison, and C. Finn. Deep reinforcement learning amidst lifelong non-stationarity. arXiv preprint arXiv:2006. 20fi:00000.0000,, 2020.
[103] J. Xie. Simglucose v0.2.1 (2018), 2019.
URL
s simglucose.
[104] T. Xie, Y. Ma, and Y--X. Wang. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. arXiv preprint arXiv:1906.0332) 2019.
[105] M. Yang, B. Dai, O. Nachum, G. Tucker, and D. Schuurmans. Offline policy selection under uncertainty. arXiv preprint arXiv:2012.069199 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Appendix B
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump-
tions 1, 2, and
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix D.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] code for the proposed UnO method(s) and the domains used for empirical studies are available http:/iiwww..ooo/ysschhaaaaaaaaa
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section F.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] All plots have standard error bars computed using 30 trials.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] All the experiments were conducted on a personal computer with 32 GiB of memory and an Intel Core i7 CPU with 12 threads. Total runtime for all the experiments combined was less than a day.
4. If you using existing assets (c.g., code, data, models) or curating/releasnng assets...
15

---

(a) If your work uses existing assets. did you cite the creators? [Yes] Our code uses Julia
[1], Blackboxoptim library [34], Python [97], and PyTorch [68].
(b) Did you mention the license of the assets? [N/A] Only open-source assets have been used.
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "w88roCWhLZe", "reviewer": "Reviewer_2SVq", "summary": "This paper proposes UnO, which is an off-policy evaluation method that estimates any distributional parameter (mean, variance, etc.) simultaneously by estimating the entire distribution of returns and it provides high-confidence bounds for these parameters. Moreover, UnO can be used in settings with partial-observability, non-Markovianity, non-stationarity, and distribution shifts.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is very easy to follow despite the fact that it presents a lot of ideas, I particularly liked the visualization in Figure 3. Although there is a lot of content in the paper, I think everything was explored with sufficient depth. Only questions I had about the technical parts were about how to address cases with unknown $\\beta$'s or unknown $\\epsilon$'s and these limitations are discussed in Appendix B.2. Maybe, more of Appendix B.2 can be incorporated into the main paper in the final version using the additional page.\n\nAs far as I understood, the main advantage of UnO is to obtain estimates for a variety of useful parameters (with high-confidence bounds that all hold simultaneously) without relying on individual methods to estimate each parameter separately. Then, for UnO to be a feasible alternative to such individual methods, it is crucial for it to be at least competitive with respect to state-of-the-art solutions. However, experiments are lacking in terms of comparisons with the existing literature. Only comparison that is made is with respect to [92] and only in terms of estimating mean and variance. I would like to see more thorough comparisons with the existing methods in terms of all parameters considered in Figure 4.\n\nAgain as far as I understood, the reason why comparisons are lacking is that there is no method that can estimate other parameters in confounded and non-Markovian environments. I am not too familiar with the literature on off-policy evaluation but if that is the case, then it should be highlighted in the introduction that UnO is the first method to estimate these parameters in such environments. Even then, I would still like to see comparisons that evaluate whether UnO is in fact able to learn better estimates in confounded and non-Markovian environments (compared with methods that ignore confoundedness and non-Markovianity).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Vevax0YeCjW", "reviewer": "Reviewer_j4b9", "summary": "Follow-up:\nI check the paper again and now I am persuaded that the proof can be extended to the reward with continuous distribution. There seems no fundamental technical barrier to me. So I deem this issue as resolved and add 1 point.\nHowever, my concern regarding the significance of the paper remains unchanged. The estimator proposed in the paper is based on the importance ratio and estimated CDF which is not novel. I also do NOT think the universality of such an estimator is a big contribution. (It is quite obvious that universality can follow from such estimators.)\nMany significant previous works on OPE have been focused on proposing estimators with important properties, such as doubly robustness (e.g. https://arxiv.org/abs/1511.03722), free of curse of horizon (e.g. https://arxiv.org/pdf/1810.12429.pdf), etc. So there are many other properties that is more meaningful and applicable than a mere universality. An estimator that is only universal but does not come with any other desired and important properties is not an interesting estimator and will be of limited use in practice.\n\nTherefore, I think the universality claimed by this paper is not interesting and significant enough. I feel this paper's significance is a little overstated. \n\n============================\nThis paper studied the OPE problem for sequential decision-making and proposed an estimator that estimates and bounds the entire distribution of returns. The method is model-free and can obtain high confidence bounds for the parameters of the distribution. The method works under different settings of MDP: fully observable MDP vs POMDP; Markovian vs non-Markovian.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Originality: This paper is original. It is the first to study the estimation of a various of parameters of the reward distribution as far as I can tell. \n\nQuality: The quality is OK. Theoretical results have clear proof and empirical results are well-explained. \n\nClarity: The writing is very clear and easy for the readers to understand. \n\nSignificance: The significance of this paper is affected by several factors. First, this paper assumes the return distribution is discrete. This assumption is too strong and restrictive, and the proof of the main results of the paper relies on this assumption. This assumption greatly simplifies the analysis and limits the usefulness of the results. Does the uniformity still hold under the general distribution assumption? As a comparison, in most of the related work, the only assumption on the reward distribution is usually a sub-Gaussian noise. Second, the proposed estimator hat{F} is naive. I suspect that it will suffer from the curse of the horizon. Still, this is avoided under the assumption of a discrete return distribution. \nThird, the main Theorem 2 and 3 rely on knowing the confidence interval defined below Line 161. However, in the general case finding these CIs is itself the major challenge. Therefore, I think all the main results rely on strong assumptions/oracles, which greatly hurts the significance of the results. It is only universal under very simple settings and has very limited usage.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Well addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7UHIvYdbpYS", "reviewer": "Reviewer_wkXw", "summary": "The paper proposes an algorithm for estimating any parameter of the distribution of returns in an off-policy manner, and derives confidence intervals for the quantities of interest. The paper also shows how the proposed algorithm can be extended to deal with many issues commonly faced when applying RL to real world problems (nonstationarity, non-markovian observations, etc.).", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I strongly recommend accepting the paper for publication.\n\n**Quality:**\n\nOverall the quality of the paper is very high. The methods are derived in a principled fashion, and important properties (guaranteed coverage etc.) are proved. The experiments also seem to be well done and are helpful for illustrating properties of the proposed method.\n\n**Significance:**\n\nThe proposed algorithm is very likely to be significant for both practitioners, as well as researchers to build upon. The generality and effectiveness of the proposed algorithm seems extremely useful, as are the confidence bounds that are important for any real-world application of off-policy learning.\n\n**Clarity:**\n\nThe paper is written clearly, although somewhat difficult to understand due to the complicated concepts involved and the large amount of ground covered within the paper. The paper is quite dense with notation, but the authors have helpfully included a notation table in the appendices.\n\n**Originality:**\n\nThe proposed algorithm is novel to the best of my knowledge.\n\n**Miscellaneous comments, questions, and suggestions to improve the paper:**\n\nCiting authors by last name and date instead of with an arbitrary number makes it possible for the reader to recognize what paper is being referred to if they're already familiar with it. It's also nice to give explicit credit to authors whose work is being built upon.\n\nLine 76: Why use discounting when there's a horizon length $T$? Is it just for the sake of generality?\n\nLine 84: It would be nice to comment on assumptions, explaining why they were made, any ramifications/limitations due to them, whether they are common, restrictive, etc.\n\nLine 273: What is the utility of confidence intervals that don't hold with the specified probability? Are they even confidence intervals in that case?\n\nIt might be better to plot confidence intervals rather than standard error. The reason I write this is that non-overlapping confidence intervals imply statistical significance, whereas non-overlapping standard error does not. This doesn't seem to matter as much for this paper though, as the experiments focused more on investigating properties of the proposed algorithm rather than comparing it against competitors (of which there seem to be few).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper does a thorough and honest job of addressing limitations and potential negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "4iDt3PnvRAN", "reviewer": "Reviewer_ZS4a", "summary": "The paper introduces UnO, a framework for estimating confidence bounds for many parameters of the reward in an off-policy setting and with finite state-action spaces. In this work, first an estimator for the CDF of the return is provided, which makes use of an importance sampling correction. From this estimator, it is easy to derive estimators for many useful parameters. Although these estimators are in general biased, it is possible to derive high confidence bounds for any of these parameters.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "\n\nThe paper is very well written and easy to follow. The authors provided a very extensive literature review on off-policy parameter estimation methods. \n\nOne thing that is missing in the paper is an analysis of which assumptions are needed in order to apply a concentration inequality for such parameters. Since the proposed estimators rely on importance sampling, a lot of concentration inequalities are not suitable. For instance, standard high confidence bounds require some moments of the importance weights to be bounded, which reflects on a condition on the Renyi divergence between the target and behavioral policies[1]. It is not clear to me how these conditions will change when computing a bound for a general nonlinear function of F. In general, these concentration inequalities might be impossible to apply without further analysis.\n\nI am happy to increase my score if the authors will clarify in the paper the issue above.\n\n[1]Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Advances in Neural Information Processing Systems, pp. 5442–5454, 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies off-policy evaluation through estimates and high-confidence bounds on any parameter of the return distribution, such as its mean, variance, IQR, etc. The authors make use of importance sampling, an often-used tool in observational studies, proving that it leads to unbiased and consistent estimation of the cumulative distribution of rewards. This is later extended to provide high-confidence bounds on the CDF, and for parameters of the CDF. The implications of various commonly made assumptions are discussed and the estimators are evaluated empirically. 

The reviews were predominantly positive, arguing for acceptance with one exception. One of the main limitations raised by reviewer j4b9 was that the return distribution is assumed to be discrete. The authors clarified in their response that this limitation may be removed. Additional clarifications were made by the authors which imply only small modifications to the manuscript. 
Decision: Accept (Poster)