Year: 2019

Abstract:
Off-policy training of contextual-bandit policies is attractive in online systems (e.g. search, recommendation, ad placement), since it enables the reuse of large amounts of log data. State-of-the-art methods for off-policy learning, however, are based on inverse propensity score (IPS) weighting, which requires that the logging policy chooses all actions with non-zero probability for any context (i.e., full support). In real-world systems, this condition is often violated, and we show that existing off-policy learning methods based on IPS weighting can fail catastrophically. We therefore develop new off-policy contextual-bandit methods that can controllably and robustly learn even when the logging policy has deficient support. To this effect, we explore three approaches that provide various guarantees for safe learning despite the inherent limitations of support deficient data: restricting the action space, reward extrapolation, and restricting the policy space. We analyze the statistical and computational properties of these three approaches, and empirically evaluate their effectiveness in a series of experiments. We find that controlling the policy space is both computationally efficient and that it robustly leads to accurate policies.

heading: 1 INTRODUCTION
text: Many interactive systems (e.g., voice assistants, recommender systems, ad placement) can be modeled as contextual bandit problems (Langford & Zhang, 2008). In particular, each user request provides a context (e.g., user profile, query) for which the system selects an action (e.g., recommended product, presented ad) and receives a reward (e.g., purchase, click). Such contextual-bandit data is logged in large quantities as a by-product of normal system operation (Li et al., 2011; 2015; Joachims et al., 2017), making it an attractive and low-cost source of training data. With terabytes of such log data readily available in many online systems, a range of algorithms have been proposed for batch learning from such logged contextual-bandit feedback (Strehl et al., 2011; Dudı́k et al., 2011; Swaminathan & Joachims, 2015a; Thomas & Brunskill, 2016; Farajtabar et al., 2018; Su et al., 2019; London & Sandler, 2019). However, as we will argue below, these algorithms require an assumption about the log data that makes them unsuitable for many real-world applications.
This assumption is typically referred to as the positivity or support assumption, and it is required by the Empirical Risk Minimization (ERM) objective that these algorithms optimize. Specifically, unlike in online learning for contextual bandits (Williams, 1992; Agarwal et al., 2014), batch learning from bandit feedback (BLBF) operates in the off-policy setting. During off-policy learning, the algorithm has to address the counterfactual question of how much reward each policy in the policy space would have received, if it had been used instead of the logging policy. To this effect, virtually all state-of-the-art off-policy learning methods for contextual-bandit problems rely on counterfactual estimators (Bottou et al., 2013; Dudı́k et al., 2011; Swaminathan & Joachims, 2015a; Thomas & Brunskill, 2016; Farajtabar et al., 2018; Su et al., 2019) that employ inverse propensity score (IPS) weighting to get an unbiased ERM objective. Unlike regression-based direct-modeling (DM) approaches that are often hampered by bias from model-misspecification, IPS allows a controllable bias-variance trade-off through clipping and other variance-regularization techniques (Strehl et al., 2011; Swaminathan & Joachims, 2015a; London & Sandler, 2019).
Unfortunately, IPS and its variance-control mechanisms break down when the logging policy does not have full support – meaning that some actions have zero probability of being selected under the logging policy. In this case IPS can be highly biased. Full support is an unreasonable assumption in many real-world systems, especially when the action space is large and many actions have poor
rewards. For example, in a recommender system with a large catalog (e.g. movies, music), it may be that less than 10% of the actions have support under the logging policy. We will show that existing learning algorithms can fail catastrophically on such support deficient data.
In this paper, we develop new off-policy contextual-bandit algorithms that are specifically designed to deal with support deficient log data. Since support deficiency translates into blind spots where we do not have any knowledge about the rewards, accounting for these blind spots as part of learning is crucial for robust learning. We approach this problem from three perspectives. First, we explore restricting the action space to those actions that have support under the logging policy. Second, we explore imputation methods that extrapolate estimated rewards to those blind spots. And, third, we restrict the policy space to only those policies that have limited exposure to the blind spots. To make the latter approach computationally tractable, we define a new measure of Support Divergence between policies, show how it can be estimated efficiently without closed-form knowledge of the logging policy, and how it can be used as a constraint on the policy space. We analyze the statistical and computational properties of all three approaches and perform an extensive empirical evaluation. We find that restricting the policy space is particularly effective, since it is computationally efficient, empirically effective at learning good policies, and convenient to use in practice.

heading: 2 RELATED WORK
text: Most prior works on BLBF can be classified into two different approaches. The first – called Direct Model (DM) – is based on a reduction to supervised learning, where a regression estimate is trained to predict rewards (Beygelzimer & Langford, 2009). To derive a policy, the action with the highest predicted reward is chosen. A drawback of this simple approach is the bias that results from misspecification of the regression model. Since regression models are often substantially misspecified for real-world data, the DM approach often does not work well empirically.
The second approach is based on policy learning via ERM with a counterfactual risk estimator. Inverse propensity score (IPS) weighting is one of the most popular estimators to be used as empirical risk. However, policy learning algorithms based on IPS and related estimators (Strehl et al., 2011; Swaminathan & Joachims, 2015a;b; Thomas & Brunskill, 2016; London & Sandler, 2019) require the assumption that the logging policy has full support for every policy in the policy space. One exception is the work of Liu et al. (2019). They relax the assumption to the existence of an optimal policy such that the logging policy covers the support of this optimal policy. However, this is an untestable assumption that does not provide guarantees for real-world applications.
Our work proposes three approaches to addressing off-policy learning with support deficiency. First, our conservative extrapolation method is related to the method proposed by Liu et al. (2019). They focus on the correction of the state distribution by defining an augmented MDP, and pessimistic imputation is used to get an estimate for policy-gradient learning. Second, our method of restricting the policy space uses a surrogate for the support divergence of two policies that was previously used as control variate in the SNIPS estimator (Swaminathan & Joachims, 2015b). It also appeared in the Lagrangian formulation of the BanditNet objective (Joachims et al., 2018) and in the gradient update in REINFORCE algorithm (Williams, 1992). This connection gives interesting new insight that the baselines used in policy-gradient algorithms not only help to reduce variance in gradients (Greensmith et al., 2004), but that they also connect to the problem of support deficiency in the off-policy setting.

heading: 3 OFF-POLICY LEARNING WITH DEFICIENT SUPPORT
text: We start by formally defining the problem of learning a contextual-bandit policy in the BLBF setting. Input to the policy are contexts x ∈ X drawn i.i.d from a fixed but unknown distribution P (X ). Given context x, the system executes a possibly stochastic policy π(Y|x) that selects an action y ∈ Y . For this context and action pair, the system observes a reward r ∈ [rmin, rmax] from P (r|x, y). Given a space of policies Π, the reward of any policy π ∈ Π is defined as
R(π) = E x E y∼π(y|x) E r∼P (r|x,y) [r]. (1)
In the BLBF setting, the learning algorithm is given a dataset D := {xi, yi, ri, π0(yi|xi)}ni=1
of past system interactions which consists of context-action-reward-propensity tuples. The propensity π0(yi|xi) is the probability of selecting action yi for context xi under the policy π0 that was used to log the data. We call π0 the logging policy, and we will discuss desired conditions on the stochasticity of π0 in the following. The goal of off-policy learning is to exploit the information in the logged data D to find a policy π̂ ∈ Π that has high reward R(π̂). Analogous to the ERM principle in supervised learning, off-policy learning algorithms typically optimize a counterfactual estimate R̂(π) of R(π) as the training objective (Li et al., 2011; 2015; Bottou et al., 2013; Swaminathan & Joachims, 2015a).
π̂ = arg max π∈Π [R̂(π)] (2)
For conciseness, we ignore additional regularization terms in the objective (Swaminathan & Joachims, 2015a), since they are irrelevant to the main point of this paper. As counterfactual estimator R̂(π), most algorithms rely on some form of IPS weighting (Strehl et al., 2011; Dudı́k et al., 2011; Swaminathan & Joachims, 2015a;b; Wang et al., 2017; Su et al., 2019) to correct the distribution mismatch between the logging policy π0 and each target policy π ∈ Π.
R̂IPS(π) = 1
n n∑ i=1 π(yi|xi) π0(yi|xi) ri. (3)
A crucial condition for the effectiveness of the IPS estimator (and similar estimators) is that the logging policy π0 assigns non-zero probability to all actions that have non-zero probability under the target policy π we aim to evaluate. This condition is known as positivity or full support, and it is defined as follows. Definition 1 (Full support). The logging policy π0 is said to have full support for π when π0(y|x) > 0 for all actions y ∈ Y and contexts x ∈ X for which π(y|x) > 0.
It is known that the IPS estimator is unbiased, ED[R̂IPS(π)] = R(π), if the logging policy π0 has full support for π (Li et al., 2011). To ensure unbiased ERM, algorithms that use the IPS estimator require that the logging policy π0 has full support for all policies π ∈ Π in the policy space. For sufficiently rich policy spaces, like deep-networks fw(x, y) with softmax outputs of the form
πw(y|x) = exp(fw(x, y))∑
y′∈Y exp(fw(x, y ′)) , (4)
this means that the logging policy π0 needs to assign non-zero probability to every action y in every context x. This is a strong condition that is not feasible in many real-world systems, especially if the action space is large and many actions have poor reward.
If the support requirement is violated, ERM learning can fail catastrophically. We will show below that the underlying reason is bias, not excessive variance that could be remedied through clipping or variance regularization (Strehl et al., 2011; Swaminathan & Joachims, 2015a). To quantify how support deficient a logging policy is, we denote the set of unsupported actions for context x under π0 as U(x, π0) := {y ∈ Y|π0(y|x) = 0}. The bias of the IPS estimator is then characterized by the expected reward on the unsupported actions. Proposition 1. Given contexts x ∼ P (X ) and logging policy π0(Y|x), the bias of R̂IPS for target policy π(Y|x) is equal to the expected reward on the unsupported action sets, i.e., bias(π|π0) = Ex[− ∑ y∈U(x,π0) π(y|x)δ(x, y)].
The proof is in Appendix A.1. From Proposition 1, it is clear that support deficient log data can drastically mislead ERM learning. To quantify the effect of support deficiency on ERM, we define the support divergence between a logging policy π0 and a target policy π as follows. Definition 2 (Support Divergence). For contexts x ∼ P (X ) and any corresponding pair of target policy π and logging policy π0, the Support Divergence is defined as
DX (π|π0) := E x∼P (X )  ∑ y∈U(x,π0) π(y|x)  . (5)
With this definition in hand, we can quantify the effect of support deficiency on ERM learning for a policy space Π under logging policy π0. Theorem 1. For any given hypothesis space Π with logging policy π0 ∈ Π, there exists a reward distribution Pr with support in [rmin, rmax] such that in the limit of infinite training data, ERM using IPS over the logged data D ∼ P (X ) × π0(·|X ) × Pr can select a policy π̂ ∈ arg maxπ∈Π ED[R̂IPS(π)] that is at least (rmax − rmin) maxπ∈ΠDX (π|π0) suboptimal.
The proof is in Appendix A.2. To illustrate the theorem, consider a problem with rewards r ∈ [−1, 0]. Furthermore, consider a policy space Π that contains a good policy πg with R(πg) = −0.1 and a bad policy πb with R(πb) = −0.7. If policy πb has support divergence DX (πb|π0) = 0.6 or larger, then ERM may return the bad πb instead of πg even with infinite amounts of training data.
Note that it is sufficient to merely have one policy in Π that has large support deficiency to achieve this suboptimality. It is therefore crucial to control the support divergence DX (π|π0) uniformly over all π ∈ Π, or to account for the suboptimality it can induce. To this effect, we explore three approaches in the following.

heading: 3.1 SAFE LEARNING BY RESTRICTING THE ACTION SPACE
text: The first and arguably most direct approach to reducing DX (π|π0) is to disallow any action that has zero support under the logging policy. For the remaining action set, the logging policy has full support by definition. This restriction of the action set can be achieved by transforming each policy π ∈ Π into a new policy that sets the probability of the unsupported actions to zero.
π(y|x) −→ π̄(y|x) := π(y|x) 1I{y/∈U(x,π0)} 1− ∑ y′∈U(x,π0) π(y ′|x) (6)
This results in a new policy space Π̄. All π̄ ∈ Π̄ have support divergence of zeroDX (π̄|π0) = 0 and ERM via IPS is guaranteed to be unbiased.
While this transformation of the policy space from Π to Π̄ is conceptually straightforward, it has two potential drawbacks. First, restricting the action space without any exceptions may overly constrain the policies in Π̄. In particular, if the optimal action y∗ for a specific context x does not have support under the logging policy, no π̄ ∈ Π̄ can ever choose y∗ even if there are many observations of similar y’s on similar context x′. The second drawback is computational. For every context x during training and testing, the system needs to evaluate the logging policy π0(y|x) to compute the transformation from π to π̄. This can be prohibitively expensive especially at test time, where – after multiple rounds of off-policy learning with data from previously learned policies – we would need to evaluate the whole sequence of previous logging policies to execute the learned policy.

heading: 3.2 SAFE LEARNING THROUGH REWARD EXTRAPOLATION
text: As illustrated above, support deficiency is a problem of blind spots where we lack information about the rewards of some actions in some contexts. Instead of disallowing the unsupported actions like in the previous section, an alternative is to extrapolate the observed rewards to fill in the blind spots. To this effect, we propose the following augmented IPS estimator that imputes an extrapolated reward δ̂(x, y) for each unsupported action y ∈ U(x, π0).
R̂δIPS(π) = 1
n n∑ i=1  π(yi|xi) π0(yi|xi) ri + ∑
y∈U(xi,π0)
π(y|xi)δ̂(xi, y)  (7) In the following proposition, we characterize the bias of the augmented IPS estimator for any given reward extrapolation δ̂(x, y). We denote the mean of the reward r for context x and action y with δ(x, y) = Er∼P (r|x,y)[r]. Furthermore, ∆(x, y) := δ̂(x, y)− δ(x, y) denotes the error of the reward extrapolation for each x and y. Proposition 2. Given contexts x1, x2, . . . , xn drawn i.i.d from the unknown distribution P (X ), for action yi drawn independently from logging policy π0 with probability π0(Y|xi), the bias of the empirical risk defined in Equation (7) is Ex[ ∑ y∈Uπ0x π(y|x)∆(x, y)].
Algorithm 1: Data Augmentation input: original logged dataset D, replaycount k,
reward estimate δ̂(x, y); output: D′; initialization: D′ = ∅ ; for j = 1, . . . , k do
for i = 1, . . . , n do Define Uxi to be the uniform distribution over U(xi, π0);
Draw y ∼ Uxi ; D′ = D′ ⋃ {xi, y, δ̂(xi, y), 1|U(xi,π0)|};
end end
In this way we can learn in the original action and policy space, but mitigate the effect of the support deficiency by explicitly incorporating the extrapolated reward δ̂(x, y). We explore two choices for δ̂(x, y) in the following, which provide different types of guarantees.
Conservative Extrapolation. To minimize the user impact of randomization in the logging policy, it is generally desirable to put zero probability on actions the are very likely to have low (or even catastrophic reward). This means that precisely those bad actions are likely to not be supported in the logging policy. A key danger of blind spots regarding those actions is that naive IPS training will inadvertently learn a policy that selects those actions. This can be avoided by being maximally conservative about unsupported actions and imputing the lowest possible reward ∀x, y ∈ U(x, π0) : δ̂(x, y) = rmin. Intuitively, by imposing the worst possible reward for the unsupported actions, the learning algorithm will aim to avoid these low-reward areas. However, unlike for the π̄ policies resulting from the restricted action space, the learned policy is not strictly prohibited from choosing unsupported actions – it is merely made aware of the maximum loss that the action may incur. Note that for problems where rmin = 0, the naive IPS estimator is identical to conservative extrapolation since the second term in Equation (7) is zero.
Regression Extrapolation. Instead of extrapolating with the worst-case reward, we may have additional prior knowledge in the form of a model-based estimate that reduces the bias. In particular, we explore using a regression estimate δ̂ = arg minδ̂θ 1 n ∑n i=1(δ̂
θ(xi, yi)− ri)2 that extrapolates from the observed data D. Typically, δ̂θ comes from a parameterized class of regression functions. Other regression objectives could also be used, such as weighted linear regression that itself uses importance sampling as weights (Farajtabar et al., 2018). But, fundamentally, all regression approaches assume that the regression model is not misspecified and that it can thus extrapolate well. Note that the IPS part of Equation (7) can be changed to any estimators (with action set restricted on U(x, π0)c for all x), and it turns out that doubly robust (Dudı́k et al., 2011) and CAB (Su et al., 2019) are special extensions of regression extrapolation that substitute the IPS part with their corresponding estimator.
Efficient Approximation. Evaluating the augmented IPS estimator from Equation (7) can be computationally expensive if the number of unsupported actions U(x, π0) is large. To overcome this problem, we propose to use sampling to estimate the expected reward on the unsupported action, which can be thought of as augmenting the dataset D with additional observations where the logging policy has zero support. In particular, we propose the data-augmentation procedure detailed in Algorithm 1. With the additional bandit data D′ = {x′j , y′j , δ̂(x′j , y′j), p′j}mj=1 from Algorithm 1, the new objective is
arg min π∈Π  1n n∑ i=1 π(yi|xi) π0(yi|xi) ri + 1 m m∑ j=1 π(y′j |x′j) p′j δ̂(x′j , y ′ j)  . (8) In Appendix A.5, we show that the empirical risk in Equation (8) has the same expectation (over randomness in D and D′) as R̂δIPS(D) and can thus serve as an approximation for Equation (7).

heading: 3.3 SAFE LEARNING BY RESTRICTING THE POLICY SPACE
text: As motivated by Theorem 1, the risk of learning from support deficient data scales with the maximum support divergence DX (π|π0) among the policies in the policy space Π. Therefore, our third approach restricts the policy space to the subset Πκ ⊂ Π that contains the policies π ∈ Π with an acceptably low support divergence DX (π|π0) ≤ κ. Πκ = {π|π ∈ Π ∧ DX (π|π0) ≤ κ} (9) The parameter κ has an intuitive meaning. It specifies the maximum probability mass that a learned policy can place on unsupported actions. By limiting this to κ, we limit the maximum bias of
the ERM procedure according to Proposition 2 while not explicitly torquing the rewards like in conservative reward imputation.
A key challenge, however, is implementing this restriction of the hypothesis space, such that the ERM learner π̂ = arg maxπ∈Πκ [R̂IPS(π)] only considers the subset Π
κ ⊂ Π. In particular, we do not have access to the context distribution P (X ) for calculating DX (π|π0), nor would it be possible to enumerate all π ∈ Π to check the condition DX (π|π0) ≤ κ, which itself requires a possibly infeasible iteration over all actions. The following theorem (with proof in Appendix A.3) gives us an efficient way of estimating and controlling DX (π|π0) without explicit knowledge of P (X ) or access to the logging policy π0 beyond the logged propensities. Theorem 2. For contexts xi drawn i.i.d from P (X ), action yi drawn from logging policy π0, we define SD(π|π0) = 1n ∑n i=1 π(yi|xi) π0(yi|xi) . For any policy π it holds that
E x∼P (X ) E y∼π0(·|x) [SD(π|π0)] +DX (π|π0) = 1 (10)
Using this theorem, the following proposition (proof in Appendix A.4, empirically verified in Appendix B) gives us an efficient way of implementing the constraintDX (π|π0) ≤ κ via 1−SD(π|π0).
Proposition 3. For any given κ ∈ (0, 1), 0 < < κ/2, let pmin denote the minimum propensity under supported set pmin = maxx,y∈U(x,π0)cπ0(y|x), then with probability larger than 1−2 exp(−2n 2p2min), the constraint 1−κ+ ≤ SD(π|π0) ≤ 1− will ensure 0 ≤ DX (π|π0) ≤ κ.
We can thus use 1− SD(π|π0) as a surrogate for DX (π|π0) in the training objective:
arg min πw∈Π
1
n n∑ i=1 πw(yi|xi) π0(yi|xi) ri. subject to 1− κ+ ≤ 1 n n∑ i=1 πw(yi|xi) π0(yi|xi) ≤ 1− (11)
Using Lagrange multipliers, an equivalent dual form of Equation (11) is:
max u1,u2≥0 min πw∈Π
1
n n∑ i=1 πw(yi|xi) π0(yi|xi) (ri + u1 − u2)− u1(1− ) + u2(1− κ+ ) (12)
For each fixed (u1, u2) pair, the inner minimization objective is ERM with IPS under a shift of the reward. Instead of maximizing over (u1, u2) in the outer objective, we treat (u1 − u2) as a hyperparameter that we select on a validation set. We explore various estimators for this modelselection problem in Section 4.
Note that, among the methods we proposed for dealing with support deficiency, this approach is the most efficient to implement, and it does not require access to the logging policy during training or testing. Furthermore, the form of the inner objective coincides with that of BanditNet (Joachims et al., 2018), which is known to work well for deep network training by controlling propensity overfitting (Swaminathan & Joachims, 2015a).

heading: 4 EMPIRICAL EVALUATION
text: We empirically evaluate the effectiveness and robustness of the three proposed approaches: restricting the action space, conservative and regression extrapolation, as well as restricting the policy space. The semi-synthetic experiments are based on two real-world datasets: one is the popular image classification dataset CIFAR10 (Krizhevsky et al.) and the other is the credit-card fraud dataset of Dal Pozzolo et al. (2015). We use the naive IPS estimator and the regression-based Direct Method (DM) as baselines.
The experiments are set up as follows. We first create a train-validation-test split for both datasets. The training set is used to generate bandit datasets for learning, the validation set is used to generate bandit datasets for model selection, and the full-information test set serves as ground truth for evaluating the learned policies. To simulate bandit feedback for the CIFAR10 dataset, our experiment setup follows traditional supervised→ bandit conversion for multi-class classification datasets (Beygelzimer & Langford, 2009). To not only have bandit data with binary multi-class rewards, we
choose a different methodology for the credit-card dataset by designating some features as corresponding to actions and rewards. More details are given in Appendix B.
To get logging policies for generating bandit feedback, we start by training a softmax-policy as in Equation (4) on a subset of the full-information data. We then introduce a temperature parameter τ into the learned policy via τfw(x, y) to be able to control its stochasticity and support deficiency. In particular, we enforce zero support for some actions by clipping the propensities to 0 if they are below a threshold of = 0.01. The larger τ , the higher the support deficiency. Note that making the threshold at = 0.01 allows us to control support while the variance of IPS stays bounded. This allows us to study support deficiency without having to worry about variance control.
For both logging and target policies, we train softmax policies where fw(x, y) is a neural network. We use the ResNet20 architecture (He et al., 2016) for CIFAR10, and a fully-connected 2-layer network for the credit-card dataset.
How do the methods perform at different level of support deficiency? Results are shown in Figure 1. First, as expected, learning using naive IPS degrades on both datasets as we make the logging policy more peaked and the number of unsupported actions increases. Note that naive IPS coincides with Conservative Extrapolation, since both datasets are scaled to have a minimum reward of zero. In the rightmost column, however, we translated the rewards to [−1, 0]. This has a strong detrimental effect on naive IPS, as it is now overly optimistic about unsupported actions. Second, the approach of dealing with support deficiency by restricting the action space also performs poorly. The second row of plot sheds some light on this, as it shows the support divergence DX (π|π0) of the learned policy. It is zero for Action Restriction as expected, which means that bias is not the problem. Instead, as the number of unsupported actions increases, the best actions are more likely to be pruned and unavailable in the restricted policy space Π̄. Third, Regression Extrapolation performs better than Conservative Extrapolation on both datasets. In both cases, the DM model is quite good which also benefits Regression Extrapolation. However, on the credit-card dataset the regression seems better at ranking than at predicting the true reward, which explains why DM performs better than Regression Extrapolation. Fourth, the method that performs well most consistently is Policy Restriction. Unlike all the other IPS-based methods, it performs well even under the translated rewards in the third column of Figure 1. This is because the objective of Policy Restriction coincides with that of BanditNet (Joachims et al., 2018), which is known to remedy propensity overfitting due to the lack of equivariance of the IPS estimator (Swaminathan & Joachims, 2015b).
How does the learning performance change with more training data? Results are shown in Figure 2. As the number of bandit examples increases, Policy Restriction, Regression Extrapolation and DM dominate over most of the range especially when the percentage of unsupported actions is large. Among the other methods, Action Restriction can take the least advantage of more data. This is plausible, since its maximum performance is limited by the available actions. For similar reasons, Conservative Extrapolation (and equivalently IPS) also flattens out, since it also tightly restricts the action space by imputing the minimum reward.
How effective are the estimators for model selection? Most learning algorithms have hyperparameters, and we now evaluate how the estimators perform for this secondary learning problem. We specifically focus on the parameter k := u1 − u2 in Policy Restriction, since it controls how much the learned policies can step outside the region of support. The table on the left of Figure 3 shows the reward of the learned policy when performing model selection with the respective estimator. Oracle is the estimator that has access to the full-information validation set, and can thus be considered as a skyline. We also included the SNIPS estimator (Swaminathan & Joachims, 2015b), which imputes the average reward on the supported action for the unsupported actions (Gilotte et al., 2018). All estimators perform quite well for model selection on CIFAR, and the results are analogous for the credit-card data (see Appendix B.2). However, the plot to the right of Figure 3 reveals that SNIPS does not accurately reflect the shape of the Oracle curve. Both Regression Extrapolation and DM, however, are found to be sufficiently accurate for reliable model selection.

heading: 5 DISCUSSION AND CONCLUSIONS
text: We identified and analyzed how off-policy learning based on IPS weighting can suffer severely degraded learning performance when the logging policy is support deficient. To remedy this problem, we explored approaches that limit the impact of missing support through three different means: restricting the action space, reward extrapolation and restricting the policy space. We find that the most natural approach of restricting the action space is neither computationally efficient, nor does it learn accurate policies. Reward extrapolation through regression and restricting the policy space, however, both perform well and robustly even at high levels of support deficiency. Among those two methods, reward extrapolation has the potential drawback that we need to compute (and/or sample from) the complement of the logging policy, which can be computationally challenging. Furthermore, having to store all old logging policies is inconvenient in practice. This makes the approach of restricting the policy space particularly attractive, since it is computationally efficient and it does not require access to the logging policy beyond the logged propensity values.

heading: A APPENDIX: PROOFS
text: In this appendix, we provide proofs of the main theorems and propositions.

heading: A.1 PROOF OF PROPOSITION 1
text: Proposition 1. Given contexts x ∼ P (X ) and logging policy π0(Y|x), the bias of R̂IPS for target policy π(Y|x) is equal to the expected reward on the unsupported action sets, i.e., bias(π|π0) = Ex[− ∑ y∈U(x,π0) π(y|x)δ(x, y)].
Proof. Recall δ(x, y) = Er[r(x, y)|x, y], and logged data D ∼ PX × π0(·|X )× Pr.
bias(π|π0) = E D [R̂IPS(π)]−R(π)
= E x
[ ∑
y∈(U(x,π0))c π0(y|x)
π(y|x) π0(y|x) δ(x, y)− ∑ y∈Y π(y|x)δ(x, y)]
= E x
[− ∑
y∈U(x,π0)
π(y|x)δ(x, y)]
(13)

heading: A.2 PROOF OF THEOREM 1
text: Theorem 1. For any given hypothesis space Π with logging policy π0 ∈ Π, there exists a reward distribution Pr with support in [rmin, rmax] such that in the limit of infinite training data, ERM using IPS over the logged data D ∼ P (X ) × π0(·|X ) × Pr can select a policy π̂ ∈ arg maxπ∈Π ED[R̂IPS(π)] that is at least (rmax − rmin) maxπ∈ΠDX (π|π0) suboptimal.
Proof. For any given hypothesis space Π and logging policy π0, define a deterministic reward distribution Pr as the following: for all context x, r(x, y) = δ(x, y) = rmin for y ∈ U(x, π0)c and r(x, y) = δ(x, y) = rmax for y ∈ U(x, π0). Let π̃ ∈ arg maxπ∈ΠDX (π|π0) and π∗ ∈ arg maxπ∈ΠR(π), then we have the following lower bound for R(π∗):
R(π∗) ≥ R(π̃)
= E x
[ ∑
y∈U(x,π0)
rmax + ∑
y∈U(x,π0)c rmin]
= rmax max π∈Π DX (π|π0) + rmin(1−max π∈Π DX (π|π0))
(14)
where the first inequality follows from the definition of π∗, the first and second equality is based on the specific reward distribution Pr and the definition of π̃. In the following we will show that for any π̂ learned by the expectation of ERM (or in the limit of infinite amount data), i.e., π̂ ∈ arg maxED[R̂DIPS(π)], π̂ have the same support as π0.
E D [R̂IPS(π)] = E x
[ ∑
y∈U(x,π0)c π(y|x)rmin] = rmin E x [ ∑ y∈U(x,π0)c π(y|x)] ≤ rmin (15)
for all π ∈ Π, then it is easy to see π0 ∈ Π is one of the solution of ERM. Actually for any π̂ ∈ arg maxED[R̂DIPS(π)], Ex[ ∑ y∈U(x,π0)c π(y|x)] = 1 and it gives us that any solution of the ERM has exactly the same support as π0, then we have R(π̂) = rmin for π̂ ∈ arg maxED[R̂DIPS(π)]. Combining the lower bound for R(π∗) and R(π̂) = rmin, we have
R(π∗)−R(π̂) ≥ rmax max π∈Π DX (π|π0) + rmin(1−max π∈Π DX (π|π0))− rmin
= (rmax − rmin) max π∈Π DX (π|π0)
(16)

heading: A.3 PROOF OF THEOREM 2
text: Theorem 2. For contexts xi drawn i.i.d from P (X ), action yi drawn from logging policy π0, we define SD(π|π0) = 1n ∑n i=1 π(yi|xi) π0(yi|xi) . For any policy π it holds that
E x∼P (X ) E y∼π0(·|x) [SD(π|π0)] +DX (π|π0) = 1 (10)

heading: Proof.
text: E x,y∼π0 [SD(π|π0)] +DX (π|π0) = E x
[ ∑
y∈U(x,π0)c π0(y|x)
π(y|x) π0(y|x) ] +DX (π|π0)
= E x
[ ∑
y∈U(x,π0)c π(y|x)] + E
x [ ∑
y∈U(x,π0)
π(y|x)]
= E x [ ∑ y∈Y π(y|x)] = 1
(17)
The first equality is based on definition of SD(π|π0) and the second equality is based on definition of support divergence.

heading: A.4 PROOF OF PROPOSITION 3
text: Proposition 3. For any given κ ∈ (0, 1), 0 < < κ/2, let pmin denote the minimum propensity under supported set pmin = maxx,y∈U(x,π0)cπ0(y|x), then with probability larger than 1−2 exp(−2n 2p2min), the constraint 1−κ+ ≤ SD(π|π0) ≤ 1− will ensure 0 ≤ DX (π|π0) ≤ κ. Proof. Recall SD(π|π0) = 1n ∑n i=1 π(yi|xi) π0(yi|xi) with (xi, yi) draw i.i.d from P (X ) × π0(Y|x). From Appendix A.3, it is easy to see Ex,y∼π0(·|x)[ π(y|x) π0(y|x) ] = 1−DX (π|π0). Let pmin denote the smallest propensity under supported action set, pmin := minx,y∈U(x,π0)c π0(y|x) > 0, then the random variable π(y|x)π0(y|x) is strictly bounded between [0, 1 pmin ]. Applying Hoeffding’s bound gives:
P(DX (π|π0) < 1− SD(π|π0)− ) = P(SD(π|π0)− (1−DX (π|π0)) < − ) ≤ exp(−2n 2p2min) (18) Since SD(π|π0) ≤ 1− gives 1− SD(π|π0)− ≥ 0, then we have
P(DX (π|π0) < 0) ≤ exp(−2n 2p2min) (19)
Similar for the other direction, Hoeffding’s bound gives:
P(DX (π|π0) > 1− SD(π|π0) + ) = P(SD(π|π0)− (1−DX (π|π0)) > ) ≤ exp(−2n 2p2min) (20)
Since SD(π|π0) ≥ 1 + − κ gives 1− SD(π|π0) + ≤ κ, then we have
P(DX (π|π0) ≥ κ) ≤ exp(−2n 2p2min) (21)
Combining the above, we have
P(0 ≤ DX (π|π0) ≤ κ) = 1− P(DX (π|π0) < 0)− P(DX (π|π0) > κ) ≥ 1− 2exp(−2n 2p2min)
(22)

heading: A.5 PROOF FOR EFFICIENT APPROXIMATION
text: Claim 1. The empirical risk defined by in Equation (8) has the same expectation (over randomness in D and sampling) as R̂δIPS(D).
Proof. Taking the expectation of empirical risk defined in Equation (8):
E [ 1 n n∑ i=1 π(yi|xi) π0(yi|xi) ri + 1 m m∑ j=1 π(yj |xj) pj δ̂(xj , yj) ]
= E x [ ∑ y∈U(x,π0)c π0(y|x) π(y|x) π0(y|x) δ(x, y) ] + E x [ ∑ y∈U(x,π0)
1 |U(x, π0)| π(y|x)
1 |U(x,π0)|
δ̂(x, y) ]
= E x [ ∑ y∈U(x,π0)c π(y|x)δ(x, y) ] + E x [ ∑ y∈U(x,π0) π(y|x)δ̂(x, y) ]
(23)
Now we will show it has the same expectation with R̂δIPS(π)
E D [ π(yi|xi) π0(yi|xi) ri + ∑
y∈U(xi,π0)
π(y|xi)δ̂(xi, y) ]
= E x
[ E
y∼π0 [ π(y|x) π0(y|x)
δ(x, y)] + ∑
y′∈U(x,π0)
π(y′|x)δ̂(x, y′) ]
= E x
[ ∑
y∈U(x,π0)c π0(y|x)
π(y|x) π0(y|x)
δ(x, y) + ∑
y′∈U(x,π0)
π(y′|x)δ̂(x, y′) ]
= E x [ ∑ y∈U(x,π0)c π(y|x)δ(x, y) ] + E x [ ∑ y∈U(x,π0) π(y|x)δ̂(x, y) ]
(24)
The proof is done by comparing Equation (23) and Equation (24).

heading: A.6 PROOF OF PROPOSITION 2
text: Proposition 2. Given contexts x1, x2, . . . , xn drawn i.i.d from the unknown distribution P (X ), for action yi drawn independently from logging policy π0 with probability π0(Y|xi), the bias of the empirical risk defined in Equation (7) is Ex[ ∑ y∈Uπ0x π(y|x)∆(x, y)].
Proof. From Appendix A.5, we are given the expectation of R̂δIPS(π), and the bias is:
bias(R̂δIPS(π)) = ED[R̂ δ IPS(π)]−R(π)
= E x [ ∑ y∈U(x,π0)c π(y|x)δ(x, y) + ∑ y∈U(x,π0) π(y|x)δ̂(x, y) ] −R(π)
= E x [ ∑ y∈U(x,π0) π(y|x)(δ̂(x, y)− δ(x, y)) ]
= E x [ ∑ y∈U(x,π0) π(y|x)∆(x, y) ]
(25)
The second equality is from Appendix A.5, the second equality is based on R(π) = Ex [∑ y∈U(x,π0)c π(y|x)δ(x, y) + ∑ y∈U(x,π0) π(y|x)δ(x, y) ] , and the last one is based on the definition of ∆(x, y) := δ̂(x, y)− δ(x, y) for all x ∈ X , y ∈ Y .

heading: B APPENDIX: EXPERIMENTS
text: In this section, we provide the experiment details and additional results to help promote reproducibility of this work.

heading: B.1 EXPERIMENT SETUP DETAILS
text: Datasets and baseline. We follow a 75:10:15 train-validation-test split for credit card fraud detection dataset, while for CIFAR10 already coming with a train-test split, we keep 10% of the training set as validation set. Baseline estimators are IPS and DM, the hyperparameters (learning rate, L2 regularization) are optimized for all the methods based on the validation set.
Bandit data generation. For CIFAR10, given supervised data {xi, y∗i }ni=1 where xi denotes the 3072 features and y∗i denotes the correct label of data (ranging from 0 to 9), under logging policy π0, the logged bandit data is generated by drawing yi ∼ π0(Y|xi), then a deterministic reward is defined as 1I{yi=y∗i }. For the credit card fraud detection dataset, we throw away the class label and only use the features for each sample to generate bandit data. To be specific, for each sample with a 28-dimensional feature vector, we define the first 20 features as the contextual information, and use the remaining 8 features as the underlying true reward for 8 different actions (with normalization).
Logging policy. For CIFAR, we learn the softmax logging policy on 35K full-information data points as a multi-class classification problem with cross-entropy loss. Similar as the experiments on BanditNet (Joachims et al., 2018), we adopt the conventional ResNet20 architecture but restrict training after a mere two epochs to derive a relative stochastic policy, since it will be easier to add temperature later to control its stochasticity and support deficiency. Similarly, for the credit card fraud detection dataset, the softmax logging policy is learned on 8K full-information data points by treating it as a multi-class classification problem using cross-entropy loss and the label being the action with the highest reward on this specific context. For CIFAR, the logging policy we trained has a 57.43% accuracy on the test-set; whereas for the credit card fraud detection dataset, the logging policy has an expected true reward of 0.71.
Reward estimator. For each experiment, we train a different regression function using the full bandit dataset. We use the same architecture as the one used for off-policy learning - where the final layer is the size of the actions, specifying the reward for each action given a particular context. The regression function is trained using the MSE objective.

heading: B.2 SUPPLEMENTARY RESULTS
text: Reliability of approximating support divergence using control variate. In this experiment, we empirically verify the reliability of estimating support divergence using control variate. The target policy is the uniform policy while the logging policies are varying in their support deficiency. Results are averaged over 10 runs and is shown in Figure 4. We investigate the behaviour of SD(π|π0) + DX (π|π0) under different number of training data and different support deficiency of the corresponding logging policy. As we can see, the sum converges to 1 as the training data
increases. Meanwhile, the variance decreases as shown in the right figure. For different support deficiency curves, the curve converges in a similar fashion and we conjecture it is due to the effect of clipping the propensity at the same threshold = 0.01, which makes pmin = 0.01 in the bound shown in Proposition 3.
Model selection comparison for the credit card dataset. The model selection comparison over the credit card fraud detection dataset is demonstrated in Figure 5. Similar as the trend in Figure 3, SNIPS and Conservative Extrapolation exhibit a large bias, also SNIPS even can not reflect the shape of the Oracle curve. DM and Regression Extrapolation closely track the Oracle line, and they have the best performance when used in model selection, as seen in the left table of Figure 5.

Review summaries:
This work addresses the problem of off-policy evaluation in the presence of positivity violations, i.e. some actions are not observed in the logged policy. As the paper points out, positivity violations can lead to unboundedly bad estimates when employing IPS. The authors propose three methods to deal with this problem. The first uses only the observed actions, the second and third use extrapolation and augmentation to provide an approximation to the off-policy problem. 

This paper talks about the problem of off-policy or batch learning in the contextual bandit setting without the complete support assumption. This problem setting is very realistic and encountered in most problems, especially in temporally extended settings, such as reinforcement learning. They compare three approaches for the same: restricting action selection, learning extrapolated reward models, and by restricting the policy class. They derive a SNIPS style estimator for the support constraint in the final approach. The approach with restricting the policy class demonstrates decent empirical results although the direct method is very much comparable.