All of the reviewers agree that this paper is both theoretically and modeling-wise a solid contribution to NeurIPS. My only concerns are that some of the author rebuttal points have not made it into the paper -- all of them should be added I think, in particular the related work (extended), the causal sufficiency clarification, and the run times.

The marginalisation of variables within some steps of an MCMC algorithm is delicate. The main proposal here appears well justified, but it would have been nice to see the argument made a little more explicitly. The type of marginalisation described here seems to be more or less what would be described as a (partially) collapsed Gibbs sampler in the sense of [David A Van Dyk and Taeyoung Park. "Partially collapsed Gibbs samplers: Theory and methods". It was less clear to me exactly how the "blocking" strategy detailed in Section 4.1 would be justified from a formal perspective, and I do think that this needs clarifying. I.e. the collection of variables to be sampled is divided into three parts -- x', x and theta and the decomposition of the kernel seems to involve sampling: x from a kernel invariant to its distribution conditional on both x' and theta (starting from the previous x) x' from a kernel invariant with respect to its distribution conditional only upon x (starting from the previous x') \theta from its full conditional distribution and it's not completely transparent how one knows that this is invariant with respect to the correct joint distribution.

This paper makes a solid contribution to improving inference in certain state space models that a used extensively in practice, particularly when implementing such models in a probabilistic programming language.

Additional Feedback: Overall, the paper addresses a very important issue into density estimation when contaminated by random outliers which is encountered in many machine learning problems. The theoretical guarantees for the linear and non-linear convergences rate and minmax bound is extremely useful for designing robust machine learning models. Unfortunately, I do not have the technical expertise to comment on the correctness of this approach. But for an out-of-area reviewer, I can see that this paper is well motivated and is written and structured well. As mentioned in my original review, experimental results with synthetic data could strengthen the paper and improve understanding of the paper, but it is not critical. The authors have explained using examples for potential applications for the theoretical results in Section 4.3 which seems good enough for me.

The reviewers agree that this paper would make a worthy contribution to NeurIPS. Please see the reviews for ways to improve the paper (especially regarding clarity and real world data). Experimental results with synthetic data could strengthen the paper but are not critical, if you think they could improve understanding of the paper, you might want to include it in the supplementary material.

In particular, the additional experiment on optimizing the dimensionality reduced functions for the real-world example looks quite persuasive, and the explanation about adding a dummy variable to address odd dimensional functions is also super valid. I also appreciate the authors for providing the detailed content of the modified paragraphs that they will include for the mathematical examples. The only small remaining issue is that for my point 6, the authors didn't seem to understand that the issue with Section 4.1 is that some of the sample points in the validation set may (almost) coincide with those in the training set, and the authors should make sure that they have excluded points that are sufficiently closed to the training set ones when generating the validation set, and clearly state this in the main text. That being said, I have decided to improve my score to 7 to acknowledge the sufficient improvement shown in the rebuttal. This paper considers the problem of dimensionality reduction for high dimensional function approximation with small data.

The paper proposes an interesting dimensionality reduction method for function approximation by generalizing linear level set learning methods to non linear level sets using the RevNet model structure and by introducing a loss function designed to give preference to functions that are sensitive only to few non linear coordinates. The paper is well-written and easy to understand. The methodology is clearly described and the experimental results are convincing.

Summary and Contributions: This paper provides a mix between discussing high-level conceptual ideas and perspectives and presenting a variety of experimental results, all under the umbrella of generalization in (Bayesian) deep learning. More concretely, the central argument of the paper is that Bayesian learning should be primarily viewed as aiming to marginalize over different plausible hypotheses of the data, intead of relying on a single hypothesis (which is what ordinary deep learning is doing). The ultimate goal is thus to accurately estimate the posterior _predictive_ distribution (over outputs), rather than to accurately approximate the posterior distribution (over weights). They thus recommend that Bayesian methods should ideally focus their efforts on carefully representing the posterior distribution in regions that contribute most to the predictive distribution. In this line of thought, they further argue that deep ensembles, one of the state-of-the-art approaches for obtaining well-calibrated predictive distributions, do effectively approximate the Bayesian model average (even if the individual ensemble members are not actually samples from the posterior), and thus should not be considered in competition to Bayesian methods.

I think that reporting it in the introduction is premature, I suggest to describe the meaning of the theorem without the statement.

The paper proposes an adaptation of the classical Q-learning algorithm with linear function approximation that enjoys polynomial sample complexity. All reviewers feel the paper contains interesting contribution to the RL literature that should appear in this conference, and I therefore recommend acceptance.