Off-Policy Risk Assessment in Contextual Bandits
Authors: Audrey Huang
Liu Leqi
Zachary Chase Lipton
Kamyar Azizzadenesheli
Venue: NeurIPS 2021 Poster (2021)
Keywords: off policy evaluation
contextual bandits
double robustness
cumulative distribution functions
risk functionals

Abstract: Even when unable to run experiments, practitioners can evaluate prospective policies, using previously logged data. However, while the bandits literature has adopted a diverse set of objectives, most research on off-policy evaluation to date focuses on the expected reward. In this paper, we introduce Lipschitz risk functionals, a broad class of objectives that subsumes conditional value-at-risk (CVaR), variance, mean-variance, many distorted risks, and CPT risks, among others. We propose Off-Policy Risk Assessment (OPRA), a framework that first estimates a target policy's CDF and then generates plugin estimates for any collection of Lipschitz risks, providing finite sample guarantees that hold simultaneously over the entire class. We instantiate OPRA with both importance sampling and doubly robust estimators. Our primary theoretical contributions are (i) the first uniform concentration inequalities for both CDF estimators in contextual bandits and (ii) error bounds on our Lipschitz risk estimates, which all converge at a rate of $O(1/\sqrt{n})$.

Off-Policy Risk Assessment in Contextual Bandits
Audrey Huang
Liu Leqi
Department of Computer Science University of Illinois Urbana-Champaign
Machine Learning Department Carnegie Mellon University Pittsburgh, PA 15213 leqil@cs cmu. edu
Urbana, II. 61801 audreyh5@illinois. edu
Zachary C. Lipton
Kamyar Azizzadenesheli
Machine Learning Department
Department of Computer Science
Carnegie Mellon University
Purdue University
Pittsburgh, PA 15213 zlipton@cmu. edu
West Lafayette, IN 47907 kamyar@purdue edu
Abstract
Even when unable to run experiments, practitioners can evaluate prospective poli- cies, using previously logged data. However, while the bandits literature has adopted diverse set of objectives, most research on off-policy evaluation to date focuses on the expected reward. In this paper, we introduce Lipschitz risk fune- tionals, a broad class of objectives that subsumes conditional value-at-riss (CVaR), variance, mean-variance, many distorted risks, and CPT risks, among others. We propose Off-Policy Risk Assessment (OPRA), framework that first estimates tar- get policy's CDF and then generates plugin estimates for any collection of Lipschitz risks, providing finite sample guarantees that hold simultaneously over the entire class. We instantiate OPRA with both importance sampling and doubly robust esti- mators. Our primary theoretical contributions are (i) the first uniform concentration inequalities for both CDF estimators in contextual bandits and (ii) error bounds on our Lipschitz risk estimates, which all converge a rate of O(1/ (1/vn).
Introduction
Many practical tasks, including medical treatment [50 and content recommendation [31 are com- monly modeled within the contextual bandits framework. In the online setting, agent observes a context at each step and chooses among the available actions. The agent then receives a context- dependent reward corresponding to the action taken, but cannot observe the rewards corresponding to alternative actions. In healthcare setting, the observed context might be a vector capturing vital signs, lab tests, and other available data, while the action space might consist of the available treatments. The reward to optimize could be a measure of patient health or treatment response.
While contextual bandits research has traditionally focused the expected reward, stakeholders often care about other risk functionals (parameters of the reward distribution) that express real-world desiderata have desirable statistical properties. For example, investors
mutual funds via the Sharpe ratio, which normalizes returns by their variance [4]. Related works in reinforcement learning (RL) have sought estimate the variance of returns [41 48) and optimize the mean return under variance constraints (33. In safety-critical and financial applications, researchers often measure the conditional value-at-risk (CVaR), which captures the expected return among the lower quantile of outcomes [40 28] In an emerging line of RL works, researchers have explored other risk functionals, including cumulative prospect weighting [22] distortion risk measures [3] and
exponential utility functions [16].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In many real-worle problems otherwise suited to the contextual bandits framework, experimentation turns out be prohibitively expensive or unethical. In such settings, we might hope to evaluate prospective policies using the data collected under a previous policy. Formally, this problem is called off-policy evaluation, and our goal to evaluate the performance of a target policy и using data collected under behavior policy 3. While most existing research focuses on estimating the expected value of the returns [20 one recent paper evaluates the variance of returns [10].
In this paper, we propose practical methods and the first sample complexity guarantees for off-policy risk evaluation, addressing a diverse set of objectives of interest to researchers and practitioners. Towards this end, we introduce Lipschitz risk functionals which encompass all objectives for which the risk (i) depends only on the CDF of rewards; and (ii) is Lipschitz with respect to changes in the CDF (as assessed via the sup norm). We prove that for bounded rewards, this class subsumes many risk functionals of practical interest, including variance, mean- vernnnaar,nc,, conditional value-at-risk, and cumulative prospect weighting, among others.
Thus, given accurate estimates of the CDF of rewards under n, we can accurately estimate Lipschitz risks. Moreover, (sup norm) bounds on our CDF estimates imply bounds on the corresponding plugin estimates for any Lipschitz risks. The key remaining step is to establish finite sample guarantees on the error in estimating the target policy's CDF of rewards. Our analysis centers on an importance sampling estimator (Section 5.1). and a variance-reduced doubly robust estimator (Section (.3)). We derive finite sample concentrations for both CDF estimators, showing that they achieve the desired O(1/ nn) rates, where is the sample size. Moreover, the estimation error for any Lipschitz risk is scales with its Lipschitz constant, and similarly converges as O(1/vn))
We assemble these results into an algorithm called OPRA (Algorithm I that outputs a comprehensive risk assessment for a target policy म, using any set of Lipschitz risk functionals. Notably, because all risk estimates share the same underlying CDF estimate, our error guarantees hold simultaneously for all estimated risk functionals in the set, regardless of the cardinality (Section 6). Finally, we present experiments that demonstrate the practical applicability our estimators.
2 Related Work
The study of risk functionals and risk-aware algorithms is core to the decision making literature
37 25). In the bandit literature, many works address regret minimization problems using risk functionals; popular examples include the CVaR, value-at-risk, and vvriinna [8] 41 60)
3
40
29
43
54
49 studies optimistic UCB exploration for optimizing CVaR while [11 6 study Thompson sampling, and (27 7 study regret minimization for linear combinations of the mean and CVaR. Using the CPT risk functional, 22 considers regret minimization in both K-armed bandits and linear contextual bandits. [53] 35) tackle the problem of black-box function optimization under different risk functionals.
In off-policy evaluation, we face an additional challenge due to the discrepancy between the data distribution and that induced by the target policy. Importance sampling (IS) estimators among the most prominent methods for dealing with distribution shift [2] 23 (5). Doubly robust (DR) estima- leverage (possibly misspecified) models to achieve lower variance without sacrificing
tors 33 3
consistency. These estimators have been adapted for off-policy evaluation in multi-armed bandits
32
52
10
contextual bandits 20 19 57 and Markov decision processes (4 51
After deriving our key results, we learned of an independent (also unpublished) work that also employs importance sampling to estimate CDFs for the purpose of providing off- off-policy estimates for parameters of the reward distribution. However, they do not establish uniform concentration of their CDF estimates or formally relate the errors in CDF and (downstream) parameter estimation leaving open questions concerning the convergence (both in finite samples and asymptotically) of the parameter estimates.
Our work formulates both importance sampling and variance-reduced doubly robust estimators and provides the first uniform finite sample concentration bounds for both types of CDF and risk estimates. For empirical CDF estimation, we build on seminal work by (21], which provided an approximation-theoreee concentration bound that was later tightened by [34].

---

3
Problem Setting
We denote contexts by X and the corresponding context space by X. Similarly, we denote actions by A and the corresponding action space by A. We study the contextual bandit problem characterized by fixed probability measure In the off-policy setting, we have access to a dataset 'D generated using a behavior policy 3 that interacts with the environment for n rounds as follows: at each round, a new context X is drawn and then the policy 3 chooses an action A ~ 3(-(X). The environment then reveals the reward R R(-|X, A) for only the chosen action A. Running this process for stepsgenerates dataset D {zt, ag ra 1==1- In the off-policy evaluation setting, our goal is to evaluate the performance of a target policy n, using only a dataset D.
context space X, and conditional reward distribution R(-I.X, A).
Next, we can express our sample space in terms of the contexts, actions, and rewards: Ω = (X' x A R). Let (2, FPp)) be the probability space induced by the behavior policy B, and F.. P) the probability space induced by the target policy л. We assume that is absolutely contin- uous with respect Pg. For any context and action a, the importance weight expresses the ratio be-
tween the two densities w(w))= = w(a, x) = x))
A(ala) and the maximum weight Wmax = suPa, a, w((a
simply the supremum taken over all contexts and actions. Further, let wa Er, [we( A, x) denote the exponential of the second order Rényi divergence. Note that by definition, S Wmmax. and in practice, we often have Wig < mmax
For any t E R. let F(t) = [e[L] denote the CDF under the target policy; further, let G(t; X, A) = [[ |X, [1 (Rge)) XX, A] denote the CDF of rewards conditioned on context X and action A, which independent of the policy. Lastly, for any R, we denote the variance by o² Xt; V7 [R()) X A| VF, [_
Finally, we introduce some notation for describing CDFs:
4 Lipschitz Risk Functionals
We now introduce Lipschitz risk functionals, a novel class of objectives for which absolute differences in the risk are bounded by sup norm differences in the CDF of rewards. After formally defining the class, we provide an de-thpth review of common risk functionals and their relationship to the CDF of rewards. When possible, we derive the associated Lipschitz constants, when rewards are bounded on support [0, D). relegating all proofs to Appendix A.2
4.1 Defining the Lipschitz Risk Functionals
The Lipschitz risk functionals are a subset of the broader family of law-invariant risk functionals. Formally, let Z Lo, P2) denote a real-valued random variable that admits CDF Fz (R, (.) A risk risk functional p is a mapping from space of random variables to the space of real R. Any risk functional p is said to be law-invariant if p(Z) depends only on the distribution of Z 30
numbers p Loo (R,, F2,
Definition 4.1 IIaa-Inva Risk Functional). A risk functional p Loo F, - RR is law- invariant if for any pair of random variables Z and Z', Fz = Fzz = p(Z) = p(Z')
When clear from the context, we sometimes abuse notation by writing p( p(Fz) in place of p( In general, it may not be practical to estimate risk functionals that not law invariant from data (4) Thus focusing on law-invariant risks is only mildly restrictive.
We can now formally define the Lipschitz risk functionals:
Definition 4.2 (Lipschitz Risk Functional), law invariant risk functional p is L-Lipschitz if for any pair of CDFs Fz and Fz and some I, E (0, oo), it satisfies
lp(Fz) - p(Fz)) ) S F - Fz 11x.
A risk functional is L-Lipschitz if, for any two random variables Z, Z'. its value is upper bounded by the sup-norm of the difference between their corresponding CDFs. The significance of this Lipschitzness property in the contextual bandit setting is that, given high confidence bound on the error of the estimated CDF of rewards for a policy n, we can obtain high confidence bound on its evaluation under any L-Lipschitz law-in inwirraiiant risk functional on the distribution of rewards.
3

---

4.2 Overview of Common Risk Functionals (and their Lipschitzness)
We now briefly describe some popular classes of risk functionals and, when possible, derive their associated Lipschitz constants.
Coherent Risk Functionals
The set of risk functionals that satisfy properties called monotonicity, subadditivity, translation invariance, and positive homogeneity (see Appendix (A.)). constitute the
coherent risk functionals [3 [5]. While not all coherent risk functionals are law-invariant, nearly
among those commonly addressed in the literature are. Examples include expected value, conditional
value-at-risk (CVaR), entropic value-at-risk, and mean semideviation the Wang transform function [55] and the proportional hazard (PH) risk functional [58]
43 Others include
Distorted Risk Functionals When the random variable Z is required to be non-negative, law- invariant coherent risk functionals are examples of the more general class of law-invariant distorted For Z 2 0, a distorted risk functional has the following form
risk functionals 55 56
C,
where the distortion function 9 [0, 1] [0 is increasing function with g(0) 0 and g(1) = 1. Distorted risk functionals are coherent if and only if g is concave (58] For example, when g(s) min(s- 1} for s E [0, 1] and E (0, 1), CVaR at level is recovered. When g is the identity map. the distorted risk functional is the expected value. The Wang risk functional at level a (55] is recovered when g(s) = [(F-((FF)) (s) - F (a:). and the proportional hazard risk functional can by obtained by setting g(s) = s" for < 1. Not all distorted risk functionals are coherent. For example, setting (ss) = 1 (+21- 1-)) recovers the value-at-riss (VaR), which is not coherent.
Lemma 4.1 (Lipschitzness of Coherent and Distorted Risk Functionals). On the space of random variables with support in [0. D). the distorted risk functional of any I Lipschitz distortion function g: [0, 1] + [0, 1]. i.e., (g(t) - g(t') S $1 b sittt',, t',, is L-Lipschitz risk functional.
Remark 4.1 (Expected Value and CVaR), Both expected value and CVaR are examples of distorted risk functionals. Then using Lemma 4.1 on the space of random variables with support in [0, D), the expected value risk functional is D- Lipschitz because is the identity and thus I-Lipschitz On the same space, the risk functional CVaR, is 2 -Lipschhitz because g is Lipschittz
Cumulative Prospect Theory (CPT) Risk Functionals
CPT risks 337 take the form:
P(F2) = -o g (1 (1- Fut (2) dt 1, +00
g (1 (1- (2)(()))))))))))))))))))) dt,
where g+.g 99 [0, 1] + [0, 1] are continuous functions with g / (0) = and g /// = The functions u² u IR + _2 are continuous, with (2) 0 when 2 2 and (z) 0 when z < e for some constant e E IR. Importantly, the CPT functional handles gains and losses separately.
The functions u+ u compare the random variable Z to baseline c, and the distortion g is applied to "gains" (when Z 2 c), while g is applied to "losses" (when Z < <).
Lemma 4.2 (Lipschitzness of CPT Functional). On the space of random variables with support in [0. D), if the CPT distortion functions g* and g are both 1 -Liisschitz, then the CPT risk functionals L-Liipchitz
The variance, mean-variance, and many other popular risks do not fit cas- ily into the aforementioned classes, but are nevertheless law-invariant. For example, for a nonnegative
Other Risk Functionals
random variable Z, the variance is defined as p(Fz) = 2 f 1(1 (1-Fz (1)Fx(())d (Jo 00 (1 Fx()))d(²
Moreover, the variance and mean-variant are both L-Lipschitz.
Lemma 4.3 (Lipschitzness of Variance). On the spuce of random variables with support in [0, DJ. variance is a 2 Lipschhttz risk functional.
A number of recent papers have addressed risk functionals expressed as weighted combinations of others, e.g., anea--arianee [4]. Other papers have optimized constrained objectives, such as expected
reward constrained by variance or CV&R below a certain threshold 212 38 When expressed as
Lagrangians, these objectives can also be expressed as weighted combinations of the risk functionals involved. We extend the Lipschitzness property to risk functionals of this form:

---

Lemma 4.4 (Lipschitzness of Weighted Sum of Risk Functionals). Let p be a weighted sum of risk functionals Pl. PI..... PK that are Li.... LK Lipschitz, respectively, with weights Ai..... AK > 0, i.e. p(Z) = -En=I \. Then p is Ex Lipschiic
Remark 4.2. Note that mean-variance is given by p(Z) E + (V(Z) for some X 0. Then, using Lemma 4.4 we immediately obtain that mean-variance is (1 + 3XD" -Lipschii.
Though we have provided many examples of Lipschitz risk functionals in this section, it is worth noting that there are a number of risk functionals that do not satisfy the Lipschitzness property, such as the value-at-risk (VaR). For the sake of brevity, we omit consideration of such risk functionals in this paper, and outline future avenues of research on this topic in the discussion.
Off-Policy CDF Estimation
This section describes our method for high-confidence off-policc estimation of F, the CDF of returns under the policy æ. The key challenge estimating is that the reward samples are observed only for actions taken by the behavior policy B. To overcome this limitation, one intuitive solution is to reweight the observed samples according to their importance sampling (IS) weight (Section [.1]. However, IS estimators are known to suffer from high variance. To mitigate this, we define the first doubly robust CDF estimator (Section 5.3)
5.1 CDF Estimation with Importance Sampling (IS)
Given an off-policy dataset D = {Ii, az Di,Tihe we define the following nonparametrie IS-based estimator for the empirical CDF,
Fis(!)
1 Σ 24) (nise)
where w(a, .r) stolz]
S(alz) are the importance weights. The IS estimator pointwise-unbiased, with variance given below (proof in Appendix [B:]): Lemma 5.1. The 18 estimator
is unbiased and its variance is
VE. [Bs(t) Ez, (A (t: 1 -Vp Ez, (x(A
- Ep, VVg [w(A X]G(;XX
The expression for variance is broken down into three terms. The first term represents randomness in the rewards. The second term represents variance due the randomness over contexts X. The final term is the penalty arising from using importance sampling, and is proportional to the importance sampling weights w and the true CDF of conditional rewards G. The variance contributed by the third term can be large when the weights w have wide range, which occurs when 3 assigns extremely small probabilities to actions where æ assigns high probability.
Due to the use of importance sampling weights, the estimated CDF Fis (t) may be greater than 1 for some f, even though a valid CDF must be in the interval [0, 1] for all t. To mitigate this problem, a weighted importance sampling (WIS) estimator can be used, which normalizes each importance weight by the sum of importance weights:
Fwis(t) Ennwway
Σ wo Iz) L:)
w w()
which 19] shows is a biased but uniformly consistent estimator. Another option is the clipped estimator IS- 2 which simply limits the estimator to the unit interval:
Pis.ccur (1) = min (t) 1).
Although Fis-cur has lower variance than the IS estimator, is potentially biased. However, given finite samples, we can bound with high confidence the sup-norm error between FTs Fis.cue and P, in Theorem below (proof in Appendix B.2)
5

---

Theorem 5.1. Given samples drawn from Pp. for the IS estimator Fis, we have
8w max
P3 |Fis Fl s EIS,
log(4/0)
2 1
(3)
or, based on w2, we obtain Bernstein-style bound.
S EIS² = mam (og(4/)) Po -
F -
2w log (4/5)
2V
2 21-8.
(4)
The same bounds hold for ||Fis-cLP - Fll
When Wa < Wmazz observe that inequality 4 is more favorable than inequality (3) Theorem 5.1 demonstrates that the Fis-cun uniformly converges to the true CDF at rate of O(1//n, with the uniform consistency of Fis-cup as an immediate consequence. To the best of our knowledge, it is the first DKW-style concentration inequality the importance sampling estimator CDF estimator in off-policy evaluation. The bound has explicit constants and subsumes the classical DKW inequality.
5.2 Model-Based CDF Estimation
As have shown previously, IS estimators can suffer from high variance, which can be limiting in practice. However, in many practical applications, conditional distribution G(t; X, A), which can be used in estimation with very low variance. In many cases, practitioners may have a model of G from expert studies or from a simulator, or can form regression estimate of from logged data. One simple model-based estimator can then be obtained using the direct method, which simply employs the model G for each observed context:
may have access to model G(t; X, A) of the
(t) = > ((t where G(t,ai,))) = Σ x
(5)
Because the DM estimator PDM does not use importance weights, it can have significantly lower variance than the IS and DR estimators. In general, however, the DI estimator biased, and its error flows directly from error in the model G (full derivations of the bias and variance are given in Lemma E.3 of Appendix D). The magnitude and distribution of bias over the context and action space is difficult to characterize. In practice, G is often estimated or modeled agnostic to the target policy, and hence may not be appo-appro in areas that are important for æ. If G is an accurate model of the conditional reward distribution, however, then FDM is a good approximation of F.
5.3 Doubly Robust (DR) CDF Estimation
We now define doubly robust (DR) CDF estimator that takes advantage of both importance sampling and models G' to obtain the best characteristics of both types of estimation. In particular, the DR estimator unbiased, but has potentially significant reduction variance. The DR estimator for the empirical CDF is defined to be
FDR = 1 Σ w(a, 2.) (1 (m:se) - -(t: (I): n
(6)
where G(I; -) Er, [GI, xr, A) Informally, the DR estimator takes the model G baseline,
using the available data to apply a correction. While T alone may be biased, FDR is an unbiased estimator of F. and can have reduced variance compared the estimator (proof in Appendix C.I):
Lemma 5.2. The DR estimator
(6) is unbiased and its variance is
VE, [PDR(1] = - Er,
(1) X1; A)] + Vr, [Er,
X,a)
Epp [Vra [w X) (G(t: X, G(t:X, A)) [x]]
n

---

The variance reduction advantage of the DR estimator becomes apparent from a direct comparison of the three terms in the IS estimator variance (Lemma (5I) and the DR estimator variance (Lemma [5. The first and second terms, which capture the variance in rewards and contexts, are identical. The third term, which represents the importance sampling penalty, is proportional to G - G in the DR estimator, but proportional to G in the IS estimator. When this difference G is smaller than G, which is often the case in practice, the third term has reduced variance in the DR estimator. The magnitude of variance reduction is greater when the weights w have a large range, which is precisely when large variance can become problematic in importance sampling.
Remark 5.1 (Double Robustness). Although we consider the setting where the behavior policy 3 is known, when 3 is unknown and needs to be estimated, the estimator FDR is consistent when either G is consistent or the policy estimator is consistent. This is where the name "doubly robust" comes from. We demonstrate and discuss this fact further in Appendix L
Although the DR estimator FOR has desirable reductions in variance, given finite samples, is not guaranteed to be valid CDF. Like the IS estimator. the DR estimator may be greater than 1 for some t due to the use importance weighting. However, it may also be negative at some as a consequence of the subtracted term in 66). As an additional consequence of this term, the DR estimator is not guaranteed to be a monotone function. As a result, in order to use the DR CDF estimate for risk estimation, we must transform FDR into a monotone function bounded in [0, 1]. Examples of such transformations include isotonic approximation [46 and monotone Lp approximation [14.
For our analysis, however, we consider a simple monotone transformation that involves an accu- mulation function, which does not allow the CDF decrease, followed by clipping to [0. 1]:
M (4) Clip max PDR (t') (t),
l'st
which is uniformly consistent estimator, the following concentration guarantee shows:
Theorem 5.2. The monotone transformation of the DR estimator MM-DR(() satisfies
Pa (1
72w2
8n-/2
F|
S == V
log
2
(8)
n
The proof is in Appendix C.2 The purpose of Theorem 5.2 is to show the dependence of the error on the importance weights Wmar and on the finite sample size n. Using the M-DR estimator, we again recover sample complexity of Ô (1 /n). The proof is given in Appendix C.2 Note that (8) does not depend on the error G - G, which is the term responsible for variance reduction, as given in Lemma
B.5 A tighter bound that incorporates the error G G remains an open problem.
6 Off-Policy Risk Assessment
Given any law-invariant risk functional p and CDF estimator F, we can estimate the value of the risk functional as f: : p(F). However, the estimator p may be biased even if F is unbiased. For Lipschitz risk functionals introduced in Section we can obtain their finite sample error bounds, using the error bound of the CDF estimator. Further, a set risk functionals of interest can be evaluated using the same estimated CDF, which suggests that the error bound of the CDF gives error bounds on the risk estimators that hold simultancously.
Theorem 6. Jutilizes error bound of the estimated CDF to derive error bounds for estimators of set of Lipschitz risk functionals. As we showed in Section most if not all commonly studied risk functionals satisfy the property of Lipschitzness, showing result's wide applicability.
Theorem 6.1. Given set of Lipschitz risk functionals {p with Lipschitz constants } and a CDF estimator F, such that || Flloc E c with probability at least 8, we have with probability least 8 that for all p P]....P.
(T) - Pp(FF) s Lipe.
7

---

Thus, one powerful property of risk estimation using the estimated CDF approach is that, given high- probability error bound on the CDF estimator, the corresponding enror bounds on estimates of all Lipschitz risk functionals of interest hold simultaneously with the same probability. Further, because the error of the IS CDF estimator éis (Theorem 5.T) and DR CDF estimator <DR (Theorem (52) converge at rate of O(1/vn)) Theorem 6.1 shows that the error of all Lipschitz risk functional estimators shrink
rate of O(I/VT). Thus, Pp are consistent risk functional estimators.
Remark 6.1. When p is the expected return, the Lipschitz constant is L D, where D is the maximum reward, and we achieve a convergence rate of mo / /n). This matches the rate of error bounds for off ooolcol mean estimation previously derived in [20].
Putting these results together, we now provide an algorithm, called OPRA (Algorithm I which given off-policy contextual bandit dataset and of Lipschitz risk functionals of interest, outputs for each risk functional an estimate of its value and a confidence bound. The algorithm first uses a valid CDF estimator, e.g., the clipped IS estimator (2 or monotonized DR estimator ( to form F with sup-norm enror OPRA then evaluates each Ly LipLiischitz risk functional Py on F to obtain Pp. along with its upper and lower confidence bound Pp + Typ..
Algorithm 1: Off-Policy Risk Assessment (OPRA)
Input: Dataset D, policy т, probability 8, models G. Lipschitz risk functionals fp with Lipschitz constants {
Estimate the CDF using a valid CDF estimator F:
Compute the corresponding CDF estimation error e such that PP[] Flooo 26)21-0
3 for p=rp do Estimate Pp Pp(F);
5 end
Output: Estimates with errors (op + Lp
OPRA can be used to obtain a full risk assessment of any given policy, using the input Lipschitz risk functionals of interest, which can include the popularly used mean, variance, and CVaR. As demonstrated in Theorem 6.1 the error guarantee the risk estimators holds simultancously for all P risk functionals with probability at least 8. Importantly, OPRA also demonstrates the computational efficiency of the distribution-centtio risk estimation approach proposed in this paper. For a given π, the CDF only needs to be estimated once, and can be used repetitively to estimate the value of the risk functionals. Further, the error of the risk estimators are determined by the known error of the CDF estimator, multiplied by the known Lipschitz constants.
7 Empirical Studies
In this section, we give empirical evidence for the effectiveness of the doubly robust (DR) CDF and risk estimates, in comparison to the importance sampling (IS), weighted importance sampling (WIS), and direct method (DM) estimates. Further, we demonstrate the convergence of the CDF and risk estimation error in terms of the number of samples. In our experiments, the relevant baselines are the IS and WIS CDF estimators with plugin risk estimates, both of which were contemporaneously proposed by (9, which are the only existing off-polic estimators for general risks. In most of our experiments, the DR CDF and risk estimates exhibit reduced variance compared to the baselines, a possibility suggested by theoretical results.
7.1 UCI Datasets
Setup. Following 20 19 57], we obtain our off off-policy contextual bandit datasets by transforming classification datasets. The contexts are the provided features, and the actions correspond to the possible class labels. To obtain the evaluation policy n, we use the output probabilities of a trained logistic regression classifier. The behavior policy is defined B au + (1 a:) TUNIF where TUNIF a uniform policy over the actions, for some a E (0, 1). We apply this process to the PageBlocks and OptDigits datasets [18]. which have dimensions d and actions & using a 0.1 (Figure I When models G are used (for DM, DR estimators), in 220), the dataset is divided into two splits, with
8

---

PageBlocks: 5=54 k=5, d=10
OptDigits: n= n-220. k=10, d=64
DR
WIS
erfor
15
0.010
DM
6.001
100
100
Figure 1: The error of the CDF estimators function of sample size n, for (left) the PageBlocks dataset and (right) the Optiigits dataset. Shaded area is the 95% quantile over 500 runs.
677
63
0.26
true
CVaR 0.5
Variance
0.25
DR
+ WIS
DM
3002
2002
2002
6002
5002
1000
2000
2000
1000
5000
1200
2200
3000
4200
5200
Figure 2: Estimated mean, CVaRo.5. and variance for the OptDigits dataset, compared to their true values (black). Shaded area is the standard deviation over 500 runs.
each of the two splits used to calculate G via regression, which is then used with the other split to calculate the estimator. The two results are averaged to produce the final estimators. We provide further details and extensive evaluations in Appendix
CDF Estimation. We evaluate the error F Fl of our CDF estimators against sample size for two UCI datasets (Figure [.. The IS and DR exhibit the expected O (1/vn) rate of convergence in error previously derived in Theorems 5.1 and 5.2 respectively. We note that the WIS estimator, while biased, performs as well as the IS estimator not better. the PageBlocks dataset (Figure [ left), the regression model for G relatively well-specified as exemplified by the relatively low error of the DM estimator, though it has high variance for low samples sizes. The DR estimator leverages this model to outperform all other estimators for all sample sizes, without suffering the drawbacks of the DM estimator. It takes order of magnitude less data reach the same еπто compared to the IS and WIS estimators. In contrast, the regression model is less well-specified in the OptDigits dataset for lower sample sizes (Figure 1 right), and consequently, the DR estimator cannot perform as well as the IS and WIS estimators for small n. However, this trend reverses as data increases and the model improves, with the DR estimator outperforming the importance sampling estimators.
Risk Functional Estimation. Figure[ssowws the mean, variance, and CVaRn.. estimates, which are obtained by evaluating each risk functional on the CDF estimators for the OptDigits dataset. Here, the estimates are plotted against the true value (dashed line) to make the variance reduction effect of the DR estimators more apparent. The DM estimator, which appeared to have competitive performance in the CDF error plot, has relatively high risk estimate error, which occurs because the DM CDF may be poorly approximated in areas that are important for risk functional estimation. The IS, WIS, and DR risk estimates converge quickly to the true value as n increases, and as expected, their relative behavior echoes the trends in Figure I as consequence of our distributional approach. The DR estimator has slightly worse performance for small samples sizes due to the poor specification the model, but soon exhibits the desired variance reduction for 1000.
Comparison Other Risk Estimators. One natural question ask how OPRA risk estimates, which can be generated for many risk functionals simultancously, compare to existing estimators for

---

individual risk functionals. To the best of our knowledge, of the risk functionals described in this paper, previous work has only derived off ooflcc estimators for the mean and variance.
20 establishes IS and DR estimators for the mean, and [0]] proposes an IS estimator for the variance. We compare these risk estimates OPRA in Table [T] using the Pageblocks dataset of Figure a select sample sizes n. We note that while a number of enhancements have been proposed for off-policy mean estimator, e.g., clipping importance weights [57], compare only analogous estimators. In general, the OPRA DR estimates outperform all other estimators. The OPRA DR estimate of the mean have the same error as the DR mean estimator from 20), and OPRA IS estimates of both mean and variance have lower MSE than existing IS mean and variance estimators.
Mean
Variance
IS 20
OPRA IS
DR 20
OPRA DR
IS [10]
OPRA IS
DR
OPRA DR
100
7.5e-3
4.4e-3
1.6e-3
1.6e-3
5.0e-5
0.7e-5
N/A
0.6e-5
924
7.5e-4
4.7e-4
2.3e-4
2.3e-4
4.0e-6
0.7e-6
N/A
0.7e-6
n 5472
12.5e-5
7.1e-5
3.4e-5
3.4e-5
5.4e-7
0.9e-7
N/A
1.le-7
Table I: Comparison of mean squared error (MSE) for OPRA versus existing off-polic estimators of the mean and variance the Pageblocks dataset (averaged over 1000 repetitions).
7.2 Application: Diabetes Treatment
To demonstrate the efficacy of our method in more complex applications, we use OPRA to evaluate the risks of target policy for diabetes treatment in the Simglucose simulator [59 In Simglucose, the agent must control insulin bolus injections given a type diabetes patient over the course of day, and the state is continuous vector consisting of the patient's 's carbohydrate intake from the last meal, blood glucose levels, and other patient measurements. At end of the day, the agent receives reward proportional to how often the patient's 's blood glucose levels stayed within acceptable limits.
We define the target policy to the simulator's built-in controller for the patient, and estimate the CDF, mean reward, and CVaRo.05 of т. The DR estimator has lower error for CDF and risk estimation compared all baseline estimators, reinforcing our findings on the UCI data (Figure
CVaB 0.05 MSE
CDF Error
Mean MSE
* WIS
IS
DM
10
samples n
Figure 3: CDF and risk estimation error OPRA in Simglucose (averaged over 100 repetitions).
Conclusion
This paper introduces a CDF-centric method for high confidence off-policy estimation of risk functionals, and the first doubly robust CDF estimator. From theoretical point view. we provide the first finite-sample concentration inequalities and confidence intervals for variety of CDF and risk estimators, which are widely applicable distributional RL settings [3 28 From a practical standpoint, our method can be used to comprehensively evaluate the behavior of target policy before deployment under wide range of risk functionals. Our work suggests several directions for future work. First, our uniform concentration bound for the doubly robust CDF estimator might be improved by incorporating its variance. Second, our heuristics for transforming CDF estimators into valid cumulative distribution functions, could likely be improved. Finally, our work suggests natural question: can concentration inequalities for risk functional estimators be derived if and only if the risk functional is Lipschitz, in some general sense?
10

---

References
[1] Carlo Acerbi. Spectral measures of risk: coherent representation of subjective risk aversion. Journal of Banking & Finance, 26(7): 2002.
[2] V. M. Aleksandrov, V. Sysoyev, and V. V. Shemeneva. Stochastic optimization. Engineering Cybermetics, 5(11-16):229 256, 1968.
[3] Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical finance, 9(3):203 228,, 1999.
[4] Alejandro Balbás, José Garrido, and Silvia Mayoral. Properties of distortion risk measures. Methodology and Computing in Applied Probability, 1163)385-399, 2009.
[5] Heejung Bang and James M Robins. Doubly robust estimation in missing data and causal inference models. Biometrics, (1(4):962-973, 2005.
[6] Dorian Baudry, Romain Gautron, Emilie Kaufmann, and Odalric-Ambryn Maillard. Thompson sampling for evar bandits. arXiv preprint arXiv:2012.0575,, 2020.
[7] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
[8] Asaf Cassel, Shic Mannor, and Assaf Zeevi. A general framework for bandit problems beyond cumulative objectives.
[9] Yash Chandak, Scott Nickum, Bruno Castro da Silva, Erik Learned-Mille Emma Brunskill, and Philip S. Thomas. Universal off off-policy evaluation, 2021.
[10] Yash Chandak, Shiv Shankar, and Philip S. Thomas. High-confidence off aff-policy (or counterfac- tual) variance estimation, 2021.
[11] Joel QL Chang, Qiuyu Zhu, and Vincent YF Tan. Risk-constrained thompson sampling for evar bandits. arXiv preprint XXi::2011.080444 2020.
[12] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. constraind reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, 18(1):6070-6120, 2017.
[13] 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.
[14] Richard B Darst and Robert Huotari. Best II-approximation bounded, approximately continuous functions on [0, 1] by nondecreasing functions. Journal of approximation theory, 43(2):178-189, 1985.
[15] Freddy Delbaen. Coherent risk measures on general probability spaces. In Advances in finance and stochastics, pages 1-37. Springer, 2002.
[16] Eric V Denardo, Haechurl Park, and Uriel G Rothblum. Risk-sensitive and risk-neutra multi- armed bandits. Mathematics of Operations Research, 32(2):374-394, 2007.
[17] Dieter Denneberg. Distorted probabilities and insurance premiums. Methods of Operations Research, 63(3):355, 1990.
[18] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[19] Miroslav Dudík, Dumitru Erhan, John Langford, Lihong Li, et al. Doubly robust policy evaluation and optimization. Statistical Science, 29-4)1 2014.
[20] Miroslav Dudik, John Langford, and Lihong Li. Doubly robust policy evaluation and learning, 2011.

---

[21] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sam- ple distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 142-669, 1956.
[22] Aditya Gopalan, LA Prashanth, Michael Fu, and Steve Marcus. Weighted bandits or: How bandits learn distorted values that are not expected. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[23] Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260))6633 685, 1952.
[24] Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652-661. PMLR, 2016.
[25] Cheng Jie, LA Prashanth, Michael Fu, Steve Marcus, and Csaba Szepesvári. Stochastic optimization in a cumulative prospect theory framework. IEEE Transactions on Automatic Control, 63(9):2877-2882 2018.
[26] Elyès Jouini, Walter Schachermayer, and Nizar Touzi. Law invariant risk measures have the fatou property. In Advances in mathematical economics, pages 49-71. Springer, 2006.
[27] Anmol Kagrecha, Jayakrishnan Nair, and Krishna Jagannathan. Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards. arXiv preprint /90iv 00569, 2019.
[28] Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill. Being optimistic to be conservative: Quickly learning evar policy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4436 4443, 2020.
[29] Pavlo Krokhmal. Higher moment coherent risk measures. 2007.
[30] Shigeo Kusuoka. On law invariant coherent risk measures. In Advances in mathematical economics, pages 83-95. Springer, 2001.
[31] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[32] Lihong Li, Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Artificial Intelligence and Statistics, pages 608-616. PMLR, 2015.
[33] Shie Mannor and John Tsitsiklis. Mean-varianee optimization in markov decision processes. arXiv preprint 1rXiv:/104.500 2011.
[34] Pascal Massart. The tight constant in the dioretzky-kkeefe-wwlfooviz inequality. The annals of Probability, pages 1269-1288 1283, 1990.
[35] Rémi Munos. From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning. 2014.
[36] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[37] LA Prashanth, Cheng Jie, Michael Fu, Steve Marcus, and Csaba Szepesvári. Cumulative prospect theory meets reinforcement learning: Prediction and control. In International Confer- ence on Machine Learning, pages 1406-1415. PMLR, 2016.
[38] Prashanth I. and Michael Fu. Risk-sensitive reinforcement learning: constrained optimiza- tion viewpoint. arXiv e-prints, pages arXiv-1810, 2018.
[39] James M Robins and Andrea Rotnitzky. Semiparametric efficiency in multivariate regression models with missing data. Journal of the American Statistical Association, 102429):122-12, 1995.
12

---

[40] R Tyrelll Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2:21 2000.
[41] Amir Sani, Alessandro Lazaric, and Rémi Munos. Risk-aversion in multi-armed bandits. arXiv preprint 1301. /936, 2013.
[42] Ekaterina N Sereda, Efim M Bronshtein, Svetozar T Rachev, Frank J Fabozzi, Wei Sun, and Stoyan V Stoyanov. Distortion risk measures in portfolio optimization. In Handbook of portfolio construction, pages 649-673. Springer, 2010.
[43] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyúski. Lectures on stochastic programming: modeling and theory. SIAM, 2014.
[44] William F Sharpe. Mutual fund performance. The Journal of business, 39(1)=119-138, 1966.
[45] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the
log-like log-likelihood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
[46] PW Smith and Swetits. Best approximation by monotone functions. Journal of approximation theory, (9(4))3388443 1987.
[47] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 1, pages 1468-1476, 1476, 2015.
[48] Aviv Tamar, Dotan Di Castro, and Shie Mannor. Journal of Machine Learning Research, 17(1):361-366, 2016.
Learning the variance of the reward-to-go. The
[49] Alex Tamkin, Ramtin Keramati, Christoph Dann, and Emma Brunskill. Distributionally-avee awarr exploration for evar bandits. In NeurIPS 2019 Workshop on Safety and Robustness on Decision Making, 2019.
[50] Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health, pages 495-517. Springer, 2017.
[51] Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforce- ment learning. In International Conference on Machine Learning, pages 2139-2148. PMLR, 2016.
[52] Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off- policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[53] Léonard Torossian, Aurélien Garivier, and Victor Picheny. X -armed bandits: Optimizing quantiles, ovar and other risks. In Asian Conference on Machine Learning, pages 252-267. PMLR, 2019.
[54] Sattar Vakili and Qing Zhao Mean-variance and value at risk in multi-armed bandit problems. In 2015 53rd Annual Allerton Conference Communication, Control, and Computing (Allerton), pages 1330-1335. IEEE, 2015.
[55] Shaun Wang. Premium calculation by transforming the layer premium density. ASTIN Bulletin: The Journal of the IAA, 26(1):71-92, 1996.
[56] Shaun S Wang, Virginia R Young, and Harry H Panjer. Axiomatic characterization of insurance prices. Insurance: Mathematics and economics, 21 (2 1997.
[57] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudık. Optimal and adaptive off-policy evalua- tion in contextual bandits. In International Conference on Machine Learning, pages 3589-3597. PMLR, 2017.
[58] Julia L Wirch and Mary R Hardy. Distortion risk measures: Coherence and stochastic dominance. In International congress on insurance: Mathematics and economics, pages 15-17, 2001.
[59] Jinyu Xie. Simglucose v0. 2.1 (2018). URL https://githhb. com//xx/23//imgllucoss 2018.
[60] Alexander Zimin, Rasmus Ibsen-Jensen, and Krishnendu Chatterjee. Generalized aisk-aversion
in stochastic multi-armed bandits. arXiv preprint 1005vv1405.0833, 2014.
13


Reviews:
[{"review_id": "qwpbiUF9ILK", "reviewer": "Reviewer_xxgN", "summary": "Previous OPE studies mostly are focused on the overall expected return. This paper studies off-policy evaluation for a more broad class of objectives, i.e., the Lipschitz risk functionals, including CVaR, variance, mean-variance, etc. The main idea is to first use an IPS/DR estimate to estimate the target policy's CDF, then use it as a plug-in estimator to any functionals that satisfy the Lipschitz property. Theoretically, an $O(1/\\sqrt{n})$ error bound is derived for the Lipschitz estimate. Empirically, the performance of the plug-in estimator (based on different CDF estimates) is examined.\n\nOPE is crucial to estimate the performance of any new policy while online A/B testing or experimentation might be infeasible. Most prior works on OPE focus on efficient estimation of the expected reward of the policy, while this paper studies the estimation problem under more general metrics, which may be of high importance in real-world applications when people care about different functionals, such as CVaR in finance. ", "questions": "", "limitations": "", "rating": 6, "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/Significance:\n\nI like the problem this paper studies since it has some practical applicability and the method is easy to use with a solid statistical guarantee. I will view the significance level as high, as this more broad class of objectives characterizes lots of useful and popular metrics people care about. Regarding to the originality, I think it is a medium-low. The method proposed is based on CDF estimate and then a plug-in in any risk functionals, this kind of approach has been used in the previous literature as well, though not explicitly stated, see the algorithms [1]. Though this paper discusses its difference with a concurrent work [2], there is still some literature that utilizes this kind of approach [1], it would be great if the authors could comment on this.\n\nQuality:\n\nThe quality of this paper is good. The motivation is clear, and the assumption of Lipschitz risk functional is well-motivated and justified. I like Section 4.1, but it might be shortened, and leave some space for experiments. The method is clearly introduced. Theoretically, this paper gives the first uniform concentration for CDF estimates in bandits, which also directly translates to a $O(1/\\sqrt{n})$ rate for the Lipschitz objective. For the empirical study side, it seems all the examinations are about, first estimating CDF using different approaches, then a direct plug-in. I am wondering if there any other baselines in the literature that says do OPE for CVaR, variance, etc. If not, it would be great to state them clearly. If yes, it would be great to include them as baselines. I would view the current experiments as ablation studies, rather than a comparison with existing methods. Some specific comments:\n\n[1]. How to estimate the Lipschitz constant when it is not obvious from the context? Or currently, it seems some estimates are not tight?\n[2]. It seems the requirement of the Lipschitz property is to derive the uniform convergence rate theoretically. I am wondering how this method (probably empirically) applies to some metrics that not satisfy this requirement, say VaR? It would be great to comment on the necessity of this assumption.\n\n[3]. Some typos: \nline 6, it would be great to define CPT when use it the first time; \nline 52, is scales;  \nline 35, off-hig evaluation; \nline 90, steps generates; \n\nClarity:\nI enjoy reading the paper and it writes well!\n\n\nref: [1]. Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy\n       [2]. Universal off-policy evaluation", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they are discussed in Section 8.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "afPVTpxak2Z", "reviewer": "Reviewer_8N59", "summary": "The work studies offline evaluation of policies assessed in terms of risk measures in a contextual bandit setting. It leverages the fact that a variety of risk measures are represented as some function of cumulative distribution function (CDF) of policy rewards with known Lipschitz constants. The work provides two consistent estimators of CDF, bounds their error from true CDF in sup norm, and use these to bound the risk measures. In experiments on two realistic datasets, the estimators are shown to have low error.", "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": "The work provides a general way of performing high-confidence off-policy value estimation which is applicable to a large class of evaluation metrics. These metrics, characterised as being Lipschitz functionals of CDF, are understudied in the machine learning literature and are practically relevant for policy evaluation in high-risk applications. The proposed approach that starts from bounding errors in estimating CDF and carrying this over to bounding errors in risk measure-based value is novel. As a result, the method guarantees good value estimates for any set of risk measures simultaneously, given they satisfy Lipschitz property. Experimental evaluation adequately verifies the theoretical results on realistic datasets.\n\nThe advantage of the approach is its generality for all Lipschitz risk measures. But familiarity with applications of such measures and their relative merits is assumed. Although many examples of such measures are presented (beyond mean, variance, and CVaR), some more details on strengths of each and applications in which they are appropriate will help to provide more guidance on use of such risk measures by the machine learning community.\nExperimental evaluation does not seem to be suited to ideal settings where risk measures are useful, e.g. continuous-valued rewards with a skewed distribution and a large range (max-min is high). For binary rewards, as in the experiments, Lipschitz constant determined by max reward D is relatively small. While classification datasets are easier to convert to a bandit task, alternatives based on semi-synthetic datasets with simulated continuous-valued outcomes could be explored. This may provide understanding of usefulness of the confidence intervals when Lipschitz constants are large.\n\n\nQuestions I will like the authors to address:\n\nDoes the approach assume non-negative rewards (for applying Lemma 4.1)? Is this without any loss of generality?\n\nHow does the bounds from the presented approach compare with existing ones for mean, variance, and CVaR?\n\nDoes the experiments provide a sense of how tight are the confidence intervals for different risk measures and datasets?\n\nIn case of unknown behaviour policy, doubly robust estimators have another advantage (in addition to being consistent under misspecification of either action or reward models) of having root n convergence rates under mild misspecification. Does this property follows as well for the proposed doubly robust estimator, both for CDF and policy value?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the analysis are mentioned. Please discuss limitations of the current experiments to evaluate methods across settings relevant to risk measures.\n\nSuggestions to improve presentation:\n\nPlease add more detailed comparison of contributions between the concurrent work of Chandak et al. [9] and this work, highlighting the distinction between risk measures considered, guarantees for estimators (in more detail), importance of Lipschitz property to the results, and experimental comparison, if possible.\n\nPlease consider adding baselines specialised to estimating mean (e.g. https://www.cs.utexas.edu/~sniekum/classes/RL-F17/papers/HCOPE.pdf), variance, and CVaR. Is the CDF based approach competitive in terms of error and interval width?\n\nPlease consider plotting percent coverage and width of the confidence intervals. The intervals in Figures 1 and 2 for different methods are not easily distinguishable, so it hard to visually verify coverage and reduction in interval width with number of samples. For example, width of DR is not visible in Figure 2.\n\nPlease explicitly write the assumption making the problem a contextual bandit, i.e. independent draws from context distribution, in contrast to the full RL problem.\n\nPlease consider including experiments on datasets where risk measures-based evaluation is well motivated for example medical applications. Some potential datasets are antimicrobial resistance http://clinicalml.org/data/amr-dataset/, or vasopressor and fluid use in ICU https://github.com/matthieukomorowski/AI_Clinician, https://github.com/clinicalml/gumbel-max-scm).\n\n\nMinor:\n\nLine 35 ‘off-hig’ ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {"ethical_concerns": "I do not foresee any ethics implications. Moving beyond mean rewards as the policy evaluation metric will provide more careful evaluation of policies that emphasizes extreme (possibly negative) rewards."}}, {"review_id": "RjyFrwrp-Km", "reviewer": "Reviewer_GLvQ", "summary": "The paper studies the problem of risk assessment with offline data. Unlike traditional work that focuses on the offline evaluation of policies, this paper introduces a new class of risk functionals (of the CDF) as the estimands and generalizes the IS estimator and AIPW estimator for the estimation of the CDF (and the risk functionals).", "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": "1. Novelty: \n\nmy main concern for this work is that it seems to be a straightforward combination of the well-known properties of the IS estimator and the AIPW estimator and a new class of estimands. The authors introduce a new class of estimands that are (Lipschitz) functionals of the CDF, so to estimate these estimands well it suffices to estimate the CDFs well. Establishing the concentration results for CDF estimates is also a straightforward adaptation of the results in the offline policy evaluation literature. Therefore, I feel there is a lack of technical novelty. Please correct me if I missed something.\n\n2.  Stronger results: \n\nContinuing with the above comment, I think the paper can be improved if stronger results can be shown. For example, is it possible to provide (asymptotic) confidence intervals for the estimands? Is it possible to establish optimality for the current results?\n\n3. Minor: \n\nLine 125: “its value” should be “the difference between the function values evaluated at Z and Z’”?\n\nLine 158: the definition of u^+(z) should depend on c as well?\n\nLine 351: might be improved\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Discussion on potential negative societal impact should be added.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "D2iYpa16K4g", "reviewer": "Reviewer_quRn", "summary": "The paper proposes off-policy risk assessment(OPRA), a framework that estimate a risk functional\nthrough first estimate CDF and second plugin estimates for any risks functional that\nsatisfies Lipschitz properties.\nThe new proposed framework is elegant and can simultaneously estimate a broad class \nof objectives including CVar, variance, mean-variance and many others.\nThe paper also provides theoretical convergence analysis for the estimator.", "questions": "", "limitations": "", "rating": 8, "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": "\nI am satisfied with the novelty and the quality of the paper, and I think the paper is \nwell written and inspiring. I would recommend acceptance of the submission.\n\n**Novelty:**\nThe paper provides the first DKW-style proof of uniform convergence of weighted empirical CDF\nif the importance ratio is bounded.\nThe proof looks standard but is new and I think it is an important complement to \nDKW-style inequalities.\n\n**Quality:**\nThe proof is sound to me.\nAnd I have the same concern of theorem 5.2 as the authors also mention in line 271.\nThe error for DR does not depend on $\\hat{G} - G$ and cannot improve over IS also seems\nweird to me. \nA better bound on that would definitely improves the paper's quality.\n\n**Clarity:**\nThe paper is well written and inspiring. \nThe background on Lipschitz risk functionals bring up a wide range of risk functionals\nthat we can directly utilized given the estimation of the CDF.\nAnd the main proof in Section 5 discusses two important estimator: IS and DR, \nboth are provided with sufficient background the theoretical results.\n\n\n**Minor:**\nIn line 229, 'DI' should replace with 'DM'.", "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": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the off-policy Lipschitz risk functional estimation in contextual bandit setting. The authors considered plug-in estimator based on the CDF-estimator, with guarantees from DKW-inequality. The paper is well-written: the motivation is clear and the logic flow is easy to follow.  The method is also novel. 

As the reviewers suggested, the experiment part is relatively weak. Please consider to add the extra empirical study into final version. 

Another issue is that there are some important related work missing, e.g., [1, 2]. Therefore, the method is not well-positioned in literature. Please consider the comparison with [1, 2] and add the table in the response to Reviewer 8N59. 

[1] Faury, Louis, Ugo Tanielian, Elvis Dohmatob, Elena Smirnova, and Flavian Vasile. "Distributionally robust counterfactual risk minimization." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, pp. 3850-3857. 2020.

[2] Karampatziakis, Nikos, John Langford, and Paul Mineiro. "Empirical likelihood for contextual bandits." arXiv preprint arXiv:1906.03323 (2019).
Decision: Accept (Poster)