{'fraction_non_alphanumeric': 0.04457396158266295, 'fraction_numerical': 0.01110928692606578, 'mean_word_length': 4.357226619759602, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Doubly robust off-policy evaluation with shrinkage

We design a new family of estimators for off-policy evaluation in contextual bandits. Our estimators are based on the asymptotically optimal approach of doubly robust estimation, but they shrink importance weights to obtain a better bias-variance tradeoff in finite samples. Our approach adapts importance weights to the quality of a reward predictor, interpolating between doubly robust estimation and direct modeling. When the reward predictor is poor, we recover previously studied weight clipping, but when the reward predictor is good, we obtain a new form of shrinkage. To navigate between these regimes and tune the shrinkage coefficient, we design a model selection procedure, which we prove is never worse than the doubly robust estimator. Extensive experiments on bandit benchmark problems show that our estimators are highly adaptive and typically outperform state-of-the-art methods.

weaker assumptions than DM [21]. However, since DR uses the same importance weights as IPS, its variance can still be quite high, unless the reward predictor is highly accurate. Therefore, several works have developed variants of DR that clip or remove large importance weights. Weight clipping incurs a small bias, but substantially decreases the variance, yielding a lower mean squared error than standard DR [3,4,27,23].
In this paper, we continue this line of work, by developing a systematic approach for designing estimators with favorable finite-sample performance. Our approach involves shrinking the importance weights to directly optimize a sharp bound on the mean squared error (MSE). We use two styles of upper bounds to obtain two classes of estimators. The first is based on an upper bound that is agnostic to the quality of the reward estimator and yields the previously studied weight clipping [16,22,23], which can be interpreted as pessimistic shrinkage. The second is based on an upper bound that incorporates the quality of the reward predictor, yielding a new estimator, which we call DR with optimistic shrinkage. Both classes of estimators involve a hyperparameter and specific choices produce the unbiased doubly robust estimator and the low-variance direct-modeling estimator; the optimal hyperparameter improves on both of these.
To tune the hyperparameter and navigate between the two estimator classes, we design a simple model-selection procedure. Model selection is crucial to our approach, but is important even for classical estimators, as their performance is highly dataset-dependent. In contrast with supervised learning, where cross-validation is a simple and effective strategy, distribution mismatch makes model selection quite challenging in contextual bandits. Our model selection approach again involves optimizing a bound on the MSE. Combined with our shrinkage estimators, we prove that our final estimator is never worse than DR. Thus, our estimators retain the asymptotic optimality of DR, but with improved finite-sample performance.
We evaluate our approach on benchmark datasets and compare its performance with a number of existing estimators across a comprehensive range of conditions. While our focus is on tuning importance weights, we also vary how we train a reward predictor, including the recently proposed more robust doubly robust (MRDR) approach [9], and apply our model selection to pick the best predictor. Our experiments show that our approach typically outperforms state-of-the-art methods in both off-policy evaluation and off-policy learning settings. We also find that the choice of the reward predictor changes, depending on whether weight shrinkage is used or not. Via extensive ablation studies, we identify a robust configuration of our shrinkage approach that we recommend as a practical choice.
Other related work. Off-policy estimation is studied in observational settings under the name average treatment effect (ATE) estimation, with many results on asymptotically optimal estimators [10,11,13,21], but only few that optimize MSE in finite samples. Most notably, Kallus [14,15] adjusts importance weights by optimizing MSE under smoothness (or parametric) assumptions on the reward function. This can be highly effective when the assumptions hold, but the assumptions are difficult to verify in practice. In contrast, we optimize importance weights without making any modeling assumptions other than boundedness of rewards.

Setup
We consider the contextual bandits protocol, where a decision maker interacts with the environment by repeatedly observing a context x ∈ X , choosing an action a ∈ A, and observing a reward r ∈ [0, 1]. The context space X can be uncountably large, but we assume that the action space A is finite. In the news recommendation example, x describes the history of past visits of a given user, a is a recommended article, and r equals one if the user clicks on the article and zero otherwise. We assume that contexts are sampled i.i.d. from some distribution D(x) and rewards are sampled from some conditional distribution D(r | x, a). We write η(x, a) := E [ r | x, a ] for the expected reward, conditioned on a given context and action, and refer to η as the regression function.
The behavior of a decision maker is formalized as a conditional distribution π(a | x) over actions given contexts, referred to as a policy. We also write π(x, a, r) := D(x)π(a | x)D(r | x, a) for the joint distribution over context-action-reward triples when actions are selected by the policy π. The expected reward of a policy π, called the value of π, is denoted as V (π) := E (x,a,r)∼π [r].
In the off-policy evaluation problem, we are given a dataset {(x i , a i , r i )} n i=1 ∼ µ consisting of context-action-reward triples collected by some logging policy µ, and we would like to estimate the value of a target policy π. The quality of an estimatorV (π) is measured by the mean squared error where the expectation is with respect to the data generation process. In analyzing the error of an estimator, we rely on the decomposition of MSE into the bias and variance terms: We consider three standard approaches for off-policy evaluation. The first two are direct modeling (DM) and inverse propensity scoring (IPS). In the former, we train a reward predictorη : X × A → [0, 1] and use it to impute rewards. In the latter, we simply reweight the data. The two estimators are: For a concise notation, let w(x, a) := π(a | x)/µ(a | x), denote the importance weight. We make a standard assumption that π is absolutely continuous with respect to µ, meaning that µ(a | x) > 0 whenever π(a | x) > 0. This condition ensures that the importance weights are well defined and that V IPS (π) is an unbiased estimator for V (π). However, if there is substantial mismatch between π and µ, then the importance weights will be large andV IPS (π) will have large variance. On the other hand, given any fixed reward predictorη (fit on a separate dataset),V DM (π) has low variance, independent of the distribution mismatch, but it is typically biased due to approximation errors in fittingη.
The third approach, called the doubly robust (DR) estimator [8], combines DM and IPS: The DR estimator applies IPS to a shifted versions of rewards, usingη as a control variate to decrease the variance of IPS. DR preserves unbiasedness of IPS and achieves asymptotic optimality, as long as it is possible to derive sufficiently good reward predictorsη given enough data [21]. Whenη = 0, DR recovers IPS and is plagued by the same large variance. However, even when the reward predictorη is perfect, any intrinsic stochasticity in the rewards may cause the terms r i − η(x i , a i ), appearing in the DR estimator, to be far from zero. Multiplied by large importance weights w(x i , a i ), these terms yield large variance for DR in comparison with DM. Several approaches seek a more favorable bias-variance trade-off by clipping, removing, or re-scaling the importance weights [27,23,14,15]. Our work also seeks to systematically replace the weights w(x i , a i ) with new weightsŵ(x i , a i ) to bring the variance of DR closer to that of DM.
In practice,η is biased due to approximation errors, so in this paper we make no assumptions about its quality. At the same time, we would like to make sure that our estimators can adapt to high-qualitŷ η if it is available. To motivate our adaptive estimator, we assume thatη is trained via weighted least squares regression on a separate dataset than used inV DR . That is, for a dataset {(x j , a j , r j )} m j=1 ∼ µ, we consider a weighting function z : X × A → R + and solvê where F is some function class of reward predictors. Natural choices of the weighting function z, explored in our experiments, include z(x, a) = 1, z(x, a) = w(x, a) and z(x, a) = w 2 (x, a). We stress that the assumption on how we fitη only serves to guide our derivations, but we make no specific assumptions about its quality. In particular, we do not assume that F contains a good approximation of η.

Our Approach: DR with Shrinkage
Our approach replaces the importance weight mapping w : X × A → R + in the DR estimator (1) with a new weight mappingŵ : X × A → R + found by directly optimizing sharp bounds on the MSE. The resulting estimator, which we call the doubly robust estimator with shrinkage (DRs) thus depends on both the reward predictorη and the weight mappingŵ: We assume that 0 ≤ŵ ≤ w, justifying the terminology "shrinkage". For a fixed choice of π andη, we will seek the mappingŵ that minimizes the MSE ofV DRs (π;η,ŵ), which we simply denote as MSE(ŵ). We similarly write Bias(ŵ) and Var(ŵ) for the bias and variance of this estimator.
We treatŵ as the optimization variable and consider two upper bounds on MSE: an optimistic one and a pessimistic one. In both cases, we separately bound Bias(ŵ) and Var(ŵ). To bound the bias, we use the following expression, derived from the fact thatV DRs is unbiased whenŵ = w: To bound the variance, we rely on the following proposition, which states that it suffices to focus on the second moment of the termsŵ(x i , a i ) r i −η(x i , a i ) : The proof of Proposition 1 and other mathematical statements from this paper are in the appendix.
We derive estimators for two different regimes depending on the quality of the reward predictorη.
Since we do not know the quality ofη a priori, in the next section we obtain a model selection procedure to select between these two estimators.

DR with Optimistic Shrinkage
Our first family of estimators is based on an optimistic MSE bound, which adapts to the quality ofη, and which we expect to be tighter whenη is more accurate. Recall thatη is trained to minimize weighted square loss with respect to some weighting function z, which we denote as We next bound the bias and variance in terms of the weighted square loss L(η).
To bound the bias we apply the Cauchy-Schwarz inequality to (4): To bound the variance, we invoke Proposition 1 and focus on bounding the quantity E µ ŵ 2 (r −η) 2 .
Using the Cauchy-Schwarz inequality, the fact that 0 ≤ŵ ≤ w, and |r −η(x, a)| ≤ 1, we obtain Combining the bounds (5) and (6) with Proposition 1 yields the following bound on MSE(ŵ): A direct minimization of this bound appears to be a high dimensional optimization problem. Instead of minimizing the bound directly, we note that it is a strictly increasing function of the two expectations that appear in it. Thus, its minimizer must be on the Pareto front with respect to the two expectations, meaning that for some choice of λ ∈ [0, ∞], the minimizer can be obtained by solving The objective decomposes across contexts and actions. Taking the derivative with respect toŵ(x, a) and setting to zero yields the solution where "o" above is a mnemonic for optimistic shrinkage. We refer to the DRs estimator withŵ =ŵ o,λ as the doubly robust estimator with optimistic shrinkage (DRos) and denote it byV DRos (π;η, λ). Note that this estimator does not depend on z, although it was included in the optimization objective.

DR with Pessimistic Shrinkage
Our second estimator family makes no assumptions on the quality ofη beyond the range bound η(x, a) ∈ [0, 1], which implies |η(x, a) − r| ≤ 1 and yields the bias and second-moment bounds As before, we do not optimize the resulting MSE bound directly and instead solve for the Pareto front points parameterized by λ ∈ [0, ∞]: The objective again decomposes across context-action pairs, yielding the solution which recovers (and justifies) existing weight-clipping approaches [16,22,23]. We refer to the resulting estimator asV DRps (π;η, λ), for doubly robust with pessimistic shrinkage, since we have used the worst-case bounds in the derivation. See Appendix A for detailed calculations.

Basic Properties
The two shrinkage estimators, for a suitable choice of λ, are never worse than DR or DM. This is an immediate consequence of their form and serves as a basic sanity check.
Proposition 2. LetV denote eitherV DRos orV DRps . Then for anyη there exists λ ≥ 0 such that Both estimators actually interpolate betweenV DM andV DR . As λ varies, we obtainV DM for λ = 0 andV DR as λ → ∞. The optimal choice of λ is therefore always competitive with both. While we do not know λ , in the next section, we derive a model selection procedure that finds a good λ.

Model Selection
All of our estimators can be written as finite sums of the formV (θ) = 1 n n i=1 Z i (θ), where θ are some fixed hyperparameters and Z i (θ) are i.i.d. random variables. For example θ = (η, o, λ) denotes that we are using a reward predictorη and the optimistic shrinkage with the parameter λ. To choose hyperparameters, we first estimate the variance ofV (θ) by the sample variance We also form a data-dependent upper bound on the bias, which we call BiasUB(θ). The only requirement is that for all θ, Bias(θ) ≤ BiasUB(θ) (with high probability), and that BiasUB(θ) = 0 whenever Bias(θ) = 0; this holds for both bias bounds from the previous section, as they become zero whenŵ = w. Now, we simply choose θ from some class of hyperparameters Θ to optimize the estimate of the MSE:θ This model selection procedure is related to MAGIC [26] as well as the model selection procedure for the SWITCH estimator [27]. In comparison with MAGIC, we pick a single parameter value θ rather than aggregating several, and we use different bias and variance estimates. SWITCH uses the pessimistic bias bound (7), whereas we will also use two additional bounding strategies. Theorem 3. Let Θ be a finite set of hyperparameter values and let Θ 0 := {θ ∈ Θ : Bias(θ) = 0} denote the subset corresponding to unbiased procedures. Then The theorem shows that the MSE of our final estimator after model selection is no worse than the best unbiased estimator in consideration. The o(n −1 ) term is asymptotically negligible, as the MSE itself is Θ(1/n). In particular, since the doubly robust estimator is unbiased and a special case of our estimators with λ = ∞, we retain asymptotic optimality as long as we include λ = ∞ in the model selection. In fact, since we may perform model selection over many different choices forη, our estimator is competitive with the doubly robust approach using the best reward predictor.
There are many natural ways to construct data-dependent upper bounds on the bias with the required properties. The three we use in our experiments involve using samples to approximate expectations in: (i) the expression for the bias given in (4), (ii) the optimistic bias bound in (5), and (iii) the pessimistic bias bound in (7). In our theory, these estimates need to be adjusted to obtain high-probability confidence bounds. In our experiments we evaluate both the basic estimates and a adjusted variant where we add twice the standard error.

Experiments
We evaluate our new estimators on the tasks of off-policy evaluation and off-policy learning, and compare their performance with previous estimators. Our secondary goal is to identify the configuration of the shrinkage estimator that is most robust for use in practice.
Datasets. Following prior work [8,25,27,9,23], we simulate bandit feedback on 9 UCI multi-class classification datasets. This lets us evaluate estimators in a broad range of conditions and gives us ground-truth policy values (see Table 3 in the appendix for the dataset statistics). Each multi-class dataset with k classes corresponds to a contextual bandit problem with k possible actions coinciding with classes. We consider either deterministic rewards, where on multiclass example (x, y * ), the action y yields the reward r = 1{y = y * }, or stochastic rewards where r = 1{y = y * } with probability 0.75 and r = 1 − 1{y = y * } otherwise. For every dataset, we hold out 25% of the examples to measure ground-truth. On the remaining 75% of the dataset, we use logging policy µ to simulate n bandit examples by sampling a context x from the dataset, sampling an action y ∼ µ(·|x) and then observing a deterministic or stochastic reward r. The value of n varies across experimental conditions. 1 Table 1: Policies. We use the 25% held-out data to obtain logging and target policies as follows. We first obtain two deterministic policies π 1,det and π 2,det by training two logistic models on the same data, but using either the first or second half of the features. We obtain stochastic policies parameterized by (α, β), following the softening technique of Farajtabar et al. [9]. Specifically, . In off-policy evaluation experiments, we consider a fixed target and several choices of logging policy (see Table 1). In off-policy learning we use π 1,(0.9,0) as the logging policy.
Reward predictors. We obtain reward predictorsη by training linear models via weighted least squares with 2 regularization, using 2-fold cross-validation to tune the regularization parameter. We (23) 45 (22)   experiment with weights z(x, a) ∈ {1, w(x, a), w 2 (x, a)} and we also consider the special weight design of Farajtabar et al. [9], which we call MRDR (see Appendix C for details). In evaluation experiments, we use 1/2 of the bandit data to trainη; in learning experiments, we use 1/3 of the bandit data to trainη. In addition to the four trained reward predictors, we also considerη ≡ 0.
Baselines. We include a number of estimators in our evaluation: the direct modeling approach (DM), doubly-robust (DR) and its self-normalized variant (snDR), our approach (DRs), and the doubly-robust version of the SWITCH estimator of Wang et al. [27], which also performs a form of weight clipping. 2 Note that DR withη ≡ 0 is identical to inverse propensity scoring (IPS); we refer to its self-normalized variant as snIPS. Our estimator and SWITCH have hyperparameters, which are selected by their respective model selection procedures (see Appendix C for details about the hyperparameter grid).

Off-policy Evaluation
We begin by evaluating different configurations of DRs via an ablation analysis. Then we compare DRs with baseline estimators. We have a total of 108 experimental conditions: for each of the 9 datasets we use 6 logging policies and consider stochastic or deterministic rewards. Except for the learning curves below, we always take n to be all available bandit data (75% of the overall dataset).
We measure performance with clipped MSE, E (V − V (π)) 2 ∧ 1 , whereV is the estimator and V (π) is the ground-truth value (computed on the held-out 25% of the data). We use 500 replicates of bandit-data generation to estimate the MSE; statistical comparisons are based on paired t-tests at significance level 0.05. In some of our ablation experiments, we pick the best hyperparameters against the test set on a per-replicate basis, which we call oracle tuning and always call out explicitly.
Ablation analysis. Table 2 displays the results of two ablation studies, one evaluating different reward predictors and the other evaluating the optimistic and pessimistic shrinkage types.
On the left, for each fixed estimator type (e.g., DR) we compare different reward predictors by reporting the number of conditions where it is statistically indistinguishable from the best and the number of conditions where it statistically dominates all other estimators using that predictor. For DRs we use oracle tuning for the shrinkage type and coefficient. The table shows that weight shrinkage strongly influences the choice of regressor. For example, z ≡ 1 and z = w are top choices for DR, but with the inclusion of shrinkage in DRs, z = w 2 emerges as the best single choice. 3 In our comparison experiments below, we therefore restrict our attention to z = w 2 and additionally also considerη ≡ 0, because it allows including IPS as a special case of DRs. Somewhat surprisingly, MRDR is in our experiments dominated by other reward predictors (except forη ≡ 0), and this remains true even with a deterministic target policy (see Table 4 in the appendix).
On the right of Table 2, we compare optimistic and pessimistic shrinkage when paired with a fixed reward predictor (using oracle tuning for the shrinkage coefficient). We report the number of times that one estimator statistically dominates the other. The results suggest that both shrinkage types are important for robust performance across conditions, so we consider both choices going forward.  Table 6 in the appendix for statistical significance.   (7) (corresponding to the bias and bias bounds) by empirical averages and takes their pointwise minimum. DRs-upper adds to theses estimates twice their standard error, before taking minimum, more closely matching our theory. For DRs, we only use the zero reward predictor and the one trained with z = w 2 , and we always select between both shrinkage types. Since SWITCH also comes with a model selection procedure, we use it to select between the same two reward predictors as DRs.
In the deterministic case (left plot) we see that DRs-upper has the best aggregate performance, by a large margin. DRs-direct also has better aggregate performance than the baselines on most of the conditions. In the stochastic case, DRs-direct has similarly strong performance, but DRs-upper degrades considerably, suggesting this model selection scheme is less robust to stochastic rewards. We illustrate this phenomenon in Figure 2, plotting the MSE as a function of the number of samples for one choice of a logging policy and dataset, with deterministic rewards on the left and stochastic on the right. Because of a more robust performance, we therefore advocate for DRs-direct as our final method. Following prior work [24, 25, 23], we learn a stochastic linear policy π u where π u (a | x) ∝ exp u f (x, a) and f (x, a) is a featurization of context-action pairs. We solve 2 -regularized empirical risk minimization u = argmin u −V (π u ) + γ u 2 via gradient descent, whereV is a policy-value estimator and γ > 0 is a hyperparameter. For these experiments, we partition the data into four quarters: one full information segment for training the logging policy and as a test set, and three bandit segments for (1) training reward predictors, (2) learning the policy, and (3) hyperparameter tuning and model selection. The logging policy is π 1,(0.9,0) and since there is no fixed target policy, we consider three reward predictors:η ≡ 0, andη trained with z = 1 µ(a|x) and z = 1 µ(a|x) 2 . In Figure 3 we display the performance of four methods (DM, DR, IPS, and DRs-direct) on four of the UCI datasets. For each method, we compute the average value of the learned policy on the test set (averaged over 10 replicates) and we report this value normalized by that for IPS. For DM and DR, we select the hyperparamater γ and reward predictor optimally in hindsight, while for DRs we use our model selection method. Note that we do not compare with SWITCH here as it is not amenable to gradient-based optimization [23]. Except for the opt-digits dataset, where all the methods are comparable, we find that off-policy learning using DRs-direct always outperforms the baselines.

A Derivation of Shrinkage Estimators
In this section we provide detailed derivations for the two estimators.
We first derive the pessimistic version. Recall that the optimization problem decouples across (x, a), so we focus on a single (x, a) pair, and we omit explicit dependence on these. Fixing λ ≥ 0, we must solve The optimality conditions are that The first case for v cannot occur, since setting v = 1 would makeŵ = −λ/2 ≤ 0 (according to the first equation), but we know that w ≥ 0. Ifŵ < w then we must haveŵ = λ/2. And so, we get which is the clipped estimator.
For the optimistic version, the optimization problem is The optimality conditions are This gives the optimistic estimator Notice that this estimator does not depend on the weighting function z, so it does not depend on how we train the regression model.

B Proofs
Proof of Proposition 1. The law of total variance gives For the first term, since a ∈A π(a | x)η(x, a ) does not depend on a, r, it does not contribute to the conditional variance, and we get Now, using our assumption that 0 ≤ŵ(x, a) ≤ w(x, a) = π(a | x)/µ(a | x), we get and hence for all x ∈ X , Here in the last step we are using boundedness of the regression function η, and the estimated regression functionη.
Thus, for T 1 the second term is at most 1, and for T 2 , we have using the above calculation. Therefore, the residual terms add up to at most 5.
Proof of Proposition 2. We analyze the optimistic version. If MSE(V DM ) ≤ MSE(V DR ), then we simply take λ = 0 at which point the objective is clearly minimized byŵ = 0. Therefore we recover V DM . On the other hand if MSE(V DR ) ≤ MSE(V DM ), then we set λ → ∞ so that the minimizer iŝ w = w. This recovers the doubly-robust estimator.
Proof of Theorem 3. The main technical part of the proof is a deviation inequality for the sample variance. For this, let us fix θ, which we drop from notation, and focus on estimating the variance We have the following lemma Lemma 4 (Variance estimation). Let Z 1 , . . . , Z n be iid random variables, and assume that |Z i | ≤ R almost surely. Then there exists a constant C > 0 such that for any δ ∈ (0, 1), with probability at least 1 − δ Proof. For this lemma only, define µ = E[Z]. By direct calculation We work with the second term first. Let Z 1 , . . . , Z n be an iid sample, independent of Z 1 , . . . , Z n . Now, by Theorem 3.4.1 of De la Pena and Giné [5], we have for a universal constant C > 0. Thus, we have decoupled the U-statistic. Now let us condition on Z 1 , . . . , Z n and write X j = 1 n−1 i =j (Z i − µ), which conditional on Z 1 , . . . , Z n is non-random.
We will apply Bernstein's inequality on 1 n n j=1 X j (Z j − µ), which is a centered random variable, conditional on Z 1:n . This gives that with probability at least 1 − δ This bound holds with high probability for any {X j } n j=1 . In particular, since |X j | ≤ R almost surely, we get that with probability 1 − δ The factors of C arise from working through the decoupling inequality.
Let us now address the first term, a simple application of Bernstein's inequality gives that with probability at least 1 − δ Combining the two inequalities, we obtain the result.
Since we are estimating the variance of the sample average estimator, we divide by another factor of n. Thus the error terms in Lemma 4 are O(n −3/2 ) and O(n −2 ) respectively, which are both o(n −1 ). We will simply write these error terms are o(n −1 ) from now on.
For the model selection result, first apply Lemma 4 for all θ ∈ Θ, taking a union bound (This only requires that |Θ| = o(exp(n))). Further take a union bound over the event that Bias(θ) ≤ BiasUB(θ) for all θ ∈ Θ, if it is needed. Then, observe that for any θ 0 ∈ Θ 0 we have The first inequality uses Lemma 4 and the fact that Bias ≤ BiasUB. The second uses thatθ optimizes this quantity, and the third uses the property that BiasUB(θ 0 ) = 0 by assumption.

B.1 Construction of bias upper bounds.
In this section we give detailed construction of bias upper bounds that we use in the model selection procedure. Recall that this is for the analysis only. Empirically we found that using the estimators alone -not the upper bounds -leads to better performance.
Throughout, we fix a set of hyperparameters θ, which we suppress from the notation.
Direct bias estimation. The most straightforward bias estimator is to simply approximate the expectation with a sample average.
This estimator has finite-sum structure, and naively, the range of each term is w ∞ = max x,a w(x, a).
The variance is at most E µ [w(x, a) 2 ]. Hence Bernstein's inequality gives that with probability at least 1 − δ Inflating the estimate by the right hand side gives BiasUB, which is a high probability upper bound on Bias.
Pessimistic estimation. The bias bound used in the pessimistic estimator and its natural sample estimator are Note that since we have already eliminated the dependence on the reward, we can analytically evaluate the expectation over actions, which will lead to lower variance in the estimate.
Again we perform a fairly naive analysis. Sinceŵ(x, a) ≤ w(x, a) and using the fact that w(x, a) = π(a | x)/µ(a | x) the range of the random variable is simply 1. Therefore, Hoeffding's inequality gives that with probability 1 − δ and we use the right hand side for our high probability upper bound.
Optimistic estimation. For the optimistic bound, we must estimate two terms, one involving the regressor and one involving the importance weights. We use Note here that the former uses sampled actions from µ, but does not involve the importance weight, while the latter involves the importance weight but analytically evaluates the expectation over µ. Thus we can expect that both are fairly low variance.
For both, we use Bernstein's inequality. For T 1 the range is naively z ∞ = max x,a z(x, a) and the variance is E µ [z(x, a) 2 ]. Thus we get that with probability at least 1 − δ/2 For the second one, the range is max x,a w(x, a)/z(x, a) and we just use Hoeffding's inequality, so that with probability 1 − 2δ z(x,a) log(2/δ) 2n The high probability upper bound follows by multiplying the two right hand sides together and taking square root.

C Experimental Details and Additional Results
Dataset statistics. We use datasets from the UCI Machine Learning Repository [6]. Dataset statistics are displayed in Table 3. MRDR. Farajtabar et al. [9] propose training the regression model with a specific choice of weighting z, which we also use in our experiments. When the evaluation policy π is deterministic, they set z(x, a) = 1{π(x) = a} · 1−µ(a|x) µ(a|x) 2 . For stochastic policies, following the implementation of Farajtabar et al., we sample a i ∼ π(· | x i ) for each example in the dataset used to train the reward predictor. Then we proceed as if the evaluation policy deterministically chooses a i on example x i . Actions  6  8  4  10  5  10  6  10  26  Examples  214  336  846  1484  5473  5620  6435  10992  20000   Table 3: Dataset statistics.

Dataset Glass Ecoli Vehicle Yeast PageBlok OptDigits SatImage PenDigits Letter
Ablation study for deterministic target policy. Since MRDR is more suited to deterministic policies, we also report the results of our regressor and shrinkage ablations for a deterministic target policy π 1,det in Table 4. As with the stochastic policies, the estimator influences the choice of reward predictor, but note that z = 1 and z = w are more favorable here. This is likely due to high variance suffered from training with z = w 2 , because the importance weights are larger with a deterministic policy. Our shrinkage ablation reveals that both estimator types are important also when the target policy is deterministic.
Ablation study for model selection. In Table 5, we show the comparison of different model selection methods under different reward predictor pairs and different shrinkage types. In most cases, Dir-all (DRs-direct where the bias bound is estimated as the pointwise minimum of (1) the bias, (2) the optimistic bound and (3) the pessimistic bound) and Up-all (all bias estimates are adjusted by adding twice standard error before taking pointwise minimum) are most frequently statistically indistinguishable from the best, which suggests that our proposed bias estimate (by taking pointwise minimum of the three) is robust and adaptive.
Comparisons across additional experimental conditions. In Figure 4 and Figure 5, we compare our new estimators, DRs-direct and DRs-upper, with baselines across various conditions (apart from deterministic versus stochastic rewards from the main paper). We first investigate the performance under friendly logging (logging and evaluation policies are derived from the same deterministic policy, π 1,det ), adversarial logging (logging and evaluation policies are derived from different policies π 1,det , π 2,det ), and uniform logging (logging policy is uniform over all actions). Then we plot the performance in the small sample regime, where we aggregate the 108 conditions (6 logging policies, 9 datasets, deterministic/stochastic reward) at just 200 bandit samples.
Comparisons across all reward predictors. In Table 6- Table 9, we compare the performance of DRs-direct and DRs-upper against baselines across various choices of reward predictors. Specifically, we consider cases when DRs is employing model selection to pick from two predictors and construct a separate comparison table for each of the following sets: {η ≡ 0, MRDR}, {η ≡ 0, z ≡ 1}, {η ≡ 0, z = w} as well as {η ≡ 0, z = w 2 } (matching the setting of the main paper). We report the number of conditions where each estimator is statistically indistinguishable from the best, and the number of conditions where each estimator statistically dominates all others. DRs-upper is most often in the top group and most often the unique winner. DRs-direct is also better than snIPS, snDR, and SWITCH. These results suggest that our shrinkage estimators are robust to different choices of reward predictors, and not just limited to the recommended set {η ≡ 0, z = w 2 }.
Robustness of DRs-direct and DRs-upper (w.r.t. inclusion of more reward predictors) In Figure 6, we test the robustness of our proposed methods as we incorporate more reward predictors. Our practical suggestions is to use {η ≡ 0, z = w 2 } (shown as DRs-direct and DRs-upper in the figure). Here we also evaluate these methods when selecting from all reward predictors in the set {η ≡ 0, z ≡ 1, z = w, z = w 2 , MRDR} (shown as DRs-direct (all) and DRs-upper (all) in the figure). For DRs-direct, the curves almost match, suggesting that it is quite robust. However, DRs-upper is less robust to including additional reward predictors.   Table 6: Significance testing for different estimators across all conditions (DM, snDR use reward z = w 2 , while SWITCH and DRs use reward from {η = 0, z = w 2 }). In the top row, we report the number of conditions where each estimator is statistically indistinguishable from the best, and in the bottom row we report the number of conditions where each estimator is the uniquely best.     Table 7: Significance testing for different estimators across all conditions (DM, snDR use reward estimated from MRDR, while SWITCH and DRs use reward from {η = 0, MRDR}). In the top row, we report the number of conditions where each estimator is statistically indistinguishable from the best, and in the bottom row we report the number of conditions where each estimator is the uniquely best.
snIPS DM snDR SWITCH DRs-direct DRs-upper  Best or Tied  10  39  19  15  25  49  Unique Best  0  23  3  1  5  43  Table 8: Significance testing for different estimators across all conditions (DM, snDR use reward z = 1, while SWITCH and DRs use reward from {η = 0, z = 1}). In the top row, we report the number of conditions where each estimator is statistically indistinguishable from the best, and in the bottom row we report the number of conditions where each estimator is the uniquely best.
snIPS DM snDR SWITCH DRs-direct DRs-upper  Best or Tied  3  44  5  5  30  58  Unique Best  0  23  0  0  6  51  Table 9: Significance testing for different estimators across all conditions (DM, snDR use reward z = w, while SWITCH and DRs use reward from {η = 0, z = w}). In the top row, we report the number of conditions where each estimator is statistically indistinguishable from the best, and in the bottom row we report the number of conditions where each estimator is the uniquely best.