Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 

[1] Ray Jiang, Sven Gowal, Yuqiu Qian, Timothy A. Mann, and Danilo J. Rezende. Beyond greedy ranking: Slate optimization via list-cvae.  
strengths_and_weaknesses: **Strengths**
* This is a well written paper in a not well studied area of OPE
* The presentation is clear and concise
* The experimental study is compelling

**Weaknesses**
* The study is limited to binary features only, with no clear explanation as to why
* 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? 
* 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. 
questions: Taken from the above section:

* Why are the action features only binary? What changes in the implementation/ theoretical results if the features are continuous?
* 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 

strengths_and_weaknesses: Strength 

- The problem may be of interest to a wider audience.
- Natural idea with a clear presentation.

Weakness

- There may be immediate ways to improve the proposed estimator under the assumptions being made.
- Paper could benefit from more thorough empirical investigation

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_.


2\.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?

3\. 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$?   

$\frac{1}{n}\sum_{i=1}^n \sum_a \pi(a|x_i) \delta(x_i, a)$

I can see one argument about minimizing compute time, but I guess sample efficiency is more important for OPE than compute. Further,

 (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,
(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?
(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)$

4\. 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.

5\. Paper would also benefit from having ablations on the impact of dataset size on the estimators.

6\. 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.
 
7\. Section 4.3: Looks like $w_x$ does not depend on $x$ at all? That does not seem like a good choice in general.

8\. Not sure if I understood the normalization process used in Table 1.

limitations: Discussed above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

* 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.
* Simplicity: the authors clearly lay out the challenge and the solution in a way that makes plain what is required to gain identifiability. 
* Strong empirical performance. 

Weaknesses:

* The main weakness here is that both assumptions are essentially untestable. 
* There are a number of hyper-parameters, it is unclear how practitioners should set these in practice.
questions: * Do the authors have thoughts on how a practitioner could test for violations to the assumptions proposed here?
* 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strength:

1. 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.

2. 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. 


Weakness:

1. 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. 

2. 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.

3. 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. 

4.  Empirically, it would be also great to add more results in terms of bias, variance to further understand the trade-off of the estimators. 
questions: Please see the Weakness section, and I am willing to adjust my score if they are properly addressed.
limitations: Yes.
review_title: null

Meta-review: metareview: The reviewers all appreciate the direction of this work, and while the merits and significance of the work have limitations -- as reflected in the weak but positive scores -- all reviewers were positive and found no reason to reject. I agree with this and recommend acceptance on the basis that the merits of the contribution and having this as part of the program outweigh the concerns regarding significance. That said, I strongly encourage the authors to use the detailed feedback from the reviewers to improve their paper.
confidence: Less certain
Decision: Accept