Off-policy Bandits with Deficient Support
Authors: Noveen Sachdeva
Yi Su
Thorsten Joachims
Venue:  (2020)
Keywords: Recommender System
Search Engine
Counterfactual Learning

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 from the production system. 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.

Under review as a conference paper at ICLR 2020
OFF-POLICY BANDITS WITH DEFICIENT SUPPORT
Anonymous authors
Paper under double-blind review
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-att methods for off 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 sup- port). In real-world systems, this condition is often violated, and we show that existing off-policy learning methods based on IPS weighting can fail catastroph- ically. We therefore develop new off-policy controllably and robustly learn even when the logging policy has deficient sup- port. To this effect, we explore three approaches that provide various guarantees for safe learning despite the inherent limitations of support deficient data: restrict- ing 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 series of experiments. We find that controlling the policy space is both computationally efficient and that it robustly leads to accurate policies.
cuntextual-bandee methods that can
INTRODUCTION
Many interactive systems (e.g., voice assistants, recommender systems, ad placement) can be mod- eled 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., recom- mended product, presented ad) and receives a reward (e.g.. purchase, click). Such contextual-bandee by-product of normal system operation (Li et al.) 2011] 2015
data is logged in large quantities Joachims et al. 2017), making it an attractive and low-cost source 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-bamn
feedback (Strchl et al. [201]] 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 be 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 is required by the Empirical Risk Minimization (ERM) objective that these algorithms optimize. Specifically, unlike online learning for contextual bandits (Williams) 1992] Agarwal et al., 2014), batch learn- ing from bandit feedback (BLBF) operates in the off-policy setting. During off col-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 oftte-of-the-art off- ool-po learning methods for contextual- -bnditt problems rely on counterfac- tual estimators (Bottou al.) [2013] Dudík 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) IPS allows controllable
approaches that are often hampered by bias from variance-regularizatio techniques (Strehl et al.)
bias-variance trade-off through clipping and other
2011 Swaminathan & Joachims 2015a London & Sandler 2019).
Unfortunately. IPS and its variance-come 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

---

Under review as a conference paper at ICLR 2020
rewards. For example, in recommender system with 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 such support deficient data.
In this paper, we develop new off-po contextual- bandii algorithms that are specifically designed to deal with support deficient log data. Since support deficiency translates into blind spots where do not have any knowledge about the rewards, accounting for these blind spots as part of learning 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 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 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 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.
2 RELATED WORK
Most prior works on BLBF can be classified into two different approaches. The first - called Direct Model (DM) is based on reduction supervised learning, where regression estimate is trained to predict rewards (Beygelzimer & Langford| (009). 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 mis- specification of the regression model. Since regression models are often substantially misspecified for real-worls 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. In- verse propensity score (IPS) weighting is one of the most popular estimators 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 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 the correction of the state distribution by defining augmented MDP, and pessimistic imputation is used to get an estimate for policy-gradient learning. Second, our method of restricting the policy space uses 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 reduce variance in gradients (Greensmith et al., 2004), but that they also connect to the problem of support deficiency in the off off-policy setting.
OFF-POLICY LEARNING WITH DEFICIENT SUPPORT
We start by formally defining the problem of learning contextual-bandit policy in the BLBF setting. Input to the policy are contexts x E X drawn i.i.d from fixed but unknown distribution P(X). Given context z, the system executes possibly stochastic policy <(*lx) that selects an action y E y. For this context and action pair, the system observes a reward r E [rmin, Tmaa]] from P(rla,y). Given a space of policies II, the reward of any policy E II is defined as
R(x)
E
[r].
(1)
# y r(P()
In the BLBF setting, the learning algorithm is given a dataset
D {xi, yi, TG, To (o [=
2

---

Under review as a conference paper at ICLR 2020
of past system interactions which consists of sontext-attoon-teward-p sity (o (x)) is the probability of selecting action yi for context 2; under the policy To that was used to log the data. We call ma the logging policy, and will discuss desired conditions on the stochasticity of To in the following. The goal of off-policy learning is to exploit the information in the logged data D find policy से IT that has high reward R(A+).
tuples. The propen-
Analogous to the ERM principle in supervised learning, off-policy learning algorithms typically
optimize a counterfactual estimate R(()) of R(T) I
as the training objective (Li et al. 2011 2015
Bottou et al. 2013; Swaminathan & Joachims 2015a).
π = arg max[[[(T]]]
(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 es-
timator R T). most algorithms rely on some form of IPS weighting (Strehl et al. 2011 Dudik et al.,
2011 Swaminathan & Joachhiss 2015a b WWan et al. 2017 Su et al. (0199) to correct the distribu- tion mismatch between the logging policy To and each target policy π E IT.
n
π (y (c))
RIPS(T) (T) n
A crucial condition for the effectiveness of the IPS estimator (and similar estimators) is that the logging policy my 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 (Full support). The logging policy mo is said to have full support for when no mo(y)>) > for all actions y y and contexts X for which (tylz) > 0.
is known that the IPS estimator is unbiased, (D(R)PS(TT) (T)) R(T). if the logging policy mo has full support for ı (Li et al., 10.1). To ensure unbiased ERM, algorithms that use the IPS estimator require that the logging policy To has full support for all policies π E II in the policy space. For sufficiently rich policy spaces, like deep-networks Su v) with softmax outputs of the form
exp(Su (zr,))
The (1
Eyery
this means that the logging policy Tu needs to assign non-zero probability to every action in every context z. 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 Joachims|201530 2015a). To quantify how support deficient a logging policy is, we denote the set of unsupported actions for context under To as
U(z, mo) {y Mo(())))) = 0}.
The bias of the IPS estimator then characterized by the expected reward on the unsupported actions.
Proposition 1. Given contexts x ~ P(X) and logging policy no (V())) the bias of RIPs for target policy ()/2z) is equal to the expected reward on the unsupported action sets, i.e., (ias(T) Ez Eyeu(E,,))) π (y]x))(2 v)).
The proof is in Appendix A.I
From Proposition I it is clear that support deficient log data can drastically mislead ERM learning. To quantify the effect of support deficiency ERM, we define the support divergence between a logging policy To and a target policy π as follows.
Definition 2 (Support Divergence). For contexts P(X) and any corresponding pair of target policy π. and logging policy na, the Support Divergence is defined as
Dx(a = E P(X(
Σ
T(ylx)
(5)
3

---

Under review as a conference paper at ICLR 2020
With this definition in hand, we can quantify the effect of support deficiency on ERM learning for policy space II under logging policy To.
Theorem 1. For any given hypothesis space II with logging policy wo E II, there exists reward distribution P, with support in [mmi Tmaul such that in the limit of infinite training data, ERM using IPS over the logged data D P(X) x To(-12) x Pr can select a policy T E arg man EE Ps(((IP((TT) that is at least (Tmax - mmin) ma Dx ( suboptimal.
The proof is in Appendix A.2 To illustrate the theorem, consider problem with rewards [-1,0]. Furthermore, consider policy space II that contains a good policy Tg with R(xg) -0.1 and bad policy Te with [((,) - -0.7. If policy m has support divergence Dx(Tolmm (To) larger, then ERM may return the bad na instead of Ty even with infinite amounts of training data.
0.6 or
Note that it is sufficient to merely have one policy in IT that has large support deficiency achieve this suboptimality. It is therefore crucial to control the support divergence (T(T) uniformly over all π II, or to account for the suboptimality can induce. To this effect, we explore three approaches in the following.
3.1 SAFE LEARNING BY RESTRICTING THE ACTION SPACE
The first and arguably most direct approach to reducing Dx(= (T)) 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 II into new policy that sets the probability of the unsupported actions zero.
T(ylz) Il ((FE(((a
E (vlxr) - #l]l)) = 1- E-Ey E EEM(,,, (yylxz)
(6)
This results in a new policy space IT. All न E IT have support divergence of zero ( = and ERM via IPS is guaranteed to be unbiased.
While this transformation of the policy space from II to II is conceptually straightforward, it has two potential drawbacks. First, restricting the action space without any exceptions may overly constrain the policies in II. particular, the optimal action y² for a specific context æ does not have support under the logging policy, no ã E II 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 evaluate the logging policy To (y/lr) 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 to evaluate the whole sequence of previous logging policies to execute the learned policy.
would need
3.2 SAFE LEARNING THROUGH REWARD EXTRAPOLATION
As illustrated above, support deficiency is 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 to extrapolate the observed rewards to fill in the blind spots. To this effect, we propose the following augmented IPS estimator that imputes extrapolated reward 8(z, y) for each unsupported action y (2 mo).
(T)
1 n2
Σ
(vn(x;)) To( [r,)
Σ
[(112:88(2, v)
In the following proposition, we characterize the bias of the augmented IPS estimator for any given reward extrapolation 8zz, y). We denote the mean of the reward r for context and action y with 8(x, v) = P(raa [r). Furthermore, A(x v) 8(. y) 5(x, y) denotes the error of the reward extrapolation for each x and y.
Proposition 2. Given contexts I1, T2,T2.... Zn drawn i.idd from the unknown distribution P(X), for action yi drawn independently from logging policy no with probability <o(V)z;), the bias of the empirical risk defined in Equation (7) is E Ex ( y)].
4

---

Under review as a conference paper at ICLR 2020
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 8(z, y). We explore two choices for 8(x, y) in the following, which provide different types of guarantees.
Algorithm 1: Data Augmentation
input: original logged dataset D, replaycount k reward estimate 5(x, y); output: D'; initialization: D' 0
for j = 1. ................................ h: do
for 1, ................................ do
Conservative Extrapolation. To minimize the user impact of randomization in the logging policy, it is generally desirable to put zero prob- ability actions the are very likely to have low (or even catastrophic reward). This means that precisely those bad actions 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 Vx, y E U(x TT) 8(x.. y) mmin- Intuitively, by imposing the worst possible reward for the unsupported actions, the learning algo- rithm will aim 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 Tién = O, the naive IPS estimator is identical to conservative extrapolation since the second term in Equation 7 is zero.
Define Un, to be the uniform distribution over mT):
Draw y ~ Ugii
D' = D' Ulai, v, 8(3;;, u), [o)
end
end
Regression Extrapolation. Instead of extrapolating with the worst-case reward, we may have addi- tional prior knowledge the form of model-based estimate that reduces the bias. In particular, we explore using a regression estimate 8 = arg minge 1. = yi) rr,² that extrapolates from the observed data D. Typically, 8 comes from parameterized class of regression functions. Other regression objectives could also be used, such as weighted linear regression that itself uses impor- tance sampling 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 (xx To) for all x), and it turns out that doubly robust (Dudik et al. (011) 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 com- putationally expensive if the number of unsupported actions ((2, To) 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 with additional observations where the log- ging policy has zero support. In particular, we propose the data-augmennation procedure detailed in Algorithm With the additional bandit data D' new objective is
{x'y, Vly 8(xy, v5), pt )3=
from Algorithm the
T(I( To (z.)
T P'J
arg min TEll
Ma vf)
n
In Appendix A.5 we show that the empirical risk in Equation randomness in D and D') as (DD) and can thus serve as an approximation for Equation (7)
(8) has the same expectation (over
3.3 SAFE LEARNING BY RESTRICTING THE POLICY SPACE
As motivated by Theorem I the risk of learning from support deficient data scales with the maxi- mum support divergence xx (1 (T)) among the policies in the policy space II. Therefore, our third approach restricts the policy space the subset II" C II that contains the policies л E II with an acceptably low support divergence Dx(m TO) S K.
T {m x
II (x(T) S x
The parameter i has an intuitive meaning. It specifies the maximum probability mass that a learned policy can place on unsupported actions. By limiting this to k, limit the maximum bias of
5

---

Under review as a conference paper at ICLR 2020
the ERM procedure according to Proposition conservative reward imputation.
2 while not explicitly torquing the rewards like in
A key challenge, however, is implementing this restriction of the hypothesis space, such that the ERM learner at arg m [Ryps( (<r) only considers the subset IT C II. In particular, not have access to the context distribution P(X') for calculating Dx(=(=o) (o)) nor would it be possible enumerate all π II to check the condition (x (O) S K. which itself requires 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 ( (o) without explicit knowledge P(X) or access to the logging policy beyond the logged propensities.
do
Theorem 2. For contexts Ty drawn i..d from P(2)), action yi drawn from logging policy no, we
define (D(TT)T)) = EE= (o)
s(pslos) For any policy it holds that
E
E
[SD(T[TO)] + (x(T =1
(10)
Using this theorem, the following proposition (proof in Appendix A.4 empirically verified in Ap- pendix B gives an efficient way of implementing the constraint ( (m) S K via 1 (p
Proposition For any given i. (0,1), < c k/2, let pmin denote the minimum propen- sity under supported set Pmii = makz ( (o (y) then with probability larger than 1-2exp(-2ne' pmine"" the constraint 1-x+e S Sp(T (T) I 1 will ensure 0 I (T) R.
We can thus use 1 - (D(T(TO) as surrogate for Dx (T) in the training objective:
(=)() To To(vilz3) [z:)" Ts. subject to - -
Tw (v (x4)
arg min Ew
S 1 -
(1I)
Y2
To (z:)
Using Lagrange multipliers, an equivalent dual form of Equation is:
(Vil
max min My Me w Ell To(yi [.,)
(ra + u2) un e) + uz(1 K +)
(12)
For each fixed (2), pair, the inner minimization objective is ERM with IPS under shift of the reward. Instead of maximizing over (u1, 42) in the outer objective, we treat (#1 w2) as a hyperparameter that select validation set. We explore various estimators for this model- selection problem in Section
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 overlitting (Swaminathan & Joachims 2015a
EMPIRICAL EVALUATION
We empirically evaluate the effectiveness and robustness of the three proposed approaches: restrict- ing 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 the popular im- age classification dataset CIFAR 10 (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 rrain-validation-eest split for both datasets. The training set is used to generate bandit datasets for learning, the validation set is used to gener- ate 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 CIFARIO dataset, our experi- ment setup follows traditional supervised > bandit conversion for multi-clan class classification datasets (Beygelzimer & Langford 2009). To not only have bandit data with binary multi-class rewards,

---

Under review as a conference paper at ICLR 2020
choose different methodology for the credit-card dataset by designating some features corre- sponding to actions and rewards. More details are given in Appendix B
To get logging policies for generating bandit feedback, we start by training softmax-polics in Equation 4 on a subset of the full-information data. We then introduce a temperature parameter т into the learned policy via 7f nz (xr (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 if they are below a threshold of e 0.01. The larger 7, 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 study support deficiency without having to worry about variance control.
For both logging and target policies, we train softmax policies where (2r y) is neural network. We use the ResNet20 architecture (He et al. 2016) for CIFARIO, and a fully-connected 2-layer network for the credit-card dataset.
CIFAR
Credit Card
Credit Card Translated
90
0.0
Accuracy
85
True Rewaadd
0.80
True Reward
0.7
0.75
80
0.6
0.70
0.5
0.4
70
Supgort Divergence
0.25
Support Divergente
Support Divergence
1.0
0.6
0.20
0.8
0.4
0.4
0.2
0.06
0.2
0.00
0.0
0.0
45
69
70
80
20
45
60
70
80
20
45
60
70
80
% Unsupported actions
Unsupported actions
% Unsupported actions
DM Hardmax IPS
Conservative Extrapetation
Regression Extrapoiation Restriction
DR
Action Restriction
Figure 1: Learning results with varying support deficiency in the logging policy.
How do the methods perform at different level of support deficiency? Results are shown in Figure [] First, expected, learning using naive IPS degrades on both datasets as 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 have minimum reward of zero. In the rightmost column, however, we translated the rewards to [-1,0]. OJ. 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 x m)) 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 lable in the restricted policy space IT. 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, 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 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 20156).
the credit-card dataset the regression
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 plausible, since its maximum performance is limited by the available actions. For similar reasons, Conservative Extrapolation (and equivalently IPS) also flattens out, since also tightly restricts the action space by imputing the minimum reward.
7

---

Under review as a conference paper at ICLR 2020
CIFAR
Credit Card
4.% Unsupported Actions
81% Unsupported Actions
46% Unsupported Actions
80% Unsupported Actions
Acturecy
Acouracy
1100 Reewarr
Trus RENaTC
70-
60
60
0.60
6.01 005 0.10
0:25
0.61 0.05
0.16
0.25
0.01
0.10
0.23
0.46
0.01
0.10
0.23
0.46
(Million)
(Million)
Data (Million)
Bandit Data (Million)
DM Hardmaa Naive IPS
Conservative Extrapotation
Regression Extrapolation
Action Restriction
Palicy Restriction
Figure 2: Learning results with varying amounts of bandit data on CIFAR 10 and credit-card dataset.
%
Oracle
Regr. Extrap.
DM
Cons. Extrap.
SNTPS
Estimated Reward
0.0
Unsupp.
45
0,878
0.878
0.878
0.878
0.876
0.0
0.871
0.871
0.871
0.871
0.871
Grade
70
0.858
0.858
0.856
0.858
0.858
Cors. Estrapolation
77
0,856
0.854
0.854
0.856
0.856
0.2
0.855
0.855
0.855
0.838
0.849
0.0
0.1
0.4 2
0.6
Figure 3: Model selection performance on CIFARIO.
How effective are the estimators for model selection? Most learning algorithms have hyperpa- rameters, and now evaluate how the estimators perform for this secondary learning problem. We specifically focus on the parameter == U4 U2 in Policy Restriction, since it controls how much the learned policies reward of the learned policy when performing model selection with the respective estimator. Oracle the estimator that has access the full-information validation and can thus be considered 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 (..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.
step outside the region of support. The table the left of Figure shows the
DISCUSSION AND CONCLUSIONS
We identified and analyzed how off off-policy learning based on IPS weighting can suffer severely de- graded 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: re- stricting 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 leam 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. Further- more, having to store all old logging policies is inconvenient practice. This makes the approach of restricting the policy space particularly attractive, since it is computationally efficient and it does not require access the logging policy beyond the logged propensity values.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning (ICML), 2014.
Alina Beygelzimer and John Langford. The offset tree for learning with partial labels. In Pro- ceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 129-138. ACM, 2009.
Léon Bottou, Jonas Peters, Joaquin Quiñonero-Came -aaneell, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. The Journal of Machine Learning Research, 14(1):3207-3260, 2013.
Andrea Dal Pozzolo, Olivier Caelen, Reid A Johnson, and Gianluea Bontempi. Calibrating prob- ability with undersampling for unbalanced classification. In 2015 IEEE Symposium Series on Computational Intelligence, pp. 159-166. IEEE, 2015.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In International Conference Machine Learning (ICML), 2011.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, pp. 1446-1455, 2018.
Alexandre Gilotte, Clément Calauzènes, Thomas Nedelec, Alexandre Abraham, and Simon Dollé. Offline a/b testing for recommender systems. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 198-206. ACM, 2018.
Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, :(Nov): 2004.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
T. Joachims, A. Swaminathan, and T. Schnabel. Unbiased dearning-to-rant with biased feedback. In ACM Conference Web Search and Data Mining (WSDM), 2017.
T. Joachims, A. Swaminathan, and M. de Rijke. Deep learning with logged bandit feedback. In International Conference on Learning Representations (ICLR), 2018
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced re- search). URL http: www www.otto.eed/okiii//a/oo.....e.e http:///kkii/fffa........ html
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in neural information processing systems, pp. 817-824, 2008
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual- bandit-based news article recommendation algorithms. In Proceedings of the fourth ACM inter- national conference on Web search and data mining, pp. 297-306. 2C11
Lihong Li, Shunbao Chen, Jim Kleban, and Ankur Gupta. Counterfactual estimation and optimiza- tion of click metrics in search engines: A case study. In Proceedings of the 24th International Conference on World Wide Web, pp. 929-934. ACM, 2015.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. arXiv preprint arXiv: 1XX.::904.00473: 2019.
Ben London and Ted Sandler. Bayesian counterfactual risk minimization. In International Confer- ence on Machine Learning, pp. 4115-4133. 2019.
Alex Strehl, John Langford, Lihong Li, and Sham Kakade. Learning from logged implicit explo- ration data. In Advances in Neural Information Processing Systems (NIPS), 2011.

---

Under review as a conference paper at ICLR 2020
Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims. Cab: Continuous adaptive blending for policy evaluation and learning. International Conference on Machine Learning, pp. 6005-6014, 2019.
A. Swaminathan and T. Joachims. Batch learning from logged bandit feedback through counter- factual risk minimization. Journal of Machine Learning Research (JMLR), 16:1731-1755, Sep 2015a. Special Issue in Memory of Alexey Chervonenkis.
A. Swaminathan and T. Joachims. The normanorml estimator for counterfactual learning. In Neural Information Processing Systems (NIPS), 2015b.
Philip Thomas and Emma Brunskill. Data-efficient off off-policy policy evaluation for reinforcement learning. In International Conference on Machine Learning (ICML), 2016.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In International Conference on Machine Learning (ICML). 2017.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement
learning. Machine learning, 8(3-4):229-255 1992.
10

---

Under review as a conference paper at ICLR 2020
A
APPENDIX: PROOFS
In this appendix, we provide proofs of the main theorems and propositions.
A.1 PROOF OF PROPOSITION
Given contexts x P(X) and logging policy (o()) the bias of RIps for target policy π (>) is equal to the expected reward on the unsupported action sets, i.e, bias(T(To) = Ex Exeu((..o)) π (1]r:)((x (x)
Proposition 1.
Proof. Recall 8(,, v) = (2, y) |r, v/. and logged data D ~ Px x mo(-12) x Pr. bias(T (b) = [[RIPs(T)] - R(T))
Ttylx) [o())>>)
E
<o( x)
8(x, v)
Σ x(yl2)0(z,)))
(13)
mo))
E
[(yl,)((2,1)) v)
(n,
A.2 PROOF OF THEOREM
Theorem For any given hypothesis space II with logging policy To E II, there exists reward distribution P, with support in ['mins Tmaz] such that in the limit of infinite training data, ERM using IPS over the logged data 'D ~ P(X) x To(-12)) x P, can select a policy h E arg max,a Ep (R)s((T) that is at least (Tmar- Tmin) max (x(T(To) suboptimal.
Proof. For any given hypothesis space II and logging policy To, define a deterministic reward dis- tribution P, as the following: for all context x, r(z,y) 8(x, Tmin for E U(x mo) and r(x, y) = 8(x, y) = Tmaz for y E U(x, mu). Let मे E arg maxxen Dx mo)) and r E arg max, R(T), then have the following lower bound for R(T*):
R(x*) 2 R(T)
Σ Tmin]
Tmax +
(14)
(a,T))))
Tmaz max Dx mo) + r Tmin #EIf
max Dx
well
where the first inequality follows from the definition of n², the first and second equality is based on the specific reward distribution P, and the definition of न.
In the following will show that for any â learned by the expectation of ERM (or in the limit of infinite amount data), i.e., arg max Ep [
have the same support as mo-
E [ = D
Σ )E
(lyl = Tmin
[y]=)| < Tmin
(15)
for all II. then it is casy to arg max Ep [RPPs(T)). Ex [))[2) = 1 and gives that any solution of the ERM has exactly the same support no. then we have R(A) Twin for â E arg max Ep (T))
II is one of the solution of ERM. Actually for any A
Combining the lower bound for R(T=) and R(#)= = Tmin, we have
R(T²)- R(#) 2 Tmar max (T mT) + Tmin max (x(T Tmin #ell
Hell
(16)
(Tmaz Fmin) max Dx (
Rell
11

---

Under review as a conference paper at ICLR 2020
A.3 PROOF OF THEOREM 2
Theorem 2. For contexts zy drawn i.i.d from P(Z)), action drawn from logging policy no, we
define SD (o) E ((pll=,) For any policy it holds that mo(
E
E
[Sp(T + (x( =I
(10)
Proof.
Σ To(u(>) T(ylx)
E [SD(T][a)] + Dx(()(T))= 2.80TT
E
(x(()
To(y)
VE
E
Σ
[y([x)] +
Σ
(17)
yEU().)))
(E
E
Σ
=1
VEY
The first equality is based on definition of (p To) and the second equality is based on definition of support divergence.
A.4 PROOF OF PROPOSITION 3
Proposition For any given k. E (0,1), 0 < k/2, let pmin denote the minimum propen- sity under supported set Pmin maz (EM,. Tolly then with probability larger than 1 1-2exp(-2nes pminn. , the constraint t $ (D(T(mO) S 1-c will ensure 0 & (x((x))))) k.
Tolyy)),
xo(8)1 with (I y:) draw i.i.d from P(X) ()(l)) From Proof. Recall (D(T/TT) 1.2 E x(ylze))
Appendix A.3 it is easy to see (e.yy-oo(-te) m)(]) = Dx mo). Let pmin denote the smallest propensity under supported action set, Pmin = (( Tu(y(z>) > 0, then the random variable x(x(z) strictly bounded between [0, [ Applying Hoeffding'ss 's bound gives: (o()))))
((Dx(T|RO) < (p(TTTOO -e) = (PSD((TTT) [1 Dx((I < -e) s exp(- - -one p pinn)
(18)
Since SD(a)=)) $ 1 gives 1 - Sp (T) 2 0, then we have
P(Dx(T|TO) < 0) S exp( 1ine2ne Expp-2nne+ 2 pmmn))
(19)
Similar for the other direction, Hoeffding's 's bound gives:
P(Dx((T)=)) Sp(T To) + = ((SD(TT - - (T)((()))))) > e) S exp(-22n -2ne² p pmi.))
(20)
Since SD(n)m)) 2 k gives - Sp(T(=)) + 5 K, then we have
P(Dx(TTTO) 2 x) S exp( 2nee 2 pmin)
(21)
Combining the above, have
P(O ( n) = (T( < - -(Dx(()x))) > x)
(22)
2exp(-e22000 2 2
A.5 PROOF FOR EFFICIENT APPROXIMATION
Claim 1. The empirical risk defined by in Equation in D and sampling) Ro (D).
8 has the same expectation (over randomness
12

---

Under review as a conference paper at ICLR 2020
Proof.
Taking the expectation of empirical risk defined in Equation (
t Ma
π (V; (r,)
((z).
To 3/
x;)
Pj
j=1
To(
TT (
6 y)]
+
E
1
Ttyax)
0zz v)
(23)
(1x,, mo)
(E
T(ylz)((z,1)) +
Σ
<vll))(<x,1) v)]
(2
Now will show it has the same expectation with (T
B (v;
E
x(y]:;))(mt..))
To
(EM(TT))
E
(0x, v)]
Σ
((,
you To (3)
(a..ao)))))
(24)
To(y (tylx)
E
(xx +
To(y (z)
mo)
of ()
E
T(ylz)0(z,V)
T(ylr)(( v)
(E
The proof is done by comparing Equation 23 and Equation
24
A.6 PROOF OF PROPOSITION 2
Proposition 2. Given contexts I1, T1..2..... 2n drawn i.idd from the unknown distribution P(X), for action y/ drawn independently from logging policy no with probability <x()) the bias of the empirical risk defined in Equation (7) is Ex E ( v)].
Proof. From Appendix A.5
we are given the expectation ( and the bias is:
bias (T))
E
Rd
(T)) R(x))
E
Σ
π (vylo)((,,1)
Σ
{()l))8(E,11] R(T))
)o
SEM(Z,
E
Σ
( - -8xx
(25)
[(gl=)A(z.1)
(E
The second equality is from Appendix A.5 the second equality is based R(x))
E2 Eyeu(E..o)= T (v)l v) Σ Eysu(z,0o) [f)l=)((z, v)), and the last one is based on the def- inition of A(z,y) = 8(z, 3) 5(x, 2) for all X M ).
13

---

Under review as a conference paper at ICLR 2020
B APPENDIX: EXPERIMENTS
In this section, we provide the experiment details and additional results to help promote reproducibil- ity of this work.
B.I EXPERIMENT SETUP DETAILS
Datasets and baseline. We follow 75:10:15 train-validation-test split for credit card fraud detec- tion dataset, while for CIFARIO 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 CIFARIO, given supervised data {zi, y/ Ji=1 where x; denotes the 3072 features and Ve denotes the correct label of data (ranging from 9), under logging policy the logged bandit data is generated by drawing ~ To (.),)), then a deterministic reward is defined as (,.m)²)- 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 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. 22188), we adopt the conventional ResNet20 architecture but restrict training after a mere two epochs to derive relative stochastic policy, since it will be easier 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 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 57. 57.43% accuracy 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 the one used for off-policy learning where the final layer is the size the actions, specifying the reward for each action given particular context. The regression function is trained using the MSE objective.
CIFAR
Credit Card
0.025
0.050
1.002
0,020
0.025
Std. Dev
0.025
Std Dev
6.020
0.968
0.020
0.015
0.10
6.10
0.944
6.005
0.847
6.000
6.000
# Bandit Data (Million)
# Bandit Data (Million)
# Bandit Data (Million)
# Bandit Data (Millonn)
% Unsupported Actions
60%
- 70%
75%
80%
Figure 4: Behaviour of Sp(T(To) + (
B.2 SUPPLEMENTARY RESULTS
Reliability of approximating support divergence using control variate. In this experiment, we empirically verify the reliability of estimating support divergence using control variate. The tar- get policy is the uniform policy while the logging policies are varying in their support deficiency. Results averaged over 10 runs and is shown in Figure 4 We investigate the behaviour of (T(TTT)) + Dx ( ( under different number of training data and different support deficiency of the corresponding logging policy. As can see, the sum converges to I the training data
14

---

Under review as a conference paper at ICLR 2020
%
Reg.
Cons. Extrap.
Oracle
DM
SNIPS
Unsupp.
Extrap.
Estimated Reward
0.8
0
0.7934
0.793
0.793
0.793
0.793
0.6
20
0.803
0.791
0.803
0.791
0.803
45
0.799
0.798
0.799
0.795
0.798
60
0.797
0.797
0.796
0.797
0.757
Cons. Extropocation
0.787
0.787
0.780
0.771
0.754
SNIPS
Reg. Estrapolation
75
0.778
0.778
0.778
0.766
0.774
0.0
DM
80
0.774
0.759
0.759
0.751
0.759
0.1
022
6.3
k-u1-u
D4
0.
0.6
D.
0.9 1.0
Figure Model selection result for credit card fraud detection
increases. Meanwhile, the variance decreases as shown in the right figure. For different support deficiency curves, the curve converges in similar fashion and we conjecture it is due to the effect of clipping the propensity at the same threshold 0.01, which makes Pmnn 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 Similar as the trend in Figure 3 SNIPS and Conservative Extrapolation exhibit a large hias, 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 Figure 5
15


Reviews:
[{"review_id": "H1glUK7pFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers a new off-policy contextual-bandit method that can learn even when the logging policy has deficient support. Three approaches are explored, namely restricting the action space, reward extrapolation, and restricting the policy space. \n\nThis paper is well written and it considers an important problem of deficient support. However, the proposed method was only compared to a few old benchmarks. How does the proposed method compare to more recent state-of-the-art off-policy bandit approaches (Liu et al. (2019), Xie et al. (2019), Tang et al. (2019)) in the experiments? The work by Liu et al. (2019) also considered the setting of deficient support.\n\nYao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. arXiv:1904.08473, 2019.\n\nJie, Liu, Liu, Wang, and Peng, Off-Policy Evaluation and Learning from Logged Bandit Feedback: Error Reduction via Surrogate Policy. ICLR 2019.\n\nTang, Feng, Li, Zhou, and Liu, Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation, arxiv: 1910.07186, 2019.\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygT4d5oYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI would lean towards being mostly neutral in terms of acceptance. While the problem being solved is very relevant and their approach compares three different approaches to the deficient support problem, I am not sure how this work is positioned with respect to approaches solving similar problems in the reinforcement learning land. For example, Batch constrained Q-learning ([1]) restricts the set of actions that can be used, Bootstrapping Error Accumulation ([2]) and SPIBB ([3]) restrict the policy class in batch reinforcement learning. I would appreciate some comparison/positioning to such methods in the bandit setting as well. The support estimation metric and the corresponding objective (Eqn 10, 11) should also be compared and contrast with explicit divergences designed for support matching (for example, in [4]).\n\nReferences:\n[1] Off-Policy Deep reinforcement learning without exploration, Fujimoto et.al. ICML 2019\n[2] Stabilizing Off-policy Q-learning via Bootstrapping Error Reduction, Kumar et.al. NeuRIPS 2019\n[3] Safe Policy Improvement with Baseline Bootstrapping. Laroche et.al. ICML 2019\n[4] Domain adaptation with asymmetrically-relaxed distribution alignment. Wu et.al. ICML 2019", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Bkla7_u6KB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nI found a few pieces of this paper confusing. In section 3.2 it is proposed that a surrogate reward function be used for actions with unknown support, but the left hand side of the equation would seem to imply that the ratio still needs to be known in order to get an estimate. Perhaps an indicator function is missing? \n\nIt is also not made plain what assumptions are being employed in order to allow for extrapolation. From what I can tell, the authors are swapping out a positivity assumption with a smoothness assumption on the reward function. However, I don't think I see this spelled out within the text. \n\nOverall, I think this is a promising approach (the empirical results certainly bare that outO but to my eyes it lacks sufficient detail and specificity. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of learning off-policy in the contextual bandit problem, more specifically when the available data is deficient (in the sense that it does not allow to build reasonable counterfactual estimators). To address this, the authors introduce three strategies: 1) restricting the action space; 2) imputing missing rewards when lacking data; 3) restricting the policy space to policies with "enough" data. All three approaches are analyzed (statistical and computational properties) and evaluated empirically. Restricting the policy space appears to be particularly effective in practice.

Although the problem being solved is very relevant,  it is not clear how this work is positioned with respect to approaches solving similar problems in RL. For example, Batch constrained Q-learning ([1]) restricts action space, while Bootstrapping Error Accumulation ([2]) and SPIBB ([3]) restrict the policy class in batch RL. A comparison with these techniques in the contextual bandit settings, in addition to recent state-of-the-art off-policy bandit approaches (Liu et al. (2019), Xie et al. (2019)) is lacking. Moreover, given the newly added results (DR method by Tang et al. (2019)), it is not clear how the proposed approach improves over existing techniques. This should be clarified. I therefore recommend to reject this paper. 

Decision: Reject