Venue: NeurIPS 2022 Conference

Reviews:

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: The authors provide finite sample Lp rate guarantees for q function estimation via minimax objectives. Unlike prior work they manage to prove guarantees with only realizability assumptions. Prior works obtained such results only for policy evaluation but not q function estimation. Or required function spaces for the adversarial weights that are too expressive to leverage statistical power.

strengths_and_weaknesses: I found the theory interesting and well presented. The results could be of interest to the community of offline RL.

My main concerns are:

why would one estimate a q function other than in order to estimate an offline policy value. Please provide more motivation as otherwise the results are covered by prior work.

why are you restricting to finite action and state spaces. Given all your realizability assumptions it would seem that this is an overkill and defeats the purpose. These function approximation would be primarily most powerful with continuous states/actions.

it is very unfortunate that only slow rates are obtained. Hence even for finite hypothesis spaces one gets n^(1/4) rates. Such realizability guarantees and also the absence of ill-posedness in this inverse problem should be leading to fast rates. See for instance the un-cited work of Chen and Qi: https://arxiv.org/abs/2201.06169 Please relate to this work in your response as it is highly relevant.
why are you only giving bounds for finite hypothesis spaces. This is very restrictive.
questions: it seems that many techniques are already existent in the prior work of JHHJL22. If one ignores the extension to measuring dists and just looks at RMSE, then can you elaborate on what new you are bringing on the technical side
limitations: Given that this is mainly a theoretical contribution, the above points would need to be addressed before publication.
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 studies the problem of learning the Q-function and density ratio for a given policy in offline reinforcement learning settings, where we have IID state, action, reward, next state tuples collected from the stationary distribution of some behavioral policy. They argue that in past work the focus has been on guarantees on the accuracy of policy value evaluation using estimates of these functions, rather than guarantees on the accuracy of the estimates of these functions themselves. The authors propose a new more general framework for regularized estimators of these functions, and provide guarantees on the L_2 error of the resulting estimates under any given distribution of state/action values. In this analysis, they provide some theoretical results which suggest that, using novel forms of regularization targeted towards some given distribution, they can likely achieve lower L_2 error w.r.t. that distribution. Finally, they test their theory with some simple synthetic experiments.
strengths_and_weaknesses: Edit: see follow up discussion below for updates on these points

Strengths:
- The theory is very clean and easy to read / understand
- They provide a nice, more novel framework for Q-function and state density ratio estimation, with very strong theoretical guarantees for these tasks
- Their experiments are clean and well presented, and make a reasonably strong case that their novel regularization is good at reducing L_2 error under the target distribution of interest
- Despite the weaknesses described below on the impact of this work, one positive impact is that it allows a strong relaxation of the identification conditions needed by existing minimax methods for Q-function and state density ratio estimation used in the OPE literature, which is significant.

Weaknesses
- The problem of needing to obtain strong guarantees on the accuracy of Q-function and state density ratio estimates is not very well motivated. As the authors point out, the main way in which these functions are used in practice is for policy value estimation, which is already very well studied in past work with guarantees for the actual task of interest. The authors mention for example that learning these functions can be used as sub-routines for other RL tasks such as actor-critic methods, but they do not provide much/any detail about this.
- Related to and expanding on the previous point, since learning the Q-function or state density ratio is not particularly useful in and of itself, it is disappointing that they do not show show that improved performance in learning these functions can actually translate to improved performance in downstream tasks where they might be used. For example, they could provide either: (1) theoretical results that show that realizable versions of their proposed estimators can give improved guarantees for downstream tasks; or (2) empirical results that show that their proposed estimators can improve the performance of downstream tasks in practice. Without either (1) or (2), or something similar, it is not clear that the work is actually high impact.
- Similar to the above two points, it is also not very clear how useful it is to be able to guarantee low L_2 error under particular target state/action distributions. For example, in the introduction they note that “downstream learning algorithms that use off-policy function estimation as a subroutine often assume the estimation to be accurate under certain specific distributions”, but unless these are fixed, known distributions it is not clear how their theory can be utilized, since they can only provide error guarantees w.r.t. fixed, known distributions. Again, without more analysis about how their theory can actually improve downstream tasks the impact is hard to assess. A concrete and detailed example case study of the use of the theory would be very helpful with these issues.
- The results about how novel (s,a)-specific forms of regularization can improve performance is fairly heuristic. For example, they suggest using $f_{s,a}(x) = \frac{1}{2}(x - \hat q^\pi(s,a))^2$ for Q-function estimation, where $\hat q^\pi$ is some first-stage estimate of the q function, which they argue results in zero error when the first-stage estimate is perfectly accurate, but they do not provide any actual concrete bounds on the resulting L_2 error given provable bounds on the accuracy of $\hat q^\pi$. Similarly, in their experiments they do not test these novel regularization methods with actual first-stage estimation of $\hat q^\pi$, but only with artificial error added to $q^\pi$, which makes the empirical usefulness of this novel regularization difficult to assess.
- There are several trivializing assumptions made, including: (1) finite state space; and (2) finite function classes. While it is true that often extending results using finite function classes to infinite ones using e.g. VC-dimension or Rademacher complexity is straightforward, this is not necessarily always the case (or at least making this exertion is sometimes less straightforward or requires additional assumptions), so not including more general results is definitely a weakness. Similarly, is there any reason why the state space was assumed to be finite? This is an unrealistic assumption in many settings, and none of the results depend on the size of the state space, so if there are any theoretical reasons why the theory doesn’t naturally extend to infinite state spaces this should be made clear. Similarly, the iid data assumption is generally unrealistic, although I am more sympathetic there since it is usually trivial to replace e.g. concentration inequalities, CLT, etc. with corresponding Markovian versions given mixing assumptions; however, there should at least be some discussion in the paper about this.
questions: Questions/Comments below:
1. Saying that estimating the Q-function / state density ratio is “Off-Policy Evaluation” is confusing and contrary, I believe, to most of the literature. Usually, OPE refers specifically to what you call “return estimation” in section 1. I think it is worthwhile making the language use more clear in title/abstract/intro, and making it more clear that the focus of the paper is NOT on performing OPE, but rather on the related task of estimating value / weight functions, which can be used as a sub-routine for OPE (or other RL tasks).
2. $d^D$ on line 57 of the introduction is not defined yet at that point.
3. Lines 149-150: you say that “even estimating a single constraint is infeasible as that requires sampling from the same state multiple times”, but it seems like for any given (s,a) the constraints should be identifiable, since the distributions of r and s’ given (s,a) under the observational distribution should be identifiable. Therefore I’m not clear what you mean by this. This requires more detail / explanation.
4. On line 205 (and later), I assume that $f’_{s,a}$ refers to the derivative of $f_{s,a}$? This notation is currently undefined and should be made explicit.
5. In figure 2, it is not very clearly explained what is going on with the “model” data. I think based on the parantheses in the text these are showing results where we use $\tilde q$ as the estimate rather than using your regularized estimator? This should be more clear.
limitations: Issues with limitations already addressed in the strengths/weaknesses section. No negative societal impact issues that I think need to be addressed.
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 studies estimating Q function in the offline setup. The state-action space is assumed to be discrete and the performance of the estimation is measured under a user-specified measure that can be different from the data distribution. The major caveat stems from the distribution shift and existing results requires completeness and realizability assumptions. This work proposes a Lagrangian method and provides statistical guarantees in the absent of completeness assumption. The analytical framework is further extended to weight function estimation.
strengths_and_weaknesses: Offline off-policy evaluation is a very important problem in RL and has many applications across various domains. The paper focuses on addressing the change of measure issue between evaluating and sampling distributions. Moreover, the paper only needs realizability assumption. Both of these advances are important in off-policy evaluation. There are many existing works studying off-policy evaluation and to my knowledge, the proposed method here is new.

The paper is relatively easy to follow, with some minor issues on notations. The result seems correct and sound, although I have not checked the detailed proofs.

I will discuss some weaknesses in the questions and limitations section.
questions: The Lagrangian form in Equation (4) is obtained from the convex optimization problem in (3). Do we gain any intuition from writing out this convex program? In fact, we can directly use $f_{s, a}$ as a regularizer and obtain Equation (4). On the other hand, there seems to be multiple ways to formulate a Lagrangian function, e.g., we can use a weighted quadratic penalty term $w(s, a) (r(s, a) +\gamma q(s', \pi) - q(s, a))^2$. Does the linear penalty in the Lagrangian form work better? Intuitively speaking, quadratic term is naturally related to penalized least square estimation.

How does Assumption 3 compare to concentrability conditions commonly used in RL literature, which assumes the ratio of visitation measure is bounded? In addition, [DJW20] uses a restricted chi-square divergence term to measure the distributional shift. They showed that the restricted chi-square divergence is tighter compared to density ratios. Can authors also comment on the connection between restricted chi-square divergence to $w_f^*$?

I am also curious about any connection to "Bellman-consistent Pessimism for Offline Reinforcement Learning", where an information theoretic confidence set of Q functions is constructed using offline data. The primary goal is different -- policy learning in the Bellman-consistent paper, however, they still obtain an estimation of Q function.

limitations: I don't see very obvious limitations in the paper, comparing to concurrent theoretical studies of RL. As mentioned, the assumption on weight function $w_f^*$ may be a bit strong.

The authors discussed the barriers of obtaining faster rate $n^{-1/2}$ in Appendix, which mainly owes to the regularity of the Lagrangian function. I am interested in whether the $n^{-1/2}$ rate is ever possible with novel techniques.
review_title: null

Meta-review: metareview: The authors provide slow rates for Q-function estimation based on minimax objectives. The contribution is technically solid, but seems somewhat incremental and even though the authors provided responses to all major reviewer concerns, there is still concern by reviewers of the applicability of their result and the incrementality. 

Despite this it seems a solid contribution to the RL literature.
confidence: Less certain
Decision: Accept