Title: OFF-POLICY EVALUATION AND LEARNING FROM LOGGED BANDIT FEEDBACK: ERROR REDUCTION VIA SURROGATE POLICY

Abstract: When learning from a batch of logged bandit feedback, the discrepancy between the policy to be learned and the off-policy training data imposes statistical and computational challenges. Unlike classical supervised learning and online learning settings, in batch contextual bandit learning, one only has access to a collection of logged feedback from the actions taken by a historical policy, and expect to learn a policy that takes good actions in possibly unseen contexts. Such a batch learning setting is ubiquitous in online and interactive systems, such as ad platforms and recommendation systems. Existing approaches based on inverse propensity weights, such as Inverse Propensity Scoring (IPS) and Policy Optimizer for Exponential Models (POEM), enjoy unbiasedness but often suffer from large mean squared error. In this work, we introduce a new approach named Maximum Likelihood Inverse Propensity Scoring (MLIPS) for batch learning from logged bandit feedback. Instead of using the given historical policy as the proposal in inverse propensity weights, we estimate a maximum likelihood surrogate policy based on the logged action-context pairs, and then use this surrogate policy as the proposal. We prove that MLIPS is asymptotically unbiased, and moreover, has a smaller nonasymptotic mean squared error than IPS. Such an error reduction phenomenon is somewhat surprising as the estimated surrogate policy is less accurate than the given historical policy. Results on multi-label classification problems and a large-scale ad placement dataset demonstrate the empirical effectiveness of MLIPS. Furthermore, the proposed surrogate policy technique is complementary to existing error reduction techniques, and when combined, is able to consistently boost the performance of several widely used approaches. * equal contribution, the order of the two co-first authors is determined by a coin toss

1. INTRODUCTION:

While maintaining online and interactive systems for information retrieval, news recommendation, ad placement, and e-commerce, we collect large batches of logs during testing phases and past deployment periods (Li et al., 2010) . Such logs contain rich information that can be used for many purposes. For example, the logs of an e-commerce system record the decisions (or actions) on which ads or recommendations are displayed to a user given a context, and the corresponding feedback (or reward), including whether the user clicks on any of the displayed items and whether a purchase occurs afterwards. Although the logs are collected when the online system is deployed with a historical algorithm (or policy), they are informative for future improvements and design of the system. One application of such logs is to estimate the performance of new policies, also known as off-policy evaluation (Dudík et al., 2014; Li et al., 2011; 2014) . Furthermore, the use of logs allows for an accurate and more efficient way to test and optimize new policies without expensive trial-and-error cycles in traditional A/B tests, which often take weeks.

Since the logged feedback only provides partial information, policy evaluation and optimization using logs are often formulated as batch contextual bandit learning. Different from the online learning setting, batch contextual bandit learning is statistically more challenging because the collected logs are off-policy, that is, they are generated by a historical policy that differs from the current policy we intend to evaluate or optimize. To bridge this discrepancy, Inverse Propensity Scoring (IPS) has been introduced to construct an unbiased counterfactual estimator of policy performance using off-policy data (Bottou et al., 2013) . However, such an estimator tends to have a large mean squared error when the current policy and the historical policy are very different. To reduce the mean squared error, a number of regularization and control variate approaches have been introduced (e.g., Dudík et al. (2014) ; Hirano et al. (2003) ; Ionides (2008) ; Li et al. (2015) ). Notably, Swaminathan & Joachims (2015a) proposed Policy Optimizer for Exponential Models (POEM), which introduces a mean squared error regularizer based on the counterfactual risk minimization principle. Empirical evaluations also suggested the effectiveness of these approaches on policy evaluation and optimization.

In this paper, we introduce a new yet simple parametric approach for mean squared error reduction in batch contextual bandit learning. Instead of using the given historical policy, we use linear models or neural network models to estimate a maximum likelihood surrogate policy using the logged actioncontext pairs. Then we use such a surrogate policy as the proposal distribution to obtain the inverse propensity weights in the off-policy estimator, as if the logs are generated by this surrogate policy. This idea dates back to the "estimated sampler" technique in statistics (Delyon & Portier, 2016; Henmi et al., 2007) . We provide theoretical justification for this approach, which is named Maximum Likelihood Inverse Propensity Scoring (MLIPS). In particular, we show that the proposed MLIPS estimator is asymptotically unbiased, and moreover, has a smaller nonasymptotic mean squared error than the IPS estimator. Such an error reduction effect is counterintuitive as we replace the known historical policy with a less accurate estimated surrogate policy, which is supposed to increase the mean squared error. We evaluate the MLIPS estimator on several multi-label classification problems and a large-scale ad placement dataset to demonstrate its empirical effectiveness on mean squared error reduction for policy evaluation and optimization. Furthermore, we also combine the MLIPS estimator with several existing approaches. We find that our surrogate policy technique is complementary to existing mean squared error reduction techniques and achieves consistently improved performance.

2. OFF-POLICY EVALUATION AND LEARNING FROM LOGGED BANDIT FEEDBACK:

In this section, we introduce the background on off-policy evaluation and learning from logged bandit feedback. In particular, we focus on IPS and present several existing mean squared error reduction and regularization approaches.

2.1. INVERSE PROPENSITY SCORING:

The value function used to evaluate a target policy π is defined as

V = E π [r] = E x∼ν E a∼π(• | x) E r∼D(•|a,x) [r].

(2.1) Here x is the context drawn from the context distribution λ, which is independent of π, a is the action taken according to π given context x, and r is the reward (or feedback) received.

In the off-policy setting, we are not able to sample different actions from the target policy π and obtain reward, which is expensive and time-consuming in practice. Instead, we collect samples from a logging policy µ, that is, a ∼ µ(• | x), and expect to use the logs to evaluate a target policy and further perform policy optimization.

To bridge the discrepancy between π and µ, the IPS estimator, which is known as the importance sampling estimator, reweights each logged action-context pair as follows,

V IPS = 1 n n i=1 ρ(x i , a i ) • r i = 1 n n i=1 π(a i | x i ) µ(a i | x i ) • r i . (2.2)

In the sequel, we use V to denote V IPS for notational simplicity.

It is worth noting that the IPS estimator is an unbiased estimator of V , and thus has been widely adopted as an objective function for optimizing the target policy π. However, ρ(

x i , a i ) = π(a i | x i )/µ(a i | x i ) in (2.

2) may induce a large mean squared error, especially when the logging policy µ is very different from the target policy π. As a result, the IPS estimator often leads to unsatisfactory policy optimization and poor generalization performance.

2.2. MEAN SQUARED ERROR REDUCTION AND REGULARIZATION:

To reduce the mean squared error of IPS, several thresholding approaches have been proposed and studied in the literature (e.g., Bottou et al. (2013) ; Cortes et al. (2010) ; Ionides (2008); Strehl et al. (2010) ). One straightforward approach is Propensity Weight Capping (Ionides, 2008) , which takes the form

EQUATION

where M > 1 is the threshold parameter. Although thresholding reduces the mean squared error when M is small, it introduces a large bias.

More recently, Swaminathan & Joachims (2015a) proposed the POEM algorithm for batch learning from bandit feedback. POEM is motivated by the structural risk minimization principle and a generalization bound that characterizes the mean squared error of

V (M )

IPS based on an empirical Bernstein argument. The POEM algorithm jointly optimizes V (M ) IPS and its empirical standard deviation, which is also known as counterfactual risk minimization.

Let u i π = min{M, π(a i | x i )/µ(a i | x i )} • r i , ūπ = n i=1 u i π /n, and Var π ( V (M ) IPS ) = ( n i=1 (u i π - ūπ )

2 )/(n -1), the POEM algorithm searches for a policy π that maximizes

V (M ) IPS -λ Var π ( V (M ) IPS )/n.

(2.4)

Here M > 1 and λ ≥ 0 are the thresholding and regularization parameters, respectively. Also note that when λ = 0, the POEM objective in (2.4) reduces to (2.3).

Motivated by the propensity overfitting problem of IPS and POEM, Swaminathan & Joachims (2015b) proposed to use control variates, which lead to the following self-normalized estimator

V SN = 1/n • n i=1 π(a i | x i )/µ(a i | x i ) • r i 1/n • n i=1 π(a i | x i )/µ(a i | x i )

.

(2.5)

Note that V SN is shifted by a constant C if each r i is shifted to r i + C. In other words, V SN is equivariant (Hesterberg, 1995) and always lies within the range of r i . In contrast, the IPS estimator does not have such properties. Self-Normalized POEM (Norm-POEM), a variant of POEM, was also proposed by Swaminathan & Joachims (2015b) . In particular, Norm-POEM searches for a policy that maximizes the normalized estimator regularized by its empirical standard deviation

Var π ( V SN ) = 1/n • n i=1 (r i -V SN ) 2 • π(a i | x i )/µ(a i | x i ) 2 1/n • n i=1 π(a i | x i )/µ(a i | x i ) 2 .

(2.6)

In addition, other techniques, such as control variates and doubly-robust estimators Dudík et al. (2014) have also been applied to reduce the mean squared error of the off-policy estimator.

3. ERROR REDUCTION VIA SURROGATE POLICY:

Instead of directly using the logging policy propensities, we propose to refit a surrogate policy and use it to obtain the inverse propensity weights in the IPS estimator defined in (2.2). We assume that the logging policy µ(a | x) is parameterized by β ∈ R d and denote it by µ(a | x; β). In particular, we assume the logging policy with β = β * generates the logged action-context pairs. Although we have the access to µ(a | x; β * ), we choose to use the maximum likelihood estimator of β * based on {(a i , x i )} n i=1 as a surrogate policy parameter, which is denoted as β, to replace β * and obtain a more accurate estimator of the value function V defined in (2.1). In particular, we define the MLIPS estimator of V as

V = 1 n n i=1 π(a i | x i ) µ(a i | x i ; β) • r i , (3.1)

where {(a i , x i )} n i=1 are the logged action-context pairs, which are independently sampled from µ(a | x; β * ).

Unlike the IPS estimator V in (2.2), the MLIPS estimator V in (3.1) is biased in general. However, V is asymptotically unbiased, and moreover, in the following subsection we show that V achieves a smaller mean squared error than V when the logging distribution µ(a | x; β) is properly chosen.

3.1. THEORETICAL ANALYSIS:

In this section, for the simplicity of analysis, we assume that the reward r is determined by a and x, that is, r = r(a, x). For notational simplicity, in the subsequent analysis we use the following equivalent definitions of V and V based on joint distributions,

V = 1 n n i=1 π(a i , x i ) µ(a i , x i ; β * ) • r(a i , x i ), V = 1 n n i=1 π(a i , x i ) µ(a i , x i ; β) • r(a i , x i ), since we have π(a | x) µ(a | x; β) = π(a, x)/λ(x) µ(a, x; β)/λ(x) = π(a, x) µ(a, x; β) . (3.2)

For the ease of notation, we denote

E (a,x)∼µ(•,•;β * ) [ • ] by E[ • ]

. Also, we denote by • the 2 -norm of a vector or the spectral norm of a matrix. For a function f (β), we denote by ∂f (β * )/∂β its derivative evaluated at β = β * , which is ∂f (β)/∂β| β=β * .

Before we lay out the main theory, we first introduce the following definitions.

Definition 3.1 (Score Function and Fisher Information). The score function S(a, x; β) ∈ R d and the Fisher Information matrix I(β) ∈ R d×d are defined as

S(a, x; β) = ∂ log µ(a, x; β) ∂β , I(β) = -E ∂S(a, x; β) ∂β . (3.3)

It is worth noting that the reformulation from µ(a | x; β) to µ(a, x; β) does not change the score function or the Fisher information matrix, since the marginal distribution of the context x in (3.2), namely λ(x), does not depend on β, and hence its partial derivative with respect to β is zero.

Definition 3.2 (Deviation Function). The difference between π(a, x)/µ(a, x; β) • r(a, x) and the true value V of the target policy, which is defined in (2.1), is denoted by

D V (r, a, x; β) = π(a, x) µ(a, x; β)

• r(a, x) -V.

(3.4)

In the sequel, we introduce two assumptions and a condition on an event. The next assumption ensures that the Fisher information matrix of the joint logging distribution µ(a, x; β * ) is well behaved and the identifiability of the model is thus ensured.

Assumption 3.3 (Nonsingular Fisher Information). For the joint distribution µ(•, •; β * ), we assume that its Fisher information matrix satisfies

I -1 (β * ) = E ∂S(a, x; β * ) ∂β -1 = O(1). (3.5)

The next assumption ensures the score and deviation functions are sufficiently smooth. Assumption 3.4 (Smoothness of Score and Deviation). For the deviation function D V (r, a, x; β) defined in (3.4), we assume that

EQUATION

where the second equality holds for any β. Meanwhile, for the score function S(a, x; β) defined in (3.3), we assume that for any

EQUATION

where ∂ 2 S(a, x; β)/∂β 2 is a tensor consisting of the third-order derivative of log µ(a, x; β) with respect to β.

Here (∂ 2 S(a, x; β 0 )/∂β 2 )(v 1 , v 2 , •) is the bilinear map R d × R d → R d induced by the tensor, which maps (v 1 , v 2 ) to a vector in R d .

The Assumptions 3.3-3.4 are satisfied, under necessary regularity conditions, by many popular models such as the multinomial logistic regression model which will be illustrated in detail in §D. Before introducing the condition, we define several events to simplify the presentation. In the following, we first define an event on the estimation error of the maximum likelihood estimator β.

Definition 3.5 (Maximum Likelihood Estimation Error). For the maximum likelihood estimator β and the true parameter β * , we define the event E β (t β ) as

E β (t β ) = β -β * ≤ t β . (3.8)

Next we define several events on the concentration behavior of the score function defined in (3.3) and the deviation function defined in (3.4) as well as their derivatives. Definition 3.6 (Concentration of Score). For the score function with true parameter β * , we define the following events,

E SG (t SG ) = 1 n n i=1 S(a i , x i ; β * ) -E S(a, x; β * ) ≤ t SG , (3.9) E SH (t SH ) = 1 n n i=1 ∂S(a i , x i ; β * ) ∂β -E ∂S(a, x; β * ) ∂β ≤ t SH .

(3.10) Also, we define

E ST (t ST ) = sup β, v =1 1 n n i=1 ∂ 2 S(a i , x i ; β) ∂β 2 (v, v, •) -E ∂ 2 S(a, x; β) ∂β 2 (v, v, •) ≤ t ST ,

where

(∂ 2 S(a, x; β)/∂β 2 )(v, v, •) is defined in Assumption 3.4. Then we define the joint event E S (t S ) = E SG (t SG ) ∩ E SH (t SH ) ∩ E ST (t ST )

, where t S = (t SG , t SH , t ST ). Definition 3.7 (Concentration of Deviation). For deviation function with true parameter β * , namely D V (r, a, x; β * ), we define

E DG (t DG ) = 1 n n i=1 ∂D V (r i , a i , x i ; β * ) ∂β -E ∂D V (r, a, x; β * ) ∂β ≤ t DG . (3.11)

Also, we write

E DH (t DH ) = sup β∈R d 1 n n i=1 ∂ 2 D V (r i , a i , x i ; β) ∂β 2 -E ∂ 2 D V (r, a, x; β) ∂β 2 ≤ t DH .

Then we define the joint event

E D (t D ) = E DG (t DG ) ∩ E DH (t DH ), where t D = (t DG , t DH ).

We now present a condition on the overall tail behavior of the probability of the events defined above.

Condition 3.8 (Concentration Tail Behavior). Let t = (t β , t S , t D ) and

E(t ) = E β (t β ) ∩ E S (t S ) ∩ E D (t D ),

(3.12) it holds that P(E(t )) ≥ 1 -f (t), where t = t ∞ for some decreasing tail function f (t) such that ∞ 0 t k df (t) is finite and goes to zero as n → ∞ for any nonnegative integer k and decreases along k. Here f (t) also depends on the dimension d and the sample size n.

Condition 3.8 states that, in addition to the upper bound on the estimation error defined in Definition 3.5, the sample versions of the score function defined in (3.3) and the deviation function defined in (3.4) as well as their derivatives all well concentrate to their population versions. In particular, the condition on the integrability of the tail function f (t) characterizes that the tail probability of concentration decays faster than the polynomial rate. As we will illustrate using the multinomial logistic regression model in §D, such a superpolynomial tail behavior is typically guaranteed by exponential concentration inequalities such as Bernstein-type inequalities and their matrix variants.

The following theorem compares the mean squared errors of the MLIPS and IPS estimators defined in (3.1) and ( 2 Theorem 3.9 (Mean Squared Error Reduction). Under Condition 3.8 and Assumptions 3.3 and 3.4, the MLIPS V is asymptotically unbiased and it holds that

EQUATION

and

ξ(n) = (E[( V -V ) 2 ]) 1/2 • O((ζ DG • (ζ ST + 1) + ζ DH ) • ( ∞ 0 t 4 df (t)) 1/2 ) + O((ζ 2 DG • (ζ ST + 1) + ζ DG • ζ DH ) • ∞ 0 t 3 df (t)).

Proof. See §A for a detailed proof.

It is worth noting that the key to our guarantee for MSE reduction lies in the fact that

E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) 2 = E ( V -V ) 2 -1/n • Var Π(r, x, a; β * ) , which is actually an orthogonality relation between ( V -V ) -(1/n) • n i=1 Π(r i , a i , x i ; β * ) and (1/n) • n i=1 Π(r i , a i , x i ; β * ).

We interpret the MSE reduction guarantee in Theorem 3.9 as follows. For the simplicity of discussion, for now we assume that the dimension d does not scale with the sample size n. The 1/n • Var(Π(r, x, a; β * )) term on the right-hand side of (3.13) characterizes the reduction of the mean squared error. For example, in the multinomial logistic regression model, the ξ(n) term is roughly of the order 1/n 3/2 . As a consequence, for a sufficiently large n, we have

1/n • Var Π(r, x, a; β * ) -ξ(n) ≥ 1/(2n) • Var Π(r, x, a; β * ) .

(3.15) In other words, the mean squared error of the MLIPS estimator is at least smaller than that of the IPS estimator by a margin of 1/(2n) • Var(Π(r, x, a; β * )), where Var(Π(r, x, a; β * )) is a population quantity that does not scale with n. In comparison, the mean squared error is also of the order 1/n in the multinomial logistic regression model. That is to say, the reduction effect does not vanish even when n → ∞. See §D for more discussions and a more detailed illustration of Theorem 3.9 using the multinomial logistic regression model.

3.2. PRACTICAL CONSIDERATIONS:

Throughout the theoretical analysis, we assume that the parametrization of the logging policy is known. However, in practice we may not know the class of logging policies that generate the logs, in which cases we can use universal function approximators such as neural networks to estimate such surrogate policies. The parametrization of the logging distribution may be misspecified when we use those approximators. However, when universal function approximators such as neural networks are used, the approximation error often diminishes with an increasing number of layers and neurons (see, for example, Schmidt-Hieber (2017); Telgarsky (2016) ; Yarotsky (2017) ). Such a diminishing approximation error should enter the Taylor expansions in Lemma A.1-A.2.

In our experiments, we found that neural network policies worked very well on both standard multi-label classification datasets and a large-scale ad placement dataset.

Due to its simplicity, MLIPS can be easily implemented without much extra effort. Furthermore, MLIPS is orthogonal to other existing approaches for mean squared error reduction in policy evaluation and optimization. Hence, it can often be combined straightforwardly with them. In our experiments, we observed that it can be used to further improve POEM for policy optimization.

Another advantage of our approach is that it still works even when we have no access to the logging policy, which often happens in real world due to various reasons. In those cases, IPS may not work at all, but our approach exhibits superior performance, as shown in our experiments.

4. EXPERIMENTS:

In this section, we empirically evaluate the effectiveness of the proposed method on a number of datasets. We first check the reduction of the mean squared error enabled by the MLIPS estimator. Then we apply IPS, MLIPS, POEM and MLPOEM to policy optimization and compare their performance on several datasets.

4.1. SETTINGS:

Datasets. First, we adopt the same experimental design as the one specified in Swaminathan & Joachims (2015a) to generate batch contextual bandit learning datasets from supervised learning datasets. Four multi-label datasets are selected from the LibSVM repository (see Swaminathan & Joachims (2015a) for more details). To construct a batch contextual bandit learning dataset, we take a supervised learning dataset D * = {(x i , y * i )} n i=1 , simulate using a logging policy µ by sampling y i ∼ µ(• | x i ), and collect the reward as the negative Hamming distance -∆(y * i , y i ) between the supervised label and the sampled label. We use a Conditional Random Field (CRF) model (Sutton & McCallum, 2012) trained on 5% of the data as the logging policy µ. We repeat this procedure four times to generate the entire bandit feedback dataset D = {(x i , y i , r i = -∆(y * i , y i ), µ(y i | x i ))} n i=1 . Both the training sets and held-out testing sets are constructed in the same way as suggested in Swaminathan & Joachims (2015a) .

In addition to these standard datasets, we also evaluate the effectiveness of our method on a large-scale ad placement dataset. The dataset is collected by Criteo, a leader in the display advertising industry (Lefortier et al., 2016) . For this dataset, we consider an ad display scenario where a policy selects the products to be displayed on a website when a user arrives. Provided the candidate set of products and impression context, we hope the policy to place ads such that the aggregated click-through-rate (CTR) or the number of clicks is maximized. We consider a subset of the dataset, which is used in the NIPS 2017 Criteo Ad Placement Challenge. Each ad is represented by a 74000-dimensional feature vector. For each context (or impression), the logged action of selecting a candidate ad, a binary reward value on whether the displayed product is clicked by the user, and the probability that the logging policy picks such a specific candidate are recorded. More details can be found at CrowdAI (2017).

Surrogate policy estimation. To fit the surrogate policy, we apply two models, a simple logistic regression model and a one-hidden-layer perceptron with ten ReLU activation units, both with 2regularization. Here five-fold cross validation is used to tune the regularization parameter. We use the L-BFGS algorithm (Liu & Nocedal, 1989) for optimization.

Policy optimization. We consider IPS, POEM (Swaminathan & Joachims, 2015a) , and Norm-POEM (Swaminathan & Joachims, 2015b) . We compare their performance with MLIPS as well as the combination of our surrogate policy technique with POEM (MLPOEM). There are several hyperparameters in POEM, Norm-POEM, and MLPOEM, including the thresholding parameter and the regularization parameter. We use five-fold cross validation on the training set to tune them. For reward maximization, following the procedures of POEM, we initialize the model weights to zeros, use mini-batch AdaGrad (Duchi et al., 2011) with a batch size of 100 and step size η = 1. On all datasets, we repeat the experiments ten times to report the average generalization performance.

4.2. MEAN SQUARED ERROR REDUCTION IN POLICY ESTIMATION:

First, we check whether the MLIPS estimator has a smaller mean squared error than the vanilla IPS estimator. Instead of comparing the estimation of the value function, we focus on comparing the performance of MLIPS and IPS on off-policy gradient estimation, whose accuracy is crucial to policy optimization. We use the LYRL dataset (Swaminathan & Joachims, 2015a) and combine the training and testing sets to obtain a large bandit feedback dataset. Given a reasonably accurate policy weight vector (after training with 10000 mini-batch updates), we compute its IPS-based gradient estimator on the entire dataset to get a rough "ground-truth" gradient. We further construct a series of data subsets to evaluate the gradient estimation with smaller sample sizes, with 2 -1/2 , 2 -2/2 , . . . , 2 -k/2 of the entire dataset. For the neural network estimate of surrogate policy (NN-surrogate), we first fit a logistic regression model and a one-hidden-layer perceptron with ten ReLU activation units to estimate the surrogate policy. After this step, we compute the Euclidean distance between the "ground-truth" gradient and the gradient estimators that correspond to smaller sample sizes. Average Euclidean distances and standard deviations are computed over twenty trials. Results are illustrated in Figure 1 .

We observe that the MLIPS estimator gives much better gradient estimation than the original IPS estimator. In particular, the relative improvement is significant especially when the sample size is small. It is also interesting to see that the difference between the linear surrogate policy and the neural network surrogate policy is very small, possibly because the actual logging CRF policy is linear. On the Criteo dataset, in which the logging policy is unknown and possibly very complicated, we find that the neural network surrogate policy works better than the linear policy.

4.3. GENERALIZATION PERFORMANCE OF POLICY OPTIMIZATION:

To evaluate the effectiveness of our method on policy optimization, we train logistic regression policies with IPS, POEM, Norm-POEM objective functions, and the IPS and POEM versions with maximum likelihood surrogate policies (MLIPS and MLPOEM). As mentioned before, we use both the logistic regression model and the one-hidden-layer perceptron model to fit the surrogate policies, which are respectively marked with "-Lin" and "-NN" suffixes in the names of the training methods. Results are summarized in Table 1 . The test set Hamming losses for all methods are averaged over ten runs. On each run, both MLIPS and MLPOEM consistently and significantly outperforms their corresponding original versions.

As a control, we study the scenario where the logging policy is not available. We train the policies using IPS while treating the logging policy to be uniform. The performance of such a variant of IPS (the last row in the table with algorithm name "IPS-Uniform") is significantly worse than our method, which also does not require knowing the logging policy. Notably, when compared against (Norm-)POEM, the state-of-the-art algorithm on these datasets, our MLPOEM algorithm can augment the generalization performance on most datasets. This indicates that our surrogate policy technique provides a complementary mean squared error reduction effect for existing methods in this field. Finally, it is worth noting that the methods with neural network surrogate polices and linear policies are not too much different in terms of performance on these datasets, possibly because the logging policies used to generate these datasets are linear. We also evaluate the performance of our method on the preprocessed data used in the NIPS 2017 Workshop Criteo ad placement challenge. Because there is no information about the logging policy used to generate the data, it is reasonable to use a complex universal function approximator to fit the surrogate policy. We implement a neural network model with 21 tanh activation units for both the surrogate policy and the target policy. Due to the massive size of this dataset and its high-dimensional and sparse feature representation, we implement the 2 -regularized IPS and MLIPS in C++ with multi-threading.

4.3.1. CRITEO AD PLACEMENT DATASET:

Both the maximum likelihood estimation and policy optimization are performed using the L-BFGS algorithm. We split the dataset into training (80%) and testing (20%) sets. The regularization parameter is chosen by five-fold cross-validation on the training set. Evaluation is performed by computing the inverse propensity weights as suggested by the NIPS challenge. In comparison with IPS, which obtains 0.556 on the training set and 0.551 on the testing set, our method obtains 0.586 on the training set and 0.572 on the testing set. An implementation of our method (0.576 on the training set and 0.568 on the testing set, which are evaluated on the hold out data for the competition) is also ranked among very top (prize winning teams) of the NIPS 2017 challenge leaderboard.

5. CONCLUSION:

We introduce a new but simple approach for mean squared error reduction in policy evaluation and optimization. Theoretical analysis illustrates that the proposed MLIPS estimator is asymptotically unbiased, and moreover, has a smaller mean squared error than the classical IPS estimator. Experimental results on several large-scale datasets also demonstrate the empirical effectiveness of the proposed estimator. Our technique can also be combined with existing approaches and further improves the performance.

where t = t ∞ . As defined in Condition 3.8, ∞ 0 t k df (t) goes to zero when n → ∞ for any k. Therefore, when n → ∞, from (A.6) we have

E[η(t )] = E E η(t ) E(t ) = O ζ DG • (ζ ST + 1) + ζ DH • ∞ 0 t 2 df (t) , (A.7)

which gives lim n→∞ E[η(t )] = 0. Thus, we have lim n→∞ [ V -V ] = 0, which means that the MLIPS estimator V is asymptotically unbiased.

Next, we proceed to prove the MSE reducing effect of V . For the mean squared error of the MLIPS estimator V , we have

E ( V -V ) 2 = E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) + η(t ) 2 = E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) 2 (i) + E E η 2 (t ) E(t ) (ii) + 2 • E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) • η(t ) (iii) , (A.8)

where for term (ii) we use the law of total expectation. In the sequel, we characterize terms (i)-(iii) respectively.

Term (i) in (A.8): Note that by Definition 3.2 we have

V -V = 1 n n i=1 D V (r i , a i , x i ; β * ), where D V (r, a, x; β) = π(a, x) µ(a, x; β) • r(a, x) -V.

We reformulate the first term on the right-hand side of (A.8) as

E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) 2 = E ( V -V ) 2 + E 1 n n i=1 Π(r i , a i , x i ; β * ) 2 -2/n 2 • E n i=1 D V (r i , a i , x i ; β * ) • n i=1 Π(r i , a i , x i ; β * ) .

(A.9) Then by the fact that E[S(a, x; β * )] = 0, for the second term on the right-hand side of (A.9) we have

E Π(r, a, x; β * ) = E D V (r, a, x; β * ) • S(a, x; β * ) • I -1 (β * ) • E S(a, x; β * ) = 0. (A.10) Meanwhile, we have E n i=1 D V (r i , a i , x i ; β * ) • n i=1 Π(r i , a i , x i ; β * ) = n i=1 E D V (r i , a i , x i ; β * ) • Π(r i , a i , x i ; β * ) + i =j E D V (r i , a i , x i ; β * ) • Π(r j , a j , x j ; β * ) = n • E D V (r, a, x; β * ) • Π(r, a, x; β * ) ,

(A.11) where the second equality follows from (A.10). Hence, we obtain from (A.9) and (A.11) that

E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) 2 (A.12) = E ( V -V ) 2 + 1/n • Var Π(r, x, a; β * ) -2/n 2 • n • E D V (r, a, x; β * ) • Π(r, a, x; β * ) .

Note that we have the following equality for the Fisher information matrix I(β * ),

E S(a, x; β * ) • S(a, x; β * ) = I(β * ) = -∂S(a, x; β * )/∂β. (A.13)

Then by the definition of Π(r, a, x; β * ) in (3.14), we have

E Π 2 (r, a, x; β * ) = E D V (r, a, x; β * ) • S(a, x; β * ) • I -1 (β * ) • E S(a, x; β * ) • S(a, x; β * ) • I -1 (β * ) • E D V (r, a, x; β * ) • S(a, x; β * ) ,

which by (A.13) and the definition of Π(r, a, x; β * ) implies

E Π 2 (r, a, x; β * ) = E D V (r, a, x; β * ) • S(a, x; β * ) • I -1 (β * ) • E D V (r, a, x; β * ) • S(a, x; β * ) = E D V (r, a, x; β * ) • Π(r, a, x; β * ) .

(A.14) Note that (A.14) implies for the third term on the right-hand side of (A.12), we have

E D V (r, a, x; β * ) • Π(r, a, x; β * ) = E Π 2 (r, a, x; β * ) = Var Π(r, x, a; β * ) ,

(A.15) where the second equality follows from (A.10). Plugging (A.15) into (A.12), we obtain

E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) 2 = E ( V -V ) 2 -1/n • Var Π(r, x, a; β * ) . (A.16)

Term (ii) in (A.8): By Condition 3.8 and the definition of η(t ) in (A.4), we have

E η 2 (t ) E(t ) = O ζ DG • t β • (ζ ST • t β + t SH ) + t 2 β • (t DH + ζ DH + t β • t DG ) 2 = O ζ DG • (ζ ST + 1) • t 2 + t 2 • (t 2 + t + ζ DH ) 2 , (A.17) where t = t ∞ . As defined in Condition 3.8, ∞ 0 t k df (t) is a decreasing function of k. Therefore, from (A.17) we have E E η 2 (t ) E(t ) = O ζ DG • (ζ ST + 1) + ζ DH 2 • ∞ 0 t 4 df (t) . (A.18)

Term (iii) in (A.8): By the law of total expectation, we have

E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) • η(t ) = E ( V -V ) • η(t ) -E E 1 n n i=1 Π(r i , a i , x i ; β * ) • η(t ) E(t ) . (A.19)

For the first term on the right-hand side of (A.19), by the Cauchy-Schwartz inequality for expectation, we have

E ( V -V ) • η(t ) ≤ E ( V -V ) 2 • E E η 2 (t ) E(t ) 1/2 (A.20) = E ( V -V ) 2 1/2 • O ζ DG • (ζ ST + 1) + ζ DH • ∞ 0 t 4 df (t) 1/2

, where the second equality follows from (A.18). Now we consider the second term on the right-hand side of (A.19). Note that by the definition of Π(r, a, x; β) in (A.3), we have

1 n n i=1 Π(r i , a i , x i ; β * ) = 1 n n i=1 E D V (r, a, x; β * ) • S(a, x; β * ) • I -1 (β * ) • S(a i , x i ; β * ) ≤ E D V (r, a, x; β * ) • S(a, x; β * ) • I -1 (β * ) • 1 n n i=1 S(a i , x i ; β * ) , (A.21)

where by (A.23) we have that, conditioning on the event E(t ) defined in (3.12),

1 n n i=1 S(a i , x i ; β * ) ≤ t SG .

Under Assumption 3.4, we prove in Lemma B.1 and (B.2) that

E D V (r, a, x; β * ) • S(a, x; β * ) = E ∂D V (r, a, x; β * ) ∂β = O(ζ DG ). (A.22)

Note that in the event E SG (t SG ) defined in (3.9), we have E[S(a, x; β * )] = 0. Hence, equivalently we have

E SG (t SG ) = 1 n n i=1 S(a i , x i ; β * ) ≤ t SG . (A.23)

Combining (A.4), (A.21), (A.22), (A.23), and Assumption 3.3, under Condition 3.8 we have

E 1 n n i=1 Π(r i , a i , x i ; β * ) • η(t ) E(t ) = O ζ DG • t SG • ζ DG • t β • (ζ ST • t β + t SH ) + t 2 β • (t β • t DG + t DH + ζ DH ) = O ζ 2 DG • (ζ ST + 1) • t 3 + ζ DG • t 3 • (t 2 + t + ζ DH ) , (A.24)

where t = t ∞ . By (A.24), using a similar argument to the one used to obtain (A.18), we have

E E 1 n n i=1 Π(r i , a i , x i ; β * ) • η(t ) E(t ) = O ζ 2 DG • (ζ ST + 1) + ζ DG • ζ DH • ∞ 0 t 3 df (t) . (A.25)

Thus, combining (A.20) and (A.25), for (A.19) we obtain

E ( V -V ) - 1 n n i=1 Π(r i , a i , x i ; β * ) • η(t ) = E ( V -V ) 2 1/2 • O ζ DG • (ζ ST + 1) + ζ DH • ∞ 0 t 4 df (t) 1/2 + O ζ 2 DG • (ζ ST + 1) + ζ DG • ζ DH • ∞ 0 t 3 df (t) . (A.26)

Note that term (ii) in (A.8), which is characterized by (A.18), is dominated by the last term on the right-hand side of (A.25), since ∞ 0 t k df (t) decreases along k under Condition 3.8. Plugging (A.16), (A.18), and (A.26) into (A.8), we obtain

E ( V -V ) 2 = E ( V -V ) 2 -1/n • Var Π(r, x, a; β * ) + E ( V -V ) 2 1/2 • O ζ DG • (ζ ST + 1) + ζ DH • ∞ 0 t 4 df (t) 1/2 + O ζ 2 DG • (ζ ST + 1) + ζ DG • ζ DH • ∞ 0 t 3 df (t) ,

which concludes the proof of Theorem 3.9.

B PROOF OF LEMMA A.1

Before proving the Lemma A.1, we first introduce the following lemma on the gradient of the deviation function D V (r, a, x; β). Lemma B.1. For the score and deviation functions defined in (3.3) and (3.4), we have On the other hand, we expand the above sum to obtain

E ∂D V (r, a, x; β * ) ∂β = -E D V (

1 n n i=1 S(a i , x i ; β) = 1 n n i=1 S(a, x; β * ) + 1 n n i=1 ∂S(a, x; β * ) ∂β • ( β -β * ) + 1 2n n i=1 ∂ 2 S(a, x; β S ) ∂β 2 ( β -β * , β -β * , •), (C.2)

where

β S = λ S β * + (1 -λ S ) β for some λ S ∈ [0, 1].

Then by the definition of ∆ S in (A.2), we combine (C.1) and (C.2) to obtain

0 = 1 n n i=1 S(a i , x i ; β * ) + E ∂S(a, x; β * ) ∂β • ( β -β * ) -∆ S ( β -β * ) + 1 2n n i=1 ∂ 2 S(a i , x i ; β S ) ∂β 2 ( β -β * , β -β * , •). (C.3) Since we have E ∂S(a, x; β * ) ∂β = -I(β * ),

which is invertible by Assumption 3.3, by rearranging the terms in (C.3) we obtain We denote by λ max (•) and λ min (•) the largest and the smallest eigenvalue of a matrix, respectively. Throughout this section, we assume that the following regularity condition holds.

β -β * = I -1 (β * ) • 1 n n i=1 S(a i , x i ; β * ) -∆ S ( β -β * ) + 1 2n n i=1 ∂ 2 S(a i , x i ; β S ) ∂β 2 ( β -β * , β -β * , •) ,

Assumption D.1. We assume that, for all i ∈ [m -1], β i is bounded by β i ≤ B. Also, we assume that r(a, x) is bounded for all a and x. Furthermore, recall that in (2.1) we have x ∼ ν, we assume that x is bounded by x ≤ X and for its covariance matrix

Σ = E x∼ν [xx ], we have λ max (Σ) = σ, λ min (Σ) = σ > 0. (D.2)

Then the score function S(a, x; β) ∈ R p(m-1) takes the form

S(a, x; β) =             exp(x β 1 ) m-1 l=1 exp(x β l ) + 1 • x -1(a = 1) • x exp(x β 2 ) m-1 l=1 exp(x β l ) + 1 • x -1(a = 2) • x . . . exp(x β m-1 ) m-1 l=1 exp(x β l ) + 1 • x -1(a = m -1) • x             , (D.3)

where 1(•) is the indicator function, while the Fisher information matrix I(β) ∈ R p(m-1)×p(m-1) is a block matrix whose (j, k)-th block, namely [I(β)] j,k , takes the form

[I(β)] j,k = E 1(j = k) - exp(x β j ) m-1 l=1 exp(x β l ) + 1 • exp(x β k ) m-1 l=1 exp(x β l ) + 1 • xx , (D.4) for j, k ∈ [m -1].

We give lower and upper bounds for eigenvalues of I(β * ) in the following lemma.

Lemma D.2 (Non-singular Fisher Information Matrix). Under Assumption D.1, the Fisher information matrix I(β) is non-singular. Furthermore, for the eigenvalues of I(β), we have

λ min (I(β)) ≥ 2e -4XB σ m 2 , λ max (I(β)) ≤ 4e 4XB σ m 2 . (D.5)

Proof. For the ease of notation, we let

EQUATION

Then, by (D.4), we have

v I(β)v = 1≤j,k≤m-1 v j [I(β)] j,k v k = E m-1 j=1 π j (v j x) 2 + m-1 j=1 π 2 j (v j x) 2 - 1≤j,k≤m-1 (π j v j x)(π k v k x) . (D.7) Note that m k=1 π k = 1, we have m-1 j=1 π j (v j x) 2 - 1≤j,k≤m-1 (π j v j x)(π k v k x) = 1≤j,k≤m-1 π j π k (v j x) 2 + π m m-1 j=1 π j (v j x) 2 - 1≤j,k≤m-1 (π j v j x)(π k v k x) = 1 2 1≤j,k≤m-1 (π j v j x -π k v k x) 2 + π m m-1 j=1 π j (v j x) 2 . (D.8)

Thus, we have

λ min I(β) = min v =1 v I(β)v = min v =1 E 1 2 1≤j,k≤m-1 (π j v j x -π k v k x) 2 + π m m-1 j=1 π j (v j x) 2 + m-1 j=1 π 2 j (v j x) 2 ≥ 2e -4XB m 2 min v =1 E m-1 j=1 (v j x) 2 = 2e -4XB m 2 λ min (Σ) = 2e -4XB σ m 2 , (D.9)

where the last two equalities are consequences of (D.6) and the Assumption D.1, respectively. This is saying that the Fisher information matrix I(β) is positive definite. For the largest eigenvalue of I(β),

we have

λ max I(β) = max v =1 E 1 2 1≤j,k≤m-1 (π j v j x -π k v k x) 2 + π m m-1 j=1 π j (v j x) 2 + m-1 j=1 π 2 j (v j x) 2 ≤ 4e 4XB m 2 max v =1 E m-1 j=1 (v j x) 2 = 4e 4XB σ m 2 ,

which, together with (D.9), concludes the proof.

Meanwhile, the deviation function D V (r, a, x; β) takes the form

D V (r, a, x; β) = π(a | x) • r(a, x) • m-1 l=1 exp(x β l ) + 1 exp(x β a ) -V. (D.10)

The gradient of the deviation function takes the form

∂D V (r, a, x; β) ∂β = π(a | x) • r(a, x) •            exp(x β 1 ) -1(a = 1) • l exp(x β l ) + 1 exp(x β a ) • x exp(x β 2 ) -1(a = 2) • l exp(x β l ) + 1 exp(x β a ) • x . . . exp(x β m-1 ) -1(a = m -1) • l exp(x β l ) + 1 exp(x β a ) • x            . (D.11)

The Hessian of the deviation function is a block matrix in R p(m-1)×p(m-1) , whose (j, k)-th block takes the form

∂ 2 D V (r, a, x; β) ∂β 2 j,k = xx • π(a | x) • r(a, x) (D.12) • 1(k = j) -1(k = a) exp x (β a -β j ) + 1(k = a = j) • l exp(x β l ) + 1 -1(a = j) • exp(x β k ) exp(x β a ) for j, k ∈ [m -1].

Note that by (D. ) where t is defined in Condition 3.12 and M is some constant that does not scale with n.

The subsequent lemmas establish the tail behaviors for the events defined in Definitions 3.5-3.7, which together yield a concrete form of the tail function f (t) defined in Condition 3.8. Lemma D.3 (Maximum Likelihood Estimation Error). Under the Assumption D.1, for the event E β (t β ) defined in (3.8), we have

P E β (t β ) ≥ 1 -C β • exp(d -nt 2 β ), where C β is a positive constant independent of n. Proof. Let n (β) be the negative log-likelihood function n (β) = -(1/n) • n i=1 log µ(a i , x i ; β),

where µ(a, x; β) is defined in (D.1). By Lemma D.2, we have λ min ≥ 2e -4XB σ/m 2 , which gives

P λ min ∇ 2 n (β * ) ≥ e -4XB σ m 2 ≥P λ min ∇ 2 n (β * ) ≥ 1 - t β 2M • 2e -4XB σ m 2 ≥P λ min ∇ 2 n (β * ) -λ min I(β * ) ≤ e -4XB σ M m 2 • t β ≥P ∇ 2 n (β * ) -I(β * ) ≤ e -4XB σ M m 2 • t β , (D.14)

where M is defined in (D.13). Then note that ∂ 2 log µ(a i , x i ; β * )/∂β 2 -I(β * ) ≤ 8e 4XB σ/m 2 and I(β * ) 2 ≤ X 2 e 4XB σm, by matrix Bernstein inequality (see, for example, Tropp (2012); Vershynin ( 2010)), we have In the sequel, we use (D.13) and the tail function in (D.21) to characterize the reduction of the mean squared error induced by the multinomial logistic regression model. First, let t 0 = (T + 1) d/n with some constant T > 0, we have the following bound on the tail probability of t based on (D.21), P(t > t 0 ) ≤ f (t 0 ) ≤ 6C • e -T d .

EQUATION

(D.22) Then recall that in Theorem 3.9 we have

ξ(n) = E ( V -V ) 2 1/2 • O ∞ 0 t 4 df (t) 1/2 + O ∞ 0 t 3 df (t) ,

where by (D.22), we have (D.23) 

t0 0 t 3 df (t) = E[t 3 | t ≤ t 0 ] ≤ (T + 1) 3 • (d/n) 3/2 = O (d/n) 3/2 ,

:



Figures and Tables:

.2). Recall that ζ DG , ζ ST , and ζ DH are defined in Assumption 3.4. Since ζ DG , ζ ST , and ζ DH are population quantities, they do not scale with the sample size n.

Figure 1: Log MSE of estimations for offpolicy gradients made by IPS (logging policy), MLIPS (linear surrogate) and NN-fitted MLIPS (NN-surrogate) for logistic regression model on the LYRL dataset in Swaminathan & Joachims (2015a).

which concludes the proof of Lemma A.2.D APPLICATION TO MULTINOMIAL LOGISTIC REGRESSIONIn this section, we consider the setting where the logging distribution µ(a | x; β) is parametrized by the multinomial logistic regression model. We assume that x ∈ R p and a ∈[m]. Let β = (β 1 , . . . , β m-1 , 0 ) , where β 1 , . . . , β m-1 ∈ R p .Thus, the dimension of the parameter β is d = p(m -1). The logging distribution µ(a | x; β) is parametrized by µ(a | x; β) = exp(x β a )

3)-(D.4) and (D.11) -(D.12) for the population quantities, which do not scale with n, in Assumptions 3.3-3.4 are all bounded under Assumption D.1. Hence, in the multinomial logistic regression model defined in (D.1) with bounded x and β as stated in Assumption D.1, when d is fixed, we have ζ DG = ζ DH = ζ ST = 1, and t ≤ M, (D.13

D.15)    where the second inequality holds for a constant C β when n sufficiently large. Combining (D.14) and (D.15), we know that n (β) is e -4XB σ/m 2 -strongly convex with at least probability 1 -C β exp(dnt 2 β ). The rest of the proof considers the case where the e -4XB σ/m 2 -strong convexity holds for n (β), which means that we haven ( β) ≥ n (β * ) + ∇ β n (β * ) ( β -β * ) + e -4XB σ 2m 2 • β -β * 2 . (D.16)By definition of MLE, β is the minimizer for n (β), which means n (β * ) ≥ n ( β). Therefore, by Cauchy-Schwarz inequality, we havee -4XB σ 2m 2 • β -β * 2 ≤ ∇ β n (β * ) (β * -β) ≤ ∇ β n (β * ) • β -β * , which gives P β -β * ≥ t β ≤ P ∇ β n (β * ) ≥ e -4XB σ 2m 2 • t β .(D.17)Note that E[S(a, x; β * )] = 0, E[S(a, x; β * )S(a, x; β * ) ] = I(β * ) and ∇ β n (β * ) = (1/n) • n i=1 S(a i , x i ; β * ), by Bernstein's inequality (see, for example, Tropp (2012)), we haveP w ∇ β n (β * ) ≥ e -4XB σ 2m 2 • t β ≤ exp -nt 2 β [8e 8XB σ/m 2 + 2X(1 + e 2XB )e 4XB t β /3]e 4XB σ -2 m 2 ≤ C β exp(-nt 2 β ), (D.18)for any w such that w = 1, where the second inequality holds for a constant C β when n is large enough. Let G d = {w ∈ R d : w = 1}, by taking a union bound over w ∈ G d in (D.18), we haveP ∇ β n (β * ) ≥ e -4XBσ 2m 2 • t β =P sup w∈G d w ∇ β n (β * ) ≥ t β ≤ C β exp(d -nt 2 β ). (D.19) Plugging (D.19) into (D.17

) and recall that (D.16) holds with at least a probability of 1 -C β exp(dnt 2 β ), we haveP(E β (t β )) ≤ 1 -C β exp(d -nt 2 β ) • 1 -C β exp(d -nt 2 β ) ≤ 1 -(C β + C β ) exp(d -nt 2 β ), which concludes the proof with C β = C β + C β .Next, we state two Lemmas on the concentration of score and deviation. The proofs for them are quite standard in matrix concentration theories.

Lemma D.4 (Concentration of Score). Under the Assumption D.1, for the logistic regression model in (D.1), with the event E SG (t SG ), E SH (t SH ) and E ST (t ST ) defined in Definition 3.6, we haveP E SG (t SG ) ≥ 1 -C SG • exp(d -nt 2 SG ), P E SH (t SH ) ≥ 1 -C SH • exp(d -nt 2 SH ) and P E ST (t ST ) ≥ 1 -C SG • exp(d -nt 2 ST ), where C SG , C SH , and C ST are positive constants independent of n.Proof. Following the arguments made in (D.15) and (D.19), the exponentially decaying tails are immediate.Lemma D.5 (Concentration of Deviation). Suppose the Assumption D.1 holds and r(a, x) ≤ R for all a and x. Then, for the logistic regression model (D.1), with the event E DG (t DG ) and E DH (t DH ) defined in 3.7, we haveP E DG (t DG ) ≥ 1 -C DG • exp(d -nt 2 DG ), P E DH (t DH ) ≥ 1 -C DH • exp(d -nt 2 DH ),(D.20) where C DG and C DH are positive constants independent of n.Proof. Recall that we have π i ≥ e -2XB /m when the Assumption D.1 holds. We have∂D V (r, a, x; β) ∂β ≤ RX (m -2)e 2XB + me 2XB ] = 2e 2XB RX(m -1),and, by similar arguments in the proof of Lemma D.2, we haveE ∂D V (r, a, x; β) ∂β • ∂D V (r, a, x; β4XB R 2 σm 2 .Then, the first inequality in (D.20) follows by similar arguments as in (D.17)-(D.18). Next, again by similar arguments in the proof of Lemma D.2, we also haveE ∂ 2 D V (r, a, x; β) ∂β 2 ≤ e 2XB Rσ(m + 1)andE ∂ 2 D V (r, a, x; β) ∂β 2 2 ≤ e 2XB R 2 X 2 σm(m + 1),Then, similar as (D.15), the second inequality in (D.20) follows by matrix Bernstein inequality. Recall the event E(t ) with t = t ∞ is defined in Condition 3.8. By Lemmas D.3-D.5, the tail function f (t) takes the form f (t) ≤ 6C • exp(d -nt 2 ), (D.21) where C = max{C β , C SG , C SH , C DG , C DH , C DT } > 0.

Evaluations of the Hamming losses for policy optimizations performed by importance weighed pol-

Table content: <table><tr><td colspan="2">icy gradient estimators and their ML-variants on the</td></tr><tr><td colspan="2">datasets of Swaminathan &amp; Joachims (2015a). Eval-</td></tr><tr><td colspan="2">uations of Norm-POEM are also included as general</td></tr><tr><td colspan="2">benchmarks. We include extra results for this experi-</td></tr><tr><td colspan="2">ment in Appendix E</td></tr><tr><td>Dataset/Alg.</td><td>Scene Yeast TMC LYRL</td></tr><tr><td>IPS</td><td>1.342 4.571 3.023 1.108</td></tr><tr><td>POEM</td><td>1.143 4.549 2.522 0.981</td></tr><tr><td>Norm-POEM</td><td>1.045 3.876 2.072 0.799</td></tr><tr><td>MLIPS-Lin</td><td>1.086 3.778 2.018 1.025</td></tr><tr><td>MLIPS-NN</td><td>1.086 3.630 2.019 0.930</td></tr><tr><td colspan="2">MLPOEM-Lin 1.086 3.894 2.010 0.949</td></tr><tr><td colspan="2">MLPOEM-NN 1.086 3.477 2.000 0.904</td></tr><tr><td>IPS-Uniform</td><td>1.086 5.893 6.174 1.463</td></tr></table>

Peer review (iclr2019):
 This work is concerned with the problem of batch contextual bandits, in which a target contextual bandit policy is optimized on the data generated by a different logging policy. The main problem is to come up with a low-variance low-bias estimator for the value of the target policy. Many of the known techniques are based on an unbiased estimator known as inverse propensity scoring (IPS), which uses the distribution over actions of the logging policy, conditioned on the observed contexts. However, IPS suffers from large variance. The paper*s idea is to do a maximum likelihood fit of a simple surrogate policy to the logged data, and then use the conditional distribution over actions of the surrogate policy to compute inverse propensity scores. The theoretical results show that the bias of this estimator vanishes asymptotically, whereas the variance is smaller than IPS. Experiments using known/unknown logging policies on artificial/real-world bandit data show that the IPS scores computed with the proposed technique are empirically better than those computed directly using the logging policy. Moreover, the advantage increases when the distribution extracted from the surrogate policy is used to compute more sophisticated estimators than IPS. The off-policy evaluation in contextual bandits is an important problem, and this paper appears to make some progress. However, the theoretical analysis is a bit disappointing, as it does not shed much light on the reasons why using a surrogate policy should help. Some additional discussion would add value to the paper. The result about the decrease in variance depends on assumptions that are not clearly justified, and is expressed in terms of abstract quantities that hard to connect to concrete scenarios. In the end, one does not get many new insights from the theory. In Assumptions 3.3-3-4, what is the variable w.r.t the asymptotic notations are understood? By that I mean, the variable n such that f(n) = O(g(n)). The experiments are competent and quite elaborated. However, the statistical significance of the improvements in Table 1 is unclear. The evaluation criterion for the Criteo experiment is unclear. As a consequence it is hard to appreciate the significance of the improvements in this case.