Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning
Authors: Alberto Maria Metelli
Alessio Russo
Marcello Restelli
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Importance Sampling
Off-Policy Evaluation
Off-Policy Learning
Subgaussian

Abstract: Importance Sampling (IS) is a widely used building block for a large variety of off-policy estimation and learning algorithms. However, empirical and theoretical studies have progressively shown that vanilla IS leads to poor estimations whenever the behavioral and target policies are too dissimilar. In this paper, we analyze the theoretical properties of the IS estimator by deriving a novel anticoncentration bound that formalizes the intuition behind its undesired behavior. Then, we propose a new class of IS transformations, based on the notion of power mean. To the best of our knowledge, the resulting estimator is the first to achieve, under certain conditions, two key properties: (i) it displays a subgaussian concentration rate; (ii) it preserves the differentiability in the target distribution. Finally, we provide numerical simulations on both synthetic examples and contextual bandits, in comparison with off-policy evaluation and learning baselines.

Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning
Alberto Maria Metelli
Alessio Russo DEIB, Politecnico di Milano alessio. russo@polimii
DEIB, Politecnico di Milano
a.bertomaria.metellllee..
Marcello Restelli
DEIB, Politecnico di Milano
rearelllo.restelligee.
Abstract
Importance Sampling (IS) a widely used building block for a large variety of off-policy estimation and learning algorithms. However, empirical and theoretical studies have progressively shown that vanilla IS leads to poor estimations whenever the behavioral and target policies are dissimilar. In this paper, analyze the theoretical properties of the IS estimator by deriving a novel anticoncentration bound that formalizes the intuition behind its undesired behavior. Then, we pro- pose new class of IS transformations. based on the notion of power mean. To the best of our knowledge, the resulting estimator is the first to achieve. under certain conditions, two key properties: (i) it displays subgaussian concentration rate; (ii) it preserves the differentiability in the target distribution. Finally, we provide numerical simulations on both synthetic examples and contextual bandits, in comparison with off off-policy evaluation and learning baselines.
Introduction
The availability of historically collected data is common scenario in many real-world decision-
making problems, including medical treatments [e.g..[7] 67], recommendation systems [e.g.. [3 [6].
personalized advertising [e.g..B 3 600, finance [e.g.. 43 and industrial robot control [e.g.. 27 26].
Historical data can be leveraged to address two classes of problems. First, given data collected with behavioral policy, we want to estimate the performance of a different targel policy. This problem is known as off-policy evaluation [Off-PE, 21] Second, we want to employ the available data to improve the performance of a baseline policy. This latter problem is named off-policy learning [Ofr- [4] Off-policy methods are studied by both the reinforcement learning [RL,
(88) and contextual multi-armed bandit [CMAB, (30 communities. Given its intrinsic simplicity compared to RL, off- policy methods are nowadays well understood in the CMAB framework [e.g.. 44 14] 64). Among them, the doubly robust estimator [DR, [4] is one the most promising off-policy methods for CMABs. DR combines a direct method (DM), in which the reward is estimated from historical data via regression, with an importance sampling [IS, 46) control variate.
IS plays crucial role in the off-policy methods and counterfactual reasoning. However, IS tends to exhibit problematic behavior for general distributions. This is formalized by heavy-tailed properties [40), which prevent the application of exponential concentration bounds [4]. To cope with this issue, typically, corrections are performed on the importance weight including truncation [23 and self-normatization [SN, 46), among the most popular. Significant results have recently been derived for both techniques 47
Nevertheless, we believe that the widespread use of IS calls for better theoretical understanding of its properties and for the design of principled weight corrections.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Defining the desirable properties of an off- policy estimator is a non-trivial task. Some works employed the mean squared error (MSE) as an index of the estimator quality [4 64]. However, controlling the MSE, while effectively capturing the bias-variance trade-off, does not provide any guarantee on the concentration properties of the estimator, which might still display heavy-tailed behavior [37]. For this reason, we believe that more suitable approach is to require that the estimator deviations concentrate at a subgaussian rate [2]. Subgausianitty implicitly controls the tail behavior and leads to tight exponential concentration inequalities. Unlike MSE, the probabilistic requirements are non- asymptotic (finite-samppl sample), from which guarantees on the MSE can be derived. While subgaussianity can be considered satisfactory requirement for Off-PE, additional properties are advisable when switching to Off-PL. In particular, the differentiability w.r.t. the target policy parameters is desirable whenever Off- PL is carried out via gradient optimization. For instance, weight truncation, as presented in [47]. allows achieving subgaussianity but leads to a non-differentiable objective. Consequently, the optimization phase requires additional care, which sometimes leads computationally heavy discretizations [47]. On the contrary, the SN estimator is differentiable in the target policy, but fails to achieve subgaussian concentration for general distributions.
In this paper, we take a step towards a better understanding of IS. After having introduced the necessary background (Section 2). we derive an anticoncentration bound for the mean estimation with vanilla IS. We show that polynomial concentration (Chebychev's inequality) is tight in this setting (Section B). This result formalizes the intuition behind the undesired behavior of these estimators for general distributions. Hence, we propose a class of importance weight corrections, based on the notion of power mean (Section[4). The rationale behind these corrections is to "smoothly shrink" the weights towards the mean, with different intensities. In this way, we mitigate the heavy-tailed behavior and, in the meantime, exert control over the induced bias. Then, derive bounds on the bias and variance that allow obtaining an exponential concentration inequality and, under certain conditions, subgaussian concentration (Section (5) Furthermore, the smooth transformation allows preserving the differentiability in the target policy, unlike some existing transformations, like weight truncation. To the best of our knowledge, this is the first IS correction that preserves the differentiablity and is proved to be subgaussian. This correction, however, requires knowledge of a distributional divergence between the target and behavioral policies. which may be unknown or difficult to compute. To this end, we introduce an approach to empirically estimate the correction parameter, preserving the desirable concentration properties (Section 6. After providing a comparative review of the literature (Section 7). we present an experimental study comparing our approach with traditional and modern off- off-policy baselines on synthetic domains and in the CMAB framework (Section (8) The proofs of the results presented in the main paper can be found in Appendix AA A preliminary version of this work was presented at the "Workshop on Reinforcement Learning Theory" of ICML 2021 [42
2 Preliminaries
We start introducing the background about probability, importance sampling and contextual bandits.
Probability We denote with ())) the set of probability measures over a (y). Let PE (()), f RR be function, and 7, be an estimator for the mean μ (y-r([()) obtained with i.i.d. samples. Suppose that with probability 1 8 it holds that 1,,, - a & / Vg(n,)) 6). For B 8>0 O, we say that Hh admits: (i) polynomial concentration if g(n,,) = (11(nd))) 9): (ii) exponential concentration if
g(0)= = O ((og(()))) log(1/5)/m) B "): (iii) subgaussian concentration if (ii) holds with 3=1 37 These cases correspond to Chebyshev's Bernstein's, and Höeffding's 's inequalities respectively 4
Importance Sampling Let P,QE ()') admitting p and q density functions, if P<c i.e.,
P is absolutely continuous w.r.t. Q, for any ae (1,2]. we introduce the integral: La (P) Sy ((p()"((()) "dy. If P= a.s. (almost surely) then la (PllQ))= La (PI(Q) allows defining several divergences. like Rényi [ST]: (1-1)-1 log la (PIQ). Let f: be function, (vanilla) importance sampling [16 allows estimating the expectation of f under the target distribution P. ie., -== Ey-r((()), using i.i.d. samples (ye]te(m) collected with the behavioral distribution Q:
p(v)
P
Σ ((I))(())) =E[m]
where
w(y)=
VYEV!
g(y)

---

It is well-known that Pr is unbiased, i.e., Fyn-olan1= = [4]. If f is bounded, the variance of [ & f (2 AO]. More in general, the integral (PIQ)) represents the a-moment of the importance weight w(y) under Q.
the estimator can be upper-bounded as Varg. eon--lln]]
Contextual Bandits A contextual multi-armed bandit [CMAB, 30 is represented by the tuple C= == (X,A, p.p.. where X' is the set of contexts, A is the finite set of actions (or arms), Pe (X) is the context distribution, and p:X x A- ((R) is the reward distribution. The agent's behavior is encoded by a policy x P (A). At each round le N. the agent observes a context x; / p. plays an action dt T (-(x+), gets the reward rt ~ p(- Ft, (2,,a)) and the system moves on to the next round. The value of a policy is given by v(T) = Sx E(x)E T(alz) p(r[z, rdrddz We denote with r(2,a)= p(r|2, rdr the reward functioo. A policy x² is optimal if it maximizes the value function, i.e., x² E arg ren (TT), where =I= {T: - (AA) is the set of all policies.
Let 1= ra be dataset of samples collected in CMAB with a behavioral policy ThE II. The off-policy evaluation [Off-PE, 21 problem consists in estimating the value function ((Te) of a target policy E II using the samples in D. The eff-policy learning [Off-PL,[4] problem consists in estimating an optimal policy x E using the samples in D. The simplest approach to address the Off-PE/Off-PL problem is to learn from D an estimate f(x, a) of the reward function (I,a) via regression. This approach is known as direct method (DM) and its properties heavily depend on the quality of the estimate f. Another approach is to simply apply IS to reweight the samples of D. leading to the inverse propensity scoring [IS. [7] estimator. The two approaches are combined in the doubly-robust [DR, [4] estimator, in which the DM estimate is corrected with an IS control variate to reduce the variance using the estimated reward f (see also Table 12 in Appendix D).
3 Anticoncentration of Vanilla Importance Sampling
In this section, we analyze the intrinsic limitations of the vanilla IS. It is well-known that under the assumption that for some ae (1.2) the divergence La (PI() Q) is finite and f is bounded, the vanilla IS estimator f., admits polynomial concentration, i.e.. with probability at least 1 8
A 14] < | (22
8na-1
We now show that the concentration in Equation I is tight, by deriving an anticoncentration bound for 1pn- pol: then, discuss its implications and compare it with previous works.
Theorem 3.1. There exist two distributions PeQe& (V) with P& Q and a bounded measurable func- tion f:y-RR R such that for every ar (1, and 8 (0, if n max {1, (1o (P)IQ) 1) }.
with probability at least 5 it holds that:
Pnnn ام ||> lffl
[a(PP1Q)
1) 1/4
1
co
T2
First of all, we note the polynomial dependence on the confidence level 5. The bound is vacuous when Ta (Pll)) 1, i.e., when P= Q a.s., since in an on-policy setting and, being the function f bounded, subgaussian concentration bounds (like Höeffding's 's inequality) hold. In particular, for a = 2, n and I2( (2(lll)) sufficiently large, the bound has order (VVT((())))) (T((P)))//(())) matching Chebyshev's 's and the existing concentration inequalities for vanilla importance sampling
Our result is of independent interest and applies for general distributions. Previous works considered the MAB 334 and CMAB (64) settings proving minimax lower bounds in mean squared error (MSE) Ey- - [. These results differ from ours in several respects. First, we focus on a specific estimator, the vanilla one, while those result are minimax. Second, they provide lower bounds the 3 From our probabilistic result, it is immediate to derive an MSE guarantee (Corollary of Appendix [..]]. Finally, they assume that the second moment of the importance weight I2( [P] QQ) is finite, whereas our result allows considering scenarios in which only moments of order a < 2 are finite.
MSE, while we focus on the deviations in probability
2 'The original result [4] Theorem 2] was limited to = 2 and based Cantelli's inequality which approaches Chebyshev's when - O. See Theorem A.I in Appendix [A.] for a proof of Equation |
3 As noted in [36). when the estimator is not well-concentrated around its mean (e.g.. in presence of heavy tails), the MSE not adequate to capture the error and high- probability bounds are more advisable.
3

---

8
wa,a(1)
A-0.5
0.76
-00 (minimum)
min(w:
4=0
A=1
w(v)
-1 (harmonic)
x \co1) (wo
0 (geometric)
w(v) (1 x1)
1 (arithmetic)
2 wfy)
w(y)
Table Choices of for the (A, corrretted Figure 1: Examples of importance weight corrections importance weight of Definition 4.1
of Definition 4. for fixed À (left) and fixed (right).
4 Power-Mean Correction of Importance Sampling
In this section, motivated by the negative result of Theorem 3.1 we look for a weight correction able to achieve subgaussian concentration. Specifically, introduce class of corrections based on the notion of power mean [6] and we study its properties. Let us start with the following definition.
Definition 4.1. Let P.QE ()) two probability distributions such that P& Q, for every SE [-00, 0o] and λe [0, 1.. let w(y) p(y)/g(v). the (X, -correccd importance weight is defined as:
(x. (()()))(()))))))))))) (1=))w(w*+>>) VyEy.
The correction can be seen as the weighted power mean with exponent s between the vanilla importance weight wyy) and 1 with weights 1- À and À respectively" We immediately notice that, regardless of the value of s, for x= 0, we reduce to the vanilla importance weight (w)) ( and for A= 1, we have identically (1)s(y) = Furthermore, a.s. regardless and A. Thus, the correction "smoothly interpolates" between the vanilla weight (yy) and its mean under Q, i.e., 1. s and À govern the "intensity" of the correction in continuous way, Differently from the truncation [23], this transformation leads to differentiable weight. Some specific choices of s and À are reported Table I and in Figure [ The following result provides a preliminary characterization of the correction, independent of the properties of the two distributions.
correction is unbiased when P Q
Lemma 4.1. Let P, P,Qe (P)) be two probability distributions with P < Q, then for every Xe [0, and yey holds that:
(i) if s then wx.s (v) E (y):
(ū) if s < then (y) & X otherwise s then (y, =
(iii) if s <<1 then Ey-qlwx, [v)] & otherwise if s 1 then Ey-
From point (ii) we observe that the corrected weight is bounded from below when 5 and bounded from above when s O. It is well-known that the inconvenient behavior of IS derives from the heavy- tailed properties [40]. Thus, the arithmetic correction (s= 1) performs just a convex combination between the vanilla weight and 1, having no effect the tail properties. Any correction with increases the weight value, making the tail even heavier. So, if we are looking for subgaussianity, we should restrict our attention to << 0, which leads to lighter tails or even bounded weights.
5 Subgaussian and Differentiable Importance Sampling
In this section, we focus on the harmonic correction (s -s= 1), which leads to weight of the form w(y) w T- Aw(yy We start analyzing the bias and variance of this class of estimators. Then, provide an exponential concentration inequality that, under certain circumstances, results to be subgaussian. Finally, we show that the resulting estimator is differentiable in the target distribution. To lighten the notation we neglect the subscript, abbreviating PA fix,-1-
Bias and Variance We now derive bounds for the bias and the variance induced by the (A,-1)- corrected importance weight.
'For se (-00, 0, 0. power mean defined as limit.
'The choice of =1 is mainly for analytical convenience and, as we shall see, it already allows enforcing the desired properties. We leave investigating the other values of for future work.

---

Lemma 5.1. Let P,QE ( be two probability distributions with P& For every xe [0. the bias and variance of the -1)--e-coreeteed importance weight can be bounded for every ae (1, 2 as:
1 nd2-a (PIQ).
y-Q Am < 11
Var 1 1
As expected, the bias is zero for A= it increases with A and with the divergence term La (P)))) Indeed, we already observed that the bias is null when P=Q a.s.. particular, for a= 2, the bound becomes A12 Instead, the variance bound decreases in À and increases with the divergence (P) For == 2, we obtain the bound f (2( Q). Note that when P= Q a.s., we recover - which the Popoviciu's inequality for the variance [50]. Thus, our weight correction allows controlling bias and variance even when (2) oD, i.c., when the vanilla IS estimator might have infinite variance. Indeed, our transformed estimator has finite variance provided
that there exists o (1 so that (PIQ)) < co. Tighter (but less intelligible) bounds on bias and variance are reported Appendix A.3
Concentration Inequality We are now ready to derive the core theoretical result. We prove an exponential concentration inequality for the (2, (X.-1)-come -cooreecd IS estimator and we show that, [2())) is finite, we are able to achieve subgaussian concentration
Theorem 5.1. Let P.QE (V) be two probability distributions such that P& Q. For every ar (1, and de (0, 1), if we select X Aa then, with probability al least 1 - ô it holds that:
21a (PIl)) - 1og
2 2og 1
P - - 1f
with
X
3(a- 1)
3(a-112L1
We immediately notice that the dependence on the confidence level is the one typical of exponential concentration for every a (1, In particular, observe that the bound is subgaussian when a=2, requiring that (2(1)) <0. Recalling that (p(()) governs the variance of the estimator, this result is in line with the general theory of estimators for which the existence of the variance is an unavoidable requirement to achieve subgaussian concentration [2]. Specifically, for a = 2 the optimal value of the parameter is X = =
leading to the bound:
(12(
Pn, - - v
(2)
3n
tighter bound, based on a different choice of the correction parameter A is derived in Ap- pendix A.3 and it is omitted here for clarity of presentation.
Differentiability As we have already observed, our weight correction, differently from truncation, is smooth and, thus, differentiable in the target policy. We now focus on the properties of the gradient of the (A, - -o-crrecte estimator and, to this purpose, we constrain the target distribution belong to parametric space differentiable distributions Pe (Poe (P))) : Oe where θ Rd. The gradient of the corrected weight WA w.r.t. the target policy parameters @ is given by:
Vewx(y) Vo poly) (1- (V)
V Vologpo(y), Vyey. q(v) (1 (1- Xw()))²
In particular, it can be proved that [Voos & ax Vo Vologpo(y)ll.. (Proposition A.1 of Ap- pendix A.3).. Thus, if the score V log is bounded, the gradient will be bounded whenever >= O. This property is advisable for gradient optimization and it is not guaranteed, for example, for vanilla IS (A=0). 0). Thus, we can also interpret as a regularization parameter for the gradient magnitude.
Data-driven Tuning of X
The computation of the parameter X requires the knowledge of the divergence (p())).. Even when P and Q are known, computing the Iz(PP (P)))) can be challenging, especially for continuous
We introduce our concentration inequalities as one-sided bounds just for simplicity but they actually hold in both directions. Indeed, by replacing function f with function -f. we obtain the reversed one-sided bound.
5

---

distributions, since it involves the evaluation of complex integral In principle, we could estimate the divergence (2(PIQ) from samples as the empirical second moment of the vanilla importance weights n _ieln]] ((1))² However, although possibly well verf-orrfognngg in practice 40), this approach would prevent any subgaussian concentration, as the behavior of the non-corrected w(y)² will be
surely heavy-tailed whenever w(y) is. A general-purpose approach to avoid the divergence estimation the Lepski's adaptation method [32], which only requires knowing an upper and a lower bound on T2( ())...) Unfortunately, this method is known to be computationally intensive.
In this section, we follow different path inspired by the recent work [66]. If choice of the parameter A corrects the weight Wx leading to an ideal estimator Pn for the mean μ., we may expect that the empirical second moment of the corrected weights wA will provide reasonable estimation of I2( ())))). Based on this observation, we propose to choose À by solving the following equation:
2log
1 71
Σ iE/m
Wanz/a (y:)²
(3)
3n
empiricall second moment
The intuition behind this approach can be stated as follows. If the empirical second moment is close to the divergence, i.e., E WAn (y.) (p) the solution Ā of Equation (3 approaches the optimal parameter, i.e., x= (/0))
XĀ. We formalize this reasoning in Appendix A.4 proving that Equation (3) admits a unique root λ [0, 1J (Lemma A.4) and that when the number of samples n grows to infinity, converges indeed to > (Lemma A.8 The following result provides the concentration properties of the estimator An,, when using À instead of X², under slightly more demanding requirements on the moments of the importance weights.
Theorem 6.1.
Let P.Qe ())) be two probability distributions such that P&Q Let 2 be the solution of Equation (3. then, if (PI)) is finite, for sufficiently large n, for every Se (0, 1), with probability least 26 it holds that:
P 5+2/3
(l1 3n
Compared to Theorem 5.1 this result is weakened in two aspects. First, the inequality holds with a smaller probability 1-20 since two estimation processes with the same samples are needed, i.c.. the computation of and the corrected estimator f,, Second, and most important, the result holds for large n, whose minimum value is reported in the proof and depends on (Pll))) which must be finite. We think this is a not too strong requirement considering that even the variance of an empirical estimate of (2(l))) would depend on the fourth moment of the importance weight, i.c., ((PQ))
7 Related Works
Importance Sampling has a long history in Monte Carlo simulation as an effective technique for
variance reduction in presence of rare events and for what-if analysis [25] 55 20, 9 52). Apart from sparse exceptions [e.g., 8, [8] in the machine learning community, IS is primarily employed for
off-policy estimation and learning [e.g.. [1 38 61. In this setting, it is well-known that IS might display an inconvenient behavior, depending on the behavioral Q and target P distributions [65 40). In particular, IS tends to enlarge the range of the estimator up to esssup P(v)/q()) Although this term is finite for discrete distributions (if P & Q), it is likely unbounded for continuous ones [T]. Furthermore, in the latter case, the vanilla IS estimator might have infinite variance and tends to
exhibit a heavy-tailed behavior [40] 41 These properties suggest that a way of addressing this phenomenon is resort robust statistics, typically employed for mean estimation under heavy- tailed distributions [37]. Methods in this class include the trimmed mean [62 22], the median of means 45 24 and the Catoni's estimator 77]. For all of them, subgaussian guarantees were
For some common distributions. including Gaussians, the integral can be computed in closed form [5] 'It is possible to circumvent the computation of (x(l)) by choosing À independently from (z(P) () at the price of downgrading the concentration from subgaussian to exponential (Corollary A.2 of Appendix A.4p

---

Estimator
Maximum Variance
Bias
Correction (order ())
Concentration (onder (?)
Is subganssion?
Is unbiased when P=Q?
differentiable?
A6 40 SN-IS
essaup
X (poly) (exp)
V
B
B
VEs log
20
S-TK(M
M
FAPP 37
X
IS-OS(r)
56
(ISPP lng
x (exp)
X
IS-A
F2t
(2(P(()
(ours)
Table 2: Comparison between several IS estimators assuming ||/ = and for a= 2 w.r.t. several indexes. For the SN-IS estimator VSN the Efron-Stein estimate of the variance and BSN is the bias. V/SN and BSN converge to O as n- sc, but no convergence rate is provided in [29].
provided 37.. These techniques have been also successfully employed for regret minimization in finite 5 and continuous arm spaces [36]. In principle, these methods could be employed as-is in combination with IS, but, being
they might disregard the peculiarities of the setting.
Several ad-hoc methods to cope with the problematic IS behavior have been progressively de- veloped. An example, devised by the statistical community, is self-normalization [SN-IS, 46): ww.)) jj{[n] ((v)). This approach has the advantage of controlling the range of the es- timator at the price of making all samples interdependent and generating a bias. Although the asymptotic consistency is guaranteed [99 [5] its finite-sample analysis more challenging.
40), a polynomial concentration inequality was provided and, more recently, exponential bounds based on Efron-Stein inequalities have been proposed 28 29]. Nevertheless, the resulting inequality is not guaranteed to decrease with (11/ /n) for general distributions and it is difficult to formally relate its concentration rate the tail properties of the involved distributions
(29). Another popular technique (1), where M > 0 is the
is the weight truncation (or clipping) [IS-TR, 23
3 w3
threshold. Some works rely on empirical selections of the truncation threshold [31 10]. while others
focus on more theoretically principled approaches (2 64 47 In particular, in 47 a subgaussian
deviation bound is derived by suitably adapting the truncation threshold as function of the number of samples and the confidence parameter 5. Another interesting approach, designed for CMABs is the switch estimator [DR-SW,EL RR, 64] that selects between DM and IS (or DR), based on the importance weight value, with also guarantees in MSE. Finally, not large part of the literature focuses less crude transformations than truncation, called smoothing [63] They typically take into explicit consideration the estimator tails [88. also providing asymptotic guarantees. Very recently, shrinkage transformations the weight were proposed, based on the minimization of different bounds on the MSE, in the CMABs (56) setting. Specifically, the optimistic shrinkage [IS-OS, (56) leads transformation similar to ours (y) = =Tw(y)/ (w)() + +). Unfortunately, even when knowing P and Q and setting adaptively, IS-OS is unable achieve subgaussian concentration and requires
1s( ()) to be finite (Appendix E for details). Refer to Table for comparison of the estimators.
8 Numerical Simulations
In this section, provide numerical simulations for off off-policy evaluation (Section 8.1 and learning (Section 8.2). with the goal of showing that our estimators, while enjoying destrable theoretical properties, competitive with traditional (e.g., vanilla IS and neff-norrmllzatiio)) and modern baselines (e.g., truncation, optimistic shrinkage). The complete results can be found in Appendix B
8.1 Off-Policy Evaluation
We present two off- off-policy evaluation experiments. We start with synthetic example with Gaussian distributions and, then, we move to the CMAB setting.
The code is provided at alltttps://ithhu. http://hhh...ooooeeet.o/tt/ee///
7

---

Estinater
50
100
IS
27.48
15.70=4.88
10.89 1.81
9.26
12.41
8.42=0.00
6.24
8.52
T.4520.37
6.14400.20
IS-TR
2.75
10.32+
8.89+0079
7.08-+00.
4.32+0.115
1.33
IS-A
21.75
6.36
13.17
9.2641.19
0.76
6.58
6.29:20.25
8.02
0.0220.112
18-3
20. 66
4.08
12.02+2.19
8.86+1 1.08
1.80++0.55
6.04++0.22
4.74
3.19++0.10
18.19
1..27
0.03
6.79
8.86
0.90
2.06
Table 3: Absolute error in the illustrative example varying the number of samples for the different estimators (mean + std, 60 runs). For each column, the estimator with smallest absolute error and the ones not statistically significantly different from that one (Welch's 's t-test with p 0.02) are in bold.
Model-free
Model-hased
4/A
0.2
0.5
0.22
0:22
0.22
3.12:+:0.99
6.73 1:21
2.30
2.77 1.330
2.57 +..31
2.3.1
2.28
c
0.5
0.5
6.73
1:21
4.7210047
2.47 0.37
2.18 0.332
0.5
8.73
1.21
3.43
2.71 0.4
2:20 0.34
8.73
1:21
4.85
0.89
3.66
0.68
2.38 0.38
6.73
0
0.5
1.5
0.5
1.5
Table 4: Absolute error in the illustrative ex- ample varying the parameter 8 of the cor- rected weight when = 500 (mean + std, 60 runs). The estimator with smallest absolute er- ror and the ones not statistically significantly different from that one (Welch's t-test with p< 0.02) are in bold.
Relative Error w.r.. IS
Relative Error w.r. IS
IS
DM
DR
DR-SW
SN-IS
IS-TR
IS-OS
18-X"
15-2
SN-DR
DR-TR
DR
OS
DR-X"
DR-Ā
Figure 2: CDF of the absolute normalized by IS error for stochastic rewards with noise 0.25, across 110 conditions.
8.1.1 Synthetic Experiment
In this experiment, we compare our corrected estimators with IS baselines a continuous- distribution off-policy estimation problem. Specifically, we consider Gaussian behavioral policy Q (NQ: and Gaussian target policy P=N((pP, We generate n i.i.d. samples from Q and we estimate the expectation function f(y) 100 cocccoosstt (2xy) under P. We select μQ= O, μAp 0.5, of and of. 1.9, leading to a divergence T2( (2())) 27.9. The results with different choices of the of are reported in Appendix B.1.1
Estimators Comparison In Table 3 we report the absolute error between the estimated and the true mean for the different importance sampling estimators. For our correction, we report the results obtained with optimal value of À according to Theorem 5.1 with a= 2 (IS-X*), value of À that optimizes a tighter bound reported Appendix A.3 (IS- **), and the value estimated from samples as in Section 6 (IS-Ā). We compare these estimators with vanilla IS (IS), self-normalized IS (SN-IS), weight truncation (IS-TR) with optimal threshold selected in [47. and IS with optimistic shrinkage (IS-OS), where 7 is computed by minimizing an MSE bound as in [56]. We notice that our estimators consistently outperform the traditional ones (IS and SN-IS) and overall suffer smaller errors than IS-TR and IS-OS. Interestingly, the minimum error is often obtained by IS-X, which uses an estimated value À that tends to get a higher value than both X and *** In this way, the correction is more intense, which, in this specific example, turns out to be beneficial.
Comparison of Different Values of s We empirically test different values of the parameter s employed in Definition 4.1 in the same setting of Table with 500 for the estimator IS-X. Since for general value of s, we do not have a principled way to select the correction parameter X, we consider different values of X. The results are reported in Table We that the best results obtained with se (-1,-2)
8.1.2 Contextual Bandits
In this section, report the experiments about off-policy evaluation in CMABs.

---

Estimator n
100
200
500
1000
2000
5000
10000
200000
.7
22.26
2.00
15.98
8.36
4.67=0.07
2.08 0.03
2.15
1.10 1:0:0.00
1.0.5
11.43
7.10
2.54 0.03
1.6100011
1.10
15-TR
17.38
18.92
40.82
8.36
4.67=0.07
2.08
2.15
0.00
15:05
24.91
1.45
31.53
1.15
15.38 0.58
17:25 1 45
16.41
30. 63 0.15
33. 05 0.02
61.61 0.01
15
17.22
1.35
17.10
1:03
11.87 0.0.5
5.06 0.17
4.56 0.06
2.78 0.02
1.00
1:27 0.001
I5-A
17.21
10.93
6.06=0000
2.08
IS-A
18.16
1.49
16.52
0
11.23 0.029
0.48 0.16
0.077
3.01 00.03
2.89 0.002
1.50 0.00
DM
20.52
0:97
4.0.1
36. 2.00
36, 0.006
41 11.99:1 0.01
42. 00.00
0.00
20.02+0092
6-30 0.11
0.00
2.16=0.02
1.38
0.64 0.000
SN-DR
20.89
28.38
20.79
10.90:0011
6.48
2.54
0.62
0.99
DR-TR
18.48
1.13
15.96
18.58
15.52 +
15.46 0.07
20:33 0.01
21.05
20.
DR
1.117
18.84
60
17.10 0.:0011:20 39
12:19 22
8.86 0.11
17.52 0.06
18.40
19.04=0.002
DR-WW
22.88
1.25
16.81
11.81+111 1.14
4.59+ 18
4.70 0.00
4.56 0.06
0.77 =0.01
1.38
0.78
DR-1*
20.03 1: 25
18.70
33
13:04 1.0.61
0.13
3.82 0.07
1:70 0.002
1.37 0.001
0.61 0:000
DR
1.22
17.29
1.17
11.39 1.053
5.00
3.65 0.06
1.67 0.02
1.08
0.63
DR-A
18.53
1.
14.92.
0.98
9.18 0..44
4.91 10.10
3.39 0.06
1.61 1.002
1.40 0.001
0.65 0.000
Table 5: Absolute error (multiplied by 100) in the letter dataset varying the number of samples n for the different estimators, when a, a;= 0.5 and ag = 0.9 (mean I std, 10 runs). For each column, the estimator with smallest absolute error and the ones not statistically significantly different from that one (Welch's t-test with p< 0.05) are in bold.
Dvalnation Reward
0.6
Evalastion Performance
Model-free
Model-based
0.5
0.3
0.4
0.3
0.2
0.1
0.1
glass
krapt
letter
ccoli
0
2,000
4,000
2,000
4,000
SN-IS IS-OS
IS-X"
IS-X
Iterations
Iterations
IS
DM
DR
Figure 3: Evaluation reward for four different datasets after 1000 iterations (4000 iterations for letter) of gradient ascent with Boltzmann policy for the model-free estimators (mean + std, 10 runs).
SN- IS
18 OS
1S
IS-ă
SN-DR
DR-OS
DR-A"
DR-X
Figure 4: Evaluation reward for the letter dataset comparing the learning curve of different estimators (mean + std, 10 runs).
Setting We follow the well-established setting of [14 64 57 [56 We consider 11 UCI [ multi-
class classification datasets (see Vable Appendix 1.1.2p. Each dataset DD { , ) hefne is mapped to CMAB problem with action set A- [K]. Every sample (z,,a) leads to a reward given by 1/a- a To model noise, the reward is switched with probability ve [o, 1]. Each dataset is split into training set Diin and an evaluation Deval with proportions 30% and 70%. A multi-class classifier C is trained on Dinin- The behavioral policy is obtained as: (=(aa=)= a K if C(x) and Tá (a|xx))
K otherwise, where a [0, 1]. The target policy xe obtained as the behavioral one by training another classifier on Drain and using a, E [0. 1]. We employ T. to generate dataset D= D={(x;,0 0;, r:)) (,) ]efn]] sampling x; from Deval where a; ~ < and r; is computed as described before. The ground truth value function is computed as v(TT))
1-a,
Te EveD Eae Te (a/ (I; a). For DM and DR, we employ regressor to learn the reward with cross- cross-fitting procedure on the full D.
Estimators Comparison We consider several settings that vary the values of as and ag across all the 11 datasets, generating 110 combinations and reward noise of y 0.25. Details and results for the noiseless case are reported in Appendix B. 1.2] To summarize the results, following the approach of [64], plot in Figure 2 the cumulative distribution function (CDF) of the absolute error normalized by the error of IS. A lower error corresponds to a CDF curve towards the upper- left corner. We distinguish between the approaches that do not make use of the reward estimate e (model-free, left) and the ones that do (model-hased, right). As for the model-free ones, we note that the performance of our estimator IS- is very close that of SN-IS. This is likely because we dealing with discrete distributions (actions are finite), which implicitly mitigate the degeneracy of the importance weight. Differently, the advantage w.r.t. the optimistic shrinkage (IS-OS) is quite significant. Instead, for the model-based estimators, we observe that our weight correction combined with the DR estimator (DR-X* and DR-Ā) outperforms the standard DR and its combinations with SN (SN-DR), truncation (DR-TR), and optimistic shrinkage (DR-OS). Instead, the switch estimator (DR-SW) displays performance comparable to ours.

---

Estimator/
10
100
200
500
1000
IS
0.6742
0.5414
0.1754
0.0326
0.0326
0.0198
0.0014
0.686
0.5416
0.176
0.0228
0.056
0
0
DR
0.6522
0.4094
0.117
0.0484
0.0378
0.0218
0.0022
DR-A
0.65
0.1046
0.1088
0.03262
0.009
0
0
Table Complementary cumulative distribution of the absolute error (multiplied by 100) () in the glass dataset varying the number of samples n for the different estimators, when aq = 0.9 and ag 0.9999 (5000 runs).
For the specific case of the letter dataset, we report in Table the results obtained by setting ag = 0.5 and a2 = 0.9 for different number of samples We notice essentially two behaviors. When the number of samples is very low (c.g., 100, 200) all estimators perform similarly, with poor performance. As increases, the benefits of the DR-like estimators becomes more visible. In particular, the DR-SW and our corrected estimators (DR-X*, * DR-A** and DR-Ā) overall dominate the other baselines.
Tail Behavior Experiment We run 5000 estimation processes using the glass dataset, n= 30, ag 0.99999, and og = 0.9. To compare the tail behavior between vanilla weights and our correction (for both model-free and model-based estimators), we consider the absolute error random (multiplicd by 100) variable E (as in Table 5) and we estimate the complementary cumulative distribution E) Thus, for large values of f, the larger P <E=&& E the heavier the tail, since a larger amount of probability mass accumulates on the right of &. Table reeports the results for both model-based based and model-free estimators. We observe that our corrected estimators consistently display a significantly lighter tail compared the vanilla ones.
8.2 Off-Policy Learning
Finally, we provide an experiment in which we employ the off-policy methods to improve baseline policy in the CMAB framework. We refer to the same setting of Section 8.1 with a uniform behavioral policy (ag = 0). For the target policy, we consider a Boltzmann policy in some featurization of the context To (z)=) exp (0 d(z)). We optimize the estimated value funetion in the parameters O via gradient ascent. Further details and experiments with regularized objectives are reported in Appendix B.2 We perform Off-PL on four datasets and the results for the model-free estimators are reported in Figure 3 We observe that our weight corrections (DR-X* and DR-Ā) outperform the considered baselines (IS, SN-IS, and IS-OS) on ecoli and letter datasets, whereas SN-IS emerges in the glass and kropt datasets. For the letter dataset, we report in Figure 4 the learning curve, distinguishing between model-free (left) and model- -based (right) estimators TM For the model-free ones, we observe the dominance of our estimators over SN estimator (SN-IS), while the optimistic shrinkage estimator (IS-OS) behaving similarly to ours. Interestingly, for the model-based estimators, plain DR beats the other estimators, including self- normaliomannnno that performs almost identically with our DR-X*, and IS-OS that fails completely to learn the task.
9 Discussion and Conclusions
In this paper, we have deepened the study of the importance sampling technique for off-policy evaluation and learning. We derived an anticoncentration bound for the vanilla IS estimator, proving polynomial concentration is tight for this setting. Then, we introduced and analyzed a class of importance weight corrections based on the intuition of smoothly shrinking the weight towards one. Assuming that the second moment of the importance weight exists, we have introduced the first transformation that achieves subgaussian concentration and maintains the differentiability of the estimator in the target policy parameters. The experimental evaluation has shown that our srretically-groundde transformation is competitive with the traditional and modern IS baselines (including self- normaoiaaazzi.nnn truncation, and optimistic shrinkage) in the CMAB framework for both evaluation and learning. The advantages of our correction are more visible in the case of continuous distributions, where the degeneracy of importance sampling is amplified. Future works include the extension of these corrections to the more challenging RI. setting with continuous actions.
''Clearly, the truncated (IS -R) and the switch SW) estimators cannot be directly employed in this setting, being con-differentiable.
10

---

References
[1] Heejung Bang and James M Robins. Doubly robust estimation in missing data and causal inference models. Biometrics, 61(4):962 970999 2005.
[2] Oliver Bembom and Mark J van der Laan. Data- adaptive selection of the truncation level for estimators. 2008.
[3] Léon Bottou, Jonas Peters, Joaquin Quiftonero Candela, Denis Xavier Charles, Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Y. Simard, and Ed Snelson. Counterfactual reasoning and learning systems: the example of computational advertising. J. Mach. Learn. Res., 14(1):3207- 3260, 2013.
[4] Stéphane Boucheron, Gábor Lugosi, Pascal Massart, al. On concentration of self-bounding functions. Electronic Journal of Probability, 14:1884-1899, 2009.
[5] Sébastien Bubeck, Nicold Cesa- Disa-Bianchh,, and Gábor Lugosi. Bandits with heavy tail. IEEE Trans. Inf. Theory, 59(11):7111-7717, 2013.
[6] Peter S Bullen. Handbook of means and their inequalities, volume 560. Springer Science Business Media, 2013.
[7] Olivier Catoni. Challenging the empirical mean and empirical variance: deviation study. In Annales de I' I'IH Probabilités et statistiques, volume 48, pages 1148-1185, 2012.
[8] Kamil Andrzej Ciosek and Shimon Whiteson. OFFER: off-environment reinforcement learning. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 1819-1825. AAAI Press, 2017.
[9] William G. Cochran. Sampling Techniques, 3rd Edition. John Wiley, 1977.
[10] Stephen R Cole and Miguel Hernán. Constructing inverse probability weights for marginal structural models. American journal of epidemiology. 168(6):656-666)) 664,, 2008.
[11] Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in Neural Information Processing Systems 23 (NIPS), pages 442-450 Curran Associates, Inc., 2010.
[12] Lue Devroye, Matthieu Lerasle, Gabor Lugosi, Roberto I Oliveira, al. Sub- sub-gaussian mean estimators. The Annals of Statistics, 44(6):2695 2725, 2016.
[13] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[14] Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning (ICML), pages 1097-1104. Omnipress, 2011.
[15] M. Gil, Fady Alajaji, and Tamás Linder. Rényi divergence measures for commonly used univariate continuous distributions. Inf. Sci., 249: 131, 2013.
[16] Alexandre Gilotte, Clément Calauzènes, Thomas Nedelec, Alexandre Abraham, and Simon Dollé. Offline A/B testing for recommender systems. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining ( (WSDM), pages 198-206. ACM, 2018.
[17] Jinyong Hahn. On the role of the propensity score in efficient semiparametric estimation of average treatment effects. Econometrica, pages 315-331, 1998.
[18] Josiah P. Hanna, Philip S. Thomas, Peter Stone, and Scott Nickum. Data-efficient policy evaluation through behavior policy search. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 1394 1403. PMLR, 2017.
[19] Tim Hesterberg. Weighted average importance sampling and defensive mixture distributions. Technometrics, 37(2):185-194, 1995.

---

[20] Timothy Classen Hesterberg. Advances in importance sampling. PhD thesis, Citeseer, 1988.
[21] 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):663-683, 1952.
[22] Peter Huber. Robust estimation of location parameter. In Breakthroughs in statistics, pages 492-518. Springer, 1992.
[23] Edward L Ionides. Truncated importance sampling. Journal of Computational and Graphical Statistics, 17(2):255-311, 2008.
[24] Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from uniform distribution. Theor. Comput. Sci., 43:169-188, 1986.
[25] Herman Kahn and Andy W Marshall. Methods of reducing sample size in monte carlo compu- tations. Journal of the Operations Research Society of America, 1(5):263-278, 1953.
[26] Ozsel Kiline, Yang Hu, and Giovanni Montana. Reinforcement learnen for robotic manipulation using simulated locomotion demonstrations. CoRR, abs/1910.07224,, 2019.
[27] Jens Kober and Jan Peters. Learning Motor Skills From Algorithms to Robot Experiments, volume 97 of Springer Tracts in Advanced Robotics. Springer, 2014.
[28] Ilja Kuzborskij and Csaba Szepesvári. Efron-stein pac-bayesian inequalities. abs/1909.01931, 2019.
CoRR,
[29] Uja Kuzborskij. Claire Vernade, András György, and Csaba Szepesvári. Confident off-policy evaluation and selection through nelf-norma importance weighting. In The 24th Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of Proceedings of Machine Learning Research, pages 640-648. PMLR, 2021.
[30] John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems 20 (NIPS), pages 817-824. Curran Associates, Inc., 2007.
[31] Brian K Lee, Justin Lessler, and Elizabeth A Stuart. Weight trimming and propensity score weighting. PloS one, 6(3):e18174, 2011.
[32] Oleg V Lepski and Vladimir G Spokoiny. Optimal pointwise adaptive methods in nonparametric estimation. The Annals of Statistics, pages
1997.
[33] Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual-bandit based news article recommendation algorithms. In Proceedings of the Forth International Conference on Web Search and Web Data Mining (WSDM), pages 297-306. ACM, 2011.
[34] Lihong Li. Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics (AISTATS), volume 38 of JMLR Workshop and Conference Proceedings. JMLR.org, 2015.
[35] Friedrich Liese and Igor Vajda. Convex statistical distances, volume 95. Teubner, 1987.
[36] Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Optimal algorithmss for lipschitz bandits with heavy-tailed rewards. In Proceedings of the 36th International Conference on Machine Learning (ICMIJ, volume 97 of Proceedings of Machine Learning Research, pages 4154-4166 PMLR, 2019.
[37] Gabor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: survey. Found. Comput. Math., 1955):1145-11990 2019.
[38] Ashique Rupam Mahmood, Hado van Hasselt, and Richard S. Sutton. Weighted importance sampling for off-policy learning with linear function approximation. In Advances in Neural Information Processing Systems 27 (NIPS), pages 3014-3022, 2014.
12

---

[39] Alberto Maria Metelli, Matteo Papini, Pierluca D'Oro, and Marcello Restelli. Policy optimiza- tion as online learning with mediator feedback. In Thirty-Fifth AAAI Conference on Artificial Intelligence, pages 8958-8966 AAAI Press, 2021.
[40] Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy opti- mization via importance sampling. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 5447-5459, 2018.
[41] Alberto Maria Metelli, Matteo Papini, Nico Montali, and Marcello Restelli. Importance sampling techniques for policy optimization. J. Mach. Learn. Res., 21:141:1-144:75, 2020.
[42] Alberto Maria Metelli, Alessio Russo, and Marcello Restelli. Subgaussian importance sampling for off-policy evaluation and learning. ICML-21 Workshop on Reinforcement Learning Theory, 2021.
[43] John E. Moody and Matthew Saffell. Learning to trade via direct reinforcement. IEEE Truns. Neural Networks, 12(4))875-889, 2001.
[44] Susan A Murphy, Mark van der Laan, James M Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 16(456):1410-1423 2001.
[45] Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[46] Art B. Owen. Monte Carlo theory, methods and examples. 2013.
[47] Mattco Papini, Alberto Maria Metelli, Lorenzo Lupo, and Marcello Restelli. Optimistic policy optimization via multiple importance sampling. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 4999. PMLR, 2019.
[48] James Pickands III et al. Statistical inference using extreme order statistics. Annals of statistics, 311:119-131, 1975.
[49] Iosif Pinelis et al. Best possible bounds of the von bahr-esseen type. Annals of Functional Analysis, 6(4):1-29, 2015.
[50] Tiberiu Popoviciu. Sur les équations algébriques ayant toutes leurs racines réelles. Mathematica, 9:129-145, 1935.
[51] Alfréd Rényi. On measures of entropy and information. Technical report. Hungarian Academy of Sciences Budapest Hungary, 1961.
[52] Brian D. Ripley. Stochastic simulation. Wiley series in probability and mathematical statistics: applied probability and statistics. Wiley, 1987.
[53] Yuta Saito, Aihara Shunsuke, Matsutani Megumi, and Narita Yusuke. Open bandit dataset and pipeline: Towards realistic and reproducible off-policy evaluation. CoRR, abs/2008.00 146, 2020.
[54] Igal Sason. On Oif-diverg:nces: Integral representations, local behavior, and inequalities. Entropy. 20(5):383, 2018
[55] David Siegmund. Importance sampling in the monte carlo study of sequential tests. The Annals of Statistics, pages 673-684, 1976.
[56] Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík. Doubly robust off-policy evaluation with shrinkage. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 9167-9176. PMLR, 2020.
13

---

[57] Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims. CAB: continuous adaptive blending for policy evaluation and learning. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 6005 6014. PMLR, 2019.
[58] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[59] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. In Advances in Neural Information Processing Systems 28 (NIPS), pages 3231-3239, 2015.
[60] Liang Tang, Rómer Rosales, Ajit Singh, and Deepak Agarwal. Automatic ad format selection via contextual bandits. In 22nd ACM International Conference on Information and Knowledge Management (CIKM' 13), pages 1587-1594. ACM, 2013.
[61] Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-policy evaluation. In Proceedings of the Twenty-Ninth AAAI Conference Artificial Intelligence, pages 3000-3006. AAAI Press, 2015.
[62] John W Tukey and Donald H McLaughlin. Less vulnerable confidence and significance procedures for location based single sample: Trimming/winsorizatinn 1. Sankhyd: The Indian Journal of Statistics, Series A, pages 331-352, 1963.
[63] Aki Vehtari, Daniel Simpson, Andrew Gelman, Yuling Yao, and Jonah Gabry. Pareto smoothed importance sampling. CoRR, abs/1507 .22.6666666. 2015.
[64] Yu- Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudík. Optimal and adaptive off aff-policy evalua- tion in contextual bandits. In Proceedings of the 34th International Conference Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 3589-3597. PMLR, 2017.
[65] Changhe Yuan and Marek J. Druzdzel. How heavy should the tails be? In Proceedings of the Eighteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS), pages 799-805. AAAI Press, 2005.
[66] Chao Zheng. A new principle for tuning-free huber regression. Statistica Sinica, 2020.
[67] Xin Zhou, Nicole Mayer-Hamblett, Umer Khan, and Michael Kosorok. Residual weighted learning for estimating individualized treatment rules. Journal of the American Statistical Association, 112(517):169-188 187, 2017.
14


Reviews:
[{"review_id": "cfDr4vSE6Ku", "reviewer": "Reviewer_9nhQ", "summary": "This paper proposes an off-policy evaluation estimator that is sub-Gaussian and differentiable. They provide an anti-concentration bound of the vanilla inverse propensity score weighting estimator, which implies that it is not sub-Gaussian. They propose a correction term on the inverse propensity score that shrinks the score. They show that the proposed estimator is sub-Gaussian under some conditions, and is differentiable with respect to the target policy parameters. They provide some empirical study to show that the proposed estimator is competitive with existing estimators. ", "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 well-structured and easy to follow. \n\nThe theoretical study of the concentration property of off-policy evaluation estimators could help better understand the behavior of these estimators. I like Table 2 in the paper which summarizes some theoretical properties of some model-free estimators. The paper presents new anti-concentration bound on the vanilla IPS estimator, and they show their proposed estimator is sub-Gaussian. \n\nThe data-driven approach for selecting \\lambda makes the proposed estimator more applicable, and is theoretically grounded by concentration bound in the paper. \n\nSince the paper is focused on concentration behaviors, I am wondering if the paper could show their concentration behaviors. I am curious whether IS, SN-IS, IS-OS are heavy-tailed empirically. \n\nIt would be great if the paper could discuss the concentration property of the model-based estimators, since it seems that these estimators perform much better than model-free estimators in both evaluation and learning. In particular, the discussion of the effect of the correction weight on the doubly robust estimator seems missing in the paper. ", "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": "4"}, "extra_text": {}}, {"review_id": "bbv6-FWQgcn", "reviewer": "Reviewer_ZK8F", "summary": "The paper addresses off-policy evaluation. It proposes to transform importance weights using the function $\\frac{\\omega(y)}{1-\\lambda + \\lambda \\omega(y)}$, where $\\omega(y) = p(y)/q(y)$ is the standard importance weight. The estimator which uses these transformed weights is analyzed both theoretically and empirically. The obtained estimator is unique in having both subgaussian concentration rate and being differentiable. The estimator depends on the hyperparameter $\\lambda$, for which the authors give an estimation procedure that only depends on observable quantities.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 original and high-quality.  It is clearly written - I feel I understand the main message even though I am a practitioner and do not come from this subcommunity. The contribution is significant and well within the scope of NeurIPS.\n\nAs a practitioner, I find it hard to comment on the proofs, but I have a couple of questions to the authors.\n1. You introduce the importance weight transformation (your definition 4.1) for arbitrary values $s$ but then the paper focusses on using $s=-1$ only. Why is that? I feel the paper should either use $s\\neq-1$ at least once in practice or else not discuss it.\n2. You address the contextual bandit setting. How hard would it be to generalise the result to off-policy evaluation for MDPs? Do you have a hunch about whether the same weight transformation would work? Of course, I am not expecting a proof (the paper already has a lot of material), but a couple of sentences of discussion would be nice.\n3. In the contextual bandit comprehensive experiment (as described in section B.1.2 in the appendix), you tried two values of alpha for the behavioral policy: $\\alpha_b \\in \\{ 0.8, 0.9\\}$. Was there a particular reason you did not try more extreme values (closer to one)? Such evaluation would be useful because it makes the task harder (the regular, untransformed importance weights can become quite large).\n4. In Table 4, the most successful approaches for large n are those that plug the proposed weight transform into the doubly robust estimator. However, theorems 5.1 and 6.1 talk about \"regular\" IS, not about doubly robust estimation. Is there a theoretical justification for combining doubly robust estimation with the proposed importance weight transform?\n\nVery minor points:\n- Line 81: \"more in general\" => \"more generally\"\n- Line 120: \"result\" => \"results\"\n- Line 772 in the appendix: missing word, probably \"samples\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss societal impact, arguing that the paper is theoretical. I agree with that assessment: off-policy evaluation can be misused but the potential for such misuse is same for this paper as for any other research on off-policy methods.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UUhiqh78-A", "reviewer": "Reviewer_4xpm", "summary": "This paper considers a power mean correction term for off-policy evaluation and learning. The resulting estimator has a subgaussian concentration rate, improving on other variants of importance sampling (which has a polynomial concentration rate). The authors bound the variance and bias of the resulting estimator. These bounds are functions of a tuned parameter $\\lambda$, where higher values of lambda increase the bias but reduce the variance giving practitioners the ability to tune the properties to their problem. The estimator also has other beneficial properties: the correction term is differentiable, and the free parameter $\\lambda$ can be tuned through data.", "questions": "", "limitations": "", "rating": 8, "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": "Overall, I think the paper is well written and provides a really interesting algorithm with interesting analysis of the new estimator and of vanilla importance-sampling. The work is well situated in the literature, although my breadth of knowledge of the CMAB literature is limited. I've also lightly checked parts of the theory for correctness, but have not thoroughly checked all the proofs. While the theoretical sections are quite dense, I think the authors do a good job giving readers the appropriate context to wade through the theory. The empirical comparisons also seem quite robust and provide comparisons to several baselines, which has been expanded from prior submissions (as they report). I have very few comments overall, and think the paper is a strong accept assuming there are no significant errors in the theory.\n\n- More runs would make the empirical results better.\n- Line 637: I think you mean just $\\leq$ instead of just $\\leq =$ in the equation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the authors do a good job detailing their algorithms. This is an algorithmic paper, so there is little to not in societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "JkS3l_qstpu", "reviewer": "Reviewer_8Vhk", "summary": "This paper proposes a new estimator for off-policy evaluation and learning: the estimator modifies original importance sampling by adding a weight correction term controlled by one additional hyper-parameter. The paper analyzed the theoretical properties of the proposed estimator and used experiments to show the effectiveness of the proposed approach.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 proposed estimator in harmonic correction (s=-1) is novel and simple its design. \n+ The paper is well organized and easy to follow overall\n+ The theoretical property of the harmonic correction part is sound and clearly discussed\n- There are a lot of different variations of the power-mean correction of IS dicussed in Sec 4. I am wondering what properties they might have. If only harmonic mean version achieves subgaussian rate, and all later experiments only use harmonic mean version, this part feels a little disconnected to the main text of the paper.\n- About the bound in Theorem 5.1 and Eq. 2, I am wondering this seems only to upper bound the difference, rather than the absolute difference. If the left hand side difference is smaller than zero, and the right hand side is positive, the bound holds automatically. Could it be possible that the proposed estimator always underestimates the $\\mu$, thus always achieve the proposed bound? In my opinion, this bound doesn't help too much in our understanding.\n- The motivation of subgaussian concentration is not very obvious for readers without enough context. I think the paper would benefit a lot by showing the practical/ theoretical benefit of achieving a subgaussian concentration bound.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper address the limitations and societal impact well.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Importance sampling (IS, aka IPS) is an oft used and oft studied technique for counterfactual reasoning. While it is unbiased (under a "full support" assumption), it can have very large variance when the target policy's distribution is substantially different from that of the data collection (i.e., logging) policy, and this can have an adverse effect on policy evaluation and learning. This paper analyzes the concentration properties of the IS estimator, proving a new "anti-concentration bound," which shows that reward estimated by IS can be bounded away from the true expected reward with probability $\geq \delta$. The paper then proposes a power-mean transformation of the importance weights, and proves that the resulting estimator has subgaussian concentration. Experiments with the new estimator round out the paper, and the results show that the transformed importance weights generally outperform the "vanilla" importance weights.

The reviews agree that this is an interesting, novel analysis, and that it is well written and easy to follow. There were some concerns, but they have mostly been answered by the authors' responses. One unresolved comment (from Reviews 8Vhk and 9nhQ) is that the case for subgaussianity would be more convincing with more empirical evidence that it helps in practice. The reviewers were puzzled why the model-based baselines, which don't exhibit subgaussian tails, outperformed the proposed methods in some experiments.

Regardless, this is a strong paper that deserves to be accepted. Based on the novelty and relevance of the topic, I would go as far as to nominate it for a spotlight talk.
Decision: Accept (Spotlight)