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: This paper studies value equivalence and considers the scenario where the agent limitations may entirely preclude identifying an exact value equivalent model, which immediately gives rise to a trade-off between identifying a model that is simple enough to learn while only incurring bounded suboptimality. To address this problem, the paper proposes an algorithm that iteratively computes an approximately-value-equivalent, lossy compression of the environment which an agent may feasibly target in lieu of the true model. It also proves an information-theoretic, Bayesian regret bound for the proposed algorithm that holds for any finite-horizon, episodic sequential decision-making problem. 

strengths_and_weaknesses: **Originality:** The paper seems to be original in the sense that it introduces an algorithm that implicitly identifies, in a purely data-driven and automated fashion, the resource limitations of the agent to facilitate tractable, near-optimal learning in what may otherwise be an intractable problem. Though I would like to note that I am not particularly familiar with this area of research.

**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 theoretical results in a very detailed manner and just went over them at a high-level.

**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 and proposed algorithm can be beneficial in the deep reinforcement learning setting. More on this can be found in the Questions section below.

questions: 1. On the significance of the theoretical results in terms of practicality in the deep reinforcement learning setting: Even though the theoretical results of this paper are interesting by themselves, I think that providing a brief section on how these results can at least help developing better deep RL algorithms (algorithms that work with high dimensional inputs) can significantly benefit the paper. Is it possible to provide a discussion on this?
2. On the significance of the illustrative example multi-resolution MDP: Is it possible to provide a discussion on why the MDP structure in example 1 is an important one? When does this structure become important? As far as I know, most of the MDPs of interest in the literature do not have this kind of a structure.

limitations: Yes the authors mention the limitations 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: In this paper the authors describe a new theoretical framework for exploration in RL. Their work builds upon earlier results on Posterior Sampling in Reinforcement learning. The main idea is to obtain posterior models which are compressed versions of the true MDP using the value equivalence principle as a distortion metric. By doing so they can harness the benefits of using value equivalent models and of posterior sampling. They provide a Bayesian regret bound for their method, which is the result of the regret caused by the use of a compressed model and that incurred while learning the model. 
strengths_and_weaknesses: The paper provides a solid theoretical framework for value equivalent posterior sampling in reinforcement learning. The recent success and simplicity of value-equivalent approaches provide motivation for such work. On the other hand, posterior sampling provides solid theoretical guarantees to the problem of exploration in RL. Studying the combination of the two approaches can be useful to the community.

The paper is well written / structured and provides a lot of additional analysis and discussion in the appendix. My main concern is described in the questions section to the authors. 

questions: My main concern is that it is not clear how this work can be useful in developing new algorithms even in simple tabular problems. The authors do not provide a practical instantiation of their method even in small toy domains and instead discuss the challenges of developing such an algorithm. This is different from standard PSRL. At the same time I cannot see how the results presented in this work can inform the design of better value equivalent algorithms which usually operate in high dimensional problems at scale (i.e. MuZero). Can the authors provide more insight on this ?
limitations: The authors have adequately addressed the limitations 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: This paper studies exploration in reinforcement learning from the Bayesian perspective, specifically adopting a Thompson sampling approach to obtain bounded Bayesian regret. The distinguishing factor in this analysis is the addition of a model compression component in which the user can accept a (tunable) amount of additional regret in exchange for simplifying the sampled model that must be solved in each iteration, potentially improving computational and/or sample complexity.
strengths_and_weaknesses: This paper moves the theory of efficient RL in an interesting direction with a novel combination of two existing ideas (PSRL and rate-distortion theory). I found it to be well-written and compelling. It is unlikely to impact practice, but it does contribute to our understanding of sample efficiency in RL, specifically by adding a tradeoff between optimality and model complexity.

--Originality--

The algorithm is clearly built upon the existing PSRL algorithm, which is fully acknowledged within the paper. The theoretical arguments are also built upon existing analyses using rate-distortion theory to quantify the simplification of the problem in a bandit context. The paper also fully acknowledges these connections.

I do think that the combination of these approaches is novel, worthwhile, and non-trivial.

The paper also does an excellent job of situating this work in the context of other theoretical results regarding efficient reinforcement learning. This occurs both in the main text and in an extensive appendix.

--Quality--

The findings in this paper are all theoretical in nature. The proofs seem well argued to me and I found no fault with them. That said, this is my first exposure to rate-distortion theory so it is possible that I would not detect a misapplication of those ideas.

--Clarity--

Overall, I found the paper to be well-written. As is typical for a theoretical paper, this paper is technically dense and requires close attention from the reader. Nevertheless, the authors have done a good job of surfacing their motivation, the core ideas of their analysis, and the potential consequences. I also appreciate the attention given to helping the reader develop intuition with rate-distortion, which is not as widely familiar to the ICML audience as other aspects of the work.

I do have one minor clarity suggestion: the paper currently uses R for both reward and rate-distortion; it might be better to separate the notation for those two concepts.

--Significance--

I think this paper tackles an important issue. The theory of efficient RL typically implicitly assumes that the agent is capable of learning a perfect model of and then perfectly solving an arbitrary MDP. It is refreshing to see theoretical work in this area that widens attention beyond this limiting assumption. It seems plausible that the framework used here could be built upon in future work to further study efficient RL with imperfect models, for instance considering different possible limits on agent capacity.

I will also say that it is not entirely clear what lesson to take from these results. The paper acknowledges that this algorithm is not practically implementable (not uncommon for a paper of this sort). But there is a high-level principle here that could inspire more practical approaches, namely that if you are careful, you can get away with simplifying the sampled model that you get from your posterior so it's easier to solve.

In all, I don't think that this paper presents a notably surprising theoretical result and certainly won't impact practice in the near term, but it does move the ball in an important direction.
questions: No questions.
limitations: Yes, I thought the paper did an excellent job of acknowledging limitations. For instance, it acknowledges a missing detail in the analysis (the form of a bound on information ratios). It is also quite forthcoming about the limited connection of the theory to practically applicable algorithms.
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: The authors introduce Value-equivalent Sampling for Reinforcement Learning (VSRL), an extension to Posterior Sampling for Reinforcement Learning (PSRL).

The key idea behind VSRL is to sequentially solve simplified versions of the true environment with the ultimate goal of minimizing the bayesian regret of the policy.

An information-theoretic analysis of VSRL is provided with regret bounds for the general case, the tabular setting, and an agent with limited capacity.
strengths_and_weaknesses: # Strengths

- The method proposed is well motivated and intuitive.
- It is supported by a thorough theoretical analysis, although regret analysis is not my area of expertise.
- The paper is mostly well written and has a nice flow of sections and ideas.

# Weaknesses

The authors do not provide any empirical evidence supporting their method. VSRL is framed as an algorithm for real-world high-dimensional settings where current agents may fail due to computational issues, but it is not even applied to a toy environment. Therefore, the reader is left at the stage of theoretical guarantees, with no actual idea of how to implement the algorithm, and how it would perform in practice.
questions: From what I understand, it is not trivial how to instantiate VSRL in practice. Could the authors think of a minimal example on which VSRL could be run? For instance, in the same vein as the experiments run in PSRL. Such experiments would definitely change my view on the limitations of this paper, which has already a strong theoretical foundation.
limitations: The main limitation of this paper is the absence of experimental results. The authors leave the application of VSRL to actual environments as future work, but in my opinion this work is incomplete without at least toy experiments demonstrating the usefulness of the approach.

The authors do not discuss potential negative impact of their work, but it is rather not applicable here since the paper is mostly about theory.
review_title: null

Meta-review: metareview: This paper studies a model-based reinforcement learning approach that is able to identify a model that is simple enough to be learned by a limited agent while incurring only bounded sub-optimality.
After reading each other's reviews and the authors' feedback, most of the reviewers' concerns have been solved and the reviewers agree that this paper deserves publication.
While preparing the final version of their paper, the authors need to consider the reviewers' concerns about the significance of the proposed approach and how the theoretical findings presented in the paper can inspire practical algorithms.
confidence: Less certain
Decision: Accept