Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes the problem of minimax bias estimation of the value of a policy using offline data. The algorithm is based on marginal-importance-sampling and minimizing the Bellman residual error.
strength_and_weaknesses: Strength:

1) The problem of estimating the confidence interval of the value of a policy using offline data is very important. Since it is known that when the offline data is not exploratory enough, it is hard to get accurate point estimation, it's important to get good interval estimation.
2) The theoretical analysis of this paper seems to be sound, although I did not check the details.

Weakness:
1) I think the notation in this paper is a bit heavy and I found it a bit hard to understand all the details. I also think it would be good to move the actual algorithms to the main sections of the paper instead of putting them in the appendix.
2) It would be good to have some empirical evaluation.

There are a few places that I don't fully understand:
Page 8 Proof of Proposition 7.4: why does the Rademacher complexity of the unit ball in H of the order O(n^{-1/2})? I assume it should also depend on certain intrinsic dimension of the space H.

clarity,_quality,_novelty_and_reproducibility: As mentioned above, I think the clarity of the paper needs to be improved. The paper has some novelty. Since it is a theoretical paper, I don't see any reproducibility issues.
summary_of_the_review: I think this is a good paper overall. But I am not very confident in my review since I did not check all the details.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of offline policy evaluation (OPE) in the reinforcement learning setting without assumption that the offline data is well-explored. For such a problem, this paper characterizes the minimax estimation bias caused by the data distribution having a limited support. Moreover, the TV-norm of the Bellman error of the visitation measure gives an upper and lower bound of the bias. Based on that, this paper proposes an estimation method for estimating the bias, which is proved to be consistent. 
strength_and_weaknesses: Strength: This paper studies a theoretical problem that is more realistic in the sense that it does not impose a coverage assumption over the dataset. The notion of minimax bias seems interesting.

Weaknesses: I feel that this paper can be improved in the following aspects.

1. It would be great to have a more in-depth exposition of the minimax bias. First, it would be better to have a rigorous definition in the “definition” environment. Second, explain why it appears. Third, give a concrete example (maybe on a toy problem like bandit) to explain it. 

2. The authors seem to assume that $w^\sharp$ lies in a certain class such that the last term in (8) vanishes. The authors should state this matter clearly. 

3. Although the results seem interesting, I am afraid that the bound might not be useful. In particular, the TV-norm of $R_{\pi}$ seems a very conservative upper bound because $1/ (1- \gamma)$ is a huge number. That means, if $ R_{\pi}$ is not small, the confidence region can be vacuous. 

4. The theoretical analysis seems not so well developed. First, the TV-norm is not the exact thing used in estimation – an approximation via convolution norm is employed. We only know such an approximation is accurate when $u$ is sufficiently large. But how large should we need? What is the error when $u$ and $n$ are both finite? Second, the error analysis is merely asymptotic. From standard concentration results, one should be able to develop a non-asymptotic theory. 



clarity,_quality,_novelty_and_reproducibility: As I mentioned above, it would be great to present the minimax bias in a more in-depth manner. In addition, I feel that the assumptions about function class should be presented explicitly. Other than that, I feel that the presentation is pretty clear. 

The novelty seems not about theoretical analysis, but about proposing a new notion that captures the effect of insufficient data coverage in OPE. I feel that this notion can be quite impactful, but the current theory and understanding seems not deep enough. 
summary_of_the_review: This paper proposes a notion that characterizes the insufficient coverage of offline data in OPE. It also proposes a method to estimate such a quantity, which leads to a procedure to estimate a confidence region of the expected rewards.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies offline policy interval evaluation for discounted MDPs where the goal is to generate an interval that contains the ground truth with high probability. Specifically, this paper shows that, without the coverage and realizability, there exists a lower bound of the asymptotic bias. Then the paper proposes an interval estimation method that can output an asymptotically valid interval without the coverage and realizability assumptions. When the realizability assumption holds, the proposed interval is shown to be optimal. 
strength_and_weaknesses: Strength:
The problem itself is very meaningful and interesting. The setting where the commonly assumed coverage and realizability fail is very practical and worth investigation.
The theoretical results are well-structured. The role of each section looks clear.

---
Weakness: 
1. This paper fails to discuss a series of works that are very related to this one. OPE is an extensively considered problem studied by a variety of authors. Almost every part of this paper has some very related works. To be specific,
(i) It is already a well-known result that OPE incurs bias without the coverage assumption (e.g. [1]). [2] has conducted a bias as well as variance analysis for OPE of tabular MDPs years ago. The relation between the lower bound in this paper and hardness results from these papers should be discussed as they seem closely related to me. 
(ii) IS/MIS is a common technique for OPE, studied by, [3-5], to list a few. In particular, [3] gives the sharpest bound for tabular MDP under the coverage assumption. How does the bound compare to this paper?
(iii) Interval estimation is great. However, for some papers with point estimation, the results can be transformed into high-probability intervals (see for e.g. [7, 8] which considered the linear function case). [10] also consider OPE like this paper. Although this paper focus on the setting without coverage assumption, it is still necessary to investigate that, If under the assumption of coverage and realizability, how do these results compare to the interval in this paper?

2. There is no numerical simulation to justify the theory. It seems necessary to show exactly how this paper compares to other IS-based OPE methods for tabular setting with coverage assumption (e.g. [3]). 
Mathematics is heavy, but there is not enough explanation of the implication behind the theory. For example, why do we need two variants of Bellman equation; in the tabular setting, if the final bound does not depend on the cardinality of the state-action space, then which term characterizes the complexity.


---

[1] Wang, Ruosong, et al. "Instabilities of offline rl with pre-trained neural representation." International Conference on Machine Learning. PMLR, 2021.

[2] Mannor, Shie, et al. "Bias and variance in value function estimation." Proceedings of the twenty-first international conference on Machine learning. 2004.

[3] Yin, Ming, and Yu-Xiang Wang. "Asymptotically efficient off-policy evaluation for tabular reinforcement learning." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[4] Li, Lihong, et al. "Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms." Proceedings of the fourth ACM international conference on Web search and data mining. 2011.

[5] Li, Lihong, Rémi Munos, and Csaba Szepesvári. "Toward minimax off-policy value estimation." Artificial Intelligence and Statistics. PMLR, 2015.

[6] Thomas, Philip, and Emma Brunskill. "Data-efficient off-policy policy evaluation for reinforcement learning." International Conference on Machine Learning. PMLR, 2016.

[7] Duan, Yaqi, Zeyu Jia, and Mengdi Wang. "Minimax-optimal off-policy evaluation with linear function approximation." International Conference on Machine Learning. PMLR, 2020. 

[8] Min, Yifei, et al. "Variance-aware off-policy evaluation with linear function approximation." Advances in neural information processing systems 34 (2021): 7598-7610.

[10] Hao, Botao, et al. "Bootstrapping Fitted Q-Evaluation for Off-Policy Inference." International Conference on Machine Learning. PMLR, 2021.
clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is clear in general.Theorems have no ambiguity to me. However, I do not see enough explanation of the results. This is a mathematically heavy paper, and therefore it is necessary to give explanations for its results and definitions.

Quality: The mathematics seems rigorous, though I did not check all the details.

Novelty: The technical novelty is unclear given the current presentation. The paper does not compare its bound with related works either theoretically or empirically. 

Reproducibility: There is no empirical results to reproduce.

summary_of_the_review: My current recommendation is reject. 
The paper indeed considers an important problem and a meaningful setting. But my major concern is that the contribution and significance of the paper is unclear.

The details are as follows:
There is a lack of comparison with closely related work.
Not enough explanation of the results. It makes this paper hard to understand for readers who are not very familiar with this exact topic.
No empirical evidence to show the validity of the proposed algorithm. 
Overall, I think a significant amount of modification is needed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied policy value interval estimation problem given offline data without sufficient coverage and without realizability assumptions. The authors showed that without coverage assumption there would be an ``irreducible bias'' and therefore, proposed a new problem setup called minimax-bias OPI, which targets at estimating (near-)optimal (shortest) interval covering the true value $J(\pi)$ with a shift at most at the level of the minimax bias. After that, in Sec. 6, they suggested an objective function to compute a near-optimal interval, which is also robust to the misspecification error of function class. Finally, in Sec. 7, they proposed how to computably approximate the solution of the objective function and established asymptotic guarantees.
strength_and_weaknesses: ### Strength

The method and analysis in this paper is interesting and inspiring. The new problem setup minimax-bias OPI is well-motivated, and it's nice to see their methods does not require the common assumptions in previous literatures to ensure the validity.


### Weakness

The final results in Sec. 7 is just an asymptotic guarantee and it is unclear about the convergence speed. Especially, it's unclear how well $||P||\_u$ approximates $||P||\_{TV}$ when $u$ is large but not infinite.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written. The proof seems correct to me.
summary_of_the_review: This paper has many interesting results. Although there is still some limitation, I would suggest the acceptance of this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: While the reviewers like the problem studied in the paper and believe there are new and interesting ideas in this work, they do not see the contributions of the paper significant enough for acceptance. The paper is theoretical and there is no experiment to support the findings and to provide a comparison with the existing results. However, the theoretical results are rather limited and do not properly address any of the critical problems in OPE. I agree with the reviewers that the paper is not ready for publication at its current form, but I think it is promising. I would strongly recommend that the authors take the reviewers' comments into account, improve their work either with better theory or a proper mix of theory and empirical evaluation, and prepare it for an upcoming venue.  
justification_for_why_not_higher_score: Lack of empirical evidence and insufficient theoretical findings.
Decision: Reject