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 authors focus on improving the performance of reinforcement learning algorithms in the presence of multi-fidelity data through the use of control variates. 
 
strengths_and_weaknesses: ## General Comments
I really like this paper, and hope that it gets accepted.  However there are a few, hopefully easy, problems that the authors need to address. First the literature review needs to be expanded to include background from variance reduction in classic RL, and asymmetric RL. Second, the assumptions and discussion surrounding policy iteration need to be more explicit in the main paper, or pointed to in the appendix. Lastly, they need to include, potentially in the appendix, other baseline algorithms in the NAS example. If these problems can be addressed in the rebuttal  period, I will increase my score. 

## Strengths
1. This is actually a really clearly written paper that I enjoyed reading.
2. I think that the area that it considers is an important one.
3. The experiments are clearly presented, and the weaknesses of the work, as well as their strengths are discussed in detail. 

## Weaknesses
1. The authors seem to ignore the full literature surrounding the learning of baselines in general reinforcement learning which I think does not set the right context for why the question the authors answer is interesting. 
2. Also ignores recent work in asymmetric reinforcement learning, which I think would benefit the larger story and analysis. Especially in connecting, in a more principled way, low fidelity and high-fidelity simulation. 
3. The NAS experiments do not include other baseline algorithms. Though I am not familiar with this specific benchmark, I have no doubt there are other algorithms which should be included to give a point of reference for what the gap between RL based methods and other methods is. 
4. The authors seem as though they are not being fully transparent about the types of MDPs for which this algorithm can currently be configured with. Does it only work with low-dimensional state-action spaces and toy problems, or can it be configured with more difficult continuous control tasks? 
5. The discussion and assumptions surrounding the policy iteration alluded to in section 3.3 was basically non-existent. For better clarity it seems like a more explicit discussion should be included (either in the main paper or the appendix). 
questions: ## Preliminaries and related work
1. "It is well known that there exists at least one optimal policy π∗ such that Vπ∗ (s) = max π Vπ (s), ∀s ∈ S and Qπ∗ (s, a) = max π Qπ (s, a), ∀s, a ∈ S × A [ 2]. Furthermore, a deterministic policy that selects the greedy action with respect to Qπ∗ (s, a), ∀s ∈ S, is an optimal policy." -- If you make statements please include a citation. I believe that a good reference for this statement would be (1).
2. "Applications of the method of control variates extend beyond variance reduction. For example, the concept of control variates is used in [ 27 ] to design a fusion framework to combine an arbitrary number of surrogate models optimally." --Also the notion of a baseline in reinforcement learning has been well studied since the inception of policy gradient methods (2). The literature surrounding baselines should be mentioned if you are talking about variance reduction in RL methods (3,4).
3. "In [1], a policy search algorithm is proposed that leverages a crude approximate model ˆP of the true MDP to quickly learn to perform well on real systems." -- Can you state explicitly the policy search algorithm that is used. 
4. "From an optimization viewpoint, this approach is reasonable only if the lower-fidelity value function lies in the vicinity of the optimal high-fidelity value function, a situation that cannot be guaranteed or known a priori in general." -- can you make this more explicit? Do you mean that it is close in terms of the true value function under co-simulation between low-fidelity and high-fidelity models?
5. It seems like this work is deeply related to asymmetric learning algorithms (5,6). Can you comment on the connection to this sub-field and how it relates to your work? It seems as though your analysis might benefit from viewing the low-fidelity process as a POMDP, and the high-fidelity process as the true underlying sequence of states.
 
## Multifidelity estimation in RL

1. "High-fidelity environments usually capture more state information than do low- fidelity environments so T can be a many-to-one map" -- It seems like this would imply that the state-space would be implicitly or explicitly larger, which you would imagine might actually slow down learning. Can you comment on this?
2. "Notice that G hi and G lo are correlated r.vs. in this multifidelity setup" -- This is only true for the first step of the monte-carlo rollout of the low fidelity simulator though. Meaning that for t > 0 all rewards could be de-correlated and the level of correlation of G should be dependent on the discount factor which close to 1 becomes vanishingly small.  Is this correct? 
3. Equation 7 implies that you are able to exactly estimate Q in the low-fidelity simulator which seems unrealistic in general. Is this the case, or did I misunderstand the notation?
4. Please include a reference for the policy improvement theorem in 3.3.2 as it does have some requirements that I am unsure are met in your setting. Depending on the variant (e.g. are we looking at exact policy iteration, asynchronous policy iteration or approximate policy iteration? 
5. " This assumption basically ensures that all actions at the target state shi have been explored equally well and enables us to make fair comparisons about estimator performance." -- This statement seems inconsistent with the message expressed earlier which was that your algorithm in fact addresses the exploration issue in systems where correlation in the expected reward ahead is high between high and low fidelity simulators.  

## Numerical experiments
1. Where are other common baselines for the neural architecture search? I appreciate the need to compare over the non-variance reduced baseline, but it seems like having examples from other algorithms in the paper is necessary to see exactly where this technology stands with respect to the larger NAS literature. 
2. What were the relative clock-times of NAS with and without the control-variate schemes? Were they comparable?
3. The plot for figure 3 seems incorrect as for the non-variance reduced algorithm the standard deviation does not fully overlap the mean, are you sure you did not report the mean and two quantiles? 

## Citations mentioned
(1) Bertsekas, Dimitri. Reinforcement learning and optimal control. Athena Scientific, 2019.

(2) https://people.cs.umass.edu/~barto/courses/cs687/williams92simple.pdf

(3) https://proceedings.neurips.cc/paper/2010/file/35cf8659cfcb13224cbd47863a34fc58-Paper.pdf

(4) https://arxiv.org/pdf/1506.02438.pdf 

(5) https://arxiv.org/abs/1710.06542

(6) https://arxiv.org/abs/2012.15566
limitations: The major weakness mentioned by the authors is the setting when the correlation between low fidelity and high-fidelity simulation is low their variance reduction algorithm can actually perform worse then the baseline. I again think that the authors need to include other baselines to give an idea of how performant their algorithm is by comparison. It need not beat these other algorithms, but other standard baselines (especially on NAS) should be included.
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: 
The paper presents a new methodology for multi-fidelity RL by leveraging low-fidelity data to decrease the variance in the MC-estimates of the value function.  The new algorithm, MFMCRL, leverages theory from control-variates to decrease the variance based on the observed correlation fbetween the high and low value returns.  This is a different approach than existing MFRL techniques that choose which simulator to gather data from and need bounds on the relationships between the simulators.  Theoretical results quantifying the improvements from this approach in both policy evaluation and policy improvement are derived.  Empirical results are presented with synthetic MDPs and in a NAS (hyperparameter tuning) environment.

strengths_and_weaknesses: Overall I think this is a very clever idea and a nicely scoped paper.  The approach is novel compared to existing MFRL techniques in that it takes a very different approach to gathering data.  There are places though, where I think the paper needs to be more precise in its terminology and also point out some disadvantages of the current formulation with respect to prior MFRL work.  Details below:

More precise terminology needed:
The assumption of independence at line 110 (when i != j) and the related covariance construction in (11) are very confusing to me.  I and j here are indexing two different sets (the high fidelity and low fidelity one) from what I can tell where each element is the return of a trajectory in the related MDP.  So there are n trajectories from Lo and n from high, right?  In that case, isn’t there likely non-zero covariance between lots of these trajectories?  That is, a rollout of the same policy in these two similar MDPs will produce correlated returns – if half of them take a right turn (stochastically) then we should expect 50% of the trajectories in Z to be correlated with another 50% in W.  So why would we expect 0 correlation just because the indexes don’t match?  What is special about two matching indexes (Z_i and W_i)?  Can the authors provide a concrete example showing why we would expect i != j to be important?

I was surprised the environment setup in Section 2.1 requires an episodic domain and specifically one with terminal states.  Is this necessary for the algorithm / analysis because it is based on MC sampling and are there natural extensions to non-episodic domains.

The sentence starting on line 120 could use a citation.

Line 199 – A  note should be made here about why the new approach needs to use (inefficient) MC returns instead of utilizing bootstrapping in learning the value function.  I presume since the latter is a biased estimator it is not usable in this framework.  That is fine, but the point should be made directly here.

I think the pseudocode block from the appendix needs to be in the main paper.  The current description of the algorithm in the main paper is not really usable without it.  If this paper gets accepted I suggest using the extra page to include that. 

On potential disadvantages with regards to previous methods:
I agree with the authors that the new approach has fewer assumptions about prior knowledge compared to previous MFRL methods. Being able to learn the correlations between the environments is a nice improvement.  But there are other dimensions where the current approach is not as efficient or flexible as previous MFRL approaches and those should be called out directly in the related work comparison.  Specifically (1) the current work always assumes there are only 2 environments (low and high) while previous work considered any number of environments – can the new framework accommodate multiple low-fidelity environments?  If so or if not this should be mentioned. (2) The new framework is doing value-based RL using MC returns, which is likely going to be very inefficient compared to the model based approaches used in prior work and (3) The authors make a point about not needing to use more complicated exploration strategies to decide what environment to sample from, but that will lead to inefficiencies.  The current approach will sample from both Low and High on every iteration, which could be very costly, whereas previous MFRL approaches only sample from High when they feel they are “ready” to take on the high-fidelity environment.  So yes, the new approach will be more sample efficient than only sampling from High, but it seems it will be much less sample efficient than previous MFRL approaches in terms of sampling the highest fidelity environment.

questions: Can the authors provide a more precise description of the i != j covariance construction and why the indexes should match up?

Why is the analysis restricted to only domains with terminal states?

Can the authors comment on the dimensions [(1) (2) and (3) in the final paragraph above] where the new algorithm may not be as strong as earlier MFRL methods?
limitations: As mentioned above, while I think the new approach has a benefit of requiring less strict knowledge about the relationship between low and fidelity environments, there seem to be areas where the new approach is not as strong as prior approaches.  These specific areas are (1) accommodating more than 2 environments, (2) losing sample efficiency by learning from MC returns rather than doing model based learning, and (3) not actively choosing which environment to sample, which will not be as efficient in querying the expensive high-fidelity environment.  If these limitations hold with respect to prior work they should be mentioned in the paper.
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: The paper is framed in the setting of multi-fidelity Reinforcement Learning (RL), i.e., the setting in which multiple instances of the environment are available, each with a different accuracy on the reward function and transition dynamics. Specifically, the paper considers the presence of two instances (an exact one and an approximate one) and proposes an approach to effectively exploit this opportunity to improve the estimation of the value functions. In particular, by assuming that the reward random variable of the two environments are correlated, a suitable control variance is exploited to reduce the variance of the estimate and achieving smaller sample complexity. A theoretical analysis is provided, showing results regarding the accuracy of the value function and of the greedy policy. An experimental evaluation on both synthetic domains and on a NAS (neural architecture search) is provided, highlighting the advantages of the proposed approach.
strengths_and_weaknesses: - The main strong point of the paper is the fact that it addresses a very relevant topic, i.e., multi-fidelity RL, that emerges in several real-world applications.

- [Novelty] The approach proposed in the paper is novel per se, although it can be considered an application of the control-variate techniques to the multi-fidelity setting. The theoretical evaluation is novel and succeeds in showing some advantages of the proposed approach (although I have some concerns that I will detail below)

- [About Correlation of the Rewards] The crucial assumption that makes the proposed approach work is that the reward random variables collected in the high-fidelity and low-fidelity environments in the same state are correlated in a statistical sense (i.e., with a non-zero correlation coefficient). This is quite different from the usual idea of fidelity in multi-armed bandits (e.g., "Kandasamy, Kirthevasan, Gautam Dasarathy, Barnabas Poczos, and Jeff Schneider. "The multi-fidelity multi-armed bandit." Advances in neural information processing systems 29 (2016).") in which the fidelity is represented as a bias on the expected reward (so, it is not a correlation in the statistical sense). Consequently, in order for the approach to make sense, it must be that the reward is stochastic given the current state and action. It seems that the approach cannot be applied to rewards that are deterministic functions of the state-action pair. Indeed, in such a case, there would be no correlation. Requiring correlated reward random variables seems quite restrictive in my view. Can the authors elaborate on this point?

- [Estimation of $Q^{lo}_{\pi}$ ] As the authors acknowledge, in order to compute the control variate, it is necessary to have access to the value of the true low-fidelity value function Q^{lo}_{\pi}. This is not available in practice. The authors propose to collect a large number $m$ of return samples from the low-fidelity environment. Although $m$ can be chosen to be large (assuming that the cost of collecting samples in low-fidelity is negligible), it represents a further source of uncertainty that will impact the computation of all the relevant quantities. Moreover, in the control variate, the covariances and the correlation coefficient are estimated from samples as well. Are these further sources of uncertainty accounted for in the theoretical analysis of Section 3.3?

*Overall*
The paper has some novelty and the experimental results, although limited to one realistic environment (and some synthetic ones), show some advantages of the proposed approach, I think the paper is currently borderline. I would appreciate it if the authors could clarify the concerns about the formulation of the fidelity (i.e., the correlation between the random variables).
questions: I would appreciate it if the authors could clarify the issues [About Correlation of the Rewards] and [Estimation of Q^{lo}_{\pi}]. Furthermore, I add some minor questions:

- In Section 2.1, the authors require the state and action spaces to be finite. Is this a crucial assumption? Can the approach be employed in continuous state-action spaces?

- In real-world applications of multi-fidelity RL, is it reasonable to assume that the mapping function from high-fidelity states to low-fidelity states $\mathcal{T}$ is known?

- Is the assumption that the low-fidelity environment admits a generative model-kind of interaction crucial for the approach? On the one hand, I guess it is because this is exploited for estimating the true value of  $Q^{\text{lo}}_{\pi}$. Can the authors elaborate?
limitations: The limitations and impact of the paper are properly addressed by the authors.
review_title: null

Meta-review: metareview: All reviewers agree on the novelty and significance of the topic addressed by the paper and feel that the paper is at the borderline of being ready for publication. But in the end, as visible in the lengthy comments and discussions about the paper, there are too many details and clarifications missing in this paper to push it solidly across the acceptance threshold. Given all the technical discussions, the authors should be in an excellent position for a significantly improved resubmission in the future.
confidence: Less certain
Decision: Reject