Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning
Year: 2022

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.

heading: 1 Introduction
text: The availability of historically collected data is a common scenario in many real-world decisionmaking problems, including medical treatments [e.g., 17, 67], recommendation systems [e.g., 33, 16], personalized advertising [e.g., 3, 60], 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 a behavioral policy, we want to estimate the performance of a different target 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 [OffPL 14]. Off-policy methods are studied by both the reinforcement learning [RL, 58] and contextual multi-armed bandit [CMAB, 30] communities. Given its intrinsic simplicity compared to RL, offpolicy methods are nowadays well understood in the CMAB framework [e.g., 44, 1, 14, 64]. Among them, the doubly robust estimator [DR, 14] is one of 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 a crucial role in the off-policy methods and counterfactual reasoning. However, IS tends to exhibit problematic behavior for general distributions. This is formalized by its 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-normalization [SN, 46], among the most popular. Significant results have recently been derived for both techniques [47, 29, 39]. Nevertheless, we believe that the widespread use of IS calls for a better theoretical understanding of its properties and for the design of principled weight corrections.
35th Conference on Neural Information Processing Systems (NeurIPS 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 [34, 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 a heavy-tailed behavior [37]. For this reason, we believe that a more suitable approach is to require that the estimator deviations concentrate at a subgaussian rate [12]. Subgaussianity implicitly controls the tail behavior and leads to tight exponential concentration inequalities. Unlike MSE, the probabilistic requirements are nonasymptotic (finite-sample), from which guarantees on the MSE can be derived. While subgaussianity can be considered a 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 to 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 3). 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, we exert control over the induced bias. Then, we 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-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 A. A preliminary version of this work was presented at the “Workshop on Reinforcement Learning Theory” of ICML 2021 [42].1

heading: 2 Preliminaries
text: We start introducing the background about probability, importance sampling and contextual bandits.
Probability We denote with PpYq the set of probability measures over a pY,FYq. Let P PPpYq, f :YÑR be a function, and µn be an estimator for the mean µ“Ey„P rfpyqs obtained with n i.i.d. samples. Suppose that with probability 1´δ it holds that |µn´µ|ď a
gpn,δq. For βą0, we say that µn admits: (i) polynomial concentration if gpn,δq“O ` 1{pnδqβ ˘ ; (ii) exponential concentration if gpδq“O `` logp1{δq{n ˘β˘
; (iii) subgaussian concentration if (ii) holds with β“1 [37]. These cases correspond to Chebyshev’s, Bernstein’s, and Höeffding’s inequalities respectively [4].
Importance Sampling Let P,QPPpYq admitting p and q as density functions, if P !Q, i.e., P is absolutely continuous w.r.t. Q, for any αPp1,2s, we introduce the integral: IαpP }Qq“ ş
Y ppyq αqpyq1´αdy. If P “Q a.s. (almost surely) then IαpP }Qq“1. IαpP }Qq allows defining several divergences, like Rényi [51]: pα´1q´1 logIαpP }Qq. Let f :YÑR be a function, (vanilla) importance sampling [IS, 46] allows estimating the expectation of f under the target distribution P , i.e., µ“Ey„P rfpyqs, using i.i.d. samples tyiuiPrns collected with the behavioral distribution Q:
pµn“ 1
n
ÿ
iPrns ωpyiqfpyiq, where ωpyq“
ppyq qpyq , @yPY.
1https://lyang36.github.io/icml2021_rltheory/camera_ready/7.pdf.
It is well-known that pµn is unbiased, i.e., Eyi„Qrpµns“µ [46]. If f is bounded, the variance of the estimator can be upper-bounded as Varyi„Qrpµnsď 1n}f}8I2pP }Qq [40]. More in general, the integral IαpP }Qq represents the α-moment of the importance weight ωpyq under Q. Contextual Bandits A contextual multi-armed bandit [CMAB, 30] is represented by the tuple C“pX ,A,ρ,pq, where X is the set of contexts, A is the finite set of actions (or arms), ρPPpX q is the context distribution, and p :X ˆAÑPpRq is the reward distribution. The agent’s behavior is encoded by a policy π :XÑPpAq. At each round tPN, the agent observes a context xt„ρ, plays an action at„πp¨|xtq, gets the reward rt„pp¨|xt,atq and the system moves on to the next round. The value of a policy π is given by vpπq“ ş
X ρpxq ř aPAπpa|xq ş R ppr|x,aqrdrdx. We denote with rpx,aq“ ş
R ppr|x,aqrdr the reward function. A policy π ˚ is optimal if it maximizes the value
function, i.e., π˚ PargmaxπPΠ vpπq, where Π“tπ :XÑPpAqu is the set of all policies. Let D“tpxt,at, rtqutPrns be a dataset of samples collected in a CMAB with a behavioral policy πb PΠ. The off-policy evaluation [Off-PE, 21] problem consists in estimating the value function vpπeq of a target policy πe PΠ using the samples in D. The off-policy learning [Off-PL, 14] problem consists in estimating an optimal policy π˚ PΠ using the samples in D. The simplest approach to address the Off-PE/Off-PL problem is to learn from D an estimate prpx,aq of the reward function rpx,aq via regression. This approach is known as direct method (DM) and its properties heavily depend on the quality of the estimate pr. Another approach is to simply apply IS to reweight the samples of D, leading to the inverse propensity scoring [IS, 17] estimator. The two approaches are combined in the doubly-robust [DR, 14] estimator, in which the DM estimate is corrected with an IS control variate to reduce the variance using the estimated reward pr (see also Table 12 in Appendix D).

heading: 3 Anticoncentration of Vanilla Importance Sampling
text: In this section, we analyze the intrinsic limitations of the vanilla IS. It is well-known that under the assumption that for some αPp1,2s the divergence IαpP }Qq is finite and f is bounded, the vanilla IS estimator pµn admits polynomial concentration, i.e., with probability at least 1´δ:2
|pµn´µ|ď}f}8 ˆ 22´αIαpP }Qq δnα´1 ˙
1 α
. (1)
We now show that the concentration in Equation (1) is tight, by deriving an anticoncentration bound for |pµn´µ|; then, we discuss its implications and compare it with previous works. Theorem 3.1. There exist two distributions P,QPPpYq with P !Q and a bounded measurable function f :YÑR such that for every αPp1,2s and δPp0,e´1q if něδemax 1,pIαpP }Qq´1q 1 α´1 (
, with probability at least δ it holds that:
|pµn´µ|ě}f}8 ˆ IαpP }Qq´1 δnα´1
˙ 1 α ˆ
1´ eδ n
˙ n´1 α
.
First of all, we note the polynomial dependence on the confidence level δ. The bound is vacuous when IαpP }Qq“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 inequality) hold. In particular, for α“2, n and I2pP }Qq sufficiently large, the bound has order O ` a I2pP }Qq{pδnq ˘
, matching Chebyshev’s and the existing concentration inequalities for vanilla importance sampling [40, 41].
Our result is of independent interest and applies for general distributions. Previous works considered the MAB [34] and CMAB [64] settings proving minimax lower bounds in mean squared error (MSE) Ey„Qrppµn´µq2s. 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 to the MSE, while we focus on the deviations in probability.3 From our probabilistic result, it is immediate to derive an MSE guarantee (Corollary A.1 of Appendix A.1). Finally, they assume that the second moment of the importance weight I2pP }Qq is finite, whereas our result allows considering scenarios in which only moments of order αă2 are finite.
2The original result [41, Theorem 2] was limited to α“2 and based on Cantelli’s inequality which approaches Chebyshev’s when δÑ0. See Theorem A.1 in Appendix A.1, for a proof of Equation (1).
3As noted in [36], when the estimator is not well-concentrated around its mean (e.g., in presence of heavy tails), the MSE is not adequate to capture the error and high-probability bounds are more advisable.

heading: 4 Power-Mean Correction of Importance Sampling
text: In this section, motivated by the negative result of Theorem 3.1, we look for a weight correction able to achieve subgaussian concentration. Specifically, we introduce a 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,QPPpYq be two probability distributions such that P !Q, for every sP r´8,8s and λPr0,1s, let ωpyq“ppyq{qpyq, the pλ,sq-corrected importance weight is defined as:
ωλ,spyq“ ´ p1´λqωpyqs`λ ¯
1 s
, @yPY.
The correction can be seen as the weighted power mean with exponent s between the vanilla importance weight ωpyq and 1 with weights 1´λ and λ respectively.4 We immediately notice that, regardless of the value of s, for λ“0, we reduce to the vanilla importance weight ω0,spyq“ωpyq and for λ“1, we have identically ω1,spyq“1. Furthermore, the correction is unbiased when P “Q a.s. regardless s and λ. Thus, the correction “smoothly interpolates” between the vanilla weight ωpyq and its mean under Q, i.e., 1. s and λ govern the “intensity” of the correction in a continuous way. Differently from the truncation [23], this transformation leads to a differentiable weight. Some specific choices of s and λ are reported in Table 1 and in Figure 1. The following result provides a preliminary characterization of the correction, independent of the properties of the two distributions. Lemma 4.1. Let P,QPPpYq be two probability distributions with P !Q, then for every λPr0,1s and yPY it holds that:
(i) if sďs1 then ωλ,spyqďωλ,s1pyq; (ii) if să0 then ωλ,spyqďλ 1 s , otherwise if są0 then ωλ,spyqěλ 1 s ;
(iii) if să1 then Ey„Qrωλ,spyqsď1, otherwise if są1 then Ey„Qrωλ,spyqsě1.
From point (ii) we observe that the corrected weight is bounded from below when są0 and bounded from above when să0. It is well-known that the inconvenient behavior of IS derives from the heavytailed properties [40]. Thus, the arithmetic correction (s“1) performs just a convex combination between the vanilla weight and 1, having no effect on the tail properties. Any correction with są1 increases the weight value, making the tail even heavier. So, if we are looking for subgaussianity, we should restrict our attention to să0, which leads to lighter tails or even bounded weights.

heading: 5 Subgaussian and Differentiable Importance Sampling
text: In this section, we focus on the harmonic correction (s“´1), which leads to a weight of the form:5 ωλ,´1pyq“ ωpyq1´λ`λωpyq . We start analyzing the bias and variance of this class of estimators. Then, we 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 ´1 subscript, abbreviating pµλ“pµλ,´1. Bias and Variance We now derive bounds for the bias and the variance induced by the pλ,´1qcorrected importance weight.
4For sPt´8,0,8u the power mean is defined as a limit. 5The choice of s“´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 s for future work.
Lemma 5.1. Let P,QPPpYq be two probability distributions with P !Q. For every λPr0,1s, the bias and variance of the pλ,´1q-corrected importance weight can be bounded for every αPp1,2s as:
ˇ
ˇ ˇ E y„Q
rpµn,λs´µ ˇ ˇ ˇ ď}f}8λα´1IαpP }Qq, Var
yi„Q rpµn,λsď }f}28 nλ2´α IαpP }Qq.
As expected, the bias is zero for λ“0; it increases with λ and with the divergence term IαpP }Qq. Indeed, we already observed that the bias is null when P “Q a.s.. In particular, for α“2, the bound becomes }f}8λI2pP }Qq. Instead, the variance bound decreases in λ and increases with the divergence IαpP }Qq. For α“2, we obtain the bound 1n}f} 2 8I2pP }Qq. Note that when P “Q a.s., we recover 1n}f} 2 8, which is the Popoviciu’s inequality for the variance [50]. Thus, our weight correction allows controlling bias and variance even when I2pP }Qq“8, i.e., when the vanilla IS estimator might have infinite variance. Indeed, our transformed estimator has finite variance provided that there exists αPp1,2q so that IαpP }Qqă8. Tighter (but less intelligible) bounds on bias and variance are reported in Appendix A.3.
Concentration Inequality We are now ready to derive the core theoretical result. We prove an exponential concentration inequality for the pλ,´1q-corrected IS estimator and we show that, if I2pP }Qq is finite, we are able to achieve subgaussian concentration.6
Theorem 5.1. Let P,QPPpYq be two probability distributions such that P !Q. For every αPp1,2s and δPp0,1q, if we select λ“λ˚α then, with probability at least 1´δ it holds that:
pµn,λ˚α ´µď}f}8p2` ? 3q ˜ 2IαpP }Qq 1 α´1 log 1δ 3pα´1q2n
¸1´ 1α
, with λ˚α“ ˆ 2log 1δ 3pα´1q2IαpP }Qqn ˙
1 α
.
We immediately notice that the dependence on the confidence level δ is the one typical of exponential concentration for every αPp1,2s. In particular, we observe that the bound is subgaussian when α“2, requiring that I2pP }Qqă8. Recalling that I2pP }Qq 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 [12]. Specifically, for α“2 the optimal value of the parameter is λ˚2 “ a p2logp1{δqq{p3I2pP }Qqnq, leading to the bound:
pµn,λ˚2 ´µď}f}8p2`
? 3q
d
2I2pP }Qq log 1δ 3n . (2)
A tighter bound, based on a different choice of the correction parameter λ˚˚α is derived in Appendix 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 pλ,´1q-corrected estimator and, to this purpose, we constrain the target distribution to belong to a parametric space differentiable distributions PΘ“tPθ PPpYq :θPΘu, where ΘĎRd. The gradient of the corrected weight ωλ w.r.t. the target policy parameters θ is given by:
∇θωλpyq“∇θ pθpyq qpyq “ p1´λqωpyq p1´λ`λωpyqq2 ∇θ logpθpyq, @yPY.
In particular, it can be proved that }∇θωλpyq}8ď 1 4λ }∇θ logpθpyq}8 (Proposition A.1 of Appendix A.3). Thus, if the score ∇θ logpθ is bounded, the gradient will be bounded whenever λą0. This property is advisable for gradient optimization and it is not guaranteed, for example, for vanilla IS (λ“0). Thus, we can also interpret λ as a regularization parameter for the gradient magnitude.

heading: 6 Data-driven Tuning of λ
text: The computation of the parameter λ˚2 requires the knowledge of the divergence I2pP }Qq. Even when P and Q are known, computing the I2pP }Qq can be challenging, especially for continuous
6We introduce our concentration inequalities as a 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.
distributions, since it involves the evaluation of a complex integral.7 In principle, we could estimate the divergence I2pP }Qq from samples as the empirical second moment of the vanilla importance weights 1n ř
iPrnsωpyiq2. However, although possibly well-performing in practice [40], this approach would prevent any subgaussian concentration, as the behavior of the non-corrected ωpyq2 will be surely heavy-tailed whenever ωpyq is. A general-purpose approach to avoid the divergence estimation is the Lepski’s adaptation method [32], which only requires knowing an upper and a lower bound on I2pP }Qq. Unfortunately, this method is known to be computationally intensive. In this section, we follow a different path inspired by the recent work [66]. If a choice of the parameter λ corrects the weight ωλ leading to an ideal estimator pµn,λ, for the mean µ, we may expect that the empirical second moment of the corrected weights ωλ will provide a reasonable estimation of I2pP }Qq. Based on this observation, we propose to choose λ by solving the following equation:
λ2 1
n
ÿ
iPrns ωλn1{4pyiq2 loooooooooomoooooooooon
empirical second moment
“ 2log 1δ
3n . (3)
The intuition behind this approach can be stated as follows. If the empirical second moment is close to the divergence, i.e., 1n ř
iPrnsωλn1{4pyiq2»I2pP }Qq, the solution pλ of Equation (3) approaches the optimal parameter, i.e., pλ» a
p2logp1{δqq{p3I2pP }Qqnq“λ˚2 . We formalize this reasoning in Appendix A.4, proving that Equation (3) admits a unique root pλPr0,1s (Lemma A.4) and that when the number of samples n grows to infinity, pλ converges indeed to λ˚2 (Lemma A.8). The following result provides the concentration properties of the estimator pµn,λ when using pλ instead of λ˚2 , under slightly more demanding requirements on the moments of the importance weights.
Theorem 6.1. Let P,QPPpYq be two probability distributions such that P !Q. Let pλ be the solution of Equation (3), then, if I3pP }Qq is finite, for sufficiently large n, for every δPp0,1q, with probability at least 1´2δ it holds that:
pµn,pλ´µď}f}8 5`2
? 3
2
d
2I2pP }Qq log 1δ 3n .
Compared to Theorem 5.1, this result is weakened in two aspects. First, the inequality holds with a smaller probability 1´2δ since two estimation processes with the same samples are needed, i.e., the computation of pλ and the corrected estimator pµn,pλ. Second, and most important, the result holds for large n, whose minimum value is reported in the proof and depends on I3pP }Qq, which must be finite. We think this is a not too strong requirement considering that even the variance of an empirical estimate of I2pP }Qq would depend on the fourth moment of the importance weight, i.e., I4pP }Qq.8

heading: 7 Related Works
text: 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, 18], in the machine learning community, IS is primarily employed for off-policy estimation and learning [e.g., 11, 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 esssupy„Q ppyq{qpyq. Although this term is finite for discrete distributions (if P !Q), it is likely unbounded for continuous ones [11]. 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 to resort to robust statistics, typically employed for mean estimation under heavytailed distributions [37]. Methods in this class include the trimmed mean [62, 22], the median of means [45, 24], and the Catoni’s estimator [7]. For all of them, subgaussian guarantees were
7For some common distributions, including Gaussians, the integral can be computed in closed form [15]. 8It is possible to circumvent the computation of I2pP }Qq by choosing λ independently from I2pP }Qq at the
price of downgrading the concentration from subgaussian to exponential (Corollary A.2 of Appendix A.4).
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 general-purpose, they might disregard the peculiarities of the setting.
Several ad-hoc methods to cope with the problematic IS behavior have been progressively developed. An example, devised by the statistical community, is self-normalization [SN-IS, 46]: rωpyiq“ωpyiq{ ř
jPrnsωpyjq. This approach has the advantage of controlling the range of the estimator at the price of making all samples interdependent and generating a bias. Although the asymptotic consistency is guaranteed [19, 59], its finite-sample analysis is more challenging. In [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 Op1{ ? nq for general distributions and it is difficult to formally relate its concentration rate to the tail properties of the involved distributions [29]. Another popular technique is the weight truncation (or clipping) [IS-TR, 23, 3]: ωTRM pyq“mintωpyq,Mu, where Mą0 is the 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 a function of the number of samples n and the confidence parameter δ. Another interesting approach, designed for CMABs is the switch estimator [DR-SW, 64] that selects between DM and IS (or DR), based on the importance weight value, with also guarantees in MSE. Finally, a not so large part of the literature focuses on less crude transformations than truncation, called smoothing [63]. They typically take into explicit consideration the estimator tails [48], also providing asymptotic guarantees. Very recently, shrinkage transformations of 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 to a transformation similar to ours ωOSτ pyq“τωpyq{pωpyq2`τq. Unfortunately, even when knowing P and Q and setting τ adaptively, IS-OS is unable to achieve subgaussian concentration and requires I3pP }Qq to be finite (Appendix E for details). Refer to Table 2 for a comparison of the estimators.

heading: 8 Numerical Simulations
text: In this section, we provide numerical simulations for off-policy evaluation (Section 8.1) and learning (Section 8.2), with the goal of showing that our estimators, while enjoying desirable theoretical properties, are competitive with traditional (e.g., vanilla IS and self-normalization) and modern baselines (e.g., truncation, optimistic shrinkage). The complete results can be found in Appendix B.9

heading: 8.1 Off-Policy Evaluation
text: We present two off-policy evaluation experiments. We start with a synthetic example with Gaussian distributions and, then, we move to the CMAB setting.
9The code is provided at https://github.com/albertometelli/subgaussian-is.

heading: 8.1.1 Synthetic Experiment
text: In this experiment, we compare our corrected estimators with IS baselines in a continuousdistribution off-policy estimation problem. Specifically, we consider a Gaussian behavioral policy Q“N pµQ,σ2Qq and a Gaussian target policy P “N pµP ,σ2P q. We generate n i.i.d. samples from Q and we estimate the expectation of function fpyq“100cosp2πyq under P . We select µQ“0, µP “0.5, σ2Q“1 and σ2P “1.9, leading to a divergence I2pP }Qq»27.9. The results with different choices of the σ2P 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 α“2 (IS-λ˚), a value of λ that optimizes a tighter bound reported in Appendix A.3 (IS-λ˚˚), and the value estimated from samples as in Section 6 (IS-pλ). We compare these estimators with vanilla IS (IS), self-normalized IS (SN-IS), weight truncation (IS-TR) with optimal threshold selected as in [47], and IS with optimistic shrinkage (IS-OS), where τ 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-pλ, which uses an estimated value pλ that tends to get a higher value than both λ˚ 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 3 with n“500 for the estimator IS-λ. Since for general value of s, we do not have a principled way to select the correction parameter λ, we consider different values of λ. The results are reported in Table 4. We can see that the best results are obtained with sPt´1,´2u.

heading: 8.1.2 Contextual Bandits
text: In this section, we report the experiments about off-policy evaluation in CMABs.
Setting We follow the well-established setting of [14, 64, 57, 56]. We consider 11 UCI [13] multiclass classification datasets (see Table 9 in Appendix B.1.2). Each dataset D˚“tpxi,a˚i quiPrn˚s is mapped to a CMAB problem with action set A“rKs. Every sample pxi,aq leads to a reward given by 1ta“a˚i u. To model noise, the reward is switched with probability ν Pr0,1s. Each dataset is split into a training set Dtrain and an evaluation Deval with proportions 30% and 70%. A multi-class classifier C is trained on Dtrain. The behavioral policy is obtained as: πbpa|xq“αb` 1´αbK if a“Cpxq and πbpa|xq“ 1´αbK otherwise, where αb Pr0,1s. The target policy πe is obtained as the behavioral one by training another classifier on Dtrain and using αe Pr0,1s. We employ πb to generate a dataset D“tpxi,ai, riquiPrns sampling xi from Deval where ai„πbp¨|xiq and ri is computed as described before. The ground truth value function is computed as vpπeq“ 1n ř xPDeval ř
aPAπepa|xqrpx,aq. For DM and DR, we employ a regressor to learn the reward with a cross-fitting procedure on the full D. Estimators Comparison We consider several settings that vary the values of αb and αe across all the 11 datasets, generating 110 combinations and a reward noise of ν“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], we 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 upperleft corner. We distinguish between the approaches that do not make use of the reward estimate pr (model-free, left) and the ones that do (model-based, right). As for the model-free ones, we note that the performance of our estimator IS-λ˚ is very close to that of SN-IS. This is likely because we are 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-λ˚ and DR-pλ) 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 a performance comparable to ours.
For the specific case of the letter dataset, we report in Table 5 the results obtained by setting αb“0.5 and αe“0.9 for different number of samples n. We notice essentially two behaviors. When the number of samples is very low (e.g., 100, 200) all estimators perform similarly, with poor performance. As n increases, the benefits of the DR-like estimators becomes more visible. In particular, the DR-SW and our corrected estimators (DR-λ˚, DR-λ˚˚, and DR-pλ) overall dominate the other baselines.
Tail Behavior Experiment We run 5000 estimation processes using the glass dataset, n“30, αe“0.9999, and αb“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 (multiplied by 100) variable E (as in Table 5) and we estimate the complementary cumulative distribution PpEąξq. Thus, for large values of ξ, the larger PpEąξq, the heavier the tail, since a larger amount of probability mass accumulates on the right of ξ. Table 6 reports the results for both model-based and model-free estimators. We observe that our corrected estimators consistently display a significantly lighter tail compared to the vanilla ones.

heading: 8.2 Off-Policy Learning
text: Finally, we provide an experiment in which we employ the off-policy methods to improve a baseline policy in the CMAB framework. We refer to the same setting of Section 8.1 with a uniform behavioral policy (αb“0). For the target policy, we consider a Boltzmann policy in some featurization of the context πθpa|xq9exp ` θTa φpxq ˘
. We optimize the estimated value function in the parameters θ 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-λ˚ and DR-pλ) 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.10 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-normalization that performs almost identically with our DR-λ˚, and IS-OS that fails completely to learn the task.

heading: 9 Discussion and Conclusions
text: 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 theoretically-grounded transformation is competitive with the traditional and modern IS baselines (including self-normalization, 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 RL setting with continuous actions.
10Clearly, the truncated (IS-TR) and the switch (DR-SW) estimators cannot be directly employed in this setting, being non-differentiable.

Review summaries:
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. 

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.

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.