The Self-Normalized Estimator for Counterfactual
Learning

Thorsten Joachims
Department of Computer Science
Cornell University
tj@cs.cornell.edu

Adith Swaminathan
Department of Computer Science
Cornell University
adith@cs.cornell.edu

Abstract
This paper identifies a severe problem of the counterfactual risk estimator typically used in batch learning from logged bandit feedback (BLBF), and proposes
the use of an alternative estimator that avoids this problem. In the BLBF setting,the learner does not receive full-information feedback like in supervised learning, but observes feedback only for the actions taken by a historical policy. This
makes BLBF algorithms particularly attractive for training online systems (e.g., adplacement, web search, recommendation) using their historical logs. The Counterfactual Risk Minimization (CRM) principle [1] offers a general recipe for designing BLBF algorithms. It requires a counterfactual risk estimator, and virtually
all existing works on BLBF have focused on a particular unbiased estimator. We
show that this conventional estimator suffers from a propensity overfitting problem
when used for learning over complex hypothesis spaces. We propose to replace
the risk estimator with a self-normalized estimator, showing that it neatly avoids
this problem. This naturally gives rise to a new learning algorithm – Normalized
Policy Optimizer for Exponential Models (Norm-POEM) – for structured output
prediction using linear rules. We evaluate the empirical effectiveness of NormPOEM on several multi-label classification problems, finding that it consistently
outperforms the conventional estimator.

1

Introduction

Most interactive systems (e.g. search engines, recommender systems, ad platforms) record large
quantities of log data which contain valuable information about the system’s performance and user
experience. For example, the logs of an ad-placement system record which ad was presented in agiven context and whether the user clicked on it. While these logs contain information that should
inform the design of future systems, the log entries do not provide supervised training data in theconventional sense. This prevents us from directly employing supervised learning algorithms to
improve these systems. In particular, each entry only provides bandit feedback since the loss/reward
is only observed for the particular action chosen by the system (e.g. the presented ad) but not for
all the other actions the system could have taken. Moreover, the log entries are biased since actions
that are systematically favored by the system will by over-represented in the logs.
Learning from historical logs data can be formalized as batch learning from logged bandit feedback(BLBF) [2, 1]. Unlike the well-studied problem of online learning from bandit feedback [3], thissetting does not require the learner to have interactive control over the system. Learning in sucha setting is closely related to the problem of off-policy evaluation in reinforcement learning [4] –we would like to know how well a new system (policy) would perform if it had been used in thepast. This motivates the use of counterfactual estimators [5]. Following an approach analogous
to Empirical Risk Minimization (ERM), it was shown that such estimators can be used to design
learning algorithms for batch learning from logged bandit feedback [6, 5, 1].
1However the conventional counterfactual risk estimator used in prior works on BLBF exhibits severe
anomalies that can lead to degeneracies when used in ERM. In particular, the estimator exhibits a
new form of Propensity Overfitting that causes severely biased risk estimates for the ERM minimizer. By introducing multiplicative control variates, we propose to replace this risk estimator witha Self-Normalized Risk Estimator that provably avoids these degeneracies. An extensive empiricalevaluation confirms that the desirable theoretical properties of the Self-Normalized Risk Estimatortranslate into improved generalization performance and robustness.

2

Related Work

Batch learning from logged bandit feedback is an instance of causal inference. Classic inferencetechniques like propensity score matching [7] are, hence, immediately relevant. BLBF is closely
related to the problem of learning under covariate shift (also called domain adaptation or sample
bias correction) [8] as well as off-policy evaluation in reinforcement learning [4]. Lower bounds fordomain adaptation [8] and impossibility results for off-policy evaluation [9], hence, also apply topropensity score matching [7], costing [10] and other importance sampling approaches to BLBF.
Several counterfactual estimators have been developed for off-policy evaluation [11, 6, 5]. All theseestimators are instances of importance sampling for Monte Carlo approximation and can be traced
back to What-If simulations [12]. Learning (upper) bounds have been developed recently [13, 1, 14]that show that these estimators can work for BLBF. We additionally show that importance sampling
can overfit in hitherto unforeseen ways with the capacity of the hypothesis space during learning.
We call this new kind of overfitting Propensity Overfitting.
Classic variance reduction techniques for importance sampling are also useful for counterfactual
evaluation and learning. For instance, importance weights can be “clipped” [15] to trade-off bias
against variance in the estimators [5]. Additive control variates give rise to regression estimators[16] and doubly robust estimators [6]. Our proposal uses multiplicative control variates. These
are widely used in financial applications (see [17] and references therein) and policy iteration forreinforcement learning (e.g. [18]). In particular, we study the self-normalized estimator [12] which
is superior to the vanilla estimator when fluctuations in the weights dominate the variance [19]. We
additionally show that the self-normalized estimator neatly addresses propensity overfitting.

3

Batch learning from logged bandit feedback

Following [1], we focus on the stochastic, cardinal, contextual bandit setting and recap the essenceof the CRM principle. The inputs of a structured prediction problem x ∈ X are drawn i.i.d. from afixed but unknown distribution Pr(X ). The outputs are denoted by y ∈ Y. The hypothesis space H
contains stochastic hypotheses h(Y | x) that define a probability distribution over Y. A hypothesish ∈ H makes predictions by sampling from the conditional distribution y ∼ h(Y | x). This definitionof H also captures deterministic hypotheses. For notational convenience, we denote the probability
distribution h(Y | x) by h(x), and the probability assigned by h(x) to y as h(y | x). We use (x, y) ∼ hto refer to samples of x ∼ Pr(X ), y ∼ h(x), and when clear from the context, we will drop (x, y).
Bandit feedback means we only observe the feedback δ(x, y) for the specific y that was predicted,
but not for any of the other possible predictions Y \ {y}. The feedback is just a number, called theloss δ : X × Y 7→ R. Smaller numbers are desirable. In general, the loss is the (noisy) realization ofa stochastic random variable. The following exposition can be readily extended to the general caseby setting δ(x, y) = E [δ | x, y]. The expected loss – called risk – of a hypothesis R(h) is
R(h) = Ex∼Pr(X ) Ey∼h(x) [δ(x, y)] = Eh [δ(x, y)] .

(1)

The aim of learning is to find a hypothesis h ∈ H that has minimum risk.
Counterfactual Estimators. We wish to use the logs of a historical system to perform learning. To
ensure that learning will not be impossible [9], we assume the historical algorithm whose predictions
we record in our logged data is a stationary policy h0 (x) with full support over Y. For a new
hypothesis h 6= h0 , we cannot use the empirical risk estimator used in supervised learning [20] to
directly approximate R(h), because the data contains samples drawn from h0 while the risk from
Equation (1) requires samples from h.
2Importance sampling fixes this distribution mismatch,h(y | x)R(h) = Eh [δ(x, y)] = Eh0 δ(x, y).
h0 (y | x)
So, with data collected from the historical system
D = {(x1 , y1 , δ1 , p1 ), . . . , (xn , yn , δn , pn )},where (xi , yi ) ∼ h0 , δi ≡ δ(xi , yi ) and pi ≡ h0 (yi | xi ), we can derive an unbiased estimate ofR(h) via Monte Carlo approximation,n
1 X h(yi | xi )R̂(h) =
δi
.
(2)
n i=1
pi
This classic inverse propensity estimator [7] has unbounded variance: pi ' 0 in D can cause R̂(h)to be arbitrarily far away from the true risk R(h). To remedy this problem, several thresholding
schemes have been proposed and studied in the literature [15, 8, 5, 11]. The straightforward option
is to cap the propensity weights [15, 1], i.e. pick M > 1 and setn1Xh(yi | xi )MR̂ (h) =δi min M,
.
n i=1
pi
Smaller values of M reduce the variance of R̂M (h) but induce a larger bias.
Counterfactual Risk Minimization. Importance sampling also introduces variance in R̂M (h)through the variability of h(ypii|xi ) . This variance can be drastically different for different h ∈ H. The
CRM principle is derived from a generalization error bound that reasons about this variance using
an empirical Bernsteinargumentno [1, 13]. Let δ(·, ·) ∈ [−1, 0] and consider the random variableh(y|x)
uh = δ(x, y) min M, h0 (y|x) . Note that D contains n i.i.d. observations uh i .
Theorem 1. Denote the empirical variance of uh by V ˆar(uh ). With probability at least 1−γ in the
random vector (xi , yi ) ∼ h0 , for a stochastic hypothesis space H with capacity C(H) and n ≥ 16,s
15 log( 10C(H)18V ˆar(uh ) log( 10C(H)
)
)
γ
γ
M
+M
.
∀h ∈ H : R(h) ≤ R̂ (h) +nn−1
Proof. Refer Theorem 1 of [1] and the proof of Theorem 6 of [13].
Following Structural Risk Minimization [20], this bound motivates the CRM principle for designingalgorithms for BLBF. A learning algorithm should jointly optimize the estimate R̂M (h) as well as
its empirical standard deviation, where the latter serves as a data-dependent regularizer.


s

ˆ
V ar(uh ) ĥCRM = argmin R̂M (h) + λ
.
(3)

n
h∈H 
M > 1 and λ ≥ 0 are regularization hyper-parameters.

4

The Propensity Overfitting Problem

The CRM objective in Equation (3) penalizes those h ∈ H that are “far” from the logging policyh0 (as measured by their empirical variance V ˆar(uh )). This can be intuitively understood as asafeguard against overfitting. However, overfitting in BLBF is more nuanced than in conventional
supervised learning. In particular, the unbiased risk estimator of Equation (2) has two anomalies.
Even if δ(·, ·) ∈ [5, 4], the value of R̂(h) estimated on a finite sample need not lie in that range.
Furthermore, if δ(·, ·) is translated by a constant δ(·, ·) + C, R(h) becomes R(h) + C by linearity of
expectation – but the unbiased estimator on a finite sample need not equal R̂(h) + C. In short, thisrisk estimator is not equivariant [19]. The various thresholding schemes for importance sampling
only exacerbate this effect. These anomalies leave us vulnerable to a peculiar kind of overfitting, as
we see in the following example.
3

Example 1. For the input space of integers X = {1..k} and the output space Y = {1..k}, define−2 if y = x
δ(x, y) =−1 otherwise.
The hypothesis space H is the set of all deterministic functions f : X 7→ Y.

1 if f (x) = y
hf (y|x) =0 otherwise.
Data is drawn uniformly, x ∼ U(X ) and h0 (Y|x) = U(Y) for all x. The hypothesis h∗ withminimum true risk is h∗f with f ∗ (x) = x, which has risk R(h∗ ) = −2.
When drawing a training sample D = ((x1 , y1 , δ1 , p1 ), ..., (xn , yn , δn , pn )), let us first consider the
special case where all xi in the sample are distinct. This is quite likely if n is small relative to k. In
this case H contains a hypothesis hoverf it , which assigns f (xi ) = yi for all i. This hypothesis has
the following empirical risk as estimated by Equation (2):nnn
1 X hoverf it (yi | xi )
1
1
1X
1X
R̂(hoverf it ) =
δi
δi
−1
=
≤
= −k.
n i=1
pi
n i=1 1/kn i=1
1/k
Clearly this risk estimate shows severe overfitting, since it can be arbitrarily lower than the true riskR(h∗ ) = −2 of the best hypothesis h∗ with appropriately chosen k (or, more generally, the choiceof h0 ). This is in stark contrast to overfitting in full-information supervised learning, where at least
the overfitted risk is bounded by the lower range of the loss function. Note that the empirical riskR̂(h∗ ) of h∗ concentrates around −2. ERM will, hence, almost always select hoverf it over h∗ .
Even if we are not in the special case of having a sample with all distinct xi , this type of overfitting
still exists. In particular, if there are only l distinct xi in D, then there still exists a hoverf it withR̂(hoverf it ) ≤ −k nl . Finally, note that this type of overfitting behavior is not an artifact of thisexample. Section 7 shows that this is ubiquitous in all the datasets we explored.
Maybe this problem could be avoided by transforming the loss? For example, let’s translate theloss by adding 2 to δ so that now all loss values become non-negative. This results in the new loss
function δ 0 (x, y) taking values 0 and 1. In conventional supervised learning an additive translationof the loss does not change the empirical risk minimizer. Suppose we draw a sample D in which not
all possible values y for xi are observed for all xi in the sample (again, such a sample is likely forsufficiently large k). Now there are many hypotheses hoverf it0 that predict one of the unobserved yfor each xi , basically avoiding the training data.
nn0
1 X hoverf it0 (yi | xi )
1X
δi
δi
= 0.
R̂(hoverf it0 ) =
=
n i=1
pi
n i=1 1/k
Again we are faced with overfitting, since many overfit hypotheses are indistinguishable from thetrue risk minimizer h∗ with true risk R(h∗ ) = 0 and empirical risk R̂(h∗ ) = 0.
These examples indicate that this overfitting occurs regardless of how the loss is transformed. Intuitively, this type of overfitting occurs since the risk estimate according to Equation (2) can be minimized not only by putting large probability mass h(y | x) on the examples with low loss δ(x, y),but by maximizing (for negative losses) or minimizing (for positive losses) the sum of the weightsn
1 X h(yi | xi ).
(4)Ŝ(h) =
n i=1
pi
For this reason, we call this type of overfitting Propensity Overfitting. This is in stark contrast to
overfitting in supervised learning, which we call Loss Overfitting. Intuitively, Loss Overfitting occurs because the capacity of H fits spurious patterns of low δ(x, y) in the data. In Propensity Overfitting, the capacity in H allows overfitting of the propensity weights pi – for positive δ, hypotheses
that avoid D are selected; for negative δ, hypotheses that overrepresent D are selected.
The variance regularization of CRM combats both Loss Overfitting and Propensity Overfitting by
optimizing a more informed generalization error bound. However the empirical variance estimate
is also affected by Propensity Overfitting – especially for positive losses. Can we avoid Propensity
Overfitting more directly?
4

5

Control Variates and the Self-Normalized Estimator

To avoid Propensity Overfitting, we must first detect when and where it is occurring. For this,we draw on diagnostic tools used in importance sampling. Note that for any h ∈ H, the sumof propensity weights Ŝ(h) from Equation (4) always has expected value 1 under the conditions
required for the unbiased estimator of Equation (2).
n Z
n Z
h
i
1X
h(yi | xi )1X
E Ŝ(h) =1 Pr(xi )dxi = 1.
(5)h0 (yi | xi ) Pr(xi )dyi dxi =n i=1
h0 (yi | xi )n i=1This means that we can identify hypotheses that suffer from Propensity Overfitting based on how far
Ŝ(h) deviates from its expected value of 1. Since hh(y|x)
is likely correlated with δ(x, y) hh(y|x),a0 (y|x)0 (y|x)large deviation in Ŝ(h) suggests a large deviation in R̂(h) and consequently a bad risk estimate.
hiHow can we use the knowledge that ∀h ∈ H : E Ŝ(h) = 1 to avoid degenerate risk estimates ina principled way? While one could use concentration inequalities to explicitly detect and eliminate
overfit hypotheses based on Ŝ(h), we use control variates to derive an improved risk estimator that
directly incorporates this knowledge.
Control Variates. Control variates – random variables whose expectation is known – are a classic
tool used to reduce the variance of Monte Carlo approximations [21]. Let V (X) be a control variate
with known expectation EX [V (X)] = v 6= 0, and let EX [W (X)] be an expectation that we would
like to estimate based on independent samples of X. Employing V (X) as a multiplicative control(X)]variate, we can write EX [W (X)] = E[WE[V (X)] v. This motivates the ratio estimatorPn
W (Xi )v,
(6)Ŵ SN = Pi=1n
i=1 V (Xi )which is called the Self-Normalized estimator in the importance sampling literature [12, 22, 23].
This estimator has substantially lower variance if W (X) and V (X) are correlated.
Self-Normalized Risk Estimator. Let us use S(h) as a control variate for R(h), yieldingPnh(yi |xi )i=1 δip
SNR̂ (h) = Pn h(y |xi ) .
i

i=1

i

(7)

pi

Hesterberg reports that this estimator tends be more accurate than the unbiased estimator of Equation (2) when fluctuations in the sampling weights dominate the fluctuations in δ(x, y) [19].
Observe that the estimate is just a convex combination of the δi observed in the sample. If δ(·, ·)is now translated by a constant δ(·, ·) + C, both the true risk R(h) and the finite sample estimate
R̂SN (h) get shifted by C. Hence R̂SN (h) is equivariant, unlike R̂(h) [19]. Moreover, R̂SN (h) isalways bounded within the range of δ. So, the overfitted risk due to ERM will now be bounded by
the lower range of the loss, analogous to full-information supervised learning.
hiFinally, while the self-normalized risk estimator is not unbiased (E R̂(h)6= ER(h)in general), itŜ(h)[Ŝ(h)]is strongly consistent and approaches the desired expectation when n is large.
i.i.d.

Theorem 2. Let D be drawn (xi , yi ) ∼ h0 , from a h0 that has full support over Y. Then,∀h ∈ H :Pr( lim R̂SN (h) = R(h)) = 1.
n→∞Proof. The numerator of R̂SN (h) in (7) are i.i.d. observations with mean R(h). Strong law
Pnof large numbers gives Pr(limn→∞ n1 i=1 δi h(ypii|xi ) = R(h)) = 1. Similarly, the denominator has i.i.d. observations with mean 1. So, the strong law of large numbers implies
Pn
Pr(limn→∞ n1 i=1 h(ypii|xi ) = 1) = 1. Hence, Pr(limn→∞ R̂SN (h) = R(h)) = 1.
In summary, the self-normalized risk estimator R̂SN (h) in Equation (7) resolves all the problems of
the unbiased estimator R̂(h) from Equation (2) identified in Section 4.
5

6

Learning Method: Norm-POEM

We now derive a learning algorithm, called Norm-POEM, for structured output prediction. The
algorithm is analogous to POEM [1] in its choice of hypothesis space and its application of the
CRM principle, but it replaces the conventional estimator (2) with the self-normalized estimator (7).
Hypothesis Space. Following [1, 24], Norm-POEM learns stochastic linear rules hw ∈ Hlinparametrized by w that operate on a d−dimensional joint feature map φ(x, y).
hw (y | x) = exp(w · φ(x, y))/Z(x).
P
0
Z(x) = y0 ∈Y exp(w · φ(x, y )) is the partition function.
Variance Estimator. In order to instantiate the CRM objective from Equation (3), we need anempirical variance estimate V ˆar(R̂SN (h)) for the self-normalized risk estimator. Following [23,Section 4.3], we use an approximate variance estimate for the ratio estimator of Equation (6). Using
the Normal approximation argument [21, Equation 9.9],PnSN(h))2 ( h(ypii|xi ) )2
i=1 (δi − R̂SNˆV ar(R̂ (h)) =.
(8)Pn( i=1 h(ypii|xi ) )2
Using the delta method to approximate the variance [22] yields the same formula. To invoke asymptotic normality of the estimator (and indeed, for reliable importance sampling estimates) we require
the true variance of the self-normalized estimator V ar(R̂SN (h)) to exist. We can guarantee this by
thresholding the importance weights, analogous to R̂M (h).
The benefits of the self-normalized estimator come at a computational cost. The risk estimatorof POEM had a simpler variance estimate which could be approximated by Taylor expansion andoptimized using stochastic gradient descent. The variance of Equation (8) does not admit stochastic
optimization. Surprisingly, in our experiments in Section 7 we find that the improved robustness ofNorm-POEM permits fast convergence during training even without stochastic optimization.
Training Objective of Norm-POEM. The objective is now derived by substituting the selfnormalized risk estimator of Equation (7) and its sample variance estimate from Equation (8) into
the CRM objective (3) for the hypothesis space Hlin . By design, hw lies in the exponential familyof distributions. So, the gradient of the resulting objective can be tractably computed whenever thepartition functions Z(xi ) are tractable. Doing so yields a non-convex objective in the parameters
w which we optimize using L-BFGS. The choice of L-BFGS for non-convex and non-smooth optimization is well supported [25, 26]. Analogous to POEM, the hyper-parameters M (clipping toprevent unbounded variance) and λ (strength of variance regularization) can be calibrated via counterfactual evaluation on a held out validation set. In summary, the per-iteration cost of optimizing theNorm-POEM objective has the same complexity as the per-iteration cost of POEM with L-BFGS. It
requires the same set of hyper-parameters. And it can be done tractably whenever the corresponding supervised CRF can be learnt efficiently. Software implementing Norm-POEM is available at
http://www.cs.cornell.edu/∼adith/POEM.

7

Experiments

We will now empirically verify if the self-normalized estimator as used in Norm-POEM can indeed
guard against propensity overfitting and attain robust generalization performance. We follow theSupervised 7→ Bandit methodology [2, 1] to test the limits of counterfactual learning in a wellcontrolled environment. As in prior work [1], the experiment setup uses supervised datasets for
multi-label classification from the LibSVM repository. In these datasets, the inputs x ∈ Rp . The
predictions y ∈ {0, 1}q are bitvectors indicating the labels assigned to x. The datasets have a rangeof features p, labels q and instances n:
Name
Scene
Yeast
TMC
LYRL

p(# features)
294
103
30438
47236

q(# labels)
6
14
22
4

6

ntrain
1211
1500
21519
23149

ntest
1196
917
7077
781265

POEM uses the CRM principle instantiated with the unbiased estimator while Norm-POEM uses theself-normalized estimator. Both use a hypothesis space isomorphic to a Conditional Random Field(CRF) [24]. We therefore report the performance of a full-information CRF (essentially, logistic
regression for each of the q labels independently) as a “skyline” for what we can possibly hope toreach by partial-information batch learning from logged bandit feedback. The joint feature map
φ(x, y) = x ⊗ y for all approaches. To simulate a bandit feedback dataset D, we use a CRF withdefault hyper-parameters trained on 5% of the supervised dataset as h0 , and replay the training data
4 times and collect sampled labels from h0 . This is inspired by the observation that supervisedlabels are typically hard to collect relative to bandit feedback. The BLBF algorithms only haveaccess to the Hamming loss ∆(y ∗ , y) between the supervised label y ∗ and the sampled label y for
input x. Generalization performance R is measured by the expected Hamming loss on the held-out
supervised test set. Lower is better. Hyper-parameters λ, M were calibrated as recommended andvalidated on a 25% hold-out of D – in summary, our experimental setup is identical to POEM [1].
We report performance of BLBF approaches without l2−regularization here; we observed NormPOEM dominated POEM even after l2−regularization. Since the choice of optimization method
could be a confounder, we use L-BFGS for all methods and experiments.
What is the generalization performance of Norm-POEM ? The key question is whether the appealing theoretical properties of the self-normalized estimator actually lead to better generalization
performance. In Table 1, we report the test set loss for Norm-POEM and POEM averaged over 10
runs. On each run, h0 has varying performance (trained on random 5% subsets) but Norm-POEM
consistently beats POEM.
Table 1: Test set Hamming loss averaged over 10 runs. Norm-POEM significantly outperforms
POEM on all four datasets (one-tailed paired difference t-test at significance level of 0.05).
R
h0
POEM
Norm-POEM
CRF

Scene
1.511
1.200
1.045
0.657

Yeast
5.577
4.520
3.876
2.830

TMC
3.442
2.152
2.072
1.187

LYRL
1.459
0.914
0.799
0.222

The plot below (Figure 1) shows how generalization performance improves with more training data
for a single run of the experiment on the Yeast dataset. We achieve this by varying the number oftimes we replay the training set to collect samples from h0 (ReplayCount). Norm-POEM consistently outperforms POEM for all training sample sizes.
h0
CRF
POEM
Norm-POEM

R

4

3.5

3

20

21

22

23

24
25
ReplayCount

26

27

28

Figure 1: Test set Hamming loss as n → ∞ on the Yeast dataset. All approaches will converge to
CRF performance in the limit, but the rate of convergence is slow since h0 is thin-tailed.

Does Norm-POEM avoid Propensity Overfitting? While the previous results indicate that
Norm-POEM achieves better performance, it remains to be verified that this improved performanceis indeed due to improved control over Propensity Overfitting. Table 2 (left) shows the average Ŝ(ĥ)
for the hypothesis ĥ selected by each approach. Indeed, Ŝ(ĥ) is close to its known expectation of
1 for Norm-POEM, while it is severely biased for POEM. Furthermore, the value of Ŝ(ĥ) depends
heavily on how the losses δ are translated for POEM, as predicted by theory. As anticipated byour earlier observation that the self-normalized estimator is equivariant, Norm-POEM is unaffectedby translations of δ. Table 2 (right) shows that the same is true for the prediction error on the test7

set. Norm-POEM is consistenly good while POEM fails catastrophically (for instance, on the TMC
dataset, POEM is worse than random guessing).
Table 2: Mean of the unclipped weights Ŝ(ĥ) (left) and test set Hamming loss R (right), averaged
over 10 runs. δ > 0 and δ < 0 indicate whether the loss was translated to be positive or negative.
POEM(δ > 0)
POEM(δ < 0)Norm-POEM(δ > 0)
Norm-POEM(δ < 0)

Scene
0.274
1.782
0.981
0.981

Ŝ(ĥ)
Yeast TMC
0.028 0.000
5.352 2.802
0.840 0.941
0.821 0.938

LYRL
0.175
1.230
0.945
0.945

Scene
2.059
1.200
1.058
1.045

R(ĥ)
Yeast
TMC
5.441 17.305
4.520
2.152
3.881
2.079
3.876
2.072

LYRL
2.399
0.914
0.799
0.799

Is CRM variance regularization still necessary? It may be possible that the improved selfnormalized estimator no longer requires variance regularization. The loss of the unregularized estimator is reported (Norm-IPS) in Table 3. We see that variance regularization still helps.
Table 3: Test set Hamming loss for Norm-POEM and the variance agnostic Norm-IPS averaged overthe same 10 runs as Table 1. On Scene, TMC and LYRL, Norm-POEM is significantly better thanNorm-IPS (one-tailed paired difference t-test at significance level of 0.05).
R
Norm-IPS
Norm-POEM

Scene
1.072
1.045

Yeast
3.905
3.876

TMC
3.609
2.072

LYRL
0.806
0.799

How computationally efficient is Norm-POEM ? The runtime of Norm-POEM is surprisingly
faster than POEM. Even though normalization increases the per-iteration computation cost, optimization tends to converge in fewer iterations than for POEM. We find that POEM picks a hypothesis with large kwk, attempting to assign a probability of 1 to all training points with negative losses.
However, Norm-POEM converges to a much shorter kwk. The loss of an instance relative to others
in a sample D governs how Norm-POEM tries to fit to it. This is another nice consequence of thefact that the overfitted risk of R̂SN (h) is bounded and small. Overall, the runtime of Norm-POEM
is on the same order of magnitude as those of a full-information CRF, and is competitive with theruntimes reported for POEM with stochastic optimization and early stopping [1], while providing
substantially better generalization performance.
Table 4: Time in seconds, averaged across validation runs. CRF is implemented by scikit-learn [27].
Time(s)POEM
Norm-POEM
CRF

Scene
78.69
7.28
4.94

Yeast
98.65
10.15
3.43

TMC
716.51227.8889.24

LYRL
617.30142.5072.34

We observe the same trends for Norm-POEM when different properties of h0 are varied (e.g.
stochasticity and quality), as reported for POEM [1].

8Conclusions

We identify the problem of propensity overfitting when using the conventional unbiased risk estimator for ERM in batch learning from bandit feedback. To remedy this problem, we propose the use ofa multiplicative control variate that leads to the self-normalized risk estimator. This provably avoids
the anomalies of the conventional estimator. Deriving a new learning algorithm called Norm-POEM
based on the CRM principle using the new estimator, we show that the improved estimator leads tosignificantly improved generalization performance.
Acknowledgement
This research was funded in part through NSF Awards IIS-1247637, IIS-1217686, IIS-1513692, the
JTCII Cornell-Technion Research Fund, and a gift from Bloomberg.
8References[1] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged
bandit feedback. In ICML, 2015.
[2] Alina Beygelzimer and John Langford. The offset tree for learning with partial labels. In KDD, pages
129–138, 2009.
[3] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press,
New York, NY, USA, 2006.
[4] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 1998.
[5] Léon Bottou, Jonas Peters, Joaquin Q. Candela, Denis X. Charles, Max Chickering, Elon Portugaly,
Dipankar Ray, Patrice Y. Simard, and Ed Snelson. Counterfactual reasoning and learning systems: theexample of computational advertising. Journal of Machine Learning Research, 14(1):3207–3260, 2013.
[6] Miroslav Dudı́k, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In ICML,
pages 1097–1104, 2011.
[7] P. Rosenbaum and D. Rubin. The central role of the propensity score in observational studies for causal
effects. Biometrika, 70(1):41–55, 1983.
[8] C. Cortes, Y. Mansour, and M. Mohri. Learning bounds for importance weighting. In NIPS, pages 442–
450, 2010.
[9] John Langford, Alexander Strehl, and Jennifer Wortman. Exploration scavenging. In ICML, pages 528–
535, 2008.
[10] Bianca Zadrozny, John Langford, and Naoki Abe. Cost-sensitive learning by cost-proportionate example
weighting. In ICDM, pages 435–, 2003.
[11] Alexander L. Strehl, John Langford, Lihong Li, and Sham Kakade. Learning from logged implicit exploration data. In NIPS, pages 2217–2225, 2010.
[12] H. F. Trotter and J. W. Tukey. Conditional monte carlo for normal samples. In Symposium on Monte
Carlo Methods, pages 64–79, 1956.
[13] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample-variance penalization.
In COLT, 2009.
[14] Philip S. Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-policy
evaluation. In AAAI, pages 3000–3006, 2015.
[15] Edward L. Ionides. Truncated importance sampling. Journal of Computational and Graphical Statistics,
17(2):295–311, 2008.
[16] Lihong Li, R. Munos, and C. Szepesvari. Toward minimax off-policy value estimation. In AISTATS, 2015.
[17] Phelim Boyle, Mark Broadie, and Paul Glasserman. Monte carlo methods for security pricing. Journal of
Economic Dynamics and Control, 21(89):1267–1321, 1997.
[18] John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust region policy
optimization. In ICML, pages 1889–1897, 2015.
[19] Tim Hesterberg. Weighted average importance sampling and defensive mixture distributions. Technometrics, 37:185–194, 1995.
[20] V. Vapnik. Statistical Learning Theory. Wiley, Chichester, GB, 1998.
[21] Art B. Owen. Monte Carlo theory, methods and examples. 2013.
[22] Augustine Kong. A note on importance sampling using standardized weights. Technical Report 348,
Department of Statistics, University of Chicago, 1992.
[23] R. Rubinstein and D. Kroese. Simulation and the Monte Carlo Method. Wiley, 2 edition, 2008.
[24] John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML, pages 282–289, 2001.
[25] Adrian S. Lewis and Michael L. Overton. Nonsmooth optimization via quasi-newton methods. Mathematical Programming, 141(1-2):135–163, 2013.
[26] Jin Yu, S. V. N. Vishwanathan, S. Günter, and N. Schraudolph. A quasi-Newton approach to nonsmoothconvex optimization problems in machine learning. JMLR, 11:1145–1200, 2010.
[27] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer,
R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.
Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.

9