Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, authors have introduced an overfitting phenomenon that has not been addressed in previous works related to policy optimization and importance sampling. They then propose a new constraint on policy and a new algorithm which avoids the overfitting. They have provided theoretical justification on why their proposed method works and show experimental results to show the effectiveness of their approach.
main_review: 

- One major issue with the proposed approach is the expressivity of the policy class. Although authors in Theorem 2 have shown that asymptotically, the expressivity stays the same, one question here is that what really happens in the non-asymptotic setting and how much we loose expressivity with the introduced constraint.

- In other words, the reviewer believes one missing part of this paper is to show how much local constraints on actions (eq. 5) is hurting the performance in the non-asymptotic setting. How does this loss change as sample size grows? Showing empirical results even on synthetic datasets will be helpful.

- One issue with Table 1 is that authors say their approach does not make any Markovian assumption and hence, its performance is worse than other competitors in the MDP setting while it outperforms other methods in the non-MDP setting. One question here is that is this comparison fair? In other words, do other methods make Markovian assumption and at the same time we expect them to perform well in a non-MDP setting?

- The writing of the paper needs a major review. Examples are but not limited to:

Page 1, Introduction Section: “different than”
Page 2, line 2: : “learning an policy”	
Page 2, Section 2, Line 6: “over next context”
Page 2, Section 2: “also sometimes refered”
Page 3, Section 3: “but a similar results”
Page 3, Section 3: “for unnormalized estimator.”
Page 5, Section 4: “function class is closed respect”
Page 7, Section 6: “Euclidean distance in over”
Page 7, Section 7: “details are provided are in the Appendix”
Page 7, Section 7: “The reward consist of”
Page 9, Section 8: “in a policy that under-weigh certain (lower performing) initial contexts”

summary_of_the_review: This paper introduces a legit overfitting issue and proposed a solution for it. However, the reviewer is not convinced enough about the effectiveness of the proposed approach due to the concerns raised in the main review plus the fact that the paper needs a major writing revision.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: When optimizing an policy under batch data under importance weighting adjustment of batch data, this paper observes that methods can learn to ignore states with highly negative rewards by having lower support to the behavior policy. And this paper proposes to solve this problem by only constraining actions that have observed in the nearby states in the batch data. Although various similarly ideas have been proposed like regularizing toward behavior policy, this paper improves on importance sampling methods that does not assume MDP that separates itself from recent baselines like PQL. They also show some analysis on this problem. They show that compared to recent baselines they improve in a tumor growth simulation environment when MDP assumption is violated, and a real-world sepsis dataset.
main_review: I find the proposed method of this paper is quite intuitive and the baselines compared seem to be appropriate. The Example 1 is good to understand with more motivating examples in the appendix. I also love the clinically-inspired evaluations.

My concerns are as followed:
1. Regarding the methods
  - A) This phenomenon seems to only apply when highly negative reward are present. One way is to shift and scale the rewards to be positive, and capped the importance weights to avoid over-maximize the reward. I am curious if authors can compare with this method, or at least illustrate why this way of shifting reward will not work.
  - B) The distance considered in the paper uses the euclidean distance in the raw input space, which may not work when lots of missingness present in the data, or in settings when some features of the inputs are not relevant to the reward. I think learning a meaningful latent space that depends on the reward like [1] could further improve this method.
  - C) The novelty of this work is not high as similar ideas have been proposed but not particularly in the non-MDP setting as acknowledged by the authors.


2. Regarding the experimental results
  - A) Although it's intuitive that this overfitting phenomenon could happen theoretically, only qualitative figures in Fig. 1(b) support this claim. I believe it's crucial to support this statement in the experiments. I think authors can quantify it in both simulations and the MIMIC3 by showing that the importance weights are close to 0 for the baselines in lower-reward states.
  - B) Since you use WIS as the validation metric, it might favor methods also optimized under IS-based methods but might give an disadvantage to non-IS based methods like PQL. Though I understand you have to choose a metric.
  - C) In Fig. 1(a) why there is no blue point around x=200~400? Just want to see if blue actually is better in those regions.

3. Regarding the presentations (this has little effect on my evaluation)
  - A) Bolding table 1 and 2 can help readers quickly understand which method is better
  - B) In Sec. 3 please list the source of equation (2). 

[1] Zhang, Amy, et al. "Learning Invariant Representations for Reinforcement Learning without Reconstruction." International Conference on Learning Representations. 2020.
summary_of_the_review: Pros:
+ The method is easy and simple and shows improvement in both experiments that include non-MDP simulations and a real-world dataset
+ The writing is mostly clear
+ The improvement shown in a real-world clinical environment is encouraging.

Cons:
- No quantitative analysis if the overfitting actually happens.
- Simple heuristics like shifting rewards to be positive and avoiding over-maximizing reward is not compared
- The novelty of this work seems limited since similar ideas have been proposed. 
- The distance considered in this paper may not handle missingness or when some input features are irrelevant to the reward.

Although I feel the proposed overfitting phenomenon can be an interesting contribution, the authors should quantify if it happens in the experiments and justify their method by comparing with heuristics like shifting the reward. I think addressing these can further push the paper over the acceptance bar.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers offline policy optimization. The author(s) discussed the issue of overfitting of the importance weights in existing offline algorithms and developed an algorithm to alleviate the issue. Results are supported via theories and real datasets from healthcare applications. 
main_review: Major comments:

* In Section 3, the author(s) decomposed the importance sampling estimator into three parts and argued that the second term can be problematic. I suggest the author(s) to design a toy simulation example to evaluate the order of magnitude of these three error terms (the first error term being $E_{\hat{p}} v^{\pi}(x) - E_{p} v^{\pi}(x)$ where $p$ corresponds to the oracle context distribution).  

* In Equations (3) and (4), suppose we plug-in the empirical behavior distribution for $\mu$, then $\hat{p}(x)$ equals $W(x)$. This would solve the over-fitting problem. In practice, according to the semiparametric theory, even if the true importance sampling ratios are known to us, the resulting estimator with an estimated ratio would be more efficient (see e.g., Tsiatis, 2006, Semiparametric Theory and Missing Data). Would you please clarify why you did not use such a simple method with an estimated importance sampling ratio?

* Would you please elaborate the constraint in Equation (6)? Why would such a constraint help solve the offline learning problem? 

* The condition $|\Pi|<+\infty$ is not sufficient to guarantee the validity of Theorem 2. As shown in the proof, $|\Pi| \delta_n$ shall decay to zero. The author(s) needs to provide an upper bound for $\delta_n$ in the proof (as a function of M and $n$) and presents the corresponding condition for $|\Pi|$. In addition, naively apply the Bonferroni's inequality would give a loose bound. Concentration inequalities would be preferred to relax the resulting condition for $|\Pi|$. 

* The proposed algorithm relies on several tuning parameters, such as $\delta$, $M$, $\lambda$ and $\alpha$. Is your algorithm sensitive to the choice of these tuning parameters? How would you recommend practioners to select these hyper-parameters? Could cross-validation be possibly employed? In addition, what policy class do you consider in the numerical experiments?

* Just curious how the proposed compares with existing baselines in standard openAI Gym environment. Have you conducted some related experiments? 

* Since the numerical experiments use policy evaluation algorithms to compare different policies, I wonder if the estimated values are sensitive to the choice of the policy evaluation algorithm or the tuning parameters used in the algorithm. Would you please discuss? 

Minor comments:

* Page 3, Line -12. Shall $hatp(x)$ be $\hat{p}(x)$? 
* Page 4, Lines -17 and -18. Missing parentheses in $E [ ... ]$.
* Page 6, Theorem 2. $M$ as a function of $n$?
* Page 13, Line -14. "to be" -> "be". 
summary_of_the_review: My detailed comments are given under the "Main Review" section. I have some concerns about the motivation of the method (#2), the theoretical results (#4), the choice of the tuning parameters (#5) and the sensitivity of the estimated values in the empirical studies to the choice of the policy evaluation algorithms (#6). So I give a score of 5. However, I would like to increase my score shall my comments be addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the overfitting issue in counterfactual policy learning. The paper first  identifies an important overfitting phenomenon in optimizing the importance weighted return, and proposes an algorithm to avoid the issue. The notable limitation of some previous approaches is that they use penalization at the policy level and do not directly address the problem with avoiding contexts with low reward. The proposed POELA method addresses deficient support in the observed finite data rather than in the expected behaviors.  Some experiments show the benefit of the proposed approach.
main_review: **Strengths**
- the paper tackles the important and relevant issue of overfitting in counterfactual risk minimization. the motivation is also nicely supported with some toy examples.
- the paper identifies the source of overfitting that is not addressed in previous works.
- the paper proposed a novel algorithm to address the overfitting issue with some gurantees  
related work is covered rigorously 
- the code is provided as supplementary material. I encourage the authors to publicize it upon publication to ensure the reproducibility

**Weaknesses**
- I skimmed through the proofs of Theorem 1 and Corollary 1. They look correct, but the bounds seem very loose and might be meaningless. It would be more interesting to see how the empirical sum of weights are different among different methods using synthetic data. 
- All experiments are based on real-world data, meaning that the policy performances are now measured with OPE on a test set, which might not be accurate. Having synthetic experiments as a complement would strengthen the empirical contribution.
- Do we still observe the overfitting issue when we use k-fold cross validation?

summary_of_the_review: The paper identifies the unexplored aspect of the overfitting issue in off-policy learning. The motivation was easy to follow with some easy examples. I would recommend a weak accept at this moment. Some additional efforts in the experiments (as I described above) would strengthen the contribution more.
review_title: null

Meta-review: In this paper, the authors proposed an offline policy optimization algorithm, motivated by an analysis of the upper bound error of importance sampling policy value estimator. Specifically, by the decomposition of the error in a particularly way, the authors identified some error which does not converge. Then, the authors introduce the contraints over feasible actions to avoid the overfitting induced by such errors. Finally, the authors tested the proposed algorithm empirically.

The paper is well-motivated and the authors addressed some of the questions in their rebuttals. However, there are still several issues need to be addressed, 

- The alternative practical estimator with plug-in behavior distribution would perfectly avoid the over-fitting, which is, however, ignored. This is an important and easy-to-implemented competitor.

- The pessimistic principle in the face of uncertainty (PFU) has been exploited extensively in offline policy optimization problem. How the proposed algorithm is connected to the PFU has not been discussed carefully, especially in terms of non-asymptotic sample complexity, which makes the paper is not well-positioned. 

- While the motivation is derived from the unbiased importance sampling estimator, the counterfactual risk minimization in Equation 7 is introduced suddently, without clear justification. 

- In my opinion, for a better clarification of the paper, the expressiveness of the policy family should not be discussed in this way. I understand the authors would like to avoid any possible degeneration, and explain the asymptotic lossless in terms of policy flexibility. However, the whole point of the paper is trying to introduce some mechanism to avoid the possible overfitting by regularizing the policy family. In other words, the restriction is on purpose and beneficial. I think the argument of policy family expressiveness should be re-considered and re-discussed. 


Minor: 

- Markovian vs. non-Markovian baseline comparison is not fair, and more comparison on well-known benchmarks, e.g., OpenAI gym, should be conducted. 
- The \sigma upper bound should be explicitly provided and verified in practice.

In sum, the paper is well-motivated, however, need further improvement to be pulished.
Decision: Reject