Off-Policy Evaluation with Deficient Support Using Side Information
Authors: Nicolò Felicioni
Maurizio Ferrari Dacrema
Marcello Restelli
Paolo Cremonesi
Venue: NeurIPS 2022 Accept (2022)
Keywords: Off-Policy Evaluation
Inverse Propensity Score
Importance Sampling
Contextual Bandits
Recommendation Systems
Deficient Support

Abstract: The Off-Policy Evaluation (OPE) problem consists in evaluating the performance of new policies from the data collected by another one. OPE is crucial when evaluating a new policy online is too expensive or risky. Many of the state-of-the-art OPE estimators are based on the Inverse Propensity Scoring (IPS) technique, which provides an unbiased estimator when the full support assumption holds, i.e., when the logging policy assigns a non-zero probability to each action. 
However, there are several scenarios where this assumption does not hold in practice, i.e., there is deficient support, and the IPS estimator is biased in the general case.
In this paper, we consider two alternative estimators for the deficient support OPE problem. 
We first show how to adapt an estimator that was originally proposed for a different domain to the deficient support setting.
Then, we propose another estimator, which is a novel contribution of this paper.
These estimators exploit additional information about the actions, which we call side information, in order to make reliable estimates on the unsupported actions. 
Under alternative assumptions that do not require full support, we show that the considered estimators are unbiased.
We also provide a theoretical analysis of the concentration when relaxing all the assumptions. Finally, we provide an experimental evaluation showing how the considered estimators are better suited for the deficient support setting compared to the baselines.

Off-Policy Evaluation with Deficient Support Using Side Information
Nicolò Felicioni
Maurizio Ferrari Dacrema
Politecnico di Milano
Politecnico di Milano
nicolo www.ciiniiooolliiii.....
maurizio ftt.:aai..ferrrr.oooo.ooo.
Marcello Restelli
Paolo Cremonesi
Politecnico di Milano
Politecnico di Milano
marcello. www.oeeeeeeeeeeeeeeeeeeeeeeeelee ma
Abstract
The Off-Policy Evaluation (OPE) problem consists evaluating the performance of new policies from the data collected by another one. OPE is crucial when evaluating a new policy online is too expensive or risky. Many of the state-of-the- art OPE estimators are based the Inverse Propensity Scoring (IPS) technique, which provides an unbiased estimator when the full support assumption holds, ie., when the logging policy assigns non-zero probability to each action. However, there are several scenarios where this assumption does not hold in practice, i.c., there is deficient support, and the IPS estimator is biased in the general case. In this paper, we consider two alternative estimators for the deficient support OPE problem. We first show how to adapt estimator that originally proposed for a different domain to the deficient support setting. Then, we propose another estimator, which is a novel contribution of this paper. These estimators exploit additional information about the actions, which we call side information, in order to make reliable estimates on the unsupported actions. Under alternative assumptions that do not require full support, we show that the considered estimators are unbiased. We also provide theoretical analysis of the concentration when relaxing all the assumptions. Finally, we provide an experimental evaluation showing how the considered estimators are better suited for the deficient support setting compared to the baselines.
Introduction
Many real-world decision-making problems can be viewed through the lens of the contextual bandit framework. Some prominent examples are medical treatments [19]. recommendation systems [[5] 18
B1 48), search engines [ ad-placement systems M. and many others. In any of these problems, we have a decision-maker who repeatedly observes a context (e.g., a profile of patient), samples an action according to its policy (e.g., provides a medical treatment), and collects reward (e.g., the patient survives). Also, in many of those applications, we have access to additional information about the actions, which we call side information. For example, in movie recommendation. we may know the director and the actors of each movie 12] ; in clinical trial, we may have access to a set of characteristics of each drug [TC
While deploying and evaluating a new policy on a real system may be prohibitively expensive (if unfeasible), logged data of contextual bandit problems relatively cheap to obtain. Hence. is desirable to use them to evaluate new policies, without the need to collect new data. This problem is called Off-Policy Evaluation (OPE). this case, have data collected by given logging policy, and
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

we want to evaluate a different policy, called evaluation policy. One way to think about this problem that we are trying to answer the following counterfactual question: "What would have happened if the evaluation policy was deployed instead of the logging one?". One of the most widely employed
estimators for OPE the Inverse Propensity Score (IPS), along with its variants IPS technique tries to de-bias the collected rewards by accounting for the propensity of the logging policy. One of the reasons for the widespread adoption of the IPS estimator is that it is unbiased under the full support assumption. The full support assumption states that no action that is possible under the evaluation policy has zero probability under the logging policy. Unfortunately, we argue that this assumption is unrealistic in many real-world systems. A practical example is recommendation system that adopts a user- user-based pre-pree pre-proeessing of the items to recommend, discarding some items for given user to improve scalability. In this way, some actions (i.e., items) will never be proposed to given context (i.e., a user), violating the full support assumption. Another example is the new action problem, namely, when the action space is expanded after the logging phase. This problem is typical of many real-world use cases, such as recommendation systems [4] 29 151, 52), drug interaction evaluation [33 clinical trials [40]. etc. In general, whenever the full support assumption is not valid, we say that we have an OPE problem with deficient support. If this is the case, the IPS estimator can be highly biased [47. A possible mitigation for this issue is using a model-based approach, which means training a regression model that aims to approximate the reward function and extrapolate the rewards for the unsupported actions [5]
43 48 56, [1]. The
35 47
The drawback of this method that model
misspecification can lead to a high bias B B5 50
In this paper, focus on estimators without regression model for deficient support that exploit side information about the actions. After introducing the necessary background (Section 2) we consider two alternative estimators for Off-Policy Evaluation with deficient support in Section B] While relaxing the full support assumption, we offer alternative assumptions that hold even with deficient support. In Section 3.1 we present the Pseudolnverse estimator. This estimator was introduced by Swaminathan et al. 63 in the context of slate recommendation. We show how this estimator can be adapted to the presence of side information, and we show that is unbiased under two alternative assumptions: full support on side information and linearity. Full support on side information is a milder assumption than full support: it requires the logging policy be able to select each feature. Linearity, instead, requires that the rewards are linear combinations of the action features. This assumption is already used in other contexts, such as recommendation systems 2 and online linear bandits 2 1 In Section 3.2. we propose a novel estimator, which we call Similarity estimator. It is based on the assumption that expected rewards of similar actions are similar. Under this assumption, we prove its unbiasedness, even in the presence of deficient support. In Section B3
we relax all the assumptions and derive sample concentration inequalities of the considered estimators for deficient support and the traditional IPS to better understand the theoretical guarantees of each of them. In Section 4 we provide an experimental evaluation, showing that the considered estimators consistently outperform traditional approaches (such IPS and regression based estimators) on a worl-world dataset with deficient support from the recommendation systems domain. Finally, in we review related work, and in Section we we draw conclusions.
Section 5
Improving OPE may be beneficial to society as it allows decision makers to assess potentially dangerous policies without testing them on real system. This is even more relevant in the presence of deficient support, when there are context-action pairs that are never observed the data.
Societal Impacts
2 Background and Preliminaries
First of all, we introduce the Off- off--Poicy Evaluation (OPE) problem in the contextual bandit setting with side information the actions, and then, we describe the deficient support problem.
Off-Policy Evaluation Let x be a context sampled from a prior (unknown) context distribution over the context space X, i.e., ~ p()). An action a is sampled from a probability (called policy) over the action space A. conditioned on the observed context x, i.c., a ~ π TT-xx). After this choice, a reward r is observed from the reward distribution conditioned
the observed context and chosen
action, i.e., r ~ p(-|2, a). Without loss of generality, we consider as reward space [0, 1]. To evaluate policy, we use the policy value R(T)= == Ez-p()) Ea-r(+)a) Ey-pp- s.a) [r). It is useful to define the expected reward given context and action: 8(I, a) == Ee [r]. With this function,
2

---

can simplify the policy value formulation: R(T) Bn--() Be- (0 a)]. In this paper, we focus on the contextual bandit problem with side information about the actions. Therefore, we have access to action features, which are represented vectors: I(a) E TR for any E A. We focus on the Off- Off-Policy Evaluation (OPE) problem. We call the logging policy Tp- Therefore, the collected dataset will be in the following form: D = { dg r, To [ fi=1 where, for each i, I, ~ p(-), a, ~ (04-) and r; ~ p(-12,, a.). Given this dataset, we would like to evaluate another policy by estimating its value function. The new policy is called the evaluation policy Te. Thus, we want to find plausible estimator R(Te) using the given dataset (R(mT)) R(T D)) such that R(TT)) = R(Te). One of the most used estimators for OPE is the Inverse Propensity Score (IPS), along with its Tee (a: [m:))
variants. The IPS estimator is defined as (Te((Te) = Ei=1 ro(a: ".- A fundamental property of such estimator is that it is unbiased estimator of the evaluation policy value if the full support assumption holds [3I] Let us define supp(f) == {a f(z) > 0}, Ao(2) == supp( Too [z)), and Ac(x) == supp( (-)x)) for any x. The full support assumption is stated in the following.
Asummption 1 (Full Support). The off-policy evaluation problem satisfies the full support assumption if Ae(x) C (a()) with probability one for p(-)-
Deficient Support Whenever the full support assumption is not valid, we say that we have an OPE problem with deficient support 47. If this is the case, the IPS estimator is no longer unbiased. Let
us define the set unsupported actions for context I under Ty as Un (z, Te: To) == Ae(x) An(z). The bias of the IPS depends on this set, as illustrated by the following proposition.
Proposition
Proposition 1). In an off-policy evaluation problem, the bias of RIps(Te) is equal to the negative expected reward on the unsupported action set:
bias(Rips(Ta.)
E ammp())
Σ
Te(a(z)0(z,a)
aEUn(Z.Fe..T))
This finding is intuitive: if the unsupported set is empty (i.e., the full support assumption is valid), the IPS estimator has no bias. Otherwise, there are unsupported actions, the IPS estimator has bias caused by the blind areas in the dataset, where there are actions for which we never observe the reward.
3 Estimators for Off-Policy Evaluation with Side Information
In this section, we first introduce two estimators for a better off-policy evaluation when we have deficient support and side information about the actions, and then we provide finite-sample error bounds. The proofs of the mathematical statements can be found in Appendix A
3.1 PseudoInverse Estimator
The Pseudolnverse (PI) estimator initially proposed by Swaminathan al. 63 for the problem
of off-policy evaluation for slate recommendation (23). the following, we will show that we can an analogous estimator for the OPE problem with side information.
We begin by describing two assumptions, which are relatively mild conditions and can also hold in the presence of deficient support.
Assumption (Full Support on Side Information). The off-policy evaluation problem satisfies the full support side information if, whenever (a(a)x) 0, this implies that, for every feature of (i.e., dj E {j]f(a); > 0}) there exists an action a' E Au(x) that has the same feature (i.e., :(a'); > 0) with probability one over p(-).
We notice that this assumption can also be satisfied in the presence of deficient support, as long as the logging policy can propose each feature. Now make assumption on the reward structure. Assumption 3 (Lincarity). For each context x E X there exists an (unknown) intrinsic reward vector &2 E F such that 5(5,, a) f((aTT dr-
Intuitively, this assumption says that each action feature contributes linearly to the final reward. This assumption found applications in different fields: in recommendation systems, it constitutes the basis
3

---

of the Matrix Factorization algorithm 27. where we have fixed the latent item factors to be the feature vectors; in bandits literature, corresponds to the linear bandit formulation [2 I.]
Hence, we can view this problem as a regression problem, where we interpret the Φz vector the weight vector
learn and want to minimize the following error (for each x:): ((f(a))(((((()))))) [ff(a)"w r) The PscudoInverse estimator derives from the minimiza- tion of this error, and is unbiased under the two previously described assumptions.
Be-ro(fla)) Br=p(-(zz,a)
Theorem 1. Consider the off-policy evaluation problem where Assumptions annd hold. Then, can define an unbiased estimator Rp ( of the expected reward of the evaluation policy as:
RPI(Te)
r
s0.z. Mass;:
ri
where To == Ea PooorePeenroee pseudoimersse of a generic matrix M.
[a))[aa²] (e E RFF,, Am.. == Bawna E R., and M is the
For the details of the derivation, we refer to version of the estimator, which is biased but consistent estimator with reduced variance:
63 Inspired by [1]. we can also use Self-Normalieed
RSN-PI(Te) pr((Te)
Σ Ex=1 ofe .m: r T. Mas)) =
rt Li as sa.z, [(ss).
3.2 Similarity Estimator
In some cases, the calculation of the pseudoinverse of matrix can be computationally expensive. Thus, in the following, we propose an estimator based computationally cheaper operations, which stems from a different assumption. Such assumption comes from the recommendation systems research literature [46]. Two of the most common approaches in recommendation systems are collaborative filteri
45 and content-based filtering kld methods. Both of these methods are based on the assumption that the reward of item (i.c., action in the contextual bandit setting) given a user (i.e., a context) can be approximated by a weighted sum of rewards observed from different items given the same user. In our setting, we can define this assumption as follows:
Assumption 4. The off-policy evaluation problem satisfies the similarity assumption if. given any context x X, the following condition holds:
Bw2+ : Ac(x) Ao(x) + R. such that Ya Ao(x), 8(2,a)=
Σ
w=(a,a')o(z,
o'E
and Σ wx(a, =
e'EAn(z)
This indicates that we can approximate the reward for any action with a weighted sum of rewards observed from the actions supported by the logging policy. The weighting function should sum to one over the supported actions, and intuitively should indicate how much two actions are perceived as similar for a given context.
The aforementioned assumption is also strictly tied with the Lipschitz assumption, which is widely exploited in the research field of online bandits with side information (25 26
54
155) The
connection between the two assumptions is exhibited by the Proposition S Appendix
A
By exploiting the similarity assumption, we can get an unbiased estimator of the expected reward of the evaluation policy even with deficient support. We explain the procedure in the following.
Theorem 2. Consider the off- policy evaluation problem where the similarity assumption holds. Then, we can define an unbiased estimator Rs(Te) of the expected reward of the evaluation policy as:
1
((a))z))
is(TTa) :
Tin
no (olas
where (aal2z)) == Ba-xe(122.) [Wa; (a, a.)).

---

We notice that the meaning of the estimator is somehow intuitive. Each observed reward is divided by the propensity of the logging policy to eliminate the bias introduced by the data collection procedure (as in IPS). At the same time, it is amplified by how much, average, the evaluation policy proposes an action similar to a, for the context z;,, Given that its structure is comparable the one of the IPS, the Self- Saff-Nomallize version of the Similarity estimator is a consistent estimator under the same assumptions of Theorem
म (ac((r))
( =
aa;
To (a)
Comparison with Regression-based Estimators While this estimator does not require a regression model, we show that, from theoretical point of view, the similarity estimator has some analogies with regression-base estimator. Within this analysis, we will also see the essential differences between the two types of estimators. First, we define the simplest and most used type of regression estimator, which we call Direct Method (DM) 5
(Te)
Σ n (EAA(())
Σ
Te(a(=:)8(1,,))
where 8 is a regression model. The theoretical analysis will focus on the expected values of the estimators. To lighten the notation, will omit the distributions of the expected value whenever the expectation is with respect to the data distribution. The expected value of DM is:
E E[RDM (ma)]
x-p(() (-10( (((x,a))
E
E
Now, let analyze the expected value of the similarity estimator:
7(a'lx)
E [[R)(TT))
=
E
5(x, a²)
xmpp(-) mo
To(a'(1)
(x:)
Σ a'EAp(a)
F(a' 7(a'Iz)0(1,d))
xmppl-)
Σ
Σ
Telalz)uu (a, (000),
(from the definition of .))
amp(-)
d'E (e)
wx(a, (')o a'EAA(x))
Σ
se-p(-) (-
Therefore, notice that the similarity estimator is analogous (in expectation) regression- estimator where the regression model is 8(z, a) Eo' wz(a, (z)8(zz d'). What the similarity estimator doing is trying to overcome support deficiency by exploiting the expected reward on supported actions and the information on the similarity between supported and unsupported actions.
However, it would be erroneous think that, because of this analogy, suffices create regression- based estimator with the regression model 8(z, a) En' Aota) (a a' (')ō(z,a)) a'). The problem is that, in general, is not possible to directly estimate all the possible expected rewards 6(z, a') for any a' Ao(x) from data. Indeed, the fact that a' Ao(z) does not imply that the logging policy chose action a', but only that the probability of selecting a' was positive. This means that, in general, may have never seen pair x, a' in the dataset, and consequently, may have never observed any r ~ p(-1z, a'). Therefore, the only way to exploit the similarity assumption is via the proposed Similarity estimator.
3.3 Concentration Analysis
Up until now, we have shown that the previous estimators are unbiased under some assumptions. the following, we will analyze the concentration behavior of the Pseudoinverse, Similarity, and traditional
5

---

IPS estimators. We will also relax every assumption and investigate the dlas-nariance trade-off that arises. To do so, we provide finite-sample error bounds. In order to lighten the notation, we will drop the distributions of the expected value whenever the expectation is for (ar, a, r) ~ p(:) (-(r))p( (r a).
We will refer to the absolute value of the bias of an estimator as = E introduce two different functions to measure the difference between the conditional distributions induced by two policies. The first one is premetric called Support Divergence, introduced by Sachdeva et al. 47:
R( We
d TT)
E x>pp()
Σ
Te(a|x)
The second one the Exponentiated Rényi Divergence
[37
Te (a Tu (z)
dz(FeelTTo)
E xepp(-) (-
Now, we are ready to introduce finite-sample concentration inequalities.
Proposition 2] Let us consider a generic off-policy evaluation problem with side information. Let Rips be the IPS estimator, Rg the similarity estimator with weighting function Wz, Rei the pseudo- inverse estimator. Then, for any y E (0,1), 1), the following inequalities hold with probability at least
1 7
(2(
[TPS(TT)) R((Te) S ddup (deuP((Tell +
n1
d2( | TO)
(Rs(TT)= -((TT) Se$ +
ny
[PI((T)) (((Te) S Se + 20 In(2/7) where (aal)) = (e) a)), oΩ21 := Ez-r() Ia rt No.. 9n.z PP1
2(pp) + 12
n
3n
sup, sup, qT rt No. [a)]. and a, D no.a are defined as in Theorem
The error bounds for both the IPS and the Similarity estimators are derived following the main idea by Metelli et al. E7. particular, they provide bound for the standard IPS estimator based on a Chebyshev-like inequality using the Rényi divergence
44 The bound for the PI estimator derives after having taken the bias into account.
from Theorem 1 by Swaminathan et al. [+
We can notice how all the bounds exhibit a similar pattern. Each inequality has a component that depends on the approximation error of the estimator (doupp (Te. To), eS S.,Pt, respectively). In particular cases, the approximation error of such estimators can be zero (drupr(Re)) there full support; c 0 when the similarity assumption holds; c = 0 when there is full support on side information and the linearity assumption holds). Still, in general, we have to consider the error resulting from the possible violation of the assumptions. Furthermore, we can notice that this type of error does not decrease with the sample size n. Therefore, if present, it is an irreducible error.
0 when
On the other hand, all the bounds have a remaining component that decreases with the sample size and depends on the difference between the evaluation and logging policies. In particular, the first two inequalities display polynomial concentration (the dependence on n and is O ((vI/n7)), This bound has been proven be tight in (39 for the IPS estimator. For the third inequality, we have better behavior due to the exponential concentration (when the variance of, is small the dependence on and is O( ((n((l)))//))
Finally, we notice that the first two inequalities are very similar since the IPS estimator and the Similarity one have comparable structure, but the former depends on d2 (TT|((TT), while the latter on dz(= To)) This indicates how the Similarity estimator has an additional degree of freedom for regulating the bias-variance trade-off. Indeed, by inducing a complex but accurate म., it may decrease the bias factor e$ while increasing dz( mo). On the other hand, with simple model of म, it may reduce the de d (T)) factor, but it may incur a high bias.

---

4
Experiments
In this section, we empirically evaluate the considered estimators in an OPE problem with real logged bandit feedback. In partieular, we will show how the estimators that exploit side information are competitive in practice with traditional techniques, especially in the presence of deficient support. The code used for the experiments can be found at https:/ // thub. www.://ewwwppoliiii//ooooooooeea htwpllliimmmiiiiiiie http://ywoooo.o///eooooooeee/eea -0de--20-------d---ii----e
4.1 Setup
We mainly make use two Python packages: Open Bandit Pipeline 49 and PylEΟE 500. These
two packages are open source and freely available Open Bandit Pipeline is library with many state-of-the-art Off-Policy estimators already implemented, while PylEOE is a collection of scripts for evaluating and comparing OPE estimators.
The dataset that we use the Open Bandit Dataset (OBD), released with Open Bandit Pipeline. OBD contains logged bandit feedback from a real-world application (a large-scale fashion e-commerce platform). There are three campaigns available, namely "ALI.", "Men", and "Women". We select the "ALL." campaign. The dimension of the context vector x is 20, and the number of actions |A] = 80. Importantly, this dataset contains side information regarding the actions (inside the dataset, called action context). The action context has 4 features for each action, among which 3 categorical and one real. We discard the last one and apply one-hot encoding on the first In the end, we get a binary feature vector f(a) for each with dimension 40,
4.2 Deficient Support Evaluation
OBD consists of two separate datasets collected with two different policies: one with a uniform random policy D, {-,, a. Tay IT, (a,a; (z:) A 1 and the other with Bernoulli Thompson Sampling (BTS) policy Dos- = [ as rss Tau (a, [ New. Since both policies satisfy the full support assumption, have pre-process the data in order to simulate deficient support scenario.
Specifically, we select the random policy as the logging one (To = Ty,), and the BTS as the evaluation policy (T. Tha). Since we have a dataset collected with the BTS, we can easily compute its policy value by on-policy estimation, which we call Ron (Te( = new Σrep,.. r. We select a set of random seeds, S. We select a deficient support rate p. This rate represents the percentage of the actions that should have deficient support for each context under the logging policy.
For each random seed E S. our pre-processing algorithm proceeds follows: (i) Select a random sub-sample of n²* = 100, 000 rows from the logging dataset D,, (ii) Select p actions randomly for each context, obtaining Un(2, Te; mo); (iii) For each context ær, discard the data points (ar, a, r, To ra(a]] ()) where a E Un(x, Te, To): (iv) Modify the logged propensity for each data point: since we know that the logging policy was a uniform random, we need to set (o(a(z) = l/|A|(100% - p): (v) Now, we can use the resulting dataset to get the estimate f((m..) and get the squared error w.r.t. Ran Ron(T.) (TT). This
pre-processing protocol is summarized in Algorithm I presented in Appendix B
4.3 Hyperparameter Selection
The proposed Similarity estimator has a weighting function to be set. In the following experimental evaluation, we present two possible variants. The crucial aspect is that they both exploit side information of the actions so that we have a weighting for unsupported actions. Other weighting functions can be proposed, but leave this analysis future work.
The first proposal is have weighting function proportional to the cosine similarity among side information: wn (a,aa,') x (a, au, := f(a)² f(a')
The cosine similarity is
typical fields like recommendation systems [66] and information retrieval (53]. We scale the
weighting function such that Ed(eAo(a) wn,a. a') 1 for any E A. (in accordance with
I 'Oeen Bandit Pipeline available with Apache License 2.0: https://github. com/st tech/zr-obp
PPyIEOE available with MIT License: https: http:/huwwb.cccooooooyyyyyyl///d
7

---

10% deficient support rate
1.0
1.4
SN Sim. (cosine)
1.2
SN Sim. (cluster)
0.8
SN
Cumulative probability
MSE (95% C.I.)
DM
0.6
0.8
0.6
0.4
SN IPS
SN Sim. (cosine)
0.4
SN Sim. (cluster)
0.2
0.2
SN P1
DM
0.0
0.0
20%
40%
60%
80%
2
Deficient support rate
Squared error
Figure 1: MSE (x 109) of the estimators for each deficient support rate.
Figure 2: Cumulative Distribution Functions of the squared error (x (x10)) for 10% deficient sup- port rate.
10%
20%
30%
40%
50%
60%
70%
80%
90%
SN IPS
5.22
3.83
3.50
2.91
2.78
3.43
4.11
5.17
6.72
DM
3.60
2.60
2.14
1.65
1.43
1.32
1.51
1.60
1.73
SN PI
1.00
1.00
1.00
1.00
1.00
2.04
3.39
8.30
7.29
SN Sim. (cosine)
2.96
2.16
1.72
1.28
1.13
1.00
1.00
1.00
1.00
SN Sim. (cluster)
2.59
1.95
1.93
1.39
1.47
1.68
1.88
2.24
2.90
Table 1: CVaR2.7 with various deficient support rates. support rate, the best result is highlighted bold.
Values normalized for each deficient
Assumption 4..
In this way, the resulting म satisfies EeEA((e) {(a/z) = 1. Hence, the Self- Normalized version of the estimator is consistent under the same assumptions of Theorem! 2 61..
The second proposal is create clustering of the actions, which induces partition of A. This is done by applying K-Means Clustering [17 [4] (we set = 30) applied on the normalized action feature vectors (a)]] Let define the function c(a) that returns, for each action, its corresponding cluster. Then, we can set the weighting function wx (a, a') x 1 E c(a')) which is I if both and a' are in the same cluster, and 0 otherwise. Again, scale the weighting function such that Σo'EA((e) W2 a') = 1. This type of estimator can also be derived starting from an alternative assumption, as we show in Appendix
The choice of the similarity function is fundamental for the proposed algorithm. However, imple- menting a cross-validation procedure for selecting the similarity is not trivial. We design a possible voss-valio procedure in the presence of deficient support, and present it in Appendix [. The idea is based on simulating deficient support on the logged dataset before selecting the similarity function. Notice that, while it represents promising direction for future research, this proposal has some limitations, which we discuss in Appendix B.
4.4 Results
We repeat our bootstrap evaluation for various deficient support rates: (10% 10%), with random seeds S = {1, ...... 200), for total of 1800 different combinations. Further details on the infrastructure used and computation time can be found in Appendix B We compare three estimators (PseudoInverse, Similarity with cosine, Similarity with clustering) with the IPS baseline. We use Seff-Normalized variants for each estimator because they outperformed non- non-normalized

---

ones. As a regression braess baseline, we include the Direct Method (DM) estimator We conducted experiments with two different regression models: logistic regression and LightGBM 24 LightGBM consistently outperformed the logistic regression model; thus, we show the results obtained for DM with LightGBM. We compute the Mean Squared Error (MSE) for each deficient support rate by averaging the squared errors obtained with different seed=" Figure 1 evaluated estimators, varying the deficient support rate. From Figure II we see how the Similarity estimators dominate the IPS and the DM baselines for each deficient support rate. For a low rate (10%), the estimator with cosine similarity has more or less the same error as the IPS. Nonetheless, increasing the deficient support, the enror of IPS increases greatly, and the proposed Similarity estimators are clear winners if compared to IPS. The clustering estimator has a lower MSE with respect to the cosine one for low deficient support rates. For high deficient support rates (>50%), it has a higher error than the cosine one but is still lower with respect to IPS. Also, when we have high support deficiency, we notice that the DM estimator is preferable to the clustering one. This shows how the Similarity estimator with clustering displays a hybrid behavior between the vanilla IPS and the cosine Similarity estimator. This finding suggests that whenever we have deficient support with low rates, the clustering estimator is preferable; conversely, the one with cosine similarity performs better with high deficient support rates, Regarding the PseudoInverse, it has the best MSE up until 50% of deficient support rate. Instead, for high deficient support (higher than or equal to 70%), it displays an unstable behavior with a high variance. This effect may be caused by the violation of the full support on side information assumption, which is shown in Table 2 Appendix B
compares the MSE of the
For more interpretable evaluation, we compute the Cumulative Distribution Function (CDF) of the squared errors of the estimators for each deficient support rate, as done by, e.g..
48
61 68) The plot
of the computed CDH for deficient support rate of 10% is in Figure 2 This curve sheds light on a noteworthy aspect of the evaluated estimators, as we explain in the following. Looking solely at Figure [ we see how the MSE of the Similarity estimator with cosine is almost equal the value of the standard IPS for deficient support rate of 10%. The MSE, though, is not a desirable metric when we are in a risk-sensitive scenario M i.e., whenever we want minimize the error in the worst case. From Figure 2 we notice that, while having a similar MSE, our Similarity estimator with cosine highly preferable IPS in the worst case (IPS has a much longer tail).
For better evaluation of the worst case, we show the Conditional Value-at as- Risk, (CVaR,)) metric [1 (ar E [0, 1)). This metric computes the average error in the worst (1 a) 100% case. It is widely used in risk-sensitive applications (e.g., in financial portfolio optimization 28 191). We set 0.7 (following [S0), meaning that we evaluate the worst 30% outcomes of the squared erro The results for the various deficient support rates are shown in Table [ We can see how both Similarity variants outperform the IPS baseline, particularly when we have strong presence of deficient actions. This indicates that the Similarity estimators are suitable also in risk-sensitive applications with deficient support. The Pseudolnverse estimator has an even lower CVaRg.7 than Similarity estimators until 50% of deficient support. For higher deficient support rates, it suffers strong performance degradation. For high deficient support rates. the DM estimator has lower CVaRg.7 than the clustering one, but the best estimator is the Similarity with cosine.
5 Related Work
with stochastic rewards, which is specific instance of the more general Reinforcement Learning framework [59]. We address the Off-Policy Evaluation (OPE) problem, which consists in evaluating a new policy from data and it is related to the estimation of the average treatment effect [9 20) Several Off-Policy estimators have been proposed recently for contextual bandit logged data, as this a very active research area 58) One of the most used approaches is the Inverse Propensity Score which constitutes the heart of many other proposed state-of-the-aan These estimators all rely on the full support assumption, which
We focus on the mathematical framework of contextual bandits 60 67
logged by different policy. This problem traces its roots in causal inference (22 12
[33 [4 50 57
58
62
65
(IPS) estimator 4
estimators
[
56
IIn Appendix we include results also for the Doubly Robust (DR) estimator with both a regression- component and IPS component.
13 which is an estimator
In Appendix B we show the MSE obtained with different dataset sizes (50,000 and 150,000).
'The CDF plats for all the deficient support rates are in the Appendix
Alternative choices of can be found in Appendix B

---

we argued is challenging to obtain in a real-world application. Thus, our paper focuses on OPE with deficient support. Despite its relevance in real-world applications, this setting is not very explored in the research literature.
London and Joachims 551 suggested approach for improved OPE estimators whenever there is "new action" problem, i.e., when the action set is expanded after the logging phase. This problem is a specialization of the deficient support problem because it focuses on actions that the logging policy could not take for any context. Instead, in the deficient support scenario, the action set with no support may be different for different contexts. Therefore, our approach more general. Furthermore, they focus only on improving regression-baset estimators using theoretical tools from domain adaptation B 2T while we concentrate on estimators with no regression model.
4 are the first to address the problem of deficient support with contextual bandit feedback data. In particular, they propose three techniques for learning in this scenario. Their most successful technique is a learning method based on the IPS estimator. This means that they do not rely on regression models, as done in this paper. However, they focus only on Off-Policy Learning. Hence, their method can not be used for evaluating other policies but only for learning one. Our work, instead, proposes solutions for Off-Policy Evaluation. OPE can be the first step in learning procedure that maximizes the given estimator.
Sachdeva et al.
In the estimators proposed in this paper, use side information about the actions. Within the scope of bandits, the term "side information" " is often used with different meanings. In principle, the contextual bandit problem was called "bandit with side information" " (30) 67 distinguish it from the standard multi-armed bandit problem. In our paper, we differentiate contexts and side information about the actions: context consists of information given each round before selecting action, while the side information about the actions is known to the decision-maker and fixed for each action. This kind of side information is actively exploited in some online bandit algorithms, which make the assumption that there is a metric space on the actions with a Lipschitz distance function of the rewards
25 26
55
Our approach, instead, focuses on the offline scenario.
For the concentration analysis, we took inspiration from Metelli et al. 337 and their follow-up papers B8 39 where they analyzed the theoretical properties of the IPS-like estimators using theoretical tools from information theory, such as the Rényi divergence [44]
Conclusions
In this paper, we focused on Off-Policy Evaluation, paying special attention to the scenario where the full support assumption is violated. We presented two estimators for better evaluation by exploiting side information about the actions: one of them was an adaptation of an estimator proposed for different application domain, while the other is a novel contribution of this paper. We evaluated their theoretical guarantees under alternative assumptions without relying on full support. We also provided finite-sample concentration inequalities, relaxing all the assumptions. The experimental evaluation with real-world data showed that the estimators using side information outperform (both in the average-case and in the worst-case scenario) the traditional approaches (like IPS and regression- based estimators) in the presence of deficient support. For future work, natural direction to follow is to extend this work to the Off-Policy Learning setting by using the proposed estimators. Furthermore, presented novel estimator with hyperparameters be selected. We proposed preliminary approach for data-driven hyperparameter selection, but it comes with some limitations. Hence, further research effort in this direction is necessary.
References
[1] Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical finance, 9(3):203-222 22280022222222 1999.
[2] Peter Auer. Using confidence bounds for exploitation-exxllraiio trade-offs. J. Mach. Learn. Res., 3:397-422, 2002.
[3] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. theory of learning from different domains. Mach, Learn., 79(1-2): 151-175, 2010.
10

---

[4] Cesare Bernardis and Paolo Cremonesi. Nfc: cold-start recommendation. User Modeling and User-Adapted Interaction, pages 1-34, 2021.
deep and hybrid item-based model for item
[5] Alina Beygelzimer and John Langford. The offset tree for learning with partial labels. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, June 28- July 1, 2009, pages 129-138. ACM, 2009.
[6] Aurélien Bibaut, Ivana Malenica, Nikos Vlassis, and Mark van der Laan. More efficient off- policy evaluation through regularized targeted learning. In Proceedings of the 36th International Conference on Machine Learming, ICML 2019, 9-15 June 2019, volume 97 of Proceedings of Machine Learning Research, pages 654-663, PMLR, 2019.
[7] Ella Bingham and Heikki Mannila. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 245-250, 2001.
[8] Lorenzo Bisi, Luca Sabbioni, Edoardo Vittori, Matteo Papini, and Marcello Restelli. Risk- averse trust region optimization for reward-volase volatility reduction. In Proceedings of the Twenty- Ninth International Joint Conference Artificial Intelligence, IJCAI 2020, pages 4583-4588 ijcai.org, 2020.
[9] Léon Bottou, Jonas Peters, Joaquin Quiñonero Candela, Denis Xavier Charles, Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Y. Simard, and Ed Snelson. Counterfactual reasoning and learning systems: the example of computational advertising. J. Mach. Learn. Res., 14(1): 3207-3260, 2013.
[10] Cynthia Brandt, Richard Morse, Keri Matthews, Kexin Sun, Aniruddha M. Deshpande, Rohit Gadagkar, Dorothy B. Cohen, Perry L. Miller, and Prakash M. Nadkarni. Metadata-driven cre- ation of data marts from eav-modeled clinical research database. Int. J. Medical Informatics, 65(3):225-22 241, 2002.
[11] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In 21 Annual Conference Learning Theory- COLT 2008, July 9-12, 2008, pages 355-366. Omnipress, 2008
[12] Yashar Deldjoo, Mihai Gabriel Constantin, Bogdan Ionescu, Markus Schedl, and Paolo Cre- monesi. MMTF-14K: multifaceted movie trailer feature dataset for recommendation and retrieval. In ACM MMSys 2018, June 12-15, 2018, pages 450-455, 2018.
[13] Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, June 28 July 2, 2011, pages 1097-1 1104. Omnipress, 2011.
[14] Miroslav Dudik, Dumitru Erhan, John Langford, and Lihong Li. Doubly robust policy evaluation and optimization. Statistical Science, 29(4):485-511 2014.
[15] Nicolò Felicioni. Enhancing counterfactual evaluation and learning for recommendation systems. In RecSys '22: Sixteenth ACM Conference on Recommender Systems, September 18 23, 2022, pages 739-741. ACM, 2022.
[16] Maurizio Ferrari Dacrema, Simone Boglio, Paolo Cremonesi, and Dietmar Jannach. A troubling analysis of reproducibility and progress in recommender systems research. ACM Trans. Inf. Syst. 39(2), January 2021.
[17] Edward W Forgy. Cluster analysis of multivariate data: efficiency versus interpretability of classifications. biometrics, 11:768-769, 1965.
[18] 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, WSDM 2018, February 5-9, 2018, pages 198-206. ACM, 2018
[19] Jinyong Hahn. On the role of the propensity score in efficient semiparametric estimation of average treatment effects. Econometrica, pages 315-331, 1998.

---

[20] Keisuke Hirano, Guido W Imbens, and Geert Ridder. Efficient estimation of average treatment effects using the estimated propensity score. Econometrica, 71(4):1 2003.
[21] Hal Daumé III and Daniel Marcu. Domain adaptation for statistical classifiers. J. Artif. Intell. Res., 101161,, 2006.
[22] Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge University Press, 2015.
[23] Ray Jiang, Sven Gowal, Yuqiu Qian, Timothy A. Mann, and Danilo J. Rezende. Beyond greedy ranking: Slate optimization via list-cvae. In 7th International Conference on Learning Representations, ICLR 2019, May 6-9, 2019. OpenReview.net, 2019.
[24] Guolin Ke, Qi Meng. Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems 30: Anmual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, pages
2017.
[25] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, May 17-20, 2008, pages 681-690. ACM, 2008.
[26] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. J. ACM, 66(4):30:1 2019.
[27] Ychuda Koren, Robert M. Bell, and Chris Volinsky, Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009.
[28] Pavlo Krokhmal, Jonas Palmquist, and Stanislav Uryasev. Portfolio optimization with condi- tional value-at-risk objective and constraints. Journal of risk, 4:43-68, 2002.
(29] Xuan Nhat Lam, Thuc Vu, Trong Due Le, and Anh Duc Duong- Addressing cold-start problem in recommendation systems. In Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication, ICUIMC 2008, January 31 February 01, 2008, pages 208-211. ACM, 2008.
[30] John Langford and Tong Zhang. The epoch-greeds algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference Neural Information Processing Systems, December 3-6, 2007, pages 817-824, Curran Associates, Inc., 2007.
[31] Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of -aandtt news article recommendation algorithms. Proceedings of the Forth International Conference on Web Search and Web Data Mining, WSDM 2011, February 9-12, 201 pages 297-306. ACM, 2011.
[32] Lihong Li, Shunbao Chen, Jim Kleban, and Ankur Gupta. Counterfactual estimation and optimization of click metries in search engines: A case study. In Proceedings of the 24th International Conference on World Wide Web Companion, WWW 2015, May 18-22, 2015 Companion Volume, pages 929-934. ACM, 2015.
[33] Zun Liu, Xing-Nan Wang, Hui Yu, Jian- Yu Shi, and Wen-Min Dong. Predict multi-type drug-drug interactions in cold start scenario. BMC bioinformatics, 23(1):1-13, 2022.
[34] Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2): 1982.
[35] Ben London and Thorsten Joachims. Offline policy evaluation with arms. In Offline Reinforcement Learning Workshop at Neural Information Processing Systems, 2020.
[36] Pasquale Lops, Marco de Gemmis, and Giovanni Semeraro. Content-based recommender systems: State of the art and trends. In Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor, editors, Recommender Systems Handbook, pages 73-105. Springer, 2011.
12

---

[37] Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy opti- mization via importance sampling. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, pages 5447-5459, 2018.
[38] Alberto Maria Metelli, Matteo Papini, Nico Montali, and Marcello Restelli. Importance sampling techniques for policy optimization. J. Mach. Learn. Res., 21:111:11114 2020.
[39] Alberto Maria Metelli, Alessio Russo, and Marcello Restelli. Subgaussian and differentiable importance sampling for off-policy evaluation and learning. In Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 641,, 2021, pages 81 19 8132, 2021.
[40] Huseyin Naci and Alec B O' C'Cnnor. Assessing comparative effectiveness of new drugs before approval using prospective network meta-analyses. Journal of clinical epidemiology, 66(8): 812-816, 2013.
[41] Sandeep Pandey, Deepak Agarwal, Deepayan Chakrabarti, and Vanja Josifovski. Bandits for taxonomies: A moodel-based approach. In Proceedings of the Seventh SIAM International Conference on Data Mining, April 26-28, 2007., pages 216-227. SIAM, 2007.
[42] Judea Pearl. Causality. Cambridge university press, 2009.
[43] Doina Precup. Richard S. Sutton, and Satinder P. Singh. Eligibility traces for off off-policy policy evaluation. In Proceedings of the Seventeenth International Conference on Machine Learning (/0M), June 29 July 2, 2000, pages 759-766. Morgan Kaufmann, 2000.
[44] Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume I: Contributions to the Theory of Statistics, volume pages 547-562. University of California Press, 1961.
[45] Paul Resnick. Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, and John Riedl. Grouplens: An open architecture for collaborative filtering of netnews. In CSCW '94, Proceedings of the Conference Computer Supported Cooperative Work, October 22-26, 1994, pages 175-186. ACM, 1994.
[46] Francesco Ricci, Lior Rokach, and Bracha Shapira, editors. Recommender Systems Handbook. Springer, 2015. ISBN 978- 1-4899-76336-
[47] Noveen Sachdeva, Yi Su, and Thorsten Joachims. Off-policy bandits with deficient support. In KDD 20: The 26th ACM SIGKDD Conference Knowledge Discovery and Data Mining, August 23-27, 2020, pages 965 975-975.44 ACM, 2020.
[48] Yuta Saito and Thorsten Joachims. Counterfactual learning and evaluation for recommender systems: Foundations, implementations, and recent advances. In RecSys '21: Fifteenth ACM Conference on Recommender Systems, 27 September 2021 October 2021, pages 828-830.
ACM, 2021.
[49] Yuta Saito, Shunsuke Aihara, Megumi Matsutani, and Yusuke Narita. Open bandit dataset and pipeline: Towards realistic and reproducible off-policy evaluation. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks NeurIPS Datasets and Benchmarks 2021, December 2021, 2021.
[50] Yuta Saito, Takuma Udagawa, Haruka Kiyohara, Kazuki Mogi, Yusuke Narita, and Kei Tateno. Evaluating the robustness of off-policy evaluation. In RecSys '21: Fifteenth ACM Conference on Recommender Systems, 27 September 2021 - October 2021, 1, pages 1 114-123, ACM, 2021.
[51] Andrew I. Schein, Alexandrin Popescul, Lyle H. Ungar, and David M. Pennock. Methods and metrics for cold-start recommendations, In SIGIR 2002: Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, August 11-15, 2002, pages 253-2601 ACM, 2002.
13

---

[52] Sulthana Shams, Daron Anderson, and Douglas J. Leith. Cluster-based bandits: Fast cold- start for recommender system new users. In SIGIR '21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, July 11-15, 2021, pages 1613-1616. ACM, 2021.
[53] Amit Singhal et al. Modern information retrieval: brief overview. IEEE Data Eng. Bull., 24 (4):35-43, 2001. 2001.
[54] Aleksandrs Slivkins. Contextual bandits with similarity information. J. Mach. Learn. Res., 15 (1):2533-2568, 2014.
[55] Aleksandrs Slivkins, Filip Radlinski, and Sreenivas Gollapudi. Learning optimally diverse rankings over large document collections. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), June 21-24, 2010, pages 983-990. Omnipress, 2010.
[56] Alexander L. Strehl, John Langford, Lihong Li, and Sham M. Kakade. Learning from logged implicit exploration data. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, pages 2217-2225, 2010.
[57] Yi Su, Lequn Wang, Michele Santacatterina, and Thorsten Joachims. CAB: continuous adaptive blending for policy evaluation and learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, volume 97 of Proceedings of Machine Learning Research, pages 6005-6014. 4. PMLR, 2019.
[58] Yi Su, Maria Dimakopoulou, Akshay Krishnamurthyy and Miroslav Dudik. Doubly robust off-policy evaluation with shrinkage. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, volume 119 of Proceedings of Machine Learning Research, pages 9167-9176. PMLR, 2020.
[59] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[60] Adith Swaminathan and Thorsten Joachims. Counterfactual risk minimization: Learning from logged bandit feedback. In Proceedings of the 32nd International Conference on Machine Learn- ing. ICML 2015, 6-11 1 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 814-823. JMLR M.g.. 2015.
[61] Adith Swaminathan and Thorsten Joachims. The self-normalized estimator for counterfactual learning. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, pages 3231-3239, 2015.
[62] Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. J. Mach. Learn. Res., 16:173 1-7755 2015.
[63] Adith Swaminathan, Akshay Krishnamurthy, Alekh Agarwal, Miroslav Dudík, John Langford, Damien Jose, and Imed Zitouni. Off Off-policy evaluation for slate recommendation. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, pages 3632-3642, 2017.
[64] Philip Thomas. Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-policy evaluation. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, pages 3000-3006. AAAI Press, 2015.
[65] Aaron David Tucker and Thorsten Joachims. Variance-optimal augmentation logging for counterfactual evaluation in contextual bandits. CoRR, abs/2202.01777 2022.
[66] Nikos Vlassis, Aurélien Bibaut, Maria Dimakopoulou, and Tony Jebara. On the design of estimators for bandit off- policy evaluation. In Proceedings of the 36th International Conference on Machine Learning, ICML 20/9, 9-15 June 2019, volume 97 of Proceedings of Machine Learning Research, pages 6468-6476 PMLR, 2019.
(67] Chih-Chun Wang, Sanjeev R Kulkarni, and H Vincent Poor. Bandit problems with side observations. IEEE Transactions Automatic Control, 50(3):338-33 2005.
14

---

[68] Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudík. Optimal and adaptive off off-policy evalua- tion contextual bandits. In Proceedings of the 34th International Conference on Machine Learning, ICMI. 2017, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 3589 -5977. PMLR, 2017.
[69] Shushang Zhu and Masao Fukushima. Worst-case conditional value-at-risk with application to robust portfolio management. Operations research, 57(5):1155-116 2009.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section o
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the final part of Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A
3. If you ran experiments..
http://ecsyspoommmmmecma ips 2022-0222-222 ope- side- info (a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes] See Appendix and
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section 4 and Appendix [
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix B
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Section
(b) Did you mention the license of the assets? [Yes] See Section
(c) Did you include any new assets either in the supplemental material or URL? [Yes] Code available at heurips- 200--2022-ppss- spdd--opesiddein--
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] See Appendix B
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] See Appendix B
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "kL_pNtiAYdP", "reviewer": "Reviewer_4Ega", "summary": "The paper looks at the problem of off-policy evaluation where the subset-support assumption is violated. Roughly speaking, the idea to get around the support issue is by estimating rewards for the actions (that may never be seen under the logging policy) using the rewards of the logged actions. For instance, prior methods assume rewards to be parametric (linear) function of action features which allows estimating rewards for the unseen actions using ordinary linear regression. In contrast, the proposed work makes an assumption that allows inferring rewards for the unseen action using a non-parametric/kernel regression. When the assumptions hold exactly, these estimators are unbiased. Empirically, the proposed estimator seems to perform better than the baseline methods when the support is very deficient. \n", "questions": "1\\. Line 39: The verbose description of “full support” makes it read like the logging policy needs a non-zero chance of taking every action.  I would recommend making it clear that the logging policy needs a non-zero chance of taking every action _that is possible under the evaluation policy_.\n\n\n2\\.Line 157: Does $w$ not require any constraints at all? Quick eyeballing suggests that it might be required that $w>=0$ and that $\\sum_{a}w(a,a’)  = 1$ for all $a’$. Without this it seems like $\\bar \\pi$ in Theorem 2 may not result in a valid probability distribution and subsequently Renyi divergence for it may become ill-defined in Proposition 2?\n\n3\\. Similarity estimator: Is importance sampling necessary? Given that an estimator of rewards can be constructed from Assumption 4, is it not possible to explicitly compute the expectation under the evaluation policy $\\pi$?   \n\n$\\frac{1}{n}\\sum_{i=1}^n \\sum_a \\pi(a|x_i) \\delta(x_i, a)$\n\nI can see one argument about minimizing compute time, but I guess sample efficiency is more important for OPE than compute. Further,\n\n (a) Given that the utility of this method is for large action sets, $pi_0(a|s)$ in the denominator is likely going to have some very small values that may blow up the variance of the estimator relative to explicitly computing the expectation,\n(b) Looks like $w$ in the experiments do not depend on $x$. Further, the action set is discrete. These can make explicit computation of the expectation easier?\n(c) One could investigate various ways of reducing computation time for directly estimating the expectation, for e.g., use normalized w values to develop sampling based procedure for estimating $\\delta(x,a)$\n\n4\\. Paper would be stronger if more ablations with different choice of feature vectors (random-projection, cosine basis, etc.) are presented to help the baseline. Doing linear regression on one-hot encoding feels naive.\n\n5\\. Paper would also benefit from having ablations on the impact of dataset size on the estimators.\n\n6\\. Choosing similarity metric $w$ (or even the underlying feature) appropriately is important for the proposed algorithm to work well. Given that reward function estimation can be reduced to supervised-learning, it would be nice to have a cross-validation procedure for both the baseline and the proposed method implemented while discussing the usefuleness of the results.\n \n7\\. Section 4.3: Looks like $w_x$ does not depend on $x$ at all? That does not seem like a good choice in general.\n\n8\\. Not sure if I understood the normalization process used in Table 1.\n", "limitations": "Discussed above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength \n\n- The problem may be of interest to a wider audience.\n- Natural idea with a clear presentation.\n\nWeakness\n\n- There may be immediate ways to improve the proposed estimator under the assumptions being made.\n- Paper could benefit from more thorough empirical investigation\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "evinNrVXG2I", "reviewer": "Reviewer_yZ68", "summary": "This paper studies the off-policy evaluation problem under deficient support, which is a common scenario in industrial settings where action space is large or new actions are added over time. This setting is challenging as the original IS estimator is biased and unreliable. Two estimators are introduced in this setting, which exploit the side information (or action information), and shows different level of bias-variance trade-off. One is based on the pseudo-inverse estimator (PI), which initially designed for the OPE for slates, here basically the idea is to view each feature of the action as a ''slot'', and under the linearity assumption of the reward as well as the coverage on the feature space, the PI gives unbiased estimate. The second estimator is based on action similarities, basically assumes each reward for unsupported actions could be represented by the weighted averages of the rewards of similar actions. Empirical studies based on real-world datasets show better performance (in terms of MSE and CVaR) compared with original self-normalized IPS.", "questions": "Please see the Weakness section, and I am willing to adjust my score if they are properly addressed.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The paper studies an important problem in the off-policy evaluation literature, i.e., the violation of full-support assumption. Most prior works assume full-support, which is a strong assumption in real-world applications. This paper takes a close look on the problem and discusses new efficient estimators, that based on mild assumptions, such as full-support not in the combinatorial action spaces, but in the feature space, which also shows better empirical performance.\n\n2. I do like the paper's perspective of reducing the combinatorial sense of full support sense in the support over the action features, which draw a nice connection in the slate literature. \n\n\nWeakness:\n\n1. I am concerned about the applicability of these methods. For PI estimator, it seems highly rely on the discrete features of the action, and the linear assumption of the reward, which seems a reasonable assumption for slate, but seems not the case for the reward for each individual action over features. \n\n2. The similarity estimator seems like the regression-based estimator, which requires extrapolation and generalization (depends on to define the weighting function). It would be great if the authors add more discussion along this line. This is indeed match the experiment result, as we do see better performance of the similarity estimator as the support divergence increases.\n\n3. The only baseline in the empirical results is the self-normalized IPS estimator, in which it is OK if this paper only considers the weighting based approach. However, the proposed similarity estimator shares a lot of similarity with the model-based approach, then it is great if the paper could add more baselines based on the model based approach. \n\n4.  Empirically, it would be also great to add more results in terms of bias, variance to further understand the trade-off of the estimators. ", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ZaxrWSlRI4g", "reviewer": "Reviewer_p8Mu", "summary": "This paper proposes two algorithms for off-policy evaluation in the presence of actions with no support in the observational data. The first algorithm is adapted from [1] and assumes a parametric decomposition of the expected reward, whereas the second algorithm leverages an action similarity assumption. The authors provide finite sample error guarantees for the two methods (as well as for the state of the art) and  a comprehensive empirical evaluation. \n\n[1] Ray Jiang, Sven Gowal, Yuqiu Qian, Timothy A. Mann, and Danilo J. Rezende. Beyond greedy ranking: Slate optimization via list-cvae.  ", "questions": "Taken from the above section:\n\n* Why are the action features only binary? What changes in the implementation/ theoretical results if the features are continuous?\n* Can the weights matrix for the Similarity algorithm be learned rather than assumed?", "limitations": "The authors have adequately addressed and potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n* This is a well written paper in a not well studied area of OPE\n* The presentation is clear and concise\n* The experimental study is compelling\n\n**Weaknesses**\n* The study is limited to binary features only, with no clear explanation as to why\n* The structure of the weights matrix in the Similarity algorithm is assumed (e.g. cosine similarity) rather than learned . Given that the linearity in reward (Assumption 4) is pretty strong, is it possible to instead learn the weighting scheme? \n* There is no guidance on which of the two methods to use (depending on the scenario). These methods display different behaviors in the experiments section. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FeS6d9mKZTA", "reviewer": "Reviewer_nksT", "summary": "This paper addresses the problem of performing off-policy evaluation using inverse propensity weighting when there are zero probability actions with respect to the logged policy. To address this, the authors provide two alternative assumptions that can be employed to find valid off-policy estimates: positivity under side information and linearity with respect to action features. After employing these, the authors show that previously proposed estimators for off policy evaluation in slate recommendation can be used for off policy evaluation. An additional nearest neighbor style estimator is also provided.", "questions": "* Do the authors have thoughts on how a practitioner could test for violations to the assumptions proposed here?\n* How does the proposed estimators compare to an outcome model? The similarity model, in particular seems nearly identical to an outcome model. It would be helpful if the authors could include some discussion on this.", "limitations": "Limitations are well addressed by the authors.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* This is a very challenging and relevant problem. Positivity violations can occur frequently in practice and there is currently no good options for dealing with this issue in the weighting context.\n* Simplicity: the authors clearly lay out the challenge and the solution in a way that makes plain what is required to gain identifiability. \n* Strong empirical performance. \n\nWeaknesses:\n\n* The main weakness here is that both assumptions are essentially untestable. \n* There are a number of hyper-parameters, it is unclear how practitioners should set these in practice.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept