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: The paper discusses the notion of _approximate value equivalence_ in model-based reinforcement learning. Approximate value equivalence is concerned with the study of families of models that yield $k$-step Bellman updates that are approximately equivalent to the Bellman update yielded by the true model, in the sense that---given a policy $\pi$ in some set of policies and a value function $v$ in some set of functions---$\tilde{\mathcal{T}}^k_\pi v\approx\mathcal{T}^k_\pi v$ (here $\tilde{\mathcal{T}}_\pi$ and $\mathcal{T}_\pi$ represent, respectively, the approximate and exact Bellman operators). The paper provides a number of results that relate different families of models in terms of the error that they incur in terms of Bellman updates. 
strengths_and_weaknesses: *Strong points:*
* The problem addressed (understanding how approximate models impact the error incurred in the computation of the value function in RL) is important and interesting;
* The presentation is very clear, well-organized, and several of the results are quite intuitive.

*Weak points:*
* The article is not self-contained, in the sense that most of the less intuitive results are presented with no hint on the proof. The paper still has available 1/2 page that could be used to provide even if a one-liner hint on how the result is established.
* It is not clear what's the practical use of the proposed bounds. The authors make an effort in Section 5 to discuss this issue, but I believe that this is a core point in assessing the significance of the contributions of the paper. In particular, the provided bounds depend critically on the distance $\beta$ and the minimum tolerated error $\mathcal{E}_\epsilon$, but---as far as I can understand---these are very difficult to assess in practical scenarios (particular in scenarios involving high-capacity approximations). Therefore, it would be important to discuss, in light of this, the practical use of the provided bounds.

questions: My main question is related with the practical use of the bounds provided in the paper, in light of the difficulty of determining the factor dependent on the distance/divergence $\beta$, and the minimum tolerated error $\mathcal{E}_\epsilon$.
limitations: N/A.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes approximate value equivalence (AVE) which extends the previously proposed VE formalism by replacing equialities with error tolerances. With this extension, it shows that AVE models with respect to one set of functions are also AVE with respect to any other set of functions if a high enough error is tolerated, which then allows for deriving bounds on the performance of VE models with respect to arbitrary sets of functions by relating them to a particular model class with known performance guarantees. Finally, the paper supports these results by providing intuitions and discussions of their implications.
strengths_and_weaknesses: **Originality:** The paper seems to be original in the sense that it extends the previously proposed VE formalism by replacing equialities with error tolerances and that it develops a whole variety of new theoretical results out of this. I am not aware of any study that does this. The related work section also seems to cover the related studies in the literature.

**Quality:** Overall, there seems to be no serious quality issues with the paper. Though, I would like to indicate that I haven’t checked the proofs in a very detailed manner and just went over them at a high-level. The submission looks technically sound and the core ideas are well-explained. However, I do have a few major and (mostly) minor questions on the quality of the paper (see the Questions section below). 

**Clarity:** I found no problems with the clarity of the paper. The paper is very well-written. I have nothing to suggest.

**Significance:** Even though the derived theoretical results seem to be interesting in their own sense, I would like to indicate that I found the paper to have problems in the significance of the results. More specifically, I am not sure if the paper provides enough discussion on how the derived results can be helpful in developing VE MBRL algorithms. More on this can be found in Question 2 below.

questions: **Major:**

1. On the role of the deterministic policy set in PVE classes: Why does the PVE class wrt all deterministic policies contains only models which can plan optimally (see the last par. of Sec. 2)? I mean what is the role of determinism here? Why doesn’t the PVE class wrt all policies (including deterministic and stochastic ones) contains only models which can plan optimally?
2. On the significance of the theoretical results in terms of practicality: In the previous studies of Grimm et al. (on VE), the authors have provided experimental results that either justify the usage of VE models or improve the currently existing algorithms. However, in this study there is no empirical demonstration of the usefulness of the theoretical results. Even though the theoretical results are interesting by themselves, I think that providing a section on how these results can at least help developing better VE MBRL algorithms can significantly benefit the paper. Is it possible to provide a discussion on how these theoretical results can be useful in giving rise to new algorithms?

**Minor:**

1. In Def. 1 and Property 1, $\mathcal{V}$ should be a subset of $\mathbb{V}$?
2. I think the par. that starts with line 164 should explicitly mention that a certain amount of error will be tolerated for $\mathcal{M}^{\infty}$. I had to read it several times to get this part.
3. In Prop. 2 should it be $\mathbb{V}_{\mathbb{\Pi}}$ in the upper bound?
4. Why is there $2^{\mathbb{V}}$’s in line 242? Shouldn’t these be $\mathbb{V}$’s?
5. There is a typo at line 257 right after the second column.
6. There seems to be a typo inside beta in Eq. 18 where one of the value functions should not have a hat?

If the authors are able to address the concerns provided in this review during the rebuttal period, I am willing to raise my score.

limitations: Yes the authors mention the limitations of their work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper extends the notion of "value equivalence" among MDPs w.r.t. sets of policies and value functions (and number of steps) to "approximate value equivalence," that permits the values after k steps of the policy to differ by  up to some parameter epsilon. It is then possible, for any two classes of models, to find an epsilon for which the models satisfy the definition. Bounds that relate the performance of policies across such approximate value equivalent models are also obtained.

strengths_and_weaknesses: It seems clear that for the kind of models studied here, we need bounds that control how close the predicted performance is to performance in the actual environment, and it seems desirable to be able to obtain this for bounded orders. This is the main strength of the paper. 

The notion of approximate value equivalence is a very natural generalization of the notion of value equivalence -- indeed, it borders on being "obvious" given the existing notion of value equivalence. I am not so moved by the results about relating arbitrary pairs of classes. I don't see the utility of this notion for such large values of epsilon as such relationships would require -- and indeed, intuitively, we would not expect totally arbitrary pairs to be "equivalent" in any meaningful sense. This dampens the significance of these contributions.

What's really missing from this work is evidence that the definition can be made to do useful work for us. I'd want to see it used to analyze an algorithm or show that some MDP can be represented more compactly, or something of similar flavor.

questions: Can you point to evidence that it is productive to consider this notion? (See the last part of "Strengths and Weaknesses" for a couple examples of what this might look like.)
limitations: This is fine.
review_title: null

Meta-review: metareview: A key discussion point in the rebuttal phase was the practical use of the proposed bounds, which two of the three reviewers brought up. The authors in response added an additional section (Section 6) and experiment to address this concern. While some concerns regarding the practical use of these bounds remain, the authors have made a sufficiently convincing case in my view. Hence, I recommend acceptance.
confidence: Less certain
Decision: Accept